Method and apparatus for performing non service affecting software upgrades in place

1. A method executed by a processor for upgrading software represented as a call flow graph having a plurality of states and a plurality of state transitions where a plurality of tokens traverse the graph executing functions, comprising:

identifying a target region of the graph;

obtaining a new region for the graph;

determining a correspondence between states of the target region of the graph and states of the new region for the graph, said step of determining the correspondence between states of the target region of the graph and states of the new region for the graph comprising:

identifying states of the target region of the graph;

identifying states of the new region for the graph; and

for each of the identified states of the target region of the graph, determining whether any of the states of the new region for the graph are associated with that state of the target region of the graph; and

replacing the target region of the graph with the new region for the graph using the correspondence between states of the target region of the graph and states of the new region for the graph.

2. The method of claim 1 , wherein replacing the target region of the graph with the new region for the graph comprises:

identifying ones of the tokens associated with the target region of the graph;

suspending tokens associated with the target region of the graph based on the determined correspondence between states, wherein each token is suspended in a desired state;

deleting the target region of the graph;

reading the new region for the graph into the graph; and

releasing the suspended tokens.

3. The method of claim 2 , wherein suspending the tokens associated with the target region of the graph comprises:

identifying ones of the tokens associated with the target region of the graph;

forcing each of the identified ones of the tokens associated with the target region of the graph into a desired state; and

for each token, in response to a determination that the token enters a desired state, suspending the token.

4. The method of claim 2 , wherein suspending the tokens associated with the target region of the graph comprises:

identifying ones of the tokens associated with the target region of the graph;

monitoring each of the identified ones of the tokens associated with the target region of the graph as the tokens traverse the target region of the graph; and

for each token, in response to a determination that the token enters a desired state, suspending the token.

5. The method of claim 2 , wherein a desired state for a token comprises a state in the target region of the graph having at least one corresponding state in the new region for the graph.

6. The method of claim 1 , wherein replacing the target region of the graph with the new region for the graph comprises:

identifying ones of the states of the target region of the graph that are entry states to the target region of the graph;

renaming each of the identified entry states;

reading the new region for the graph into the graph; and

transferring ones of the tokens associated with the target region of the graph to the new region for the graph using the determined correspondence between states.

7. The method of claim 4 , wherein tokens of the graph not associated with the target region of the graph that would otherwise enter the target region of the graph instead enter the new region for the graph using the renamed entry states.

8. The method of claim 1 , wherein identifying the target region of the graph comprises:

selecting at least one function to be upgraded; and

identifying ones of the states and ones of the state transitions adapted to perform the selected at least one function.

9. An apparatus comprising a processor for upgrading software represented as a call flow graph having a plurality of states and a plurality of state transitions where a plurality of tokens traverse the graph executing functions, the apparatus comprises:

means for identifying a target region of the graph;

means for obtaining a new region for the graph;

means for determining a correspondence between states of the target region of the graph and states of the new region for the graph, said means for determining the correspondence between states of the target region of the graph and states of the new region for the graph further comprising:

means for identifying states of the target region of the graph;

means for identifying states of the new region for the graph; and

for each of the identified states of the target region of the graph, means for determining whether any of the states of the new region for the graph are associated with that state of the target region of the graph; and

means for replacing the target region of the graph with the new region for the graph using the correspondence between states of the target region of the graph and states of the new region for the graph.

10. The apparatus of claim 9 , wherein the means for replacing the target region of the graph with the new region for the graph comprises:

means for identifying ones of the tokens associated with the target region of the graph;

means for suspending tokens associated with the target region of the graph based on the determined correspondence between states, wherein each token is suspended in a desired state;

means for deleting the target region of the graph;

means for reading the new region for the graph into the graph; and

means for releasing the suspended tokens.

11. The apparatus of claim 10 , wherein the means for suspending the tokens associated with the target region of the graph comprises:

means for identifying ones of the tokens associated with the target region of the graph;

means for forcing each of the identified ones of the tokens associated with the target region of the graph into a desired state; and

means for suspending each token, where each token is suspended in response to a determination that the token enters a desired state.

12. The apparatus of claim 10 , wherein the means for suspending the tokens associated with the target region of the graph comprises:

means for identifying ones of the tokens associated with the target region of the graph;

means for monitoring each of the identified ones of the tokens associated with the target region of the graph as the tokens traverse the target region of the graph; and

means for suspending each token, where each token is suspended in response to a determination that the token enters a desired state.

13. The apparatus of claim 10 , wherein a desired state for a token comprises a state in the target region of the graph having at least one corresponding state in the new region for the graph.

14. The apparatus of claim 9 , wherein the means for replacing the target region of the graph with the new region for the graph comprises:

means for identifying ones of the states of the target region of the graph that are entry states to the target region of the graph;

means for renaming each of the identified entry states;

means for reading the new region for the graph into the graph; and

means for transferring ones of the tokens associated with the target region of the graph to the new region for the graph using the determined correspondence between states.

15. The apparatus of claim 14 , wherein tokens of the graph not associated with the target region of the graph that would otherwise enter the target region of the graph instead enter the new region for the graph using the renamed entry states.

16. The apparatus of claim 9 , wherein the means for identifying the target region of the graph comprises:

means for selecting at least one function to be upgraded; and

means for identifying ones of the states and ones of the state transitions adapted to perform the selected at least one function.

17. A non-transitory computer readable medium storing a software program that, when executed by a computer, causes the computer to perform a method for upgrading software represented as a call flow graph having a plurality of states and a plurality of state transitions where a plurality of tokens traverse the graph executing functions, comprising:

identifying a target region of the graph;

obtaining a new region for the graph;

determining a correspondence between states of the target region of the graph and states of the new region for the graph, said step of determining the correspondence between states of the target region of the graph and states of the new region for the graph comprising:

identifying states of the target region of the graph;

identifying states of the new region for the graph; and

for each of the identified states of the target region of the graph, determining whether any of the states of the new region for the graph are associated with that state of the target region of the graph; and

replacing the target region of the graph with the new region for the graph using the correspondence between states of the target region of the graph and states of the new region for the graph.

18. The non-transitory computer readable medium of claim 17 , wherein replacing the target region of the graph with the new region for the graph comprises one of:

identifying ones of the tokens associated with the target region of the graph, suspending tokens associated with the target region of the graph based on the determined correspondence between states where each token is suspended in a desired state, deleting the target region of the graph, reading the new region for the graph into the graph, and releasing the suspended tokens; or

identifying ones of the states of the target region of the graph that are entry states to the target region of the graph, renaming each of the identified entry states, reading the new region for the graph into the graph, and transferring ones of the tokens associated with the target region of the graph to the new region for the graph using the determined correspondence between states.