Apparatus and method for computing the processing delay of adaptive applications network terminals and applications thereof

• US 5,961,599 A
• Filed: 10/15/1997
• Issued: 10/05/1999
• Est. Priority Date: 10/15/1996
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Moghe, Pratyush, Kalavade, Asawaree
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Coulter, Kenneth R.
• Application Number:
  US08/950,638
• Time in Patent Office: 720 Days
• Field of Search: 395/200.54, 709/224
• US Class Current: 709/224
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis

Abstract

Method and apparatus for computing the processing delay of a terminal running a system of one or more adaptive applications, each adaptive application consisting of a set of executable tasks sharing system resources, the set of execution tasks having execution times depending on a particular adaptation level, the method including the steps of: modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by the application in a particular adaptation level; modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution; modeling a system-wide computation by a state process for capturing transitions of executing tasks as the tasks currently use or contend for the shared system resources, the state process being characterized as a stochastic process; calculating a stationary distribution π^M from the stochastic state process; and, from the stationary distribution, calculating the processing delay of the adaptive applications.

Claims

1. Method for designing a system having resources enabling the concurrent execution of one or more adaptive applications, each of said adaptive applications consisting of a set of executable tasks sharing said system resources, said set of executable tasks having execution times depending on a particular adaptation level, said method comprising the steps of:

a) mapping components of each said adaptive application to system resources;

b) computing performance measures based upon a particular adaptation process, said performance measures including a measure of the resource contention at resource R;

c) comparing resource contention at each particular resource with a predetermined threshold; and

,

d) if said resource contention at a particular resource is less than said predetermined threshold, then removing a most idle resource from said mapping and returning to step a).

2. Method for designing a system according to claim 1, wherein said step of computing performance measures includes the step of computing a processing delay of each application.

3. Method for designing a system according to claim 1, wherein the step of computing a processing delay of each application includes the steps of:

a) modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level;

b) modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution;

c) modeling a system-wide computation by a state process, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process;

d) calculating a stationary distribution π

^M from said stochastic state process; and

,

e) from said stationary distribution, calculating the processing delay of said adaptive applications.

4. Method for designing a system according to claim 3, wherein said step of modelling an adaptation process for each adaptive application includes the step of approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ

_m representing a long-term fraction of time spent by said application in an adaptation level m.

5. Method for designing a system according to claim 4, further including the step of modelling the computation offered by an application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

6. Method for designing a system according to claim 5, wherein system-wide state change occurs at specific time instances, each said time instants defined as a state transition time A_n, said step of modelling said state process includes the step of generating a joint sequence (Y, Z,U) enabling reproduction of an evolution of said state process where

Y is a vector sequence equal to {Y_n, n=0, 1, . . . }, where Y_n,=(I, w_I), where I is a set of nodes ready and waiting at transition time A_n^-,w_I is the delay incurred by these nodes, and A_n - denotes the time just prior to an n^th transition time;

Z is a vector sequence equal to {Z_n, n=0, 1, . . . }, where Z_n =(J, r_J) where J is a set of nodes that are running at transition time A_n, r_J is the remaining execution time of these nodes; and

U is a vector sequence equal to {U_n, n=0, 1, . . . }, where U_n =(App, m^App, t^App) where App is the application, m^App is the adaptation application of application at instant A_n^-, and t^App is the elapsed time of application at time A_n^-.

7. Method for designing a system according to claim 6, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k,l,c), said step d) of calculating a stationary distribution further including the step of computing a transition probability function defined by:

##EQU11## where (i,j,a), (k,l,c)ε

S, where S is the state space of state process X.

8. Method for designing a system according to claim 7, wherein said stationary distribution represents the probability that (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π

^M further including the step of solving a set of linear equations ##EQU12##

9. Method for designing a system according to claim 8, further including the step of calculating an unconditioned stationary distribution π

regardless of adaptation level m, said step of calculating π

including the step of solving a set of linear equations;

10. Method for designing a system according to claim 9, further including the step of calculating an average nodal wait time W_b representing a mean time a said node "b" has to wait before it can run on the resource it is mapped to, said calculating step including the steps of solving an equation where r_b is equal to a value of node b'"'"'s remaining execution time and is equal to its execution time t_b and w_b^ija represents node b'"'"'s wait at state (i,j,a).

11. Method for designing a system according to claim 10, further including the step of calculating an average resource wait time W_R representing said measure of the resource contention at resource R, said calculating step including the steps of solving an equation ##EQU13## where W_b represents the average nodal wait time for node b.

22. An application manager as claimed in claim 1, further including means for comparing a processing delay computed for a first adaptive application against a predetermined threshold and determining feasibility of said change in said adaptation level of a second adaptive application.

23. An application manager as claimed in claim 22, wherein said means for computing a processing delay distribution for said terminal, further including means for determining a combination of adaptation level changes whereby excess delay probabilities for all adaptive applications are feasible.

32. An application manager according to claim 23, wherein said adaptive application includes one of video and audio applications.

12. Method for computing the processing delay of a terminal running a system of one or more adaptive applications, each adaptive application consisting of a set of executable tasks sharing system resources, said set of execution tasks having execution times depending on a particular adaptation level, said method comprising the steps of:

a) modelling the adaptation of each adaptive application as an adaptation process having steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level;

b) modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution;

c) modeling a system-wide computation by a state process X, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process;

d) calculating a stationary distribution π

^M from said stochastic state process; and

,

e) from said stationary distribution, calculating the processing delay of said adaptive applications.

13. A method according to claim 12, wherein said processing delay is calculated for a particular combination of adaptation levels.

14. A method according to claim 12, wherein said processing delay is calculated regardless of a combination of adaptation levels.

15. A method according to claim 12, wherein said step of modelling an adaptation process for each adaptive application includes the step of approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ

_m representing a long-term fraction of time spent by said application in an adaptation level m.

16. A method according to claim 15, further including the step of modelling the computation offered by an application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

17. A method according to claim 16, wherein system-wide state changes in a computation occur at specific time instances, each said time instants defined as a state transition time A_n, said step of modelling said state process includes the step of generating a joint sequence (Y, Z,U) enabling reproduction of an evolution of said state process X where

Y is a vector sequence equal to {Y_n,n=0, 1, . . . }, where Y_n,=(I, w_I), where I is a set of nodes ready and waiting at transition time A_n^-, w_I is the delay incurred by these nodes, and A_n^- denotes the time just prior to an n^th transition time;

Z is a vector sequence equal to {Z_n, n=0, 1, . . . }, where Z_n =(J, r_J) where J is a set of nodes that are running at transition time A_n,r_J is the remaining execution time of these nodes; and

U is a vector sequence equal to {U_n,n=0, 1, . . . }, where U_n =(App,m^App, t^App) where App is the application, m^App is the adaptation application of application at instant A_n^-, and t^App is the elapsed time of application at time A_n^-.

18. A method according to claim 17, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k, l,c), said step d) of calculating a stationary distribution further including the step of computing a transition probability function defined by:

##EQU14## where (i,j,a), (k,l,c) ε

S, where S is the state space of X.

19. A method according to claim 18, wherein said stationary distribution represents the probability that (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π

^M further including the step of solving a set of linear equations ##EQU15##20.

20. A method according to claim 18, further including the step of calculating an unconditioned stationary distribution π

regardless of adaptation level m, said step of calculating π

including the step of solving a set of linear equations;

21. An application manager for optimizing system resources of a terminal in an interconnected network, said terminal having one or more concurrently running adaptive applications, each adaptive application consisting of a set of executable tasks sharing said system resources, said set of execution tasks having execution times depending on a particular adaptation level, said application manager comprising:

means for receiving feedback information from said network, said feedback indicating network performance;

means for computing a processing delay distribution for said terminal, said processing delay distribution based upon any combination of adaptation levels; and

,

means for changing an adaptation level for a particular adaptation application in accordance with said feedback information and said processing delay distribution computed for said terminal, whereby system resources are optimized.

24. An application manager as claimed in claim 21, wherein said step of computing the processing delay for said terminal comprises:

means for modelling the adaptation of each adaptive application as an adaptation process having a steady-state probability distribution representing the fraction of time spent by said application in a particular adaptation level;

means for modelling execution time variations of tasks in each application, for a particular adaptation level, by a random variable of arbitrary and known probability distribution;

means for modelling a system-wide computation by a state process X, said state process capturing transitions of executing tasks as said tasks currently use or contend for shared system resources, said state process being characterized as a stochastic process; and

,

means for calculating a stationary distribution π

^M from said stochastic state process, said processing delay for said terminal being calculated from said stationary distribution π

^M.

25. An application manager according to claim 24, wherein said processing delay is calculated for a particular combination of adaptation levels.

26. An application manager according to claim 25, wherein said means for modelling an adaptation process for each adaptive application further includes means for approximating the adaptation of each adaptive application as a jump process having a steady state transition probability distribution γ

_m representing a long-term fraction of time spent by said application in an adaptation level m.

27. An application manager according to claim 26, further including means for modelling the computation offered by an adaptation application in a particular adaptation level as a task graph consisting of nodes representing task level computations and arcs connecting said nodes for specifying execution precedence.

28. An application manager according to claim 27, wherein said means for receiving feedback information from said network occurs at specific time instants, each said time instants defined as a state transition time A_n, said means for modelling the system-wide computation further including means for generating a joint sequence (Y,Z,U) enabling reproduction of an evolution of said state process where

Y is a vector sequence equal to {Y_n,n=0, 1, . . . }, where Y_n,=(I,w_I), where I is a set of nodes ready and waiting at transition time A_n^-, w_I is the delay incurred by these nodes, and A_n^- denotes the time just prior to an n^th transition time;

Z is a vector sequence equal to {Z_n,n=0, 1, . . . }, where Z_n =(J, r_J) where J is a set of nodes that are running at transition time A_n, r_J is the remaining execution time of these nodes; and

U is a vector sequence equal to {U_n, n=0, 1, . . . }, where U_n =(App, m^App, t^App) where App is the application, m^App is the adaptation application of application at instant A_n^-, and t^App is the elapsed time of application at time A_n^-.

29. An application manager according to claim 28, wherein said joint sequence (Y,Z,U) makes transitions from a first state (i,j,a) to a second state (k,l,c), said means for calculating a stationary distribution further including means for computing a transition probability function defined by:

##EQU16## where(i,j,a),(k,l,c) ε

S, where S is the state space of state process X.

30. An application manager according to claim 29, wherein said stationary distribution represents the probability that said joint process (Y,Z,U) transitions to state (i,j,a), for a particular adaptation level m, given that (Y,Z,U) changes from a current state, said step of calculating said stationary distribution π

^M further including means for solving a set of linear equations ##EQU17##

31. An application manager according to claim 30, further including means for calculating an unconditioned stationary distribution π

regardless of adaptation level m, said calculating means solving a set of linear equations;