rfc3074.txt

最新的RFC


RFC 3074              DHC Load Balancing Algorithm         February 2001


   The Server ID may be any unique server attribute, (e.g., IP address,
   DNS name, etc.) that is meaningful in the context of the relay agent
   operation.

   A forwarder may be configured to forward a given packet to more than
   one server.  For example, a BOOTP relay could be set up to split the
   load between 2 primary-backup server pairs, each pair running the
   DHCP Failover Protocol [FAILOVR].  In this case, a packet that is
   intended for a server pair Will have to be forwarded to both the
   primary, and the secondary server of the pair.

   A possible configuration file for a forwarding agent (e.g., BOOTP
   relay) may look like this:

   192.33.43.11 192.33.43.12: 0..24;
   192.33.43.13:  25..55;
   192.33.43.15:  56..128;
   192.33.43.16: 129 130 131 200..202;

   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, 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 hash value 129,139,131,200,201 or 202, will be forwarded to
   server 192.33.43.16.

6.  Hash Function for Load Balancing

   The following hash function is a C language implementation of the
   algorithm known as "Pearson's hash".  The Pearson's hash algorithm
   was originally published in [PEARSON].

   The hash function is computationally inexpensive, requires an array
   lookup and xor operation for each key byte.  To make this proposal
   work, all interoperable implementations MUST use this hash function,
   with the set of mixing table values given below:

/* A "mixing table" of 256 distinct values, in pseudo-random order. */

unsigned char  loadb_mx_tbl[256] ={
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,
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,
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,
200, 121,  5, 20, 113, 71, 35, 128, 13, 182, 94, 25, 226, 227, 199, 75,



Volz, et al.                Standards Track                     [Page 6]

RFC 3074              DHC Load Balancing Algorithm         February 2001


27, 41, 245, 230, 224, 43, 225, 177, 26, 155, 150, 212, 142, 218, 115,
241, 73, 88, 105, 39, 114, 62, 255, 192, 201, 145, 214, 168, 158, 221,
148, 154, 122, 12, 84, 82, 163, 44, 139, 228, 236, 205, 242, 217, 11,
187, 146, 159, 64, 86, 239, 195, 42, 106, 198, 118, 112, 184, 172, 87,
2, 173, 117, 176, 229, 247, 253, 137, 185, 99, 164, 102, 147, 45, 66,
231, 52, 141, 211, 194, 206, 246, 238, 56, 110, 78, 248, 63, 240, 189,
93, 92, 51, 53, 183, 19, 171, 72, 50, 33, 104, 101, 69, 8, 252, 83, 120,
76, 135, 85, 54, 202, 125, 188, 213, 96, 235, 136, 208, 162, 129, 190,
132, 156, 38, 47, 1, 7, 254, 24, 4, 216, 131, 89, 21, 28, 133, 37, 153,
149, 80, 170, 68, 6, 169, 234, 151
};

unsigned char loadb_p_hash(
        const unsigned char *key,       /* The key to be hashed */
        const int len )                 /* Key length in bytes  */
{
unsigned char hash  = len;
int i;

        for (i=len ; i > 0 ;  )
            hash = loadb_mx_tbl  [ hash ^ key[ --i ] ];

        return( hash );
}

int accept_service_request(
        const unsigned char HBA[32],    /* The hash bucket bitmap */
        const unsigned char *key,       /* The service transaction id
*/
        const int len  )                /* length of the above */
{
unsigned char hash = loadb_p_hash(key,len);
int index          = (hash >> 3) & 31;
int bitmask        = 1 << (hash & 7);

        /* return 1 if we should service this transaction */
        return((HBA[index] & bitmask) != 0);
}

7.  Security Considerations

   This proposal in and by itself provides no security, nor does it
   impact existing security.  Servers using this algorithm are
   responsible for ensuring that if the contents of the HBA are
   transmitted over the network as part of the process of configuring
   any server, that message be secured against tampering, since
   tampering with the HBA could result in denial of service for some or
   all clients.



Volz, et al.                Standards Track                     [Page 7]

RFC 3074              DHC Load Balancing Algorithm         February 2001


8.  References

   [FAILOVR]  Kinnear, K,, Droms, R., Rabil, G., Dooley, M., Kapur, A.,
              Gonczi, S. and B. Volz, "DHCP Failover Protocol", Work in
              Progress.

   [PEARSON]  The Communications of the ACM  Vol.33, No.  6 (June 1990),
              pp. 677-680.

   [RFC2131]  Droms, R., "Dynamic Host Configuration Protocol", RFC
              2131, March 1997.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels," BCP 14, RFC 2119, March 1997.

9.  Acknowledgements

   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
   encumbrances.

   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 CISCO Systems in February, 1999.  Rob Stevens suggested the
   potential use of this algorithm for purposes beyond those of the
   Failover Protocol.

   Many thanks to Ralph Droms, Kim Kinnear, Mark Stapp, Glenn Waters,
   Greg Rabil and Jack Wong for their comments during the ongoing
   discussions.





















Volz, et al.                Standards Track                     [Page 8]

RFC 3074              DHC Load Balancing Algorithm         February 2001


10.  Authors' Addresses

   Bernie Volz
   Ericsson
   959 Concord Street
   Framingham, MA  01701

   Phone: [phone]
   EMail: [e-mail]


   Steve Gonczi
   Network Engines, Inc.
   25 Dan Road Canton, MA 02021-2817

   Phone: [phone]
   EMail: [e-mail]


   Ted Lemon
   950 Charter Street
   Redwood City, CA 94043

   EMail: [e-mail]


   Rob Stevens
   Join Systems, Inc.
   1032 Elwell Ct Ste 243 Palo Alto CA 94203

   Phone: [phone]
   EMail: [e-mail]



















Volz, et al.                Standards Track                     [Page 9]

RFC 3074              DHC Load Balancing Algorithm         February 2001


11.  Full Copyright Statement

   Copyright (C) The Internet Society (2001).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.



















Volz, et al.                Standards Track                    [Page 10]