Method and system for load-balanced data exchange in distributed network-based resource allocation

• US 6,766,348 B1
• Filed: 08/03/1999
• Issued: 07/20/2004
• Est. Priority Date: 08/03/1999
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: WorldCom, Inc. (Verizon Communications Inc.)
• Inventors: Gold, Jeffrey, Pedersen, David, Combs, Charles, Schear, David, Mair, Brian
• Primary Examiner(s): Khatri, Anil
• Assistant Examiner(s): PHAM, THOMAS K
• Application Number:
  US09/365,631
• Time in Patent Office: 1,813 Days
• Field of Search: 709/100, 709/104, 709/105, 709/226, 709/228, 709/229, 710/268
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method and system for allocating distributed resources connected to a computer network to application programs running on computers attached to the communications network. The distributed resource allocator system comprises a number of identical processes running on one or more computers attached to the communications network. Application programs request allocation of resources from a local distributed resource allocator system process running using a resource allocator applications programming interface. Application programs request allocation of resource from a remote distributed resource allocator system process via a resource allocator access protocol. The distributed resource allocator system is fault-tolerant and provides contention control and load balancing. The resource allocator system also manages information about the capacities and capabilities of resources connected to the communications network. Application programs can thus be easily written to make use of distributed resources connected to a communications network without having to manage global network information and without needing complex contention control and load balancing subroutines.

Claims

1. In a computer network, a distributed resource allocation system operating across a plurality of domains within the computer network that balances the assignment of resources, comprising:

a resource allocator in a domain that receives a resource request from an application program;

a resource database including data regarding resources in the domain of the resource allocator;

a load balancing mechanism that examines the resource database to locate a resource in the domain of the resource allocator matching the resource request, and if more than one resource matches the resource request, forms a resource list by sorting the more than one resource according to greatest remaining capacity and selects a resource in the resource list based on a predetermined rule;

another resource allocator in another domain that communicates with the load balancing mechanism; and

another resource database containing data regarding resources in the another domain,

wherein if the load balancing mechanism does not locate a resource in the resource database that matches the resource request, then the load balancing mechanism examines the another resource database to locate a resource matching the resource request, and if more than one resource matches the resource request, forms a resource list by sorting the more than one resource according to greatest remaining capacity and selects a first resource in the resource list.

2. The system recited in claim 1 wherein the resource database includes data regarding resources in the plurality of domains and wherein if the load balancing mechanism does not locate a resource in the domain of the resource allocator that matches the resource request, then the load balancing mechanism examines the resource database to locate a resource in another domain that matches the resource request, and if more than one resource in another domains matches the resource request, forms a resource list by sorting the more than one resource in another domain according to greatest remaining capacity and selects a resource in the resource list.

3. The system recited in claim 1 wherein the predetermined rule selects the resource in the resource list that leads the list.

4. The system recited in claim 1 wherein the predetermined rule selects the resource in the resource list having the best fit.

5. The system recited in claim 1, further comprising an application programming interface to the application program that interfaces with the resource allocator, wherein the application program interface includes an Allocate-Resource function that causes the resource allocator to allocate the resource to the application program.

6. The system recited in claim 1, further comprising an application programming interface that provides functions that are called by the application program and executed by the resource allocator, including functions that allocate, deallocate, and make use of the resources.

7. The system recited in claim 1, wherein each resource is categorized and described in the resource database as being a member of one of two categories that include task-oriented and interaction-oriented resources, a task-oriented resource accepting and executing tasks assigned to it without needing additional interaction with an application program assigning the task, and an interaction-oriented resource requiring a dialogue or interaction with an application program in order to complete a task.

8. The system recited in claim 1, wherein each resource is described in the resource database as having a total capacity for handling a maximum number of tasks or dialogues and a remaining capacity that identifies that portion of the total capacity that has not been allocated to application programs through calls to an application programming interface.

9. The system recited in claim 1, further comprising a flow control and data transmission interface both between the application program and the resource allocator that coordinates use of the network resources by the application program and between components of the resource allocator, wherein the components of the resource allocator include resource allocator systems that execute functions called by the application program.

10. The system recited in claim 1, further comprising a resource allocator user agent associated with the resource allocator that transfers function calls from application programs running on one computer over the computer network, and a resource allocator system that transfers function calls received over the computer network from the resource allocator user agent to the resource allocator for execution.

11. The system recited in claim 1, further comprising an application programming interface to the application program that interfaces with the resource allocator and includes a Set-Current-Capacity function that causes the resource allocator to set a remaining capacity description stored in the resource database for a resource indicated by arguments to the Set-Current-Capacity function to a particular value indicated by an argument to the Set-Current-Capacity function.

12. The system recited in claim 1, further comprising an application programming interface to the application program that interfaces with the resource allocator and includes a Schedule-Task function that causes the resource allocator to schedule a task, indicated by an argument to the Schedule-Task function, to a resource indicated by an argument to the Schedule-Task function.

13. The system recited in claim 1, further comprising an application programming interface to the application program that interfaces with the resource allocator, wherein the application program interface includes a Bind function that causes the resource allocator to establish a session with the application program, a handle indicating the established session returned to the application program by the resource allocator as a result of successfully executing the Bind function, wherein the established sessions provides to the application program a context in which to make subsequent function calls to the distributed resource allocator handling system.

14. In a computer network, a distributed resource allocation system operating across a plurality of domains within the computer network that balances the assignment of resources, comprising:

a resource allocator in a domain that receives a resource request from an application program;

a resource database including data regarding resources in the domain of the resource allocator;

a load balancing mechanism that examines the resource database to locate a resource in the domain of the resource allocator matching the resource request, and if more than one resource matches the resource request, forms a resource list by sorting the more than one resource according to greatest remaining capacity and selects a resource in the resource list based on a predetermined rule;

another resource allocator in another domain that communicates with the load balancing mechanism using a remote access system protocol for transferring data from one resource allocator to another resource allocator; and

another resource database containing data regarding resources in the another domain,

wherein if the load balancing mechanism does not locate a resource in the resource database that matches the resource request, then the load balancing mechanism examines the another resource database using the remote access system protocol to locate a resource matching the resource request.

15. In a computer network that interconnects computer resources, a flow control and data transmission interact both between application programs and a distributed resource allocator handling system that coordinates use of the computer resources by the application programs and between components of the distributed resource allocator handling system, wherein the components of the distributed resource allocator handling system include resource allocator systems that execute functions called by the application programs, resource allocator user agents that transfer function calls from application programs running on one computer over the computer network to a second computer, and resource allocator system agents that transfer function calls received over the computer network from a resource allocator user agent to a resource allocator system for execution, the flow control and data transmission interface comprising:

an application programming interface that provides the functions that are called by the application programs and executed by a resource allocator system, including functions that allocate, deallocate, and make use of the computer resources;

a remote access agent protocol used by a resource allocator user agent running on a local computer to encapsulate the application programming interface function calls made by an application program running on the local computer and transport the encapsulated function calls over the computer network to a resource allocator system agent running on a remote computer, and used by the resource allocator system agent to encapsulate data returned by a resource allocator system running on the remote computer in response to the function calls and transport the encapsulated data over the computer network to the resource allocator user agent; and

a remote access system protocol used by the resource allocator systems of the distributed resource allocator handling system to transfer data from one resource allocator system to another.

16. The flow control and data transmission interface of claim 15 wherein the application programming interface includes a Bind function that causes the resource allocator handling system to establish a session with a calling application program, a handle indicating the established session returned to the calling application program by the resource allocator handling system as a result of successfully executing the Bind function, wherein the established session provides to the application program a context in which to make subsequent function calls to the resource allocator handling system.

17. The flow control and data transmission interface of claim 15 wherein the application programming interface includes a Register-Resource function that causes the resource allocator handling system to add a description of a resource indicated by arguments to the Register-Resource function into a global network information database.

18. In a computer network that interconnects computer resources, a method for exchanging function calls and data between application programs and a distributed resource allocator handling system that coordinates use of the computer resources by the application programs and for exchanging data between components of the distributed resource allocator handling system, wherein the components of the distributed resource allocator handling system include a resource allocator system that execute functions called by the application programs, a resource allocator user agent that transfer function calls from application programs running on one computer over the computer network to a second computer, and a resource allocator system agent that transfer function calls received over the computer network from the resource allocator user agent to the resource allocator system for execution, the method comprising:

calling a function within an application program that is provided by an application programming interface and executed by the resource allocator system;

when the resource allocator system is running on a different computer than on which the application programs is running,

passing the function call from the application program to the resource allocator user agent running on the same computer as that on which the application programs is running,

packaging the function call by the resource allocator user agent into a remote access agent protocol message and sending the remote access agent protocol message over the computer network to the resource allocator system agent running on the same computer as than on which the resource allocator system is running, and

unpackaging the function call from the received remote access agent protocol by the resource allocator system agent and passing the function call directly from the resource allocator system agent to the resource allocator system;

when the resource allocator system is running on the same computer as that on which the application programs is running, passing the function call directly from the application program to the resource allocator system;

executing the function by the resource allocator system and returning to the application program data provided by the resource allocator system as a result of execution of the function call; and

when execution of the function by the resource allocator system causes the resource allocator system to change data stored in a global network information database to describe a current state for the distributed resource allocator handling system and when more than one resource allocator system is running on the computer network, sending a resource allocator system protocol message from the resource allocator system that executed the function call to all remaining resource allocator systems running on the computer network so that all resource allocator systems can accordingly update their respective global network information databases.

19. The method of claim 18 wherein the application programming interface includes an Allocate-Resource function that causes the resource allocator handling system to allocate a resource indicated by arguments to the Allocate-Resource function to a calling application program for subsequent use by the calling application program.

20. The method of claim 18 wherein each resource is described in the global network information database as having a total capacity for handling a maximum number of tasks or dialogues and a remaining capacity that identifies that portion of the total capacity that has not been allocated to application programs through calls to the application programming interface function Allocate-Resource.