Nick McKeown
- 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. 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.htmlGoogle 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.shtmlGoogle 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 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Google Scholar
- 35 R. E. Taljan, "Data structures mid network aluwithms.'" in Soc. Ind. Appl. Mathentatics, PA. Nov. 1983. 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. Google Scholar
Index Terms
- The iSLIP scheduling algorithm for input-queued switches
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