(57)【要約】【課題】連想メモリを使用して各属性用の専用記憶領域を用意することなく、属性に応じた処理を可能とするネットワーク中継装置を提供する。【解決手段】受信したデータに対応するエントリが登録されたＣＡＭと、ＣＡＭの動作を制御する制御部とを備え、エントリはデータの属性を表す属性情報と、同一属性のデータの処理順序を管理するページ情報とを含み、制御部はＣＡＭに新たなエントリを登録する際にＣＡＭの空きエントリのアドレスを取得し、該取得したアドレスが新たなエントリの属性情報と同一属性の最後のエントリのアドレスよりも大きい場合、新たなエントリのページ情報を最後のエントリのページ情報と同じページ番号とし、小さい場合新たなエントリのページ情報を最後のエントリのページ情報とは異なるページ番号として、新たなエントリを取得した空きエントリのアドレスに追加することにより、上記課題を解決する。【選択図】図２
2010250486.tif 000002
【特許請求の範囲】
【請求項１】
受信したデータに対応するエントリが登録されたＣＡＭと、前記ＣＡＭの動作を制御する制御部とを備え、
前記エントリは、前記受信したデータの属性を表す属性情報と、同一属性のデータの処理順序を管理するページ番号を表すページ情報とを含み、
前記制御部は、前記ＣＡＭに新たなエントリを登録する際に、前記ＣＡＭの空きエントリのアドレスを取得し、該取得した空きエントリのアドレスが、前記新たなエントリの属性情報と同一属性の最後のエントリのアドレスよりも大きい場合、前記新たなエントリのページ情報を前記最後のエントリのページ情報と同じページ番号とし、小さい場合、前記新たなエントリのページ情報を前記最後のエントリのページ情報とは異なるページ番号として、前記新たなエントリを前記取得した空きエントリのアドレスに追加することを特徴とするネットワーク中継装置。
【請求項２】
前記エントリは、さらに、同一属性の最初および最後のエントリを表すヘッドビットおよびテールビットを含み、
前記制御部は、前記ＣＡＭに登録された同一属性の最初のエントリのヘッドビットおよび最後のエントリのテールビットをアクティブ状態とし、
前記ＣＡＭに新たなエントリを登録する際に、前記属性および前記アクティブ状態のテールビットを第１の検索キーとして前記ＣＡＭのエントリを検索し、前記第１の検索キーに一致するエントリが存在する場合、該一致するエントリのテールビットを非アクティブ状態、前記新たなエントリのテールビットをアクティブ状態とし、
前記第１の検索キーに一致するエントリが存在しない場合、前記新たなエントリのヘッドビットおよびテールビットをアクティブ状態とし、前記ページ情報を前記ページ番号の初期値にすることを特徴とする請求項１に記載のネットワーク中継装置。
【請求項３】
前記エントリは、さらに、同一属性の最初および最後のエントリを表すヘッドビットおよびテールビットを含み、
前記制御部は、前記ＣＡＭに登録された同一属性の最初のエントリのヘッドビットおよび最後のエントリのテールビットをアクティブ状態とし、
前記ＣＡＭに登録されたエントリを検索する際に、前記属性および前記アクティブ状態のヘッドビットを第２の検索キーとして前記ＣＡＭのエントリを検索し、前記第２の検索キーに一致するエントリのページ情報からページ番号を取得した後、当該第２の検索キーに一致するエントリを解放し、前記属性および前記取得したページ番号を第３の検索キーとして前記ＣＡＭのエントリを検索し、前記第３の検索キーに一致するエントリのヘッドビットをアクティブ状態とし、
前記第３の検索キーに一致するエントリが存在しない場合、さらに、前記属性と前記ページ番号を異なるページ番号に変更したものを第４の検索キーとして前記ＣＡＭのエントリを検索し、前記第４の検索キーに一致するエントリが存在する場合、該第４の検索キーに一致するエントリのヘッドビットをアクティブ状態とすることを特徴とする請求項１に記載のネットワーク中継装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のインタフェースポートを有し、送信元のポートからデータ（パケット）を受信し、中継処理を行って送信先のポートを特定し、受信したデータを特定した送信先のポートから送信するネットワーク中継装置に関するものである。
【背景技術】
【０００２】
従来、ネットワーク中継装置において、優先度などのデータ属性毎にデータ（パケット）の中継処理を管理する必要がある場合、各属性用に専用記憶領域を確保する方法が一般的に用いられていた。
【０００３】
例えば、スイッチやルータなどのネットワーク中継装置は複数のインタフェースポートを持ち、各インタフェースポートから入力されるデータを宛先のインタフェースポートに出力する機能を持っている。具体的には、ネットワーク中継装置は、入力データを一時的に装置内の記憶領域に退避しておき、入力データに含まれる制御データを解析して宛先のインタフェースポートを特定した後、退避しておいたデータをこの宛先のインタフェースポートから出力する。
【０００４】
このとき、各インタフェースポートから入力されてくるデータが個別の優先度を持つ場合、ネットワーク中継装置は、その優先度に応じて処理を行う必要がある。この様な場合には、前述のように各インタフェースポートに優先度別にデータ、またはデータの格納場所を記録したポインタを格納しておくための専用記憶領域を用意しておく方法が一般的に用いられている。
【０００５】
例えば、優先度が８段階である場合、図６に示すように、各インタフェースポートにそれぞれ８個の専用記憶領域を用意し、データ出力時には、より高い優先度に対応する専用記憶領域に格納されているデータを先に処理することで、優先順位に応じた処理が実現可能となる。図６の例では、最初に一番高い優先度８の記憶領域１００に格納されているデータが処理され、以下順に、記憶領域１０２（優先度７）…記憶領域１０４（優先度１）に格納されているデータが処理される。
【０００６】
ところが、上記のような方法の場合では、その他の属性、例えばネットワークにおけるＶＬＡＮ−ＩＤでも個別の管理をする必要があるときは、ＶＬＡＮ−ＩＤが４種類あると仮定すれば、４種類×８優先度で３２個の専用記憶領域を用意する必要があった。
このように、考慮すべき属性に応じて用意すべき専用記憶領域が増えることになり、管理が煩雑となる。
【０００７】
さらに、上記の方法では、記憶領域を効率的に使用できない場合がある。例えば、ある属性に所属するデータが大量に発生して、その属性用に用意した専用記憶領域に格納できない状態になった場合を考える。このとき、その他の属性用の記憶領域には余裕があったとすると、システム全体では記憶領域が枯渇していないにもかかわらず、特定の属性を持ったデータを格納できずに破棄するなどの問題が発生することになる。このように、装置内の記憶領域を有効活用できない場合、結果として装置の性能低下を引き起こす可能性がある。
【０００８】
これを回避する方法として、それぞれの属性用専用記憶領域を十分に大きく用意しておくことが考えられる。しかし、記憶領域が必要以上に大きくなることによるコスト増大の問題がある。
【０００９】
ここで、本発明に関連性のある先行技術文献として、特許文献１がある。
特許文献１には、プロトコル識別子およびプロトコルアドレスを含む複数のエントリを連想メモリテーブルに記憶しておき、プロトコル識別子に対応するシーケンサにより、連想メモリテーブルに記憶されたエントリのプロトコルアドレスの一致検索を行うことによって、複数の異なるプロトコルのアドレスを１つの連想メモリテーブルに記憶して、その中から所定プロトコルの所定アドレスを有するエントリを検出することが開示されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平８−２１２７９０号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、連想メモリ（ＣＡＭ）を使用して、属性情報をデータまたはデータ格納場所を示すポインタと共に格納しておくことにより、各属性用の専用記憶領域を用意することなく、優先度などの属性に応じた中継処理を可能とするネットワーク中継装置を提供することにある。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明は、受信したデータに対応するエントリが登録されたＣＡＭと、前記ＣＡＭの動作を制御する制御部とを備え、前記エントリは、前記受信したデータの属性を表す属性情報と、同一属性のデータの処理順序を管理するページ番号を表すページ情報とを含み、前記制御部は、前記ＣＡＭに新たなエントリを登録する際に、前記ＣＡＭの空きエントリのアドレスを取得し、該取得した空きエントリのアドレスが、前記新たなエントリの属性情報と同一属性の最後のエントリのアドレスよりも大きい場合、前記新たなエントリのページ情報を前記最後のエントリのページ情報と同じページ番号とし、小さい場合、前記新たなエントリのページ情報を前記最後のエントリのページ情報とは異なるページ番号として、前記新たなエントリを前記取得した空きエントリのアドレスに追加することを特徴とするネットワーク中継装置を提供する。
【００１３】
また、前記エントリは、さらに、同一属性の最初および最後のエントリを表すヘッドビットおよびテールビットを含み、前記制御部は、前記ＣＡＭに登録された同一属性の最初のエントリのヘッドビットおよび最後のエントリのテールビットをアクティブ状態とし、前記ＣＡＭに新たなエントリを登録する際に、前記属性および前記アクティブ状態のテールビットを第１の検索キーとして前記ＣＡＭのエントリを検索し、前記第１の検索キーに一致するエントリが存在する場合、該一致するエントリのテールビットを非アクティブ状態、前記新たなエントリのテールビットをアクティブ状態とし、前記第１の検索キーに一致するエントリが存在しない場合、前記新たなエントリのヘッドビットおよびテールビットをアクティブ状態とし、前記ページ情報を前記ページ番号の初期値にするのが好ましい。
【００１４】
また、前記エントリは、さらに、同一属性の最初および最後のエントリを表すヘッドビットおよびテールビットを含み、前記制御部は、前記ＣＡＭに登録された同一属性の最初のエントリのヘッドビットおよび最後のエントリのテールビットをアクティブ状態とし、前記ＣＡＭに登録されたエントリを検索する際に、前記属性および前記アクティブ状態のヘッドビットを第２の検索キーとして前記ＣＡＭのエントリを検索し、前記第２の検索キーに一致するエントリのページ情報からページ番号を取得した後、当該第２の検索キーに一致するエントリを解放し、前記属性および前記取得したページ番号を第３の検索キーとして前記ＣＡＭのエントリを検索し、前記第３の検索キーに一致するエントリのヘッドビットをアクティブ状態とし、前記第３の検索キーに一致するエントリが存在しない場合、さらに、前記属性と前記ページ番号を異なるページ番号に変更したものを第４の検索キーとして前記ＣＡＭのエントリを検索し、前記第４の検索キーに一致するエントリが存在する場合、該第４の検索キーに一致するエントリのヘッドビットをアクティブ状態とするのが好ましい。
【発明の効果】
【００１５】
本発明によれば、データを属性に応じて管理するときに、各属性用の専用記憶領域を設ける場合に比べて、制御部の回路を簡略化することができ、装置内の記憶領域を無駄なく有効に活用することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明に係るネットワーク中継装置の一実施形態を示すブロック図である。
【図２】本発明に係るネットワーク中継装置の一実施形態における動作を表す説明図である。
【図３】（ａ）および（ｂ）は、本発明に係る連想メモリのページ概念を示す説明図である。
【図４】本発明に係るネットワーク中継装置の一実施形態におけるエントリ登録時の制御を示すフローチャートである。
【図５】本発明に係るネットワーク中継装置の一実施形態におけるエントリ取り出し時の制御を示すフローチャートである。
【図６】従来の、専用記憶領域による優先順位処理方法を示す説明図である。
【発明を実施するための形態】
【００１７】
本発明に係るネットワーク中継装置を、添付の図面に示す好適実施形態に基づいて以下に詳細に説明する。
【００１８】
図１は、本発明のネットワーク中継装置の構成を表す一実施形態のブロック図である。図１に示すネットワーク中継装置１０は、制御部１２、連想メモリ（以下、ＣＡＭともいう）１４、ＳＲＡＭ１６、およびデータ格納用メモリ１８によって構成される。
【００１９】
制御部１２は、ＣＡＭ１４、ＳＲＡＭ１６、およびデータ格納用メモリ１８の動作を制御する。制御部１２は、例えば、ＣＡＭ１４に対してエントリの更新（登録、削除）、および検索の制御をし、ＳＲＡＭ１６に対してデータ格納先アドレスの更新の制御をし、データ格納用メモリ１８に対してデータの更新を制御する。
【００２０】
ＣＡＭ１４は、図２に示すように、データ格納用メモリ１８の各々のデータに対応するエントリ１９ａ，１９ｂ，１９ｃ，…１９ｄを有する半導体メモリである。ＣＡＭ１４は、エントリに有効なデータが記憶されていない空きエントリを検索し、優先順位に応じて、例えば、空きエントリのうちの最も小さいアドレスの空きエントリのアドレスを出力する。また、ＣＡＭ１４は、検索キーによって、記憶された複数のエントリの内容（データ）を同時に検索し、優先順位に応じて、例えば、検索キーと一致する内容を含むエントリのうちの最も小さいアドレスに記憶されたエントリのアドレスを出力する。エントリについては後述する。
【００２１】
ＳＲＡＭ（スタティックラム）１６は、データが記憶されたデータ格納用メモリ１８のアドレスを記憶する半導体メモリである。
ＳＲＡＭ１６は、図２に示すように、ＣＡＭ１４の各エントリ１９ａ，１９ｂ，１９ｃ，…１９ｄのそれぞれに、１対１に対応する記憶領域３０，３２，３４，…を有する。つまり、ＣＡＭ１４から出力されるエントリのアドレスが、そのままＳＲＡＭ１６のアドレスとして使用される。ＳＲＡＭ１６の記憶領域３０，３２，３４，…に記憶されたデータ格納用メモリのアドレスは、各エントリ１９ａ，１９ｂ，１９ｃ，…１９ｄのそれぞれに、１対１に対応するデータが記憶されたデータ格納用メモリ１８のデータ格納領域４０，４２，４４，…をそれぞれ指し示すポインタの役割を果たす。これ以外の記憶領域も同じである。
【００２２】
例えば、エントリ１９ａに対応する記憶領域３０には、エントリ１９ａに対応するデータ１が格納された、データ格納用メモリ１８のデータ格納領域４０のアドレスが記憶される。
【００２３】
データ格納用メモリ１８は、受信したパケットのデータそのものを記憶する半導体メモリである。
【００２４】
例えば、制御部１２がある属性のデータを取り出す場合、まずＣＡＭ１４にアクセスして取り出したい属性のエントリを検索する。この時、例えば、最初のエントリとしてエントリ１９ａが検出されると、ＣＡＭ１４からエントリ１９ａのアドレスが出力され、エントリ１９ａ（のアドレス）と１対１に対応するＳＲＡＭ１６の記憶領域３０から、データ格納用メモリ１８のデータ格納領域４０のアドレスが出力される。その後、制御部１２は、データ格納用メモリ１８のデータ格納領域４０にアクセスして格納されているデータを取り出すことになる。
【００２５】
次に、エントリについて説明する。
各エントリ１９ａ，１９ｂ，１９ｃ，…１９ｄは、図２に示すように、属性情報２０、ヘッドビット２２、テールビット２４、およびページ情報２６から構成される。
【００２６】
ここで、属性情報２０は、データの属性を表すものであり、任意のビット数で構成される。属性には、例えば優先度やＶＬＡＮ−ＩＤ等を用いることができ、それぞれ複数種類に分類される。例えば、優先度を８種類、ＶＬＡＮ−ＩＤを４種類とすると、属性情報２０のビット数は、３２種類の属性情報が設定可能なビット数、すなわち５ビット以上であればよい。
ある属性を含むエントリを取り出す場合には、当該属性を検索キーとしてＣＡＭ１４を検索することで、１つのＣＡＭ１４内に複数種類の属性のエントリが存在していても、当該属性のエントリのみを取り出すことができる。
【００２７】
ヘッドビット２２は、エントリが同一属性のエントリのうちの最初のエントリであることを表すものであり、１ビットで構成される。制御部１２により、ＣＡＭ１４に記憶された同一属性のすべてのエントリのうち、最初のエントリ（ＣＡＭ１４に記憶された同一属性のエントリのうち、最も登録順序の古いエントリ、すなわち、最初に中継処理が行われるエントリ）のヘッドビット２２がアクティブ状態（セット）、図１の例では、ヘッドビット２２が”１”に設定される。
【００２８】
テールビット２４は、エントリが同一属性のエントリのうちの最後のエントリであることを表すものであり、１ビットで構成される。制御部１２により、ＣＡＭ１４に記憶された同一属性のすべてのエントリのうち、最後のエントリ（ＣＡＭ１４に記憶された同一属性のエントリのうち、最も登録順序の新しいエントリ、すなわち、最後に中継処理が行われるエントリ）のテールビット２４がアクティブ状態（セット）、図１の例では、テールビット２４が”１”に設定される。
【００２９】
ページ情報２６は、エントリが登録されるＣＡＭ１４のページ番号を表すものであり、任意のビット数で構成される。ページは、同一属性のエントリに対応するデータの処理順序を保つ（同一属性のデータを受信した順序で送信する）ために導入した、ＣＡＭ１４のメモリ領域を管理する上での仮想的な概念である。例えば、エントリを登録するとき、ＣＡＭ１４の空きエントリのアドレスが同一属性の最後のエントリのアドレスよりも小さい場合、例えば、この最後のエントリのページ番号に１を追加し、これを新たに登録するエントリのページ番号とする。ページ番号を検索キーとしてＣＡＭ１４を検索することにより、空きエントリのアドレスに関わらず、同一属性のエントリに対応するデータの処理順序を正しく保つ（管理する）ことができる。例えば、ページ番号が１〜８まである場合、まず、属性とページ番号＝１で検索し、以下ページ番号を１つずつ増加させて検索することを、ページ番号が８になるまで繰り返す。８ページ使う場合には、ページ情報２６のビット数は、３ビット以上であればよい。
【００３０】
次に、ページの概念について図３（ａ）および（ｂ）に基づいて説明する。なお、以下の説明では、アドレスの最初の側を前、あるいは小さい、最後の側を後、あるいは大きいともいう。
【００３１】
データは、インタフェースポートに到着した順序（受信した順序）でデータ格納用メモリ１８に格納されるが、出力される（取り出される）順序は、属性情報に応じて変更される。例えば、優先度が高いデータは、後で到着したとしても先に出力される。すると、データ出力が完了したエントリは空きエントリとなるため、結果として空きエントリの位置は規則的に並ばず、不規則な状態でＣＡＭ１４内に散在することになる。このような状態で空きエントリを検索した場合、検索された空きエントリのアドレスがＣＡＭ１４に登録された同一属性の最後のエントリのアドレスよりも小さい場合がある。この状態でこの空きエントリに新たなデータを格納（新たなエントリを登録）すると、ＣＡＭ１４を検索キーで検索した結果、古いデータよりも新しいデータが先に出力されることになり、同一属性のデータ間の処理順序が入れ替わってしまうことになる。この問題を解決するためにページの概念を導入し、同一属性のデータ間の処理順序が入れ替わることがないようにする。
【００３２】
図３（ａ）は、同一属性のエントリ１，２，３がこの順序でＣＡＭ１４に登録された状態を表す。同図に示す例の場合、ＣＡＭ１４の空きエントリを検索した結果、新たに追加するエントリ５６を登録する空きエントリのアドレスが同一属性の最後のエントリ５４（エントリ３）のアドレスよりも後のアドレスなので、エントリ５６のページ番号は同一属性の最後のエントリと同じページ番号１とされる。これにより、エントリ５６（エントリ４）は、同一属性の最後のエントリのアドレスよりも後ろの（大きい）アドレスに登録（追加）される。従って、属性とページ番号＝１を検索キーとしてＣＡＭ１４を検索した場合に、既存エントリ５０，５２，５４、追加エントリ５６が一致検出され、アドレスの小さい順に出力されるため、データの処理順序が正しく保たれる。
【００３３】
一方、図３（ｂ）では、新たにエントリ６０が登録（追加）される空きエントリのアドレスが、エントリ６０と同一属性の最後のエントリのアドレスよりも前の（小さい）アドレスにあるため、追加エントリ６０のページ番号を１にすると、検索時に追加エントリ６０が、古いデータである既存エントリ５０，５２，５４よりも先に出力され、データの処理順序を保つことができない。この場合には、最後のエントリ５４（エントリ３）のページ番号に１を加算し、つまり追加エントリ６０（エントリ４）のページ番号を２とし、追加エントリ６０が新しい最後のエントリとして追加される。
これにより、属性とページ番号＝１を検索キーとしてＣＡＭ１４を検索した場合に、既存エントリ５０，５２，５４の一致が検出され、この順序で各エントリのデータが出力される。次に同一属性とページ番号＝２を検索キーとしてＣＡＭ１４を検索した場合に、エントリ６０の一致が検出されて、追加された新しい最後のエントリ６０（エントリ４）が出力される。従って、データの処理順序が正しく保たれる。
【００３４】
このように、追加エントリ６０が、同一属性の最後のエントリのアドレスよりも前の（小さい）アドレスにある場合には、ページ番号を更新することによりデータの処理順序を保持することができる。
【００３５】
次に、ネットワーク中継装置１０の動作を説明する。
【００３６】
新たなエントリを登録する場合の制御を、図４に示すフローチャートに沿って説明する。
制御部１２の制御により、まず、ＣＡＭ１４の空きエントリを検索する（ステップＳ１）。
【００３７】
ここで、空きエントリがなければ（ステップＳ２で‘Ｎ’）、すなわちＣＡＭ１４のメモリ領域が全て使用されている状態であれば、制御部１２に対して空きエントリがないことを通知して終了する（ステップＳ３）。
【００３８】
一方、空きエントリがあれば（ステップＳ２で‘Ｙ’）、新たなエントリの属性とテールビット＝１を検索キーとしてＣＡＭ１４の検索を行い、新たなエントリと同一属性の最後のエントリを探す（ステップＳ４）。
【００３９】
ここで、同一属性の最後のエントリが見つからなかった場合には（ステップＳ５で‘Ｎ’）、新たなエントリが当該属性の最初のエントリであり、ＣＡＭ１４の処理待ちキューへの新規登録となるから、制御部１２は、新たなエントリのヘッドビットとテールビットを”１”とし、ページ番号を初期値である”１”として、ステップＳ１で検出した空きエントリに登録する（ステップＳ６）。
【００４０】
また、制御部１２は、この新たなエントリに対応するデータをデータ格納用メモリ１８の所定のアドレスに記憶し、新たなエントリのＣＡＭ１４のアドレスに対応するＳＲＡＭ１６のアドレスに、データを記憶したデータ格納用メモリ１８のアドレスを記憶する（ステップＳ７）。
【００４１】
一方、当該属性の最後のエントリが見つかった場合には（ステップＳ５で‘Ｙ’）、既登録キューへの追加となり、当該属性のエントリのうち、テールビットがセットされているエントリ、つまりテールビットが”１”のエントリのアドレスとページ情報（ページ番号）とが制御部１２に保存される。また、最後のエントリは新たなエントリを追加することにより、最後のエントリではなくなるので、制御部１２により、そのテールビットがクリア、つまりテールビットが”０”とされる（ステップＳ８）。
【００４２】
その後、制御部１２は、ステップＳ１で見つけた空きエントリのアドレスと、ステップＳ８で保存した最後のエントリのアドレスとを比較する（ステップＳ９）。
【００４３】
ここで、空きエントリのアドレスの方が大きい場合には（ステップＳ９で‘Ｎ’）、制御部１２により、新たなエントリが空きエントリに追加（キューイング）される。ここで、新たなエントリのテールビットはセットされ、ページ番号は更新されず、最後のエントリと同じページ番号とされる（ステップＳ１０）。また、制御部１２は、データ格納用メモリ１８の所定のアドレスにデータを格納し、新たなエントリの示すＣＡＭ１４のアドレスに対応するＳＲＡＭ１６のアドレスに、データを記憶したデータ格納用メモリ１８のアドレスの情報を記憶して、登録処理を終了する（ステップＳ１１）。
【００４４】
一方、最後のエントリのアドレスの方が大きい場合には（ステップＳ９で‘Ｙ’）、制御部１２は、新たなエントリの属性と、ヘッドビット＝１と、最後のエントリのページ番号＋１（次ページ）に更新されたページ番号を検索キーとしてＣＡＭ１４の検索を行う（ステップＳ１２）。
【００４５】
ここで、更新されたページ内に、ヘッドビットがセットされている同一属性のエントリが見つかった場合には（ステップＳ１３で‘Ｙ’）、ページ情報２６のビットが１周して、最初のページ番号１に戻ってしまったことを意味するので、制御部１２に対して空きページがないことを通知して処理を終了する（ステップＳ１４）。
【００４６】
例えば、ページ情報が３ビットであり、そのビット＝‘０００’〜‘１１１’（２進数）に対応してページ番号１〜８が割り当てられているとする。ここで、ページ番号が”８”であるときにページを更新すればページ番号は”１”、すなわちページ情報の３ビットが”１１１”から”０００”となるのでページ情報のビットが１周して最初のページ番号１に戻ってしまう。
【００４７】
一方、更新されたページ内に、ヘッドビットがセットされている同一属性のエントリが見つからなかった場合には（ステップＳ１３で‘Ｎ’）、そのページは最初のページではないので、ステップＳ１で見つけた空きエントリに、新たなエントリが追加（キューイング）される。ここで、新たなエントリのテールビットはセットされ、ページ情報は当該更新されたページ番号とされる（ステップＳ１５）。また、制御部１２は、データ格納用メモリ１８の所定のアドレスにデータを格納し、新たなエントリの示すＣＡＭ１４のアドレスに対応するＳＲＡＭ１６のアドレスに、データを記憶したデータ格納用メモリ１８のアドレスの情報を記憶して、登録処理を終了する（ステップＳ１１）。
【００４８】
次に、エントリからデータを取り出す（読み出す）場合の制御を、図５に示すフローチャートに沿って説明する。
制御部１２の制御により、まず、取り出したいエントリの属性とヘッドビット＝１を検索キーとしてＣＡＭ１４の検索を行い、取り出したいエントリと同一属性の最初のエントリを探す（ステップＳ２０）。つまり、当該属性のエントリのうち、ヘッドビットがセットされているエントリ、つまりヘッドビットが”１”であるエントリを探す。当該属性の中で最初のエントリが見つかると、そのエントリからデータが取り出される。
【００４９】
その後、制御部１２は、データを取り出したエントリのページ情報（ページ番号）を保存し、ヘッドビットをクリア、つまりヘッドビットを”０”にし、データを取り出したエントリ１９を解放する（ステップＳ２１）。すなわち、空きエントリとして再び使用可能な状態とする。
【００５０】
続いて、制御部１２は、データを取り出したエントリと同一の属性、およびステップＳ２１で保存しておいたページ番号を検索キーとして、データを取り出したエントリ１９と同一の属性およびページ番号を持つエントリがないかＣＡＭ１４の検索を行う（ステップＳ２２）。
【００５１】
ここで、同一の属性およびページ番号を持つエントリが見つかった場合には（ステップＳ２３で‘Ｙ’）、最初に見つかった同一の属性およびページ番号を持つエントリ１９のヘッドビットをセット、つまりヘッドビットを”１”とし、処理を終了する（ステップＳ２４）。
【００５２】
一方、制御部１２は、同一の属性およびページ番号を持つエントリ１９が見つからなければ（ステップＳ２３で‘Ｎ’）、当該ページ番号には同一の属性を持つエントリがない、つまり、当該ページの出力が完了したか、全ページ完了したかを判断する。全ページ完了していない場合には（ステップ２５で‘Ｎ’）、次のページ、つまり、当該ページ番号＋１に更新されたページ番号を検索キーとしてＣＡＭ１４の検索を行う（ステップＳ２６）。
【００５３】
ここで、更新されたページ内で、同一の属性を持つエントリが見つかれば（ステップＳ２３で‘Ｙ’）、最初に見つかった同一の属性を持つエントリのヘッド情報をセット、つまりヘッドビットを”１”とし、処理を終了する（ステップＳ２４）。
【００５４】
一方、制御部１２は、全てのページ番号を検索しても、同一の属性を持つエントリが見つからなければ、ＣＡＭ１４のメモリ領域全体のどこにも同一の属性を持つエントリがない、つまり、全ページの出力が完了したということであるから、そのまま処理を終了する（ステップＳ２５で‘Ｙ’）。
【００５５】
このように、本実施形態のネットワーク中継装置によれば、データを属性に応じて管理するときに、連想メモリの使用効率を高め、装置内の記憶領域を無駄なく有効に活用することができるとともに、制御部の回路も簡略化することができる。
【００５６】
なお、本発明において、ＳＲＡＭとデータ格納用メモリは必須の構成要素ではなく、ＣＡＭのエントリ又はＳＲＡＭに、受信したデータを含める構成とすることもできる。
また、エントリにヘッドビットとテールビットを含むことは必須ではない。例えば、属性とページ番号を検索キーとしてＣＡＭのエントリを検索することにより、同一属性の最初と最後のエントリを検出することもできる。
また、ページ番号は、更新時に１を加算することに限定されず、例えば、１を減算してもよいし、あるいは、所定値を加算もしくは減算してもよい。すなわち、ページ番号の更新時には、更新前のページ番号と異なるページ番号にすればよい。また、ページ番号の初期値は１に限定されず、任意の値を設定することができる。
【００５７】
以上、本発明のネットワーク中継装置について詳細に説明したが、本発明は、上記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において、各種の改良や変更を行ってもよい。
【符号の説明】
【００５８】
１０  ネットワーク中継装置
１２  制御部
１４  連想メモリ（ＣＡＭ）
１６  ＳＲＡＭ
１８  データ格納用メモリ
１９  エントリ
２０  属性情報
２２  ヘッドビット
２４  テールビット
２６  ページ情報
３０，３２，３４  記憶領域
４０，４２，４４  データ格納領域
５０，５２  既存エントリ
５４  最後のエントリ
５６，６０  追加エントリ
１００，１０２，１０４  記憶領域
【図１】
2010250486.tif 000003
【図２】
2010250486.tif 000004
【図３】
2010250486.tif 000005
【図４】
2010250486.tif 000006
【図５】
2010250486.tif 000007
【図６】
2010250486.tif 000008