Unformatted text preview:

CS 636 InternetworkingCS 636 InternetworkingRamana KompellaROUTER ALGORITHMICSLecture 20: SwitchingSome slides courtesy of Nick McKeown1CS 636 Internetworking 2Generic Router ArchitectureLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryData HdrData HdrData Hdr12N 12NN times line rateN times line rateRouter evolution: bus to crossbar Bus, shared CPUCS 636 Internetworking 3Router evolution: bus to crossbar Bus, shared CPUs Can lead to packet reorderingCS 636 Internetworking 4Router evolution: bus to crossbar Bus, per line card CPUsCS 636 Internetworking 5Router evolution: bus to crossbar Modern crossbar, per line card forwarding enginesCS 636 Internetworking 6CS 636 Internetworking 7InterconnectsTwo basic techniquesInput QueueingOutput QueueingUsually a non-blockingswitch fabric (e.g. crossbar)Usually a fast busCS 636 Internetworking 8InterconnectsOutput QueueingIndividual Output Queues Centralized Shared MemoryMemory b/w = (N+1).R12NMemory b/w = 2N.R12NCS 636 Internetworking 9Output QueueingThe “ideal”111111111111222222CS 636 Internetworking 10Output QueueingHow fast can we make centralized shared memory?SharedMemory200 byte bus5ns SRAM12N• 5ns per memory operation• Two memory operations per packet• Therefore, up to 160Gb/s• In practice, closer to 80Gb/sCS 636 Internetworking 11InterconnectsInput Queueing with CrossbarconfigurationData InData OutSchedulerMemory b/w = 2RTake-a-ticket scheduler Potential n-fold parallelism over single bus How to schedule, to avoid two inputs from using same output bus ?CS 636 Internetworking 12Gigaswitch architecture Each output maintains a queue for all inputs waiting to send Queue stored at inputs using a simple ticket mechanismCS 636 Internetworking 13Gigaswitch architecture Scales well requiring only two log N bit counters at each outputCS 636 Internetworking 14CS 636 Internetworking 15Head of Line BlockingCS 636 Internetworking 16CS 636 Internetworking 17CS 636 Internetworking 18Input QueueingHead of Line BlockingDelayLoad58.6%100%Karol’s result Assume each packet destined to each output with probability 1/N Equal size packets, probability that an output O is idle is probability that none of the inputs choose O Each input does not choose O with probability 1 – 1/N. P (O idle) = (1-1/N)N◦ Converges to (1-1/e) ~ 0.63 Careful analysis by Karol shows throughput ~ 0.58CS 636 Internetworking 19CS 636 Internetworking 20Input QueueingVirtual output queuesCS 636 Internetworking 21Input QueuesVirtual Output QueuesDelayLoad100%CS 636 Internetworking 22Input QueueingSchedulerMemory b/w = 2RCan be quitecomplex!Next lecture Scheduling in input queued switch fabrics◦ Parallel iterative matching◦ iSlip◦ ..CS 636 Internetworking 23Shared memory switches Operation◦ Packets read into memory from input links◦ Read out of memory to appropriate output links. Problem: memory bandwidth does not scale well◦ With 8 input and 8 need memory 16 times faster than link speeds. Use wide memory access width. ◦ Bits come in serially, accumulated into register, load cell into cell-wide.◦ Reverse process on output.  Datapath switch uses central memory of 4K cells on-chip, augmented with flow control and off-chip packet buffers.  But are memory and power optimal because data is only moved once. CS 636 Internetworking


View Full Document

Purdue CS 63600 - Switching

Download Switching
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 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 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?