article

Free access

The iSLIP scheduling algorithm for input-queued switches

Editor: Simon S. Lam Author:

Nick McKeownAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 7, Issue 2

Pages 188 - 201

https://doi.org/10.1109/90.769767

Published: 01 April 1999 Publication History

PDF eReader

References

[1]

M. Ali and H. Nguyen, "A neural network implementation of an input access sclleme in a high-speed packct switch," in Proc. GLOBECOM "89. pp. 1192-1196.

Google Scholar

[2]

T. Anderson. S. Owicki, .I. Saxe. and C. Thacker, "'High speed switch scheduling for local area networks.'" ACM Trans. Comput. Svst., vol. I I. no. 4, pp. 319-352, Nov, 1993.

Crossref

Google Scholar

[3]

D. Anick, D. Mitra. and M. M. Sondhi, "'Stochastic theory of a datahandling syslem with multiple s~urces," Bell Svst. 7~c'h. J. vol. 61. pp. 1871-1894. 1982.

Google Scholar

[4]

"GRF Multigigabit Router," GRF IP Switch Tech. Product Description, Ascend Comnmnications, Wcstford. MA. IOnlinel. Available HTTP: http://www.ascend.com/230.html

Google Scholar

[5]

T. X. Brown and K. H. Liu. "'Neural network design of a Banyan network controller," IEEE,I. Sele~'t. Areas Commun., vol. 8, pp. 1289-1298, Oct. 1990.

Google Scholar

[6]

"Performing lnternet Routing and Switching at Gig,'tbit Speeds." GSR 12000 l'ech. Product Description, Cisco Systems, San Jose, CA. tOn.- line}. Available HTTP: http://www.cisco.com/warp/public/733/12()()() /index.shtml

Google Scholar

[7]

Y. Rekhter, B. D:lvie. D. Katz, E. Rosen, and G. Swallow. (1997). "'Cisco systems" tag switching architecture overview'" Internct RFC 211),.'5. Cisco S)'stcms. San J~se, CA. {Online}. Available HTTP: htt p://inlb.internet.i si .edu/i n-notes/rfc/ti les/rfc2105 .txt

Crossref

Google Scholar

[8]

M. Chcn and N. D. Georganas, "'A fast algorithm for multi-channel/port traffic scl:eduling" in Proc. IElz,'E Stq~elz'om/ICC '94, pp. 96--100.

Google Scholar

[9]

F. M. Chiussi and F. A. "l\-~bagi, "ln~plemcntation of a three-stage Banyan-based architecture with input and t~utput buffers for large I~lst packet switches," Stanford, CA, Stanford CSL Tcch. Rep. CSL-93-577, June 1993.

Crossref

Google Scholar

[10]

R. Cruz. "A calculus tbr network delay. Part I: Network elements in isolation," IEEE Trans. lt!}'orm. Theory, vol. 37, pp. 114--I 21, 199 I.

Crossref

Google Scholar

[11]

H. Heffes and D, M, Lucantoni. "A Markov modul,qted ch:~ractcrization of packctized voice and data traffic and related statistical multiplexer performance," IEEE J. Seh,ct. Areas Commlt/i., vo}. 4, pp. 856-868. 1988.

Google Scholar

[12]

J. E. Hol:croft and R. M. Karp. "'An algorithm for maximum matching in bipartite graphs." Soc. Ind. Appl. Math. J. Computation, vol. 2. pp. 225-231, 1973.

Google Scholar

[13]

A. Huan.o,: and S. Knauer. "Starlite" A wideband digital switch." in Proe. GLOBECOM '84, pp. 12 i-125.

Google Scholar

[14]

J. Hui and E. Arthurs, "A broadband packet switch for integrated transport," IEEE J. Select. Areas (_:otnmtt/i., vol. 5, pp. 1264-1273. Oct. 1987.

Google Scholar

[15]

R. Jain and S. A. Routhier, "'Packet trains: Measurements and a new model for computer network traflic,'" IEEE,l. Select. Areas Commtt/l., vol. 4, pp. 986-995, Apr. 1986.

Google Scholar

[16]

M. Karol, M. Hluchyj, and S. Morgan, "'Input versus output queueing on a space division switch," IEEE Trans. Commun. vol. 35, pp. 1347-1356, 1988.

Google Scholar

[17]

M. Karol and M. Hluchyj, "'Queueing in high-performance packetswitching," IEEE J. Select. Areas Commun., vol. 6, pp. 1587-1597, Dec. 1988.

Google Scholar

[18]

M. Karol, K. Eng, and H. Obara, "'Improving the performance of inputqucued ATM packet switches." in Prec. INFOCOM '92, pp. II0-115.

Crossref

Google Scholar

[19]

R. O. LaMaire and D. N. Serpanos, "'Two-dimensional round-robin schedulcls for packet switches with multiple input queues," {EEE/ACM Tlt'ttns. N.,tworking. vol. 1. pp. 471-482. Oct. 1993.

Crossref

Google Scholar

[20]

S. Low and P. Varaiya, "'Burstiness bounds for some burst reducing servers," in Proc. INFOCOM '93, pp. 2-9.

Google Scholar

[21]

G. Kesidis, J. Walrand. and C.-S. Chang, "'Effective bandwidths for multicla.,:s Markov fluids and other ATM sources," IEEk, TACM Trans. Networking, vol. 1. pp. 424-428, Aug. 1993.

Crossref

Google Scholar

[22]

W. E. Leland, W. Willinger. M. Taqqu, D. Wilson, "'On the self-similar nature of Ethernet traffic," in Proc. SIGCOMM, San Francisco, CA, pp. 183-193. Sept. 1993.

Crossref

Google Scholar

[23]

C. Lund, S. Phillips, and N. Reingold. "'Fair prioritized scheduling in an input-buffered switch." in Prec. IF'IPIEEE Cot!tl Broadband Commun. '96, Montreal, Canada. Apr. 1996. pp. 358-369.

Google Scholar

[24]

N. McKeown. "'Scheduling algorithms for input-queued cell switches." Ph.D. dissertation. Univ. Calil\wnia at Berkcley, 1995.

Crossref

Google Scholar

[25]

N. McKeown, V. Anantlmram, and J. Walrand, "'Achieving 100% throughput in an input-qucued switch," in l'roc. IEFE INFOCOM "96. San Francisco, CA, pp. 296-3()2.

Crossref

Google Scholar

[26]

N. McKcown, M. Izzard. A. Mekkittikul, B. Ellersick. and M. Horowitz, "'The tiny tera: A small high-bandwidth packet switch core,'" IEEE Micro, vol. 17, pp. 26-33, Jan.-Feb. 1997.

Crossref

Google Scholar

[27]

S. Chuang, A. Goel, N. McKeown. B. Prabhakar. "'Matching output queueing with a combined input output queued switch,"lEEE J. Select. Areas C:munun.," to be published.

Crossref

Google Scholar

[28]

A. Mekkittikul and N. McKeown. "'A practical scheduling algorithm for achieving 100% throughput in input-queued switches." in Pro~'. hYFOCOM "98, San Francisco, CA, vol. 2, pp. 792-799.

Google Scholar

[29]

P. Newman, G. Minshall, and T. Lyon, "'IP switching: ATM under I P'" IEEE/ACM Trans. Networking, vol. 6. pp. 117-129, Apr. 1998.

Crossref

Google Scholar

[30]

H. Obara. "'Optimum architecture for input queueing ATM switches," IEEE Eh,ctron. Let/., pp. 555-557, Mat'. 1991.

Google Scholar

[31]

C. Partridge et al. "'A lifty gigabit pcr second IP router." IEEE/ACM Trans. Networking. to be published.

Google Scholar

[32]

G. Pm'uikar, D. C. Schmidt, and J. S. Turner. "altPm: A strategy for 7 r (3r .. integ atin~, IP with ATM,'" in Prec. A CM SIGCOMM "95, Cambridue, MA, pp. 287-295.

Crossref

Google Scholar

[33]

Y. Tamir and H.-C. Chi, "Symmetric crossbar arbiters for VLSI communication switches," IEEE 7?'Ltn.v. Parallel I)Lvt. S~wt., vol. 4, pp. 13-27. 1993.

Crossref

Google Scholar

[34]

Y. Tarnir and G. Frazier, "'High perl-ormance multi-queue buffers for - VLSI comlnt, rtication switches," it} Ptv~.'. 15th Annu. Sym/~. (_'omput. Arch., June 198;g, pp. 343-354.

Crossref

Google Scholar

[35]

R. E. Taljan, "Data structures mid network aluwithms.'" in Soc. Ind. Appl. Mathentatics, PA. Nov. 1983.

Crossref

Google Scholar

[36]

T, P. Troudet and S. M. Waiters, "Hoplield neural network architecture fiw crossbar switch control "" IEEE Trtitts. Circuits Svst. vol. 38, pp. 42-57. Jan. 1991.

Google Scholar

[37]

C.-Y. Chang, A. J. Paulraj, and T. Kailath, "'A brotidb,'lnd packet switch architecture with input and output qt.eueing.'" in Pr+~" Gh~hec'~nn '94, pp. 448-452.

Google Scholar

[38]

I. llit~dis and W. E. Denzel, "Performance of packet switches with input and output queueing.'" in Proc. ICC '90, Atlanta. GA, Apt'. 1990. pp. 747-53.

Google Scholar

[39]

A. L. Gupta and N. D. Georganas. "Analysis of a packet switch with input and output btLt'l'ers and speed constraints," in Ptvm. INFOCOM "91. Bal Harbour, FL, pp. 694-700.

Google Scholar

[40]

Y. Oie. M. Murata. K. Kt,bot,'t, and H. Miyahanl. '\E ect of spcedup in nonblocking packet switch." in t"ro~' ICC '89, Boston. MA, June 1989, pp. 410---414.

Google Scholar

[41]

J. S.-C. Chen and T. E. Stern. "'Throttghput analysis, optimal buffer allocation, and traffic imbalance study ~ia generic nonblocking packet switch." lEEk, J. Sele+'t. Areas (_.'ommttn., vol. 9, pp. 439--449. Apt'. 1991.

Google Scholar

[42]

P. Gupta and N. McKeown. "'Designing and implementing a fast crossbar scheduler." IEEE Micro. vol. {9, pp. 20-28, Jan.-Feb. 1999.

Crossref

Google Scholar

Cited By

View all

Liang CSong XCheng JWang MLiu YLiu ZZhao SCui YSekar VYu MSeneviratne AVeitch D(2024)NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter NetworkProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672222(415-432)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672222
Biglari SHuang RZhao HMohanty S(2024)Designing Reconfigurable Interconnection Network of Heterogeneous Chiplets Using Kalman FilterProceedings of the Great Lakes Symposium on VLSI 202410.1145/3649476.3660389(663-668)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3649476.3660389
Gomez-Lopez Gde la Rosa MEscudero-Sahuquillo JGarcia PQuiles FLagadec P(2024)Hybrid Congestion Control for BXI-Based Interconnection NetworksEuro-Par 2024: Parallel Processing10.1007/978-3-031-69766-1_17(242-256)Online publication date: 26-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-69766-1_17
Show More Cited By

Index Terms

The iSLIP scheduling algorithm for input-queued switches
1. Networks
  1. Network protocols
    1. Link-layer protocols
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

FIFO-Based Multicast Scheduling Algorithm for Virtual Output Queued Packet Switches

Many networking/computing applications require high speed switching for multicast traffic at the switch/router level to save network bandwidth. However, existing queuing-based packet switches and scheduling algorithms cannot perform well under multicast ...
A logarithmic scheduling algorithm for high speed input-queued switches

Throughput of input queued switches using FIFOs is limited due to the Head of Line blocking (HoL) problem. Using VOQs at inputs and a proper scheduling algorithm, near 100% throughput can be achieved. Scaling in terms of number of ports and line rates ...
On tracking the behavior of an output-queued switch using an input-queued switch

We address the problem of fair scheduling of packets in Internet routers with input-queued (IQ) switches and unity speedup. Scheduling in IQ switches is formulated as tracking the behavior of an output-queued (OQ) switch that provides optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 7, Issue 2

April 1999

131 pages

ISSN:1063-6692

Editor:
Simon S. Lam
Univ. Texas, Austin

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 1999

Published in TON Volume 7, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

229
Total Citations
View Citations
2,507
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)7

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liang CSong XCheng JWang MLiu YLiu ZZhao SCui YSekar VYu MSeneviratne AVeitch D(2024)NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter NetworkProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672222(415-432)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672222
Biglari SHuang RZhao HMohanty S(2024)Designing Reconfigurable Interconnection Network of Heterogeneous Chiplets Using Kalman FilterProceedings of the Great Lakes Symposium on VLSI 202410.1145/3649476.3660389(663-668)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1145/3649476.3660389
Gomez-Lopez Gde la Rosa MEscudero-Sahuquillo JGarcia PQuiles FLagadec P(2024)Hybrid Congestion Control for BXI-Based Interconnection NetworksEuro-Par 2024: Parallel Processing10.1007/978-3-031-69766-1_17(242-256)Online publication date: 26-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-69766-1_17
Zhang YWang MMai YYu Z(2023)TensorCache: Reconstructing Memory Architecture With SRAM-Based In-Cache Computing for Efficient Tensor Computations in GPGPUsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.332674131:12(2030-2043)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TVLSI.2023.3326741
Papaphilippou PSano KAdhi BLuk W(2023)Experimental Survey of FPGA-Based Monolithic Switches and a Novel Queue BalancerIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.324458934:5(1621-1634)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3244589
Wang LGuan ZChen ZHu M(2023)sChain: An Efficient and Secure Solution for Improving Blockchain StorageIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.328548918(3662-3676)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3285489
Patronas GVlassopoulos NBellos PReisis D(2023)Accelerating the scheduling of the network resources of the next-generation optical data centersParallel Computing10.1016/j.parco.2022.102993115:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.parco.2022.102993
Sharma SKushwaha AAlizadeh MVarghese GGumaste A(2022)Tuneman: Customizing Networks to Guarantee Application Bandwidth and LatencyACM Transactions on Internet Technology10.1145/357565723:1(1-26)Online publication date: 9-Dec-2022
https://dl.acm.org/doi/10.1145/3575657
Agarwal RRajakrishnan SShmoys DMilani AWoelfel P(2022)From Switch Scheduling to Datacenter SchedulingProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538443(313-323)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538443
Li CDong DLiao X(2022)MUA-Router: Maximizing the Utility-of-Allocation for On-chip Pipelining RoutersACM Transactions on Architecture and Code Optimization10.1145/351902719:3(1-23)Online publication date: 4-May-2022
https://dl.acm.org/doi/10.1145/3519027
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

FIFO-Based Multicast Scheduling Algorithm for Virtual Output Queued Packet Switches

A logarithmic scheduling algorithm for high speed input-queued switches

On tracking the behavior of an output-queued switch using an input-queued switch

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations