Evaluating the state pattern implementation
In the previous post I proposed the SCTP protocol as a problem space that would allow us to explore some interesting programming topics. SCTP is covered in RFC 4960 for those that want to dig deeper. In this post I will briefly describe the structure of the implementation I came up with and examine the state machine.
It's not easy to get a good implementation directly from an RFC on the first try, so I decided to try writing a prototype in Python, and then translate it into C#. I thought this approach was helpful. If you would like to try Python you can use Iron Python which is .Net friendly. I will only present the C# implementation in the blog however.
SCTP Structure
Before going over the state machine, it probably makes sense to describe the high level layout of the code for my SCTP implementation.
You can see from the class diagram that the Association knows its related SctpSocket, has a state, uses a PacketReceiver instance to receive packets, and a PacketBuilder instance to assemble outgoing packets. The PacketReceiver and PacketBuilder keep track of the appropriate remote or local transmit sequence numbers (TSNs) needed to do their work, and interact with StreamSequencer instances to ensure proper ordering within a stream.
The following sequence diagram shows how events coming from the application or network are processed. They are initially passed by the Association to the current state, which routes them as appropriate to the PacketReceiver or PacketBuilder to do the actual work.
This design means that most of the real work happens in the Association, PacketBuilder and PacketReceiver, and the implementation of each state is usually pretty simple. It makes sense when you think about it. If you extracted the code responsible for managing the state machine, there probably wouldn't be that much to look at.
Implementation
As stated previously, I wanted to try using the state pattern to get some experience with it. I chose to use singleton state classes instead of keeping instances with instance data in them so that I don't create a lot of work for the garbage collector (GC).
Even though I'm still deciding how happy I am with my implementation, I will present the state machine I came up with since I still should be able cover some interesting topics with it.
To start out, the base class AssociationState is a good place to see all the events the state machine handles:
internal class AssociationState
{
public virtual void Enter(Association association);
public virtual void Exit(Association association);
#region Network events
public virtual AssociationState Receive_InitAck(
Association association, InitAckChunk chunk);
public virtual AssociationState Receive_Abort(
Association association, AbortChunk chunk);
public AssociationState Receive_Init(
Association association, InitChunk chunk);
public virtual AssociationState Receive_CookieEcho(
Association association,
CommonHeader common,
CookieEchoChunk inChunk);
public virtual AssociationState Receive_Sack(
Association association, SackChunk chunk);
public virtual AssociationState Receive_CookieAck(Association association);
public virtual AssociationState Receive_Shutdown(
Association association, ShutdownChunk chunk);
public virtual AssociationState Receive_ShutdownAck(Association association);
public virtual AssociationState Receive_ShutdownComplete(Association association);
public virtual AssociationState Receive_Data(
Association association, DataChunk chunk);
#endregion
#region API Events
public virtual AssociationState Associate(
Association association,
IPAddress address,
int peerPort,
AssociateOptions options);
public virtual AssociationState Abort(Association association);
public virtual AssociationState Shutdown(Association association);
public virtual AssociationState SendMessage(
Association association, byte[] message);
#endregion
#region Internal Events
public virtual AssociationState DataQueueClear(Association association);
#endregion
}
Each state returns what should be the next state of the Association, or null if there is no change. The state machine is driven by a simple SetState method that determines if the state changed:
private void SetState(AssociationState state)
{
AssociationState temp = m_state;
if (state != null)
{
m_state = state;
Trace.WriteLine(
String.Concat("State changed: ", temp.ToString(),
" => ", state.ToString()));
temp.Exit(this);
state.Enter(this);
}
}
When the Association receives an event it calls SetState as follows:
this.SetState(m_state.Receive_Data(this, chunk as DataChunk));
One advantage that I noticed by using the state pattern is that all states except Closed can benefit from refactoring common code into an intermediate state ActiveState to handle Abort behavior:
internal class ActiveState : AssociationState
{
public override AssociationState Abort(Association association)
{
var chunk = new AbortChunk();
association.PacketBuilder.EndSend(
association.PacketBuilder.BeginSend(
new Chunk[] { chunk }, null, null));
return AssociationStates.Closed;
}
public override AssociationState Receive_Abort(
Association association, AbortChunk chunk)
{
association.CleanUp();
return AssociationStates.Closed;
}
}
Thoughts on the State pattern
Even though my implementation is missing a pretty important item, a way to sequence event processing in the state machine, there are some things I like about the pattern:
- I can clearly see the available states, and events in the state machine.
- I can refactor common code between multiple states into an intermediate state.
- The complier will enforce that each state has some code to handle each event.
- I can write a pretty understandable state machine even w/o any tools
Some key concerns I have about the pattern:
- Is introducing a class per state going to increase the size of my binaries to the point where it is a problem?
- The state machine code is not as integrated with the rest of the code as I'm used to. This is probably the consequence of making the state machine behavior easy to read.
- Does state pattern make state machines so easy that modeling/code generation is pointless? This is not so much a problem with the pattern, but with running me out of things to talk about in my blog :)
- Would a model to generate code for this pattern have enough in common with models for other state machine implementation patterns?
We'll probably get around to exploring some of these questions in later posts. But I did try the pattern to get some experience with it, and having things to investigate further is to be expected.
What's next
My simple SCTP implementation needs some TLC, but I chose this problem intentionally to stir up some conversations on how to solve some design problems. You may have noticed from the above discussion a small problem with my state machine. Specifically, I'm thinking about this piece of code:
internal class ActiveState : AssociationState
{
public override AssociationState Abort(Association association)
{
var chunk = new AbortChunk();
association.PacketBuilder.EndSend(
association.PacketBuilder.BeginSend(
new Chunk[] { chunk }, null, null));
return AssociationStates.Closed;
}
}
An application would probably call an API called BeginAbort expecting an asynchronous behavior only for it to land here in the state machine and block on a thread due to the synchronous use of EndSend(BeginSend(...)). Obviously there is a problem here. There is an inherent assumption that processing of each event is synchronous. Simply removing the call to EndSend may not be an appropriate solution because upon Send failure, you may not want to go to the Closed state.
This example shows a common theme when working with asynchronous code. Most programming techniques need a modification to work properly. In the next post, I hope to show a way solve this little problem.
Summary
In this post I described the structure of my SCTP prototype, and my state machine implementation using the state pattern. I also pointed out a kind of problem that happens often when reusing existing code or patterns in asynchronous code.
Series
Comments
- Anonymous
May 02, 2011
Interesting Finds: May 3, 2011