1、1,Chapter 5 Network Layer,College of Computer Science Chongqing University,2,College of Computer Science,Network LayerChapter 5,Design IssuesRouting AlgorithmsCongestion ControlQuality of ServiceInternetworkingNetwork Layer of the Internet,3,College of Computer Science,The Network Layer,Responsible
2、for delivering packets between endpoints over multiple linksThe network layer is the lowest layer that deals with end-to-end transmission.It must:-Know about the topology of the communication subnet;-Take care to choose routes,and-Deal with data exchange between different networks.,4,College of Comp
3、uter Science,Design Issues,Store-and-forward packet switching Connectionless service datagrams Connection-oriented service virtual circuits Comparison of virtual-circuits and datagrams,5,College of Computer Science,Store-and-Forward Packet Switching,Hosts send packets into the network;packets are fo
4、rwarded by routers,ISPs equipment,The environment of the network layer protocols.,6,College of Computer Science,Services Provided to the Transport Layer,The network services to the transport layer goals:The services should be independent of the router technology.The transport layer should be shielde
5、d from the routers present.The uniform addresses plan across LANs and WANs.Connection-oriented or connectionless?-the routers job is moving packets around.The subnet is inherently unreliable.Therefore,the hosts should do error control and flow control themselves.The conclusion is connectionless,with
6、 primitives SEND PACKET and RECEIVE PACKET and little else.-the subnet service should be reliable,connection-oriented.These two camps are exemplified by the Internet and ATM.,7,College of Computer Science,Connectionless ServiceDatagrams,Packet is forwarded using destination address inside itDifferen
7、t packets may take different paths,ISPs equipment,Routing within a diagram subnet,8,College of Computer Science,Connection-OrientedVirtual Circuits,Packet is forwarded along a virtual circuit using tag inside itVirtual circuit(VC)is set up ahead of time,ISPs equipment,As table Cs Table Es Table,Rout
8、ing within a virtual-circuit subnet,9,College of Computer Science,Comparison of Virtual-Circuits&Datagrams,flash,10,College of Computer Science,trade-offs,1.router memory space and bandwidth:VC allow packets to contain circuit numbers instead of full destination addresses.It saves bandwidth.The pric
9、e paid is the table space within the routers.2.setup time versus address parsing time:Using VCs requires a setup phase,need time and resources.However,routing in a VC subnet is easy.In a datagram subnet,a more complicated lookup procedure is required.3.amount of table space required in router memory
10、:A datagram subnet needs an entry for every possible destination,whereas a virtual-circuit subnet just needs an entry for each virtual circuit.4.quality of service and avoiding congestion:VCs have some advantages when the connection is established.With a datagram subnet,congestion avoidance is more
11、difficult.5.overhead required to set up and clear a VC:If the majority of the traffic is expected to be transaction,the use of VC is not wise.(permanent 永久性 VC may be useful here.6.loss of a communication line is fatal to virtual circuits using it but can be easily compensated for if datagrams are u
12、sed.Datagrams also allow the routers to balance the traffic throughout the subnet,since routes can be changed partway through a long sequence of packet transmissions.,11,College of Computer Science,Network LayerChapter 5,Design IssuesRouting AlgorithmsCongestion ControlQuality of ServiceInternetwork
13、ingNetwork Layer of the Internet,12,College of Computer Science,Routing Algorithms(1),Optimality principle Shortest path algorithm Flooding Distance vector routing Link state routing Hierarchical routing Broadcast routing Multicast routing Anycast routing Routing for mobile hosts Routing in ad hoc n
14、etworks,13,College of Computer Science,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 routes for changes in topology(e.g.,failures)Forwarding is the sending of packets
15、along a path,14,College of Computer Science,Routing Algorithms(3),Correctness,simplicity,robustness,stability,fairness,and optimality are properties desirable in a routing algorithm.However,some of them are often contradictory goals.Reducing the number of hops tends to improve the delay and also red
16、uce the amount of bandwidth consumed,which tends to improve the throughput as well.,Conflict between fairness and optimality,15,College of Computer Science,Routing Algorithms(4),Routing algorithms can be grouped into two major classes:1.In nonadaptive algorithms,the choice of the route is computed i
17、n advance,off-line,and downloaded to the routers when the network is booted.Also called static routing.2.Adaptive algorithms change their routing decisions to reflect changes in the network(topology and traffic).Adaptive algorithms differ in where they get their information(e.g.from adjacent routers
18、,or from all routers),when they change the routes,and what metric is used for optimization(e.g.,distance,number of hops,or estimated transit time).Also called dynamic routing.,16,College of Computer Science,The Optimality Principle,“If router J is on the optimal path from router I to router K,then t
19、he optimal path from J to K also falls along the same route”.Consequently the set of optimal routes from all sources to a given destination form a tree rooted at the destination.Such a tree is called a sink tree 汇集树.The goal of all routing algorithms is to discover and use the sink trees for all rou
20、ters.,17,College of Computer Science,Shortest Path Algorithm(1),Dijkstras algorithm 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 dist
21、ance at other nodes to infinityRelax distance to other nodesPick the lowest distance node,add it to sink treeRepeat until all nodes are in the sink tree,18,College of Computer Science,Shortest Path Algorithm(2),A network and first five steps in computing the shortest paths from A to D.Pink arrows sh
22、ow the sink tree so far.,19,College of Computer Science,Shortest Path Algorithm(3),.,.,Start with the sink,all other nodes are unreachable,Relaxation step.Lower distance to nodes linked to newest member of the sink tree,20,College of Computer Science,Shortest Path Algorithm(4),.,Find the lowest dist
23、ance,add it to the sink tree,and repeat until done,21,College of Computer Science,Flooding,A simple method to send a packet to all network nodesEach node 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 f
24、lood;even using a hop limit can blow up exponentially,22,College of Computer Science,Distance Vector Routing(1),Distance vector is a distributed routing algorithmShortest path computation is split across nodesused in the Internet(RIP)Algorithm:Each node knows distance of links to its neighborsEach n
25、ode advertises vector of lowest known distances to all neighborsEach node uses received vectors to update its ownRepeat periodically,23,College of Computer Science,Distance Vector Routing(2),Network,24,College of Computer Science,The Count-to-Infinity Problem,Failures can cause DV to“count to infini
26、ty”while seeking a path to an unreachable node,Good news of a path to A spreads quickly,X,Bad news of no path to A is learned slowly,25,College of Computer Science,Link State Routing(1),Link state is an alternative to distance vectorMore computation but simpler dynamicsWidely used in the Internet(OS
27、PF,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 for each destination,26,College of Computer Science,Link State Routing(2),The idea behind link state rou
28、ting can be stated as five parts.Each router must do the following:1.Discover its neighbors,learn their network address.2.Measure the delay or cost to each of its neighbors.3.Construct a packet telling all it has just learned.4.Send this packet to all other routers.5.Compute the shortest path to eve
29、ry other router.In effect,the complete topology and all delays are experimentally measured and distributed to every router.Then Dijkstras algorithm can be run to find the shortest path to every other router.,27,College of Computer Science,Learning about the Neighbors,When a router is booted,its firs
30、t task is to learn neighbors.It sends a special HELLO packet on each line.The router on the other end is expected to send back a reply telling who it is.,(a)Nine routers and a broadcast LAN.(b)A graph model of(a).,Broadcast LAN modeled as a well-connected node,28,College of Computer Science,Setting
31、Link Costs,Requires each link to have a distance or cost metric for finding shortest paths.Determine the delay is to send over the line a special ECHO packet that the other side is required to send back immediately.,29,College of Computer Science,Building Link State Packets(LSPs),LSP(Link State Pack
32、et)for a node lists neighbors and weights of links to reach them,Network,LSP for each node,30,College of Computer Science,Distributing the LSPs Reliable Flooding,Seq.number and age are used for reliable floodingNew LSPs are acknowledged on the lines they are received and sent on all other lines Exam
33、ple shows the LSP database at router B,31,College of Computer Science,Computing the New Routes,Once a router has accumulated a full set of link state packets,it construct the entire subnet graph,then Dijkstras algorithm can be run locally to construct the shortest path to all possible destinations.,
34、32,College of Computer Science,Distance vector versus link-state Packets,Routing table in A,the subnet,The link state packets,Distance vectorFrom A,Forwarding table,33,College of Computer Science,Hierarchical Routing(1),As network grow in sizes,the routers are divided into what we will call regions,
35、with each router knowing its own region,but nothing about other regions.For huge networks,it may be necessary to group the regions into clusters,the clusters into zones,the zones into groups,and so on.Next is an example of routing in a two-level hierarchy with five regions.The full routing table for
36、 router 1A has 17 entries.There are entries for all the local routers,and all other regions condensed into a single router,so all traffic for region 2 goes via the 1B-2A line,but the rest of the remote traffic goes via the 1C-3B line.Hierarchical routing has reduced the table from 17 to 7 entries.,3
37、4,College of Computer Science,Hierarchical Routing(2),Hierarchical routing reduces the work of route computation but may result in slightly longer paths than flat routing,Best choice to reach nodes in 5 except for 5C,35,College of Computer Science,Broadcast Routing,Broadcast sends a packet to all no
38、desRPF(Reverse Path Forwarding,反向路径转发):send broadcast received on the link to the source out all remaining linksAlternatively,can build and use sink trees at all nodes,Network,Sink tree for I is efficient broadcast,RPF from I is larger than sink tree,36,College of Computer Science,Multicast Routing(
39、1)Dense Case,Multicast sends to a subset of the nodes called a groupUses a different tree for each group and source,Network with groups 1&2,Spanning tree from source S,S,S,S,Multicast tree from S to group 1,Multicast tree from S to group 2,37,College of Computer Science,Multicast Routing(2)Sparse Ca
40、se,CBT(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.,Sink tree from core to group 1,Multicast is send to the core then down when it reaches the sink tree,38,College of Computer Science,Anyc
41、ast Routing,Anycast sends a packet to one(nearest)group memberFalls out of regular routing with a node in many places,Anycast routes to group 1,Apparent topology of sink tree to“node”1,39,College of Computer Science,Routing for Mobile Hosts(1),Each area has one or more foreign agents,keeping track o
42、f all mobile hosts visiting the area.Each area has a home agent,keeping track of hosts whose home in the area,but visiting another area.,A WAN to which LANs,MANs,and wireless cells are attached.,40,College of Computer Science,Routing for Mobile Hosts(2),Mobile hosts can be reached via a home agentFi
43、xed home agent tunnels packets to reach the mobile host;reply can optimize path for subsequent packetsNo changes to routers or fixed hosts,41,College of Computer Science,Routing in Ad Hoc Networks,The network topology changes as wireless nodes moveRoutes are often made on demand,e.g.,AODV(Ad hoc On-demand Distance Vector),As broadcast reaches B&D,
