1、计算机网络 The Network LayerThe Network LayerTopicsNetwork Layer Design IssuesStore-and-Forward Packet SwitchingImplementation of Connectionless ServiceImplementation of Connection-Oriented ServiceComparison of Virtual-Circuit and Datagram SubnetsRouting AlgorithmsnCorrectnessnSimplicitynRobustnessnStabi
2、litynFairnessnOptimalityRouting AlgorithmsnShortest Path RoutingnFloodingnDistance Vector RoutingnLink State RoutingnHierarchical RoutingRouting Algorithm BasicsnThe routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be t
3、ransmitted on.nIf 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.nIf the subnet uses virtual circuits internally,routing decisions are made only when a new virtual circuit is being set up.Routi
4、ng Algorithm Basics(2)nAll optimal routes from station A to other stations in the network,jointly constitute a sink treenRouters have to collaborate to build the sink tree for each source station or destination station.Routing Algorithm Basics(3)nMetrics used for optimizationDistanceNumber of hopsTi
5、me delay nTwo major classes of routing algorithmsNonadaptive 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.Shor
6、test Path RoutingnIdea: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.nthe labels(weights)
7、on the arcs could be computed as a function of the distance,bandwidth,average traffic,communication cost,measured delay,and other factors.nShortest Path Criteria:sum of the weights all the way,or,the number of hops.Shortest Path RoutingDijkstra AlgorithmnBasic Idea:during each step,select a newly re
8、achable node at the lowest cost,and add the edge to that node,to the sink tree rooted at the source node built so far.FloodingnBasic idea:Forward an incoming packet across every outgoing line,except the one it came through.nBasic problem:how to avoid“drowning by packets”?Use a hop counter:after a pa
9、cket 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 in the direction that makes sense.nFlooding makes sense only when robustness is needed,e.g.in military applicat
10、ionsDistance Vector RoutingBellman-Ford or Ford-Fulkerson algorithmnDistance Vector Routing Algorithms:each router maintains a table(i.e,a vector)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 perio
11、dically.nUpdating Process:Take a look at the costs that your direct neighbors are advertising to get a packet to the destination.Select the neighbor whose advertised cost,added with the cost to get to that neighbor,is the lowest.Advertise that new cost to the other neighbors.nIn DVR,there is the pro
12、blem of count-to-infinity in the presence of node crashes.DVR Examplen(a)A subnet.(b)Input from A,I,H,K,and the new routing table for JLink State RoutingnLink 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.nE
13、ach 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 other routers.Compute the shortest path to every other router.Measuring Line CostnJust sen
14、d an ECHO packet through each interface,and measure the round-trip delay.Thatll give you a reasonable estimate of the actual delay.nWhether to take the load into account when measuring the delay?Yes:the timer should be started when the ECHO packet is queued.You may redirect traffic in such a way tha
15、t the alternative route is unloaded.No:the timer should be started when the ECHO packet reaches the front of the queue.The shortest path you choose may be overloaded.Building Link State PacketsnThe packet starts with the identity of the sender,followed by a sequence number and age,and a list of dual
16、 items(neighbor,the delay to it).nThe hard part is when to build them,at regular intervals or when some significant event occurs?Practice shows that once an hour is often enough.Distributing the Link State PacketsnUse a flooding algorithm,and dam the flood through sequence numbers:all routers mainta
17、in a list of(source,seq number)-pairs.nTo safeguard against old data,down links,etc.an age 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.nTo guard against errors on the router-router lines,all link state
18、 packets are acknowledged.Goods and Badsof LSRnGoodsGood consistency of each router informationQuick convergence for good and bad newsnBadsEach router need large memory to store the input link states of other routersThe computation time can be an issueHierarchical RoutingnProblem:No routing algorith
19、m discussed so far can scale:all of them require each router to know about all others=too demanding with respect to memory capacity and processing power.nGo for suboptimal routes by introducing hierarchical routing and regions,and separate algorithms for intra-region and inter-region routing.Example
20、:Hierarchical RoutingMulticasting routingnMOSPFnDVMRPnCBT Next discussion topicsnMulticasting routingnAd hoc routingnBroadcasting routingMobile hosts routingCongestion Control AlgorithmsnGeneral Principles of Congestion ControlnCongestion Prevention PoliciesnCongestion Control in Virtual-Circuit Sub
21、netsnCongestion Control in Datagram SubnetsnLoad SheddingnJitter ControlCongestion nCongestion:When too many packets are present,performance degradesnAt very high traffic,performance collapses completely and almost no packets are delivered.CongestionGeneral Principles of Congestion ControlnTwo group
22、s of solutions:nOpen loop:attempt to solve the problem by good design,in essence,to make sure it does not occur in the first place.nClosed loop:are based on the concept of a feedback loop.Monitor the system to detect when and where congestion occurs.Pass information to where action can be taken.Adju
23、st system operation to correct the problem.PolicyCongestion Control in Virtual-Circuit SubnetsHop-by-Hop Choke PacketsnWhen a router runs out of its resources,it sends a choke packet back to the source host,giving it the destination found in the packet.nWhen the source host gets the choke packet,it
24、will slow down the traffic sent to the specified destination.nHop-by-Hop:the choke packet affects every hop it passes through.n(a)A choke packet that affects only the source.n(b)Hop-by-Hop choke packet.Random early detectionnBy having routers drop packets before the situation has become hopeless(hen
25、ce the early in the name),the idea is that there is time for action to be taken before it is too late.nTo determine when to start discarding,routers maintain a running average of their queue lengths.nWhen the average queue length on some line exceeds a threshold,the link is said to be congestion and
26、 a small fraction of the packets are dropped at randomJitter ControlQuality of ServicenA stream of packets from a source to a destination is called a flow.nIn a connection-oriented network,all the packets belonging to a flow follow the same route;in a connectionless network,they may follow different
27、 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.Traffic ShapingnTraffic shaping is about regulating the average rate of data transmission.nThe goal is to allow
28、applications to transmit a wide variety of traffic that suits their needs,include some bursts.The Leaky Bucket AlgorithmnImagine a bucket with a small hole in the bottom.No matter the rate at which water enters the bucket,the outflow is at a constant rate,when there is any water in the bucket and ze
29、ro when the bucket is empty.*实现：-对定长分组的实现：以分组为单位；-对变长分组的实现：采用字节计数法。n漏桶算法（续）：*举例：设计算机以25MB/s速率产生数据，路由器长时间的最佳工作速率不超过2MB/s。数据以每秒中有40ms，1MB的突发数据输入。为平稳输出，使用一个=2MB/s，容积C=1MB的漏桶。a图为漏桶的输入，b 图为漏桶的输出。The Token Bucket AlgorithmnThe leaky bucket algorithm enforces a rigid output pattern at the average rate,no m
30、atter how bursty the traffic is.For many applications,it is better to allow the output to speed up somewhat when large bursts arrive,so a more flexible algorithm is needed,preferably one that never loses data.One such algorithm is the token bucket algorithm.n通信量整形令牌桶算法：*实现：-采用分组计数法：设置令牌计数器，每隔T加1，每发送
31、一个分组减1，计数器为0时停止发送。-采用字节计数法：时钟每隔T令牌计数器加k字节，每发送一个分组减该分组长度。*对突发时间长度的限制：设突发时间长度S秒，令牌桶容量B字节，令牌到达率R字节/秒，最大速率M字节/秒，由B+RS=MS 得 S=B/(M-R)。n通信量整形令牌桶算法：*对突发长度的限制（续）：例：容量C分别是250KB、500KB和750KB，=2MB，M=25MB/s。假定当1MB突发数据到达时，令牌桶已满。5.4.2 实现高QoS的技术（续）n资源预留：可能被预留资源的种类：-带宽 -缓冲区空间 -CPU时钟周期 Admission controlnAdmission con
32、trol：确定接收或拒绝一个流并非易事,原因：-由于有些应用可能知道带宽需求，但不知道缓冲区和CPU时钟周期的需求。-有些应用需要更高的容错能力。-有些应用希望讨价还价流的参数。Admission control flow specification(流说明)：-能够准确描述规范化的流参数。-从源端到目的端沿途路由器可修改这些参数。举例：-令牌桶速率：长时间间隔的平均输入桶的每秒字节数。-令牌桶容量。-峰值数据速率：限制短暂时间间隔发送速率。-最小、最大分组长度：含头部。Packets scheduling n按比例路由：由于路由器一般不了解整个网络的流量，一种高QoS的方法是根据输出链路能力
33、按相等或比例划分，在多条路径上传输。nPackets scheduling：公平队列算法：*Nagle算法：-到达分组按分类或流进入各自队列；-轮流从各队列输出，一旦某队列空，立即从非空队列输出。Packets schedulingn分组调度（续）：公平队列算法(FIFO)加权队列算法(WFQ)5.4.2 实现高QoS的技术（续）n分组调度（续）：加权公平队列（WFQ）：-对不同的队列设置优先级（即权重）。-按权重比例发送。5.4.2 实现高QoS的技术（续）n分组调度（续）：令牌+WFQ提供可证明的最大队列延时：n条流的令牌桶+WFQ队列模型。b1r1bnrnw1wnInternetwork
34、ingnHow Networks DiffernHow Networks Can Be ConnectednConcatenated Virtual CircuitsnConnectionless InternetworkingnTunnelingnFragmentationConnecting NetworksHow Networks DifferHow Networks Can Be ConnectednRepeaters at the physical layer for boosting signals.nBridges to make the interconnection at t
35、he data link layer.nMultiprotocolrouters for forwarding,and possibly splitting up packets(bridges cant do the latter).nTransport gateways for interfacing between two transport connections.nApplication gateways,translate message semantics.Concatenated Virtual CircuitsConnectionless internetworkingnHa
36、ve the network layer offer only datagram services:unreliable,unordered packet flow.nMain problem:Addressing different networks use completely different addresses,so how do I address a host in an IP network when Ive only got SNA?nSolution:consider,using IP as a universal network protocolTunnelingnWe
37、can solve a lot of the internetworking problems when we can assume that the source and destination of the same type of network is connected by different network,we need only to tunnel packets through intermediate networks.FragmentationnFragmentation:Different networks may impose different maximum pa
38、cket sizes.This means that we may have to split a packet into smaller ones when forwarding it through a network whose maximum packet size is too smallnWhere to reassemble the fragments?Gateway:Transparent fragmentationThe destination host:Nontransparent fragmentationThe Network Layer in the Internet
39、The Internet Protocol(IP)nThe Internet is a collection of many networks connected together by a bunch of backbones.nThe glue that holds the whole Internet together is the network layer protocol,IP(Internet Protocol).The IPv4 HeaderThe IPv4 Header(2)AddressesIP Addresses(2)Subnets(1)nAll hosts on the
40、 same network must have the same network number.This may cause a single organization to acquire several classes of addresses for multiple LANs.nUse a single network address for the entire organization,and internally divide the host address space into a subnet address and a host idnTo implement subne
41、tting,the main router needs a subnet mask that indicate CIDR Classless InterDomainRoutingCIDR ExamplesCIDRAggregate EntriesnFor many routers outside 194.24.0.0,the only thing they see is that there are(at least)3 network addresses for which packets follow the same route.These entries can be aggregated into a single entry 194.24.0.0/19 with a single submaskof 19/13 1/0 bits.
