組織：中國互動出版網（http://www.china-pub.com/）
RFC文檔中文翻譯計劃（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
譯者：徐永久（albertxu    albertxu@bigfoot.com）
譯文發布時間：2001-3-27
版權：本中文翻譯文檔版權歸中國互動出版網所有?？梢杂糜诜巧虡I用途自由轉載，但必須保留本文檔的翻譯及版權信息。



Network Working Group                                   B. Volz
Request for Comments: 3074                             Ericsson 
Category: Standards Track                              S. Gonczi   
              Network Engines,Inc.                                                             T. Lemon
                                           Internet Engines, Inc.
                                                      R. Stevens
                                               Join Systems, Inc.
February 2001

DHCP 負載平衡算法 

本備忘錄的狀態
本文檔講述了一種Internet社區的Internet標準跟蹤協議，它需要進一步進行討論和建議以得到改進。請參考最新版的“Internet正式協議標準” (STD1)來獲得本協議的標準化程度和狀態。本備忘錄的發布不受任何限制。
版權聲明
Copyright (C) The Internet Society (2001).

摘要
本文檔建議了一種負載平衡算法，它讓多個合作的服務器決定哪一個來為客戶服務，而不必在初始設置時作任何信息交換。
當存在多個DHCP 服務器時，根據服務器端散列存儲的客戶MAC 地址來選擇服務器。建議的技術提供了高效選擇服務器的手段，當網絡上存在多個DHCP 服務器時，不需要改變客戶端的設置。對于選擇目標服務器作為轉向代理，例如 BOOTP 中繼也采用同樣的方法。
目錄
1.  介紹	2
2. 術語	2
2.1.  要求的術語	2
2.2. 負載平衡術語	2
3.  背景知識和外部需求	3
4. 概覽	3
5. 操作	4
5.1 設置	4
5.2 面向服務器的 HBA	4
5.3 延遲服務參數	4
5.4 轉向 HBA	4
6.  負載平衡的散列函數	5
7.  安全考慮	6
參考	6
鳴謝	7
作者地址：	7
版權聲明	8
致謝	8

1.  介紹
本協議最初用來支持對特定的 DHCP 失敗請求協議的負載平衡優化。作者后來意識到可以用來優化多個合作的 DHCP 服務和 BOOTP 中繼代理。本建議可以設置每個參與的服務器接受一個預先設置的客戶負載百分比。這可以通過確定性的散列算法來達到，對于具有同樣特性的其他協議也能很容易的做到。
2. 術語
本節既討論了 IETF 協議指定的一般性術語，也討論了本文檔要用到的一些術語。 
2.1.  要求的術語
本文中的關鍵字“必須”，“必須不”，“要求的”，“應該”，“不應該”，“會”，“不會”，“建議”，“或許”，“可選的”在 RFC 2119 中解釋。   
2.2. 負載平衡術語
本文檔介紹了以下術語：
    服務延遲 （Service Delay）, SD
參加負載平衡方案中的服務器允許對客戶機延遲服務，而不是忽略客戶請求。
散列桶分配 （Hash Bucket Assignments）, HBA
參加負載平衡方案服務器的配置節名稱，設置散列桶的大小。
服務器 ID （Server ID）, SID
對參與的服務器指定 ID 。從 DHCP 的行文來說， SID 就是指服務器的 IP 地址或者 DNS 名字。
服務事務 (Service Transaction) , ST
客戶機和服務器之間信息交換的集合，例如 DHCP 服務器和客戶機之間 DISCOVER/OFFER/REQUEST/ACK 信息的交換就是一種服務事務。
服務事務 ID (Service Transaction ID), STID
負載平衡中單個客戶請求屬性。
3.  背景知識和外部需求
因為 DHCP 客戶機采用 UDP 廣播來聯系 DHCP 服務器，因此，客戶機的   DHCPDISCOVER 消息可以被多臺服務器接收到。所有接收到這條廣播的服務器會 對客戶機作出響應，來讓客戶機決定采用哪一臺服務器。
如果使用了 BOOTP 中繼代理，一般它會轉發或者向所有配置的服務器重新廣播客戶機的請求，因此也存在同樣低效的問題。
優化算法允許服務器采用計算“服務”和“不服務”的比例來讓每一個事務選擇。轉發代理也可以采用同樣的計算方法選擇轉發目的地。
在每一種例子中，對服務器的選擇是可計算的，而不必要求參與者協商誰來響應。
因為幾乎不能預測下一個請求會來自哪一臺客戶機，所以該算法逼近自然界的概率。對短期而言，實際的客戶機得到的請求百分比會偏離期望的百分比，但是隨著請求次數的增加，每一臺服務器的負載百分比就會達到配置的百分比。
4. 概覽
DHCP 服務器必須使用客戶機標記選項作為 STID ，如果沒有客戶機標記的話，   DHCP 包的 hlen 域 必須使用要散列的數據長度，而 chaddr 的內容必須為要散列的數據。最多用到客戶端標記或者 chaddr 的最初 16 字節。
本建議把 STID 映射為第6節中函數用到的散列值。返回的散列值就能用來決定誰能響應客戶機的請求，或者誰是轉發目標。
提供的散列函數產生0 到 255 的散列值，產生相當平坦的散列桶分布，對于每一個參與的服務器，通過分配指定的散列值來分配資源。
服務器僅當那些請求機器的 STID 匹配分配的散列值中的一個時才會接受請求。
任何沒有對服務器分配的散列桶會導致一些客戶的 ST 完全被忽略。 STID 并非一定要唯一，但是必須有足夠余量能分布到每一臺服務器。
HBA 可以以消息傳送，封包在其他協議中，例如：e-mail 或者 DHCP Failover    協議。
DHCP 服務器實現可以采取可配置的策略，來處理負載平衡已經配置好，但是服務器不能響應或者不符合預定的分配地址的情況。
DHCP 服務器的這項功能可以通過設置 DS 參數來達到。來讓服務器延遲對客戶機的請求。
DHCP 服務器應該利用客戶機請求的 secs 域的值，如果這個值不為0 的話。
因為有些客戶可能沒能正確實現 secs 域，DHCP 服務器應該記錄客戶事務的第一次情況，如果第二次請求包中的 secs 域依然為0 ，那么DHCP 服務器就可以采用請求之間延時，而不再使用 secs 域。
5. 操作
5.1 設置
設置步驟包括分配散列值給服務器，這一步通過提供一個或者多個散列桶分配來實現。這可以通過配置文件，Windows NT 注冊表，EEPROM 等得到。另外，散列桶的值可以采用一些貪婪算法來分配。例如：“所有奇數由A 服務器服務，所有偶數由B 服務器服務?！?5.2 面向服務器的 HBA 
當設置為一個指定的服務器時，HBA 應該采用 32 位八進制的簡單位圖。
HBA 位圖的第一個八進制代表了 HBA 值 0-7，下一個為 8-15，依此類推，第32個代表 248-255，在每一個八進制數字中，最小位代表了那個八進制數中最小的HBA 值。
HBA 的每個位和每個可能的散列值對應。如果位圖中的位是設置的話，意味著接收服務器必須服務客戶機的請求，這時，STID 產生對應的散列值。
例如，如果一臺服務器的HBA 如下：   
            FF FF FF FF FF FF 00 00 ( 0   - 63 )
            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 (192 - 255 )
那么它必須服務那些STID 散列值在 0-47 和64-127 之間的客戶機請求。
5.3 延遲服務參數
延遲服務參數是可選的。
如果這個參數沒有設置，那么 HBA 會設置一個嚴格的服務/不服務規則。
如果參數已經設置，對于本來不服務于一些特定客戶請求的服務器，可以在 S 秒以后響應請求。服務器可以利用BOOTP 消息頭中的 secs 域來決定客戶嘗試獲得服務的請求時間，否則它會采用其他辦法繼續請求。
5.4 轉向 HBA 
當設置為轉向代理時，(例如，BOOTP 中繼) 可能會使用包含服務器ID/散列桶值對的HBA。
這里，服務器 ID (SID) 決定了服務器對指定的散列桶負責，轉向代理轉發每個客戶請求， STID 產生指定的散列值給 SID 決定的服務器。
服務器 ID 可以是任意服務器屬性的唯一值，（例如 IP 地址，DNS 名字等），只要在中繼代理中的上下文有意義就可以了。
轉發器可以設置為轉發指定的包到多臺服務器，例如，BOOTP中繼可以設置為把負載分割為兩個基本的備份服務器對，每一個對運行 DHCP Failover 協議。在這個例子中，一個目標為服務器對的包就會轉發到基本的和輔助的服務器對。
一個轉發代理的可能配置文件設置如下：
   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;
以上的配置文件包含4 個 HBA，第一行的含義為：
“客戶請求產生的 STID 散列值在0-24 之間時，轉發到服務器 192.33.43.11 和192.33.43.12”。
第四行的含義是：“ STID 散列值為129,139,131,200,201或者202時，轉發到 192.33.43.16 ”。
6.  負載平衡的散列函數
下面的散列函數采用 C 語言來實現，利用了"Pearson 的散列" 算法。
   
這個函數具有計算的廉價性，對每一個鍵字節作一次數組搜索和 xor 操作。
為了讓本建議運作，所有其他的實現方法必須使用這個散列函數?；旌媳砑系臄抵等缦拢? 
/* 256 個唯一值的混合表，采用偽隨機排序。*/

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,

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,       /* 要散列的鍵值 */
        const int len )                 /* 鍵長度（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],    /* 散列桶二進制表 */
        const unsigned char *key,       /* 服務事務 id   */
        const int len  )                /* 長度   */
{
unsigned char hash = loadb_p_hash(key,len);
int index          = (hash >> 3) & 31;
int bitmask        = 1 << (hash & 7);

        /* 服務事務的話，返回  1 */
        return((HBA[index] & bitmask) != 0);
}
7.  安全考慮
本建議本身不構成安全問題，也不會影響現存的安全設置。采用這個算法的服務器保證HBA 的內容能在網絡上傳送，這個消息能防止竄改。因為對 HBA 的篡改會導致一些或者所有客戶拒絕服務。

      
參考

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

鳴謝

特別感謝 Peter K. Pearson，無私奉獻他的算法。
本建議來自1999年2月，在CISCO 公司和 Ted Lemon討論 Failover協議時，對散列 MAC 地址到單個位的思想。 Rob Stevens 建議采用這個算法。
還要感謝在以后的討論中 Ralph Droms, Kim Kinnear, Mark Stapp, Glenn Waters,Greg Rabil 和 Jack Wong 提出的建議。
作者地址：
   Bernie Volz
   Ericsson
   959 Concord Street
   Framingham, MA  01701

   Phone: +1-617-513-9060
   EMail: bernie.volz@ericsson.com

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

   Phone: 781-332-1165
   EMail: steve.gonczi@networkengines.com

   Ted Lemon
   950 Charter Street
   Redwood City, CA 94043

   EMail: ted.lemon@nominum.com

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

   Phone: (650)-968-4470
   EMail: robs@join.com

版權說明

   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.

致謝
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC3074  DHC Load Balancing Algorithm                   DHCP 負載平衡算法




1
RFC文檔中文翻譯計劃