Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Data plane > Route lookup - Pg. 118

118 CHAPTER 7 Routers Route lookup Route lookup algorithms in IP networks make use of the inherent structure of IP addresses. Before presenting various lookup algorithms, we review IP addressing and address prefixes. Addressing In network layer protocols, specifically in the IP, addresses identify network adap- ters. It is important to note that a single end system may have multiple network inter- faces. For example, a typical laptop today has one network interface that uses wired Ethernet, one network interface that uses wireless Ethernet, and possibly another one that uses a cellular data connection. Each interface uses its own IP address. One of the requirements for addresses in the network layer is that they are designed such that end-to-end connectivity--the main functionality of the network layer--becomes possible. In the case of IP, addresses are globally unique. That means that every network interface connected to the Internet must use a different IP address. This global uniqueness of all IP addresses is no longer true due to Network Address Translation, which is discussed in Chapter 8. However, for the purpose of our discussion in this chapter, we assume that IP addresses are indeed unique. With a globally unique IP address, an end-system interface can be unambiguously identified. A sender who wants to transmit a packet to that interface can then simply put the corresponding IP address into the destination address field. The network uses this destination address then to determine how to forward the packet throughout the network such that it reaches the receiver's network interface in the end. One important observation is that each router in the network needs to know where to send packets for every possible IP address. End systems may decide to send traffic to any possible destination at any time. A router needs to be able to forward any packet and thus needs to know on which of its links to forward a packet with any possible IP address. In the IP protocol, the address field is 32 bits long. Ignoring that some addresses are reserved and cannot be used, there are 2 32 % 4 Â 10 9 possible IP addresses. For each of these addresses the router needs to maintain information on where to send a packet that is destined for them. If IP addressing was done the same way as addressing is done for Ethernet, where each interface gets an address assigned at manufacturing time, then there would be no structure to the IP address space. In such a case, routers would have to maintain a separate forwarding entry for each existing IP address. Such a forwarding table would require around four billion entries and consume a large amount of memory. To avoid this problem, IP uses structured address assignments that ensure that inter- faces located on the same subnetwork have similar addresses. The similarity in addresses can be used to condense the information that needs to be stored on routers. Internet Protocol addresses can be divided logically into a network portion and a host portion. The network portion identifies a network (i.e., a set of inter- connected network interfaces that share the same network portion in their addresses). The host portion identifies a particular interface within a network. With this structure, a whole network of computers can be represented by a single