Network layer functionsNetwork service modelVirtual circuitsVirtual circuits: signaling protocolsDatagram networks:Network layer service models:Datagram or VC network: why?RoutingRouting Algorithm classificationA Link-State Routing AlgorithmDijsktra’s AlgorithmDijkstra’s algorithm: exampleDijkstra’s algorithm, discussionDistance Vector Routing AlgorithmDistance Table: exampleDistance table gives routing tableDistance Vector Routing: overviewDistance Vector Algorithm:Distance Vector Algorithm (cont.):Distance Vector Algorithm: exampleSlide 21Distance Vector: link cost changesSlide 23Comparison of LS and DV algorithmsHierarchical RoutingSlide 26Intra-AS and Inter-AS routingSlide 28Network Layer 4-1Network layer functionstransport packet from sending to receiving hosts network layer protocols in every host, 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 linkphysicalNetwork Layer 4-2Network service modelQ: What service model for “channel” transporting packets from sender to receiver?guaranteed bandwidth?preservation of inter-packet timing (no jitter)?loss-free delivery?in-order delivery?congestion feedback to sender????virtual circuitor datagram?The most important abstraction provided by network layer:service abstractionNetwork Layer 4-3Virtual circuitscall setup, teardown for each call before data can floweach packet carries VC identifier (not destination host ID)every router on source-dest path maintains “state” for each passing connectiontransport-layer connection only involved two end systemslink, router resources (bandwidth, buffers) may be allocated to VCto get circuit-like performance“source-to-dest path behaves much like telephone circuit”performance-wisenetwork actions along source-to-dest pathNetwork Layer 4-4Virtual circuits: signaling protocolsused to setup, maintain teardown VCused in ATM, frame-relay, X.25not used in today’s Internet– research issueapplicationtransportnetworkdata linkphysicalapplicationtransportnetworkdata linkphysical1. Initiate call2. incoming call3. Accept call4. Call connected5. Data flow begins6. Receive dataNetwork Layer 4-5Datagram networks: 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 dataNetwork Layer 4-6Network layer service models:NetworkArchitectureInternetATMATMATMATMServiceModelbest effortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedrateguaranteed minimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno (inferredvia loss)nocongestionnocongestionyesnoGuarantees ?Internet model being extended: Intserv, DiffservNetwork Layer 4-7Datagram 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 networkNetwork Layer 4-8RoutingGraph 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 possibleNetwork Layer 4-9Routing 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 changesNetwork Layer 4-10A 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 knownNetwork Layer 4-11Dijsktra’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 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 NNetwork Layer 4-12Dijkstra’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,EAEDCBF2213112535Network Layer 4-13Dijkstra’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