Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010047166 | TK5105.35 C524 2001 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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.
Table of Contents
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 |