draft-ietf-dhc-loadb-02.txt   draft-ietf-dhc-loadb-03.txt 
Network Working group DHC load balancing algorithm June 2000 Network Working group DHC Load Balancing Algorithm September 2000
Internet Draft Bernie Volz Internet Draft Bernie Volz
IPWorks, Inc. IPWorks, Inc.
Steve Gonczi Steve Gonczi
Network Engines, Inc. Network Engines, Inc.
Ted Lemon Ted Lemon
Internet Engines, Inc. Internet Engines, Inc.
Rob Stevens Rob Stevens
Join Systems, Inc. Join Systems, Inc.
June 2000 Expires Dec 2000 September 2000 Expires March 2001
DHC load balancing algorithm DHC Load Balancing Algorithm
<draft-ietf-dhc-loadb-02.txt> <draft-ietf-dhc-loadb-03.txt>
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with all This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. Internet-Drafts are working provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, and documents of the Internet Engineering Task Force (IETF), its areas, and
its working groups. Note that other groups may also distribute working its working groups. Note that other groups may also distribute working
documents as Internet Drafts. documents as Internet Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
skipping to change at page 1, line 47 skipping to change at page 1, line 47
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2000). All Rights Reserved. Copyright (C) The Internet Society (2000). All Rights Reserved.
Abstract Abstract
This draft proposes a method of algorithmic load balancing. It enables This draft proposes a method of algorithmic load balancing. It enables
multiple, cooperating servers to decide which one should service a multiple, cooperating servers to decide which one should service a
client, without exchanging any information beyond initial configuration. client, without exchanging any information beyond initial configuration.
The server selection is based on the servers hashing client MAC The server selection is based on the servers hashing client MAC
addresses, when multiple DHCP servers are available to service DHCP addresses when multiple DHCP servers are available to service DHCP
clients. The benefits are similar to those enumerated in [SSO-03], but clients. The proposed techique provides for efficient server selection
this draft does not require modifications to existing DHCP clients. The when multiple DHCP servers offer services on a network without requiring
same method is proposed to select the target server of a forwarding any changes to existing DHCP clients. The same method is proposed to
agent such as a BOOTP relay. select the target server of a forwarding agent such as a BOOTP relay.
1. Introduction 1. Introduction
This protocol was originally devised to support a specific load This protocol was originally devised to support a specific load
balancing optimization of the DHCP Failover Protocol [FAILOVR]. The balancing optimization of the DHCP Failover Protocol [FAILOVR]. The
authors later realized that it could be used to optimize the behavior of authors later realized that it could be used to optimize the behavior of
cooperating DHCP servers and the BOOTP relay agents that forward packets cooperating DHCP servers and the BOOTP relay agents that forward packets
to them. The proposal makes it possible to set up each participating to them. The proposal makes it possible to set up each participating
server to accept a preconfigured (approximate) percentage of the client server to accept a preconfigured (approximate) percentage of the client
load. This is done using a deterministic hashing algorithm, that could easily load. This is done using a deterministic hashing algorithm, that could
be applied to other protocols having similar characteristics. easily be applied to other protocols having similar characteristics.
2. Terminology 2. Terminology
This section discusses both the generic requirements terminology common This section discusses both the generic requirements terminology common
to many IETF protocol specifications, and also terminology introduced by to many IETF protocol specifications, and also terminology introduced by
this document. this document.
2.1. Requirements terminology 2.1. Requirements Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC 2119]. document are to be interpreted as described in RFC 2119 [RFC 2119].
2.2. Load balancing terminology 2.2. Load Balancing Terminology
This document introduces the following terms: This document introduces the following terms:
Service Delay, SD Service Delay, SD
A load balancing parameter, allowing delayed service of a client by a A load balancing parameter, allowing delayed service of a client by a
server participating in the load-balancing scheme, instead of server participating in the load-balancing scheme, instead of
ignoring the client. ignoring the client.
Hash Bucket Assignments, HBA Hash Bucket Assignments, HBA
A configuration directive that assigns a set of hash bucket values to A configuration directive that assigns a set of hash bucket values to
skipping to change at page 4, line 40 skipping to change at page 4, line 40
5.1 Configuration 5.1 Configuration
The configuration step consists of assigning hash values to available The configuration step consists of assigning hash values to available
servers. This is accomplished by providing one or more Hash Bucket servers. This is accomplished by providing one or more Hash Bucket
Assignments (HBA-s). These may come from a configuration file, the Assignments (HBA-s). These may come from a configuration file, the
Windows NT registry, EEPROM, etc. Alternatively, the hash bucket Windows NT registry, EEPROM, etc. Alternatively, the hash bucket
values could be assigned using some agreed upon algorithm. values could be assigned using some agreed upon algorithm.
E.g.:"Every odd value is serviced by server A and every even value E.g.:"Every odd value is serviced by server A and every even value
is serviced by serber B". is serviced by serber B".
5.2 HBA intended for a server 5.2 HBA Intended for a Server
When configuring one specific server, an HBA in the form of a simple bit When configuring one specific server, an HBA in the form of a simple bit
map of 32 octet values SHOULD be used. map of 32 octet values SHOULD be used.
The first octet in the HBA bitmap represents HBA values 0-7, the next The first octet in the HBA bitmap represents HBA values 0-7, the next
byte values 8-15, and so on, with the thirty-second octet representing byte values 8-15, and so on, with the thirty-second octet representing
values 248-255. In each octet, the least significant bit in that octet values 248-255. In each octet, the least significant bit in that octet
represents the smallest HBA value in that octet. represents the smallest HBA value in that octet.
Each bit of the HBA is associated with one possible hash value. If a bit Each bit of the HBA is associated with one possible hash value. If a bit
is set in the map, it means the recipient server MUST service each is set in the map, it means the recipient server MUST service each
client request, where the STID yields the corresponding hash value. client request, where the STID yields the corresponding hash value.
For example, if a server receives a HBA with the following 32 octets: For example, if a server is configured with an HBA of the following 32
octets:
FF FF FF FF FF FF 00 00 ( 0 - 63 ) FF FF FF FF FF FF 00 00 ( 0 - 63 )
FF FF FF FF FF FF FF FF ( 64 - 127 ) FF FF FF FF FF FF FF FF ( 64 - 127 )
00 00 00 00 00 00 00 00 (128 - 191 ) 00 00 00 00 00 00 00 00 (128 - 191 )
00 00 00 00 00 00 00 00 (192 - 255 ) 00 00 00 00 00 00 00 00 (192 - 255 )
then it MUST service any client requests where the STID hashes into the then it MUST service any client requests where the STID hashes into the
bucket values of 0 through 47 and 64 through 127. bucket values of 0 through 47 and 64 through 127.
The format of the option MUST be as follows when used with the DHCP 5.3 Delayed Service Parameter
Failover [FAILOVR] Protocol:
Code Len Hash Buckets
+-----+-----+-----+-----+----+-----+-----+-----+
| 0 | 11 | 0 | 32 | b1 | b2 | ... | b32 |
+-----+-----+-----+-----+----+-----+-----+-----+
The option code and length are 2 byte NBO values. The option number is
assigned in the option number space of [FAILOVR].
5.3 Delayed Service parameter
The Delayed Service parameter is optional. If it is not sent, the HBA
sets up a strict Serve/Do not serve policy.
If the parameter is used, it MUST be sent immediately before the HBA. The Delayed Service parameter is optional.
The server that is not supposed to serve a specific request (based on
the HBA, and the STID hash), is allowed to respond, after S seconds have
elapsed since the client first attempted to get service. A server MAY
use the secs field in the BOOTP header for determining the time since
the client has been trying to get service, or it MAY track repeated
requests some other way. If the parameter is used, its format MUST be as
follows:
Code Len Secs If the parameter is not configured, the HBA sets up a strict Serve/Do
+-----+-----+-----+-----+----+ not serve policy.
| 0 | 10 | 0 | 1 | S |
+-----+-----+-----+-----+----+
The option code and length are 2 byte NBO values. The option number is If the parameter is configured, the server that is not supposed to serve
assigned in the option number space of [FAILOVR]. S is a one byte value, a specific request (based on the HBA and the STID hash), is allowed to
1..255. It represents the number of seconds to delay service. The server respond, after S seconds have elapsed since the client first attempted
MAY serve a client after S seconds elapsed from the client's first to get service. A server MAY use the secs field in the BOOTP header for
request, even if the HBA and STID hash indicate the server should not determining the time since the client has been trying to get service,
respond. or it MAY track repeated requests some other way.
5.4 HBA intended for a forwarder 5.4 HBA Intended for a Forwarder
When configuring a forwarding agent, (e.g.: BOOTP relay) HBA-s When configuring a forwarding agent, (e.g.: BOOTP relay) HBA-s
consisting of pairs of Server-ID / Hash Bucket values MAY be used. consisting of pairs of Server-ID / Hash Bucket values MAY be used.
Here, the Server ID (SID) designates the server responsible for the Here, the Server ID (SID) designates the server responsible for the
specified Hash Bucket. The forwarding agent forwards each client specified Hash Bucket. The forwarding agent forwards each client
request, where the STID yields the specified hash value, to the server request, where the STID yields the specified hash value, to the server
designated by the SID. designated by the SID.
The Server ID may be any unique server attribute, (E.g.: IP address, DNS The Server ID may be any unique server attribute, (E.g.: IP address, DNS
skipping to change at page 6, line 42 skipping to change at page 6, line 21
192.33.43.16: 129 130 131 200..202; 192.33.43.16: 129 130 131 200..202;
The above configuration consists of 4 HBA-s. The first HBA example The above configuration consists of 4 HBA-s. The first HBA example
reads: "Any Client request, where the STID yields a hash value 0 to 24, reads: "Any Client request, where the STID yields a hash value 0 to 24,
will be forwarded to both server 192.33.43.11 and 192.33.43.12". will be forwarded to both server 192.33.43.11 and 192.33.43.12".
The 4th HBA example states: "Any Client request, where the STID yields a The 4th HBA example states: "Any Client request, where the STID yields a
hash value 129,139,131,200,201 or 202, will be forwarded to server hash value 129,139,131,200,201 or 202, will be forwarded to server
192.33.43.16. 192.33.43.16.
6. Hash function for load balancing 6. Hash Function for Load Balancing
The following hash function is a C language implementation of the The following hash function is a C language implementation of the
algorithm known as "Pearson's hash". The Pearson's hash algorithm was algorithm known as "Pearson's hash". The Pearson's hash algorithm was
originally published in [PEARSON]. originally published in [PEARSON].
The hash function is computationally inexpensive, requires an The hash function is computationally inexpensive, requires an array
array lookup and xor operation for each key byte. To make this proposal lookup and xor operation for each key byte. To make this proposal work,
work, all interoperable implementations MUST use this hash function, all interoperable implementations MUST use this hash function, with the
with the set of mixing table values given below: set of mixing table values given below:
/* A "mixing table" of 256 distinct values, in pseudo-random order. */ /* A "mixing table" of 256 distinct values, in pseudo-random order. */
unsigned char loadb_mx_tbl[256] ={ unsigned char loadb_mx_tbl[256] ={
251, 175, 119, 215, 81, 14, 79, 191, 103, 49, 181, 143, 186, 157, 0, 251, 175, 119, 215, 81, 14, 79, 191, 103, 49, 181, 143, 186, 157, 0,
232, 31, 32, 55, 60, 152, 58, 17, 237, 174, 70, 160, 144, 220, 90, 57, 232, 31, 32, 55, 60, 152, 58, 17, 237, 174, 70, 160, 144, 220, 90, 57,
223, 59, 3, 18, 140, 111, 166, 203, 196, 134, 243, 124, 95, 222, 179, 223, 59, 3, 18, 140, 111, 166, 203, 196, 134, 243, 124, 95, 222, 179,
197, 65, 180, 48, 36, 15, 107, 46, 233, 130, 165, 30, 123, 161, 209, 23, 197, 65, 180, 48, 36, 15, 107, 46, 233, 130, 165, 30, 123, 161, 209, 23,
97, 16, 40, 91, 219, 61, 100, 10, 210, 109, 250, 127, 22, 138, 29, 108, 97, 16, 40, 91, 219, 61, 100, 10, 210, 109, 250, 127, 22, 138, 29, 108,
244, 67, 207, 9, 178, 204, 74, 98, 126, 249, 167, 116, 34, 77, 193, 244, 67, 207, 9, 178, 204, 74, 98, 126, 249, 167, 116, 34, 77, 193,
skipping to change at page 7, line 39 skipping to change at page 7, line 39
{ {
unsigned char hash = len; unsigned char hash = len;
int i; int i;
for (i=len ; i > 0 ; ) for (i=len ; i > 0 ; )
hash = loadb_mx_tbl [ hash ^ key[ --i ] ]; hash = loadb_mx_tbl [ hash ^ key[ --i ] ];
return( hash ); return( hash );
} }
An example of how to check if we should service a transaction: An example of how to check if a server should service a transaction:
int accept_service_request( int accept_service_request(
const unsigned char HBA[32], /* The hash bucket bitmap */ const unsigned char HBA[32], /* The hash bucket bitmap */
const unsigned char key, /* The service transaction id */ const unsigned char key, /* The service transaction id */
const int len ) /* length of the above */ ) const int len ) /* length of the above */ )
{ {
unsigned char hash = loadb_p_hash(key,len); unsigned char hash = loadb_p_hash(key,len);
int index = (hash >> 3) & 31; int index = (hash >> 3) & 31;
int bitmask = 1 << (hash & 7); int bitmask = 1 << (hash & 7);
skipping to change at page 8, line 17 skipping to change at page 8, line 17
This proposal in and by itself provides no security, nor does it impact This proposal in and by itself provides no security, nor does it impact
existing security. Servers using this algorithm are responsible for existing security. Servers using this algorithm are responsible for
ensuring that if the contents of the HBA are transmitted over the ensuring that if the contents of the HBA are transmitted over the
network as part of the process of configuring any server, that message network as part of the process of configuring any server, that message
be secured against tampering, since tampering with the HBA could result be secured against tampering, since tampering with the HBA could result
in denial of service for some or all clients. in denial of service for some or all clients.
8. References 8. References
[FAILOVR] Kinnear, K,, Droms, R., Rabil, G., Dooley, M., Kapur, A., [FAILOVR] Kinnear, K,, Droms, R., Rabil, G., Dooley, M., Kapur, A.,
Gonczi, S., Volz, B., "DHCP Failover Protocol", Internet Gonczi, S., Volz, B., "DHCP Failover Protocol", Work in
Draft <draft-ietf-dhc-failover-07.txt>, June 2000. Progress.
[PEARSON] The Communications of the ACM Vol.33, No. 6 (June 1990), [PEARSON] The Communications of the ACM Vol.33, No. 6 (June 1990),
pp. 677-680. pp. 677-680.
[RFC2131] R. Droms, "Dynamic Host Configuration Protocol", RFC2131, [RFC2131] R. Droms, "Dynamic Host Configuration Protocol", RFC2131,
March 1997. March 1997.
[RFC2219] Bradner, S., "Key words for use in RFCs to Indicate [RFC2219] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels," RFC-2219, March 1997. Requirement Levels," RFC-2219, March 1997.
[SSO-03] Stump, G., Gupta, P., Droms, R. Sommerfeld, R.
"The Server Selection Option for DHCP"
<draft-ietf-dhc-sso-03.txt>
9. Acknowledgements 9. Acknowledgements
Special thanks to Peter K. Pearson, the author of Pearson's hash who has Special thanks to Peter K. Pearson, the author of Pearson's hash who has
kindly granted his permission to use his algorithm, free of any kindly granted his permission to use his algorithm, free of any
encumbrances. encumbrances.
This proposal stems from the original idea of hashing MAC addresses to a This proposal stems from the original idea of hashing MAC addresses to a
single bit by Ted Lemon, during a Failover Protocol discussion held at single bit by Ted Lemon, during a Failover Protocol discussion held at
CISCO Systems in February, 1999. Rob Stevens suggested the potential use CISCO Systems in February, 1999. Rob Stevens suggested the potential use
of this algorithm for purposes beyond those of the Failover Protocol. of this algorithm for purposes beyond those of the Failover Protocol.
 End of changes. 

This html diff was produced by rfcdiff 1.25, available from http://www.levkowetz.com/ietf/tools/rfcdiff/