RFC 3074¶
概要¶
この文章ではロードバランシングのアルゴリズムを提案します．これは，はじめの設定以外の情報交換を必要とせずに，複数のサーバのうちのどれがクライアントに対して応答するかを決定するものです．
このサーバ選択アルゴリズムは，複数のDHCPサーバがクライアントにサービス提供を行う際，サーバで計算するクライアントのMACアドレスのハッシュをもとにします．この提案手法は，複数のDHCPサーバがネットワーク上で動作する時，既存のDHCPクライアントになんの変更の必要もなしに，効率的なサーバ選択を提供します．同様の手法はBOOTP relayのような転送エージェントを利用する場合に，ターゲットサーバを選択する場合にも提案されています．
1. 序論¶
このプロトコルはもともと，DHCP Failoverプロトコルのうち，特にロードバランシング最適化のために生まれました．著者らはのちに，冗長化されたDHCPサーバと，それらにパケットを転送するBOOTP relay agentの動作を最適化するために利用できることに気がつきました． この提案では，それぞれのサーバでクライアントの負荷割合をあらかじめ設定することができます． これは，決定論的ハッシュアルゴリズムを用いて行われ，似た特性を持つ他のプロトコルに容易に適用できます．
2. 用語¶
このセクションでは，多くのIETFプロトコル使用で共通な一般的な必要用語と，この文章で導入される用語の両方について議論します．
2.1 必要用語¶
"MUST", "MUST NOT", "REQUIERD", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", "OPTIONAL"のキーワードについては，RFC 2119に記載されている通りに解釈します．
2.2 ロードバランシング用語¶
このドキュメントでは下記の用語について紹介します．
- Service Delay, SD
- ロードバランシングのパラメータの一つで，クライアントを無視する代わりにロードバランシングに参加しているサーバによる遅延サービスを許可する遅延時間．
- Hask Bucket Assignments, HBA
- ロードバランシングスキームに参加するサーバに一連のHack Backet値を割り当てる構成ディレクティブ．
- Server ID, SID
- 参加しているサーバの一つを指定するために利用されるID．DHCPのコンテキストでは，このSIDはIPアドレスか，サーバのDNS nameである．
- Service Transaction, ST
- サーバがクライアントにサービス提供もしくは拒否をする一連の情報交換．例: DHCPサーバとクライアントで交換される，DISCOVER/OFFER/REQUEST/ACK メッセージはService Transactionである．
- Service Transaction ID, STID
- ロードバランシングに利用される個別のクライアントリクエストの属性．
3. バックグラウンドと外部要件¶
DHCPクライアントはDHCPサーバにコンタクトするためにUDP broadcastを利用するため，クライアントのDHCPDISCOVERメッセージは1台以上のサーバで受信される可能性があります．ブロードキャストを受け取った全てのサーバはクライアントに応答し，クライアントにどのサーバを利用するかを選ばせるでしょう．
BOOTP relay agentを利用する場合，クライアントのブロードキャストは一般にすべての設定されたサーバに転送，もしくは再ブロードキャストされるという同様の非効率性が存在します．
後述の最適化により，それぞれのトランアクションに対して,"サービスする"/"サービスしない"振る舞いをすることでサーバを選択することができます． 転送エージェントは転送先を決定するために同様の計算で動作できます．
いずれのケースでも，どちらが応答するかネゴシエーションすることなくサーバの選択がおこなわれます．
どのクライアントが次にリクエストをするかを予測することはほぼ不可能であるため，このアプローチは本質的には確率的なものです．短時間のうちにおいては，実際のところ特定のサーバによってサービスされるクライアントの割合は指定した割合から逸脱する可能性は十分あります．リクエストの数が上昇すると，それぞれのサーバで処理される実際の負荷の割合は設定された割合に近づくでしょう．
4. 概要¶
DHCPサーバはClient Identifierが存在する場合はそれを必ずSTIDとして利用します．もしClient Identifierオプションがない場合，DHCPパケットのhlenフィールドはハッシュ化されたデータの長さのために利用し，chaddrはハッシュ化されたデータでなければなりません．Client Identifierもしくはchaadrの最も始めの16bytesが利用されます．
この手案はこのSTIDをsection 6に示す関数を用いてハッシュ化した値に対応させます．そして，結果のハッシュ値を使って，どのサーバがリクエストに応答するべきか，もしくは転送するべきターゲットを決定する必要があります．
このハッシュ関数は0-255のハッシュ値を生成し，ランダムなSTIDや，パターン性のあるSTIDシーケンスにかなり均等なHack Backet分布を生成します． リソースアロケーションはそれぞれのサーバに特定のハッシュ値セットを割り当てることで実現します．
リクエストのSTIDハッシュが自身に割り当てられたハッシュ値セットのうちにマッチした場合にのみ，サーバはリクエストに応答します．
どのサーバにも割り当てされていないHack Backetは一部のクライアントSTは完全に無視されることになります(いくつかの状況では，これは好ましい結果になるかもしれません)．STIDはユニークである必要はありませんが，負荷を各サーバに分散するために十分ばらけているべきです．
HBAは他のプロトコルでカプセル化されて送信されるかもしれません．例: e-mail, DHCP Failover protocol option.
DHCPサーバの実装では，ロードバランシングは行われているがレスポンスが不可能であるもしくは十分なアドレスがないサーバを扱うための設定をオプションで設定することができます．
もし，client requestのsecsフィールドの値が0でなければ，この機能を提供するDHCPサーバはこの値を利用するべきです．いくつかのクライアントはこのsecsフィールドの実装が正しくないため，DHCPサーバは，通常は応答しないクライアントトランザクションのはじめのインスタンスを見続ける場合があります． もしサーバが過去に記録されたリクエストと同様のトランザクションIDをもったリクエストを受信した場合，もしくは2番目のpacketのsecsフィールドが0の場合，DHCPサーバは，最初とその次のクライアントリクエストまでの経過時間をsecsフィールドの代わりに利用することができます．
5. 動作¶
5.1 設定¶
この設定のステップは利用可能なサーバにハッシュ値を割り当てることから成ります．これは一つ以上のHBAが提供されていることで実現します．それらは，設定ファイルや，Windows NTレジストリ，EEPROMなどから構成されます．あるいは，HBAは決められたアルゴリズムを利用して割り当てることもできます．例: 奇数はserverA, 偶数はserverBが応答するなど．
5.2 サーバ向けのHBA¶
あるサーバを設定する時，32オクテットのシンプルなビットマップ形式を利用するべきです． HBAビットマップはじめのオクテットは0-7のHBA値で表現され，次は8-15，のように表現され，第32オクテットで248-255の値を表現します．それぞれのオクテットで，LSBはそのオクテットの最小のHBA値を表現します．
それぞれのHBAのビットは一つの取りうるハッシュ値にひもづきます．もしあるビットがビットマップにセットされていたら，それはSTIDのハッシュ値に対応して生成されたそれぞれのクライアントリクエストに応答しなければならないことを意味します．
たとえば，もしサーバには下記のような32オクテットの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のハッシュがHack Backetの0-47,と64-127の値のであるあらゆるクライアントリクエストに対して応答しなければなりません．
5.3 遅延サービスパラメータ¶
遅延サービスパラメータはオプションです．
もしパラメータが設定されていない場合，HBAは厳格に"サービスする"/"サービスしない"というポリシを構成します．
もしパラメータが設定されていた場合，HBAやSTID hashに基づく特定のリクエストに対して応答することになっていないサーバが，クライアントのはじめの試行から, S 秒間経過したのちに応答することを許可します．
サーバはBOOTPヘッダのsecsフィールドをサービスを利用しようとした時からの経過時間として利用しても構いませんし，他の手法で繰り返しのリクエストを追跡しても構いません．
5.4 フォワーダ向けのHBA¶
BOOTP relayといった転送エージェントを設定する際，Server-IDとHack Backet値のペアからなるHBAが利用できます．
ここで，Server ID(SID)は特定のHack Backetを担うサーバを指定します．その転送エージェントはSTIDが特定のハッシュ値を生成した各クライアントリクエストを，SIDで指定されたサーバに転送します．このサーバIDは何らかのユニークなサーバ属性(例: IP address, DNS nameなど)が利用でき，リレーエージェントの動作上，意味があるものです．
フォワーダは1つ以上のサーバにパケットを転送するように設定されているかもしれません．たとえば，BOOTP relayは互いでDHCP Failover Protocolが動作している2つのprimary-backupサーバペアの間で負荷を分割するように設定さえうります．
このありがちな転送エージェント(例: BOOTP realy)の設定ファイルとして，下記のようなものがあります
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からなっています．はじめのHBAの例は次のように読み取れます: "STIDのハッシュ値が0-24となるすべてのクライアントリクエストは192.133.43.11と192.33.43.12の両方のサーバに転送されます"
6. ロードバランシング用ハッシュ関数¶
下記のハッシュ関数はピアソンハッシュとして知られるアルゴリズムのC言語の実装です．このピアソンハッシュアルゴリズムはもともと[PEARSON: The Communications of the ACM Vol.33, No. 6 (June 1990), pp. 677-680.] で公開されました．
このハッシュ関数はそれぞれのキーバイトに配列検索とXOR演算を必要とし，計算機的に軽量なものです．この提案を使うためには，相互運用性のあるすべての実装はこのハッシュ関数を使用する必要があります．ミキシングテーブルの値のセットを下記に示します:
/* 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,
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. セキュリティの考察¶
この提案の内容とそれ自身は，セキュリティを提供せず，既存のセキュリティに影響を与えることもありません．もし，HBAの内容がいずれかのサーバを構成するプロセスの一部としてネットワークに送信されることがある場合，このアルゴリズムを利用するサーバは，そのメッセージの改ざんの脅威から守る責任があります．HBAの改ざんによって，いくつかもしくはすべてのクライアントへのサービスの提供不可を招くためです．
8. 参考¶
[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. 謝辞¶
ピアソンハッシュの著者であるPeter K. Pearsonに感謝します．彼は何の制約なしに彼のアルゴリズムを利用することを快く許可してくれました．
この提案は1999年2月，CISCO Systemsで開かれたFailover Protocolの会議中にTed LemonがMAC Addressを1ビットにハッシュ化する独特のアイディアが肝となっています．Rob StevensはFailover Protocolの目的を超えて，このアルゴリズムの有用性を示唆しました．
議論中にコメントをいただいた，Ralph Droms，Kim Kinnear，Mark Stapp，Glenn Waters，Greg Rabil，Jack Wongらに多大なる感謝をいたします．