Free Trial

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

Share this Page URL

APPENDIX Detailed Models > A.2 HARDWARE MODELS - Pg. 437

A.2 Hardware Models 437 estimate of 1 from R4. Thus R2 picks the shorter-distance neighbor, R4, to reach D. If the link from R2 to R4 fails, R2 will time-out this link, set its estimate of distance to D through R4 to infinity, and then choose the route through R3. Unfortunately, distance vector takes a long time to converge when destinations become unreachable [Per92]. Link state routing [Per92] avoids the convergence problems of distance vector by having each router construct a link state packet listing its neighbors. In Figure A.2, for instance, R3's link state packet (LSP) will list its links to R2 and R4. Each router then broadcasts its LSP to all other routers in the domain using a primitive flooding mechanism; LSP sequence numbers are used to prevent LSPs from circulating forever. When all routers have each other's LSP, every router has a map of the network and can use Dijkstra's algorithm [Per92] to calculate shortest-path routes to all destinations. The most common routing protocol used within ISP domains is a link state routing protocol called open shortest path first (OSPF) [Per92]. While shortest-path routing works well within domains, the situation is more complex for routing between domains. Imagine that Figure A.2 is modified so that the ISP in the middle, say, ISP A, does not have a direct route to D's domain but instead is connected to ISPs C and E, each of which has a path to D's domain. Should ISP A send a packet addressed to D to ISP C or E? Shortest-path routing no longer makes sense because ISPs want to route based on other metrics (e.g., dollar cost) or on policy (e.g., always send data through a major competitor, as in so-called "hot potato" routing). Thus interdomain routing is a more messy kettle of fish than routing within a domain. The most commonly used interdomain protocol today is called the border gateway protocol (BGP) [Ste99], which uses a gossip mechanism akin to distance vector, except that each route is augmented with the path of domains instead of just the distance. The path ostensibly makes convergence faster than distance vector and provides information for policy decisions. To go beyond this brief sketch of routing protocols, the reader is directed to Intercon- nections by Radia Perlman [Per92] for insight into routing in general and to BGP-4 by John Stewart [Ste99] as the best published textbook on the arcana of BGP.