Hierarchical State Machine

In this article, we will be highlighting the advantages of hierarchical state machine design over conventional state machine design.

In conventional state machine design, all states are considered at the same level. The design does not capture the commonality that exists among states. In real life, many states handle most  messages in similar fashion and differ only in handling of few key messages. Even when the actual handling differs, there is still some commonality. Hierarchical state machine design captures the commonality by organizing the states as a hierarchy. The states at the higher level in hierarchy perform the common message handling, while the lower level states inherit the commonality from higher level ones and perform the state specific functions. The table given below shows the mapping between conventional states and their hierarchical counterparts for a typical call state machine.

Conventional States Hierarchical States
Awaiting First Digit Setup.CollectingDigits.AwaitingFirstDigit
Collecting Digits Setup.CollectingDigits.AwaitingSubsequent Digits
Routing Call Setup.RoutingCall
Switching Path Setup.SwitchingPath
Conversation Conversation
Awaiting Onhook Releasing.AwaitingOnhook
Releasing Path Releasing.ReleasingPath

 A conventional state machine is designed as a two dimensional array with one dimension as the state and the other dimension specifying the message to be handled. The state machine determines the message handler to be called by indexing with the current state and the received message. In real life scenario, a task usually has a number of states along with many different types of input messages. This leads to a message handler code explosion. Also, a huge two dimensional array needs to be maintained. Hierarchical state machine design avoids this problem by recognizing that most states differ in the handling of only a few messages. When a new hierarchical state is defined, only the state specific handlers need to be specified.

Conventional State Machine Example

The figure below describes the state transition diagram for an active standby pair. The design here assumes that the active and standby are being managed by an external entity.

Conventional state transition diagram

The different states for the state machine are Active, Standby, Suspect and Failed. The input messages to be handled are Switchover, Fault Trigger, Diagnostics Passed, Diagnostics Failed and Operator Inservice. Thus the handler two dimensional array is 4 x 5 i.e. 20 handlers need to be managed. 

The code below shows the handlers that need to be defined. A dummy "do nothing" handler should be specified for all other entries of the two dimensional state table. This simple example clearly illustrates the problem with conventional state design. There is a lot of code repetition between handlers. This creates a maintenance headache for state machine designers. We will see in the following section that hierarchical state machine design exploits these very similarities to implement a more elegant state structure. 

Conventional State Machine Implementation

/* == Active State Handlers == */
void ActiveStateFaultTriggerHandler(Msg *pMsg)
 {
    PerformSwitchover();            // Perform Switchover, as active failed
    NextState = SUSPECT;            // Run diagnostics to confirm fault
    SendDiagnosticsRequest();
    RaiseAlarm(LOSS_OF_REDUNDANCY); // Report loss of redundancy to operator
 }
 
void ActiveStateSwitchoverHandler(Msg *pMsg)
{
  PerformSwitchover();              // Perform Switchover on operator command
  CheckMateStatus();                // Check if switchover completed
  SendSwitchoverResponse();         // Inform operator about switchover
  NextState = STANDBY;              // Transition to standby
}

/* == Standby State Handlers == */
void StandbyStateFaultTriggerHandler(Msg *pMsg)
{
  NextState = SUSPECT;              // Run diagnostics to confirm fault
  SendDiagnosticsRequest();
  RaiseAlarm(LOSS_OF_REDUNDANCY);   // Report loss of redundancy to operator
}

void StandbyStateSwitchoverHandler(Msg *pMsg)
{
  PerformSwitchover();              // Perform switchover on operator command
  CheckMateStatus();                // Check if switchover completed
  SendSwitchoverResponse();         // Inform operator about switchover
  NextState = ACTIVE;               // Transition to active
}

/* == Suspect State Handlers == */
void SuspectStateDiagnosticsFailedHandler(Msg *pMsg)
{
   SendDiagnosticsFailureReport();   // Inform operator about diagnostics
   NextState = FAILED;               // Move to the failed state
}

void SuspectStateDiagnosticsPassedHandler(Msg *pMsg)
{
   SendDiagnosticsPassReport();      // Inform operator about diagnostics
   ClearAlarm(LOSS_OF_REDUNDANCY);   // Clear loss of redundancy alarm
   NextState = STANDBY;              // Move to standby state
}

void SuspectStateOperatorInservice(Msg *pMsg)
{
   // Operator has replaced the card, so abort the current diagnostics
   // and restart new diagnostics on the replaced card.
   AbortDiagostics();   
   SendDiagnosticsRequest();         // Run diagnostics on replaced card
   SendOperatorInserviceResponse();  // Inform operator about diagnostics start
}
/* == Failed State Handlers == */
void FailedStateOperatorInservice(Msg *pMsg)
{
   SendDiagnosticsRequest();         // Run diagnostics on replaced card
   SendOperatorInserviceResponse();  // Inform operator about diagnostics start
   NextState = SUSPECT;              // Move to suspect state for diagnostics
}

Hierarchical State Machine Example

The following state transition diagram recasts the state machine by introducing two levels in the hierarchy. Inservice and Out_Of_Service are the high level states that capture the common message handling. Active and Standby states are low level states inheriting from Inservice state. Suspect and Failed are low level states inheriting from Out_Of_Service state.

Hierarchical state transition diagram

The following diagram clearly illustrates the state hierarchy. Even the Inservice and Out_Of_Service, high level states inherit from the Unit_State that is at the highest level.

State hierarchy for Unit

Hierarchical State Machine Source Code

The C++ implementation details of the hierarchical state machine are given below. It is apparent that all the commonality has moved to the high level states viz. Inservice and Out_Of_Service. Also, contrast this with the conventional state machine implementation.

The code below contains hyperlinks to more detailed information about the classes, methods and variables in this information.

Header File

The header file below declares the Unit state machine using the Hierarchical_State_Machine  class. Important points to note are:

 

Hierarchical_State_Machine.h
00001 
00002 class Message;
00009 
00010 
00011 
00031 
00032 class Hierarchical_State_Machine
00033 {
00037 
00038     class Unit_State
00039     {
00040     public:
00041 
00043         virtual void On_Switchover(Hierarchical_State_Machine &u, 
                                           const Message *p_Message)  {} 
00044 
00046         virtual void On_Fault_Trigger(Hierarchical_State_Machine &u, 
                                              const Message *p_Message) {}  
00047 
00049         virtual void On_Diagnostics_Failed(Hierarchical_State_Machine &u, 
                                                   const Message *p_Message) {}
00050 
00052         virtual void On_Diagnostics_Passed(Hierarchical_State_Machine &u, 
                                                   const Message *p_Message) {}
00053 
00055         virtual void On_Operator_Inservice(Hierarchical_State_Machine &u, 
                                                   const Message *p_Message) {}      
00056     };
00057     friend Unit_State;   
00058 
00059 
00062 
00063     class Inservice : public Unit_State
00064     {
00065     public:
00066         void On_Switchover(Hierarchical_State_Machine &u, 
                                 const Message *p_Message);   
00067         void On_Fault_Trigger(Hierarchical_State_Machine &u, 
                                    const Message *p_Message);
00068     };
00069     friend Inservice;   
00070 
00075 
00076     class Active : public Inservice
00077     {
00078     public:
00079         void On_Switchover(Hierarchical_State_Machine &u, 
                                 const Message *p_Message);   
00080         void On_Fault_Trigger(Hierarchical_State_Machine &u, 
                                    const Message *p_Message);
00081     };
00082     friend Active;    
00083 
00088 
00089     class Standby : public Inservice
00090     {
00091     public:
00092         void On_Switchover(Hierarchical_State_Machine &u, 
                                 const Message *p_Message);   
00093     }; 
00094     friend Standby;   
00095 
00098 
00099     class Out_Of_Service : public Unit_State
00100     {
00101     public:
00102         void On_Operator_Inservice(Hierarchical_State_Machine &u, 
                                         const Message *p_Message);
00103     };
00104     friend Out_Of_Service;    
00105 
00109     class Suspect : public Out_Of_Service
00110     {
00111     public:
00112         void On_Diagnostics_Failed(Hierarchical_State_Machine &u, 
                                         const Message *p_Message);
00113         void On_Diagnostics_Passed(Hierarchical_State_Machine &u, 
                                         const Message *p_Message);
00114         void On_Operator_Inservice(Hierarchical_State_Machine &u, 
                                         const Message *p_Message);
00115     };
00116     friend Suspect;    
00117 
00121     class Failed : public Out_Of_Service
00122     {
00123     public:
00124         // No Need to Override any other method
00125     };
00126     friend Failed;    
00127 
00128 private:
00129     static Active Active_State;   
00130     static Standby Standby_State; 
00131     static Suspect Suspect_State; 
00132     static Failed Failed_State;   
00133 
00134     void Next_State(Unit_State &r_State);
00135     
00136 
00137     // Common Methods invoked from several states
00138     // (See article on FSM Inheritance for details)
00139     virtual void Send_Diagnostics_Request();
00140     virtual void Raise_Alarm(int reason);
00141     virtual void Clear_Alarm(int reason);
00142     virtual void Perform_Switchover();
00143     // . . .
00144     virtual void Send_Switchover_Response();
00145     virtual void Send_Operator_Inservice_Response();
00146     virtual void Send_Diagnostics_Failure_Report();
00147     virtual void Send_Diagnostics_Pass_Report();
00148     virtual void Abort_Diagnostics();
00149     virtual void Check_Mate_Status();
00150     Unit_State *p_Current_State;   
00151 
00152 public:
00153     void On_Message(const Message *p_Message);
00154 };
00155 
00159 
00160 void Hierarchical_State_Machine::Next_State(Unit_State &r_State)
00161 {
00162     p_Current_State = &r_State;
00163 }
00164 
00165 

Source File

Important things to note about the source file:

 

Hierarchical_State_Machine.cpp
00007 
00008 #include "Hierarchical_State_Machine.h"
00009 #include "Unit_Messages.h"
00010 #include "assert.h"
00011 
00016 
00017 void Hierarchical_State_Machine::On_Message(const Message *p_Message)
00018 {
00019     switch (p_Message->GetType())
00020     {
00021     case Message::FAULT_TRIGGER:
00022         p_Current_State->On_Fault_Trigger(*this, p_Message);
00023         break;
00024 
00025     case Message::SWITCHOVER:
00026         p_Current_State->On_Switchover(*this, p_Message);
00027         break;
00028 
00029     case Message::DIAGNOSTICS_PASSED:
00030         p_Current_State->On_Diagnostics_Passed(*this, p_Message);
00031         break;
00032 
00033     case Message::DIAGNOSTICS_FAILED:
00034         p_Current_State->On_Diagnostics_Failed(*this, p_Message);
00035         break;
00036 
00037     case Message::OPERATOR_INSERVICE:
00038         p_Current_State->On_Operator_Inservice(*this, p_Message);
00039         break;
00040 
00041     default:
00042         assert(false);
00043         break;
00044     }
00045 }
00046 
00055 
00056 void Hierarchical_State_Machine::Inservice::On_Fault_Trigger(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00057 {
00058     u.Next_State(u.Suspect_State);
00059     u.Send_Diagnostics_Request();
00060     u.Raise_Alarm(LOSS_OF_REDUNDANCY);
00061 }
00062 
00070 
00071 void Hierarchical_State_Machine::Inservice::On_Switchover(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00072 {
00073     u.Perform_Switchover();
00074     u.Check_Mate_Status();
00075     u.Send_Switchover_Response();
00076 }
00077 
00088 
00089 void Hierarchical_State_Machine::Active::On_Fault_Trigger(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00090 {
00091     u.Perform_Switchover();
00092     Inservice::On_Fault_Trigger(u, p_Message);  
00093 }
00094 
00100 
00101 void Hierarchical_State_Machine::Active::On_Switchover(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00102 {
00103     Inservice::On_Switchover(u, p_Message);
00104     u.Next_State(u.Standby_State);
00105 }
00106 
00112 
00113 void Hierarchical_State_Machine::Standby::On_Switchover(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00114 {
00115     Inservice::On_Switchover(u, p_Message);
00116     u.Next_State(u.Active_State);
00117 }
00118 
00127 
00128 void Hierarchical_State_Machine::Out_Of_Service::On_Operator_Inservice(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00129 {
00130     // Operator has replaced the card, so abort the current diagnostics
00131     // and restart new diagnostics on the replaced card.  
00132     u.Send_Diagnostics_Request();
00133     u.Send_Operator_Inservice_Response();
00134     u.Next_State(u.Suspect_State);
00135 }
00136 
00142 
00143 void Hierarchical_State_Machine::Suspect::On_Diagnostics_Failed(
                                         Hierarchical_State_Machine &u, 
                                         const Message *p_Message)
00144 {
00145     u.Send_Diagnostics_Failure_Report();
00146     u.Next_State(u.Failed_State);
00147 }
00148 
00155 
00156 void Hierarchical_State_Machine::Suspect::On_Diagnostics_Passed(
                                                  Hierarchical_State_Machine &u, 
                                                  const Message *p_Message)
00157 {
00158     u.Send_Diagnostics_Pass_Report();
00159     u.Clear_Alarm(LOSS_OF_REDUNDANCY);
00160     u.Next_State(u.Standby_State);
00161 }
00162 
00167 
00168 void Hierarchical_State_Machine::Suspect::On_Operator_Inservice(
                                                  Hierarchical_State_Machine &u, 
                                                  const Message *p_Message)
00169 {
00170     u.Abort_Diagnostics();
00171     Out_Of_Service::On_Operator_Inservice(u, p_Message); 
00172 }

 

Explore More ...
Click here to open Hierarchical State Machine Documentation in a new window Hierarchical State Machine Documentation
Click here to download Hierarchical State Machine Source Code Hierarchical State Machine Source Code