计算机网络英文版课件5

Computer network Chapter 5 The Network Layer,郭 斌 E_mail: jxnuit163.com,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 Internetworking,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 Implementation 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 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 uniform 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 datagrams 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 is 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 that 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 uses 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 is 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 adjacent 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. 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 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 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 stored 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 every 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 .,