Switching - Cornell University

1 SwitchingAn Engineering Approach to Computer NetworkingAn Engineering Approach to Computer NetworkingWhat is it all about?nnHow do we move traffic from one part of the network to another?How do we move traffic from one part of the network to another?nnConnect end-systems to switches, and switches to each otherConnect end-systems to switches, and switches to each othernnData arriving to an input port of a switch have to be moved toData arriving to an input port of a switch have to be moved toone or more of the output portsone or more of the output portsTypes of Switching elementsnnTelephone switchesTelephone switchesuuswitch samplesswitch samplesnnDatagram routersDatagram routersuuswitch datagramsswitch datagramsnnATM switchesATM switchesuuswitch ATM cellsswitch ATM cellsClassificationnnPacket vs. circuit switchesPacket vs. circuit switchesuupackets have headers and samples don tpackets have headers and samples don tnnConnectionless vs. connection orientedConnectionless vs.

2 Connection orienteduuconnection oriented switches need a call setupconnection oriented switches need a call setupuusetupishandledinsetupishandledinc ontrol planecontrol planebyswitch controlleruconnectionless switches deal withself-containeddatagramsConnectionles s(router)Connection-oriented( Switching system)PacketswitchInternet routerATM Switching systemCircuitswitchTelephone switchingsystemOther Switching element functionsnnParticipate in routing algorithmsParticipate in routing algorithmsuuto build routing tablesto build routing tablesnnResolve contention for output trunksResolve contention for output trunksuuschedulingschedulingnnAdmission controlAdmission controluuto guarantee resources to certain streamsto guarantee resources to certain streamsnnWe ll discuss these laterWe ll discuss these laternnHere we focus on pure data movementHere we focus on pure data movementRequirementsnnCapacity of switch is the maximum rate at which it can moveCapacity of switch is the maximum rate at which it can moveinformation, assuming all data paths are simultaneously activeinformation, assuming all data paths are simultaneously activennPrimary goal:Primary goal.

3 Maximize capacitymaximize capacityuusubject to cost and reliability constraintssubject to cost and reliability constraintsnnCircuit switch must reject call if can t find a path for samplesCircuit switch must reject call if can t find a path for samplesfrom input to outputfrom input to outputuugoal:goal:minimize call blockingminimize call blockingnnPacket switch must reject a packet if it can t find a buffer to storePacket switch must reject a packet if it can t find a buffer to storeit awaiting access to output trunkit awaiting access to output trunkuugoal:goal:minimize packet lossminimize packet lossnnDon t reorderDon t reorderpacketspacketsA generic switchOutlinennCircuit switchingCircuit switchingnnPacket switchingPacket switchinguuSwitch generationsSwitch generationsuuSwitch fabricsSwitch fabricsuuBuffer placementBuffer placementuuMulticast switchesMulticast switchesCircuit switchingnnMoving 8-bit samples from an input port to an output portMoving 8-bit samples from an input port to an output portnnRecall that samples have no headersRecall that samples have no headersnnDestination of sample depends onDestination of sample depends ontimetimeat which it arrives at theat which it arrives at theswitchswitchuuactually, relative order within aactually, relative order within aframeframennWe ll first study something simpler than a switch: a multiplexorWe ll first study something simpler than a switch.

4 A multiplexorMultiplexors and demultiplexorsnnMost trunks time division multiplex voice samplesMost trunks time division multiplex voice samplesnnAt a central office, trunk is demultiplexed and distributed toAt a central office, trunk is demultiplexed and distributed toactive circuitsactive circuitsnnSynchronous multiplexorSynchronous multiplexoruuN input linesN input linesuuOutput runs N times as fast as inputOutput runs N times as fast as inputMore on multiplexingnnDemultiplexorDemultiplexor uuone input line and N outputs that run N times slowerone input line and N outputs that run N times sloweruusamples are placed in output buffer in round robin ordersamples are placed in output buffer in round robin ordernnNeither multiplexor nor demultiplexor needs addressingNeither multiplexor nor demultiplexor needs addressinginformation (why?)information (why?)nnCan cascade multiplexorsCan cascade multiplexorsuuneed a standardneed a standarduuexample: DS hierarchy in the US and Japanexample: DS hierarchy in the US and JapanInverse multiplexingnnTakes a high bit-rate stream and scatters it across multipleTakes a high bit-rate stream and scatters it across multipletrunkstrunksnnAt the other end, combines multiple streamsAt the other end, combines multiple streamsuuresequencingresequencingto accommodate variation in delaysto accommodate variation in delaysnnAllows high-speed virtual links using existing technologyAllows high-speed virtual links using existing technologyA circuit switchnnA switch that can handle N calls has N logical inputs and NA switch that can handle N calls has N logical inputs and Nlogical outputslogical outputsuuNupto200,000 Nupto200,000nnIn practice, input trunks are multiplexedIn practice, input trunks are multiplexeduuexample: DS3 trunk carries 672 simultaneous callsexample.

5 DS3 trunk carries 672 simultaneous callsnnMultiplexed trunks carryMultiplexed trunks carryframesframes=setofsamples=setofsamp lesnnGoal: extract samples from frame, and depending on position inGoal: extract samples from frame, and depending on position inframe, switch to outputframe, switch to outputuueach incoming sample has to get to the right output line and theeach incoming sample has to get to the right output line and therightslotintheoutputframerightslotint heoutputframeuudemultiplexdemultiplex,sw itch,multiplex,switch,multiplexCall blockingnnCan t find a path from input to outputCan t find a path from input to outputnnInternal blockingInternal blockinguuslot in output frame exists, but no pathslot in output frame exists, but no pathnnOutput blockingOutput blockinguuno slot in output frame is availableno slot in output frame is availablennOutput blocking is reduced inOutput blocking is reduced intransittransitswitchesswitchesuuneed to put a sample in one ofneed to put a sample in one ofseveralseveralslots going to the desirednext hopTime division switchingnnKey idea: whenKey idea.

6 Whendemultiplexingdemultiplexing, position in frame determines, position in frame determinesoutput trunkoutput trunknnTime division Switching interchanges sample position within aTime division Switching interchanges sample position within aframe: time slot interchange (TSI)frame: time slot interchange (TSI)HowlargeaTSIcanwebuild?nnLimit is time taken to read and write to memoryLimit is time taken to read and write to memorynnFor 120,000 circuitsFor 120,000 circuitsuuneed to read and write memory once every 125 microsecondsneed to read and write memory once every 125 microsecondsuueach operation takes around operation takes around > impossible with current=> impossible with currenttechnologytechnologynnNeed to look to other techniquesNeed to look to other techniquesSpace division switchingnnEach sample takes a different pathEach sample takes a different paththoguhthoguhthetheswithcswithc,,depe nding on its destinationdepending on its destinationCrossbarnnSimplest possible space-division switchSimplest possible space-division switchnnCrosspointsCrosspointscanbeturne donoroffnFor multiplexed inputs, need a switchingschedule(why?)

7 NInternally nonblockingubut need N2crosspointsutime taken to set each crosspoint grows quadraticallyuvulnerable to single faults (why?)Multistage crossbarnnIn a crossbar during each Switching time only oneIn a crossbar during each Switching time only onecrosspointcrosspointperperrow or column is activerow or column is activennCan save crosspoints if aCan save crosspoints if acrosspointcrosspointcan attach to more thancan attach to more thanone input line (why?)one input line (why?)nnThis is done in a multistage crossbarThis is done in a multistage crossbarnnNeed to rearrange connections every Switching timeNeed to rearrange connections every Switching timeMultistage crossbarnnCan suffer internal blockingCan suffer internal blockinguuunless sufficient number of second-level stagesunless sufficient number of second-level stagesnnNumber of crosspoints < NNumber of crosspoints < N22nnFinding a path from input to output requires a depth-first-searchFinding a path from input to output requires a depth-first-searchnnScales better than crossbar, but still not too wellScales better than crossbar, but still not too welluu120,000 call switch needs ~250 million crosspoints120.

8 000 call switch needs ~250 million crosspointsTime-space switchingnnPrecede each input trunk in a crossbar with a TSIP recede each input trunk in a crossbar with a TSInnDelay samples so that they arrive at the right time for the spaceDelay samples so that they arrive at the right time for the spacedivision switch s scheduledivision switch s scheduleTime-space-time (TST) switchingnnAllowed to flip samples both on input and output trunkAllowed to flip samples both on input and output trunknnGives more flexibility => lowers call blocking probabilityGives more flexibility => lowers call blocking probabilityOutlinennCircuit switchingCircuit switchingnnPacket switchingPacket switchinguuSwitch generationsSwitch generationsuuSwitch fabricsSwitch fabricsuuBuffer placementBuffer placementuuMulticast switchesMulticast switchesPacket switchingnnIn a circuit switch, path of a sample is determined at time ofIn a circuit switch, path of a sample is determined at time ofconnection establishmentconnection establishmentnnNo need for a sample header--position in frame is enoughNo need for a sample header--position in frame is enoughnnIn a packet switch, packets carry a destination fieldIn a packet switch.

9 Packets carry a destination fieldnnNeed to look up destination port on-the-flyNeed to look up destination port on-the-flynnDatagramDatagramuulookup based on entire destination addresslookup based on entire destination addressnnCellCelluulookup based on VCIlookup based on VCInnOther than that, very similarOther than that, very similarRepeaters, bridges, routers, and gatewaysnnRepeaters: at physical levelRepeaters: at physical levelnnBridges: at datalink level (based on MAC addresses) (L2)Bridges: at datalink level (based on MAC addresses) (L2)uudiscover attached stations by listeningdiscover attached stations by listeningnnRouters: at network level (L3)Routers: at network level (L3)uuparticipateinroutingprotocolsparti cipateinroutingprotocolsnnApplication level gateways: at application level (L7)Application level gateways: at application level (L7)uutreat entire network as a single hoptreat entire network as a single mail gateways mail gateways andtranscoderstranscodersnnGain functionality at the expense of forwarding speedGain functionality at the expense of forwarding speeduufor best performance, push functionality as low as possiblefor best performance, push functionality as low as possiblePort mappersnnLook up output port based on destination addressLook up output port based on destination addressnnEasy for VCI: just use a tableEasy for VCI: just use a tablennHarder for datagrams:Harder for datagrams:uuneed to findneed to findlongest prefix matchlongest prefix packet with address packet with address : ( *, 3), ( *, 4), ( , 2)entries: ( *, 3), ( *, 4), ( , 2)nnA standard solution:A standard solution.

10 TrietrieTriesnnTwo ways to improve performanceTwo ways to improve performanceuucache recently used addresses in a CAMcache recently used addresses in a CAMuumove common entries up to a higher level (match longer strings)move common entries up to a higher level (match longer strings)Blocking in packet switchesnnCan have both internal and output blockingCan have both internal and output blockingnnInternalInternaluuno path to outputno path to outputnnOutputOutputuutrunk unavailabletrunk unavailablennUnlike a circuit switch, cannot predict if packets will block (why?)Unlike a circuit switch, cannot predict if packets will block (why?)nnIf packet is blocked, must either buffer or drop itIf packet is blocked, must either buffer or drop itDealing with blockingnnOverprovisioningOverprovisioni nguuinternal links much faster than inputsinternal links much faster than inputsnnBuffersBuffersuuat input or outputat input or outputnnBackpressureBackpressureuuif switch fabric doesn t have buffers, prevent packet from enteringif switch fabric doesn t have buffers.