Tutorial: State Machines

After some considerations, I’ve decided not to update the “Playground User’s Guide” with information about State Machines. As a concept, State Machines are useful, but not essential. And my implementation that I’ve put into Playground is perhaps useful, but still experimental.

So, instead, I’ll provide a short tutorial here.

What is a State Machine?

In computer science, one of the simplest conceptual machines it a Deterministic Finite Automaton (DFA). Informally, a DFA has a fixed series of states and an explicit transition from one state to the next. If you want the formal definition, try Google or Wikipedia. Often, when  one speaks of a “State Machine”, one is talking about a DFA.

Truthfully, most programs can be represented as a DFA whether they were intended to be or not. But sometimes it is useful to write a program in an explicitly state-machine-oriented form. It can make clear how the program works and how it should handle inputs as the states change.

Network protocols with many states are good candidates. Consider your “dataReceived” method. What kind of data is it expecting? A SYN? an ACK? DATA? How should it respond to the data it receives?

You can either build a complicated if-else statement, or you can store some internal “state” that routes the incoming data to the appropriate place.

Class playground.network.common.statemachine.StateMachine

Within Playground is a class called “StateMachine” that is designed to make creating state-based operations easier. It starts by simply creating an instance of the class with a name (the name is used for logging and debugging).

self.fsm = StateMachine("MyStateMachine")

Once the StateMachine class is instantiated, you can add states to it using the addState() method. This method requires a name, zero or more transitions, and optional callbacks for when the state is entered or exited.

A transition is a tuple of a “signal” and another state name. The signal tells the state machine what state it should change to when it receives the specified signal. Signals can be any object.

The callbacks supported are “onEnter” and “onExit”. As you might imagine, the former is called when the State Machine enters the state, and the latter is called when the State Machine exits a state. Most commonly, you’ll only need “onEnter” and for some states you may not need a callback at all. The signature for both callbacks is callback(signal, data). The “signal” will be whatever signal caused the transition (either in or out) and the data is whatever data was passed to the state machine along with the signal. This will become more clear in the example that follows.

So, suppose I have a Network Protocol that has a “Listening” state. When it receives a message with a SYN, it should transition into state “Handshake”. You would create this state like this:

self.fsm.addState("Listening", ("SYN_RECEIVED", "Handshake"))

There’s nothing special about any of these strings. I just made them up. We’ll see how to use SYN_RECEIVED in a minute. For now, let’s start defining the “Handshake” state. Notice that for the “Listening” state, we had no callbacks. But for the “Handshake” state, we want to respond to the SYN when we enter the state. Perhaps we decide to exit it when we receive the first ACK. Our definition might look like this:

self.fsm.addState("Handshake", ("ACK_RECEIVED", "Open"), onEnter=self.handleSyn)

Our handleSyn method might look something like this:

def handleSyn(self, signal, data):
  self.authenticateCerts(data)
  # process the data, create SynAckMsg
  self.transport.write(SynAckMsg)

Once the StateMachine has all of its states, you initialize it by declaring an initial state.

self.fsm.start("Listening")

To use the StateMachine, you need to send it signals (and optional data). Typically, you might do this when you receive an incoming network message:

def dataReceived(self, data):
  # convert data to msg
  if msg.type == "SYN":
    self.fsm.signal("SYN_RECEIVED", msg)
  if msg.type == "ACK":
    self.fsm.signal("ACK_RECEIVED", msg)

Of course, that still is an ugly if statement. What we could do instead is create our transition signals to be some subset of the message’s data. Perhaps the “.type” field is perfectly sufficient for differentiating all the transitions in and out of states. If so, we could re-write all of our states with just that field as the signal.

self.fsm.addState("Listening",("SYN", "Handshake"))

Now, our dataReceived method just looks like this:

def dataReceived(self, data):
  # convert data to msg
  self.fsm.signal(msg.type, msg)

But if you need additional differentiation, see if you can figure out a combination of fields to get similar results.

Please note that what is shown in this example is super simplified. Most states will need to have many transitions, including transitions back to itself (in the “open” state, for example, it should stay in that state until a “FIN” is received, or something like that). You may also need to create special signals for when your side of the connection sends the “FIN”.

IT IS IMPORTANT TO REMEMBER that if the StateMachine receives a signal for which there is no transition defined, IT WILL TRANSITION TO AN ERROR STATE.

The default error state does nothing (except potential log the error), but you cannot get out of it. If you want to change the error state, you can configure it when you call state by identifying another state you’ve defined as an error state.

self.fsm.start(startingState, errorState)

Final Thoughts

As I said earlier, this is still experimental. There are a number of ways that I could do this differently. For example, maybe it would make more sense to have a state always transitioning back to itself unless you explicitly define a transition out, and error states also have to be explicitly transitions. I don’t know, I’m still thinking about it. So please don’t complain if there are changes later in the semester.

If you’d like to see an example of the StateMachine in action, take a look at playground.network.gate.ChaperoneProtocol.py.

Leave a Reply

Your email address will not be published. Required fields are marked *