7.8 Token Ring for Communication

This section develops a simulation of communication on a token-ring network. Each process on the ring now represents an Interface Message Processor (IMP) of a node on the network. The IMP handles message passing and network control for the host of the node. Each IMP process creates a pair of pipes to communicate with its host process, as shown in Figure 7.9. The host is represented by a child process forked from the IMP.

Figure 7.9. IMP-host structure.

Each IMP waits for messages from its host and from the ring. For simplicity, a message consists of five integersa message type, the ID of the source IMP, the ID of the destination IMP, a status, and a message number. The possible message types are defined by the enumerated type msg_type_t .

 typedef enum msg_type{TOKEN, HOST2HOST, IMP2HOST, HOST2IMP, IMP2IMP} msg_type_t; 

The IMP must read a TOKEN message from the ring before it writes any message it originates to the ring. When it receives an acknowledgment of its message, it writes a new TOKEN message on the ring. The acknowledgments are indicated in the status member that is of type msg_status_t defined by the following.

 typedef enum msg_status{NONE, NEW, ACK} msg_status_t; 

The IMP waits for a message from either its host or the ring. When an IMP detects that the host wants to send a message, it reads the message into a temporary buffer and sets the got_msg flag. Once the got_msg flag is set, the IMP cannot read any additional messages from the host until the got_msg flag is clear.

When the IMP detects a message from the network, its actions depend on the type of message. If the IMP reads a TOKEN message and it has a host message to forward ( got_msg is set), the IMP writes the host message to the network. If the IMP has no message to send ( got_msg is clear), it writes the TOKEN message on the network.

If the IMP reads a message other than a TOKEN message from the ring, its actions depend on the source and destination IDs in the message.

1. If the source ID of the message matches the IMP's ID, the message was its own. The IMP prints a message to standard error reporting whether the message was received by the destination. In any case, the IMP writes a TOKEN message to the ring and clears got_msg .

2. If the destination ID of the message matches the IMP's ID, the message is for the IMP or the IMP's host. The IMP prints a status message to standard error reporting the type of message. The IMP changes the status of the message to ACK and writes the message to the ring. If the message is for the host, also send the message to the host through the pipe.

3. Otherwise, the IMP writes the message to the ring unchanged.

The actual IEEE 802.5 token-ring protocol is more complicated than this. Instead of fixed-length messages, the IMPs use a token-holding timer set to a prespecified value when transmission starts. An IMP can transmit until the timer expires , so messages can be quite long. There can also be a priority scheme [111]. In the actual token-ring protocol, one IMP is designated as the active monitor for the ring. It periodically issues control frames to tell the other stations that the active monitor is present. The active monitor detects whether a token has been lost and is responsible for regenerating tokens. All the stations periodically send standby-monitor-present control frames downstream to detect breaks in the ring.

Start with Program 7.1. Modify it so that after the ring is created, each IMP process creates two pipes and a child host process, as shown in Figure 7.9. Redirect standard output and standard input of the child host as shown in Figure 7.9, and have the child execute the hostgen program with the appropriate command-line arguments. The IMP enters an infinite loop to monitor its possible inputs, using select . When input is available, the IMP performs the simple token-ring protocol described above.

Write and test a separate program, hostgen , that takes two command-line arguments: an integer process number n and an integer sleep time s . The hostgen program monitors standard input and logs any input it receives to standard error. Use the read_timed of Program 4.16 on page 115 with a random timeout between 0 and s seconds. If a timeout occurs, write a random integer between 0 and n to standard output. Test the hostgen program separately.