| List of Contributors | p. xi |
| Architectures of Internet Switches and Routers | p. 1 |
| Introduction | p. 2 |
| Bufferless Crossbar Switches | p. 3 |
| Introduction to Switch Fabrics | p. 3 |
| Output-queued Switches | p. 4 |
| Input-queued Switches | p. 4 |
| Scheduling Algorithms for VOQ Switches | p. 5 |
| Combined Input-Ouput-queued Switches | p. 9 |
| Buffered Crossbar Switches | p. 12 |
| Buffered Crossbar Switches Overview | p. 12 |
| The VOQ/BCS Architecture | p. 13 |
| Multi-stage Switching | p. 19 |
| Architecture Choice | p. 19 |
| The MSM Clos-network Architecture | p. 20 |
| The Bufferless Clos-network Architecture | p. 23 |
| Optical Packet Switching | p. 27 |
| Multi-rack Hybrid Opto-electronic Switch Architecture | p. 27 |
| Optical Fabrics | p. 28 |
| Reduced Rate Scheduling | p. 30 |
| Time Slot Assignment Approach | p. 30 |
| Double Algorithm | p. 32 |
| Adjust Algorithm | p. 32 |
| Conclusion | p. 34 |
| Theoretical Performance of Input-queued Switches Using Lyapunov Methodology | p. 39 |
| Introduction | p. 39 |
| Theoretical Framework | p. 41 |
| Description of the Queueing System | p. 41 |
| Stability Definitions for a Queueing System | p. 43 |
| Lyapunov Methodology | p. 44 |
| Lyapunov Methodology to Bound Queue Sizes and Delays | p. 47 |
| Application to a Single Queue | p. 48 |
| Final Remarks | p. 49 |
| Performance of a Single Switch | p. 50 |
| Stability Region of Pure Input-queued Switches | p. 51 |
| Delay Bounds for Maximal Weight Matching | p. 54 |
| Stability Region of CIOQ with Speedup 2 | p. 55 |
| Scheduling Variable-size Packets | p. 57 |
| Networks of IQ Switches | p. 58 |
| Theoretical Performance | p. 59 |
| Conclusions | p. 61 |
| Adaptive Batched Scheduling for Packet Switching with Delays | p. 65 |
| Introduction | p. 65 |
| Switching Modes with Delays: A General Model | p. 66 |
| Batch Scheduling Algorithms | p. 69 |
| Fixed Batch Policies | p. 70 |
| Adaptive Batch Policies | p. 72 |
| The Simple-batch Static Schedule | p. 73 |
| An Interesting Application: Optical Networks | p. 74 |
| Throughput Maximization via Adaptive Batch Schedules | p. 76 |
| Summary | p. 78 |
| Geometry of Packet Switching: Maximal Throughput Cone Scheduling Algorithms | p. 81 |
| Introduction | p. 81 |
| Backlog Dynamics of Packet Switches | p. 84 |
| Switch Throughput and Rate Stability | p. 86 |
| Cone Algorithms for Packet Scheduling | p. 88 |
| Projective Cone Scheduling (PCS) | p. 89 |
| Relaxation, Generalizations, and Delayed PCS (D-PCS) | p. 90 |
| Argument Why PCS and D-PCS Maximize Throughput | p. 92 |
| Quality of Service and Load Balancing | p. 93 |
| Complexity in Cone Schedules - Scalable PCS Algorithms | p. 95 |
| Approximate PCS | p. 95 |
| Local PCS | p. 95 |
| Final Remarks | p. 98 |
| Fabric on a Chip: A Memory-management Perspective | p. 101 |
| Introduction | p. 101 |
| Benefits of the Fabric-on-a-Chip Approach | p. 102 |
| Emulating an Output-queued Switch | p. 103 |
| Packet Placement Algorithm | p. 105 |
| Switch Architecture | p. 105 |
| Memory-management Algorithm and Related Resourses | p. 106 |
| Sufficiency Condition on the Number of Memories | p. 109 |
| Implementation Considerations | p. 114 |
| Logic Dataflow | p. 114 |
| FPGA Implementation Results | p. 119 |
| Conclusions | p. 120 |
| Packet Switch with Internally Buffered Crossbars | p. 121 |
| Introduction to Packet Switches | p. 121 |
| Crossbar-based Switches | p. 122 |
| Internally Buffered Crossbars | p. 124 |
| Combined Input-Crosspoint Buffered (CICB) Crossbars | p. 126 |
| FIFO-CICO Switches | p. 126 |
| VOQ-CICB Switches | p. 128 |
| Separating Matching into Input and Output Arbitrations | p. 130 |
| Weighted Arbitration Schemes | p. 130 |
| Arbitration Schemes based on Round-robin Selection | p. 135 |
| CICB Switches with Internal Variable-length Packets | p. 141 |
| Output Emulation by CICB Switches | p. 141 |
| Conclusions | p. 144 |
| Dual Scheduling Algorithm in a Generalized Switch: Asymptotic Optimality and Throughput Optimality | p. 147 |
| Introduction | p. 148 |
| System Model | p. 150 |
| Queue Length Dynamics | p. 151 |
| Dual Scheduling Algorithm | p. 152 |
| Asymptotic Optimality and Fairness | p. 153 |
| An Ideal Reference System | p. 153 |
| Stochastic Stability | p. 154 |
| Asymptotic Optimality and Fairness | p. 155 |
| Throughput-optimal Scheduling | p. 159 |
| Throughput Optimality and Fairness | p. 159 |
| Optimality Proof | p. 160 |
| Flows with Exponentially Distributed Size | p. 163 |
| A New Scheduling Architecture | p. 165 |
| Conclusions | p. 166 |
| The Combined Input and Crosspoint Queued Switch | p. 169 |
| Introduction | p. 169 |
| History of the CICQ Switch | p. 172 |
| Performance of CICQ Cell Switching | p. 175 |
| Traffic Models | p. 176 |
| Simulation Experiments | p. 177 |
| Performance of CICQ Packet Switching | p. 179 |
| Traffic Models | p. 179 |
| Simulation Experiments | p. 179 |
| Design of Fast Round-robin Arbiters | p. 181 |
| Existing RR Arbiter Designs | p. 182 |
| A New Short-term Fair RR Arbiter - The Masked Priority Encoder (MPE) | p. 183 |
| A New Fast Long-term Fair RR Arbiter - The Overlapped RR (ORR) Arbiter | p. 186 |
| Future Directions - The CICQ with VCQ | p. 188 |
| Design of Virtual Crosspoint Queueing (VCQ) | p. 189 |
| Evaluation of CICQ Cell Switch with VCQ | p. 190 |
| Summary | p. 192 |
| Time-Space Label Switching Protocol (TSL-SP) | p. 197 |
| Introduction | p. 197 |
| Time Label | p. 198 |
| Space Label | p. 200 |
| Time-Space Label Switching Protocol (TSL-SP) | p. 201 |
| Illustrative Results | p. 205 |
| Summary | p. 209 |
| Hybrid Open Hash Tables for Network Processors | p. 211 |
| Introduction | p. 211 |
| Conventional Hash Algorithms | p. 213 |
| Chained Hash Tables | p. 214 |
| Open Hash Tables | p. 215 |
| Performance Degradation Problem | p. 216 |
| Improvements | p. 218 |
| Hybrid Open Hash Tables | p. 219 |
| Basic Operations | p. 219 |
| Basic Ideas | p. 219 |
| Performance Evaluation | p. 220 |
| Hybrid Open Hash Table Enhancement | p. 222 |
| Flaws of Hybrid Open Hash Table | p. 222 |
| Dynamic Enhancement | p. 223 |
| Adaptative Enhancement | p. 224 |
| Timeout Enhancement | p. 224 |
| Performance Evaluation | p. 224 |
| Extended Discussions of Concurrency Issues | p. 225 |
| Insertion | p. 225 |
| Clean-to-copy Phase Change | p. 226 |
| Timestamps | p. 227 |
| Conclusion | p. 227 |
| Index | p. 229 |
| Table of Contents provided by Publisher. All Rights Reserved. |
