Question? Leave a message!




Network layer functions

Network layer functions 17
Computer Communication Networks (CCN) Network Layer (Routing) 1Network layer functions 1 application transport network data link network physical data link network • transport packet network physical data link data link physical physical from sending to network data link network physical receiving hosts data link physical network • network layer network data link data link physical physical protocols in every network application data link transport physical host, router network data link physical Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 2Network layer functions 2 three important functions: • path determination: route taken by packets from source to dest. Routing algorithms • Switching (forwarding): move packets from router‟s input to appropriate router output • call setup: (optional) some network architectures require router call setup along path before data flows Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 3Network service model Q: What service model for “channel” transporting The most important packets from sender to abstraction provided receiver by network layer: • guaranteed bandwidth virtual circuit • preservation of interpacket or timing (no jitter) datagram • lossfree delivery • inorder delivery • congestion feedback to sender Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 4Datagram networks: the Internet model 1 • no call setup at network layer • routers: no state about endtoend connections – no networklevel concept of “connection” • packets typically routed using destination host ID – packets between same sourcedest pair may take different paths Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 5Datagram networks: the Internet model 2 application application transport transport network network 1. Send data 2. Receive data data link data link physical physical Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 6Routing Routing protocol Goal: determine “good” path 5 (sequence of routers) thru 3 network from source to dest. B C 5 2 A 2 1 F 3 • Graph abstraction for 1 2 D E routing algorithms: 1 • graph nodes are routers “good” path: • graph edges are typically means physical links minimum cost path other def‟s possible • link cost: delay, cost, or congestion level Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 7Routing Algorithm classification 1 Global or decentralized information Global: • all routers have complete topology, link cost info • “link state” algorithms Decentralized: • router knows physicallyconnected neighbors, link costs to neighbors • iterative process of computation, exchange of partial info with neighbors • “distance vector” algorithms Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 8Routing Algorithm classification 2 Static or dynamic Static: • routes change slowly over time Dynamic: • routes change more quickly – periodic update – in response to link cost changes Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 9A LinkState Routing Algorithm 1 Dijkstra‟s algorithm • net topology, link costs known to all nodes – accomplished via “link state broadcast” – all nodes have same info • computes least cost paths from one node („source”) to all other nodes – gives routing table for that node – iterative: after k iterations, know least cost path to k dest.‟s Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 10A LinkState Routing Algorithm 2 Notation: • c(i,j): link cost from node i to j. cost infinite if not direct neighbors • D(v): current value of cost of path from source to dest. V • p(v): predecessor node (neighbor of v) along path from source to v • N: set of nodes whose least cost path definitively known Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 11Dijkstra‟s algorithm: example D(B),p(B) D(D),p(D) Step D(C),p(C) D(E),p(E) start N D(F),p(F) 2,A 1,A 0 5,A infinity A infinity 2,A 1 4,D 2,D AD infinity 2 2,A 3,E ADE 4,E 3 3,E ADEB 4,E 4 ADEBC 4,E 5 ADEBCF 5 3 B C 5 2 A 2 1 F 3 1 2 D E 1 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 12Dijsktra‟s Algorithm 1 Initialization: 2 N = A 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 / new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v / 15 until all nodes in N Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 13Dijkstra‟s algorithm: discussion Algorithm complexity: n nodes • each iteration: need to check all nodes, w, not in N • n(n+1)/2 comparisons: O(n2) • more efficient implementations possible: O(nlogn) Oscillations possible: • e.g., link cost = amount of carried traffic Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 14Distance Vector Routing Algorithm 1 iterative: • continues until no nodes exchange info. • selfterminating: no “signal” to stop asynchronous: • nodes need not exchange info/iterate in lock step distributed: • each node communicates only with directly attached neighbors Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 15Distance Vector Routing Algorithm 2 Distance Table data structure • each node has its own • row for each possible destination • column for each directlyattached neighbor to node • example: in node X, for dest. Y via neighbor Z: distance from X to = X Y, via Z as next hop D (Y,Z) Z c(X,Z) + min D (Y,w) = w Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 16Distance table: example cost to destination via 1 E B C D () A B 7 D A 2 8 1 A 1 14 5 E D 2 B 7 8 5 E D c(E,D) + min D (C,w) D (C,D) = w C 6 9 = 2+2 = 4 4 E D c(E,D) + min D (A,w) D (A,D) = w D 4 11 2 = 2+3 = 5 loop E B c(E,B) + min D (A,w) D (A,B) = w = 8+6 = 14 loop Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 17Distance table gives routing table cost to destination via Outgoing link E to use, cost D () A B D A 1 14 5 A A,1 B 7 8 5 B D,5 C 6 9 4 C D,4 D 4 11 2 D D,4 Routing table Distance table Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 18Distance Vector Routing: overview 1 Iterative, asynchronous: each local iteration caused by: • local link cost change • message from neighbor: its least cost path change from neighbor Distributed: • each node notifies neighbors only when its least cost path to any destination changes – neighbors then notify their neighbors if necessary Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 19Distance Vector Routing: overview 2 Each node: wait for (change in local link cost of msg from neighbor) recompute distance table if least cost path to any dest has changed, notify neighbors Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 20Distance Vector Algorithm 1 At all nodes, X: 1 Initialization: 2 for all adjacent nodes v: X 3 D (,v) = infty / the operator means "for all rows" / X 4 D (v,v) = c(X,v) 5 for all destinations, y X 6 send min D (y,w) to each neighbor / w over all X's neighbors / w Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 21Distance Vector Algorithm 2 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 / change cost to all dest's via neighbor v by d / 14 / note: d could be positive or negative / X X 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 / shortest path from V to some Y has changed / 19 / V has sent a new value for its min DV(Y,w) / w 20 / call this received new value is "newval" / X 21 for the single destination y: D (Y,V) = c(X,V) + newval 22 X 23 if we have a new min D (Y,w)for any destination Y w X 24 send new value of min D (Y,w) to all neighbors w 25 26 forever Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 22Distance Vector Algorithm: example 1 Y 2 1 Z X X Z c(X,Z) + min D (Y,w) D (Y,Z) = 7 w = 7+1 = 8 Y X c(X,Y) + min D (Z,w) D (Z,Y) = w = 2+1 = 3 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 23Distance Vector: link cost changes 1 Link cost changes: 1 node detects local link cost change Y updates distance table (line 15) 4 1 if cost change in least cost path, notify X Z 50 neighbors (lines 23,24) algorithm terminates “good news travels fast” Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 24Distance Vector: link cost changes 2 Link cost changes: 60 good news travels fast Y 4 1 bad news travels slow “count X Z to infinity” problem 50 algorithm continues on Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 25Distance Vector: poisoned reverse If Z routes through Y to get to X : 60 Z tells Y its (Z‟s) distance to X is infinite Y 4 1 (so Y won‟t route to X via Z) X Z will this completely solve count to infinity 50 problem algorithm terminates Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 26Comparison of LS and DV algorithms 1 Message complexity • LS: with n nodes, E links, O(nE) msgs sent each • DV: exchange between neighbors only – convergence time varies Speed of Convergence • LS: O(n2) algorithm requires O(nE) msgs – may have oscillations • DV: convergence time varies – may be routing loops – counttoinfinity problem Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 27Comparison of LS and DV algorithms 1 Robustness: what happens if router malfunctions LS: – node can advertise incorrect link cost – each node computes only its own table DV: – DV node can advertise incorrect path cost – each node‟s table used by others • error propagate thru network Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 28Internet AS Hierarchy IntraAS border (exterior gateway) routers InterAS interior (gateway) routers Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 29IntraAS Routing • Also known as Interior Gateway Protocols (IGP) • Most common IGPs: – RIP: Routing Information Protocol – OSPF: Open Shortest Path First – IGRP: Interior Gateway Routing Protocol (Cisco propr.) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 30RIP (Routing Information Protocol) 1 • Distance vector algorithm • Included in BSDUNIX Distribution in 1982 • Distance metric: of hops (max = 15 hops) • Distance vectors: exchanged every 30 sec via Response Message (also called advertisement) • Each advertisement: route to up to 25 destination nets Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 31RIP (Routing Information Protocol) 2 z w x y A D B C Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x 1 …. …. .... Routing table in D Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 32RIP: Link Failure and Recovery If no advertisement heard after 180 sec neighbor/link declared dead – routes via neighbor invalidated – new advertisements sent to neighbors – neighbors in turn send out new advertisements (if tables changed) – link failure info quickly propagates to entire net – poison reverse used to prevent pingpong loops (infinite distance = 16 hops) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 33RIP Table processing 1 • RIP routing tables managed by applicationlevel process called routed (daemon) • advertisements sent in UDP packets, periodically repeated Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 34RIP Table processing 2 Router: giroflee.eurocom.fr Destination Gateway Flags Ref Use Interface 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454 Three attached class C networks (LANs) Router only knows routes to attached LANs Default router used to “go up” Route multicast address: 224.0.0.0 Loopback interface (for debugging) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 35OSPF (Open Shortest Path First) • “open”: publicly available • Uses Link State algorithm – LS packet dissemination – Topology map at each node – Route computation using Dijkstra‟s algorithm • OSPF advertisement carries one entry per neighbor router • Advertisements disseminated to entire AS (via flooding) Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar 36
Website URL
Comment