DOC PREVIEW
U of I CS 438 - Packet Forwarding

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 438 - Packet Forwarding

Documents in this Course
Routing

Routing

5 pages

TCP

TCP

26 pages

TROLL

TROLL

3 pages

Load more
Download Packet Forwarding
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Packet Forwarding and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Packet Forwarding 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?