Broadband Packet Switching Technologies

xii CONTENTS
APPENDIX SONET AND ATM PROTOCOLS		407
A.1 ATM Protocol Reference Model r 409
A.2 Synchronous Optical Network ŽSONET. r 410
A.2.1	SONET sublayers r 410
A.2.2	STS-N signals r 412
A.2.3 SONET overhead bytes r 414
A.2.4 Scrambling and descrambling r 417
A.2.5	Frequency justification r 418
A.2.6	Automatic protection switching ŽAPS. r 419
A.2.7	STS-3 versus STS-3c r 421
A.2.8	OC-N multiplexer r 422

A.3 Sub-Layer Functions in Reference Model r 423

A.4 Asynchronous Transfer Mode ŽATM. r 425 A.4.1 Virtual pathrvirtual channel identifier

ŽVPIrVCI. r 426

A.4.2 Payload type identifier ŽPTI. r 427 A.4.3 Cell loss priority ŽCLP. r 428

A.4.4 Pre-defined header field values r 428

A.5 ATM Adaptation Layer ŽAAL. r 429 A.5.1 AAL type 1 ŽAAL1. r 431 A.5.2 AAL type 2 ŽAAL2. r 433

A.5.3 AAL types 3r4 ŽAAL3r4. r 434

A.5.4 AAL type 5 ŽAAL5. r 436

References r 438

INDEX

439

PREFACE

This packet switching book mainly targets high-speed packet networking. As

Internet traffic grows exponentially, there is a great need to build multiterabit Internet protocol ŽIP. routers, asynchronous transfer mode ŽATM. switches, multiprotocol label switch ŽMPLS. switches, and optical switches.

Packet switching technologies have been investigated and researched intensively for almost two decades, but there are very few appropriate textbooks describing it. Many engineers and students have to search for technical papers and read them in an ad hoc manner. This book is the first that explains packet switching concepts and implementation technologies in broad scope and great depth.

This book addresses the basics, theory, architectures, and technologies to implement ATM switches, IP routers, and optical switches. The book is based on the material that Jonathan has been teaching to the industry and universities for the past decade. He taught a graduate course ‘‘Broadband

Packet Switching Systems’’ at Polytechnic University, New York, and used the draft of the book as the text. The book has incorporated feedback from both industry people and college students.

The fundamental concepts and technologies of packet switching described in the book are useful and practical when designing IP routers, packet switches, and optical switches. The basic concepts can also stand by themselves and are independent of the emerging network platform, for instance, IP, ATM, MPLS, and IP over wavelength-division multiplexing ŽWDM..

ATM switching technologies have been widely used to achieve high speed and high capacity. This is because ATM uses fixed-length cells and the switching can be implemented at high speed with synchronous hardware

xiii

xiv PREFACE

logics. Although most of low-end to medium-size IP routers do not use the same hardware-based technologies as those of ATM switches, next-genera- tion backbone IP routers will use the ATM switching technologies Žalthough the cell size in the switch core of IP routers may be different from that of

ATM cells.. The switching technologies described in this book are common to both ATM switches and IP routers. We believe that the book will be a practical guide to understand ATM switches and IP routers.

AUDIENCE

This book can be used as a reference book for industry people whose job is related to ATMrIPrMPLS networks. Engineers from network equipment and service providers can benefit from the book by understanding the key concepts of packet switching systems and key techniques of building a high-speed and high-capacity packet switch. This book is also a good text for senior and graduate students in electrical engineering, computer engineering, and compute science. Using it, students will understand the technology trend in packet networks so that they can better position themselves when they graduate and look for jobs in the high-speed networking field.

ORGANIZATION OF THE BOOK

The book is organized as follows.

Chapter 1 introduces the basic structure of ATM switching systems and IP routers. It discusses the functions of both systems and their design criteria and performance requirements.

Chapter 2 classifies packet switching architectures into different categories and compares them in performance and implementation complexity. It also covers terminologies, concepts, issues, solutions, and approaches of designing packet switches at a high level so that readers can grasp the basics before getting into the details in the following chapters.

Chapter 3 discusses the fundamentals of input-buffered switches. Switches with input and output buffering are also described in this chapter. We show the problems of input-buffered switches, and present the techniques and algorithms that have been proposed to tackle the problems.

Chapter 4 discusses the shared-memory switches, which have been widely used in industry because of their high performance and small buffers. We describe the operation principles of the shared-memory switches in detail.

PREFACE xv

Chapter 5 discusses banyan-family switches, which have attracted many researchers for more than two decades as components of interconnection networks. We discuss the theory of the nonblocking property of

Batcher banyan switches and describe several example architectures in detail.

Chapter 6 discusses several switches based on the knockout principle.

Their implementation architectures are described in detail.

Chapter 7 describes a scalable multicasting switch architecture and a fault-tolerant switch. The latter is very important for a reliable network but has not been received much attention. We discuss the architectures and algorithms for building such switches.

Chapter 8 discusses a scalable crosspoint-buffered switch architecture

with a distributed-contention control scheme. We also describe how to support multiple quality-of-service ŽQoS. classes in the switch.

Chapter 9 discusses an input output-buffered switch, called the tandem-crosspoint switch, that fully utilizes current CMOS technologies.

Chapter 10 discusses multi-stage Clos-network switches, which are attractive because of their scalability. It presents the properties of Clos networks and introduces several routing algorithms in the Clos network.

Chapter 11 describes optical switch architectures in both all-optical and optoelectronic approaches. Several design examples are described.

Chapter 12 introduces mobility-support ATM switches. It also discusses wireless ATM protocols and surveys several proposed wireless ATM systems.

Chapter 13 discusses fast IP route lookup approaches, which have been proposed over the past few years. Their performance and implementation complexity are described.

ACKNOWLEDGMENTS

This book could not have been published without the help of many people.

We thank them for their efforts in improving the quality of the book. We have done our best to accurately describe broadband packet switching technologies. If any errors are found, please send an email to [e-mail]. We will correct them in future editions.

The entire manuscript draft was reviewed by Dr. Aleksandra Smiljanic ŽAT & T Laboratories., Dr. Li-Sheng Chen ŽAlcatel., Dr. Kurimoto Takashi

ŽNTT., Dr. Soung-Yue Liew, and Dr. Zhigang Jing ŽPolytechnic University..

We are immensely grateful for their critiques and suggestions.

Several chapters of the book are based on research work that was done at

Polytechnic University, Chinese University of Hong Kong, and NTT. We

xvi PREFACE

would like to thank several persons who contributed material to some chapters. Especially, we thank Professor Tony Lee ŽChinese University of

Hong Kong., Dr. Necdet Uzun ŽAurora Netics,Inc.., Professor Byeong-Seog Choe ŽDong Guk University., Dr. Jin-Soo Park ŽCoree Networks., Dr.

Ti-Shiang Wang ŽNokia., Dr. Heechang Kim ŽTelecordia., Roberto Rojas-

Cessa ŽCoree Networks., Taweesak Kijkanjanarat ŽPolytechnic University., and Dr. Naoaki Yamanaka ŽNTT..

Jonathan wants 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. Cheuk would like to thank his wife, Lili, and his parents for their love and support. Eiji wishes to thank his wife, Noako, and his daughter, Kanako, for their love.

H. JONATHAN CHAO

CHEUK H. LAM

EIJI OKI

July 2001

Broadband Packet Switching Technologies: A Practical Guide to ATM Switches and IP Routers

H. Jonathan Chao, Cheuk H. Lam, Eiji Oki

Copyright 2001 John Wiley & Sons, Inc. ISBNs: 0-471-00454-5 ŽHardback.; 0-471-22440-5 ŽElectronic.

BROADBAND PACKET

SWITCHING TECHNOLOGIES

Broadband Packet Switching Technologies: A Practical Guide to ATM Switches and IP Routers

H. Jonathan Chao, Cheuk H. Lam, Eiji Oki

Copyright 2001 John Wiley & Sons, Inc. ISBNs: 0-471-00454-5 ŽHardback.; 0-471-22440-5 ŽElectronic.

CHAPTER 1

INTRODUCTION

The scalable and distributed nature of the Internet continuously contributes to a wild and rapid growth of its population, including the number of users, hosts, links, and emerging applications. The great success of the Internet thus leads to exponential increases in traffic volumes, stimulating an unprecedented demand for the capacity of the core network.

Network providers therefore face the need of providing a new network infrastructure that can support the growth of traffic in the core network. Advances in fiber throughput and optical transmission technologies have enabled operators to deploy capacity in a dramatic fashion. However, the advancement in packet switchrrouter technologies is rather slow, so that it is still not able to keep pace with the increase in link transmission speed.

Dense-wavelength-division-multiplexing ŽDWDM. equipment is installed on each end of the optical fiber to multiplex wavelengths Ži.e., channels. over a single fiber. For example, a 128-channel OC-192 Ž10 Gbitrs. DWDM system can multiplex the signals to achieve a total capacity of 1.2 Tbitrs. Several vendors are expected to enter trials for wide area DWDM networks that support OC-768 Ž40 Gbitrs. for each channel in the near future.

Another advanced optical technology that is being deployed in the optical network is the optical cross connect ŽOXC. system. Since the optical-to-elec- trical-to-optical conversions do not occur within the system, transmission interfaces are transparent. The OXC System is based on the microelectromechanical systems ŽMEMS. technology, where an array of hundreds or thousands of electrically configurable microscopic mirrors is fabricated on a

2INTRODUCTION

single substrate to direct light. The switching scheme is based on freely moving mirrors being rotated around micromachined hinges with submillisecond switching speed. It is rateand format-independent.

As carriers deploy fiber and DWDM equipment to expand capacity, terabit packet switching technologies are required to aggregate high-bit-rate links while achieving higher utilization on the links. Although OXC systems have high-speed interfaces Že.g., 10 or 40 Gbitrs. and large switching capacity Že.g., 10 40 Tbitrs., the granularity of the switching is coarse, e.g., 10 or 40 Gbitrs. As a result, it is required to have high-speed and largecapacity packet switchesrrouters to aggregate lower-bit-rate traffic to 10 or 40 Gbitrs links. The aggregated traffic can be delivered to destinations through DWDM transmission equipment or OXC systems. The terabit packet switches that are critical elements of the Internet network infrastructure must have switch fabric capable of supporting terabit speeds to eliminate the network bottlenecks. Core terabit switchesrrouters must also deliver low latency and guaranteed delay variance to support real-time traffic. As a result, quality-of-service ŽQoS. control techniques, such as traffic shaping, packet scheduling, and buffer management, need to be incorporated into the switchesrrouters.

Asynchronous transfer mode ŽATM. is revolutionizing the telecommunications infrastructure by transmitting integrated voice, data, and video at very high speed. The current backbone network mainly consists of ATM switches and IP routers, where ATM cells and IP packets are carried on an optical physical layer such as the Synchronous Optical Network ŽSONET.. ATM also provides different QoS requirements for various multimedia services. Readers who are interested in knowing the SONET frame structure, the ATM cell format, and the functions associated with SONETrATM layers are referred to the Appendix.

Along with the growth of the Internet, IP has become the dominant protocol for data traffic and is making inroads into voice transmission as well. Network providers recognize the cost savings and performance advantages of converging voice, data, and video services onto a common network infrastructure, instead of an overlayered structure. Multi-protocol label switching ŽMPLS. is a new technology combining the advantageous features of the ATM network, short labels and explicit routing, and the connectionless datagram of the IP network. The MPLS network also provides traffic engineering capability to achieve bandwidth provisioning, fast restoration, load balancing, and virtual private network ŽVPN. services. The so-called label switching routers ŽLSRs. that route packets can be either IP routers, ATM switches, or frame relay switches. In this book, we will address the issues and technologies of building a scalable switchrrouter with large capacity, e.g., several terabits per second.

In the rest of this chapter, we briefly describe the ATM network, ATM switch systems, IP router systems, and switch design criteria and performance requirements.

ATM SWITCH SYSTEMS

3

1.1 ATM SWITCH SYSTEMS

1.1.1 Basics of ATM Networks

ATM protocol corresponds to layer 2 as defined in the open systems interconnection ŽOSI. reference model. ATM is connection-oriented. That is, an end-to-end connection Žor ®irtual channel. needs to be set up before routing ATM cells. Cells are routed based on two important values contained in the 5-byte cell header: the ®irtual path identifier ŽVPI. and ®irtual channel identifier ŽVCI., where a virtual path consists of a number of virtual channels. The number of bits allocated for a VPI depends on the type of interface. If it is the user network interface ŽUNI., between the user and the first ATM switch, 8 bits are provided for the VPI. This means that up to 28 s 256 virtual paths are available at the user access point. On the other hand, if the it is the network node interface ŽNNI., between the intermediate ATM switches, 12 bits are provided for the VPI. This indicates that there are 212 s 4096 possible virtual paths between ATM switches. In both UNI and NNI, there are 16 bits for the VCI. Thus, there are 216 s 65,536 virtual channels for each virtual path.

The combination of the VPI and the VCI determines a specific virtual connection between two ends. Instead of having the same VPIrVCI for the whole routing path, the VPIrVCI is determined on a per-link basis and changes at each ATM switch. Specifically, at each incoming link to a switch node, a VPIrVCI may be replaced with another VPIrVCI at the output link with reference to a table called a routing information table ŽRIT. in the ATM switch. This substantially increases the possible number of routing paths in the ATM network.

The operation of routing cells is as follows. Each ATM switch has its own RIT containing at least the following fields: old VPIrVCI, new VPIrVCI, output port address, and priority field Žoptional.. When an ATM cell arrives at an input line of the switch, it is split into the 5-byte header and the 48-byte payload. By using the VPIrVCI contained in the header as the old VPIrVCI value, the switch looks in the RIT for the arriving cell’s new VPIrVCI. Once the match is found, the old VPIrVCI value is replaced with the new VPIrVCI value. Moreover, the corresponding output port address and priority field are attached to the 48-byte payload of the cell, before it is sent to the switch fabric. The output port address indicates to which output port the cell should be routed. There are three modes of routing operations within the switch fabric: the unicast mode refers to the mode in which a cell is routed to a specific output port, the multicast mode refers to the mode in which a cell is routed to a number of output ports, and the broadcast mode refers to the mode in which a cell is routed to all output ports. In the unicast mode, log 2 N bits, where N is the number of inputroutput ports, are sufficient to indicate any possible output port. However, in the multicastrbroadcast modes, N bits, each associated with a particular output

4INTRODUCTION

Fig. 1.1 VPIrVCI translation along the path.

port, are needed in a single-stage switch. The priority field enables the switch to selectively transmit cells to the output ports or discard them when the buffer is full, according to service requirements.

ATM connections either are preestablished through provisioning or are set up dynamically on demand using signaling, such as UNI signaling and private network network interface ŽPNNI. routing signaling. The former is referred to permanent virtual connections ŽPVCs., while the latter is referred to switched virtual connections ŽSVCs.. For SVCs, the RIT is updated by a call processor during the call setup, which finds an appropriate routing path between the source and the destination. The VPIrVCI of every link along the path, the output port addresses of the switches, and the priority field are determined and filled into the table by the call processor. The call processor has to ensure that at each switch, the VPIrVCI of the cells coming from different connections but going to the same output port are different. In practice, there is a call processor for every ATM switch. For simplicity, Figure 1.1 just shows a call processor to update the RIT of each switch in a conceptual way.

With respect to Figure 1.1, once a call setup is completed, the source starts to send a cell whose VPIrVCI is represented by W. As soon as this cell arrives at the first ATM switch, the entries of the table are searched. The matched entry is found with a new VPIrVCI X, which replaces the old VPIrVCI W. The corresponding output port address Žwhose value is 100. and the priority field are attached to the cell so that the cell can be routed to output port 100 of the first switch. At the second ATM switch, the VPIrVCI of the cell whose value is X is updated with a new value Y. Based on the output port address obtained from the table, the incoming cell is routed to