山東大學(xué)計算機網(wǎng)絡(luò)英語課件05Network Layer

1、Network LayerChapter 5CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Design IssuesRouting AlgorithmsCongestion ControlQuality of ServiceInternetworkingNetwork Layer of the InternetRevised: August 2011The Network LayerCN5E by Tanenbaum & Wetherall, Pearson Educat

2、ion-Prentice Hall and D. Wetherall, 2011Responsible for delivering packets between endpoints over multiple linksPhysicalLinkNetworkTransportApplicationDesign IssuesStore-and-forward packet switching Connectionless service datagrams Connection-oriented service virtual circuits Comparison of virtual-c

3、ircuits and datagrams CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Store-and-Forward Packet SwitchingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Hosts send packets into the network; packets are forwarded by routersISPs

4、equipmentConnectionless Service DatagramsPacket is forwarded using destination address inside itDifferent packets may take different pathsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011ISPs equipmentAs table (initially) As table (later) Cs Table Es TableConnecti

5、on-Oriented Virtual CircuitsPacket is forwarded along a virtual circuit using tag inside itVirtual circuit (VC) is set up ahead of timeCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011ISPs equipmentAs table Cs Table Es TableComparison of Virtual-Circuits & Datagra

6、msCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Routing Algorithms (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Optimality principle Shortest path algorithm Flooding Distance vector routing Link state routing Hierarchi

7、cal routing Broadcast routing Multicast routing Anycast routing Routing for mobile hosts Routing in ad hoc networks Routing Algorithms (2)Routing is the process of discovering network pathsModel the network as a graph of nodes and linksDecide what to optimize (e.g., fairness vs efficiency)Update rou

8、tes for changes in topology (e.g., failures)Forwarding is the sending of packets along a pathCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011The Optimality PrincipleCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Each portion

9、of a best path is also a best path; the union of them to a router is a tree called the sink treeBest means fewest hops in the exampleNetworkSink tree of best paths to router BBShortest Path Algorithm (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Dijkstras al

10、gorithm computes a sink tree on the graph:Each link is assigned a non-negative weight/distanceShortest path is the one with lowest total weightUsing weights of 1 gives paths with fewest hopsAlgorithm:Start with sink, set distance at other nodes to infinityRelax distance to other nodesPick the lowest

11、 distance node, add it to sink treeRepeat until all nodes are in the sink treeShortest Path Algorithm (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011A network and first five steps in computing the shortest paths from A to D. Pink arrows show the sink tree so

12、far.Shortest Path Algorithm (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011. . . . .Start with the sink, all other nodes are unreachableRelaxation step. Lower distance to nodes linked to newest member of the sink treeShortest Path Algorithm (4)CN5E by Tanenba

13、um & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011. . .Find the lowest distance, add it to the sink tree, and repeat until doneFloodingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011A simple method to send a packet to all network nodesEach no

14、de floods a new packet received on an incoming link by sending it out all of the other linksNodes need to keep track of flooded packets to stop the flood; even using a hop limit can blow up exponentiallyDistance Vector Routing (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D.

15、Wetherall, 2011Distance vector is a distributed routing algorithmShortest path computation is split across nodesAlgorithm:Each node knows distance of links to its neighborsEach node advertises vector of lowest known distances to all neighborsEach node uses received vectors to update its ownRepeat pe

16、riodicallyDistance Vector Routing (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011NetworkVectors received at J fromNeighbors A, I, H and KNew vector for JThe Count-to-Infinity ProblemCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wethera

17、ll, 2011Failures can cause DV to “count to infinity” while seeking a path to an unreachable nodeGood news of a path to A spreads quicklyXBad news of no path to A is learned slowlyLink State Routing (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Link state is

18、an alternative to distance vectorMore computation but simpler dynamicsWidely used in the Internet (OSPF, ISIS)Algorithm:Each node floods information about its neighbors in LSPs (Link State Packets); all nodes learn the full network graphEach node runs Dijkstras algorithm to compute the path to take

19、for each destinationLink State Routing (2) LSPsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011LSP (Link State Packet) for a node lists neighbors and weights of links to reach themNetworkLSP for each nodeLink State Routing (3) Reliable FloodingCN5E by Tanenbaum &

20、 Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Seq. number and age are used for reliable floodingNew LSPs are acknowledged on the lines they are received and sent on all other lines Example shows the LSP database at router BHierarchical RoutingHierarchical routing reduces the work

21、 of route computation but may result in slightly longer paths than flat routingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Best choice to reach nodes in 5 except for 5CBroadcast RoutingBroadcast sends a packet to all nodesRPF (Reverse Path Forwarding): send b

22、roadcast received on the link to the source out all remaining linksAlternatively, can build and use sink trees at all nodesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011NetworkSink tree for I is efficient broadcastRPF from I is larger than sink treeMulticast Ro

23、uting (1) Dense CaseMulticast sends to a subset of the nodes called a groupUses a different tree for each group and sourceCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Network with groups 1 & 2Spanning tree from source SSSSMulticast tree from S to group 1Multic

24、ast tree from S to group 2Multicast Routing (2) Sparse CaseCBT (Core-Based Tree) uses a single tree to multicastTree is the sink tree from core node to group membersMulticast heads to the core until it reaches the CBTp 1.CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall

25、, 2011Sink tree from core to group 1Multicast is send to the core then down when it reaches the sink treeAnycast RoutingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Anycast sends a packet to one (nearest) group memberFalls out of regular routing with a node in

26、 many places Anycast routes to group 1Apparent topology of sink tree to “node” 1Routing for Mobile HostsMobile hosts can be reached via a home agentFixed home agent tunnels packets to reach the mobile host; reply can optimize path for subsequent packetsNo changes to routers or fixed hostsCN5E by Tan

27、enbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Routing in Ad Hoc NetworksThe network topology changes as wireless nodes moveRoutes are often made on demand, e.g., AODV (below) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011As broadcast

28、 reaches B & DBs and Ds broadcast reach C, F & GCs, Fs and Gs broadcast reach H & I As starts to find route to ICongestion Control (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Handling congestion is the responsibility of the Network and Transport layers wor

29、king togetherWe look at the Network portion hereTraffic-aware routing Admission control Traffic throttling Load shedding Congestion Control (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Congestion results when too much traffic is offered; performance degrade

30、s due to loss/retransmissionsGoodput (=useful packets) trails offered loadCongestion Control (3) Approaches CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Network must do its best with the offered loadDifferent approaches at different timescalesNodes should also

31、 reduce offered load (Transport)Traffic-Aware RoutingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Choose routes depending on traffic, not just topologyE.g., use EI for West-to-East traffic if CF is loadedBut take care to avoid oscillations Admission ControlAdm

32、ission control allows a new traffic load only if the network has sufficient capacity, e.g., with virtual circuitsCan combine with looking for an uncongested routeCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Network with some congested nodesUncongested portion

33、and route AB around congestionTraffic ThrottlingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Congested routers signal hosts to slow down trafficECN (Explicit Congestion Notification) marks packets and receiver returns signal to senderLoad Shedding (1)CN5E by T

34、anenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011When all else fails, network will drop packets (shed load)Can be done end-to-end or link-by-linkLink-by-link (right) produces rapid relief13245Load Shedding (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall a

35、nd D. Wetherall, 2011End-to-end (right) takes longer to have an effect, but can better target the cause of congestion1327564Quality of ServiceCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Application requirements Traffic shaping Packet scheduling Admission cont

36、rol Integrated services Differentiated services Application Requirements (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Different applications care about different propertiesWe want all applications to get what they need.“High” means a demanding requirement,

37、e.g., low delayApplication Requirements (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Network provides service with different kinds of QoS (Quality of Service) to meet application requirements Network ServiceApplicationConstant bit rateTelephonyReal-time var

38、iable bit rateVideoconferencingNon-real-time variable bit rateStreaming a movieAvailable bit rateFile transferExample of QoS categories from ATM networksTraffic Shaping (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Traffic shaping regulates the average rate

39、and burstiness of data entering the networkLets us make guaranteesShape traffic hereTraffic Shaping (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Token/Leaky bucket limits both the average rate (R) and short-term burst (B) of trafficFor token, bucket size is

40、 B, water enters at rate R and is removed to send; opposite for leaky.Leaky bucket(need not full to send)Token bucket(need some water to send)to sendto sendTraffic Shaping (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Shaped by R=200 Mbps B=9600 KBShaped by

41、R=200 Mbps B=0 KBHost trafficR=200 Mbps B=16000 KBSmaller bucket size delays traffic and reduces burstinessPacket Scheduling (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Packet scheduling divides router/link resources among traffic flows with alternatives t

42、o FIFO (First In First Out)Example of round-robin queuing11122333Packet Scheduling (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Fair Queueing approximates bit-level fairness with different packet sizes; weights change target levelsResult is WFQ (Weighted Fa

43、ir Queueing)Packets may be sent out of arrival orderFinish virtual times determine transmission orderFi = max(Ai, Fi-1) + Li/WAdmission Control (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Admission control takes a traffic flow specification and decides whe

44、ther the network can carry itSets up packet scheduling to meet QoSExample flow specificationAdmission Control (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Construction to guarantee bandwidth B and delay D:Shape traffic source to a (R, B) token bucketRun WFQ

45、 with weight W / all weights R/capacityHolds for all traffic patterns, all topologiesIntegrated Services (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Design with QoS for each flow; handles multicast traffic.Admission with RSVP (Resource reSerVation Protocol

46、):Receiver sends a request back to the senderEach router along the way reserves resourcesRouters merge multiple requests for same flowEntire path is set up, or reservation not madeIntegrated Services (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011R3 reserves

47、flow from S1R3 reserves flow from S2R5 reserves flow from S1; merged with R3 at HMergeDifferentiated Services (1)Design with classes of QoS; customers buy what they wantExpedited class is sent in preference to regular classLess expedited traffic but better quality for applicationsCN5E by Tanenbaum &

48、 Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Differentiated Services (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Implementation of DiffServ:Customers mark desired class on packetISP shapes traffic to ensure markings are paid forRouters

49、 use WFQ to give different service levelsInternetworkingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Internetworking joins multiple, different networks into a single larger networkHow networks differ How networks can be connected Tunneling Internetwork routing

50、 Packet fragmentation How Networks DifferCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Differences can be large; complicates internetworkingHow Networks Can Be ConnectedCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Interne

51、tworking based on a common network layer IPPacket mapped to a VC hereCommon protocol (IP) carried all the wayTunneling (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Connects two networks through a middle onePackets are encapsulates over the middleTunneling (

52、2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Tunneling analogy: tunnel is a link; packet can only enter/exit at endsPacket Fragmentation (1)Networks have different packet size limits for many reasonsLarge packets sent with fragmentation & reassemblyCN5E by T

53、anenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011G1 fragmentsG2 reassemblesTransparent packets fragmented / reassembled in each networkNon-transparent fragments are reassembled at destinationG3 fragmentsG4 reassemblesG1 fragments destination will reassemblePacket Fragmenta

54、tion (2)Example of IP-style fragmentation:CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011PacketnumberStartoffsetEndbitOriginal packet:(10 data bytes)Fragmented:(to 8 data bytes)Re-fragmented:(to 5 bytes)Packet Fragmentation (3)CN5E by Tanenbaum & Wetherall, Pear

55、son Education-Prentice Hall and D. Wetherall, 2011Path MTU Discovery avoids network fragmentationRouters return MTU (Max. Transmission Unit) to source and discard large packets Try 1200Try 900 Network Layer in the Internet (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Weth

56、erall, 2011IP Version 4 IP Addresses IP Version 6 Internet Control Protocols Label Switching and MPLS OSPFAn Interior Gateway Routing Protocol BGPThe Exterior Gateway Routing Protocol Internet Multicasting Mobile IP Network Layer in the Internet (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Pr

57、entice Hall and D. Wetherall, 2011IP has been shaped by guiding principles:Make sure it worksKeep it simpleMake clear choicesExploit modularityExpect heterogeneityAvoid static options and parametersLook for good design (not perfect)Strict sending, tolerant receivingThink about scalabilityConsider pe

58、rformance and costNetwork Layer in the Internet (3)Internet is an interconnected collection of many networks that is held together by the IP protocolCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011IP Version 4 Protocol (1)CN5E by Tanenbaum & Wetherall, Pearson Ed

59、ucation-Prentice Hall and D. Wetherall, 2011IPv4 (Internet Protocol) header is carried on all packets and has fields for the key parts of the protocol: IP Addresses (1) Prefixes CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Addresses are allocated in blocks cal

60、led prefixesPrefix is determined by the network portionHas 2L addresses aligned on 2L boundaryWritten address/length, e.g., /24IP Addresses (2) Subnets CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Subnetting splits up IP prefix to help with managementLooks lik