(57)【要約】 【課題】  本発明は、ネットワーク中継装置に関し、データ領域を効率的に使用することができるネットワーク中継装置を提供することを目的とする。【解決手段】  受信されたパケットデータは、ライト部１３１により、所定のバイト数で区切られてそれぞれがアドレスで管理されるバッファメモリ１３２に所定のバイト数単位に格納され、格納されたアドレスは、管理データで管理される。管理データは、複数のアドレス情報の書き込みアドレスと、キューの次の管理データのアドレスを示すネクストと、アドレス情報の書き込み・読み出し位置を示すポインタとからなり、アドレス情報にパケットデータを格納したアドレスが順に格納され、キュー毎にネクストにより管理データが繋げられてキューのパケットデータを管理する。【選択図】      図１
2006014186.tif 000002
【特許請求の範囲】
【請求項１】
受信したパケットをキューにより管理するネットワーク中継装置において、
所定の領域に分割され、各領域にアドレスが付与されて管理され、受信したパケットのデータを格納しておくバッファメモリ（１３２）と、
パケットのデータが格納された領域の全てのアドレスを保持するアドレスリストを有する管理データでパケットを管理するとともに、この管理データを順に連結してキューとして管理するキュー管理部（１３）とを備えることを特徴とするネットワーク中継装置。
【請求項２】
前記管理データのアドレスリストに、複数のパケットのデータ格納領域のアドレスも保持するようにしたことを特徴とする請求項１に記載のネットワーク中継装置。
【請求項３】
前記管理データは、前記アドレスリストの中で、どのアドレスまで書き込みが完了したかを示す書き込みポインタと、どのアドレスまで読み出しが完了したかを示す読み出しポインタとを有することを特徴とする請求項２に記載のネットワーク中継装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク中継装置に関し、特に、受信パケットをバッファリングしておくキューの管理方法に関する。
【背景技術】
【０００２】
従来、受信したデータのバッファなどを、キューにより管理することが行われており、この種のキューの管理方法としては、データを格納しておく領域の一部に次のデータの格納領域を設定し、キュー内のデータを順に辿れるようにしている（例えば、特許文献１参照）。
【特許文献１】特開２００２−３３７６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、このような従来のキューの管理方法にあっては、データの格納領域の先頭のアドレスでデータの格納領域自体を連結してキューを形成していたので、データの格納領域は連続した領域でなければならず、可変長のデータを格納する場合、領域が空いていても連続した領域が確保できないとデータを格納できなくなり、データ領域を効率的に使用できないという問題があった。
【０００４】
そこで、本発明は、データが格納された領域の全てのアドレスを保持する管理データでデータを管理し、この管理データを順に繋げてキューを管理することにより、データ領域を効率的に使用することができるネットワーク中継装置を提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記課題を解決する第１の発明は、受信したパケットをキューにより管理するネットワーク中継装置において、所定の領域に分割され、各領域にアドレスが付与されて管理され、受信したパケットのデータを格納しておくバッファメモリ（１３２）と、パケットのデータが格納された領域の全てのアドレスを保持するアドレスリストを有する管理データでパケットを管理するとともに、この管理データを順に連結してキューとして管理するキュー管理部（１３）とを備えることを特徴とするものである。
【０００６】
この発明では、パケットのデータが格納された領域のアドレスによりパケットが管理される。したがって、連続した領域でなくてもパケットのデータを格納して管理できる。
【０００７】
上記課題を解決する第２の発明は、上記第１の発明の構成に加え、前記管理データのアドレスリストに、複数のパケットのデータ格納領域のアドレスも保持するようにしたことを特徴とするものである。
【０００８】
この発明では、１つの管理データで複数のパケットが管理される。したがって、１つの管理データで複数のパケットのデータを参照することができる。
【０００９】
上記課題を解決する第３の発明は、上記第２の発明の構成に加え、前記管理データは、前記アドレスリストの中で、どのアドレスまで書き込みが完了したかを示す書き込みポインタと、どのアドレスまで読み出しが完了したかを示す読み出しポインタとを有することを特徴とするものである。
【００１０】
この発明では、アドレスリストの中の書き込み完了位置、読み出し完了位置が保持され、この書き込み完了位置により次の書き込み位置が容易に分かり、書き込み完了位置と読み出し完了位置が一致したことで、管理するデータが無くなったことが容易に分かる。
【発明の効果】
【００１１】
本発明によれば、パケットのデータが格納された領域の全てのアドレスを保持してパケットを管理しているので、連続した領域でなくてもパケットのデータを格納して管理でき、データ領域を効率的に使用することができる。
【００１２】
また、１つの管理データで複数のパケットの格納領域を管理するようにすれば、１つの管理データを参照するだけで複数のパケットのデータを参照することができ、データ領域を効率的に使用することができるとともに、キュー内のデータの参照処理を高速化することができる。
【００１３】
また、アドレスリストの中の書き込み完了位置、読み出し完了位置を保持するようにすれば、次の書き込み位置や管理するデータが無くなったことが容易に分かり、キューの処理を効率化することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明を図面を参照して説明する。
【００１５】
図１は本発明の一実施形態のネットワーク中継装置を示すブロック図である。
【００１６】
図１において、本実施形態のネットワーク中継装置は、パケットを受信する受信部１１と、受信したパケットのヘッダからパケットの種別を識別するパケット識別部１２と、パケット識別部１２の識別結果によりパケットをキューに繋いで管理するキュー管理部１３と、キュー管理部１３が優先度などによって出力するパケットをルーティング処理する中継処理部１４と、ルーティング処理が施されたパケットを送信する送信部１５とを備えている。
【００１７】
キュー管理部１３は、パケット識別部１２から受け取ったパケットをキューに繋げるライト部１３１と、パケットのデータを格納するバッファメモリ１３２と、バッファメモリ１３２への書き込み・読み出しの制御を行うバッファ制御部１３３と、バッファメモリ１３２の領域の空き・塞がりを管理するバッファ管理部１３４と、予め設定されたタイミングで優先度の高いキューのパケットから、バッファメモリ１３２からパケットデータを読み出して中継処理部１４に送るリード部１３５と、優先度やパケットの種別や宛先などによって設けられているキュー毎に、その先頭（Top）と後尾（Last）を管理するキュー管理テーブル１３６とを備えている。
【００１８】
図２は、バッファメモリ１３２でのパケットデータの格納例を示す図である。
【００１９】
図２に示すように、バッファメモリ１３２は、３２バイト単位の領域で管理されており、各領域にはアドレスが付与され、パケットの実データ、もしくは実データを格納している領域を管理する管理データが格納される。
【００２０】
図３は、管理データの構成を示す図である。
【００２１】
図３に示すように、このデータは、実データを格納している領域の情報を格納する２バイトデータのアドレス情報（ａ１〜ａ１４）１４個からなるアドレスリストと、キューにおける次の管理データのアドレスを格納する３バイトデータのネクスト（Ｎｅｘｔ）と、書き込み・読み出しポインタを格納する１バイトデータのポインタ（Ｐ）とからなる。
【００２２】
それぞれのアドレス情報の、０〜７ビット目の８ビットは、データが格納されている領域のアドレスを示し（Ａｄｄｒｅｓｓ：書き込みアドレス）、８〜１２ビット目の５ビットは、最終パケットの場合の３２バイトの領域内の何バイトまでが有効データなのか（１〜３２）を示し（ＬＮＧ）、１３ビット目の１ビットは、パケットの最終を示し（ＥＯＰ：１なら最終）、１４ビット目の１ビットは、パケットの先頭を示している（ＳＯＰ：１なら先頭）。なお、１５ビット目は０を設定する。
【００２３】
ポインタの、０〜３ビット目の４ビット（読み出しポインタ）は、ａ１〜ａ１４のアドレス情報に格納されたアドレスの領域のうち、読み出しが終了した領域のアドレスを格納したアドレス情報の番号（１〜１４）が設定され、４〜７ビット目の４ビット（書き込みポインタ）は、ａ１〜ａ１４のアドレス情報のうち、書き込みが終了した領域のアドレスを格納したアドレス情報の番号（１〜１４）が設定される。
【００２４】
図２の例では、アドレス０から２番地には、キュー０の１番目のパケットが格納されている（１／３〜３／３）。
【００２５】
３番地には、これらデータを格納している領域の管理データが格納されている。１番目から３番目のアドレス情報（ａ１〜ａ３）の書き込みアドレスにはデータが格納されている領域のアドレス（０〜２）が設定され、１番目のアドレス情報（ａ１）のＳＯＰが１に設定され、３番目のアドレス情報（ａ３）のＥＯＰが１に設定されるとともに、ＬＮＧに書き込みアドレスに設定されたアドレス（２番地）に格納されたデータの有効バイト数が設定される。
【００２６】
なお、図中の管理データのアドレスリスト（ａ１〜ａ１４）の数字は、データが格納された領域のアドレスを示し、上部のＳはＳＯＰが１であることを示し、ＥはＥＯＰが１であることを示している。また、ポインタの内容については、後述する。
【００２７】
以降、同様に、４〜６番地には、キュー０の２番目のパケットが格納され、７〜１１番地には、キュー０の３番目のパケットが格納され、１２〜１６番地には、キュー０の４番目のパケットが格納される。
【００２８】
ここで、４番目のパケットの管理データを格納する途中で、３番地の管理データのアドレスリストを使い切ってしまう。その場合、新しい管理データ用の領域を確保し（図では１７番地）、３番地の管理データのネクストに次の管理データのアドレスを格納する。
【００２９】
そして、１７番地のアドレスリストの１番目と２番目のアドレス情報（ａ１、ａ２）に４番目のパケットの続きの領域のアドレスが格納される。
【００３０】
このようにして、データを格納した領域を管理する管理データを、キュー毎に順に辿れるようにしている。
【００３１】
同様に、キュー１の１番目のパケットは、１８〜２４番地に格納され、管理データは２５番地に格納され、２６〜２８番地に格納された２番目のパケットの管理データも格納される。
【００３２】
ポインタの書き込みポインタは、図２の３番地の管理データでは、１４番目のアドレス情報までデータが書き込まれた領域のアドレスが格納されているので、１４が設定され、１７番地の管理データでは、ａ２までデータが書き込まれた領域のアドレスが格納されているので２が設定され、２５番地の管理データでは、ａ１１までデータが書き込まれた領域のアドレスが格納されているので、１１が設定される。
【００３３】
そして、新たにデータの書き込みをする場合は、書き込みポインタの次のアドレス情報から書き込みアドレスなどを格納し、最後に書き込んだ領域のアドレスを設定したアドレス情報の番号を新しい書き込みポインタとする。
【００３４】
読み出しポインタは、図２の例では、読み出しはされていない状態を示しているので、どの管理データの読み出しポインタも０が設定されている。
【００３５】
そして、データの読み出しをする場合は、読み出しポインタの次のアドレス情報の書き込みアドレスに設定されているアドレスの領域から読み出しを行い、最後に読み出した領域のアドレスが設定されたアドレス情報の番号を新しい読み出しポインタとする。このとき、新しい読み出しポインタと書き込みポインタの値が同じになった場合、その管理データには管理するデータが無くなったことを示しているので、管理データの領域を解放する。
【００３６】
キュー管理テーブル１３６は、図２の例では、キュー０の管理データは、３番地、１７番地の順なので、先頭には３が設定され、後尾には１７が設定され、キュー１の管理データは２５番地のみなので、先頭、後尾ともに２５が設定される。
【００３７】
このようなネットワーク中継装置において、受信部１１で受信されたパケットは、パケット識別部１２に送られる。
【００３８】
パケット識別部１２は、受信したパケットの種別や宛先アドレスや送信元アドレスなどを参照して識別し、優先度や送信元アドレスや受信先アドレス毎に設けられたキューのどのキューに繋ぐかを決定し、決定したキューに付与されているキューＩＤ（ＱＩＤ）などを制御データとしてパケットに付与してキュー管理部１３に送る。
【００３９】
キュー管理部１３のライト部１３１は、パケットのデータを受け取ると、受け取ったデータの長さを認識し、このデータが格納できる分の空き領域をバッファ管理部１３４に要求する。
【００４０】
バッファ管理部１３４からアドレスが割り当てられると、ライト部１３１は、バッファ制御部１３３を介して、割り当てられたアドレスに受け取ったデータを書き込む。
【００４１】
データの書き込みが終了すると、ライト部１３１は、制御データに設定されているキューＩＤを読み出して、キュー管理テーブル１３６からそのキューＩＤのキューの先頭と後尾のアドレスを読み出す。
【００４２】
そして、読み出したキューの先頭、後尾の値が空であるか判定し、空であれば、管理データ用の領域をバッファ管理部１３４に要求し、割り当てられた領域に、データを書き込んだ領域のアドレスやＳＯＰやＥＯＰやＬＮＧなどを書き込み、書き込みポインタをパケットの最後の部分を書き込んだ領域のアドレスを設定したアドレス情報の番号に書き換える。
【００４３】
このとき、管理データのアドレスリストのアドレス情報を全て使ってしまったら、バッファ管理部１３４に新しい管理データ用の領域を要求し、割り当てられた領域のアドレスを前の管理データ（アドレス情報を使い切った管理データ）のネクストに書き込むとともに、書き込みポインタに１４を設定する。
【００４４】
そして、割り当てられた領域に、新たにアドレス情報及び書き込みポインタを書き込み、キュー管理テーブル１３６の当該キューの先頭のアドレス及び後尾のアドレスを新しい管理データのアドレスに書き換える。
【００４５】
読み出したキューの先頭、後尾の値が空でなければ、読み出したキューの後尾のアドレスの管理データに、データを書き込んだ領域のアドレスやＳＯＰやＥＯＰやＬＮＧなどを書き込み、書き込みポインタをパケットの最後の部分を書き込んだ領域のアドレスを設定したアドレス情報の番号に書き換える。
【００４６】
このとき、管理データのアドレスリストのアドレス情報を全て使ってしまったら、上述のときと同様に、バッファ管理部１３４から新しい管理データ用の領域を割り当ててもらい、前の管理データ（アドレス情報を使い切った管理データ）のネクスト及び書き込みポインタを書き換え、割り当てられた領域に、新たにアドレス情報及び書き込みポインタを書き込み、キュー管理テーブル１３６の当該キューの後尾のアドレスを新しい管理データのアドレスに書き換える。
【００４７】
このようにしてキューに繋がれたパケットは、リード部１３５が、キューの優先度などに応じて、予め設定されたタイミングでキューＩＤによりキュー管理テーブル１３６からキューの先頭と後尾のアドレスを読み出し、バッファ制御部１３３を介して、先頭のアドレスの管理データを読み出す。
【００４８】
読み出した管理データの読み出しポインタを参照し、読み出しポインタの次のアドレス情報を参照し、ＳＯＰが１になっているのを確認して、バッファ制御部１３３を介して書き込みアドレスに設定されているアドレスの領域からデータを読み出す。
【００４９】
同様に、ＥＯＰが１のアドレス情報まで、順に書き込みアドレスに設定されているアドレスの領域からデータを読み出して繋げ、ＥＯＰが１のアドレス情報の書き込みアドレスに設定されているアドレスの領域のデータを読み出して繋げてパケットを再生し、再生したパケットを中継処理部１４に送る。
【００５０】
パケットを中継処理部１４に送ったら、管理データの読み出しポインタを更新し、更新した読み出しポインタと書き込みポインタとを比較し、値が異なっていれば処理を終了する。
【００５１】
更新した読み出しポインタと書き込みポインタの値が同一であれば、管理している領域が無くなったとともに、キューのデータも無くなったことを示しているので、キュー管理テーブル１３６の該当キューＩＤの先頭、後尾の値を空にし、バッファ管理部１３４に当該管理データの領域の解放を要求し、処理を終了する。
【００５２】
データの読み出し中に、アドレスリストの最後のアドレス情報まできてもＥＯＰが１でなかった場合、アドレスリストの最後のアドレス情報の書き込みアドレスに設定されているアドレスの領域からデータを読み出して繋げた後、管理情報のネクストを参照し、ネクストに設定されたアドレスの領域に格納されている管理データを参照し、読み出しポインタが０であることを確認し、１番目のアドレス情報から書き込みアドレスに設定されているアドレスの領域のデータを読み出して繋げ、ＥＯＰが１のアドレス情報まで読み出しを行ってパケットを再生し、再生したパケットを中継処理部１４に送る。
【００５３】
パケットを中継処理部１４に送ったら、管理データの読み出しポインタを更新し、更新した読み出しポインタと書き込みポインタとを比較し、値が異なっていればキュー管理テーブル１３６の当該キューの先頭の値を、次の管理データのアドレスに書き換え、前の管理データの領域の解放をバッファ管理部１３４に要求し、処理を終了する。
【００５４】
更新した読み出しポインタと書き込みポインタの値が同一であれば、管理している領域が無くなったとともに、キューのデータも無くなったことを示しているので、キュー管理テーブル１３６の該当キューＩＤの先頭、後尾の値を空にし、バッファ管理部１３４に当該管理データの領域の解放を要求し、処理を終了する。
【００５５】
中継処理部１４は、キュー管理部１３からパケットのデータを受け取ると、予め設定された情報に従って、パケットの宛先アドレスの書き換えなどのルーティング処理を行い、送信部１５によりパケットを送信する。
【００５６】
このように本実施形態においては、バッファメモリ１３２に格納したパケットデータの管理データとして、パケットデータを格納したそれぞれのアドレスを複数管理し、キューとしてこの管理データを順に繋げたので、連続した領域でなくてもデータを格納して管理することができ、また、可変長のデータであっても容易に管理することができ、データ領域を効率的に使用することができる。
【００５７】
また、１つの管理データ内の複数のアドレスに複数のパケットデータのアドレスを格納することができれば、１つの管理データで複数のパケットデータを管理することができ、データ領域を効率的に使用することができるとともに、管理データを１つ参照しただけで複数のパケットデータを参照することができ、キュー内のデータの参照処理を高速化することができる。
【図面の簡単な説明】
【００５８】
【図１】本発明の一実施形態のネットワーク中継装置を示す図であり、そのブロック図である。
【図２】そのバッファメモリへのパケットデータの格納方法を示す図である。
【図３】その管理データの構成を示す図である。
【符号の説明】
【００５９】
１１  受信部
１２  パケット識別部
１３  キュー管理部
１３１  ライト部
１３２  バッファメモリ
１３３  バッファ制御部
１３４  バッファ管理部
１３５  リード部
１３６  キュー管理テーブル
１４  中継処理部
１５  送信部
【図１】
2006014186.tif 000003
【図２】
2006014186.tif 000004
【図３】
2006014186.tif 000005