SØG - mellem flere end 8 millioner bøger:
Viser: Interconnections for Computer Communications and Packet Networks
Søgbar e-bog
Interconnections for Computer Communications and Packet Networks Vital Source e-bog
Roberto Rojas-Cessa
(2016)
Taylor & Francis
763,00 kr.
Leveres umiddelbart efter køb
Interconnections for Computer Communications and Packet Networks
Roberto Rojas-Cessa
(2017)
Sprog: Engelsk
Taylor & Francis Group
1.948,00 kr.
ikke på lager, Bestil nu og få den leveret
om ca. 10 hverdage
om ca. 10 hverdage
Detaljer om varen
- 1. Udgave
- Vital Source searchable e-book (Reflowable pages)
- Udgiver: Taylor & Francis (November 2016)
- ISBN: 9781315356037
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.
Licens varighed:
Bookshelf online: 5 år fra købsdato.
Bookshelf appen: ubegrænset dage fra købsdato.
Udgiveren oplyser at følgende begrænsninger er gældende for dette produkt:
Print: 2 sider kan printes ad gangen
Copy: højest 2 sider i alt kan kopieres (copy/paste)
Bookshelf online: 5 år fra købsdato.
Bookshelf appen: ubegrænset dage fra købsdato.
Udgiveren oplyser at følgende begrænsninger er gældende for dette produkt:
Print: 2 sider kan printes ad gangen
Copy: højest 2 sider i alt kan kopieres (copy/paste)
Detaljer om varen
- Hardback: 276 sider
- Udgiver: Taylor & Francis Group (Januar 2017)
- ISBN: 9781482226966
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.
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 Classifi cation
.
.
.
.
.
.
.
.
.
.
.
.
.
. 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
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 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 Classifi cation
.
.
.
.
.
.
.
.
.
.
.
.
.
. 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
De oplyste priser er inkl. moms
Butikker og åbningstid
Handler du som firma
Forretningsbetingelser
Porto og forsendelse
Data & cookiepolitik
Handler du som firma
Forretningsbetingelser
Porto og forsendelse
Data & cookiepolitik
Polyteknisk Boghandel og Forlag A/S - Anker Engelundsvej 1 - 2800 Lyngby
Tlf 77 42 43 44 - email poly@polyteknisk.dk - CVR 34072655 - Sydbank Reg: 6748 Konto 0001107927
Tlf 77 42 43 44 - email poly@polyteknisk.dk - CVR 34072655 - Sydbank Reg: 6748 Konto 0001107927