Methods and systems for distributing signaling messages among multiple processors for stateful and/or sequenced processing of the messages on a per-sequence basis

Technical Field

0001The present invention relates generally to the distribution and processing of messages in a communications network. More particularly, the present invention relates to methods and systems for distributing messages among multiple processors for stateful or sequenced processing of the messages on a per-sequence basis.

Background Art

0002Within a signaling system 7 (SS7) communication network call setup and teardown information is conveyed using ISDN user part (ISUP) messages. Typically, all ISUP messages associated with the same call or "circuit" are routed along the same signaling path between the originating and terminating offices involved in the call. The routing of these ISUP messages is commonly performed by SS7 signal transfer point (STP) routing nodes that reside in the network. As signaling networks have evolved, STP nodes have increasingly been used to perform message processing functions in addition to basic message routing functionality. One example of such message processing is SS7 global title translation (GTT), which is performed on class 0 signaling connection control part (SCCP) messages transmitted through a signaling network. For SCCP messages, protocol class 0 identifies a service class characterized by connectionless service for which sequencing is not required.

0003<figref idref="f0001">Figure 1</figref> is a block diagram of an exemplary STP node <b>100</b> that performs internal GTT processing on SCCP messages. STP <b>100</b> employs a distributed, multi-processor architecture, which allows a number of independent processor cards to simultaneously receive and process SS7 signaling messages. More particularly, STP <b>100</b> includes an interprocessor message transport bus <b>102,</b> a pair of maintenance and administration subsystem processors <b>104,</b> a first SS7 link interface module (LIM) <b>110,</b> a second LIM <b>112,</b> a first GTT processor <b>120,</b> and a second GTT processor <b>122.</b> As generally indicated in <figref idref="f0001">Figure 1</figref>, an SCCP message received at LIM <b>110</b> may be identified as requiring GTT processing and may be directed to GTT processor <b>122.</b> GTT processor <b>122</b> performs GTT address translation on the received SCCP message and determines the routing prior to directing the message to outbound LIM <b>112</b> for transmission.

0004In STP <b>100</b> illustrated in <figref idref="f0001">Figure 1</figref>, GTT processors <b>110</b> and <b>112</b> are identically provisioned so as to be operated in a load-sharing manner. That is, an inbound or receiving LIM module distributes received SCCP messages to a GTT processor based on the available capacity of each active GTT processor module in the system. Load-sharing among multiple redundant processors is advantageous for non-stateful processing of messages. For example, GTT processing of class 0 SCCP messages requires only that a received SCCP message be translated and routed to a final destination based on the translated address. Once the GTT processor performs an address translation and directs the SCCP message to an outbound LIM, that particular address translation is of no significance to translation operations performed on SCCP messages subsequently received by the STP. Hence, GTT processing of class 0 SCCP messages is not stateful in nature, and a relatively simple load-sharing algorithm may be employed to handle internal SCCP message distribution within a multi-processor STP. For example, class 0 SCCP message may be load-shared among GTT processors on a per-message basis using any suitable message-based distribution function.

0005In contrast to class 0 SCCP messaging, ISUP message processing can be both stateful and sequenced. As used herein, the term "stateful processing" refers to processing where state information must be stored by a processor in order to process messages relating to the same transaction. The term "sequenced processing" refers to processing that requires messages to be processed, sent or received in a particular sequence. <figref idref="f0002">Figure 2</figref> is a simplified call setup scenario involving a sample telecommunication network <b>150</b> that includes a calling party <b>152,</b> a called party <b>154,</b> an originating end office exchange <b>156,</b> a tandem office exchange <b>158,</b> a terminating end office exchange <b>160,</b> and three STP nodes <b>162 - 166.</b> When calling party <b>152</b> completes the dialing of digits associated with called party <b>154</b> (i.e., 851-2345), originating exchange <b>156</b> selects and reserves a voice trunk for the call. In this example, the selected voice trunk terminates at tandem exchange <b>158.</b> As such, an ISUP initial address message (IAM) is generated by originating exchange <b>156</b> and transmitted via STP nodes <b>162</b> and <b>164</b> to tandem exchange <b>158.</b> This IAM message includes information necessary for the intermediate tandem exchange <b>158</b> to complete the call setup operation. Upon receipt of the originating exchange generated IAM message, tandem exchange <b>158</b> secures the voice trunk to exchange <b>156</b> and subsequently reserves a voice trunk to terminating exchange <b>160.</b> Tandem exchange <b>158</b> then generates an ISUP address complete (ACM) message, which is transmitted back to the originating exchange, and a second IAM message (i.e., IAM*), which is transmitted to the terminating exchange <b>160</b> in a manner similar to that described above.

0006Sometimes all of the dialed digits needed to initiate the call setup sequence are not transmitted in the IAM message. For example, the ITU ISUP protocol employs a subsequent address message (SAM) and a subsequent directory number message (SDM) to carry additional called party (CdPA) information in addition to that provided in an IAM message. A detailed description of the ITU ISUP protocol may be found in ITU publications Q.761 <i>Signaling System No. 7 - ISDN User Part Functional Description,</i> 12/1999 and Q.762 <i>Signaling System No. 7 - ISDN User Part General Functions Of Messages And Signals,</i> 12/1999.

0007<figref idref="f0003">Figure 3</figref> illustrates sample telecommunications network <b>150</b> and a portion of the ITU ISUP signaling involved in a call setup operation. In this signaling example, an IAM message is transmitted by the originating exchange <b>156</b> after the calling party <b>152</b> has dialed a sufficient number of digits (e.g., calling party dials "851") to enable the exchange <b>156</b> to determine which voice trunk to select. The remaining dialed digit information necessary to complete the call setup is communicated to the tandem office <b>158</b> via one (or more) SAM messages, as indicated in <figref idref="f0003">Figure 3</figref>.

0008The scenario described above and illustrated in <figref idref="f0003">Figure 3</figref> is an example of a signaling scenario that presents significant problems for stateful and/or sequenced processing of the messages. Unlike the GTT processing of class 0 SCCP messages, where all of the information necessary to process a received message is present in that message, an ISUP processing application may require that multiple, related messages (e.g., IAM, SAM, SDM messages) be collected and analyzed before stateful and/or sequenced processing can be successfully completed. For example, commonly assigned co-pending U.S. Patent Publication No. <patcit id="pcit0001" dnum="US20020054674A"><text>US 2002/0054674</text></patcit> (hereinafter, the '674 Publication) discloses methods and systems for providing triggerless intelligent network screening services based on stateful and sequenced processing of call setup messages. In one embodiment of the invention disclosed in the '674 Publication, a triggerless screening service routing node, such as an STP, screens call setup messages, such as ISUP messages, and provides intelligent network services. Examples of intelligent network services provided include calling party screening, called party screening, charged party screening, and redirecting party screening. Each of these applications may utilize dialed digits collected from call setup messages to make a screening decision. If the dialed digits are sent in multiple messages, processing of the multiple messages may be stateful because processors may remember the state of a call in order to determine the message to be expected next. For example, after receiving an IAM message with partial dialed digits, a processor may enter a state, such as "waiting for SAM." Such processing may also be sequenced in that IAM and SAM messages must be received, processed, and transmitted in order. Thus, in order to ensure such stateful and sequenced processing, it is necessary that these call setup messages be processed by the same processor or that call setup information from one processor be forwarded to another processor. Distributing the call state among processors is undesirable because such distribution information consumes processor cycles and inter-processor bandwidth.

0009One message distribution approach that has been previously deployed in some distributed processing systems involves distributing messages among processors in a round-robin manner. In round-robin message distribution, messages are distributed sequentially among processors. When the last processor is reached, distribution starts again with the first processor and the algorithm repeats. While such a distribution technique may provide uniform distribution of messages across multiple application processors, this approach requires communication of state information between processors for stateful or sequenced processing, such as any of the ISUP screening processing operations described in the '674 Publication, to be performed. This type of "constant cross-talk" architecture is complex, inefficient and wasteful of communication module processing and internal communication bus bandwidth resources.

0010Document <patcit id="pcit0002" dnum="US6002693A"><text>US 6,002,693</text></patcit> discloses a method for converting a 5-bit Signaling Link Selection (SLS) into an 8-bit format SLS. The SLS field identifies one link of a multi-link link set along which an outgoing message will be transmitted.

0011Document "Integrated Services Digital Network (ISDN); Signalling System No. 7: Signalling Connection Control Part (SCCP) (connectionless and connection oriented) to support international interconnection; Part 1: Protocol specification ITU-T recommendations Q.711 to Q.716 (1996), modified; Draft ETSI EN 300 009-1 ", ETSI Standards (1999-11), XP014023105 discloses that there are two classes of SCCP messages (class 0 and class 1) and that SLS values within class 0 are assigned in such a way as to load-share the messages across the network.

0012Accordingly, there exists a long-felt need for improved methods and systems for distributing signaling messages among multiple processors for stateful or sequenced processing.

Disclosure of the Invention

0013The present invention includes a signal transfer point with multiple application processors for sharing the stateful or sequenced processing of messages, such as ISUP messages or class 1, 2, or 3 SCCP messages. The signal transfer point computes a sequence identifier that is unique to a given sequence of messages. The sequence identifier is used to distribute a particular message to an application processor. Because messages in the same sequence will have the same sequence identifier, messages relating to the same sequence will be distributed to the same application processor. As a result, the exchange of messages or state information between application processors is not needed. Thus, by performing distribution on a per-sequence basis, rather than a per-message basis, the present invention is more efficient than conventional message distribution algorithms.

0014A stateful application screening and sequencing function, which may be resident in the STP, computes the sequence identifier for each received message identified as requiring stateful or sequenced message processing. For ISUP messages, the stateful application screening and sequencing function may use the circuit identification code (CIC) and originating point code (OPC) values in received messages to compute the sequence identifier. For class 1 SCCP messages, the stateful application screening and sequencing function may use the signaling link selection (SLS) and OPC values in each received message to compute the sequence identifier.

0015Accordingly, it is an object of the present invention to provide methods and systems for distributing messages among multiple processors so that stateful and/or sequenced processing of the messages can be shared on a per-sequence basis.

0016It is another object of the invention to provide methods and systems for distributing messages among multiple processors that allow stateful and/or sequenced processing of the messages on a per-sequence basis without requiring communication of state information between processors.

0017Some of the objects of the invention having been stated hereinabove, other objects will be evident as the description proceeds, when taken in connection with the accompanying drawings as best described hereinbelow.

Brief Description of the Drawings

0018Preferred embodiments of the invention will now be explained with reference to the accompanying drawings of which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> is a block diagram of a conventional signal transfer point (STP) configured to load share stateless processing of class 0 signaling connection control part (SCCP) messages;</li><li><figref idref="f0002">Figure 2</figref> is a network diagram illustrating an ISDN user part (ISUP) call setup signaling message flow associated with a call setup attempt;</li><li><figref idref="f0003">Figure 3</figref> is a network diagram illustrating an ISUP call setup signaling message flow, which includes a subsequent address message (SAM);</li><li><figref idref="f0004">Figure 4</figref> is a is a block diagram illustrating an exemplary internal architecture of a signal transfer point (STP) routing node suitable for use with embodiments of the present invention;</li><li><figref idref="f0005">Figure 5</figref> is a block diagram illustrating an exemplary internal architecture of an STP node including a stateful application screening and sequencing module according to an embodiment of the present invention;</li><li><figref idref="f0006">Figure 6</figref> is a block diagram illustrating a signaling system 7 (SS7) communication module associated with an STP according to an embodiment of the present invention;</li><li><figref idref="f0007">Figure 7</figref> is a flow chart illustrating exemplary message distribution processing that may be performed within a signal transfer point according to an embodiment of the present invention;</li><li><figref idref="f0008">Figure 8</figref> is a block diagram illustrating the structure of an SS7 ISDN user part message;</li><li><figref idref="f0009">Figure 9</figref> is a flow diagram illustrating application processor selection using a normal distribution component of a sequence-based message distribution algorithm according to an embodiment of the present invention;</li><li><figref idref="f0010">Figure 10</figref> is a flow diagram illustrating application processor selection using a failure distribution component of a sequence-based message distribution algorithm according to an embodiment of the present invention; and</li><li><figref idref="f0011">Figure 11</figref> is a block diagram illustrating a system for distributing messages among multiple processors for stateful and/or sequenced processing on a per sequence basis according to an embodiment of the present invention.</li></ul>

Detailed Description of the Invention

0019According to one embodiment, the present invention includes a communications network routing node, such as a signaling system 7 (SS7) signal transfer point (STP), configured to distribute signaling messages among multiple processors so that stateful or sequenced processing of the signaling messages can be shared among the processors on a per-sequence basis. <figref idref="f0004">Figure 4</figref> is a block diagram illustrating an exemplary STP node <b>200</b> suitable for use with embodiments of the present invention. STP <b>200</b> is described herein as a collection of modules and functions. It is understood that these modules and functions may be implemented in software residing in memory and executed by one or more general-purpose microprocessors. Alternatively, the modules and functions described herein may be implemented in hardware, such as application-specific integrated circuits (ASICs) or programmable logic modules. Any combination of hardware, software, and firmware for distributing messages among multiple processors for stateful and/or sequenced on a per-sequence basis as described herein is intended to be within the scope of the invention.

0020As shown in <figref idref="f0004">Figure 4</figref>, STP <b>200</b> includes the following subsystems: a maintenance and administration subsystem (MAS) <b>202,</b> a communication subsystem <b>204</b> and an application subsystem <b>206.</b> MAS <b>202</b> provides maintenance communications, initial program loading, peripheral services, alarm processing and system disks. Communication subsystem <b>204</b> includes an interprocessor message transport (IMT) bus that is the main communication bus among subsystems in STP <b>200.</b> The IMT bus may include 1 Gbps counter-rotating serial buses.

0021Application subsystem <b>206</b> includes application cards or printed circuit boards capable of communicating with the other cards through the IMT bus. Numerous types of application cards can be included in STP <b>200.</b> Exemplary application cards that may be included in STP <b>200</b> include a link interface module (LIM) <b>208</b> that provides SS7 links and X.25 links, a data communication module (DCM) <b>210</b> that provides an Internet protocol (IP) signaling interface to external nodes, and a high-speed asynchronous transfer mode (ATM) communication link module (HSL) <b>212.</b> One or more database service modules (DSM) <b>214</b> may also be included for stateful and stateless processing of signaling messages.

Exemplary Internal Architecture of an STP Routing Node

0022<figref idref="f0005">Figure 5</figref> illustrates an exemplary internal architecture of an STP including a stateful application screening and sequencing module according to an embodiment of the present invention. In <figref idref="f0005">Figure 5</figref>, STP node <b>200</b> includes a high-speed IMT communications bus <b>220.</b> A number of distributed processing modules or cards are coupled to IMT bus <b>220,</b> including: a pair of maintenance and administration subsystem processors <b>222,</b> an SS7-capable link interface module <b>224,</b> and an application subsystem <b>226</b> that includes a first application processor <b>228,</b> a second application processor <b>230,</b> a third application processor <b>232,</b> and a fourth application processor <b>234.</b> Application processors <b>228, 230, 232,</b> and <b>234</b> may include any stateful and/or sequenced message processing applications, such as the ISUP screening applications described in the '674 Publication referenced above.

0023The modules and application processors illustrated in <figref idref="f0005">Figure 5</figref> may be physically connected to IMT bus <b>220</b> such that signaling and other types of messages may be routed internally between active cards or modules. In one embodiment, application processors <b>228, 230, 232,</b> and <b>234</b> may be DSM modules physically connected to IMT bus <b>220.</b> In an alternate embodiment of the present invention, application processors <b>228, 230, 232,</b> and <b>234</b> may be external computing platforms, such as Tekelec TekServer™ platforms, which may be directly coupled to IMT bus <b>220</b> or indirectly coupled to IMT bus <b>220</b> via Ethernet interface modules (not shown in <figref idref="f0005">Figure 5</figref>).

0024For simplicity of illustration, only a single LIM <b>224</b> is illustrated in <figref idref="f0005">Figure 5</figref>. However, the distributed processing architecture of STP <b>200</b> enables multiple LIM, DSM, TekServer™ and other processing modules to be simultaneously coupled to IMT bus <b>220.</b> Furthermore, although only one application processor group is illustrated in <figref idref="f0005">Figure 5</figref>, multiple application processor groups or subsystems may be included in STP node <b>200</b> without departing from the scope of the invention.

0025<figref idref="f0006">Figure 6</figref> illustrates an exemplary internal architecture for a link interface module according to an embodiment of the present invention. Referring to <figref idref="f0006">Figure 6</figref>, LIM <b>224</b> includes a number of functions including an SS7 MTP level 1 function <b>250,</b> an MTP level 2 function <b>252,</b> an I/O buffer <b>254,</b> an SS7 MTP level 3 message handling and discrimination (HMDC) function <b>256,</b> an application screening and sequencing function <b>258,</b> a message routing function <b>260,</b> a message handling and distribution (HMDT) function <b>262,</b> and a routing information database <b>264.</b> MTP level 1 function <b>250</b> sends and receives digital data over a particular physical interface. MTP level 2 function <b>252</b> provides error detection, error correction, and sequenced delivery of SS7 message packets. I/O buffer <b>254</b> provides temporary buffering of incoming and outgoing signaling message packets.

0026HMDC function <b>256</b> receives an incoming signaling message from the lower processing layers and determines whether the message is addressed to and consequently requires processing by one or more application subsystems in STP node <b>200.</b> Stateful application screening and sequencing function <b>258</b> is responsible for examining an incoming signaling message, which may not be addressed to STP node <b>200</b> and determining whether the message requires stateful and/or sequenced processing by an application subsystem in STP node <b>200.</b> Stateful application screening and sequencing function <b>258</b> also generates a sequencing value for each message identified as requiring stateful and/or sequenced processing. The sequencing value is preferably unique on a per-sequence basis. The sequencing value, along with the identified target application subsystem, determines the application processor module in the application subsystem to which the message should be distributed. Because the sequencing values are unique on a per-sequence basis, messages in the same sequence are distributed to the same processor. As a result, processing of the messages can be shared among multiple processors without requiring the communication of state information between processors.

0027In one embodiment, stateful application screening and sequencing function <b>258</b> examines the message transfer part (MTP) origination point code (OPC), destination point code (DPC), and service indicator octet (SIO) parameter values in a received call setup signaling message (e.g., ISUP IAM message) to determine the need for stateful processing by an application subsystem.

Stateful Sequencing and Message Distribution Algorithms

0028In the event that a signaling message is identified as requiring stateful and/or sequenced processing by an application subsystem, stateful application screening and sequencing function <b>258</b> applies a sequencing algorithm that uses information contained in the message to generate the sequencing value. For a received ISUP message, the sequencing algorithm may use the CIC and OPC values from the messages to generate the sequencing value. For class 1, class 2, or class 3 SCCP messages, the sequencing algorithm may use the SLS and OPC values from the message to generate the sequencing value.

0029The message distribution algorithms of the present invention achieve superior performance when compared to round-robin message distribution. In round-robin message distribution, messages are distributed sequentially among processors on a per-message basis. Round-robin message distribution techniques ensure that messages are distributed equally to all active application processors in a system or service group regardless of the content of the messages. However, round-robin message distribution does not ensure that messages in the same sequence will be distributed to the same processor. Thus, using such round-robin distribution techniques when messages require stateful or sequenced processing means that a dynamic message distribution mapping must be constructed by each communication module and that this message distribution mapping information be continuously shared among all communications modules in the system. For example, for the scenario in which a message requiring stateful or sequenced processing is received by a communication module, before a first communication module that receives the message from the network can distribute the message to an application processor in the system, the communication module must determine if the message is the first message in a sequence of messages requiring stateful or sequenced processing. If another message associated with the sequence has already been received and distributed to a particular controlling application processor in the system, then the received message must be distributed to that same controlling application processor.

0030Since there is no guarantee in round-robin message distribution that all messages related to the same messaging sequence will be received by the same communication module, each communication module must share its current distribution mapping information the other communication modules so that all messages associated with the same messaging sequence can be distributed to the same application processor. In even a relatively small distributed processing system, the processing overhead and bandwidth costs of maintaining real-time synchronization among a number of communication modules can be significant.

0031The improved message sequencing and distribution methods according to the present invention provide guaranteed distribution of sequenced messages to the appropriate application processor without requiring the extensive processing overhead and bandwidth costs described above with respect to the round-robin approach. Once again, the present invention involves the use of a stateful message sequencing and distribution algorithm, which does not require the exchange of dynamic message distribution mapping information among communication modules in the system. Instead, stateful application screening and sequencing function <b>258</b> applies a stateful sequencing algorithm that uses information contained in a message to generate a sequence identifier value used to select the appropriate controlling application processor to which the message is distributed. Because the sequence identifier is the same for all messages in a sequence, messages in the same sequence will be automatically delivered to the same application processor. In addition, because different sequences of messages will sometimes have different sequence identifiers, the stateful or sequenced processing of messages can be shared on a per sequence basis.

0032An exemplary stateful message distribution algorithm that utilizes the sequence identifier will now be described in detail. In the illustrated example, the stateful message distribution algorithm includes a normal condition component and a failure condition component. The normal condition component may be used first, regardless of the condition of the application processors. The failure condition component may be used when the normal condition component selects an unavailable application processor.

Normal Condition Component Equation

0033<maths id="math0001" num="(1)"><math display="block"><mi>Offset value</mi><mo mathvariant="normal">=</mo><mi mathvariant="normal">v</mi><mo mathvariant="normal">-</mo><mi mathvariant="normal">E</mi><mo mathvariant="normal">*</mo><mfenced><mo mathvariant="normal">⌊</mo><mi>v</mi><mo mathvariant="normal">/</mo><mi>E</mi><mo mathvariant="normal">⌋</mo></mfenced></math><img file="EP1568203B1_D0001.tif" /></maths> Where, v is the sequence identifier computed for a message; E is the number of equipped processors associated with a particular application or service; and └ ┘ is the round down operator.

Failure Condition Component Equation

0034<maths id="math0002" num="(2)"><math display="block"><mi>Offset value</mi><mo>=</mo><mi mathvariant="normal">A</mi><mo>-</mo><mfenced><mfenced><mfenced><mo>⌊</mo><mi>v</mi><mo>/</mo><mi>E</mi><mo>⌋</mo></mfenced><mo>*</mo><mi mathvariant="normal">F</mi><mo>+</mo><mi mathvariant="normal">N</mi></mfenced><mo>-</mo><mfenced><mi mathvariant="normal">A</mi><mo>*</mo><mfenced><mo>⌊</mo><mfenced><mo>⌊</mo><mmultiscripts><msub><mo>/</mo><mi>E</mi></msub><mprescripts /><none /><mi>v</mi></mmultiscripts><mo>⌋</mo><mo>*</mo><mi>F</mi><mo>+</mo><mi>N</mi></mfenced><mo>/</mo><mi>A</mi></mfenced><mo>⌋</mo></mfenced></mfenced></math><img file="EP1568203B1_D0002.tif" /></maths> Where, v is the sequence identifier computed for a message; A is the number of available processors associated with a particular application or service; E is the number of equipped processors associated with a particular application or service; F is the number of failed processors associated with a particular application or service; N is the failure order of application processors determined via 0,1,2,3. (1^st to fail, 2^nd, etc...); and └ ┘ is the round down operator.

0035As the naming convention would suggest, the failure condition component of the algorithm is used only in cases where one or more application processors in the system have failed. Otherwise, only the normal condition component is employed. In both exemplary algorithm components, evaluated fractions are rounded down to the nearest integer. For a received ISUP message, the value sequence identifier (v) may be calculated as the sum of the CIC code value and the OPC value. For a class 1, class 2, and class 3 SCCP messages, the sequence identifier (v) may be calculated as the sum of the SLS value and the OPC value.

0036The present invention is not limited to using the CIC, OPC, and SLS values to compute sequence identifiers. Any suitable values from a received message that can be used to compute a value that is the same for each message in a sequence and that is unique on per-sequence basis is intended to be within the scope of the invention. For example, for a sequence of session initiation protocol (SIP) messages, the sequence identifier may be determined using the Call_ID, the Call_Sequence (Cseq), the Session_ID, the To, and the From parameters contained in each message. For H.225 signaling messages, the Call_Reference_Value parameter may be used in determining the sequence identifier. In some cases, lower level protocol parameters may be used to determine the sequence identifier. For example, in the stream control transmission protocol (SCTP), an SCTP association identifier and/or stream identifier may be used to determine the sequence identifier. In a transmission control protocol (TCP) environment, an IP address and a TCP port may be used to determine the sequence identifier.

0037An application processor sequence table, shown below in Table 1, may be accessible by stateful application screening and sequencing function <b>258</b> to determine the number of available processors for use in Equations (1) and (2). Table 1 includes an application group field, an application processor identifier field, and a processor status field. The application group field is used to distinguish groups of processors that are supporting different applications (e.g., prepaid calling service). A unique processor identifier is assigned to each application processor within a given application group. The information in this table is used in conjunction with the stateful distribution algorithm to determine the controlling application processor for a message in a given messaging sequence, as described below. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1: Application Processor Sequence And Status</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="33mm" /><colspec colnum="2" colname="col2" colwidth="26mm" /><colspec colnum="3" colname="col3" colwidth="24mm" /><thead><row><entry align="center" valign="top"><b>Application Group</b></entry><entry align="center" valign="top"><b>Processor ID</b></entry><entry align="center" valign="top"><b>Status</b></entry></row></thead><tbody><row><entry align="center">Prepaid</entry><entry align="center">A</entry><entry align="center">Available</entry></row><row><entry align="center">Prepaid</entry><entry align="center">B</entry><entry align="center">Available</entry></row><row><entry align="center">Prepaid</entry><entry align="center">C</entry><entry align="center">Available</entry></row><row><entry align="center">Prepaid</entry><entry align="center">D</entry><entry align="center">Available</entry></row></tbody></tgroup></table></tables>

Message Distribution Operation

0038<figref idref="f0007">Figure 7</figref> is a flow chart illustrating exemplary steps that may be performed by stateful application screening and sequencing function <b>258</b> and message distribution function <b>262</b> in distributing signaling messages among multiple processors for sequenced and/or stateful processing according to an embodiment of the present invention. Beginning with step <b>ST1,</b> a message is received at LIM <b>224</b> and is passed up the stack to stateful application screening and sequencing function <b>258.</b> For purposes of illustration, the received message is assumed to be an ISUP message, such as an ISUP LAM message. Stateful application screening and sequencing function <b>258</b> examines parameters associated with the received message <b>300</b> and determines whether stateful and/or sequenced processing is indicated and if so, to which group of application processors the message should be distributed <b>(ST2).</b> Table 2 is a sample screening table which may be used or accessed by function <b>258</b> to make such a determination. Table 2 includes a number of screening keys, including a service indicator (SI) key, a DPC key, an OPC key, a CIC code key, and an SCCP subsystem (SSN) key. Associated with each compound key entry is an application group value that identifies a group of application processors for performing stateful, sequenced, and non-stateful, non-sequenced processing of received messages, depending on the message type. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2: Sample Application Screening Criteria</title><tgroup cols="6"><colspec colnum="1" colname="col1" colwidth="10mm" /><colspec colnum="2" colname="col2" colwidth="13mm" /><colspec colnum="3" colname="col3" colwidth="13mm" /><colspec colnum="4" colname="col4" colwidth="11mm" /><colspec colnum="5" colname="col5" colwidth="12mm" /><colspec colnum="6" colname="col6" colwidth="20mm" /><thead><row><entry namest="col1" nameend="col5" align="center" valign="top"><u>APPLICATION SCREENING KEY(s)</u></entry><entry align="center" valign="top"><u>DATA</u></entry></row><row><entry align="center" valign="top"><u>SI</u></entry><entry align="center" valign="top"><u>DPC</u></entry><entry align="center" valign="top"><u>OPC</u></entry><entry align="center" valign="top"><u>CIC</u></entry><entry align="center" valign="top"><u>SSN</u></entry><entry align="center" valign="top"><u>App Group</u></entry></row></thead><tbody><row><entry align="center">3</entry><entry align="center">2-3-7</entry><entry align="center">*</entry><entry align="center">n/a</entry><entry align="center">*</entry><entry align="center">GTT</entry></row><row><entry align="center">3</entry><entry align="center">2-3-6</entry><entry align="center">*</entry><entry align="center">n/a</entry><entry align="center">23</entry><entry align="center">GTT</entry></row><row><entry align="center">5</entry><entry align="center">3-2-2</entry><entry align="center">4-1-1</entry><entry align="center">42</entry><entry align="center">n/a</entry><entry align="center">Prepaid</entry></row><row><entry align="center">5</entry><entry align="center">*</entry><entry align="center">1-0-0</entry><entry align="center">*</entry><entry align="center">n/a</entry><entry align="center">Prepaid</entry></row></tbody></tgroup></table></tables>

0039In Table 2, the entries with "GTT" in the application group field identify messages that require non-stateful, non-sequenced processing, and thus messages matching these entries would not be selected for stateful and/or sequenced processing. The entries with "prepaid" in the application group column identify messages that require prepaid call screening. Since prepaid call screening may require stateful, sequenced processing, messages matching these entries may be identified for further distribution processing by stateful application screening and sequencing function <b>258.</b> Some messages require sequenced but non-stateful processing. An example of these types of messages are SCCP type 1 messages. Accordingly, stateful application screening and sequencing function <b>258</b> may identify these messages as requiring further distribution processing by stateful application screening and sequencing function <b>258.</b> SCCP type 1 and type 2 messages may require both stateful processing. Accordingly, stateful application screening and sequencing function <b>258</b> may identify these messages as requiring further distribution processing by stateful application screening and sequencing function <b>258.</b>

0040In this example, since the received message is assumed to be an ISUP IAM message, stateful application screening and sequencing function may examine ISUP message parameters to determine whether stateful and/or sequenced processing is indicated. Referring to <figref idref="f0008">Figure 8</figref>, an ISUP message <b>300</b> includes an SI field <b>310</b> with a value of 5 identifying the ISUP message type, an OPC field <b>312</b> with a value of 1-0-0, a DPC field <b>314</b> with a value of 2-0-0, and a CIC field <b>316</b> with a value of 15. In an ANSI compliant network, OPC and DPC values are 24 binary bits (commonly represented as 8 bits - 8 bits - 8 bits), while a CIC value may include up to 8 bits. Given the information contained in the received message <b>300,</b> screening function <b>258</b> locates a matching entry in Table 2 (i.e., the last record), indicating that processing is required by application B. If a matching entry had not been located in Table 2, no further screening and sequencing processing need be performed by function <b>258,</b> and the message could be passed along for additional screening operations or simply routed on towards a final destination <b>(ST3).</b>

0041Given that a matching entry was located in this example, the message undergoes further processing by screening function <b>258.</b> More particularly, the OPC and CIC values in message <b>300</b> are extracted and mathematically combined to yield the sequence identifier (v), as described above (step <b>ST3).</b> In this case, the addition of the 24 bit OPC value (i.e., 00000001-00000000-00000000 binary or 65536 decimal) and the 8 bit CIC value (i.e., 00001111 binary or 15 decimal) yields a sequence identifier value of 65551 (decimal). The number of equipped or provisioned processors associated with the "prepaid" application group (i.e., 4) is then obtained from Table 1. These two values are next plugged into Equation 1 above to compute the offset value, as indicated in step <b>ST5.</b> Using a sequence identifier, v, of 65551 and an equipped processor count value, E, of 4 the distribution algorithm described above yields a resulting offset value of 3. In step <b>ST6,</b> a specific application processor is selected from the group of 4 processors using the offset value.

0042<figref idref="f0009">Figure 9</figref> graphically illustrates application processor selection based on the offset value according to an embodiment of the present invention. Referring to <figref idref="f0009">Figure 9</figref>, the four application processors that make up the prepaid application processor group can be thought of as a ring of processors for distribution purposes where the specific application processor for processing a message may be selected by stepping around the ring in a number of steps equal to the offset value. In an actual implementation, the values representing each application processor in a group may be stored in sequential memory locations and the offset may be used to step among the various memory locations. In this example, the calculated offset value of 3 is used to step around the 4 application processors of the conceptual ring illustrated in <figref idref="f0009">Figure 9</figref> in a clockwise manner. In memory, each offset increment may lead to a new memory location where a new application processor identifier is stored. Once the last memory location containing an application processor identifier is reached, function <b>258</b> may return to the memory location of the first application processor identifier. As indicated in <figref idref="f0009">Figure 9</figref>, beginning with application processor A, the first offset step leads to application processor B. The second offset step leads to application processor C, and the final third offset step leads to application processor D.

0043Returning to <figref idref="f0006">Figure 6</figref>, once the application processor has been selected, its status is checked (step <b>ST7).</b> Since application processor D is available, the message and selected processor information is passed to distribution function <b>262</b> on LIM <b>224</b> and the message is transmitted to application processor D via IMT bus <b>220</b> (step <b>ST8).</b>

0044When an application processor is selected using the normal distribution algorithm component, stepping is performed in a clockwise manner around the ring and each application processor "node" in the ring is counted regardless of the status of each node. Only application processor status is required for stateful application screening and sequencing function <b>258</b> to select a target processor. No additional state information associated with past message distribution transactions need be maintained or accessed by function <b>258</b> in order to determine to which application processor a particular message should be distributed.

0045Once again, in round-robin message distribution, every LIM module in the system would be required to be made aware of where the ISUP IAM message was sent so that any subsequent, related messages (e.g., SAM or SDM messages) could be distributed to the same application processor. The present embodiment only requires that the LIMs know the status of each application processor. Ping or heartbeat messages can be used by screening and sequencing function <b>258</b> in order to maintain the application processor status information shown in Table 1. Such messages will not consume a significant portion of IMT bus bandwidth when compared to the exchange of state information.

0046In order to illustrate message distribution when an application processor fails, an example will now be described in which it is assumed that prepaid application processor D has failed and can no longer accept or process messages. In this example, steps <b>ST1-ST7</b> are the same as those steps described above for the normal or non-failure case. For example, the offset is computed using Equation (1) described above, using v = 65551 and E = 4, which yields an offset value of 3. Using the application processor ring structure diagram illustrated in <figref idref="f0009">Figure 9</figref>, the offset is stepped off in a clockwise manner starting from application processor A. As in the previous example, the offset results in the selection of application processor D. However, in this case, application processor D has failed and can no longer accept traffic. Consequently, as indicated in step <b>ST9,</b> Equation (2) is evaluated using the following input parameters; v= 3, A = 3, E = 4, F = 1, N = 0, which yields a failure offset value of 3. In step <b>ST10,</b> the failure offset value is used to select the application processor.

0047Referring to <figref idref="f0010">Figure 10</figref>, the failure offset value is applied to the application processor ring diagram; however, failure offset values are stepped off in a counterclockwise manner starting from application processor A. Furthermore, when stepping off a failure offset, only available nodes in the ring are counted (i.e., failed application processor nodes are skipped). Beginning with application processor A, the first offset step leads to application processor C. Application processor D is skipped since it is unavailable. The second offset step leads to application processor B, and the final third offset step leads to application processor A. Consequently, the message and selected processor information is passed to distribution function <b>262</b> on LIM <b>224,</b> and the message is transmitted to application processor A via IMT bus <b>220,</b> as indicated by step <b>ST8</b> in <figref idref="f0007">Figure 7</figref>.

0048Certain applications may only require a copy of some or all of the received message contents, and in such instances the original received message may simply be copied and then routed from the system without being distributed to an application processor. The message copy may be distributed to the appropriate processor using the stateful message distribution and sequencing algorithms described above. In other applications, such as call screening applications, the actual signaling message may be distributed to the appropriate application processor using the algorithms described above before being allowed to pass to the intended destination. Distributing both message copies and original messages using the algorithms described above is intended to be within the scope of the invention.

0049<figref idref="f0011">Figure 11</figref> illustrates another example of distributing messages that require stateful and/or sequenced processing on a per-sequence basis according to an embodiment of the present invention. Referring to <figref idref="f0011">Figure 11</figref>, STP <b>100</b> includes LIM <b>224</b> and IMT bus <b>220,</b> as described above. In addition, STP <b>100</b> includes a plurality of external application processors <b>1100, 1102, 1104,</b> and <b>1106.</b> Application processors <b>1100, 1102, 1104,</b> and <b>1106</b> may be any suitable stand-alone computing platforms for running one or more stateful and/or sequenced call processing applications. In one embodiment of the invention, application processors <b>1100, 1102, 1104,</b> and <b>1106</b> may be Tekelec Tekserver™ platforms executing ISUP call screening applications described in the above-referenced '674 Publication.

0050In the illustrated example, application processors <b>1100, 1102, 1104,</b> and <b>1106</b> are labeled 0, 1, 2, and 3, respectively. For purposes of this example, it is assumed that ISUP call control messages are received by <b>LIM 224</b> and that the offset values computed for the ISUP messages have values ranging from 0 to 31. Tables 3-5 shown below illustrate status, offset assignments, and traffic distribution for application processors <b>1100, 1102, 1104,</b> and <b>1106.</b><tables id="tabl0003" num="0003"><table frame="all"><title>Table 3: Application Processor States</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="29mm" /><colspec colnum="2" colname="col2" colwidth="27mm" colsep="1" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry>Status:</entry><entry>A A A A</entry></row></tbody></tgroup></table></tables><tables id="tabl0004" num="0004"><table frame="all"><title>Table 4: Offset Assignments</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="24mm" /><colspec colnum="2" colname="col2" colwidth="68mm" colsep="1" /><tbody><row><entry>Value</entry><entry>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15</entry></row><row><entry>Appln Proc.</entry><entry>0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3</entry></row><row><entry /><entry /></row><row><entry>Value</entry><entry>16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31</entry></row><row><entry>Appln. Proc. 0</entry><entry>1 2 3 0 1 2 3 0 1 2 3 0 1 2 3</entry></row></tbody></tgroup></table></tables><tables id="tabl0005" num="0005"><table frame="all"><title>Table 5: Traffic Distribution</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="26mm" /><colspec colnum="2" colname="col2" colwidth="18mm" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry># of messages</entry><entry>8 8 8 8</entry></row></tbody></tgroup></table></tables>

0051In operation, when an ISUP message with a computed sequencing value of 5 is processed by LIM <b>224,</b> the offset is: 5-4*( └5/4┘ )=1. Using the offset assignments in Table 3 above, application processor 1 is chosen since the first processor from zero reading left to right is application processor 1.

0052In the event that application processor 1 fails, Equation 1 above is evaluated to result in an initial selection of application processor 1. Since application processor 1 is not available, Equation 2 is used to calculate the new offset. The calculation of the new offset using Equation 2 is as follows: <maths id="math0003"><math display="block"><mtable columnalign="left"><mtr><mtd><mi>Offset</mi></mtd><mtd><mo>=</mo><mn>3</mn><mo>-</mo><mfenced><mfenced><mfenced><mo>⌊</mo><mn>5</mn><mo>/</mo><mn>4</mn><mo>⌋</mo></mfenced><mo>*</mo><mn>1</mn><mo>+</mo><mn>0</mn></mfenced><mo>-</mo><mfenced><mn>3</mn><mo>*</mo><mfenced><mo>⌊</mo><mrow><mo>(</mo><mo>⌊</mo><mn>5</mn><mo>/</mo><mn>4</mn><mo>⌋</mo><mo>*</mo><mn>1</mn><mo>+</mo><mn>0</mn><mrow><mo>)</mo></mrow></mrow><mo>/</mo><mn>3</mn><mo>⌋</mo></mfenced></mfenced></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><mn>3</mn><mo>-</mo><mn>1</mn><mo>-</mo><mn>0</mn></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><mn>2.</mn></mtd></mtr></mtable></math><img file="EP1568203B1_D0003.tif" /></maths> As discussed above with regard to <figref idref="f0010">Figure 10</figref>, for the failure condition, offsets are stepped off in the reverse direction from the normal case when all application processors are operational. In addition, failed application processors are not counted. Tables 6 and 7 shown below illustrate the distribution data structures used after application processor 1 fails. Table 8 illustrates the corresponding traffic distribution. In Table 6, failure offset counting starts with the first entry in the table and then proceeds backwards through the table from processor 3. Therefore, when an ISUP message with a computed sequencing value of 5 and a resulting offset value of 2 is processed by LIM <b>224,</b> counting proceeds from processor 0 to processor 3, and to processor 2. Application processor 2 is available, and it is selected. <tables id="tabl0006" num="0006"><table frame="all"><title>Table 6: Application Processor States</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="29mm" /><colspec colnum="2" colname="col2" colwidth="28mm" colsep="1" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry>Status</entry><entry>A N/A A A</entry></row></tbody></tgroup></table></tables><tables id="tabl0007" num="0007"><table frame="all"><title>Table 7: Offset Assignments:</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="23mm" /><colspec colnum="2" colname="col2" colwidth="69mm" colsep="1" /><tbody><row><entry>Value</entry><entry>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15</entry></row><row><entry>Appln: Proc.</entry><entry>0 0 2 3 0 2 2 3 0 3 2 3 0 0 2 3</entry></row><row><entry /><entry /></row><row><entry>Value</entry><entry>16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31</entry></row><row><entry>Appln. Proc.</entry><entry>0 2 2 3 0 3 2 3 0 0 2 3 0 2 2 3</entry></row></tbody></tgroup></table></tables><tables id="tabl0008" num="0008"><table frame="all"><title>Table 8: Traffic Distribution</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="26mm" /><colspec colnum="2" colname="col2" colwidth="20mm" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry># of messages</entry><entry>11 0 11 10</entry></row></tbody></tgroup></table></tables>

0053If application processor 2 subsequently fails, Equation 1 is still executed yielding the original application processor 2, which is out of service. Equation 2 is then evaluated as follows: <maths id="math0004"><math display="block"><mtable columnalign="left"><mtr><mtd><mi>Offset</mi></mtd><mtd><mo>=</mo><mn>2</mn><mo>-</mo><mfenced><mfenced><mfenced><mo>⌊</mo><mn>5</mn><mo>/</mo><mn>4</mn><mo>⌋</mo></mfenced><mo>*</mo><mn>2</mn><mo>+</mo><mn>0</mn></mfenced><mo>-</mo><mfenced><mn>2</mn><mo>*</mo><mfenced><mo>⌊</mo><mfenced><mo>⌊</mo><mn>5</mn><mo>/</mo><mn>4</mn><mo>⌋</mo><mo>*</mo><mn>2</mn><mo>+</mo><mn>0</mn></mfenced><mo>/</mo><mn>2</mn><mo>⌋</mo></mfenced></mfenced></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><mn>2</mn><mo>-</mo><mfenced><mn>2</mn><mo>-</mo><mn>2</mn></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><mn>2.</mn></mtd></mtr></mtable></math><img file="EP1568203B1_D0004.tif" /></maths> Tables 9-11 shown below illustrate the data structures used to select an application processor when two application processors have failed. As with the failure cases discussed above, failure offset counting proceeds right to left and failed application processors are not counted. Therefore, when an ISUP message with a computed sequencing value of 5 and a failure offset of 2 is processed by LIM <b>224,</b> using Table 9, application processor 3 is first looked at since it is available. Application processors 2 and 1 are skipped, since they are not available. The next offset step thus results in application processor 0, which is available. Accordingly, application processor 0 is selected. <tables id="tabl0009" num="0009"><table frame="all"><title>Table 9: Application Processor Status</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="29mm" /><colspec colnum="2" colname="col2" colwidth="28mm" colsep="1" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry>Status</entry><entry>A N/A N/A A</entry></row></tbody></tgroup></table></tables><tables id="tabl0010" num="0010"><table frame="all"><title>Table 10: Offset Assignments</title><tgroup cols="2" colsep="0"><colspec colnum="1" colname="col1" colwidth="26mm" /><colspec colnum="2" colname="col2" colwidth="68mm" colsep="1" /><tbody><row><entry>Value</entry><entry>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15</entry></row><row><entry>TekServer</entry><entry>0 0 3 3 0 0 3 3 0 0 3 3 0 0 3 3</entry></row><row><entry /><entry /></row><row><entry>Value</entry><entry>16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31</entry></row><row><entry>TekServer</entry><entry>0 0 3 3 0 0 3 3 0 0 3 3 0 0 3 3</entry></row></tbody></tgroup></table></tables><tables id="tabl0011" num="0011"><table frame="all"><title>Table 11: Traffic Distribution</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="25mm" /><colspec colnum="2" colname="col2" colwidth="19mm" /><tbody><row><entry>Appln. Proc.</entry><entry>0 1 2 3</entry></row><row><entry># of messages</entry><entry>16 0 0 16</entry></row></tbody></tgroup></table></tables>

0054Thus, as described above, the present invention includes methods and systems for distributing messages that require stateful and/or sequenced processing among multiple processors. According to the method, messages that require stateful and/or sequenced processing are identified. For each message identified as requiring and/or sequenced stateful processing, a sequence identifier is computed. Messages in the same sequence will have the same sequence identifiers, and messages in different sequences may have different sequence identifiers. The sequence value is then used to select an application processor. Because messages with different sequence identifiers result in different application processors, distribution is performed on a per sequence basis. In addition, because messages within the same sequence are sent to the same processor, exchange of state information between communication modules and/or application processors is not required.

0055It will be understood that various details of the invention may be changed without departing from the scope of the invention. Furthermore, the foregoing description is for the purpose of illustration only, and not for the purpose of limitation.