Other Titles: Computer communications and packet networks

Includes bibliographical references and index.

Preface Organization of the Book ... xvi Suggested Coverage ... xvii Acknowledgments xix I Processor Interconnections 1 1 Multiprocessor Interconnection Networks 3 1.1 Introduction ... 4 1.1.1 Multiprocessor Computing Architectures ... 5 1.1.1.1 SIMD Machines ... 5 1.1.1.2 Multiple SIMD Machines ... 5 1.1.1.3 MIMD Machines ... 5 1.1.2 Multiprocessor vs. Multicomputer Systems ... 6 1.1.2.1 Need for an Interconnection Network ... 6 1.1.3 Topology of Interconnect Networks ... 7 1.2 Direct Networks ... 7 1.2.1 Mesh Interconnect Networks ... 8 1.2.1.1 Torus Network ... 9 1.2.1.2 Ring Interconnection Network (1D Torus) . . 10 1.2.2 Honeycomb Networks ... 10 1.2.2.1 Honeycomb Mesh Network ... 10 1.2.2.2 Honeycomb Tori Network ... 11 1.2.3 Hypercube (Binary n-Cube) ... 11 1.2.4 k-Ary n-Cube ... 13 1.2.5 Tree Interconnection Networks ... 14 1.2.5.1 Hyper Tree ... 16 1.2.6 Fully Connected Network ... 18 1.3 Indirect Networks ... 18 1.3.1 Single-Stage Interconnection Networks ... 19 1.3.1.1 Crossbar Network ... 19 1.3.2 Multistage Interconnect Networks ... 21 1.3.2.1 General Form of a Multistage Interconnect . 21 1.3.3 Unidirectional MINs ... 22 1.3.3.1 Buttery (k-ary n-y) Network ... 23 1.3.3.2 Omega Network ... 23 1.3.4 Bidirectional MINs ... 24 1.3.4.1 Fat-Tree Network ... 24 1.3.5 Design Constraints ... 25 1.4 Further Reading ... 27 1.5 Exercises ... 27 2 Routing 29 2.1 Introduction ... 29 2.2 Deterministic (Static) Routing ... 30 2.2.1 Destination-Tag Routing in Buttery Networks ... 30 2.2.2 Dimension-Order Routing in Cube Networks ... 31 2.3 Oblivious Routing ... 32 2.3.1 Valiant's Randomized Routing Algorithm ... 33 2.3.1.1 Valiant's Algorithm on Torus Topologies . . 33 2.3.2 Minimal Oblivious Routing ... 34 2.3.2.1 Minimal Oblivious Routing on a Folded-Clos Network (Fat-Tree) ... 34 2.3.2.2 Minimal Oblivious Routing on a Torus: ... 35 2.3.2.3 Load-Balanced Oblivious Routing ... 37 2.4 Adaptive Routing ... 38 2.4.1 Minimal Adaptive Routing ... 39 2.4.2 Fully Adaptive Routing ... 40 2.4.3 Load-Balanced Adaptive Routing ... 41 2.4.4 Search-Based Adaptive Routing ... 42 2.5 Exercises ... 43 II Data Networks 45 3 Internet Protocol (IP) Address Lookup 47 3.1 Introduction ... 48 3.2 Basic Binary Tree ... 50 3.3 Disjoint Trie ... 52 3.3.1 Procedure to Build a Disjoint Trie ... 53 3.4 Path-Compressed Trie ... 54 3.5 Multibit Trie ... 55 3.6 Level-Compressed Trie ... 56 3.7 Lulea Algorithm ... 58 3.7.1 Number of Prefix Levels ... 59 3.7.2 Representation of Prexes as a Bit Vector ... 59 3.7.2.1 Code Field and Maptable ... 62 3.7.2.2 Code Field ... 63 3.7.2.3 Lulea Matching Process ... 65 3.8 DIR-24-8 Scheme ... 66 3.9 Bloom Filter-Based Algorithm ... 67 3.9.0.4 IP Address Lookup Using a Bloom Filter . . 68 3.10 Helix: A Parallel-Search Lookup Scheme ... 71 3.11 Ternary Content-Addressable Memory ... 75 3.12 Additional Readings ... 78 3.13 Exercises ... 78 4 Packet Classification 81 4.1 Introduction to Packet Classification ... 81 4.2 Trie-Based Packet Classification Schemes ... 84 4.2.1 Hierarchical Trie ... 84 4.2.2 Set Pruning Trie ... 86 4.2.3 Grid of Tries ... 87 4.3 Geometric Schemes ... 87 4.3.1 Crossproduct Scheme ... 88 4.3.2 Hierarchical Intelligent Cuttings (HiCuts) ... 89 4.4 Heuristics Schemes ... 91 4.4.1 Recursive Flow Classification ... 91 4.5 Additional Readings ... 96 4.6 Exercises ... 96 5 Basics of Packet Switching 99 5.1 Introduction ... 100 5.2 Circuit Switching ... 100 5.3 Packet Switching ... 101 5.4 Routers and Switches ... 102 5.4.1 Basic Terms ... 103 5.4.1.1 Output Contention ... 103 5.4.1.2 Blocking and Nonblocking Fabrics ... 103 5.4.2 Classification of Switches ... 104 5.4.2.1 Number of Stages ... 104 5.4.2.2 Number of Paths ... 107 5.4.2.3 Queueing Strategies ... 107 5.4.3 Time and Space Switching ... 107 5.4.4 Managing Internet Packets in a Switch ... 108 5.4.4.1 Segmentation and Reassembly ... 108 5.4.4.2 Cell-Based Forwarding ... 109 5.4.4.3 Packet-Based Forwarding ... 109 5.5 Performance Metrics ... 110 5.5.1 Throughput ... 110 5.5.2 Latency ... 111 5.5.2.1 Queueing Delay ... 111 5.5.2.2 Processing Delay ... 112 5.5.3 Internal Transmission Speed and Bit Slicing ... 112 5.5.4 Speedup ... 112 5.5.5 Unicasting and Multicasting ... 113 5.5.5.1 Unicasting ... 113 5.5.5.2 Multicasting ... 113 5.5.5.3 Multicast Queueing ... 114 5.5.5.4 Multicast Scheduling ... 114 5.6 Traffic Patterns ... 114 5.6.1 Admissible Traffic ... 115 5.6.2 Arrival Distributions ... 115 5.6.2.1 Bernoulli and Poisson Arrivals ... 115 5.6.2.2 Bursty On-Off Traffic ... 116 5.6.3 Destination Distributions ... 116 5.6.3.1 Independent and Identically Distributed Traffic ... 117 5.6.3.2 Uniform Distribution ... 117 5.6.3.3 Nonuniform Distribution ... 117 5.6.3.4 Independent, Nonidentical, and Nonuniformly Distributed Traffic ... 118 5.7 Ideal Packet Switch: Output Queueing ... 119 5.8 Exercises ... 121 6 Input-Queued Switches 123 6.1 Introduction ... 124 6.2 Input-Queued Switch with FIFO ... 124 6.3 Virtual Output Queue (VOQ) Switches ... 126 6.4 Weight and Size Matching ... 127 6.5 Maximum Weight Matching (MWM) ... 128 6.6 Maximal-Weight Matching ... 129 6.6.1 Iterative Longest Queue First (iLQF) ... 130 6.6.2 Iterative Oldest Cell First (iOCF) ... 131 6.7 Size-Matching Schemes ... 132 6.7.1 Parallel Interactive Matching (PIM) ... 132 6.7.2 Iterative Round-Robin Matching (iRRM) ... 133 6.7.3 Round-Robin with Slip (iSLIP) ... 135 6.7.4 Dual Round-Robin Matching (DRRM) ... 135 6.7.5 Round-Robin with Exhaustive Service ... 137 6.8 Frame-Based Matching ... 140 6.8.1 Frame Size Occupancy-Based Schemes ... 140 6.8.1.1 Unlimited Frame-Size Occupancy based PIM (uFPIM) ... 141 6.8.1.2 Unlimited Framed-Size Occupancy based Round Robin Matching (uFORM) ... 142 6.9 Output-Queued Switch Emulation ... 143 6.10 Exercises ... 144 7 Shared-Memory Packet Switches 149 7.1 Introduction ... 149 7.2 Basics of a Shared-Memory Packet Switch ... 150 7.2.1 Shared-Memory Packet Switches with Multiple Memory Blocks ... 152 7.3 Shared-Memory Crosspoint Buffered Switch with Memory Allocation and Speedup of m (SMCBm)... 153 7.4 Shared-Memory Crosspoint Buffered Switch with Input-Crosspoint Matching (mSMCB) ... 155 7.5 Shared-Memory Switch with Memory Shared by Output Ports 159 7.6 Performance Analysis of Shared-Memory Switches ... 160 7.7 Buffer Management for Shared-Memory Switches ... 162 7.7.1 Static Threshold-Based schemes ... 162 7.7.2 Push-Out Schemes ... 163 7.7.3 Dynamic Schemes ... 163 7.8 Exercises ... 164 8 Internally Buffered Packet Switches 169 8.1 Introduction ... 170 8.2 Buffered-Crossbar Switch ... 170 8.3 Combined Input-Crosspoint Buffered (CICB) Packet Switch 171 8.3.1 CICB with First-In First-Out (FIFO) Input Buffers . 171 8.3.2 CICB with Virtual Output Queues at Inputs ... 172 8.3.3 Separating Arbitration in CICB Switches ... 174 8.3.4 Flow Control Mechanism ... 175 8.4 Arbitration Schemes for CICB Switches ... 175 8.4.1 Oldest-Cell First (OCF) and Round-Robin Arbitrations 175 8.4.2 Longest Queue First and Round-Robin Arbitration . . 176 8.4.3 Most Critical Internal Buffer First ... 176 8.4.4 Round-Robin (RR) Arbitration ... 177 8.4.5 Round-Robin with Adaptable Frame Size (RR-AF) Arbitration Scheme ... 179 8.5 Switching Internal Variable-Length Packets ... 181 8.6 Exercises ... 182 9 Load-Balancing Switches 183 9.1 Introduction ... 183 9.2 Load Decomposition in Packet Switches ... 184 9.3 Load-Balanced Birkhoff-von Neumann Switches ... 187 9.4 Out-of-Sequence Forwarding in Load-Balanced Switches ... 190 9.4.1 Bounding the Number of Out-of-Sequence Cells ... 190 9.4.1.1 First-Come First-Serve (FCFS) ... 190 9.4.1.2 Earlier Deadline First (EDF) ... 190 9.4.2 Preventing Out-of-Sequence Forwarding ... 191 9.4.2.1 Full Frame First (FFF) [92] ... 191 9.5 Load-Balanced Combined-Input Crosspoint-Buffered Switches 193 9.5.1 Load-Balanced CICB Switch with Full Access to Crosspoint Buffers (LB-CICB-FA) ...194 9.5.2 Load-Balanced CICB Switch with Single Access (LBCICB-SA) ... 197 9.5.3 Switch Performance Analysis ... 201 9.6 Exercises ... 205 10 Clos-Network Packet Switches 207 10.1 Introduction ... 207 10.2 Clos Networks ... 208 10.2.1 Clos Network with More than Three Stages ... 211 10.3 Queueing in Clos-Network Switches ... 211 10.3.1 Space-Space-Space (S3) Switches ... 213 10.3.1.1 Port-First Matching Scheme ... 213 10.3.1.2 Module-First Matching (MoM) Scheme ... 214 10.3.2 Memory-Space-Memory (MSM) Switches ... 217 10.3.2.1 Round-Robin Matching in MSM Switches . . 218 10.3.3 Memory Memory Memory (MMM) Switches ... 221 10.3.3.1 MMM with Extended Queues (MMeM) ... 222 10.3.4 Space-Space-Memory (SSM) Switches ... 223 10.3.4.1 Weighted Central Module Link Matching (WCMM) ... 224 10.4 Exercises ... 230 11 Buffer Management in Routers 231 11.1 Tail Drop ... 231 11.2 Random Early Detection (RED) ... 232 11.3 Weighted Random Early Detection (WRED) ... 235 11.4 Fair Random Early Detection (FRED) ... 236 11.5 Adaptive Random Early Detection (ARED) ... 237 11.6 Differential Dropping (RIO) ... 238 11.7 Exercises ... 239 III Data-Center Networks 243 12 Data Center Networks 245 12.1 Introduction ... 245 12.2 Switch-Centric Architectures ... 246 12.2.1 Three-Tier Network ... 246 12.2.2 Fat-Tree Network ... 247 12.2.3 VL2 Network ... 247 12.3 Server-Centric Architectures ... 248 12.3.1 CamCube ... 248 12.4 Hybrid Architectures ... 249 12.4.1 DCell ... 249 12.4.2 BCube ... 250 12.4.3 C-Through ... 251 12.4.4 Helios ... 253 12.4.5 MDCube ... 254 12.5 Exercises ... 255 Bibliography 257 Index 275

This book introduces different interconnection networks applied to different systems. Interconnection networks are used to communicate processing units in a multi-processor system, routers in communication networks,and servers in data centers. Queuing techniques are applied to interconnection networks to support a higher utilization of resources. There are different queuing strategies, and these determine not only the performance of the interconnection network, but also the set of requirements to make them work effectively and their cost. Routing algorithms are used to find routes to destinations and directions in what information travels. Additional properties, such as avoiding deadlocks and congestion, are sought. Effective routing algorithms need to be paired up with these networks. The book will introduce the most relevant interconnection networks, queuing strategies, and routing algorithm. It discusses their properties and how these leverage the performance of the whole interconnection system. In addition, the book covers additional topics for memory management and congestion avoidance, used to extract higher performance from the interconnection network.