バッファメモリ装置、及び、バッファリング方法
【課題】バッファメモリを用いた装置において、ソフトエラーの発生によって使用されなくなったバッファメモリの領域を再度使用することを目的とする。
【解決手段】バッファ内の領域にデータを記憶し、当該バッファ内の領域からデータを読み出すバッファメモリ装置は、データを前記バッファ内の空き領域に書き込み、前記バッファ内の領域からのデータの読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とし、データが書き込まれてから所定の時間が経過した廃棄領域を検出し、検出した廃棄領域を空き領域とする。
【解決手段】バッファ内の領域にデータを記憶し、当該バッファ内の領域からデータを読み出すバッファメモリ装置は、データを前記バッファ内の空き領域に書き込み、前記バッファ内の領域からのデータの読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とし、データが書き込まれてから所定の時間が経過した廃棄領域を検出し、検出した廃棄領域を空き領域とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソフトエラーにより使用できなくなったバッファを復旧する技術に関する。
【背景技術】
【０００２】
バッファメモリを備える装置、例えば、パケットを転送するスイッチ等の通信装置は、受信したパケットをバッファメモリに一旦蓄積し、ＱｏＳ（Quality of Service）等を考慮した順序でパケットをバッファメモリから読み出して送出している。
【０００３】
このような通信装置においては、不具合が発生すると通信に少なからず影響を与えることから、不具合を容易に判定する技術が提案されている。
【０００４】
例えば、バッファメモリを複数に分割して線形リスト構造で管理する通信装置において、バッファメモリの不具合の一つであるオーバーフローを容易に判定する技術が提案されている（特許文献１等参照）。
【０００５】
また、通信装置においては、不具合が発生してもできる限り処理を続行する必要があるため、バッファメモリの領域からデータを読み出そうとしたときに何らかの理由でエラーとなった場合には、その領域を廃棄し、その他の領域を用いて処理を続行する。
【０００６】
ここで、近年、半導体デバイスの微細化、高集積化、及び、低電圧化等が進み、半導体デバイスにソフトエラーが発生する確率が高くなってきている。ソフトエラーとは、ハードウェアに異常が見られない一過性の不良をいう。例えば、メモリに記憶されているデータが書き換えられていたようなエラーであって、そのメモリ素子には異常がなく、データを再度書き込めば正常に動作するようなエラーである。
【０００７】
このようなソフトエラーは、いつ起こるか分からず、また、発生頻度もそう多くはない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００４−２８０３３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、上述のような通信装置では、バッファメモリの領域からデータを読出す際に発生したエラーがソフトエラーによるものである場合は、廃棄された領域に問題が無いにもかかわらず使用されないことになる。
【００１０】
そこで、本発明は、バッファメモリを用いた装置において、ソフトエラーの発生によって使用されなくなったバッファメモリの領域を再度使用することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の１形態に係るバッファメモリ装置は、バッファ内の領域にデータを記憶させ、当該バッファ内の領域からデータを読み出すバッファメモリ装置であって、データを前記バッファ内の空き領域に書き込む書込手段と、前記バッファ内の領域からデータを読み出す読出手段であって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出手段と、前記書込手段によってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧手段と、を有する。
【発明の効果】
【００１２】
上記構成のバッファメモリ装置は、ソフトエラーの発生によって使用されなくなったバッファメモリの領域を再度使用することができる。
【図面の簡単な説明】
【００１３】
【図１】パケット転送装置の機能的構成の例を示すブロック図である。
【図２】パケット転送装置においてバッファリング処理を行う機能部の詳細を示す図である。
【図３】パケットバッファ及びテーブル等の関連を示す図である。
【図４】パケットバッファ及びテーブルの使用例を示す図である。
【図５】廃棄要素バッファの判定方法を示す図である。
【図６】パケットの書込み処理を示すフローチャートである。
【図７】パケットの書込み処理のタイムチャート（１）である。
【図８】パケットの書込み処理のタイムチャート（２）である。
【図９】パケットの書込み処理のタイムチャートである。
【図１０】パケットの読出し処理を示すフローチャートである。
【図１１】パケットの読出し処理のタイムチャート（１）である。
【図１２】パケットの読出し処理のタイムチャート（２）である。
【図１３】復旧処理を示すフローチャートである。
【図１４】復旧処理のタイムチャートである。
【図１５】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（１）である。
【図１６】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（２）である。
【図１７】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（３）である。
【図１８】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（４）である。
【図１９】パケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図（１）である。
【図２０】パケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図（２）である。
【図２１】廃棄要素バッファが発生した後のパケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【図２２】廃棄要素バッファが発生した後のパケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【図２３】復旧処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【発明を実施するための形態】
【００１４】
＜実施形態＞
実施形態のバッファメモリ装置は、バッファメモリの領域に記憶されたデータが読み出されるまでの通常の時間を推定し、その推定時間を超えてもデータが読み出されていない領域を空き領域とするものである。すなわち、通常は読み出されているはずのデータが未だ読み出されていないので、今後も読み出されることはないであろうと推定して使用するものである。
【００１５】
実施形態のバッファメモリ装置は、スイッチ等のパケット転送装置で用いられているバッファメモリ装置であり、バッファメモリを複数の領域（以下、「要素バッファ」という。）に分割し、線形リスト構造で管理している。具体的には、パケットを記憶している要素バッファをつなげたパケットキューと、パケットを記憶していない空き要素バッファをつなげた空キューとの２種類のキューを用いて管理する。尚、パケットキューは、パケットの種類により複数ある。
【００１６】
パケットキューの要素バッファは、記憶しているデータが読み出されると空きキューにつながれ再利用される。
【００１７】
データ読出しの際、要素バッファを指すアドレスに誤りがある場合はエラーアドレスとして、そのアドレスを廃棄する。要素バッファを指すアドレスが廃棄されると、そのアドレスによるリンクが切れることから、そのリンク以降のキューにつなげられている要素バッファは全て廃棄されることになる。またこの場合、エラーアドレスが指すはずであった要素バッファが不明であることから、どの要素バッファが廃棄されたかを知ることはできない。
【００１８】
そこで、実施形態のバッファメモリ装置では、要素バッファにデータが記憶されてからの経過時間を基に、廃棄された要素バッファであるか否かを判断する。
【００１９】
しかし、スイッチ等のパケット転送装置では、パケットの受信タイミングと送信タイミングはパケットの種類に依存する。従って、要素バッファにデータが残っている場合に、まだ送信する順番が来ないためにデータ読み出されていないのか、廃棄されていずれのキューにもつながれていないためにデータが読み出されていないのかを判断することは容易ではない。
【００２０】
実施形態のバッファメモリ装置は、正常な状態において、要素バッファに記憶されたデータが読み出されるまでの最長の時間を推定し、バッファメモリの領域に記憶されたデータが、推定時間を超えても未だ読み出されていない要素バッファは、廃棄された要素バッファであると判断する。
【００２１】
廃棄された要素バッファであると判断された要素バッファを、空き要素バッファとして再び使用することにより、バッファメモリを無駄なく有効に使用することが可能となる。
【００２２】
以下、スイッチ等のパケット転送装置で用いられているバッファメモリ装置を例に説明する。
【００２３】
＜機能＞
以下、図１を用いて、パケット転送装置１００の機能について説明する。
【００２４】
図１は、パケット転送装置１００の機能的構成の例を示すブロック図である。
【００２５】
パケット転送装置１００は、受信したパケットをバッファメモリに蓄積し、ＱｏＳ等を考慮した順序でパケットをバッファメモリから読み出して送信する。すなわち、スイッチ等が通常有する転送機能を有するが、図１においては、バッファメモリに関係する機能部を中心に記載している。また、図１において、点線矢印はパケットの流れを示す。
【００２６】
パケット転送装置１００は、受信部１１０、送信部１２０、書込部１３０、帯域制御部１４０、読出部１５０、バッファリング管理部１６０及びパケットバッファ２００を有する。
【００２７】
受信部１１０は、パケット２０を受信し、書込部１３０に依頼して、受信したパケットをパケットバッファ２００に記憶させる機能を有する。
【００２８】
書込部１３０は、受信部１１０から受け取ったパケット２０をパケットバッファ２００に記憶させる機能を有する。パケットバッファ２００内のアドレスを、書込部１３０はバッファリング管理部１６０から取得する。
【００２９】
送信部１２０は、読出部１５０から渡されたパケット２１を送信する機能を有する。
【００３０】
読出部１５０は、帯域制御部１４０からの指示により、パケットバッファ２００に記憶されているパケット２１を読み出して送信部１２０に渡す機能を有する。パケット２１を読み出すパケットバッファ２００内のアドレスを、読出部１５０はバッファリング管理部１６０から取得する。
【００３１】
帯域制御部１４０は、パケットバッファ２００に記憶されているパケットを、どのような順序で送信するかを管理する機能を有する。パケットを送信する順序は、書込部１３０から渡される情報に基づいて、パケットが属する通信に保障すべき帯域等に応じて帯域制御部１４０が定める。
【００３２】
次に、バッファリング管理部１６０は、エラー判定部１７０、時間カウンタ１８０及び復旧処理部１９０の３つの機能部と、リンク管理テーブル２１０、使用中フラグテーブル２２０、書込時間テーブル２３０、ＨＥＡＤ／ＴＡＩＬテーブル２４０、キュー長管理テーブル２５０及び空キュー管理テーブル２６０の６つのテーブルを有する。
【００３３】
バッファリング管理部１６０は、これらの３つの機能部と６つのテーブルを用いて、パケットバッファ２００の要素バッファを管理する機能を有する。バッファリング管理部１６０がパケットバッファ２００を管理する方法については、＜パケットバッファの使用方法＞の項で説明する。
【００３４】
エラー判定部１７０は、要素バッファを指すアドレスに誤りがあるか否かを判定する機能を有する。具体的には、要素バッファからパケットを読み出す際のアドレスが誤っていないか否かを判定する。このアドレスは、リンク管理テーブル２１０に登録されているアドレスである。実施形態では、例えば、ＥＣＣ（Error Correcting Code） Ｍｕｌｔｉ ｂｉｔ ｅｒｒｏｒが発生した場合にエラーアドレスであると判定するものとする。従って、リンク管理テーブル２１０には、登録されているアドレス毎に誤り訂正符号が付加されているものとする。
【００３５】
時間カウンタ１８０は、要素バッファが、廃棄された要素バッファ（以下、「廃棄要素バッファ」という。）であるか否かを判断するために用いるタイマである。時間カウンタ１８０がカウント値を更新する周期、及び、廃棄要素バッファであるか否かを判断する方法は、＜廃棄要素バッファの判定方法＞の項で説明する。
【００３６】
復旧処理部１９０は、パケットバッファ２００から廃棄要素バッファを見つけ出して、空き要素バッファとする処理（以下、「復旧処理」という。）を実行する機能を有する。
【００３７】
リンク管理テーブル２１０は、パケットバッファ２００の要素バッファのキューを構築する機能を有する。
【００３８】
使用中フラグテーブル２２０は、パケットバッファ２００の各要素バッファの使用状態を記憶しておく機能を有する。
【００３９】
書込時間テーブル２３０は、パケットバッファ２００の各要素バッファにパケットが書き込まれた時間を記憶しておく機能を有する。具体的には、書き込まれたときに、時間カウンタ１８０が示しているカウント値を記憶しておく。
【００４０】
ＨＥＡＤ／ＴＡＩＬテーブル２４０は、複数のパケットキューそれぞれの、先頭の要素バッファのアドレス（以下、「ＨＥＡＤアドレス」という。）と末尾の要素バッファのアドレス（以下、「ＴＡＩＬアドレス」という。）とを記憶しておく機能を有する。キューに新たな要素バッファがつながった場合等には、ＨＥＡＤアドレス又はＴＡＩＬアドレスが書き換わることになる。
【００４１】
キュー長管理テーブル２５０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０で管理している各パケットキューにつながっている要素バッファの数を記憶しておく機能を有する。
【００４２】
空キュー管理テーブル２６０は、空き要素バッファをつなげた空キューの先頭の空き要素バッファのアドレス（以下、「ＴＯＰアドレス」という。）と末尾の空き要素バッファのアドレス（以下、「ＥＮＤアドレス」という。）とを記憶しておく機能を有する。
【００４３】
ここで、図２に、図１に示したパケット転送装置１００の機能部のうち、バッファリング処理を行う機能部の詳細を示す。
【００４４】
テンポラリバッファ１は、受信するパケット長を測定するまでの待ち合わせ用のバッファである。ユーザ識別２は、受信したパケットのユーザを識別する機能を有し、受信したパケットをキューイングするパケットキューの番号を決定する。尚、図２では、Ｅｔｈｅｒパケットを記載しており、「ＳＡ」又は「ＶＩＤ」等を基にキュー番号を決定する。パケット長測定３は、受信したパケットの長さを測定し、ＥｎＱ処理部４にパケットの格納を指示する。図１の受信部１１０は、テンポラリバッファ１、ユーザ識別２、及び、パケット長測定３等によって実現される。
【００４５】
ＥｎＱ処理部４は、パケット長測定３からの指示により、テンポラリバッファ１からパケットを受信してパケットバッファメモリ７に格納する。図１の書込部１３０は、ＥｎＱ処理部４等によって実現される。また、図１のパケットバッファ２００は、パケットバッファメモリ７に該当する。
【００４６】
ＲｅｓｅｒｖｅｄＴｏｐレジスタ５は、空き領域を管理する空キューの先頭の要素バッファのアドレスを示し、ＲｅｓｅｒｖｅｄＥＮＤレジスタ６は、空き領域を管理する空キューの末尾の要素バッファのアドレスを示す。図１の空キュー管理テーブル２６０は、ＲｅｓｅｒｖｅｄＴｏｐレジスタ５及びＲｅｓｅｒｖｅｄＥＮＤレジスタ６に該当する。
【００４７】
リンク管理メモリ８は、図１のリンク管理テーブル２１０を記憶しておくメモリである。また、キュー長管理メモリ９は、図１のキュー長管理テーブル２５０を記憶しておき、ＨＥＡＤ／ＴＡＩＬメモリ１０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０を記憶しておくメモリである。
【００４８】
ＤｅＱ処理部１１は、パケットバッファメモリ７からパケットを読み出す。図１の読出部１５０は、ＤｅＱ処理部１１によって実現される。
【００４９】
帯域制御部１２は、ユーザ毎の帯域制御を行う。例えば、トークンバケット方式のシェーパー等が該当する。図１の帯域制御部１４０は、帯域制御部１２によって実現される。
【００５０】
アドレス損失復旧処理部１３は、パケットバッファメモリ７の使用状況の管理と、損失したアドレスの検出及び復旧を行う。時間カウンタ１４は、いわゆるタイマであり、図１の時間カウンタ１８０に該当する。また、使用中フラグメモリ１５は、使用中フラグテーブル２２０を記憶しておき、書込み時間メモリ１６は書込時間テーブル２３０を記憶しておくメモリである。図１のバッファリング管理部１６０の処理は、アドレス損失復旧処理部１３、ＥｎＱ処理部４及びＲｅｓｅｒｖｅｄＴｏｐレジスタ５等によって実現される。
【００５１】
＜テーブル＞
以下、パケットバッファ２００、リンク管理テーブル２１０、使用中フラグテーブル２２０、書込時間テーブル２３０、ＨＥＡＤ／ＴＡＩＬテーブル２４０、キュー長管理テーブル２５０及び空キュー管理テーブル２６０について、図３を用いて説明する。
【００５２】
図３は、パケットバッファ２００及びテーブル等の関連を示す図である。
【００５３】
パケットバッファ２００は、所定サイズの領域に分割されている。この分割された１領域が、１要素バッファである。実施形態では、パケットバッファ２００は１６個の要素バッファで構成されているものとする。以下、それぞれの要素バッファを、要素バッファ［０］〜要素バッファ[１５]という。添字の「０」〜「１５」をそれぞれの要素バッファの番号という。
【００５４】
リンク管理テーブル２１０は、パケットバッファ２００の要素バッファの数と同じ１６個の配列を有する。以下、この配列の要素を、リンク管理テーブル［０］〜リンク管理テーブル［１５］という。リンク管理テーブル２１０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。また、リンク管理テーブル２１０の各要素には、自要素が対応する要素バッファの次につながっている要素バッファのアドレスが記憶されている。例えば、要素バッファ［０］の次に要素バッファ［１］がつながっているとすると、リンク管理テーブル［０］には、要素バッファ［１］のアドレス「Ａ１」が記憶されている。
【００５５】
使用中フラグテーブル２２０は、パケットバッファ２００の要素バッファの数と同じ１６個の配列、例えば、ビット配列を有する。以下、この配列の要素を、使用中フラグテーブル［０］〜使用中フラグテーブル［１５］という。使用中フラグテーブル２２０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。
【００５６】
使用中フラグテーブル[０]が「１」の場合は、要素バッファ[０]にパケットが記憶されていることを示す。一方、「０」の場合は、要素バッファ[０]は空領域であることを示す。使用中フラグテーブル[１]〜使用中フラグテーブル［１５］も同様である。
【００５７】
書込時間テーブル２３０も、パケットバッファ２００の要素バッファの数と同じ１６個の配列を有する。以下、この配列の要素を、書込時間テーブル［０］〜書込時間テーブル［１５］という。書込時間テーブル２３０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。
【００５８】
書込時間テーブル２３０には、対応する要素バッファにパケットが書き込まれた時の、時間カウンタ１８０の値が記憶されている。例えば、書込時間テーブル［０］が「０」の場合は、要素バッファ［０］にパケットが書き込まれた時に、時間カウンタ１８０のカウント値が「０」であったことを示している。
【００５９】
ＨＥＡＤ／ＴＡＩＬテーブル２４０は、パケットキューを管理する機能を有し、管理するパケットキューの数分の配列を有する。実施形態では、２つのパケットキューを管理するものとする。以下、この配列の要素を、ＨＥＡＤ／ＴＡＩＬテーブル［０］及びＨＥＡＤ／ＴＡＩＬテーブル［１］といい、添え字は各要素で管理するキューの番号を示す。
【００６０】
また、１つの配列は、ＨＥＡＤアドレスとＴＡＩＬアドレスとで構成され、それぞれＨＥＡＤ［０］、ＴＡＩＬ［０］のように言う。ＨＥＡＤアドレスは、キューの先頭の要素バッファのアドレスを記憶し、ＴＡＩＬアドレスは、キューの末尾の要素バッファのアドレスを記憶する。
【００６１】
キュー長管理テーブル２５０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０で管理するパケットキューの数と同じ２個の配列を有する。以下、この配列の要素を、キュー長管理テーブル［０］及びキュー長管理テーブル［１］という。キュー長管理テーブル２５０の配列の要素の番号は、ＨＥＡＤ／ＴＡＩＬテーブル２４０の配列の番号と対応している。
【００６２】
空キュー管理テーブル２６０は、空キューを管理する機能を有し、ＴＯＰアドレスとＥＮＤアドレスとで構成される。ＴＯＰアドレスは、空キューの先頭の要素バッファのアドレスを記憶し、ＥＮＤアドレスは、キューの末尾の要素バッファのアドレスを記憶する。
【００６３】
＜パケットバッファの使用方法＞
以下、バッファリング管理部１６０が、パケットバッファ２００を使用する方法について、図４を用いて説明する。
【００６４】
図４は、パケットバッファ２００及びテーブルの使用例を示す図である。
【００６５】
図４では、上部に、パケットバッファ２００及びテーブルの内容を示し、下部に、２つのパケットキュー、及び、空キューのイメージを示す。円は、要素バッファを示し、円の内部の数字は、円で示される要素バッファの番号を示す。また、パケットキュー［０］は、ＨＥＡＤ／ＴＡＩＬテーブル［０］で管理されるパケットキューを示し、パケットキュー［１］は、ＨＥＡＤ／ＴＡＩＬテーブル［１］で管理されるパケットキューを示す。空キューは、空キュー管理テーブル２６０で管理される空キューを示す。図１５等においても同様である。
【００６６】
パケットキュー［０］には、要素バッファ［０］、［１］、［２］、［５］の４つ要素バッファにパケットが書き込まれ、順番につながっている。
【００６７】
この要素バッファの順番は、リンク管理テーブル２１０によって、次のように管理されている。要素バッファ［０］に後続する要素バッファのアドレスは、リンク管理テーブル［０］に記憶されている「Ａ１」である。「Ａ１」は、要素バッファ［１］のアドレスである為、要素バッファ［０］に後続する要素バッファは要素バッファ［１］である。次に、要素バッファ［１］に後続する要素バッファのアドレスは、リンク管理テーブル［１］に記憶されている「Ａ２」である。従って、要素バッファ［１］に後続する要素バッファは要素バッファ［２］である。このように、キューが構築されている。
【００６８】
このパケットキュー［０］の先頭の要素バッファのアドレスと末尾の要素バッファのアドレスとを、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ／ＴＡＩＬテーブル［０］が記憶している。ＨＥＡＤ［０］及びＴＡＩＬ［０］は、それぞれ要素バッファ［０］のアドレス「Ａ０」及び要素バッファ［５］のアドレス「Ａ５」を記憶している。キュー長管理テーブル［０］は、つながっている要素バッファの個数「４」を記憶している。
【００６９】
また、使用中フラグテーブル［０］、［１］、［２］、［５］には、それぞれ「１」が設定されている。対応する要素バッファ［０］、［１］、［２］、［５］にパケットが書き込まれているからである。書込時間テーブル［０］、［１］、［２］、［５］には、要素バッファ［０］、［１］、［２］、［５］にパケットが書き込まれ時の時間カウンタ１８０の値「０」が設定されている。
【００７０】
同様に、パケットキュー［１］には、要素バッファ［３］、［４］の２つ要素バッファにパケットが書き込まれ、順番につながっている。
【００７１】
従って、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］及びＴＡＩＬ［１］は、それぞれ「Ａ３」及び「Ａ４」を記憶し、キュー長管理テーブル［１］は、「２」を記憶している。
【００７２】
また、使用中フラグテーブル［３］、［４］には、それぞれ「１」が設定されている。書込時間テーブル［３］、［４］には、要素バッファ［３］、［４］にパケットが書き込まれ時の時間カウンタ１８０の値「１」が設定されている。
【００７３】
また、空キューには、空き要素バッファがつながっている。空キュー管理テーブル２６０のＴＯＰアドレス及びＥＮＤアドレスは、それぞれ「Ａ６」及び「Ａ１５」を記憶している。
【００７４】
ここで、例えば、パケットキュー［０］の要素バッファ［０］に記憶されているデータが読み出されると、要素バッファ［０］は空き要素バッファとなり、空キューの末尾につながれる。
【００７５】
＜廃棄要素バッファの判定方法＞
次に、復旧処理において、パケットバッファ２００内の各要素バッファが、廃棄要素バッファであるか否かを判断する方法について、図５を用いて説明する。
【００７６】
図５は、廃棄要素バッファの判定方法を示す図である。図５においては、説明の便宜上、３つの要素バッファと関連するテーブルを記載している。
【００７７】
復旧処理は、時間カウンタ１８０がカウンタ値を更新する都度に実行する。下向き矢印は、復旧処理を実行するタイミングを示している（矢印３００等参照）。
【００７８】
まず、時間カウンタ１８０のカウンタ値は、所定の周期で、「０」、「１」、「２」と順に繰り返される（１段目の時間カウンタ１８０参照）。復旧処理はこの周期で実行される。
【００７９】
その周期は、要素バッファにパケットが書き込まれた時から読み出されるであろうと推測される時までの時間（以下、「滞留時間」という。）を基に決定する。
【００８０】
滞留時間が経過しているにも関わらずパケットが読み出されていない要素バッファを、廃棄要素バッファであると判断するからである。
【００８１】
実施形態では、時間カウンタ１８０のカウンタ値と、各要素バッファにパケットが書き込まれた時間を記憶している書込時間テーブル２３０とを基に、各要素バッファにパケットが書き込まれてから滞留時間が経過しているか否かを判断する。
【００８２】
まず、滞留時間は、パケット転送装置１００で転送するパケットを送信するユーザに割り当てられた帯域、いわゆる通信速度と、そのユーザが使用することが出来るパケットバッファ２００のサイズとに基づいて求める。
【００８３】
パケット転送装置１００で転送するパケットのうち、最も小さい帯域が割り当てられているパケットの滞留時間を、パケット転送装置１００の滞留時間とする。
【００８４】
例えば、あるユーザに割り当てられた帯域が、「１Ｇｂｐｓ（ｂｉｔ／秒）」であり、そのユーザに割り当てられたパケットバッファ２００内の領域のサイズが、「１Ｍ×１２８ｂｉｔ」であるとする。この場合、このユーザのパケットの滞留時間は、「１Ｍ×１２８ｂｉｔ／１Ｇｂｐｓ＝１２８ｍｓ」となる。
【００８５】
実施形態では、滞留時間が「１２８ｍｓ」の場合、周期を「１ｓｅｃ」とする。そして、時間カウンタ１８０のカウンタ値と、書込時間テーブル２３０に記憶されている値との差、すなわち、経過したカウント値（以下、「使用時間」という。）が「２」である要素バッファを、廃棄要素バッファであると判断する。使用時間が「２」である場合に廃棄バッファであると判断するのは、滞留時間を超過していないにもかかわらず廃棄要素バッファであると判断されてしまうことを防ぐためである。
【００８６】
図５を参照しながら、廃棄要素バッファの判定方法を説明する。
【００８７】
要素バッファ［０］にパケットが記憶されると（データ３０１参照）、使用中フラグテーブル［０］に「１」が設定され（３段目の使用中フラグテーブル２２０参照）、書込時間テーブル［０］に時間カウンタ１８０のカウンタ値「０」が設定される（４段目の書込時間テーブル２３０参照）。
【００８８】
時間カウンタ１８０のカウンタ値が、「０」から「１」に更新されると、復旧処理が実行され（矢印３００参照）、各要素バッファにパケットが書き込まれてからの時間である使用時間を算出する。最下段に示す「算出した使用時間」の配列の番号は、要素バッファの番号と対応しているものとし、使用時間［０］等というものとする。
【００８９】
使用時間は、使用中フラグテーブル２２０に設定されている値が「１」、すなわち、パケットが書き込まれている要素バッファに対してのみ行う。
【００９０】
ここでは、要素バッファ［０］のみにパケットが書き込まれているので、書込時間テーブル［０］から時間カウンタ１８０のカウンタ値「１」までの使用時間［０］は「１」となる。使用時間が「１」であるので、要素バッファ［０］は、廃棄要素バッファではないと判断される。
【００９１】
時間カウンタ１８０のカウンタ値が「１」の間に、要素バッファ［０］からパケットが読み出され、使用中フラグテーブル［０］に「０」が設定される。また、要素バッファ［１］にパケットが書き込まれ、使用中フラグテーブル［１］に「１」が設定され、書込時間テーブル［１］に時間カウンタ１８０のカウンタ値「１」が設定される。
【００９２】
次に、時間カウンタ１８０のカウンタ値が、「１」から「２」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。
【００９３】
時間カウンタ１８０のカウンタ値が「２」の間に、要素バッファ［２］にパケットが書き込まれ、使用中フラグテーブル［２］に「１」が設定され、書込時間テーブル［２］に時間カウンタ１８０のカウンタ値「２」が設定される。
【００９４】
次に、時間カウンタ１８０のカウンタ値が、「２」から「０」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。使用時間［１］が「２」となるため（使用時間３０３の斜線部分参照）、要素バッファ［１］は、廃棄要素バッファであると判断される。
【００９５】
次に、時間カウンタ１８０のカウンタ値が、「０」から「１」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。使用時間［２］が「２」となるため（使用時間３０４の斜線部分参照）、要素バッファ［２］は、廃棄要素バッファであると判断される。
【００９６】
＜動作＞
以下、実施形態のパケット転送装置１００の動作について図を用いて説明する。
【００９７】
パケット転送装置１００の動作として、４つの処理を説明する。
【００９８】
１つ目の処理は、パケットの書込み処理であり、図６〜図９、図１５〜１８を用いて説明する。
【００９９】
図６は、パケットの書込み処理を示すフローチャートであり、図７〜図９は、パケットの書込み処理のタイムチャートであり、図１５〜図１８は、パケットの書込み処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１００】
２つ目の処理は、パケットの読出し処理であり、図１０〜図１２、図１９及び図２０を用いて説明する。パケットの読出し処理が正常に行われる場合と、廃棄要素バッファが発生する場合とを説明する。
【０１０１】
図１０は、パケットの読出し処理を示すフローチャートであり、図１１及び図１２は、パケットの読出し処理のタイムチャートであり、図１９及び図２０は、パケットの読出し処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０２】
３つ目の処理は、廃棄要素バッファが発生した後の、パケットの読出し処理及び書込み処理であり、図２１及び図２２を用いて説明する。
【０１０３】
図２１は、パケットの読出し処理におけるパケットバッファ２００及びテーブルの遷移を示す図であり、図２２は、書込み処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０４】
４つ目の処理は、復旧処理であり、図１３、図１４、図２３を用いて説明する。
【０１０５】
図１３は、復旧処理を示すフローチャートであり、図１４は、復旧処理のタイムチャートであり、図２３は、復旧処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０６】
実施形態では、パケット転送装置１００が受信するパケットは可変長であり、パケットの長さに応じて、要素メモリを複数個使用するものとする。また、パケットバッファ２００の要素メモリは、全て同じサイズであるとする。
【０１０７】
図７等のタイムチャートにおいて、番号が同じクロックは、同じタイミングのクロックであるものとする。また、図７等においては、入力されるパケットは、Ｅｔｈｅｒパケット６４Ｂｙｔｅ長の例を示す。パケットバッファ２００のデータ幅を１２８ｂｉｔ幅とし、受信されるパケットのデータ幅も１２８ｂｉｔとする。すなわち、１要素バッファを、１２８ｂｉｔとする。
【０１０８】
キュー番号（ＱＩＤ）はパケットのヘッダ内のＶＩＤを用いる。また、パケット長（ＬＥＮＧＴＨ）は、パケットバッファ２００の要素バッファの使用数で表わす。従って、Ｅｔｈｅｒパケット６４Ｂｙｔｅのパケット長は、「６４Ｂｙｔｅ／１２８ｂｉｔ」で「４」となる。すなわち、パケットは４つに分割されて、それぞれ要素バッファに書き込まれる。以下、分割されたパケットを、パケット（１）、パケット（２）のように言うものとする。
【０１０９】
ＥＮＡＢＬＥは、受信されるパケットが有効である区間を表わしている。ＳＴＡＲＴはユーザパケットの先頭を、ＥＮＤはユーザパケットの末端を表している。
【０１１０】
尚、タイムチャートにおいて、各テーブルのアドレス「Ａ１」等は、各テーブル［１］等のアドレスを示すものとする。
【０１１１】
図１５等のパケットバッファ２００及びテーブルの遷移を示す図では、テーブル等で斜線が引かれている部分は、書き換えられたことを示す。
【０１１２】
また、パケットバッファ２００の配列要素の数字は、書き込まれているパケットの分割の番号を示す。
【０１１３】
＜パケットの書込み処理＞
まず、図６〜図９、図１５〜１８を用いてパケットの書込み処理について説明する。
【０１１４】
図１５は、パケット転送装置１００の起動時のテーブル及びキュー等の状態を示している。すなわち、空キューに、要素バッファ［０］〜要素バッファ［１５］がつながっている。また、使用中フラグテーブル２２０の各配列要素には「０」が設定されている。
【０１１５】
ここでは、図１５で示す初期状態から、３つのパケットを順次受信する場合を例に説明する。キュー番号「０」、パケット長「４」のパケットを受信し、キュー番号「１」、パケット長「６」のパケットを受信し、キュー番号「０」、パケット長「４」のパケットを受信する場合である。
【０１１６】
図１６は、図１５の状態から、最初のキュー番号「０」、パケット長「４」のパケットを受信し、パケットバッファ２００に記憶したときのテーブル及びキュー等の状態を示している。
【０１１７】
図１７は、図１６の状態から、キュー番号「１」、パケット長「６」のパケットを受信したときのテーブル等の状態を示し、図１８は、図１７の状態から、２つ目のキュー番号「０」パケット長「４」のパケットを受信したときのテーブル等の状態を示す。
【０１１８】
＜１つ目のパケットの書込み処理＞
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積する（図７の処理４００参照）と同時に、キュー番号「０」及びパケット長「４」を検出する（図７の処理４０１及び処理４０２参照）。
【０１１９】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号及びパケット長を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する（図７の処理４０３参照）。
【０１２０】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「０」を渡して、空き要素バッファのアドレスを要求する。
【０１２１】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ０」（図１５参照）を読み出して、書込部１３０に渡す。
【０１２２】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ０」の要素バッファ［０］にパケット（１）を書込む（ステップＳ１２０、図１６参照）。また、書込部１３０は、書き込んだパケットのヘッダ部から帯域制御部１４０が帯域の制御に必要な情報を読み出し、帯域制御部１４０に渡す。
【０１２３】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［０］に対応する使用中フラグテーブル２２０の配列要素、すなわち、使用中フラグテーブル［０］に「１」を設定する（ステップＳ１３０、図９の処理４２０、及び、図１６参照）。
【０１２４】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「１」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［０］に対応する書込時間テーブル２３０の配列要素、すなわち、書込時間テーブル［０］に「１」設定する（ステップＳ１４０、図９の処理４２１、及び、図１６参照）。
【０１２５】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１２６】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１２７】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１２８】
具体的に、バッファリング管理部１６０は、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］に加算し、「４」とする（図８の処理４１０、及び、図１６参照）。
【０１２９】
バッファリング管理部１６０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ０」で更新する（図８の処理４１１、及び、図１６参照）。
【０１３０】
また、バッファリング管理部１６０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［０］を、パケット（４）が書き込まれた要素バッファ［３］のアドレス「Ａ３」で更新する（図８の処理４１２、及び、図１６参照）。
【０１３１】
バッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）が書き込まれた要素バッファ［３］が対応するリンク管理テーブル［３］の内容である「Ａ４」で更新する（図８の処理４１３、及び、図１６参照）。
【０１３２】
＜２つ目のパケットの書込み処理＞
次に、パケット転送装置１００が、キュー番号が「０」、パケット長が「４」であるパケットを受信したあとに、キュー番号が「１」、パケット長が「６」であるパケットを受信する場合を説明する。
【０１３３】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積すると同時に、キュー番号「１」及びパケット長「６」を検出する。
【０１３４】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号「１」及びパケット長「６」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０１３５】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「１」を渡して、空き要素バッファのアドレスを要求する。
【０１３６】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ４」を読み出して、書込部１３０に渡す。
【０１３７】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ４」の要素バッファ［４］にパケット（１）を書込む（ステップＳ１２０）。
【０１３８】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［４］に対応する使用中フラグテーブル［４］に「１」を設定する（ステップＳ１３０、図９の処理４２２、及び、図１７参照）。
【０１３９】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「２」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［４］に対応する書込時間テーブル［４］に「２」設定する（ステップＳ１４０、図９の処理４２３、及び、図１７参照）。
【０１４０】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１４１】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（６）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「６」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１４２】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１４３】
具体的には、書込部１３０から渡されたパケット長「６」を、キュー長管理テーブル２５０のキュー長管理テーブル［１］に加算し、「６」とする（図８の処理４１４、及び、図１７参照）。
【０１４４】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ４」で更新する（図８の処理４１５、図１６、及び、図１７参照）。
【０１４５】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［１］を、パケット（６）が書き込まれた要素バッファ［９］のアドレス「Ａ９」で更新する（図８の処理４１６、及び、図１７参照）。
【０１４６】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（６）が書き込まれた要素バッファ［９］が対応するリンク管理テーブル［９］の内容である「Ａ１０」で更新する（図８の処理４１７、及び、図１７参照）。
【０１４７】
＜３つ目のパケットの書込み処理＞
次に、パケット転送装置１００が、キュー番号が「１」、パケット長が「６」であるパケットを受信したあとに、キュー番号が「０」、パケット長が「４」であるパケットを受信する場合を説明する。
【０１４８】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積すると同時に、キュー番号「０」及びパケット長「４」を検出する。
【０１４９】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号「０」及びパケット長「４」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０１５０】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「０」を渡して、空き要素バッファのアドレスを要求する。
【０１５１】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１０」を読み出して、書込部１３０に渡す。
【０１５２】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ１０」の要素バッファ［１０］にパケット（１）を書込む（ステップＳ１２０）。
【０１５３】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１０］に対応する使用中フラグテーブル［１０］に「１」を設定する（ステップＳ１３０）。
【０１５４】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「２」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［１０］に対応する書込時間テーブル［１０］に「２」設定する（ステップＳ１４０）。
【０１５５】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１５６】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１５７】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１５８】
具体的には、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］に加算し、「８」とする（図１７、及び、図１８参照）。
【０１５９】
パケットキュー［０］のキューの末尾に、今回受信したパケットを書き込んだ要素バッファ［１０］〜［１３］をつなげるために、現在のＴＡＩＬ［０］に記憶されているアドレス「Ａ３」が指す要素バッファ［３］に対億するリンク管理テーブル［３］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１０」で書き換える（図１７、及び、図１８参照）。また、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［０］を、パケット（４）を書き込んだ要素バッファ［１３］のアドレスである「Ａ１３」で更新する（図１８参照）。
【０１６０】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）を書き込んだ要素バッファ［１３］に対応するリンク管理テーブル［１３］の内容「Ａ１４」で更新する（図１８参照）。
【０１６１】
＜パケットの読出し処理＞
次に、図１０〜図１２、図１９〜図２０を用いてパケットの読出し処理を説明する。
【０１６２】
ここでは、図１８で示す状態から、キュー番号「０」、パケット長「４」のパケットを読み出し、キュー番号「１」、パケット長「６」のパケットを読み出す場合を説明する。但し、２つ目のキュー番号「１」、パケット長「６」のパケットを読み出す際にエラーが発生するものとする。
【０１６３】
図１９は、図１８の状態で、キュー番号「０」、パケット長「４」のパケットを読み出したときのテーブル及びキュー等の状態を示している。
【０１６４】
図２０は、図１９の状態で、キュー番号「１」、パケット長「６」のパケットの読み出す際にエラーが発生したときのテーブル等の状態を示す。
【０１６５】
以下、パケット転送装置１００が、２つのパケットをパケットバッファ２００から読み出す場合を説明する。
【０１６６】
＜１つ目のパケットの読出し処理＞
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「０」を渡して、読出部１５０にパケットの送信を依頼する。
【０１６７】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「０」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０１６８】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「０」のキューに要素バッファがつながれているかを判断する。具体的には、キュー長管理テーブル［０］の内容が「０」である場合は、要素バッファはつながれていないと判断する。
【０１６９】
要素バッファがつながれていない場合（ステップＳ２２０：Ｙｅｓ）、バッファリング管理部１６０は、読み出すべきパケットが記録されていない旨を読出部１５０に返す。
【０１７０】
読み出すべきパケットが記録されていない旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１７１】
一方、要素バッファがつながれている場合（ステップＳ２２０：Ｎｏ）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ０」を読み出す。
【０１７２】
ここでは、キュー長管理テーブル［０］の内容は「８」であるので（図１８参照）、バッファリング管理部１６０は、ＨＥＡＤ［０］の内容「Ａ０」を読み出す。
【０１７３】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０１７４】
依頼されたエラー判定部１７０は、渡されたアドレスがエラーアドレスであるか否かを判定して、結果をバッファリング管理部１６０に返す。
【０１７５】
判定結果がエラーアドレスである場合（ステップＳ２３０：Ｙｅｓ）、バッファリング管理部１６０は、キュー長管理テーブル［０］に「０」を設定し、エラーが発生した旨を書込部１３０に返す。
【０１７６】
エラーが発生した旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１７７】
一方、判定結果がエラーアドレスでない場合（ステップＳ２３０：Ｎｏ）、バッファリング管理部１６０は、アドレス「Ａ０」を読出部１５０に渡す。
【０１７８】
ここでは、アドレス「Ａ０」は、エラーアドレスではないので、アドレス「Ａ０」を受け取った読出部１５０は、渡されたアドレス「Ａ０」の要素バッファ［０］からパケット（１）を読み出す（ステップＳ２４０）。
【０１７９】
アドレスを読出部１５０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［０］に対応する使用中フラグテーブル２２０の配列要素、すなわち、使用中フラグテーブル［０］に「０」を設定する（ステップＳ２５０、図１２の処理５１０、及び、図１９参照）。
【０１８０】
読出部１５０は、パケットの読出しが終了するまで、要素バッファをバッファリング管理部１６０に要求し、ステップＳ２３０〜ステップ２５０の処理を繰り返す（ステップＳ２６０：Ｎｏ）。
【０１８１】
読出部１５０は、パケットの読出しが終了したら、すなわち、パケット（４）の読出しが終了したら（ステップＳ１６０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、読み出しが終了した旨を通知する。パケットの読出しの終了は、最後のパケットの部分、ここではパケット（４）に設定されている最後である旨を示すフラグを参照して判定する。
【０１８２】
終了通知を受けたバッファリング管理部１６０は、パケットの読出しの完了処理を行う（ステップＳ２７０）。
【０１８３】
具体的には、読出部１５０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］の値「８」から減算し、「４」とする（図１１の処理５００、図１８、及び、図１９参照）。
【０１８４】
パケットキュー［０］につながっている要素バッファ［０］〜［３］を、空き要素バッファとして空キューの末尾につなげる。空キュー管理テーブル２６０のＥＮＤアドレス「Ａ１５」で指す要素バッファ［１５］と対応するリンク管理テーブル［１５］の内容を、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ０」で更新する（図１１の処理５０１、処理５０２、図１８、及び、図１９参照）。パケット（４）を読み出した要素バッファ［３］のアドレス「Ａ３」で、ＥＮＤアドレスを更新する（図１の処理５０３、及び、図１９参照）。
【０１８５】
パケットキュー［０］から要素バッファ［０］〜［３］を外す。パケット（４）を読み出した要素バッファ［３］に対応するリンク管理テーブル２１０［３］の内容「Ａ１０」で、ＨＥＡＤ［０］を更新する（図１１の処理５０４、及び、図１９参照）。
【０１８６】
＜２つ目のパケットの読出し処理（エラー発生）＞
次に、パケット転送装置１００が、キュー番号が「０」、パケット長が「４」であるパケットを読み出したあとに、キュー番号が「１」、パケット長が「６」であるパケットの読出しに失敗する場合を説明する。
【０１８７】
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「１」を渡して、読出部１５０にパケットの送信を依頼する。
【０１８８】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「１」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０１８９】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「１」のキューに要素バッファがつながれているかを判断する。この場合、パケットキュー［１］には要素バッファがつながれているので（ステップＳ２２０：Ｎｏ）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］の内容「Ａ４」を読み出す。
【０１９０】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０１９１】
依頼されたエラー判定部１７０は、渡されたアドレス「Ａ４」がエラーアドレスであると判定して、結果をバッファリング管理部１６０に返す。
【０１９２】
エラーアドレスである旨の判定を受け取ったので（ステップＳ２３０：Ｙｅｓ）、バッファリング管理部１６０は、キュー長管理テーブル［０］に「０」を設定し、エラーが発生した旨を書込部１３０に返す（図２０参照）。
【０１９３】
エラーが発生した旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１９４】
この場合、キュー長管理テーブル［１］は「０」となるので、パケットキュー［１］には要素バッファがつながれていないとして、パケット転送装置１００の処理が続けられる。すなわち、ＨＥＡＤ［１］の内容「Ａ４」は無効として扱われ、リンク管理テーブル２１０に「Ａ４」は登録されていないこととなるため、「Ａ４」からつながっていた要素バッファ［４］〜［９］は、以後使用されることはない。すなわち、廃棄されたことになる。
【０１９５】
＜廃棄要素バッファが発生した後の、パケットの読出し処理及び書込み処理＞
次に、要素バッファ［４］〜［９］が廃棄された後に、パケットの読出し及び書込みが行われる場合を、図を用いて説明する。
【０１９６】
図２１は、図２０の状態で、キュー番号「０」パケット長「４」のパケットを読み出したときのテーブル等の状態を示す。パケット読出しの際のタイムチャートを図１１及び図１２に示す。
【０１９７】
図２２は、図２１の状態で、キュー番号「１」パケット長「４」のパケットを書込んだときのテーブル等の状態を示す。
【０１９８】
＜廃棄要素バッファが発生した後の、パケットの読出し処理＞
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「０」を渡して、読出部１５０にパケットの送信を依頼する。
【０１９９】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「０」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０２００】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「０」のキューに要素バッファがつながれているかを判断する。
【０２０１】
キュー長管理テーブル［０］の内容は「０」ではないので、（ステップＳ２２０：Ｎｏ、図２０参照）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ１０」を読み出す。
【０２０２】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０２０３】
ここでは、アドレス「Ａ１０」はエラーアドレスではないので（ステップＳ２３０：Ｎｏ）、バッファリング管理部１６０は、アドレス「Ａ１０」を読出部１５０に渡す。
【０２０４】
アドレス「Ａ１０」を受け取った読出部１５０は、渡されたアドレス「Ａ１０」の要素バッファ［１０］からパケット（１）を読み出す（ステップＳ２４０）。
【０２０５】
アドレスを読出部１５０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１０］に対応する使用中フラグテーブル［１０］に「０」を設定する（ステップＳ２５０、図１２の処理５１１参照）。
【０２０６】
読出部１５０は、パケットの読出しが終了するまで、要素バッファをバッファリング管理部１６０に要求し、ステップＳ２３０〜ステップ２５０の処理を繰り返す（ステップＳ２６０：Ｎｏ）。
【０２０７】
読出部１５０は、パケットの読出しが終了したら、すなわち、パケット（４）の読出しが終了したら（ステップＳ１６０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、読み出しが終了した旨を通知する。
【０２０８】
終了通知を受けたバッファリング管理部１６０は、パケットの読出しの完了処理を行う（ステップＳ２７０）。
【０２０９】
具体的には、読出部１５０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］から減算し、「０」とする（図１１の処理５０５、及び、図２１参照）。
【０２１０】
パケットキュー［０］につながっている要素バッファ［１０］〜［１３］を、空き要素バッファとして空キューの末尾につなげる。空キュー管理テーブル２６０のＥＮＤアドレス「Ａ３」で指す要素バッファ［３］と対応するリンク管理テーブル［３］の内容を、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ１０」で更新する（図１１の処理５０６、処理５０７、図２０、及び、図２１参照）。パケット（４）を読み出した要素バッファ［１３］のアドレス「Ａ１３」で、ＥＮＤアドレスを更新する（図１１の処理５０８、図２０、及び、図２１参照）。
【０２１１】
パケット（４）を読み出した要素バッファ［１３］に対応するリンク管理テーブル２１０［１３］の内容「Ａ１４」で、ＨＥＡＤ［０］を更新する（図１１の処理５０９、及び、図２１参照）。尚、キュー長管理テーブル［０］が「０」となった場合は、ＨＥＡＤ［０］を更新しなくてもよい。
【０２１２】
＜廃棄要素バッファが発生した後の、パケットの書込み処理＞
次に、要素バッファ［４］〜［９］が廃棄された後に、キュー番号「１」パケット長「４」のパケットを書込む場合を説明する。
【０２１３】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、キュー番号「１」及びパケット長「４」を検出する。受信部１１０は、検出したキュー番号「１」及びパケット長「４」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０２１４】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「１」を渡して、空き要素バッファのアドレスを要求する。
【０２１５】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１４」を読み出して、書込部１３０に渡す。
【０２１６】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ１４」の要素バッファ［１４］にパケット（１）を書込む（ステップＳ１２０）。また、書込部１３０は、書き込んだパケットのヘッダ部から帯域制御部１４０が帯域確保に必要な情報を読み出し、帯域制御部１４０に渡す。
【０２１７】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１４］に対応する使用中フラグテーブル［１４］に「１」を設定する（ステップＳ１３０、図２２参照）。
【０２１８】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［１４］に対応する書込時間テーブル［１４］に「０」設定する（ステップＳ１４０、図２２参照）。
【０２１９】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０２２０】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０２２１】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０２２２】
具体的には、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［１］に加算し、「４」とする（図２２参照）。
【０２２３】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１４」で更新する。
【０２２４】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［１］を、パケット（４）が書き込まれた要素バッファ［１］のアドレス「Ａ１」で更新する。
【０２２５】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）が書き込まれた要素バッファ［１］が対応するリンク管理テーブル［１］の内容である「Ａ２」で更新する。
【０２２６】
このように、廃棄された要素バッファ［４］〜［９］は、パケットの書込み及び読み込みにおいて、使用されることはない。
【０２２７】
＜復旧処理＞
次に、図１３、図１４、図２３を用いて復旧処理を説明する。
【０２２８】
ここでは、時間カウンタ１８０のカウンタ値が更新されたら実行される復旧処理について説明する。
【０２２９】
図２３は、図２２の状態で、復旧処理が行われたあとのテーブル等の状態を示す。すなわち、廃棄要素バッファ［４］〜［９］が、空き要素バッファに復旧している。
【０２３０】
時間カウンタ１８０のカウント値が「０」から「１」に更新されたことを検知したバッファリング管理部１６０は、復旧処理部１９０に復旧処理を行うよう依頼する。
【０２３１】
依頼を受けた復旧処理部１９０は、パケットバッファ２００の要素バッファ［０］から順に、廃棄要素バッファであるか否かに確認を開始する（図１３のステップＳ３００）。
【０２３２】
まず、復旧処理部１９０は、要素バッファ［０］が使用中であるか、すなわち、読み出しを待つパケットが書き込まれているかを判断する（ステップＳ３１０）。具体的には、復旧処理部１９０は、要素バッファ［０］に対応する使用中フラグテーブル２２０の使用中フラグテーブル［０］が、「１」である場合は使用中であると判断し、「０」である場合は使用中ではないと判断する。
【０２３３】
要素バッファ［０］が使用中でないと判断した場合（ステップＳ３１０：Ｎｏ）、復旧処理部１９０は、次の要素バッファ［１］の判断に移る（ステップＳ３１０）。
【０２３４】
一方、要素バッファ［０］が使用中であると判断した場合（ステップＳ３１０：Ｙｅｓ）、復旧処理部１９０は、滞留時間より長い時間使用中であるか否か、すなわち、廃棄要素バッファであるか否かを判断する。この判断は、上述の＜廃棄要素バッファの判定方法＞で説明した方法により判断する。
【０２３５】
まず、復旧処理部１９０は、要素バッファ［０］は廃棄要素バッファではないと判断する。具体的には、使用中フラグテーブル［０］は「１」である（図１４の処理６００、及び、図２２参照）ので廃棄要素バッファであるか否かの判断を行う。時間カウンタ１８０のカウンタ値が「１」であり、要素バッファ［０］に対応する書込時間テーブル２３０の書込時間テーブル［０］の値が「０」であるので（図１４の処理６０１参照）、使用時間が「１」となり滞留時間が経過していないと判断する。
【０２３６】
要素バッファ［０］が廃棄要素バッファではないと判断した場合（ステップＳ３２０：Ｎｏ）、復旧処理部１９０は、次の要素バッファ［１］の判断に移る（ステップＳ３１０）。
【０２３７】
一方、要素バッファ［０］が廃棄要素バッファであると判断した場合（ステップＳ３２０：Ｙｅｓ）、復旧処理部１９０は、要素バッファ［０］を空キューにつなげる。
【０２３８】
復旧処理部１９０は、要素バッファ［０］は廃棄要素バッファではないと判断したので、次の要素バッファ［１］の判断に移る。
【０２３９】
このように、ステップ３１０〜ステップ３３０までの処理を、全ての要素バッファに対して順位行う（ステップＳ３４０：Ｎｏ）。
【０２４０】
例えば、要素バッファ［２］の処理を、復旧処理部１９０は次のように行う。
【０２４１】
使用中フラグテーブル［２］は「０」であるので（ステップＳ３１０：Ｎｏ）、廃棄要素バッファであるか否かの判断を行わずに、次の要素バッファ［３］の判断に移る（ステップＳ３１０）。
【０２４２】
要素バッファ［４］、すなわち、廃棄要素バッファの復旧処理を、復旧処理部１９０は次のように行う。
【０２４３】
使用中フラグテーブル［４］は「１」である（ステップＳ３１０：Ｙｅｓ、図１４の処理６０２参照）ので廃棄要素バッファであるか否かの判断を行う。時間カウンタ１８０のカウンタ値が「１」であり、要素バッファ［４］に対応する書込時間テーブル［４］の値が「２」であるので（図１４の処理６０３参照）、使用時間が「２」となり滞留時間が経過していると判断する。
【０２４４】
復旧処理部１９０は、要素バッファ［４］が廃棄要素バッファであると判断したので（ステップＳ３２０：Ｙｅｓ）、要素バッファ［４］を空キューにつなげる。
【０２４５】
具体的には、要素バッファ［４］に対応する使用中フラグテーブル［４］に「０」を設定する（図１４の処理６０４参照）。次に、空キュー管理テーブル２６０のＥＮＤアドレス「Ａ１３」（図２２参照）が指す要素バッファ［１３］に対応するリンク管理テーブル［１３］に、廃棄要素バッファであると判断された要素バッファ［４］のアドレス「Ａ４」で更新する（図１４の処理６０５参照）。空キュー管理テーブル２６０のＥＮＤアドレスを、要素バッファ［４］のアドレス「Ａ４」で更新する（図１４の処理６０６参照）。
【０２４６】
全ての要素バッファの判断を行ったら復旧処理を終了する（ステップＳ３４０：Ｙｅｓ）。
【０２４７】
＜補足＞
以上、本発明の実施形態について説明したが、本発明は上記形態に限らず、以下のようにしてもよい。
（１）実施形態では、パケットをバッファに記憶する場合を説明したが、パケット以外のデータをバッファに読み書きする場合であってもよい。また、各要素バッファは同じサイズでなくてもよい。
（２）パケット転送装置１００は、図１の各構成要素の全部又は一部を、コンピュータのプログラムで実現してもよいし、その他どのような形態で実施してもよい。
【０２４８】
コンピュータプログラムの場合、メモリカード、ＣＤ−ＲＯＭなどいかなる記録媒体に書き込まれたものをコンピュータに読み込ませて実行させる形にしてもよいし、ネットワークを経由してプログラムをダウンロードして実行させる形にしてもよい。
【符号の説明】
【０２４９】
１ テンポラリバッファ
２ ユーザ識別
３ パケット長測定
４ ＥｎＱ処理部
５ ＲｅｓｅｒｖｅＴＯＰレジスタ
６ ＲｅｓｅｒｖｅＥＮＤレジスタ
７ パケットバッファメモリ
８ リンク管理メモリ
９ キュー長管理メモリ
１１ ＤｅＱ処理部
１２ 帯域制御部
１３ アドレス損失復旧処理部
１４ 時間カウンタ
１５ 使用中フラグメモリ
１６ 書込時間メモリ
２０ ２１ パケット
１００ パケット転送装置
１１０ 受信部
１２０ 送信部
１３０ 書込部
１４０ 帯域制御部
１５０ 読出部
１６０ バッファリング管理部
１７０ エラー判定部
１８０ 時間カウンタ
１９０ 復旧処理部
２００ パケットバッファ
２１０ リンク管理テーブル
２２０ 使用中フラグテーブル
２３０ 書込時間テーブル
２４０ ＨＥＡＤ／ＴＡＩＬテーブル
２５０ キュー長管理テーブル
２６０ 空キュー管理テーブル
【技術分野】
【０００１】
本発明は、ソフトエラーにより使用できなくなったバッファを復旧する技術に関する。
【背景技術】
【０００２】
バッファメモリを備える装置、例えば、パケットを転送するスイッチ等の通信装置は、受信したパケットをバッファメモリに一旦蓄積し、ＱｏＳ（Quality of Service）等を考慮した順序でパケットをバッファメモリから読み出して送出している。
【０００３】
このような通信装置においては、不具合が発生すると通信に少なからず影響を与えることから、不具合を容易に判定する技術が提案されている。
【０００４】
例えば、バッファメモリを複数に分割して線形リスト構造で管理する通信装置において、バッファメモリの不具合の一つであるオーバーフローを容易に判定する技術が提案されている（特許文献１等参照）。
【０００５】
また、通信装置においては、不具合が発生してもできる限り処理を続行する必要があるため、バッファメモリの領域からデータを読み出そうとしたときに何らかの理由でエラーとなった場合には、その領域を廃棄し、その他の領域を用いて処理を続行する。
【０００６】
ここで、近年、半導体デバイスの微細化、高集積化、及び、低電圧化等が進み、半導体デバイスにソフトエラーが発生する確率が高くなってきている。ソフトエラーとは、ハードウェアに異常が見られない一過性の不良をいう。例えば、メモリに記憶されているデータが書き換えられていたようなエラーであって、そのメモリ素子には異常がなく、データを再度書き込めば正常に動作するようなエラーである。
【０００７】
このようなソフトエラーは、いつ起こるか分からず、また、発生頻度もそう多くはない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００４−２８０３３３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、上述のような通信装置では、バッファメモリの領域からデータを読出す際に発生したエラーがソフトエラーによるものである場合は、廃棄された領域に問題が無いにもかかわらず使用されないことになる。
【００１０】
そこで、本発明は、バッファメモリを用いた装置において、ソフトエラーの発生によって使用されなくなったバッファメモリの領域を再度使用することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の１形態に係るバッファメモリ装置は、バッファ内の領域にデータを記憶させ、当該バッファ内の領域からデータを読み出すバッファメモリ装置であって、データを前記バッファ内の空き領域に書き込む書込手段と、前記バッファ内の領域からデータを読み出す読出手段であって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出手段と、前記書込手段によってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧手段と、を有する。
【発明の効果】
【００１２】
上記構成のバッファメモリ装置は、ソフトエラーの発生によって使用されなくなったバッファメモリの領域を再度使用することができる。
【図面の簡単な説明】
【００１３】
【図１】パケット転送装置の機能的構成の例を示すブロック図である。
【図２】パケット転送装置においてバッファリング処理を行う機能部の詳細を示す図である。
【図３】パケットバッファ及びテーブル等の関連を示す図である。
【図４】パケットバッファ及びテーブルの使用例を示す図である。
【図５】廃棄要素バッファの判定方法を示す図である。
【図６】パケットの書込み処理を示すフローチャートである。
【図７】パケットの書込み処理のタイムチャート（１）である。
【図８】パケットの書込み処理のタイムチャート（２）である。
【図９】パケットの書込み処理のタイムチャートである。
【図１０】パケットの読出し処理を示すフローチャートである。
【図１１】パケットの読出し処理のタイムチャート（１）である。
【図１２】パケットの読出し処理のタイムチャート（２）である。
【図１３】復旧処理を示すフローチャートである。
【図１４】復旧処理のタイムチャートである。
【図１５】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（１）である。
【図１６】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（２）である。
【図１７】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（３）である。
【図１８】パケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図（４）である。
【図１９】パケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図（１）である。
【図２０】パケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図（２）である。
【図２１】廃棄要素バッファが発生した後のパケットの読出し処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【図２２】廃棄要素バッファが発生した後のパケットの書込み処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【図２３】復旧処理におけるパケットバッファ及びテーブルの遷移を示す図である。
【発明を実施するための形態】
【００１４】
＜実施形態＞
実施形態のバッファメモリ装置は、バッファメモリの領域に記憶されたデータが読み出されるまでの通常の時間を推定し、その推定時間を超えてもデータが読み出されていない領域を空き領域とするものである。すなわち、通常は読み出されているはずのデータが未だ読み出されていないので、今後も読み出されることはないであろうと推定して使用するものである。
【００１５】
実施形態のバッファメモリ装置は、スイッチ等のパケット転送装置で用いられているバッファメモリ装置であり、バッファメモリを複数の領域（以下、「要素バッファ」という。）に分割し、線形リスト構造で管理している。具体的には、パケットを記憶している要素バッファをつなげたパケットキューと、パケットを記憶していない空き要素バッファをつなげた空キューとの２種類のキューを用いて管理する。尚、パケットキューは、パケットの種類により複数ある。
【００１６】
パケットキューの要素バッファは、記憶しているデータが読み出されると空きキューにつながれ再利用される。
【００１７】
データ読出しの際、要素バッファを指すアドレスに誤りがある場合はエラーアドレスとして、そのアドレスを廃棄する。要素バッファを指すアドレスが廃棄されると、そのアドレスによるリンクが切れることから、そのリンク以降のキューにつなげられている要素バッファは全て廃棄されることになる。またこの場合、エラーアドレスが指すはずであった要素バッファが不明であることから、どの要素バッファが廃棄されたかを知ることはできない。
【００１８】
そこで、実施形態のバッファメモリ装置では、要素バッファにデータが記憶されてからの経過時間を基に、廃棄された要素バッファであるか否かを判断する。
【００１９】
しかし、スイッチ等のパケット転送装置では、パケットの受信タイミングと送信タイミングはパケットの種類に依存する。従って、要素バッファにデータが残っている場合に、まだ送信する順番が来ないためにデータ読み出されていないのか、廃棄されていずれのキューにもつながれていないためにデータが読み出されていないのかを判断することは容易ではない。
【００２０】
実施形態のバッファメモリ装置は、正常な状態において、要素バッファに記憶されたデータが読み出されるまでの最長の時間を推定し、バッファメモリの領域に記憶されたデータが、推定時間を超えても未だ読み出されていない要素バッファは、廃棄された要素バッファであると判断する。
【００２１】
廃棄された要素バッファであると判断された要素バッファを、空き要素バッファとして再び使用することにより、バッファメモリを無駄なく有効に使用することが可能となる。
【００２２】
以下、スイッチ等のパケット転送装置で用いられているバッファメモリ装置を例に説明する。
【００２３】
＜機能＞
以下、図１を用いて、パケット転送装置１００の機能について説明する。
【００２４】
図１は、パケット転送装置１００の機能的構成の例を示すブロック図である。
【００２５】
パケット転送装置１００は、受信したパケットをバッファメモリに蓄積し、ＱｏＳ等を考慮した順序でパケットをバッファメモリから読み出して送信する。すなわち、スイッチ等が通常有する転送機能を有するが、図１においては、バッファメモリに関係する機能部を中心に記載している。また、図１において、点線矢印はパケットの流れを示す。
【００２６】
パケット転送装置１００は、受信部１１０、送信部１２０、書込部１３０、帯域制御部１４０、読出部１５０、バッファリング管理部１６０及びパケットバッファ２００を有する。
【００２７】
受信部１１０は、パケット２０を受信し、書込部１３０に依頼して、受信したパケットをパケットバッファ２００に記憶させる機能を有する。
【００２８】
書込部１３０は、受信部１１０から受け取ったパケット２０をパケットバッファ２００に記憶させる機能を有する。パケットバッファ２００内のアドレスを、書込部１３０はバッファリング管理部１６０から取得する。
【００２９】
送信部１２０は、読出部１５０から渡されたパケット２１を送信する機能を有する。
【００３０】
読出部１５０は、帯域制御部１４０からの指示により、パケットバッファ２００に記憶されているパケット２１を読み出して送信部１２０に渡す機能を有する。パケット２１を読み出すパケットバッファ２００内のアドレスを、読出部１５０はバッファリング管理部１６０から取得する。
【００３１】
帯域制御部１４０は、パケットバッファ２００に記憶されているパケットを、どのような順序で送信するかを管理する機能を有する。パケットを送信する順序は、書込部１３０から渡される情報に基づいて、パケットが属する通信に保障すべき帯域等に応じて帯域制御部１４０が定める。
【００３２】
次に、バッファリング管理部１６０は、エラー判定部１７０、時間カウンタ１８０及び復旧処理部１９０の３つの機能部と、リンク管理テーブル２１０、使用中フラグテーブル２２０、書込時間テーブル２３０、ＨＥＡＤ／ＴＡＩＬテーブル２４０、キュー長管理テーブル２５０及び空キュー管理テーブル２６０の６つのテーブルを有する。
【００３３】
バッファリング管理部１６０は、これらの３つの機能部と６つのテーブルを用いて、パケットバッファ２００の要素バッファを管理する機能を有する。バッファリング管理部１６０がパケットバッファ２００を管理する方法については、＜パケットバッファの使用方法＞の項で説明する。
【００３４】
エラー判定部１７０は、要素バッファを指すアドレスに誤りがあるか否かを判定する機能を有する。具体的には、要素バッファからパケットを読み出す際のアドレスが誤っていないか否かを判定する。このアドレスは、リンク管理テーブル２１０に登録されているアドレスである。実施形態では、例えば、ＥＣＣ（Error Correcting Code） Ｍｕｌｔｉ ｂｉｔ ｅｒｒｏｒが発生した場合にエラーアドレスであると判定するものとする。従って、リンク管理テーブル２１０には、登録されているアドレス毎に誤り訂正符号が付加されているものとする。
【００３５】
時間カウンタ１８０は、要素バッファが、廃棄された要素バッファ（以下、「廃棄要素バッファ」という。）であるか否かを判断するために用いるタイマである。時間カウンタ１８０がカウント値を更新する周期、及び、廃棄要素バッファであるか否かを判断する方法は、＜廃棄要素バッファの判定方法＞の項で説明する。
【００３６】
復旧処理部１９０は、パケットバッファ２００から廃棄要素バッファを見つけ出して、空き要素バッファとする処理（以下、「復旧処理」という。）を実行する機能を有する。
【００３７】
リンク管理テーブル２１０は、パケットバッファ２００の要素バッファのキューを構築する機能を有する。
【００３８】
使用中フラグテーブル２２０は、パケットバッファ２００の各要素バッファの使用状態を記憶しておく機能を有する。
【００３９】
書込時間テーブル２３０は、パケットバッファ２００の各要素バッファにパケットが書き込まれた時間を記憶しておく機能を有する。具体的には、書き込まれたときに、時間カウンタ１８０が示しているカウント値を記憶しておく。
【００４０】
ＨＥＡＤ／ＴＡＩＬテーブル２４０は、複数のパケットキューそれぞれの、先頭の要素バッファのアドレス（以下、「ＨＥＡＤアドレス」という。）と末尾の要素バッファのアドレス（以下、「ＴＡＩＬアドレス」という。）とを記憶しておく機能を有する。キューに新たな要素バッファがつながった場合等には、ＨＥＡＤアドレス又はＴＡＩＬアドレスが書き換わることになる。
【００４１】
キュー長管理テーブル２５０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０で管理している各パケットキューにつながっている要素バッファの数を記憶しておく機能を有する。
【００４２】
空キュー管理テーブル２６０は、空き要素バッファをつなげた空キューの先頭の空き要素バッファのアドレス（以下、「ＴＯＰアドレス」という。）と末尾の空き要素バッファのアドレス（以下、「ＥＮＤアドレス」という。）とを記憶しておく機能を有する。
【００４３】
ここで、図２に、図１に示したパケット転送装置１００の機能部のうち、バッファリング処理を行う機能部の詳細を示す。
【００４４】
テンポラリバッファ１は、受信するパケット長を測定するまでの待ち合わせ用のバッファである。ユーザ識別２は、受信したパケットのユーザを識別する機能を有し、受信したパケットをキューイングするパケットキューの番号を決定する。尚、図２では、Ｅｔｈｅｒパケットを記載しており、「ＳＡ」又は「ＶＩＤ」等を基にキュー番号を決定する。パケット長測定３は、受信したパケットの長さを測定し、ＥｎＱ処理部４にパケットの格納を指示する。図１の受信部１１０は、テンポラリバッファ１、ユーザ識別２、及び、パケット長測定３等によって実現される。
【００４５】
ＥｎＱ処理部４は、パケット長測定３からの指示により、テンポラリバッファ１からパケットを受信してパケットバッファメモリ７に格納する。図１の書込部１３０は、ＥｎＱ処理部４等によって実現される。また、図１のパケットバッファ２００は、パケットバッファメモリ７に該当する。
【００４６】
ＲｅｓｅｒｖｅｄＴｏｐレジスタ５は、空き領域を管理する空キューの先頭の要素バッファのアドレスを示し、ＲｅｓｅｒｖｅｄＥＮＤレジスタ６は、空き領域を管理する空キューの末尾の要素バッファのアドレスを示す。図１の空キュー管理テーブル２６０は、ＲｅｓｅｒｖｅｄＴｏｐレジスタ５及びＲｅｓｅｒｖｅｄＥＮＤレジスタ６に該当する。
【００４７】
リンク管理メモリ８は、図１のリンク管理テーブル２１０を記憶しておくメモリである。また、キュー長管理メモリ９は、図１のキュー長管理テーブル２５０を記憶しておき、ＨＥＡＤ／ＴＡＩＬメモリ１０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０を記憶しておくメモリである。
【００４８】
ＤｅＱ処理部１１は、パケットバッファメモリ７からパケットを読み出す。図１の読出部１５０は、ＤｅＱ処理部１１によって実現される。
【００４９】
帯域制御部１２は、ユーザ毎の帯域制御を行う。例えば、トークンバケット方式のシェーパー等が該当する。図１の帯域制御部１４０は、帯域制御部１２によって実現される。
【００５０】
アドレス損失復旧処理部１３は、パケットバッファメモリ７の使用状況の管理と、損失したアドレスの検出及び復旧を行う。時間カウンタ１４は、いわゆるタイマであり、図１の時間カウンタ１８０に該当する。また、使用中フラグメモリ１５は、使用中フラグテーブル２２０を記憶しておき、書込み時間メモリ１６は書込時間テーブル２３０を記憶しておくメモリである。図１のバッファリング管理部１６０の処理は、アドレス損失復旧処理部１３、ＥｎＱ処理部４及びＲｅｓｅｒｖｅｄＴｏｐレジスタ５等によって実現される。
【００５１】
＜テーブル＞
以下、パケットバッファ２００、リンク管理テーブル２１０、使用中フラグテーブル２２０、書込時間テーブル２３０、ＨＥＡＤ／ＴＡＩＬテーブル２４０、キュー長管理テーブル２５０及び空キュー管理テーブル２６０について、図３を用いて説明する。
【００５２】
図３は、パケットバッファ２００及びテーブル等の関連を示す図である。
【００５３】
パケットバッファ２００は、所定サイズの領域に分割されている。この分割された１領域が、１要素バッファである。実施形態では、パケットバッファ２００は１６個の要素バッファで構成されているものとする。以下、それぞれの要素バッファを、要素バッファ［０］〜要素バッファ[１５]という。添字の「０」〜「１５」をそれぞれの要素バッファの番号という。
【００５４】
リンク管理テーブル２１０は、パケットバッファ２００の要素バッファの数と同じ１６個の配列を有する。以下、この配列の要素を、リンク管理テーブル［０］〜リンク管理テーブル［１５］という。リンク管理テーブル２１０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。また、リンク管理テーブル２１０の各要素には、自要素が対応する要素バッファの次につながっている要素バッファのアドレスが記憶されている。例えば、要素バッファ［０］の次に要素バッファ［１］がつながっているとすると、リンク管理テーブル［０］には、要素バッファ［１］のアドレス「Ａ１」が記憶されている。
【００５５】
使用中フラグテーブル２２０は、パケットバッファ２００の要素バッファの数と同じ１６個の配列、例えば、ビット配列を有する。以下、この配列の要素を、使用中フラグテーブル［０］〜使用中フラグテーブル［１５］という。使用中フラグテーブル２２０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。
【００５６】
使用中フラグテーブル[０]が「１」の場合は、要素バッファ[０]にパケットが記憶されていることを示す。一方、「０」の場合は、要素バッファ[０]は空領域であることを示す。使用中フラグテーブル[１]〜使用中フラグテーブル［１５］も同様である。
【００５７】
書込時間テーブル２３０も、パケットバッファ２００の要素バッファの数と同じ１６個の配列を有する。以下、この配列の要素を、書込時間テーブル［０］〜書込時間テーブル［１５］という。書込時間テーブル２３０の配列の要素の番号は、パケットバッファ２００の要素バッファの番号と対応している。
【００５８】
書込時間テーブル２３０には、対応する要素バッファにパケットが書き込まれた時の、時間カウンタ１８０の値が記憶されている。例えば、書込時間テーブル［０］が「０」の場合は、要素バッファ［０］にパケットが書き込まれた時に、時間カウンタ１８０のカウント値が「０」であったことを示している。
【００５９】
ＨＥＡＤ／ＴＡＩＬテーブル２４０は、パケットキューを管理する機能を有し、管理するパケットキューの数分の配列を有する。実施形態では、２つのパケットキューを管理するものとする。以下、この配列の要素を、ＨＥＡＤ／ＴＡＩＬテーブル［０］及びＨＥＡＤ／ＴＡＩＬテーブル［１］といい、添え字は各要素で管理するキューの番号を示す。
【００６０】
また、１つの配列は、ＨＥＡＤアドレスとＴＡＩＬアドレスとで構成され、それぞれＨＥＡＤ［０］、ＴＡＩＬ［０］のように言う。ＨＥＡＤアドレスは、キューの先頭の要素バッファのアドレスを記憶し、ＴＡＩＬアドレスは、キューの末尾の要素バッファのアドレスを記憶する。
【００６１】
キュー長管理テーブル２５０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０で管理するパケットキューの数と同じ２個の配列を有する。以下、この配列の要素を、キュー長管理テーブル［０］及びキュー長管理テーブル［１］という。キュー長管理テーブル２５０の配列の要素の番号は、ＨＥＡＤ／ＴＡＩＬテーブル２４０の配列の番号と対応している。
【００６２】
空キュー管理テーブル２６０は、空キューを管理する機能を有し、ＴＯＰアドレスとＥＮＤアドレスとで構成される。ＴＯＰアドレスは、空キューの先頭の要素バッファのアドレスを記憶し、ＥＮＤアドレスは、キューの末尾の要素バッファのアドレスを記憶する。
【００６３】
＜パケットバッファの使用方法＞
以下、バッファリング管理部１６０が、パケットバッファ２００を使用する方法について、図４を用いて説明する。
【００６４】
図４は、パケットバッファ２００及びテーブルの使用例を示す図である。
【００６５】
図４では、上部に、パケットバッファ２００及びテーブルの内容を示し、下部に、２つのパケットキュー、及び、空キューのイメージを示す。円は、要素バッファを示し、円の内部の数字は、円で示される要素バッファの番号を示す。また、パケットキュー［０］は、ＨＥＡＤ／ＴＡＩＬテーブル［０］で管理されるパケットキューを示し、パケットキュー［１］は、ＨＥＡＤ／ＴＡＩＬテーブル［１］で管理されるパケットキューを示す。空キューは、空キュー管理テーブル２６０で管理される空キューを示す。図１５等においても同様である。
【００６６】
パケットキュー［０］には、要素バッファ［０］、［１］、［２］、［５］の４つ要素バッファにパケットが書き込まれ、順番につながっている。
【００６７】
この要素バッファの順番は、リンク管理テーブル２１０によって、次のように管理されている。要素バッファ［０］に後続する要素バッファのアドレスは、リンク管理テーブル［０］に記憶されている「Ａ１」である。「Ａ１」は、要素バッファ［１］のアドレスである為、要素バッファ［０］に後続する要素バッファは要素バッファ［１］である。次に、要素バッファ［１］に後続する要素バッファのアドレスは、リンク管理テーブル［１］に記憶されている「Ａ２」である。従って、要素バッファ［１］に後続する要素バッファは要素バッファ［２］である。このように、キューが構築されている。
【００６８】
このパケットキュー［０］の先頭の要素バッファのアドレスと末尾の要素バッファのアドレスとを、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ／ＴＡＩＬテーブル［０］が記憶している。ＨＥＡＤ［０］及びＴＡＩＬ［０］は、それぞれ要素バッファ［０］のアドレス「Ａ０」及び要素バッファ［５］のアドレス「Ａ５」を記憶している。キュー長管理テーブル［０］は、つながっている要素バッファの個数「４」を記憶している。
【００６９】
また、使用中フラグテーブル［０］、［１］、［２］、［５］には、それぞれ「１」が設定されている。対応する要素バッファ［０］、［１］、［２］、［５］にパケットが書き込まれているからである。書込時間テーブル［０］、［１］、［２］、［５］には、要素バッファ［０］、［１］、［２］、［５］にパケットが書き込まれ時の時間カウンタ１８０の値「０」が設定されている。
【００７０】
同様に、パケットキュー［１］には、要素バッファ［３］、［４］の２つ要素バッファにパケットが書き込まれ、順番につながっている。
【００７１】
従って、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］及びＴＡＩＬ［１］は、それぞれ「Ａ３」及び「Ａ４」を記憶し、キュー長管理テーブル［１］は、「２」を記憶している。
【００７２】
また、使用中フラグテーブル［３］、［４］には、それぞれ「１」が設定されている。書込時間テーブル［３］、［４］には、要素バッファ［３］、［４］にパケットが書き込まれ時の時間カウンタ１８０の値「１」が設定されている。
【００７３】
また、空キューには、空き要素バッファがつながっている。空キュー管理テーブル２６０のＴＯＰアドレス及びＥＮＤアドレスは、それぞれ「Ａ６」及び「Ａ１５」を記憶している。
【００７４】
ここで、例えば、パケットキュー［０］の要素バッファ［０］に記憶されているデータが読み出されると、要素バッファ［０］は空き要素バッファとなり、空キューの末尾につながれる。
【００７５】
＜廃棄要素バッファの判定方法＞
次に、復旧処理において、パケットバッファ２００内の各要素バッファが、廃棄要素バッファであるか否かを判断する方法について、図５を用いて説明する。
【００７６】
図５は、廃棄要素バッファの判定方法を示す図である。図５においては、説明の便宜上、３つの要素バッファと関連するテーブルを記載している。
【００７７】
復旧処理は、時間カウンタ１８０がカウンタ値を更新する都度に実行する。下向き矢印は、復旧処理を実行するタイミングを示している（矢印３００等参照）。
【００７８】
まず、時間カウンタ１８０のカウンタ値は、所定の周期で、「０」、「１」、「２」と順に繰り返される（１段目の時間カウンタ１８０参照）。復旧処理はこの周期で実行される。
【００７９】
その周期は、要素バッファにパケットが書き込まれた時から読み出されるであろうと推測される時までの時間（以下、「滞留時間」という。）を基に決定する。
【００８０】
滞留時間が経過しているにも関わらずパケットが読み出されていない要素バッファを、廃棄要素バッファであると判断するからである。
【００８１】
実施形態では、時間カウンタ１８０のカウンタ値と、各要素バッファにパケットが書き込まれた時間を記憶している書込時間テーブル２３０とを基に、各要素バッファにパケットが書き込まれてから滞留時間が経過しているか否かを判断する。
【００８２】
まず、滞留時間は、パケット転送装置１００で転送するパケットを送信するユーザに割り当てられた帯域、いわゆる通信速度と、そのユーザが使用することが出来るパケットバッファ２００のサイズとに基づいて求める。
【００８３】
パケット転送装置１００で転送するパケットのうち、最も小さい帯域が割り当てられているパケットの滞留時間を、パケット転送装置１００の滞留時間とする。
【００８４】
例えば、あるユーザに割り当てられた帯域が、「１Ｇｂｐｓ（ｂｉｔ／秒）」であり、そのユーザに割り当てられたパケットバッファ２００内の領域のサイズが、「１Ｍ×１２８ｂｉｔ」であるとする。この場合、このユーザのパケットの滞留時間は、「１Ｍ×１２８ｂｉｔ／１Ｇｂｐｓ＝１２８ｍｓ」となる。
【００８５】
実施形態では、滞留時間が「１２８ｍｓ」の場合、周期を「１ｓｅｃ」とする。そして、時間カウンタ１８０のカウンタ値と、書込時間テーブル２３０に記憶されている値との差、すなわち、経過したカウント値（以下、「使用時間」という。）が「２」である要素バッファを、廃棄要素バッファであると判断する。使用時間が「２」である場合に廃棄バッファであると判断するのは、滞留時間を超過していないにもかかわらず廃棄要素バッファであると判断されてしまうことを防ぐためである。
【００８６】
図５を参照しながら、廃棄要素バッファの判定方法を説明する。
【００８７】
要素バッファ［０］にパケットが記憶されると（データ３０１参照）、使用中フラグテーブル［０］に「１」が設定され（３段目の使用中フラグテーブル２２０参照）、書込時間テーブル［０］に時間カウンタ１８０のカウンタ値「０」が設定される（４段目の書込時間テーブル２３０参照）。
【００８８】
時間カウンタ１８０のカウンタ値が、「０」から「１」に更新されると、復旧処理が実行され（矢印３００参照）、各要素バッファにパケットが書き込まれてからの時間である使用時間を算出する。最下段に示す「算出した使用時間」の配列の番号は、要素バッファの番号と対応しているものとし、使用時間［０］等というものとする。
【００８９】
使用時間は、使用中フラグテーブル２２０に設定されている値が「１」、すなわち、パケットが書き込まれている要素バッファに対してのみ行う。
【００９０】
ここでは、要素バッファ［０］のみにパケットが書き込まれているので、書込時間テーブル［０］から時間カウンタ１８０のカウンタ値「１」までの使用時間［０］は「１」となる。使用時間が「１」であるので、要素バッファ［０］は、廃棄要素バッファではないと判断される。
【００９１】
時間カウンタ１８０のカウンタ値が「１」の間に、要素バッファ［０］からパケットが読み出され、使用中フラグテーブル［０］に「０」が設定される。また、要素バッファ［１］にパケットが書き込まれ、使用中フラグテーブル［１］に「１」が設定され、書込時間テーブル［１］に時間カウンタ１８０のカウンタ値「１」が設定される。
【００９２】
次に、時間カウンタ１８０のカウンタ値が、「１」から「２」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。
【００９３】
時間カウンタ１８０のカウンタ値が「２」の間に、要素バッファ［２］にパケットが書き込まれ、使用中フラグテーブル［２］に「１」が設定され、書込時間テーブル［２］に時間カウンタ１８０のカウンタ値「２」が設定される。
【００９４】
次に、時間カウンタ１８０のカウンタ値が、「２」から「０」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。使用時間［１］が「２」となるため（使用時間３０３の斜線部分参照）、要素バッファ［１］は、廃棄要素バッファであると判断される。
【００９５】
次に、時間カウンタ１８０のカウンタ値が、「０」から「１」に更新されると、復旧処理が実行され、各要素バッファの使用時間を算出する。使用時間［２］が「２」となるため（使用時間３０４の斜線部分参照）、要素バッファ［２］は、廃棄要素バッファであると判断される。
【００９６】
＜動作＞
以下、実施形態のパケット転送装置１００の動作について図を用いて説明する。
【００９７】
パケット転送装置１００の動作として、４つの処理を説明する。
【００９８】
１つ目の処理は、パケットの書込み処理であり、図６〜図９、図１５〜１８を用いて説明する。
【００９９】
図６は、パケットの書込み処理を示すフローチャートであり、図７〜図９は、パケットの書込み処理のタイムチャートであり、図１５〜図１８は、パケットの書込み処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１００】
２つ目の処理は、パケットの読出し処理であり、図１０〜図１２、図１９及び図２０を用いて説明する。パケットの読出し処理が正常に行われる場合と、廃棄要素バッファが発生する場合とを説明する。
【０１０１】
図１０は、パケットの読出し処理を示すフローチャートであり、図１１及び図１２は、パケットの読出し処理のタイムチャートであり、図１９及び図２０は、パケットの読出し処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０２】
３つ目の処理は、廃棄要素バッファが発生した後の、パケットの読出し処理及び書込み処理であり、図２１及び図２２を用いて説明する。
【０１０３】
図２１は、パケットの読出し処理におけるパケットバッファ２００及びテーブルの遷移を示す図であり、図２２は、書込み処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０４】
４つ目の処理は、復旧処理であり、図１３、図１４、図２３を用いて説明する。
【０１０５】
図１３は、復旧処理を示すフローチャートであり、図１４は、復旧処理のタイムチャートであり、図２３は、復旧処理におけるパケットバッファ２００及びテーブルの遷移を示す図である。
【０１０６】
実施形態では、パケット転送装置１００が受信するパケットは可変長であり、パケットの長さに応じて、要素メモリを複数個使用するものとする。また、パケットバッファ２００の要素メモリは、全て同じサイズであるとする。
【０１０７】
図７等のタイムチャートにおいて、番号が同じクロックは、同じタイミングのクロックであるものとする。また、図７等においては、入力されるパケットは、Ｅｔｈｅｒパケット６４Ｂｙｔｅ長の例を示す。パケットバッファ２００のデータ幅を１２８ｂｉｔ幅とし、受信されるパケットのデータ幅も１２８ｂｉｔとする。すなわち、１要素バッファを、１２８ｂｉｔとする。
【０１０８】
キュー番号（ＱＩＤ）はパケットのヘッダ内のＶＩＤを用いる。また、パケット長（ＬＥＮＧＴＨ）は、パケットバッファ２００の要素バッファの使用数で表わす。従って、Ｅｔｈｅｒパケット６４Ｂｙｔｅのパケット長は、「６４Ｂｙｔｅ／１２８ｂｉｔ」で「４」となる。すなわち、パケットは４つに分割されて、それぞれ要素バッファに書き込まれる。以下、分割されたパケットを、パケット（１）、パケット（２）のように言うものとする。
【０１０９】
ＥＮＡＢＬＥは、受信されるパケットが有効である区間を表わしている。ＳＴＡＲＴはユーザパケットの先頭を、ＥＮＤはユーザパケットの末端を表している。
【０１１０】
尚、タイムチャートにおいて、各テーブルのアドレス「Ａ１」等は、各テーブル［１］等のアドレスを示すものとする。
【０１１１】
図１５等のパケットバッファ２００及びテーブルの遷移を示す図では、テーブル等で斜線が引かれている部分は、書き換えられたことを示す。
【０１１２】
また、パケットバッファ２００の配列要素の数字は、書き込まれているパケットの分割の番号を示す。
【０１１３】
＜パケットの書込み処理＞
まず、図６〜図９、図１５〜１８を用いてパケットの書込み処理について説明する。
【０１１４】
図１５は、パケット転送装置１００の起動時のテーブル及びキュー等の状態を示している。すなわち、空キューに、要素バッファ［０］〜要素バッファ［１５］がつながっている。また、使用中フラグテーブル２２０の各配列要素には「０」が設定されている。
【０１１５】
ここでは、図１５で示す初期状態から、３つのパケットを順次受信する場合を例に説明する。キュー番号「０」、パケット長「４」のパケットを受信し、キュー番号「１」、パケット長「６」のパケットを受信し、キュー番号「０」、パケット長「４」のパケットを受信する場合である。
【０１１６】
図１６は、図１５の状態から、最初のキュー番号「０」、パケット長「４」のパケットを受信し、パケットバッファ２００に記憶したときのテーブル及びキュー等の状態を示している。
【０１１７】
図１７は、図１６の状態から、キュー番号「１」、パケット長「６」のパケットを受信したときのテーブル等の状態を示し、図１８は、図１７の状態から、２つ目のキュー番号「０」パケット長「４」のパケットを受信したときのテーブル等の状態を示す。
【０１１８】
＜１つ目のパケットの書込み処理＞
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積する（図７の処理４００参照）と同時に、キュー番号「０」及びパケット長「４」を検出する（図７の処理４０１及び処理４０２参照）。
【０１１９】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号及びパケット長を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する（図７の処理４０３参照）。
【０１２０】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「０」を渡して、空き要素バッファのアドレスを要求する。
【０１２１】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ０」（図１５参照）を読み出して、書込部１３０に渡す。
【０１２２】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ０」の要素バッファ［０］にパケット（１）を書込む（ステップＳ１２０、図１６参照）。また、書込部１３０は、書き込んだパケットのヘッダ部から帯域制御部１４０が帯域の制御に必要な情報を読み出し、帯域制御部１４０に渡す。
【０１２３】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［０］に対応する使用中フラグテーブル２２０の配列要素、すなわち、使用中フラグテーブル［０］に「１」を設定する（ステップＳ１３０、図９の処理４２０、及び、図１６参照）。
【０１２４】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「１」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［０］に対応する書込時間テーブル２３０の配列要素、すなわち、書込時間テーブル［０］に「１」設定する（ステップＳ１４０、図９の処理４２１、及び、図１６参照）。
【０１２５】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１２６】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１２７】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１２８】
具体的に、バッファリング管理部１６０は、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］に加算し、「４」とする（図８の処理４１０、及び、図１６参照）。
【０１２９】
バッファリング管理部１６０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ０」で更新する（図８の処理４１１、及び、図１６参照）。
【０１３０】
また、バッファリング管理部１６０は、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［０］を、パケット（４）が書き込まれた要素バッファ［３］のアドレス「Ａ３」で更新する（図８の処理４１２、及び、図１６参照）。
【０１３１】
バッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）が書き込まれた要素バッファ［３］が対応するリンク管理テーブル［３］の内容である「Ａ４」で更新する（図８の処理４１３、及び、図１６参照）。
【０１３２】
＜２つ目のパケットの書込み処理＞
次に、パケット転送装置１００が、キュー番号が「０」、パケット長が「４」であるパケットを受信したあとに、キュー番号が「１」、パケット長が「６」であるパケットを受信する場合を説明する。
【０１３３】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積すると同時に、キュー番号「１」及びパケット長「６」を検出する。
【０１３４】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号「１」及びパケット長「６」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０１３５】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「１」を渡して、空き要素バッファのアドレスを要求する。
【０１３６】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ４」を読み出して、書込部１３０に渡す。
【０１３７】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ４」の要素バッファ［４］にパケット（１）を書込む（ステップＳ１２０）。
【０１３８】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［４］に対応する使用中フラグテーブル［４］に「１」を設定する（ステップＳ１３０、図９の処理４２２、及び、図１７参照）。
【０１３９】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「２」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［４］に対応する書込時間テーブル［４］に「２」設定する（ステップＳ１４０、図９の処理４２３、及び、図１７参照）。
【０１４０】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１４１】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（６）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「６」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１４２】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１４３】
具体的には、書込部１３０から渡されたパケット長「６」を、キュー長管理テーブル２５０のキュー長管理テーブル［１］に加算し、「６」とする（図８の処理４１４、及び、図１７参照）。
【０１４４】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ４」で更新する（図８の処理４１５、図１６、及び、図１７参照）。
【０１４５】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［１］を、パケット（６）が書き込まれた要素バッファ［９］のアドレス「Ａ９」で更新する（図８の処理４１６、及び、図１７参照）。
【０１４６】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（６）が書き込まれた要素バッファ［９］が対応するリンク管理テーブル［９］の内容である「Ａ１０」で更新する（図８の処理４１７、及び、図１７参照）。
【０１４７】
＜３つ目のパケットの書込み処理＞
次に、パケット転送装置１００が、キュー番号が「１」、パケット長が「６」であるパケットを受信したあとに、キュー番号が「０」、パケット長が「４」であるパケットを受信する場合を説明する。
【０１４８】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、パケット２０をテンポラリバッファ１に蓄積すると同時に、キュー番号「０」及びパケット長「４」を検出する。
【０１４９】
キュー番号とパケット長を検出した受信部１１０は、検出したキュー番号「０」及びパケット長「４」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０１５０】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「０」を渡して、空き要素バッファのアドレスを要求する。
【０１５１】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１０」を読み出して、書込部１３０に渡す。
【０１５２】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ１０」の要素バッファ［１０］にパケット（１）を書込む（ステップＳ１２０）。
【０１５３】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１０］に対応する使用中フラグテーブル［１０］に「１」を設定する（ステップＳ１３０）。
【０１５４】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値「２」を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［１０］に対応する書込時間テーブル［１０］に「２」設定する（ステップＳ１４０）。
【０１５５】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０１５６】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０１５７】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０１５８】
具体的には、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］に加算し、「８」とする（図１７、及び、図１８参照）。
【０１５９】
パケットキュー［０］のキューの末尾に、今回受信したパケットを書き込んだ要素バッファ［１０］〜［１３］をつなげるために、現在のＴＡＩＬ［０］に記憶されているアドレス「Ａ３」が指す要素バッファ［３］に対億するリンク管理テーブル［３］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１０」で書き換える（図１７、及び、図１８参照）。また、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［０］を、パケット（４）を書き込んだ要素バッファ［１３］のアドレスである「Ａ１３」で更新する（図１８参照）。
【０１６０】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）を書き込んだ要素バッファ［１３］に対応するリンク管理テーブル［１３］の内容「Ａ１４」で更新する（図１８参照）。
【０１６１】
＜パケットの読出し処理＞
次に、図１０〜図１２、図１９〜図２０を用いてパケットの読出し処理を説明する。
【０１６２】
ここでは、図１８で示す状態から、キュー番号「０」、パケット長「４」のパケットを読み出し、キュー番号「１」、パケット長「６」のパケットを読み出す場合を説明する。但し、２つ目のキュー番号「１」、パケット長「６」のパケットを読み出す際にエラーが発生するものとする。
【０１６３】
図１９は、図１８の状態で、キュー番号「０」、パケット長「４」のパケットを読み出したときのテーブル及びキュー等の状態を示している。
【０１６４】
図２０は、図１９の状態で、キュー番号「１」、パケット長「６」のパケットの読み出す際にエラーが発生したときのテーブル等の状態を示す。
【０１６５】
以下、パケット転送装置１００が、２つのパケットをパケットバッファ２００から読み出す場合を説明する。
【０１６６】
＜１つ目のパケットの読出し処理＞
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「０」を渡して、読出部１５０にパケットの送信を依頼する。
【０１６７】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「０」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０１６８】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「０」のキューに要素バッファがつながれているかを判断する。具体的には、キュー長管理テーブル［０］の内容が「０」である場合は、要素バッファはつながれていないと判断する。
【０１６９】
要素バッファがつながれていない場合（ステップＳ２２０：Ｙｅｓ）、バッファリング管理部１６０は、読み出すべきパケットが記録されていない旨を読出部１５０に返す。
【０１７０】
読み出すべきパケットが記録されていない旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１７１】
一方、要素バッファがつながれている場合（ステップＳ２２０：Ｎｏ）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ０」を読み出す。
【０１７２】
ここでは、キュー長管理テーブル［０］の内容は「８」であるので（図１８参照）、バッファリング管理部１６０は、ＨＥＡＤ［０］の内容「Ａ０」を読み出す。
【０１７３】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０１７４】
依頼されたエラー判定部１７０は、渡されたアドレスがエラーアドレスであるか否かを判定して、結果をバッファリング管理部１６０に返す。
【０１７５】
判定結果がエラーアドレスである場合（ステップＳ２３０：Ｙｅｓ）、バッファリング管理部１６０は、キュー長管理テーブル［０］に「０」を設定し、エラーが発生した旨を書込部１３０に返す。
【０１７６】
エラーが発生した旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１７７】
一方、判定結果がエラーアドレスでない場合（ステップＳ２３０：Ｎｏ）、バッファリング管理部１６０は、アドレス「Ａ０」を読出部１５０に渡す。
【０１７８】
ここでは、アドレス「Ａ０」は、エラーアドレスではないので、アドレス「Ａ０」を受け取った読出部１５０は、渡されたアドレス「Ａ０」の要素バッファ［０］からパケット（１）を読み出す（ステップＳ２４０）。
【０１７９】
アドレスを読出部１５０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［０］に対応する使用中フラグテーブル２２０の配列要素、すなわち、使用中フラグテーブル［０］に「０」を設定する（ステップＳ２５０、図１２の処理５１０、及び、図１９参照）。
【０１８０】
読出部１５０は、パケットの読出しが終了するまで、要素バッファをバッファリング管理部１６０に要求し、ステップＳ２３０〜ステップ２５０の処理を繰り返す（ステップＳ２６０：Ｎｏ）。
【０１８１】
読出部１５０は、パケットの読出しが終了したら、すなわち、パケット（４）の読出しが終了したら（ステップＳ１６０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、読み出しが終了した旨を通知する。パケットの読出しの終了は、最後のパケットの部分、ここではパケット（４）に設定されている最後である旨を示すフラグを参照して判定する。
【０１８２】
終了通知を受けたバッファリング管理部１６０は、パケットの読出しの完了処理を行う（ステップＳ２７０）。
【０１８３】
具体的には、読出部１５０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］の値「８」から減算し、「４」とする（図１１の処理５００、図１８、及び、図１９参照）。
【０１８４】
パケットキュー［０］につながっている要素バッファ［０］〜［３］を、空き要素バッファとして空キューの末尾につなげる。空キュー管理テーブル２６０のＥＮＤアドレス「Ａ１５」で指す要素バッファ［１５］と対応するリンク管理テーブル［１５］の内容を、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ０」で更新する（図１１の処理５０１、処理５０２、図１８、及び、図１９参照）。パケット（４）を読み出した要素バッファ［３］のアドレス「Ａ３」で、ＥＮＤアドレスを更新する（図１の処理５０３、及び、図１９参照）。
【０１８５】
パケットキュー［０］から要素バッファ［０］〜［３］を外す。パケット（４）を読み出した要素バッファ［３］に対応するリンク管理テーブル２１０［３］の内容「Ａ１０」で、ＨＥＡＤ［０］を更新する（図１１の処理５０４、及び、図１９参照）。
【０１８６】
＜２つ目のパケットの読出し処理（エラー発生）＞
次に、パケット転送装置１００が、キュー番号が「０」、パケット長が「４」であるパケットを読み出したあとに、キュー番号が「１」、パケット長が「６」であるパケットの読出しに失敗する場合を説明する。
【０１８７】
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「１」を渡して、読出部１５０にパケットの送信を依頼する。
【０１８８】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「１」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０１８９】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「１」のキューに要素バッファがつながれているかを判断する。この場合、パケットキュー［１］には要素バッファがつながれているので（ステップＳ２２０：Ｎｏ）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］の内容「Ａ４」を読み出す。
【０１９０】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０１９１】
依頼されたエラー判定部１７０は、渡されたアドレス「Ａ４」がエラーアドレスであると判定して、結果をバッファリング管理部１６０に返す。
【０１９２】
エラーアドレスである旨の判定を受け取ったので（ステップＳ２３０：Ｙｅｓ）、バッファリング管理部１６０は、キュー長管理テーブル［０］に「０」を設定し、エラーが発生した旨を書込部１３０に返す（図２０参照）。
【０１９３】
エラーが発生した旨を受け取った読出部１５０は、次のパケット送信依頼を待つ（ステップＳ２１０）。
【０１９４】
この場合、キュー長管理テーブル［１］は「０」となるので、パケットキュー［１］には要素バッファがつながれていないとして、パケット転送装置１００の処理が続けられる。すなわち、ＨＥＡＤ［１］の内容「Ａ４」は無効として扱われ、リンク管理テーブル２１０に「Ａ４」は登録されていないこととなるため、「Ａ４」からつながっていた要素バッファ［４］〜［９］は、以後使用されることはない。すなわち、廃棄されたことになる。
【０１９５】
＜廃棄要素バッファが発生した後の、パケットの読出し処理及び書込み処理＞
次に、要素バッファ［４］〜［９］が廃棄された後に、パケットの読出し及び書込みが行われる場合を、図を用いて説明する。
【０１９６】
図２１は、図２０の状態で、キュー番号「０」パケット長「４」のパケットを読み出したときのテーブル等の状態を示す。パケット読出しの際のタイムチャートを図１１及び図１２に示す。
【０１９７】
図２２は、図２１の状態で、キュー番号「１」パケット長「４」のパケットを書込んだときのテーブル等の状態を示す。
【０１９８】
＜廃棄要素バッファが発生した後の、パケットの読出し処理＞
帯域制御部１４０は、ＱｏＳ等を考慮した送信タイミングが来たら、送信するキュー番号「０」を渡して、読出部１５０にパケットの送信を依頼する。
【０１９９】
依頼を受けた読出部１５０は、バッファリング管理部１６０にキュー番号「０」を渡して、読み出すパケットが書き込まれている要素バッファのアドレスを要求する（図１０のステップＳ２１０）。
【０２００】
要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、渡されたキュー番号「０」のキューに要素バッファがつながれているかを判断する。
【０２０１】
キュー長管理テーブル［０］の内容は「０」ではないので、（ステップＳ２２０：Ｎｏ、図２０参照）、バッファリング管理部１６０は、パケットキュー［０］の先頭につながれている要素バッファのアドレス、すなわち、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ１０」を読み出す。
【０２０２】
アドレスを読み出したバッファリング管理部１６０は、エラー判定部１７０に読み出したアドレスを渡してチェックを依頼する。
【０２０３】
ここでは、アドレス「Ａ１０」はエラーアドレスではないので（ステップＳ２３０：Ｎｏ）、バッファリング管理部１６０は、アドレス「Ａ１０」を読出部１５０に渡す。
【０２０４】
アドレス「Ａ１０」を受け取った読出部１５０は、渡されたアドレス「Ａ１０」の要素バッファ［１０］からパケット（１）を読み出す（ステップＳ２４０）。
【０２０５】
アドレスを読出部１５０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１０］に対応する使用中フラグテーブル［１０］に「０」を設定する（ステップＳ２５０、図１２の処理５１１参照）。
【０２０６】
読出部１５０は、パケットの読出しが終了するまで、要素バッファをバッファリング管理部１６０に要求し、ステップＳ２３０〜ステップ２５０の処理を繰り返す（ステップＳ２６０：Ｎｏ）。
【０２０７】
読出部１５０は、パケットの読出しが終了したら、すなわち、パケット（４）の読出しが終了したら（ステップＳ１６０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、読み出しが終了した旨を通知する。
【０２０８】
終了通知を受けたバッファリング管理部１６０は、パケットの読出しの完了処理を行う（ステップＳ２７０）。
【０２０９】
具体的には、読出部１５０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［０］から減算し、「０」とする（図１１の処理５０５、及び、図２１参照）。
【０２１０】
パケットキュー［０］につながっている要素バッファ［１０］〜［１３］を、空き要素バッファとして空キューの末尾につなげる。空キュー管理テーブル２６０のＥＮＤアドレス「Ａ３」で指す要素バッファ［３］と対応するリンク管理テーブル［３］の内容を、ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［０］の内容「Ａ１０」で更新する（図１１の処理５０６、処理５０７、図２０、及び、図２１参照）。パケット（４）を読み出した要素バッファ［１３］のアドレス「Ａ１３」で、ＥＮＤアドレスを更新する（図１１の処理５０８、図２０、及び、図２１参照）。
【０２１１】
パケット（４）を読み出した要素バッファ［１３］に対応するリンク管理テーブル２１０［１３］の内容「Ａ１４」で、ＨＥＡＤ［０］を更新する（図１１の処理５０９、及び、図２１参照）。尚、キュー長管理テーブル［０］が「０」となった場合は、ＨＥＡＤ［０］を更新しなくてもよい。
【０２１２】
＜廃棄要素バッファが発生した後の、パケットの書込み処理＞
次に、要素バッファ［４］〜［９］が廃棄された後に、キュー番号「１」パケット長「４」のパケットを書込む場合を説明する。
【０２１３】
受信部１１０は、パケット２０の受信を開始し（図６のステップＳ１００）、キュー番号「１」及びパケット長「４」を検出する。受信部１１０は、検出したキュー番号「１」及びパケット長「４」を書込部１３０に渡して、受信したパケットをパケットバッファ２００に記憶するよう依頼する。
【０２１４】
依頼を受けた書込部１３０は、バッファリング管理部１６０にキュー番号「１」を渡して、空き要素バッファのアドレスを要求する。
【０２１５】
空き要素バッファのアドレスの要求を受けたバッファリング管理部１６０は、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１４」を読み出して、書込部１３０に渡す。
【０２１６】
アドレスを渡された書込部１３０は、渡されたアドレス「Ａ１４」の要素バッファ［１４］にパケット（１）を書込む（ステップＳ１２０）。また、書込部１３０は、書き込んだパケットのヘッダ部から帯域制御部１４０が帯域確保に必要な情報を読み出し、帯域制御部１４０に渡す。
【０２１７】
アドレスを書込部１３０に渡したバッファリング管理部１６０は、渡したアドレスで指される要素バッファ［１４］に対応する使用中フラグテーブル［１４］に「１」を設定する（ステップＳ１３０、図２２参照）。
【０２１８】
また、バッファリング管理部１６０は、時間カウンタ１８０のカウント値を読み出して、読み出したカウント値を、渡したアドレスで指される要素バッファ［１４］に対応する書込時間テーブル［１４］に「０」設定する（ステップＳ１４０、図２２参照）。
【０２１９】
書込部１３０は、パケットの書き込みが終了するまで、空き要素バッファをバッファリング管理部１６０に要求し、ステップＳ１１０〜ステップ１４０の処理を繰り返す（ステップＳ１５０：Ｎｏ）。
【０２２０】
書込部１３０は、パケットの書き込みが終了したら、すなわち、パケット（４）の書き込みが終了したら（ステップＳ１５０：Ｙｅｓ）、パケット長「４」をバッファリング管理部１６０に渡し、書込みが終了した旨を通知する。
【０２２１】
終了通知を受けたバッファリング管理部１６０は、パケットの書込みの完了処理を行う（ステップＳ１６０）。
【０２２２】
具体的には、書込部１３０から渡されたパケット長「４」を、キュー長管理テーブル２５０のキュー長管理テーブル［１］に加算し、「４」とする（図２２参照）。
【０２２３】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＨＥＡＤ［１］を、空キュー管理テーブル２６０のＴＯＰアドレス「Ａ１４」で更新する。
【０２２４】
ＨＥＡＤ／ＴＡＩＬテーブル２４０のＴＡＩＬ［１］を、パケット（４）が書き込まれた要素バッファ［１］のアドレス「Ａ１」で更新する。
【０２２５】
空キュー管理テーブル２６０のＴＯＰアドレスを、パケット（４）が書き込まれた要素バッファ［１］が対応するリンク管理テーブル［１］の内容である「Ａ２」で更新する。
【０２２６】
このように、廃棄された要素バッファ［４］〜［９］は、パケットの書込み及び読み込みにおいて、使用されることはない。
【０２２７】
＜復旧処理＞
次に、図１３、図１４、図２３を用いて復旧処理を説明する。
【０２２８】
ここでは、時間カウンタ１８０のカウンタ値が更新されたら実行される復旧処理について説明する。
【０２２９】
図２３は、図２２の状態で、復旧処理が行われたあとのテーブル等の状態を示す。すなわち、廃棄要素バッファ［４］〜［９］が、空き要素バッファに復旧している。
【０２３０】
時間カウンタ１８０のカウント値が「０」から「１」に更新されたことを検知したバッファリング管理部１６０は、復旧処理部１９０に復旧処理を行うよう依頼する。
【０２３１】
依頼を受けた復旧処理部１９０は、パケットバッファ２００の要素バッファ［０］から順に、廃棄要素バッファであるか否かに確認を開始する（図１３のステップＳ３００）。
【０２３２】
まず、復旧処理部１９０は、要素バッファ［０］が使用中であるか、すなわち、読み出しを待つパケットが書き込まれているかを判断する（ステップＳ３１０）。具体的には、復旧処理部１９０は、要素バッファ［０］に対応する使用中フラグテーブル２２０の使用中フラグテーブル［０］が、「１」である場合は使用中であると判断し、「０」である場合は使用中ではないと判断する。
【０２３３】
要素バッファ［０］が使用中でないと判断した場合（ステップＳ３１０：Ｎｏ）、復旧処理部１９０は、次の要素バッファ［１］の判断に移る（ステップＳ３１０）。
【０２３４】
一方、要素バッファ［０］が使用中であると判断した場合（ステップＳ３１０：Ｙｅｓ）、復旧処理部１９０は、滞留時間より長い時間使用中であるか否か、すなわち、廃棄要素バッファであるか否かを判断する。この判断は、上述の＜廃棄要素バッファの判定方法＞で説明した方法により判断する。
【０２３５】
まず、復旧処理部１９０は、要素バッファ［０］は廃棄要素バッファではないと判断する。具体的には、使用中フラグテーブル［０］は「１」である（図１４の処理６００、及び、図２２参照）ので廃棄要素バッファであるか否かの判断を行う。時間カウンタ１８０のカウンタ値が「１」であり、要素バッファ［０］に対応する書込時間テーブル２３０の書込時間テーブル［０］の値が「０」であるので（図１４の処理６０１参照）、使用時間が「１」となり滞留時間が経過していないと判断する。
【０２３６】
要素バッファ［０］が廃棄要素バッファではないと判断した場合（ステップＳ３２０：Ｎｏ）、復旧処理部１９０は、次の要素バッファ［１］の判断に移る（ステップＳ３１０）。
【０２３７】
一方、要素バッファ［０］が廃棄要素バッファであると判断した場合（ステップＳ３２０：Ｙｅｓ）、復旧処理部１９０は、要素バッファ［０］を空キューにつなげる。
【０２３８】
復旧処理部１９０は、要素バッファ［０］は廃棄要素バッファではないと判断したので、次の要素バッファ［１］の判断に移る。
【０２３９】
このように、ステップ３１０〜ステップ３３０までの処理を、全ての要素バッファに対して順位行う（ステップＳ３４０：Ｎｏ）。
【０２４０】
例えば、要素バッファ［２］の処理を、復旧処理部１９０は次のように行う。
【０２４１】
使用中フラグテーブル［２］は「０」であるので（ステップＳ３１０：Ｎｏ）、廃棄要素バッファであるか否かの判断を行わずに、次の要素バッファ［３］の判断に移る（ステップＳ３１０）。
【０２４２】
要素バッファ［４］、すなわち、廃棄要素バッファの復旧処理を、復旧処理部１９０は次のように行う。
【０２４３】
使用中フラグテーブル［４］は「１」である（ステップＳ３１０：Ｙｅｓ、図１４の処理６０２参照）ので廃棄要素バッファであるか否かの判断を行う。時間カウンタ１８０のカウンタ値が「１」であり、要素バッファ［４］に対応する書込時間テーブル［４］の値が「２」であるので（図１４の処理６０３参照）、使用時間が「２」となり滞留時間が経過していると判断する。
【０２４４】
復旧処理部１９０は、要素バッファ［４］が廃棄要素バッファであると判断したので（ステップＳ３２０：Ｙｅｓ）、要素バッファ［４］を空キューにつなげる。
【０２４５】
具体的には、要素バッファ［４］に対応する使用中フラグテーブル［４］に「０」を設定する（図１４の処理６０４参照）。次に、空キュー管理テーブル２６０のＥＮＤアドレス「Ａ１３」（図２２参照）が指す要素バッファ［１３］に対応するリンク管理テーブル［１３］に、廃棄要素バッファであると判断された要素バッファ［４］のアドレス「Ａ４」で更新する（図１４の処理６０５参照）。空キュー管理テーブル２６０のＥＮＤアドレスを、要素バッファ［４］のアドレス「Ａ４」で更新する（図１４の処理６０６参照）。
【０２４６】
全ての要素バッファの判断を行ったら復旧処理を終了する（ステップＳ３４０：Ｙｅｓ）。
【０２４７】
＜補足＞
以上、本発明の実施形態について説明したが、本発明は上記形態に限らず、以下のようにしてもよい。
（１）実施形態では、パケットをバッファに記憶する場合を説明したが、パケット以外のデータをバッファに読み書きする場合であってもよい。また、各要素バッファは同じサイズでなくてもよい。
（２）パケット転送装置１００は、図１の各構成要素の全部又は一部を、コンピュータのプログラムで実現してもよいし、その他どのような形態で実施してもよい。
【０２４８】
コンピュータプログラムの場合、メモリカード、ＣＤ−ＲＯＭなどいかなる記録媒体に書き込まれたものをコンピュータに読み込ませて実行させる形にしてもよいし、ネットワークを経由してプログラムをダウンロードして実行させる形にしてもよい。
【符号の説明】
【０２４９】
１ テンポラリバッファ
２ ユーザ識別
３ パケット長測定
４ ＥｎＱ処理部
５ ＲｅｓｅｒｖｅＴＯＰレジスタ
６ ＲｅｓｅｒｖｅＥＮＤレジスタ
７ パケットバッファメモリ
８ リンク管理メモリ
９ キュー長管理メモリ
１１ ＤｅＱ処理部
１２ 帯域制御部
１３ アドレス損失復旧処理部
１４ 時間カウンタ
１５ 使用中フラグメモリ
１６ 書込時間メモリ
２０ ２１ パケット
１００ パケット転送装置
１１０ 受信部
１２０ 送信部
１３０ 書込部
１４０ 帯域制御部
１５０ 読出部
１６０ バッファリング管理部
１７０ エラー判定部
１８０ 時間カウンタ
１９０ 復旧処理部
２００ パケットバッファ
２１０ リンク管理テーブル
２２０ 使用中フラグテーブル
２３０ 書込時間テーブル
２４０ ＨＥＡＤ／ＴＡＩＬテーブル
２５０ キュー長管理テーブル
２６０ 空キュー管理テーブル
【特許請求の範囲】
【請求項１】
バッファ内の領域にデータを記憶させ、当該バッファ内の領域からデータを読み出すバッファメモリ装置であって、
データを前記バッファ内の空き領域に書き込む書込手段と、
前記バッファ内の領域からデータを読み出す読出手段であって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出手段と、
前記書込手段によってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧手段と
を備えるバッファメモリ装置。
【請求項２】
前記バッファメモリ装置は、受信したパケットを前記バッファ内の領域に記憶させ、所定の帯域を保証しながら当該バッファ内の領域から読み出したパケットを送信する転送装置に備えられ、
前記書込手段は、受信したパケットを前記バッファ内の空き領域に書き込み、
前記読出手段は、前記バッファからパケットを読み出し、読み出しに成功した場合は、当該パケットが蓄積されていた領域を空き領域とし、読み出しに失敗した場合は、当該パケットが蓄積されていた領域を廃棄領域とし、
前記領域復旧手段の所定の時間は、パケットがバッファに記憶されてから読み出されるまでに要する時間であって、前記所定の帯域に基づいて求めた時間であり、前記領域復旧手段は、前記廃棄領域にパケットが記憶されてから当該所定の時間が経過した場合に、当該廃棄領域を空き領域とする
請求項1記載のバッファメモリ装置。
【請求項３】
前記所定の時間は、前記転送装置が保証する帯域のうち最も小さい帯域と、当該帯域に割り当てられている前記バッファ内の領域サイズとから算出する
請求項２記載のバッファメモリ装置。
【請求項４】
バッファ内の領域にデータをバッファリング装置に記憶させ、当該バッファ内の領域からデータを当該バッファリング装置に読み出させるバッファリング方法であって、
データを前記バッファ内の空き領域に書き込む書込ステップと、
前記バッファ内の領域からデータを読み出す読出ステップであって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出ステップと、
前記書込ステップによってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧ステップと
を備えるバッファリング方法。
【請求項１】
バッファ内の領域にデータを記憶させ、当該バッファ内の領域からデータを読み出すバッファメモリ装置であって、
データを前記バッファ内の空き領域に書き込む書込手段と、
前記バッファ内の領域からデータを読み出す読出手段であって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出手段と、
前記書込手段によってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧手段と
を備えるバッファメモリ装置。
【請求項２】
前記バッファメモリ装置は、受信したパケットを前記バッファ内の領域に記憶させ、所定の帯域を保証しながら当該バッファ内の領域から読み出したパケットを送信する転送装置に備えられ、
前記書込手段は、受信したパケットを前記バッファ内の空き領域に書き込み、
前記読出手段は、前記バッファからパケットを読み出し、読み出しに成功した場合は、当該パケットが蓄積されていた領域を空き領域とし、読み出しに失敗した場合は、当該パケットが蓄積されていた領域を廃棄領域とし、
前記領域復旧手段の所定の時間は、パケットがバッファに記憶されてから読み出されるまでに要する時間であって、前記所定の帯域に基づいて求めた時間であり、前記領域復旧手段は、前記廃棄領域にパケットが記憶されてから当該所定の時間が経過した場合に、当該廃棄領域を空き領域とする
請求項1記載のバッファメモリ装置。
【請求項３】
前記所定の時間は、前記転送装置が保証する帯域のうち最も小さい帯域と、当該帯域に割り当てられている前記バッファ内の領域サイズとから算出する
請求項２記載のバッファメモリ装置。
【請求項４】
バッファ内の領域にデータをバッファリング装置に記憶させ、当該バッファ内の領域からデータを当該バッファリング装置に読み出させるバッファリング方法であって、
データを前記バッファ内の空き領域に書き込む書込ステップと、
前記バッファ内の領域からデータを読み出す読出ステップであって、読み出しに成功した場合は、当該領域を空き領域とし、読み出しに失敗した場合は、当該領域を廃棄領域とする読出ステップと、
前記書込ステップによってデータが書き込まれてから所定の時間が経過した前記廃棄領域を検出し、検出した廃棄領域を空き領域とする領域復旧ステップと
を備えるバッファリング方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１１−１４１６９０（Ｐ２０１１−１４１６９０Ａ）
【公開日】平成２３年７月２１日（２０１１．７．２１）
【国際特許分類】
【出願番号】特願２０１０−１４９７（Ｐ２０１０−１４９７）
【出願日】平成２２年１月６日（２０１０．１．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【出願人】（０００２３７６６２）富士通テレコムネットワークス株式会社 (682)
【Ｆターム（参考）】
【公開日】平成２３年７月２１日（２０１１．７．２１）
【国際特許分類】
【出願日】平成２２年１月６日（２０１０．１．６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【出願人】（０００２３７６６２）富士通テレコムネットワークス株式会社 (682)
【Ｆターム（参考）】
[ Back to top ]