1Packet Forwarding10/3/07 CS/ECE 438 - UIUC, Fall 2007 2Now Arriving at Layer 3 … although layer 2 switches and layer3 routers are similar in many ways … and ATM/Virtual Circuits are usedat layer 2 these days10/3/07 CS/ECE 438 - UIUC, Fall 2007 3Network Layers and RoutersApplicationPresentationPhysicalTransportSessionData LinkNetworkPhysicalData LinkNetworkApplicationPresentationPhysicalTransportSessionData LinkNetworkHostRouter10/3/07 CS/ECE 438 - UIUC, Fall 2007 4Router DesignInput PortInput PortInput PortInput PortInput PortInput PortOutput PortOutput PortOutput PortOutput PortOutput PortOutput PortSwitchFabric10/3/07 CS/ECE 438 - UIUC, Fall 2007 5Forwarding Forwarding Algorithm Consult packet header Consult forwarding tables Decide on output port Three general types Datagram forwarding Virtual Circuits Source Routing Differ by contents of header and tables10/3/07 CS/ECE 438 - UIUC, Fall 2007 6Switching and Forwarding Forwarding The task of specifying an appropriate output port for apacket Datagram Virtual Circuit Switching Source Routing Each packet contains enough information for a switch todetermine the correct output port Later Building forwarding tables – routing.Packet HeaderOutput Port Specification210/3/07 CS/ECE 438 - UIUC, Fall 2007 7Forwarding with Datagrams Connectionless Each packet travels independently Switch Translates global address to output port Maintains table of translations Used in traditional data networks i.e., Internet10/3/07 CS/ECE 438 - UIUC, Fall 2007 8Forwarding with DatagramsHostAHostGHostDHostEHostCHostBHostFαβ γδ012301230123012310/3/07 CS/ECE 438 - UIUC, Fall 2007 9Routing TableABCDEFGABCDEFGABCDEFGABCDEFGα’s Table β’s Table γ’s Tableδ’s TableEach switch maintainsa routing table thattranslates a host nameto an output portβαAGDECBFγδ0123012301230123011111330112233312333000013010/3/07 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 thelast packet?βαAGDECBFγδ012301230123012310/3/07 CS/ECE 438 - UIUC, Fall 2007 11Forwarding with Datagrams Analogous to following signs Requires globally unique addresses Routing is decentralized A router follows global routing algorithms Two packets usually take the same pathbut… Each router can change its mind at anytime10/3/07 CS/ECE 438 - UIUC, Fall 2007 12Traceroute Example From last year’s solutionstraceroute www.scott.aqtraceroute to www.scott.aq (203.167.246.34), 30hops max, 40 byte packets1 uiuc-ewsl-vlan1.gw.uiuc.edu (130.126.160.1) 0.425ms 0.213 ms 0.319 ms2 …13 ae-0-0.bbr1.Washington1.Level3.net(64.159.0.229) 21.946 msas-2-0.bbr2.Washington1.Level3.net (209.247.10.130)21.351 ms 21.280 ms310/3/07 CS/ECE 438 - UIUC, Fall 2007 13Datagrams Advantages Routes around failures Can send traffic immediately Disadvantages Header requires full unique address Might not be possible to deliver packet Successive packets may not follow the same route Global address to path translations requires significantstorage10/3/07 CS/ECE 438 - UIUC, Fall 2007 14Forwarding with VirtualCircuits Connection oriented Requires explicit setup and teardown Packets follow established route Why support connections in a network? Useful for service notions Important for telephony Switch Translates virtual circuit ID on incoming link to virtualcircuit ID on outgoing link Circuit Ids can be per-link or per-switch Used in ATM10/3/07 CS/ECE 438 - UIUC, Fall 2007 15Virtual Circuits Packet header stores: Virtual Circuit ID Router stores: Table of how to forward packets for eachvirtual circuit Note: VCID need not be global Assign a VCID to a circuit for each link-link pair10/3/07 CS/ECE 438 - UIUC, Fall 2007 16Forwarding with VirtualCircuits Set up A virtual circuit identifier (VCI) is assigned to the circuit foreach link it traverses VCI is locally significant <incoming port, incoming VCI> uniquely identifies VC Switch Maintains a translation table from <incoming port,incoming VCI> to <outgoing port, outgoing VCI> Permanent Virtual Circuits (PVC) Long-lived Switch Virtual Circuits (SVC) Uses signaling to establish VC10/3/07 CS/ECE 438 - UIUC, Fall 2007 17Forwarding with VirtualCircuitsVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINα βδTable entries after A→Econnection is set0100VCIOUTPortOUTVCIINPortIN0203VCIOUTPortOUTVCIINPortIN0100VCIOUTPortOUTVCIINPortINβαAGDECBFγδ0123012301230123A→E10/3/07 CS/ECE 438 - UIUC, Fall 2007 18Forwarding with VirtualCircuits A simple example setup protocol Each host and switch maintains per-linklocal variable for VCI assignment When setup frame leaves host/switch Assign outgoing VCI Increment assignment counter port and circuit id combination is unique switches maintain translation table from incoming port/VCI pair to outgoing port/VCI pair410/3/07 CS/ECE 438 - UIUC, Fall 2007 19Forwarding with VirtualCircuits Assumptions Circuits are simplex On a duplex link, the same VCI can be usedfor two circuits, one in each direction The same VCI can be used on differentports of the same switch At setup, the lowest available VCI is used10/3/07 CS/ECE 438 - UIUC, Fall 2007 20Forwarding with VirtualCircuitsHostAHostGHostDHostEHostCHostBHostFαβ γδ23012123123Set up circuit:A → E1 3000SetupMessage:Dest = EHost EVCI = ?SetupMessage:Dest = E<0,0> →<1,?> SetupMessage:Dest = E<3,0> →<2,?>SetupMessage:Dest = E<0,0> →<1,?>10/3/07 CS/ECE 438 - UIUC, Fall 2007 21Forwarding with VirtualCircuitsHostAHostGHostDHostEHostCHostBHostFαβ γδ23012123123Set up circuit:A → E1 3000ACKMessage:VCI = 0Host EVCI = 0ACKMessage:VCI = 0<0,0> →<1,0> ACKMessage:VCI = 0<3,0> →<2,0>ACKMessage:VCI = 0<0,0> →<1,0>Host AVCI = 010/3/07 CS/ECE 438 - UIUC, Fall 2007 22Forwarding with VirtualCircuitsHostAHostGHostDHostEHostCHostBHostFαβ γδ23012123123Set up circuits:A → EC → FG → E1 3000000000100 12110/3/07 CS/ECE 438 - UIUC, Fall 2007 23Forwarding with VirtualCircuitsVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINTable entries after A→E, C→F, G→E connection is
View Full Document