云物流实例资料.docVIP

Routing Principles In order to transfer packets from a sending host to the destination host, the network layer must determine the path or route that the packets are to follow. Whether the network layer provides a datagram service (in which case different packets between a given host-destination pair may take different routes) or a virtual circuit service (in which case all packets between a given source and destination will take the same path), the network layer must nonetheless determine the path for a packet. This is the job of the network layer routing protocol. At the heart of any routing protocol is the algorithm (the routing algorithm) that determines the path for a packet. The purpose of a routing algorithm is simple: given a set of routers, with links connecting the routers, a routing algorithm finds a good path from source to destination. Typically, a good path is one which has least cost, but we will see that in practice, real-world concerns such as policy issues (e.g., a rule such as router X, belonging to organization Y should not forward any packets originating from the network owned by organization Z) also come into play to complicate the conceptually simple and elegant algorithms whose theory underlies the practice of routing in todays networks. Figure 4.2-1: Abstract model of a network The graph abstraction used to formulate routing algorithms is shown in Figure 4.2-1. (To view some graphs representing real network maps, see [Dodge 1999] ; for a discussion of how well different graph-based models model the Internet, see [Zegura 1997]). Here, nodes in the graph represent routers - the points at which packet routing decisions are made - and the lines (edges in graph theory terminology ) connecting these nodes represent the physical links between these routers. A link also has a value representing the cost of sending a packet across the link. The cost may reflect the level of congestion on that link (e.g., the current average delay for a packet