Internet Routing--A Little Deeper

Internet RoutingA Little Deeper

Basic IP routing on the Internet is not that difficult to understand, and you need a basic understanding to comprehend the security risks to the infrastructure of the global Internet. In Chapter 1 we likened Internet routing to the post office method of addressing and delivering mail. Let's review what we learned quickly. An Autonomous System Number (ASN) represents a collection of routers under a common administrative control. Every ISP or organization that shares routing information using BGP has a unique ASN, and each is identified by that number. An AS runs an interior gateway protocol (IGP) to route packets within its own network. The IGP is typically OSPF or IS-IS, but large enterprise networks may run (E)IGRP or other IGPs. The IGP is a "hop-by-hop" protocol. A packet flowing through an AS is forwarded hop-by-hop , by each router, based on a precalculated forwarding table. The calculated paths are usually based on a "cost" metric such as link bandwidth or distance, as shown in Figure 2-1.

Figure 2-1: Packet flow through a network using an IGP

As you can see from the bold lines between routers, the best path from Router A to Router I is A-B-C-F-D-H-I. In this example, the metric of each link in the network is the approximate distance, in miles, between the routers. The shorter path is always preferred over the longer path. The IGP on each router runs an algorithm to compute the best path from any one point in the network to any other point. If a link or router fails, the paths are automatically recalculated based on the metrics applied.

What happens when a packet needs to be sent to another AS? Why don't we run the same IGP with other ASs to exchange routes? Historically, IGPs were the only protocols used to route packets within a network, and between networks. Today, the global routing table is too large (approximately 150,000 routes as of this writing) for IGPs to calculate paths in a timely manner, and IGPs carry very little policy information. IGPs works best with small routing tables in order to calculate paths very quickly. This is where BGP comes in.

BGP is used to calculate the next hop for a packet to reach its destination, but that next hop is the exit point (a router), where the packet leaves the network towards its destination. The exit point could be the IP address of the router that originated the advertisement for the destination, or the IP address of a router that peers with another AS. To summarize the whole process, a router looks at its BGP routing table to determine the "next-hop exit point," then the router looks at the IGP routing table to determine the next router in the path to forward the packet to so that it can reach that exit point. Figure 2-2 illustrates the difference between the BGP and IGP next hop calculation.

Figure 2-2: Example of BGP next hop vs. IGP next hop

In this example, Routers C, E, and F are exit gateways to other networks. This process of querying the BGP routing table to find the exit point, and then querying the IGP routing table to find each physical hop along the path to the exit point, is called a recursive lookup.

Path Selection

BGP carries many attributes related to prefixes, which control how a route is used both inside an AS and between other ASs. Entire books are written covering the details of the BGP protocol, but we'll show you the BGP path selection process and the most commonly used attributes that affect routing decisions. The path selection process can be very complicated and vary widely depending on network design, peering relationships, and policies. This example is somewhat generic, and may differ slightly depending on the router vendor.

• Given equal IP prefixes with different mask lengths, the "longest match" or "more specific" is always more preferred. So given 192.0.2.0/24 and 192.0.2.0/27 in a routing table, the longest match (/27) will always be the preferred route, regardless of all other metrics.

• BGP assigns the first valid path as the current "best path," and then compares other prefixes of equal length according to the following criteria:

  • Prefer path with highest weight This value is only valid on the local router on which it is configured.

  • Prefer path with highest local_preference This value is only valid within the AS.

  • Prefer path that was locally originated A prefix injected on the local router through a network or aggregate statement.

  • Prefer path with shortest AS-PATH Fewest ASNs in the path (can be ignored).

  • Prefer path with lowest origin-type IGP=lowest, then EGP, then incomplete (IGP is most common).

  • Prefer path with lowest Multi-Exit-Discriminator (MED) This is slightly complicated and does not appear to be used often.

  • Prefer externally learned paths over internally learned paths eBGP routes more preferred than iBGP routes.

  • Prefer path to lowest IGP metric of the next hop This is the "distance" or "cost" metric, mentioned above. As it turns out, many paths are selected at this step, all other attributes typically being equal.

    Note 

    This step has historically been called shortest exit. This simply means that any given provider will select the shortest path out of their network to deliver the packet, thereby sending any given packet out of its network as quickly as possible. To reduce the cost of providing service, ISPs do not want to carry traffic on the backbone any longer than necessary.

  • If both paths are external, prefer the path received first (oldest) This minimizes route oscillation (flapping) when a newer path arrives, even if it might be preferred by subsequent steps.

  • Prefer path from lowest advertising router ID Compare IP addresses of router IDs and select the lowest ( numerically ).

  • Prefer path from lowest neighbor IP address This is the IP address used to set up the peering relationship. This step is considered the "tie breaker"when all other attributes are equal, this one will be unique.

As you can see, the process compares many different attributes. Some of these only apply to a local router, some only apply within a single AS, and some can be influenced by external peers. As we noted at the beginning of this section, the most specific prefix match is always preferred when multiple prefixes of differing lengths are received.