Method and apparatus for breaking down computing tasks across a network of heterogeneous computer for parallel execution by utilizing autonomous mobile agents

• US 7,082,604 B2
• Filed: 04/20/2001
• Issued: 07/25/2006
• Est. Priority Date: 04/20/2001
• Status: Expired due to Fees

• Current Assignee: Mobile Travel Technologies Limited (Travelport Worldwide Ltd.)
• Original Assignee: Mobile Travel Technologies Limited (Travelport Worldwide Ltd.)
• Inventors: Schneiderman, Marc
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US09/838,806
• Publication Number:
  US 20020156932A1
• Time in Patent Office: 1,922 Days
• Field of Search: 718100-108, 719/317, 709202-246, 714/715, 713/1
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/4862 the task being a mobile agent, i.e. specifically designed to migrate
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/548 Object oriented; Remote method invocation [RMI] non-remote method invocation G06F9/449
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416

Abstract

A method and apparatus is provided for breaking down computing tasks within a larger application and distributing such tasks across a network of heterogeneous computers for simultaneous execution. The heterogeneous computers may be connected across a wide or local area network. The invention supports mobile agents that are self-migrating and can transport state information and stack trace information as they move from one host to another, continuing execution where the mobile agents may have left off. The invention includes a server component for providing an execution environment for the agents, in addition to sub-components which handle real-time collaboration between the mobile agents as well as facilities monitoring during execution. Additional components provide realistic thread migration for the mobile agents. Real-time stack trace information is stored as the computing tasks are executed, and if over-utilization of the computing host occurs, execution of the computing task can be halted and the computing task can be transferred to another computing hosts where execution can be seamlessly resumed using the stored, real-time state information and stack trace information.

Claims

1. A method for providing parallel execution of computing tasks in a heterogeneous computing environment having a plurality of computing hosts, comprising:

partitioning a computing task into small tasks;

assigning each of the small tasks to mobile agents stored at a central server;

monitoring the computing hosts for detecting an indication that migration needs to be initiated;

determining available computing hosts in the heterogeneous computing environment;

automatically transferring said mobile agents to determined available computing hosts responsive to a detected indication that migration needs to be initiated;

executing said mobile agents at the available computing hosts using execution code from the central server in response to a request from the available computing hosts; and

maintaining, at a second computing host at which none of said mobile agents are executing, stack trace and state information about each of said mobile agents to allow one or more of said mobile agents to be reconstructed at an alternate computing host using said stack trace and state information.

2. The method of claim 1, wherein said indication that migration needs to be initiated comprises an indication of network latency.

3. The method of claim 1, further comprising transferring the execution code from the central server to virtual machines at the available computing hosts.

4. The method of claim 3, wherein the step of transferring the execution code is performed in response to a request by a mobile agent.

5. The method of claim 4, wherein the step of transferring the execution code is performed by a web server.

6. The method of claim 1, wherein the step of executing the mobile agents is performed in virtual machines at the computing hosts without modification of the virtual machines.

7. The method of claim 1 further comprising monitoring execution of the mobile agents at the available computing hosts.

8. The method of claim 1 further comprising allowing the mobile agents to collaborate over the heterogeneous computing environment as the mobile agents execute at the available computing hosts.

9. The method of claim 1, wherein the mobile agents are executed in real time.

10. The method of claim 1, wherein said step of determining available computing hosts is performed in real time.

11. The method of claim 1, wherein the indication comprises an indication of hostile attack.

12. The method of claim 1, wherein the indication comprises an indication of hacking.

13. The method of claim 1, wherein the indication comprises an indication of network failure.

14. The method of claim 1 wherein the indication comprises an indication of computer hardware failure.

15. The method of claim 1 further comprising reconstructing one or more of said mobile agents at said second computing host using said stack trace and state information stored at said first computing host.

16. A method for providing parallel computing using mobile agents in a heterogeneous computing environment having a plurality of computing hosts, comprising:

assigning a computing task to one or more mobile agents stored at a central server;

monitoring the computing hosts for detecting an indication that migration needs to be initiated;

transferring the one or more mobile agents to one or more available computing hosts responsive to a detected indication that migration needs to be initiated;

transferring execution code from the central server to the one or more available computing hosts in response to a request from the available computing hosts;

executing the one or more mobile agents at the one or more available computing hosts using the execution code; and

storing stack trace and real-time state information about the one or more mobile agents at a first alternate computing host on which none of the one or more mobile agents are executing to allow the one or more mobile agents to be reconstructed at a second alternate computing host.

17. The method of claim 16, wherein said detected indication that migration needs to be initiated is an indication of network latency, said method further comprising, prior to transferring the mobile agents, the step of:

halting transferring of the mobile agents if said detected network latency exceeds a threshold.

18. The method of claim 17 comprising transferring the mobile agents if utilization of computing hosts fails to exceed a predetermined threshold.

19. The method of claim 16, wherein the step of transferring said one or more mobile agents to one or more available computing hosts comprises transferring data relating to said one or more mobile agents to said one or more available computing hosts.

20. A method for migrating a software application running in a virtual machine from a primary host to a secondary host comprising;

constructing an application using a plurality of mobile agents stored in a central server;

transferring the plurality of mobile agents to a first computing host;

executing the plurality of mobile agents at said first computing host;

maintaining stack trace and state information about each of the plurality of mobile agents at a second computing host on which none of the plurality of mobile agents are executing;

detecting an indication to migrate the application, wherein said indication comprises one of the group consisting of;

network latency, hostile attack, hacking,

network failure and computer hardware failure;

in response to a detected indication, automatically migrating the application in its entirety from said first computing host to a third computing host without modifying the virtual machine at said third computing host by reconstructing each of the plurality of mobile agents at said third computing host using said stack trace and state information; and

executing the plurality of mobile agents at the third computing host using execution code provided by the central server in response to a request from the third computing host.

21. The method of claim 20 further comprising resuming execution of the mobile agent at said third computing host at a point where execution was halted.

22. The method of claim 21, wherein said stack trace and state information comprises information about an execution thread of the mobile agent as it existed at said first computing host prior to being transferred to said third computing host.

23. The method of claim 20 further comprising:

continuing monitoring for another indication to migrate the application;

continuing migrating the application to other hosts.

24. A computer system for providing parallel execution of computing tasks in a heterogeneous computing environment comprising at least two computing hosts, said system comprising;

a dispatcher for partitioning the computing task into a plurality of small tasks and dispatching the small tasks;

mobile agents for receiving small tasks from the dispatcher;

means for monitoring execution of the mobile agents at the computing hosts;

means for detecting over-utilization of one of the computing hosts and for issuing a warning when one of the computing hosts is over-utilized,

computing resources on a network including virtual machines for executing mobile agent software code;

means for transferring the mobile agents to the computing resources; and

means for automatically transferring execution code as well as stack trace and state information about each of the mobile agents responsive to detected over-utilization of one of the computing hosts from a central server to the computing resources, the computing resources receiving and executing one of the small tasks assigned to a mobile agent in the virtual machines using the execution code from the central server in response to a request from the available computing resources and the means for transferring execution code maintaining stack trace and state information about each of the mobile agents at a first computing host where none of the mobile agents are executing to allow each of the mobile agents to be reconstructed at a second computing host.

25. The computer system of claim 24 wherein the central server comprises a web server.

26. The computer system of claim 25, wherein the web server is located at a first organization.

27. The apparatus computer system of claim 26 further comprising an agent execution environment located at a second organization.

28. The computer system of claim 27 further comprising firewalls at said first and second organizations to allow execution code for said mobile agents to be exchanged between said first and second organizations.

29. The computer system of claim 24 further comprising means for monitoring execution of the small tasks.

30. The computer system of claim 24 further comprising collaboration means for allowing the mobile agents to communicate and share information in real time.

31. The computer system of claim 24, wherein the in mobile agents execute in real time.

32. The computer system of claim 24, further comprising storage means for storing real time state information about the mobile agents as the mobile agents execute at the computing resources.

33. The computer system of claim 24 further comprising:

means for monitoring execution of the mobile agents at the computing hosts; and

means for detecting over-utilization of one of the computing hosts and for issuing a warning when one of the computing hosts is over-utilized.

34. The computer system of claim 24, wherein said means for transferring said mobile agents to said computing resources comprises means for transferring data relating to said mobile agents to said computing resources.

35. A method for providing realistic thread migration which comprises:

instantiating a mobile agent thread at a first computing host;

processing said mobile agent thread at said first computing host;

storing stack trace and state information about said mobile agent thread at a second computing host at which said mobile agent thread is not executing as said mobile agent thread executes at said first computing host;

detecting an indication to migrate said mobile agent thread and in response to said indication;

stopping execution of said mobile agent thread;

automatically transferring the execution code for said mobile agent thread from a central server to a third computing host; and

automatically transferring said stack trace and state information about said mobile agent thread to said third computing host.

36. The method of claim 35, wherein the steps are carried out without the need to explicitly write any additional software code to either initiate, manage, or facilitate the transfer of a mobile agent during said process of thread migration.

37. The method of claim 35 further comprising:

receiving said stack trace and state information about said mobile agent thread at said third computing host;

reconstructing said mobile agent thread at said third computing host using said stack trace and state information about said mobile agent thread; and

continuing processing of said mobile agent thread at said third computing host at a point at which execution of said thread was stopped at said first computing host.

38. The method of claim 37 wherein the step of automatically transferring said stack trace and state information about said mobile agent thread further comprises serializing the state information about said mobile agent thread.