Announcement Project 2 extended to 2/20 midnight Project 3 available this weekend Homework 3 available today, will put it onlineOutline Introduction and Network Service Models Routing Principles Link State Algorithm Distance Vector AlgorithmNetwork layer functions transport packet from sending to receiving hosts  network layer protocols in everyhost, routerthree important functions:path determination:route taken by packets from source to dest. Routing algorithmsforwarding:move packets from router’s input to appropriate router outputcall setup:some network architectures require router call setup along path before data flowsnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysicalVirtual circuits call setup, teardown for each call beforedata can flow each packet carries VC identifier (not destination host ID)everyrouter on source-dest path maintains “state” for each passing connection“source-to-dest path behaves much like telephone circuit” performance-wise network actions along source-to-dest pathVirtual circuits: signaling protocols used to setup, maintain teardown VC used in ATM, frame-relay, X.25 not used in today’s Internetapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive dataDatagram networks: the Internet model no call setup at network layer routers: no state about end-to-end connections no network-level concept of “connection”packets forwarded using destination host address packets between same source-dest pair may take different pathsapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Send data2. Receive dataDatagram or VC network: why?Internet data exchange among computers “elastic” service, no strict timing req.  “smart” end systems (computers) can adapt, perform control, error recovery simple inside network, complexity at “edge” many link types  different characteristics uniform service difficultATM evolved from telephony human conversation:  strict timing, reliability requirements need for guaranteed service “dumb” end systems telephones complexity inside networkOutline Introduction and Network Service Models Routing Principles Link State Algorithm Distance Vector AlgorithmRoutingGraph abstraction for routing algorithms: graph nodes are routers graph edges are physical links link cost: delay, $ cost, or congestion levelGoal: determine “good” path(sequence of routers) thru network from source to dest.Routing protocolAEDCBF2213112535 “good” path: typically means minimum cost path other def’s possibleRouting Algorithm classificationGlobal or decentralized information?Global: all routers have complete topology, link cost info “link state” algorithmsDecentralized: router knows physically-connected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors “distance vector” algorithmsStatic or dynamic?Static: routes change slowly over timeDynamic: routes change more quickly periodic update in response to link cost changesA Link-State Routing AlgorithmDijkstra’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.’sNotation: 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 along path from source to v, that is next vN: set of nodes whose least cost path definitively knownDijsktra’s Algorithm1 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) = infinity 7 8 Loop9 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 NDijkstra’s algorithm: exampleStep012345start NAADADEADEBADEBCADEBCFD(B),p(B)2,A2,A2,AD(C),p(C)5,A4,D3,E3,ED(D),p(D)1,AD(E),p(E)infinity2,DD(F),p(F)infinityinfinity4,E4,E4,EAEDCBF2213112535Dijkstra’s algorithm, discussionAlgorithm complexity: n nodes each iteration: need to check all nodes, w, not in N n*(n+1)/2 comparisons: O(n^2) more efficient implementations possible: O(nlogn)Oscillations possible: e.g., link cost = amount of carried trafficADCB11+ee0e1100ADCB2+e0001+e1ADCB02+e1+e100ADCB2+e0e01+e1initially…recomputerouting…recompute…recomputeDistance Vector Routing Algorithmiterative: continues until no nodes exchange info.self-terminating: no “signal” to stopasynchronous: nodes need notexchange info/iterate in lock step!distributed: each node communicates onlywith directly-attached neighborsDistance 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:D (Y,Z)Xdistance from X toY, via Z as next hopc(X,Z) + min {D (Y,w)}Zw==Distance Table: exampleAEDCB781212D ()ABCDA1764B148911D5542Ecost to destination viadestinationD (C,D)Ec(E,D) + min {D (C,w)}Dw==2+2 = 4D (A,D)Ec(E,D) + min {D (A,w)}Dw==2+3 = 5D (A,B)Ec(E,B) + min {D (A,w)}Bw==8+6 = 14loop!loop!Distance table gives routing tableD ()ABCDA1764B148911D5542Ecost to destination viadestinationABCDA,1D,5D,4D,2Outgoing link to use, costdestinationDistance tableRouting tableDistance Vector Routing: overviewIterative, asynchronous: each local iteration caused by:  local link cost change  message from neighbor: its least cost path change from neighborDistributed: each node notifies neighbors onlywhen its least cost path to any destination changes neighbors then notify their neighbors if