GIMPS State Transition Diagrams and Message Processing Rules
Introduction
These pages provide an analysis of the GIMPS protocol in the form of a
set of state transition diagrams and tables, and include notes on the
message processing rules that should be applied for each event/state
combination. The analysis is intended to be complete. It uses the
terminology and operational model of the latest (-05) version of the
specification, GIMPS:
General Internet Messaging Protocol for Signaling, although it may
not be consistent in all details.
The expectation is that some form of this state transition analysis
will be included in future versions of the protocol specification.
Overview
Conceptually, the operation of GIMPS processing at a node may be seen
as the cooperation of 4 types of state machine:
- There is a top-level machine which represents the node itself.
This is responsible for the processing of events which cannot be
directed towards a more specific state machine, for example, inbound
messages for which no per-flow routing state currently exists. This
machine exists permanently, and is responsible for creating 'per-flow'
state machines to manage the operation of the GIMPS handshake and
routing state maintenance procedures.
- For each flow where the node is responsible for initiating the
creation of routing state, there is an instance of a Query-Node routing
state machine. This machine sends Query and Confirm messages and waits
for Responses, according to the requirements from locally generated API
commands or timer processing (e.g. message repetition or routing state
refresh).
- For each flow where the node has accepted the creation of routing
state by a peer, there is an instance of a Responding-Node routing
state machine. This machine is responsible for managing the status of
the routing state for that flow. In some cases, it is also responsible
for retransmission of Response messages; however, in many cases, the
generation of Response messages is handled by the Node level machine,
and the Responding-Node state machine is not even created for a flow
until a properly formatted Confirm has been received.
- Messaging assocations have their own lifecycle, from when they
are first created (in an 'incomplete' state, listening for an inbound
connection or waiting for outbound connections to complete), to when
they are active and available for use.
Conceptually, a fifth machine type (to operate the low-level datagram
mode messaging rules) can also be imagined, including rate control,
bypass operation and so on. This is not considered in the current
analysis; instead, the events have been modelled at a higher level,
after such processing has taken place. What this means in practice is
that not all network events translate (immediately or at all) into
events processed by the state machines listed above.
Note that, apart from the fact that the various machines can be created
and destroyed by each other, there is almost no interaction between
them. The machines for different flows do not interact; the Query and
Response machines for a single flow do not interact.
Notation and Terminology
The state transition diagrams and tables use the following notation and
terminology:
- MA = Message Association.
- *_Dmode_* = event relating to a message transmitted or received
in D-Mode.
- *_Cmode_* = event relating to a message transmitted or received
in C-Mode.
- rx_ = a message received event
- tg_ = a trigger event, either from the API or from another
internal state machine.
- to_ = a timeout event.
- er_ = an error indication event. This may be filtered back to the
NSLP.
Node Level Processing
The Node state machine has only one state. This state machine controls
the top level
processing of GIMPS messages and commands from the GIMPS API.
Incoming messages are handled according to message type, and whether
state may be stored for a particular flow / NSLP. If no state needs to
be stored for a message then the NSLP data is passed up to the NSLP
directly. Otherwise, if a suitable R-Node or Q-Node state machine
already exists the message is passed on to it. If no suitable Q-Node or
R-Node state machine exists then an R-Node state machine is created if
local policy allows.
Incoming API commands are passed directly to the appropriate Q-Node or
R-Node state machine by General Processing, if a suitable one exists.
If the NSLP calls SendMessage for a flow / NSLP for which a Q-Node or
R-Node state machine does not exist then a Q-Node state machine is
created by General Processing, if local policy allows this, and the
event is passed on.
State Transition Diagram State Transition Table
Query-Node Routing State Machine
The Query Node routing state machine has three states:
- Awaiting Response
- Established
- Awaiting Refresh
The Q-Node machine is created by the Node machine as a result of a
request to send a message for a flow where the appropriate state does
not exist. The Query is generated immediately, and the machine
transitions to the Awaiting Response state, in which timout-based
retransmissions are handled. Once a Response has been successfully
recieved and routing state created, the machine transitions to
Established, during which NSLP data can be sent and received normally.
The Awaiting Refresh state can be considered as a substate of
Established, where a new Query has been generated to refresh the
routing state (as in Awaiting Response) but NSLP data can be handled
normally. Further detailed notes are included here.
State Transition Diagram State Transition Table
Responding Node Routing State Machine
The policy governing the creation of the R-Node state machine has 4
cases, and these affect which state the state machine enters first;
they are shown in the following figure:
In case (1), no state machine is ever created. In cases (2) and (3) the
R-Node state machine is created on receipt of a Query message. In case
(3) a timer is required to destroy the R-Node state machine if a valid
Confirm message is not forthcoming. In case (4) the R-Node state
machine cannot be created until a valid Confirm message is received.
It should be noted that in case (4) the R-Node state machine is only
created if the full Query / Response / Confirm sequence is completed.
If the Confirm message is lost, and a data message is received instead
the General Processing state machine recognises that the incoming
message does not have the required Response cookie and returns an error
to the remote node.
Apart from this policy freedom, the R-Node state machine is very
simple: it has two states, Awaiting Confirm and Established. The state
entered on creation of the R-Node state machine depends on which of the
above policies is in place for a given flow / NSLP. Creation of the
R-Node state machine is controlled by the General Processing state
machine.
In the state transition diagram itself, (2), (3) and (4) show the
effects of the policies outlined above. More detailed processing notes
are contained here.
State Transition Diagram State Transition Table
Messaging Association Model
Messaging associations are modelled for use within GIMPS with a simple
2-state process, which is either waiting for the connection process to
complete, or open and ready to use. Clearly, many internal details of
the messaging assocation protocols are hidden in this model, especially
where the messaging association uses multiple protocol layers; however,
the specification of these is left up to the individual protocol
definitions. Note also that although the existence of messaging
associations is not directly visible to NSLPs, there is some
interaction between the two because security-related information
becomes available during the open process, and this may be indicated to
signalling applications if they have requested it. More detailed notes
are contained here.
State Transition Diagram State Transition Table