A router can learn the routes to remote networks and subnets using manual instructions or by means of configuring routing protocols. This way routers learn how to reach destination networks/subnets dynamically. This post's primary focus is about Interior Gateway Protocols (IGPs) such as: RIP, OSPF, EIGRP. The only Exterior Gateway Protocol (EGP) we use nowadays is called BGP.
First things first. There are three terms I need to define in order to explain the process of selecting the best route. These are:
The Longest Match Rule
When a router receives a packet, while processing the header, it is the DESTINATION IP address that is compared with the entries in the routing table in order to determine the next step.
This next step is to find the egress (outbound) interface and the address of the next device to send the packet to. This form of routing is known as the destination-based routing.
The process of comparing the destination IP with the prefixes int the routing table is done bit by bit (yes, routers see IP addresses in the binary notation).
The entry that has the longest number of network bits that match the IP destination address is always the best match (best path).
This is always the FIRST thing a router checks.
If there is ONLY ONE best match, a router has a simple task to do. It moves the packet to the outbound interface (egress) and encapsulates the packet in the layer 2 header according to the technology/protocol that is used on the outbound interface (Ethernet, PPP, HDCL, Frame-Relay etc.). Then, the frame is converted to bits and placed onto the wire/fiber optic cable.
NOTICE!
If the outbound interface is a multi-access interface (such as Ethernet, Frame-Relay, ATM etc.), the router must know the layer 2 identifier of the next-hop device (layer 3 to layer 2 address resolution). For instance, in case the outbound interface is Ethernet, the MAC address of the next-hop device must be in the router's arp cache (if not found, the arp query is sent). In case, the egress interface is of a point-to-point type (subinterface point-to-point or protocol such as PPP, HDLC etc. is used), there is NO layer 3 to layer 2 resolution being performed. The packet is simply encapsulated in layer 2 frame sent out that interface.
Let's consider the example depicted in pic. 1.
In this example the router receives an IP packet. The DESTINATION Address in the packet is 172.31.1.33. The router is going to compare this address (bit by bit), with the prefixes (address/network-mask) in the routing table presented, trying to find the closest match (the number of bits that are the same). The entry that is the best match will give the router instructions as to what is the address of the next-hop device (here another router) and the outbound interface.
Let's play the router's game and compare all the entries with the DESTINATION IP address of the packet.
There are three candidate entries pointing to three different next-hop routers and three different outbound interfaces (pic. 1). The pic. 2 shows these numbers in the binary notation.
First things first. There are three terms I need to define in order to explain the process of selecting the best route. These are:
The Longest Match Rule
When a router receives a packet, while processing the header, it is the DESTINATION IP address that is compared with the entries in the routing table in order to determine the next step.
This next step is to find the egress (outbound) interface and the address of the next device to send the packet to. This form of routing is known as the destination-based routing.
The process of comparing the destination IP with the prefixes int the routing table is done bit by bit (yes, routers see IP addresses in the binary notation).
The entry that has the longest number of network bits that match the IP destination address is always the best match (best path).
This is always the FIRST thing a router checks.
If there is ONLY ONE best match, a router has a simple task to do. It moves the packet to the outbound interface (egress) and encapsulates the packet in the layer 2 header according to the technology/protocol that is used on the outbound interface (Ethernet, PPP, HDCL, Frame-Relay etc.). Then, the frame is converted to bits and placed onto the wire/fiber optic cable.
NOTICE!
If the outbound interface is a multi-access interface (such as Ethernet, Frame-Relay, ATM etc.), the router must know the layer 2 identifier of the next-hop device (layer 3 to layer 2 address resolution). For instance, in case the outbound interface is Ethernet, the MAC address of the next-hop device must be in the router's arp cache (if not found, the arp query is sent). In case, the egress interface is of a point-to-point type (subinterface point-to-point or protocol such as PPP, HDLC etc. is used), there is NO layer 3 to layer 2 resolution being performed. The packet is simply encapsulated in layer 2 frame sent out that interface.
Let's consider the example depicted in pic. 1.
Let's play the router's game and compare all the entries with the DESTINATION IP address of the packet.
There are three candidate entries pointing to three different next-hop routers and three different outbound interfaces (pic. 1). The pic. 2 shows these numbers in the binary notation.
Pic. 2 - Destination IP Address Comparison
Clearly, when converted into binary, the first entry shows the best match . The number of identical bits between the packet's destination address and router's knowledge about the subnet is 28 identical bits (highlighted in red). The second entry has only 24 identical bits, and the third one, only 16 bits match the destination IP address (class B network address). That is why the egress interface for the packet towards 172.31.1.33 is FastEthernet0/0 (pic. 1).
So far, we have only dealt with the situation in which there is a SINGLE best match. What if there are more than one entries (paths available) in the routing table with the EXACT same longest match?
There are two other parameters a router uses to break the tie:
There are the situations that your router(s) may use more than one source of information. Not that you create such situation on purpose. You are better off using one protocol (e.g. OSPF), but reality bites and sometimes you have to support more than one routing protocol in the same routing domain. In such situations your router may receive the same prefix(es) from different sources. As a result of that multiple sources (RIP, OSPF, EIGRP etc.) provider the router with the EXACT same prefix (address/network-mask).
In order to deal with situations like this, Cisco have created a ranking which assign the protocols (sources of information) different levels of "trustworthiness" (if that's a word). This level of "believability" is expressed with the arbitrarily allocated value that is given to different sources of information. This parameter is called: Administrative Distance (or just 'distance').
So far, we have only dealt with the situation in which there is a SINGLE best match. What if there are more than one entries (paths available) in the routing table with the EXACT same longest match?
There are two other parameters a router uses to break the tie:
- Administrative Distance
- Metric
There are the situations that your router(s) may use more than one source of information. Not that you create such situation on purpose. You are better off using one protocol (e.g. OSPF), but reality bites and sometimes you have to support more than one routing protocol in the same routing domain. In such situations your router may receive the same prefix(es) from different sources. As a result of that multiple sources (RIP, OSPF, EIGRP etc.) provider the router with the EXACT same prefix (address/network-mask).
In order to deal with situations like this, Cisco have created a ranking which assign the protocols (sources of information) different levels of "trustworthiness" (if that's a word). This level of "believability" is expressed with the arbitrarily allocated value that is given to different sources of information. This parameter is called: Administrative Distance (or just 'distance').
The LOWER the value of AD is, the more trusted the source of information is going to be.
Consider the pic. 3. The router receives EXACT same prefix (192.168.1.0/24) from two different sources: RIP and OSPF. Since this is going to cause an issue as to which one is better, AD is going to break the tie. OSPF is more trusted than RIP as it has lower value of Administrative Distance assigned to it (110) compared to RIP's (120).
There are many reasons why RIP is less trusted source than OSPF, but explaining it in detail is beyond of the scope of this post. Needless to say, if you do not like Cisco arbitrarily set values, there are ways of changing them. The commands are different for different protocols, and when we get to advanced topics (hopefully), I'm going to show them to you.
Metric
Another situations that might put a router in a difficult position regarding which path is the best occurs when there are multiple longest match entries in the routing table, coming from the same source. Or more accurately speaking, there are multiple best matches (EXACT prefixes) having the same value of Administrative Distance (AD).
In such situations, the tie-breaker is going to be the LOWEST value of the METRIC.
A metric is the value calculated for each prefix and expresses, for the lack of better word, how far the destination is. The lower the value, the more preferred the path is.
Keep in mind, that the type of metric routing protocols use (the way they calculate it) is different between them and totally INCOMPATIBLE. They use different ways and factors to calculate their metric.
Just to give you a few examples, RIP uses the concept of hop-count. The number (metric) tells the router how many routers the packet must traverse before it reaches the destination.
OSPF on the other hand, uses the cost as its metric. It is calculated based on the bandwidth of the interfaces (links) in the path. This way, its metric is far more sophisticated and more suitable for our networks compared to RIP.
As you see it is not the coincidence that OSPF is more trusted source of information compared to RIP.
Consider the following example (pic. 4).
Consider the pic. 3. The router receives EXACT same prefix (192.168.1.0/24) from two different sources: RIP and OSPF. Since this is going to cause an issue as to which one is better, AD is going to break the tie. OSPF is more trusted than RIP as it has lower value of Administrative Distance assigned to it (110) compared to RIP's (120).
There are many reasons why RIP is less trusted source than OSPF, but explaining it in detail is beyond of the scope of this post. Needless to say, if you do not like Cisco arbitrarily set values, there are ways of changing them. The commands are different for different protocols, and when we get to advanced topics (hopefully), I'm going to show them to you.
Pic. 3 - Advertisement Come from Different Sources (Protocols).
I have included a few AD values for the most often used protocols to get you going. For more information on that go to Cisco web site. Of course the best way of finding the values is to use my favorite search engine: google ;).
Metric
Another situations that might put a router in a difficult position regarding which path is the best occurs when there are multiple longest match entries in the routing table, coming from the same source. Or more accurately speaking, there are multiple best matches (EXACT prefixes) having the same value of Administrative Distance (AD).
In such situations, the tie-breaker is going to be the LOWEST value of the METRIC.
A metric is the value calculated for each prefix and expresses, for the lack of better word, how far the destination is. The lower the value, the more preferred the path is.
Keep in mind, that the type of metric routing protocols use (the way they calculate it) is different between them and totally INCOMPATIBLE. They use different ways and factors to calculate their metric.
Just to give you a few examples, RIP uses the concept of hop-count. The number (metric) tells the router how many routers the packet must traverse before it reaches the destination.
OSPF on the other hand, uses the cost as its metric. It is calculated based on the bandwidth of the interfaces (links) in the path. This way, its metric is far more sophisticated and more suitable for our networks compared to RIP.
As you see it is not the coincidence that OSPF is more trusted source of information compared to RIP.
Consider the following example (pic. 4).
Pic. 4 - An Example of Metric Types.
If in your design you decided to use RIP in the above topology, the router A, would choose the best path towards 10.2.2.0/24 through router B. This is because the metric used by RIP takes into consideration the number of routers the packet has to traverse, and nothing else. The path through router B is better (1 hop), as opposed to the path through routers C, D, B (3 hops). RIP does not factor in the bandwidth of the links in the path.
If you chose to use OSPF instead, the number of hops (routers the packet is going to go through) is irrelevant. OSPF makes forwarding decisions based on the bandwidth available in the paths. This way, OSPF prefers path through routers C, D, B, rather than through router B (much faster links available).
you are ready to take a look at the algorithm.
If you chose to use OSPF instead, the number of hops (routers the packet is going to go through) is irrelevant. OSPF makes forwarding decisions based on the bandwidth available in the paths. This way, OSPF prefers path through routers C, D, B, rather than through router B (much faster links available).
you are ready to take a look at the algorithm.
- Prefer the path with the longest match entry in the routing table (irrespective of the metric or AD).
- In case there are multiple best matches available, check the AD value (if they come from the same source). Choose the source of information with the lowest AD.
- If the best match prefixes (more than one) come from the source with the same AD, choose the lowest metric number.
The same order of operation is presented in the pic. 5.
Pic. 5 - Route Selection Process.
Traffic Sharing
One last scenario. What if a router receives more than one exact longest match prefixes that have the same values of AD and the metric?
All of them are the best candidates and the router performs load sharing (load balancing) using all of the egress interfaces that are the best. Of course, whether it is per-packet, or per flow load-balancing depends on the switching engine configuration of your router.
I hope you have caught the idea by now.
One last scenario. What if a router receives more than one exact longest match prefixes that have the same values of AD and the metric?
All of them are the best candidates and the router performs load sharing (load balancing) using all of the egress interfaces that are the best. Of course, whether it is per-packet, or per flow load-balancing depends on the switching engine configuration of your router.
I hope you have caught the idea by now.
No comments:
Post a Comment