Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Broadband Packet Switching Technologies

.pdf
Скачиваний:
109
Добавлен:
17.08.2013
Размер:
14.9 Mб
Скачать

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

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