7.1 Ring Topology

The ring topology is one of the simplest and least expensive configurations for connecting communicating entities. Figure 7.1 illustrates a unidirectional ring structure. Each entity has one connection for input and one connection for output. Information circulates around the ring in a clockwise direction. Rings are attractive because interconnection costs on the ring scale linearly ”in fact, only one additional connection is needed for each additional node. The latency increases as the number of nodes increases because the time it takes for a message to circulate is longer. In most hardware implementations , the rate at which nodes can read information from the ring or write information to the ring does not change with increasing ring size, so the bandwidth is independent of the size of the ring. Several network standards, including token ring (IEEE 802.5), token bus (IEEE 802.4) and FDDI (ANSI X3T9.5) are based on ring connectivity.

Figure 7.1. Unidirectional ring with five nodes.

This chapter develops several projects based on the ring topology of Figure 7.1. The nodes represent processes and the links represent pipes. Each process is a filter that reads from standard input and writes to standard output. Process n-1 redirects its standard output to the standard input of process n through a pipe. Once the ring structure is set up, the project can be extended to simulate network standards or to implement algorithms for mutual exclusion and leader election based on the ring architecture.

Section 7.2 presents a step-by-step development of a simple ring of processes connected by pipes. Section 7.3 provides several exploratory exercises that build on the basic ring structure. The figures of Section 7.2 trace the code through the creation of two processes on the ring, but the basic ring is too complicated to trace manually much beyond that.

We suggest that before working through Section 7.3, you use the fork-pipe simulator to try some of the examples. The book web page has a link to this simulator, which shows a diagram of the processes and pipes as it traces the code. The simulator also allows experimentation with process chains, fans and trees as well as more complicated structures such as a bidirectional ring. The simulator allows you to experiment with the effects of using different CPU scheduling algorithms, or you can single-step through the code, determining which process runs at each step. The simulator also can produce a log of the output generated and a trace of the instructions executed.

Once you have a thorough understanding of the ring and its behavior, you can go on to the other projects in this chapter. Section 7.4 tests the ring connectivity and operation by having the ring generate a Fibonacci sequence. Section 7.5 and Section 7.6 present two alternative approaches for protecting critical sections on the ring. Once the ring structure is set up, the basic project of Section 7.2 can be extended to simulate network standards or to implement algorithms for mutual exclusion and leader election based on the ring architecture. The remaining sections of the chapter describe extensions exploring different aspects of network communication, distributed processing and parallel algorithms. The extensions described in each of the later sections are independent of those in other sections.