PRAISE FOR
PRINCIPLES AND PRACTICES OF INTERCONNECTION NETWORKS
The scholarship of this book is unparalleled in its area. This text is for interconnection networks what Hennessy and Patterson’s text is for computer architecture — an authoritative, one-stop source that clearly and methodically explains the
more significant concepts. Treatment of the material both in breadth and in depth is
very well done . . . a must read and a slam dunk! — Timothy Mark Pinkston, University of Southern California
[This book is] the most comprehensive and coherent work on modern interconnection networks. As leaders in the field, Dally and Towles capitalize on their vast
experience as researchers and engineers to present both the theory behind such networks and the practice of building them. This book is a necessity for anyone studying,
analyzing, or designing interconnection networks. — Stephen W. Keckler, The University of Texas at Austin
This book will serve as excellent teaching material, an invaluable research reference, and a very handy supplement for system designers. In addition to documenting
and clearly presenting the key research findings, the book’s incisive practical treatment is unique. By presenting how actual design constraints impact each facet of
interconnection network design, the book deftly ties theoretical findings of the past
decades to real systems design. This perspective is critically needed in engineering
education. — Li-Shiuan Peh, Princeton University
Principles and Practices of Interconnection Networks is a triple threat: comprehensive, well written and authoritative. The need for this book has grown with the
increasing impact of interconnects on computer system performance and cost. It
will be a great tool for students and teachers alike, and will clearly help practicing
engineers build better networks. — Steve Scott, Cray, Inc.
Dally and Towles use their combined three decades of experience to create a
book that elucidates the theory and practice of computer interconnection networks.
On one hand, they derive fundamentals and enumerate design alternatives. On the
other, they present numerous case studies and are not afraid to give their experienced opinions on current choices and future trends. This book is a "must buy" for
those interested in or designing interconnection networks. — Mark Hill, University
of Wisconsin, Madison
This book will instantly become a canonical reference in the field of interconnection networks. Professor Dally’s pioneering research dramatically and permanently
changed this field by introducing rigorous evaluation techniques and creative solutions to the challenge of high-performance computer system communication. This
well-organized textbook will benefit both students and experienced practitioners.
The presentation and exercises are a result of years of classroom experience in creating this material. All in all, this is a must-have source of information. — Craig
Stunkel, IBM

This
. Page Intentionally Left Blank


Principles and Practices of
Interconnection Networks


This
. Page Intentionally Left Blank


Principles and Practices of
Interconnection Networks

William James Dally

Brian Towles


Publishing Director:
Senior Editor:
Publishing Services Manager:
Project Manager:
Editorial Coordinator:
Editorial Assistant:
Cover Design:
Cover Image:
Text Design:
Composition:

Copyeditor:
Proofreader:
Indexer:
Interior printer
Cover printer

Diane D. Cerra
Denise E. M. Penrose
Simon Crump
Marcy Barnes-Henrie
Alyson Day
Summer Block
Hannus Design Associates
Frank Stella, Takht-i-Sulayan-I (1967)
Rebecca Evans & Associates
Integra Software Services Pvt., Ltd.
Catherine Albano
Deborah Prato
Sharon Hilgenberg
The Maple-Vail Book Manufacturing Group
Phoenix Color Corp.

Morgan Kaufmann Publishers is an imprint of Elsevier
500 Sansome Street, Suite 400, San Francisco, CA 94111
This book is printed on acid-free paper.
c 2004 by Elsevier, Inc. All rights reserved.
Figure 3.10 c 2003 Silicon Graphics, Inc. Used by permission. All rights reserved.
Figure 3.13 courtesy of the Association for Computing Machinery (ACM), from James Laudon and
Daniel Lenoski, “The SGI Origin: a ccNUMA highly scalable server,” Proceedings of the International
Symposium on Computer Architecture (ISCA), pp. 241-251, 1997. (ISBN: 0897919017) Figure 10.

Figure 10.7 from Thinking Machines Corp.
Figure 11.5 courtesy of Ray Mains, Ray Mains Photography,
/>Designations used by companies to distinguish their products are often claimed as trademarks or
registered trademarks. In all instances in which Morgan Kaufmann Publishers is aware of a claim, the
product names appear in initial capital or all capital letters. Readers, however, should contact the
appropriate companies for more complete information regarding trademarks and registration.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
or by any means—electronic, mechanical, photocopying, or otherwise—without written permission of
the publishers.
Permissions may be sought directly from Elsevier’s Science & Technology Rights
Department in Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail:
You may also complete your request on-line via the Elsevier homepage
() by selecting "Customer Support" and then "Obtaining Permissions."
Library of Congress Cataloging-in-Publication Data
Dally, William J.
Principles and practices of interconnection networks / William
Dally, Brian Towles.
p. cm.
Includes bibliographical references and index.
ISBN 0-12-200751-4 (alk. paper)
1. Computer networks-Design and construction.
2. Multiprocessors. I. Towles, Brian. II. Title.
TK5105.5.D3272003
004.6’5–dc22
ISBN: 0-12-200751-4
For information on all Morgan Kaufmann publications,
visit our Web Site at www.mkp.com
Printed in the United States of America
04 05 06 07 08
5 4 3 2 1


2003058915


Contents

Acknowledgments

xvii

Preface

xix

About the Authors

xxv

Chapter 1 Introduction to Interconnection Networks
1.1
1.2

1.3

1.4
1.5

Three Questions About Interconnection Networks
Uses of Interconnection Networks
1.2.1 Processor-Memory Interconnect 5

1.2.2 I/O Interconnect 8
1.2.3 Packet Switching Fabric 11
Network Basics
1.3.1 Topology 13
1.3.2 Routing 16
1.3.3 Flow Control 17
1.3.4 Router Architecture 19
1.3.5 Performance of Interconnection Networks 19
History
Organization of this Book

1
2
4

13

21
23

Chapter 2 A Simple Interconnection Network

25

2.1
2.2
2.3
2.4
2.5
2.6

2.7

25
27
31
32
33
36
42

Network Specifications and Constraints
Topology
Routing
Flow Control
Router Design
Performance Analysis
Exercises

vii


viii

Contents

Chapter 3
3.1

3.2
3.3


3.4
3.5
3.6
3.7

Nomenclature
3.1.1 Channels and Nodes 46
3.1.2 Direct and Indirect Networks 47
3.1.3 Cuts and Bisections 48
3.1.4 Paths 48
3.1.5 Symmetry 49
Traffic Patterns
Performance
3.3.1 Throughput and Maximum Channel Load
3.3.2 Latency 55
3.3.3 Path Diversity 57
Packaging Cost
Case Study: The SGI Origin 2000
Bibliographic Notes
Exercises

Chapter 4
4.1
4.2
4.3
4.4
4.5
4.6
4.7


5.3
5.4
5.5
5.6
5.7

Butterfly Networks

The Structure of Butterfly Networks
Isomorphic Butterflies
Performance and Packaging Cost
Path Diversity and Extra Stages
Case Study: The BBN Butterfly
Bibliographic Notes
Exercises

Chapter 5
5.1
5.2

Topology Basics

45
46

50
51
51


60
64
69
69

75
75
77
78
81
84
86
86

Torus Networks

89

The Structure of Torus Networks
Performance
5.2.1 Throughput 92
5.2.2 Latency 95
5.2.3 Path Diversity 96
Building Mesh and Torus Networks
Express Cubes
Case Study: The MIT J-Machine
Bibliographic Notes
Exercises

90

92

98
100
102
106
107


Contents

ix

Chapter 6 Non-Blocking Networks

111

6.1
6.2
6.3

112
112
116

6.4
6.5
6.6
6.7
6.8


Non-Blocking vs. Non-Interfering Networks
Crossbar Networks
Clos Networks
6.3.1 Structure and Properties of Clos Networks 116
6.3.2 Unicast Routing on Strictly Non-Blocking
Clos Networks 118
6.3.3 Unicast Routing on Rearrangeable Clos Networks 122
6.3.4 Routing Clos Networks Using Matrix
Decomposition 126
6.3.5 Multicast Routing on Clos Networks 128
6.3.6 Clos Networks with More Than Three Stages 133
Beneˇs Networks
Sorting Networks
Case Study: The Velio VC2002 (Zeus) Grooming Switch
Bibliographic Notes
Exercises

134
135
137
142
142

Chapter 7 Slicing and Dicing

145

7.1


146

7.2

7.3
7.4
7.5
7.6

Concentrators and Distributors
7.1.1 Concentrators 146
7.1.2 Distributors 148
Slicing and Dicing
7.2.1 Bit Slicing 149
7.2.2 Dimension Slicing 151
7.2.3 Channel Slicing 152
Slicing Multistage Networks
Case Study: Bit Slicing in the Tiny Tera
Bibliographic Notes
Exercises

149

153
155
157
157

Chapter 8 Routing Basics


159

8.1
8.2
8.3
8.4

160
162
163
164

A Routing Example
Taxonomy of Routing Algorithms
The Routing Relation
Deterministic Routing
8.4.1 Destination-Tag Routing in Butterfly Networks 165
8.4.2 Dimension-Order Routing in Cube Networks 166


x

Contents
8.5
8.6
8.7

Case Study: Dimension-Order Routing in the Cray T3D
Bibliographic Notes
Exercises


Chapter 9
9.1

9.2

9.3
9.4
9.5
9.6
9.7

Valiant’s Randomized Routing Algorithm
9.1.1 Valiant’s Algorithm on Torus Topologies 174
9.1.2 Valiant’s Algorithm on Indirect Networks 175
Minimal Oblivious Routing
9.2.1 Minimal Oblivious Routing on a
Folded Clos (Fat Tree) 176
9.2.2 Minimal Oblivious Routing on a Torus 178
Load-Balanced Oblivious Routing
Analysis of Oblivious Routing
Case Study: Oblivious Routing in the
Avici Terabit Switch Router(TSR)
Bibliographic Notes
Exercises

Chapter 10
10.1
10.2
10.3

10.4
10.5
10.6
10.7
10.8

11.2
11.3

Adaptive Routing

Adaptive Routing Basics
Minimal Adaptive Routing
Fully Adaptive Routing
Load-Balanced Adaptive Routing
Search-Based Routing
Case Study: Adaptive Routing in the
Thinking Machines CM-5
Bibliographic Notes
Exercises

Chapter 11
11.1

Oblivious Routing

Routing Mechanics

Table-Based Routing
11.1.1 Source Routing 204

11.1.2 Node-Table Routing 208
Algorithmic Routing
Case Study: Oblivious Source Routing in the
IBM Vulcan Network

168
170
171

173
174

176

180
180
183
186
187

189
189
192
193
195
196
196
201
201


203
203

211
212


Contents
11.4
11.5

Bibliographic Notes
Exercises

xi
217
217

Chapter 12 Flow Control Basics

221

12.1
12.2
12.3
12.4
12.5

222
225

228
230
230

Resources and Allocation Units
Bufferless Flow Control
Circuit Switching
Bibliographic Notes
Exercises

Chapter 13 Buffered Flow Control

233

13.1
13.2

234
237

13.4

Packet-Buffer Flow Control
Flit-Buffer Flow Control
13.2.1 Wormhole Flow Control 237
13.2.2 Virtual-Channel Flow Control 239
Buffer Management and Backpressure
13.3.1 Credit-Based Flow Control 245
13.3.2 On/Off Flow Control 247
13.3.3 Ack/Nack Flow Control 249

Flit-Reservation Flow Control

13.5
13.6

13.4.1 A Flit-Reservation Router 252
13.4.2 Output Scheduling 253
13.4.3 Input Scheduling 255
Bibliographic Notes
Exercises

13.3

245

251

256
256

Chapter 14 Deadlock and Livelock

257

14.1

258

14.2


Deadlock
14.1.1 Agents and Resources 258
14.1.2 Wait-For and Holds Relations 259
14.1.3 Resource Dependences 260
14.1.4 Some Examples 260
14.1.5 High-Level (Protocol) Deadlock 262
Deadlock Avoidance
14.2.1 Resource Classes 263
14.2.2 Restricted Physical Routes 267
14.2.3 Hybrid Deadlock Avoidance 270

263


xii

Contents
14.3

14.4

14.5
14.6
14.7
14.8

Adaptive Routing
14.3.1 Routing Subfunctions and
Extended Dependences 272
14.3.2 Duato’s Protocol for Deadlock-Free Adaptive

Algorithms 276
Deadlock Recovery
14.4.1 Regressive Recovery 278
14.4.2 Progressive Recovery 278
Livelock
Case Study: Deadlock Avoidance in the Cray T3E
Bibliographic Notes
Exercises

Chapter 15
15.1
15.2

15.3

15.4

15.5

15.6
15.7
15.8
15.9

Service Classes and Service Contracts
Burstiness and Network Delays
15.2.1 (σ, ρ) Regulated Flows 287
15.2.2 Calculating Delays 288
Implementation of Guaranteed Services
15.3.1 Aggregate Resource Allocation 291

15.3.2 Resource Reservation 292
Implementation of Best-Effort Services
15.4.1 Latency Fairness 294
15.4.2 Throughput Fairness 296
Separation of Resources
15.5.1 Tree Saturation 297
15.5.2 Non-interfering Networks 299
Case Study: ATM Service Classes
Case Study: Virtual Networks in the Avici TSR
Bibliographic Notes
Exercises

Chapter 16
16.1

16.2
16.3
16.4
16.5

Quality of Service

272

277

279
279
281
282


285
285
287

290

294

297

299
300
302
303

Router Architecture

305

Basic Router Architecture
16.1.1 Block Diagram 305
16.1.2 The Router Pipeline 308
Stalls
Closing the Loop with Credits
Reallocating a Channel
Speculation and Lookahead

305


310
312
313
316


Contents
16.6
16.7
16.8
16.9

xiii

Flit and Credit Encoding
Case Study: The Alpha 21364 Router
Bibliographic Notes
Exercises

319
321
324
324

Chapter 17 Router Datapath Components

325

17.1


325

17.2

17.3
17.4
17.5
17.6

Input Buffer Organization
17.1.1 Buffer Partitioning 326
17.1.2 Input Buffer Data Structures 328
17.1.3 Input Buffer Allocation 333
Switches
17.2.1 Bus Switches 335
17.2.2 Crossbar Switches 338
17.2.3 Network Switches 342
Output Organization
Case Study: The Datapath of the IBM Colony
Router
Bibliographic Notes
Exercises

334

343
344
347
348


Chapter 18 Arbitration

349

18.1
18.2
18.3
18.4

349
351
352
354

18.5
18.6
18.7

Arbitration Timing
Fairness
Fixed Priority Arbiter
Variable Priority Iterative Arbiters
18.4.1 Oblivious Arbiters 354
18.4.2 Round-Robin Arbiter 355
18.4.3 Grant-Hold Circuit 355
18.4.4 Weighted Round-Robin Arbiter
Matrix Arbiter
Queuing Arbiter
Exercises


357
358
360
362

Chapter 19 Allocation

363

19.1
19.2
19.3

363
366
367

Representations
Exact Algorithms
Separable Allocators
19.3.1 Parallel Iterative Matching 371
19.3.2 iSLIP 371
19.3.3 Lonely Output Allocator 372


xiv

Contents
19.4
19.5

19.6
19.7
19.8
19.9
19.10

Wavefront Allocator
Incremental vs. Batch Allocation
Multistage Allocation
Performance of Allocators
Case Study: The Tiny Tera Allocator
Bibliographic Notes
Exercises

Chapter 20
20.1

20.2

20.3
20.4
20.5
20.6

Processor-Network Interface
20.1.1 Two-Register Interface 391
20.1.2 Register-Mapped Interface 392
20.1.3 Descriptor-Based Interface 393
20.1.4 Message Reception 393
Shared-Memory Interface

20.2.1 Processor-Network Interface 395
20.2.2 Cache Coherence 397
20.2.3 Memory-Network Interface 398
Line-Fabric Interface
Case Study: The MIT M-Machine Network Interface
Bibliographic Notes
Exercises

Chapter 21
21.1
21.2
21.3

21.4
21.5
21.6
21.7
21.8

Network Interfaces

Error Control

Know Thy Enemy: Failure Modes and Fault Models
The Error Control Process: Detection, Containment,
and Recovery
Link Level Error Control
21.3.1 Link Monitoring 415
21.3.2 Link-Level Retransmission 416
21.3.3 Channel Reconfiguration, Degradation,

and Shutdown 419
Router Error Control
Network-Level Error Control
End-to-end Error Control
Bibliographic Notes
Exercises

373
376
378
380
383
385
386

389
390

394

400
403
407
408

411
411
414
415


421
422
423
423
424


Contents

xv

Chapter 22 Buses

427

22.1
22.2
22.3

428
432
436

22.4
22.5
22.6
22.7

Bus Basics
Bus Arbitration

High Performance Bus Protocol
22.3.1 Bus Pipelining 436
22.3.2 Split-Transaction Buses 438
22.3.3 Burst Messages 439
From Buses to Networks
Case Study: The PCI Bus
Bibliographic Notes
Exercises

441
443
446
446

Chapter 23 Performance Analysis

449

23.1

449

23.2

23.3
23.4
23.5
23.6

Measures of Interconnection Network Performance

23.1.1 Throughput 452
23.1.2 Latency 455
23.1.3 Fault Tolerance 456
23.1.4 Common Measurement Pitfalls 456
Analysis
23.2.1 Queuing Theory 461
23.2.2 Probabilistic Analysis 465
Validation
Case Study: Efficiency and Loss in the
BBN Monarch Network
Bibliographic Notes
Exercises

460

467
468
470
471

Chapter 24 Simulation

473

24.1
24.2

473
475


24.3

24.4

Levels of Detail
Network Workloads
24.2.1 Application-Driven Workloads 475
24.2.2 Synthetic Workloads 476
Simulation Measurements
24.3.1 Simulator Warm-Up 479
24.3.2 Steady-State Sampling 481
24.3.3 Confidence Intervals 482
Simulator Design
24.4.1 Simulation Approaches 485
24.4.2 Modeling Source Queues 488

478

484


xvi

Contents

24.5
24.6

24.4.3 Random Number Generation
24.4.4 Troubleshooting 491

Bibliographic Notes
Exercises

Chapter 25
25.1

25.2

25.3

Simulation Examples

Routing
25.1.1 Latency 496
25.1.2 Throughput Distributions
Flow Control Performance
25.2.1 Virtual Channels 500
25.2.2 Network Size 502
25.2.3 Injection Processes 503
25.2.4 Prioritization 505
25.2.5 Stability 507
Fault Tolerance

490
491
492

495
495
499

500

508

Appendix A Nomenclature

511

Appendix B

Glossary

515

Appendix C

Network Simulator

521

Bibliography

523

Index

539


Acknowledgments


We are deeply indebted to a large number of people who have contributed to the
creation of this book. Timothy Pinkston at USC and Li-Shiuan Peh at Princeton
were the first brave souls (other than the authors) to teach courses using drafts of
this text. Their comments have greatly improved the quality of the finished book.
Mitchell Gusat, Mark Hill, Li-Shiuan Peh, Timothy Pinkston, and Craig Stunkel
carefully reviewed drafts of this manuscript and provided invaluable comments that
led to numerous improvements.
Many people (mostly designers of the original networks) contributed information to the case studies and verfied their accuracy. Randy Rettberg provided information on the BBN Butterfly and Monarch. Charles Leiserson and Bradley Kuszmaul
filled in the details of the Thinking Machines CM-5 network. Craig Stunkel and Bulent Abali provided information on the IBM SP1 and SP2. Information on the Alpha
21364 was provided by Shubu Mukherjee. Steve Scott provided information on the
Cray T3E. Greg Thorson provided the pictures of the T3E.
Much of the development of this material has been influenced by the students
and staff that have worked with us on interconnection network research projects at
Stanford and MIT, including Andrew Chien, Scott Wills, Peter Nuth, Larry Dennison,
Mike Noakes, Andrew Chang, Hiromichi Aoki, Rich Lethin, Whay Lee, Li-Shiuan
Peh, Jin Namkoong, Arjun Singh, and Amit Gupta.
This material has been developed over the years teaching courses on interconnection networks: 6.845 at MIT and EE482B at Stanford. The students in these
classes helped us hone our understanding and presentation of the material. Past TAs
for EE482B Li-Shiuan Peh and Kelly Shaw deserve particular thanks.
We have learned much from discussions with colleagues over the years, including Jose Duato (Valencia), Timothy Pinkston (USC), Sudha Yalamanchili (Georgia
Tech),Anant Agarwal (MIT),Tom Knight (MIT), Gill Pratt (MIT), Steve Ward (MIT),
Chuck Seitz (Myricom), and Shubu Mukherjee (Intel). Our practical understanding
of interconnection networks has benefited from industrial collaborations with Justin
Rattner (Intel), Dave Dunning (Intel), Steve Oberlin (Cray), Greg Thorson (Cray),
Steve Scott (Cray), Burton Smith (Cray), Phil Carvey (BBN and Avici), Larry Dennison (Avici), Allen King (Avici), Derek Chiou (Avici), Gopalkrishna Ramamurthy
(Velio), and Ephrem Wu (Velio).

xvii



xviii

Acknowledgments
Denise Penrose, Summer Block, and Alyson Day have helped us throughout the
project.
We also thank both Catherine Albano and Deborah Prato for careful editing, and
our production manager, Marcy Barnes-Henrie, who shepherded the book through
the sometimes difficult passage from manuscript through finished product.
Finally, our families: Sharon, Jenny, Katie, and Liza Dally and Herman and Dana
Towles offered tremendous support and made significant sacrifices so we could have
time to devote to writing.


Preface

Digital electronic systems of all types are rapidly becoming commmunication limited. Movement of data, not arithmetic or control logic, is the factor limiting cost,
performance, size, and power in these systems. At the same time, buses, long the
mainstay of system interconnect, are unable to keep up with increasing performance
requirements.
Interconnection networks offer an attractive solution to this communication crisis and are becoming pervasive in digital systems. A well-designed interconnection
network makes efficient use of scarce communication resources — providing highbandwidth, low-latency communication between clients with a minimum of cost
and energy.
Historically used only in high-end supercomputers and telecom switches, interconnection networks are now found in digital systems of all sizes and all types.
They are used in systems ranging from large supercomputers to small embedded
systems-on-a-chip (SoC) and in applications including inter-processor communication, processor-memory interconnect, input/output and storage switches, router
fabrics, and to replace dedicated wiring.
Indeed, as system complexity and integration continues to increase, many designers are finding it more efficient to route packets, not wires. Using an interconnection
network rather than dedicated wiring allows scarce bandwidth to be shared so it can
be used efficiently with a high duty factor. In contrast, dedicated wiring is idle much

of the time. Using a network also enforces regular, structured use of communication
resources, making systems easier to design, debug, and optimize.
The basic principles of interconnection networks are relatively simple and it is
easy to design an interconnection network that efficiently meets all of the requirements of a given application. Unfortunately, if the basic principles are not understood it is also easy to design an interconnection network that works poorly if at all.
Experienced engineers have designed networks that have deadlocked, that have performance bottlenecks due to a poor topology choice or routing algorithm, and that
realize only a tiny fraction of their peak performance because of poor flow control.
These mistakes would have been easy to avoid if the designers had understood a few
simple principles.
This book draws on the experience of the authors in designing interconnection
networks over a period of more than twenty years. We have designed tens of networks
that today form the backbone of high-performance computers (both message-passing

xix


xx

Preface
and shared-memory), Internet routers, telecom circuit switches, and I/O interconnect. These systems have been designed around a variety of topologies including
crossbars, tori, Clos networks, and butterflies. We developed wormhole routing and
virtual-channel flow control. In designing these systems and developing these methods we learned many lessons about what works and what doesn’t. In this book, we
share with you, the reader, the benefit of this experience in the form of a set of simple principles for interconnection network design based on topology, routing, flow
control, and router architecture.

Organization
The book starts with two introductory chapters and is then divided into five parts
that deal with topology, routing, flow control, router architecture, and performance.
A graphical outline of the book showing dependences between sections and chapters is shown in Figure 1. We start in Chapter 1 by describing what interconnection
networks are, how they are used, the performance requirements of their different
applications, and how design choices of topology, routing, and flow control are made

to satisfy these requirements. To make these concepts concrete and to motivate the
remainder of the book, Chapter 2 describes a simple interconnection network in detail: from the topology down to the Verilog for each router. The detail of this example
demystifies the abstract topics of routing and flow control, and the performance issues with this simple network motivate the more sophisticated methods and design
approaches described in the remainder of the book.
The first step in designing an interconnection network is to select a topology
that meets the throughput, latency, and cost requirements of the application given
a set of packaging constraints. Chapters 3 through 7 explore the topology design
space. We start in Chapter 3 by developing topology metrics. A topology’s bisection
bandwidth and diameter bound its achievable throughput and latency, respectively,
and its path diversity determines both performance under adversarial traffic and fault
tolerance. Topology is constrained by the available packaging technology and cost
requirements with both module pin limitations and system wire bisection governing
achievable channel width. In Chapters 4 through 6, we address the performance
metrics and packaging constraints of several common topologies: butterflies, tori, and
non-blocking networks. Our discussion of topology ends at Chapter 7 with coverage
of concentration and toplogy slicing, methods used to handle bursty traffic and to
map topologies to packaging modules.
Once a topology is selected, a routing algorithm determines how much of the bisection bandwidth can be converted to system throughput and how closely latency
approaches the diameter limit. Chapters 4 through 11 describe the routing problem and a range of solutions. A good routing algorithm load-balances traffic across
the channels of a topology to handle adversarial traffic patterns while simultaneously exploiting the locality of benign traffic patterns. We introduce the problem in
Chapter 8 by considering routing on a ring network and show that the naive greedy algorithm gives poor performance on adversarial traffic. We go on to describe oblivious


Preface

xxi

A
1. Introduction


Introduction
Q: 1,2
S: 1,2

12. Flow
Control Basics

Flow Control
Q:12,13,14
S:12,13,14,15

2. Simple
Network
13. Buffered
Flow Control
3. Topology
Basics

Topology
Q:3-5
S:3-7

14. Deadlock
& Livelock

15. Quality of
Service

4. Butterflies


5. Tori

6. Nonblocking
7. Slicing

8. Routing
Basics

Routing
Q:8-11
S:8-11

16. Router
Architecture

Router Architecture
Q:16-19
S:16-19,20

17. Datapath
Components

20. Network
Interfaces

18. Arbitration

21. Error
Control


19. Allocation

22. Buses

9. Oblivious
Routing
10. Adaptive
Routing

23. Perf.
Analysis

Performance
Q:23
S:23-25
24. Simulation

11. Routing
Mechanics
25. Simulation
Examples
A

Figure 1

Outline of this book showing dependencies between chapters. Major sections are denoted as
shaded areas. Chapters that should be covered in any course on the subject are placed along
the left side of the shaded areas. Optional chapters are placed to the right. Dependences are
indicated by arrows. A solid arrow implies that the chapter at the tail of the arrow must be
understood to understand the chapter at the head of the arrow. A dotted arrow indicates that

it is helpful, but not required, to understand the chapter at the tail of the arrow before the
chapter at the head. The notation in each shaded area recommends which chapters to cover in
a quarter course (Q) and a semester course (S).


xxii

Preface
routing algorithms in Chapter 9 and adaptive routing algorithms in Chapter 10. The
routing portion of the book then concludes with a discussion of routing mechanics
in Chapter 11.
A flow-control mechanism sequences packets along the path from source to destination by allocating channel bandwidth and buffer capacity along the way. A good
flow-control mechanism avoids idling resources or blocking packets on resource constraints, allowing it to realize a large fraction of the potential throughput and minimizing latency respectively. A bad flow-control mechanism may squander throughput
by idling resources, increase latency by unnecessarily blocking packets, and may even
result in deadlock or livelock. These topics are explored in Chapters 12 through 15.
The policies embedded in a routing algorithm and flow-control method are realized in a router. Chapters 16 through 22 describe the microarchitecture of routers
and network interfaces. In these chapters, we introduce the building blocks of routers
and show how they are composed. We then show how a router can be pipelined to
handle a flit or packet each cycle. Special attention is given to problems of arbitration
and allocation in Chapters 18 and 19 because these functions are critical to router
performance.
To bring all of these topics together, the book closes with a discussion of network performance in Chapters 23 through 25. In Chapter 23 we start by defining
the basic performance measures and point out a number of common pitfalls that
can result in misleading measurements. We go on to introduce the use of queueing
theory and probablistic analysis in predicting the performance of interconnection
networks. In Chapter 24 we describe how simulation is used to predict network
performance covering workloads, measurement methodology, and simulator design.
Finally, Chapter 25 gives a number of example performance results.

Teaching Interconnection Networks

The authors have used the material in this book to teach graduate courses on interconnection networks for over 10 years at MIT (6.845) and Stanford (EE482b). Over
the years the class notes for these courses have evolved and been refined. The result
is this book.
A one quarter or one semester course on interconnection networks can follow
the outline of this book, as indicated in Figure 1. An individual instructor can add
or delete the optional chapters (shown to the right side of the shaded area) to tailor
the course to their own needs.
One schedule for a one-quarter course using this book is shown in Table 1 . Each
lecture corresponds roughly to one chapter of the book. A semester course can start
with this same basic outline and add additional material from the optional chapters.
In teaching a graduate interconnections network course using this book, we typically assign a research or design project (in addition to assigning selected exercises
from each chapter). A typical project involves designing an interconnection network
(or a component of a network) given a set of constraints, and comparing the performance of alternative designs. The design project brings the course material together


Preface

xxiii

Table 1 One schedule for a ten-week quarter course on interconnection networks. Each chapter covered
corresponds roughly to one lecture. In week 3, Chapter 6 through Section 6.3.1 is covered.
Week

Topic

Chapters

1

Introduction


1, 2

2

Topology

3, 4

3

Topology

5, (6)

4

Routing

8, 9

5

Routing

10, 11

6

Flow Control


12, 13, 14

7

Router Architecture

16, 17

8

Arbitration & Allocation

18, 19

9

Performance

23

10

Review

for students. They see the interplay of the different aspects of interconnection network design and get to apply the principles they have learned first hand.
Teaching materials for a one quarter course using this book (Stanford EE482b)
are available on-line at This page also includes example projects and student papers from the last several offerings of this
course.



This
. Page Intentionally Left Blank