Broadband Packet Switching Technologies
.pdfBroadband 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
A Wiley-Interscience Publication
JOHN WILEY & SONS, INC.
New York r Chichester r Weinheim r Brisbane r Singapore r Toronto
Designations used by companies to distinguish their products are often claimed as trademarks. In all instances where John Wiley & Sons, Inc., is aware of a claim, the product names appear in initial capital or ALL CAPITAL LETTERS. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.
Copyright 2001 by John Wiley & Sons, Inc. All rights reserved.
No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic or mechanical, including uploading, downloading, printing, decompiling, recording or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the Publisher. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 605 Third Avenue, New York, NY 10158-0012, Ž212. 850-6011, fax Ž212. 850-6008, E-Mail: PERMREQ & WILEY.COM.
This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold with the understanding that the publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional person should be sought.
ISBN 0-471-22440-5
This title is also available in print as ISBN 0-471-00454-5
For more information about Wiley products, visit our web site at www.Wiley.com.
CONTENTS
PREFACE |
xiii |
1 INTRODUCTION |
1 |
1.1ATM Switch Systems r 3
1.1.1Basics of ATM networks r 3
1.1.2ATM switch structure r 5
1.2IP Router Systems r 8
1.2.1Functions of IP routers r 8
1.2.2Architectures of IP routers r 9
1.3Design Criteria and Performance Requirements r 13
References r 14
2 BASICS OF PACKET SWITCHING |
15 |
2.1Switching Concepts r 17
2.1.1Internal link blocking r 17
2.1.2Output port contention r 18
2.1.3Head-of-line blocking r 19
2.1.4Multicasting r 19
2.1.5Call splitting r 20
2.2Switch Architecture Classification r 21
2.2.1Time division switching r 22
v
viCONTENTS
2.2.2Space division switching r 24
2.2.3Buffering strategies r 34
2.3Performance of Basic Switches r 37
2.3.1Input-buffered switches r 37
2.3.2Output-buffered switches r 40
2.3.3Completely shared-buffer switches r 44 References r 46
3 INPUT-BUFFERED SWITCHES |
49 |
3.1A Simple Switch Model r 50
3.1.1Head-of-line blocking phenomenon r 51
3.1.2Traffic models and related throughput results r 52
3.2Methods for Improving Performance r 53
3.2.1Increasing internal capacity r 53
3.2.2Increasing scheduling efficiency r 54
3.3Scheduling Algorithms r 57
3.3.1Parallel iterative matching ŽPIM. r 58
3.3.2Iterative round-robin matching ŽiRRM. r 60
3.3.3Iterative round-robin with SLIP ŽiSLIP. r 60
3.3.4Dual round-robin matching ŽDRRM. r 62
3.3.5Round-robin greedy scheduling r 65
3.3.6Design of round-robin arbitersrselectors r 67
3.4Output-Queuing Emulation r 72
3.4.1Most-Urgent-Cell-First-Algorithm ŽMUCFA. r 72
3.4.2Chuang et al.’s results r 73
3.5Lowest-Output-Occupancy-Cell-First Algorithm ŽLOOFA. r 78
References r 80
4 SHARED-MEMORY SWITCHES |
83 |
4.1Linked-List Approach r 84
4.2Content-Addressable Memory Approach r 91
4.3Space Time Space Approach r 93
4.4Multistage Shared-Memory Switches r 94
4.4.1Washington University gigabit switch r 95
4.4.2Concentrator-based growable switch architecture r 96
4.5Multicast Shared-Memory Switches r 97
CONTENTS vii
4.5.1Shared-memory switch with a multicast logical queue r 97
4.5.2Shared-memory switch with cell copy r 98
4.5.3Shared-memory switch with address copy r 99 References r 101
5 BANYAN-BASED SWITCHES |
103 |
5.1Banyan Networks r 103
5.2Batcher-Sorting Network r 106
5.3Output Contention Resolution Algorithms r 110
5.3.1Three-phase implementation r 110
5.3.2Ring reservation r 110
5.4The Sunshine Switch r 112
5.5Deflection Routing r 114
5.5.1Tandem banyan switch r 114
5.5.2Shuffle-exchange network with deflection routing r 117
5.5.3Dual shuffle-exchange network with error-correcting routing r 118
5.6Multicast Copy Networks r 125
5.6.1Broadcast banyan network r 127
5.6.2Encoding process r 129
5.6.3Concentration r 132
5.6.4Decoding process r 133
5.6.5Overflow and call splitting r 133
5.6.6Overflow and input fairness r 134
References r 138
6 KNOCKOUT-BASED SWITCHES |
141 |
6.1Single-Stage Knockout Switch r 142
6.1.1Basic architecture r 142
6.1.2Knockout concentration principle r 144
6.1.3Construction of the concentrator r 146
6.2Channel Grouping Principle r 150
6.2.1Maximum throughput r 150
6.2.2Generalized knockout principle r 152
6.3A Two-Stage Multicast Output-Buffered ATM
Switch r 154
6.3.1Two-stage configuration r 154
viiiCONTENTS
6.3.2Multicast grouping network r 157
6.3.3Translation tables r 160
6.3.4Multicast knockout principle r 163
6.4A Fault-Tolerant Multicast Output-Buffered ATM
Switch r 169
6.4.1Fault model of switch element r 169
6.4.2Fault detection r 172
6.4.3Fault location and reconfiguration r 174
6.4.4Performance analysis of reconfigured switch module r 181
6.5Appendix r 185
References r 187
7 THE ABACUS SWITCH |
189 |
7.1Basic Architecture r 190
7.2Multicast Contention Resolution Algorithm r 193
7.3Implementation of Input Port Controller r 197
7.4Performance r 198
7.4.1Maximum throughput r 199
7.4.2Average delay r 203
7.4.3Cell loss probability r 206
7.5ATM Routing and Concentration Chip r 208
7.6Enhanced Abacus Switch r 211
7.6.1Memoryless multistage concentration network r 212
7.6.2Buffered multistage concentration network r 214
7.6.3Resequencing cells r 217
7.6.4Complexity comparison r 219
7.7Abacus Switch for Packet Switching r 220
7.7.1Packet interleaving r 220
7.7.2Cell interleaving r 222
References r 224
8 CROSSPOINT-BUFFERED SWITCHES |
227 |
8.1Overview of Crosspoint-Buffered Switches r 228
8.2Scalable Distributed Arbitration Switch r 229
8.2.1SDA structure r 229
8.2.2Performance of SDA switch r 231
8.3Multiple-QoS SDA Switch r 234
8.3.1MSDA structure r 234
CONTENTS ix
8.3.2 Performance of MSDA switch r 236
References r 238
9 THE TANDEM-CROSSPOINT SWITCH |
239 |
9.1Overview of Input Output Buffered Switches r 239
9.2TDXP Structure r 241
9.2.1Basic architecture r 241
9.2.2Unicasting operation r 242
9.2.3Multicasting operation r 246
9.3Performance of TDXP Switch r 246
References r 252
10 CLOS-NETWORK SWITCHES |
253 |
10.1Routing Properties and Scheduling Methods r 255
10.2A Suboptimal Straight Matching Method for Dynamic
Routing r 258
10.3The ATLANTA Switch r 259
10.3.1Basic architecture r 261
10.3.2Distributed and random arbitration r 261
10.3.3Multicasting r 262
10.4The Continuous Round-Robin Dispatching Switch r 263
10.4.1Basic architecture r 264
10.4.2Concurrent round-robin dispatching ŽCRRD. scheme r 265
10.4.3Desynchronization effect of CRRD r 267
10.5The Path Switch r 268
10.5.1Homogeneous capacity and route assignment r 272
10.5.2Heterogeneous capacity assignment r 274
References r 277
11 OPTICAL PACKET SWITCHES |
279 |
11.1All-Optical Packet Switches r 281
11.1.1The staggering switch r 281
11.1.2ATMOS r 282
11.1.3Duan’s switch r 283
11.2Optoelectronic Packet Switches r 284
11.2.1HYPASS r 284
11.2.2STAR-TRACK r 286
xCONTENTS
11.2.3Cisneros and Brackett’s Architecture r 287
11.2.4BNR switch r 289
11.2.5Wave-mux switch r 290
11.3The 3M Switch r 291
11.3.1Basic architecture r 291
11.3.2Cell delineation unit r 294
11.3.3VCI-overwrite unit r 296
11.3.4Cell synchronization unit r 297
11.4Optical Interconnection Network for Terabit IP
Routers r 301
11.4.1Introduction r 301
11.4.2A terabit IP router architecture r 303
11.4.3Router module and route controller r 306
11.4.4Optical interconnection network r 309
11.4.5Ping-pong arbitration unit r 315
11.4.6OIN complexity r 324
11.4.7Power budget analysis r 326
11.4.8Crosstalk analysis r 328
References r 331
12 WIRELESS ATM SWITCHES |
337 |
12.1Wireless ATM Structure Overviews r 338
12.1.1System considerations r 338
12.1.2Wireless ATM protocol r 349
12.2Wireless ATM Systems r 341
12.2.1NEC’s WATMnet prototype system r 341
12.2.2Olivetti’s radio ATM LAN r 342
12.2.3Virtual connection tree r 342
12.2.4BAHAMA wireless ATM LAN r 343
12.2.5NTT’s wireless ATM Access r 343
12.2.6Other European projects r 243
12.3Radio Access Layers r 344
12.3.1Radio physical layer r 344
12.3.2Medium access control layer r 346
12.3.3Data link control layer r 346
12.4Handoff in Wireless ATM r 347
12.4.1Connection rerouting r 348
12.4.2Buffering r 340
CONTENTS xi
12.4.3Cell routing in a COS r 351
12.5Mobility-Support ATM Switch r 352
12.5.1Design of a mobility-support switch r 353
12.5.2Performance r 358
References r 362
13 IP ROUTE LOOKUPS |
365 |
13.1IP Router Design r 366
13.1.1Architectures of generic routers r 366
13.1.2IP route lookup design r 368
13.2IP Route Lookup Based on Caching Technique r 369
13.3IP Route Lookup Based on Standard Trie
Structure r 369
13.4Patricia Tree r 372
13.5Small Forwarding Tables for Fast Route Lookups r 373
13.5.1Level 1 of data structure r 374
13.5.2Levels 2 and 3 of data structure r 376
13.5.3Performance r 377
13.6Route Lookups in Hardware at Memory Access Speeds r 377
13.6.1The DIR-24-8-BASIC scheme r 378
13.6.2Performance r 381
13.7IP Lookups Using Multiway Search r 381
13.7.1Adapting binary search for best matching prefix r 381
13.7.2Precomputed 16-bit prefix table r 384
13.7.3Multiway binary search: exploiting the cache line r 385
13.7.4Performance r 388
13.8IP Route Lookups for Gigabit Switch Routers r 388
13.8.1Lookup algorithms and data structure construction r 388
13.8.2Performance r 395
13.9IP Route Lookups Using Two-Trie Structure r 396
13.9.1IP route lookup algorithm r 397
13.9.2Prefix update algorithms r 398
13.9.3Performance r 403
References r 404