JP4659657B2 - フレーム多重装置 - Google Patents

Description

この発明は、複数の回線から入力された可変長フレームを多重して出力するフレーム多重装置に関する。

従来より、複数の回線から、イーサネット（登録商標）フレームのような可変長フレーム（またはパケット）からなるトラフィックが入力され、それらのトラフィックを多重して出力する通信装置として、フレーム多重装置が公知である。フレーム多重装置に入力される総帯域が装置の出力帯域よりも大きいと、輻輳が発生し、フレームの廃棄が発生する可能性がある。

一部の大量のトラフィックを流す回線によって、少量のトラフィックしか流さない回線のトラフィックが廃棄されてしまわないようにするためには、トラフィックを送信している複数の回線が装置の出力帯域を公平に使用できるように、各トラフィックを多重する機能が必要である。このような機能を有するフレーム多重装置として、重み付きラウンドロビン（ＷＲＲ：Ｗｅｉｇｈｔｅｄ Ｒｏｕｎｄ Ｒｏｂｉｎ）によるキューバッファ読み出し制御方式を用いたフレーム多重装置が公知である。

図８は、従来の重み付きラウンドロビンによるキューバッファ読み出し制御方式を用いたフレーム多重装置の構成を示す図である。図８に示すように、従来のフレーム多重装置１は、複数のキューバッファ＃１〜＃ｎ（２ａ，２ｂ，２ｃ，２ｄ）とスケジューラ３から構成されている。キューバッファ２ａ，２ｂ，２ｃ，２ｄは、各回線ごとに設けられており、各回線からフレーム多重装置１に入力されたフレームを一時的に保持する。

スケジューラ３は、フレーム多重装置１の出力帯域が各回線に指定された重みに従った帯域となるように、各キューバッファ２ａ，２ｂ，２ｃ，２ｄからのフレーム読み出し順序を巡回的に決定する。その際、スケジューラ３は、キューバッファ２ａ，２ｂ，２ｃ，２ｄにフレームが格納されていない回線を除いて、フレーム読み出し順序を決定する。従って、各回線の重みを等しくすれば、トラフィックを送信している複数の回線の帯域が均等になるように、各トラフィックを多重することが可能となる。

また、区別された個々のユーザが発生させるトラフィックの流れのトラフィックフローの集まりであるチャネルが複数存在する物理回線における論理チャネル帯域保証装置であって、前記トラフィックフロー単位での公平な帯域の分割を行うスケジューラと、前記帯域を制限する単位となる個々のチャネルが利用する帯域を、該チャネル毎に与えられた帯域を超えることなく割り当てるシェーパーとを有することを特徴とする論理チャネル帯域保証装置が公知である（例えば、特許文献１参照。）。この論理チャネル帯域保証装置では、前記シェーパーは、フレームが各チャネルバッファからアウトプットバッファへ転送される際に、重み付きラウンドロビンを用いている。

特開２０００−４９８１２号公報

しかしながら、上述した従来のフレーム多重装置では、次のような問題点がある。一般に、キューバッファは、メモリ使用効率の観点から、共有メモリで構成されている。従って、共有メモリの空きアドレスを管理し、共有メモリにフレームを書き込む際には、空きアドレスを取得し、共有メモリからフレームを読み出す際には、アドレスを返却する処理が必要となる。共有メモリの空きアドレスを管理するには、共有メモリの全アドレス数にアドレス長を乗じた容量を格納できる管理用メモリが必要となる。

また、キューバッファに格納されるフレームは、共有メモリ上の不特定のアドレスに書き込まれる。キューバッファを構築するには、各フレームのメモリ上のアドレスとその順序を管理するために、キューバッファ長にアドレス長を乗じた容量を格納できる管理用メモリが必要となる。

また、重み付きラウンドロビンによるキューバッファ読み出し制御方式を、フレーム多重装置の出力する最大帯域を使用するベストエフォートサービスに適用する場合には、フレーム間に余分な間隔を空けずにフレームが出力される。そのため、可変長フレームの最短フレーム長をＸ０とし、フレーム多重装置の出力帯域をＹ０とすると、最短フレームを読み出すのに許容される時間Ｔ０は、最短フレーム長Ｘ０をフレーム多重装置の出力帯域Ｙ０で除した時間Ｔ０となる。従って、スケジューラは、最短フレームの読み出しを決定した後、時間Ｔ０の間に次の読み出しフレームを決定する必要がある。

このように、極めて短時間の間に上記２つの管理用メモリにアクセスする必要があるため、両管理用メモリには、高価なＳＲＡＭ（Ｓｙｎｃｒｏｎｉｚｅｄ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）が用いられている。そのため、収容回線数が増えると、著しくコストが増大する。また、収容回線数に比例して必要なメモリ容量が増加するため、大きなＳＲＡＭが必要となり、装置が大型化してしまう。これらの原因により、収容回線数を増やしたくても、その数が制限されてしまう。また、フレーム多重装置の出力速度が上がると、最短フレームの読み出し時間Ｔ０が短くなるため、より短い時間で読み出しフレームの順序を決める必要がある。そのため、出力速度を上げたくても、その速度が制限されてしまう。

さらに、上記特許文献１に開示された装置では、乗算や除算を伴う複雑な処理を行うため、ソフトウェア処理が必要となり、処理を高速化できないという問題点がある。処理を高速化できないと、複数の回線間で装置の出力帯域を公平に使用するための制御を行う時間間隔を大きくしなければならないため、公平性の精度の低下を招くという問題点がある。

この発明は、上述した従来技術による問題点を解消するため、複数の回線間で装置の出力帯域を公平に使用する機能を有するフレーム多重装置において、コストの増大や装置の大型化を招くことなく、収容回線数を増やすことができるフレーム多重装置を提供することを目的とする。また、この発明は、複数の回線間で装置の出力帯域を公平に使用する機能を有するフレーム多重装置において、出力速度を上げることができるフレーム多重装置を提供することを目的とする。

上述した課題を解決し、目的を達成するため、本発明の一実施態様にかかるフレーム多重装置は、複数の回線ごとにカウンタを備えている。流量監視部は、各回線に対応するカウンタの値に基づいて各回線のフレーム流量を監視する。そして、流量監視部は、回線ごとに、通過するフレームのフレーム長を対応するカウンタの値に加算する。また、帯域管理部は、フレームが入力されている回線の中から巡回的に１回線を選択する。そして、帯域管理部は、選択された回線に対応するカウンタの値から所定のトークン量を減算する。出力制御部は、流量監視部を通過したフレームをキューバッファに格納し、装置の出力帯域にして出力する。

この実施の態様によれば、トラフィックを送信している各回線間でフレーム流量を均等な帯域で監視することができるので、回線ごとにキューバッファを設けなくても、複数の回線間で均等な帯域を利用できるようにフレームを多重することができる。従って、従来必要であった共有メモリの空きアドレス管理用メモリが不要となるので、コストの低減を図ることができる。また、キューバッファメモリを構築するための管理用メモリも不要になる。

その代わり、この実施の態様では、回線ごとにカウンタが必要になる。従来のキューバッファメモリを構築するには、［キューバッファ長（フレーム数）×アドレス長］のメモリ容量が必要である。それに対して、この発明では、カウンタが、カウンタ長（バイト数）を表すことができるだけのビット数を有していればよいので、メモリ容量を大幅に削減することができる。従って、コストの増大や装置の大型化を招くことなく、収容回線数を増やすことができる。

この実施の態様において、流量監視部に廃棄判定部が設けられていてもよい。廃棄判定部は、各回線に入力されたフレームを、そのフレームの入力によって対応するカウンタの値が、予め回線ごとに設定された閾値を超える場合に廃棄し、超えない場合に通過させる。ここで、閾値は、回線ごとに許容されるトラフィックのバースト量に等しくなっていてもよい。このようにすれば、廃棄されたフレームがカウンタの値に反映されないので、カウンタの上限値を容易に決定することができる。従って、カウンタに必要なメモリの容量を容易に算出することができる。

また、この実施の態様において、帯域管理部にタイミング管理部が設けられていてもよい。タイミング管理部は、フレームが入力されている回線の中から１回線を選択する処理を行うためのトリガを、予め設定されたフレーム流量の許容帯域（Ｙとする）でトークン量（Ｘとする）を除した帯域管理周期（Ｔとすると、Ｔ＝Ｘ／Ｙ）ごとに発生する。さらに、この発明において、帯域管理部に回線検索部が設けられていてもよい。回線検索部は、タイミング管理部から発せられたトリガを契機としてカウンタの値を参照する。そして、回線検索部は、そのカウンタの値に基づいて、フレームが入力されている回線の中から１回線を選択する。

ここで、トークン量は、入力される可変長フレームの最短フレームの長さよりも長く設定されているとよい。例えば、トークン量は、入力される可変長フレームの最長フレームと同じ長さに設定されていてもよい。また、フレーム流量の許容帯域は、出力制御部の出力帯域に等しくてもよい。このようにすれば、帯域管理周期が最短フレームの読み出し時間よりも長くなるので、巡回的に１回線を選択する処理を、従来の重み付きラウンドロビンによるキューバッファ読み出し制御方式よりも長い周期で行うことができる。従って、出力速度を上げることができる。

また、この実施の態様において、帯域管理部に回線ごとに選択回数カウンタが設けられていてもよい。選択回数カウンタは、回線検索部により選択された回数をカウントする。このようにすれば、帯域管理部において選択回数とトークン量の積よりフレームの通過量を監視することができる。フレームの通過量を管理するのに必要となるメモリ量は、フレームの通過量をバイト単位でカウントする場合のメモリ量の［１／トークン量］で済む。従って、収容回線数を増やしたり、出力速度を上げても、より低コストでフレームの通過量を監視することができる。この場合、選択回数カウンタの値、またはそれにトークン量を乗じた値をフレーム多重装置の外部へ出力させることにより、オペレータ等にフレームの通過量を通知するようにしてもよい。

また、この実施の態様において、カウンタの構成を、複数ビットのカウンタ部分と例えば１ビットの符号ビットを有する構成としてもよい。カウンタ部分は、カウントした値を示す。符号ビットは、カウンタ部分の値が正の値であるか否かを示す。この場合、帯域管理部は、各カウンタの符号ビットを参照し、符号ビットが、カウンタ部分の値が正の値であることを示している回線の中から１回線を選択するようにしてもよい。また、その１回線を選択するにあたって、帯域管理部は、重み付きラウンドロビン方式により巡回的に回線の検索を行ってもよい。その際、各回線に均等な重みとしてもよいし、各回線に重みをつけてもよい。

本発明にかかるフレーム多重装置によれば、複数の回線間で装置の出力帯域を公平に使用する機能を有し、コストの増大や装置の大型化を招くことなく、収容回線数を増やすことができるという効果を奏する。また、本発明にかかるフレーム多重装置によれば、複数の回線間で装置の出力帯域を公平に使用する機能を有し、出力速度を上げることができるという効果を奏する。

以下に添付図面を参照して、この発明にかかるフレーム多重装置の好適な実施の形態を詳細に説明する。ここでは、特に限定しないが、例えばイーサネット網でフレームにＶＬＡＮタグが付与されていて、ＶＬＡＮ ＩＤにより回線を識別する構成を例にして説明する。なお、ＶＬＡＮは、Ｖｉｒｔｕａｌ ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）のことである。

図１は、本発明にかかるフレーム多重装置の構成の一例を示す図である。図１に示すように、フレーム多重装置１００は、流量監視部１０、帯域管理部２０、複数のカウンタ＃１〜＃ｎ（３０ａ，３０ｂ）および出力制御部４０を備えており、ｎ回線から入力された可変長フレームを多重して出力する。ここで、ｎは、２以上の整数である。

カウンタ３０ａ，３０ｂは、ｎ回線の入力回線の回線ごとに設けられている。カウンタ３０ａ，３０ｂは、カウントした数値を示す複数ビットのカウンタ部分と、そのカウンタ部分の値が正の値であるか否かを示す例えば１ビットの符号ビット（図４参照）を有する。例えば、符号ビットの値が“１”であれば、カウンタ部分が示す数値は正の値であり、符号ビットの値が“０”であれば、カウンタ部分が示す数値は、ゼロまたは負の値である。符号の値が“１”であるということは、そのカウンタに対応する回線にフレームが入力されている、すなわちフレームが流れていることを表している。

流量監視部１０は、カウンタ３０ａ，３０ｂのカウンタ部分の値に基づいて各回線のフレーム流量を監視し、所定のフレーム流量を超過しているフレームを廃棄し、超過していないフレームを通過させる。また、流量監視部１０は、通過させたフレームのフレーム長を、そのフレームが流れる回線に対応するカウンタ３０ａ，３０ｂのカウンタ部分の値に加算する。帯域管理部２０は、フレームが入力されている回線の中から巡回的に１回線を選択し、選択された回線に対応するカウンタ３０ａ，３０ｂの値から所定のトークン量を減算する。

出力制御部４０は、流量監視部１０を通過したフレームを内蔵するキューバッファ（ＦＩＦＯ：Ｆｉｒｓｔ−Ｉｎ Ｆｉｒｓｔ−Ｏｕｔ）に格納し、キューバッファからフレームを出力帯域で読み出して出力する。従って、実施の形態のフレーム多重装置１００では、回線ごとのキューバッファを構築する必要がないので、単純にキューバッファを構築できる。

図２は、流量監視部の詳細な構成の一例を示す図である。図２に示すように、流量監視部１０は、廃棄判定部１１、フレーム長検出部１２および加算回路１３を備えている。廃棄判定部１１は、入力されたフレームのＶＬＡＮ ＩＤに基づいてそのフレームが属する回線を判定し、その回線に対応するカウンタ３０ａ、３０ｂのカウンタ部分の値を参照する。そして、廃棄判定部１１は、参照したカウンタ部分の値が所定の閾値を超過している場合には、そのフレームを廃棄し、カウンタ部分の値が閾値以下である場合には、そのフレームを通過させる。ここで、カウンタ部分の値と比較される閾値は、回線ごとに許容されるトラフィックのバースト量に相当する。

フレーム長検出部１２は、廃棄判定部１１を通過したフレームのフレーム長を検出し、それを加算回路１３へ通知する。ここで、フレーム長には、ＶＬＡＮタグ、プリアンブル、ＦＣＳ（Ｆｒａｍｅ Ｃｈｅｃｋ Ｓｅｑｕｅｎｃｅ、フレームチェック部）およびイーサネットフレームの最小ギャップ１２バイトが含まれる。加算回路１３は、該当するカウンタ３０ａ、３０ｂのカウンタ部分の値に、フレーム長検出部１２から通知されたフレーム長を加算してカウンタ値を更新する。従って、流量監視部１０によって、各カウンタ３０ａ，３０ｂのカウンタ部分に各回線のフレーム通過量が加算される。

図３は、帯域管理部の詳細な構成の一例を示す図である。図４は、回線検索部の動作を説明する図である。図３に示すように、帯域管理部２０は、タイミング管理部２１、回線検索部２２および減算回路２３を備えている。タイミング管理部２１は、予め設定されたフレーム流量の許容帯域Ｙで一定値のトークン量Ｘを除した帯域管理周期Ｔ（＝Ｘ／Ｙ）ごとにトリガを発生する。

図４に示すように、回線検索部２２は、タイミング管理部２１から発せられたトリガを契機として各カウンタ３０ａ，３０ｂの符号ビット＃１〜＃ｎ（３１ａ，３１ｂ，３１ｃ，３１ｄ）の値を参照し、その値が“１”である回線を巡回的に検索する。この巡回的な検索方式として、重み付きラウンドロビンを使用することができる。その際、各回線に均等な重みで巡回的な検索を行ってもよいし、各回線に重みをつけて巡回的な検索を行ってもよい。ここでは、均等な重みで検索を行うとする。

回線検索部２２は、帯域管理周期Ｔの１周期における検索を開始した後、符号ビットの値が“１”であるという条件に最初に適合した回線を選択する。そして、回線検索部２２は、その選択結果を減算回路２３へ通知するとともに、その適合した回線の情報を保持する。回線検索部２２は、次の周期における検索時には、今回適合した回線の次の回線から巡回的に検索を開始する。ここで、次の回線とは、例えば各回線に互いに異なる番号を付与し、その番号で回線を並べた場合に、その並びが降順であれば、今回適合した回線の番号の次に小さい番号の回線のことであり、昇順であれば、次に大きい番号の回線のことである。

減算回路２３は、回線検索部２２から通知された回線に対応するカウンタのカウンタ部分の値からトークン量Ｘを減算してカウンタ値を更新する。従って、フレームが流れている回線間において、均等な回数だけ一定量のトークン量Ｘがカウンタ３０ａ，３０ｂから減算される。この減算量の総和は、単位時間でのフレーム流量の許容帯域Ｙに従った通過許容量に相当する。この結果、帯域管理部２０によって、カウンタ３０ａ，３０ｂから各回線のフレーム通過許容量が減算される。

図５は、流量監視部におけるフレーム流量の監視およびカウンタ値の更新処理のフローチャートである。図５に示すように、流量監視部１０に入力されたフレームが廃棄判定部１１に到着する（ステップＳ１）と、廃棄判定部１１は、そのフレームのＶＬＡＮ ＩＤに基づいてそのフレームが属する回線を判定する（ステップＳ２）。そして、廃棄判定部１１は、その判定した回線に対応するカウンタのカウンタ部分の値を参照する（ステップＳ３）。

続いて、廃棄判定部１１は、参照したカウンタの値と閾値を比較し、カウンタの値が閾値を超えているか否かを判定する（ステップＳ４）。カウンタの値が閾値を超過している場合（ステップＳ４：Ｙｅｓ）には、そのフレームを廃棄する（ステップＳ５）。一方、カウンタの値が閾値以下である場合（ステップＳ４：Ｎｏ）には、そのフレームを通過させる（ステップＳ６）。そして、フレーム長検出部１２により、その通過したフレームのフレーム長を検出し、加算回路１３によりカウンタの値を更新する（ステップＳ７）。

図６は、帯域管理部における回線の検索およびカウンタ値の更新処理のフローチャートである。ここでは、回線に一連の番号を付与し、その番号をｉ（ｉは、１≦ｉ≦ｎの整数）で表し、回線の並びをｉの昇順とする。また、番号がｉである回線を、回線＃ｉと表す。図６に示すように、タイミング管理部２１から回線検索部２２にトリガが与えられる（ステップＳ１１）と、回線検索部２２は、前回の検索時に選択した回線の情報を保持しており、前回の検索時に選択した回線を回線＃ｉとする（ステップＳ１２）。回線検索部２２が初めて検索を行う場合には、回線検索部２２は、特に限定しないが、例えば前回の検索時に選択した回線の番号を１とする。

続いて、回線検索部２２は、ｉがｎに等しいか否かを判定する（ステップＳ１３）。ｎは、回線に付与された番号のうちの最後の番号である。等しい場合（ステップＳ１３：Ｙｅｓ）には、ｉを１とする（ステップＳ１４）。等しくない場合（ステップＳ１３：Ｎｏ）には、ｉをインクリメントし、［ｉ＝ｉ＋１］とする（ステップＳ１５）。つまり、前回の検索時に最後の番号の回線を選択した場合（ステップＳ１３：Ｙｅｓ）には、検索を開始する回線を最初の番号の回線とし、それ以外の場合（ステップＳ１３：Ｎｏ）には、検索を開始する回線を、前回の検索時に選択した回線の番号の次の番号の回線とする。

続いて、回線検索部２２は、回線＃ｉに対応するカウンタのカウンタ部分の値がゼロよりも大きいか否かを判定する（ステップＳ１６）。ゼロよりも大きい場合（ステップＳ１６：Ｙｅｓ）には、検索の結果として回線＃ｉを選択する（ステップＳ１７）。そして、回線検索部２２は、前回の検索時に選択した回線の情報を、今回の検索時に選択した回線＃ｉの情報に更新する（ステップＳ１８）。続いて、減算回路２３により回線＃ｉに対応するカウンタのカウンタ部分の値を更新する（ステップＳ１９）。

ステップＳ１６で、回線＃ｉに対応するカウンタのカウンタ部分の値がゼロ以下である場合（ステップＳ１６：Ｎｏ）には、回線＃ｉの番号が、前回の検索時に選択した回線の番号と同じであるか否かを判定する（ステップＳ２０）。同じである場合（ステップＳ２０：Ｙｅｓ）には、検索を終了する（ステップＳ２１）。同じでない場合（ステップＳ２０：Ｎｏ）には、ステップＳ１３に戻り、巡回的に回線を検索する。

上述した流量監視部１０および帯域管理部２０の動作により、カウンタ３０ａ，３０ｂのカウンタ部分の値は、各回線ごとの［（通過量）−（通過許容量）］となる。上述したように、廃棄判定部１１により、カウンタの値が閾値を超えた場合にフレームが廃棄され、帯域管理部２０により、カウンタ３０ａ，３０ｂのカウンタ部分の値が正である場合にその値からトークン量Ｘが減算されるので、各回線の通過量は、［（通過許容量）＋（閾値）］となる。通過許容量は、帯域管理部２０により回線間で均等となる。

ここで、トークン量Ｘは、入力される可変長フレームの最短フレームの長さよりも長く設定されている。ここでは、特に限定しないが、トークン量Ｘは、入力される可変長フレームの最長フレームと同じ長さに設定されているとする。なお、上述した回線検索部２２の検索処理に要求される時間が帯域管理周期Ｔに依存するので、この検索処理性能に応じてトークン量Ｘを他の値に設定することができる。また、ここでは、フレーム流量の許容帯域Ｙとして、フレーム多重装置１００の出力帯域、すなわち出力制御部４０の出力帯域が用いられる。このフレーム流量の許容帯域Ｙについても、フレーム多重装置１００の許容したい流量に従って自由に設定することができる。

次に、具体例を示す。なお、本発明は、この具体例によって限定されるものではない。構成パラメータおよびトラフィックを以下の通りとする。

（１）構成パラメータ
収容する回線数ｎを１０００とし、トークン量Ｘを、イーサフレームの最大長１５１８バイトとＶＬＡＮタグ４バイトとプリアンブル８バイトと最小フレーム間ギャップ１２バイトを足した１５４２バイトとする。フレーム流量の許容帯域Ｙを１Ｇｂｐｓとする。従って、帯域管理周期Ｔは、次式より１２．３３６μｓとなる。
１５４２（バイト）×８（ビット／バイト）÷１０⁹（ビット／ｓ）×１０⁶＝１２．３３６（μｓ）

また、各回線の閾値を１２８ｋバイトとし、出力制御部４０のキューバッファを構成するＦＩＦＯの容量を３２Ｍバイトとする。ＦＩＦＯを１２８バイト単位で管理すると、必要なアドレス数は、次式より２６２１４４となり、アドレスを表現するために必要なビット数は、１８ビットとなる。
３２×１０２４²（バイト）÷１２８（バイト）＝２６２１４４＝２¹⁸

（２）トラフィック
回線＃１〜＃４９８については、入力帯域を１０Ｍｂｐｓとし、フレーム長を５３２バイトとする。回線＃４９９については、入力帯域を２Ｍｂｐｓとし、フレーム長を８４バイトとする。回線＃５００については、入力帯域を１００Ｍｂｐｓとし、フレーム長を１５４２バイトとする。回線＃５０１〜＃１０００については、入力がないとする。各フレーム長には、ＶＬＡＮタグ、プリアンブル、ＦＣＳおよびイーサネットフレームの最小ギャップが含まれる。

上記条件において、定常的な入力により、回線＃１〜＃４９８と回線＃５００については、対応するカウンタのカウンタ部分の値が１２８ｋバイト（１３１０７２バイト）になっているとする。また、回線＃４９９に対応するカウンタのカウンタ部分の値が８４バイト（１フレーム分）になっているとする。さらに、前回の回線検索時に回線＃５００が選択されたとする。以下、便宜上、回線＃ｉに対応するカウンタのカウンタ部分の値をカウンタ値＃１と表す。なお、回線＃５０１〜＃１０００については、それらに対応するカウンタのカウンタ部分の値が常にゼロであるので、省略する。

（３）検索開始時
カウンタ値＃１〜＃４９８は、１３１０７２バイトである。カウンタ値＃４９９は、８４バイトである。カウンタ値＃５００は、１３１０７２バイトである。

（４）１周期目
検索は、回線＃５０１から開始される。カウンタ値＃５０１〜＃１０００がゼロであるので、回線＃５０１〜＃１０００は、選択されない。回線＃１に戻って検索が行われ、回線＃１が選択される。その結果、カウンタ値＃１から１５４２バイトが減算される。従って、カウンタ値＃１は、１２９５３０バイトとなる。その他のカウンタ値は、上記検索開始時と同じである。

（５）２周期目
検索は、回線＃２から開始され、回線＃２が選択される。その結果、カウンタ値＃２から１５４２バイトが減算される。従って、カウンタ値＃２は、１２９５３０バイトとなる。カウンタ値＃１は、１２９５３０バイトのままである。その他のカウンタ値は、１周期目が終了した時点と同じである。

（６）３〜４９８周期目
２周期目と同様に、順次、回線＃３、回線＃４、・・・、回線＃４９８が選択される。そして、その都度、カウンタ値＃３、カウンタ値＃４、・・・、カウンタ値＃４９８からそれぞれ１５４２バイトが減算され、それらのカウンタ値は、１２９５３０バイトとなる。従って、４９８周期目が終了した時点で、カウンタ値＃１〜＃４９８は、１２９５３０バイトとなる。カウンタ値＃４９９とカウンタ値＃５００は、２周期目が終了した時点と同じである。

（７）４９９周期目
検索は、回線＃４９９から開始され、回線＃４９９が選択される。その結果、カウンタ値＃４９９から１５４２バイトが減算される。従って、カウンタ値＃４９９は、−１４５８バイトとなる。その他のカウンタ値は、４９８周期目が終了した時点と同じである。

（８）５００周期目
検索は、回線＃５００から開始され、回線＃５００が選択される。その結果、カウンタ値＃５００から１５４２バイトが減算される。従って、カウンタ値＃５００は、１２９５３０バイトとなる。その他のカウンタ値は、４９９周期目が終了した時点と同じである。

ここまでに５００周期分の時間が経過しており、その間に各回線にフレームが流入してきている。そのフレーム量は、次式で表される。
入力帯域／フレーム長×経過時間

回線＃１〜＃４９８について計算すると、次式の通り、おおよそ１４フレームとなる。
１０×１０⁶（ビット／ｓ）÷８（ビット／バイト）÷５３２（バイト／フレーム）×１２．３３６×１０^-6（ｓ／サイクル）×５００（サイクル）＝１４．４・・・（フレーム）

回線＃４９９について計算すると、次式の通り、おおよそ１８フレームとなる。
２×１０⁶（ビット／ｓ）÷８（ビット／バイト）÷８４（バイト／フレーム）×１２．３３６×１０^-6（ｓ／サイクル）×５００（サイクル）＝１８．３・・・（フレーム）

回線＃５００について計算すると、次式の通り、５０フレームとなる。
１００×１０⁶（ビット／ｓ）÷８（ビット／バイト）÷１５４２（バイト／フレーム）×１２．３３６×１０^-6（ｓ／サイクル）×５００（サイクル）＝５０（フレーム）

５００周期目が終了した時点の各回線のカウンタ値と、（１）構成パラメータにおいて仮定した各回線の閾値１２８ｋバイトと、上述した５００周期分の時間が経過する間に各回線に流入したフレーム量とを比較すると、廃棄判定部１１で通過可能な各回線のフレーム数は、次の通りとなる。回線＃１〜＃４９８については、３フレームである。回線＃４９９については、１８フレームである。回線＃５００については、１フレームである。

各回線のカウンタ値に、５００周期目が終了するまでに通過したフレーム量を加えると、５００周期目が終了した時点での各回線の正しいカウンタ値は、次の通りとなる。カウンタ値＃１〜＃４９８は、１３１１２６バイトとなる。カウンタ値＃４９９は、５４バイトとなる。カウンタ値＃５００は、１３１０７２バイトとなる。

（９）５０１周期目
検索は、回線＃５０１から開始される。カウンタ値＃５０１〜＃１０００がゼロであるので、回線＃５０１〜＃１０００は、選択されない。回線＃１に戻って検索が行われ、回線＃１が選択される。その結果、カウンタ値＃１から１５４２バイトが減算される。従って、カウンタ値＃１は、１２９５８４バイトとなる。その他のカウンタ値は、５００周期目が終了した時点の正しいカウンタ値と同じである。

（１０）５０２周期目
検索は、回線＃２から開始され、回線＃２が選択される。その結果、カウンタ値＃２から１５４２バイトが減算される。従って、カウンタ値＃２は、１２９５８４バイトとなる。カウンタ値＃１は、１２９５８４バイトのままである。その他のカウンタ値は、５０１周期目が終了した時点と同じである。

（１１）５０３〜９９８周期目
５０２周期目と同様に、順次、回線＃３、回線＃４、・・・、回線＃４９８が選択される。そして、その都度、カウンタ値＃３、カウンタ値＃４、・・・、カウンタ値＃４９８からそれぞれ１５４２バイトが減算され、それらのカウンタ値は、１２９５８４バイトとなる。従って、９９８周期目が終了した時点で、カウンタ値＃１〜＃４９８は、１２９５８４バイトとなる。カウンタ値＃４９９とカウンタ値＃５００は、５０２周期目が終了した時点と同じである。

（１２）９９９周期目
検索は、回線＃４９９から開始され、回線＃４９９が選択される。その結果、カウンタ値＃４９９から１５４２バイトが減算される。従って、カウンタ値＃４９９は、−１４８８バイトとなる。その他のカウンタ値は、９９８周期目が終了した時点と同じである。

（１３）１０００周期目
検索は、回線＃５００から開始され、回線＃５００が選択される。その結果、カウンタ値＃５００から１５４２バイトが減算される。従って、カウンタ値＃５００は、１２９５３０バイトとなる。その他のカウンタ値は、９９９周期目が終了した時点と同じである。

１０００周期目が終了した時点で回線＃１〜＃４９８、回線＃４９９および回線＃５００の各カウンタ値から減算したトークン量は、いずれも３０８４バイトである。回線＃５０１〜＃１０００については、減算したトークン量は、０バイトである。１０００周期分の時間が１２．３３６ｍｓ（＝１２．３３６μｓ×１０００）であるので、各回線について減算したトークン量をレートに換算すると、回線＃１〜＃４９８、回線＃４９９および回線＃５００のいずれも２Ｍｂｐｓとなる。回線＃５０１〜＃１０００については、０Ｍｂｐｓである。

１００１周期目以降も続けると、フレームが流れている回線数で出力帯域を均等にした２Ｍｂｐｓに相当するトークンが、フレームが流れている回線に対応するカウンタから減算される。この結果、回線＃１〜＃５００については、１２８ｋバイトのカウンタ閾値と２Ｍｂｐｓ帯域が通過可能なフレーム流量となる。通過したフレームは、出力制御部４０のＦＩＦＯにキューイングされ、１Ｇｂｐｓで出力される。以上のようにして、フレームの流れている回線間で均等に帯域が利用できるようにフレーム多重が行われる。

次に、上述した具体例で必要とされるメモリ量と、重み付きラウンドロビンによる読み出し制御方式で同様の制御を行う場合に必要となるメモリ量を比較する。具体例の場合には、ＦＩＦＯの開始位置と終了位置を示すアドレスが必要であるので、キューバッファ管理に必要なメモリのビット数は、３６ビット（＝１８ビット×２）である。

また、カウンタの最大値は、１３２６１３バイト（＝閾値１２８ｋバイト−１＋最大フレーム長１５４２バイト）である。これを表現するには、カウンタのカウンタ部分として１８ビットが必要である。さらにカウンタには符号ビットとして１ビットが必要であるので、１回線当たり合計で１９ビットが必要となる。従って、１０００回線分のカウンタを構築するために必要なメモリのビット数は、１９０００ビットとなる。

重み付きラウンドロビンによる読み出し制御方式の場合には、共有バッファの空きアドレスを管理するメモリのビット数は、４７１８５９２ビット（＝アドレス数２６２１４４×アドレス長１８）となる。また、キュー長を上記具体例のカウンタ長と同じ１２８ｋバイトとすると、イーサネットの最短フレームが８４バイトであるため、キューバッファに最大で１５６０フレームを格納する必要がある。従って、１０００回線分のキューバッファを構築するために必要なメモリのビット数は、２８０８００００ビット（＝フレーム長１５６０×アドレス長１８×回線数１０００）となる。

上述したように、具体例では、カウンタを構築するために必要なメモリとキューバッファ管理に必要なメモリで、合計１９０３６ビットが必要である。それに対して、重み付きラウンドロビンによる読み出し制御方式では、空きアドレスを管理するメモリとキューバッファを構築するのに必要なメモリで、合計３２７９８５９２ビットが必要である。従って、具体例によれば、必要なメモリの容量がおよそ１／１７００になる。このように、メモリの容量を大幅に削減することができるので、コストの増大や装置の大型化を招くことなく、収容回線数を増やすことができる。

また、具体例では、回線を検索する周期が１２．３３６μｓであり、この時間内に回線検索部２２と減算回路２３の処理を行えばよい。それに対して、重み付きラウンドロビンによる読み出し制御方式で同様の制御を行う場合には、最短フレームを読み出すのに必要な時間（Ｔ０）は０．６７２μｓであり、この時間内に次の読み出しを行うフレームを検索しなければならない。このように、回線を検索する時間を十分に長くすることができるので、出力速度を上げることができる。

図７は、帯域管理部の他の例を示す図である。図７に示す帯域管理部５０は、図３に示す帯域管理部２０の構成に、ｎ回線の入力回線の回線ごとに選択回数カウンタ２４ａ，２４ｂを設けたものである。選択回数カウンタ＃１〜＃ｎ（２４ａ，２４ｂ）は、回線検索部２２による回線検索の結果、選択された回数を回線ごとにカウントする。回線検索部２２は、上述した回線検索処理の実行中に、選択した回線に対応する選択回数カウンタ２４ａ，２４ｂの値をインクリメントする。

また、特に図示しないが、帯域管理部５０は、各選択回数カウンタ２４ａ，２４ｂの値とトークン量の積を求め、その値を外部へ出力するようにしてもよい。外部へ出力する手段としては、特に限定しないが、例えばＳＮＭＰ（Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ）やＣＬＩ（Ｃｏｍｍａｎｄ Ｌｉｎｅ Ｉｎｔｅｒｆａｃｅ）などを用いることができる。

選択回数カウンタ２４ａ，２４ｂの値とトークン量の積は、通過許容量となる。フレームの通過量は、通過許容量にカウンタ３０ａ，３０ｂの閾値を足したものであるので、フレームの通過量を閾値の誤差で求めることができる。この情報をオペレータに通知することによって、回線ごとにフレーム通過量を監視できるので、加入者回線を収容する装置の場合には、加入者回線の異常を発見することができる。また、回線ごとにフレーム通過量を監視することによって、上位ネットワークの増強を行う必要性があるか否かを的確に判断することが可能となる。

さらに、例えば上記具体例のように、トークン量Ｘを１５４２バイトとすると、フレーム通過量の監視を行うために必要なメモリの容量は、フレーム通過量をバイト単位で管理する場合の１／１５４２でよい。以上において本発明は、上述した実施の形態に限らず、種々変更可能である。

（付記１）複数の回線から入力された可変長フレームを多重して出力するフレーム多重装置において、
複数の回線ごとに設けられた複数のカウンタと、
各回線に対応する前記カウンタの値に基づいて各回線のフレーム流量を監視し、通過するフレームのフレーム長を、該フレームが入力された回線に対応する前記カウンタの値に加算する流量監視部と、
フレームが入力されている回線の中から巡回的に１回線を選択し、選択された回線に対応する前記カウンタの値から所定のトークン量を減算する帯域管理部と、
前記流量監視部を通過したフレームをキューバッファに格納し、出力帯域で出力する出力制御部と、を備えることを特徴とするフレーム多重装置。

（付記２）前記流量監視部は、各回線に入力されたフレームを、該フレームの入力によって対応するカウンタの値が、予め回線ごとに設定された閾値を超える場合に廃棄し、超えない場合に通過させる廃棄判定部を有することを特徴とする付記１に記載のフレーム多重装置。

（付記３）前記帯域管理部は、フレームが入力されている回線の中から１回線を選択する処理を行うためのトリガを、予め設定されたフレーム流量の許容帯域で前記トークン量を除した帯域管理周期ごとに発生するタイミング管理部を有することを特徴とする付記１に記載のフレーム多重装置。

（付記４）前記帯域管理部は、前記タイミング管理部から発せられたトリガを契機として前記カウンタの値を参照し、該カウンタの値に基づいて、フレームが入力されている回線の中から１回線を選択する回線検索部を有することを特徴とする付記３に記載のフレーム多重装置。

（付記５）前記帯域管理部は、回線ごとに前記回線検索部により選択された回数をカウントする選択回数カウンタを有することを特徴とする付記４に記載のフレーム多重装置。

（付記６）前記閾値は、回線ごとに許容されるトラフィックのバースト量に等しいことを特徴とする付記２に記載のフレーム多重装置。

（付記７）前記トークン量は、入力される可変長フレームの最短フレームの長さよりも長く設定されていることを特徴とする付記３に記載のフレーム多重装置。

（付記８）前記トークン量は、入力される可変長フレームの最長フレームと同じ長さに設定されていることを特徴とする付記３に記載のフレーム多重装置。

（付記９）前記フレーム流量の許容帯域は、前記出力制御部の出力帯域に等しいことを特徴とする付記３に記載のフレーム多重装置。

（付記１０）前記カウンタは、カウントした値を示す複数ビットのカウンタ部分と、該カウンタ部分の値が正の値であるか否かを示す符号ビットを有することを特徴とする付記１に記載のフレーム多重装置。

（付記１１）前記帯域管理部は、前記符号ビットが、前記カウンタ部分の値が正の値であることを示す回線の中から１回線を選択することを特徴とする付記１０に記載のフレーム多重装置。

（付記１２）前記帯域管理部は、重み付きラウンドロビン方式により巡回的に回線の検索を行い、該当する１回線を選択することを特徴とする付記１１に記載のフレーム多重装置。

（付記１３）前記帯域管理部は、各回線に均等な重みで巡回的な検索を行うことを特徴とする付記１２に記載のフレーム多重装置。

（付記１４）前記帯域管理部は、各回線に重みをつけて巡回的な検索を行うことを特徴とする付記１２に記載のフレーム多重装置。

以上のように、本発明にかかるフレーム多重装置は、ｘＤＳＬやＦＴＴｘなどのブロードバンドによる加入者回線を効率良く収容するネットワーク機器に有用である。

本発明にかかるフレーム多重装置の構成の一例を示す図である。 流量監視部の構成の一例を示す図である。 帯域管理部の構成の一例を示す図である。 回線検索部の動作を説明する図である。 フレーム流量の監視およびカウンタ値の更新処理のフローチャートである。 回線の検索およびカウンタ値の更新処理のフローチャートである。 帯域管理部の他の例を示す図である。 従来のフレーム多重装置の構成を示す図である。

符号の説明

１０ 流量監視部
１１ 廃棄判定部
２０，５０ 帯域管理部
２１ タイミング管理部
２２ 回線検索部
２４ａ，２４ｂ 選択回数カウンタ
３０ａ，３０ｂ カウンタ
３１ａ，３１ｂ，３１ｃ，３１ｄ 符号ビット
４０ 出力制御部
１００ フレーム多重装置

Claims (5)

1. 複数の回線から入力された可変長フレームを多重して出力するフレーム多重装置において、
   複数の回線ごとに設けられた複数のカウンタと、
   各回線に対応する前記カウンタの値に基づいて各回線のフレーム流量を監視し、通過するフレームのフレーム長を、該フレームが入力された回線に対応する前記カウンタの値に加算する流量監視部と、
   フレームが入力されている回線の中から巡回的に１回線を選択し、選択された回線に対応する前記カウンタの値から所定のトークン量を減算する帯域管理部と、
   前記流量監視部を通過したフレームをキューバッファに格納し、出力帯域で出力する出力制御部と、
   を備えることを特徴とするフレーム多重装置。
2. 前記流量監視部は、各回線に入力されたフレームを、該フレームの入力によって対応するカウンタの値が、予め回線ごとに設定された閾値を超える場合に廃棄し、超えない場合に通過させる廃棄判定部を有することを特徴とする請求項１に記載のフレーム多重装置。
3. 前記帯域管理部は、フレームが入力されている回線の中から１回線を選択する処理を行うためのトリガを、予め設定されたフレーム流量の許容帯域で前記トークン量を除した帯域管理周期ごとに発生するタイミング管理部を有することを特徴とする請求項１に記載のフレーム多重装置。
4. 前記帯域管理部は、前記タイミング管理部から発せられたトリガを契機として前記カウンタの値を参照し、該カウンタの値に基づいて、フレームが入力されている回線の中から１回線を選択する回線検索部を有することを特徴とする請求項３に記載のフレーム多重装置。
5. 前記帯域管理部は、回線ごとに前記回線検索部により選択された回数をカウントする選択回数カウンタを有することを特徴とする請求項４に記載のフレーム多重装置。

Images