COM1204 Object-Oriented Design, Summer 1998

Phone System Design Document, 2nd design, PS2


by Professor Futrelle


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

Executive Summary

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.

The State-Machine View

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.



The Messages that the Nodes See

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.


Messages (packet types)
To Switch
To Phone
 Dial   Busy
 Speech  Speech

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).

Packet types:

Dial (D)
Includes the number dialed. Usually an integer, but may be a pair of exchange, integer.
Ring (R)
No additional information required.
Pickup (P)
No additional information required.
Hangup (H)
No additional information required.
Speech (S)
Includes a string.
Busy (B)
No additional information required.
Absence of any packet, the link is "quiet".

States of a Switch

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.

Connected (C)
Phone is connected
Picked_up (P)
The phone is picked up (so it can report it as busy to another caller, and not ring it).
Ringing (R)
Ring been sent to this or another phone (connection made when one picks up).
Other phone (O)
Contains the number of the other phone requesting or having a connection.

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.


All possible switch state combinations

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.

Responding to Messages, the Switch State Diagram

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.

First Notes on State-Based Implementation

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.

Back to Teaching Gateway