Preface |
|
xiii | |
About the Authors |
|
xvii | |
1 introduction and Overview |
|
1 | |
|
1.1 Switching and Transmission |
|
|
2 | |
|
1.1.1 Roles of Switching and Transmission |
|
|
2 | |
|
1.1.2 Telephone Network Switching and Transmission Hierarchy |
|
|
4 | |
|
1.2 Multiplexing and Concentration |
|
|
5 | |
|
1.3 Timescales of Information Transfer |
|
|
8 | |
|
1.3.1 Sessions and Circuits |
|
|
9 | |
|
|
9 | |
|
|
9 | |
|
1.4 Broadband Integrated Services Network |
|
|
10 | |
|
|
12 | |
2 Circuit Switch Design Principles |
|
15 | |
|
2.1 Space-Domain Circuit Switching |
|
|
16 | |
|
2.1.1 Nonblocking Properties |
|
|
16 | |
|
2.1.2 Complexity of Nonblocking Switches |
|
|
18 | |
|
2.1.3 Clos Switching Network |
|
|
20 | |
|
2.1.4 Benes Switching Network |
|
|
28 | |
|
2.1.5 Baseline and Reverse Baseline Networks |
|
|
31 | |
|
2.1.6 Cantor Switching Network |
|
|
32 | |
|
2.2 Time-Domain and Time-Space-Time Circuit Switching |
|
|
35 | |
|
2.2.1 Time-Domain Switching |
|
|
35 | |
|
2.2.2 lime-Space-Tune Switching |
|
|
37 | |
|
|
39 | |
3 Fundamental Principles of Packet Switch Design |
|
43 | |
|
3.1 Packet Contention in Switches |
|
|
45 | |
|
3.2 Fundamental Properties of Interconnection Networks |
|
|
48 | |
|
3.2.1 Definition of Banyan Networks |
|
|
49 | |
|
3.2.2 Simple Switches Based on Banyan Networks |
|
|
51 | |
|
3.2.3 Combinatoric Properties of Banyan Networks |
|
|
54 | |
|
3.2.4 Nonblocking Conditions for the Banyan Network |
|
|
54 | |
|
|
59 | |
|
3.3.1 Basic Concepts of Comparison Networks |
|
|
61 | |
|
3.3.2 Sorting Networks Based on Bitonic Sort |
|
|
64 | |
|
3.3.3 The OddEven Sorting Network |
|
|
70 | |
|
3.3.4 Switching and Contention Resolution in Sort-Banyan Network |
|
|
71 | |
|
3.4 Nonblocking and Self-Routing Properties of Clos Networks |
|
|
75 | |
|
3.4.1 Nonblocking Route Assignment |
|
|
76 | |
|
3.4.2 Recursiveness Property |
|
|
79 | |
|
3.4.3 Basic Properties of Half-Clos Networks |
|
|
81 | |
|
3.4.4 Sort-Clos Principle |
|
|
89 | |
|
|
90 | |
4 Switch Performance Analysis and Design improvements |
|
95 | |
|
4.1 Performance of Simple Switch Designs |
|
|
95 | |
|
4.1.1 Throughput of an Internally Nonblocking Loss System |
|
|
96 | |
|
4.1.2 Throughput of an Input-Buffered Switch |
|
|
96 | |
|
4.1.3 Delay of an Input-Buffered Switch |
|
|
103 | |
|
4.1.4 Delay of an Output-Buffered Switch |
|
|
112 | |
|
4.2 Design Improvements for Input Queueing Switches |
|
|
113 | |
|
4.2.1 Look-Ahead Contention Resolution |
|
|
113 | |
|
4.2.2 Parallel Iterative Matching |
|
|
115 | |
|
4.3 Design Improvements Based on Output Capacity Expansion |
|
|
119 | |
|
|
119 | |
|
4.3.2 Channel-Grouping Principle |
|
|
121 | |
|
|
131 | |
|
4.3.4 Replication Principle |
|
|
137 | |
|
|
138 | |
|
|
144 | |
5 Advanced Switch Design Principles |
|
151 | |
|
5.1 Switch Design Principles Based on Deflection Routing |
|
|
151 | |
|
5.1.1 Tandem-Banyan Network |
|
|
151 | |
|
5.1.2 Shuffle-Exchange Network |
|
|
154 | |
|
5.1.3 Feedback Shuffle-Exchange Network |
|
|
158 | |
|
5.1.4 Feedback Bidirectional Shuffle-Exchange Network |
|
|
166 | |
|
5.1.5 Dual Shuffle-Exchange Network |
|
|
175 | |
|
5.2 Switching by Memory I/O |
|
|
184 | |
|
5.3 Design Principles for Scalable Switches |
|
|
187 | |
|
5.3.1 Generalized Knockout Principle |
|
|
187 | |
|
5.3.2 Modular Architecture |
|
|
191 | |
|
|
198 | |
6 Switching Principles for Multicast, Multirate, and Multimedia Services |
|
205 | |
|
|
205 | |
|
6.1.1 Multicasting Based on Nonblocking Copy Networks |
|
|
208 | |
|
6.1.2 Performance Improvement of Copy Networks |
|
|
213 | |
|
6.1.3 Multicasting Algorithm for Arbitrary Network Topologies |
|
|
220 | |
|
6.1.4 Nonblocking Copy Networks Based on Broadcast Clos Networks |
|
|
228 | |
|
|
235 | |
|
6.2.1 Basic Concept of Path Switching |
|
|
237 | |
|
6.2.2 Capacity and Route Assignments for Multirate Traffic |
|
|
242 | |
|
6.2.3 Trade-Off Between Performance and Complexity |
|
|
249 | |
|
6.2.4 Multicasting in Path Switching |
|
|
254 | |
|
|
268 | |
|
6.A.1 A Formulation of Effective Bandwidth |
|
|
268 | |
|
6.A.2 Approximations of Effective Bandwidth Based on OnOff Source Model |
|
|
269 | |
|
|
270 | |
7 Basic Concepts of Broadband Communication Networks |
|
275 | |
|
7.1 Synchronous Transfer Mode |
|
|
275 | |
|
7.2 Delays in ATM Network |
|
|
280 | |
|
7.3 Cell Size Consideration |
|
|
283 | |
|
7.4 Cell Networking, Virtual Channels, and Virtual Paths |
|
|
285 | |
|
|
285 | |
|
7.4.2 Cell Sequence Preservation |
|
|
286 | |
|
7.4.3 Virtual-Circuit Hop-by-Hop Routing |
|
|
286 | |
|
7.4.4 Virtual Channels and Virtual Paths |
|
|
287 | |
|
7.4.5 Routing Using VCI and VPI |
|
|
289 | |
|
7.4.6 Motivations for VP/VC Two-Tier Hierarchy |
|
|
293 | |
|
7.5 ATM Layer, Adaptation Layer, and Service Class |
|
|
295 | |
|
7.6 Transmission Interface |
|
|
300 | |
|
7.7 Approaches Toward IP over ATM |
|
|
300 | |
|
7.7.1 Classical IP over ATM |
|
|
301 | |
|
7.7.2 Next Hop Resolution Protocol |
|
|
302 | |
|
7.7.3 IP Switch and Cell Switch Router |
|
|
303 | |
|
7.7.4 ARIS and Tag Switching |
|
|
306 | |
|
7.7.5 Multiprotocol Label Switching |
|
|
308 | |
|
Appendix 7.A ATM Cell Format |
|
|
311 | |
|
|
311 | |
|
|
314 | |
|
|
319 | |
8 Network Traffic Control and Bandwidth Allocation |
|
323 | |
|
8.1 Fluid-Flow Model: Deterministic Discussion |
|
|
326 | |
|
8.2 Fluid-Flow OnOff Source Model: Stochastic Treatment |
|
|
332 | |
|
8.3 Traffic Shaping and Policing |
|
|
348 | |
|
8.4 Open-Loop Flow Control and Scheduling |
|
|
354 | |
|
8.4.1 First-Come-First-Serve Scheduling |
|
|
355 | |
|
8.4.2 Fixed-Capacity Assignment |
|
|
357 | |
|
8.4.3 Round-Robin Scheduling |
|
|
358 | |
|
8.4.4 Weighted Fair Queueing |
|
|
364 | |
|
8.4.5 Delay Bound in Weighted Fair Queueing with Leaky-Bucket Access Control |
|
|
373 | |
|
8.5 Closed-Loop Flow Control |
|
|
380 | |
|
|
381 | |
9 Packet Switching and Information Transmission |
|
385 | |
|
9.1 Duality of Switching and Transmission |
|
|
386 | |
|
9.2 Parallel Characteristics of Contention and Noise |
|
|
390 | |
|
9.2.1 Pseudo Signal-to-Noise Ratio of Packet Switch |
|
|
390 | |
|
9.2.2 Clos Network with Random Routing as a Noisy Channel |
|
|
393 | |
|
9.3 Clos Network with Deflection Routing |
|
|
396 | |
|
9.3.1 Cascaded Clos Network |
|
|
397 | |
|
9.3.2 Analysis of Deflection Clos Network |
|
|
397 | |
|
9.4 Route Assignments and Error-Correcting Codes |
|
|
402 | |
|
9.4.1 Complete Matching in Bipartite Graphs |
|
|
402 | |
|
|
405 | |
|
9.4.3 Route Assignments of Benes Network |
|
|
407 | |
|
9.5 Clos Network as Noiseless Channel-Path Switching |
|
|
410 | |
|
9.5.1 Capacity Allocation |
|
|
411 | |
|
9.5.2 Capacity Matrix Decomposition |
|
|
414 | |
|
9.6 Scheduling and Source Coding |
|
|
416 | |
|
9.6.1 Smoothness of Scheduling |
|
|
417 | |
|
9.6.2 Comparison of Scheduling Algorithms |
|
|
420 | |
|
9.6.3 Two-Dimensional Scheduling |
|
|
424 | |
|
|
430 | |
Bibliography |
|
433 | |