Load balancing between service component instances

Details Load balancing between service component instances Load balancing between service component instances

1998-12-02

2002-08-27

Vincent, David (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S412000

Reexamination Certificate

active

06442165

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to load balancing. More particularly, the present invention relates to load balancing service requests between at least two service component instances associated with a network access point.
2. The Background
The proliferation of fixed price unlimited network access is one manifestation of the increasing demand for inexpensive network access to a resource rich communications system, such as the Internet. To keep their network access operations profitable, if not soluble, network access providers, such as ISPs (“Internet Service Providers”) must balance the needs of their subscribers with the cost of providing network access capacity that is sufficient to support those needs. However, sizing network access capacity is difficult to do because the demand for network access may vary continuously.
For example,
FIG. 1
is a block diagram of one possible implementation of an access point that has a network access request capacity dependent on the service components used by the access point. Access point
10
is shown in relation to a communications system
12
that uses a communications backbone
14
, such as the Internet. Access point
10
includes a client
16
and the necessary network connections to service components that provide the services required to properly process a network access request received by client
16
from a host
18
.
When host
18
sends a network access request to access point
10
, client
16
receives the request and processes the request according to the access methodology used by host
18
. For example, if host
18
relies on a dial-up methodology, client
16
responds to the network access request by requesting, among other things, the following services from its service components. First, client
16
will send a service request to a service component that provides authentication and authorization services, such as an AAA (Authentication, Authorization, and Accounting) server
20
. AAA server
20
will respond by determining whether the network access request received is authorized and respond with a reply, which indicates whether the request is authorized or unauthorized. Second, if client
16
receives a reply indicating that the network access request is authorized, client
16
then sends a request for an address to another service component, such as a DHCP (dynamic host configuration protocol) server
22
. Those of ordinary skill in the art will recognize that the address provided by a DHCP server
22
will be in the format of an IP address. Upon receiving the address, client
16
sends a reply packet having the address to host
18
, enabling host
18
to proceed within the log-on process using the address contained within the packet.
From the above example, providing the necessary processing required to support a network access request under a particular access methodology depends on the performance of the service components used. Thus, one solution is to size service components, i.e., build or provide service components that have high transaction rates, so as to maintain network access request processing levels at or above the level required by hosts seeking network access even during peak times. This approach is expensive because it provides a static solution to a problem that is dynamic in nature. By preparing for the worst case scenario, the solution builds in inefficiencies during off-peak periods and thus, results in an “over-built” and hence, more expensive than necessary network access point.
Building network access points which are less over-built, such as network access points that have sufficient resources for the average demand over a given period, may also be implemented but such an approach does not adequately provide for peak periods (such as the situation described above) or for periods which require less than the average number of resources.
Accordingly, a need exists for an apparatus which may be used in conjunction with components within a network access point to load balance the processing of network access requests using the services of at least two instances of a particular service component type, such as an AAA server.
Further, a need exists for an apparatus that may be used in conjunction with components within a network access point to load balance the processing of network access requests according to the measured performance of the instances used.
Further, a need exists for an apparatus that may be used in conjunction with components within a network access point to load balance the processing of network access requests between or among instances of a particular service component type without the need for receiving feedback from each instance used.
Furthermore, a need exists for an apparatus which may be used in conjunction with components within a network access point to load balance the processing of network access requests between or among instances while detecting inoperative and/or restarted instances.
SUMMARY OF THE INVENTION
Service requests, which are used to properly process a network access request received from a client, are processed by routing the service requests between at least two service component instances according to a load balancing algorithm. Load balancing includes: calculating a first ticket amount and a second ticket amount; assigning the first ticket amount to a first instance and the second ticket amount to a second instance; using a selection scheme to select an instance having a ticket amount greater than a threshold amount to process a service request; decrementing the ticket amount corresponding to the instance selected; and scheduling the instance selected to receive a service request.
The present invention may further include distinguishing between operable and inoperable instances during load balancing, providing ticket amounts that are not based on performance ratings to inoperable instances, and providing ticket amounts that are based on performance ratings to operable instances. For example, inoperable instances may each receive a ticket amount that is one increment above the threshold amount and operable instances may each receive a ticket amount that is based on the performance rating of each operable instance.


REFERENCES:
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 4933937 (1990-06-01), Konishi
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5317562 (1994-05-01), Nardin et al.
patent: 5359592 (1994-10-01), Corbalis et al.
patent: 5367517 (1994-11-01), Cidon et al.
patent: 5408472 (1995-04-01), Hluchyj et al.
patent: 5423002 (1995-06-01), Hart
patent: 5430715 (1995-07-01), Corbalis et al.
patent: 5502725 (1996-03-01), Pohjakallio
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5513172 (1996-04-01), Shikama et al.
patent: 5541957 (1996-07-01), Lau
patent: 5561663 (1996-10-01), Klausmeier
patent: 5570360 (1996-10-01), Klausmeier et al.
patent: 5570361 (1996-10-01), Norizuki et al.
patent: 5592470 (1997-01-01), Rudrapatna et al.
patent: 5594727 (1997-01-01), Kolbenson et al.
patent: 5594732 (1997-01-01), Bell et al.
patent: 5610910 (1997-03-01), Focsaneanu et al.
patent: 5666353 (1997-09-01), Klausmeier et al.
patent: 5699521 (1997-12-01), Iizuka et al.
patent: 5717604 (1998-02-01), Wiggins
patent: 5734654 (1998-03-01), Shirai et al.
patent: 5768521 (1998-06-01), Dedrick
patent: 5799040 (1998-08-01), Lau
patent: 5835494 (1998-11-01), Hughes et al.
patent: 5835727 (1998-11-01), Wong et al.
patent: 5926458 (1999-07-01), Yin
patent: 5953336 (1999-09-01), Moore et al.
patent: 6018770 (2000-01-01), Little et al.
patent: 6026440 (2000-02-01), Schrader et al.
patent: 6119160 (2000-09-01), Zhang et al.
patent: 6128279 (2000-10-01), O'Neil et al.
patent: 6198479 (2001-03-01), Humpleman et al.

Affiliated with

Also associated with

Rating

Load balancing between service component instances does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Load balancing between service component instances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load balancing between service component instances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2929141