Name
Title | ||
|---|---|---|
Randomized parallel schedulers for switch-memory-switch routers: analysis and numerical studies |
Abstract | ||
|---|---|---|
We present new results and numerical studies of very fast schedulers for SMS (Switch-Memory-Switch) routers, which emulate output-queuing by buffering packets in a parti- tioned shared-memory located between input and output ports. The architecture of Juniper's core routers and Brocade's storage switches is based on SMS. Our numerical results demonstrate that RiPSS, a randomized highly parallel SMS scheduler that we had developed recently, runs in just 3 rounds on switches with up to 4,096 inputs, and has a very low drop probability. We also show that RiPSS makes effective use of the shared-memory, with packets being uniformly distributed across the memory banks for both Bernoulli and bursty arrivals. We describe a new and improved randomized pipelined scheduler, PRiPSS, and analyze its performance. Both our analysis and our simulation results for PRiPSS show that it has better throughput than RiPSS with a slightly higher latency in terms of rounds of communication in the underlying hardware. Our analysis also shows that PRiPSS is self-stabilizing, i.e., if occasional lapses occur due to the probabilistic nature of the algorithm, it resumes normal behavior without the need for external intervention. While the choice of RiPSS or PRiPSS would depend on whether throughput or latency is the primary concern, our results indicate that both schedulers are much faster than other schedulers for output-queuing, whether implemented directly or through emulation on SMS. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/INFCOM.2004.1354611 | INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies |
Keywords | Field | DocType |
packet switching,parallel architectures,probability,queueing theory,scheduling,telecommunication network routing,Bernoulli-bursty arrival,Brocade storage switch,Juniper core router architecture,buffering packet,drop probability,output-queuing,packet distribution,probabilistic algorithm,randomized parallel scheduler,randomized pipelined scheduler,shared-memory location,switch-memory-switch router | Randomized algorithm,Scheduling (computing),Computer science,Latency (engineering),Network packet,Computer network,Input/output,Queueing theory,Packet switching,Throughput,Distributed computing | Conference |
Volume | ISSN | ISBN |
3 | 0743-166X | 0-7803-8355-9 |
Citations | PageRank | References |
17 | 0.86 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amit Prakash | 1 | 50 | 5.97 |
| Adnan Aziz | 2 | 1778 | 149.76 |
| Vijaya Ramachandran | 3 | 17 | 0.86 |