Routing

RoutingRouting is the mechanism that enables a data packet to find its way to adestination, whether that is a device in the next room or on the other sideof the world.A router compares the destination address of each data packet it receiveswith a table of addresses held in memory — the router table. If it finds aChapter Two16match in the table, it forwards the packet to the address associated withthat table entry, which may be the address of another network or of a“next-hop” router that will pass the packet along towards its finaldestination.If the router can’t find a match, it goes through the table again looking atjust the network ID part of the address (extracted using the subnet maskas described above). If a match is found, the packet is sent to theassociated address or, if not, the router looks for a default next-hopaddress and sends the packet there. As a final resort, if no default addressis set, the router returns a “Host Unreachable” or “Network Unreachable”message to the sending IP address. When this message is received itusually means that somewhere along the line a router has failed.What happens if, or when, this elegantly simple structure breaks down?Are there packets out there hopping forever around the Internet,passing from router to router and never finding their destination? The IPheader includes a control field that prevents this from happening. Thetime-to-live (TTL) field is initialised by the sender to a certain value,usually 64, and reduced by one each time the packet passes througha router. When TTL get down to zero, the packet is discarded and thesender is notified using an Internet Control Message Protocol (ICMP)“time-out” message. Building Router TablesThe clever part of a router’s job is building its routing table. For simplenetworks a static table loaded from a start-up file is adequate but, moregenerally, Dynamic Routing enables tables to be built up by routerssending and receiving broadcast messages.These can be either ICMP Router Solicitation and Router Advertisementmessages which allow neighbouring routers to ask “Who’s there?” andrespond “I’m here”, or more useful RIP (Router Information Protocol)messages, in which a router periodically broadcasts its complete routertable onto the network.Other RIP and ICMP messages allow routers to discover the shortest pathto an address, to update their tables if another router spots an inefficientrouting and to periodically update routes in response to networkavailability and traffic conditions. A major routing challenge occurs in mesh or mobile ad-hoc networks(MANETs), where the network topology may be continuously changing.One approach to routing in MANETs, inspired by ant behaviour, isdescribed in the Section “Wireless Mesh Network Routing, p. 345”.