[Dr.WoW] [No.56] Shortest Path Routing Highlighted

Latest reply: Nov 8, 2016 17:59:55 2827 3 0 1

1 Default Routing vs. Specific Routing

What is shortest path routing? Just as it sounds, this entails selecting the closest path. For networks with multiple egresses, shortest path routing refers to packets choosing the link that will involve the smaller cost to reach the destination network for use in forwarding. Now, how do packets select the link with the smaller cost for forwarding? This can be accomplished using default routes and specific routes. Below, I'll answer several questions to introduce a few of the essential concepts behind default routing and specific routing and help everyone in understanding this.

Question 1: What is default routing, and is default routing a kind of static routing?

Actually, default routing is a special kind of routing that can be configured through static routes or generated through dynamic routes such as OSPF and IS-IS. Therefore, default routing is actually not a kind of static routing. In routing tables, the default route has a destination network of 0.0.0.0 and a subnet mask of 0.0.0.0. Below is a default route in a routing table:

[FW] display ip routing-table                                                    

Route Flags: R - relay, D - download to fib                                   

------------------------------------------------------------------------------ 

Routing Tables: Public                                                           

 

        Destinations : 1       Routes : 2                                     

 

Destination/Mask    Proto  Pre  Cost       Flags NextHop         Interface      

        0.0.0.0/0    Static 60   0           RD     10.1.1.2        GigabitEthernet2/2/21 

                       Static 60   0           RD     10.2.0.2        GigabitEthernet2/2/17

If a packet's destination address cannot be matched with any route, then the system will use default routing to forward this packet.

Question 2: What are specific routes?

I, Dr. WoW, believe that specific routing is defined comparatively against default routing; all routes in a routing table that are not default routes are specific routes. For example, 10.1.0.0/16 and 192.168.1.0/24 are both specific routes when compared with the default route. Compared to the parent route 10.1.0.0/16, the routes 10.1.1.0/24, 10.1.2.0/24, and 10.1.3.0/24 are all specific routes. There is no relationship between specific routes and the protocol type, so specific routes can be configured as static routes or can be generated by dynamic routing policies.

Question 3: How do packets check the routing table?

As everyone may know, when packets check the routing table, they conduct their check based upon the longest matching principle, but what exactly does this mean? To give an example, a routing table has three routes, 10.1.0.0/16,10.1.1.0/24 and 0.0.0.0/0. When packets with a destination address of 10.1.1.1/30 check the routing table, the route that they ultimately match is the 10.1.1.0/24 route, because when a packet checks the routing table, a packet's destination address is matched digit by digit with the routing table's entries' masks using "AND" logic, and if the obtained address corresponds with a routing table entry's network address then they match. Ultimately, the longest matching routing table entry is selected to forward the packet. If a packet with the destination address of 192.168.1.1/30 checks the routing table, it will only be able to be matched to the default route 0.0.0.0/0 (because the packet's destination address cannot be matched with any specific route) and so the system will ultimately use default routing to forward this packet.

From the above questions it should be clear that when there are specific routes in a routing table, the packet is first matched to a specific route, and only if there is not a matching specific route is the default route(s) checked.

Below, we'll look at Question 4: How is routing conducted when there are multiple default routes?

Let's first look at the networking approach shown in Figure 1-1. We've configured two default routes on a firewall, with one that has a next hop of R1 and one that has a next hop of R2. Let's ping the two server addresses on the destination network from the PC.

Figure 1-1 Default route multi-homing

[Dr.WoW] [No.56] Shortest Path Routing-1044585-1 

The two default routes are configured as follows on the firewall:

[FW] ip route-static 0.0.0.0 0 10.1.1.2

[FW] ip route-static 0.0.0.0 0 10.1.2.2

A packet capture on FW's GE0/0/3 interface shows that the packets have both been forwarded from GE0/0/3:

[Dr.WoW] [No.56] Shortest Path Routing-1044585-2

[Dr.WoW] [No.56] Shortest Path Routing-1044585-3 

Why did this happen? Did the two default routes not load distribute? In fact, for multi-homing routing when there are multiple default routes, the specific link that a packet travels is calculated by a HASH algorithm involving the source IP address+the destination IP address. This kind of algorithm primarily looks at a packet's source IP address and destination IP address, so when addresses are different, the calculated results will also be different. Using this kind of algorithm, the opportunity to forward packets is identical between equal-cost routes. To give an example, if packets' source IP addresses are the same, and the destination IP addresses neighbor one another, for example 10.1.1.1 and 10.1.1.2, then during path selection, each link will forward one stream of packets. However, as the source and destination IP addresses for a network's traffic accessing external networks are random, the results of the HASH algorithm are completely uncontrollable. Therefore, although the default routes are equal-cost routes, it's possible that the packets will all be forwarded from one link. This is also why the packets in the above example were both forwarded from interface GE0/0/3.

What I discussed above was a bit of basic knowledge. Now let's look at how the 'default routing+specific route' shortest path routing method selects the shortest path. Let's first look at a simple network environment, shown in Figure 1-2.

Figure 1-2 Multiple egress network diagram

[Dr.WoW] [No.56] Shortest Path Routing-1044585-4 

In the above figure, when enterprise intranet users access an external network server, there are two paths for associated packets through the firewall. Under normal circumstances, enterprises generally configure two default routes on an egress firewall, one for each ISP. Above, I mentioned that in path selection via default routing, a source IP+destination IP HASH algorithm determines the path by which data packets are forwarded. This may result in traffic accessing ISP2's server being forwarded through Path 1 in the figure after the HASH algorithm is calculated, meaning that the packet would be sent on Path 1 to ISP1, and then sent through ISP1 to ISP2, travelling a large loop before finally reaching its ultimate destination. This would severely and negatively affect forwarding efficiency and user experience.

So, what method can we use to ensure packets do not travel a circuitous path? The answer is to configure specific routing. As we discussed above, packets are preferentially matched to specific routes, and only look for default routes if there is not a specific route they can be matched to. For the network shown in Figure 1-2, we could configure a specific route to the server, with the next hop pointing to ISP2. In this way, after packets are matched to this specific route they will not be forwarded circuitously. From the figure it can be seen that the path selected for sending packets is the shortest of the two paths, which is what we mean by 'shortest path routing.' We can also verify this using the network shown in Figure 1-1. We configure two static routes on the firewall such as the ones below:

[FW] ip route-static 10.10.10.10 255.255.255.255 10.1.1.2(Next hop is R1's address)

[FW] ip route-static 10.10.11.11 255.255.255.255 10.1.2.2(Next hop is R2's address)

A packet capture on the firewall's GE0/0/3 interface shows that there are only packets going to 10.10.10.10:

[Dr.WoW] [No.56] Shortest Path Routing-1044585-5 

A packet capture on the firewall's GE0/0/2 interface shows that there are only packets going to 10.10.11.11.

[Dr.WoW] [No.56] Shortest Path Routing-1044585-6 

This proves that the packets preferentially checked for the two specific routes that we just configured. However, in real-world network environments, there are many servers on the Internet, and asking administrators to configure so many specific routes on egress network gateway firewalls is not realistic. Is there a convenient and fast method to configure specific routes? This requires that the ISP routing function step into the limelight. But what exactly is ISP routing?

2 ISP Routing

In the term 'ISP routing', we can see the key acronym "ISP", which indeed speaks to this method's functionality. Each ISP has their own public well-known network segments, and if all of these public well-known network segments were configured into specific routes as we discussed above, then none of the packets going to this ISP would be forwarded in a circuitous fashion. How can we change an ISP's public well-known network segments into specific routes?

First, the administrator needs to collect together all of the public network segments within an ISP (these can be found through online searches), and then compile the address network segments into a file with an extension of .csv (we'll call this the ISP address file). The compilation requirements are as shown in Figure 1-3:

Figure 1-3 Compiling an ISP address file

[Dr.WoW] [No.56] Shortest Path Routing-1044585-7 

After the ISP address file's compilation is complete, we need to upload this onto the firewall's designated path, for example onto a CF Card. There are many upload methods, such as SFTP, FTP, TFTP, etc., and these will not be described here.

After the ISP address file has been uploaded to the firewall, the egress interface and next hop are configured, so that after the ISP routing function is enabled, each IP address segment in the ISP address file will be converted into a separate static route. In this way, the entire ISP address file will morph into a script for configuring a batch of static routes for one ISP, and you won't need to worry about configuring an enormous number of static routes again!

Below, we'll use an experimental network to verify the results of multi-homing using ISP routing; this network is shown in Figure 1-4.

Figure 1-4 ISP routing network diagram

[Dr.WoW] [No.56] Shortest Path Routing-1044585-8 

In this network, we've separately compiled ISP1 and ISP2's address network segments into the files ispa.csv and ispb.csv respectively.

We first used methods such as SFTP, FTP, TFTP, etc. to upload the two csv files onto the firewall's designated path. The Eudemon8000E-X firewall series' path is cfcard:/isp/; the Eudemon200E-N\1000E-N firewall series' path is hda1:/isp/.

After completing the upload of the csv files, a related command is used to configure the corresponding egress interface and next hop, and the ISP routing function is enabled. Using the Eudemon8000E-X firewall series as an example, the configuration command is as below:

[FW] isp set filename ispa.csv GigabitEthernet 2/0/1 next-hop 201.1.1.2

In addition to this, we can also use the Web configuration method to configure ISP routing. This method is even simpler, and csv file uploading and configuration(s) input can be completed in one step. Using Eudemon8000E-X as an example, the input method is shown in Figure 1-5.

Figure 1-5 Using the Web configuration method to enable ISP routing

[Dr.WoW] [No.56] Shortest Path Routing-1044585-9 

The input method for ispb.csv is the same as for ispa.csv, with the exception that the egress interface and next hop are changed to GE2/0/2 and 202.1.1.2 respectively:

Destination/Mask    Proto  Pre  Cost    Flags NextHop         Interface       

      210.1.1.1/32  ISP    60   0      D   201.1.1.2         GigabitEthernet2/0/1 

      210.1.1.2/32  ISP    60   0      D   201.1.1.2         GigabitEthernet2/0/1 

      210.1.1.3/32  ISP    60   0      D   201.1.1.2         GigabitEthernet2/0/1 

      220.1.1.1/32  ISP    60   0      D   202.1.1.2         GigabitEthernet2/0/2  

      220.1.1.2/32  ISP    60   0      D   202.1.1.2         GigabitEthernet2/0/2  

      220.1.1.3/32  ISP    60   0      D   202.1.1.2         GigabitEthernet2/0/2  

When an intranet user accesses a server belonging to ISP1, after packets are matched to the routing table they are forwarded from interface GigabitEthernet2/0/1; likewise, when one of ISP2's servers is accessed, packets are forwarded from interface GigabitEthernet2/0/2. This guarantees that packets are always forwarded to the destination network via the shortest path.

In the above routing table, it can be seen that ISP routing and static routing are extremely similar; in the routing table, other than the fact that the protocol type is ISP, the table's other content is exactly the same as with static routing. Moreover, these two kinds of routing can overlap one another; for example, if a static route is first configured and then an ISP route with the same destination address and next hop is imported, this route's protocol type will change from static to ISP in the routing table (the opposite is true as well). However, in real-world use, there are still several differences between ISP routing and static routing:

1.         Static routes are configured manually route by route, and can be displayed in the configuration file; ISP routes can only be input collectively via the method described above, and cannot be displayed in the configuration file.

2.         Static routes can be deleted and added; for ISP routing, deletions and additions may only be of the address network segments in the ISP address file, but single ISP routes cannot be deleted or added using commands.

What we discussed above was the process of an administrator building ISP routes, but in actuality, firewalls have already been equipped with factory default csv files for 4 ISPs―china-mobile.csv (China Mobile), china-telecom.csv(China Telecom), china-unicom.csv (China Unicom) and china-educationnet.csv (CERNET)― and so ISP routing for these can be enabled simply by the admin executing the input.

To summarize, at the core of shortest path routing is a 'head to head battle' between the three kinds of routing:

l   Default equal-cost routing allows all packets passing through a firewall to be matched to a route and forwarded, but there is no way to ensure that packet forwarding uses the shortest link for forwarding (the packet's forwarding egress is selected through a HASH algorithm involving the source IP address+the destination IP address).

l   Specific routing ensures that packets accessing different ISP servers from one another are all forwarded from the firewall's link connected to the corresponding ISP, achieving shortest path access, however, the difficulty involved in configuring a large number of specific routes manually is a problem for enterprise network administrators.

l   ISP routing, on the other hand, fills in the deficiencies of specific routing in terms of the difficulty presented by large batch manual configuration, allowing for specific routes to be configured for all of an ISP's address network segments in just a matter of minutes.

Each of these three kinds of routing has their own unique properties, and only using them together allows for each of them to make up for the others' shortcomings so that their strong points may be displayed. In this sort of combined use, specific routing and ISP routing are used to direct packets in being forwarded by the shortest path, with packets that can't be matched to a specific route then being forwarded through checking for a default route.

However, the shortest path routing method is only a basic method of conducting routing for multi-homing. As we know, route checking in this method is performed using packets' destination addresses, and this is where a problem arises: if an admin wishes to differentiate between intranet users and allow users with different priority levels to forward packets from different links, or if the admin wishes to differentiate the links used to forward traffic based upon different applications, these goals cannot be completed through checking for routes using the destination address. To accomplish this, we need more flexible path selection mechanisms, for example using packets' source IP address, the application protocol type, etc. to differentiate user traffic, and then furthermore conduct differentiated forwarding of this different user traffic. Therefore, our focus naturally shifts to policy-based routing.

 

 

 

To view the list of all Dr. WoW technical posts, click here.

  • x
  • convention:

user_1787981
Created Jan 27, 2016 01:57:50 Helpful(0) Helpful(0)

Thanks for sharing.
  • x
  • convention:

user_2790689
Created Jan 28, 2016 01:14:39 Helpful(0) Helpful(0)

Thank you.

 

  • x
  • convention:

nklsureshkumar
Created Nov 8, 2016 17:59:55 Helpful(0) Helpful(0)

great work as useful doc .
  • x
  • convention:

Reply

Reply
You need to log in to reply to the post Login | Register

Notice Notice: To protect the legitimate rights and interests of you, the community, and third parties, do not release content that may bring legal risks to all parties, including but are not limited to the following:
  • Politically sensitive content
  • Content concerning pornography, gambling, and drug abuse
  • Content that may disclose or infringe upon others ' commercial secrets, intellectual properties, including trade marks, copyrights, and patents, and personal privacy
Do not share your account and password with others. All operations performed using your account will be regarded as your own actions and all consequences arising therefrom will be borne by you. For details, see " Privacy."
If the attachment button is not available, update the Adobe Flash Player to the latest version!
Login and enjoy all the member benefits

Login and enjoy all the member benefits

Login