Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-02-26
2002-11-12
Robinson, Greta L. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C705S080000, C705S400000, C709S202000
Reexamination Certificate
active
06480861
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computerized information systems. More specifically, it describes sophisticated techniques for managing, locating, allocating and assuring the availability of information resources in a distributed environment.
BACKGROUND OF THE INVENTION
Distributed applications are much more difficult to write and manage than applications developed for a single computer. The basic problem facing distributed application designers is not a lack of resources but an inability to dynamically manage and effectively leverage those resources. Efficiently utilizing a multiplicity of resources often becomes a prohibitively complex problem.
The availability of an application on demand is of critical importance in many operational environments. In a distributed environment, it is possible to enhance the availability and fault-tolerance of an application by providing redundant points of service in order to ensure that the failure of any individual part of the network does not prevent the network, as a whole, from delivering critical services. However, the introduction of redundant points of service raises a set of secondary issues that are addressed by distributed application designers. First, one must consider the manner in which the application leverages redundant resources so as to decrease the response time of a given service provider when this provider is under load. One must also consider the number of service points which will be sufficient to accommodate demand, as well as the physical locations at which these service points should be located.
Many prior art approaches make no attempt whatsoever to leverage redundant resources so as to decrease the response time of a given service provider under load. Instead, alternate service instances of a given resource are held in reserve and exist solely to provide fault-tolerant service provision. The primary advantage of this simplistic approach is that the backup instances of service have predictable levels of performance. However, this method is inefficient. Redundant resources which are idle are maintained and upgraded, but bring no benefit other than increasing the odds that a service can tolerate the failure of a given service provider.
Other prior art techniques do provide for the leverage of resources. One example of such a technique is known as “early binding”. Service requestors are statically assigned instances of service provision, which is advantages in that requests for service are spread across multiple instances of a given service provider. Service requests are then assigned to a specific instance of a service provider before invocation. Since requestors are “early-bound” to service provision, the method does not require the performance of successive iterations in an attempt to locate a suitable service provider. However, a major shortcoming of the “early binding” approach stems from the static binding that occurs between a request for service and the service provider. This method is not able to adjust to any shifts in the population or state of service providers. A failure in an individual instance of a service provider denies access of that service to the population of requestors it services. Moreover, the allocation of requests cannot respond to varying loads. If a community of service requestors is very active, the system does not spread the demands across all available providers. Only those providers statically bound to the requestors are used to process the workload created by the incoming requests.
Another existing technique for leveraging redundant resources is termed “late binding”. Service requestors are dynamically assigned to a given instance of a given service provider. The dynamic assignment of a service request to a service provider requires that the system decide which candidate service provider should process a given request. This decision is made by employing any of three strategies:
(i) Round Robin: incoming service requests are assigned to a list of candidate service providers by a dispatching entity. Selection of candidates is determined by the order of the candidates on the list. Each service provider receives a service request in turn.
(ii) Random Binding: similar to the Round Robin method, except that the list of candidate service providers has no particular order. Assignment of service provisions is drawn from the list of candidates at random.
(iii) Policy Driven: the dispatching entity examines incoming service requests and applies a set of policies that influence the dynamic assignment of requests to service providers.
The Round Robin and Random Binding strategies make the assignment of service requests to service providers using a blind algorithm. They do not take into consideration the demand or load on system resources. Policy-driven algorithms distribute service requests based on a set of rules. The system reports a set of “metrics” to a rule engine. The rule engine uses these metrics to make decisions regarding the allocation of system resources to satisfy service requests.
The problem with policy-based algorithms is that they create bottlenecks in the dispatching entity. The overhead associated with the gathering of data and the interpretation of that data is often intensely resource consuming. More importantly, because service providers require different sets of resources from different locations and in different ratios, the policies created for one class of service provision are not applicable to other service providers. Taken together, these factors result in a direct relationship between the complexity of the dispatching entity and the number of services being managed.
Prior art techniques have also been developed to determine the quantity of service points which are sufficient to accommodate demand. Distributed applications attempt to spread requests for service across a population of candidate service providers. In its simplest form, the response time for a provision of service ought to decrease as the population of service providers increases. Distributed application architects take a specification of maximum acceptable response time and an estimation of projected load, and then commission resources to meet that demand. They guess at the amount of resources they should assign to a given problem, and tune this estimate over time through observation.
The task of estimating and refining resource allocation estimates and bringing additional resources on-line (or off-line) is labor intensive. Moreover, each time the demand, resource, or priority profiles of a network change, the allocation of resources should be adjusted. The man-hours required to dynamically tune resources allocation in a distributed environment are prohibitive.
Pursuant to one common prior art approach, the management of access to system resources in a distributed environment may be conducted by ascertaining the rights and privileges of a service requestor at the time that a service request is received. If a requestor's privileges are sufficient to allow execution of the request for service provision, the request proceeds. Requestors with insufficient privileges are not granted access to a service. Using this approach, access to a system resource is binary: based upon the identity of the service provider, the request is either granted or not granted. Access privileges to system resources are typically defined and assigned by an administrator. The administrator grants these privileges to requesting entities in an effort to anticipate access requirements in advance of actual service requests. While this method of access control is well-suited to the provision of system security, it is deficient when applied to resource allocation. The assignment of privileges to regulate access to resources is essentially an effort to early-bind the set of resources to a service requestor. Such an assignment shares the same set of design deficits as the early binding technique described above.
As a consequence of the limitations of the foregoing resource allocation techniques, it has b
Kanevsky Paul
Pizi Anthony C.
Tsao Thomas
Tyler Daniel
Merrill Lynch, Co., Inc
Morgan & Lewis & Bockius, LLP
Robinson Greta L.
LandOfFree
Distributed adaptive computing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed adaptive computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed adaptive computing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2959191