Cho dù các lớp mạng cung cấp một dịch vụ datagram (trong trường hợp các gói tin khác nhau giữa một cặp điểm đến cho chủ nhà có thể sử dụng các tuyến khác nhau) hoặc một dịch vụ mạch ảo (trong trường hợp tất cả các gói dữ liệu giữa nguồn và đích sẽ đi theo con đường tương tự), | Point-to-Point Routing Algorithms 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 . 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 today s networks. Figure Abstract model of a network The graph abstraction used to formulate routing algorithms is shown in Figure . 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 . the current average delay for a packet .
