EEPW论坛

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