Interconnections for Computer Communications and Packet Networks: 1st Edition (Hardback) book cover

Interconnections for Computer Communications and Packet Networks

1st Edition

By Roberto Rojas-Cessa

CRC Press

276 pages | 13 Color Illus. | 140 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781482226966
pub: 2017-01-06
SAVE ~$33.00
$165.00
$132.00
x
eBook (VitalSource) : 9781315373485
pub: 2016-11-03
from $28.98


FREE Standard Shipping!

Description

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.

Reviews

"The organization of the book is very convenient. It is easy to read each part separately. Moving around the book is easy with a table of contents at the beginning of the book and separate tables of contents starting each chapter. In addition, every chapter ends with sample exercises. All parts of the book are richly illustrated with numerous figures. According to the saying that one image is worth a thousand words, drawings make it much easier for a reader to follow the discussion.

The book ends with a very solid bibliography containing 191 positions. The largest part of the bibliography gathers positions from the 1990s and 2000s, but some positions from the three most recent years are also included. Interested readers will then be able to broaden their self-studies on interconnection networks. The bibliography is followed by the useful terms index. In my opinion, this book is mostly aimed at undergraduate students interested in modern telecommunication and computer networks. Nevertheless, graduate students will also find this book a helpful textbook for their learning efforts."

—IEEE Communications Magazine, July 2017 Issue

Table of Contents

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

About the Author

Roberto Rojas-Cessa received a B.S. Degree in Electronic Instrumentation from Universidad Veracruzana, Mexico; a M.Sc. in Electrical Engineering from Center for Research and Advanced Studies and Research of the National Polytechnic Institute, Mexico; a M.Sc. degree in Computer Engineering; and a Ph.D. degree in Electrical Engineering from NYU Tandon School of Engineering, Brooklyn, NY.

Currently, Dr. Rojas-Cessa is an Associate Professor in the Department of Electrical and Computer Engineering, New Jersey Institute of Technology. He has been involved in the design and implementation of application specific integrated circuits (ASIC) for biomedical applications and high-speed computer communications, as well as the development of high-performance and large capacity packet switches. He was part of the team designing a 40 Tb/s core router in Coree, Inc, in Tinton Falls, NJ. His research interests include high-speed switching and routing, fault tolerance, quality-of-service networks, network measurements, and distributed systems. He is a co-author of the book "Advanced Internet Protocols, Services, and Applications," Wiley and Sons, 2012. Dr. Rojas-Cessa was a Visiting Professor in Thammasat University, Thailand. His research has been funded by U.S. National Science Foundation, Japan Society for the Promotion of Science, and other institutions.

Dr. Rojas-Cessa is involved in several technical and organizing committees of IEEE conferences, serves as a reviewer for a large number of technical journals, and is a member of the editorial board of the journals Conference Papers in Science and Elektronica. He has served as a reviewer and panelist for U.S. National Science Foundation and U.S. Department of Energy. He is the author of over 100 conference and journal papers and an inventor of 10 U.S. patents, with a similar number of patent applications pending. Additionally, Dr. Rojas-Cessa is the recipient of the "Excellence in Teaching Award 2013" from the Newark College of Engineering at NJIT. He is a Senior Member of IEEE and a Member of ACM. He has taught Introduction to Computer Architecture, Internet and Higher Layer Protocols, and High Performance Routers and Switches for over 10 years.

Subject Categories

BISAC Subject Codes/Headings:
COM011000
COMPUTERS / Systems Architecture / General
COM043000
COMPUTERS / Networking / General
COM059000
COMPUTERS / Computer Engineering