WIXLIB

ReviewFDescribe each of the following in terms ofnetwork layers– Repeater– Hub/Switch– Bridge– RouterComputer NetworksNetwork LayerTopicsIntroduction to Network LayerIntroduction (5 - 5.1)F Routing (5.2)F Congestion Control (5.3) Internetworking (5.4)Misc (5.5 - 5.6)7FFFFF– the Internet, ATM– may require many hops– data link layer from one end of wire to anotherMust know topology of subnetF Avoid overloading routesF Deal with different networksFNetwork Layer ServicesDepend upon services to Transport LayerF Often network carrier to network customerF– very well definedFGoals– services independent of subnet technology– shield transport layer from topology– uniform number of network addresses, acrossLANs or WANSFLots of freedom, but two factions– connection-oriented and connectionlessService to transport layerGetting packets from source to destinationConnectionlessFInternet camp– 30 years of experience with real networks– subnet is unreliable, no matter how welldesigned– hosts should accept this and do error control andflow control– SEND PACKET and RECV PACKET– each packet full information on source, dest– no ordering or flow control since will beredundant with transport layer1

Connected Vs ConnectionlessConnection-OrientedFFTelephone company camp– transport layer (connectionless)– 100 years of international experience– set up connection between end hosts– negotiate about parameters, quality and cost– communicate in both directions– all packets delivered in sequenceuReally, where to put the complexitycomputers cheapdon’t clutter network layer since relied upon for yearsu some applications don’t want all those servicesuu– subnet (connected)umost users don’t want complex protocols on their machinesureal-time services much better on connected– embedded systems don’tsome might still be lost– flow control to help slow sendersF(Un) Connected, (Un) Reliable– 4 classes, but two are the most popularSummary ComparisonInternal OrganizationFVirtual Circuit– do not choose new route per packet– establish route and re-use– terminate route when terminate connectionFDatagrams– no advance routes– each packet routed independently– more work but more robustExamples of ServicesTopicsFIntroduction (5 - 5.1)Routing (5.2)Congestion Control (5.3)F Misc (5.5 - 5.6)F4 F– the Internet, ATM2

Routing Algorithmscorrectness and simplicity (obviously)F robustnessOptimality vs. FairnessFuuparts can fail, but system should nottopology can changeWhat to optimize?F– Minimize delay– Maximize network throughput– But basic queuing theory says if system nearcapacity then long delays!stabilityF fairness and optimality conflict!FCompromise: minimize hops (common metric)F– Improves delay– Reduces bandwidth, so usually increases throughputTwo Classes of Routing AlgorithmsFOptimality PrincipalNon-Adaptive algorithms– decisions not based on measurements– routes computed offline in advance– also called Static RoutingFAdaptive algorithms“If J is on optimal path from I to K, thenoptimal path from J to K is also on that path”F– change routes based on topology and traffic– info: locally, adjacent routers, all routers– freq: every T seconds, load change, topology changeFExplanation by contradiction:– Call I to J, r1 and J to K, r2– Assume J to K has a route better than r2, say r3– Then r1r3 is shorter than r1r2Metric?u– distance, number of hops, transit timeFcontradiction!Useful when analyzing specific algorithmsSink TreeSet of optimal nodes to a given destinationF Not necessarily uniqueF Routing algorithms want sink treesSink TreesFFNo loops– each packet delivered in finite time– well, routers go up and down and have differentnotions of sink treesFHow is sink tree information collected?– we’ll talk about this laterNext up: static routing algorithmsF On deck: adaptive algorithmsF3

Static Routing - Start SimpleShortest path routingHow do we measure shortest?F Number of hopsF Geographic distanceF Mean queuing and transmission delayF Combination of aboveComputing the Shortest PathFFFFDijkstra’s Algorithm (1959)Label each node with distance from sourceFAs algorithm proceeds, labels change– if unknown, then – tentative at first– permanent when “added” to treeDijkstra’s Algorithm: A to DFloodingFSend every incoming packet on everyoutgoing linkFVast numbers of duplicate packets– problems?– infinite, actually, unless we stop. How?Hop count: decrease each hopF Sequence number: don’t flood twiceF Selective flooding: send only in about theright directionFUses of FloodingFMilitary applicationsFlow Based RoutingFFAbove algorithms only consider topology– Do not consider load– redundancy is nice– routers can be blown to bitsDistributed databases– multiple sources– update all at onceFBaseline– flooding always chooses shortest path– compare other algorithm to floodingEx: if huge traffic from A to B then betterpath would be AGEFCF Min average delay for the entire subnetF4

TopicsFFFFIntroductionRouting (5.2)Modern Routing4– static4– adaptive Congestion Control (5.3)The Internet (5.4, brief)Most of today’s computer networks usedynamic routingF Distance vector routingF– Original Internet routing algorithmF– Modern Internet routing algorithmDistance Vector RoutingComputationDistance Vector RoutingFEach router has table– preferred outgoing line– estimate of “distance” to get thereFAssume knows “distance” to each neighbor– if hops, just 1 hop– if queue length, measure the queues– if delay, can send PING packetFExchange tables with neighbors periodicallyLink state routingFJust got Routing Table from X– Xi is estimate of time from X to iDelay to X is m msecF Know distance to X (say, from ECHO’s)F– Can reach router i via X in Xi m msecDo for all neighborsF Closest to i as “preferred outgoing line”F Can then make new routing tableFDistance VectorExampleGood News Travels FastA is initially downF Path to A updated every exchangeF Stable in 4 exchangesF5

Bad News Travels SlowlyThe Split Horizon HackFReport to router along pathFWidely used but sometimes fails!FIf D goes downFA and B have routethrough other– ex: C says to reach A when talking to B– C can say to D quicklySloooowly converges to (count to infinity)F Better to set infinity to max 1– A and B count to asslowly as before!FOther Ad Hoc also failFLink State RoutingFFUsed (w/variations) on Internet since 1979Basically– Experimentally measure distance– Use Dijkstra’s shortest pathFLearning NeighborsFUpon boot, send HELLO packet along pointto-point lineFRouters attached to LAN?– names must be uniqueSteps– Discover neighbors– Measure delay to each– Construct a packet telling what learned– Send to all other routers– Compute shortest pathMeasuring Line “Cost”FSend ECHO packet, other router returnsFFactor in load (queue length)?Building Link State PacketsFIdentity of sender, sequence number, age,list of (neighbors distance)FWhen to send them?– delay– Yes, if other distance equal, will improve perf– No, oscillating routing tables– Ex: Back and forth between C-F and E-I6

Distribution ProblemsDistributing Link State PacketsF– routes will change “mid-air” based on new topologyFFSequence numbers wrap aroundFRouter crashes start sequence number at 0?FCorrupted packet (65540)Tricky if topology changes as packets travel– use 32 bits and will take 137 yearsBasically, use flooding with checks– increment sequence each time new packet sentForward all new packetsF Discard all duplicatesF If sequence number lower than max for sendingstation– next packet it sends will be ignoredF– then packet is obsolete and discard– packets 5 - 65540 will be ignoredFUse age field– decrement every second– if 0, then discard info for that routerFHold for a bit before processingKeeping Track of PacketsKeeping Track of PacketsStationBFA arrived– ack A– forward C and FFFF arrived– send only to C– ack F– forward A and CFComputing New RoutesFIf C arrives via F before forwarded,updated bits and don’t send to FLink State Routing TodayRouter has all link state packets– build subnet graphN routers degree K, O(KN) spaceF ProblemsFOpen Shortest Path First (OSPF) (5.5.5)FIntermediate Sys Intermediate Sys (IS-IS)F– router lies: forgets link, claims low distance– router fails to forward, or corrupts packets– router runs out of memory, calculates wrong– with large subnets, becomes probableFE arrived via EAB and via EFB– used in Internet today– used in Internet backbones– variant used for IPX in Novell networks– carry multiple network layer protocolsLimit damage from above when happens7

Network to Data Link AdressTranslationA Slight Change in PlansF TheNetwork Layer– Introduction– Routing (5.2)– The Internet (5.5)F44 ARP (5.5.4)OSPF (5.5.5)u BGP (5.5.6)uuFInternet hosts use IPData link layer does not understand IP– Ethernet uses 48-bit address– ex: ifconfig gives 00:10:4B:9E:B3:E6Q: How do IP addresses get mapped ontodata link layer addresses, such as Ethernet?F A: The Address Resolution Protocol (ARP)F– Congestion Control (5.3)Example 1Address ResolutionFLookup IP of eagle.cs.uni.edu– DNS (chapter 7)– returns 192.31.65.5FHost 1 builds packet to 192.31.65.5– now, how does data link layer know where tosend it?– need Ethernet address of Host 2FCould have config file to map IP to Ethernet– hard to maintain for thousands of machinesHost 1 sends message to Host 2, say “mary@eagle.cs.uni.edu”Address ResolutioningARP OptimizationsHost 1 broadcasts packet asking “Whoowns IP address 192.31.65.5 ?”FSend to H2 again?Each machien checks its IP address.F Host 2 responds w/Ethernet address (E2)FMany times, H1 requires ack from H2FF– cache requests (time out in case of new card)– send H1 IP enet (192.31.65.7 , E2)– Address Resolution Protocol (ARP)Host 1 data-link can then encapsulate IPpacket in frame addressed to E2 and dumpF Enet board on Host 2 recognizes, stripsframe header and sends up to IP layerF– H2 caches and uses if neededFHosts broadcast mapping when boot– host looks for its own IP addressushould get no answer, else don’t boot– other enet hosts all can cache answer8

Example 2SolutionsSolution 1F– CS router configured to respond to ARPrequests for 192.31.63.0– Host 1 makes an ARP cache entry of(192.31.63.8 , E3)usends all traffic to Host 4 to CS router– Called Proxy ARPSolution 2F– Host 1 knows Host 4 is on different subnetuHost 1 sends message to Host 4Router does not forward data-link layer broadcastsInside Out and Upside DownEither way .FHost 1 packs IP into Enet frame to E3F CS router receives frame, removes packetFSends ARP packet onto FDDIPuts packet into payload of FDDI frame andput on ringF EE router receives frame, removes packet .FBroadcast:– “my enet adress 13.05.05.18.01.25”– “does anyone know my IP?”– sees 192.31.63.0 to 192.31.60.7– learns 192.31.60.7 is at F3Can a host learn its IP address at boot?– Reverse Address Resolution Protocol (RARP)FFsends to CS router– CS router doesn’t need to know about remotenetworksFFRARP server sees request, sends IPAllows sharing boot images– IP not hard-codedFRARP broadcasts not across router– BOOTP uses UDPRouting on the InternetInternet made up of Autonomous Systems(AS)F Standard for routing inside ASF– interior gateway protocol– OSPFFStandard for routing outside AS– exterior gateway protocol– BGPOpen Shortest Path First (OSPF)1979, RIP, distance vector, replaced bylink-stateF In 1990, OSPF standardizedF “O” is for “Open”, not proprietaryF ASes can be large, need to scaleF– Areas, that are self-contained (not visible fromoutside)9