View page as slide show

Communications Software Protocols and Architecture

Behavior of Communication systems

  • Communication systems are event driven systems
  • Flow of event driven system is determined by external events.
    • In communication systems the events are the incoming messages
  • Flow of event driven program is not predetermined, so there is a need to describe the event based behaviour of system
    • How the application reacts in different events at different situations.
  • Behaviour model describes the reactions and results for incoming input to the entity
    • Local input e.g. timer, keyboard …
    • external input e.g. incoming messages (PDU or primitive)
  • In communication software CPO (communicating protocol object) have to react to the incoming messages based on the protocol
    • i.e. The entities have to react to events based on the used protocol.
  • In communication systems the events can get in at any point of application running
    • Communication problems can cause for example a loss or repetition of message
    • Connection may get broken before all the data has been sent
    • Malicious people may try to break the system with properly timed messages
  • The behaviour of event driven system is modeled by using finite state machines

Finite state machine (FSM)

  • aka. Finite state automaton
  • Consists of:
    • Finite amount of states in which the entity can be
    • input events (signals, messages…)
    • Transition funtions
      • The conditions on which the state is changed.
    • Output events
  • Formal method to describe behavior

Basic types of FSMs

  • Directed graph
    • shows just state transition
  • Deterministic FSM
    • All the possible inputs are taken into account in all states
    • For each state, there is one and only one transition to next state for each possible input.
  • Non-Deterministic FSM
    • There can be several next states with single input from one state
    • Can be transferred to deterministic FSM

FSM's with output

  • Besides state change the input often causes running of output function
    • print information, send reply messages, quit timer…
  • Moore FSM
    • Output function is determined by the current state. → output is attached to the state
  • Mealy FSM
    • Output function is determined by state and the input. → output is attached to the links between states
    • Common in describing communicating systems
  • Extended FSM (EFSM)
    • state change is associated with a set of input Boolean conditions and a set of output Boolean function.

Formal definition of Mealy FSM

  • Mealy FSM is 6-tuple: MFSM = (S,S0,I,O,T,A)
    • S = Set of States
    • S0 = Start State
    • I = Inputs (e.g. all possible messages that can be received)
    • O = Outputs (e.g. all possible messages that can be sent)
    • T = Transition function that returns next state based on current state and Input
    • A = output function that determines the output based on current state and Input

FSM Transition

  • Transition from one state to another is defined by transition function.
    • transition is triggered by input event.
  • Transition function produces the output and next state
    • Result depends on current state and input event
  • FSM is inactive, when it is in state
    • Waits for an input to perform next activity
  • Some events may cause the state to remain same → transition to itself

Modeling FSM

  • Table based modeling
    • State transition table
    • Input events on rows
    • States on columns
    • Crossing of input event and state describes the transition function
  • Graphical model
    • State transition diagrams
    • State chart (in UML)

FSM as Table

  • all states and inputs must exist
  • Intersection contains first the optional event and then the transition
  • Example: Parity bit counter
    • Three states: idle, s_odd,s_even
      • starts at idle
    • Three Messages: Message 0, Message 1, Finished
input\state idle s_odd s_even
Message 0 s_even s_odd s_even
Message 1 s_odd s_even s_odd
Finished print error
idle
print odd
idle
print even
idle

FSM as Graph

  • States are described as circles
    • name of state is inside circle
    • start state is denoted with double circle
  • State transition is described with arrow
    • Input causing the transition is written by the transition arrow.
  • output is written separated by a line
    • in Moore machine under the state name
    • in Mealy machine under the input

UML State chart

  • State machine description in UML
    • Based of Harell state chart
  • Supports both Mealy and Moore machines
  • Describes the behaviour of an object
    • In communication systems CPO (Communicating protocol object)
  • Is designed for OO software behaviour description
    • Adds hierarchically nested states and orthogonal regions

Basic rules

for drawing state diagrams about communicating system

  • There has to be start state
    • End state is recommended
  • All states have to take into account all possible inputs
    • You should think how your software should react to each input in each state
    • You can use “default” behaviour for all the inputs that you do not think has any special meaning at given state.
  • Conditions can be changed as local inputs to keep state machine deterministic
    • Use whichever solution fits better for your need (e.g. usually which ever is more clear)

Why use state machines

  • Helps design of system
    • Easy to see that all the possible inputs are taken into account in each state
    • Verify that the behaviour matches to MSC's
  • Helps implementation
  • Good for explaining the behaviour of the communication software
    • Easy to see how the system reacts on different events
  • Helps testing of implementation
    • The expected behaviour can be easily found out and thus tested.

State machines in communicating system

  • State machine describes how the incoming messages affect on internal behaviour of the object.
    • Message passing involves sending and receiving messages through a channel
  • Communication system consist of at least two CPO's
    • The behaviour of one CPO affects to the other.
  • Protocol is described in set of communicating FSM's
    • State machines of communicating CPO's are directly linked.
    • Output of sender CPO is input of receiver CPO and vice versa.
    • FSM waits in a state for an event to occur (e.g. message to arrive)

Timers

  • Communication protocols usually rely on timers
    • surviving error condition.
  • Timers are started usually after transition
    • Last for specified time
  • Timer expiration can be handled as timer expire message arrival
  • Different timers may have their own expiration messages

Human and door example

  • Let's have initial thought of model for human to enter class room via door
  • DOOR object
    • Door can be open or closed
      • states: Open, Closed
    • Human can go through the door and open or close the door
      • Inputs (from human): Open door, Close door, Go (through the door)
    • opening, closing or going through can either be success or fail
      • Outputs (to Human): OK, Fail
  • Human object
    • Human can be inside or outside
      • States: outside, inside
    • Brain gives the orders to human what to do
      • Inputs (from brain): open, close, walk
    • Human can go through door, open it or close it.
      • Outputs (to Door): Open door, Close Door, Go
    • Human effort can be success or fail
      • Inputs (from door): OK, Fail
  • When drawing state machine for DOOR there should be no problems.
  • When creating state machine for Human we realise problem.
    • Knowing the state and input is not always enough to determine what we should do.
      • Fail message in outside state can arrive because user tried to open the door when it was open or close because it was closed or go through the door when it was closed.
    • In order to differentiate the situation we need to add states to human
      • new states: Wait_ response_to_getting_in, Wait_response_to_getting_out, wait_opening_inside, wait_opening_outside …
    • Other possibility is to add different outputs to door.
      • new Outputs: Failed_to_open, door_closed …
    • If you cannot change door then you have to change human and vice versa to make your solution be compatible and functional

Exercise

  • Create transition table for Human door interaction
  • Based on transition table draw state diagram.

Summary

  • Finite state machines are used to model the dynamic real-time behaviour of communications software
    • Each CPO (or process) can be defined by a set of states.
  • FSM consist of States (Initial, Current and New), Input Events and Output Events
  • The process waits in a state for an event to occur.
    • Messages are received as events by the receiving FSM.
  • When input event occurs, FSM transitions to another state, and in doing so can send out messages and performs other tasks.
Last modified: 2013/07/01 14:42