This addendum focuses on the initial formulation of the state-machine approach to handling the active elements in the phone system, which are the nodes -- the phones and switches. This is an HTML document reachable via the Teaching Gateway from my homepage www.ccs.neu.edu/home/futrelle.
See the original "2nd design" document for the first executive summary (hardcopy MSWord doc). This document discusses the state-machine approach to modeling the phone system, the approach settled on at the end of that document. The fundamental idea is that a given node, that is, a phone or switch, is in a given state at any time step. For a phone the state will include values such as "just_dialed" or "connected". For a switch, the state is more complex and is handled on a phone-by-phone basis for phones directly connected to the switch. (Connecting other switches is not dealt with in this Addendum.) For a given phone attached to a switch, the state might include, is the phone picked_up or is it connected to some other specific phone, etc.
Since each separate node object (a C++ object) maintains its own separate values of its state, kept as values of its slots, any method of the node that runs can decide what to do given the state, including changing the state. The events that trigger changes are the arrival of messages, which in are case are packets in the link(s) attached to a node. Based on the current state and the message received, a generic run() function is executed that decides what to do next. We say that the phones follow scripts in deciding what to do, e.g., initiate a call, and the switches follow policies, e.g., they have a fixed way of handling an incoming dial message, either connecting the phones or returning a busy message. Introducing randomness in the scripts adds a great deal of realism to the simulation, e.g., how long a phone waits before initiating a call. Another realistic aspect is to use timers that create a timeout message after a certain number of steps, e.g., giving up after no reply is received for a long time.
The overall design strategy has two aspects that can be developed in parallel. The first is that actual choice of states and design of the scripts and policies. The second is the design of the object-oriented strategies for representing states and the scripts and policies in working code. The former task can be pursued without regard to implementation. The latter can be pursued without regard to the actual states and scripts or policies to be used. This addendum focuses on the state design, not the code.
This addendum discusses a simple switch, attached to phones (not to any other switches) because a switch has a simple "reactive" policy. It doesn't initiate any actions on its own.
By a state-machine, we normally mean a finite-state automaton. Another, somewhat different approach, which we won't use here, but can be useful, is that of Petri Nets. (See, for example, the book Computer Networks by Andrew S. Tanenbaum for the application of these to network analysis.) A state-machine is a set of states (nodes) and transitions (arcs). The system is in one of a discrete set of states at any moment. When an input is received it causes the system to choose a transition and move to another state (including the possibility of staying in the same state). A simple example is shown in Fig. 1.
Figure 1. Simple example of a 2-state finite-state-machine for a phone. The inputs attached to the arcs control the transitions between the two states. (This is not the final formulation, just an example.)
We first review the types of messages that can flow between nodes. This is a list of packet types. The arrival of a message is considered an "event". The only other types of events that can occur are timeout events, but these happen only within phones, and will be ignored for this discussion. Packets have a source and destination. In this discussion a single switch is attached to multiple phones, in a star topology, so each messages from a phone goes to the switch, and each message from the switch goes to a phone. Our emphasis is on the messages that go to a switch, but both types are shown here.
|
|
|
|
|
|
| Dial | Busy |
| Ring | |
| Pickup | |
| Hangup | |
| Speech | Speech |
| NULL | NULL |
Note that we have omitted the dial_tone type for simplicity. We assume that the switch always grants the ability to dial as soon as a phone is picked up. NULL means no packet is present in the link (alternatively, we could always have a packet present but have one of type NULL).
The choice of states and representation of the states is not always an easy design issue. But the switch operates in a rather simple way, always "doing what it's told" immediately. The only state it needs therefore is its information about each phone on a phone-by-phone basis.
From the switch's point-of-view, here is what it needs to remember about each phone, so these will be the switch's states, one copy for each connected phone. The first three are Boolean, and the last contains an integer (or no_phone, e.g., minus 1). The first three are listed in alphabetical order for later convenience.
The simple quiescent state, also the initial state, is when all three Boolean values are false. We will now list all eight possible combinations of the three boolean values and pick out only those that we'll need to consider, e.g., a phone can't be connected if it's hung up. Each triple is listed as one Boolean value, T or F for each of the C, P, and R states. Note that the state numbers are exactly those of the three digit binary number CPR if we use T=1 and F=0.
|
C = Connected, P = Picked_up, R = Ringing |
|||||
| # | C | P | R | Valid? | Comments |
| 0 | F | F | F | Yes | Quiescent state |
| 1 | F | F | T | Yes | Ringing OK if unconnected and hung up |
| 2 | F | T | F | Yes | Simply picked up (may dial, can't receive calls) |
| 3 | F | T | T | Yes | Ringing other phone |
| 4 | T | F | F | No | Can't be connected if not picked up |
| 5 | T | F | T | No | Can't be connected if not picked up and should not be ringing |
| 6 | T | T | F | Yes | This is the normal state during a conversation |
| 7 | T | T | T | No | Won't ring during a conversation. |
One important point to keep in mind when viewing the table above is that the valid states are the states that the switch can move to after processing a message (an incoming packet). Of course after a ring has been sent to a phone and the switch enters state 1, the phone will probably be picked up, but when the pickup message is received the phone will move into state 6 in which it is picked up, connected, and has R = False -- it is no longer ringing. The bottom line is that there are five valid states for each phone within the switch. The other item in the state, the phone number, is just a placeholder and is not used in making decisions about how to respond to messages.
There is a slight complication here, because the status of one phone can be affected by messages that it sends or by a dial or hangup messages sent by another phone. In the state diagram below, the messages are indicated on the arcs with either a 1 or a 2, indicating the phone whose state we are examining (1) and the other phone (2) that may affect 1's state. The only message types possible on the arcs are the ones to the switch, Dial, Pickup, Hangup, Speech, and NULL. Thus, Dial is a dial message from the phone whose states we are portraying, and Dial 2 is a dial to this phone from some other phone. Each state is labeled by a CPR triple, e.g., state 2 by FTF.
Figure 2. Portion of the state diagram for a switch that is relevant to a single phone. Messages from that phone are indicated on the arcs. All messages ending in "2" are messages from some other phone that is attempting to dial this phone or is connected to this phone. Speech messages are not shown because they never cause a state change. They are passed through a connection or ignored if the receiving phone has hung up. NULL messages are also ignored and cause no state change. (NULL messages will be relevant to timeout events, but the switch never times out. It simply continues to do what it has been told to do until the request is satisfied or revoked, e.g., by a hangup.) The layout of the diagram reflects the basic symmetry between the two phones, and the fact that pickup and hangup are in some sense inverses of one another. For example the connected state has two pickup and two hangup transitions attached to it and the sequence dial and pickup 2 leads to a connected state just as the sequence dial 2 and pickup does. Also note that in all three states in which the phone is picked up, a hangup is allowed and leads to the quiescent state. When a connection is being made or broken, a related set of state transitions is going on in the other phone. This is going to need some review and careful thinking to assure ourselves that it works properly for a pair of phones, no matter which order the two phones are handled in (in the run() loop).
In the Switch class, the status of the phones can be a vector of Sw_phone_status objects (a vector of pointers, actually). Each status object would have three Boolean slots for P, C, and R, as well as an integer slot for the connected phone number. When a decision is to be made, we must run distinct code for each of the possible four states that the phone status could be in and generate the correct actions and a possible change to a new state. We could represent the states entirely by their state numbers ("#" in the state combinations table above), but that makes the design less transparent and harder to think about and makes it harder to read, understand, and debug. Of course in the implementation of a real system, simple bit patterns are used because of space and efficiency issues. We can achieve a nice compromise with a function that tests the state as in the following example. Assume that the status is stored in a vector phone_states, then a call to test to see if phone 7 is in state 1 (FFT), which is the only ring_sent state, could be phone_states[7]->is_state(false,false,true), returning true or false. If the phone is then picked up after the ring is sent, the connection is made and the state is reset from state 1 to state 6, using phone_states[7]->set_state(true,true,false). Actually, when a connection is made, the state of both phones is altered, including the phone number each is connected to (each to the other).
The code for making these decisions could be a sequence of simple (not nested) if statements in a method of the Switch class called act_on_message(). In it there could be a sequence of is_state() tests each followed by code to do whatever is necessary followed by a return (from the act_on_message() function). This acts like an enhanced switch statement, but an ordinary C++ switch statement is strictly limited to scalar types such as integers, characters, and enums. This formulation allows us to go beyond the switch syntax, using return instead of break. I will not elaborate further on coding details in this note.
New 7/28/98. Last revision, 7/28/98.