JP2005354738A - Ａｔｍセル転送装置 - Google Patents

Abstract

【課題】 通信路帯域を有効に利用するシェーピング装置を提供する。
【解決手段】 高優先度パケット用のキュー１００と低優先度パケット用のキュー１０１を設け、優先キュー１００からパケットを送信すべき時刻になっているのに関わらず優先キューに送信待ちパケットがない場合に、読出された非優先キュー１０１の送信待ちパケットに対して高優先度を与えて送信する。
【選択図】 図１

Description

本発明は、パケット転送網に接続されるパケット中継装置に関し、更に詳しくはパケット中継装置内のトラヒックシェーピング装置に関する。

インターネット等のネットワークにおけるパケット転送では、ユーザは、情報系列を数十バイト〜数万バイト程度の長さのデータ列（ペイロード）に分割し、通信プロトコル毎に決められているフォーマットに従って宛先情報や制御情報（ヘッダ）を付加したパケットを用いて情報を転送する。パケットの長さはプロトコル毎に異なり、ＩＰ（Internet Protocol）の様にパケット毎に可変長のものと、ＡＴＭ（Asynchronous Transfer Mode）の様に固定長のものがある。

近年、公衆パケット網において安価なサービスが適用されるようになり、複数の私設網を公衆パケット網を介して接続した仮想私設網（Virtual Private Network：ＶＰＮ）が注目されている。図２に公衆網を介した企業ネットワークの接続図を示す。図２において、私設網Ａ４１と私設網Ｂ４２は公衆網４０を介して接続されている。一般に、公衆網を介して通信を行う場合、ユーザはパケット転送前に公衆網の管理者との間に、送信帯域やパケット転送の優先度に関する契約を行う。ユーザ・公衆網管理者間の契約が成立し、端末が公衆網に向けてパケットを転送し始めると、公衆網の入口に位置している中継装置４０２で端末の送信帯域を監視し、契約内容に違反している端末のパケットの優先度を下げたり、あるいは違反パケットを廃棄したりする。この公衆網側の監視機能をＵＰＣ（Usage Parameter Control）という。通信途中でパケットが廃棄されても、通常は受信端末でパケット廃棄が生じたことを認識して送信端末に向けてパケット再送要求が出され、送信端末がパケットを再送する機能を備えているので、最終的な情報の欠落はないが、転送遅延が非常に大きくなってしまうことや、再送パケットによって網が輻輳（込み合うこと）する原因にもなるために、パケット廃棄は生じないことが望ましい。そこで、公衆網に向けてパケットを送信している中継装置４０１では、公衆網のＵＰＣによってパケットが廃棄されない様に送信帯域を制御してパケットを送信することが必要となる。このパケット送信帯域を制御する機能をトラヒックシェーピング機能、あるいは単にシェーピング機能という。シェーピング機能を実現するためのシェーピング装置は、上述の様な、公衆網に直接接続されている中継装置の他に、ユーザの送信端末や、あるいは私設網へ向けてパケットを送信する公衆網の出口部分に必要な場合もある。

公衆網がユーザに提供するサービス、すなわちユーザ・公衆網管理者間の契約は、公衆網内に常時一定の帯域を確保してからパケットを転送する契約と、公衆網ＡＴＭ内の帯域を確保せずにパケットを転送するベストエフォート系の契約に大別される。前者は、公衆網内で他のユーザのトラヒック量の影響を受けずに常に一定の帯域でパケットを転送できるため、音声等の転送に適している。後者は、他のユーザのトラヒック量によっては、転送遅延が大きくなったり、あるいは網内でパケットが廃棄されることもあるが、一般に固定帯域契約よりも安価であり、ＦＴＰ（File Transfer Protocol）や電子メール等のバースト的（突発的）なデータ系トラヒックの転送に用いられている。最近では、ベストエフォート系の契約ながら公衆網が混雑しているときでも一定帯域を保証するクラスが提案されている（ＡＴＭでは、ＧＦＲ（Guaranteed Frame Rate）と呼ばれている）。このクラスでは、パケット転送前に最低保証帯域と最大転送帯域を契約し、公衆網内が混雑していないときには最大転送帯域でパケットを転送し、網が混雑してきた場合でも最低保証帯域分は必ず転送される。

シェーピング装置の実現方法に関しては、例えば、特開平9-307566号公報“トラフィックシェーピング装置”（従来技術１）に述べられている。従来技術１はＡＴＭに関して記述されている。従来技術１では、シェーピングを行いたい契約単位（例えば、ＶＣ（Virtual Connection））毎にキューを備え、セル（一般に、ＡＴＭで用いる固定長パケットを特に“セル”と称する）送信時に送信したＶＣの次のセルを送信することができる時刻（以下、送信予定時刻）を計算し、それを二分木構造を用いて記憶している。すなわち、二分木の底辺は各ＶＣの送信予定時刻が記憶されており、送信予定時刻が早い（時間的に過去にあるもの）時刻のＶＣが勝ち上がっていき、最終的に最も送信予定時刻が早いＶＣが選び出される。従って、二分木の頂点には最も優先して送信されるべきＶＣの送信予定時刻（底辺にある値の一つ）が記憶されている。送信予定時刻の計算およびソーティングは、セル送信時の他に、送信待ちセルがない状態でセルを受信したときにも行なわれる。これにより、前回セル送信時のソーティング結果（二分木構造）を利用してソーティングを行うことができるため、log(ＶＣ数)のオーダの処理時間で最優先に送信すべきＶＣを選び出すことができる。

通常、通信路に送信されているパケットの中には、重要なパケットとさほど重要でないパケットが混在している。ここで、重要なパケットとは、ｔｅｌｎｅｔ等の低遅延転送が要求されるトラヒックのパケットであり、さほど重要でないパケットとは、電子メールの様な遅延が大きくなっても影響が少ないトラヒックのパケットのことである。この様に重要なパケットとさほど重要でないパケットが混在している場合では、網が輻輳しているときにでも重要なパケットを優先して先に送信する優先制御を行うことが重要となる。そこで、通常パケットのヘッダ部分には、そのパケットの優先度を示すフィールドが準備されている。例えば、ＩＰパケットの場合にはサービスタイプ（Type of Service）フィールドであり、ＡＴＭセルの場合にはＣＬＰ（Cell Loss Priority）ビットである。尚、以下では、簡単のために優先度は２段階（高優先度／低優先度）して説明するが、ＩＰパケットでは更に細かい優先度を与えることもできる。また、高優先度が割り当てられたパケットを高優先度パケット、低優先度が割り当てられたパケットを低優先度パケットと記述する。

帯域保証を行うベストエフォート系のサービスに対して、従来のシェーピング装置を適用すると、全パケットを高優先度で送信することになる。保証帯域を超えた高優先度パケットは、ＵＰＣ機能によって優先度が下げられるが、このとき、上記の重要パケット・非重要パケットを考慮せずに、高優先度パケット・低優先度パケットを決定するため、重要なｔｅｌｎｅｔが低優先度パケットになったり、さほど重要でないＷｅｂのパケットが高優先度パケットになったりすることもあり、これはユーザにとって望ましい優先度の割り当てではない。シェーピング装置内で、重要パケットを高優先度パケットに、非重要パケットを低優先度パケットに割り当てることは容易であるが、高優先度パケットの送信帯域が保証帯域以下になるようにシェーピングを行わないと、ＵＰＣで無作為に優先度が下げられることになるので、これもユーザにとって望ましい優先度の割り当てではない。また、重要パケットのトラヒック量が少ない場合には保証帯域をできないが、主な課金の対象は保証帯域分であるので保証帯域を有効に使い切ることが重要である。

本発明の第１の目的は、同一相手先に送信するパケットの内の優先して送信すべきパケットを保証帯域（パケット転送前に契約）で送信し、通信路帯域に余裕があれば、優先パケットの送信帯域と非優先パケットの送信帯域の合計帯域が最大転送帯域（パケット転送前に契約）以下になる様に非優先パケットを送信する様なシェーピング装置を提供することである。

本発明の第２の目的は、上述のユーザにとって望ましい優先度割り当てを行い、更に、さほど重要でないパケットの一部を高優先度パケットとして送信することで保証帯域を有効に利用する様なシェーピング装置を提供することである。

本発明の第３の目的は、ＡＴＭ網において上位レイヤのパケット単位で帯域保証を行うＧＦＲサービスに対応したシェーピング装置を提供することである。

上記第１の課題を解決するために、本発明においては、パケット中継装置の回線対応部内のシェーピング部に、ユーザ毎に高優先度パケットを蓄積するためのキュー（以下、優先キュー）と、低優先度パケットを蓄積するためのキュー（以下、非優先キュー）を備える。優先キュー、および非優先キューはおのおの１つであってもよいし、複数個のキューが存在してもよい。

また、優先キューに蓄積されている送信待ちパケットの先頭パケットの送信予定時刻は保証帯域を守る様に計算し、非優先キューに蓄積されている送信待ちパケットの先頭パケットの送信予定時刻はすぐに送信される時刻を計算し、優先キュー／非優先キューを含めた送信帯域（最大契約帯域）に対応する送信予定時刻を計算するための送信予定時刻計算回路を備える。更に、優先キューから読出されたパケットには高優先度を与え、非優先キューから読出されたパケットには低優先度を与える優先度情報付与回路を備える。送信予定時刻計算回路と優先度情報付与回路によって、重要パケットを高優先度パケットとして保証帯域で送信することができ、かつ残りの帯域（最大契約帯域−保証帯域）で非重要パケットを低優先度パケットとして送信することができる。

前記送信予定時刻計算回路は、優先キューの送信予定時刻を計算する際に、優先キューのキュー長（蓄積パケット数）を参照し、一定量以上のパケットが蓄積されている場合には保証帯域を守らずにすぐに送信される時刻を送信予定時刻として計算してもよい。これにより、シェーピングしている為に優先キューの蓄積パケット数が多くなり、キューから溢れてしまう現象を回避することができる。

上記第２の課題を解決するために、本発明においては、前記優先度付与回路に、優先キューからパケットを送信すべき時刻になっているのに関わらず優先キューに送信待ちパケットがない場合に、読出された非優先キューの送信待ちパケットに対して高優先度を与える機能を備える。これにより、重要パケットのトラヒック量が少ない場合にも保証帯域をすべて優先パケットとして送信することができ、保障帯域を有効に利用することができる。

上記第３の課題を解決するために、本発明においては、上位レイヤのパケット最終セル（以下、ＥＯＰ（End Of Packet）セル）を検出して、ＥＯＰセルを送受信した場合にのみ上記ＩＰパケットを送受信した場合の処理を行う機能を備える。これにより、上位レイヤのパケット単位でセルを送受信することができ、ＧＦＲサービスに対応したシェーピングを行うことができる。

以上に述べた様に、本発明によれば、重要パケットを高優先度パケットとして保証帯域で送信することができ、重要パケット間に空き時間がある場合には非重要パケットを低優先度パケットとして隙間なく送信できるシェーピング装置を提供することができる。従って、網が空いているときには最大帯域でパケットを転送することができ、網が混雑しているときにでも重要パケットを保証帯域で転送することができ、通信路の帯域を有効に利用することができる。更に、重要パケットのトラヒック量が少ない場合には非重要パケットを高優先度パケットとして送信することができ、保障帯域を最大限に利用することができる。

また、本発明によれば、ＡＴＭにおいて上位レイヤのパケット単位でＵＰＣを行うＧＦＲサービスに対するシェーピング装置も構成することができ、網が空いているときには最大帯域で上位レイヤのパケットを転送することができ、網が混雑しているときにでも上位レイヤの優先パケットを保証帯域で転送することができる。

図３に本発明を適用したパケット中継装置の構成図を示す。以下では、パケットはＩＰパケットとして説明する。ＩＰパケットのフォーマットを図４に示しておく。図３において、パケット中継装置９８は、網９９−１〜９９−３に接続されている。パケット中継装置９８は、接続されている回線の種類（イーサ、ＡＴＭ、フレームリレー等）に対応した回線対応部２−１〜２−３、次の転送先を決定するパケット処理部３−１〜３−２、および複数のパケット処理部の中継を行うクロスバスイッチ８から構成されている。図３では１つのパケット処理部３−１に、複数の回線対応部２−１、２−２がバス９によって接続されているが、１つのパケット処理部に１つの回線対応部が接続される構成でもよい。また、図３では複数のパケット処理部３−１、３−２がクロスバスイッチ８によって接続されているが、パケット処理部が１つである様な構成でもよく、この場合クロスバスイッチ８は不要である。

次に、パケット中継装置９８がパケットを受信し、送信先の検索を行い、検索結果の回線に向けてパケットを送信する動作について説明する。私設網９９−２から受信されたパケットは、回線対応部２−２、およびバス９を介してパケット処理部３−１内のパケット転送部４へ送られる。パケット転送部４では、受信パケットをパケットバッファ５に一時的に保存するとともに、その転送先ＩＰアドレス（図４ではDestination IP Address）等のルーティングに必要な情報が書き込まれているヘッダをルート検索部６に通知する。ルート検索部６では、ヘッダ内の転送先アドレスからルーティング情報メモリ７に記憶してあるルーティング先を読出す。ルート検索部６は、読出した結果のルーティング先の情報をパケット転送部４に通知する。パケット転送部４は、パケットバッファ５からパケットを読出し、ルート検索部６から通知されたルーティング先へ読出したパケットを転送する。ルーティング先の検索結果によって、パケットはクロスバスイッチ８、他のパケット処理部、バスを介して回線対応部に転送される場合と、直接バス９を介して回線対応部に転送される場合がある。例えば、公衆網９９−１に向けて転送する場合は、バス９を介して回線対応部２−１に転送され、公衆網９９−１との契約帯域を守るために、パケットはシェーピング装置１によってシェーピングされて、物理レイヤ対応部１１１を介して、公衆網９９−１に送信される（私設網に向けて送信する場合には、一般にシェーピングの必要性は薄い）。

図１に回線対応部２−１内のシェーピング装置１のブロック図を示す。図１において、シェーピング装置１は、パケットを一時的にキューイングしておくパケットバッファ部１０、受信したパケットの優先度を判別し、受信パケットをキューイングすべきキューを決定するキューイング先判別回路１１、キュー毎の送信予定時刻から各ユーザ毎に最優先で送信すべきキューの送信予定時刻までを２分木構造を用いて記憶し、更にユーザ毎の送信予定時刻から最優先で送信すべきユーザの送信予定時刻までを２分木構造を用いて記憶しておく送信予定時刻記憶回路１２、送信予定時刻記憶回路１２に記憶してある２分木構造の送信予定時刻を用いて最優先で送信すべきキューを選び出し、結果を再び送信予定時刻記憶回路１２に書き戻すソーティング回路１７、パケット送信・受信時に該当出力相手先の送信予定時刻を計算し、計算結果の送信予定時刻を送信予定時刻記憶回路１２に保存する送信予定時刻計算回路１３、および送信予定時刻記憶回路１２に記憶されているキュー毎の送信予定時刻に従って、パケットバッファ１０からパケットを読出して送信するパケット読出し回路１４、送信されるパケットに対して優先度情報（高優先度／低優先度）を付与する優先度情報付与回路１５、および現在の時刻を示している時計１６より構成される。

パケットバッファ１０は、保証帯域内で送信する優先パケットをキューイングしておく優先キュー１００（ユーザ毎に存在し、図１ではユーザ１の優先キューを１００−１、ユーザ２の優先キューを１００−２と示している）と、保証帯域外で網が空いているときに送信する非優先パケットをキューイングしておく非優先キュー１０１（図１では優先キューと同様の規則で１０１−１、１０１−２と示している）により構成される。

送信予定時刻計算回路１３は、パケット受信時点、あるいはパケット送信時点から直ちにパケットを送信させるための送信予定時刻１３００を計算する即出し時刻計算回路１３０と、保証帯域を超えない様な送信間隔を守るための送信予定時刻１３１０を計算する帯域保証読出し時刻計算回路１３１と、送信予定時刻記憶回路１２に、前記２つの送信予定時刻１３００および１３１０のいずれをを書込むか、あるいはいずれも書込まないか、を選択する選択回路１３２、および最大契約帯域を超えない様な送信間隔を守るための送信予定時刻を計算する最大帯域読出し回路１３３から構成される。具体的には、即出し時刻計算回路１３０では、時計１６によって通知される現在時刻１６００を用いて、送信予定時刻１３００を、
送信予定時刻１３００＝現在時刻＋１
として計算する。すなわち、他のキューから送信するパケットがない場合には、すぐにパケットが送信される。また、帯域保証読出し時刻計算回路１３１、および最大帯域読出し時刻計算回路１３３では、複数のＶＣの送信予定時刻が競合してゆらぎが生じた様な場合にも平均として契約帯域で送信できる様なアルゴリズムによって、送信予定時刻１３１０を計算する。例えば、“The ATM Forum TM4.0”等に記載されているリーキーバケットアルゴリズムを用いれば、前述の様なゆらぎを吸収して、平均として契約帯域でパケットを送信することができる。

次に、送信予定時刻記憶回路１２の記憶フォーマットを図６に、詳細ブロック図を図７に示す。図６に示す様に、送信予定時刻記憶回路１２には、キュー毎に送信予定時刻３０、送信予定時刻３０が有効であることを示す時刻有効フラグ３１、およびキューに送信待ちのパケットが蓄積されていることを示すパケット有効フラグ３２が記憶されている。また、図７に示す様に、送信予定時刻記憶回路１２は、送信予定時刻に関する情報を記憶するメモリ１２２、メモリ１２２の制御信号を生成しメモリ１２２からのリードデータを各ブロックに送るメモリ制御回路１２０、およびメモリ１２２に記憶してある送信予定時刻３０が有効な値であるか否かを判断し、時刻有効フラグ３１を更新する時刻有効フラグ更新回路１２１より構成される。

ここで、時刻有効フラグの意味について説明する。シェーピング時刻を決定している時計１６は通常有限ビット数のカウンタとして構成するが、この場合、カウンタのビット数によって決まる一定周期毎に同じ時刻を示すことになる。すなわち、メモリ１２２内に、ある送信予定時刻を記憶していても、その時刻が正しい送信予定時刻を示しているのか、カウンタが１周以上回ってしまった不正な（過去になり過ぎている）時刻を示しているのか、を決定することができない。これを区別するのが時刻有効フラグ３１である。時刻有効フラグ３１は、送信予定時刻３０が正しい時刻を示しているときに‘１’、カウンタが１周以上回ってしまった不正な時刻を示しているときに‘０’となるフラグである。

以上に示した構成のシェーピング装置１を用いて、パケット転送部４からバス９を介して受信したパケットを回線に向けて送信するまでの動作を説明する。

また、ソーティング回路１７は、従来技術１に示されているソーティング方法と同様のソーティングを行う。

（１）パケット受信動作
ここでのパケット受信動作とは、シェーピング装置１が、バス９を介してパケット転送部４からパケットを受信したときの動作のことを示している。シェーピング装置１がパケットを受信すると、まず最初にキューイング先判別回路１１において、受信セルを優先キュー１００にキューイングするか、非優先キュー１０１にキューイングするか、を決定する。キューの決定は、例えばＩＰパケットの場合は、受信パケットのヘッダ中にあるサービスタイプ、パケット長、プロトコル種別、ＳＩＰ（Source IP Address）、ＤＩＰ（Destination IP Address）等の情報（図４の網掛けで示したフィールドの情報）を用いて行なわれる。キューイング先のキューが決定されると、受信パケットはパケットバッファ１０にキューイングされる。キューイングと同時にどのキューにキューイングされたかを示す信号１１００が送信予定時刻計算回路１３に向けて送られる。送信予定時刻計算回路１３は、送信予定時刻記憶回路１２に記憶している受信パケットをキューイングしたキューに関する送信予定時刻３０、時刻有効フラグ３１、およびパケット有効フラグ３２を読出す。

送信予定時刻計算回路１３内の選択回路１３２の動作規則を図５に示し、受信時のフロー図を図９に示す。パケット有効フラグ＝１のときは（図９ステップ５０）、既に１個以上のパケットがキューイングされており、その最初の送信待ちパケットに対する送信予定時刻が計算されているということであるから、送信予定時刻の更新はしない。パケット有効フラグ＝０、かつ時刻有効フラグ＝０のときは（図９ステップ５１）、空のキューに受信パケットをキューイングし、かつ記憶していた送信予定時刻は十分に時間が経過しているために無効なものになっているので送信予定時刻を更新する必要がある。パケット有効フラグ＝０、かつ時刻有効フラグ＝１のときは、記憶していた送信予定時刻は有効な時刻である。記憶していた送信予定時刻が現在時刻と比較して未来にある場合には（図９ステップ５２）、シェーピング間隔が狭くなるのを防ぐために送信予定時刻を更新してはいけないが、記憶していた送信予定時刻が現在時刻と同時刻、あるいは現在時刻と比較して過去にある場合には、既にシェーピング間隔以上の間隔が空いており、即出しをしてもシェーピング間隔を守ることができるので、送信予定時刻の更新を行う。パケット受信時の送信予定時刻の更新は、すべて即出しをさせるためのものであるから、送信予定時刻の更新を行うときには常に即出し時刻計算回路１３０で計算された送信予定時刻１３００を送信予定時刻記憶回路１２の送信予定時刻領域３０に上書きする（図９ステップ５３）。また、該当キューはパケットを受信したのであるから、パケット有効フラグ３２は常に１にセットする。
更に、ユーザ毎の送信予定時刻も全く同様の規則により変更する。

前述の様に、送信予定時刻記憶回路１２には最優先で送信すべきキューの送信予定時刻も記憶されているが、パケット受信により、送信予定時刻３０、およびパケット有効フラグ３２が更新されたため、最優先で送信すべきキューが変化した可能性がある。そこで、更新された情報を基にソーティング回路１７でソーティングを行い、最優先で送信すべきキューを選び直す。

（２）パケット送信動作
ここでのパケット送信動作とは、シェーピング装置１から、回線に向けてパケットを送信する動作のことを示している。パケット送信は、パケット受信とは非同期に行なわれる。図１において、パケット読出し回路１４は、送信予定時刻記憶回路１２に記憶してある最優先で送信すべきユーザの送信予定時刻３０、時刻有効フラグ３１、パケット有効フラグ３２を読出す。該ユーザが送信可能と判定されるのは、パケット有効フラグ３２＝１、かつ時刻有効フラグ３１＝１、かつ送信予定時刻３０≦現在時刻（送信予定時刻３０が過去または現在）のときのみである。それ以外の場合は、最優先で送信すべきキューのパケットでさえ送信できないのであるから、すべてのキューのパケットが送信できない。最優先で送信されるべきユーザのパケットが送信されるときは、次に該ユーザの中で最優先で送信すべきユーザの送信予定時刻３０、時刻有効フラグ３１、パケット有効フラグ３２を読出す。パケットが読出されるのは、パケット有効フラグ３２＝１、かつ時刻有効フラグ３１＝１、かつ送信予定時刻３０≦現在時刻（送信予定時刻３０が過去または現在）のときのみである。それ以外の場合は、従って、どのキューからもパケットを送信しない。同一ユーザの優先キューと非優先キューが、共に読出し可能な状態になっているときは、必ず優先キューのパケットを送信する（完全優先制御）。

パケット読出し回路１４によってパケットバッファ１０から読出されたパケットは、優先度情報付与回路１５に転送されて優先度情報が付与される。優先度情報とは、ＩＰパケットの場合はサービスタイプフィールド（図４のType of Service）であり、ＡＴＭセルの場合はＣＬＰビットのことを示している。優先度情報付与回路１５は、優先キュー１００から読出したパケットは高優先度、非優先キュー１０１から読出したパケットは低優先度を付与し、回線に向けてパケットを送信する。

パケットを送信したとき、同じキューにキューイングされている次のパケットのために送信予定時刻３０を更新する。パケット送信時に送信したキューの種別を示す信号１４００が送信予定時刻計算回路１３に向けて送られる。送信予定時刻計算回路１３内の選択回路１３２の動作規則を図５に示し、送信時のフロー図を図１０に示す。送信したパケットが優先キューから読出されたパケットであった場合、保証帯域を守るために帯域保証読出し時刻計算回路１３１の計算結果１３１０を選択する（図１０ステップ５４−１）。非優先キューのパケットを送信した場合には、即出しをすればよいので即出し時刻計算回路１３０の計算結果１３００を選択する（図１０ステップ５４−２）。選択された送信予定時刻は、送信予定時刻記憶回路１２の送信予定時刻領域３０に上書きされる。同時に、ユーザ毎の送信予定時刻も更新し、上書きする。

更に、パケットを送信したことによりパケットを読出したキューが空になった（キュー長＝０）ときには、パケット有効フラグ＝０として送信予定時刻記憶回路１２に記憶する。パケットを送信してもキューが空にならなかった（キュー長＞０）ときには、送信予定時刻記憶回路１２のパケット有効フラグ３２は更新しない（パケット有効フラグ＝１）。また、時刻有効フラグは、“１”の状態から更新しない。

（３）時刻有効フラグ更新動作
本発明では図８に示す様な構造の時計を使用する。有限ビット数の時計８９のある値（時刻）が現在時刻８０であり、一定の速度でカウントアップされている（時計方向に進んでいる）。カウントアップの速度は、送信先回線の帯域に依存している。現在時刻８０が既に過ぎた領域が過去領域８１であり、まだ現在時刻８０が達していない領域が未来領域８２である。現在時刻８０ではない、過去領域８１と未来領域８２の接点に不確定領域８３を設けておく。不確定領域８３は、過去でも未来でもない領域であり、現在時刻から常に一定の距離（時間差）にある。

不確定領域８３を設けておかないと、ある時刻に過去であった送信予定時刻が、時刻が１進んだだけで未来の時刻になってしまい、正しいシェーピングを行うことができなくなる、という不都合が生じる。そこで、メモリ１２２に記憶してある送信予定時刻３０が更新されずに過去領域８１の時刻になり、更に時間が進み不確定領域８３の時刻になったとき、時刻有効フラグを‘０’にする。

送信予定時刻記憶回路１２内の時刻有効フラグ更新回路１２１の動作を図１１のフロー図を用いて説明する。時刻有効フラグ更新回路１２１では、まずキュー毎の送信予定時刻３０、時刻有効フラグ３１、およびパケット有効フラグ３２をメモリ１２２から読出す（図１１ステップ５５）。読出した時刻有効フラグ３１＝０であるときは、既に送信予定時刻３０は無効なものと判断されているので、すべての情報を更新しない（図１１ステップ５６）。時刻有効フラグ３１＝１、かつ送信予定時刻３０が不確定領域９３にないときは、まだ送信予定時刻３０は有効であるので、この場合もすべての情報を更新しない（図１１ステップ５７）。
時刻有効フラグ３１＝１、送信予定時刻３０が不確定領域９３にあり、かつパケット有効フラグ３２＝１のときには、まだ送信待ちのパケットが存在しているので時刻有効フラグを０にしてはいけない。そこでこの場合は、送信予定時刻を過去領域内で現在時刻から最も離れた時刻（図９の９４）に更新して書き戻し、時刻有効フラグ、パケット有効フラグは共に１のまま更新しないでメモリ１２２に書き戻す（図１１ステップ５８−１、５９）。時刻有効フラグ３１＝１、送信予定時刻３０が不確定領域９３にあり、かつパケット有効フラグ３２＝０のときには、送信待ちパケットのパケットは存在していないので、送信予定時刻、パケット有効フラグは更新せずに書き戻し、時刻有効フラグを０に更新してメモリ１２２に書き戻す（図１１ステップ５８−２、５９）。

次に、時刻の更新のタイミングについて説明する。あるキューが不確定領域９３内で１回も更新されなかった場合、時刻有効フラグ＝１のまま送信予定時刻が未来領域に入ってしまうために、不確定領域８３を設けていない場合と同様に正しいシェーピングを行うことができなくなる。以上の理由により、不確定領域内にすべてのキューに対して上記の時刻有効フラグ更新動作を１回以上行う必要がある。これは、不確定領域の時間幅以下の周期で送信予定時刻の更新を行えば容易に実現できる。

図１では、各ユーザ毎に優先キュー１００、および非優先キュー１０１共に１つずつ存在する場合の例を示したが、各ユーザ毎に複数個の優先キュー、複数個の非優先キューを備えてもよい。キューの数が多くなれば、例えば同じ電子メールのトラヒックでもユーザＡの電子メールをユーザＢの電子メールよりも優先して転送するといった、より細かな優先制御を行うことができる。優先キューが複数個存在する場合には、保証帯域は複数の優先キューの送信帯域の合計になる様にリーキーバケットアルゴリズムのパラメータを設定しなければならない。また、非優先キューが複数個存在する場合には、各非優先キュー間の優先制御は、上位キューにパケットが存在すれば必ず優先される完全優先制御、あるいは設定した比率（例えば２：１）で上位キューと下位キューのパケットを送信する重み付き順廻優先制御（Weighted Round Robin）等を用いることができる。

以上に述べたシェーピング装置の実施例では、優先パケットに対しては最低保証帯域でシェーピングしているため、入力帯域の方が大きければ、キューが溢れてパケットが廃棄されることがある。これを防ぐために、キューが溢れそうな場合には最低保証帯域を守らずに最大限にパケットを送信する機能を付加してもよい。図１に示したシェーピング装置では、優先パケットを送信すると、帯域保証読出し時刻計算回路１３１の計算結果を次のパケットの送信予定時刻としていたが、このときに、優先キューのキュー長を参照し、キュー長によって選択条件を修正することで、上記機能を容易に実現することができる。すなわち、優先キューのキュー長が、予め設定しておいた閾値よりも小さい場合には、通常通り帯域保証読出し時刻計算回路１３１の計算結果を次のパケットの送信予定時刻とし、優先キューのキュー長が、前記閾値よりも大きい場合には、即出し時刻計算回路１３０の計算結果を次のパケットの送信予定時刻とする様に、選択回路１３２の条件を修正するだけでよい。保証帯域を超える帯域分の優先度情報は、低優先度で送信しておけば網側のＵＰＣで廃棄されることはない。

また、優先パケットの入力帯域が小さければ、高優先度で送信されるパケットの送信帯域が保証帯域を下回ることになり、課金の主な対象となることが多い保証帯域を有効利用することができない。この場合は、優先キューの送信予定時刻になっても優先キューに送信待ちパケットが存在しない場合には、パケット読出し回路１４は非優先キューからパケットを読出し、優先度情報付与回路１５では高優先度を付与する機能を付加することで保証帯域を有効利用することができる。

以上に説明したシェーピング部１を備えたパケット中継装置９８から公衆網９９−１に向けて送信されるパケットの様子を図１２に示す。図１２の上半分は送信されるパケットの時間間隔を示しており、横軸を時間軸としている。また、下半分には各時間の送信帯域の変化を示している。各ユーザは、常時、最低保証帯域と最大契約帯域の間の帯域でパケットを送信している（領域１）。同時にパケットを送信するユーザが増加し、送信帯域が小さくなっても最低保証帯域を下回ることはない（領域２）。また、同時にパケットを送信するユーザが減少すると、送信帯域を最大契約帯域まで増加させることができる（領域３）。いずれの場合も高優先度パケットは、他に送信しているユーザ数に依存せず、常に一定の帯域でパケットを送信することができ、低優先度パケットは通信路の帯域に余裕がある場合にのみ、その空き帯域で送信することができる。

第２の実施例として、ＡＴＭセルを用いたＧＦＲ用シェーピング装置について説明する。図１３にＧＦＲ用シェーピング装置をブロック図を示す。ＡＴＭセルは５３バイトの固定長パケットであり、１個以上のセルが集まって上位レイヤのパケットを構成するが、同一ＶＣ内の異なるパケットが混在すると受信端末側でパケットの区切りを識別できない。従って、セル読出し回路７４に同一上位パケットのセルを連続して読出し、送信する機能を備える。また、キューイング先判別回路７１は、受信ＡＴＭセルのヘッダ内のＶＰＩ、ＶＣＩ、ＣＬＰを参照して受信セルをキューイングするキューを決定する。上位パケットの最終セルの識別は、セルヘッダ内のぺイロードタイプ（３ビット）によって行うことができる。ペイロードタイプが、“０００”または“０１０”のときが先頭・中間セル、“００１”または“０１１”のときが最終セルである。それ以外の値はセルが管理用セル（ＯＡＭセル・ＲＭセル）であることを示している。

ＩＰパケットの送受信動作とは、以下の点が異なる。ＡＴＭ上位レイヤのパケットを受信すると、まずＳＡＲ（Segmentation And Reassembly）７８においてパケットを４８バイト毎に分割し、５バイトのＡＴＭヘッダを付加してＡＴＭセルを構成し、ＡＴＭセルはキューイング先判別回路７１に転送される。キューイング先判別回路７１が、上位パケットの先頭・中間セルを受けた場合には送信予定時刻、時刻有効フラグ、およびパケット有効フラグの更新は行なわず、上位パケットの最終セルを受信した場合にのみ送信予定時刻、時刻有効フラグおよびパケット有効フラグの更新を行う。最終セル受信時の処理はＩＰパケットの規則と同じである（図１４参照）。

次に、セル送信時の相違点を示す。帯域保証は上位パケットに対して行わなければならないので、上述の様に、上位パケットの先頭・中間セルを送信した場合は連続してセルを読出す必要がある。従って、この場合には、セルを送信したキューが優先キュー／非優先キューによらず、セル読出し回路７４は、送信予定時刻計算回路７３内の選択回路７３２において即出し時刻計算回路７３０の計算結果７３００が送信予定時刻として選択される様な指示７４００を出す。一方、上位パケットの最終セルを送信した場合には、ＩＰパケット送信時と同じ規則で送信予定時刻を選択する（図１４参照）。

以上の様に、本発明のＩＰパケット用シェーピング装置１の送信予定時刻計算回路内の選択回路の条件に、最終セルと先頭・中間セルによる条件を付加するだけで、容易にＧＦＲ用シェーピング装置を構成することができる。

本発明を適用したトラヒックシェーピング装置の一実施例の構成を示すブロック図である。 公衆網を介した企業ネットワークの接続図である。 パケット中継装置の一実施例の構成を示すブロック図である。 ＩＰパケットのフォーマットを示す図である。 送信予定時刻計算回路１３内の選択回路１３２の選択規則を示したテーブルである。 送信予定時刻記憶回路１２内のメモリ１２２の記憶フォーマットを示す図である。 送信予定時刻記憶回路１２の詳細ブロック図である。 有限ビット数のカウンタを用いて構成したシェーピング用時計の概念図である。 パケット受信時の送信予定時刻を決めるためのフロー図である。 パケット送信時の送信予定時刻を決めるためのフロー図である。 時刻優先フラグ更新のためのフロー図である。 シェーピング装置１の送信帯域と送信されるパケットの例を示した概念図である。 本発明を適用したＧＦＲ用トラヒックシェーピング装置の一実施例の構成を示すブロック図である。 送信予定時刻計算回路７３内の選択回路７３２の選択規則を示したテーブルである。

符号の説明

１，７… シェーピング装置、１０… パケットバッファ、１００，７００… 優先キュー、１０１，７０１… 非優先キュー、１１，７１… キューイング先判別回路、１２，７２… 送信予定時刻記憶回路、１３，７３… 送信予定時刻計算回路、１４… パケット読出し回路、１５，７５… 優先度情報付与回路、１６… 時計、１７，７７… ソーティング回路、７０… セルバッファ、７４… セル読出し回路、７８… ＳＡＲ。

Claims (16)

1. パケット転送網に接続されており、受信パケットのヘッダに記述してある宛先情報を参照して送信先を決定するパケット転送部と、接続されている回線の種別に対応した回線対応部を備えたパケット中継装置において、
   回線対応部内のトラヒックシェーピング部に、
   該回線対応部がパケット転送部から受信し保証帯域内で送信されるパケットが蓄積される出力相手先毎の優先キューと、
   該回線対応部がパケット転送部から受信し保証帯域外の帯域で送信されるパケットが蓄積される出力相手先毎の非優先キューと、
   該回線対応部がパケット転送部から受信したパケットのヘッダに記述してあるユーザ情報および優先度に関する情報を参照して優先度を判別し、出力相手先毎の優先キューか、非優先キューのいずれかにキューイングする機能を備えたキューイング先判別回路と、
   該キュー毎の送信待ち先頭パケットの送信予定時刻を計算する送信予定時刻計算回路と、
   送信予定時刻計算回路で計算された該キュー毎の送信予定時刻および最優先で送信すべきキューの送信予定時刻を記憶しておく送信予定時刻記憶回路と、
   前記送信予定時刻記憶回路に記憶されているキュー毎の送信予定時刻を参照して最優先で送信すべきキューを選び出すソーティング回路と、
   送信予定時刻記憶回路に記憶されている送信予定時刻に従ってキューからパケットを読出して該回線対応が接続されている回線に向けて送信するパケット読出し回路と、
   前記パケット読出し回路によって読出されたパケットのヘッダの優先度に関する情報を書込む優先度情報付与回路を備えたことを特徴とするパケット中継装置。
2. 請求項１記載のパケット中継装置において、
   請求項１記載の優先キューが同一出力相手先に対して複数個存在し、複数個のキューの間に優先順位を設け、送信待ちパケットが存在するキューの内、最も優先順位の高いキューからパケットを読出して送信することを特徴とするパケット中継装置。
3. 請求項１記載のパケット中継装置において、
   請求項１記載の非優先キューが同一出力相手先に対して複数個存在し、複数個のキューの間に優先順位を設け、送信待ちパケットが存在するキューの内、最も優先順位の高いキューからパケットを読出して送信することを特徴とするパケット中継装置。
4. 請求項１記載のパケット中継装置において、
   請求項１記載の請求項１記載の非優先キューが同一出力相手先に対して複数個存在し、複数個のキューの間に優先順位を設け、送信待ちパケットが存在するキューの内、最も優先順位の高いキューからパケットを読出して送信し、パケットを読出したキューの優先順位を最下位優先順位に修正することを特徴とするパケット中継装置。
5. 請求項１記載のパケット中継装置において、
   請求項１記載の送信予定時刻計算回路が、パケットを連続して読出すような送信予定時刻を計算する回路と、保証帯域を守るような送信予定時刻を計算する回路を備え、更に送信予定時刻として二つの計算結果のうちいずれかを選択するための選択回路を備えたことを特徴とするパケット中継装置。
6. 請求項５記載のパケット中継装置において、
   請求項５記載の選択回路が、請求項１記載の回線対応部がパケットを受信したときには、請求項６記載のパケットを連続して読出すような送信予定時刻計算回路の計算結果を選択し、
   請求項１記載の回線対応部が請求項１記載の優先キューからパケットを送信したときには、請求項６記載の保証帯域を守るような送信予定時刻を計算する回路の計算結果を選択し、
   請求項１記載の回線対応部が請求項１記載の非優先キューからパケットを送信したときには、請求項６記載のパケットを連続して読出すような送信予定時刻計算回路の計算結果を選択する機能を備えたことを特徴とするパケット中継装置。
7. 請求項６記載のパケット中継装置において、
   請求項１記載の優先キューに予め閾値を設定しておき、
   該キューに蓄積されているパケット数が前記閾値を超えていない場合には、請求項６記載の選択回路が保証帯域を守るような送信予定時刻を計算する回路の計算結果を選択し、
   該キューに蓄積されているパケット数が前記閾値を超えている場合には、請求項６記載の選択回路がパケットを連続して読出すような送信予定時刻を計算する回路の計算結果を選択することを特徴とするパケット中継装置。
8. 請求項１記載のパケット中継装置において、
   請求項１記載の優先度情報付与回路が、請求項１記載のパケット読出し回路が請求項１記載の優先キューからパケットを読出した場合には高優先度を示す優先度情報を読出したパケットのヘッダ部に書込み、
   請求項１記載のパケット読出し回路が請求項１記載の非優先キューからパケットを読出した場合には低優先度を示す優先度情報を読出したパケットのヘッダ部に書込むことを特徴とするパケット中継装置。
9. 請求項１記載のパケット中継装置において、
   請求項１記載の優先度情報付与回路が、請求項１記載の優先キューに対する送信予定時刻に該優先キューに送信待ちパケットが存在しないで非優先キューからパケットを送信するときに、高優先度を示す優先度情報を読出したパケットのヘッダ部に書込むことを特徴とするパケット中継装置。
10. 請求項８記載のパケット中継装置において、
    請求項８記載の優先度情報として、ＩＰパケットのヘッダ内のＴＯＳ領域の値を変化させることを特徴とするパケット中継装置。
11. 請求項８記載のパケット中継装置において、
    請求項８記載の優先度情報として、ＡＴＭセルのヘッダ内のＣＬＰビットの値を変化させることを特徴とするパケット中継装置。
12. ユーザ毎に高優先度パケットを蓄積するためのキュー（以下、優先キュー）と低優先度パケットを蓄積するためのキュー（以下、非優先キュー）を有するシェーピング部を備えるパケット中継装置。
13. 請求項１２において、優先キューに蓄積されている送信待ちパケットの先頭パケットの送信予定時刻を保証帯域を守る様に設定し、非優先キューに蓄積されている送信待ちパケットの先頭パケットの送信予定時刻をすぐに送信される時刻に設定し、優先キュー／非優先キューを含めた送信帯域（最大契約帯域）に対応する送信予定時刻を設定するための送信予定時刻計算回路をさらに備えるパケット中継装置。
14. 請求項１３において、優先キューから読出されたパケットには高優先度を与え、非優先キューから読出されたパケットには低優先度を与える優先度情報付与回路をさらに備えるパケット中継装置。
15. 請求項１４において、上記送信予定時刻計算回路は、優先キューの送信予定時刻を計算する際に、優先キューのキュー長（蓄積パケット数）を参照し、一定量以上のパケットが蓄積されている場合には保証帯域を守らずにすぐに送信される時刻を送信予定時刻として設定するパケット中継装置。
16. 優先キューからパケットを送信すべき時刻になっているのに関わらず優先キューに送信待ちパケットがない場合に、読出された非優先キューの送信待ちパケットに対して高優先度を与えるパケット優先度設定方法。

Images