Methods and apparatus for prioritizing message flows in a state machine execution environment

A method and apparatus are provided for prioritizing message flows in a state machine execution environment. A state machine is disclosed that employs a flow graph that provides a flow control mechanism The flow control mechanism defines a plurality of states and one or more transitions between the plurality of states, wherein one or more tokens circulate within the flow graph and execute functions during the one or more transitions between the states The disclosed state machine parses one of the tokens to extract one or more predefined information elements; and assigns a priority to the token based on the extracted information elements and a state occupancy of the token, wherein the assigned priority controls an order in which the token is processed.

FIELD OF THE INVENTION

The present invention relates to message processing techniques and, more particularly, to techniques for prioritizing message flows in a state machine execution environment

BACKGROUND OF THE INVENTION

Software applications are often constructed using an abstract state description language Voice over Internet Protocol (IP) (or VoIP) call control applications, for example, have been realized by using a high level description language to describe the data processing and message exchange behavior of a VoIP Media Gateway Controller (MGC). In this system, an “execution engine” accepts a high level “graph language” used by the execution engine to create internal data structures that realize the VoIP MGC behaviors described in the input graph language. The combination of the execution engine and the input file that contains the graph language describing the VoIP MGC behavior results in a system that exhibits the desired MGC processing characteristics

The description language supports an enhanced transition graph model. As a result, the computation can be best understood as a graph consisting of a set of nodes connected by arcs. Using this model, there may be many tokens that exist at a given node The arcs represent transitions that tokens take between nodes. Tokens traverse arcs in response to events that can be derived from either timers or messages.

In many systems, especially those that implement VoIP call control, the system must perform predictably in the face of high demand, such as spikes of traffic Typically, a call flow will be started with an event in the form of a message, generated on behalf of a user, when a user goes off-hook or completes entering a telephone number of a desired destination. The initial event will be followed by a series of message exchanges used by the specific protocol to move the call into a quiescent state

In a conventional system under heavy or overload conditions, all messages (and therefore transitions between states) will be given an equal priority This may result in a delay for the completion of a call setup message sequence (representing a call accepted by the system and already in progress), as requests for new service (e.g., a new call) will compete for resources with calls that are already in the process of being torn down. Thus, additional resources will be expended for a given offered load, as the system will not give precedence to a call in a tear-down phase that would be returning resources to the system.

A need therefore exists for an improved state machine execution environment that prioritizes message flows.

SUMMARY OF THE INVENTION

Generally, a method and apparatus are provided for prioritizing message flows in a state machine execution environment. According to one aspect of the invention, a state machine is disclosed that employs a flow graph that provides a flow control mechanism. The flow control mechanism defines a plurality of states and one or more transitions between the plurality of states, wherein one or more tokens circulate within the flow graph and execute functions during the one or more transitions between the states. The disclosed state machine parses one of the tokens to extract one or more predefined information elements; and assigns a priority to the token based on the extracted information elements and a state occupancy of the token, wherein the assigned priority controls an order in which the token is processed.

For example, the extracted information elements can comprise one or more name/value pairs As used herein, the state occupancy is a position of the token in the flow graph. The assigned priority can be based, for example, on an effect that a particular transition by the token will have on other resources In further variations, the assigned priority can be based, for example, on one or more of an amount of computation resources required by the token; a time sensitivity of the token; a determination of whether the token includes idle time and a determination of whether a response is expected by another entity to the token In one embodiment, the flow graph is a call flow graph that controls a processing of call control messages and wherein the functions include one or more of sending messages to other tokens and to external devices; and parsing incoming messages from other tokens or external devices.

According to another aspect of the invention, a higher priority can be assigned to a token that will trigger a transition that will return one or more currently used system resources to an available status The state machine can optionally assign the token to one of a plurality of priority-based queues In addition, the state machine can optionally dynamically adjust a priority assigned to the token based on an overload status. The state machine can discard one or more lower priority tokens when a priority queue of a predefined priority level is full.

DETAILED DESCRIPTION

The present invention provides methods and apparatus for prioritizing messages flows within a formal state machine execution environment. As used herein, a flow control mechanism defines a plurality of states (or nodes) in a graph and the transition arcs between such states. The present invention provides a state machine execution environment that employs an explicit flow control mechanism. According to one aspect of the invention, the disclosed state machine execution environment employs a two-stage processing of messages. In a first stage, a preliminary pass is performed over messages (or selected portions thereof) to extract information, such as one or more name/value pairs, that can be employed to prioritize the message. In a second stage, the messages are processed using the context of the computation to choose a specific message parsing behavior

Using a combination of the preliminary parsing in the first stage and the position of the target token in the call flow graph (referred to herein as the “state occupancy” of the token), it is possible to assign a priority to the subsequent processing of the message within the formal state machine execution environment. The assigned priority can be used to control the order in which messages are processed

In general, the prioritization can be based on, for example, the effect that a particular state transition has on other resources. In various embodiments, the prioritization can be based, for example, one or more of the amount of required computation resources, the time sensitivity of the message, whether the required message processing includes idle time, and whether a prompt response is expected to the message. If no response is expected, the recipient can typically replay the message out of order In addition, using the assigned priority, call flows that are in the process of being set up, or being torn down, can be assigned a higher priority, thus minimizing the peak resources needed by the system to function responsively and those providing extra margin for handling overload.

According to another aspect of the invention, a conditional prioritization technique can be employed. Building upon the information that is available to the execution engine as a side effect of prioritization of the messages, the queue length of the lower priority messages can be used to set a dynamic policy for treatment of message processing. Since in this system, messages are partially processed upon reception, this mechanism can be used to selectively discard unassociated messages (i.e., messages that are not part of an existing call flow/computation) and/or unsolicited messages (i.e., messages that are not expected responses)

In a conditional prioritization implementation, as the load on the system teaches a predefined threshold, such as a “yellow zone” queue length of the lower priority messages currently waiting processing, the system would start to discard messages currently unassociated with a current flow. If the queue length of the lower priority messages continues to grow, reaching a predefined “red zone,” the system begins to discard messages that are associated but are unsolicited. As the queue length shrinks below each of the thresholds described above, the system ceases discarding the related class of messages. In this way, the system will maximize its ability to properly handle extreme spikes in message traffic, minimizing the impact on memory and processing burden on the host system.

While the present invention is illustrated herein in the context of an exemplary Voice over Internet Protocol Media Gateway Controller, the present invention may be employed in any environment where a number of tokens circulate within a flow graph in a state machine and execute functions during transitions between states, as would be apparent to a person of ordinary skill in the art.

FIG. 1illustrates an exemplary network environment100in which the present invention can operate. The exemplary network environment100is a Voice over Internet Protocol call control environment. As shown inFIG. 1, a personal call agent110connected to one or more VoIP Gateways130-1through130-N by an IP network120, route Voice over Internet Protocol telephone calls to or from one or more end users140-1through140-N Generally, the personal call agent110provides multi-protocol VoIP call control, in a known manner. For example, the personal call agent110can provide protocol translation between one or more of the following well-known VoIP protocols: SIP, H 248, MGCP, IPDC/Q 931 and SS7/M2UA.

As discussed further below in conjunction withFIG. 3, the personal call agent110reduces the call flow into a combination of state and name/value pairs to enable the above-mentioned protocol inter-working It is noted that in a distributed model, multiple instances of the personal call agent110can create dynamic associations to provide call control to end users.

As discussed hereinafter, in the exemplary embodiment, the functionality of the present invention resides in the personal call agent110. In this example, the VoIP control is being managed by the personal call agent110, and the desired behavior is created by managing the messages at the personal call agent110without burdening the gateway130with additional processing requirements.

FIG. 2illustrates an implementation of the personal call agent110using a state machine execution environment incorporating features of the present invention. As previously indicated, software applications, such as the exemplary Voice over Internet Protocol (IP) (or VoIP) call control applications, are often constructed using an abstract state description language. As shown inFIG. 2, the personal call agent110includes an execution engine220(i.e., a virtual machine) that accepts a graph language210that describes the media gateway controller functions. The graph language210is used by the execution engine220to create internal data structures230that realize the VoIP MGC behaviors described in the input graph language210The combination of the execution engine220and the input file210that contains the graph language describing the VoIP MGC behavior results in a system that exhibits the desired MGC processing characteristics. Thus, the personal call agent110is a combination of a protocol engine220and a set of data files230.

As discussed further below in conjunction withFIG. 3, the data files230explicitly define the call flow in terms of state transitions and message translations Generally, as discussed further below, a call flow is read into the personal call agent110and instantiated at start up time.

FIG. 3illustrates an exemplary call flow graph300(or mole generally, a “flow graph”) The desired service is realized in the personal call agent110using a flow representation of the computation. As shown inFIG. 3, the call flow graph300provides a flow control mechanism that defines a plurality of states (or nodes)310-1through310-N (hereinafter, collectively referred to as states310) and the transition arcs320-1through320-N (hereinafter, collectively referred to as transitions320) between such states310.

Generally, a number of tokens (corresponding to messages in the exemplary VoIP environment) circulate within the graph300and execute functions during transitions320between states310. In the exemplary VoIP environment, the transition functions include sending messages to other tokens and to external devices; and parsing incoming messages from other tokens or external devices.

FIG. 4illustrates an exemplary portion of a call flow graph400incorporating features of the present invention Generally, a “graph function” is a function invoked at an entry state that causes the engine to pass control back to the calling state rather than to an arbitrary next state. The graph function comprises one or more states The effect is that there is a set of states that are partitionable, starting with the entry state and including all of the reachable states up to the state that uses a “graph return” to send control back to the entry state. A portion of a graph, such as the graph300ofFIG. 3, can be considered to be a set of graph functions.

As shown inFIG. 4, an entry state410has a first transition415to an intermediate state420. The intermediate state420has a second transition425to a returning state430. The returning state430has a third transition435that uses a graph return to pull the next state from a graph stack450, in a known manner. The “graph call” function executed at the entry state410pushes its own state number onto the graph stack450to be used later by the “graph return” method invoked by the returning state430.

FIG. 5illustrates the processing of VoIP control messages515in accordance with an embodiment of the present invention. As shown inFIG. 5, the VoIP control messages515, such as an exemplary input message parsing file520, are applied to the exemplary call flow graph300ofFIG. 3The call flow graph300is defined by a call flow definition file550. Thus, the call flow definition file550is an example of the input graph language210ofFIG. 2

As previously indicated, a number of tokens (e.g., corresponding to messages520) circulate within the graph300and execute functions during transitions between states. In the exemplary VoIP environment, the transition functions include sending messages to other tokens and to external devices; and parsing incoming messages from other tokens or external devices. In the example shown inFIG. 5, a transition function triggers the generation of an output message generation file530

FIG. 6illustrates exemplary pseudo-code for a message handling process600incorporating features of the present invention. As shown inFIG. 6, the message handling process600initially determines during step605if any priority queue is full. If any priority queue is full, then the oldest message is selected during step610from the highest priority queue. The selected message is processed and control is passed to the associated token before the process600returns.

During step620, the process determines if there are additional incoming messages to be processed that are waiting on the server input by the state machine. If there are additional incoming messages, the message is partially parsed during step625to recover information that relates the message to a particular token. If a token not found, then the message is assigned to a base token.

A test is performed during step630to determine if the state machine is in an overload condition. If the state machine is in an overload condition, the state of the token is examined during step635to determine an appropriate input message handling priority. The message is then placed in a priority queue.

If it is determined during step640that the message has an immediate priority, then the message is processed to completion and control is passed to that token. Thereafter, the process600breaks out of the while “incoming messages” loop during step645

If the message does not have an immediate priority, then the process600continues at the top of the while “incoming messages” loop during step650to check for more messages waiting on input.

If the state machine is not in an overload condition, the message is processed during step660and control is passed to the token. Thereafter, the process600breaks out of the while “incoming messages” loop during step665

If it is determined during step675that either priority queue is full, then the oldest message is selected during step680from highest priority queue, the selected message is processed, and control is passed to the associated token. Thereafter, the process600breaks out of the while “incoming messages” loop during step685.

During step698, the process600selects the oldest message from the highest priority queue, processes the selected message and passes control to the associated token before returning.

WhileFIG. 6shows an exemplary sequence of steps, it is also an embodiment of the present invention that the sequence may be varied. Various permutations of the algorithm are contemplated as alternate embodiments of the invention.

In addition, while exemplary embodiments of the present invention have been described with respect to processing steps in a software program, as would be apparent to one skilled in the art, various functions may be implemented in the digital domain as processing steps in a software program, in hardware by circuit elements of state machines, or in combination of both software and hardware. Such software may be employed in, for example, a digital signal processor, micro-controller, or general-purpose computer. Such hardware and software may be embodied within circuits implemented within an integrated circuit.

Thus, the functions of the present invention can be embodied in the form of methods and apparatuses for practicing those methods. One or more aspects of the present invention can be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a device that operates analogously to specific logic circuits. The invention can also be implemented in one or more of an integrated circuit, a digital signal processor, a microprocessor, and a micro-controller.

System and Article of Manufacture Details