(57)【要約】【課題】ルータ等における再送要求が起こる頻度を低減する。【解決手段】通常データを入力順に書き込むとともに書き込み順に読み出す先入れ先出しのメモリを備えたバッファ装置において、ＲＥＤデータを前記メモリの空き領域に書き込んで前記先入れ先出しの処理の対象とし、且つ、前記ＲＥＤデータを書き込んだ領域に前記通常データを書き込む必要が生じたとき、該通常データを前記ＲＥＤデータに上書きして書き込む。【選択図】図１
2009164911.tif 000002
【特許請求の範囲】
【請求項１】
通常データを入力順に書き込むとともに書き込み順に読み出す先入れ先出しのメモリを備えたバッファ装置において、
ＲＥＤによって破棄するとマークされたデータを前記メモリの空き領域に書き込んで前記先入れ先出しの処理の対象とし、且つ、前記ＲＥＤによって破棄するとマークされたデータを書き込んだ領域に前記通常データを書き込む必要が生じたとき、該通常データを前記ＲＥＤによって破棄するとマークされたデータに上書きして書き込むことを特徴とするバッファ装置。
【請求項２】
請求項１に記載のバッファ装置において、
前記ＲＥＤによって破棄するとマークされたデータの書き込みを、前記メモリの空き領域の大きさに応じて実施することを特徴とするバッファ装置。
【請求項３】
請求項１に記載のバッファ装置において、
前記メモリの充填率が定常的に所定値を越えているときは、前記ＲＥＤによって破棄するとマークされたデータの書き込みを行わないことを特徴とするバッファ装置。
【請求項４】
請求項３に記載のバッファ装置において、
前記メモリの充填率を、前記メモリに書き込まれている前記通常データのみによって計算することを特徴とするバッファ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで通信されるデータをルータ等で一時的に保管するバッファ装置に関し、特にＲＥＤによって破棄するとマークされたデータを受信する際の処理ついて改良を行ったバッファ装置に関するものである。
【背景技術】
【０００２】
ネットワークにおけるルータでのキューの通常の動作は、ティルドロップ（tail drop)と呼ばれる方式であり、この方式では溢れたトラフィックをすべて破棄するということになる。しかしながら、この方式では、あるトラフィックに対して公平性を保てないことがあり、再送の衝突を引き起こす原因となる。そこで、ＲＥＤ(Random Early Detection )という方式がＬｉｎａｘカーネル等で提供されている（非特許文献１参照）。
【０００３】
ＲＥＤは、キューがハードリミットに達する前に、フローからランダムに選択されたトラフィックを制限する方式である。この方式によって混雑している接続をより穏やかに減速させることができ、再送の衝突を防ぐことができる。
【非特許文献１】S.Floyd and V.Jacobson,"Random Early Detection Gataways for Congestion Avoidance",IEEE/ACM Transaction on Networking,Vol.1,pp.397-413,1993
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記ＲＥＤでは、キューがリミットに達する前にデータを破棄するために、本来破棄しなくても問題なく処理できたはずのデータまで破棄してしまう可能性がある。この場合、本来生じなくても良かったはずの再送要求が発生し、余分なトラフィックが生じる可能性がある。
【０００５】
本発明の目的は、ＲＥＤによって破棄するとマークされたデータであっても、一旦メモリに格納しておくことにより、メモリがリミットに達しなかった場合、そのデータを転送させ、再送要求が起こる頻度を低減することができるようにしたバッファ装置を提供することである。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、請求項１にかかる発明は、通常データを入力順に書き込むとともに書き込み順に読み出す先入れ先出しのメモリを備えたバッファ装置において、ＲＥＤによって破棄するとマークされたデータを前記メモリの空き領域に書き込んで前記先入れ先出しの処理の対象とし、且つ、前記ＲＥＤによって破棄するとマークされたデータを書き込んだ領域に前記通常データを書き込む必要が生じたとき、該通常データを前記ＲＥＤによって破棄するとマークされたデータに上書きして書き込むことを特徴とする。
請求項２にかかる発明は、請求項１に記載のバッファ装置において、前記ＲＥＤによって破棄するとマークされたデータの書き込みを、前記メモリの空き領域の大きさに応じて実施することを特徴とする。
請求項３にかかる発明は、請求項１に記載のバッファ装置において、前記メモリの充填率が定常的に所定値を越えているときは、前記ＲＥＤによって破棄するとマークされたデータの書き込みを行わないことを特徴とする。
請求項４にかかる発明は、請求項３に記載のバッファ装置において、前記メモリの充填率を、前記メモリに書き込まれている前記通常データのみによって計算することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、ＲＥＤによって破棄するとマークされたデータであっても一旦メモリに格納される。そして、ＲＥＤによって破棄するとマークされたデータがメモリに格納された後にメモリの空き容量が少なくなり、そこに通常データが送られてきたときは、その通常データでＲＥＤによって破棄するとマークされたデータが上書きされる。このため、ＲＥＤによって破棄するとマークされたデータであっても、ＲＥＤの機能を乱すことなく送受信できるようになり、破棄することによってネットワーク上で起こる再送要求を減らすことが可能になる。また、メモリの充填率が定常的に所定値を越えているときは、ＲＥＤによって破棄するとマークされたデータの書き込みを行わないので、ＲＥＤによって破棄するとマークされたデータの無駄な書き込みが防止され、消費電力の増大を抑制することが可能であり、通常のＦＩＦＯとそれほど変わらない消費電力で本発明を実装することが可能となる。
【発明を実施するための最良の形態】
【０００８】
本発明では、ＲＥＤによって破棄するとマークされたデータ（以下、「ＲＥＤデータ」と呼ぶ）をメモリ上のあるアドレスに格納するが、当該ＲＥＤデータを格納したアドレスに対して、ＲＥＤによって破棄するとマークされないデータ（以下、「通常データ」と呼ぶ）を格納しなければならない場合には、通常データを優先すべくＲＥＤデータに上書きし、メモリに書き込まれた順番を狂わせることなく通常データおよび上書きされなかったＲＥＤデータを読み出すことができるようにアドレスを管理する。
【０００９】
また、本発明では、ＲＥＤデータを一時格納するが、メモリの充填率が定常的にある割合を保っているような状況では、ＲＥＤデータを格納しても結局破棄される結果となり、そのような状況の下では回路が無駄に電力を消費するため、メモリの充填率を動的にモニタリングしながら、ＲＥＤデータを格納して意味のある場合にのみ、そのＲＥＤデータを格納する。
【００１０】
また、本発明では、メモリの充填率は通常データが使用している領域によってのみ計算されるようにし、ＲＥＤデータによって使用されている領域は使用されていないものとみなす。
【００１１】
本発明は、ＦＩＦＯを元にしたものであり、通常データはアドレスの先頭から順番に書き込み、書き込んだ順番で読み出す。ＲＥＤデータは、メモリの空いている領域に書き込む。そのメモリマップを図１に示した。
【実施例】
【００１２】
図２に本発明の実施例のバッファ装置の構成を示す。本実施例のバッファ装置は、受信コントローラ１０、送信コントローラ２０、アドレス管理部３０、ＦＩＦＯからなるメモリ４０、メモリ４０の充填率のモニタを行うモニタ部５０からなる。
【００１３】
受信コントローラ１０は、入力されたデータがＲＥＤデータか通常データかのチェックを行う。また、データパケットのヘッダからパケットサイズを特定して、バースト長（データサイズ）を計算し、その結果をアドレス管理部３０に伝える。さらに、モニタ部５０からメモリ４０の残りの空きサイズを受け、入力されるデータのサイズがその空きサイズを超えた場合には、通常データ、ＲＥＤデータに拘わらず、そのデータの受信を拒否する。モニタ部５０がメモリ４０の充填率が定常的（所定時間以上）に高い（例えば、５０％越え）と判断した場合には、ＲＥＤデータは破棄される。
【００１４】
送信コントローラ２０は、アドレス管理部３０によって指定されたメモリ４０のアドレスのデータを受け、そのデータから、これから読み出すデータのサイズを特定しバースト長を計算し、その値をアドレス管理部３０に返し、読み出すアドレスを生成させる。
【００１５】
アドレス管理部３０は、受信用のアドレスと送信用のアドレスを管理する。このアドレス管理が本実施例の肝心な点である。すなわち、受信コントローラ１０、送信コントローラ２０から、ＲＥＤが有効かどうかの情報を受け取って、その情報を元にメモリ４０に渡すアドレスを生成する。アドレスの管理の詳しい方法は後に述べる。
【００１６】
メモリ４０には、書き込み側のポートと読み出し側のポートが個別に用意されているメモリを使用する。つまり、書き込みと読出しが同時アクセス可能なメモリ（ＦＩＦＯ）である。
【００１７】
モニタ部５０は、アドレス管理部３０から現在の書き込みアドレスと読み出しアドレスを受け、その情報を元にメモリ４０の残りの容量を計算し、その情報を受信コントローラ１０に渡す。また、メモリ４０の充填率の変化を監視し、定常的に充填率が高い場合は受信コントローラ１０にその情報を渡し、ＲＥＤデータを格納するかどうかを判断する手助けをする。
【００１８】
本実施例のバッファ装置は、以上の構成要素を実装することによって実現可能である。次にアドレス管理の方法について述べる。図３にアドレス管理部３０の構成を示す。３１は受信用アドレスを管理する受信アドレス管理部、３２は送信用アドレスを管理する送信アドレス管理部である。３３はＦＩＦＯからなるアドレスメモリであり、メモリ４０にＲＥＤデータを格納したアドレスと通常データを格納したアドレスとを格納する。例えば、図１において、メモリ４０での通常データの書き込みアドレス（write_ptr）が図の位置のときに、ＲＥＤデータＤ６が書き込まれた場合、アドレスメモリ３３にその書き込みアドレス（write_ptr）の値とＲＥＤデータＤ６を書き込んだメモリ領域のアドレス（red_write_ptr)とを格納する。
【００１９】
図３において、（rx_en）はデータ受信可のときアサートされる受信イネーブル信号、（red_en）は受信データがＲＥＤデータのときアサートされるＲＥＤイネーブル信号、（rx_burst_cnt）は受信データのバースト長である。また、（tx_en）はデータ送信可のときアサートされる送信イネーブル信号、（tx_burst_cnt）は送信データのバースト長である。また、（rx_address）は受信アドレス（後記する（write_ptr）や（red_write_ptr)相当）、（tx_address）は送信アドレス（後記する（read_ptr）相当）である。
【００２０】
受信時の受信アドレス管理部３１の動作を図４のメモリ４０の説明図と、図５のフローチャートで説明する。受信アドレス管理部３１において、ＲＥＤイネーブル信号（red_en）がアサートされていなければ（Ｓ１−ＮＯ）、受信データは通常データであり、これを書き込むためのアドレス（write_ptr)を生成する。このアドレスは、初期値（0x0)からインクリメントすることにより実現する。
【００２１】
受信した通常データのサイズがメモリ４０の空き容量より小さく（Ｓ２）、かつアドレスメモリ３３が空でないとき（Ｓ３−ＮＯ）、つまりＲＥＤデータが書き込まれているときは、アドレスメモリ３３に格納されているＲＥＤ書き込みアドレス（red_write_ptr）の値をチェックし（Ｓ４）、このＲＥＤ書き込みアドレス（red_write_ptr）の値が前記生成された書き込みアドレス（write_ptr)の値と一致した場合（Ｓ５−ＹＥＳ）は、アドレスメモリ３３の読み出しアドレス（read_ptr)を更新した上で、通常データをメモリ４０の書き込みアドレス（write_ptr)に書き込む（Ｓ６）。このとき、一致したＲＥＤ書き込みアドレス（red_write_ptr）のＲＥＤデータは上書きされ破棄される。一致しない場合（Ｓ５−ＮＯ）は通常データをメモリ４０の通常領域に書き込む（Ｓ７）。なお、受信した通常データのサイズがメモリ４０の空き容量より大きい場合（Ｓ２−ＮＯ）は、その通常データを破棄する（Ｓ８）。また、アドレスメモリ３３が空のとき（Ｓ３−ＹＥＳ）は、そのまま書き込みアドレス（write_ptr)に通常データを書き込む（Ｓ７）。
【００２２】
一方、ＲＥＤイネーブル信号（red_en）がアサートされている場合（Ｓ１−ＹＥＳ）は、受信データはＲＥＤデータである。まず、送信アドレス管理部３２からそのときの読み出しアドレス（read_ptr）を参照し、この値を元に、ＲＥＤデータ格納用のメモリ領域を確保するために、ＲＥＤデータが格納されている現在のＲＥＤ先頭アドレス（red_top_adr）を計算する（Ｓ９）。次に、計算されたＲＥＤ先頭アドレス（red_top_adr）の値と、受信したＲＥＤデータを格納するためのＲＥＤ書き込みアドレス（red_write_ptr）の値を比較して、計算されたＲＥＤ先頭アドレス（red_top_adr）の値が大きければ（Ｓ１０−ＹＥＳ）、この値をＲＥＤ書き込みアドレス（red_write_ptr）に採用し（Ｓ１１）、小さければＲＥＤ書き込みアドレス（red_write_ptr）はそのまま（Ｓ１２）として、それを採用する。
【００２３】
次に、ＲＥＤ書き込みアドレス（red_write_ptr）の値と読み出しアドレス（read_ptr)の値からＲＥＤデータを格納するためのメモリ４０の空き領域を計算し（Ｓ１３）、メモリ４０の空き容量がＲＥＤデータのサイズより大きいとき（Ｓ１４−ＮＯ）、ＲＥＤデータをＲＥＤ書き込みアドレス（red_write_ptr）に書き込む（Ｓ１５）。このとき、実際に採用されたＲＥＤ書き込みアドレス（red_write_ptr）と、その時の通常データ用の書き込みアドレス（write_ptr)を、アドレスメモリ３３に格納する。なお、メモリ４０の空き容量がＲＥＤデータのサイズより小さいとき（Ｓ１４−ＹＥＳ）は、ＲＥＤデータを破棄する（Ｓ１６）。
【００２４】
送信時の動作を図６のフローチャートで説明する。アドレスメモリ３３が空であれば（Ｓ２１−ＹＥＳ）、つまり、ＲＥＤデータが格納されていなければ、メモリ４０の読み出しアドレス（read_ptr)から順番にデータを読み出し送信する（Ｓ２２）。
【００２５】
一方、アドレスメモリ３３空でない時（Ｓ２１−ＮＯ）、つまり、ＲＥＤデータが格納されているときは、アドレスメモリ３３に格納されているデータのうち、ＲＥＤデータを書き込んだときの、通常データを格納するアドレスを示す（write_tpr)の値をチェックし（Ｓ２３）、そのアドレス（rwite_ptr）の値と、現在の読み出しアドレス（read_ptr)の値を比較して一致しなければ（Ｓ２４−ＮＯ）、現在の読み出しアドレス（read_ptr)の示すアドレスから通常データを読み出し送信する（Ｓ２５）。一致した場合（Ｓ２４−ＹＥＳ）は、アドレスメモリ３３に格納したＲＥＤ書き込みアドレス（red_write_ptr）が示すアドレスからＲＥＤデータを読み出し送信する（Ｓ２６）。このときは、アドレスメモリ３３の読み出しアドレス（read_ptr)を更新する。
【００２６】
このようなアドレス管理を行うことで、ＲＥＤデータを保持しながら、書き込まれた順番通りにデータ読み出すことができる。ところで、メモリ４０の充填率が定常的に５０％を超えているような場合、ＲＥＤデータを一旦格納したとしても、そのＲＥＤデータは読み出されることなく受信した通常データによって上書きされる。したがって、このような状況でＲＥＤデータを格納するための機能を有効にしておくことは電力の浪費を招くため、この機能を停止させる機能を持たせる。それを実現するのがモニタ部５０のブロックである。
【００２７】
モニタ部５０は、アドレスメモリ３３から通常データの書き込みアドレス（write_ptr）と読み出しアドレス（read_ptr）の値を受けて、この値を元にメモリ４０の充填率を計算する。また、図４のＲＥＤ先頭アドレス（red_top_adr）が更新されると、ＲＥＤデータが利用可能なメモリ領域の容量をフルにセットし、書き込まれるたびに充填率をモニタリングする。この領域の残りの容量が書き込まれるＲＥＤデータのサイズより小さい場合には、書き込まないようにする。メモリ４０の充填率をモニタリングし、その充填率が常に高い値（例えば、５０％越え）をとっているような場合には、受信コントローラ１０にその状態を伝え、ＲＥＤデータを受け付けないようにする。
【００２８】
しかし、莫大なデータがバーストで受信される場合、一時的にメモリ４０の充填率が増加することが考えられる。この場合、一時的に充填率が増加するため、ＲＥＤシステムは破棄するデータにマークを行う。しかし、そのバーストがＲＥＤデータを含めてもフルにはならないという状況であれば、上記の機能を動作させることは有効である。したがって、モニタリングしながら、過渡的にメモリ４０の充填率が増加した場合は、上記の機能を動作させる。その後、しばらく経ってもメモリ４０の充填率が減少しない場合には上記の機能を停止させる。
【図面の簡単な説明】
【００２９】
【図１】本実施例のメモリの説明図である。
【図２】本実施例のバッファ装置の構成を示すブロック図である。
【図３】アドレス管理部の構成を示すブロック図である。
【図４】受信データをメモリに書き込む際の説明図である。
【図５】受信データをメモリに書き込む動作のフローチャートである。
【図６】メモリから送信データを読み出す動作のフローチャートである。
【符号の説明】
【００３０】
１０：受信コントローラ
２０：送信コントローラ
３０：アドレス管理部、３１：受信アドレス管理部、３２：送信アドレス管理部、３３：アドレスメモリ
４０：メモリ
５０：モニタ部
【図１】
2009164911.tif 000003
【図２】
2009164911.tif 000004
【図３】
2009164911.tif 000005
【図４】
2009164911.tif 000006
【図５】
2009164911.tif 000007
【図６】
2009164911.tif 000008