通信網絡技術課件：chapter5 The Network Layer

1、Computer Networks2RoadmapIntroductionPhysical LayerData Link LayerTransport LayerNetwork LayerMedium Access SublayerApplication LayerThe Network LayerChapter 54What you will learn:5.1 Network layer design issues5.2 Routing algorithms5.3 Congestion control algorithms5.4 Quality of service5.5 Internet

2、working5.6 The Networking layer in the internetThe Network Layer is concerned about getting packets from source to destination, no matter how many hops it may take. Its all about routing . The network layer is the lowest layer that deals with end-to-end transmission. 55.1 Network Layer Design Issues

3、Store-and-Forward Packet SwitchingServices Provided to the Transport LayerImplementation of Connectionless ServiceImplementation of Connection-Oriented ServiceComparison of Virtual-Circuit and Datagram Subnets6Store-and-Forward Packet SwitchingThe environment of the network layer protocols.fig 5-17W

4、ho-Does-WhatThe network layer is responsible for routing packets from the source to destination. The routing algorithm is the piece of software that decides where a packet goes next (e.g., which output line, or which node on a broadcast channel). For connectionless networks, the routing decision is

5、made for each datagram. For connection-oriented networks, the decision is made once, at circuit setup time. 8Routing algorithm must dealCorrectness and simplicitynetworks are never taken down; individual parts (e.g., links, routers) may fail, but the whole network should not. Stabilityif a link or r

6、outer fails, how much time elapses before the remaining routers recognize the topology change? (Some never do.) Fairness and optimality: an inherently intractable problem. Definition of optimality usually doesnt consider fairness.Do we want to maximize channel usage? Minimize average delay? When we

7、look at routing in detail, well consider both adaptive-those that take current traffic and topology into consideration-and non-adaptive algorithms. 9Congestion (NOT Contention)The network layer also must deal with congestion: When more packets enter an area than can be processed, delays increase and

8、 performance decreases. If the situation continues, the subnet may have no alternative but to discard packets. If the delay increases, the sender may (incorrectly) retransmit, making a bad situation even worse. Overall, performance degrades because the network is using (wasting) resources processing

9、 packets that eventually get discarded.10InternetworkingWhen we consider internetworking, connecting different network technologies together, there are the same problems, only worse: Packets may travel through many different networks Each network may have a different frame format Some networks may b

10、e connectionless, other connection oriented.11Services Provided to the Transport LayerDesign GoalsThe services should be independent of the router technologyThe transport layer should be shielded from the number, type , and topology of the routers present.The network addresses made available to the

11、transport layer should use a uniform numbering plan, even across LANs and WANs.12Services Provided to the Transport LayerConnection-Oriented Service: The subnet, with the help of the network layer, should provide the following operations:The sending side of the pair should open a connection with its

12、 peer.This connection has properties negotiated by the pair.Communication is bi-directional and packets are delivered in order.Flow control is accomplished in the subnet.Connectionless Service: The subnet has no state information. It does only send_packet and receive_packet. Error control and flow c

13、ontrol are done by the host (network or higher layers.)13 “Does error/flow control belong in network or transport layer?” Internet community viewpoint: The subnet is inherently unreliable no matter how it is designed. Thus, hosts are forced to do error/flow control anyway. Given that they perform er

14、ror/flow control, why have the network layer duplicate the same function? The TCP/IP Internet is connectionless in its implementation but provides connections to its users.Common carrier viewpoint: The connection oriented approach is the right way. Users dont want complex error/flow control protocol

15、s in host computers. Users want reliable, trouble-free service. (ATM) 14Implementation of Connectionless ServiceDatagram for connectionless service:Each packet sent is routed independently of its predecessors. Decisions are made on the fly, so more computing required, however this method is more rob

16、ust.Virtual Circuit for connection-oriented service:A path from the source router to the destination router must be established before any data packets can be sent.Avoids choosing a new route for each packet. A virtual circuit is a state - it remembers how to send a packet from source to destination

17、. This state is held in the subnet, in the source DLL or in each of the DLL layers along the route.15Implementation of Connectionless ServiceRouting within a diagram subnet.Every router has an internal table telling it where to send packets for each possible dest. Each table entry is a pair consisti

18、ng of a dest and the outgoing line to use for that dest.16Implementation of Connection-Oriented ServiceRouting within a virtual-circuit subnet.Incoming packets with connection id 1 is to be sent to router C and given id 117Implementation of Connection-Oriented ServiceVirtual Circuit : “Source-to-des

19、t path behaves much like telephone circuit”Call setup, teardown for each call before data can flowEach packet carries VC identifier (not destination host ID)Every router on source-destination path maintains “state” for each passing connectionTransport-layer connection only involved two end systemsLi

20、nk, router resources (bandwidth, buffers) may be allocated to VCUsed in ATM, frame-relay, X.2518Comparison of Virtual-Circuit and Datagram Subnets5-419Trade-offs between VC and datagramRouter memory space and bandwidthIf the packets tend to be fairly short, a full dest. Address in every packet may r

21、epresent a significant amount of overhead and wasted bandwidth. The price paid for using VC is the table space within the routers.Setup time versus address parsing timeUsing VC requires a setup phase, which takes time. In a datagram subnet, a more complicated lookup procedure is required to locate t

22、he entry for the destination.Amount of table space required in router memory205.2 Routing AlgorithmsThe Optimality PrincipleShortest Path RoutingFloodingDistance Vector RoutingLink State RoutingHierarchical RoutingBroadcast RoutingMulticast RoutingRouting for Mobile HostsRouting in Ad Hoc Networks21

23、Routing AlgorithmsRouting is concerned with the question: Which line should router J use when forwarding a packet to router K ? Goal: determine “good” path (sequence of routers) through network from source to destinationThe routing algorithm is that part of the network layer software responsible for

24、 deciding which output line an incoming packet should be transmitted on.22Routing AlgorithmsGraph abstraction for routing algorithms:1.graph nodes are routers2.graph edges are physical linkslink cost: delay, $ cost, or congestion level“Good” path:typically means minimum cost pathother definitions po

25、ssible23Routing AlgorithmsPropertiesCorrectness and SimplicityRobustnessDuring years of continuous operation, being able to handle all kinds of hardware and software failures. Being able to handle changes in topology and traffic patterns.StabilityOf the algorithms. Can you get a mathematical and rea

26、listic answer.Fairness and OptimalityOften contradictory24Routing AlgorithmsConflict between fairness and optimality.25Routing AlgorithmsThere are two types of algorithms: Adaptive algorithms - use such dynamic information as current traffic, topology, delay, etc. to select routes. Non-adaptive algo

27、rithms - routes never change once initial routes have been selected. Also called static routing. 26Adaptive algorithmsAdaptive algorithms can be further divided in the following types: Isolated: each router makes its routing decisions using only the local information it has on hand. Specifically, ro

28、uters do not even exchange information with their neighbors. Centralized: a centralized node makes all routing decisions. Specifically, the centralized node has access to global information. Distributed: algorithms that use a combination of local and global information. 27The Optimality PrincipleThe

29、 Optimality Principle:This simply states that if router I is on the optimal path from router J to router K, then the optimal path from I to K also falls along this same path.This means we can form a sink tree (optimal paths to B) as in the Figure.28The Optimality Principle(a) A subnet. (b) A sink tr

30、ee for router B.29Shortest Path RoutingOften used because simple and easy to understandShortest Path Metrics (Path Length)Number of HopsPhysical DistanceMean Queuing and Transmission DelayBandwidthAverage TrafficCommunication Cost30Shortest Path RoutingUse Dijkstras algorithm (or variation) (SPF, Sh

31、ortest Path First algorithm)Basic idea is: Choose the source, and put nodes connected to source in list to consider. From the list to consider choose the nearest node. 31Shortest Path RoutingThe first 5 steps used in computing the shortest path from A to D. The arrows indicate the working node.32Dij

32、sktras Algorithm1 Initialization: 2 N = A 3 for all nodes v 4 if v one-step reachable from A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v one-step reachable from w and not in N: 12 D(v) = min( D(v), D(w) + c

33、(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N33Dijsktras AlgorithmDijkstras algorithm to compute the shortest path through a graph.5-8 top 34Dijsktras AlgorithmDijkstras algorithm to compute the shortest path

34、through a graph.5-8 bottom35FloodingFlooding is a form of isolated routing. Does not select a specific route. When a router receives a packet, it sends a copy of the packet out on each line (except the one on which it arrived).To prevent packets from looping forever, each router decrements a hop cou

35、nt contained in the packet header. Whenever the hop count decrements to zero, the router discards the packet.36FloodingTo reduce looping even further: Add a sequence number to each packets header. Each router maintains a private sequence number. When it sends a new packet, it copies the sequence num

36、ber into the packet, and increments its private sequence number. For each source router S, a router: Keeps track of the highest sequence number seen from S. Whenever it receives a packet from S containing a sequence number lower than the one stored in its table, it discards the packet. Otherwise, it

37、 updates the entry for S and forwards the packet on 37FloodingFlooding has several important uses: In military applications, the network must remain robust in the face of (extreme) hostility Sending routing updates, because updates cant rely on the correctness of a routers routing table. Theoretical

38、-chooses all possible paths, so it chooses the shortest one. In selective flooding, a router sends packets out only on those lines in the general direction of the destination. That is, dont send packets out on lines that clearly lead in the wrong direction. 38Dynamic routing algorithmsDistance Vecto

39、r RoutingEach router maintain a table giving the best known distance to each destination and which line to use to get thereThese tables are updated by exchanging information with the neighborsExample: RIP, IGRP, EIGRPAlso known as Bellman-Ford/Ford-FulkersonLink State Routing39Distance Vector Routin

40、gRouters work together. Each router maintains a table (vector) giving the best known distance to a destination and the line to use for sending there. Tables are updated by exchanging information with neighbors. Each router knows the distance (cost) of reaching its neighbors (e.g. send echo requests)

41、. Routers periodically exchange routing tables with each of their neighbors. Upon receipt of an update, for each destination in its table, a router:Compares the metric in its local table with the metric in the neighbors table plus the cost of reaching that neighbor.if the path via the neighbor has a

42、 lower cost, the router updates its local table to forward packets to the neighbor40Distance Vector Routing(a) A subnet. (b) Input from A, I, H, K, and the new routing table for J. Metric is delay JA: 8 ms JI: 10ms JH: 12ms JK: 6msOutgoing link to usecostdestination41The Count-to-Infinity ProblemThi

43、s algorithm was used in the original ARPANET. Unfortunately, it suffers from the problem: convergence takes time, good news travels quickly, bad news travels slowly (count-to-infinity problem). 42The Count-to-Infinity ProblemThe count-to-infinity problem.Suppose A is down initially and all the Other

44、s know this.When A comes up, the other routers Learn about it via the vector exchanges.All routers are initially up, and Suddenly A goes down43The Count-to-Infinity ProblemThe core of the problem is:When X tells Y that it has a path somewhere, Y has no way of knowing whether it itself is on the path

45、.Attempts to solve:Split horizon with poisoned reverse in RFC 105844Link State RoutingThe old Arpanet routing algorithm was replaced in 1979. Problems with old algorithm included:High-priority routing update packets were large, adversely affecting traffic. Network was too slow in adapting to congest

46、ion, too fast to react to minor changes.Average queue length was used to estimate delay. This works only if all lines have the same capacity and propagation delay.Doesnt take into account that packets have varying sizes. 45Link State RoutingIn the new algorithm: Each router maintains a database desc

47、ribing the topology and link delays between each router. That is, each router keeps track of the full graph of links and nodes. Each router periodically discovers it neighborsSends hello message on booting.Measures the delays across its links (echo requests - should load be taken into account?),Forw

48、ards that information to all other routers (link state packets). Avoids the count to infinity problem since all routers get each other routers information.46Link State Routing4.Updates are propagated at high priority using flooding. Updates contain sequence numbers, and a router forwards new copies

49、of the packet. Why use flooding? Because that way routing updates propagate even when routing tables arent quite correct. ACKs are sent to neighbors. 5.Each router uses an SPF algorithm to calculate shortest paths based on the current values in its database. 6.Because each router makes its calculati

50、on using the same information, better routing decisions are made.47Link State RoutingEach router must do the following:Discover its neighbors, learn their network address.Measure the delay or cost to each of its neighbors.Construct a packet telling all it has just learned.Send this packet to all oth

51、er routers.Compute the shortest path to every other router.48Learning about the Neighbors(a) Nine routers and a LAN. (b) A graph model of (a).When a router is booted, its first task is to learn who its neighbors are. It accomplishes this goal by sending a special HELLO packet on each point-to-point

52、line. 49Measuring Line CostThe Most direct way to determine the delay is to send over the line a special ECHO packet that other side is required to send back immediately. By measuring the round-trip time and dividing it by two, the sending router can get a reasonable estimate of the delay. For even

53、better results, the test can be conducted several times, and the average used. 50Should load be taken into account?Whether to take the load into account when measuring the delay?A subnet in which the East and West parts are connected by two lines.51Building Link State Packets(a) A subnet. (b) The li

54、nk state packets for this subnet.Sequence number (32-bits, one per second, wrap around after 137 years)Age for the packet (decrement once per second)A list of neighbors and delay for it52Distributing the Link State PacketsBasic distribution algorithm: FloodingTo keep the flood in check, each packet

55、contains a sequence number that is incremented for each new packet sent. Routers keep track of all the (source router, sequence) pairs they see. When a new link state packet comes in, it is checked against the list of packets already seen. If it is new, it is forwarded on all lines except the one it

56、 arrived on. If it is a duplicate, it is discarded. If a packet with a sequence number lower than the highest one seen so far ever arrives, it is rejected as being obsolete since the router has more recent data. 53Distributing the Link State PacketsProblems:Sequence number confusionRouter crashes an

57、d lose track of its sequence num.A sequence number is corrupted.The Age field The solution to all these problems is to include the age of each packet after the Seq. and decrement it once per second. When the age hits zero, the information from that router is discarded.54Distributing the Link State P

58、acketsAlgorithm RefinementsWhen a link state packet comes in to a router for flooding, it is not queued for transmission immediately. Instead it is first put in a holding area to wait a short while. If another link state packet from the same source comes in before the first packet is transmitted, th

59、eir sequence numbers are compared. If they are equal, the duplicate is discarded. If they are different, the older one is thrown out. To guard against errors on the router-router lines, all link state packets are acknowledged. When a line goes idle, the holding area is scanned in round-robin order t

60、o select a packet or acknowledgement to send 55Distributing the Link State PacketsThe packet buffer for router B in the previous slide (Fig. 5-13).The send flags mean that the packet must be sent on the indicated line.The ack flags mean that it must be acknowledged there.To reduce the numbers of lin