Question? Leave a message!




Network layer functions

Network layer functions 17
Dr.ShivJindal Profile Pic
Dr.ShivJindal,India,Teacher
Published Date:19-07-2017
Website URL
Comment
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 inter-packet ? or timing (no jitter)? ? datagram? • loss-free delivery? ? • in-order 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 end-to-end connections – no network-level concept of “connection” • packets typically routed using destination host ID – packets between same source-dest 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 physically-connected 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 Link-State 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 Link-State 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. • self-terminating: 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 directly-attached 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 20