《现代计算机网络讲义5(英语)+网络层ppt课件.ppt》由会员分享，可在线阅读，更多相关《现代计算机网络讲义5(英语)+网络层ppt课件.ppt（136页珍藏版）》请在三一办公上搜索。
1、2022/11/23,1,The Network LayerGoal: end-to-end transmission,Chapter 5,2022/11/23,2,5.1 Network Layer Design Isues,Store-and-Forward Packet SwitchingServices Provided to the Transport LayerImplementation of Connectionless ServiceImplementation of Connection-Oriented ServiceComparison of Virtual-Circu
2、it and Datagram Subnets,2022/11/23,3,5.1.1 Store-and-Forward Packet Switching,The environment of the network layer protocols.Store and forwardRoute,2022/11/23,4,5.1.2 Services Provided to the Transport Layer,The services should be independent of the router technology.The transport layer should be sh
3、ielded from the number, type, and topology of the routers present.The network addresses should use a uniform numbering plan, even across LANs and WANs.,2022/11/23,5,5.1.3 Implementation of Connectionless Service,Routing within a diagram subnet.,2022/11/23,6,5.1.4 Implementation of Connection-Oriente
4、d ServiceI,Routing within a virtual-circuit subnet.,Multiple Logic Link,2022/11/23,7,5.1.5 Comparison of Virtual-Circuit and Datagram Subnets,5-4,2022/11/23,8,5.2 Routing Algorithms(1),The Optimality PrincipleShortest Path RoutingFloodingDistance Vector RoutingLink State RoutingHierarchical RoutingB
5、roadcast RoutingMulticast RoutingRouting for Mobile HostsRouting in Ad Hoc Networks,2022/11/23,9,A good routing algorithm: CorrectnessSimplicityRobustnessStabilityFairnessOptimality. Nonadaptive or adaptive (static or dynamic) algorithms,5.2 Routing Algorithms(2),2022/11/23,10,5.2.1 The Optimality P
6、rinciple,If 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 route. Sink tree: the set of optimal routes from all sources to a given destination form a tree rooted at the destinationA sink tree for router B.The goal of all routing
7、 algorithms is to discover the sink trees,2022/11/23,11,5.2.2 Shortest Path Routing,Computing the shortest path from A to D. Permanent nodeTentatively labeled node Working node.,http:/carbon.cudenver.edu/hgreenbe/sessions/dijkstra/DijkstraApplet.html,2022/11/23,12,5.2.3 Flooding,Every incoming packe
8、t is sent out on every outgoing line except the one it arrived on. Throw out duplicate packetsHop counter To keep track of the flooded packetsSelective flooding Robust,2022/11/23,13,5.2.4 Distance Vector Routing(1),Distance vector routing algorithmsEach router maintain a table giving the best known
9、distance to each destination and the line to get there.These tables are updated by exchanging information with the neighbors.,2022/11/23,14,5.2.4 Distance Vector Routing (2),The count-to-infinity problemGood newsBad news,2022/11/23,15,5.2.5 Link State Routing(1),Each router must do the following:Dis
10、cover its neighbors, learn their network address.sending a HELLO packet on each point-to-point lineMeasure 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.,2022/11/23,1
11、6,5.2.5 Link State Routing(2),Measuring Line CostSend a ECHO packet that requires the other side to send back immediately Delay time: bandwidth or bandwidth + load ?Oscillations, CF or EI,2022/11/23,17,5.2.5 Link State Routing(3),Building Link State Packets periodically or when some significant even
12、t occurs identity of the sendera sequence numberage a list of neighbors,2022/11/23,18,5.2.5 Link State Routing(4),Distributing (Flooding) the Link State PacketsEach packet contains a 32 bit sequence number. Routers keep track of all the (source router, sequence) pairs and check every arrived state p
13、acket. If it is new, flooding.If it is a duplicate , discarded.If it is old, rejected. AgeRouter decrements the age once per second. The information whose age is zero will be discarded. Dcremented by each router during the flooding process,2022/11/23,19,Computing the New RoutesDijkstras algorithm.Pr
14、oblem:The memory required to store the input data and all route information for every router Some error on a router will influence all network,5.2.5 Link State Routing(5),2022/11/23,20,5.2.6 Hierarchical Routing,As in telephone network, RegionRouter knowing all the details within its own region, but
15、 knowing nothing about other regions. Increased path lengthHow many levels should the hierarchy have?,2022/11/23,21,5.2.7 Broadcast Routing (1),Special ApplicationSending a packet to all destinations simultaneouslyBroadcasting methodSimply send a distinct packet to each destination FloodingMultidest
16、ination routingEach packet contains a list of destinations. the router checks it to determine the set of output lines that will be needed.For each output line the router generates a new copy of the packet including only those destinations that are to use the line. Spanning tree, router copy an incom
17、ing broadcast packet onto all the spanning tree linesReverse path forwarding, router checks if the packet arrived on the line that is normally used for sending packets to the source of the broadcast,2022/11/23,22,Reverse path forwarding. (a) A subnet.(b) Is sink tree.(c) The tree built by reverse pa
18、th forwarding.,5.2.7 Broadcast Routing (2),2022/11/23,23,GroupMulticast or BroadcastGroup management. Create and destroy groups, join and leave groupsSender and receiver. Routers know which of their hosts belong to which groups. Based on Spanning tree (see next page)Each router computes a spanning t
19、ree covering all other routers The router examines its spanning tree and removes all lines that do not lead to the members of the group. Multicast packets are forwarded only along the appropriate spanning tree.Each router should store a total of M*N trees (N groups and M members),5.2.8 Multicast Rou
20、ting(1),2022/11/23,24,5.2.8 Multicast Routing(2),(a) A network. (b) A spanning tree for the leftmost router. (c) A multicast tree for group 1. (d) A multicast tree for group 2.,25,5.2.8 Multicast Routing (3),Sharing treethe root near the middle of the group.Sources sends message to the root, which t
21、hen does the multicast along the spanning tree. One group one tree,5.2.9 Anycast Routing,(a) Anycast routes to group 1. (b) Topology seen by the routing protocol.,Assigning a common IP address to multiple instances of the same serviceA packet is delivered to the nearest member of an anycast service.
22、 Common services include DNS, multicast rendezvous points (RPs) can take advantage of anycast addressing.Providing redundancy and load sharing to specific types of network services .Distance vector and Link state routing can produce anycast routes,2022/11/23,27,5.2.10 Routing for Mobile Hosts(1),Bas
23、ic goals: All higher-layer connections should survive the address changeMobile host should be reachable as long as it is connected to the Internet somewhere.A modela WAN to which LANs, MANs, and wireless cells are attached.Home Location / Foreign Agent,2022/11/23,28,Mobile Node (MN): a node which ca
24、n change its location while maintaining any ongoing communications and using only its home (permanent) IP address.Care-of address (COA)Used by a MN while it is attached to a foreign link. The association of a COA with a home address for a mobile node is known as a binding. Home Agent (HA): a router
25、with at least one interface on the MNs home link which:Intercepts packets destined to the MNs home address and tunnels them to the MNs current location (or COA).Foreign Agent (FA): a router on a foreign link which:Acts as the default router for packets generated by the MN while connected to this for
26、eign linkAssists the MN in informing its HA of its current COAProvides a COA or de-tunnels packets for the MN,5.2.10 Routing for Mobile Hosts(2),2022/11/23,29,Registration protocolPeriodically, each FA broadcasts a packet announcing its existence.The MH registers with the FA, giving its home address
27、, and some security information.The foreign agent contacts the mobile hosts HA: One of your hosts is over here and its COA. The HA examines the security information and acknowledgementFA gets the acknowledgement and informs the mobile host that it is now registered.,5.2.10 Routing for Mobile Hosts(3
28、),2022/11/23,30,5.2.10 Routing for Mobile Hosts (4),Packet routing for mobile users.,Home Agent,Foreign AgentMN,Correspondent node,2022/11/23,31,Micro-Mobility (1),2022/11/23,32,Micro-Mobility (2),Handover latency registration procedure QoS packet lossThree kinds of handover operationsSmooth Handove
29、r, minimizes data loss during the time that the MN is establishing its link to the new access pointFast Handover, Minimizes latency for establishing new communication pathsSeamless Handover, Smooth and FastHierarchical Mobile IPMovement detection,2022/11/23,33,5.2.11 Routing in Ad Hoc (1),Ad hoc net
30、worksEach node consists of a router and a hostCommunicate directly using radios and no wired backboneAll nodes are capable of movementthe topology may be changing all the timeEase of deploymentMultihopLow powerAutonomous,2022/11/23,34,5.2.11 Routing in Ad Hoc (2),AODV (Ad hoc On-demand Distance Vect
31、or)In a mobile environment To determine a route only when they are needed Highly ScalableNeed for broadcast is minimizedQuick response to link breakage in active routesLoop freeAODV Unicast message typesRoute Request (RREQ): to startup route discovery Route Reply (RREP): route discovery completedRou
32、te Error (RERR): Link Breakage IndicationRoute Reply Acknowledgement (RREP-Ack): to used in cases where the link may be unreliable.,2022/11/23,35,5.2.11 Routing in Ad Hoc (3) Route Discovery,(a) Range of As broadcast. In the range, B connected A with a arc(b) After B and D have received As broadcast
33、.(c) After C, F, and G have received As broadcast.(d) After E, H, and I have received As broadcast.The shaded nodes are new recipients. The arrows show the possible reverse routes.,2022/11/23,36,5.2.11 Routing in Ad Hoc (4) Route Discovery,A constructs a special ROUTE REQUEST packet and broadcast.Th
34、e format of Route Request packetThe source and destination addresses, typically their IP addressesRequest ID, identify the ROUTE REQUEST packet (duplicate?)Sources and Dest.s sequence counter (fresh?) Destinations sequence number that A has seen (0, if it has never seen it).Hop count, will keep trac
35、k of how many hops the packet has made.,2022/11/23,37,5.2.11 Routing in Ad Hoc (5) Route Discovery,Source broadcasts ROUTE REQUESTWhen a ROUTE REQUEST packet arrives at a node.Duplicate (source addr. and ID)? Discarded.Increments the Hop count field and rebroadcasts the ROUTE REQUEST packetStores th
36、e information to construct the reverse path.If a fresh (seq-no equal to or greater) route to the destination is known, a RREP is sent back to the source telling it how to get to the destination along the reverse path.Updates time-out entries, records the destination sequence number of requested dest
37、ination.,2022/11/23,38,5.2.11 Routing in Ad Hoc (6) Route Discovery,In response to the incoming request, destination builds a RREP packetThe Source address and Destination address are copied from the requestThe Destination sequence number taken from its counter in memoryThe Hop count field is set to
38、 0The Lifetime field controls how long the route is valid.Unicast the packet step by step follows the reverse path.All the nodes on the path learn the route to the destination freely,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,RREQ,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,Reverse Path S
39、etup,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,RREP,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,Forward Path Setup,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,AODV (Example),B,S,E,C,G,F
40、,A,H,D,Y,I,K,P,L,J,T,Z,AODV (Example),B,S,E,C,G,F,A,H,D,Y,I,K,P,L,J,T,Z,2022/11/23,48,5.2.11 Routing in Ad Hoc (7) Route Maintenance,Nodes broadcasts HELLO to tell her neighbor he is alive Active Neighbor will send some packets through the node to destination. Node upstream of break broadcasts RERRN
41、eighboring nodes propagate if they use source of RERR as next hop for destination,2022/11/23,49,5.2.11 Routing in Ad Hoc (8) Route Maintenance,(a) Ds routing table before G goes down.(b) The graph after G has gone down.D informs A/B that G is invalid,2022/11/23,50,5.3 Congestion Control Algorithms,G
42、eneral Principles of Congestion ControlCongestion Prevention PoliciesCongestion Control in Virtual-Circuit SubnetsCongestion Control in Datagram SubnetsLoad SheddingJitter Control,2022/11/23,51,Congestion Definition,When too much traffic is offered, congestion sets in and performance degrades sharpl
43、y.to achieve high utilization, low queueing delay and loss, fairness, and stability.,2022/11/23,52,Resource (link bandwidth and buffer space) vs. loadSources can create a demand for network resources higher than the network can handle at a certain link. The buffer in the routers offers of protection
44、 against an increase in traffic arrival rate.If the buffer space is exhausted, the router has to start dropping packets.Too much buffer space can be more harmful than too little, because the packets will have to be dropped only after they have consumed valuable network resources.local vs. global Flo
45、w control vs. Congestion controlFlow control is only one method of the congestion control.,2022/11/23,53,5.3.1 General Principles of Congestion Control,Open loop and closed loopOpen loop to solve the problem by good design, make decisions without regard to the current state of the network.Sender des
46、cribes its rate to the network with parameters like burst size and interburst interval.Closed loop are based on a feedback loop. Monitor the system, detect when and where congestion occurs.Implicit: the end-hosts monitor their own transmissions (delay, loss)Explicit: congestion info. can be carried
47、in protocol headers explicitlyPass information to where action can be taken.Adjust system operation .,2022/11/23,54,Increase the resourcesDecrease the load. Selecting which packets to dropDetermining when this is appropriate.Limiting new data flow,5.3.1 General Principles of Congestion Control (2),2
48、022/11/23,55,5.3.2 Congestion Prevention Policies,Policies that affect congestion.,2022/11/23,56,5.3.3 Congestion Control in Virtual-Circuit Subnets,Admission controlSet up new VC but avoiding problem areas. Negotiate an agreement between the host and subnet,2022/11/23,57,5.3.4 Congestion Control in
49、 Datagram Subnets (1),Monitor the utilization of its output linesU, the recent utilization of that line.f, instantaneous line utilization, (either 0 or 1), a, constant determines how fast the router forgets recent historyUnew = aUold + (1-a) fWarning state, when U moves above the threshold Warning B
50、itSet in the packets head when into warning state.Destination copied the bit into the next acknowledgement.The source then cut back on traffic.As long as the warning bits continued to flow in, the source continued to decrease its transmission rate.,2022/11/23,58,Hop-by-Hop Choke PacketsA choke packe
