Routing in the Internet is fundamentally impacted by IP addressing. A unique feature of the Internet is that the end hosts and routers alike share from the same addressing family, and this has a profound impact on routing. The address family is known as the IPv4 address family, and its recent version is known as IPv6. We will focus our discussion here specifically on IPv4 addressing.
The IPv4 address family is a 32-bit address that is typically written in dotted decimal for- mat, A.B.C.D, where each part represents the decimal value for 8 bits. Routing benefits form an important requirement in regard to address space allocation; that is, the address space is compacted through subnet masking, and addresses are assigned in contiguous blocks for a specific network. For example, contiguous addresses 192.168.1.0 to 192.168.1.255 would be assigned to a network (or subnet); similarly, contiguous addresses 192.168.2.0 to 192.168.2.255 would be assigned to another network, and so on. To reiterate, address block contiguity to de- fine a network is a fundamental requirement in IP that impacts routing. For example, because of this contiguity, a routing table at a router needs only one entry for an address block such as 192.168.1.0 to 192.168.1.255, instead of 256 separate address entries for each of these IP ad- dresses from this range. If each router were required to keep an entry for all232IP addresses, this would simply not scale! There is, however, an important trade-off, due to contiguous address blocks—not all addresses can be assigned to end hosts. For example, if we consider the address block from 192.168.1.0 to 192.168.1.255 to identify a subnet, then two addresses at the extreme ends are reserved to identify the network and for the broadcast purpose, respec- tively; specifically, the “0” address, i.e., 192.168.1.0, will be reserved to identify the subnet and and the “255” address, i.e., 192.168.1.255, will be reserved as the broadcast address.
We, however, need a simple mechanism to define contiguous address blocks that may fall at a different bit boundary level. Originally, IPv4 unicast addressing was allocated through implicit bit boundaries for network block addresses at an 8-bit, 16-bit, and 24-bit boundary,
known as Class A, Class B, Class C addresses, respectively. The difficulty with implicit bound- ary, at least for routing purpose, is that at the 24-bit level boundary, the number of address blocks is too huge to handle if all were advertised! This is mainly because of another im- portant imposition on IPv4 addressing; that is, a network address block follows a simple flat addressing principle. This means that if we want to route a packet from network 134.193.0.0 to network 134.194.0.0, we cannot count on the most significant 8 bits, i.e., 134, as some hi- erarchical indicator to make a local/hierarchical routing decision; instead, we need to keep both entries 134.193.0.0 and 134.194.0.0—this is known as flat addressing. Similarly, if all 24-bit network address blocks are to be considered, then we need224entries for a routing decision due to flat addressing. Instead of the implicit network boundaries at an 8-bit, 16-bit, and 24- bit level, the explicit network boundaries through network masking, referred to as classless inter-domain routing (CIDR), were found to be more flexible in reducing the need to assign IP address blocks for networks at a 24-bit boundary or the other implicit boundaries at 8-bit and 16-bit level.
The basic idea behind CIDR is that along with the address of a specific host, an explicit net masking is also applied that defines the network where this host resides. For example, if the host that we want to reach is 192.168.40.49, and if the address block is netmasked at the 21-bit boundary level, all a router needs to know is that 192.168.40.49 is identified as being on a network defined on the 21-bit boundary. Typically, this is indicated through the CIDR notation 192.168.40.0/21 where /21 indicates the network address block netmask. How do we arrive at 192.168.40.0/21 from 192.168.40.49? It is easy to understand when we look at the bit level information. Note that /21 means that the first 21 most significant bits in a 32-bit address are 1s and the rest are 0s, i.e., 11111111 11111111 11111000 00000000; this 32-bit netmask can also be written in the dotted decimal IP address format as 255.255.248.0. That is, a netmask written in CIDR notation /21 and its IP address notation, 255.255.248.0, are interchangeable.
As a convention, the CIDR netmask is used in identifying IP prefix-level networks, while the format such as 255.255.248.0 is used in a subnet mask on a computer when comparisons are required for packet forwarding in a subnet.
When we consider 192.168.40.49 with /21 in the CIDR notation, we can perform a bitwise
“AND” operation as shown below:
11000000 10101000 00101000 00110001 →192.168.40.49 AND 11111111 11111111 11111000 00000000 →netmask (/21)
11000000 10101000 00101000 00000000 →192.168.40.0
That is, the bitwise AND operations result in obtaining the net address 192.168.40.0, which is tied with /21 so that the network boundary is understood.
Thus, when a host in another network that has the IP address, say, 10.6.17.14 wants to send a packet to, say, 192.168.40.76, it needs to send to network 192.168.40.0/21, hoping that once it reaches this destination network, i.e., 192.168.40.0/21, it knows how to handle the delivery to the final host. This is analogous to the postal system; it is similar to sending a letter that needs to reach a postal code, and hoping that once it reaches that postal code, it can be delivered to the actual house address.
A question is how does the originating host know how to get the packet out of its own network so that it can then traverse the global Internet toward its destination. Second, is it different and/or where is it different if the packet had a destination that happens to be in the
same network, for example, if 192.168.40.49 were to send a packet to 192.168.40.76, or beyond that. We will consider routing a packet under three different scenarios.
9.2.1 Routing Packet: Scenario A
The first scenario we consider is a subnet defined by an IP address block through a standard subnet masking. That is, consider sending a packet from a host with IP address 192.168.40.49 (“49ers”) to another host with IP address 192.168.40.76 (“76ers”). The first requirement is that each host along with its IP address must have a subnet mask associated with it. In this example, we assume the subnet mask for this subnet is 255.255.255.0 which is indicated in the configura- tion profile of these two hosts. The sending host first determines its own subnet by comparing the subnet mask and the IP address of the destination (192.168.40.76) with its stored subnet mask 255.255.255.0 through the bitwise AND operation as shown below:
11000000 10101000 00101000 00110001 →192.168.40.49 (“49ers”) AND 11111111 11111111 11111111 00000000 →subnet mask (255.255.255.0)
11000000 10101000 00101000 00000000 →192.168.40.0 (/24) 11000000 10101000 00101000 01001100 →192.168.40.76 (“76ers”) AND 11111111 11111111 11111111 00000000 →subnet mask (255.255.255.0)
11000000 10101000 00101000 00000000 →192.168.40.0 (/24)
Thus, Host “49ers” realizes that the destination host, Host “76ers,” belongs to the same sub- net. Assume that subnet 192.168.40.0 is served by an Ethernet LAN (see Figure 9.2). Thus, to send a packet, the host with address 192.168.40.49 is required to rely on the Ethernet in- terface for packet delivery; for that, a protocol called the Address Resolution Protocol (ARP), which does the function of mapping the IP address to the Ethernet address, is first invoked.
Through this process, Host “49ers” finds the Ethernet address of the destination IP address 192.168.40.76. Once the Ethernet address of the destination is determined, the packet is sent as an Ethernet frame with the destination address set to this Ethernet address. In a sense, we can say that in the same Ethernet LAN, “routing” a packet does not really involve routing.
F I G U R E 9.2 Host “49ers” (192.168.40.49) and Host “76ers” (192.168.40.76) on an Ethernet subnet with mask 255.255.255.0.
F I G U R E 9.3 Network 192.168.40.0/21 with subnets and routers.
9.2.2 Routing Packet: Scenario B
The second scenario is where communication is not limited to the same subnet, but it is in the same network in the sense that it is provided by the same provider, such as a campus or an enterprise network. We identify this network as 192.168.40.0/21, which covers the address range 192.168.40.0–192.168.47.255. We assume that it consists of Ethernet segments where subnets are allocated and that all Ethernet-based subnets use subnet mask 255.255.255.0. Se- rial links are used between three of the four routers where subnet mask 255.255.255.252 is used. The topology of network 192.168.40.0/21 with all its subnets is shown in Figure 9.3.
We assume that this intradomain network uses the OSPF protocol among its routers. For il- lustration, consider sending a packet again from Host “49ers,” with IP address 192.168.40.49 and subnet mask 255.255.255.0, to a third host with IP address 192.168.41.22 (“catch22”). Note that Host “49ers” does not know about the subnet mask of Host “catch22.” Based on its own subnet mask, Host “49ers” compares and determines that Host “catch22” is on a different subnet, 192.168.41.0, as shown below:
11000000 10101000 00101000 00110001 →192.168.40.49 (“49ers”) AND 11111111 11111111 11111111 00000000 →subnet mask (255.255.255.0)
11000000 10101000 00101000 00000000 →192.168.40.0 (/24) 11000000 10101000 00101001 00010110 →192.168.41.22 (“catch22”) AND 11111111 11111111 11111111 00000000 →subnet mask (255.255.255.0)
11000000 10101000 00101001 00000000 →192.168.41.0 (/24)
R1:
Net Mask NextHop Interface
192.168.40.0 255.255.255.0 direct en0
192.168.41.0 255.255.255.0 direct en1
192.168.42.0 255.255.255.0 192.168.47.249 sl2 192.168.43.0 255.255.255.0 192.168.47.242 sl1 192.168.44.0 255.255.255.0 192.168.47.242 sl1 192.168.45.0 255.255.255.0 192.168.47.242 sl1 192.168.47.240 255.255.255.252 direct sl1 192.168.47.248 255.255.255.252 direct sl2
0.0.0.0 0.0.0.0 192.168.47.242 sl1
R2:
Net Mask NextHop Interface
192.168.40.0 255.255.255.0 192.168.47.241 sl1 192.168.41.0 255.255.255.0 192.168.47.241 sl1 192.168.42.0 255.255.255.0 192.168.47.246 sl0
192.168.43.0 255.255.255.0 direct en2
192.168.44.0 255.255.255.0 direct en0
192.168.45.0 255.255.255.0 direct en1
192.168.47.240 255.255.255.252 direct sl1 192.168.47.244 255.255.255.252 direct sl1
0.0.0.0 0.0.0.0 192.168.43.254 en2
R3:
Net Mask NextHop Interface
192.168.40.0 255.255.255.0 192.168.47.250 sl0 192.168.41.0 255.255.255.0 192.168.47.250 sl0
192.168.42.0 255.255.255.0 direct en0
192.168.43.0 255.255.255.0 192.168.47.254 sl2 192.168.44.0 255.255.255.0 192.168.47.245 sl1 192.168.45.0 255.255.255.0 192.168.47.245 sl1 192.168.47.244 255.255.255.252 direct sl0 192.168.47.248 255.255.255.252 direct sl1 192.168.47.252 255.255.255.252 direct sl2
0.0.0.0 0.0.0.0 192.168.47.254 sl2
R4:
Net Mask NextHop Interface
192.168.40.0 255.255.255.0 192.168.43.253 en0 192.168.41.0 255.255.255.0 192.168.43.253 en0 192.168.42.0 255.255.255.0 192.168.47.253 sl0
192.168.43.0 255.255.255.0 direct en0
192.168.44.0 255.255.255.0 192.168.43.253 en0 192.168.45.0 255.255.255.0 192.168.43.253 en0 192.168.47.252 255.255.255.252 direct sl0
0.0.0.0 0.0.0.0 10.1.2.3 sl1
F I G U R E 9.4 Routing tables (with interfaces) at routers in Network 192.168.40.0/21 (see Figure 9.3).
Now Host “49ers” has a decision to make since it realizes that Host “catch22” is not on the same subnet. To make this decision, Host “49ers” must be equipped with a mechanism for handling such packet arrival; this mechanism is provided through a default gateway address.
This means that if a packet’s destination is not on the same subnet, the default gateway will be the agent that will be the recipient of this packet, which, in turn, hopefully knows how to handle it. The knowledge of this default gateway is known to the sending host either by static configuration or through the Dynamic Host Configuration Protocol (DHCP). In general, the following must hold for a host to communicate on the Internet:
Either through static configuration or through DHCP, a host must have three key pieces of informa- tion: its host IP address, the subnet mask, and the default gateway. Note that the default gateway is not needed for scenario A; however, since a host must reside in an interconnected environment where it will invariably want to send a packet to a destination such as an email server or a web server that is outside its subnet, the default gateway information becomes a necessity. For a host to use Internet services, it is also required to have information about the IP address of at least a DNS server so that this server can be queried to find the actual IP address of a specific domain name. Thus, a host typ- ically requires four pieces of information: its host IP address, the subnet mask, the default gateway, and a DNS server’s IP address.
Now going back to our example, the IP address of the default gateway must fall on the same subnet as the host. Here, the default gateway for Host “49ers” is assigned the address 192.168.40.254, and this happens to be an interface to a router that has an interface to subnet
192.168.41.0, and also to other subnets; see Figure 9.3, where this is depicted with the router marked as R1.
With the availability of the default gateway information at Host “49ers,” and on recog- nizing that this packet is to be sent to the gateway, it would do an ARP request to find the Ethernet interface address for 192.168.40.254, so that the packet can be sent as an Ethernet frame to router R1.
Once the packet arrives at router R1, the router is now required to make a decision on which interface to send it out since it has multiple interfaces. Based on the destination net- works it has learned about, a router would maintain a routing table so it knows how to handle an arriving packet. Furthermore, based on the routing table, the forwarding table information is derived to determine which interface is to be used for packet forwarding. In Figure 9.4, we show a routing table view with interface information for router R1. From the table for R1, we can see that the packet that originated at Host “49ers” will be sent on the interface with IP address 192.168.41.254 for delivery to Host “catch22” on the Ethernet segment.
We next consider the case in which Host “49ers” has a packet to send to Host “221bBak- erStreet” (with IP address 192.168.44.221). This packet will first arrive at router R1 since by inspecting the address of Host “221bBakerStreet”, Host “49ers” would realize that the host does not belong to this subnet. At router R1, by inspecting the routing table, the packet would be forwarded to router R2, whereupon it will be sent on the Ethernet interface with IP address 192.168.44.254.
We can thus see that for any packet that is meant for a host within network 192.168.40.0/21, routers would be required to have next-hop information for different subnet segments. The process of learning about different subnets within this domain can be accom- plished using OSPF flooding. For instance, each router can learn about different subnets from a link state advertisement (LSA) that would contain subnet information with mask by using the network link-type LSA (refer to Chapter 6). Once announcements about various subnets are received, each router can use shortest path routing to determine the appropriate next hop to reach different subnets; the tables at each router are shown in Figure 9.4. You may note that the table at router R1 does not show an entry for the serial link subnet 192.168.42.0/30; the assumption here is that serial link subnets are not to be advertised in the LSA; this is similar for other tables. Furthermore, note that each table contains a 0.0.0.0/0 entry, which is referred to as the default route. The default route is similar to the default gateway maintained by each host; this entry points to a next-hop for forwarding a packet that lists a destination not listed in the routing table.
In essence, through scenario B, we have illustrated how to route a packet from a host to another host in a different subnet but within an administrative domain. Typically, such an administrative domain is defined by an AS, or a provider.
9.2.3 Routing Packet: Scenario C
In this scenario, we consider routing a packet that is generated at Host “49ers” meant for a host outside of network 192.168.40.0/21 to, say, host 10.5.16.60 where each network is served by a different AS. By using the next hop for the default route at each router, the packet gen- erated at Host “49ers” would be forwarded from R1 to R2 to R4. Note that R4 is the border router in this domain that can speak OSPF to interior routers, but can also speak BGP to its
F I G U R E 9.5 AS routing path of a packet from 192.168.40.0/21 to 10.5.0.0/16 through intermediate ASes.
peering EBG speaker. If R4 were to maintain a default route entry in its routing table, the packet that originated at Host “49ers” will be forwarded outside network 192.168.40.0/21 on the external link.
In Figure 9.5, we show connectivity from network 192.168.40.0/21 to network 10.5.0.0/16 that requires traversing through intermediate ASes. Suppose that each AS maintains an en- try for default route to the next AS. Then the packet from 192.168.40.49 will be routed from AS64617, its home AS, to its neighboring AS, AS64701. The border router at AS64701, on re- ceiving this packet, will check if it is meant for an address block that is internal to it, and will realize that it does not; thus, it will forward it to its other border router through inter- nal routers. Assume that this border router in AS64701 has set up the default route to be to AS64730. Thus, the packet will eventually arrive at the border router in AS64516, the home to network 10.5.0.0/16. The border router will recognize that it supports this network and would then use interior routing protocol to deliver to the final destination host.
Note that we have assumed that everyone uses the default route concept. There are, how- ever, certain problems with every AS using the default route to send a packet out if its AS.
For example, if the destination host is from an IP address block that has not yet been allocated by the Internet registry, the packet would keep hopping from one AS to another until the age field (also known as the time-to-live field) in the IP packet header expires. This indicates that there are two possibilities: (1) at least one of the intermediate ASes maintains all default-free entries, that is, every valid IP prefix is explicitly listed, meaning there is no default route en- try, 0.0.0.0/0, or (2) the originating AS at its border router maintains the list of every valid IP prefix assigned thus far so that it can filter this packet (refer to Chapter 16) and drop it, preventing from going into the next AS.
We first discuss the first possibility. An intermediate AS such as AS64730, shown in Fig- ure 9.5, is known as a transit AS. Note that there is no such thing as the core transit AS; in fact, that would be restrictive, like EGP, which we discussed earlier. BGP provides the flexibility that there can be different transit ASes that serve as peers to each other. Since different stub ASes can be connected to different transit ASes, any transit ASes at the core need to exchange the entire routing table information about IP prefixes with other peering ASes using the BGP
protocol. Thus, typically the core backbone Internet service providers (ISPs) maintain default- free routing tables for all valid IP prefixes so learned.
Consider Figure 9.5 again. Here network 172.17.0.0/16 homed in AS64822 would become known to transit AS, AS64731, which in turn would share this information with transit AS, AS64730. This way, BGP routers at transit ASes can build a complete default-free routing table. Now if Host “49ers” in network 192.168.40.0/21 in AS64617 generates a packet to an IP destination that is from an IP address that is not valid, then the border router in AS64701 would note this and drop this packet. In other words, a default-free routing table allows an IP packet with a destination in nonallocated address blocks from being forwarded further by dropping it. Transit ASes commonly employ a default-free routing table for such reasons.
We next discuss the second possibility. This option is possible since the BGP protocol announces IP prefixes through UPDATE messages that would traverse through and reach every edge or stub AS, such as AS64617 and AS64516. Typically, most stub ASes use the default route entry, i.e., they do not store all IP prefix entries, partly because they usually have single outlets to the rest of the Internet, and because it puts more than the required work on its border router, which may not be able to handle the load if it is not a powerful router with required memory. That is, it is not necessary to maintain a full default-free table at the border router of a stub AS. However, more and more stub ASes now maintain a full IP prefix table at their border routers. This can be driven by local needs in a stub AS, for example, to perform unicast reverse-path-forwarding (uRPF) checks as a measure for IP address spoofing. Thus, while from a BGP perspective, a stub AS is not required to maintain a default-free routing table, it has essentially become a necessity because of issues such as spoofing attacks.
To summarize, routing a packet that has originated in a network (IP prefix ) in a stub AS with destination in another network (IP prefix ) in another stub AS, would hop through at least a transit AS. Any path selection decision at a BGP speaker when there is connectivity from one AS to the next at multiple border BGP speakers, or from one AS to multiple ASes, would be based on the BGP path selection algorithm described in Section 8.7.1 in Chapter 8.
Certainly, before route selection can be invoked about an IP prefix , the BGP UPDATE mes- sage would be used to announce this IP prefix ; the AS number is prepended as necessary when the information about this IP prefix crosses from one AS to another.
Before concluding this section, we discuss another term in regard to ASes. So far, we have mentioned two types of ASes: stub AS and transit AS. An AS can also be multihomed. Briefly, a multihomed AS connects to two or more transit ASes. As an example, consider Figure 9.5 again. Here, AS64617 is a stub AS; AS64701 is a transit AS that is also multihomed while AS64516 is a stub AS that is multihomed. Thus, ASes can be classified into three categories:
stub singlehomed, stub multihomed, and transit multihomed.