DOC PREVIEW
U of I CS 438 - Switching Hardware

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 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 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

19/22/06 CS/ECE 438 - UIUC, Fall 2006 1Switching Hardware9/22/06 CS/ECE 438 - UIUC, Fall 2006 2Switch DesignChampaignEffinghamSpringfieldBloomingtonSt. LouisIndianapolisChicagoHow should wedesign Champaignto accommodatetraffic flows?9/22/06 CS/ECE 438 - UIUC, Fall 2006 3Contention Bridges: same collision domain If an output port is busy when forwarding packetfrom input port, cause collision Switches: different collision domain Use CSMA/CD before sending packet onward Buffer packets When output port is busy When multiple packets are destined for sameoutput port9/22/06 CS/ECE 438 - UIUC, Fall 2006 4Switch DesignInput PortInput PortInput PortInput PortInput PortInput PortOutput PortOutput PortOutput PortOutput PortOutput PortOutput PortSwitchFabric9/22/06 CS/ECE 438 - UIUC, Fall 2006 5Contention – Output PortBufferingBAirate Bobwriting complaintletter in triplicateAlicewaiting to returnpenny given in errortrying to buy food youstandard checkout lines customer service1x6 switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 6Contention – Input PortBufferingstandard checkout lines customer serviceBAirate Bobwriting complaintletter in triplicateAlicewaiting to returnpenny given in errortrying to buy foodyou1x6 switchhead-of-lineblockingcashiers are standing by!cashiers are standing by!cashiers are standing by!29/22/06 CS/ECE 438 - UIUC, Fall 2006 7Contention – Output PortContentionBirate Bobwriting complaintletter in triplicateAlice waiting to return penny given in erroryouAwaiting to complainabout head-of-line blockingstandard checkout lines customer service1x6 switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 8Contention – BufferingCapacityByoubuffering capacityper outputis finiteAangry mob eagerlyawaiting opportunityto address underpaidcustomer servicerepresentative(others turned away at door)angry mob eagerlyawaiting opportunityto address underpaidcustomer servicerepresentativeangry mob eagerlyawaiting opportunityto address underpaidcustomer servicerepresentativestandard checkout lines customer service1x6 switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 9Contention – Back Pressure Let the receiver tell the sender to slow down Propagation delay requires that the receiverreact before the buffer is full Typically used in networks with smallpropagation delayswitch 1 switch 2“no more, please”9/22/06 CS/ECE 438 - UIUC, Fall 2006 10Contention – Back Pressure NOTE Propagation delay requires that switch 2 exertbackpressure at high-water mark rather whenbuffer completely full. Backpressure is thustypically only used in networks with smallpropagation delays (e.g., switch fabrics).Switch2 113 2 14 3 215 4 312 1234569 8 76 5 4123stop12347 6 5stop123458 7 6stop1234569 87Discard:91234568Discard:9Discard:123456Switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 11Switch Design Goals Throughput Number of packets a switch can forwardper second Scalability How many input/output ports can itconnect Cost Per port monetary costs9/22/06 CS/ECE 438 - UIUC, Fall 2006 12Special Purpose Switches Problem Connect N inputs to M outputs NxM (“N by M”) switch Often N = M Goals High throughput Best is MIN(sum of inputs, sum of outputs) Avoid contention Good scalability Linear size/cost growth39/22/06 CS/ECE 438 - UIUC, Fall 2006 13Switch Design Ports handle complexity Forwarding decisions Buffering Simple fabric Move packets from inputs to outputs May have a small amount of internalbuffering9/22/06 CS/ECE 438 - UIUC, Fall 2006 14Switch Design Goals Throughput Main problem is contention Need a good traffic model Arrival time Destination port Packet length Telephony modeling is well understood Until faxes and modems Modeling of data traffic is new Not well understood Will good models help?9/22/06 CS/ECE 438 - UIUC, Fall 2006 15Switch Design Goals Contention Avoid contention through intelligent buffering Use output buffering when possible Apply back pressure through switch fabric Improve input buffering through non-FIFObuffers Reduces head-of-line blocking Drop packets if input buffers overflow9/22/06 CS/ECE 438 - UIUC, Fall 2006 16Switch Design Goals Scalability O(N) ports Port design complexity O(N) gives O(N2)for entire switch Port design complexity of O(1) givesO(N) for entire switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 17Switch Design Crossbar switches Banyan Networks Batcher Networks Sunshine Switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 18Crossbar Switch Every input port is connected to everyoutput port NxN Output ports Complexity scales as O(N2)49/22/06 CS/ECE 438 - UIUC, Fall 2006 19Crossbar SwitchOutput PortOutput PortOutput PortOutput Port9/22/06 CS/ECE 438 - UIUC, Fall 2006 20Knockout Switch Assumption: It is unlikely that N inputs will have packets destined forthe same output port Pick L from N packets at a port Output port maintains L cyclic buffers Shifter places up to L packets in one cycle Each buffer gets only one packet Output port uses round-robin between buffers Arrival order is maintained Problem Hot spots Output ports scale as O(N)9/22/06 CS/ECE 438 - UIUC, Fall 2006 21Knockout Switch Output port design Packet filters Recognize packets destined for a specific port Concentrator Selects up to L packets from those destined for thisport Discards excess packets Queue Length L9/22/06 CS/ECE 438 - UIUC, Fall 2006 22Knockout SwitchR RRDRRDR2x2randomselectorDelayunitChoose L of NEx: 2 of 4What happensif more than Larrive?1 2 3 4Choice1Choice2Discard1341234Discard12349/22/06 CS/ECE 438 - UIUC, Fall 2006 23Self-Routing Fabrics Idea Use source routing on “network” in switch Input port attaches output port number asheader Fabric routes packet based on output port Types Banyan Network Batcher-Banyan Network Sunshine Switch9/22/06 CS/ECE 438 - UIUC, Fall 2006 24Banyan Network A network of 2x2 switches Each element routes to output 0 or 1based on packet header A switch at stage i looks at bit i in theheader010010059/22/06 CS/ECE 438 - UIUC, Fall 2006 25Banyan Network0010111101110010111101110010111101110010111101110010111101119/22/06 CS/ECE 438 - UIUC, Fall 2006 26Banyan Network Perfect Shuffle N inputs requires log2N stages of N/2 switchingelements Complexity on order of N log2N Collisions If two packets arrive at the same


View Full Document

U of I CS 438 - Switching Hardware

Documents in this Course
Routing

Routing

5 pages

TCP

TCP

26 pages

TROLL

TROLL

3 pages

Load more
Download Switching Hardware
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 Switching Hardware 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 Switching Hardware 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?