Switching Theory-Architectures And Performance In Broadband Atm Networks

qhl0222_cn

Preface............................................................................................ xv
Chapter 1 Broadband Integrated Services Digital Network ............... 1
1.1. Current Networking Scenario ..................................................... 1
1.1.1. Communication services................................................. 1
1.1.2. Networking issues........................................................ 4
1.2. The Path to Broadband Networking ............................................. 6
1.2.1. Network evolution through ISDN to B-ISDN .................... 6
1.2.2. The protocol reference model ........................................... 10
1.3. Transfer Mode and Control of the B-ISDN ................................... 14
1.3.1. Asynchronous time division multiplexing ........................... 14
1.3.2. Congestion control issues............................................... 16
1.4. Synchronous Digital Transmission ............................................... 18
1.4.1. SDH basic features ..................................................... 19
1.4.2. SDH multiplexing structure........................................... 21
1.4.3. Synchronization by pointers........................................... 27
1.4.4. Mapping of SDH elements............................................ 31
1.5. The ATM Standard................................................................ 33
1.5.1. Protocol reference model ................................................ 34
1.5.2. The physical layer ....................................................... 39
1.5.3. The ATM layer ......................................................... 42
1.5.4. The ATM adaptation layer............................................ 45
1.5.4.1. AAL Type 1 .............................................. 47
1.5.4.2. AAL Type 2 .............................................. 48
1.5.4.3. AAL Type 3/4 ........................................... 48
1.5.4.4. AAL Type 5 .............................................. 49
Switching Theory: Architecture and Performance in Broadband ATM Networks
Achille Pattavina
Copyright © 1998 John Wiley & Sons Ltd
ISBNs: 0-471-96338-0 (Hardback); 0-470-84191-5 (Electronic)
x
Contents
1.5.4.5. AAL payload capacity ................................... 50
1.6. References............................................................................ 51
1.7. Problems ............................................................................. 52
Chapter 2 Interconnection Networks............................................. 53
2.1. Basic Network Concepts .......................................................... 53
2.1.1. Equivalence between networks ........................................ 57
2.1.2. Crossbar network based on splitters and combiners ................ 60
2.2. Full-connection Multistage Networks ........................................... 63
2.3. Partial-connection Multistage Networks ........................................ 64
2.3.1. Banyan networks ....................................................... 65
2.3.1.1. Banyan network topologies .............................. 66
2.3.1.2. Banyan network properties .............................. 70
2.3.2. Sorting networks ........................................................ 75
2.3.2.1. Merging networks ......................................... 76
2.3.2.2. Sorting networks........................................... 80
2.4. Proof of Merging Schemes......................................................... 86
2.4.1. Odd–even merge sorting ............................................... 86
2.4.2. Bitonic merge sorting ................................................... 87
2.5. References............................................................................ 89
2.6. Problems ............................................................................. 90
Chapter 3 Rearrangeable Networks............................................... 91
3.1. Full-connection Multistage Networks ........................................... 91
3.2. Partial-connection Multistage Networks ........................................ 96
3.2.1. Partially self-routing PC networks ................................... 96
3.2.1.1. Horizontal extension ..................................... 97
3.2.1.2. Vertical replication ...................................... 103
3.2.1.3. Vertical replication with horizontal extension ...... 107
3.2.1.4. Bounds on PC rearrangeable networks .............. 109
3.2.2. Fully self-routing PC networks..................................... 114
3.2.3. Fully self-routing PC networks with output multiplexing ..... 118
3.3. Bounds on the Network Cost Function ...................................... 123
3.4. References.......................................................................... 124
3.5. Problems ........................................................................... 126
Chapter 4 Non-blocking Networks ............................................. 127
4.1. Full-connection Multistage Networks ......................................... 127
4.1.1. Two-stage network.................................................... 127
4.1.2. Three-stage network .................................................. 128
4.1.3. Recursive network construction...................................... 130
4.2. Partial-connection Multistage Networks ...................................... 134
4.2.1. Vertical replication .................................................... 134
Contents
xi
4.2.2. Vertical replication with horizontal extension..................... 136
4.2.3. Link dilation........................................................... 142
4.2.4. EGS networks......................................................... 144
4.3. Comparison of Non-blocking Networks ...................................... 150
4.4. Bounds on the Network Cost Function....................................... 152
4.5. References .......................................................................... 154
4.6. Problems............................................................................ 155
Chapter 5 The ATM Switch Model .............................................. 157
5.1. The Switch Model................................................................ 159
5.2. ATM Switch Taxonomy......................................................... 163
5.3. References .......................................................................... 165
Chapter 6 ATM Switching with Minimum-Depth
Blocking Networks ..................................................... 167
6.1. Unbuffered Networks ............................................................ 168
6.1.1. Crossbar and basic banyan networks ............................... 168
6.1.1.1. Basic structures ........................................... 168
6.1.1.2. Performance............................................... 169
6.1.2. Enhanced banyan networks.......................................... 172
6.1.2.1. Structures ................................................. 172
6.1.2.2. Performance............................................... 175
6.2. Networks with a Single Plane and Internal Queueing ..................... 177
6.2.1. Input queueing ........................................................ 181
6.2.2. Output queueing ...................................................... 184
6.2.3. Shared queueing....................................................... 192
6.2.4. Performance ............................................................ 197
6.3. Networks with Unbuffered Parallel Switching Planes....................... 204
6.3.1. Basic architectures ..................................................... 204
6.3.2. Architectures with output queueing................................. 205
6.3.2.1. Specific architectures ..................................... 206
6.3.2.2. Performance............................................... 209
6.3.3. Architectures with combined input–output queueing............. 212
6.3.3.1. Models for performance analysis ....................... 213
6.3.3.2. Performance results ...................................... 216
6.4. Additional Remarks.............................................................. 221
6.5. References .......................................................................... 222
6.6. Problems............................................................................ 224
Chapter 7 ATM Switching with Non-Blocking Single-Queueing
Networks ...................................................................227
7.1. Input Queueing................................................................... 229
7.1.1. Basic architectures ..................................................... 229
xii
Contents
7.1.1.1. The Three-Phase switch ............................... 229
7.1.1.2. The Ring-Reservation switch ......................... 234
7.1.2. Performance analysis ................................................. 236
7.1.2.1. Asymptotic throughput ................................. 237
7.1.2.2. Packet delay.............................................. 239
7.1.2.3. Packet loss probability .................................. 240
7.1.3. Enhanced architectures ............................................... 241
7.1.3.1. Architecture with channel grouping ................... 242
7.1.3.2. Architecture with windowing .......................... 251
7.2. Output Queueing ................................................................ 259
7.2.1. Basic architectures ..................................................... 259
7.2.2. Performance analysis ................................................. 263
7.3. Shared Queueing................................................................. 267
7.3.1. Basic architectures ..................................................... 267
7.3.2. Performance analysis ................................................. 271
7.4. Performance Comparison of Different Queueings ........................... 274
7.5. Additional Remarks ............................................................. 276
7.6. References.......................................................................... 277
7.7. Problems ........................................................................... 279
Chapter 8 ATM Switching with Non-Blocking Multiple-Queueing
Networks ...................................................................281
8.1. Combined Input–Output Queueing .......................................... 284
8.1.1. Basic architectures ..................................................... 284
8.1.1.1. Internal queue loss ...................................... 284
8.1.1.2. Internal backpressure.................................... 288
8.1.2. Performance analysis ................................................. 295
8.1.2.1. Constrained output queue capacity ................... 296
8.1.2.2. Arbitrary input and output queue capacities ........ 299
8.1.3. Architectures with parallel switching planes....................... 315
8.2. Combined Shared-Output Queueing......................................... 317
8.2.1. Basic architecture ...................................................... 318
8.2.2. Performance analysis ................................................. 320
8.3. Combined Input-Shared Queueing ........................................... 324
8.3.1. Basic architectures .................................................... 325
8.3.2. Performance analysis ................................................. 327
8.4. Comparison of Switch Capacities in Non-blocking Switches ............. 331
8.5. Additional Remarks ............................................................. 333
8.6. References.......................................................................... 334
8.7. Problems ........................................................................... 335
Contents
xiii
Chapter 9 ATM Switching with Arbitrary-Depth Blocking
Networks ................................................................... 337
9.1. Switch Architectures Based on Deflection Routing .......................... 338
9.1.1. The Shuffleout switch ................................................ 339
9.1.2. The Shuffle Self-Routing switch ................................... 342
9.1.3. The Rerouting switch ................................................ 343
9.1.4. The Dual Shuffle switch............................................. 345
9.2. Switch Architectures Based on Simpler SEs .................................. 350
9.2.1. Previous architectures with SEs ..................................... 351
9.2.2. The Tandem Banyan switch ......................................... 351
9.3. Architecture Enhancements...................................................... 355
9.3.1. Extended routing...................................................... 355
9.3.2. Interstage bridging..................................................... 355
9.4. Performance Evaluation and Comparison .................................... 358
9.4.1. The Shuffleout switch ................................................ 358
9.4.1.1. Network with 2
×
4 SEs .............................. 358
9.4.1.2. Network with 2
×
2 SEs .............................. 360
9.4.1.3. Network performance.................................... 361
9.4.2. The Shuffle Self-Routing switch ................................... 363
9.4.2.1. Basic network with 2
×
4 SEs ........................ 364
9.4.2.2. Basic network with 2
×
2 SEs ........................ 365
9.4.2.3. Basic network performance ............................. 365
9.4.2.4. Network with extended routing and 2
×
4 SEs.... 366
9.4.2.5. Network with extended routing and 2
×
2 SEs.... 368
9.4.2.6. Network performance with extended routing ........ 369
9.4.3. The Rerouting switch ................................................ 370
9.4.4. The Dual Shuffle switch............................................. 373
9.4.5. The Tandem Banyan switch ......................................... 376
9.4.6. Interconnection network performance comparison ................. 377
9.4.7. Overall switch performance .......................................... 382
9.5. Switch Architectures with Parallel Switching Planes ........................ 384
9.6. Additional Remarks.............................................................. 386
9.7. References .......................................................................... 388
9.8. Problems............................................................................ 390
Appendix Synchronous Queues................................................... 391
A.1 Synchronous Single-server Queues .............................................392
A.1.1. The M/D/1 queue................................................... 392
A.1.1.1. The asynchronous M/G/1 queue .................... 392
A.1.1.2. The asynchronous M/D/1 queue .................... 394
A.1.1.3. The synchronous M/D/1 queue .................... 395
A.1.2. The Geom(N)/D/1 queue ......................................... 398
A.1.3. The Geom/G/1 queue.............................................. 399
xiv
Contents
A.1.4. The Geom/G/1/B queue.......................................... 399
A.2. Synchronous Multiple-server Queues . . . . . . . . . . . . . . . . . . . . . . 401
A.2.1. The M/D/C queue ................................................ 401
A.2.2. The Geom(N)/D/C/B queue..................................... 402
A.3. References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
Index...............................................................................................409

cjchang1

Thanks a lot !!!!!!!!!!!!!!!!

humann

3ks3ks

wangdong2011

Very good.

tongxin33

thanks   for  sharing !!!

zhanpeng6012

矮脚虎啊

gs2198

GSDFHBSFJFGHK

Ryggeor

thnx!

cdting

非常感謝~~~~