An adaptive communications protocol for network computers (extended abstract)

ABSTRACT

A network computer is a collection of computers designed to function as one machine. On a network computer, as opposed to a multiprocessor, constituent subcomputers are memory-disjoint and communicate only by some form of message exchange. Ensemble architectures like multiprocessors and network computers are of growing interest because of their capacity to support parallel programs, where a parallel program is one that is made up of many simultaneously-active, communicating processes. Parallel programs should, on an appropriate architecture, run faster than sequential programs, and, indeed, good speed-ups have been reported in parallel programming experiments in several domains, amongst which are AI, numerical problems, and system simulation. Our interest lies in network computers, particularly ones that range in size from several hundred nodes to several thousand.

Network computers may be organized in either of two basic ways: their nodes may communicate over a shared bus (or series of buses), as in S/Net; or over point-to-point links, as in Cosmic Cube and the Transputer Network. The work to be presented deals with the point-to-point class, the elements of which we shall refer to as “linked networks”.

Linked networks face a fundamental communication problem. Unless they are completely connected (which is rarely possible), two communicating nodes will not necessarily be connected by a single link. Messages between nodes must therefore, in general, travel over several links and be processed by several intermediate nodes. Communication delays increase with the length of the traveled path. Network computer designers therefore provide networks the diameters of which are small relative to their size, and network operating systems will attempt to place communicating processes as close to each other as possible.

We present a communication protocol for linked networks that was designed specifically for network computers. Staged Circuit Switching is a communication protocol that combines aspects of store-and-forwarding with aspects of circuit switching, where circuit switching refers to the class of protocols in which a communicating source and destination first construct a dedicated path or circuit between them, then communicate directly over this path. The path may be a physical connection, as in spaced-switched circuit-switching, or a series of dedicated slots in time-division multiplexing switches, as in time-switching protocols. The stage-circuit-switching design is strongly related to spaced-switched circuit-switching and encompasses both the protocol itself and a communication architecture to support it.

In staged circuit switching, each message constructs for itself the longest physical circuit that it can without waiting for links. When a message is to be sent, a header that records the message's source and destination is sent propagating through the network towards the destination node; the header seizes each free link along its path and incorporates it into a growing circuit. When it meets a busy link, or arrives at its destination, circuit building stops, the message's data portion is transmitted and acknowledged over the existing circuit, and the circuit is released. A message that has not arrived at its destination then gathers itself together and plunges onward in the same fashion. In an empty network then, staged circuit switching is the same as circuit switching: each message is transmitted over a direct circuit from source to destination. In a heavily loaded network, it is the same as store-and-forwarding: each next-link is busy, each circuit is therefore only one link long, and the message proceeds hop by hop. The protocol combines the speed benefits of circuit switching at light traffic loads, with the high bandwidth advantages of store-and-forwarding at heavy loads.

We have carried out extensive simulation studies to evaluate the dynamics of staged circuit switching from the point of view of message delays, throughput, circuit lengths, efficiency, implementation, and so on. The studies were implemented in the context of a toroidal topology of diameter 32, yielding a 1024-node network. Uniform source-to-destination distributions were used. Both the topology and the source-to-destination distributions are analyzed. An analysis of network saturation based on mean values is also given.

Staged circuit switching unambiguously emerges as a strong protocol with superior performance characteristics than either classical store-and-forwarding or circuit switching, particularly with regards to adaptability to varying network loads and in providing a consistently high effective network bandwidth. On the basis of our results the protocol is proposed as a suitable candidate for linked networks. Its attractiveness is further enhanced by its potential ability to continually reconfigure the network dynamically at runtime to optimize for observed traffic patterns. Heavily-used circuits may be left in place over longer periods than a single message transmission. In this way, the system constantly rearranges the network topology in order to bring heavily-communicating distant nodes closer together, thereby acting as a “communication cache”. A “cache hit” would correspond to finding the desired destination node one hop away from a given source. Effective exploitation of this capability is the subject of ongoing research.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Cellular architectures

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Hardware

  • Emerging technologies

    • Quantum technologies

      • Quantum dots and cellular automata

• Networks

  • Network performance evaluation

  • Network protocols

• Theory of computation

  • Models of computation