Librería Portfolio

Features

Introduces Interconnection networks in simple and understandable terms
Covers interconnection legacy to state-of-the-art topologies
Describes emerging applications of interconnection for processors, networks, and datacenters
Presents the readers with interconnection concepts in terms that are simple to understand and from simple to new technologies in a concise manner
Summary

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.



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