JP5610227B2

JP5610227B2 - 計算機及び識別子管理方法

Info

Publication number: JP5610227B2
Application number: JP2011111834A
Authority: JP
Inventors: 健二藤平; 芦　賢浩; 賢浩芦; 誠由高瀬
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2011-05-18
Filing date: 2011-05-18
Publication date: 2014-10-22
Anticipated expiration: 2031-05-18
Also published as: CN102843287B; US20120294307A1; JP2012244364A; US8886913B2; CN102843287A

Description

本発明は、計算機に関し、特に、ユーザ毎に通信接続を管理する通信システムにおいて、ユーザ識別子を変換する計算機に関する。

企業内ネットワークで流通する情報量は年々増加し、企業ユーザ向け通信サービスの重要性がますます高くなっている。そこで、通信事業者は企業ユーザに対し、複数拠点に配置された企業内ＬＡＮ（Local Area Network）同士を接続するための通信網を敷設し、企業ユーザ毎に帯域を確保する帯域保証型サービスを提供している。一例として、予め帯域を確保したパスをエンド・トゥー・エンドで確立することにより、帯域保証を実現するＭＰＬＳ−ＴＰ（Multi Protocol Label Switching-Transport Profile）を適用した通信システムの導入を進めている。

また、企業ユーザ向け通信サービスの需要の拡大に従って、多数の企業ユーザ向け通信サービスの管理効率を高めるための広帯域化、及び、重要データ（例えばユーザデータ）を確実に通信するための高い信頼性が要求されている。さらに、通信システムの維持コストを低減するため、通信システムが備える各通信装置の消費電力削減が要求されている。

通信事業者は、１００Ｇｂｐｓ（Gigabit per second）の高速通信をサポートする帯域保証技術の導入を検討している。高速通信を実現するために、各通信装置では、通信事業者網の管理者によって指定されるユーザＩＤ（ユーザ識別子）の値を、装置内で扱う内部ＩＤ（内部識別子）に高速に変換する。

例えば、前述のＭＰＬＳ−ＴＰにおいて、ユーザＩＤの値のとり得る範囲は２０ｂｉｔ、すなわち最大１０４８５７５と標準規定されている。そのため、通信事業者網の管理者によって指定されるユーザＩＤは２０ｂｉｔ値であり、主信号フレームには同じ２０ｂｉｔ値が付与される。しかしながら、通信システムによって管理されるユーザ数は一般的に１０４８５７５よりも小さい。そのため、各通信装置では、通信事業者網の管理者によって指定されるユーザＩＤを、当該通信装置で管理可能なユーザ数をとり得る値の範囲とする内部ＩＤに変換することにより、効率的に高速通信を実現する。

ＣＡＭ（Content Addressable Memory）を用いることによって、ユーザＩＤを内部ＩＤに高速に変換する処理を実現する方式が知られている。しかしながら、ＣＡＭが搭載されたチップは消費電力が大きいため、通信システムの維持コストが大きくなるという問題がある。この問題を解決するための技術として、特許文献１に開示された技術が知られている。

特許文献１には、ＣＡＭを用いずに、値範囲を圧縮するハッシュ関数を用いることによって、ユーザＩＤを内部ＩＤに高速に変換する方式が開示されている。

一般的に、ハッシュ関数を用いる場合には、複数の入力値に対して同一の出力値を出力してしまう事象、いわゆる衝突が発生する。一方、特許文献１に開示された技術によれば、複数のハッシュ関数を用いて並列処理することによって、衝突の発生確率を減らし、且つ、高速に内部ＩＤを決定することができる。

なお、特許文献１に開示された技術では、ユーザＩＤを内部ＩＤに変換する場合に、複数のエントリー表（ハッシュ表）が用いられる。エントリー表は、ユーザ毎のユーザＩＤと内部ＩＤとの対応関係、すなわちユーザ毎の識別子変換に関する情報を管理する。このエントリー表に新規ユーザのエントリー（新規エントリー）を設定する場合には、エントリー表においてエントリー設定可能な箇所に、新規ユーザのユーザＩＤと内部ＩＤの対応関係を設定する。

一方、エントリー表においてエントリー設定可能な箇所がない場合には、既に設定されている設定済みエントリーを再配置した後に、新規エントリーを設定する。なお、エントリー可能な箇所がない場合とは、設定済みエントリー数がエントリー表の数よりも多い場合、すなわち、いずれのエントリー表にも新規エントリーを設定できない場合である。

特表２００３-５１０９６３号公報

ところで、前述のように帯域保証型サービスでは、重要データを確実に通信するための高い信頼性が要求されている。特に、エントリー表に新規エントリーを設定する場合には、設定済みエントリーに係るユーザの通信（識別子変換処理を含む）に影響を与えない必要がある。ここでいう影響とは、例えば通信断やパケットロスの発生である。

しかしながら、特許文献１に開示された技術では、エントリー表に新規エントリーを設定する際に、エントリー表においてエントリー設定可能な箇所がない場合には、前述の再配置処理が実行され、この再配置処理の実行中、設定済みエントリーに係るユーザの通信断及びパケットロスが発生するという課題があった。図１４Ａ〜図１６Ｂを用いて説明する。

図１４Ａは、従来技術におけるエントリー再配置前のエントリー表Ｅ１（４１）の一例を示す図である。図１４Ｂは、従来技術におけるエントリー再配置前のエントリー表Ｅ２（４２）の一例を示す図である。例えば図１４Ａ及び図１４Ｂに示す２つのエントリー表Ｅ１、Ｅ２が存在すると仮定する。

エントリー表Ｅ１（４１）は、ハッシュ関数Ｈ１のハッシュ出力値Ａ１（７０１）、ユーザＩＤ“Ｌ０”（７０２）、内部ＩＤ（７０３）の対応関係を管理する。ここでは、ハッシュ出力値Ａ１（＝１）と、ユーザＩＤ（＝２）と、内部ＩＤ（＝０）とが対応付けられた１つのエントリー７０５が設定されている。

一方、エントリー表Ｅ２（４２）は、ハッシュ関数Ｈ１と異なるハッシュ関数Ｈ２のハッシュ出力値Ａ２（７０８）、ユーザＩＤ“Ｌ０”（７０９）、内部ＩＤ（７１０）の対応関係を管理する。ここでは、ハッシュ出力値Ａ２（＝０）と、ユーザＩＤ（＝０）と、内部ＩＤ（＝１）とが対応付けられた１つのエントリー７１１が設定されている。

ここで、新たに、ハッシュ出力値Ａ１＝１、且つ、ハッシュ出力値Ａ２＝０のエントリーを設定する場合には、エントリー表Ｅ１、Ｅ２の両エントリー表において、エントリー設定不可能である。そのため、例えばエントリー表Ｅ１において設定済みのエントリー７０５を、エントリー表Ｅ２に再配置（移動）する再配置処理が実行される。

図１５Ａは、従来技術におけるエントリー再配置中のエントリー表Ｅ１（４１）の一例を示す図である。図１５Ｂは、従来技術におけるエントリー再配置中のエントリー表Ｅ２（４２）の一例を示す図である。

図１５Ａに示すエントリー表Ｅ１では、設定済みのエントリー７０５が削除されている。一方、図１５Ｂに示すエントリー表Ｅ２は、図１４Ｂに示すエントリー表Ｅ２と同一である。なお、図１５Ａ及び図１５Ｂに示す再配置中の状態では、エントリー７０５に対応するユーザＩＤ“２”の通信断及びパケットロスが発生する。

図１６Ａは、従来技術におけるエントリー再配置後のエントリー表Ｅ１（４１）の一例を示す図である。図１６Ｂは、従来技術におけるエントリー再配置後のエントリー表Ｅ２（４２）の一例を示す図である。

図１６Ａに示すエントリー表Ｅ１は、図１５Ａに示すエントリー表Ｅ１と同一である。一方、図１６Ｂに示すエントリー表Ｅ２では、再配置処理によって削除されたエントリー７０５が、ハッシュ出力値Ａ２＝２のエントリー７１２に新たに設定されている。これにより、追加すべきハッシュ出力値Ａ１＝１、且つ、ハッシュ出力値Ａ２＝０のエントリーを、エントリー表Ｅ１のエントリー７０５の位置に追加することができる。

なお、エントリー表の数を増やすことにより、ユーザの通信断及びパケットロスの発生確率を下げることが可能である。しかしながら、メモリサイズの制約により、前述の再配置処理を回避するために十分な数のエントリー表を実装することは困難である。

本発明は、上述した問題を考慮したものであって、他ユーザの識別子変換処理に影響を与えることなく、新規ユーザの識別子変換情報（ハッシュ出力値とユーザＩＤと内部ＩＤの対応関係）を設定可能な計算機及び識別子管理方法を提供することを目的とする。

本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機であって、前記メモリは、複数のハッシュ関数と、前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、前記プロセッサは、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報を登録すべきエントリー表を選択することを特徴とする。

本発明によれば、他ユーザの識別子変換処理に影響を与えることなく、新規ユーザの識別子変換情報を設定することができる。

本発明の第１の実施形態の通信システムの構成例を示す図である。本発明の第１の実施形態のノードの構成の一例を示す図である。本発明の第１の実施形態のノードのハードウェア構成例を示す図である。本発明の第１の実施形態のユーザＩＤ処理部による内部ＩＤ付与処理の一例を示す図である。本発明の第１の実施形態のハッシュ関数Ｈ１の一例を示す図である。本発明の第１の実施形態のハッシュ関数Ｈ２の一例を示す図である。本発明の第１の実施形態のエントリー表Ｅ１の一例を示す図である。本発明の第１の実施形態のエントリー表Ｅ２の一例を示す図である。本発明の第１の実施形態のエントリー表Ｅ１の一例を示す図である。本発明の第１の実施形態のエントリー表Ｅ２の一例を示す図である。本発明の第１の実施形態のエントリー数管理表の一例を示す図である。本発明の第１の実施形態のエントリー数管理表の一例を示す図である。本発明の第１の実施形態のエントリー追加処理の一例を示すフローチャートである。本発明の第１の実施形態のエントリー追加処理の一例を示すシーケンス図である。本発明の第２の実施形態のハッシュ関数Ｈ１の一例を示す図である。本発明の第２の実施形態のハッシュ関数Ｈ２の一例を示す図である。本発明の第２の実施形態のエントリー表Ｅ１の一例を示す図である。本発明の第２の実施形態のエントリー表Ｅ２の一例を示す図である。本発明の第２の実施形態のエントリー表Ｅ１の一例を示す図である。本発明の第２の実施形態のエントリー表Ｅ２の一例を示す図である。本発明の第２の実施形態のエントリー数管理表の一例を示す図である。本発明の第２の実施形態のエントリー数管理表の一例を示す図である。本発明の第２の実施形態のエントリー追加処理の一例を示すフローチャートである。従来技術におけるエントリー再配置前のエントリー表Ｅ１の一例を示す図である。従来技術におけるエントリー再配置前のエントリー表Ｅ２の一例を示す図である。従来技術におけるエントリー再配置中のエントリー表Ｅ１の一例を示す図である。従来技術におけるエントリー再配置中のエントリー表Ｅ２の一例を示す図である。従来技術におけるエントリー再配置後のエントリー表Ｅ１の一例を示す図である。従来技術におけるエントリー再配置後のエントリー表Ｅ２の一例を示す図である。

以下、本発明の実施形態を添付図面に基づいて説明する。

（第１の実施形態）
図１は、本発明の第１の実施形態の通信システム１００の構成例を示す図である。本発明の第１の実施形態の通信システム１００は、帯域保証網Ｎ１、及び、帯域保証網Ｎ１を管理する網管理装置６を備える。帯域保証網Ｎ１は、複数のノード（通信装置、計算機）１、２、３を備える。

ノード１は、ノード２、及び、ノード４と接続する。ノード４は、アクセス網Ｎ２が備える通信装置である。ノード１は、ノード４から受信した主信号フレーム７にユーザＩＤを付与することによって、主信号フレーム８を生成し、ノード２に送信する。ユーザＩＤは、帯域保証網Ｎ１の管理者、及び、ノード１、２、３によってユーザ毎に一意に定められ、ユーザ識別の際に用いられる識別子である。ここでいうユーザとは、例えば会社、会社内の部署等の組織単位のユーザでもよいし、個人単位のユーザでもよい。

ノード２は、ノード１、及び、ノード３に接続する。ノード２は、ノード１から主信号フレーム８を受信し、受信した主信号フレーム８に付与されたユーザＩＤを解析する。すなわち、付与されたユーザＩＤに応じて、帯域保証網Ｎ１の管理者によって予め設定された送信先であるノード３を特定する。その後、主信号フレーム８と同一の主信号フレーム９をノード３に送信する。

ノード３は、ノード２、及び、ノード５と接続する。ノード５は、アクセス網Ｎ３が備える通信装置である。ノード３は、ノード２から主信号フレーム９を受信し、受信した主信号フレーム９に付与されたユーザＩＤを解析する。すなわち、付与されたユーザＩＤに応じて、帯域保証網Ｎ１の管理者によって予め設定された送信先であるノード５を特定する。その後、主信号フレーム９に付与されたユーザＩＤを削除することによって、主信号フレーム１０を生成し、ノード５に送信する。

帯域保証網Ｎ１の管理者は、網管理装置６を用いて、ユーザＩＤに応じた通信経路を予め設定する。通信経路の設定方式としては、例えばＭＰＬＳ−ＴＰを用いる。

網管理装置６は、インターネット等のネットワークを介して、ノード１、２、３に接続される。網管理装置６は、入出力インタフェースとしてのディスプレイ、キーボード、マウス等（不図示）を備える。帯域保証網Ｎ１の管理者は、網管理装置６が備える入出力インタフェースを用いて、主信号フレーム７の通信経路、すなわち、ノード１からノード２及びノード３を経由してノード５に到達する通信経路を設定する。

図２は、本発明の第１の実施形態のノード１（２、３）の構成の一例を示す図である。なお、以下では、ノード１を例に説明するが、ノード２、３も同様である。

ノード１は、監視制御部２１、インタフェース部２２ａ、２２ｂ、及び、スイッチ部２３を備える。

監視制御部２１は、ノード１の動作を監視制御する。監視制御部２１は、監視制御インタフェース２４、通信経路設定部２５、複数のハッシュ関数２８ｃ、複数のエントリー表２９ｃ、及び、エントリー数管理表３０を備える。

監視制御インタフェース２４は、網管理装置６と接続するためのインタフェース装置である。例えばＳＮＭＰ（Simple Network Management Protocol）によって、網管理装置６と通信する。

通信経路設定部２５は、帯域保証網Ｎ１の管理者が網管理装置６を用いて設定した通信経路をノード１に設定する。具体的には、設定された通信経路に対応するユーザＩＤを、インタフェース部２２ａ、２２ｂに反映する。ＭＰＬＳ−ＴＰを用いて通信経路を設定する場合、ユーザＩＤはＭＰＬＳラベル値である。

ハッシュ関数２８ｃは、２０ｂｉｔのユーザＩＤ、すなわち０から１０４８５７５までの範囲の値を、ノード１に設定可能なユーザＩＤ数の範囲の値に変換する、すなわち値範囲を圧縮する関数である。ハッシュ関数２８ｃについては、図５Ａ及び図５Ｂを参照して詳細に後述する。

エントリー表２９ｃは、ユーザ毎のユーザＩＤと内部ＩＤとの対応関係、すなわちユーザ毎の識別子変換に関する情報（識別子変換情報）を管理する表である。具体的には、ハッシュ関数２８ｃの入力値であるユーザＩＤ（入力識別子）と、ユーザＩＤに対するハッシュ関数２８ｃの出力値（値範囲が圧縮された値）と、ユーザＩＤを変換して得られる内部ＩＤ（出力識別子）との対応関係を示す情報を管理する。エントリー表２９ｃについては、図６Ａ〜図６Ｄを参照して詳細に後述する。

エントリー数管理表３０は、複数のエントリー表２９ｃの各々における識別子変換情報の登録状況を管理する。具体的には、複数のエントリー表２９ｃの各々における設定済みエントリーの数を管理する。エントリー数管理表３０については、図７Ａ及び図７Ｂを参照して詳細に後述する。

インタフェース部２２ａは、複数の物理終端部２６ａ、ユーザＩＤ処理部２７ａ、複数のハッシュ関数２８ａ、及び、複数のエントリー表２９ａを備える。このインタフェース部２２ａは、当該ノード１と主信号フレームを送受信する他のノードとの間のインタフェースである。

物理終端部２６ａは、主信号フレームを送受信する物理インタフェースである。複数の物理終端部２６ａが一つのユーザＩＤ処理部２７ａに接続される。

ユーザＩＤ処理部２７ａは、物理終端部２６ａから主信号フレームを受信すると、ハッシュ関数２８ａ、及び、エントリー表２９ａを参照して、受信した主信号フレームに、ユーザＩＤに応じた内部ＩＤを付与する。その後、内部ＩＤが付与された主信号フレームをスイッチ部２３へ送信する。内部ＩＤを付与する処理については、図４を参照して詳細に後述する。

ハッシュ関数２８ａは、ハッシュ関数２８ｃと同一のハッシュ関数である。予めインタフェース部２２と監視制御部２１には、複数の同一のハッシュ関数２８が実装される。

エントリー表２９ａは、エントリー表２９ｃと同一のエントリー表である。監視制御部２１がエントリー表２９ｃを更新すると、更新後のエントリー表２９ｃをインタフェース部２２ａに送信する。インタフェース部２２ａは、監視制御部２１から受信した更新後のエントリー表２９ｃに基づいて、エントリー表２９ａを上書き（更新）する。

スイッチ部２３は、ユーザＩＤ処理部２７ａから、内部ＩＤが付与された主信号フレームを受信すると、当該付与された内部ＩＤと、通信経路設定部２５によって設定された通信経路とに基づいて、宛先を決定する。その後、決定された宛先に対応するユーザＩＤ処理部２７ｂに、内部ＩＤが付与された主信号フレームを送信する。

インタフェース部２２ｂは、複数の物理終端部２６ｂ、ユーザＩＤ処理部２７ｂ、複数のハッシュ関数２８ｂ、及び、複数のエントリー表２９ｂを備える。以下、前述のインタフェース部２２ａとの差異点について説明する。

ユーザＩＤ処理部２７ｂは、スイッチ部２３から主信号フレームを受信すると、主信号フレームに付与された内部ＩＤに基づいて、物理終端部２６ｂを選択する。その後、主信号フレームから内部ＩＤを削除し、選択された物理終端部２６ｂに送信する。

図３は、本発明の第１の実施形態のノード１（２、３）のハードウェア構成例を示す図である。図３に示すノード１は、それぞれバス３１で相互に接続されたメモリ装置３２、演算処理装置３３、インタフェース装置３４を備える。

メモリ装置３２は、図２に示す通信経路設定部２５の機能を実現するためのプログラムを記憶するＲＡＭ（Random Access Memory）等の記憶装置である。このメモリ装置３２は、プログラムの実行に必要なファイル、データ（複数のハッシュ関数２８ｃ、複数のエントリー表２９ｃ、及び、エントリー数管理表３０を含む）等も記憶する。

演算処理装置３３は、メモリ装置３２に格納されたプログラムを実行するＣＰＵ（Central Processing Unit）等の演算処理装置である。インタフェース装置３４は、外部ネットワーク等に接続するためのインタフェース装置である。

なお、ノード１は、例えば入力装置、出力装置、補助記憶装置、及び、記憶媒体に記憶されたデータを読み込むためのドライブ装置（いずれも不図示）を備えてもよい。

図４は、本発明の第１の実施形態のユーザＩＤ処理部２７ａによる内部ＩＤ付与処理の一例を示す図である。ここでは、ユーザＩＤ処理部２７ａが、物理終端部２６ａから受信した主信号フレームに内部ＩＤを付与する手順を説明する。

まずステップ５１において、ユーザＩＤ処理部２７ａは、物理終端部２６ａからユーザＩＤ“Ｌ０”が付与された主信号フレームを受信する（５１）。

次にステップ５２ａ、５２ｂにおいて、ユーザＩＤ処理部２７ａは、複数のハッシュ関数Ｈ１、Ｈ２を用いて、受信した主信号フレームに付与されたユーザＩＤ“Ｌ０”のハッシュ出力値Ａ１、Ａ２をそれぞれ計算する（５２ａ、５２ｂ）。具体的には、ユーザＩＤ“Ｌ０”を複数のハッシュ関数Ｈ１、Ｈ２にそれぞれ入力する。そうすると、値範囲が圧縮されたハッシュ出力値Ａ１（５６ａ）、Ａ２（５６ｂ）が出力される。これにより、ユーザＩＤ処理部２７ａは、ハッシュ出力値Ａ１、Ａ２を取得する。

その後ステップ５３ａ、５３ｂにおいて、ユーザＩＤ処理部２７ａは、予め作成済のエントリー表Ｅ１、Ｅ２を読み出す（５３ａ、５３ｂ）。エントリー表Ｅ１は、ハッシュ出力値Ａ１に対応するエントリー表である。すなわち、ハッシュ出力値Ａ１、ユーザＩＤ、及び、内部ＩＤの対応関係を管理する。一方、エントリー表Ｅ２は、ハッシュ出力値Ａ２に対応するエントリー表である。すなわち、ハッシュ出力値Ａ２、ユーザＩＤ、及び、内部ＩＤの対応関係を管理する。

ユーザＩＤ処理部２７ａは、読み出されたエントリー表Ｅ１を参照し、ハッシュ出力値Ａ１（５６ａ）に対応するユーザＩＤ“Ｌ１”、及び、内部ＩＤ（５７ａ）を取得する。同様に、読み出されたエントリー表Ｅ２を参照し、ハッシュ出力値Ａ２（５６ｂ）に対応するユーザＩＤ“Ｌ２”、及び、内部ＩＤ（５７ｂ）を取得する。

その後ステップ５４において、ユーザＩＤ処理部２７ａは、取得されたユーザＩＤ（５７ａ、５７ｂ）と、ユーザＩＤ“Ｌ０”とを照合する（５４）。その後、ユーザＩＤ“Ｌ０”と一致するユーザＩＤ（２つのユーザＩＤ“Ｌ１”、“Ｌ２”のいずれか）が存在する場合には、当該ユーザＩＤに対応する内部ＩＤを、主信号フレームに付与する（５５）。

以上のように、ユーザＩＤ処理部２７ａは、複数のハッシュ関数Ｈ１、Ｈ２を用いて並列処理することによって、衝突の発生確率を減らし、且つ、高速に内部ＩＤを決定することができる。

図５Ａは、本発明の第１の実施形態のハッシュ関数Ｈ１（２８ｃ−１）の一例を示す図である。図５Ｂは、本発明の第１の実施形態のハッシュ関数Ｈ２（２８ｃ−２）の一例を示す図である。ハッシュ関数２８ｃは、図５Ａに示すハッシュ関数Ｈ１（２８ｃ−１）、及び、図５Ｂに示すハッシュ関数Ｈ２（２８ｃ−２）を含む。

図５Ａ及び図５Ｂでは、ノード１（又は、ノード２、３）に設定可能なユーザＩＤ数が４である場合の入力値（ユーザＩＤ値）と出力値の対応関係を示している。

図５Ａに示すハッシュ関数Ｈ１は、２０ｂｉｔのユーザＩＤ、すなわち０から１０４８５７５までの範囲の値で示される入力値を入力し、入力値に対応する２ｂｉｔの数字、すなわち０から３までの範囲の値で示される出力値Ａ１を均等に出力する。例えば、入力値が（ユーザＩＤ“０”、“１”、“１４”、…）である場合には、出力値Ａ１は０である。

図５Ｂに示すハッシュ関数Ｈ２は、ハッシュ関数Ｈ１と同様に、２０ｂｉｔのユーザＩＤを入力し、入力値に対応する出力値Ａ２を均等に出力する。例えば、入力値が（“０”、“４”、“９”、…）である場合には、出力値Ａ２は０である。

以上に示すハッシュ関数Ｈ１、Ｈ２を用いることにより、通信経路設定部２５は、ユーザＩＤの値範囲を圧縮することができる。

なお、これらハッシュ関数Ｈ１、Ｈ２は、例えばＣＲＣ（Cyclic Redundancy Check）演算や、剰余演算など、論理的な数式を実行するハードウェアとして実装される。また、ノード１はこれら複数のハッシュ関数Ｈ１、Ｈ２を備えることにより、一つのハッシュ関数のみを備える場合と比較して、衝突の発生確率を低減することが可能となる。また、ここではノード１が２つのハッシュ関数Ｈ１、Ｈ２を備える場合について説明してきたが、３つ以上のハッシュ関数を備えてもよい。

図６Ａ及び図６Ｃは、本発明の第１の実施形態のエントリー表Ｅ１（２９ｃ−１）の一例を示す図である。図６Ｂ及び図６Ｄは、本発明の第１の実施形態のエントリー表Ｅ２（２９ｃ−２）の一例を示す図である。エントリー表２９ｃは、図６Ａ（又は図６Ｃ）に示すエントリー表Ｅ１（２９ｃ−１）と、図６Ｂ（又は図６Ｄ）に示すエントリー表Ｅ２（２９ｃ−２）とを含む。

なお、図６Ａ及び図６Ｂは、変更前のエントリー表Ｅ１、Ｅ２である。一方、図６Ｃ及び図６Ｄは、変更後のエントリー表Ｅ１、Ｅ２である。変更前及び変更後については、図８の具体例において後述する。

エントリー表Ｅ１は、図５Ａのハッシュ関数Ｈ１に対応するエントリー表である。すなわち、ハッシュ関数Ｈ１のハッシュ出力値Ａ１（１４１）、ユーザＩＤ“Ｌ０”（１４２）、内部ＩＤ（１４３）の対応関係を管理する。

一方、エントリー表Ｅ２は、図５Ｂのハッシュ関数Ｈ２に対応するエントリー表である。すなわち、ハッシュ関数Ｈ２のハッシュ出力値Ａ２（１４８）、ユーザＩＤ“Ｌ０”（１４９）、内部ＩＤ（１５０）の対応関係を管理する。

以上に示すエントリー表Ｅ１、Ｅ２を用いることにより、通信経路設定部２５は、ハッシュ関数Ｈ１、Ｈ２によって値範囲が圧縮されたユーザＩＤ（ハッシュ出力値Ａ１、Ａ２）を、高速に内部ＩＤに変換することができる。なお、ここではノード１が２つのエントリー表Ｅ１、Ｅ２を備える場合について説明してきたが、ハッシュ関数の数が３つ以上である場合には、ハッシュ関数の数と同じ３つ以上のエントリー表を備えてもよい。

図７Ａ、及び、図７Ｂは、本発明の第１の実施形態のエントリー数管理表３０の一例を示す図である。図７Ａは、変更前のエントリー数管理表３０であり、図６Ａ及び図６Ｂに示すエントリー表Ｅ１、Ｅ２に対応する。一方、図７Ｂは、変更後のエントリー数管理表３０であり、図６Ｃ及び図６Ｄに示すエントリー表Ｅ１、Ｅ２に対応する。

エントリー数管理表３０は、各エントリー表２９ｃの識別子（１８１）、各エントリー表２９ｃにおいて設定済みのエントリー数（１８２）の対応関係、すなわちエントリー表２９ｃ毎のエントリー数を管理する。

図６Ａに示すエントリー表Ｅ１では、設定済みのエントリー数が０である。また、図６Ｂに示すエントリー表Ｅ２では、設定済みのエントリー数が１である。そのため、図７Ａに示すエントリー数管理表３０では、エントリー表Ｅ１の設定済みエントリー数が０、及び、エントリー表Ｅ２の設定済みエントリー数が１として登録されている。

一方、図６Ｃに示すエントリー表Ｅ１では、設定済みのエントリー数が０である。また、図６Ｄに示すエントリー表Ｅ２では、設定済みのエントリー数が２である。そのため、図７Ｂに示すエントリー数管理表３０では、エントリー表Ｅ１の設定済みエントリー数が０、及び、エントリー表Ｅ２の設定済みエントリー数が２として登録されている。

以上のように、エントリー数管理表３０は、各エントリー表２９ｃの設定済みのエントリー数を管理する。これにより、ノード１は、各エントリー表２９ｃにおけるエントリー設定状況に応じて、新規エントリーの登録先のエントリー表２９ｃを選択することが可能となる。

図８は、本発明の第１の実施形態のエントリー追加処理の一例を示すフローチャートである。ここでは、通信経路設定部２５が、エントリー表２９ｃに新規エントリーを追加（登録）する手順を、具体例を用いて説明する。

通信経路設定部２５は、処理開始後（３０１）、網管理装置６から新規ユーザＩＤ（例えば、ユーザＩＤ“Ｌ”）の設定コマンドを受信するまで、待ち状態となる（３０２）。新規ユーザＩＤ“Ｌ”の設定コマンドを受信した場合には（３０２でＹＥＳ）、変数"エントリー先候補"に"なし"を、設定済みエントリー数を表す変数Ｎに０を、カウンタｉに１を、それぞれ初期値として設定する（３０３）。

次に、通信経路設定部２５は、エントリー表Ｅｉにおいて、ハッシュ出力値ＡｉがＨｉ（Ｌ）であるエントリーが空、且つ、変数Ｎの値がエントリー表Ｅｉの設定済みエントリー数以下であるか否かを判定する（３０４）。なお、Ｈｉ（Ｌ）とは、入力値Ｌに対するハッシュ関数Ｈｉの出力値である。

具体的には、まず、エントリー表Ｅ１（図６Ａ）から、ハッシュ出力値Ａ１がＨ１（Ｌ）であるエントリーを検索し、該当するエントリーが空であるか否かを確認する。例えば、ステップ３０２で新規ユーザＩＤ“Ｌ＝２”の設定コマンドを受信した場合には、入力値２に対するハッシュ関数Ｈ１（図５Ａ）の出力値は１である。すなわち、Ｈ１（２）＝１である。そのため、エントリー表Ｅ１（図６Ａ）から、ハッシュ出力値Ａ１が１であるエントリーが空であることを確認する。

次に、エントリー数管理表３０（図７Ａ）を参照し、変数Ｎの値（ここでは初期値０）と、エントリー表Ｅ１の設定済みエントリー数とを比較する。エントリー数管理表３０（図７Ａ）において、エントリー表Ｅ１の設定済みエントリー数は０である。そのため、変数Ｎの値はエントリー表Ｅ１の設定済みエントリー数以下である。以上より、ステップ３０４においてＹＥＳとなる。

ステップ３０４においてＹＥＳの場合には、通信経路設定部２５は、変数“エントリー先候補”に“Ｅｉ”を、変数Ｎに“エントリー表Ｅｉの設定済みエントリー数”を設定する（３０５）。上記具体例では、変数"エントリー先候補"に"Ｅ１"を、変数Ｎにエントリー表Ｅ１の設定済みエントリー数である０を設定する。一方、ステップ３０４においてＮＯの場合には（３０４でＮＯ）、ステップ３０５の処理を実行しない。

ステップ３０６に進むと、通信経路設定部２５は、カウンタｉをインクリメントする（３０６）。上記具体例では、ｉ＝２となる。

その後、通信経路設定部２５は、カウンタｉの値がエントリー表数ｉｍａｘよりも大きいか否かを判定する（３０７）。カウンタｉの値がエントリー表数ｉｍａｘ以下である場合には（３０７でＮＯ）、ステップ３０４に戻って処理を繰り返す。一方、カウンタｉの値がエントリー表数ｉｍａｘよりも大きい場合には（３０７でＹＥＳ）、ステップ３０８に進む。

上記具体例では、カウンタｉの値は２であり、エントリー表数ｉｍａｘの値は２（エントリー表Ｅ１、Ｅ２の２つ）である。そのため、カウンタｉの値はエントリー表数ｉｍａｘ以下であるので（３０７でＮＯ）、ステップ３０４に戻る。

ステップ３０４に戻ると、通信経路設定部２５は、エントリー表Ｅ２（図６Ｂ）から、ハッシュ出力値Ａ２がＨ２（２）であるエントリーを検索し、該当するエントリーが空であるか否かを確認する。入力値２に対するハッシュ関数Ｈ２（図５Ｂ）の出力値は２である。すなわち、Ｈ２（２）＝２である。そのため、エントリー表Ｅ２（図６Ｂ）から、ハッシュ出力値Ａ２が２であるエントリーが空であることを確認する。

次に、エントリー数管理表３０（図７Ａ）を参照し、変数Ｎの値（ここでは０）と、エントリー表Ｅ２の設定済みエントリー数とを比較する。エントリー数管理表３０（図７Ａ）において、エントリー表Ｅ２の設定済みエントリー数は１である。そのため、変数Ｎの値はエントリー表Ｅ２の設定済みエントリー数以下である。以上より、ステップ３０４においてＹＥＳとなる。

ステップ３０５に進み、通信経路設定部２５は、変数“エントリー先候補”に“Ｅ２”を、変数Ｎにエントリー表Ｅ２の設定済みエントリー数である１を設定する（３０５）。その後、カウンタｉをインクリメントしてｉ＝３とする（３０６）。そうすると、カウンタｉの値３はエントリー表数ｉｍａｘ（＝２）よりも大きいので（３０７でＹＥＳ）、ステップ３０８に進む。

以上に示すステップ３０４〜３０７の処理により、通信経路設定部２５は、変数“エントリー先候補”及び変数Ｎを用いて、設定済みエントリー数の最も多いエントリー表を、新規エントリーの登録先候補として決定する。

ステップ３０８では、通信経路設定部２５は、変数"エントリー先候補"の値が"なし"であるか否かを確認する（３０８）。変数“エントリー先候補”の値が“なし”である場合には（３０８でＹＥＳ）、ステップ３１１に進む。一方、変数“エントリー先候補”の値が“なし”でない場合には（３０８でＮＯ）、ステップ３０９に進む。上記具体例では、変数“エントリー先候補”の値は“Ｅ２”であるので（３０８でＮＯ）、ステップ３０９に進む。

ステップ３０９では、通信経路設定部２５は、変数“エントリー先候補”で示されるエントリー表に、ユーザＩＤ“Ｌ”のエントリーを追加し、エントリー数管理表３０を更新する（３０９）。

上記具体例では、変数“エントリー先候補"の値が"Ｅ２"であるので、エントリー表Ｅ２に、ユーザＩＤ“２”のエントリーを追加する。なお、新規エントリーを追加する場合に、新規エントリーに係る内部ＩＤは、全てのエントリー表Ｅ１、Ｅ２においてユニークな値とする。その結果、図６Ａに示すエントリー表Ｅ１、及び、図６Ｂに示すエントリー表Ｅ２は、それぞれ図６Ｃに示すエントリー表Ｅ１、及び、図６Ｄに示すエントリー表Ｅ２に変更する。

また、エントリー数管理表３０を更新する。上記具体例では、エントリー表Ｅ２のエントリー数が１から２に変更されるので、図７Ａに示すエントリー数管理表３０は、図７Ｂに示すエントリー数管理表３０に変更する。

その後ステップ３１０において、通信経路設定部２５は、変更後のエントリー表Ｅ１及びＥ２（エントリー表２９ｃ）の情報を、各インタフェース部２２ａ、２２ｂに送信する（３１０）。各インタフェース部２２ａ、２２ｂは、受信した変更後のエントリー表Ｅ１及びＥ２の情報を、各インタフェース部２２ａ、２２ｂが備えるエントリー表２９ａ、２９ｂに上書き（更新）する。その後ステップ３１７において、監視制御部２１は、通信経路を設定した旨を示す通信経路設定応答６０４を、網管理装置６に送信する（３１７）。

一方、ステップ３０８においてＹＥＳの場合には（３０８でＹＥＳ）、ステップ３１１に進み、通信経路設定部２５は、カウンタｉの値を“１”に設定する（３１１）。

その後、通信経路設定部２５は、エントリー表Ｅｉにおいて、ハッシュ出力値ＡｉがＨｉ（Ｌ）であるエントリーを占有しているユーザＩＤ“Ｌｅ”を、エントリー表Ｅ（ｉ＋１）に再配置可能であるか否かを判定する（３１２）。再配置可能である場合には（３１２でＹＥＳ）、ステップ３１６に進む。

一方、再配置不可能である場合には（３１２でＮＯ）、通信経路設定部２５は、カウンタｉをインクリメントする（３１３）。その後、カウンタｉの値がエントリー表数ｉｍａｘと等しくなるまで、ステップ３１２の処理を繰り返す（３１４）。

カウンタｉの値がエントリー表数ｉｍａｘと等しくなった場合（３１４でＹＥＳ）、通信経路設定部２５は、新規ユーザＩＤ“Ｌ”のエントリー先を確保できるまで、再配置処理を実行する（３１５）。具体的には、図１４Ａ〜図１６Ｂを用いて前述したような再配置処理を実行する。

ステップ３１６に進んだ場合、通信経路設定部２５は、エントリー表２９ｃを再配置し、新規ユーザＩＤ“Ｌ”のエントリーを追加し、エントリー数管理表３０を更新する（３１６）。その後、ステップ３１０に進む。

以上に示す処理により、通信経路設定部２５は、設定済みエントリー数が他のエントリー表２９ｃよりも多いエントリー表２９ｃ、すなわち設定済みエントリー数が最も多いエントリー表２９ｃに優先的に新規エントリーを追加する。その結果、エントリーが追加されたエントリー表２９ｃと、他のエントリー表２９ｃとの間では、設定済みエントリー数の差がさらに大きくなる。すなわち、エントリー表２９ｃ間で設定済みエントリー数に偏りが生じることになる。

これにより、将来エントリーを追加する際の衝突の発生確率を下げることが可能となる。また、衝突が発生した際の再配置処理の実行頻度を削減することにより、主信号フレームの通信断の時間を低減することが可能となる。

また、通信経路設定部２５は、設定済みエントリー数の最も多いエントリー表２９ｃが複数存在する場合には、表番号（Ｅｉ）の大きなエントリー表２９ｃに優先的に新規エントリーを追加する。これにより、表番号の大きなエントリー表２９ｃに多くのエントリーが設定され、表番号の小さなエントリー表２９ｃに少ないエントリーが設定されるように制御することができる。これにより、将来エントリーを追加する際の衝突の発生確率を下げることが可能となる。なお、新規エントリーの追加先は、表番号の大きなエントリー表２９ｃに限定されるものではない。

図９は、本発明の第１の実施形態のエントリー追加処理の一例を示すシーケンス図である。ここでは、帯域保証網Ｎ１の管理者が、網管理装置６を用いて、ノード１、２、３に新規ユーザＩＤ“Ｌ”のエントリーを追加する手順を説明する。

まず、帯域保証網Ｎ１の管理者が、網管理装置６の入出力インタフェースを操作することにより、追加すべき新規ユーザＩＤ“Ｌ”の新規通信経路の設定コマンドを入力する（６０１）。続いて、網管理装置６は、入力されたユーザＩＤ“Ｌ”の値、及び、新規通信経路の情報を含む通信経路設定要求６０２を、ノード１、２、３に送信する。

各ノード１、２、３の通信経路設定部２５は、受信した通信経路設定要求６０２に基づいて、ユーザＩＤ“Ｌ”のエントリー追加処理を実行する（６０３）。ユーザＩＤ“Ｌ”のエントリー追加処理については、前述の図８に示した通りである。

各ノード１、２、３の監視制御部２１は、ステップ６０３のエントリー追加処理が終了すると、通信経路の設定が終了した旨を示す通信経路設定応答６０４を、網管理装置６に送信する。網管理装置６は、通信経路設定応答６０４を受信すると、ユーザＩＤ“Ｌ”の新規通信経路の設定結果を出力（例えばディスプレイ上に表示）する（６０５）。

以上に示す処理により、帯域保証網Ｎ１の管理者は、網管理装置６を用いて、ノード１、２、３に新規ユーザＩＤ“Ｌ”のエントリーを追加することができる。

（第２実施形態）
以下、本発明の第２の実施形態について説明する。なお、以下では、前述の第１の実施形態との差異点を中心に説明する。

前述の第１の実施形態では、エントリー数管理表３０（図７Ａ及び図７Ｂ参照）は、各エントリー表２９ｃのエントリー数を管理した。この第２の実施形態では、エントリー数管理表３０（図１２Ａ及び図１２Ｂ参照）は、各エントリー表２９ｃのエントリー未設定フィールド数である"空き数"を管理する。

図１０Ａは、本発明の第２の実施形態のハッシュ関数Ｈ１（２８ｃ−１）の一例を示す図である。図１０Ｂは、本発明の第１の実施形態のハッシュ関数Ｈ２（２８ｃ−２）の一例を示す図である。ハッシュ関数２８ｃは、図１０Ａに示すハッシュ関数Ｈ１（２８ｃ−１）、及び、図１０Ｂに示すハッシュ関数Ｈ２（２８ｃ−２）を含む。

図１０Ａ及び図１０Ｂでは、ノード１（又は、ノード２、３）に設定可能なユーザＩＤ数が４である場合の入力値（ユーザＩＤ値）と出力値の対応関係を示している。

なお、本発明の第２の実施形態のハッシュ関数Ｈ１、Ｈ２は、２０ｂｉｔのユーザＩＤ、すなわち０から１０４８５７５までの範囲の値を、ノード１（又は、ノード２、３）に設定可能なユーザＩＤ数以下の範囲の値に変換する関数である。

図１０Ａに示すハッシュ関数Ｈ１は、２０ｂｉｔのユーザＩＤ、すなわち０から１０４８５７５までの範囲の値で示される入力値を入力し、入力値に対応する２ｂｉｔの数字、すなわち０から３までの範囲の値で示される出力値Ａ１を均等に出力する。例えば、入力値が（ユーザＩＤ“０”、“１”、“１４”、…）である場合には、出力値Ａ１は０である。

図１０Ｂに示すハッシュ関数Ｈ２は、２０ｂｉｔのユーザＩＤを入力し、入力値に対応する０から２までの範囲の値で示される出力値Ａ２を均等に出力する。例えば、入力値が（“０”、“４”、“９”、…）である場合には、出力値Ａ２は０である。

以上に示すハッシュ関数Ｈ１、Ｈ２を用いることにより、通信経路設定部２５は、ユーザＩＤの値範囲をユーザＩＤ数以下の値の範囲に圧縮することができる。

なお、これらハッシュ関数Ｈ１、Ｈ２は、例えばＣＲＣ（Cyclic Redundancy Check）演算や、剰余演算など、論理的な数式を実行するハードウェアとして実装される。なお、ノード１はこれら複数のハッシュ関数Ｈ１、Ｈ２を備えることにより、一つのハッシュ関数のみを備える場合と比較して、衝突の発生確率を低減することが可能となる。また、ここではノード１が２つのハッシュ関数Ｈ１、Ｈ２を備える場合について説明してきたが、３つ以上のハッシュ関数を備えてもよい。

さらに、本発明の第２の実施形態では、ハッシュ関数Ｈ１、Ｈ２の出力値範囲として、設定可能なユーザＩＤ数よりも小さい値範囲を許容している。また、ハッシュ関数Ｈ１、Ｈ２の出力値の取り得る数が互いに異なる。これにより、実装メモリサイズに応じた柔軟なエントリー表２９の管理が可能となる。

図１１Ａ及び図１１Ｃは、本発明の第２の実施形態のエントリー表Ｅ１（２９ｃ−１）の一例を示す図である。図１１Ｂ及び図１１Ｄは、本発明の第１の実施形態のエントリー表Ｅ２（２９ｃ−２）の一例を示す図である。エントリー表２９ｃは、図１１Ａ（又は図１１Ｃ）に示すエントリー表Ｅ１（２９ｃ−１）と、図１１Ｂ（又は図１１Ｄ）に示すエントリー表Ｅ２（２９ｃ−２）とを含む。

なお、図１１Ａ及び図１１Ｂは、変更前のエントリー表Ｅ１、Ｅ２である。一方、図１１Ｃ及び図１１Ｄは、変更後のエントリー表Ｅ１、Ｅ２である。変更前及び変更後については、図１３の具体例において後述する。

エントリー表Ｅ１は、図１０Ａハッシュ関数Ｈ１に対応するエントリー表である。すなわち、ハッシュ関数Ｈ１のハッシュ出力値Ａ１（２４１）、ユーザＩＤ“Ｌ０”（２４２）、内部ＩＤ（２４３）の対応関係を管理する。

一方、エントリー表Ｅ２は、図１０Ｂのハッシュ関数Ｈ２に対応するエントリー表である。すなわち、ハッシュ関数Ｈ２のハッシュ出力値Ａ２（２４８）、ユーザＩＤ“Ｌ０”（２４９）、内部ＩＤ（２５０）の対応関係を管理する。

なお、エントリー表Ｅ１では、ハッシュ出力値Ａ１（２４１）の取り得る値は、０から３までの４つの値である。一方、エントリー表Ｅ２では、ハッシュ出力値Ａ２（２４８）の取り得る値は、０から２までの３つの値である。

図１２Ａ、及び、図１２Ｂは、本発明の第２の実施形態のエントリー数管理表３０の一例を示す図である。図１２Ａは、変更前のエントリー数管理表３０であり、図１１Ａ及び図１１Ｂに示すエントリー表Ｅ１、Ｅ２に対応する。一方、図１２Ｂは、変更後のエントリー数管理表３０であり、図１１Ｃ及び図１１Ｄに示すエントリー表Ｅ１、Ｅ２に対応する。

エントリー数管理表３０は、各エントリー表２９ｃの識別子（２８１）、各エントリー表２９ｃに設定可能なエントリー数を表す表サイズ（２８２）、各エントリー表２９ｃにおいて設定済みのエントリー数（２８３）、各エントリー表２９ｃのエントリー未設定フィールド数である空き数（２８４）の対応関係、すなわちエントリー表２９ｃ毎の空き数（エントリー未設定フィールド数）を管理する。

図１１Ａに示すエントリー表Ｅ１では、設定可能なエントリー数が４、設定済みのエントリー数が０、エントリー未設定フィールド数が４である。また、図１１Ｂに示すエントリー表Ｅ２では、設定可能なエントリー数が３、設定済みのエントリー数が１、エントリー未設定フィールド数が２である。そのため、図１２Ａに示すエントリー数管理表３０では、エントリー表Ｅ１の表サイズが４、エントリー数が０、空き数が４として登録されている。同様に、エントリー表Ｅ２の表サイズが３、エントリー数が１、空き数が２として登録されている。

一方、図１１Ｃに示すエントリー表Ｅ１では、設定可能なエントリー数が４、設定済みのエントリー数が０、エントリー未設定フィールド数が４である。また、図１１Ｄに示すエントリー表Ｅ２では、設定可能なエントリー数が３、設定済みのエントリー数が２、エントリー未設定フィールド数が１である。そのため、図１２Ｂに示すエントリー数管理表３０では、エントリー表Ｅ１の表サイズが４、エントリー数が０、空き数が４として登録されている。同様に、エントリー表Ｅ２の表サイズが３、エントリー数が２、空き数が１として登録されている。

以上のように、エントリー数管理表３０は、各エントリー表２９ｃのエントリー未設定フィールド数である空き数を管理する。これにより、ノード１は、各エントリー表２９ｃにおけるエントリー未設定状況に応じて、新規エントリーの登録先のエントリー表２９ｃを選択することが可能となる。なお、表サイズ２８２やエントリー数２８３の欄は設けなくてもよい。

図１３は、本発明の第２の実施形態のエントリー追加処理の一例を示すフローチャートである。ここでは、通信経路設定部２５が、エントリー表２９ｃに新規エントリーを追加（登録）する手順を、具体例を用いて説明する。

通信経路設定部２５は、処理開始後（４０１）、網管理装置６から新規ユーザＩＤ（例えば、ユーザＩＤ“Ｌ”）の設定コマンドを受信するまで、待ち状態となる（４０２）。新規ユーザＩＤ“Ｌ”の設定コマンドを受信した場合には（４０２でＹＥＳ）、変数"エントリー先候補"に"なし"を、空き数を表す変数Ｎに設定可能なユーザＩＤ数である４を、カウンタｉに１を、それぞれ初期値として設定する（４０３）。

次に、通信経路設定部２５は、エントリー表Ｅｉにおいて、ハッシュ出力値ＡｉがＨｉ（Ｌ）であるエントリーが空、且つ、変数Ｎの値がエントリー表Ｅｉの空き数以上であるか否かを判定する（４０４）。なお、Ｈｉ（Ｌ）とは、入力値Ｌに対するハッシュ関数Ｈｉの出力値である。

具体的には、まず、エントリー表Ｅ１（図１１Ａ）から、ハッシュ出力値Ａ１がＨ１（Ｌ）であるエントリーを検索し、該当するエントリーが空であるか否かを確認する。例えば、ステップ４０２で新規ユーザＩＤ“Ｌ＝２”の設定コマンドを受信した場合には、入力値２に対するハッシュ関数Ｈ１（図１０Ａ）の出力値は１である。すなわち、Ｈ１（２）＝１である。そのため、エントリー表Ｅ１（図１１Ａ）から、ハッシュ出力値Ａ１が１であるエントリーが空であることを確認する。

次に、エントリー数管理表３０（図１２Ａ）を参照し、変数Ｎの値（ここでは初期値４）と、エントリー表Ｅ１の空き数とを比較する。エントリー数管理表３０（図１２Ａ）において、エントリー表Ｅ１の空き数は４である。そのため、変数Ｎの値はエントリー表Ｅ１の空き数以上である。以上より、ステップ４０４においてＹＥＳとなる。

ステップ４０４においてＹＥＳの場合には、通信経路設定部２５は、変数“エントリー先候補”に“Ｅｉ”を、変数Ｎに“エントリー表Ｅｉの空き数”を設定する（４０５）。上記具体例では、変数"エントリー先候補"に"Ｅ１"を、変数Ｎにエントリー表Ｅ１の空き数である４を設定する。一方、ステップ４０４においてＮＯの場合には（４０４でＮＯ）、ステップ４０５の処理を実行しない。

ステップ４０６に進むと、通信経路設定部２５は、カウンタｉをインクリメントする（４０６）。上記具体例では、ｉ＝２となる。

その後、通信経路設定部２５は、カウンタｉの値がエントリー表数ｉｍａｘよりも大きいか否かを判定する（４０７）。カウンタｉの値がエントリー表数ｉｍａｘ以下である場合には（４０７でＮＯ）、ステップ４０４に戻って処理を繰り返す。一方、カウンタｉの値がエントリー表数ｉｍａｘよりも大きい場合には（４０７でＹＥＳ）、ステップ４０８に進む。

上記具体例では、カウンタｉの値は２であり、エントリー表数ｉｍａｘの値は２（エントリー表Ｅ１、Ｅ２の２つ）である。そのため、カウンタｉの値はエントリー表数ｉｍａｘ以下であるので（４０７でＮＯ）、ステップ４０４に戻る。

ステップ４０４に戻ると、通信経路設定部２５は、エントリー表Ｅ２（図１１Ｂ）から、ハッシュ出力値Ａ２がＨ２（２）であるエントリーを検索し、該当するエントリーが空であるか否かを確認する。入力値２に対するハッシュ関数Ｈ２（図１０Ｂ）の出力値は２である。すなわち、Ｈ２（２）＝２である。そのため、エントリー表Ｅ２（図１１Ｂ）から、ハッシュ出力値Ａ２が２であるエントリーが空であることを確認する。

次に、エントリー数管理表３０（図１２Ａ）を参照し、変数Ｎの値（ここでは４）と、エントリー表Ｅ２の空き数とを比較する。エントリー数管理表３０（図１２Ａ）において、エントリー表Ｅ２の空き数は２である。そのため、変数Ｎの値はエントリー表Ｅ２の空き数以上である。以上より、ステップ４０４においてＹＥＳとなる。

ステップ４０５に進み、通信経路設定部２５は、変数“エントリー先候補”に“Ｅ２”を、変数Ｎにエントリー表Ｅ２の空き数である２を設定する（４０５）。その後、カウンタｉをインクリメントしてｉ＝３とする（４０６）。そうすると、カウンタｉの値３はエントリー表数ｉｍａｘ（＝２）よりも大きいので（４０７でＹＥＳ）、ステップ４０８に進む。

以上に示すステップ４０４〜４０７の処理により、通信経路設定部２５は、変数“エントリー先候補”及び変数Ｎを用いて、空き数の最も少ないエントリー表を、新規エントリーの登録先候補として決定する。

ステップ４０８では、通信経路設定部２５は、変数"エントリー先候補"の値が"なし"であるか否かを確認する（４０８）。変数“エントリー先候補”の値が“なし”である場合には（４０８でＹＥＳ）、ステップ４１１に進む。一方、変数“エントリー先候補”の値が“なし”でない場合には（４０８でＮＯ）、ステップ４０９に進む。上記具体例では、変数“エントリー先候補”の値は“Ｅ２”であるので（４０８でＮＯ）、ステップ４０９に進む。

ステップ４０９では、通信経路設定部２５は、変数“エントリー先候補”で示されるエントリー表に、ユーザＩＤ“Ｌ”のエントリーを追加し、エントリー数管理表３０を更新する（４０９）。

上記具体例では、変数“エントリー先候補"の値が"Ｅ２"であるので、エントリー表Ｅ２に、ユーザＩＤ“２”のエントリーを追加する。なお、新規エントリーを追加する場合に、新規エントリーに係る内部ＩＤは、全てのエントリー表Ｅ１、Ｅ２においてユニークな値とする。その結果、図１１Ａに示すエントリー表Ｅ１、及び、図１１Ｂに示すエントリー表Ｅ２は、それぞれ図１１Ｃに示すエントリー表Ｅ１、及び、図１１Ｄに示すエントリー表Ｅ２に変更する。

また、エントリー数管理表３０を更新する。上記具体例では、エントリー表Ｅ２の空き数が２から１に変更されるので、図１２Ａに示すエントリー数管理表３０は、図１２Ｂに示すエントリー数管理表３０に変更する。

その後ステップ４１０において、通信経路設定部２５は、変更後のエントリー表Ｅ１及びＥ２（２９ｃ）の情報を、各インタフェース部２２ａ、２２ｂに送信する（４１０）。各インタフェース部２２ａ、２２ｂは、受信した変更後のエントリー表Ｅ１及びＥ２（２９ｃ）の情報を、各インタフェース部２２ａ、２２ｂが備えるエントリー表２９ａ、２９ｂに上書き（更新）する。その後ステップ４１７において、監視制御部２１は、通信経路を設定した旨を示す通信経路設定応答６０４を、網管理装置６に送信する（４１７）。

なお、ステップ４１１〜４１６の処理については、前述のステップ３１１〜３１６の処理と同様であるとして、ここでは説明を省略する。

以上に示す処理により、通信経路設定部２５は、エントリー未設定フィールド数が他のエントリー表２９ｃよりも少ないエントリー表２９ｃ、すなわちエントリー未設定フィールド数が最も少ないエントリー表２９ｃに優先的に新規エントリーを追加する。その結果、エントリーが追加されたエントリー表２９ｃと、他のエントリー表２９ｃとの間では、エントリー未設定フィールド数の差がさらに大きくなる。すなわち、エントリー表２９ｃ間でエントリー未設定フィール数に偏りが生じることになる。

また、通信経路設定部２５は、エントリー未設定フィールド数の最も少ないエントリー表２９ｃが複数存在する場合には、表番号（Ｅｉ）の大きなエントリー表２９ｃに優先的に新規エントリーを追加する。これにより、表番号の大きなエントリー表２９ｃに多くのエントリーが設定され、表番号の小さなエントリー表２９ｃに少ないエントリーが設定されるように制御することができる。これにより、将来エントリーを追加する際の衝突の発生確率を下げることが可能となる。なお、新規エントリーの追加先は、表番号の大きなエントリー表２９ｃに限定されるものではない。

以上に示す各実施形態によれば、ハッシュ関数を用いた処理を実行する計算機（例えば通信装置、暗号処理装置）において、限られたメモリサイズ上の複数のエントリー表に対して効果的に新規エントリーを追加することができる。

すなわち、計算機は、新規エントリーを追加する際に、当該新規エントリーを追加可能なエントリー表２９ｃが複数ある場合、エントリー数管理表３０を参照し、エントリー設定状況に応じて新規エントリーの最適な追加先を選択する。これにより、将来エントリーを追加する場合に、設定済みエントリーの再配置処理を回避する又は再配置処理の実行頻度を削減することができる。また、設定済みエントリーの識別子変換処理に影響を与えることなく、新規エントリーを追加することができる。特に、帯域保証型サービスを提供する通信システムでは、設定済みエントリーに係るユーザの通信断を防ぐとともに、新規エントリーを追加することができる。

以上、本発明の各実施形態について説明したが、上記各実施形態は本発明の適用例の一つを示したものであり、本発明の技術的範囲を上記各実施形態の具体的構成に限定する趣旨ではない。

例えば、上記説明では、本発明をＭＰＬＳ−ＴＰに基づく帯域保証網Ｎ１に適用した場合を例に説明してきたが、この場合には限らない。例えば、ＡＴＭ（Asynchronous Transfer Mode）やＥｔｈｅｒｎｅｔ（登録商標）ＶＬＡＮ（Virtual Local Area Network）等のユーザ毎のユーザＩＤに基づいて通信接続を管理する通信システム内の通信装置に対しても適用可能である。

Ｎ１帯域保証網
Ｎ２、Ｎ３アクセス網
１、２、３、４、５ノード
６網管理サーバ
２５通信経路設定部
２７ａ、２７ｂユーザＩＤ処理部
２８ａ、２８ｂ、２８ｃハッシュ関数
２９ａ、２９ｂ、２９ｃエントリー表
３０エントリー数管理表

Claims

プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記プロセッサは、
前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報を登録すべきエントリー表を選択し、
前記複数のエントリー表の識別子変換情報の設定状況に、エントリー表間での偏りが生じるように、前記新たな識別子変換情報を登録すべきエントリー表を選択することを特徴とする計算機。
プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記プロセッサは、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報を登録すべきエントリー表を選択し、
前記管理表は、前記複数のエントリー表の各々における識別子変換情報の設定数を管理し、
前記プロセッサは、前記複数のエントリー表から、前記設定数が他のエントリー表よりも多いエントリー表を選択することを特徴とする計算機。
プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記プロセッサは、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報を登録すべきエントリー表を選択し、
前記管理表は、前記複数のエントリー表の各々における識別子変換情報の未設定数を管理し、
前記プロセッサは、前記複数のエントリー表から、前記未設定数が他のエントリー表よりも少ないエントリー表を選択することを特徴とする計算機。
前記複数のハッシュ関数のうち少なくとも２つのハッシュ関数は、それぞれ異なる範囲の出力値を出力するものであり、
前記複数のエントリー表の各々は、当該エントリー表に対応する前記ハッシュ関数の出力値の数以下の識別子変換情報を管理することを特徴とする請求項３に記載の計算機。
プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機における識別子管理方法であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記方法は、
前記プロセッサが、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報複数を登録すべきエントリー表を選択する手順と、
前記選択された登録すべきエントリー表に、前記新たな識別子変換情報を登録する手順と、
を含み、
前記選択する手順において、前記プロセッサは、前記複数のエントリー表の識別子変換情報の設定状況に、エントリー表間での偏りが生じるように、前記新たな識別子変換情報を登録すべきエントリー表を選択することを特徴とする記載の識別子管理方法。
プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機における識別子管理方法であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記方法は、
前記プロセッサが、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報複数を登録すべきエントリー表を選択する手順と、
前記選択された登録すべきエントリー表に、前記新たな識別子変換情報を登録する手順と、
を含み、
前記管理表は、前記複数のエントリー表の各々における識別子変換情報の設定数を管理し、
前記選択する手順において、前記プロセッサは、前記設定数が他のエントリー表よりも多いエントリー表を選択することを特徴とする識別子管理方法。
プログラムを実行するプロセッサと、前記プロセッサによって実行されるプログラムを格納するメモリと、を備え、通信データに付与された識別子を変換する計算機における識別子管理方法であって、
前記メモリは、
複数のハッシュ関数と、
前記複数のハッシュ関数の各々に対応し、当該ハッシュ関数の出力値と、当該ハッシュ関数の入力値である入力識別子と、前記入力識別子を変換して得られる出力識別子と、の対応を示す識別子変換情報を管理する複数のエントリー表と、
前記複数のエントリー表の各々における識別子変換情報の設定状況を管理する管理表と、を記憶し、
前記方法は、
前記プロセッサが、前記複数のエントリー表のいずれかに、新たな識別子変換情報を登録する場合には、前記管理表によって管理される前記複数のエントリー表の各々における識別子変換情報の設定状況に応じて、前記新たな識別子変換情報複数を登録すべきエントリー表を選択する手順と、
前記選択された登録すべきエントリー表に、前記新たな識別子変換情報を登録する手順と、
を含み、
前記管理表は、前記複数のエントリー表の各々における識別子変換情報の未設定数を管理し、
前記選択する手順において、前記プロセッサは、前記未設定数が他のエントリー表よりも少ないエントリー表を選択することを特徴とする識別子管理方法。
前記複数のハッシュ関数のうち少なくとも２つのハッシュ関数は、それぞれ異なる範囲の出力値を出力するものであり、
前記複数のエントリー表の各々は、当該エントリー表に対応する前記ハッシュ関数の出力値の数以下の識別子変換情報を管理することを特徴とする請求項７に記載の識別子管理方法。