计算机网络英文版课件：ch5-network

1、5 The Network Layer Network LayerNetwork Layer Design IssuesIssues Datagram Virtual Circuit Routing AlgorithmsShortest Path Routing Flooding Distance Vector Routing Link State Routing Hierarchical Routing Congestion Control AlgorithmsGeneral Principles Congestion Prevention Congestion Control Load S

2、heddingQuality of ServiceInternetworkingNetwork Layer in the InternetInternets Network Layer IPv4 Header ICMP IP Addresses & Routing Table NATARP,DHCPOSPFBGP IPv6HomeWork (1) (2)OverviewNetwork layer is the lowest layer that deals with end-to-end transmission Network layer must know about topology A

3、void overloading some of the communication lines and routers while leaving others idle5.1 Network Layer Design IssuesIssuesNetwork Layer Design IssuesServices Provided to Transport LayerInternal Organization of Network LayerStore-and-Forward Packet Switching Services Provided to Transport LayerDesig

4、n GoalThe transport layer should be shielded from the number, type, and topology of the routers presentThe network addresses made available to the transport layer should use a uniform numbering plan, even across LANs and WANsTwo classes serviceConnection-Oriented Service (Virtual Circuit)Connectionl

5、ess Service (Datagram)DatagramDatagram (1)Routing within a datagram subnetDatagram (2)TransportNetworkDatalink Process P1 has a long message for P2Datagram(3)B.3B.2B.1C.3C.2C.1C.3C.1C.2B.1B.3B.2ABCA12345BCB.3B.2B.1C.3C.2C.1Virtual Circuit Virtual Circuit (1)Routing within a virtual-circuit subnet.Vi

6、rtual Circuit(2)B.3B2B.1C.3C.2C.1C.3C.2C.1B.3B.2B.1ABCA12345BCvc1vc2 vc1: A-1-2-4-B vc2: A-1-3-5-C Virtual-Circuit vs. Datagram5-45.2 Routing AlgorithmsResponsibility of Routing AlgorithmsResponsible for deciding which output line an incoming packet should be transmitted onIf the subnet uses datagra

7、ms internally, this decision must be made anew for every arriving data packet since the best route may have changed since last timeIf the subnet uses virtual circuits internally, routing decisions are made only when a new virtual circuit is being set up. Thereafter, data packets just follow the prev

8、iously-established route (Session routing)Forwarding & RoutingGoals for the Routing AlgorithmCorrectness Simplicity Robustness Stability FairnessOptimalityMinimizing mean packet delayMaximizing total network throughputClassification of Routing AlgorithmsNonadaptive algorithms (Static Routing)Do not

9、base their routing decisions on measurements or estimates of the current traffic and topologyThe choice of the route to use is computed in advance, off-line, and downloaded to the routers when the network is booted Adaptive algorithmsChange their routing decisions to reflect changes in the topology,

10、 and usually the traffic as wellThe Optimality PrincipleIf router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same routeIf a route rx better than r2 existed from J to K, it could be concatenated with r1 to improve the route from I to KCo

11、ntradicting our statement that r1r2 is optimal IKJr1r2rx r1+r2 r1+rxSink TreeOptimal routes from all sources to a destination form a tree rooted at the destinationDoes not contain any loops, so each packet will be delivered within a finite number of hopsThe goal of routing algorithmsDiscover and use

12、 the sink trees for all routers Different routers may have different ideas about the current topology sometimeExample of Sink Tree(a) A subnet. (b) A sink tree for router BShortest Path RoutingShortest Path RoutingBuild a weighted and directed graph of subnetNodes represent routersArcs represents co

13、mmunication linesWeightHops Geographic distance in kilometers Mean queueing and transmission delayDetermined by hourly test, some standard test packetA function of the distance, bandwidth, average traffic, communication cost, mean queue length, measured delay, and other factors Dijkstra AlgorithmFin

14、ds the shortest path between a given pair of routersFloodingFloodingNo network info requiredIncoming packets retransmitted on every link except incoming linkEventually a number of copies will arrive at destination146235Flooding Example (Step 1)124356Flooding Example (Step 2)124356Flooding Example (S

15、tep 3)Techniques for Damping the FloodProblemGenerates vast numbers of duplicate packetsan infinite number unless some measures are taken to damp the process MeasuresThe header of each packet contains a hop counterCounter is decremented at each hopWhen the counter reaches zero, discard the packetSen

16、der initializes the hop counter as the length of the path from source to destination, or the subnet diameterSource puts a sequence number in each packetEach router records maximal seq per source telling which seq have already been seenSelective floodingEach router records received data items in data

17、baseEvery data items contains a version numberOlny new data items will be floodedSelective Flooding Example (Step 1)462351Selective Flooding Example (Step 2)243561Selective Flooding Example (Step 3)124356Properties of FloodingAll possible routes are triedVery robustAt least one packet will have take

18、n minimum hop count routeAll nodes are visitedUseful to distribute routing informationDistance Vector RoutingDistance Vector RoutingRouted by rumorEach router maintains a tableThe best known distance to each destinationThe distance might be number of hops, time delay in milliseconds, Which line to u

19、seThe table is updated by exchanging information with neighbors Send Routing information (Destination, Distance)Periodically (RIP Routing Information Protocol:30 seconds)Whenever table changes (triggered update)Receive Routing informationUpdate local table if receive a better routeRefresh existing r

20、outesDelete routing table items if they time out (RIP 180s)Example 1Input from A, I, H, K, and the new routing table for J.Example 2: Initial StatusAC127BD31Dest.CostNextHopB2BC7CD-Node ADest.CostNextHopA2AC1CD3DNode BDest.CostNextHopA7AB1BD1DNode CDest.CostNextHopA-B3BC1CNode DDest.CostNextHopB2BC7

21、CD8CNode AExample 2: 1st Iteration (C A)AC127BD31Dest.CostNextHopA2AC1CD3DDest.CostNextHopA7AB1BD1DNode CDest.CostNextHopA-B3BC1CNode DD(A, D) = D(A, C) + D(C,D) = 7 + 1 = 8(D(C,A), D(C,B), D(C,D)Node BDest.CostNextHopB2BC3BD5BNode AExample 2: 1st Iteration (BA, CA)AC127BD31Dest.CostNextHopA2AC1CD3D

22、Node BDest.CostNextHopA7AB1BD1DNode CDest.CostNextHopA-B3BC1CNode DD(A,D) = D(A,B) + D(B,D) = 2 + 3 = 5 D(A,C) = D(A,B) + D(B,C) = 2 + 1 = 3 Example 2: End of 1st IterationAC127BD31Dest.CostNextHopB2BC3BD5BNode ADest.CostNextHopA2AC1CD2CDest.CostNextHopA3BB1BD1DNode CDest.CostNextHopA5BB2CC1CNode DN

23、ode BExample 2: End of 2nd IterationAC127BD31Dest.CostNextHopB2BC3BD4BDest.CostNextHopA2AC1CD2CDest.CostNextHopA3BB1BD1DNode CDest.CostNextHopA4CB2CC1CNode DNode ANode BExample 2: End of 3rd IterationAC127BD31Dest.CostNextHopB2BC3BD4BDest.CostNextHopA2AC1CD2CDest.CostNextHopA3BB1BD1DNode CDest.CostN

24、extHopA4CB2CC1CNode DNothing changes algorithm terminatesNode ANode BCount-to-infinity ProblemBC 11AD1“bad news travels slowly”cost(B,A)= DCNA1AC1CD2CBtimeDCNA2BB1BD1DDCNA3CB2CC1CCDDCNA-C1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CDCNA4BB1BD1DDCNA3CB2CC1CDCNA5CC1CD2C

25、DCNA4BB1BD1DDCNA5CB2CC1CDCNA5CC1CD2CDCNA6BB1BD1DDCNA5CB2CC1CDCNA7CC1CD2CDCNA6BB1BD1DDCNA7CB2CC1CAnother problem:cost(B,A): changed 1 to 4 cost(B,A): changed 4 to 1 RIP: Set infinity to 16Problem of Distance Vector RoutingDistance Vector RoutingRIP (Routing Information Protocol)Cisco EIGRP (Enhanced

26、Interior Gateway Routing Protocol)The problem of Distance Vector algorithmWhen X tells Y that it has a path somewhere, Y has no way of knowing whether it itself is on the pathPath Vector Routing BGP-4 (Border Gateway Protocol)IDRP (Inter-domain Routing Protocol)Link State RoutingLink State Routing E

27、ach router must do the following Discover its neighbors, learn their network addressMeasure the delay or cost to each of its neighborsConstruct a packet (LSP: Link-state Packet) telling all it has just learned Send LSP to all other routers (not only neighbors) reliablyCompute the shortest path to ev

28、ery other router1. Learning about the NeighborsHELLO packet Broadcast network: Broadcast a special HELLO packetMulti-access network: Unicast HELLO to neighborsNeighbors send back a reply telling who it isNames (Route IDs) must be globally uniqueSimplify the topologyWhen two or more routers are conne

29、cted by a LAN or other multi-access networkArtificial Node (a) Nine routers and a LAN. (b) A graph model of (a)2. Measuring Line CostThe delay to each of its neighborsMeasuring the round-trip time (ECHO Packet)BandwidthAn issue is whether to take the load into account when measuring the delay? (rout

30、ing tables may oscillate, leading to erratic routing and many potential problems) 3. Building Link State PacketsWhen to build LSPBuild LSP periodicallyBuild LSP when some significant event occurssuch as a line or neighbor going down or coming back up again or changing its properties appreciably (a)

31、A subnet. (b) The link state packets for this subnet4. Distributing the Link State PacketsResponsibilityDistributing the LSP reliablyAvoid different routers from using different versions of the topology, which can lead to inconsistencies, loops, unreachable machines, and other problemsThe basic dist

32、ribution algorithm Use flooding to distribute LSPsGuard against errors on the router-router lines, all LSP are acknowledgedAbout Link State PacketsSequence numberIf LSP is new, forwarded it on all lines except the one it arrived onIf LSP is a duplicate, it is discarded (selective flooding)If lower t

33、han the highest one seen so far ever arrives, it is rejected as being obsoleteIf a router is down, and then restart, .if the sequence numbers wrap around, if a sequence number is ever corrupted, AgeIf a router is downIf a router changed its routerIDIf a router need to delete an LSPRefinements to LSP

34、 Flooding Algorithm5. Computing the New RouteOnce a router has accumulated a full set of LSPs, it can construct the entire graphEvery link is represented twice, once for each direction. The two values can be averaged or used separatelyRun Dijkstras algorithm locally to construct the shortest path to

35、 all possible destinationsThe results of this algorithm can be installed in the routing tables局域网 L1局域网 L2(a) 网络拓扑22544333288131212107616ABHGFECDI广域网 W5广域网 W3广域网 W2广域网 W6广域网 W1广域网 W4(b) 有向图L1L2W1W3W2DBCAIHGFE12422233341312167788810W4W64W565有向图L1L2W1W3W2DBCAIHGFE12422233341312167788810W4W64W565L1L2W1

36、W3W2DBAIGFE4331216788W4W6W5654以路由器F为根的最短路径树 F的路由表DestNextHopL1DL2GW1DW2DW3(direct)W4DW5(direct)W6GExamples of Link State RoutingIS-IS (Intermediate System-Intermediate System):DECnetISO CLNPIPAppleTalkNovell NLSP (IPX)support multiple network layer protocols at the same time OSPF (Open Shortest Path

37、 First)designed several years after IS-IS Only for IPHierarchical RoutingHierarchical Routing (1)Hierarchical Routing (2)Consider a subnet with 720 routers. If there is no hierarchy720 routing table entriesIf the subnet is partitioned into 24 regions of 30 routers each (Total:53)30 local entries23 r

38、emote entries If a three-level hierarchy is chosen, with 8 clusters, each containing 9 regions of 10 routers (Total: 25)10 entries for local routers8 entries for routing to other regions within its own cluster7 entries for distant clusters5.3 Congestion Control AlgorithmsGeneral Principles of Conges

39、tion ControlCongestion When too much traffic is offered, congestion sets in and performance degrades sharply次要因素：突发流量与缓冲队列(太长/太短) 慢CPU忙于维护操作，转发操作太慢导致线路容量浪费Congestion Control & Flow ControlThe difference between congestion control and flow controlCongestion control is a global issueFlow control is to

40、 make sure that a fast sender cannot continually transmit data faster than the receiver is able to absorb itGeneral Principles of Congestion ControlOpen loopAttempt to solve the problem by good design to make sure it does not occur in the first placeOnce the system is up and running, midcourse corre

41、ctions are not madeClosed loopBased on the concept of a feedback loopExplicit feedback Implicit feedbackClosed Loop: A Feedback LoopStep 1: Monitor the system, detect when and where congestion occursStep 2: Pass information to where action can be takenStep 3: Adjust system operation to correct the p

42、roblem1.Information about CongestionPercentage of all packets discarded for lack of buffer spaceAverage queue lengthsNumber of packets that time out and are retransmittedAverage packet delay, and the standard deviation of packet delay 2.Transfer Information about CongestionTransfer congestion inform

43、ation from the point where it is detected to the point where something can be doneSend a packet to the traffic source, announcing the problem A bit reserved in every packet, when a router detects congested state, sets this bit for all outgoing packets, to warn the neighbors Hosts or routers periodic

44、ally send probe packet and collect information about congestion, use this information to route traffic around problem areas 3. Adjust System OperationKnowledge of congestion will cause the hosts to take appropriate action to reduce the congestion Time scale must be adjusted carefully (Router yells S

45、TOP/GO to sender)System oscillatingReacting too sluggishly To work well, some kind of averaging is neededTaxonomy for closed loop algorithms Explicit feedback: packets are sent back from the point of congestion to warn the sourceImplicit feedback: the source deduces the existence of congestion by ma

46、king local observations, such as the time needed for acknowledgements to come back Congestion Prevention Policies (Open loop)Congestion Prevention Policies LayerPoliciesTransportRetransmission policy Out-of-order caching policy Acknowlegement policy Flow control policy Timeout determinationNetwork V

47、irtual circuits vs. datagram inside the subnet Packet queuing and service policy Packet discard policy Routing algorithm Packet lifetime managementData linkRetransmission policy Go back NSelectiveOut-of-order caching policy Acknowlegement policy (piggyback)Flow control policy (windows size)Congestio

48、n Control in Virtual-Circuit Subnets(Closed Loop)Congestion Control in Virtual-Circuit SubnetAdmission control Once congestion has been signaled, no more virtual circuits are set up until the problem has gone awayAllow new virtual circuits, but carefully route all new virtual circuits around problem

49、 areasNegotiate an agreement between the host and subnet when a virtual circuit is set up Route new VC around Congestion AreasCongestion Control in Datagram Subnets(Closed Loop)Utilization of Output LinesA router monitors the utilization of its output linesu Recent utilizationf A sample of the insta

50、ntaneous line utilizationWhenever u moves above the threshold, the output line enters a warning state The Warning BitRoutersWhen output line enters a warning state, set the Warning Bit in the packets header (DECnet, Frame-relay)DestinationWhen packet arrived at its destination, the bit is copied int

51、o the next ACK back to the sourceSourceAs long as the warning bits continued to flow in, the source continued to decrease its transmission rateWhen they slowed to a trickle, increased the transmission rate. Traffic increased only when no router along the path was in troubleRouter-to-Source Choke Pac

52、ketsRoutersRouter sends a choke packet back to source host, giving it the destination found in the packetThe original packet is tagged so that it will not generate any more choke packetsChoke packet type: mild warning, stern warning, ultimatum Source host Receives choke packet, reduce the traffic se

53、nt to the specified destination by x percent (e.g. 50%)Ignore choke packets referring to that destination for a periodAfter that period, listens for more choke packetsIf one arrives, the host reduces the flow still moreIf no choke packets arrive, increase the flow Hosts can adjust traffic, e.g. wind

54、ow size1st choke packet causes the data rate to be reduced to 50%, 2nd one causes a reduction to 25%, and so onIncreases are done in smaller increments to prevent congestion from reoccurring quicklyHop-by-Hop Choke PacketsProblem of sending a choke packet to the sourceHigh speedOver long distanceHav

55、e the choke packet take effect at every hop it passes throughProvide quick relief at the point of congestion at the price of using up more buffers upstream Hop-by-Hop Choke Packets(a) A choke packet that affects only the source.(b) A choke packet that affects each hop it passes through.Load Shedding

56、Loading SheddingLoading SheddingWhen routers are being inundated by packets, just throw them awayPoliciesPick packets at random to drop Wine & Milk E.g. file transfer, multimediaRequires cooperation from the senders Packet priorityE.g. algorithms for compressing video, The low-priority packets being

57、 cheaper to send than the high-priority ones, Allow hosts to exceed the limits specified in agreement, but all excess traffic must be marked as low priorityRED (Random Early Detection)Drop packets before situation becomes hopelessWhen the average queue length on some line exceeds a threshold (be con

58、gested), action is takenHow should router tell source about the problem? Send a choke packetJust discard the selected packetSources respond to lost packets by slowing down their transmission rateOnly works when sources respond to lost packets by slowing down their transmission rateIn wireless networ

59、ks, where most losses are due to noise on the air link, this approach cannot be used. Jitter ControlJitter ControlJitterThe variation in the packet arrival timesHigh jitter will give an uneven quality to the sound or movie (VOD, Telephony, videoconferencing)Jitter ControlRouters check incoming packe

60、t to see how much the packet is behind or ahead of its scheduleThis information is stored in the packet and updated at each hopForwarding policies5.4 Quality of ServiceFour Primary ParametersReliabilityDelayJitterBandwidthRequirements5-30ATM Networks: Flow ClassificationATM networks classify flows i