(57)【要約】【課題】　実質的に規模が無制限のクラスタ・コンピューティング環境においてオペレーティング・システム・イメージを複写する方法を提供する。【解決手段】　本発明に係る方法は従来の方法が必要としたインストールに対する厳密な量的制御を必要としない。本発明に係る方法によれば、オペレーティング・システム・イメージは自身をクラスタ環境中に伝搬させ、それをクラスタ全体がインストールされるまで続ける。多忙期間にはインストールを自動的に遅延させる規制法を採用することにより、ブロードキャスト嵐と応答嵐を避ける。本発明に係る方法では、クラスタ中のノード数およびクラスタ・ネットワークの構成を予め知っている必要がない。【選択図】          図２
2004139564.tif 000002
【特許請求の範囲】
【請求項１】
　コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法であって、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成るコンピュータの組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする
方法。
【請求項２】
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
請求項１に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項３】
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
請求項２に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項４】
　前記目標インストール要求速度が合計ネットワーク帯域幅速度に比例している、
請求項２に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項５】
　前記目標インストール要求速度が合計ネットワーク帯域幅速度の１０％より小さい、
請求項４に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項６】
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
請求項２に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項７】
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
請求項６に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項８】
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
請求項７に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項９】
　前記インストール・コンピュータは新たにインストールされたクライアント・コンピュータ（今や二次的インストール・コンピュータ）に前記新たな現在のインストール確率を送信し、前記新たにインストールされた二次的インストール・コンピュータは前記新たな現在のインストール確率でインストール要求に応答する、
請求項８に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項１０】
　前記減少率が１／２であり、前記インストール・コンピュータおよび前記二次的インストール・コンピュータは同じ確率を有し、前記インストール・コンピュータおよび前記二次的インストール・コンピュータの合計応答確率は前記インストール・コンピュータの旧応答確率と同じである、
請求項９に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項１１】
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
請求項６に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項１２】
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
請求項８に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項１３】
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
請求項１０に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
【請求項１４】
　コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法を実行する手段を備えたコンピュータ読み取り可能な記録媒体であって、
　前記方法が、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成る組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする、
記録媒体。
【請求項１５】
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
請求項１４に記載の記録媒体。
【請求項１６】
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
請求項１５に記載の記録媒体。
【請求項１７】
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
請求項１４に記載の記録媒体。
【請求項１８】
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
請求項１７に記載の記録媒体。
【請求項１９】
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
請求項１８に記載の記録媒体。
【請求項２０】
　ネットワークによって結合されたコンピュータの組を備え、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成るコンピュータの組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする
方法を実行するように適合したプログラムを実行するコンピュータの組を含むコンピュータ・システム。
【請求項２１】
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
請求項２０に記載のコンピュータ・システム。
【請求項２２】
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
請求項２１に記載のコンピュータ・システム。
【請求項２３】
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
請求項２２に記載のコンピュータ・システム。
【請求項２４】
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
請求項２３に記載のコンピュータ・システム。
【請求項２５】
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
請求項２４に記載のコンピュータ・システム。
【請求項２６】
　ランダムな態様でノードからノードへオペレーティング・システム・イメージをすべての所望のノードが前記ペレーティング・システム・イメージを受け取るまで伝搬させることにより、複数のノードにオペレーティング・システム・ソフトウェアをインストールする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明はＣＰＵ群から成るクラスタ群を備えたコンピューティング・システムにおけるオペレーティング・システムのインストールに関する。
【背景技術】
【０００２】
　安価なコンピューティングを実現するクラスタ化の価値は、ウェブを提供する高性能コンピューティングなどの分野で広く知られている。しかし、クラスタの大きさは一般に約５１２ノードにとどまっている。それは主に、オペレーティング・システムの１つの版で大きなクラスタの初期セットアップをいかにして行うかという問題に起因している。現在、クラスタ群は１つのクラスタをインストールするのに単一サーバ手法または階層型サーバ手法を用いている。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
　単一サーバ手法では、インストール・サーバとなるべき、インテリジェンスとソフトウェア（すなわち通常のＣＰＵ〔つまりシステム中のノード〕に共通のオペレーティング・システムのほかにインストールに必要な余分なソフトウェア）をすべて備えた単一のワークステーションですべてのノードに対してインストールを行う。階層型手法では、主サーバが二次的な組を形成しているインストール・サーバ群に対してインストールを行うから、オペレーティング・システムの伝搬が緊密に制御された「波」の形で生じる。すなわち、主サーバが二次的サーバ群に対してインストールを行い、これら二次的サーバ群が残りのクライアントに対してインストールを行う。これらの２つの方法には、「ブロードキャスト嵐（broadcast storm)」と呼ばれる現象が生じるという問題がある。ブロードキャスト嵐は、多数のノードを同時にパワーアップし、それらのノード群が規則正しく短い間隔で同時にネットワーク・パケットをブロードキャストする結果生じるものであり、ネットワークを飽和させ最終的にはネットワーク上の通信をすべて不通にさせる。
【課題を解決するための手段】
【０００４】
　本発明は速度制限的な特徴を有する、プログラムをインストールする方法に関する。インストール・サーバはクライアントが出す要求に確率基準に応答する。これにより、ネットワークの帯域幅に過負荷がかかる機会が減少する。
【０００５】
　本発明の特徴はクライアントが出す動的インストール要求速度であり、それは他の（すべての）クライアントによる要求の（合計）速度に基づく。
【０００６】
　本発明の別の特徴はクライアントへのソフトウェアのインストールであり、それは当該クライアントが別のクライアントにプログラムをインストールするのを可能にするのに十分なものである。したがって、インストールを要求しているクライアントは少なくとも一時的にインストール・サーバになり、クライアントが出す要求に確率基準に応答する。しかし、その応答速度は最初にインストールしたサーバより遅い。
【０００７】
　本発明の別の特徴はクライアントによる自己調整要求速度であり、それは他のクライアントによる要求数に基づく。
【０００８】
　本発明の別の特徴は要求を出すクライアント用に限定されたアドレス範囲を各インストール・サーバが割り当てることである。新たに生成されたサーバはこの限定されたアドレス範囲内で応答することができる。
【発明を実施するための最良の形態】
【０００９】
　図１を参照する。図１は本発明に係るコンピュータ・クラスタ１００の一部の概略を示す図である。ボックス１１０はＣＰＵ、ディスク駆動装置、メモリ、およびＣＰＵに物理的に近接して設けられた他の周辺機器を備えたコンピュータを模式的に表している。ボックス１０５は別のコンピュータに問題のソフトウェアをインストールするのに必要なソフトウェア、それに付随するハードウェアおよびＬｉｎｕｘオペレーティング・システムの全イメージなどのファームウェア、ならびに新たなクライアント・ノードに接触してインストールを実行する本発明に係るインストール・プログラムを備えたインストール・モジュールを表している。
【００１０】
　線２０はクラスタ内のノード（すなわちＣＰＵ）間の通信リンクを表わしている。このリンクは無線、既存のバス、これら２つの組み合わせなどである。線２２−ｉはクラスタ内の他のノードへのリンクを表わしている。コンピュータから成るネットワークにはそれが担持しうる合計ネットワーク帯域幅、およびネットワークが担持しうる、単位時間当たりのインストール要求数である合計ネットワーク帯域幅速度がある。
【００１１】
　本発明が解決しようとする課題は、「嵐（storm)」を生じさせることなく時宜にかなった形態でクラスタのノード群全体にインストールを実行することである。嵐とは、通信リンクを覆うトランザクションが同時に多数発生し、ノードをまたぐ通信システムの能力に過負荷が課される状態のことである。現代のコンピューティング技術では数万のノードから成るアーキテクチャが企図されているが、現在は数万のノードから成るクラスタにソフトウェアをインストールしアップグレードすることは実際的でない。
【００１２】
　本発明に係る「自己複製インストール法（Self-Replicating Installation Method: ＳＲＩＭ）」では、ノードを管理しておき選択したノード集合だけをインストール・サーバにするのではなく、すべてのノードをインストール・サーバにする。ＳＲＩＭを用いると、インストールは制御されず非決定的形態でクラスタ全体に広がり、それはクラスタ中のすべてのノードがインストールされるまで続く。
【００１３】
　（ノード数が５１２超の）大きなクラスタではノード群をパワーオンし、それらにインストール要求をブロードキャストさせるだけですぐにブロードキャスト嵐を引き起こすから、ＳＲＩＭでは「クライアント・ブロードキャスト規制法（Client Broadcast Regulation Method: ＣＢＲＭ）」を採用してクライアント・ノードが出すインストール要求を制限し、ノードがブロードキャストしてサーバを探索する頻度を低減させてインストール要求間の間隔がどんどん延びるようにしている。同様に、多数のサーバにクライアントからの要求に応答させると、類似の「応答嵐（response storm）」を引き起こす可能性がある。これを避けるために、ＳＲＩＭでは「サーバ応答規制法（Server Response Regulation Method:ＳＲＲＭ）」を採用してサーバの応答数を低減している。
【００１４】
　〔自己複製インストール法（ＳＲＩＭ）〕
　ＳＲＩＭは第１のインストール・サーバである単一のノード１１０から開始する。ノード１１０にはオペレーティング・システムおよびクライアント・ノードに対して（図１でボックス１０５、１０５−ｉで表記されている）インストール・サーバ自体としてのインストールを実行するのに必要なすべてのソフトウェアのコピーがインストールされている。オペレーティング・システムに特有の事項ではないが、Ｌｉｎｕｘの場合、第１のサーバにはＬｉｎｕｘの完全な版、および別のノードに対してインストールを実行するのに必要なすべてのＲＰＭ（インストール・パッケージ）、さらに実行するのに必要なすべてのインストール・サービスを持たせる。様々なオペレーティング・システムによってインストールするのに必要なソフトウェアは、コンピューティング産業においてよく知られている。サーバ１１０はメーカーが推奨する既存の任意の方法でインストールすることができる。
【００１５】
　第１のサーバがインストール済みでありクライアントに対してインストールを開始しうる状態にある場合、クライアントの経験的に決められた部分がパワーアップし（後述する）ＣＢＲＭを用いてブロードキャストを開始する。好適な実施形態では、すべてのクライアントがパワーアップしブロードキャスト・プロセスを開始する。サーバはよく知られたプロトコルたとえばＤＨＣＰを備えている。ＤＨＣＰはコンピューティング・ノードの初期ブートの間にサーバとコンピューティング・ノードとの間で通信するのに使われるプロトコルである。ＤＨＣＰはサーバがノードにネットワーキング情報とスタートアップ情報、たとえばそのＩＰアドレスとゲートウェイを供給する際に依拠するプロトコルを規定するとともに、ノードに初期ブリングアップ・カーネルを供給する。
【００１６】
　サーバは第１のインストール要求を受信すると、応答（answer）で応答(respond) する。この結果、自身を１つのクライアントに添付（attach）する。また、別のサーバが出す応答があっても、上記クライアントはそれを無視する。いったん添付したら、サーバはそのＤＨＣＰサービスをシャットダウンし、別のインストール要求を無視し、上記クライアントに対するインストールを開始する。そのＤＨＣＰをシャットダウンすることにより、サーバは別のＤＨＣＰ応答を排除する。これにより、ネットワーク通信量が低減する。次いで、サーバは上記クライアントにオペレーティング・システムの完全な版、および（ボックス１０５に格納されており）上記クライアントが自身を複製する際に必要になるサービスやインストール可能なイメージをすべてインストールする。上記クライアントはインストールが完了したら、自身を再ブートして自分自身（すなわち同位のサーバ）になる。「クライアント」および「インストール・サーバ」なる用語は時の経過とともに変化する。たとえば、クライアントは未インストールまたは未アップグレードのノードであるが、いったんアップグレードするとサーバになる。以上説明した事項は本発明に従って採用したピア・ツー・ピア手法を反映したものである。サーバはクライアントに対するインストールを完了すると、そのＤＨＣＰサービスを無視し、別のクライアントに対してサービスしうる状態、すなわち、要求を受信しインストールを実行しうる状態になる。
【００１７】
　サーバによるインストール応答は「確率的」である。すなわち、サーバは自分が聞いた要求に確率に従って応答したりしなかったりする。たとえば、１〜１００のランダム数を算出し、問題の応答（すなわち当該ランダム数）が基準確率（たとえば２５％）によって設定された範囲（この場合０〜２５）の内または外のどちらに存在するかに従って応答したりしなかったりする。
【００１８】
　基本インストール・フローを図２を参照して以下にまとめる。
　（１）　ＣＤ（またはディスケット、インターネット、またはＯＳをインストールするよく知られた任意の方法）によって主（第１の）ノードにオペレーティング・システム・イメージ、ソフトウェア・パッケージ、および自身を複製するのに必要なすべてのサービスをインストールする。
　（２）主サーバ上で必要なサービスを開始する。
　（３）クライアントをパワーアップする（一度にすべてのクライアントをパワーアップするのが望ましい）。
　（４）クライアントはパワーアップしたら、ブロードキャストしてサーバの探索を開始する。
このプロセスにはＣＢＲＭを用いる。
　（５）サーバはクライアントに応答し、自身を当該クライアント添付し、自身のＤＨＣＰサービスをシャットダウンする。
　（６）サーバは１つのノードにオペレーティング・システム・イメージ、インストール可能なイメージ、および必要なすべてのサービスをインストールする。
　（７）新サーバは自身を同位のサーバとして再ブートし、旧サーバはＤＨＣＰを再開始して新たなクライアントに再添付する。
　（８）新サーバは再ブートを完了したら、ブロードキャストしてクライアントの探索を開始する。
　（９）新サーバはブロードキャストして添付すべきクライアントを探索する。これはクラスタ内のすべてのノードがインストールされるまで続ける。
【００１９】
　現在の実務では、ノードはパワーオンするといわゆる「ダム（dumb）ブロードキャスト」を開始する。すなわち、ノードは一定の短い間隔でブロードキャストしてサーバを探索する。一度に多数のクライアントがパワーオンすると、すべてのクライアントがダム・ブロードキャスト・メソッドを呼び出すから、ネットワークを飽和させ通常すべてのネットワーク通信を不可能にするブロードキャスト嵐が始まる。一部のマシンのＢＩＯＳには、クライアントが少ない個数のブロードキャストののち（すなわち約６０秒のち）にそのブロードキャストに対するＤＨＣＰ応答を受信しない場合には、ノードを再ブートするように命令が組み込まれている。
【００２０】
　ＣＢＲＭは、クライアントは適切なサーバを見いだすまでに多くの時間（またはきわめて大きなクラスタでは数日間）ブロードキャストし続けるものと仮定することにより、クライアントが賢明にブロードキャストを行いうるようにするものである。ＣＢＲＭによれば、ネットワーク通信量およびブロードキャスト嵐の可能性を大幅に低減することが可能になる。
【００２１】
　〔クライアント・ブロードキャスト規制法（ＣＢＲＭ）〕
　ＣＢＲＭは動的であり、ネットワーク状態に対する感受性を基にして嵐の発生を抑止するものである。ノード上でＣＢＲＭを開始すると、ブロードキャストはゆるやかな速度（たとえば１分間当り６回）で行われるようになる。ブロードキャストしながら、ノードはネットワーク上で発生するブロードキャストの総数をモニタし、合計ブロードキャスト速度を求める。次いで、この合計ブロードキャスト速度と格納してある目標要求速度とを比較する。合計ブロードキャスト速度が目標要求速度よりも小さい場合、ノード自身のブロードキャスト速度を目標要求速度と合計ブロードキャスト速度との差に比例する量だけ増加させる。逆に、合計ブロードキャスト速度が目標要求速度よりも大きい場合、ノード自身のブロードキャスト速度を目標要求速度と合計ブロードキャスト速度との差に比例する量だけ減少させる。こうして、各ノードのブロードキャスト速度は目標要求速度に近い合計ブロードキャスト速度を維持しうる値に収束するようになる。あるクライアントのブロードキャスト総数と別のクライアントのブロードキャスト総数は単純に関連し、個々の応答速度を調整するという観点からは等価である。
【００２２】
　合計ブロードキャスト速度は変動する傾向があり時として大きく変動するから、目標要求速度は大きなゆらぎを許容する裕度を備えるように選定する必要がある。また、目標要求速度は総ネットワーク帯域幅の小さな部分（おそらく１％）に設定する。ＤＨＣＰブロードキャストはきわめて小さいから、きわめて大きな個数のブロードキャストが可能になるとともに、起こりうる速度スパイクを許容する余地がある。特定のネットワークの場合の経験によれば、合計ブロードキャスト速度はシステム管理者によって調整することができる。
【００２３】
　留意点を挙げると、クライアントが迅速にブロードキャストできるようにして、サーバを数秒間早く見い出しうるようにすることは重要ではない。本発明の目的はブロードキャスト嵐を避けることである。ブロードキャスト嵐を引き起こす急速で非管理のブロードキャストこそ問題である。ブロードキャストの間隔を制御することにより、ＣＢＲＭは偽ネットワーク通信量の問題を軽減するものである。
【００２４】
　再度、図２を参照してフローチャートを敷衍（ふえん）する。
【００２５】
　まず、（集合全体であると想定する）クライアント群が６回／分でブロードキャストを開始する。
【００２６】
　各クライアントはネットワークから合計ブロードキャスト速度を読み取り、それを目標要求速度と比較する（目標要求速度はネットワークのセットアップ中またはブロードキャスト・メッセージによって取得する）。
【００２７】
　各クライアントは実際のブロードキャスト速度と目標要求速度とを比較する。この例では、目標要求速度を６０回／分、他のクライアントに起因する現在のブロードキャスト速度を３０回／分と想定する。
【００２８】
　現在のブロードキャスト速度が目標要求速度よりも小さいから、クライアントのブロードキャスト速度を目標要求速度と現在のブロードキャスト速度との差の比例分、たとえば差の半分だけ増加させる。この例の場合、差は５４回／分であるから、クライアントのブロードキャスト速度を２７回／分だけ増加させて３３回／分にする。残りのクライアントのブロードキャスト速度も増加させる。
【００２９】
　応答しているサーバはないから、クライアントはこのブロードキャスト速度でブロードキャストを続け、所定期間後にブロードキャスト速度を再評価する。この所定期間を決めるにはいくつかの方法がある。たとえば、ｘ秒±ｙ（ただしｙはｘの１０％の範囲のランダム数）のように決める。これにより同時に、クライアント速度をを増加または減少させることに起因する速度スパイクを低減することができる。
【００３０】
　今度は、クライアント速度を増加させた結果、合計ブロードキャスト速度が６３回／分になったと想定する。合計ブロードキャスト速度は目標要求速度よりも大きいから、クライアントのブロードキャスト速度を減少させる。クライアントのブロードキャスト速度はここでも差の半分だけ、すなわち１．５回／分だけ調整する。これにより、クライアントのブロードキャスト速度は（丸めて）３１回／分になる。
【００３１】
　このプロセスはクライアントがサーバに応答されるまで続ける。
【００３２】
　〔サーバ応答規制法（ＳＲＲＭ）およびＩＰアドレス割り当て〕
　プロセスがいったん大きなクラスタと折り合いを付けると、応答しうるサーバの数が多くなる。したがって、「応答嵐（response storm）」を避ける方法を備えるのが有利になる。応答嵐とは個々の要求に応答するサーバの数が多すぎる状態のことである。この応答嵐が発生するのを避けるために、サーバ応答規制法（Server Response Regulation Method:ＳＲＲＭ）を採用する。ＳＲＲＭを用いると、任意の要求に応答しうるマシンの平均個数は常にほぼ１になる。
【００３３】
　クラスタはグローバルに一定に保たれている２つのリソースを備えているものと見ることができる。これら２つのリソースの一方は（１００％から始まる）応答確率であり、他方はネットワーク内のＩＰアドレス（ＴＣＰの慣例によるとたとえば１０．０．０．０．８）である。サーバはクライアントに対してインストールを行うときには常に、自身が保有するこれら２つのリソースを自身と当該クライアントとの間で平等に分割する。
【００３４】
　図３を参照して一例を説明する。
【００３５】
　最初のインストール期間中、第１のサーバはクライアントの要求に対してたとえば２５％の確率で応答する。応答するか否かはランダム数発生器の結果に基づいて決める。
【００３６】
　サーバは（最終的には）インストールすべきクライアントの要求を受け入れる。サーバは（ＴＣＰの場合）よく知られたＩＰ範囲１０．６４．０．０〜１０．１２７．２５５．２５５のＩＰアドレスを保有している。サーバは（当該サーバのＩＰ範囲の１／２に当たる）１０．９６．０．１なるＩＰアドレスをクライアントに割り当てる。次いで、クライアントにオペレーティング・システムをインストールする。
【００３７】
　クライアントはサーバとのコネクションを切断するまえに、自身がインストールすることになる新クライアントに割り当てるべきＩＰアドレスのブロックを要求する。サーバは自身のＩＰアドレス・ブロックの１／２に当たる範囲のＩＰアドレスをクライアントに与える。このようにＩＰアドレスを動的に割り当てることは好都合である。すなわち、ＩＰアドレスを管理していないから、ボトルネックが形成されない。アドレス範囲の半分を利用可能なアドレス・ブロックにする実際的な利点は、ＩＰアドレスの割り当てを動的かつ非管理に行える点である。このアルゴリズムの場合、ＩＰアドレスの完全なブロックは稀にしか使用されない。これはクラスタに悪影響を与えない。なぜなら、ＩＰアドレスのこのブロックはクラスタの外部には反映されないので、すべてのクラスタは同一のＩＰアドレスを使用しうるからである。
【００３８】
　アドレスのブロックを受け取ったのちノードがインストールに失敗しても、それはクラスタの残りのノードのインストール動作に影響しない。失敗したノードはＩＰアドレスの一部を保持することになるが、それは問題ではない。可能なＩＰアドレスの個数は考えうるクラスタの個数よりも大きいから、実際にはＩＰアドレスが不足することはない。
【００３９】
　クライアントは応答パーセンテージ（百分率）を要求する。サーバはその応答パーセンテージの１／２を譲渡する。いま、クライアントとサーバの双方がクライアントのインストール要求に対して同一の機会（１２．５％）を有し、サーバが自分と同一個数のＩＰアドレスをクライアントに譲渡するものと想定する。２５％という初期値と譲渡の際に生じる端数はシステム管理者が調整することができる。
【００４０】
　次いで、プロセスは始めから繰り返す。
【００４１】
　インストール・プロセスが終了するのは、システム管理者が定めた期間内にネットワークに要求が発生しないときである。
【００４２】
　以上説明した方法を用いると、インストールの仕事はクラスタ中に平等に分散される傾向がある。サーバがクライアントの要求に応答する機会は確率的であるから、特定の要求に複数のサーバが応答しうる。しかし、平均的な場合には、応答しうるサーバはほぼ１つである。クラスタが大きくなるのにつれて、サーバ群が応答する確率は指数関数的に小さくなる。この結果、応答嵐の可能性を回避することができるようになる。
【００４３】
　本発明に係る方法（ＳＲＩＭとＣＢＲＭ）は多くの態様で実現することができる。１つの方法は各ノードで、あるいは各ノードのネットワーク通信カードでＣＢＲＭをサポートする専用のＢＩＯＳ（ファームウェア）を用いるものである。これにはインストールするオペレーティング・システムを変更する必要がないという利点がある。別の方法はインストール後の最初の再ブート時に呼び出し、インストール・プロセスが終了したら自動消滅する、インストール・パッケージの一部をなすプログラムを用いるものである。しかしながら、当業者は別の方法を容易に案出することができる。いずれにせよ、駆動プログラムによって、ブロードキャスト間の遅延時間（すなわちブロードキャスト間隔）の間にネットワーク通信カードがＣＢＲＭ法に従うようにさせることができる。別の実装として、ネットワーク・カード自体にＣＢＲＭソフトウェアを直接に搭載する方法が考えられる。この場合、ノードＢＩＯＳがネットワーク・インタフェース・カード用のデバイス・ドライバを始動し、同カードがＣＢＲＭ自体を実行することになる。そして、ＣＢＲＭがノードＢＩＯＳおよびネットワーク・インタフェース・カードＢＩＯＳのどちらに実装されているのかが、インストール・サーバに分かっている必要がある。
【００４４】
　本発明は広い範囲のクラスタ・サイズに適用することを意図しているから、当業者が予期しうるように、インストール速度が一部の構成では一部の従来技術の方法よりも早いが、一部の特定の場合には一部の従来技術の方法の方がインストール速度が早い。本発明の狙いは特定の構成ではなく、柔軟性にある。柔軟性は特にクラスタの大きさが以前には非実際的であったほどに大きい場合、特定の構成に特化した方法より有益であると考えられる。伝統的なボトルネックは伝統的なブロードキャスト法ではなくＣＢＲＭを採用することにより除去することができる。また、従来の方法には任意的な制限があった。たとえば、１つのノードは他の１６個のノードに対してインストールすると、それで終了であった。
【００４５】
　当業者が認識しうるように、本発明の範囲内で多くの変形をデバイなすことができる。たとえば、アドレス範囲を動的にし、インストール速度を遅くして潜在的なクライアントの数を増加させることができる。同様に、応答パーセンテージの数値を動的にすることができる。サーバはそのアドレス範囲を１／２ではなく１／４あるいは他の分数分だけ譲渡することができる。ネットワーク通信量の判断基準を単位時間当りの要求個数ではなく（能力と比較した）単位時間当りのパケット数またはバイト数にすることができる。これにより、より大きな（より小さな）オペレーティング・システムおよびより早い（より遅い）ネットワークを用いることが可能になる。本発明に係る方法はオペレーティング・システム（たとえばＬｉｎｕｘ）の初期インストールに限定されない。本発明に係る方法は（適切なインストール・プログラムを付随させることにより）アプリケーション・プログラムに適用することができるし、アップグレードにも適用することができる。「オペレーティング・ソフトウェア」なる用語は問題の機能を実行するソフトウェアを意味し、たとえばコンピュータの操作や天気予報プログラムにおける計算を実行するソフトウェアを意味する。
【００４６】
以上、本発明を１つの好適な実施形態の観点から説明したが、当業者が理解しうるように、本発明は特許請求の範囲の本旨と範囲の内で様々な態様で実施することができる。
【００４７】
　まとめとして以下の事項を開示する。
　（１）
　コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法であって、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成るコンピュータの組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする
方法。
　（２）
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
上記（１）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（３）
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
上記（２）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（４）
　前記目標インストール要求速度が合計ネットワーク帯域幅速度に比例している、
上記（２）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（５）
　前記目標インストール要求速度が合計ネットワーク帯域幅速度の１０％より小さい、
上記（４）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（６）
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
上記（２）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（７）
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
上記（６）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（８）
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
上記（７）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（９）
　前記インストール・コンピュータは新たにインストールされたクライアント・コンピュータ（今や二次的インストール・コンピュータ）に前記新たな現在のインストール確率を送信し、前記新たにインストールされた二次的インストール・コンピュータは前記新たな現在のインストール確率でインストール要求に応答する、
上記（８）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（１０）
　前記減少率が１／２であり、前記インストール・コンピュータおよび前記二次的インストール・コンピュータは同じ確率を有し、前記インストール・コンピュータおよび前記二次的インストール・コンピュータの合計応答確率は前記インストール・コンピュータの旧応答確率と同じである、
上記（９）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（１１）
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
上記（６）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（１２）
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
上記（８）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（１３）
　前記第１のインストール・コンピュータはネットワーク・アドレス範囲の中間点であるネットワーク・アドレスを有し、前記第１のインストール・コンピュータは自身がインストールした各二次的インストール・コンピュータに前記第１のインストール・コンピュータの当時の現在のネットワーク・アドレス範囲の半分である二次的インストール・コンピュータ・ネットワーク・アドレス範囲と、前記二次的インストール・コンピュータ・ネットワーク・アドレス範囲の中間点であるネットワーク・アドレスとを割り当てる、
上記（１０）に記載の、コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法。
　（１４）
　コンピュータの組を備えたネットワークにおいてコンピュータ・プログラムをインストールする方法を実行する手段を備えたコンピュータ読み取り可能な記録媒体であって、
　前記方法が、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成る組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする、
記録媒体。
　（１５）
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
上記（１４）に記載の記録媒体。
　（１６）
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
上記（１５）に記載の記録媒体。
　（１７）
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
上記（１４）に記載の記録媒体。
　（１８）
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
上記（１７）に記載の記録媒体。
　（１９）
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
上記（１８）に記載の記録媒体。
　（２０）
　ネットワークによって結合されたコンピュータの組を備え、
　オペレーティング・ソフトウェアおよびインストール・ソフトウェアを備えた第１のインストール・コンピュータを準備するステップと、
　動的に調整可能な速度でインストール要求をブロードキャストする少なくとも１つのクライアント・コンピュータから成るコンピュータの組を準備するステップと
を備え、
　前記インストール・コンピュータは第１のインストール要求に応答してコンピュータから成る前記組の第１のクライアント・コンピュータに前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることにより、前記クライアント・コンピュータを二次的なインストール・コンピュータとして確立し、
　インストール操作の間、前記第１のインストール・コンピュータはインストール要求を無視し、
　第１のインストールが完了したら、前記第１のインストール・コンピュータおよび前記二次的なインストール・コンピュータの双方は前記オペレーティング・ソフトウェアおよびインストール・ソフトウェアの双方をインストールすることによりインストール要求に対してサービスする
方法を実行するように適合したプログラムを実行するコンピュータの組を含むコンピュータ・システム。
　（２１）
　クライアント・コンピュータが最初に初期要求速度でインストール要求をブロードキャストし、前記ネットワークで担持されている合計インストール要求速度をモニタし、
　前記クライアント・コンピュータは前記合計インストール要求速度と目標インストール要求速度とを比較し、前記合計インストール要求速度と前記目標インストール要求速度との差によって決まる調整量だけ自身の速度を調整することより自身のブロードキャスト速度を調整する、
上記（２０）に記載のコンピュータ・システム。
　（２２）
　前記調整量が前記合計インストール要求速度と前記目標インストール要求速度との前記差に線形に比例している、
上記（２１）に記載のコンピュータ・システム。
　（２３）
　インストール・コンピュータは自身が受信したインストール要求に確率的態様で応答する、
上記（２２）に記載のコンピュータ・システム。
　（２４）
　インストール・コンピュータは自身が受信したインストール要求に初期基準確率に従って応答する、
上記（２３）に記載のコンピュータ・システム。
　（２５）
　インストール・コンピュータは自身が受信したインストール要求に現在のインストール確率に従って応答し、自身が応答したインストール要求を完了したら、ある減少率だけ自分の現在のインストール確率を減少させて将来の要求に応答する際に依拠する新たな現在のインストール確率を算出する、
上記（２４）に記載のコンピュータ・システム。
　（２６）
　ランダムな態様でノードからノードへオペレーティング・システム・イメージをすべての所望のノードが前記ペレーティング・システム・イメージを受け取るまで伝搬させることにより、複数のノードにオペレーティング・システム・ソフトウェアをインストールする方法。
【図面の簡単な説明】
【００４８】
【図１】本発明で用いるコンピュータ・クラスタの概略を示す図である。
【図２】本発明に係る手順を示す図である。
【図３】図２の手順の一部を示す図である。
【符号の説明】
【００４９】
　２０　線
　２２　線
１０５　インストール・モジュール
１１０　コンピュータ
【図１】
2004139564.tif 000003
【図２】
2004139564.tif 000004
【図３】
2004139564.tif 000005