CONTENTS xi 11.2 Combined Input and Crosspoint Buffered Switches with VOQ 370 11.2.1 CIXB with One-Cell Crosspoint Buffers (CIXB-1)/371 11.2.2 Throughput and Delay Performance 371 11.2.3 Non-Negligible Round-Trip Times in CIXB-k 376 11.3 OCF_OCF:Oldest Cell First Scheduling /376 11.4 LQF_RR:Longest Queue First and Round-Robin Scheduling in CIXB-1 378 11.5 MCBF:Most Critical Buffer First Scheduling /379 12 CLOS-NETWORK SWITCHES 382 12.1 Routing Property of Clos Network Switches /383 12.2 Looping Algorithm 387 12.3 m-Matching Algorithm /388 12.4 Euler Partition Algorithm /388 12.5 Karol's Algorithm /389 12.6 Frame-Based Matching Algorithm for Clos Network(f-MAC)/391 12.7 Concurrent Matching Algorithm for Clos Network(c-MAC)/392 12.8 Dual-Level Matching Algorithm for Clos Network (d-MAC)/395 12.9 The ATLANTA Switch 398 12.10 Concurrent Round-Robin Dispatching(CRRD)Scheme /400 12.11 The Path Switch 404 12.11.1 Homogeneous Capacity and Route Assignment /406 12.11.2 Heterogeneous Capacity Assignment /408 13 MULTI-PLANE MULTI-STAGE BUFFERED SWITCH 413 13.1 TrueWay Switch Architecture /414 13.1.1 Stages of the Switch /415 13.2 Packet Scheduling /417 13.2.1 Partial Packet Interleaving (PPD)/419 13.2.2 Dynamic Packet Interleaving (DPI)/419 13.2.3 Head-of-Line (HOL)Blocking /420 13.3 Stage-To-Stage Flow Control /420 13.3.1 Back-Pressure /421 13.3.2 Credit-Based Flow Control /421 13.3.3 The DQ Scheme /422 13.4 Port-To-Port Flow Control /424 13.4.1 Static Hashing /424 13.4.2 Dynamic Hashing /425 13.4.3 Time-Stamp-Based Resequence /428 13.4.4 Window-Based Resequence /428Book1099 — “ftoc” — 2007/2/16 — 21:26 — page xi — #7 CONTENTS xi 11.2 Combined Input and Crosspoint Buffered Switches with VOQ / 370 11.2.1 CIXB with One-Cell Crosspoint Buffers (CIXB-1) / 371 11.2.2 Throughput and Delay Performance / 371 11.2.3 Non-Negligible Round-Trip Times in CIXB-k / 376 11.3 OCF_OCF: Oldest Cell First Scheduling / 376 11.4 LQF_RR: Longest Queue First and Round-Robin Scheduling in CIXB-1 / 378 11.5 MCBF: Most Critical Buffer First Scheduling / 379 12 CLOS-NETWORK SWITCHES 382 12.1 Routing Property of Clos Network Switches / 383 12.2 Looping Algorithm / 387 12.3 m-Matching Algorithm / 388 12.4 Euler Partition Algorithm / 388 12.5 Karol’s Algorithm / 389 12.6 Frame-Based Matching Algorithm for Clos Network (f-MAC) / 391 12.7 Concurrent Matching Algorithm for Clos Network (c-MAC) / 392 12.8 Dual-Level Matching Algorithm for Clos Network (d-MAC) / 395 12.9 The ATLANTA Switch / 398 12.10 Concurrent Round-Robin Dispatching (CRRD) Scheme / 400 12.11 The Path Switch / 404 12.11.1 Homogeneous Capacity and Route Assignment / 406 12.11.2 Heterogeneous Capacity Assignment / 408 13 MULTI-PLANE MULTI-STAGE BUFFERED SWITCH 413 13.1 TrueWay Switch Architecture / 414 13.1.1 Stages of the Switch / 415 13.2 Packet Scheduling / 417 13.2.1 Partial Packet Interleaving (PPI) / 419 13.2.2 Dynamic Packet Interleaving (DPI) / 419 13.2.3 Head-of-Line (HOL) Blocking / 420 13.3 Stage-To-Stage Flow Control / 420 13.3.1 Back-Pressure / 421 13.3.2 Credit-Based Flow Control / 421 13.3.3 The DQ Scheme / 422 13.4 Port-To-Port Flow Control / 424 13.4.1 Static Hashing / 424 13.4.2 Dynamic Hashing / 425 13.4.3 Time-Stamp-Based Resequence / 428 13.4.4 Window-Based Resequence / 428