Nibba group: IP Forwarding

IP Forwarding

IP routers use datagram forwarding, described in 1.4 Datagram Forwarding above, to deliver packets, but the “destination” values listed in the forwarding tables are network preﬁxes – representing entire LANs – instead of individual hosts. The goal of IP forwarding,then,becomes delivery to the correct LAN;aseparate process is used to deliver to the ﬁnal host once the ﬁnal LAN has been reached. The entire point, in fact, of having a network/host division within IP addresses is so that routers need to listonlythenetworkpreﬁxesofthedestinationaddressesintheirIPforwardingtables. Thisstrategyisthe key to IP scalability: it saves large amounts of forwarding-table space, it saves time as smaller tables allow faster lookup, and it saves the bandwidth and overhead that would be needed for routers to keep track of individualaddresses. Togetanideaoftheforwarding-tablespacesavings,therearecurrently(2013)around a billion hosts on the Internet, but only 300,000 or so networks listed in top-level forwarding tables. With IP’s use of network preﬁxes as forwarding-table destinations, matching an actual packet address to a forwarding-tableentryisnolongeramatterofsimpleequalitycomparison; routersmustcompareappropriate IP forwarding tables are sometimes also referred to as “routing tables”; in this book, however, we make at least a token effort to use “forwarding” to refer to the packet forwarding process, and “routing” to refer to mechanisms by which the forwarding tables are maintained and updated. (If we were to be completely consistent here, we would use the term “forwarding loop” rather than “routing loop”.) Now let us look at an example of how IP forwarding (or routing) works. We will assume that all network nodes are either hosts – user machines, with a single network connection – or routers, which do packetforwarding only. Routers are not directly visible to users, and always have at least two different network interfaces representing different networks that the router is connecting. (Machines can be both hosts and routers, but this introduces complications.) Suppose A is the sending host, sending a packet to a destination host D. The IP header of the packet will contain D’s IP address in the “destination address” ﬁeld (it will also contain A’s own address as the “source address”). TheﬁrststepisforAtodeterminewhetherDisonthesameLANasitselfornot;thatis,whether D is local. This is done by looking at the network part of the destination address, which we will denote by Dnet. If this net address is the same as A’s (that is, if it is equal numerically to Anet), then A ﬁgures D is on the same LAN as itself, and can use direct LAN delivery. It looks up the appropriate physical address for D (probably with the ARP protocol, 7.9 Address Resolution Protocol: ARP), attaches a LAN header to the packet in front of the IP header, and sends the packet straight to D via the LAN. If, however, Anet and Dnet do not match – D is non-local – then A looks up a router to use. Most ordinary hostsuseonlyonerouterforallnon-localpacketdeliveries,makingthischoiceverysimple. Athenforwards the packet to the router, again using direct delivery over the LAN. The IP destination address in the packet remains D in this case, although the LAN destination address will be that of the router. When the router receives the packet, it strips off the LAN header but leaves the IP header with the IP destination address. It extracts the destination D, and then looks at Dnet. The router ﬁrst checks to see if any of its network interfaces are on the same LAN as D; recall that the router connects to at least one additionalnetworkbesidestheoneforA.Iftheanswerisyes,thentherouterusesdirectLANdeliverytothe destination,asabove. If,ontheotherhand,Dnet isnotaLANtowhichtherouterisconnecteddirectly,then the router consults its internal forwarding table. This consists of a list of networks each with an associated next_hop address. These xnet,next_hopy tables compare with switched-Ethernet’s xhost,next_hopy tables; theformertypewillbesmallerbecausetherearemanyfewernetsthanhosts. Thenext_hopaddressesinthe table are chosen so that the router can always reach them via direct LAN delivery via one of its interfaces; generally they are other routers. The router looks up Dnet in the table, ﬁnds the next_hop address, and uses direct LAN delivery to get the packet to that next_hop machine. The packet’s IP header remains essentially unchanged, although the router most likely attaches an entirely new LAN header. The packet continues being forwarded like this, from router to router, until it ﬁnally arrives at a router that is connected to Dnet; it is then delivered by that ﬁnal router directly to D, using the LAN.