《计算机网络英文版课件5》由会员分享，可在线阅读，更多相关《计算机网络英文版课件5（119页珍藏版）》请在金锄头文库上搜索。
1、Computer network Chapter 5 The Network Layer,郭 斌 E_mail: ,The Network Layer,The network layer is mainly concerned with getting packets from the source all the way to the destination, providing end-to-end transmission. Provides services to the transport layer Carry through congestion control Internet
2、working,Topics,Network Layer Design Issues Routing Algorithms Congestion Control Algorithms Internetworking The Network Layer in the Internet,Network Layer Design Issues,Store-and-Forward Packet Switching Services Provided to the Transport Layer Implementation of Connectionless Service Implementatio
3、n of Connection-Oriented Service Comparison of Virtual-Circuit and Datagram Subnets,Store-and-Forward Packet Switching,At the network layer, the packet is delivered by intermediate routers hop by hop using store-and-forward packet switching.,Services Provided to the Transport Layer,The network layer
4、 services have been designed with the following goals in mind. The services should be independent of the routers technology. The transport layer should be shielded from the number, type, and topology of the routers present. The network addresses made available to the transport layer should use a uni
5、form numbering plan, even across LANs and WANs. Two type: Connectionless services Connection-oriented services,Implementation of Connectionless Service,No advance setup is needed. Packets are injected into the subnet individually and routed independently of each other. The packets are called datagra
6、ms and the subnet is called a datagram subnet.,Implementation of Connection-Oriented Service,A route from the source machine to the destination machine must be set up in advance, and stored in tables inside the routers.That route is used for all traffic flowing over the connection. This connection i
7、s called a VC (virtual circuit) and the subnet is called a virtual-circuit subnet.,Comparison of Virtual-Circuit and Datagram Subnets,Routing Algorithms,Shortest Path Routing Flooding Distance Vector Routing Link State Routing Hierarchical Routing,Routing Algorithm Basics,The routing algorithm is th
8、at part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on. If the subnet uses datagrams internally, this decision must be made anew for every arriving data packet since the best route may have changed since last time. If the subnet u
9、ses virtual circuits internally, routing decisions are made only when a new virtual circuit is being set up.,Routing Algorithm Basics(2),Two major classes of routing algorithms Nonadaptive or Static: the routing table is computed in advance, off-line, and downloaded to the routers when the network i
10、s booted. Adaptive or Dynamic: change their routing decisions to reflect changes in the topology, and usually the traffic as well. Adaptive routing algorithm What Metric is used for optimization Distance ,Number of hops,Estimated transit time where they get their information e.g., locally, from adja
11、cent routers, or from all routers when they change the routes e.g., every T sec, when the load changes or when the topology changes,Shortest Path Routing,Idea: build a graph of the subnet, with each node of the graph representing a router and each arc of the graph representing a communication line.
12、To choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph. the labels (weights) on the arcs could be computed as a function of the distance, bandwidth, average traffic, communication cost, measured delay, and other factors. Shortest Path
13、Criteria: sum of the weights all the way, or, the number of hops.,Shortest Path Routing (2),Dijkstra Algorithm 1. Mark every node as unscanned and give each node a label of INF 2. Set the label of the root to 0 and the predecessor of the root to itself. The root will be the only node that is its own
14、 predecessor. 3. Loop until you have scanned all the nodesFind the node n with the smallest label. Since the label represents the distance to the root we call it d_min.Mark the node as scanned.Scan all the adjacent nodes m and see if the distance to the root through n is shorter than the distance st
15、ored in the label of m. if it is, update the label and update pred m = n.Min neighbors (dist(root, neighbor) + dist(neighbor, node) 4. When the loop finishes, we have a tree stored in pred format rooted at the root,Shortest path routing (3),Flooding,Basic idea: Forward an incoming packet across ever
16、y outgoing line, except the one it came through. Basic problem: how to avoid “drowning by packets”?,Flooding (1),solution Use a hop counter: after a packet has been forwarded across N routers, it is discarded. Be sure to forward a packet only once (i.e. avoid directed cycles). Requires sequence numbers per source router. Flood selectively: only on those lines that are going approximately in the right direction. Flooding is not practical in most applications, but it does have some uses for in military applications, the tremendous robustness of flooding is highly desirable .,
