計算機網(wǎng)絡computer networks5e

1、The Network Layer副教授The Network LayerTopicsNetwork Layer Design IssuesStore-and-Forward PacketSwitchingImplementation of Connectionless ServiceImplementation of Connection-Oriented Service數(shù)據(jù)報和虛電路n 網(wǎng)絡層為接在網(wǎng)絡上的主機所提供的服務可以有兩大類：n 無連接的網(wǎng)絡服務（數(shù)據(jù)報服務）n 面向連接的網(wǎng)絡服務（虛電路服務）。網(wǎng)絡隨時接受主機發(fā)送的分組（即數(shù)據(jù)報）網(wǎng)絡提為供每數(shù)個分據(jù)組地務選的擇路特由點。H4

2、H2DBH6EH1 A H5CH3分組交換網(wǎng)路徑可能變化H1 向H5 發(fā)送分組H2 向H6 發(fā)送分組網(wǎng)絡盡最大努力地將分組交付給目的主機，提但網(wǎng)供絡數(shù)對源據(jù)主報機服沒有務任的何特承諾點。H4H2DBH6EH1 A H5CH3分組交換網(wǎng)網(wǎng)絡不保證所傳送的分組不丟失也不保證按源主機發(fā)送分組的先后順序以及在提時供限數(shù)內(nèi)必據(jù)須報將分服組務交的付給特目點的主機H4H2DBH6EH1 A H5CH3分組交換網(wǎng)當網(wǎng)絡發(fā)生擁塞時網(wǎng)絡中提的供結(jié)數(shù)點可據(jù)根報據(jù)情服況務將的一些特分點組丟棄H4H2DBH6EH1 A H5CH3分組交換網(wǎng)數(shù)據(jù)報提供的服務是不可靠的，它不能保證服務質(zhì)量。提實供際上數(shù)“盡據(jù)最報大努服力務

3、交付的”的特服點務就是沒有質(zhì)量保證的服務。H4H2DBH6EH1 A H5CH3分組交換網(wǎng)主機H1 先向主機 H5 發(fā)出一個特定格式的分組，要求進行通信，同時尋找一條合適路由。若主機 H5 同意通信就發(fā)回提響供應，虛然后電雙路方就服建務立了的虛特電路點。 H4H2DBH6EH1 A H5CH3分組交換網(wǎng)虛電路H1 要和H5 通信H1 向H5 發(fā)送的所有分組都沿此虛電路傳送。同理，主機H2 和主機 H6 通信之前，也要建立虛電路。提供虛電路服務的特點H4H2DBH6EH1 A H5CH3分組交換網(wǎng)在虛電路建立后，網(wǎng)絡向用戶提供的服務就好像在兩個主機之間建立了一對穿過網(wǎng)絡的數(shù)字管道。所有提發(fā)送供的

4、分虛組電都按路順服序進務入的管道特，然點后按照先進先出的原則沿著此管道傳送到目的站主機。H4H2DBH6EH1 A H5CH3分組交換網(wǎng)到達目的站的分組順序就與發(fā)送時的順序一致，因此網(wǎng)絡提供虛電路服務對通信的服務質(zhì)量提Q供oS虛(Qu電alit路y of服Se務rvic的e)有特較保證。H4H2DBH6EH1 A H5CH3分組交換網(wǎng)兩種服務的思路來源不同n 虛電路服務的思路來源于傳統(tǒng)的電信網(wǎng)。¨ 電信網(wǎng)負責保證可靠通信的一切措施，因此電信網(wǎng)的結(jié)點交換機復雜而昂貴。n 數(shù)據(jù)報服務力求使網(wǎng)絡生存性好和使對網(wǎng)絡的功能分散，因而只能要求網(wǎng)絡提供盡最大努力的服務。¨ 可靠通信由用戶

5、終端中的保證。（即TCP）來Comparison of Virtual-Circuit and DatagramSubnetsRouting Algorithmsn Correctnessn Simplicityn Robustnessn Stabilityn Fairnessn Optimality5.2 Whats Inside a Routern RoutDeartaalinrkclahyeitrecturePhysical layerNetwork layerFrom: James F. Kurose, Keith W. Ross, “Computer Networks: A Top-

6、Down Approach”, 5th Ed.5.2.1 Input Portn Input port processing¨ The lookup/forwarding module in the here is central¨ It is desirable for the input port processing at line speedn A binary search through an address space of size 2Nn CAM (Content Addressable Memory)¨ A packet may be temp

7、orarily blocked, so it must be queued at the input portFrom: James F. Kurose, Keith W. Ross, “Computer Networks: A Top-Down Approach”, 5th Ed.5.2.3 Output Portn Output port processing¨ The queuing and buffer management functionality is needed when the switch fabric delivers packets to the outpu

8、t port at a rate that exceeds the output link rate.From: James F. Kurose, Keith W. Ross, “Computer Networks: A Top-Down Approach”, 5th Ed.5.2.4 Where Does Queuing? (1)n Output port queuingn Introduce to packet scheduler and AQM (Active Queue Management)From: James F. Kurose, Keith W. Ross, “Computer

9、 Networks: A Top-Down Approach”, 5th Ed.5.2.4 Where Does Queuing? (2)n HOL (Head-Of- the-Line) blocking at an input queued switchFrom: James F. Kurose, Keith W. Ross, “Computer Networks: A Top-Down Approach”, 5th Ed.Routing AlgorithmsShortest Path Routing FloodingDistance Vector Routing Link State R

10、outingHierarchical Routingnnnnn5.3 Routing Algorithms (1)n Routing is the process of discovering network paths¨ Mthe network as a graph of nodes and links¨ Decide what to optimize (e.g., fairness vs efficiency)¨ Update routes for changes in topology (e.g., failures)5.3 Routing Algorit

11、hms (2)n The difference of forwarding and routing¨ Forwarding is the sending of packets along a path¨ Routing is responsible for filling in and updating the routing tablesn The kind of routing algorithm¨ Nonadaptive algorithms is static routing¨ Adaptive algorithms is dynamic rou

12、ting5.3.1 The Optimality Principlen Each portion of a best path is also a best path; the union of them to a router is a tree called the sink treeB¨ Best means fewest hops in the exampleSink tree of best paths to router BNetworkRouting Algorithm Basicsn The routing algorithm is that part of the

13、network layer software responsible for deciding which output line anincopacket should be transmitted on.n If the subnet uses datagrams internally, this decision mustbeanew for every arriving data packet since the bestroute may have changed since last time.n If the subnet uses virtual circuits intern

14、ally, routingdecisions areset up.only when a new virtual circuit is beingRouting Algorithm Basics(3)n Metrics used for optimization¨ Distance¨ Number of hops¨ Time delayn Two major classes of routing algorithms¨ Nonadaptive or Static: the routing table is computed in advance, off

15、-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.5.3.3 FloodingA simple method to send a packet to all network nodesEach node floods a new packet received on

16、annninco linkslink by sending it out all of the otherNodes need to keep track of flooded packets to stop the flood; even using a hop limit can blow up exponentiallynA better technique for damUse floodingthe floodnnShortest Path RoutingIdea: build a graph of the subnet, with each node of the graph re

17、presenting 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, averag

18、e traffic, communication cost, measured delay, and other factors.Shortest Path Criteria: sum of the weights all the way, or, the number of hops.nnnShortest Path RoutingDijkstra Algorithmn Basic Idea: during each step, select a newly reachable node at the lowest cost, and add the edge to that node, t

19、o the sink tree rooted at the source node built so far.FloodingBasic idea: Forward an incopacket acrossnevery outgoing line, except the one it came through.Basic problem: how to avoid “drowning by packets”?Use a hop counter: after a packet has beennforwarded across N routers, it is discarded.Besure

20、to forward a packet only once (i.e. avoiddirected cycles). Requires sequence numbers persource router.Flood selectively: only in thedirection that makes sense.Flooding makes sense only when robustness is needed, e.g. in military applicationsnFlooding(2)Flooding is not practical for sending most pack

21、ets, but it does have some important uses.n First, it ensures that a packet is delivered to every node in the network.n Second, flooding is tremendously robust.Distance Vector RoutingBellman-Ford or Ford-Fulkerson algorithmDistance Vector Routing Algorithms:each router maintains a table (i.e, a vect

22、or) giving the best known distance to each destination and which line to use to get there, which are updated by exchanging information with the neighbors periodically.Updating Process: Take a look at the costs that yournndirect neighbors avertising to get a packet to thedestination. Select the neigh

23、bor whose advertised cost, added with the cost to get to that neighbor, is the lowest. Advertise that new cost to the other neighbors.In DVR, there is the problem of count-to-infipresence of node crashes.in thenDVR Examplen (a)A subnet. (b)Input from A, I, H, K, and the new routing table for JLink S

24、tate Routingn Link State Routing: broadcast info on the entire network topology to all routers, and let each of them calculate a sink tree to the other routers.n Each router must do the following:¨ Discover its neighbors, learn their network address.¨ Measure the delay or cost to each of i

25、ts neighbors.¨ Construct a packet telling all it has just learned.¨ Send this packet to all other routers.¨ Compute the shortest path to every other router.Measuring Line Costn Jusd an ECHO packet through eachinterface, and measure the round-trip delay. Thatll give you a reasonable es

26、timate of the actual delay.n Whether to take the load into measuring the delay?when¨ Yes: the timer should be started when the ECHO packet is queued. You may redirect traffic in such a way that the alternative route is unloaded.¨ No: the timer should be started when the ECHO packet reaches

27、 the front of the queue. The shortest path you choose may be overloaded.Building Link State Packetsn The packet starts with the identity of the sender, followed by a sequence number and age, and a list of dualitems( neighbor, the delay to it ).n The hard part is when to build them, at regular interv

28、als or when some significant event occurs? Practice shows that once an hour is often enough.Distributing the Link State PacketsUse a flooding algorithm, and dam the flood through sequence numbers: all routers maintain a list of (source, seq number)-pairs.nTo safeguardold data, down links, etc.nan ag

29、e is added to an LSP. The age is decremented once a second, and every time it is forwarded by a router. When the age hits zero, the LSP is discarded.To guarderrors on the router-routernlines, all link state packets are acknowledged.Goods and Badsof LSRn Goods¨ Good consistency of each router in

30、formation¨ Quick convergence for good and bad newsn Bads¨ Each router need large memory to store the input link states of other routers¨ The computation time can be an issueHierarchical Routingn Problem: No routing algorithm discussed so far can scale: all of them require each router

31、to know about all others => too demanding with respect to memory capacity and processing power.n Go for suboptimal routes by introducing hierarchical routing and regions, and separate algorithms for intra-region and inter-region routing.Example: Hierarchical RoutingMulticasting routingn MOSPFn DV

32、MRPn CBTNext discussion topicsn Multicasting routingn Ad hoc routingn Broadcasting routingMobile hosts routingCongestion Control AlgorithmsGeneral Principles of Congestion Control Congestion Prevention Policies Congestion Control in Virtual-CircuitSubnetsCongestion Control in Datagram Subnets Load S

33、heddingJitter ControlnnnnnnCongestionCongestion: When too many packets are present, performance degradesAt very high traffic, performance collapses completely and almost no packets are delivered.nnCongestionGeneral Principles of CongestionControlTwo groups of solutions:Open loop: attempt to solve th

34、e problem by good design, in essence, to make sure it does not occur in the first place.d loop: are based on the concept of a feedback loop.¨ Monitor the system to detect when and wherecongestion occurs.¨ Pass information to where action can be taken.¨ Adjust system operation to corre

35、ct the problem.nnnPolicy5.4.1 Approaches to CongestionControln Network musts best with the offered load¨ Different approaches at different timescales¨ Nodes should also reduce offered load (Transport)5.4.2 Traffic-Aware Routingn Choose routes depending on traffic, not just topology¨ E

36、.g., use EI for West-to-East traffic if CF is loaded¨ But take care to avoid oscillationsCongestion Control inVirtual-Circuit Subnets5.4.4 Traffic Throttling (1)n Traffic Throttling is a technique ofavoidancecongestion¨ To maintain a good estimate of the queuing delay, using EWMA (Exponent

37、ially Weighted Moving Average),d, a sample of the instantaneous queue length, s, canbeperiodically and d updated according todnew= dold + (1 )swhere the constant determines how fast the router forgets recent history. This is called ann Choke Packets¨ the router selects a congested packet and se

38、nds achoke packet back to the source host,5.4.4 Traffic Throttling (2)n Explicit Congestion Notification¨ Congested routers signal hosts to slow down traffic¨ ECN (Explicit Congestion Notification) marks packetsand receiver returns signal to senderHop-by-Hop Choke Packetsn When a router ru

39、ns out of its resources, ids achoke packet back to the source host, giving it the destination found in the packet.n When the source host gets the choke packet, it will slow down the traffic sent to the specified destination .n Hop-by-Hop: the choke packet affects every hop it passes through.n (a)A c

40、hoke packet that affects only the source.n (b)Hop-by-Hop choke packet.Load Shedding (1)n Load shedding policy¨ The policy of old is better than new is often called wine¨ The policy of new is better than old is often called milkn Priority and loss priorityn SLA (Service Lever Agreement)Prob

41、lems: 14Random early detectionBy having routers drop packets before the situation has become hopeless (hence the ''early'' in the name), the idea is that there is time for action to be taken before it is too late.To determine when to start discarding, routers maintain a running avera

42、ge of their queue lengths.When the average queue length on some line exceeds a threshold, the link is said to be congestion and a small fraction ofthe packets are dropped at randomnnn5.4.5 Load Shedding (2)n Active Queue Management¨ 主動隊列管理（AQM）的引入n “首/尾丟棄”未解決滿隊列問題¨ 什么是AQMn 主動的而非響應性的分組丟棄策略n

43、 采用標記分組通知信源n 主要目標是保持較小的隊列¨ AQM的優(yōu)點n 減少路由器中分組丟棄n 減少路由器中分組丟棄5.4.5 Load Shedding (3)n RED (Random Early Detection) (1)¨ 在網(wǎng)絡出現(xiàn)擁塞之前，以一定概率丟棄/標記分組的方式通知端系統(tǒng)¨ 算法 (1)n 路由器使用平均隊列長度（avg queue）度量網(wǎng)絡擁塞n 標記概率Prob1maxpminthmaxthAvg Queue5.4.5 Load Shedding (4)n RED (Random Early Detection) (2)¨ 算法

44、(2)n 主要參數(shù)¨ 最小閾值（minth），最大閾值（maxth）和最大概率（maxp）¨ 若avg_queue<minth，則丟棄/標記概率為0¨ 若minthavg_queue<maxth，則丟棄/標記概率為maxp(avg_queue-minth)/(maxth-minth)¨ 若avg_queue>maxth，則丟棄/標記概率為15.4.5 Load Shedding (5)n RED (Random Early Detection) (3)¨ 算法 (3)n 引入P（比例）器¨ maxp(avg_queu

45、e-minth)/(maxth-minth)，即pi=kqi<1>其中，qi為隊列長度的第i個采樣值，pi為第i個計算得到的概率值n 為減少“瞬時抖動”而引入低通濾波器¨ 對式<1>，qave用平均隊列長度代替qiqave= (1-w)qave + wqi其中，w為權(quán)重5.4.5 Load Shedding (5)n RED (Random Early Detection) (3)¨ RED變形n 動態(tài)調(diào)整丟棄/標記概率，如ARED、SRED、BLUEn 使用PI器：REM、P和AVQ5.5 Quality of Service5.5.1 Appli

46、cation Requirements (1)n Different applications care about different properties¨ We want all applications to get what they need“High” means a demanding requirement, e.g., low delay5.5.1 Application Requirements (2)n Network provides service with different kinds of QoS (Quality of Service) to me

47、et application requirementsExample of QoS categories from ATM networksNetwork ServiceApplicationConstant bit rateTelephonyReal-time variable bit rateconferencingNon-real-time variable bit rateStreaa movieAvailable bit rateFile transferJitter ControlQuality of ServiceA stream of packets from a source

48、 to a destination is called a flow.In a connection-oriented network, all the packets belonging to a flow follow the same route; in a connectionless network, they may follow different routes. The needs of each flow can be characterized by four primary parameters: reliability, delay, jitter, and bandwidth. Together these determine the QoS (Quality of Service) the flow requires.nnTraffic Shan Traffic shais about regulating theaverage rate of data transmission.n The goal is to al