(57)【要約】【課題】低負荷および低消費電力で、ネットワークスイッチ装置内のテーブルを運用する。【解決手段】テーブルは、ネットワーク上のノードの識別番号と、当該ノードの経路情報を関連付けて保持する。除算部１１０は、ネットワーク上のノードから受信したデータに含まれる送信元ノードの識別番号を、当該テーブルに確保された格納領域の数以下の素数で除算する。登録部１２０は、送信元ノードの識別番号の剰余をテーブルのアドレスとして、当該アドレスが指し示す格納領域に、送信元ノードの識別番号と当該ノードへの経路情報を登録する。【選択図】図２
2016025520.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上のノードの識別番号と、当該ノードの経路情報を関連付けて保持するためのテーブルと、
ネットワーク上のノードから受信したデータに含まれる送信元ノードの識別番号を、前記テーブルに確保された格納領域の数以下の素数で除算する除算部と、
前記送信元ノードの識別番号の剰余を前記テーブルのアドレスとして、当該アドレスが指し示す格納領域に、前記送信元ノードの識別番号と当該ノードへの経路情報を登録する登録部と、
を備えることを特徴とするネットワークスイッチ装置。
【請求項２】
前記除算部は、前記送信元ノードの識別番号を、前記テーブルに確保された格納領域の数に近似する素数で除算することを特徴とする請求項１に記載のネットワークスイッチ装置。
【請求項３】
前記テーブルに確保された格納領域の数は、必要な格納領域の数の２倍以上に設定されることを特徴とする請求項１または２に記載のネットワークスイッチ装置。
【請求項４】
前記除算部は、受信したデータに含まれる送信元ノードの識別番号を、それぞれ異なる複数の素数で除算し、
前記登録部は、導出された複数の剰余がアドレスとして指し示す複数の格納領域の内、既に別のノードの識別番号および経路情報が登録されている格納領域を除き、優先順位が高い素数で除算された剰余がアドレスとして指し示す格納領域に、前記送信元ノードの識別番号と当該ノードの経路情報を登録することを特徴とする請求項１から３のいずれかに記載のネットワークスイッチ装置。
【請求項５】
前記送信元ノードの識別番号の剰余が指し示す格納領域に、既に別のノードの識別番号及び経路情報が登録されている状態をコリジョンと呼ぶとき、
前記送信元ノードの識別番号をそれぞれ除算すべき素数の数は、前記ノードの識別番号に割り当てられる数の範囲、前記テーブルに確保された格納領域の数、及び許容するコリジョンの発生確率にもとづき決定されることを請求項４に記載のネットワークスイッチ装置。
【請求項６】
前記送信元ノードの識別番号は、前記送信元ノードのＭＡＣ（Media Access Control）アドレスであることを特徴とする請求項１から５のいずれかに記載のネットワークスイッチ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レイヤ２スイッチ（以下、Ｌ２スイッチという）等のネットワークスイッチ装置に関する。
【背景技術】
【０００２】
Ｌ２スイッチはＯＳＩ参照モデルのデータリンク層で動作する装置であり、ポートごとにコリジョンドメインを分割する。Ｌ２スイッチはフレーム単位でデータを扱い、フレームに付加された宛先ノードのＭＡＣ（Media Access Control）アドレスを参照して、フレームを転送する。フレームを転送するためにＬ２スイッチは、ＭＡＣアドレステーブルを保持する。ＭＡＣアドレステーブルには、ポート番号と、そのポートに接続されているノードのＭＡＣアドレスを少なくとも含む情報が登録される。初期状態ではＭＡＣアドレステーブルは空の状態であり、学習によりエントリを増やしていく。ＭＡＣアドレステーブルは、ＣＡＭ(Content Addressable Memory)と呼ばれるメモリチップで構成されることが一般的である（ＣＡＭを使用した中継装置として、例えば特許文献１参照）。ＣＡＭでは入力フレーム内の送信先アドレスと、テーブル内に登録されているアドレスとを全ビット比較して、一致するアドレスを検索する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−３６８７９３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
近年のネットワークの高速化に伴いＣＡＭのサーチ速度の不足、高速メモリ検索による消費電力の増大が問題となっている。ＭＤ（Message Digest）５等のハッシュ関数を用いてアドレス空間を圧縮する方式もあるが、このような複雑な演算処理を、高速処理が要求されるフレーム転送処理に適用すると負荷および消費電力が増大する。
【０００５】
本発明はこうした状況に鑑みてなされたものであり、その目的は、低負荷および低消費電力で、ネットワークスイッチ装置内のテーブルを運用する技術を提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明のある態様のネットワークスイッチ装置は、ネットワーク上のノードの識別番号と、当該ノードの経路情報を関連付けて保持するためのテーブルと、ネットワーク上のノードから受信したデータに含まれる送信元ノードの識別番号を、前記テーブルに確保された格納領域の数以下の素数で除算する除算部と、前記送信元ノードの識別番号の剰余を前記テーブルのアドレスとして、当該アドレスが指し示す格納領域に、前記送信元ノードの識別番号と当該ノードへの経路情報を登録する登録部と、を備える。
【０００７】
なお、以上の構成要素の任意の組合せや、本発明の構成要素や表現を方法、装置、システム、プログラムなどの間で相互に置換したものもまた、本発明の態様として有効である。
【発明の効果】
【０００８】
本発明によれば、低負荷および低消費電力で、ネットワークスイッチ装置内のテーブルを運用できる。
【図面の簡単な説明】
【０００９】
【図１】図１（ａ）−（ｃ）は、Ｌ２スイッチによるＭＡＣアドレスの学習処理を説明するための図である。
【図２】本発明の実施の形態に係るＬ２スイッチの構成を示す図である。
【図３】登録部の処理を説明するためのフローチャートである。
【図４】図３のフローチャートのデータ判定処理のサブルーチンである。
【図５】ＭＡＣアドレステーブルの格納領域のフォーマットを示す図である。
【図６】被除数、除数、及びエントリ領域の関係を示す図である。
【図７】被除数の範囲が０〜２＾４６の場合における、除算関数の数の決定テーブルを示す図である。
【図８】図８（ａ）−（ｂ）は、図７のテーブルをグラフ化した図である。
【発明を実施するための形態】
【００１０】
図１（ａ）−（ｃ）は、Ｌ２スイッチ１００によるＭＡＣアドレスの学習処理を説明するための図である。図１（ａ）−（ｃ）では、Ｌ２スイッチ１００が４つのポートＰ１〜Ｐ４を備える例を考える。図１（ａ）に示すように第１ポートＰ１にはノードＡ２００ａが、第２ポートＰ２にはノードＢ２００ｂが、第３ポートＰ３にはノードＣ２００ｃが、第４ポートＰ４にはノードＤ２００ｄがそれぞれ接続されている。初期状態では、Ｌ２スイッチ１００内のＭＡＣアドレステーブルは空である。この状態にて例えば、ノードＢ２００ｂがノードＣ２００ｃにＭＡＣフレームを送信した場合を考える。
【００１１】
図１（ｂ）は、ＭＡＣフレームの一例としてＤＩＸ仕様のイーサネット（登録商標）フレームのフォーマットを示す。図１（ｂ）に示すようにイーサネットフレームには、宛先ＭＡＣアドレス及び送信元アドレスが含まれる。図１（ａ）の例では宛先ＭＡＣアドレスにノードＣ２００ｃのＭＡＣアドレス、送信元アドレスにノードＢ２００ｂのＭＡＣアドレスが格納される。
【００１２】
Ｌ２スイッチ１００は、第２ポートＰ２から当該フレームを受信すると、そのポート番号と、当該フレーム内の送信元ＭＡＣアドレスを関連付けてＭＡＣアドレステーブル１５０に登録する。図１（ｃ）は、ノードＢ２００ｂのＭＡＣアドレス登録後のＭＡＣアドレステーブル１５０を示している。ノードＢ２００ｂから送信されたフレームは、第２ポートＰ２に着信したため、ノードＢ２００ｂの経路情報として第２ポートＰ２を登録している。以下、この学習処理を繰り返すことによりＭＡＣアドレステーブル１５０のエントリ数を増加させていく。
【００１３】
図２は、本発明の実施の形態に係るＬ２スイッチ１００の構成を示す図である。実施の形態に係るＬ２スイッチ１００は、ポート部Ｐ、除算部１１０、登録部１２０、転送部１３０及びＭＡＣアドレステーブル１５０を備える。
【００１４】
ＭＡＣアドレステーブル１５０は、ネットワーク上のノードのＭＡＣアドレスと、当該ノードの経路情報を関連付けて保持する。ＭＡＣアドレステーブル１５０が確保すべき必要な格納領域の数は、Ｌ２スイッチ１００を使用するネットワークの規模などを考慮して設計者により決定される。本実施の形態では必要な格納領域の数として２＾２０（≒１００００００）を想定する。本実施の形態ではＭＡＣアドレステーブル１５０に、必要な格納領域の数より大きい数の格納領域を確保する。例えば、必要な格納領域の数の２倍以上の数の格納領域を確保する。上記の２＾２０の格納領域が必要な場合、例えばその２倍の２＾２１の格納領域を確保する。格納領域を必要数より大きくする趣旨は後述する。
【００１５】
ポート部Ｐは図１（ａ）に示したように複数のポートを実装する。除算部１１０は、ポート部Ｐを介してネットワーク上のノードから受信したフレームに含まれる送信元ノードのＭＡＣアドレスを、ＭＡＣアドレステーブル１５０に確保された格納領域の数以下の素数で除算する。登録部１２０は当該送信元ノードのＭＡＣアドレスの剰余をＭＡＣアドレステーブル１５０のアドレスとして、当該アドレスが指し示す格納領域に、当該送信元ノードのＭＡＣアドレスと当該ノードの経路情報を登録する。ノードのＭＡＣアドレスを、そのままＭＡＣアドレステーブル１５０のアドレスとして使用せず、ノードのＭＡＣアドレスを素数で除算して得られる剰余をアドレスとして使用する。これによりＭＡＣアドレステーブル１５０の必要な格納領域の数を削減できる。
【００１６】
当該素数として、ＭＡＣアドレステーブル１５０に確保された格納領域の数に近似する素数（より好ましくは当該格納領域の数に最も近い素数）を使用することが望ましい。上述のように２＾２１（＝２０９７１５２）の格納領域が確保される場合、当該素数として２０９７１４３を使用することが望ましい。なお格納領域の数より大きな素数を使用すると、格納領域のアドレスとして存在しない剰余が発生する場合がある。格納領域の数から離れた素数を用いてもよいが、格納領域の数から離れるほど、使用されない格納領域が増大する。
【００１７】
除算部１１０は、ポート部Ｐを介して受信したフレームに含まれる送信元ノードのＭＡＣアドレスをそれぞれ異なる複数の素数で除算し、導出される複数の剰余を登録部１２０に出力する。また除算部１１０は、ポート部Ｐを介して受信したフレームに含まれる送信先ノードのＭＡＣアドレスをそれぞれ異なる複数の素数で除算し、導出される複数の剰余を転送部１３０に出力する。複数の素数で除算するために図２に示す除算部１１０は、複数の除算エンジン１１〜１Ｎを備える。素数による除算をソフトウェアで演算すると相対的に時間がかかるため、リアルタイム性が要求されるネットワークスイッチでは複数のハードウェアエンジンを設けて並列処理することが望ましい。
【００１８】
複数の素数は、ＭＡＣアドレステーブル１５０に確保された格納領域の数より小さく、かつ当該格納領域の数に近い順に選定されることが好適である。例えば、２＾２１（＝２０９７１５２）の格納領域が確保される場合で、８個の素数で８通りの除算が行われる場合、複数の素数として２０９７１４３，２０９７１３３，２０９４１３１，２０９７０９７，２０９７０９１，２０９７０８３，２０９７０４７，２０９７０４１を使用する。
【００１９】
登録部１２０は、除算部１１０から入力される送信元ＭＡＣアドレスの複数の剰余（アドレス）が指し示す複数の格納領域の内、既に別のノードのＭＡＣアドレスおよび経路情報が登録されている格納領域を除き、優先順位が高い素数で除算された剰余（アドレス）が指し示す格納領域に、当該送信元ノードのＭＡＣアドレスと当該ノードの経路情報を登録する。以下、具体的に説明する。登録部１２０は比較判定部２１及びリード／ライト部２２を含む。
【００２０】
図３は、登録部１２０の処理を説明するためのフローチャートである。図４は、図３のフローチャートのデータ判定処理（Ｓ２０）のサブルーチンである。比較判定部２１は、除算部１１０から入力される送信元ＭＡＣアドレスの複数の剰余に対応する複数のアドレスに格納されたデータのリード要求をリード／ライト部２２に発行する（Ｓ１０）。リード／ライト部２２は当該リード要求に応じて、指定された複数のアドレスにそれぞれ格納さているデータを読み出し、比較判定部２１に渡す。比較判定部２１は、リード／ライト部２２から受け取ったデータの判定処理を実行する（Ｓ２０）。図４のサブルーチンを説明する前に、ＭＡＣアドレステーブル１５０の格納領域のフォーマットを説明する。
【００２１】
図５は、ＭＡＣアドレステーブル１５０の格納領域のフォーマット１５０ｉを示す図である。本実施の形態ではＭＡＣアドレステーブル１５０の格納領域に使用フラグ領域、ＭＡＣアドレス領域、除算関数番号領域、及び経路情報領域を含む。使用フラグ領域は、当該格納領域にデータが格納されているか否かを示すフラグが設定される領域である。例えば「０」が未使用、「１」が使用を示す。除算関数番号領域には、格納領域のアドレスの導出に使用した複数の除算関数の内、アドレスとして選択された剰余を導出した除算関数の識別番号が格納される。本実施の形態では複数の除算エンジン１１〜１Ｎの内、その剰余がアドレスとして採用された除算エンジンの識別番号が格納される。
【００２２】
図５に示す格納データ１５１〜１５Ｎは、リード／ライト部２２が比較判定部２１からのリード要求に応じて、指定された複数のアドレスのそれぞれから読み出したデータを示している。格納データ１５１、１５Ｎのように、まだエントリされていない格納領域のデータは使用フラグが「０」であり、他の領域は空である。格納データ１５２のようにエントリ済みの格納領域のデータは使用フラグが「１」であり、登録されたＭＡＣアドレス、除算関数番号および経路情報を含んでいる。
【００２３】
図４に戻る。比較判定部２１は、リード／ライト部２２から受け取った各格納データから使用フラグの値を抽出する（Ｓ２１）。使用フラグの値が「０」のデータについては（Ｓ２２のＮ）、何も処理しない。使用フラグの値が「１」のデータについては（Ｓ２２のＹ）、そのデータに格納されているＭＡＣアドレスと、外部から受信した送信元ＭＡＣアドレスが比較される（Ｓ２３）。両アドレスが一致している場合（Ｓ２３のＹ）、アドレス一致フラグに「１」が設定され（Ｓ２４）、一致していない場合（Ｓ２３のＮ）、アドレス一致フラグに「０」が設定される（Ｓ２５）。図４に示す処理は、除算エンジンの数に対応した複数のロジック回路で並列に実行されることが好適である。
【００２４】
図３に戻る。比較判定部２１は複数の格納データの内、アドレス一致フラグが「１」のデータが存在するか否か判定する（Ｓ３０）。存在する場合（Ｓ３０のＹ）、ＭＡＣアドレスの登録処理を終了する。この場合、今回受信した送信元ＭＡＣアドレスが、ＭＡＣアドレステーブル１５０に既に登録されているため新たな登録処理は発生しない。
【００２５】
アドレス一致フラグが「１」のデータが存在しない場合（Ｓ３０のＮ）、比較判定部２１は、使用フラグが「０」の格納データのアドレスの内、最も優先順位が高い除算エンジンで算出されたアドレスを選択する（Ｓ４０）。除算エンジンの優先順位の具体例は後述する。比較判定部２１は、選択したアドレスのデータ領域に、今回受信した送信元ＭＡＣアドレス、経路情報、採用した剰余を導出した除算エンジンの識別番号の書き込みをリード／ライト部２２に要求する（Ｓ５０）。リード／ライト部２２はそれらの情報を、指定されたアドレスのデータ領域に書き込む。
【００２６】
図２に戻る。転送部１３０は転送制御部３１及びリード部３２を含む。転送制御部３１は、ポート部Ｐを介してネットワーク上のノードから受信したフレームに含まれる送信先ノードのＭＡＣアドレスを確認する。また転送制御部３１は、除算部１１０から入力される送信先ＭＡＣアドレスの複数の剰余に対応する複数のアドレスに格納されたデータのリード要求をリード部３２に発行する。リード部３２は当該リード要求に応じて、指定された複数のアドレスにそれぞれ格納さているデータを読み出し、転送制御部３１に渡す。
【００２７】
転送制御部３１は、リード部３２から受け取った各格納データから使用フラグの値を抽出する。使用フラグの値が「０」のデータは無視する。使用フラグの値が「１」のデータに格納されているＭＡＣアドレスと、外部から受信した送信先ＭＡＣアドレスを比較する。転送制御部３１は、両アドレスが一致したデータに含まれる除算関数番号と、当該データの格納領域のアドレスを今回導出した除算関数番号を比較する。両除算関数番号が一致する場合、転送制御部３１は、当該データに含まれる経路情報に従い、受信したフレームを転送する。例えば当該経路情報に含まれるポート番号が第３ポートである場合、転送制御部３１は、受信したフレームを第３ポートＰ３から送出する。この処理は、送信先のノードの経路情報が、上述の学習により既にＭＡＣアドレステーブル１５０に登録されている場合の処理である。転送制御部３１は、送信先ノードの登録情報をＭＡＣアドレステーブル１５０から抽出できない場合、受信したフレームを全てのポートからブロードキャストする。
【００２８】
以下、上記処理に使用する、素数を用いたデータの縮退方法について詳細に説明する。エグザクトマッチの母数となるキーの長さをｎビットとする。除数をｍ次の多項式とすると、コリジョンが発生する確率は１／（２＾ｍ）となる。実際は母数がｎビットであるため、被除数の種別が２＾ｎとなり、同じ値となる確率は下記（式１）で表される。
【００２９】
【数１】
2016025520.tif 000003
【００３０】
簡単のため、２回連続で同じ値となる確率を下記（式２）のように定義する。
１／（２＾ｍ））×（１／（２＾ｍ））  ・・・（式２）
【００３１】
同じ値となる確率を例えば１％未満にしたい場合、下記（式３）を満たすようにｍを設定する必要がある。
０．０１＞（１／（２＾ｍ））×（１／（２＾ｍ））  ・・・（式３）
【００３２】
除数とすべき多項式には素数を用いる。以下、母数ｎ＝４６、被除数（母集団）の数＝２＾４６、縮退領域の数＝２＾２１とする例を考える。ＭＡＣアドレスは４８ビットであるが、Ｉ／ＧビットとＧ／Ｌビットを除外して４６ビットと考える。縮退領域の数は、上記のＭＡＣアドレステーブル１５０に確保された格納領域の数に相当する。
【００３３】
縮退関数ｆ（２＾ｎ，ｘ）を除算の剰余（２＾ｎ÷ｘの剰余）で定義する。ｘは除数であり、素数とする。本実施の形態では、縮退領域の数（以下適宜、エントリ数という）＝２＾２１より小さく、エントリ数に近い８種類の素数（２０９７１４３，２０９７１３３，２０９４１３１，２０９７０９７，２０９７０９１，２０９７０８３，２０９７０４７，２０９７０４１）を使用する。即ち、コリジョンの発生確率を低下させるため８種類の縮退関数（上記の除算関数に相当する）を用いる。２＾２１のエントリ領域の使用率を５０％とする。
【００３４】
図６は、被除数、除数、及びエントリ領域の関係を示す図である。図６は上述のように、被除数の範囲が０〜２＾４６、エントリ数が２＾２１の例を描いている。必要エントリ数は２＾２０であり、エントリ領域の使用率を５０％とするため、実際に確保されるエントリ数を２＾２１としている。
【００３５】
除算関数１は被除数を素数（＝２０９７１４３）で除数した剰余で定義され、除算関数２は被除数を素数（＝２０９７１３３）で除数した剰余で定義され、除算関数３は被除数を素数（＝２０９４１３１）で除数した剰余で定義され、除算関数４は被除数を素数（＝２０９７０９７）で除数した剰余で定義され、除算関数５は被除数を素数（＝２０９７０９１）で除数した剰余で定義され、除算関数６は被除数を素数（＝２０９７０８３）で除数した剰余で定義され、除算関数７は被除数を素数（＝２０９７０４７）で除数した剰余で定義され、及び除算関数８は被除数を素数（＝２０９７０４１）で除数した剰余で定義される。図６に示すように素数がエントリ数に近いほど、使用するエントリ領域の範囲が広くなる。剰余の最大値は、素数から１を減算した値となるためである。
【００３６】
除算関数１〜８は、番号が小さい順に優先順位が高く設定される。即ち、除算関数１〜８の剰余（アドレス）でそれぞれアクセスされる複数のエントリ領域の内、未使用でかつ優先順位が高いエントリ領域に、登録すべきデータがエントリされる。
【００３７】
以下、使用する除算関数の数の決定方法について説明する。除算関数の数は、被除数、エントリ数、コリジョンの発生確率にもとづき決定される。本実施の形態では除算関数の数は除算エンジンの数に一致し、ＭＡＣアドレスを除算する素数の数にも一致する。
【００３８】
図７は、被除数の範囲が０〜２＾４６の場合における、除算関数の数の決定テーブルを示す図である。太線（実線）より内側の範囲はコリジョン発生確率が１％未満の、エントリ数と除算エンジンの数の組み合わせを示している。太線（点線）より内側の範囲はコリジョン発生確率が２％未満の、エントリ数と除算エンジンの数の組み合わせを示している。
【００３９】
例えばエントリ数が２＾２０（＝１０４８５７６）の場合、エントリ数が１０５０００に最も近似する。その場合のコリジョン発生確率を１％未満に設定したい場合、このテーブルを参照すると、７個以上の除算エンジンが必要なことが分かる。なおエントリ数が２＾２１（＝２０９７１５２）の場合は図示されていないが、８個以上の除算エンジンを用いれば、コリジョン発生確率を１％未満にできる。
【００４０】
図８（ａ）−（ｂ）は、図７のテーブルをグラフ化した図である。横軸がエントリ数、縦軸がコリジョン発生確率を示す。図８（ｂ）は、図８（ａ）のコリジョン発生確率が１％以下の領域を抜き出した図である。図８（ａ）−（ｂ）から分かるようにコリジョン発生確率を低下させるには、エントリ数を少なくするか、除算エンジン数を多くすればよいことが分かる。
【００４１】
当該コリジョン発生確率は、図１−図５に示した登録処理では、送信元ノードのＭＡＣアドレスの剰余が指し示す格納領域に、既に別のノードのＭＡＣアドレス及び経路情報が登録されている状態が発生したことに相当する。従って図２の除算エンジンの数は、ＭＡＣアドレスに割り当てられている数の範囲、ＭＡＣアドレステーブル１５０に確保された格納領域の数、及び許容するコリジョンの発生確率にもとづき決定されることになる。
【００４２】
以上説明したように本実施の形態によれば、ＭＡＣアドレスに除算関数を適用して、ＭＡＣアドレステーブル１５０のアドレス空間を縮退することにより、低負荷および低消費電力でＭＡＣアドレステーブル１５０を運用できる。
【００４３】
従来、ＭＡＣアドレステーブル１５０にはＣＡＭが使用されることが一般的であったが、近年のネットワークの高速化に伴いＣＡＭのサーチ速度の不足、高速メモリ検索による消費電力の増大が問題となっている。チップベンダでも問題視しており各社独自の方式でサーチエンジンが開発されている。ただし未だ標準化等は行われておらず、市販のサーチエンジンを使用する場合には、自分達の秘密情報である検索内容をチップベンダに開示して該当チップでの可否判断を仰ぐ状態で、装置開発において大きな妨げになっている。
【００４４】
ＣＡＭで用いるような全ビット一致比較をやめて、本実施の形態のように除算関数を用いた縮退方式を用いてサーチエンジンを形成することで、高速かつ低消費電力なサーチエンジンを自己管轄下で運用できる。本実施の形態に係る除算関数を用いた縮退方式は、ＭＤ５等のハッシュ関数を用いた縮退方式と比較して演算が単純であるため、負荷および消費電力を低減できる。また以下に説明するようにコリジョンの発生確率も低減できる。
【００４５】
除算関数で使用する除数を素数とすることによりコリジョンの発生確率を低減できる。除数の公倍数以外では、コリジョンが発生しない性質を利用している。ＭＡＣアドレステーブル１５０に確保する格納領域の数を、必要な格納領域の数より大きくする（例えば２倍にする）ことにより、コリジョンの発生確率を低減できる。未使用の格納領域の数が減ってくると、コリジョンの発生確率が加速度的に増加する。格納領域の数を、必要な格納領域の数より大きくすることにより、これを回避できる。また除数に使用する素数を、格納領域の数に近い値に設定することにより、使用する格納領域が限定されることを防止できる。また最小公倍数の散発を防止できる。
【００４６】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００４７】
上述の実施の形態では、ネットワーク上のノードのＭＡＣアドレスの縮退について説明したが、ＭＡＣアドレス以外の識別番号の縮退についても本発明を適用できる。例えば専用線で接続される複数のノードに、その専用線サービス特有の識別番号がそれぞれ割り当てられる場合、その識別番号の縮退に本発明に係る縮退方式を適用できる。なおＩＰアドレスはロンゲストマッチが必要であるため、本発明に係る縮退方式は適していない。
【符号の説明】
【００４８】
１００  Ｌ２スイッチ、  ２００ａ  ノードＡ、  ２００ｂ  ノードＢ、  ２００ｃ  ノードＣ、  ２００ｄ  ノードＤ、  Ｐ  ポート部、  Ｐ１  第１ポート、  Ｐ２  第２ポート、  Ｐ３  第３ポート、  Ｐ４  第４ポート、  １１０  除算部、  １１  第１除算エンジン、  １２  第２除算エンジン、  １Ｎ  第Ｎ除算エンジン、  １２０  登録部、  ２１  比較判定部、  ２２  リード／ライト部、  １３０  転送部、  ３１  転送制御部、  ３２  リード部、  １５０  ＭＡＣアドレステーブル。
【図１】
2016025520.tif 000004
【図２】
2016025520.tif 000005
【図３】
2016025520.tif 000006
【図４】
2016025520.tif 000007
【図５】
2016025520.tif 000008
【図６】
2016025520.tif 000009
【図７】
2016025520.tif 000010
【図８】
2016025520.tif 000011