PREFACE As increasing voice,audio,video,TV,and gaming traffic is carried over IP,Internet traffic continues to grow rapidly.Many network-related applications are emerging for portable devices.As smart cellular phone technology advances,the price decreases,and the infras tructure to support wireless applications(voice,data,video)is being deployed ubiquitously to meet unprecedented demands from users.All of these fast-growing services translate into the high volume of Internet traffic,stringent quality of service(QoS)requirements,large number of hosts/devices to be supported,large forwarding tables to support,high speed packet processing,and large storage capability.When designing/operating next genera- tion switches and routers,these factors create new specifications and new challenges for equipment vendors and network providers. Jonathan has co-authored two books:Broadband Packet Switching Technologies-A Practical Guide to ATM Switches and IP Routers and Quality of Service Control in High- Speed Networks,published by John Wiley in 2001.Because the technologies in both electronics and optics have significantly advanced and because the design specifications for routers have become more demanding and challenging,it is time to write another book This book includes new architectures,algorithms,and implementations developed since 2001.Thus,it is more updated and more complete than the two previous books. In addition to the need for high-speed and high-capacity transmission/switching equip- ment,the control function of the equipment and network has also become more sophisticated in order to support new features and requirements of the Internet,including fast re-routing due to link failure (one or more failures),network security,network measurement for dynamic routing,and easy management.This book focuses on the subsystems and devices on the data plane.There is a brief introduction to IP network management to familiarize readers with how the network is managed,as many routers are interconnected together. The book starts with an introduction to today's and tomorrow's networks,the router architectures and their building blocks,examples of commercial high-end routers,and the challenging issues of designing high-performance high-speed routers.The book first covers the main functions in the line cards of a core router,including route lookup,packet classification,and traffic management for QoS control described in Chapters 2,3,and XV
Book1099 — “fpref” — 2007/2/16 — 21:26 — page xv — #1 PREFACE As increasing voice, audio, video, TV, and gaming traffic is carried over IP, Internet traffic continues to grow rapidly. Many network-related applications are emerging for portable devices. As smart cellular phone technology advances, the price decreases, and the infrastructure to support wireless applications (voice, data, video) is being deployed ubiquitously to meet unprecedented demands from users. All of these fast-growing services translate into the high volume of Internet traffic, stringent quality of service (QoS) requirements, large number of hosts/devices to be supported, large forwarding tables to support, high speed packet processing, and large storage capability. When designing/operating next generation switches and routers, these factors create new specifications and new challenges for equipment vendors and network providers. Jonathan has co-authored two books: Broadband Packet Switching Technologies—A Practical Guide to ATM Switches and IP Routers and Quality of Service Control in HighSpeed Networks, published by John Wiley in 2001. Because the technologies in both electronics and optics have significantly advanced and because the design specifications for routers have become more demanding and challenging, it is time to write another book. This book includes new architectures, algorithms, and implementations developed since 2001. Thus, it is more updated and more complete than the two previous books. In addition to the need for high-speed and high-capacity transmission/switching equipment, the control function of the equipment and network has also become more sophisticated in order to support new features and requirements of the Internet, including fast re-routing due to link failure (one or more failures), network security, network measurement for dynamic routing, and easy management. This book focuses on the subsystems and devices on the data plane. There is a brief introduction to IP network management to familiarize readers with how the network is managed, as many routers are interconnected together. The book starts with an introduction to today’s and tomorrow’s networks, the router architectures and their building blocks, examples of commercial high-end routers, and the challenging issues of designing high-performance high-speed routers. The book first covers the main functions in the line cards of a core router, including route lookup, packet classification, and traffic management for QoS control described in Chapters 2, 3, and xv
xvi PREFACE 4,respectively.It then follows with 11 chapters in packet switching designs,covering various architectures,algorithms,and technologies(including electrical and optical packet switching).The last chapter of the book presents the state-of-the-art commercial chipsets used to build the routers.This is one of the important features in this book-showing readers the architecture and functions of practical chipsets to reinforce the theories and conceptual designs covered in previous chapters. A distinction of this book is that we provide as many figures as possible to explain the concepts.Readers are encouraged to first scan through the figures and try to understand them before reading the text.If fully understood,readers can skip to the text to save time. However,the text is written in such a way as to talk the readers through the figures. Jonathan and Bin each have about 20 years of experience researching high-performance switches and routers,implementing them in various systems with VLSI(very-large-scale integration)and FPGA(field-programmable gate array)chips,transferring technology to the industry,and teaching such subjects in the college and to the industry companies.They have accumulated their practical experience in writing this book.The book includes theoretical concepts and algorithms,design architectures,and actual implementations.It will benefit the readers in different aspects of building a high-performance switch/router.The draft of the book has been used as a text for the past two years when teaching senior undergraduate and first-year graduate students at the author's universities.If any errors are found,please send an email to chao@poly.edu.The authors will then make the corresponding corrections in future editions. Audience This book is an appropriate text for senior and graduate students in Electrical Engineering, Computer Engineering,and Computer Science.They can embrace the technology of the Internet so as to better position themselves when they graduate and look for jobs in the high- speed networking field.This book can also be used as a reference for people working in the Internet-related area.Engineers from network equipment vendors and service providers can also benefit from the book by understanding the key concepts of packet switching systems and the key techniques of building high-speed and high-performance routers
Book1099 — “fpref” — 2007/2/16 — 21:26 — page xvi — #2 xvi PREFACE 4, respectively. It then follows with 11 chapters in packet switching designs, covering various architectures, algorithms, and technologies (including electrical and optical packet switching). The last chapter of the book presents the state-of-the-art commercial chipsets used to build the routers. This is one of the important features in this book—showing readers the architecture and functions of practical chipsets to reinforce the theories and conceptual designs covered in previous chapters. A distinction of this book is that we provide as many figures as possible to explain the concepts. Readers are encouraged to first scan through the figures and try to understand them before reading the text. If fully understood, readers can skip to the text to save time. However, the text is written in such a way as to talk the readers through the figures. Jonathan and Bin each have about 20 years of experience researching high-performance switches and routers, implementing them in various systems with VLSI (very-large-scale integration) and FPGA (field-programmable gate array) chips, transferring technology to the industry, and teaching such subjects in the college and to the industry companies. They have accumulated their practical experience in writing this book. The book includes theoretical concepts and algorithms, design architectures, and actual implementations. It will benefit the readers in different aspects of building a high-performance switch/router. The draft of the book has been used as a text for the past two years when teaching senior undergraduate and first-year graduate students at the author’s universities. If any errors are found, please send an email to chao@poly.edu. The authors will then make the corresponding corrections in future editions. Audience This book is an appropriate text for senior and graduate students in Electrical Engineering, Computer Engineering, and Computer Science. They can embrace the technology of the Internet so as to better position themselves when they graduate and look for jobs in the highspeed networking field. This book can also be used as a reference for people working in the Internet-related area. Engineers from network equipment vendors and service providers can also benefit from the book by understanding the key concepts of packet switching systems and the key techniques of building high-speed and high-performance routers
ACKNOWLEDGMENTS This book would not have been published without the help of many people.We would like to thank them for their efforts in improving the quality of the book. Several chapters of the book are based on research work that was done at Polytechnic University and Tsinghua University.We would like to thank several individuals who con- tributed material to some sections.They are Professor Ming Yu(Florida State University)on Section 1.5,Professor Derek C.W.Pao(City University of Hong Kong)on Section 2.4.2, and Professor Aleksandra Smiljanic(Belgrade University)on a scheduling scheme she proposed in Chapter 7.We would like to express our gratitude to Dr.Yihan Li (Auburn University)for her contribution to part of Chapter 7,and the students in Bin's research group in Tsinghua University for their contribution to some chapters.They are Chenchen Hu,Kai Zheng,Zhen Liu,Lei Shi,Xuefei Chen,Xin Zhang,Yang Xu,Wenjie Li,and Wei Li.The manuscript has been managed from the beginning to the end by Mr Jian Li (Polytechnic University),who has put in tremendous effort to carefully edit the manuscript and serve as a coordinator with the publisher. The manuscript draft was reviewed by the following people and we would like to thank them for their valuable feedback:Professor Cristina Lopez Bravo(University of Vigo,Spain),Dr Hiroaki Harai (Institute of Information and Communications Technol- ogy,Japan),Dr Simin He(Chinese Academy of Sciences),Professor Hao Che(University of Texas at Arlington),Professor Xiaohong Jiang (Tohoku University,Japan),Dr Yihan Li (Auburn University),Professor Dr Soung Yue Liew(Universiti Tunku Abdul Rahman, Malaysia),Dr Jan van Lunteren(IBM,Zurich),Professor Jinsoo Park(Essex County Col- lege,New Jersey),Professor Roberto Rojas-cessa (New Jersey Institute of Technology), Professor Aleksandra Smiljanic (Belgrade University,Serbia and Montenegro),Professor Dapeng Wu(University of Florida),and Professor Naoaki Yamanaka(Keio University, Japan). xvii
Book1099 — “flast” — 2007/2/16 — 21:25 — page xvii — #1 ACKNOWLEDGMENTS This book would not have been published without the help of many people. We would like to thank them for their efforts in improving the quality of the book. Several chapters of the book are based on research work that was done at Polytechnic University and Tsinghua University. We would like to thank several individuals who contributed material to some sections. They are Professor MingYu (Florida State University) on Section 1.5, Professor Derek C. W. Pao (City University of Hong Kong) on Section 2.4.2, and Professor Aleksandra Smiljanic (Belgrade University) on a scheduling scheme she proposed in Chapter 7. We would like to express our gratitude to Dr. Yihan Li (Auburn University) for her contribution to part of Chapter 7, and the students in Bin’s research group in Tsinghua University for their contribution to some chapters. They are Chenchen Hu, Kai Zheng, Zhen Liu, Lei Shi, Xuefei Chen, Xin Zhang, Yang Xu, Wenjie Li, and Wei Li. The manuscript has been managed from the beginning to the end by Mr Jian Li (Polytechnic University), who has put in tremendous effort to carefully edit the manuscript and serve as a coordinator with the publisher. The manuscript draft was reviewed by the following people and we would like to thank them for their valuable feedback: Professor Cristina López Bravo (University of Vigo, Spain), Dr Hiroaki Harai (Institute of Information and Communications Technology, Japan), Dr Simin He (Chinese Academy of Sciences), Professor Hao Che (University of Texas at Arlington), Professor Xiaohong Jiang (Tohoku University, Japan), Dr Yihan Li (Auburn University), Professor Dr Soung Yue Liew (Universiti Tunku Abdul Rahman, Malaysia), Dr Jan van Lunteren (IBM, Zurich), Professor Jinsoo Park (Essex County College, New Jersey), Professor Roberto Rojas-cessa (New Jersey Institute of Technology), Professor Aleksandra Smiljanic (Belgrade University, Serbia and Montenegro), Professor Dapeng Wu (University of Florida), and Professor Naoaki Yamanaka (Keio University, Japan). xvii
xviii ACKNOWLEDGMENTS Jonathan would like to thank his wife,Ammie,and his children,Jessica,Roger,and Joshua,for their love,support,encouragement,patience,and perseverance.He also thanks his parents for their encouragement. Bin would like to thank his wife,Yingjun Ma,and his daughter,Jenny for their under- standing and support.He also thanks his father-in-law for looking after Jenny to spare his time to prepare the book
Book1099 — “flast” — 2007/2/16 — 21:25 — page xviii — #2 xviii ACKNOWLEDGMENTS Jonathan would like to thank his wife, Ammie, and his children, Jessica, Roger, and Joshua, for their love, support, encouragement, patience, and perseverance. He also thanks his parents for their encouragement. Bin would like to thank his wife, Yingjun Ma, and his daughter, Jenny for their understanding and support. He also thanks his father-in-law for looking after Jenny to spare his time to prepare the book
CHAPTER 1 INTRODUCTION The Internet,with its robust and reliable Internet Protocol (IP),is widely considered the most reachable platform for the current and next generation information infrastructure. The virtually unlimited bandwidth of optical fiber has tremendously increased the data transmission speed over the past decade.Availability of unlimited bandwidth has stimulated high-demand multimedia services such as distance learning,music and video download, and videoconferencing.Current broadband access technologies,such as digital subscriber lines(DSLs)and cable television(CATV),are providing affordable broadband connection solutions to the Internet from home.Furthermore,with Gigabit Ethernet access over dark fiber to the enterprise on its way,access speeds are expected to largely increase.It is clear that the deployment of these broadband access technologies will result in a high demand for large Internet bandwidth.To keep pace with the Internet traffic growth,researchers are continually exploring faster transmission and switching technologies.The advent of optical transmission technologies,such as dense wave division multiplexing(DWDM),optical add- drop multiplexers,and ultra-long-haul lasers have had a large influence on lowering the costs of digital transmission.For instance,300 channels of 11.6 Gbps can be wavelength-division multiplexed on a single fiber and transmitted over 7000 km [1].In addition,a 1296 x 1296 optical cross-connect (OXC)switching system using micro-electro-mechanical systems (MEMS)with a total switching capacity of 2.07 petabits/s has been demonstrated [2].In the rest of this chapter,we explore state-of-the-art network infrastructure,future design trends,and their impact on next generation routers.We also describe router architectures and the challenges involved in designing high-performance large-scale routers. High Performance Switches and Routers,by H.Jonathan Chao and Bin Liu Copyright 2007 John Wiley Sons,Inc. 1
Book1099 — “c01” — 2007/2/16 — 18:26 — page 1 — #1 CHAPTER 1 INTRODUCTION The Internet, with its robust and reliable Internet Protocol (IP), is widely considered the most reachable platform for the current and next generation information infrastructure. The virtually unlimited bandwidth of optical fiber has tremendously increased the data transmission speed over the past decade. Availability of unlimited bandwidth has stimulated high-demand multimedia services such as distance learning, music and video download, and videoconferencing. Current broadband access technologies, such as digital subscriber lines (DSLs) and cable television (CATV), are providing affordable broadband connection solutions to the Internet from home. Furthermore, with Gigabit Ethernet access over dark fiber to the enterprise on its way, access speeds are expected to largely increase. It is clear that the deployment of these broadband access technologies will result in a high demand for large Internet bandwidth. To keep pace with the Internet traffic growth, researchers are continually exploring faster transmission and switching technologies. The advent of optical transmission technologies, such as dense wave division multiplexing (DWDM), optical adddrop multiplexers, and ultra-long-haul lasers have had a large influence on lowering the costs of digital transmission. For instance, 300 channels of 11.6 Gbps can be wavelength-division multiplexed on a single fiber and transmitted over 7000 km [1]. In addition, a 1296 × 1296 optical cross-connect (OXC) switching system using micro-electro-mechanical systems (MEMS) with a total switching capacity of 2.07 petabits/s has been demonstrated [2]. In the rest of this chapter, we explore state-of-the-art network infrastructure, future design trends, and their impact on next generation routers. We also describe router architectures and the challenges involved in designing high-performance large-scale routers. High Performance Switches and Routers, by H. Jonathan Chao and Bin Liu Copyright © 2007 John Wiley & Sons, Inc. 1