Packet ForwardingNow Arriving at Layer 3Network Layers and RoutersRouter DesignForwardingSwitching and ForwardingForwarding with DatagramsSlide 8Routing TableSlide 10Slide 11Traceroute ExampleDatagramsForwarding with Virtual CircuitsVirtual CircuitsSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Forwarding with source routingForwarding with Source RoutingSlide 27ATMSlide 29ATM DetailsATM CellsATM RationaleSlide 33Slide 34Slide 35Slide 36Slide 37ATM and LANsStructure of LANEATM Local Area Network Emulation (LANE)Slide 41ATM/LANE Protocol LayersPacket Forwarding01/14/19 CS/ECE 438 - UIUC, Fall 2007 2Now Arriving at Layer 3… although layer 2 switches and layer 3 routers are similar in many ways… and ATM/Virtual Circuits are used at layer 2 these days01/14/19 CS/ECE 438 - UIUC, Fall 2007 3Network Layers and RoutersApplicationPresentationPhysicalTransportSessionData LinkNetworkPhysicalData LinkNetworkApplicationPresentationPhysicalTransportSessionData LinkNetworkHostRouter01/14/19 CS/ECE 438 - UIUC, Fall 2007 4Router DesignInput PortInput PortInput PortInput PortInput PortInput PortOutput PortOutput PortOutput PortOutput PortOutput PortOutput PortSwitch Fabric01/14/19 CS/ECE 438 - UIUC, Fall 2007 5ForwardingForwarding AlgorithmConsult packet headerConsult forwarding tablesDecide on output portThree general typesDatagram forwardingVirtual CircuitsSource RoutingDiffer by contents of header and tables01/14/19 CS/ECE 438 - UIUC, Fall 2007 6Switching and ForwardingForwardingThe task of specifying an appropriate output port for a packetDatagram Virtual Circuit SwitchingSource RoutingEach packet contains enough information for a switch to determine the correct output portLaterBuilding forwarding tables – routing.Packet HeaderOutput Port Specification01/14/19 CS/ECE 438 - UIUC, Fall 2007 7Forwarding with DatagramsConnectionlessEach packet travels independentlySwitchTranslates global address to output portMaintains table of translationsUsed in traditional data networksi.e., Internet01/14/19 CS/ECE 438 - UIUC, Fall 2007 8Forwarding with DatagramsHost AHost GHost DHost EHost CHost BHost F 012301230123012301/14/19 CS/ECE 438 - UIUC, Fall 2007 9Routing TableABCDEFGABCDEFGABCDEFGABCDEFG’s Table ’s Table ’s Table ’s TableEach switch maintains a routing table that translates a host name to an output portAGDECBF0123012301230123011111330112233312333000013001/14/19 CS/ECE 438 - UIUC, Fall 2007 10Forwarding with DatagramsA EDATAEA sends:C FDATAFC sends:B EDATAEB sends:F GDATAGF sends:A HDATAHA sends:What happens to the last packet?AGDECBF012301230123012301/14/19 CS/ECE 438 - UIUC, Fall 2007 11Forwarding with DatagramsAnalogous to following signsRequires globally unique addressesRouting is decentralizedA router follows global routing algorithmsTwo packets usually take the same path but…Each router can change its mind at any time01/14/19 CS/ECE 438 - UIUC, Fall 2007 12Traceroute ExampleFrom last year’s solutionstraceroute www.scott.aq traceroute to www.scott.aq (203.167.246.34), 30 hops max, 40 byte packets 1 uiuc-ewsl-vlan1.gw.uiuc.edu (130.126.160.1) 0.425 ms 0.213 ms 0.319 ms 2 …13 ae-0-0.bbr1.Washington1.Level3.net (64.159.0.229) 21.946 ms as-2-0.bbr2.Washington1.Level3.net (209.247.10.130) 21.351 ms 21.280 ms01/14/19 CS/ECE 438 - UIUC, Fall 2007 13DatagramsAdvantagesRoutes around failuresCan send traffic immediatelyDisadvantagesHeader requires full unique addressMight not be possible to deliver packetSuccessive packets may not follow the same routeGlobal address to path translations requires significant storage01/14/19 CS/ECE 438 - UIUC, Fall 2007 14Forwarding with Virtual CircuitsConnection orientedRequires explicit setup and teardownPackets follow established routeWhy support connections in a network?Useful for service notionsImportant for telephonySwitchTranslates virtual circuit ID on incoming link to virtual circuit ID on outgoing linkCircuit Ids can be per-link or per-switchUsed in ATM01/14/19 CS/ECE 438 - UIUC, Fall 2007 15Virtual CircuitsPacket header stores:Virtual Circuit IDRouter stores:Table of how to forward packets for each virtual circuitNote: VCID need not be globalAssign a VCID to a circuit for each link-link pair01/14/19 CS/ECE 438 - UIUC, Fall 2007 16Forwarding with Virtual CircuitsSet upA virtual circuit identifier (VCI) is assigned to the circuit for each link it traversesVCI is locally significant<incoming port, incoming VCI> uniquely identifies VCSwitchMaintains a translation table from <incoming port, incoming VCI> to <outgoing port, outgoing VCI>Permanent Virtual Circuits (PVC)Long-livedSwitch Virtual Circuits (SVC)Uses signaling to establish VC01/14/19 CS/ECE 438 - UIUC, Fall 2007 17Forwarding with Virtual CircuitsPort INVCI INPort OUTVCI OUTPort INVCI INPort OUTVCI OUTPort INVCI INPort OUTVCI OUT Table entries after A E connection is set0100VCI OUTPort OUTVCI INPort IN0203VCI OUTPort OUTVCI INPort IN0100VCI OUTPort OUTVCI INPort INAGDECBF0123012301230123AE01/14/19 CS/ECE 438 - UIUC, Fall 2007 18Forwarding with Virtual CircuitsA simple example setup protocolEach host and switch maintains per-linklocal variable for VCI assignmentWhen setup frame leaves host/switchAssign outgoing VCIIncrement assignment counterport and circuit id combination is uniqueswitches maintain translation table fromincoming port/VCI pair tooutgoing port/VCI pair01/14/19 CS/ECE 438 - UIUC, Fall 2007 19Forwarding with Virtual CircuitsAssumptionsCircuits are simplexOn a duplex link, the same VCI can be used for two circuits, one in each directionThe same VCI can be used on different ports of the same switchAt setup, the lowest available VCI is used01/14/19 CS/ECE 438 - UIUC, Fall 2007 20Forwarding with Virtual CircuitsHost AHost GHost DHost EHost CHost BHost F 23012123123Set up circuit:A E1 3000Setup Message: Dest = EHost EVCI = ?Setup Message: Dest = E<0,0> <1,?> Setup Message: Dest = E<3,0> <2,?>Setup Message: Dest = E<0,0> <1,?>01/14/19 CS/ECE 438 - UIUC, Fall 2007 21Forwarding with Virtual CircuitsHost AHost GHost DHost EHost CHost BHost F 23012123123Set up circuit:A E1 3000ACK
View Full Document