CONTENTS ix 7 INPUT-BUFFERED SWITCHES 225 7.1 Scheduling in VOQ-Based Switches /226 7.2 Maximum Matching /229 7.2.1 Maximum Weight Matching /229 7.2.2 Approximate MWM /229 7.2.3 Maximum Size Matching /230 7.3 Maximal Matching 231 7.3.1 Parallel Iterative Matching(PIM)/232 7.3.2 Iterative Round-Robin Matching(iRRM)/233 7.3.3 Iterative Round-Robin with SLIP (iSLIP)/234 7.3.4FIRM/241 7.3.5 Dual Round-Robin Matching(DRRM)/241 7.3.6 Pipelined Maximal Matching /245 7.3.7 Exhaustive Dual Round-Robin Matching (EDRRM)/248 7.4 Randomized Matching Algorithms 249 7.4.1 Randomized Algorithm with Memory /250 7.4.2 A Derandomized Algorithm with Memory 250 7.4.3 Variant Randomize Matching Algorithms /251 7.4.4 Polling Based Matching Algorithms /254 7.4.5 Simulated Performance /258 7.5 Frame-based Matching /262 7.5.1 Reducing the Reconfiguration Frequency /263 7.5.2 Fixed Size Synchronous Frame-Based Matching /267 7.5.3 Asynchronous Variable-Size Frame-Based Matching /270 7.6 Stable Matching with Speedup /273 7.6.1 Output-Queuing Emulation with Speedup of 4 274 7.6.2 Output-Queuing Emulation with Speedup of 2 /275 7.6.3 Lowest Output Occupancy Cell First(LOOFA)/278 8 BANYAN-BASED SWITCHES 284 8.1 Banyan Networks 284 8.2 Batcher-Sorting Network 287 8.3 Output Contention Resolution Algorithms /288 8.3.1 Three-Phase Implementation 288 8.3.2 Ring Reservation 288 8.4 The Sunshine Switch /292 8.5 Deflection Routing /294 8.5.1 Tandem Banyan Switch 294 8.5.2 Shuffle-Exchange Network with Deflection Routing /296 8.5.3 Dual Shuffle-Exchange Network with Error-Correcting Routing /297Book1099 — “ftoc” — 2007/2/16 — 21:26 — page ix — #5 CONTENTS ix 7 INPUT-BUFFERED SWITCHES 225 7.1 Scheduling in VOQ-Based Switches / 226 7.2 Maximum Matching / 229 7.2.1 Maximum Weight Matching / 229 7.2.2 Approximate MWM / 229 7.2.3 Maximum Size Matching / 230 7.3 Maximal Matching / 231 7.3.1 Parallel Iterative Matching (PIM) / 232 7.3.2 Iterative Round-Robin Matching (iRRM) / 233 7.3.3 Iterative Round-Robin with SLIP (iSLIP) / 234 7.3.4 FIRM / 241 7.3.5 Dual Round-Robin Matching (DRRM) / 241 7.3.6 Pipelined Maximal Matching / 245 7.3.7 Exhaustive Dual Round-Robin Matching (EDRRM) / 248 7.4 Randomized Matching Algorithms / 249 7.4.1 Randomized Algorithm with Memory / 250 7.4.2 A Derandomized Algorithm with Memory / 250 7.4.3 Variant Randomize Matching Algorithms / 251 7.4.4 Polling Based Matching Algorithms / 254 7.4.5 Simulated Performance / 258 7.5 Frame-based Matching / 262 7.5.1 Reducing the Reconfiguration Frequency / 263 7.5.2 Fixed Size Synchronous Frame-Based Matching / 267 7.5.3 Asynchronous Variable-Size Frame-Based Matching / 270 7.6 Stable Matching with Speedup / 273 7.6.1 Output-Queuing Emulation with Speedup of 4 / 274 7.6.2 Output-Queuing Emulation with Speedup of 2 / 275 7.6.3 Lowest Output Occupancy Cell First (LOOFA) / 278 8 BANYAN-BASED SWITCHES 284 8.1 Banyan Networks / 284 8.2 Batcher-Sorting Network / 287 8.3 Output Contention Resolution Algorithms / 288 8.3.1 Three-Phase Implementation / 288 8.3.2 Ring Reservation / 288 8.4 The Sunshine Switch / 292 8.5 Deflection Routing / 294 8.5.1 Tandem Banyan Switch / 294 8.5.2 Shuffle-Exchange Network with Deflection Routing / 296 8.5.3 Dual Shuffle-Exchange Network with Error-Correcting Routing / 297