Broadband packet switching technologies : a practical guide to ATM switches and IP routers

The effective design of high-speed, reliable switching systems is essential for moving the huge volumes of traffic and multimedia over modern communications networks. This book explains all the main packet-switching architectures, including all theoretical and practical topics relevant to the design and management of high-speed networks. Delivering the most systematic coverage available of the subject, the authors interweave fundamental concepts with real-world applications and include engineering case studies from wireless and fiber-optic communications.
Market: Hardware and Software Engineers in the telecommunication industry, System Engineers, and Technicians.

Author Notes

H. JONATHAN CHAO, PhD, earned his doctorate at The Ohio State University. Since 1992 he has been Professor of Electrical Engineering at Polytechnic University, Brooklyn, New York and conducts research in terabit ATM switches and IP routers, quality of service control, and photonic packet switching. He was co-founder and Chief Technical Officer of Coree Networks Inc., building a terabit IP/MPLS switch router. Between 1985 and 1992 he was a member of technical staff at Telcordia in New Jersey. He is a Fellow of the IEEE and has published widely in the above subjects.
CHEUK H. LAM, PhD, earned his doctorate at the Chinese University of Hong Kong. He is a member of the technical staff at Lucent Technologies Inc., Landover, Maryland.
EIJI OKI, PhD, earned his doctorate at Keio University, Yokohama, Japan. He is a research engineer at NTT Network Service Systems Laboratories, Tokyo. In 2000 he was a visiting scholar at Polytechnic University.

Preface	p. xiii
1 Introduction	p. 1
1.1 ATM Switch Systems	p. 3
1.1.1 Basics of ATM networks	p. 3
1.1.2 ATM switch structure	p. 5
1.2 IP Router Systems	p. 8
1.2.1 Functions of IP routers	p. 8
1.2.2 Architectures of IP routers	p. 9
1.3 Design Criteria and Performance Requirements	p. 13
References	p. 14
2 Basics of Packet Switching	p. 15
2.1 Switching Concepts	p. 17
2.1.1 Internal link blocking	p. 17
2.1.2 Output port contention	p. 18
2.1.3 Head-of-line blocking	p. 19
2.1.4 Multicasting	p. 19
2.1.5 Call splitting	p. 20
2.2 Switch Architecture Classification	p. 21
2.2.1 Time division switching	p. 22
2.2.2 Space division switching	p. 24
2.2.3 Buffering strategies	p. 34
2.3 Performance of Basic Switches	p. 37
2.3.1 Input-buffered switches	p. 37
2.3.2 Output-buffered switches	p. 40
2.3.3 Completely shared-buffer switches	p. 44
References	p. 46
3 Input-Buffered Switches	p. 49
3.1 A Simple Switch Model	p. 50
3.1.1 Head-of-line blocking phenomenon	p. 51
3.1.2 Traffic models and related throughput results	p. 52
3.2 Methods for Improving Performance	p. 53
3.2.1 Increasing internal capacity	p. 53
3.2.2 Increasing scheduling efficiency	p. 54
3.3 Scheduling Algorithms	p. 57
3.3.1 Parallel iterative matching (PIM)	p. 58
3.3.2 Iterative round-robin matching (iRRM)	p. 60
3.3.3 Iterative round-robin with SLIP (iSLIP)	p. 60
3.3.4 Dual round-robin matching (DRRM)	p. 62
3.3.5 Round-robin greedy scheduling	p. 65
3.3.6 Design of round-robin arbiters/selectors	p. 67
3.4 Output-Queuing Emulation	p. 72
3.4.1 Most-Urgent-Cell-First-Algorithm (MUCFA)	p. 72
3.4.2 Chuang et al.'s results	p. 73
3.5 Lowest-Output-Occupancy-Cell-First Algorithm (LOOFA)	p. 78
References	p. 80
4 Shared-Memory Switches	p. 83
4.1 Linked-List Approach	p. 84
4.2 Content-Addressable Memory Approach	p. 91
4.3 Space--Time--Space Approach	p. 93
4.4 Multistage Shared-Memory Switches	p. 94
4.4.1 Washington University gigabit switch	p. 95
4.4.2 Concentrator-based growable switch architecture	p. 96
4.5 Multicast Shared-Memory Switches	p. 97
4.5.1 Shared-memory switch with a multicast logical queue	p. 97
4.5.2 Shared-memory switch with cell copy	p. 98
4.5.3 Shared-memory switch with address copy	p. 99
References	p. 101
5 Banyan-Based Switches	p. 103
5.1 Banyan Networks	p. 103
5.2 Batcher-Sorting Network	p. 106
5.3 Output Contention Resolution Algorithms	p. 110
5.3.1 Three-phase implementation	p. 110
5.3.2 Ring reservation	p. 110
5.4 The Sunshine Switch	p. 112
5.5 Deflection Routing	p. 114
5.5.1 Tandem banyan switch	p. 114
5.5.2 Shuffle-exchange network with deflection routing	p. 117
5.5.3 Dual shuffle-exchange network with error-correcting routing	p. 118
5.6 Multicast Copy Networks	p. 125
5.6.1 Broadcast banyan network	p. 127
5.6.2 Encoding process	p. 129
5.6.3 Concentration	p. 132
5.6.4 Decoding process	p. 133
5.6.5 Overflow and call splitting	p. 133
5.6.6 Overflow and input fairness	p. 134
References	p. 138
6 Knockout-Based Switches	p. 141
6.1 Single-Stage Knockout Switch	p. 142
6.1.1 Basic architecture	p. 142
6.1.2 Knockout concentration principle	p. 144
6.1.3 Construction of the concentrator	p. 146
6.2 Channel Grouping Principle	p. 150
6.2.1 Maximum throughput	p. 150
6.2.2 Generalized knockout principle	p. 152
6.3 A Two-Stage Multicast Output-Buffered ATM Switch	p. 154
6.3.1 Two-stage configuration	p. 154
6.3.2 Multicast grouping network	p. 157
6.3.3 Translation tables	p. 160
6.3.4 Multicast knockout principle	p. 163
6.4 A Fault-Tolerant Multicast Output-Buffered ATM Switch	p. 169
6.4.1 Fault model of switch element	p. 169
6.4.2 Fault detection	p. 172
6.4.3 Fault location and reconfiguration	p. 174
6.4.4 Performance analysis of reconfigured switch module	p. 181
6.5 Appendix	p. 185
References	p. 187
7 The Abacus Switch	p. 189
7.1 Basic Architecture	p. 190
7.2 Multicast Contention Resolution Algorithm	p. 193
7.3 Implementation of Input Port Controller	p. 197
7.4 Performance	p. 198
7.4.1 Maximum throughput	p. 199
7.4.2 Average delay	p. 203
7.4.3 Cell loss probability	p. 206
7.5 ATM Routing and Concentration Chip	p. 208
7.6 Enhanced Abacus Switch	p. 211
7.6.1 Memoryless multistage concentration network	p. 212
7.6.2 Buffered multistage concentration network	p. 214
7.6.3 Resequencing cells	p. 217
7.6.4 Complexity comparison	p. 219
7.7 Abacus Switch for Packet Switching	p. 220
7.7.1 Packet interleaving	p. 220
7.7.2 Cell interleaving	p. 222
References	p. 224
8 Crosspoint-Buffered Switches	p. 227
8.1 Overview of Crosspoint-Buffered Switches	p. 228
8.2 Scalable Distributed Arbitration Switch	p. 229
8.2.1 SDA structure	p. 229
8.2.2 Performance of SDA switch	p. 231
8.3 Multiple-QoS SDA Switch	p. 234
8.3.1 MSDA structure	p. 234
8.3.2 Performance of MSDA switch	p. 236
References	p. 238
9 The Tandem-Crosspoint Switch	p. 239
9.1 Overview of Input--Output-Buffered Switches	p. 239
9.2 TDXP Structure	p. 241
9.2.1 Basic architecture	p. 241
9.2.2 Unicasting operation	p. 242
9.2.3 Multicasting operation	p. 246
9.3 Performance of TDXP Switch	p. 246
References	p. 252
10 Clos-Network Switches	p. 253
10.1 Routing Properties and Scheduling Methods	p. 255
10.2 A Suboptimal Straight Matching Method for Dynamic Routing	p. 258
10.3 The ATLANTA Switch	p. 259
10.3.1 Basic architecture	p. 261
10.3.2 Distributed and random arbitration	p. 261
10.3.3 Multicasting	p. 262
10.4 The Continuous Round-Robin Dispatching Switch	p. 263
10.4.1 Basic architecture	p. 264
10.4.2 Concurrent round-robin dispatching (CRRD) scheme	p. 265
10.4.3 Desynchronization effect of CRRD	p. 267
10.5 The Path Switch	p. 268
10.5.1 Homogeneous capacity and route assignment	p. 272
10.5.2 Heterogeneous capacity assignment	p. 274
References	p. 277
11 Optical Packet Switches	p. 279
11.1 All-Optical Packet Switches	p. 281
11.1.1 The staggering switch	p. 281
11.1.2 ATMOS	p. 282
11.1.3 Duan's switch	p. 283
11.2 Optoelectronic Packet Switches	p. 284
11.2.1 HYPASS	p. 284
11.2.2 STAR-TRACK	p. 286
11.2.3 Cisneros and Brackett's Architecture	p. 287
11.2.4 BNR switch	p. 289
11.2.5 Wave-mux switch	p. 290
11.3 The 3M Switch	p. 291
11.3.1 Basic architecture	p. 291
11.3.2 Cell delineation unit	p. 294
11.3.3 VCI-overwrite unit	p. 296
11.3.4 Cell synchronization unit	p. 297
11.4 Optical Interconnection Network for Terabit IP Routers	p. 301
11.4.1 Introduction	p. 301
11.4.2 A terabit IP router architecture	p. 303
11.4.3 Router module and route controller	p. 306
11.4.4 Optical interconnection network	p. 309
11.4.5 Ping-pong arbitration unit	p. 315
11.4.6 OIN complexity	p. 324
11.4.7 Power budget analysis	p. 326
11.4.8 Crosstalk analysis	p. 328
References	p. 331
12 Wireless ATM Switches	p. 337
12.1 Wireless ATM Structure Overviews	p. 338
12.1.1 System considerations	p. 338
12.1.2 Wireless ATM protocol	p. 349
12.2 Wireless ATM Systems	p. 341
12.2.1 NEC's WATMnet prototype system	p. 341
12.2.2 Olivetti's radio ATM LAN	p. 342
12.2.3 Virtual connection tree	p. 342
12.2.4 BAHAMA wireless ATM LAN	p. 343
12.2.5 NTT's wireless ATM Access	p. 343
12.2.6 Other European projects	p. 243
12.3 Radio Access Layers	p. 344
12.3.1 Radio physical layer	p. 344
12.3.2 Medium access control layer	p. 346
12.3.3 Data link control layer	p. 346
12.4 Handoff in Wireless ATM	p. 347
12.4.1 Connection rerouting	p. 348
12.4.2 Buffering	p. 340
12.4.3 Cell routing in a COS	p. 351
12.5 Mobility-Support ATM Switch	p. 352
12.5.1 Design of a mobility-support switch	p. 353
12.5.2 Performance	p. 358
References	p. 362
13 IP Route Lookups	p. 365
13.1 IP Router Design	p. 366
13.1.1 Architectures of generic routers	p. 366
13.1.2 IP route lookup design	p. 368
13.2 IP Route Lookup Based on Caching Technique	p. 369
13.3 IP Route Lookup Based on Standard Trie Structure	p. 369
13.4 Patricia Tree	p. 372
13.5 Small Forwarding Tables for Fast Route Lookups	p. 373
13.5.1 Level 1 of data structure	p. 374
13.5.2 Levels 2 and 3 of data structure	p. 376
13.5.3 Performance	p. 377
13.6 Route Lookups in Hardware at Memory Access Speeds	p. 377
13.6.1 The DIR-24-8-BASIC scheme	p. 378
13.6.2 Performance	p. 381
13.7 IP Lookups Using Multiway Search	p. 381
13.7.1 Adapting binary search for best matching prefix	p. 381
13.7.2 Precomputed 16-bit prefix table	p. 384
13.7.3 Multiway binary search: exploiting the cache line	p. 385
13.7.4 Performance	p. 388
13.8 IP Route Lookups for Gigabit Switch Routers	p. 388
13.8.1 Lookup algorithms and data structure construction	p. 388
13.8.2 Performance	p. 395
13.9 IP Route Lookups Using Two-Trie Structure	p. 396
13.9.1 IP route lookup algorithm	p. 397
13.9.2 Prefix update algorithms	p. 398
13.9.3 Performance	p. 403
References	p. 404
Appendix Sonet and ATM Protocols	p. 407
A.1 ATM Protocol Reference Model	p. 409
A.2 Synchronous Optical Network (SONET)	p. 410
A.2.1 SONET sublayers	p. 410
A.2.2 STS-N signals	p. 412
A.2.3 SONET overhead bytes	p. 414
A.2.4 Scrambling and descrambling	p. 417
A.2.5 Frequency justification	p. 418
A.2.6 Automatic protection switching (APS)	p. 419
A.2.7 STS-3 versus STS-3c	p. 421
A.2.8 OC-N multiplexer	p. 422
A.3 Sub-Layer Functions in Reference Model	p. 423
A.4 Asynchronous Transfer Mode (ATM)	p. 425
A.4.1 Virtual path/virtual channel identifier (VPI/VCI)	p. 426
A.4.2 Payload type identifier (PTI)	p. 427
A.4.3 Cell loss priority (CLP)	p. 428
A.4.4 Pre-defined header field values	p. 428
A.5 ATM Adaptation Layer (AAL)	p. 429
A.5.1 AAL type 1 (AAL1)	p. 431
A.5.2 AAL type 2 (AAL2)	p. 433
A.5.3 AAL types 3/4 (AAL3/4)	p. 434
A.5.4 AAL type 5 (AAL5)	p. 436
References	p. 438
Index	p. 439

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents