Network Layer part 1 CPSC 363 Computer Networks Ellen Walker Hiram College Includes figures from Computer Networking by Kurose Ross Addison Wesley 2002 Network Layer Implements host to host communication Distributed throughout hosts and routers No central routing mechanism Network layer functions Path determination routing Forwarding to appropriate output link Call setup ATM not IP Routing vs Forwarding Routing is a network wide process that determines end to end paths Even though it is not done in a centralized way Forwarding is a router only algorithm that sends each packet out the right interface Uses tables determined by routing algorithm Reads addresses in datagram headers Virtual Circuit Setup Build routing information tables including unique VC numbers in each router Data transfer look at each packet determine output interface and VC number based on input interface and VC number Teardown inform both ends and all internal routers that the VC is no longer needed routers remove information from their tables Setup teardown done by signaling messages that cause VC tables to be modified Used by ATM networks basis in telephony guaranteed bandwidth constant or min and ordering Datagram Every packet contains entire address sufficient information to be routed to destination No signaling messages needed Each router maintains a forwarding table to indicate the direction to each destination Forwarding tables can change at any time Therefore no guarantee all packets in message take the same route Today s Internet provides only Datagram service also called best effort Advantages of Internet Model We can build more reliable transfer models e g TCP on top of it Easy to interconnect networks with different link layer technologies satellite vs copper vs radio etc Network doesn t need to understand application packets to route them new applications can always be added on hosts Routing Each host attached directly to a first hop router e g in the network card Goal is to find the least cost path from source router to destination router Assume every link has a numerical cost Add up all link costs to get a path cost Find Least Cost Path from A to F Routing Algorithms Dynamic Results change as network connectivity changes Global Works with complete information about all nodes and link costs Also called link state algorithms Decentralized Each router makes its decisions based on partial information about nodes and link costs More complete routing information evolves by information exchange between neighbors Example distance vector algorithm Link State Algorithm Initialization All nodes broadcast the identities and costs of their neighboring links until every node has an identical table then every node can run its own copy of the algorithm Dijkstra s Algorithm all shortest paths Builds a list of shortest known distance to every other node When complete all links have been considered Dijkstra s Algorithm Initialization N A the only node we know is the source For every node v If v is adjacent to A then D v link cost from A to v Prev v A Else D v infinity Dijkstra s Algorithm Loop Find a node w not in N such that D w is a minimum Add w to N For each v adjacent to w and not in N update distance to be distance through w if it s less D v min D v D w link cost from w to v If D w link cost is shorter set Prev v w This loop is repeated until all nodes are in N Dijkstra s Algorithm Example Source node is A A 0 B 3 C x D 2 E 4 F x Choose node D A 0 B 3 C x D 2 E 3 F x Choose node B A A 0 B 3 C 4 D 2 E 3 F 4 Choose node C A 0 B 3 C 4 D 2 E 3 F 4 Choose node F A 0 B 3 C 4 D 2 E 3 F 4 4 4 2 D 1 C A 0 B 3 C 4 D 2 E 3 F 7 Choose node E B 3 1 E 1 3 F Final Previous table A A B A C B D A E D F E Node chosen when v got its final value to the left Result of Dijkstra s Algorithm Each node knows its previous node along the least cost path from A Example Previous table is A A B A C B D A E D F E Path from A to F A EF A D E F ADEF prev of F is E prev of E is D prev of D is A Use this information to make a next hop table Result of Dijkstra s Algorithm Example Example Previous table is A A B A C B D A E D F E Path from A to F A EF A D E F ADEF prev of F is E prev of E is D prev of D is A In node A next hop F is D In node D next hop F is E In node E next hop F is F Comments on Dijkstra s Algorithm Time cost is O N2 Roughly N searches through N possible next nodes each time Note that the number of links is also O N2 for most networks Traffic considerations can cause oscillation Make costs not depend on traffic not practical Avoid running algorithm simultaneously in all nodes add random delay Distance Vector Algorithm Each node Receives information from its neighbors Calculates Distributes new information to its neighbors until no new information is received This algorithm is Asynchronous Distributed Iterative Distance Table Each row represents a destination Each column represents a next hop Thus a cell indicates the current best estimate cost from me to row via column Example in node A Row B col C c A C C s estimate of C B Example Distance Table In A BDE B379 C478 D925 E834 F745 Red minimum indicates which next hop to take A 1 C 4 4 2 D B 3 1 E 1 3 F Distance Algorithm Initialize all values where row col to direct distance to that col e g B B 3 and D D 2 Initialize all other values to infinity Send min distance for each destination to all neighbors Wait for a change either message or link cost If cost to neighbor v changes by d add d to each value in column v If update from v cost from v to Y has changed recalculate distance to y link to v cost from v to Y If change caused a new min send new D value for that min to all neighbors Example Assuming no initial knowledge generate distance table and next hop Set AD to 5 and let network re adjust Set AB to 100 and try again A 1 C 4 4 2 D B 3 1 E 1 3 F Comments on Distance Vector Algorithm With no changes settles fairly quickly As soon as information propagates from one edge of the network to the other network diameter Good news spreads quickly Reduction in link distance Bad …