19/27/06 CS/ECE 438 - UIUC, Fal l 2006 1Packet Forwarding9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 days9/27/06 CS/ECE 438 - UIUC, Fal l 2006 3Network Layers and RoutersApplicationPresentationPhysicalTransportSessionData LinkNetworkPhysicalData LinkNetworkApplicationPresentationPhysicalTransportSessionData LinkNetworkHostRouter9/27/06 CS/ECE 438 - UIUC, Fal l 2006 4Router DesignInput PortInput PortInput PortInput PortInput PortInput PortOutput PortOutput PortOutput PortOutput PortOutput PortOutput PortSwitchFabric9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 tables9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 Specification29/27/06 CS/ECE 438 - UIUC, Fal l 2006 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., Internet9/27/06 CS/ECE 438 - UIUC, Fal l 2006 8Forwarding with DatagramsHostAHostGHostDHostEHostCHostBHostFαβ γδ01230123012301239/27/06 CS/ECE 438 - UIUC, Fal l 2006 9Routing TableABCDEFGABCDEFGABCDEFGABCDEFGα’s Table β’s Table γ’s Tableδ’s TableEach switch maintainsa routing table thattranslates a host nameto an output portβαAGDECBFγδ012301230123012301111133011223331233300001309/27/06 CS/ECE 438 - UIUC, Fal l 2006 10Forwarding with DatagramsA → EDATAEA sends:C → FDATAFC sends:B → EDATAEB sends:F → GDATAGF sends:A → HDATAHA sends:What happens to thelast packet?βαAGDECBFγδ01230123012301239/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 anytime9/27/06 CS/ECE 438 - UIUC, Fal l 2006 12Traceroute Example From HW1 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.425 ms 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 ms39/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 significantstorage9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 ATM9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 pair9/27/06 CS/ECE 438 - UIUC, Fal l 2006 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 VC9/27/06 CS/ECE 438 - UIUC, Fal l 2006 17Forwarding 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 pair9/27/06 CS/ECE 438 - UIUC, Fal l 2006 18Forwarding 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 used49/27/06 CS/ECE 438 - UIUC, Fal l 2006 19Forwarding 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,?>9/27/06 CS/ECE 438 - UIUC, Fal l 2006 20Forwarding 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 = 09/27/06 CS/ECE 438 - UIUC, Fal l 2006 21Forwarding with VirtualCircuitsHostAHostGHostDHostEHostCHostBHostFαβ γδ23012123123Set up circuits:A → EC → FG → E1 3000000000100 1219/27/06 CS/ECE 438 - UIUC, Fal l 2006 22Forwarding with VirtualCircuitsVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINα βδTable entries after A→E connection is set0100VCIOUTPortOUTVCIINPortIN0203VCIOUTPortOUTVCIINPortIN0100VCIOUTPortOUTVCIINPortINβαAGDECBFγδ0123012301230123A→E9/27/06 CS/ECE 438 - UIUC, Fal l 2006 23Forwarding with VirtualCircuitsVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINVCIOUTPortOUTVCIINPortINTable entries after A→E, C→F, G→E connection is
View Full Document