idnits 2.17.1 draft-gonczi-dhc-loadb-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 3 longer pages, the longest (page 7) being 76 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 8 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 5 instances of too long lines in the document, the longest one being 4 characters in excess of 72. ** There are 7 instances of lines with control characters in the document. == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 270 has weird spacing: '...'s hash algor...' == Line 375 has weird spacing: '...for the purpo...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (Apr 2000) is 8770 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC 2119' is mentioned on line 87, but not defined -- Looks like a reference, but probably isn't: '256' on line 277 == Unused Reference: 'RFC2131' is defined on line 340, but no explicit reference was found in the text == Unused Reference: 'RFC2219' is defined on line 343, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'FAILOVR' -- Possible downref: Non-RFC (?) normative reference: ref. 'PEARSON' Summary: 6 errors (**), 0 flaws (~~), 10 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Draft Bernie Volz 2 Steve Gonczi 3 Process Software 5 Ted Lemon 6 Internet Engines, Inc. 8 Rob Stevens 9 Join Systems, Inc. 11 October 1999 Expires Apr 2000 13 DHC load balancing algorithm 14 16 Status of this Memo 18 This document is an Internet-Draft and is in full conformance with 19 all provisions of Section 10 of RFC2026. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html. 37 Copyright Notice 39 Copyright (C) The Internet Society (1999). All Rights Reserved. 41 Abstract 43 This draft proposes a method of algorithmic load balancing 44 that enables multiple, cooperating servers to decide which one 45 should service a client, without requiring participating servers 46 to exchange information. 48 It proposes a computable server selection mechanism for the 49 DHCP or DHC Failover Protocol. 51 In addition, it provides for the use of the same mechanism 52 to govern the target server selection of a forwarding agent 53 such as a BOOTP relay. 55 1. Introduction 57 This protocol was originally devised to support a specific load 58 balancing optimization of the DHC Failover Protocol [FAILOVR]. 60 The authors later realized that it could be used to optimize the 61 behavior of cooperating DHCP servers and the BOOTP relay agents that 62 forward packets to them. 64 This proposal makes it possible to set up each participating server to 65 accept a preconfigured (approximate) percentage of the client load. 66 This is done using a deterministic hashing algorithm, and 67 assumes that the hash will produce an even distribution of values 68 based on client load. Whether the distribution is in fact even for 69 any given set of clients is dependent on the clients, but the hash is 70 expected to produce reasonably evenly distributed output in all cases. 72 This algorithm could easily be applied to other protocols that 73 have similar characteristics and for which load balancing would be 74 helpful. 76 2. Terminology 78 This section discusses both the generic requirements terminology 79 common to many IETF protocol specifications, and also terminology 80 introduced by this document. 82 2.1. Requirements terminology 84 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 85 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 86 document are to be interpreted as described in RFC 2119 [RFC 2119]. 88 2.2. Load balancing terminology 90 This document introduces the following terms: 92 Hash Bucket Assignments, HBA 93 A configuration directive that assigns a set of hash bucket values to 94 a server participating in the load balancing scheme. 96 Server ID, SID 97 An identifier that can be used to designate one of the participating 98 servers in the context of another protocol implementing this proposal. 99 In the context of DHCP, this SHOULD be the IP address or DNS name 100 of the server. 102 Service Transaction, ST 103 A set of client-server exchanges that lead to a server 104 providing or denying some service to a client. 105 Example: the DISCOVER/OFFER/REQUEST/ACK message exchange 106 between a DHCP server and client is a service transaction. 107 A service transaction may contain one or more messages. 109 Service Transaction ID, STID 110 An attribute of the individual client requests used for load balancing. 111 Deciding which attribute to use is entirely up to the specific 112 implementation. 114 3. Background and External Requirements 116 Because DHCP clients use UDP broadcast to contact DHCP servers, a client 117 DHCPDISCOVER message may be received by more than one server. All 118 servers receiving such a broadcast may respond to the client, letting 119 the client choose which server it will use. 121 When a BOOTP relay agent is used, it typically forwards or rebroadcasts 122 client broadcasts to all configured servers, so a similar inefficiency 123 is present. 125 The optimization described allows a server to be chosen for each 126 such transaction by performing a "serve" / "do not serve" computation. 127 A forwarding agent can perform the same computation to choose a 128 forwarding destination. 130 In either case, the choice of server can be computed, without the 131 participants having to negotiate who is to respond. 133 Each client request MUST have some hashable property that varies from 134 ST to ST, though it is not required that the attribute values should be 135 unique for each ST. The selected attribute MUST have the same value for 136 each message making up a multi-message ST. 138 The approach is probabilistic in nature, because it is nearly impossible 139 to foresee which client will request service next. For short periods 140 of time, the actual percentage of clients served by a given server 141 will likely deviate from the desired percentage. As the number of 142 requests grows, the actual percentage of the load being handled by 143 each server will approximate the configured percentage. 145 4. Overview 147 The specific implementation MUST choose an ST attribute that will 148 be used as the ST "key" for load balancing. 150 DHCP servers MUST use the Client Identifier option as the STID if it 151 is present. If no Client Identifier option is present, the hlen 152 field of the DHCP packet should be used as the length of the data to 153 be hashed, and the contents of the chaddr should be the data to be 154 hashed, except that in no event should more than sixteen bytes be 155 used. 157 Other implementations MAY choose other attribute(s) as their STID. 159 The proposal maps the chosen STID into a hash value using the 160 function in section 6. The resulting hash value can then be used 161 to decide who should respond to the request, or who the forwarding 162 target should be. 164 The provided hash function generates hash values 0 to 255, 165 and yields a fairly even hash bucket distribution for random STIDs, and 166 also for STID sequences that have some pattern. 168 Resource allocation is accomplished by assigning specific hash 169 values to each participating server. 171 Each server is assigned ownership of one or more hash values, 172 and will only service requests where the STID hash matches one 173 of these values. 175 Any hash buckets not assigned to servers will result 176 in some client ST-s being entirely ignored. (In some scenarios, 177 this may be the desired outcome.) STID-s need not be unique, but 178 should have sufficient variety to exercise each hash value 179 assigned to any server. 181 5. Operation 183 5.1 Configuration 185 The configuration step consists of assigning hash values 186 to available servers. This is accomplished by providing one 187 or more Hash Bucket Assignments (HBAs). (These may come from 188 a configuration file, the Windows NT registry, EEPROM, etc.) 190 Alternatively, HBAs can be transmitted as messages, 191 encapsulated in messages of another protocol, for example using 192 e-mail, a DHC Failover Protocol option, or some other mechanism. 194 5.2 HBA intended for a participant server 196 When configuring one specific server, an HBA in the form of a 197 simple bit map of 32 octet values MAY be used. If the HBA is 198 represented in this form, the first octet in the HBA bitmap will 199 represent HBA values 0-7, the next byte values 8-15, and so on, 200 with the thirty-second octet representing values 248-255. 201 In each octet, the most significant bit in that octet represents 202 the largest HBA value represented in that octet. 203 So for example bit 7 of the first octet represents HBA value 7, and 204 bit 0 of the first octet represents HBA value 0. 206 Each bit of the HBA is associated with one possible hash 207 value. If a bit is set in the map, it means the recipient server 208 MUST service each client request, where the STID yields the 209 corresponding hash value. 211 For example, if a server receives a HBA 212 with the following 32 octets: 213 buckets 214 FF FF FF FF FF FF FF FF ( 0 - 63 ) 215 FF FF FF FF FF FF FF FF ( 64 - 127 ) 216 00 00 00 00 00 00 00 00 ( 128 - 191 ) 217 00 00 00 00 00 00 00 00 ( 192 - 255 ) 219 then it MUST service any client requests where the STID 220 hashes into the bucket values of 0 through 127. 222 The above example is merely for illustration 223 purposes. An application implementing this algorithm is free 224 to choose a different format, as long as the server is informed 225 in some way of hash bucket values it owns. 227 5.3 HBA intended for a forwarder 229 When configuring a forwarding agent, (e.g.: BOOTP relay) 230 HBAs consisting of pairs of Server-ID / Hash Bucket values 231 MAY be used. 233 Here, the Server ID (SID) designates the server responsible for 234 the specified Hash Bucket. The forwarding agent 235 forwards each client request, where the STID yields the 236 specified hash value, to the server designated by the SID. 238 The Server ID may be any unique server attribute, 239 (E.g.: IP address, DNS name, etc) that is meaningful in the context of 240 the relay agent operation. 242 A forwarder may be configured to forward a packet to 243 more than one server. For example, a BOOTP relay could be 244 set up to split the load between 2 primary-backup server pairs, 245 running the DHC Failover Protocol [FAILOVR]. 247 A possible configuration file for a forwarding agent 248 (e.g.: BOOTP relay) may look like this: 250 192.33.43.11 0 .. 24; 251 192.33.43.12 25 .. 55; 252 192.33.43.13 56 ..128; 253 192.33.43.14 129..255; 254 192.33.43.15 129..255; 256 The above configuration consists of 5 HBAs. The first HBA states: 257 "Any Client request, where the STID yields a hash value 258 0 to 24, will be forwarded to server 192.33.43.11". 259 Note that that HBA #4 and #5 instruct to forward the same requests 260 to both 192.33.43.142 and 192.33.43.14. 262 The above example is merely for illustration purposes. An implementing 263 application is free to choose a different format, as long as the 264 forwarding agent is given a list of SIDs, with the set of hash bucket 265 values each server owns. 267 6. Hash function for load balancing 269 The following hash function is a c language implementation of the 270 algorithm known as "Pearson's hash". The Pearson's hash algorithm 271 was originally published in [PEARSON] 273 To make this proposal work, all interoperable implementations 274 MUST use the same hash function. 276 /* A "mixing table" of 256 distinct values, in pseudo-random order. */ 277 unsigned char loadb_mx_tbl[256] = 278 { 279 251, 175, 119, 215, 81, 14, 79, 191, 103, 49, 280 181, 143, 186, 157, 0, 232, 31, 32, 55, 60, 281 152, 58, 17, 237, 174, 70, 160, 144, 220, 90, 282 57, 223, 59, 3, 18, 140, 111, 166, 203, 196, 283 134, 243, 124, 95, 222, 179, 197, 65, 180, 48, 284 36, 15, 107, 46, 233, 130, 165, 30, 123, 161, 285 209, 23, 97, 16, 40, 91, 219, 61, 100, 10, 286 210, 109, 250, 127, 22, 138, 29, 108, 244, 67, 287 207, 9, 178, 204, 74, 98, 126, 249, 167, 116, 288 34, 77, 193, 200, 121, 5, 20, 113, 71, 35, 289 128, 13, 182, 94, 25, 226, 227, 199, 75, 27, 290 41, 245, 230, 224, 43, 225, 177, 26, 155, 150, 291 212, 142, 218, 115, 241, 73, 88, 105, 39, 114, 292 62, 255, 192, 201, 145, 214, 168, 158, 221, 148, 293 154, 122, 12, 84, 82, 163, 44, 139, 228, 236, 294 205, 242, 217, 11, 187, 146, 159, 64, 86, 239, 295 195, 42, 106, 198, 118, 112, 184, 172, 87, 2, 296 173, 117, 176, 229, 247, 253, 137, 185, 99, 164, 297 102, 147, 45, 66, 231, 52, 141, 211, 194, 206, 298 246, 238, 56, 110, 78, 248, 63, 240, 189, 93, 299 92, 51, 53, 183, 19, 171, 72, 50, 33, 104, 300 101, 69, 8, 252, 83, 120, 76, 135, 85, 54, 301 202, 125, 188, 213, 96, 235, 136, 208, 162, 129, 302 190, 132, 156, 38, 47, 1, 7, 254, 24, 4, 303 216, 131, 89, 21, 28, 133, 37, 153, 149, 80, 304 170, 68, 6, 169, 234, 151 305 }; 307 unsigned char loadb_p_hash( unsigned char *key,/* The key to be hashed */ 308 int len) /* Length of key in bytes*/ 309 { 310 unsigned char hash = len; 311 int i; 313 for( i=len ; i > 0 ; ) 314 { 315 hash = loadb_mx_tbl [ hash ^ key[ --i ] ]; 316 } 317 return( hash ); 318 } 320 7. Security 322 This proposal in and by itself provides no security, nor does 323 it impact existing security. 325 Servers using this algorithm are responsible for ensuring that if 326 the contents of the HBA are transmitted over the network as part of 327 the process of configuring any server, that message be secured 328 against tampering, since tampering with the HBA could result in 329 denial of service for some or all clients. 331 8. References 333 [FAILOVR] Droms, R., Rabil, G., Dooley, M., Kapur, A., Gonczi, S., 334 Volz, B., "DHCP Failover Protocol", Internet Draft 335 , June 1999. 337 [PEARSON] The Communications of the ACM Vol.33, No. 6 (June 1990), 338 pp. 677-680. 340 [RFC2131] R. Droms, "Dynamic Host Configuration Protocol", RFC2131, 341 March 1997. 343 [RFC2219] Bradner, S., "Key words for use in RFCs to Indicate Requirement 344 Levels," RFC-2219, March 1997. 346 9. Acknowledgements 348 Special thanks to Peter K. Pearson, the author of Pearson's hash 349 who has kindly granted his permission to use this algorithm, 350 free of any encumbrances. 352 This proposal stems from the original idea of hashing MAC addresses 353 to a single bit by Ted Lemon, during a Failover Protocol discussion 354 held at CISCO Systems in February, 1999. 356 Rob Stevens suggested the potential use of this algorithm for 357 purposes beyond the Failover Protocol. 359 Many thanks to Ralph Droms, Kim Kinnear, Mark Stapp, Glenn Waters, 360 Greg Rabil and Jack Wong for their comments during the 361 ongoing discussions. 363 10. Full Copyright Statement 365 Copyright (C) The Internet Society (1999). All Rights Reserved. 367 This document and translations of it may be copied and furnished to 368 others, and derivative works that comment on or otherwise explain it or 369 assist in its implementation may be prepared, copied, published and 370 distributed, in whole or in part, without restriction of any kind, 371 provided that the above copyright notice and this paragraph are included 372 on all such copies and derivative works. However, this document itself 373 may not be modified in any way, such as by removing the copyright notice 374 or references to the Internet Society or other Internet organizations, 375 except as needed for the purpose of developing Internet standards in 376 which case the procedures for copyrights defined in the Internet 377 Standards process must be followed, or as required to translate it 378 into languages other than English. 380 The limited permissions granted above are perpetual and will not be 381 revoked by the Internet Society or its successors or assigns. 383 This document and the information contained herein is provided on an "AS 384 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 385 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 386 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT 387 INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 388 FITNESS FOR A PARTICULAR PURPOSE. 390 11. Author's information 392 Bernie Volz 393 Steve Gonczi 394 Process Software Corporation 395 959 Concord St. 396 Framingham, MA 01701 397 Phone: (508) 879-6994 398 EMail: volz@process.com 399 gonczi@process.com 401 Ted Lemon 402 Internet Engines, Inc. 403 950 Charter Street 404 Redwood City, CA 94063 405 Phone: (650) 779 6031 406 EMail: mellon@isc.org 408 Rob Stevens 409 Join Systems, Inc. 410 1032 Elwell Ct Ste 243 411 Palo Alto CA 94203 412 Phone: (650)-968-4470 413 EMail: robs@join.com