(57)【要約】【課題】本発明は、ＯＳＰＦ（Ｏｐｅｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｆｉｒｓｔ）プロトコルのｔｙｐｅ　５　ＬＳＡ（Ｌｉｎｋ　Ｓｔａｔｅ　Ａｄｖｅｒｔｉｓｅｍｅｎｔ）の分離セットによるフラッシング方法を提供する。【解決手段】ネットワーク・デバイスで生成されるＬＳＡの全ては、予めマッピングによりＳセットに分離される。まず、ＬＳＡの１セットだけがフラッシュされ、次に、ＬＳＡの他のセットが所定のフラッシング間隔で順にフラッシュされる。本方法は、ＬＳＡによるネットワーク・トラフィックへの瞬間的な影響を低減し、ネットワークは低い負荷レベルをキープする。さらに、本方法は、全てのＬＳＡがネットワーク・フラッシュ間隔ごとに一度にフラッシュされ、ＯＳＰＦプロトコルが通常になされることを保証する。【特許請求の範囲】
【請求項１】
ＯＳＰＦ（Ｏｐｅｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｆｉｒｓｔ）プロトコルのｔｙｐｅ　５　ＬＳＡ（Ｌｉｎｋ　Ｓｔａｔｅ　Ａｄｖｅｒｔｉｓｅｍｅｎｔ）の分離セットによるフラッシング方法であって、
（１）マッピング手法によりネットワーク・デバイスで生成されるｔｙｐｅ　５　ＬＳＡの全てをＳセットに分離し、
（２）１〜Ｓの整数であるカレント処理セットのナンバーをＮとして記録し、
（３）セットの各々について、ネットワーク・フラッシング間隔をＳにより除した長さのフラッシング間隔の間待機し、
（４）Ｎ番目のセットの全てのＬＳＡをフラッシュし、Ｎに１を加え、ＮがＳより大きいか否か判断し、ＮがＳより大きいならば、Ｎに１をセットしてステップ（３）に戻り、ＮがＳより大きくないならば、ステップ（３）に直接戻る、
フラッシング方法。
【請求項２】
ステップ（１）は、１〜Ｓの範囲のナンバーにＬＳＡのＩＤ値をマッピングする、ことをさらに含む、請求項１に記載の方法。
【請求項３】
前記マッピング手法は、ＬＳＡのＩＤ値をＳで除した剰余に１を加えることを含む、請求項２に記載の方法。
【請求項４】
前記マッピング手法は、
ａ．ＬＳＡのＩＤ値をＰバイトに分割し、
ｂ．最初のＰ／２バイトと最後のＰ／２バイトとで排他的論理和を行い、
ｃ．前記排他的論理和の結果をＳにより除した剰余に１を加える、
ことを含み、
前記Ｐは偶数である、
請求項２に記載の方法。
【請求項５】
前記ネットワーク・デバイスは、ルータ、又は、イーサネット（登録商標）・レベル３エクスチェンジである、請求項１に記載の方法。
【請求項６】
前記ネットワーク・フラッシング間隔は、ＩＥＴＦ　ＲＦＣ
２３２８（Ｔｈｅ　Ｉｎｔｅｒｎｅｔ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｔａｓｋ　Ｆｏｒｃｅ　Ｒｅｑｕｅｓｔ　Ｆｏｒ　Ｃｏｍｍｅｎｔｓ　２３２８）により定義されている、請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ通信に関し、詳細には、ＯＳＰＦ（Ｏｐｅｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｆｉｒｓｔ）プロトコルのｔｙｐｅ　５　ＬＳＡ（Ｌｉｎｋ　Ｓｔａｔｅ　Ａｄｖｅｒｔｉｓｅｍｅｎｔ）の分離セットによるフラッシング方法に係る。
【０００２】
【従来の技術】
広く使用されているルーティング・プロトコルであるＯＳＰＦは、リンク状態演算を行う。すなわち、各々のルータは当該ルータの近傍の各々へのリンク状態をテストし、ＬＳＡを形成する。次に、各々のルータは全受信ＬＳＡに従い、ルーティング情報を計算する。該ＬＳＡは自律システム・ネットワーク全体に伝搬する。
【０００３】
ＯＳＰＦプロトコルにおいて、ｔｙｐｅ　５　ＬＳＡが外部のルーティングを示すために使用される。ネットワーク技術の大幅な進展により、ｔｙｐｅ　５　ＬＳＡの数は非常に増加するであろう。あるいは、当該数は数十万に達するかもしれない。ＩＥＴＦ　ＲＦＣ　２３２８規格（Ｔｈｅ　Ｉｎｔｅｒｎｅｔ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｔａｓｋ　Ｆｏｒｃｅ　Ｒｅｑｕｅｓｔ　Ｆｏｒ　Ｃｏｍｍｅｎｔｓ　２３２８　ｓｔａｎｄａｒｄ）は、ルータにより生成されるＬＳＡの全ては、例えば、１，８００秒程度の所定の間隔でフラッシュされる、と規定する。すなわち、各々のＬＳＡの新規のバージョンが当該間隔で送出される。この場合、ＬＳＡが３，６００秒以内にフラッシュされない場合、当該ＬＳＡは削除された、と他のルータによりみなされるであろう。
【０００４】
【発明が解決しようとする課題】
これはシンプルな固定間隔処理モードである。このモードにおいては、ＬＳＡが生成された１，８００秒後に、ネットワーク・デバイスが当該ＬＳＡの新規のバージョンを送出するであろう。すなわち、一度にフラッシュするであろう。ｔｙｐｅ　５　ＬＳＡの数が非常に多い場合、フラッシング処理がネットワーク・バンドワイズ・リソースの多くを占めるであろう点で、このモードは好ましくない。これによれば、ネットワーク・トラフィックは低減され、他のネットワーク・デバイスの処理に影響する。
【０００５】
ネットワーク・デバイスが数十万のｔｙｐｅ　５　ＬＳＡを一度に生成するならば、ＬＳＡの全ては１，８００秒後に同時にフラッシュされるであろう。その際、数万のパケットがネットワークに発生する。ネットワークがこのような集中的なトラフィックに耐えることができず、パケットの一部が失われ、当該パケットが複数回送信しなおされるであろうことが容易に予測される。さらに、他のデバイスに影響するこのネットワークのネットワーク・デバイスの全てに、フラッシュされたＬＳＡは伝搬される。特に、処理能力の低いネットワーク・デバイスは、ブロックされ、応答せず、サービスを停止するかもしれない。
【０００６】
【課題を解決するための手段】
ネットワークにおけるトラフィックの影響を低減するために、及び、安定したオペレーションを確保するために、本発明は、ＯＳＰＦプロトコルにおけるｔｙｐｅ　５　ＬＳＡの分離セットによるフラッシング方法を提供することを目的とする。
【０００７】
本発明の方法は、以下のステップ（１）〜（４）を含む。
（１）ＯＳＰＦプロトコルを実行するネットワーク・デバイスに多量のｔｙｐｅ　５　ＬＳＡがある場合、マッピング手法によりＬＳＡの全てをＳセットに均等に分離し、各々のセットを１〜Ｓのナンバーでナンバリングする。すなわち、ＬＳＡのＩＤ値は１〜Ｓの範囲のナンバーにマッピングされる。
（２）ネットワーク・デバイスにおいて、１〜Ｓであるカレント処理セットのナンバーをＮとして記録する。
（３）セットの各々について、ネットワーク・フラッシング間隔をＳにより除した長さのフラッシング間隔の間待機する。
（４）Ｎ番目のセットの全てのＬＳＡをフラッシュし、Ｎに１を加え、ＮがＳより大きいか否か判断し、ＮがＳより大きいならば、Ｎに１をセットしてステップ（３）に戻り、ＮがＳより大きくないならば、ステップ（３）及びステップ（４）に直接戻る。
【０００８】
上記方法において、ＯＳＰＦプロトコルを実行するネットワーク・デバイスは、ルータ、又は、イーサネット（登録商標）・レベル３エクスチェンジであってよく、ネットワーク・フラッシング間隔は、ＩＥＴＦ　ＲＦＣ　２３２８により定義されている。
【０００９】
上記方法において、マッピング手法は、ＬＳＡのＩＤ値をＳで除した剰余に１を加えることを含んでもよい。さらに、マッピング手法は、以下のステップａ〜ｃを含んでもよい。
ａ．ＬＳＡのＩＤ値をＰバイトに分割する（Ｐは偶数）。
ｂ．最初のＰ／２バイトと最後のＰ／２バイトとで排他的論理和を行う。
ｃ．排他的論理和の結果をＳにより除した剰余に１を加える、
【００１０】
本発明の方法は、瞬間的なトラフィックのネットワークへの影響を低減することができる。トラフィックは異なる時点に効果的に分散され、ネットワークは常に低レベル負荷をキープする。本方法によれば、ＯＳＰＦプロトコルを実行することは、ネットワーク・トラフィックのピークにおけるバースト・アウトの原因とはならない。本方法は、ネットワークの他のネットワーク・デバイスへの影響を回避し、ネットワーク・デバイスの全てのオペレーションを安定させ、たいへん効果的にする。ｔｙｐｅ　５　ＬＳＡの全ては、分離セットの処理完了後、１，８００秒以内に一度にフラッシュされる。これによれば、ＯＳＰＦプロトコル・メカニズムの通常のオペレーションが保証される。
【００１１】
【発明の実施の形態】
本発明は、２つの実施の形態を参照して、以下に詳細に記載される。
【００１２】
第１の実施の形態において、本発明はルータでなされる。
【００１３】
ルータは１０，０００のＬＳＡを生成する、とする。第一に、ＬＳＡの全てを２５１のセットに分離する。すなわち、１〜２５１までの範囲のナンバーにＬＳＡの全てのＩＤ値をマッピングする。マッピング方法としては、モジュール演算を使用することができる。すなわち、ＬＳＡのＩＤ値を２５１で除した剰余に１を加えればよい。ＬＳＡの全てはこのステップの後、１〜２５１のセット・ナンバーを有する２５１のセットに均等に分離される。
【００１４】
第二に、ルータにＮとしてカレント・セットのナンバーを記録する。Ｎの初期値として１がセットされる。
【００１５】
第三に、７秒間待機し（７は１，８００を２５１により除したおよその値である）、セット１のＬＳＡの全てを処理し、フラッシュする。次に、現在１であるＮの値に１を加え、セット２のＬＳＡをフラッシュする。このような処理を繰り返し、Ｎの値が２５１を越えると、当該Ｎの値は再び１にセットされる。さらに７秒待機した後、セット１から上記手順をリピートする。
【００１６】
本発明が適用される前は、１０，０００のＬＳＡが一度にフラッシュされる必要があった。これは、ネットワークに影響を与えるだろう。すなわち、当該ネットワークはある程度ブロックされるかもしれない。従来技術と異なり、本発明では、ＬＳＡは７秒ごとに略４０回だけ（１０，０００を２５１により除したおよその値）フラッシュされる。
【００１７】
第２の実施の形態において、本発明はイーサネット（登録商標）・レベル３・エクスチェンジでなされる。
【００１８】
イーサネット（登録商標）・レベル３・エクスチェンジが１００，０００のＬＳＡを生成する、とする。第一に、ＬＳＡの全てを１，０００セットに分離する。すなわち、ＬＳＡの全てのＩＤ値を１〜１，０００の範囲のナンバーにマッピングする。マッピング方法としては、以下に詳細に説明されるオーバーラップ排他的論理和を使用することができる。
ａ．　３２ビット整数であるＬＳＡのＩＤ値を４つのバイトに分割する。
ｂ．　最初の２バイトと最後の２バイトとで排他的論理和演算を行い、新規の１６ビット整数を取得する。
ｃ．　ステップｂの取得結果を１，０００により除した剰余に１を加算する。
【００１９】
ＬＳＡの全ては１〜１，０００のセット・ナンバーを有する１，０００セットに分離される。
【００２０】
第二に、イーサネット（登録商標）・レベル３・エクスチェンジにＮとしてカレント・セットのナンバーを記録する。Ｎの初期値として１がセットされる。
【００２１】
第三に、１．８秒間待機し（１．８は１，８００を１，０００により除した値である）、セット１のＬＳＡの全てをフラッシュする。次に、現在１であるＮの値に１を加え、セット２のＬＳＡをフラッシュする。このような処理を繰り返し、Ｎの値が１，０００を越えると、当該Ｎの値は再び１にセットされる。さらに１．８秒待機した後、セット１から上記手順をリピートする。
【００２２】
本発明が適用される前は、１００，０００のＬＳＡが毎回フラッシュされた。これは、ネットワークに多大な影響を与えるだろう。例えば、この影響により、ネットワークは一時的に停止するかもしれず、ネットワーク・デバイスのいくつかは応答を停止するかもしれない。本方法によれば、ＬＳＡは１．８秒ごとに略１，０００回だけ（１００，０００を１，０００により除した値）フラッシュされる。これによれば、ルート情報の数十のメッセージだけが送出される。これはネットワーク・リンクの動作に影響せず、効果的にネットワーク・デバイスを保護する。
【００２３】
本発明の方法は、たいへん効果的であり、様々なタイプのルータ及びエクスチェンジに適用することができる。上記マッピング方法はモジュール演算もしくはオーバーラップ排他的論理和であってよい。しかしながら、本発明は開示された実施の形態に限定されるものではなく、本発明の精神及び範囲に含まれる様々な修正および均等をカバーすることを意図するものである。