(57)【特許請求の範囲】
【請求項１】
到着するセルを一時的に蓄積するセルバッファ部と、セル送出予定時刻を演算するセル送出予定時刻演算部と、セルを送出する送出制御部とを備えたトラフィックシェーピング装置において、
前記セル送出予定時刻演算部で求められたセル送出予定時刻を用いてソーティング処理を行い、前記セルバッファ部内のセルのうち送出予定時刻の最も早いセルを決定するソーティング部を備えたことを特徴とするトラフィックシェーピング装置。
【請求項２】
前記ソーティング部は、セル送出予定時刻を二進木構造に管理する手段を備え、過去のソート結果を利用した処理を行うことを特徴とする請求項１記載のトラフィックシェーピング装置。
【請求項３】
前記ソーティング部は、セルの送出予定時刻と共にコネクションの優先順位とを比較し、送出予定時刻が最も早く、かつ、優先順位の最も高いセルを次に送出すべきセルとして選択する機能を備えることを特徴とする請求項１または２記載のトラフィックシェーピング装置。
【請求項４】
前記セル送出予定時刻演算部は、リーキーバケットカウンタを有し、対向装置のリーキーバケット方式のＵＰＣによりセルが廃棄されない最適なセル送出予定時刻を演算することを特徴とする請求項１、２または３記載のトラフィックシェーピング装置。
【請求項５】
次段の装置からのセル送出抑制信号を受け取る手段を有し、セル送出抑制信号が入力されていない期間にのみセルの送出を行わせる機能を有することを特徴とする請求項１ないし４のうち１記載のトラフィックシェーピング装置。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、トラフィックシェーピング装置に係り、特に、非同期転送モード（ＡＴＭ）によるディジタル通信におけるセル流の制御のために使用して好適なトラフィックシェーピング装置に関する。
【０００２】
【従来の技術】
一般に、ＡＴＭ通信網は、１つの中継点に一時的に多数のセルが集中的に到着すると、通信網の円滑な運用が困難になるという性質を有している。このため、ＡＴＭ通信網においては、網側に、端末からのセル流量を監視し、違反セルの抽出、廃棄を実施する  Ｕｓａｇｅ  Ｐａｒａｍｅｔｅｒ  Ｃｏｎｔｒｏｌ（ＵＰＣ）機能を備えている。これに対して、端末側において、加入者が契約時に申告した契約帯域の値を守っていても、伝送路を通過中に生じるセル流の乱れにより伝送路にバースト性をはらむことになる。このバースト的に発生したセルの発生間隔を制御するシェーピング技術がある。
【０００３】
このシェーピング方式に関する従来技術として、例えば、特開平０６−３１５０３４号公報等に記載された技術が知られている。この従来技術は、セルの送出時刻を演算する送出時刻制御部と、セルを格納するメモリと、このメモリからセルを伝送路に読み出す読出制御部とにより構成され、メモリにセルを一時蓄積することによりセルの送出時間間隔を等間隔に制御することを可能にして、セルの到着時間間隔のゆらぎを吸収するというものである。
【０００４】
【発明が解決しようとする課題】
ＡＴＭ広域網は、伝送帯域等の限られた網内資源を有効に活用するために、加入者毎に使用可能な帯域を契約し、網側装置がＵＰＣ機能により、加入者が契約帯域を守っているかどうかを監視し、違反セルを廃棄している。これに対し、ＡＴＭ  ＬＡＮ等の構内網は、帯域に余裕を持たせた設計とし、網としてのＵＰＣ機能を持たず、端末装置にもシェーピング機能を不要とすることにより装置価格を低減させているのが一般的である。
【０００５】
このような構内網に適用されるＡＴＭ交換機あるいはＡＴＭ多重化装置をＡＴＭ広域網に接続する場合、構内網のバースト性の高いセル流をそのまま広域網に送信すると広域網のＵＰＣ機能によってセル廃棄が行われるために実用上通信ができないという問題が生じる。
【０００６】
そして、このような問題点を解決するために前述した公報に記載の従来技術が用いられるが、この従来技術は、送出予定時刻に対応するメモリアドレスにセルを書き込むため、予め、可能な送出時刻全てに相当するメモリ容量を用意しておく必要があるが、高速の伝送路上で低速のコネクションのシェーピングを行う場合に、セル間隔が極めて長くなるため、用意すべきメモリ量が膨大となるという問題を有している。例えば、１５５Ｍｂｐｓの伝送路上で、６４ｋｂｐｓのコネクションのシェーピングを行おうとすると、セルの送出間隔が２４００セル以上となるため、Ｎセルのバースト到着に耐えるためには２４００×Ｎ以上のセル送出予定時刻に対応するメモリアドレスが必要であった。
【０００７】
本発明の目的は、前記従来技術の問題点を解決し、構内網のバースト性の高いセル流を効率的にシェーピングすることができ、ＡＴＭ交換機あるいはＡＴＭ多重化装置に適用して好適なトラフィックシェーピング装置を提供することにある。
【０００８】
【課題を解決するための手段】
本発明によれば前記目的は、到着するセルを一時的に蓄積するセルバッファ部と、セル送出予定時刻を演算するセル送出予定時刻演算部と、セルを送出する送出制御部とを備えたトラフィックシェーピング装置において、前記セル送出予定時刻演算部で求められたセル送出予定時刻を用いてソーティング処理を行い、前記セルバッファ部内のセルのうち送出予定時刻の最も早いセルを決定するソーティング部を備えたことにより達成される。
【０００９】
また、前記目的は、前記ソーティング部に、セル送出予定時刻を二進木構造に管理する手段を備え、過去のソート結果を利用した処理を行わせることにより、また、セルの送出予定時刻と共にコネクションの優先順位とを比較し、送出予定時刻が最も早く、かつ、優先順位の最も高いセルを次に送出すべきセルとして選択する機能を備えることにより達成される。
【００１０】
さらに、前記目的は、前記セル送出予定時刻演算部に、リーキーバケットカウンタを備え、対向装置のリーキーバケット方式のＵＰＣによりセルが廃棄されない最適なセル送出予定時刻を演算させることにより達成される。
【００１１】
また、前記目的は、次段の装置からのセル送出抑制信号を受け取る手段をさらに備え、セル送出抑制信号が入力されていない期間にのみセルの送出を行わせるようにすることにより達成される。
【００１２】
本発明の第１の特徴は、既に到着しているセルのうちの最も早く送出すべきセルを選択するソーティング部を備えることにある。これにより、シェーピングの対象とするコネクション毎のセルバッファ内の先頭のセルのソーティングを行えばよく、コネクション数分のソーティングを行うのに必要なメモリだけを用意すればよく、メモリ容量を低減することができる。
【００１３】
また、本発明の第２の特徴は、ソーティング部においてセル送出予定時刻を二進木構造に管理し、前回のソーティング時の情報を活用するようにしている点にある。これにより、ソーティングに必要な処理時間及びメモリ量をさらに低減することができる。また、ソーティング部は、送出側の１セル時間以内に次に送信すべきセルを決定する必要があるが、送信する帯域が大きいと極めて高速の動作が必要となる。この本発明の第２の特徴によれば、このような場合にも、所要メモリ量および処理時間を抑えることができる。
【００１４】
また、本発明の第３の特徴は、コネクション毎に優先順位を設け、ソーティング部がセルの送出予定時刻と前記優先順位の両者を勘案して最適なセルを次の送信セルとして選択する機能を備えている点にある。ＡＴＭスイッチは、ＬＡＮのデータのようにバースト性が高く遅延がある程度許容できるトラフィックによって音声データのような遅延の許容できないトラフィックが悪影響を受けないようにする目的で、優先制御を行うことが一般的である。しかし、スイッチで優先制御を行っても、回線への送信時にシェーピングを行った結果、ＬＡＮのデータの送出予定時刻と音声データの送出予定時刻とが同一となった場合にも優先制御を行わなければ音声データの遅延が増大するという問題が生じうる。本発明の第３の特徴によれば、このように送出予定時刻が同一となった場合にも音声データを優先的に送出するように優先順位付けを行うことができる。
【００１５】
本発明の第４の特徴は、リーキーバケット方式ＵＰＣによりセルが廃棄されない最適なセル送信予定時刻を演算する機能を備えた点にある。従来技術では、セルの送信時間間隔がある一定の時間間隔以上となることを保証するようにシェーピングするのが一般的である。このとき、セル間隔のゆらぎの最大値がτであるような入力セル流をシェーピングすると、シェーピング後の出力セル流は、入力セル流に対してτだけ遅延することになる。本発明の第４の特徴によれば、網側のＵＰＣで許容される範囲内で入力セル流のゆらぎを残すことによって、シェーピング後の出力セル流の遅延時間を減らすことができる。
【００１６】
本発明の第５の特徴は、次段装置からのセル送出抑制信号を受け取る手段を備えた点にある。例えば、複数の低速回線に送信するセルのシェーピングを行う場合、トラフィックシェーピング装置にてシェーピングを行った後、次段に分離装置を置き、複数の低速回線に出力する構成が考えられる。この場合、分離装置の出力セル流について正しくセル流がシェーピングされるように制御する必要があるが、分離装置から回線に出力されるまでの間にセル間隔にゆらぎが生じる可能性のある場合や、出力回線毎に速度が異なる場合には制御が困難である。本発明の第５の特徴によれば、分離装置がセルを送信したタイミングに従ってセル送出抑制信号を解除するように制御することによって、このような場合にも正しくシェーピングすることができる。
【００１７】
本発明では、到着したセルの送出予定時刻は、当該コネクションの直前のセルが既に送出済であればセルの到着時に決定し、直前のセルがまだ送出されていなければその送出時点で決定される。すなわち、セルの送出予定時刻の管理用のメモリは最大コネクション数の分だけ用意しておけばよい。
【００１８】
【発明の実施の形態】
以下、本発明によるトラフィックシェーピング装置の一実施形態を図面により詳細に説明する。
【００１９】
図１は本発明の一実施形態によるトラフィックシェーピング装置の構成を示すブロック図、図２、図３は本発明の一実施形態によるトラフィックシェーピング装置の適用例を説明する図、図４はセル送出予定時刻を二進木構造に管理するソーティング用二進木の更新例を説明する図である。図１〜図３において、１０はトラフィックシェーピング装置、１１はセルバッファ部、１２は送出予定時刻演算部、１３はソーティング部、１４は送出制御部、１００〜１０２は端末装置、１０３〜１０５、１０７は回線インタフェース部、１０６はＡＴＭスイッチ部、１０８はＡＴＭ広域網、１０９はＡＴＭ交換機、１１０は分離装置、１１１〜１１３は回線終端部である。
【００２０】
本発明の一実施形態によるトラフィックシェーピング装置１０は、図１に示すように、セルバッファ部１１、送出予定時刻演算部１２、ソーティング部１３、及び送出制御部１４を備えて構成されている。
【００２１】
図示トラフィックシェーピング装置１０に到着したセルは、一時的にセルバッファ部１１に格納され、シェーピングの対象であるコネクション（ＶＰコネクション、ＶＣコネクション、あるいは、それらの集合）毎の待ち行列に管理される。
【００２２】
空の（待ち行列内にセルが１つもない）待ち行列にセルが到着した場合、及び、送出制御部１４からセルが１つ送出された場合のいずれかの場合、到着したセルあるいは送出されたセルの属するシェーピング対象コネクションについて、セルバッファ部１１内の該当コネクションの待ち行列の先頭のセルの送出予定時刻が、送出予定時刻演算部１２により所定の計算式に従って演算される。ソーティング部１３は、演算の結果求められた送出予定時刻を用いてソーティング処理を行い、セルバッファ部１１内のセルのうち最も早く送出すべきセル及びその送出予定時刻を決定する。
【００２３】
送出制御部１４は、ソーティング部１３で決定された送出予定セルの送出予定時刻と現在時刻とを常時監視比較し、現在時刻が送出予定時刻に達し、かつ、セル送出抑制信号を受信していなければセルバッファ部１１から該当セルを取り出して送出するとともに、次のセルの送出予定時刻を演算するように送出予定時刻演算部１２に通知する。
【００２４】
前述した本発明の一実施形態によるトラフィックシェーピング装置は、優先制御機能が追加されている場合、ソーティング部１３に、ソート結果がでた時点で緊急用セルや音声データのような優先順位の高いセルがあるか否かを判定させる。そして、ソーティング部１３は、優先順位の高いセルがある場合、ソート結果で得られたセルよりも先に優先順位の高いセルを送出するように送出制御部１４に指示する。また、該当するセルがない場合、ソーティング部１３は、送出制御部１４に該当コネクションＮｏ．の送出を指示する。
【００２５】
さらに、前述した本発明の一実施形態によるトラフィックシェーピング装置は、セル送出信号を受け取る回路が追加されている場合、セル送出抑制信号を受信するまでの間、送出制御部１４にセルの送出を抑制する信号を出し、送出制御部１４はセル送出を止める。
【００２６】
前述した構成を有するトラフィックシェーピング装置１０の適用例を示す図２において、ＡＴＭ交換機１０９は、端末装置１００〜１０２に対する回線インタフェース部１０３〜１０５と、ＡＴＭスイッチ部１０６と、ＡＴＭスイッチ部１０６とＡＴＭ広域網１０８との間に位置する回線インタフェース部１０７とにより構成される。
【００２７】
そして、前述したトラフィックシェーピング装置１０は、回線インタフェース部１０７のＡＴＭ広域網への送信部に適用され、ＡＴＭ広域網１０８のＵＰＣ機能によりセルが廃棄されないようにセルの送出間隔を制御している。
【００２８】
前述した構成を有するトラフィックシェーピング装置１０の他の適用例が図３に示されている。
【００２９】
図３に示す例は、複数の低速回線に送信するセルのシェーピングを行う場合の例であり、多重化されているセルに対して、トラフィックシェーピング装置１０によりシェーピングを行った後、次段に分離装置１１０を置き、複数の低速回線の回線終端１１１〜１１３にセルを出力するようにしたものである。
【００３０】
この場合、分離装置１１０の出力セル流について正しくセル流がシェーピングされるように制御する必要があるが、分離装置から低速回線に出力されるまでの間にセル間隔にゆらぎが生じる可能性のある場合や、出力回線毎に速度が異なる場合には、制御が難しくなるが、分離装置１１０がセルを送信したタイミングに従って、トラフィックシェーピング装置１０に対するセル送出抑制信号を解除するように制御することにより、前述の場合にも正しくシェーピングを行うことができる。
【００３１】
次に、セル送出予定時刻を二進木構造に管理するソーティング用二進木の更新例を図４を参照して説明する。
【００３２】
セル送出予定時刻を二進木構造に管理するため、セルの送信あるいは到着の結果、新たにセルの送出予定時刻が決定された場合、該当コネクションから始めて前回のソーティング結果の二進木を根の方向にたどりつつ送出予定時刻及び優先順位に従って比較を繰り返すことにより、次に最も早く送出すべきセル及び送出予定時刻を求めることができる。すなわち、図４に示す例で、例えば、コネクション３の送出予定時刻更新時には、図の網掛けの情報のみについて、隣合うコネクションの送出時刻の情報を比較して更新していけばよい。
【００３３】
前述の処理のための処理時間の大半は、二進木を格納したメモリへのアクセス時間であり、ｌｏｇ２（コネクション数）のオーダの時間で処理することができる。また、この処理のために必要なメモリ量は、二進木の格納用のメモリであり、コネクション数の２倍のオーダの量となり、既存技術の場合に比較して大きく低減することができる。
【００３４】
さらに、コネクションの優先順位情報もセル送出予定時刻と共に比較することにより、ソーティング部１３ににより同時刻に出力すべきコネクションが複数あった場合に、より優先順位の高いものを早く出力するように選択することができる。
【００３５】
また、リーキーバケット方式のＵＰＣでは、現在のカウンタ値をＣ、前回のセル到着時のカウンタ値をｃ、セル到着による増分をｉ、単位時間経過時の減算値をｄ、スレッショルドをＮ、前回のセル到着からの経過時間をｔとすると、
Ｃ＋ｉ＞Ｎ
となった場合に違反セルと判定される。Ｃ  ＝  ｍａｘ  ｛  ０，  ｃ−ｄｔ  ｝  であるので、前記式は、
ｍａｘ｛  ０，  ｃ−ｄｔ＋ｉ｝＞Ｎとなる。
【００３６】
言い換えれば、
ｔ≧  ｍａｘ｛０，ｃ＋ｉ−Ｎ｝／ｄ        ………（１）
であれば違反セルと判定されない。そこで、セル送出予定時刻演算部１２は、式（１）を満足する最小のセル間隔ｔを求めることにより、リーキーバケットＵＰＣによりセルが廃棄されることのない最適なセル送出予定時刻を求めることができる。
【００３７】
また、ソーティング部１３により決定された次のセル送出予定時刻をＴとすると、送出制御部１４は、
｛（現在時刻）≧Ｔ｝、かつ、（次段からのセル送出抑制信号を受信していない）という条件を常時監視し、条件成立時のみセルを送出することによって、次段装置の出力でのシェーピング機能を実現することができる。
【００３８】
【発明の効果】
以上説明したように本発明によれば、メモリ等の外部装置を削減し、送出時刻の最も早いセルを次に送出すべきセルとして選択することができるトラフィックシェーピング装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態によるトラフィックシェーピング装置の構成を示すブロック図である。
【図２】本発明の一実施形態によるトラフィックシェーピング装置の適用例を説明する図である。
【図３】本発明の一実施形態によるトラフィックシェーピング装置の他の適用例を説明する図である。
【図４】セル送出予定時刻を二進木構造に管理するソーティング用二進木の更新例を説明する図である。
【符号の説明】
１０  トラフィックシェーピング装置
１１  セルバッファ部
１２  送出予定時刻演算部
１３  ソーティング部
１４  送出制御部
１００〜１０２  端末装置
１０３〜１０５、１０７  回線インタフェース部
１０６  ＡＴＭスイッチ部
１０８  ＡＴＭ広域網
１０９  ＡＴＭ交換機
１１０  分離装置
１１１〜１１３  回線終端部
【図１】
0003589260.tif 000002
【図２】
0003589260.tif 000003
【図３】
0003589260.tif 000004
【図４】
0003589260.tif 000005