Overview

Interconnection networks are widely used today. The simplest example is a network connecting processors and memory modules in a shared-memory multiprocessor, in which processors perform read or write operations in the memory modules. Another example is a network connecting a number of processors (typically with their own local memory) in a distributed system, allowing the processors to communicate through messages while executing parts of a common application. In these two types of network, the individual components (processors and memories) are connected through a collection of links and switchboxes, where a switchbox allows a given component to communicate with several other components without having a separate link to each of them.

A third type of networks, called wide-area networks, connects large numbers of processors that operate independently (and typically execute different and unrelated applications), allowing them to share various types of information. In such networks, the term packet is often used instead of message (a message may consist of several packets, each traversing the network independently), and they consist of more complicated switchboxes called routers. The best known example of this kind of network is the Internet.

The network's links and switchboxes establish one or more paths between the sender of the message (the source) and its receiver (the destination). These links and switchboxes can be either unidirectional or bidirectional. The specific organization, or topology, of the network may provide only a single path between a given source and a given destination, in which...