CSDThe Computer Science DepartmentCSD

      COMP 680E: High-Speed Internet Switches and Routers

      Spring Semester 2007

    Reading Material


    กก

    Topic

    Reading
    General Background
    • V. Cerf and R. Kahn, A Protocol for Packet Network Interconnection, IEEE Transactions on Communications COM-22, 1974, pp. 637-648. 
    • Clark, Design Philosophy of the DARPA Internet Protocols , In Proc. ACM SIGCOMM , Stanford, CA, August 1988, pp. 106-114. 
    • 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. 
    • 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. 
    • X. Xiao and L. M. Ni, "Internet QoS: A Big Picture", IEEE Network Mag., Mar./Apr. 1999 
    • Issues and Trends in Router Design, S. Keshav and R. Sharma, IEEE Comm. Mag., May 1998
    • H. J. Chao, Next Generation Routers,IEEE proceeding, 2002
    Router Design
    • 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. 
    • Nick Mckeown, "Fast Switched Backplane for a Gigabit Switched Router," Cisco White Paper.
    • S. Keshav and R. Sharma, Issues and Trends in Router Design, IEEE Communications Magazine, Vol. 36, No. 5, May 1998, pp. 144-151. 
    • J. Aweya, "IP Router Architecture: An Overview," Nortel White paper.
    • 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.
    • "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.
    • "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.
    • "Analysis of the Parallel Packet Switch Architecture,"
      Sundar Iyer and Nick McKeown,
      IEEE/ACM Transactions on Networking, April 2003.
    VOQ Switch Scheduling
    • N. Mckeown, iSLIP: A Scheduling Algorithm for Input-Queued Switches, IEEE Transactions on Networking, Vol 7, No.2, April 1999.
    • 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.
    • P. Gupta and N. Mckeown, "Designing and implementing a fast crossbar scheduler," IEEE Micro  , Jan.-Feb. 1999, Page(s): 20 -28.
    • 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.
    • Paolo Giaccone, Balaji Prabhakar, Devavrat Shah, Towards Simple, High-Performance Schedulers for High-Aggregate Bandwidth Switches, IEEE INFOCOM 2002, New York, USA, June 2002.
    • Paolo Giaccone, Devavrat Shah, Balaji Prabhakar, An Implementable Parallel Scheduler for Input-Queued Switches, Hot Interconnects 9, Stanford, CA, USA, August 2001.
    • D. Serpanos and P. Antoniadis, "FIRM: A Class of Distributed Scheduling Algorithms for High-Speed ATM Switches with Multiple Input Queues,"
      IEEE INFOCOM 2000.
    • T. Anderson, S. Owicki, J. Saxe, and C. Thacker, "High-speed switch scheduling for local-area networks," ACM TOCS, Nov. 1994, Pages: 319 - 352.
    • 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.
    • 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. 
    • 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. 
    • 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. 
    • 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. 
    • "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.
    • "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.
    • "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.
    VOQ/CIOQ QoS Guarantees
    • 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.
    • 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.
    • 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.
    • P. Krishna, N. Patel, A. Charny, R. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE JSAC, June 1999, pp. 1057 -1066.
    • 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
    • Designing Buffers for Router Line Cards, Sundar Iyer, R. R. Kompella, and Nick McKeown, IEEE TON, 2002.
    • Sizing Router Buffers, Guido Appenzeller, Isaac Keslassy, Nick McKeown, SIGCOMM 2004
    Table Lookup and Packet Classification
    • A. Brodnik, S. Carlsson, M. Degermark, and S. Pink, Small Forwarding Tables for Fast Routing Lookups , Proc. ACM SIGCOMM , Cannes, France, September 1997 . 
    • F. Baboescu and G. Varghese, Scalable Packet Classification , Proc. ACM SIGCOMM , San Diego, CA, August 2001. 
    • P. Gupta and N. Mckeown, "Classifying packets with hierarchical intelligent cuttings,'' IEEE Micro , Volume: 20 Issue: 1 , Jan.-Feb. 2000, Page(s): 34 -41
    • P. Gupta and N. Mckeown, "Algorithms for Packet Classification," IEEE Network, March 2001.
    • F. Baboescu and G. Varghese, "Scalable Packet Classification", In Proceedings of ACM SIGCOMM 2001, San Diego, CA, August 2001. 
    • "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.
    • "Algorithms for Packet Classification"
      Pankaj Gupta and Nick McKeown
      IEEE Network, March 2001.
    Queue Management and Scheduling
    • 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. 
    •  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. 
    • M. A. Sanchez, E. W. Biersack, and W. Dabbous, "Survey and Taxonomy of IP Address Lookup Algorithms," IEEE Network Magazine, 15(2):8--23, March/April 2001.
    • "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.
    • "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.
    • "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.
    Quality of Service and Differentiated Services
    • C. Dovrolis and P. Ramanathan, "A Case for Relative Differentiated Services and the Proportional Differentiation Model", IEEE Network Mag., Sept./Oct. 1999 
    • D. D. Clark and W. Fang, "Explicit Allocation of Best Effort Packet Delivery Service", IEEE/ACM Trans. Net., Aug. 1998.
    • R. Guerin and V. Peris, "Quality-of-Service in Packet Networks: Basic Mechanisms and Directions", Computer Networks 31 (1999) 169-189.
    • I. Stoica and H. Zhang, "Providing Guaranteed Service Without Per Flow Management", SIGCOMM'99.
    • C. Dovrolis, D. Stiliadis and P. Ramanathan, "Proportional Differentiated Services: Delay Differentiation and Packet Scheduling", SIGCOMM'99.
    • 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. 
    • "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.
    • "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
    Burst Switching
    • 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. 
    High scalable switches
    • "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.
    • 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
    • Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering, C. S. Chang, et al., Computer Comm., Oct, 2001
    • Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering, C. S. Chang, et al., Computer Comm. Oct, 2001
    • Load balancing with Memory,
      M. Mitzenmacher, B. Prabhakar, and D. Shah,       in FOCS 2002.
    • 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

    Back to COMP680E Home Page