Sign in to follow this  

finite state machines (fsm) and networking

This topic is 3485 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I dont know very much about finite state machines - but do they have any application to the handling of network protocols?. As an example take an ftp server where there are a bunch of connections, that need to be managed in different ways, both active and passive, and taking into account the ability of the client to initiate transfers as well as handling timeouts, socket errors, dns resolution etc. A lot of this would seem like it could be captured as basic state changes. Also what would be the drawbacks of such an approach. I am presently using c++ and boost::asio which I really like for its async event driven approach - but at a slightly higher abstraction, my code is starting to become complicated when there are lots of logical interactions going on. There is an interesting article on wikipedia discussing event based fsm Event-driven finite state machine which would seem sort of applicable. Additionally is there anything that automatically generates template code for fsm - for example going from a diagram to code or even from a more high level textual representation to code (like parser generators yacc,lex etc). I am normally a bit distrustful of code template generation stuff (ie uml applications) but am curious to know if something like this might exist. <edit for clarity>

Share this post


Link to post
Share on other sites
FSMs aren't magical beasts. They have many, many applications and sure, I use them for managing my connection states. Each state performs a different function (send connection request, send handshakes, send keep alives, send disconnection request...).

if you look at this page under external links, you'll see some sourceforge projects to help you out design your FSMIf like that sort of stuff, look for UML code generators as well.

Although in my opinion, I'm not sure they warrant the use of complicated tools. They are simple enough in most cases (states, set of actions, then transition to another state). Unless you really want to go nuts with them... not sure if Boost has some tool for templated FSMs code.

....sure enough, here you go.

Share this post


Link to post
Share on other sites
Quote:
Original post by chairthrower
I dont know very much about finite state machines - but do they have any application to the handling of network protocols?.


Some FSM are Turing complete. There's people who argue they are optimal programming model, and they are even right in some cases.

Protocols are even designed with them. So yes, they do have applications.

Quote:
As an example take an ftp server where there are a bunch of connections, that need to be managed in different ways, both active and passive, and taking into account the ability of the client to initiate transfers as well as handling timeouts, socket errors, dns resolution etc. A lot of this would seem like it could be captured as basic state changes. Also what would be the drawbacks of such an approach.


In general, once you implement the protocol itself, there will be only a handful of stateless functions that need to be implemented.

Quote:
I am presently using c++ and boost::asio which I really like for its async event driven approach - but at a slightly higher abstraction, my code is starting to become complicated when there are lots of logical interactions going on.


That is the consequence of async programming model. ASIO is closer to active objects than FSM, although they are conceptually related.

Both models are very suitable for concurrent programming, but in C++, they aren't necessarily user friendly, as they can lead to convoluted code.


FSMs won't solve your code complexity problems compared to ASIO. If anything, they'll make it worse.

If you're looking into user-friendly async logic, look into futures, and perhaps even Lua. The later can be made async with little effort using cooperative threading, and ASIO can provide the scheduling logic behind that.

Those would allow you to write sequential code that is still fine-grained and async.

FSM-like programming model is often used for network handlers, but not higher-level logic. i've also seen elaborate FSMs used for AI.

As the saying goes: "Some people, when confronted with a problem, think
“I know, I'll use regular expressions.” Now they have two problems."

Quote:
Additionally is there anything that automatically generates template code for fsm


Lex/Yacc convert some syntax into FSM. Protocols are defined as FSM already, so there's no need for conversion. Just implement the state tables and use switch. That said, I'm sure that work has been done around this, but I don't see any huge benefit in doing so. Implementing, for example, TCP FSM is fairly straight-forward and trivial task.

The main problems you're encountering come more from event-driven programming model than networking itself. C++ doesn't really do much to help with that.

Share this post


Link to post
Share on other sites
Thanks a lot for the really imformative replies.

Quote:
Although in my opinion, I'm not sure they warrant the use of complicated tools.


Yes i think that you are right - I plan to confine my experiments to hard coding although the fsm designer you link to looks good. argg - my repsository adds a versioning extension to the qt moc binaries and the configure is not picking it up. will need to fiddle a bit more.

Quote:
If you're looking into user-friendly async logic, look into futures, and perhaps even Lua. The later can be made async with little effort using cooperative threading, and ASIO can provide the scheduling logic behind that.


I really like the idea of active objects and specifically the non shared state concurrency aspects. (i dont have the background to understand the higher order aspects of things like join and pi calculus that i sometimes see in discussions). it is relatively simple to create a model whereby you register for events on an object as well as post events to objects but at least in my practical experiments there often seems to be a requirement to query the state on an object (ie state info accessor).

the round trip messaging aspect of this operation is slow if using threading concurrency because of the needed context switch in the dispatch processing pump of the subject - although it could be made acceptable (as you note) with cooperative multitasking (fibres). the thing that bothers me about futures with an active object model is that they would appear (to me) to break the deadlock free guarantees that exist, even if they help alleviate the headache of implementing code on the client side ( having to split the functionality for handling the request state info message and for the returned message containing said state information).

Quote:
“I know, I'll use regular expressions.” Now they have two problems."


this is a pretty strong advice against needlessly mixing programming models, but would there be any advantage in encapsulating a fsm inside an active object. for example the message inbox of the active object takes a message which will trigger a state transition and will perhaps also broadcast messages to other interested active objects (eg other spawned network connections). this input message could come from other active objects or from internally encapsulated low level networking object stuff. To try and make it concrete in my mind i wrote a very light c++ example.

If anyone has the time and would like to critique the design please do so (excuse the implementation detail of strings which should probably be enums).

the idea is that low level network socket/acceptor stuff is encapsulated and we bind the msg that we want sent back to the messaging inbox for fsm transition with the asio callback. but the messaging inbox can also process messages from external active objects (eg a spawned ftp transfer connection).

 struct fsm
: public boost::enable_shared_from_this<fsm>
{

typedef boost::shared_ptr< fsm> ptr;

tcp::socket socket_;

tcp::acceptor acceptor_;

string state;


fsm( boost::asio::io_service& io_service)
: socket_( io_service)
// , acceptor_( io_service)
, acceptor_( io_service, tcp::endpoint( tcp::v4(), 10003))
{
transition_to( "init");
}

void transition_to( const string &s)
{
cout << "state: " << quote( state) << " --> " << quote( s) << endl;
state = s;
}

void post_asio_message( const string &success, const string &failure, const boost::system::error_code &error)
{
// for an asio message interpret the message to post according to failure or success condition
string msg = error ? failure : success;
post_message( msg, error);
}

void post_message( const string &msg, const any &payload)
{
// post message can take messages comming from the encapsulated asio objects or from
// external objects to trigger state change

cout << "state: " << quote( state) << " msg is " << quote( msg) << endl;

if( state == "init")
{
if( msg == "start") {

acceptor_.async_accept( socket_,
boost::bind( &fsm::post_asio_message, shared_from_this(), "got_connection", "got_connection_failed",_1));

transition_to( "listening");
}
else assert( 0);
return ;
}

else if( state == "listening")
{

if( msg == "got_connection")
{
cout << "tcp_server.handle_accept() "
<< " local " << socket_.local_endpoint() << " <--"
<< " remote " << socket_.remote_endpoint() << endl;
// eg could issue authentication challenge and transition to next state
// but keep it simple for moment
string message = "hi there\n";
vector< char> write_buf( message.begin(), message.end());

boost::asio::async_write(
socket_,
boost::asio::buffer( write_buf),
// should have explicit policy here
boost::bind( &fsm::post_asio_message, shared_from_this(), "wrote_data", "wrote_data_failed",_1));

transition_to( "writing");
return;
}

else if( msg == "got_connection_failed")
{
cout << msg << " " << any_cast< boost::system::error_code>( payload).message() << endl;
transition_to( "close");
return;
}
else if( msg == "timout" )
{
// ...
}
else if( msg == "timout_failed" )
{
// ...
}
else if( msg == "reconfigure")
{
// ...
}
else if( msg == "stop")
{
// ...
}
assert( 0);
return ;
}

else if( state == "writing")
{
// in fact socket is is probably closed automatically when nothing registered against it
if( msg == "wrote_data_failed") {
// ahhh but
socket_.close();
transition_to( "finished");
}
if( msg == "wrote_data") {
socket_.close();
transition_to( "finished");
}
// other messages
else assert( 0);
}

else
assert( 0);
}
};



Share this post


Link to post
Share on other sites
Quote:
the idea is that low level network socket/acceptor stuff is encapsulated and we bind the msg that we want sent back to the messaging inbox for fsm transition with the asio callback. but the messaging inbox can also process messages from external active objects (eg a spawned ftp transfer connection)


The implementation is the typical protocol handler loop. As you said, strings are sub-optimal. This type of handlers is usually very light-weight. Since you know the transitions, you can calculate the transition/event table in advance. Perhaps even use tokenizer to parse the incoming requests.

Quote:
but would there be any advantage in encapsulating a fsm inside an active object


Active objects are basic FSM. They carry state, and can only be modified by single thread at any given time and all AO communicate via messages. They have very rich alphabet, and likely very large number of states, but since they act as handlers for messages, they behave just like FSM. This is part of basic premise behind AO - FSM is known to work well for parallel programming. But typical model of trivial alphabet and states is too limited, so they offer rich programming model.

The problem occurs with complex actions, which require cooperation and consistency between multiple AO, especially if they're running in multiple threads.

One way of solving this is to encapsulate all the logically local logic into same AO, so that every operation performed on it is transactional (if something throws an exception, you can let the running AO handle it appropriately, and revert to sane state).

But as far as protocol handler is concerned - it should be single-threaded (perhaps singletonish in nature), and trivial in implementation. You basically need a handful of events: connect/disconnect/timeout/error + one for each operation (on_receive as the generic, or more specific on_request_file, on_authenticate,...).

Share this post


Link to post
Share on other sites
I switched to asio stream buffers, and made the thing table driven using a key tuple based on the current state and the recieved message which then map to handler methods contained an associatative array. Also followed through with your idea of a pre- lex of the stream to propagate up the protocol command processing to be handled using the same state transition table. its nice that its possible to concisely fill the transition map with multiple default entries (such as generic timeout, generic socket error) by just using a loop to populate entries (which would not be possible with a fsm textual representation which was one of my questions in the initial post).

that said i am not completely convinced by the approach and feel a bit more thought/experimentation is needed. I see that in some cases a synch handling approach leads to cleaner code - as you suggested by using asio as a driver). Two things I do like about having an explicit cycling variable representing the mode/state is that its a very good source for log reporting and also that changes to the state can wrap the need (couple of lines of code) as a general source of notification events that need to be registered for by other connection objects (eg spawned ftp transfer).

thanks for your valuable insights and conceptually connecting the AO / fsm dots - there are lots of good ideas there.

Share this post


Link to post
Share on other sites

This topic is 3485 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this