# Patent

## Title
End-to-end logic tracing of complex call flows in a distributed call system

## Abstract

A logic history can be provided for every request or call instance through a distributed computing system that uniquely traces its entire path, end-to-end, in-band within the messaging for the system. The end result is a single true representation of what occurred with no post computational inference. Accordingly, unique logic history codes are not forced across the system. Rather sub-components that are logic history enabled can use codes that have meaning and applicability to itself. Unique logic history codes are not forced across the system, which in practice would be brittle. Rather each sub-component that is logic history enabled can use codes that have meaning and applicability only to itself. This allows the system to be flexible and lets sub-components change and redefine their logic and logic history traces without impacting the rest of the system.

## Background
RELATED APPLICATIONS
This application is a continuation of U.S. patent application Ser. No. 14/071,342, entitled “End-to-End Logic Tracing of Complex Call Flows in a Distributed Call System”, filed on Nov. 4, 2011; which is a continuation of U.S. patent application Ser. No. 12/081,191, entitled “End-to-End Logic Tracing of Complex Call Flows in a Distributed Call System”, filed on Apr. 11, 2008, now U.S. Pat. No. 8,576,991; which claims priority to U.S. Provisional Application No. 61/064,671, filed Mar. 19, 2008, entitled “End-to-End Logic Tracing of Complex Call Flows in a Distributed Call System.” The entirety of all three of which are expressly incorporated herein by reference.


BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to any moderately complex software system. It is especially applicable to large scale, distributed systems, where it is mandatory to track down what logic was applied across multiple components in the system.
2. Background of Related Art
Distributed Emergency Call Systems in telecommunications are in general very complex computing systems. In the realm of emergency call systems in particular, un-interrupted service must be provided with each “request” being correctly processed within a well specified time interval. The latter requirement is often met by fallback logic that is invoked whenever one or more unexpected conditions occur. Typically, in Emergency Call Systems a request is a call instance placed by a person in distress. The terms “request”, “call instance” and “transaction” are used herein to refer to an atomic transaction through a complex computing system.
Distributed systems exist that employ various implementations of tracing and logging that allow an operator to trace or follow a request throughout the system, e.g., to collect statistics or to trouble-shoot a particular problem. But in many cases just the exit criteria are collected, i.e., the end-result of a request but not how the request got to that point.
Telephony systems generally use Call Detail Records (CDRs), error logs, and Simple Network Management Protocol (SNMP) traps to gather what occurred on the system. Using conventional technology an adjunct system usually has to gather all the desired data and make a best attempt at correlating and reconstructing what most likely occurred by inference of the data gathered.
The present inventors have recognized that the existing technology for logic tracing of a complex call flow in a distributed system is dependent on gathering all applicable data, in a timely manner, and dependent on best attempts at gathering and correlating available data. Unfortunately, unless complete forethought is given before a given call is made, it is usually problematic to afterwards correlate call flow data relating to that call.
FIG. 3 shows a distributed computing system consisting of an exemplary four components, and use of conventional technology to collect a transaction history.
In particular, FIG. 3 shows a distributed computing system including (by way of example only) a front end component A 302, a core processing component B 304, a helper #1 component C 306, and a helper #2 component D 308. For fault tolerance purposes, any or all of the components 302, 304, 306, 308 may be multiple components themselves, as depicted by the shadowed boxes shown in FIG. 3.
To perform a logic tracing of a call flow, using conventional technology the data is collected, post-processed and correlated to get a view of what occurred for the transaction.
Using existing technologies, call data records (CDRs) 303, error logs 307, 309 and Simple Network Management Protocol (SNMP) traps are generated at the various components 302, 304, 306, 308 using disparate technologies. In general, the various logging pieces including call data records (CDRs) 303 are collected (preferably in a common format) and then stored in an appropriate transaction datastore 314.
In the example of FIG. 3, the identifier “Transaction XYZ” is used. As depicted in the reconstructed transaction flow 312, component A 302 generates CDRs for Transaction XYZ.
In the example Component B 304 uses SNMP traps, so Component B 304 generates SNMP traps for Transaction XYZ. In many cases, SNMP traps are only generated in the case of abnormal conditions.
Two helper Components C 306, D 308, write transaction details into respective logs 307, 309 (in the given example), so Components C and D 306, 308 generate system log messages for Transaction XYZ. The location and format of each of the system logs 307, 309 is system dependent. Similar to an SNMP trap, a system log is in general only used to record abnormal conditions.
With traditional systems and call flow tracing technology an operator must know what type transaction recording method each component in the complex system uses. With such knowledge beforehand, the operator will then gain access to each of the recording method's “storage” and then determine a way to correlate a particular transaction from end-to-end and based on information obtained from appropriate storage for each component 302, 304, 306, 308. Most likely a “transaction identifier” is used to perform this task. Once all those pieces are in hand, a best attempt at identifying the flow of a given transaction may be reconstructed as depicted at 312.
However, the inventors herein recognize that the quality of this reconstruction is a direct function of the amount of (or lack of thereof) the data logged by the system's respective components. Using conventional call flow logic tracing technology, once the relevant data has been gathered, it must be analyzed to reproduce the actual call. The resulting reproduction is in many cases, at best, only an approximation of the actual call flow.
There is a need for improved complex call flow tracing in a distributed call system.



BRIEF DESCRIPTION OF THE DRAWINGS
Features and advantages of the present invention will become apparent to those skilled in the art from the following description with reference to the drawings, in which:
FIG. 1 shows an exemplary distributed computing system comprising four components, each embedding characters into an in-band logic history to collect a call flow transaction history, in accordance with the principles of the present invention.
FIG. 2 shows an exemplary logic string through an exemplary system, using an in-band logic history compilation technique implementing distributed logic compilation from within a complex distributed system, in accordance with the principles of the present invention.
FIG. 3 shows a distributed computing system consisting of an exemplary four components, and use of conventional technology to collect a transaction history.



SUMMARY OF THE INVENTION
In accordance with the principles of the present invention, an in-band call flow logic history is embedded in a logic history relating to a call request passed through a distributed call system. The in-band logic history comprises a first group of characters representing specific events in a logic flow of the call request relevant to a first component in the distributed call system, and a second group of characters representing specific events in the logic flow of the call request relevant to a second component in the distributed call system. The first group of characters and the second group of characters are retrieved in-band with the call request as the call request travels through the distributed call system.
In accordance with a method and apparatus according to the present invention, a method of embedding an end-to-end logic flow history in-band with a given call request comprises receiving a call request, and instantiating a logic history in-band relating to said call request. Characters representing a logic flow history are embedded into the in-band logic history. The call request is passed to another component in the distributed call system. A returned logic history string is received from the other component. The returned logic history string is embedded into the in-band logic history, and the logic history is stored in a suitable logic history database.
DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS
The present invention provides the ability to create an end-to-end in-band logic history for every request or call instance through a distributed computing system. Importantly, the created logic history uniquely traces each request's entire path, end-to-end, in-band within the messaging for the system. The end result is a single true representation of what occurred with no post computational inference.
The logic history creation performed in accordance with the principles of the present invention results in no measurable degradation to overall performance, and in general provides higher performance than otherwise conventional technique of logging and gathering the individual constituent parts and re-associating the data together. Thus, there is no longer the need for operational staff to correlate Call Detail Records (CDRs), error logs, SNMP traps etc. to gather what occurred in the system for a particular transaction of interest.
The inventors recognize that in critical systems such as a 911 emergency call system, it is very important to know what actually occurred in a particular emergency call, and not what may have occurred as is provided by conventional post-call inference technology. The invention provides a unique technique with the ability to track every logic decision point of a request, end-to-end, throughout a distributed call system. The inventive technique performs end-to-end logic tracing without the need for comparable overhead required by use of conventional tracing and logging mechanisms, and without any measurable effect on overall performance.
Many emergency call systems in telecommunications are implemented as distributed, fault tolerant systems. This invention provides the ability for a system operator or other interested and/or authorized party to uniquely trace the logic path through every sub-component in the distributed call system, and to gather the results of all components in the same hierarchical manner that the call instance used through the system. Thus the resulting logic trace shows the unique trace of the request through the system and is therefore referred to herein as a true and accurate “logic history”.
Preferably the logic history is stored in a human readable informational style. The logic history may be graded and verified by automated processes as desired.
While described with respect to end-to-end logic tracing of complex call flows in a distributed call system, the invention ultimately has application to computing systems that deploy messaging, and/or distributed systems wherein knowledge of the exact path (i.e. logic) of a transaction is required.
FIG. 1 shows an exemplary distributed computing system comprising four components, each embedding characters into an in-band logic history to collect a call flow transaction history, in accordance with the principles of the present invention.
For fault tolerance purposes there may be one or more of each component 202, 204, 206, 208 as indicated by the shadowed boxes in FIG. 1.
As shown in the example system of FIG. 1, there is a front end component A 202 that handles the in and outbound flow of requests.
The exemplary system also includes a core processing component B 204. The core processing component B 204 preferably adds to a logic history as shown and described in FIGS. 1 and 2. The exemplary system also includes two helper components C 206, and D 208.
Component A 202 accesses a suitable logic history database 214. The logic history database 214 may be co-located with component A 202, or may be remote therefrom.
As depicted in FIG. 1, a typical request (e.g., incoming call 200) enters the computing system via Front End Component A 202. The incoming call 200 is then routed between appropriate internal components, with a response (e.g., an outgoing call 210) eventually exiting the system.
It is desirable for operators of such systems to have the ability to know exactly how the request traveled through the system, e.g., which logic decision points were taken (or not taken), what the exact sequence of events was, etc. Ideally, as provided by the techniques and technology of the present invention, this is done without any measurable time degradation and for every request.
The present invention presents a unique solution by providing end-to-end, in band tracing of the logic taken by a request. In band refers to the ability to log and maintain a logic trace relating to a routed call data or message within the distributed call system itself, and logged real-time as the relevant call request progresses through each affected component of the distributed call system.
In this example, the incoming call 200 is processed by the front end component 202 which instantiates its logic history in the logic history database 214 and initializes it with its unique identifier A.
As a particular logic is followed, logic codes are added in-band to the logic history maintained in the logic history database 214. This assures that the logic history not only is obtained by information immediately relevant to the call request itself, but it eliminates any delays or failures to match a given request with its history drawn from an out-of-band source, e.g., from inferences made from call data records and such.
Continuing on with the given example shown in FIGS. 1 and 2, at some point and time, the front end component A 202 passes the request on to the core processing component B 204. This component B 204 performs database lookups in a suitable Component B datastore 205, thereby adding logic codes to the requests' logic history.
In the given example, Component B 204 then asks for additional processing from two helper components C 206, and D 208.
All of the exemplary Components A 202, B 204, C 206, D 208 start their own logic history, first by initializing it with their unique identifier (in this example B, C, and D) and then by adding on their logic codes. Once a component 202, 204, 206, 208 has completed its processing, it returns its relevant logic history string to the invoking caller (in this case Component A 202), which then embeds the returned string relevant to that component (in this case Components B 204, C 206 and D 208) into its own logic history. In this example, the returned logic history strings from the helper Components C 206, D 208 are embedded in the same logic history added to by the core processing Component B 204, which in turn is all embedded in the logic history originally instantiated (i.e., started) by the front end Component A 202.
The resulting logic history string 212 is a unique presentation of the path travelled by the call request through relevant portions of the distributed call system. Moreover, the logic history is easily and directly available contemporaneous with the call request itself (i.e., it is in-band). Thus, as soon as the call request is completed, the complete end-to-end call history is also complete and available, e.g., from the logic history database 214.
The logic history is easily readable, verified and archived by automated processes 214.
As depicted in the exemplary logic history string 212, logic history is preferably provided in a hierarchal manner. For instance, the logic history provided by components C 206 and D 208 are embedded into the logic history of the logic history provided by component B 204. In turn, the logic performed by component B 204 is embedded into the logic history provided by instantiating component A 202.
The proposed technology provides the ability to log a logic history for every call instance through a distributed computing system. The inventive in-band logic history uniquely traces a call's entire path, end-to-end, in-band within the distributed call system itself. The end result is a single true representation of what occurred with no inference required. Moreover, the in-band logic history is performed with no measurable degradation to overall performance.
The inventive in-band logic history generally provides higher performance than the otherwise conventional technology requiring call logging and post-call gathering of individual constituent parts, and then re-associating the data together to form a best-guess at what logic was actually performed. With a logic history embedded in-band in accordance with the principles of the present invention, there is no longer the conventional need for operational staff to correlate Call Detail Records (CDRs), error logs, SNMP traps etc. to gather what occurred in the system for a particular transaction of interest.
The invention does not force unique logic history codes across the system, which in practice would be brittle. Rather each sub-component that is logic history enabled can use codes that have meaning and applicability only to itself. This allows the system to be flexible and lets sub-components change and redefine their logic and logic history traces without impacting the rest of the system.
FIG. 2 shows an exemplary logic string through an exemplary system, using an in-band logic history compilation technique implementing in-band logic compilation from within a complex distributed system, in accordance with the principles of the present invention.
In particular, as shown in FIG. 2, a distributed computing system in general may consist of, say, N components (with N>=1) affecting a given call request. Each component can be considered as a self-contained computing unit that handles one or more tasks and returns a result. One component may request service from one or more other components within the system.
The exemplary component shown in FIG. 2 performs a database query and retrieves and returns a key. At each logic decision point a uniquely defined identifier is added to an in-band logic history to document the path taken through the code. Because the logic history is in-band, it is created real time within the distributed call system itself.
The uniquely defined identifier is a number in the example, though it may certainly instead be alphanumeric, and/or even textual.
In step 100 shown in FIG. 2, the first task at the entry point to the exemplary component initializes, or instantiates, the logic history. The logic history is preferably instantiated within a suitable logic history database 214, though it can instead be instantiated within the component A 202 itself. The instantiated logic history may be given a unique name relevant to the given particular computing component, e.g. “MyComponent”.
In step 102, a lookup is performed in a particular database pool (e.g., the logic history database 214 shown in FIG. 1) to query the database pool for a particular logic history. In the disclosed embodiment, a literal character (e.g., a literal “1”) is appended to the logic history at this point.
In step 103, the database lookup in step 102 can throw errors that may terminate the logic flow. In that case the logic history would be complete, and in the given example an indication as to this logic occurrence is indicated, e.g., with a literal “1” in step 102.
On the other hand, the database may report that there is no pool (steps 104, 106) with the desired criteria (whatever they may be). If not, then this logical flow may be documented with a suitable number, character, text, etc. In this example, a literal character (e.g., a “2”) would be appended to the logic history (in step 106) to indicate the occurrence of this logic flow to this particular call request, and the logic flow would advance to an end step 130.
Assuming that the logic history has been found in step 102, the logic will now move to step 108 where a lookup for keys of type A is performed to check if they are of a certain type. In this sample there are two types of keys, key type A and key type B. Step 108, if successful, would append an appropriate indicator (e.g., a literal “3”) to the in-band logic history. Any error would be reported in step 109.
In the given example, type A keys are the preferred keys and looked up first. In step 110, the flow determines whether or not the key is a type A key. If so, then the process moves to step 112, where action is taken to indicate in the in-band logic history that a type A key was found, e.g., by appending a literal “4” to the logic history.
From step 112, the process moves to step 126 to determine whether or not the call was a test call (important to test the operation and response of 911 emergency systems). If the call was a test call, the process moves to the end step 130. If not, the process moves to step 128 to add a key to the response depicted in step 128, and then to the end step 130.
Returning to step 110, if the key was not a type A key, then the process moves to step 114, where type B keys are searched for in the pool. If a type B key is found, a literal “5” would be appended to the in-band logic history. Any error would be reported in step 115.
Step 116 determines if a type B key is found. If not, the process moves to step 122 where a found valid key of type B is added to the logic history, then the process moves to step 126. Otherwise, if a type B key is found, step 120 determines if the key is still valid. If the key is still valid, step 122 determines and reports that an invalid type B key was found, and the process proceeds to step 126.
If no Type B key was found in step 116, then the process proceeds to step 118 to appropriately mark the in-band logic history, e.g., with a literal “6” 118 appended to the Logic History. As indicated earlier, the database lookup for the key can throw errors 109, 115 in which case the logic will come to an abrupt end with no further additions to the logic history. On the other hand, if a type B key was found, the logic determines if the type B keys is invalid 120, in which case the literal “8” is appended to the logic history in step 124. If the type B key is valid, a literal “7” will be appended to the logic history in step 122.
At the very end of the logic call flow, the logic does one final check to see if this was a test transaction 126 (which are quite common in distributed systems). Only if this was a real call (i.e., not a test call), step 128 will append a suitable indicator to the in-band logic history, e.g., a literal “9”, and the retrieved Key is returned in the response at the end step 130.
In summary, one possible call path through this sample component could be captured as [MyComponent: 1,3,4,9]. We choose to use the comma (,) as a delimiter between logic codes, however any other delimiter would serve just as well. The entire string of logic codes is delimited by a pair of two brackets ([,]). However any other pair of suitable delimiters may be chosen.
While the invention has been described with reference to the exemplary embodiments thereof, those skilled in the art will be able to make various modifications to the described embodiments of the invention without departing from the true spirit and scope of the invention.

## Claims

1. A method, comprising:
generating, at a given component of a plurality of components comprising one or more computing devices, a given logic history associated with the given component in response to receiving a call request at the given component;
embedding, at another component of the plurality of components comprising one or more computing devices, another logic history associated with the other component into the given logic history in response to the call request being routed from the given component to the other component; and
storing the given logic history for the call request in a database, wherein the given logic history characterizes an end-to-end logic flow history of the call request.

2. The method of claim 1, wherein each of the given and another logic history comprises a unique identifier associated with a respective component of the plurality of components.

3. The method of claim 2, wherein each logic code of a plurality of logic codes characterizes an event occurring at a respective component of the plurality of components in response to the call request.

4. The method of claim 2, wherein a given logic code of a plurality of logic codes is independent of the remaining plurality of logic codes.

5. The method of claim 1, comprising:
identifying a particular logic code associated with a particular component of the plurality of components; and
querying the database for a particular logic history that includes the particular logic code;
receiving the given logic history in response to the querying.

6. The method of claim 1, wherein the embedding is conducted substantially in real-time at the other component as the call request is routed to the other component.

7. An apparatus, comprising:
a given component comprising one or more computing devices, the given component being configured to:
receive a call request from a network server; and
embed a given logic code uniquely identifying the given component to a given logic flow history in response to the call request;

another component comprising one or more computing devices, the other component being configured to:
receive the call request from the given component; and
embed another logic code uniquely identifying the other component into the given logic flow history in response to receipt of the call request; and

a logic history database to receive and store the given logic flow history for the call request, the given logic flow history characterizing unique routing events encountered throughout the call request.

8. The apparatus of claim 7, wherein the given and another logic codes characterize an event occurring at a respective component in response to the call request.

9. The apparatus of claim 8, wherein the given logic code is independent of the other logic code.

10. The apparatus of claim 7, wherein the other logic code is embedded substantially in real-time at the other component as the call request is routed to the other component.

11. The apparatus of claim 7, comprising:
identifying a particular logic code associated with one of the given and the other component; and
querying the database for a particular logic history that includes the particular logic code;
receiving the given logic flow history in response to the querying.

12. The apparatus of claim 7, wherein the given logic code comprises a unique identifier associated with the given component.

13. A method, comprising:
generating, at a first component of a plurality of components comprising one or more computing devices, a first logic history associated with the first component in response to receiving a call request at the first component;
embedding, at a second component of a plurality of components comprising one or more computing devices, a second logic history associated with the second component into the first logic history in response to the call request being routed from the first component to the second component; and
embedding, at a third component of a plurality of components comprising one or more computing devices, a third logic history associated with the third component into the second logic history in response to the call request being routed from the second component to the third component; and
embedding, at a fourth component of a plurality of components comprising one or more computing devices, a fourth logic history associated with the fourth component into the second logic history in response to the call request being routed from the third component to the fourth component; and
storing the first logic history with the embedded second, third and fourth logic histories for the call request in a database, wherein the first logic history characterizes an end-to-end logic flow history of the call request.