CSD The Computer Science Department CSD

CSIT 560: Internet Infrastructure: Switches and Routers

Spring Semester 2009

Reading Material

　

Topic	Reading
General Background	o Pablo Molinero, Nick McKeown , "The performance of circuit switching in the Internet" OSA Journal of Optical Networking, Vol. 2, No. 4, March 2003 o V. Cerf and R. Kahn, A Protocol for Packet Network Interconnection, IEEE Transactions on Communications COM-22, 1974, pp. 637-648. o Clark, Design Philosophy of the DARPA Internet Protocols , In Proc. ACM SIGCOMM , Stanford, CA, August 1988, pp. 106-114. o S. Shenker, Fundamental Design Issues for the Future Internet , IEEE Journal on Selected Areas in Communications, Vol. 13, No. 7, September 1995, pp. 1176-1188. o David D. Clark and Marjory S. Blumenthal. Rethinking the design of the Internet: The end to end arguments vs. the brave new world. Workshop on Policy Implications of End-to-End. December 1, 2000. o X. Xiao and L. M. Ni, "Internet QoS: A Big Picture", IEEE Network Mag., Mar./Apr. 1999 o S. Keshav and R. Sharma, Issues and Trends in Router Design, IEEE Comm. Mag., May 1998 o H. J. Chao, Next Generation Routers,IEEE proceeding, 2002
Router Design	o N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick and M. Horowitz, The Tiny Tera: A Packet Switch Core , Proc. Hot Interconnects V, Stanford University, August 1996. o Nick Mckeown, "Fast Switched Backplane for a Gigabit Switched Router," Cisco White Paper. o S. Keshav and R. Sharma, Issues and Trends in Router Design, IEEE Communications Magazine, Vol. 36, No. 5, May 1998, pp. 144-151. o J. Aweya, "IP Router Architecture: An Overview," Nortel White paper. o Marco Ajmone Marsan, Andrea Bianco, Paolo Giaccone, Emilio Leonardi, Fabio Neri, Input-queued router architectures exploiting cell-based switching fabrics, Computer Networks, Vol.37, No.5, pp.541-559, November, 2001. o "Matching Output Queueing with a Combined Input Output Queued Switch," Shang-Tse Chuang, Ashish Goel, Nick McKeown, Balaji Prabhakar, Computer Systems Technical Report CSL-TR-98-758. March 1998. o "Routers with a Single Stage of Buffering," Sundar Iyer, Rui Zhang, Nick McKeown, ACM SIGCOMM, Pittsburgh, USA, Sep. 2002. Computer Communication Review, vol. 32, no. 4, Oct 2002. o "Analysis of the Parallel Packet Switch Architecture," Sundar Iyer and Nick McKeown, IEEE/ACM Transactions on Networking, April 2003. o Nick McKeown,"Optics inside Routers", ECOC 2003, Rimini, Italy, September 2003. o Isaac Keslassy, Shang-Tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, “Scaling Internet Routers Using Optics”, ACM SIGCOMM Aug. 2003, Karlsruhe, Germany.
VOQ Switch Scheduling	o N. Mckeown, iSLIP: A Scheduling Algorithm for Input-Queued Switches, IEEE Transactions on Networking, Vol 7, No.2, April 1999. o N. Mckeown, A. Mekkittikul, V. Anantharam, and J. Walrand,"Achieving 100% throughput in an input-queued switch," IEEE Transactions on Communications, Aug. 1999, Page(s): 1260 -1267. o P. Gupta and N. Mckeown, "Designing and implementing a fast crossbar scheduler," IEEE Micro , Jan.-Feb. 1999, Page(s): 20 -28. o Y. Jiang and M. Hamdi, "A fully desynchronized round-robin matching scheduler for a VOQ packet switch architecture ," 2001 IEEE Workshop on High Performance Switching and Routing , 2001, Page(s): 407 -411. o Paolo Giaccone, Balaji Prabhakar, Devavrat Shah, Towards Simple, High-Performance Schedulers for High-Aggregate Bandwidth Switches, IEEE INFOCOM 2002, New York, USA, June 2002. o Paolo Giaccone, Devavrat Shah, Balaji Prabhakar, An Implementable Parallel Scheduler for Input-Queued Switches, Hot Interconnects 9, Stanford, CA, USA, August 2001. o D. Serpanos and P. Antoniadis, "FIRM: A Class of Distributed Scheduling Algorithms for High-Speed ATM Switches with Multiple Input Queues," IEEE INFOCOM 2000. o T. Anderson, S. Owicki, J. Saxe, and C. Thacker, "High-speed switch scheduling for local-area networks," ACM TOCS, Nov. 1994, Pages: 319 - 352. o M. Marsan, A. Bianco, E. Leonardi, and L. Milia, "RPA: a flexible scheduling algorithm for input buffered switches," IEEE Transactions on Communications, Volume: 47 Issue: 12 , Dec. 1999, Page(s): 1921 -1933. o Cheng-Shang Chang, Duan-Shin Lee and Yi-Shean Jou, "Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering" to appear in the special issue of Computer Communications on ``Current Issues in Terabit Switching,'' 2001. o Cheng-Shang Chang, Duan-Shin Lee and Ching-Ming Lien, "Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering" to appear in the special issue of Computer Communications on ``Current Issues in Terabit Switching,'' 2001. o Cheng-Shang Chang, Wen-Jyh Chen and Hsiang-Yi Huang, "Birkhoff-von Neumann input buffered crossbar switches for Guaranteed-Rate Services," IEEE Transactions on Communications, Vol. 49, pp. 1145-1147, July 2001. o I. Keslassy and N. Mckeown, "Analysis of scheduling algorithms that provide 100% throughput in input-queued switches", Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing. Monticello, Illinois, October 2001. o "High-Speed Switch Scheduling for Local-Area Networks," T. Anderson, S. Owicki, J. Saxe, and C. Thacker, ACM Transactions on Computer Systems, II (4):319-352, November 1993. o "Symmetric Crossbar Arbiters for VLSI Communication Switches," Y. Tamir and H.-C. Chi, IEEE Transactions on Parallel and Distributed Systems, 4(j):13-27, 1993. o "Switch Scheduling via Edge coloring,"G. Aggarwal, R. Motwani, D. Shah, and A. Zhu,Proceeding of IEEE Foundations of Computer Science (FOCS), Boston, USA, October 2003. o Mingjie Lin, Nick McKeown, "The Throughput of a Buffered Crossbar Switch", IEEE Communications Letters 2004. o N. Chrysos, M. Katevenis, “Weighted Fairness in Buffered Crossbar Scheduling,” Proceedings of the IEEE Workshop on High Performance Switching and Routing, Torino, Italy, pp. 17–22, June 2003. o Paolo Giaccone, Balaji Prabhakar, Devavrat Shah, “Randomized scheduling algorithms for high-aggregate bandwidth switches,” IEEE Journal on Selected Areas in Communications, High-performance electronic switches/routers for high-speed internet", Vol.21, No.4, pp.546-559, ISSN: 0733-8716 , May 2003
VOQ/CIOQ QoS Guarantees	o Isaac Keslassy and Nick McKeown, "Maintaining Packet Order in Two-Stage Switches", Proceedings of IEEE INFOCOM '02, New York, June 2002. o Shang-Tse Chuang, Sundar Iyer, Nick McKeown, "Practical Algorithms for Performance Guarantees in Buffered Crossbars”, Proceedings of IEEE INFOCOM 2005, Miami, Florida, March 2005. o S. T. Chuang, A. Goel, N. Mckeown, and B. Prabhakar, "Matching output queueing with a combined input/output-queued switch,'' IEEE Journal on Selected Areas in Communications , June 1999, Page(s): 1030 -1039. o G. Nong and M. Hamdi, "On the provision of quality-of-service guarantees for input queued switches,"IEEE Communications Magazine , Volume: 38 Issue: 12 , Dec. 2000, Page(s): 62 -69. o A. C. Kam and K. Y. Siu, "Linear-complexity algorithms for QoS support in input-queued switches with no speedup," IEEE JSAC, June 1999, pp. 1040 -1056. o P. Krishna, N. Patel, A. Charny, R. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE JSAC, June 1999, pp. 1057 -1066. o E. Leonardi, M. Mellia, F. Neri, and M. Marsan, "On the stability of input-queued switches with speed-up," IEEE/ACM Transactions on Networking , Volume: 9 Issue: 1 , Feb 2001, Page(s): 104 -118
Memory Issues	o Neda Beheshti, Yashar Ganjali, Monia Ghobadi, Nick McKeown, and Geoff Salmon , "Experimental Study of Router Buffer Sizing", IMC'08, October 2008, Vouliagmeni, Greece. o Designing Buffers for Router Line Cards, Sundar Iyer, R. R. Kompella, and Nick McKeown, IEEE TON, 2002. o Sizing Router Buffers, Guido Appenzeller, Isaac Keslassy, Nick McKeown, SIGCOMM 2004 o Neda Beheshti, Yashar Ganjali, Ramesh Rajaduray, Daniel Blumenthal, and Nick McKeown, "Buffer sizing in all-optical packet switches", In Proceedings of OFC/NFOEC, Anaheim, CA, March 2006. o Neda Beheshti, Yashar Ganjali, Jad Naous, and Nick McKeown, "Experimenting with Buffer Sizing in Routers", ANCS'07, December 2007, Orlando, Florida, USA. o Neda Beheshti, Yashar Ganjali, Ashish Goel, Nick McKeown ,"Obtaining High Throughput Networks with Tiny Buffers", In Proceedings of 16th International Workshop on Quality of Service (IWQoS), Enschede, Netherlands, June 2008.
Table Lookup and Packet Classification	o A. Brodnik, S. Carlsson, M. Degermark, and S. Pink, Small Forwarding Tables for Fast Routing Lookups , Proc. ACM SIGCOMM , Cannes, France, September 1997 . o P. Gupta and N. Mckeown, "Classifying packets with hierarchical intelligent cuttings,'' IEEE Micro , Volume: 20 Issue: 1 , Jan.-Feb. 2000, Page(s): 34 -41 o P. Gupta and N. Mckeown, "Algorithms for Packet Classification," IEEE Network, March 2001. o F. Baboescu and G. Varghese, "Scalable Packet Classification", In Proceedings of ACM SIGCOMM 2001, San Diego, CA, August 2001. o "Routing Lookups in Hardware at Memory Access Speeds" ,Pankaj Gupta, Steven Lin, and Nick McKeown ,IEEE INFOCOM April 1998, Vol 3, pp. 1240-1247, San Francisco. o "Algorithms for Packet Classification" , Pankaj Gupta and Nick McKeown , IEEE Network, March 2001. o M. A. Ruiz-Sanchez, E. W. Biersack and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms”, IEEE Network, pp.8-23, March/April 2001.
Queue Management and Scheduling	o S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance , IEEE/ACM Transactions on Networking , Vol. 1, No. 4, August 1993, pp. 397-413. o I. Stoica , S. Shenker , and H. Zhang , Core -Stateless Fair Queueing: Achieving Approximately Fair Allocations in High Speed Networks , Proc. ACM SIGCOMM , Vancouver, Canada, September 1998. o "Analysis and Simulation of a Fair Queueing Algorithm," A. Demers, S. Keshav, and S. Shenker, Proceedings of the ACM Sigcomm '89 and Computer Communications Review 19(4):1-12, 1989. o "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single Node Case," A. Parekh and R. Gallager, IEEE/ACM Transactions on Networking, 1(3):344-357, June 1993. o "Efficient Fair Queueing Using Deficit Round-Robin," M. Shreedhar and G.Varghese, Proceedings of the ACM Sigcomm '95 and IEEE/ACM Transactions on Networking 4(3):375-385, June 1996. o K. Avrachenkov, U. Ayesta, P. Brown, and E. Nyberg, “Differentiation between short and long TCP flows: predictability of the response time,” in Proc. IEEE INFOCOM, March 2004. o A. Rai, E. W. Biersack, and G. Urvoy-Keller, “Size-based scheduling to improve the performance of short TCP flows,” IEEE Network, January/February 2005.
Quality of Service and Differentiated Services	o Rui Zhang-Shen, Nick McKeown , "Guaranteeing Quality of Service to Peering Traffic", Proceedings of IEEE INFOCOM 2008, Phoenix, AZ, April 2008. o C. Dovrolis and P. Ramanathan, "A Case for Relative Differentiated Services and the Proportional Differentiation Model", IEEE Network Mag., Sept./Oct. 1999 o D. D. Clark and W. Fang, "Explicit Allocation of Best Effort Packet Delivery Service", IEEE/ACM Trans. Net., Aug. 1998. o R. Guerin and V. Peris, "Quality-of-Service in Packet Networks: Basic Mechanisms and Directions", Computer Networks 31 (1999) 169-189. o I. Stoica and H. Zhang, "Providing Guaranteed Service Without Per Flow Management", SIGCOMM'99. o C. Dovrolis, D. Stiliadis and P. Ramanathan, "Proportional Differentiated Services: Delay Differentiation and Packet Scheduling", SIGCOMM'99. o L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: A New Resource Reservation Protocol". IEEE Communications Magazine, 31(9):8-18, September 1993. o "On the Speedup Required for Combined Input and Output Queued Switching," Balaji Prabhakar and Nick McKeown, Computer Systems Technical Report CSL-TR-97-738. November 1997. o "The Throughput of Data Switches with and without Speedup," J.G. Dai and B. Prabhakr, Proceedings of the IEEE INFOCOM, 2:556-564, Tel Aviv, Israel, March 2000 o Gozdecki. J, Jajszczyk. A, Stankiewicz. R, "Quality of service terminology in IP networks", IEEE Communications Magazine, 41(3): 153- 159, March 2003. o Ian Foster, Markus Fidler, Alain Roy, Volker Sander and Linda Winkler, “End-to-end quality of service for high-end applications”, Computer Communications, 27(14):1375-1388, September 2004.
Burst Switching	o Baldine. I and el, " Jump Start: a just-in-time signaling architecture for WDM burst-switched networks", IEEE Communications Magazine, 40(2):82-89, Feb 2002. o C. Qiao "Optical Burst Switching (OBS) - A New Paradigm for an Optical Internet", in a special issue of J. High Speed Networks (JHSN) on WDM Networks, Vol. 8, No. 1, pp. 69-84. o Yijun Xiong and el, “Control architecture in optical burst-switched WDM networks”, EEE Journal on Communications, 18(10): 1838- 1851, Oct 2000. o Lisong Xu and el, "Techniques for optical packet switching and optical burst switching", IEEE Communications Magazine, 39(1):136-142, Jan 2001.
High scalable switches	o "Scaling Internet Routers Using Optics", Isaac Keslassy, Shang-Tse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, Nick McKeown, ACM SIGCOMM Aug. 2003, Karlsruhe, Germany. o Feng Wang and Mounir Hamdi, "Analysis on the Central-stage Buffered Clos-network for packet switches", IEEE International Conference on Communications (ICC'05), in Korea, May 2005
Load balancing switches	o Rui Zhang-Shen, Nick McKeown,"Designing a Fault-Tolerant Network Using Valiant Load-Balancing”, Proceedings of IEEE INFOCOM 2008, Phoenix, AZ, April 2008. o Cheng-Shang Chang, Duan-Shin Lee and Yi-Shean Jou, "Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering" to appear in the special issue of Computer Communications on ``Current Issues in Terabit Switching,'' 2001. o Cheng-Shang Chang, Duan-Shin Lee and Ching-Ming Lien, "Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering" to appear in the special issue of Computer Communications on ``Current Issues in Terabit Switching,'' 2001. o Load balancing with Memory, M. Mitzenmacher, B. Prabhakar, and D. Shah, in FOCS 2002. o A Load-Balanced Switch with an Arbitrary Number of Linecards, Isaac Keslassy, Shang-Tse Chuang, Nick McKeown ,Proceedings of IEEE Infocom '04, Hong Kong, March 2004 o Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, Duan-Shin Lee, "Optimal Load-Balancing", Proceedings of IEEE INFOCOM 2005, Miami, Florida, March 2005. o Rui Zhang-Shen, Nick McKeown, "Designing a Predictable Internet Backbone with Valiant Load-Balancing”, Thirteenth International Workshop on Quality of Service (IWQoS), Passau, Germany, June 2005.

Back to CSIT 560 Home Page