(57)【要約】【課題】パケット転送装置において、到着するパケットを高速かつ小規模な回路で輻輳状態に応じて変動する確率で、パケットをランダムに廃棄する。【解決手段】あらかじめ定めた確率で信号を発生する信号発生回路１００であって、乱数を発生する乱数発生手段１０１と乱数と比較するための比較定数を保持する比較定数保持手段１０２と、乱数と定数とを比較した結果に応じて信号を生成する信号生成手段１０３とを有する信号発生回路を用いて到着したパケットの廃棄判定を行う。【選択図】        図１
2004186815.tif 000002
【特許請求の範囲】
【請求項１】
乱数を発生する乱数発生手段と、
前記乱数と比較される比較定数を保持する比較定数保持手段と、
前記乱数と前記比較定数であって、前記乱数の範囲内の値とを比較し、その結果に応じて、前記乱数の範囲と前記比較定数の関係によりあらかじめ定めた確率で信号を生成する信号生成手段とを、
有する信号発生回路。
【請求項２】
乱数を発生する乱数発生手段と、前記乱数と比較される比較定数を保持する比較定数保持手段と、前記乱数と前記比較定数であって、前記乱数の範囲内の値とを比較し、その結果に応じて、前記乱数の範囲と前記比較定数の関係によりあらかじめ定めた確率で信号を生成する信号生成手段とを有する信号発生回路と、
パケットを受信するパケット受信手段と、
受信パケットを保持するパケット保持手段と、
前記パケット保持手段で保持しているパケットを送信するパケット送信手段と、
前記比較定数保持手段で保持させる定数を決定する比較定数決定手段とを具備し、
前記パケット受信手段は、パケットを受信しパケットの到着を前記乱数発生手段と前記比較定数決定手段に通知し、前記信号発生回路が生成する信号に応じて到着したパケットを廃棄するかあるいは前記パケット保持手段に転送し、
前記パケット保持手段は前記パケット受信手段が転送するパケットを保持し保持しているパケットの量を前記比較定数決定手段に通知し、
前記比較定数決定手段は前記パケット受信手段から通知されるパケットの到着通知と前記信号発生回路から出力される信号と前記パケット保持手段から通知されるパケットの量に応じて前記定数を決定するよう構成されているパケット転送装置。
【請求項３】
前記乱数発生手段は、出力値を１ずつ増加させるカウント手段と前記カウント手段から出力される複数のビットの順序を入れ換えるビット順序交換手段を有している請求項２に記載のパケット転送装置。
【請求項４】
前記カウント手段は前記パケットの到着通知に応じて出力値を１ずつ増加させるよう構成されている請求項３に記載のパケット転送装置。
【請求項５】
前記カウント手段は定期的に出力値を１ずつ増加させるよう構成されている請求項３に記載のパケット転送装置。
【請求項６】
前記乱数発生手段は、ｍ系列を生成するフィードバックシフトレジスタとフィードバックシフトレジスタから出力される複数のビットの順序を入れ換えるビット順序交換手段を有している請求項２に記載のパケット転送装置。
【請求項７】
前記フィードバックシフトレジスタは前記パケットの到着通知に応じて出力値を遷移させるよう構成されている請求項６に記載のパケット転送装置。
【請求項８】
前記フィードバックシフトレジスタは定期的に出力値を遷移させるよう構成されている請求項６に記載のパケット転送装置。
【請求項９】
前記フィードバックシフトレジスタに対して定期的にすべてレジスタが０にならないような初期値にリセットするリセット手段をさらに有する請求項６から８のいずれか１つに記載のパケット転送装置。
【請求項１０】
前記フィードバックシフトレジスタに対してすべてのレジスタが０になったときに、すべてレジスタが０にならないような初期値にリセットするリセット手段をさらに有する請求項６から８のいずれか１つに記載のパケット転送装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット転送装置及びそれに用いる信号発生回路に関し、特に、輻輳の兆候が出始めた時点で通過するパケットを確率的に廃棄するＲａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ（ＲＥＤ）方式のパケット転送装置及びそれに用いる信号発生回路に関する。
【０００２】
【従来の技術】
インターネットプロトコルの中継交換ノードにおいて、輻輳の兆候が出始めた時点で通過するパケットの中から少ない廃棄率でランダムに選んで廃棄するか、又は、パケットのヘッダ内の輻輳通知ビットを立てることにより、一部のホストのアプリケーション又はトランスポートプロトコルに輻輳の発生を通知し、そのホストからの送出量の削減を誘導する方法であるＲａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ（ＲＥＤ）方式による輻輳回避方法が知られている（非特許文献１参照）。ＲＥＤ方式において、輻輳の状態、つまりパケットの溜まり具合に応じて確率を変動させ、動的に変動する確率に対して到着するパケットをランダムに廃棄する必要がある。
【０００３】
また従来、ランダムに信号を生成する装置として、図４に示す構成のものが知られている（特許文献１参照）。同図は、暗号通信装置などで使用される擬似乱数を発生させる擬似乱数発生装置を示していて、ｍ系列を生成する線形フィードバックシフトレジスタ４０１は、初期値設定端子４０３によって初期値を設定でき、また、クロックに同期して状態が遷移する。非線形変換関数回路４０２は、前記線形フィードバックシフトレジスタ４０１のうち特定の１ビットを除いた残りの各レジスタ値を非線形変換して１ビットの出力を得る。排他的論理和演算手段４０４によって、特定の１ビットと前記非線形変換関数回路４０２が出力する１ビットの排他的論理和演算を行い擬似乱数として出力する。上記装置を用いることにより、線形フィードバックシフトレジスタ４０１の段数を十分に大きくすれば、排他的論理和演算手段４０４から出力される０、１の出現は等頻度で、乱数特性の良い擬似乱数発生が可能になる。
【０００４】
【非特許文献１】
Ｓａｌｌｙ  Ｆｌｏｙｄ，  Ｖａｎ  Ｊａｃｏｂｓｏｎ．  “Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ  Ｇａｔｅｗａｙｓ  ｆｏｒ  Ｃｏｎｇｅｓｔｉｏｎ  Ａｄｏｉｄａｎｃｅ”，（ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ，  Ｖｏｌ．１，  Ｎｏ．４，  ｐｐ１−３２，  Ａｕｇｕｓｔ，１９９３．）
【特許文献１】
特開２０００−８１９６９号公報（図８，要約）
【０００５】
【発明が解決しようとする課題】
しかしながら、上記従来の擬似乱数発生装置においては、等頻度で０、１を発生することは可能であるが、上述のＲＥＤ方式については動的に変動する確率に対してランダムに０、１を発生させることが必要になる。例えば、あるパケットバッファがある状態のときに、５％の確率でランダムにパケットを廃棄する必要があり、別の状態では、５０％の確率でパケットをランダムに廃棄することが必要になる。常に５０％の確率でランダムに廃棄する必要があるならば、上記従来の擬似乱数発生装置を用いればよいが、変動する確率に対しては用いることができない。
【０００６】
そこで、本発明は、上述した問題点に鑑み、到着するパケットを高速かつ小規模な回路で輻輳状態に応じて変動する確率に対してランダムに廃棄するための信号発生回路を提供することを第１の目的とし、また、それを用いたパケット転送装置を提供することを第２の目的とする
【０００７】
【課題を解決するための手段】
本発明の第１様態は、上記第１の目的を達成するために、あらかじめ定めた確率で信号を発生する信号発生回路であって、乱数を発生する乱数発生手段と前記乱数と比較するための比較定数を保持する比較定数保持手段と、前記乱数と前記定数とを比較した結果に応じて信号を生成する信号生成手段とを有する信号発生回路を用いる。
本発明の第１様態により、比較定数保持手段で保持する比較定数を変動させることによって信号の生成確率を設定でき、また、乱数発生手段が乱数を発生するので設定した生成確率に対してランダムに信号を出力できる。
【０００８】
本発明の第２様態は、上記第２の目的を達成するために、第１様態に記載の信号発生回路と、パケットを受信するパケット受信手段と、受信パケットを保持するパケット保持手段と、前記パケット保持手段で保持しているパケットを送信するパケット送信手段と、前記比較定数保持手段で保持させる定数を決定する比較定数決定手段を具備し、前記パケット受信手段はパケットを受信しパケットの到着を前記乱数発生手段と前記比較定数決定手段に通知し、前記信号生成手段が生成する信号に応じて到着したパケットを廃棄するかあるいは前記パケット保持手段に転送し、前記パケット保持手段は前記パケット受信手段が転送するパケットを保持し保持しているパケットの量を前記比較定数決定手段に通知し、前記比較定数決定手段は前記パケット受信手段から通知されるパケットの到着通知と前記信号発生回路から出力される信号と前記パケット保持手段から通知されるパケットの量に応じて前記定数を決定するよう構成されているパケット転送装置を用いる。
本発明の第２様態により、信号生成手段によって設定した生成確率に対してランダムに信号を出力できるので、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【０００９】
本発明の第３様態は、第２様態のパケット転送装置において、出力値を１ずつ増加させるカウント手段と前記カウント手段から出力される複数のビットの順序を入れ換えるビット順序交換手段を有する乱数発生手段を用いる。
本発明の第３様態により、出力値を１ずつ増加させるカウント手段と複数のビットの順序を入れ換えるビット順序交換手段を用いて乱数を生成するので、比較的単純な方法で擬似乱数を生成できて、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１０】
本発明の第４様態は、第３様態のパケット転送装置において、前記パケットの到着通知に応じて出力値を１ずつ増加させるよう構成されているカウント手段を用いる。
本発明の第４様態により、カウント手段はパケットの到着によって出力値を１ずつ増加させるので、周期性のないパケットフローに対して、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１１】
本発明の第５様態は、第３様態のパケット転送装置において、定期的に出力値を１ずつ増加させるよう構成されているカウント手段を用いる。
本発明の第５様態により、カウント手段は定期的に出力値を１ずつ増加させるので、周期性のないパケットフローに対して、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１２】
本発明の第６様態は、第２様態のパケット転送装置において、ｍ系列を生成するフィードバックシフトレジスタとフィードバックシフトレジスタから出力される複数のビットの順序を入れ換えるビット順序交換手段を有する乱数発生手段を用いる。
本発明の第６様態により、ｍ系列を生成するフィードバックシフトレジスタと複数のビットの順序を入れ換えるビット順序交換手段を用いて乱数を生成するので、比較的単純な方法で擬似乱数を生成できて、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１３】
本発明の第７様態は、第６様態のパケット転送装置において、前記パケットの到着通知に応じて出力値を遷移させるよう構成されているフィードバックシフトレジスタを用いる。
本発明の第７様態により、フィードバックシフトレジスタはパケットの到着によって出力値を遷移させるので、周期性のないパケットフローに対して、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１４】
本発明の第８様態は、第６様態のパケット転送装置において、定期的に出力値を遷移させるよう構成されているフィードバックシフトレジスタを用いる。
本発明の第８様態により、フィードバックシフトレジスタは定期的に出力値を遷移させるので、周期性のないパケットフローに対して、動的に変動する確率に対して到着するパケットをランダムに廃棄することができる。
【００１５】
本発明の第９様態は、第６から第８様態のいずれか１つのパケット転送装置において、前記フィードバックシフトレジスタに対して定期的にすべてレジスタが０にならないような初期値にリセットするリセット手段をさらに付加した構成にする。
本発明の第９様態により、フィードバックシフトレジスタは定期的にリセットされるので何らかの理由ですべてのレジスタが０になっても確実にｍ系列を再生でき、動的に変動する確率に対して到着するパケットをランダムに廃棄することができるようになる。
【００１６】
本発明の第１０様態は、第６から第８様態のパケット転送装置において、前記フィードバックシフトレジスタに対してすべてのレジスタが０になったときに、すべてレジスタが０にならないような初期値にリセットするリセット手段をさらに付加した構成にする。
本発明の第１０様態により、フィードバックシフトレジスタは何らかの理由ですべてのレジスタが０になったときにリセットされるので確実にｍ系列を再生でき、動的に変動する確率に対して到着するパケットをランダムに廃棄することができるようになる。
【００１７】
【発明の実施の形態】
本発明の好ましい実施の形態について、図１〜図３を用いて説明する。図１は本発明の実施の形態の信号発生回路１００及びそれを用いたパケット転送装置１１０の構成を示している。本発明の信号発生回路１００は、図１に示すように、乱数を次々に発生する乱数発生手段１０１と、この乱数と比較するための比較定数を保持する比較定数保持手段１０２と、この乱数と上記定数とを比較した結果に応じて信号を生成する信号生成手段１０３とを有する。例えば、信号発生回路１００から２０％の確率で一様に信号を出力させるために、乱数発生手段１０１は１以上１０００以下の整数の値を一様にランダムに発生する。また、比較定数保持手段１０２には２００（１０進数）という値を保持させる。信号生成手段１０３は前記乱数が前記比較定数以下であった場合には信号を出力し、前記比較定数より大きければ信号を出力しない。前記乱数が５５であった場合には前記定数以下なので信号が出力される。すなわち、比較定数は、乱数の範囲内の値とされ、この値が個々の乱数と比較されるのである。
【００１８】
以上のような構成にすることにより、信号発生回路１００は１以上１０００以下の整数の値を一様にランダムに生成するので２００以下になる確率は２０％であり、信号の発生頻度も一様になる。
【００１９】
また、本発明のパケット転送装置１１０は上述の信号発生回路１００とパケットを受信するパケット受信手段１１３と、受信パケットを保持するパケット保持手段１１１と、パケット保持手段１１１で保持しているパケットを送信するパケット送信手段１１４と、比較定数保持手段１０２で保持させる定数を決定する比較定数決定手段１１２を具備する。パケット受信手段１１３は外部から到来するパケットを受信し、パケットの到着を乱数発生手段１０１と比較定数決定手段１１２に通知し、信号生成手段１０３が生成する信号に応じてパケットを廃棄する。廃棄しなかったパケットはパケット保持手段１１１に転送され保持される。
【００２０】
パケット保持手段１１１はパケット受信手段１１３が転送するパケットを保持し保持しているパケットの量を比較定数決定手段１１２に通知する。比較定数決定手段１１２はパケット受信手段１１３から通知されるパケットの到着通知と信号生成手段１０３から出力される信号（信号発生回路１００の出力信号でもある）とパケット保持手段１１１から通知されるパケットの量に応じて定数を決定する。パケット受信手段１１３が受信するパケットの量がパケット送信手段１１４が送信するパケットの量より大きい場合、パケット保持手段１１１で保持するパケットの量が増加し、輻輳状態になる。
【００２１】
比較定数決定手段１１２は、ある時刻においてパケット保持手段１１１が保持しているパケットの量と、パケット受信手段１１３から通知されるパケット到着通知と信号発生回路１００から通知される信号によってパケットの廃棄が起きてから、その時刻までに連続して廃棄されずに通過したパケットの数を求め、これらを用いて定数を決定する。輻輳状態でない場合には定数は０となり、乱数発生手段１０１が発生する乱数によらず信号発生回路１００からは信号が発生されず、受信したパケットは全く廃棄されない。輻輳の兆候が出始めた時点で、０でない定数を出力することによって受信したパケットを確率的に廃棄する。
【００２２】
比較定数決定手段１１２は、前述の“Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ  Ｇａｔｅｗａｙｓ  ｆｏｒ  Ｃｏｎｇｅｓｔｉｏｎ  Ａｖｏｉｄａｎｃｅ”に記載の計算方法によりパケットの廃棄を行う確率を求め、さらにその確率から定数を決定する。以上のような構成にすることにより、輻輳の兆候が出始めた時点で通過するパケットを確率的に廃棄するＲＥＤ方式を実現できる。
【００２３】
次に、図１中の乱数発生手段１０１の構成例を図２、図３に示す。図２における乱数発生手段１０１の構成例は、出力値を１ずつ増加させるカウント手段２０１とカウント手段２０１から出力される複数のビットの順序を入れ換えるビット順序交換手段２０２を有する。カウント手段２０１は１０ビットのデータを出力し、ビット順序交換手段２０２は、前記データのＭＳＢとＬＳＢを反転して出力している。
【００２４】
図３における乱数発生手段１０１の構成例は、ｍ系列を生成するフィードバックシフトレジスタ３０１とフィードバックシフトレジスタ３０１から出力される複数のビットの順序を入れ換えるビット順序交換手段３０２を有する。フィードバックシフトレジスタ３０１は１０ビットのデータを出力し、ビット順序交換手段３０２は、前記データのいくつかのビットの順序を入れ換えて出力している。
【００２５】
図２、図３のような構成にすることにより、擬似的に０以上１０２３以内の乱数を発生することができる。図２において、ビット順序交換手段２０２がビット順序を入れ換えているのは、１ずつ増加させるカウント手段２０１のみを用いると信号生成手段１０３において連続的に信号が生成されてしまうのを防止するためである。図３において、ビット順序交換手段３０２がビット順序を入れ換えているのは、フィードバックシフトレジスタ３０１のみを用いても一様に０以上１０２３以下の数を発生することは知られているが、そのまま用いると大きい数字、又は小さい数字が連続して出力されることがあるのでビット順序を入れ換えておくことにより、信号生成手段１０３において連続的に信号が生成されてしまうのを防止する。ＴＣＰフローを廃棄する場合、連続的にパケットを廃棄してしまうとグローバル同期というような問題を引き起こす可能性があるが、ある程度ランダム性をもって廃棄すればよいことから、簡単な構成で擬似乱数を発生させる構成をとっている。
【００２６】
また、図２におけるカウント手段２０１のカウントアップタイミングは、複数のＴＣＰフローのパケットの到着順に規則性がなければパケットの到着に合わせてもよいし、パケットの到着時刻に規則性がなければ定期的に行ってもよい。図３のフィードバックシフトレジスタ３０１のフィードバックシフトレジスタの出力値の遷移タイミングについても同様である。通常、ＴＣＰフローのパケットの到着に規則性はないと考えられるため、どちらでも同様の効果が得られる。また、図３のフィードバックシフトレジスタ３０１を用いる場合、何らかの理由で１であるビットがすべて消失すると永久に０を出力してしまうので、すべてのビットが０になったとき、あるいは定期的に０でない数にリセットする手段を付加するとより安全にｍ系列を生成できる。
【００２７】
【発明の効果】
本発明の第１様態によれば、乱数発生手段が発生する乱数の範囲と比較定数保持手段が保持する定数を設定することによって、信号生成手段が前記乱数と前記定数とを比較した結果に応じて信号を生成するので、様々な確率で信号を生成することができる。
【００２８】
本発明の第２様態によれば、乱数発生手段はパケットの到着に応じて、あるいは定期的に次々に乱数を発生することができ、比較定数決定手段はパケット受信手段から通知されるパケットの到着通知と信号発生回路から出力される信号とパケット保持手段から通知されるパケットの量に応じて定数を決定するので、輻輳状態に応じて定数を決めることができ、パケット受信手段は、信号生成手段が生成する信号に応じて到着したパケットを廃棄するかあるいは前記パケット保持手段に転送することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００２９】
本発明の第３様態によれば、出力値を１ずつ増加させるカウント手段と前記カウント手段から出力される複数のビットの順序を入れ換えるビット順序交換手段によって比較的簡単に乱数発生手段を構成でき、信号生成手段は与えられた定数に応じてランダムに信号を生成できるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００３０】
本発明の第４様態によれば、カウント手段はパケットの到着通知に応じて出力値を１ずつ増加させることにより、信号生成手段はパケット毎に次々に信号を発生することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
本発明の第５様態によれば、カウント手段は定期的にカウンタを１ずつ増加させることにより、信号生成手段は次々に信号を発生することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００３１】
本発明の第６様態によれば、ｍ系列を生成するフィードバックシフトレジスタとフィードバックシフトレジスタから出力される複数のビットの順序を入れ換えるビット順序交換手段によって比較的簡単に乱数発生手段を構成でき、信号生成手段は与えられた定数に応じてランダムに信号を発生することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００３２】
本発明の第７様態によれば、フィードバックシフトレジスタはパケットの到着通知に応じて出力値を遷移することにより、信号生成手段はパケット毎に次々に信号を発生することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００３３】
本発明の第８様態によれば、フィードバックシフトレジスタは定期的に出力値を遷移することにより、信号生成手段は次々に信号を発生することができるので、輻輳状態で決まる確率に応じて到着するパケットをランダムに廃棄することができる。
【００３４】
本発明の第９様態によれば、フィードバックシフトレジスタは定期的に０以外の初期値に遷移するので、回路故障などによってすべてのビットが０になっても復旧可能な安全なパケット転送装置を提供できる。
【００３５】
本発明の第１０様態によれば、フィードバックシフトレジスタはすべてのレジスタが０になったときに０以外の初期値に遷移するので、回路故障などによってすべてのビットが０になっても復旧可能な安全なパケット転送装置を提供できる。
【図面の簡単な説明】
【図１】本発明の実施の形態におけるパケット転送装置の構成例を示すブロック図
【図２】本発明の実施の形態における乱数発生手段をカウンタを用いて構成した場合の構成例を示すブロック図
【図３】本発明の実施の形態における乱数発生手段をｍ系列を生成するフィードバックシフトレジスタを用いて構成した場合の構成例を示すブロック図
【図４】従来の技術における擬似乱数発生装置を示すための回路
【符号の説明】
１００  信号発生回路
１０１  乱数発生手段
１０２  比較定数保持手段
１０３  信号生成手段
１１０  パケット転送装置
１１１  パケット保持手段
１１２  比較定数決定手段
１１３  パケット受信手段
１１４  パケット送信手段
２０１  カウント手段
２０２、３０２  ビット順序交換手段
３０１  フィードバックシフトレジスタ
４００  擬似乱数発生装置
４０１  線形フィードバックシフトレジスタ
４０２  非線形変換関数回路
４０３  初期値設定端子
【図１】
2004186815.tif 000003
【図２】
2004186815.tif 000004
【図３】
2004186815.tif 000005
【図４】
2004186815.tif 000006