(57)【要約】【課題】データ伝送性能の低下を防止できる伝送装置等を提供する。【解決手段】伝送装置は、ユーザフロー毎に出力キューを有し、入力したパケットを、当該パケットが属するユーザフローに対応した出力キューに格納するバッファを有する。伝送装置は、各ユーザフローの出力順序を示すリンクリストを記憶したリストテーブルを有する。伝送装置は、リンクリスト内の先頭エントリを参照してユーザフローに対応した出力キューにクレジットを発行する発行部を有する。伝送装置は、クレジットが発行された出力キューからパケットをパケット単位で出力する出力制御部を有する。【選択図】図３
2015091061.tif 000002
【特許請求の範囲】
【請求項１】
ユーザフロー毎にキューを有し、入力したデータを、当該データが属するユーザフローに対応した前記キューに格納するバッファと、
前記ユーザフローの出力順序を示すリンクリストを記憶した記憶部と、
前記リンクリストを参照して前記ユーザフローに対応した前記キューに所定の出力許可量を発行する発行部と、
前記出力許可量が発行された前記キューからデータをデータ単位で出力する出力制御部と
を有することを特徴とする伝送装置。
【請求項２】
前記キューからデータを出力した場合に、当該キューのユーザフローに対応した前記出力許可量から当該データの出力量を減算することで、当該ユーザフローに対応した現在許可量を算出する算出部
を有し、
前記出力制御部は、
前記ユーザフローに対応した前記現在許可量が正の場合に、当該ユーザフローに対応した前記キューからデータをデータ単位で出力することを特徴とする請求項１に記載の伝送装置。
【請求項３】
前記発行部は、
少なくとも、前記キュー選択の処理に要する時間よりも大の時間をデータ換算した前記出力許可量を発行することを特徴とする請求項１又は２に記載の伝送装置。
【請求項４】
前記出力制御部は、
前記ユーザフローに対応した前記現在許可量が正でない場合に、当該ユーザフローに対応した前記キューからのデータ出力を停止することを特徴とする請求項１〜３の何れか一つに記載の伝送装置。
【請求項５】
第１のタイミングを検出すると、対象データが属する対象ユーザフローに対応したエントリが当該対象ユーザフローに対応した一時記憶部内に記憶済みであるか否かを判定する判定部と、
前記対象ユーザフローのエントリが前記一時記憶部に記憶済みの場合に、前記対象ユーザフローのエントリの当該一時記憶部への記憶を禁止すると共に、前記対象ユーザフローのエントリが前記一時記憶部に記憶済みでない場合に、前記対象ユーザフローのエントリを当該一時記憶部に記憶する記憶制御部と、
第２のタイミングを検出すると、前記一時記憶部に記憶中のエントリを前記リンクリストに追加するリスト操作を実行する実行部と
を有することを特徴とする請求項１〜４の何れか一つに記載の伝送装置。
【請求項６】
前記実行部は、
前記リンクリスト内の連続するエントリに境界を設定可能にし、前記境界で区分するエントリの区間をデータ出力の優先度に設定することを特徴とする請求項５に記載の伝送装置。
【請求項７】
前記リンクリストは、
前記エントリ毎に、当該エントリの識別情報と、当該エントリの前後のエントリの識別情報とを対応付けて管理することを特徴とする請求項５又は６に記載の伝送装置。
【請求項８】
前記データの入力に応じて当該データが属するユーザフロー毎にデータ量を加算することで現在キュー長を算出すると共に、当該ユーザフローに対応した前記出力許可量の発行に応じて前記現在キュー長から前記出力許可量を減算することで現在キュー長を算出するキュー長算出部を有し、
前記判定部は、
前記ユーザフロー対応の前記現在キュー長が正で、かつ、当該ユーザフロー対応の回線帯域が正常状態の場合に、前記第１のタイミングを検出することを特徴とする請求項５〜７の何れか一つに記載の伝送装置。
【請求項９】
前記実行部は、
前記記憶部内に前記エントリがあり、かつ、前記実行部側で処理が可能な状態の場合に、前記第２のタイミングを検出することを特徴とする請求項５〜８の何れか一つに記載の伝送装置。
【請求項１０】
ユーザフロー毎にキューを有し、入力したデータを、当該データが属するユーザフローに対応した前記キューに格納し、
前記ユーザフローの出力順序を示すリンクリストを参照して前記ユーザフローに対応した前記キューに所定の出力許可量を発行し、
前記出力許可量が発行された前記キューからデータをデータ単位で出力する
処理を実行することを特徴とする伝送方法。
【請求項１１】
ユーザフロー毎にキューを有し、入力したデータを、当該データが属するユーザフローに対応した前記キューに格納し、
前記ユーザフローの出力順序を示すリンクリストを参照して前記ユーザフローに対応した前記キューに所定の出力許可量を発行し、
前記出力許可量が発行された前記キューからデータをデータ単位で出力する
処理を伝送装置に実行させることを特徴とする伝送プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、伝送装置、伝送方法及び伝送プログラムに関する。
【背景技術】
【０００２】
近年、伝送システムでは、例えば、スマートフォン等の普及やインターネットを用いたサービスの多様化に伴って、局に集約するユーザ数や、通信するデータ量が増加傾向にある。伝送システムに使用する伝送装置では、例えば、データ遅延が許されない音声や、データ遅延がある程度許されるメール等の各種データを同時に処理するため、データ種別に応じて優先度を識別し、その優先度に応じてデータ処理を実行する。
【０００３】
例えば、伝送装置は、多くのユーザを収容し、かつ、可変長のパケットに対してデータの優先度を識別しながら、キュー選択の高速スケジューリングを実現している。このような高速スケジューリング方式としては、例えば、パケット単位でのＲＲ（Round  Robin）方式が採用されている。
【０００４】
しかしながら、ＲＲ方式等のパケット単位でキュー選択する方式では、パケットの処理時間よりも長くキューの選択に時間がかかると、選択キューからの出力パケット間に隙間が生じて、パケットを効率良く伝送出力するパケット伝送性能が低下する。そこで、パケット単位でキューを選択する方式では、複数のパケットの内、最短パケットの処理時間内でキュー選択する仕組みにしている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−３００５７７号公報
【特許文献２】特開平１１−２９８５２３号公報
【特許文献３】特開２００９−１３５８１０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＲＲ方式等のパケット単位でキュー選択する方式では、ユーザフロー数が増えると、キュー選択に要する処理負担も大きく、キューの選択に時間がかかる。その結果、パケットの処理時間よりも長くキューの選択に時間がかかり、パケット間に隙間が生じて、パケット伝送性能が低下する。
【０００７】
しかも、パケット単位でキュー選択する方式では、回線の高速化で回線帯域が広くなるに連れて単位時間当たりに処理するデータ量が増えるものの、１パケットの処理時間は短くなる。従って、パケット伝送性能の低下を防止するために、１パケットの処理時間を短くするに連れて、そのキュー選択に要する処理時間も短くすることが求められている。
【０００８】
パケット単位でキュー選択する方式において、例えば、回線帯域が１０Ｇｂｐｓを実現するためには、１５０ＭＨｚのクロックで８クロック相当の処理時間内にキューを選択する。また、例えば、回線帯域が４０Ｇｂｐｓを実現するためには、１５０ＭＨｚのクロックで２クロック相当の処理時間内にキューを選択する。更に、例えば、回線帯域が１００Ｇｂｐｓを実現するためには、１５０ＭＨｚのクロックで１クロック相当の処理時間内にキュー選択する。つまり、パケット単位でキュー選択する方式において、キュー選択に要する処理時間は、回線帯域が広くなるに連れて短くなるため、パケット単位での高速スケジューリングには限界がある。従って、回線帯域が広くなるに連れてパケット伝送性能の低下が生じているのが実情である。
【０００９】
一つの側面では、データ伝送性能の低下を防止できる伝送装置等を提供することを目的とする。
【課題を解決するための手段】
【００１０】
一つの案では、ユーザフロー毎にキューを有し、入力したデータを、当該データが属するユーザフローに対応した前記キューに格納するバッファを有する。案では、前記ユーザフローの出力順序を示すリンクリストを記憶した記憶部を有する。更に、案では、前記リンクリストを参照して前記ユーザフローに対応した前記キューに所定の出力許可量を発行する発行部を有する。更に、案では、前記出力許可量が発行されたキューからデータをデータ単位で出力する出力制御部を有する。
【発明の効果】
【００１１】
データ伝送性能の低下を防止できる。
【図面の簡単な説明】
【００１２】
【図１】図１は、本実施例の伝送システムの一例を示す説明図である。
【図２】図２は、伝送装置の一例を示すブロック図である。
【図３】図３は、スケジュール管理部及びバッファ管理部の一例を示すブロック図である。
【図４】図４は、リンクリストのエントリ構成の一例を示す説明図である。
【図５】図５は、リンクリストの一例を示す説明図である。
【図６】図６は、優先度を設定したリンクリストの一例を示す説明図である。
【図７】図７は、１００Ｇｂｐｓの回線帯域の１５０ＭＨｚのクロックと発行クレジット量との関係の一例を示す説明図である。
【図８】図８は、短パケット出力時のスケジュール管理部及びバッファ管理部の動作の一例を示す説明図である。
【図９】図９は、短パケット出力時のスケジュール管理部及びバッファ管理部の動作の一例を示す説明図である。
【図１０】図１０は、長パケット出力時のスケジュール管理部及びバッファ管理部の動作の一例を示す説明図である。
【図１１】図１１は、長パケット出力時のスケジュール管理部及びバッファ管理部の動作の一例を示す説明図である。
【図１２】図１２は、エントリ格納処理に関わる追加制御部の処理動作の一例を示すフローチャートである。
【図１３】図１３は、エントリ読出処理に関わる追加制御部の処理動作の一例を示すフローチャートである。
【図１４】図１４は、リスト操作処理に関わるリスト操作部の処理動作の一例を示すフローチャートである。
【図１５】図１５は、並び替えのリスト操作に関わるリンクリスト内のエントリの変更推移の一例を示す説明図である。
【図１６】図１６は、第１のパケット出力処理に関わる出力制御部の処理動作の一例を示すフローチャートである。
【図１７】図１７は、第２のパケット出力処理に関わる出力制御部の処理動作の一例を示すフローチャートである。
【図１８】図１８は、キュー階層構造の一例を示す説明図である。
【図１９】図１９は、キュー階層構造上の全体リンクリストの参照動作の一例を示す説明図である。
【図２０】図２０は、キュー階層構造の一例を示す説明図である。
【図２１】図２１は、伝送プログラムを実行する伝送装置を示す説明図である。
【発明を実施するための形態】
【００１３】
以下、図面に基づいて、本願の開示する伝送装置、伝送方法及び伝送プログラムの実施例を詳細に説明する。尚、本実施例により、開示技術が限定されるものではない。
【実施例】
【００１４】
図１は、本実施例の伝送システムの一例を示す説明図である。図１に示す伝送システム１は、複数の端末装置２と、複数の伝送装置３とを有する。端末装置２と伝送装置３との間や伝送装置３間は、例えば、光ファイバ４等の物理回線で通信接続するものとする。端末装置２は、例えば、パーソナルコンピュータ等の通信端末装置である。また、端末装置２は、例えば、スマートフォン、タブレット端末や携帯電話機等の無線端末である。伝送装置３は、例えば、端末装置２から収集した音声やメール等の各種データを格納したパケットを他の伝送装置３や他の端末装置２に伝送する伝送装置である。尚、伝送装置３は、例えば、端末装置２が無線端末の場合に、無線端末を無線接続して収容する基地局等である。
【００１５】
図２は、伝送装置３の一例を示すブロック図である。図２に示す伝送装置３は、複数の入力ポート１１と、複数の出力ポート１２と、パケット処理部１３と、トラフィック管理部１４とを有する。入力ポート１１は、光ファイバ４と物理的に接続し、例えば、光ファイバ４から光信号を入力し、入力した光信号をパケット単位のビット列に変換する光電変換機能を備えた入力インタフェースである。出力ポート１２は、例えば、光ファイバ４と物理的に接続し、パケット単位のビット列を光信号に変換する光電変換機能を備え、変換された光信号を光ファイバ４に出力する出力インタフェースである。パケット処理部１３は、ビット列のパケット内のヘッダ情報を解析し、その解析結果に基づき、伝送経路の選択やパケットの廃棄判定等の各種パケット処理を実行する、例えば、ＮＰＵ（Network  Processing  Unit）等で実現する。
【００１６】
トラフィック管理部１４は、バッファリング機能と、優先制御機能と、帯域制御機能と、出力キュー選択機能等とを有する。バッファリング機能は、入力パケットのパケット情報にあるフローＩＤからユーザフローを識別し、入力パケットが属するユーザフロー毎にバッファ内に出力キューを生成し、出力キュー内に入力パケットを格納する機能である。尚、ユーザフローとは、例えば、特定ユーザから他の特定ユーザへのデータの流れである。優先制御機能は、ユーザフローの優先度に応じてパケットの出力タイミングを決定する機能である。尚、優先度は、データのクラス情報やトークン状態等に応じたユーザフローの出力優先度である。帯域制御機能は、例えば、トークンバケット方式やリーキーバケット方式等を用いてユーザフロー毎の回線帯域を管理する機能である。出力キュー選択機能は、複数の出力キューの内、対応する出力キューを選択し、選択した出力キュー内のパケットを出力ポート１２から出力する機能である。尚、トラフィック管理部１４は、例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）や、ＦＰＧＡ（Field-Programmable  Gate  Array）等で実現する。
【００１７】
トラフィック管理部１４は、スケジュール管理部２０と、バッファ管理部３０とを有する。バッファ管理部３０は、入力パケットが属するユーザフロー毎に出力キューをバッファ内に生成し、当該ユーザフローに対応した出力キューに入力パケットを格納する、例えば、バッファリング機能を司るものである。スケジュール管理部２０は、複数の出力キューの内、対応する出力キューを効率良く、かつ、高速に決定する、例えば、優先制御機能、帯域制御機能や出力キュー選択機能等を司るものである。
【００１８】
図３は、スケジュール管理部２０及びバッファ管理部３０の一例を示すブロック図である。図３に示すバッファ管理部３０は、ＥｎＱ部３１と、バッファ３２と、出力制御部３３とを有する。ＥｎＱ部３１は、入力ポート１１を通じてパケットを入力する。バッファ３２は、ＥｎＱ部３１から入力パケットを検出すると、入力パケットが属するユーザフローに対応した出力キュー３２Ａに入力パケットを格納する。尚、バッファ３２は、新規のユーザフローに属する入力パケットを検出すると、新規のユーザフローに対応した出力キュー３２Ａを生成する。つまり、バッファ３２は、ユーザフロー毎に出力キュー３２Ａを有する。更に、ＥｎＱ部３１は、入力パケットを検出すると、入力パケットの入力パケット長及び入力パケットのユーザフローを識別するフロー番号をパケット情報としてスケジュール管理部２０に通知する。
【００１９】
出力制御部３３は、複数の出力キュー３２Ａの内、ユーザフロー単位で出力キュー３２Ａを選択し、選択された出力キュー３２Ａ内のパケットをパケット単位で出力する。また、出力制御部３３は、ユーザフローに属するパケットを格納した出力キュー３２Ａ毎に、出力キュー３２Ａから出力可能なクレジット量をカウントするクレジットカウンタ３３Ａを生成する。尚、クレジット量は、少なくとも出力キュー３２Ａの選択の処理に要する時間よりも大の時間をデータ換算したデータ量等の出力許可量である。クレジットカウンタ３３Ａは、出力キュー３２Ａ内のパケットを出力した場合に、現在クレジット量から出力パケット長を減算することで現在クレジット量を更新する、例えば算出部である。クレジットカウンタ３３Ａは、スケジュール管理部２０が発行した発行クレジット量を現在クレジット量に加算することで現在クレジット量を更新する。
【００２０】
スケジュール管理部２０は、追加制御部２１と、リスト管理部２２と、全体管理部２３とを有する。追加制御部２１は、ＥｎＱ部３１から得た入力パケットのパケット情報に基づき、図５に示すリンクリスト４０を構成するエントリ４１を取得する処理部である。リンクリスト４０は、フロー番号で識別するユーザフローの出力順序を示す配列リストである。リンクリスト４０は、フロー番号を識別するエントリ４１を出力順に数珠繋ぎにして配列している。全体管理部２３は、追加制御部２１及びリスト管理部２２を管理している。
【００２１】
追加制御部２１は、フロー管理部２１１と、要求判定部２１２とを有する。フロー管理部２１１は、現在キュー長を管理するキュー長カウンタ２１１Ａをユーザフロー毎に生成する。キュー長カウンタ２１１Ａは、現在キュー長から発行クレジット量を減算することでユーザフロー毎に現在キュー長を更新する、例えば、キュー長算出部である。フロー管理部２１１は、ユーザフロー毎のキュー長カウンタ２１１Ａの現在キュー長を参照し、キュー長カウンタ２１１Ａの現在キュー長が正（プラス値）であるか否かを判定する。
【００２２】
要求判定部２１２は、第１のタイミングに応じて入力パケットのエントリに関わるリスト操作要求があるか否かを判定し、リスト管理部２２側で実行するリスト操作の処理時間を確保するための処理部である。第１のタイミングとは、例えば、パケット入力やトークン追加処理でユーザフロー毎の出力キュー３２Ａがパケット出力可能な状態に移行した場合のリンクリスト４０に対する追加イベントが発生したタイミングである。また、第１のタイミングとは、例えば、クレジット発行が完了してリンクリスト４０に対する追加イベントが発生したタイミングである。リスト操作要求とは、例えば、リンクリスト４０にフロー番号のエントリ４１を追加するリスト操作をリスト管理部２２に要求するコマンドである。
【００２３】
要求判定部２１２は、図示せぬ記憶領域内にＦＩＦＯ２１２Ａ等の一時記憶部を生成する。尚、任意のユーザフローからリスト操作要求が発生するタイミングの最短時間は、最短パケットの処理時間となる。しかしながら、異なるユーザフローの短パケットが短い間隔で入力されると、ユーザフロー毎に、最短パケットの処理時間で当該パケットのエントリ４１に関わるリスト操作要求が発生する。そして、要求判定部２１２は、リスト管理部２２側で処理可能な時間よりも短い時間でリスト管理部２２に対してリスト操作要求が発行されることになるため、リスト操作要求に関わるエントリ４１をＦＩＦＯ２１２Ａ内に一時的に格納する。その結果、要求判定部２１２は、リスト管理部２２側で処理可能なタイミングでリスト操作要求をリスト管理部２２に通知するため、各ユーザフローのリンクリスト４０のリスト操作を実行する処理時間を確保できる。
【００２４】
要求判定部２１２は、対象ユーザフローに属するパケットの入力タイミングで、現在キュー長が正、かつ、回線帯域がＯＫの場合に、リンクリスト４０をリスト操作する際の対象ユーザフローのエントリを取得する。また、要求判定部２１２は、対象ユーザフローの回線帯域の更新タイミングで、現在キュー長が正、かつ、回線帯域がＯＫの場合に、リンクリスト４０をリスト操作する際の対象ユーザフローのエントリを取得する。また、要求判定部２１２は、対象ユーザフロー対応のクレジットカウンタ３３Ａへのクレジット発行が完了したタイミングで、現在キュー長が正、かつ、回線帯域がＯＫの場合に、リンクリスト４０をリスト操作する際の対象ユーザフローのエントリを取得する。
【００２５】
要求判定部２１２は、対象ユーザフローのエントリ４１を取得すると、取得されたエントリ４１と同一のエントリがＦＩＦＯ２１２Ａ内にあるか否かを判定する、例えば、判定部である。要求判定部２１２は、同一のエントリ４１がＦＩＦＯ２１２Ａ内にある場合に、当該エントリ４１のＦＩＦＯ２１２Ａ内への格納を禁止する。また、要求判定部２１２は、同一のエントリ４１がＦＩＦＯ２１２Ａ内にない場合に、当該エントリ４１をＦＩＦＯ２１２Ａ内に格納する。その結果、要求判定部２１２は、ＦＩＦＯ２１２Ａ内のリンクリスト４０に関わる同一エントリ４１の重複登録を防止し、１エントリ／１フローを実現する。
【００２６】
要求判定部２１２は、第２のタイミングを検出すると、ＦＩＦＯ２１２Ａに格納中の先頭エントリ４１をリンクリスト４０内の適切な位置に挿入する。尚、第２のタイミングは、ＦＩＦＯ２１２Ａ内にエントリ４１があり、かつ、リスト管理部２２側で処理が可能な状態の場合のタイミングである。
【００２７】
要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１があるか否かを判定する。要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１がある場合に、ＦＩＦＯ２１２Ａ内の先頭のエントリ４１を読み出す。要求判定部２１２は、先頭のエントリ４１を読み出した場合に、対象ユーザフローに対応したキュー長カウンタ２１１Ａの最新の状態を参照する。要求判定部２１２は、リンクリスト４０のエントリ４１に関わるリスト操作を要求する、最新状態を反映したリスト操作要求をリスト管理部２２に通知する。更に、要求判定部２１２は、リスト操作要求の通知が完了した後、ＦＩＦＯ２１２Ａ内の先頭エントリ４１を削除する。
【００２８】
要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１がない場合に、リスト操作要求を発行せずに処理を終了する。また、要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１がある場合でも、リスト管理部２２側で処理可能な状態でない場合に、ＦＩＦＯ２１２Ａ内の先頭エントリ４１を残したまま、リスト操作要求を発行せずに処理を終了する。
【００２９】
リスト管理部２２は、リスト操作部２２１と、リストテーブル２２２と、発行部２２４とを有する。リスト操作部２２１は、要求判定部２１２からのリスト操作要求のエントリ４１をリンクリスト４０の適切な位置に挿入するリスト操作を実行する、例えば、実行部である。リスト操作部２２１は、リスト操作を実行したリンクリスト４０を、例えば、記憶部等のリストテーブル２２２内に格納する。
【００３０】
図４は、リンクリスト４０のエントリ構成の一例を示す説明図である。図４に示すリンクリスト４０内のエントリ４１は、エントリ番号４１Ａと、前方向ポインタ４１Ｂと、後方向ポインタ４１Ｃとを有する。エントリ番号４１Ａは、リンクリスト４０内の対象ユーザフローのフロー番号のエントリ４１を識別する番号である。前方向ポインタ４１Ｂは、対象ユーザフローと前方向に隣接するユーザフローのフロー番号のエントリ４１を識別するエントリ番号である。後方向ポインタ４１Ｃは、対象ユーザフローと後方向に隣接するユーザフローのフロー番号のエントリ４１を識別するエントリ番号である。尚、エントリ番号４１Ａは、例えば、ソフトの配列の要素番号等であっても良い。リンクリスト４０は、エントリ番号４１Ａ毎に双方向の前方向ポインタ４１Ｂ及び後方向ポインタ４１Ｃを管理しているため、エントリ番号４１Ａの追加、削除や並び替えが容易である。
【００３１】
図５は、リンクリスト４０の一例を示す説明図である。図５に示すリンクリスト４０は、エントリ４１と、先頭（ヘッド）４２と、最後尾（テイル）４３とを有し、先頭４２から最後尾４３までの出力順序にユーザフローのエントリ４１を繋げた双方向の配列リストである。リスト管理部２２は、リストテーブル２２２内に格納中のリンクリスト４０を参照し、リンクリスト４０内の先頭４２から最後尾４３までの各エントリ４１を辿ることで、対象ユーザフローの出力順序を識別できる。また、リスト管理部２２は、リンクリスト４０を参照し、リンクリスト４０の最後尾４３から先頭４２までの各エントリ４１を辿ることで、ユーザフローの出力順序の逆経路を識別できる。
【００３２】
図６は、優先度を設定したリンクリスト４０の一例を示す説明図である。図６に示すリンクリスト４０は、先頭４２から最後尾４３までのエントリ４１の内、境界４４のエントリ４１を指定可能にし、境界４４、先頭４２若しくは最後尾４３で優先度を設定する。リスト操作部２２１は、例えば、第１の境界４４Ａを指定し、先頭４２のエントリ４１から第１の境界４４Ａのエントリ４１までの区間内の各エントリ４１に第１位の優先度Ｌｖ１を設定する。また、リスト操作部２２１は、第２の境界４４Ｂを指定し、第１の境界４４Ａのエントリ４１直後のエントリ４１から第２の境界４４Ｂのエントリ４１までの区間内の各エントリ４１に第２位の優先度Ｌｖ２を設定する。
【００３３】
また、リスト操作部２２１は、第３の境界４４Ｃを指定し、第２の境界４４Ｂのエントリ４１直後のエントリ４１から第３の境界４４Ｃのエントリ４１までの区間内の各エントリ４１に第３位の優先度Ｌｖ３を設定する。また、リスト操作部２２１は、第３の境界４４Ｃのエントリ４１直後のエントリ４１から最後尾４３までの区間の各エントリ４１に第４位の優先度Ｌｖ４を設定する。尚、第１位の優先度Ｌｖ１は優先順位が最も高く、優先順位の高い順に第２位の優先度Ｌｖ２、第３位の優先度Ｌｖ３、第４位の優先度Ｌｖ４…の順である。従って、リスト操作部２２１は、リンクリスト４０内の任意のエントリ４１に境界４４を指定することで簡単に優先度を設定できる。
【００３４】
リスト管理部２２の発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照し、先頭のエントリ４１がある場合、先頭エントリ４１のユーザフローに対応したクレジットカウンタ３３Ａに固定長のクレジットを発行する。その結果、キュー長カウンタ２１１Ａは、現在キュー長から発行クレジット量を減算することで現在キュー長を更新する。また、クレジットカウンタ３３Ａは、現在クレジット量に発行クレジット量を加算することで現在クレジット量を更新する。発行クレジット量は、少なくとも次の出力キュー３２Ａの選択に要する処理時間よりも大の時間をデータ換算したデータ量、例えば、固定長の１０２４バイトとする。図７は、１００Ｇｂｐｓの回線帯域の１５０ＭＨｚクロックと発行クレジット量との関係の一例を示す説明図である。発行クレジット量は、例えば、１５０ＭＨｚクロックの８クロック分の時間相当のデータ量である。例えば、図７の上段に示す比較例として１００Ｇｂｐｓの回線帯域で従来のＲＲ方式を採用した場合では、１５０ＭＨｚの１クロック分の時間内に出力キューを選択する処理時間を確保する必要がある。従って、回線帯域が広くなるに連れて処理時間を確保するのは困難と言える。これに対して、本実施例では、図７の下段に示すように、１５０ＭＨｚクロックの８クロック分（クレジット量）相当の時間内に出力キュー３２Ａを選択すれば良く、回線帯域が広くなったとしても出力キュー３２Ａの選択に要する処理時間を確保している。
【００３５】
スケジュール管理部２０及びバッファ管理部３０は、ユーザフロー毎に、出力キュー３２Ａ、クレジットカウンタ３３Ａ及びキュー長カウンタ２１１Ａを生成する。
【００３６】
次に本実施例の伝送システム１の動作について説明する。図８及び図９は、短パケット出力時のスケジュール管理部２０及びバッファ管理部３０の動作の一例を示す説明図である。図８の（Ａ）に示す伝送装置３は、例えば、バッファ３２内の対象ユーザフロー対応の出力キュー３２Ａに格納中のパケット長（キュー長）を“０”バイト、対象ユーザフロー対応のキュー長カウンタ２１１Ａの現在キュー長を“０バイト”とする。更に、伝送装置３は、対象ユーザフロー対応のクレジットカウンタ３３Ａの現在クレジット量を“０バイト”とする。
【００３７】
バッファ管理部３０内のＥｎＱ部３１は、図８の（Ａ）に示すように、６４バイトのパケットを入力すると、入力パケットが属する対象ユーザフロー対応の出力キュー３２Ａ内に６４バイトの入力パケットを格納する。ＥｎＱ部３１は、６４バイトのパケットに関するパケット情報をスケジュール管理部２０に通知する。尚、パケット情報は、入力パケットのパケット長及び入力パケットが属するユーザフローのフロー番号等を含む。
【００３８】
スケジュール管理部２０内の対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“０バイト”に入力パケット長“６４バイト”を加算することで“６４バイト”として現在キュー長を更新する。スケジュール管理部２０内の発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図８の（Ｂ）に示すように、発行クレジット“１Ｋバイト（１０２４バイト）”を先頭エントリ４１のユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａに発行する。クレジットカウンタ３３Ａは、現在クレジット量“０バイト”に発行クレジット量“１０２４バイト”を加算することで“１０２４バイト”として現在クレジット量を更新する。キュー長カウンタ２１１Ａは、現在キュー長“６４バイト”から発行クレジット量“１０２４バイト”を減算することで“−９６０バイト”として現在キュー長を更新する。
【００３９】
バッファ管理部３０内の出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量“１０２４バイト”が正であるか否かを判定する。出力制御部３３は、現在クレジット量が正である場合に、図８の（Ｃ）に示すように、対象ユーザフロー対応の出力キュー３２Ａに格納された６４バイトのパケットを出力する。そして、対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“１０２４バイト”から出力パケット長“６４バイト”を減算することで“９６０バイト”として現在クレジット量を更新する。
【００４０】
更に、ＥｎＱ部３１は、図８の（Ｄ）に示すように、６４バイトのパケットを入力すると、６４バイトの入力パケットを対象ユーザフロー対応の出力キュー３２Ａ内に格納する。そして、ＥｎＱ３１は、６４バイトのパケット格納に関わるパケット情報をスケジュール管理部２０に通知する。対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“−９６０バイト”に６４バイトの入力パケット長を加算することで“−８９６バイト”の現在キュー長を更新する。
【００４１】
更に、出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量“９６０バイト”が正であるか否かを判定する。出力制御部３３は、現在クレジット量が正である場合に、対象ユーザフロー対応の出力キュー３２Ａを選択し、図９の（Ａ）に示すように、出力キュー３２Ａに格納された６４バイトのパケットを出力する。そして、対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“９６０バイト”から出力パケット長“６４バイト”を減算することで“８９６バイト”として現在クレジット量を更新する。
【００４２】
更に、ＥｎＱ部３１は、図９の（Ｂ）に示すように、１０２４バイトのパケットを入力すると、入力パケットを対象ユーザフロー対応の出力キュー３２Ａ内に格納する。そして、ＥｎＱ部３１は、１０２４バイトのパケット格納に関わるパケット情報をスケジュール管理部２０に通知する。対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“−８９６バイト”に１０２４バイトの入力パケット長を加算することで“１２８バイト”として現在キュー長を更新する。
【００４３】
更に、出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量“８９６バイト”が正であるか否かを判定する。出力制御部３３は、現在クレジット量“８９６バイト”が正である場合に、図９の（Ｃ）に示すように、対象ユーザフロー対応の出力キュー３２Ａ内に格納された１０２４バイトのパケットを出力する。そして、対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“８９６バイト”から出力パケット長“１０２４バイト”を減算することで“−１２８バイト”として現在クレジット量を更新する。
【００４４】
更に、発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図９の（Ｄ）に示すように、発行クレジットを先頭エントリ４１の対象ユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａに発行する。対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“−１２８バイト”に発行クレジット量“１０２４バイト”を加算することで“８９６バイト”として現在クレジット量を更新する。更に、対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“１２８バイト”から発行クレジット量“１０２４バイト”を減算することで“−８９６バイト”として現在キュー長を更新する。
【００４５】
伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがあり、かつ、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量が正の場合に、出力キュー３２Ａ内のパケットをパケット単位で出力する。更に、伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがある場合に、パケット単位でパケットを順次出力する。その結果、伝送装置３は、現在クレジット量が０以下になるまで出力キュー３２Ａ内の短パケットをパケット単位で順次出力できる。
【００４６】
伝送装置３は、リンクリスト４０を定期的に参照して先頭エントリ４１のユーザフローに対応したクレジットカウンタ３３Ａに固定長のクレジットを発行する。その結果、クレジットを発行された対象ユーザフロー対応の出力キュー３２Ａは、パケットが出力可能な状態となる。
【００４７】
図１０及び図１１は、長パケット出力時のスケジュール管理部２０及びバッファ管理部３０の動作の一例を示す説明図である。図１０（Ａ）の伝送装置３は、バッファ３２内の対象ユーザフロー対応の出力キュー３２Ａ内に格納中のパケット長を“０”バイト、対象ユーザフロー対応のキュー長カウンタ２１１Ａの現在キュー長を“０バイト”とする。更に、伝送装置３は、対象ユーザフロー対応のクレジットカウンタ３３Ａの現在クレジット量を“０バイト”とする。
【００４８】
ＥｎＱ部３１は、図１０の（Ａ）に示すように、“４０００バイト”のパケットを入力すると、入力パケットを対象ユーザフロー対応の出力キュー３２Ａ内に格納する。そして、ＥｎＱ部３１は、４０００バイトのパケット格納に関するパケット情報をスケジュール管理部２０に通知する。対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“０バイト”に入力パケット長“４０００バイト”を加算することで“４０００バイト”として現在キュー長を更新する。
【００４９】
発行部２２４は、リンクリスト４０の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図１０の（Ｂ）に示すように、発行クレジット“１０２４バイト”を先頭エントリ４１の対象ユーザフロー対応のクレジットカウンタ３３Ａに発行する。クレジットカウンタ３３Ａは、現在クレジット量“０バイト”に発行クレジット量“１０２４バイト”を加算することで“１０２４バイト”として現在クレジット量を更新する。更に、対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“４０００バイト”から発行クレジット量“１０２４バイト”を減算することで“２９７６バイト”として現在キュー長を更新する。
【００５０】
出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量“１０２４バイト”が正であるか否かを判定する。出力制御部３３は、現在クレジット量“１０２４バイト”が正である場合に、図１０の（Ｃ）に示すように、対象ユーザフロー対応の出力キュー３２Ａ内に格納中の４０００バイトのパケットを出力する。そして、対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“１０２４バイト”から出力パケット長“４０００バイト”を減算することで“−２９７６バイト”として現在クレジット量を更新する。
【００５１】
更に、ＥｎＱ部３１は、図１０の（Ｄ）に示すように、６４バイトのパケットを入力した場合に、入力パケットを対象ユーザフロー対応の出力キュー３２Ａ内に格納する。そして、ＥｎＱ部３１は、６４バイトのパケット格納に関するパケット情報をスケジュール管理部２０に通知する。対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“２９７６バイト”に入力パケット長“６４バイト”を加算することで“３０４０バイト”として現在キュー長を更新する。
【００５２】
発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図１１の（Ａ）に示すように、発行クレジット“１０２４バイト”を先頭エントリ４１の対象ユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａに発行する。クレジットカウンタ３３Ａは、現在クレジット量“−２９７６バイト”に発行クレジット量“１０２４バイト”を加算することで“−１９５２バイト”として現在クレジット量を更新する。更に、対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“３０４０バイト”から発行クレジット量“１０２４バイト”を減算することで“２０１６バイト”として現在キュー長を更新する。
【００５３】
発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図１１の（Ｂ）に示すように、発行クレジット“１０２４バイト”を先頭エントリ４１の対象ユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａに発行する。クレジットカウンタ３３Ａは、現在クレジット量“−１９５２バイト”に発行クレジット量“１０２４バイト”を加算することで“−９２８バイト”として現在クレジット量を更新する。更に、対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“２０１６バイト”から発行クレジット量“１０２４バイト”を減算することで“９９２バイト”として現在キュー長を更新する。
【００５４】
発行部２２４は、リンクリスト４０内の先頭エントリ４１を定期的に参照して、対象ユーザフローの先頭エントリ４１があるか否かを判定する。発行部２２４は、対象ユーザフローの先頭エントリ４１がある場合、図１１の（Ｃ）に示すように、発行クレジット“１０２４バイト”を先頭エントリ４１の対象ユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａに発行する。クレジットカウンタ３３Ａは、現在クレジット量“−９２８バイト”に発行クレジット量“１０２４バイト”を加算することで“９６バイト”として現在クレジット量を更新する。更に、対象ユーザフロー対応のキュー長カウンタ２１１Ａは、現在キュー長“９９２バイト”から発行クレジット量“１０２４バイト”を減算することで“−３２バイト”として現在キュー長を更新する。
【００５５】
更に、出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量“９６バイト”が正であるか否かを判定する。出力制御部３３は、現在クレジット量“９６バイト”が正である場合に、図１１の（Ｄ）に示すように、対象ユーザフロー対応の出力キュー３２Ａ内に格納中の６４バイトのパケットを出力する。そして、対象ユーザフロー対応のクレジットカウンタ３３Ａは、現在クレジット量“９６バイト”から出力パケット長“６４バイト”を減算することで“−３２バイト”として現在クレジット量を更新する。
【００５６】
伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内にパケットがあり、かつ、現在クレジット量が正の場合に、出力キュー３２Ａ内のパケットが長パケットの場合でも、出力キュー３２Ａ内の長パケットをパケット単位で出力する。その結果、伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内の長パケットをパケット単位で出力できる。
【００５７】
伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａからパケット出力する場合に、現在クレジット量から出力パケット長を減算することで、対象ユーザフロー対応のクレジットカウンタ３３Ａの現在クレジット量を更新する。伝送装置３は、リンクリスト４０を定期的に参照して先頭エントリ４１のユーザフローに対応したクレジットカウンタ３３Ａに固定長のクレジットを発行する。伝送装置３は、クレジットカウンタ３３Ａの現在クレジット量が正になるまで、対象ユーザフローに対応したパケット出力を停止する。
【００５８】
図１２は、エントリ格納処理に関わる追加制御部２１の処理動作の一例を示すフローチャートである。図１２に示すエントリ格納処理は、第１のタイミングに応じて対象ユーザフローのパケットのエントリ４１をＦＩＦＯ２１２Ａ内に格納する処理である。
【００５９】
図１２において追加制御部２１内の要求判定部２１２は、ＥｎＱ部３１からのパケット情報に基づき、対象ユーザフローへのパケットが入力されたか否かを判定する（ステップＳ１１）。要求判定部２１２は、対象ユーザフローへのパケットが入力された場合に（ステップＳ１１肯定）、対象ユーザフロー対応のキュー長カウンタ２１１Ａ内の現在キュー長に入力パケット長を加算する（ステップＳ１１Ａ）。要求判定部２１２は、対象ユーザフロー対応のキュー長カウンタ２１１Ａ内の現在キュー長が正であるか否かを判定する（ステップＳ１２）。要求判定部２１２は、現在キュー長が正である場合に（ステップＳ１２肯定）、対象ユーザフロー対応の回線帯域がＯＫであるか否かを判定する（ステップＳ１３）。要求判定部２１２は、回線帯域がＯＫである場合に（ステップＳ１３肯定）、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内に既にあるか否かを判定する（ステップＳ１４）。
【００６０】
要求判定部２１２は、対象ユーザフローのエントリがＦＩＦＯ２１２Ａ内に既にない場合に（ステップＳ１４否定）、対象ユーザフローのエントリ４１をＦＩＦＯ２１２Ａ内に格納し（ステップＳ１５）、図１２に示す処理動作を終了する。要求判定部２１２は、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内にない場合にのみ、当該エントリ４１をＦＩＦＯ２１２Ａ内に格納する。その結果、要求判定部２１２は、ＦＩＦＯ２１２Ａ内のリンクリスト４０に関わる同一エントリの重複登録を防止し、１エントリ／１フローを実現できる。
【００６１】
要求判定部２１２は、対象ユーザフローへのパケットが入力されなかった場合に（ステップＳ１１否定）、対象ユーザフロー対応の回線帯域の更新を検出したか否かを判定する（ステップＳ１６）。尚、回線帯域の更新とは、例えば、ＮＧからＯＫへの更新である。要求判定部２１２は、回線帯域の更新を検出した場合に（ステップＳ１６肯定）、対象ユーザフロー対応のキュー長カウンタ２１１Ａの現在キュー長が正であるか否かを判定すべく、ステップＳ１２に移行する。
【００６２】
要求判定部２１２は、回線帯域の更新を検出しなかった場合に（ステップＳ１６否定）、対象ユーザフロー対応のクレジットカウンタ３３Ａへのクレジット発行が完了したか否かを判定する（ステップＳ１７）。要求判定部２１２は、クレジット発行が完了した場合に（ステップＳ１７肯定）、対象ユーザフロー対応の現在キュー長から発行クレジット量を減算する（ステップＳ１８）。要求判定部２１２は、発行クレジット量減算後、対象ユーザフロー対応の現在キュー長が正であるか否かを判定すべく、ステップＳ１２に移行する。
【００６３】
要求判定部２１２は、クレジット発行が完了しなかった場合に（ステップＳ１７否定）、図１２に示す処理動作を終了する。要求判定部２１２は、対象ユーザフロー対応の現在キュー長が正でない場合に（ステップＳ１２否定）、図１２に示す処理動作を終了する。要求判定部２１２は、対象ユーザフロー対応の回線帯域がＯＫでない場合に（ステップＳ１３否定）、又は対象ユーザフローのエントリがＦＩＦＯ２１２Ａ内に既にある場合に（ステップＳ１４肯定）、図１２に示す処理動作を終了する。
【００６４】
図１２に示すエントリ格納処理の要求判定部２１２は、対象ユーザフローへのパケットが入力された場合、対象ユーザフロー対応の回線帯域を更新した場合や、対象ユーザフロー対応のクレジット発行が完了した場合に、現在キュー長が正であるか否かを判定する。要求判定部２１２は、対象ユーザフロー対応の現在キュー長が正、かつ、対象ユーザフロー対応の回線帯域がＯＫの場合に、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内に既にあるか否かを判定する。要求判定部２１２は、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内にない場合にのみ、エントリ４１をＦＩＦＯ２１２Ａ内に格納する。その結果、要求判定部２１２は、リンクリスト４０に対する同一エントリ４１の重複登録を防止し、１エントリ／１フローを実現できる。
【００６５】
図１３は、エントリ読出処理に関わる追加制御部２１の処理動作の一例を示すフローチャートである。エントリ読出処理は、第２のタイミングに応じて、ＦＩＦＯ２１２Ａ内の先頭のエントリ４１を読み出し、読み出したエントリ４１に関わるリスト操作要求を発行する処理である。
【００６６】
図１３において追加制御部２１内の要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１が存在するか否かを判定する（ステップＳ２１）。要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１が存在する場合に（ステップＳ２１肯定）、リスト管理部２２側で処理可能な状態であるか否かを判定する（ステップＳ２２）。
【００６７】
要求判定部２１２は、リスト管理部２２側で処理可能な状態の場合に（ステップＳ２２肯定）、ＦＩＦＯ２１２Ａ内の先頭エントリ４１を取得する（ステップＳ２３）。要求判定部２１２は、対象ユーザフロー対応のキュー長カウンタ２１１Ａの内容を参照して最新状態情報を取得する（ステップＳ２４）。要求判定部２１２は、対象ユーザフローの最新状態情報を取得した後、リスト操作部２２１に対して対象ユーザフローのエントリ４１に関わる、最新の状態情報を反映したリスト操作要求を発行する（ステップＳ２５）。尚、リスト操作要求は、例えば、リンクリスト４０に対してエントリ４１の追加、削除や並び替えのリスト操作を要求するコマンドである。その結果、リスト操作部２２１は、要求判定部２１２からのリスト操作要求に応じて、ＦＩＦＯ２１２Ａ内の先頭エントリ取得時の対象ユーザフローの最新状態を認識できる。要求判定部２１２は、リスト操作要求を発行した後、ＦＩＦＯ２１２Ａ内の先頭エントリ４１を削除し（ステップＳ２６）、図１３に示す処理動作を終了する。
【００６８】
要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１が存在しない場合に（ステップＳ２１否定）、図１３に示す処理動作を終了する。要求判定部２１２は、リスト管理部２２側で処理可能な状態でない場合に（ステップＳ２２否定）、図１３に示す処理動作を終了する。
【００６９】
図１３に示すエントリ読出処理の要求判定部２１２は、ＦＩＦＯ２１２Ａ内にエントリ４１が存在し、かつ、リスト管理部２２側で処理が可能な状態の場合に、対象ユーザフローの最新状態情報を取得する。要求判定部２１２は、エントリ４１に関わる、最新状態情報を反映したリスト操作要求をリスト操作部２２１に通知する。つまり、リスト操作部２２１は、処理が可能なタイミングで、要求判定部２１２からリスト操作要求を受け付ける。その結果、例えば、異なるユーザフローの短パケットが短い間隔で到着しても、そのフロー番号をＦＩＦＯ２１２Ａ内に一時的に記憶することで輻輳を吸収するため、処理可能時間よりも短い間隔で複数のリスト操作要求が集中するような場合にも対応できる。
【００７０】
尚、任意のユーザフローからリスト操作要求が発生するタイミングの最短時間は、最短パケットの処理時間となる。しかし、同一ユーザフローの最短パケットが連続した場合でも、固定長のクレジット量単位で管理しているため、リスト操作を最短パケットの処理時間内に終わらせる必要はなく、クレジット量相当の時間内に終わらせれば良い。
【００７１】
図１４は、リスト操作処理に関わるリスト操作部２２１の処理動作の一例を示すフローチャートである。図１４に示すリスト操作処理は、リスト操作要求を受信した場合に、対象ユーザフローに対応したリスト操作要求に関わるエントリ４１を用いてリンクリスト４０のリスト操作を実行する処理である。
【００７２】
図１４においてリスト操作部２２１は、追加制御部２１内の要求判定部２１２から対象ユーザフロー対応のエントリ４１に関わるリスト操作要求を受信したか否かを判定する（ステップＳ３１）。リスト操作部２２１は、対象ユーザフロー対応のリスト操作要求を受信した場合に（ステップＳ３１肯定）、リストテーブル２２２内のリンクリスト４０を参照する（ステップＳ３２）。
【００７３】
リスト操作部２２１は、参照したリンクリスト４０内にリスト操作要求に関わる同一エントリ４１があるか否かを判定する（ステップＳ３３）。リスト操作部２２１は、リンクリスト４０内に同一エントリ４１がある場合に（ステップＳ３３肯定）、エントリ４１の優先度変更要求を検出したか否かを判定する（ステップＳ３４）。尚、優先度変更要求は、例えば、図示せぬ管理端末から指定可能な要求である。
【００７４】
リスト操作部２２１は、エントリ４１の優先度変更要求を検出した場合に（ステップＳ３４肯定）、リンクリスト４０内の該当エントリ４１の優先度変更のリスト操作を実行する（ステップＳ３５）。尚、優先度変更のリスト操作は、リンクリスト４０内のエントリ４１に境界４４を指定することでリンクリスト４０内のエントリ４１の優先度を変更するリスト操作である。リスト操作部２２１は、エントリ４１の優先度を変更したリンクリスト４０をリストテーブル２２２内に格納し（ステップＳ３６）、図１４に示す処理動作を終了する。
【００７５】
リスト操作部２２１は、リンクリスト４０内に同一エントリ４１がない場合に（ステップＳ３３否定）、リンクリスト４０内の各優先度の境界４４又は最後尾４３にリスト操作要求に関わるエントリを追加するリスト操作を実行する（ステップＳ３７）。尚、エントリ追加のリスト操作は、リンクリスト４０内の各優先度の境界４４又は最後尾４３にエントリ４１を追加するリスト操作である。そして、リスト操作部２２１は、優先度の境界４４又は最後尾４３にエントリ４１を追加したリンクリスト４０をリストテーブル２２２内に格納すべく、ステップＳ３６に移行する。
【００７６】
リスト操作部２２１は、エントリ４１の優先度変更要求を検出しなかった場合に（ステップＳ３４否定）、リンクリスト４０内の該当エントリ４１の順序を並び替える並び替え要求を検出したか否かを判定する（ステップＳ３８）。リスト操作部２２１は、並び替え要求を検出した場合に（ステップＳ３８肯定）、並び替えのリスト操作を実行する（ステップＳ３９）。尚、並び替えのリスト操作は、リンクリスト４０内の任意のエントリ４１の順序を並び替えるリスト操作である。そして、リスト操作部２２１は、エントリ４１の順序を並び替えたリンクリスト４０をリストテーブル２２２内に格納すべく、ステップＳ３６に移行する。
【００７７】
リスト操作部２２１は、並び替え要求を検出しなかった場合に（ステップＳ３８否定）、該当エントリ４１を破棄し（ステップＳ４０）、図１４に示す処理動作を終了する。尚、ステップＳ４０の該当エントリ４１は、新しく追加しようとするエントリ、すなわち新規エントリに相当する。リスト操作部２２１は、対象ユーザフロー対応のエントリ４１に関わるリスト操作要求を受信しなかった場合に（ステップＳ３１否定）、図１４に示す処理動作を終了する。
【００７８】
図１４に示すリスト操作処理のリスト操作部２２１は、対象ユーザフローのリスト操作要求を受信した場合に、リンクリスト４０内にリスト操作要求に関わるエントリ４１と同一のエントリ４１があるか否かを判定する。リスト操作部２２１は、リンクリスト４０内にリスト操作要求と同一のエントリ４１がない場合に、リンクリスト４０内の優先度の境界４４又は最後尾４３にリスト操作要求のエントリ４１を追加するリスト操作を実行する。その結果、リスト操作部２２１は、リンクリスト４０内の優先度の境界４４又は最後尾４３にエントリ４１を順次追加できる。尚、エントリ４１を追加するリスト操作には、新規のエントリ４１を先頭４２に配置するリンクリスト４０のリスト操作を含む。
【００７９】
リスト操作部２２１は、リンクリスト４０内にリスト操作要求と同一のエントリ４１があり、かつ、優先度変更要求の場合に、指定した境界４４に応じてエントリ４１の優先度を設定するリスト操作を実行する。その結果、リスト操作部２２１は、リンクリスト４０内のエントリ４１の優先度を自由に設定できる。
【００８０】
リスト操作部２２１は、リンクリスト４０内にリスト操作要求と同一のエントリ４１があり、かつ、並び替え要求の場合に、リンクリスト４０内のエントリ４１を並び替えるリスト操作を実行する。その結果、リスト操作部２２１は、リンクリスト４０内のエントリ４１を簡単に並び替えることができる。
【００８１】
リスト操作部２２１は、リンクリスト４０内の先頭４２のエントリ４１のユーザフローに対応したクレジット発行が完了する都度、該当エントリ４１をリンクリスト４０から削除する。そして、リスト操作部２２１は、先頭４２のエントリ４１のリンクリスト４０へのリスト再追加が可能な場合、エントリ４１をＦＩＦＯ２１２Ａに追加登録する。その結果、出力制御部３３は、リンクリスト４０の先頭４２から最後尾４３へと、エントリ４１のユーザフローに対応した出力キュー３２Ａからパケットを順次出力することになるため、ＲＲ方式に類似した動作を実現している。
【００８２】
次に、並び替えのリスト操作について説明する。図１５は、並び替えのリスト操作に関わるリンクリスト４０のエントリ４１の変更推移の一例を示す説明図である。図１５の（Ａ）に示すリンクリスト４０は、例えば、先頭４２から最後尾４３までの区間のエントリ４１としてエントリ番号＃１０→＃０→＃１１→＃５→＃３→＃７１→＃３１の順に配置する。そして、エントリ番号＃０に第１位の境界４４Ａ、エントリ番号＃３に第２位の境界４４Ｂ、エントリ番号＃３１に最後尾４３を設定する。その結果、エントリ番号＃１０及び＃０は第１位の優先度Ｌｖ１、エントリ番号＃１１、＃５及び＃３は第２位の優先度Ｌｖ２、エントリ番号＃７１及び＃３１は第３位の優先度Ｌｖ３として設定する。
【００８３】
次に、新規ユーザフローのエントリ番号＃５３を第１位の優先度Ｌｖ１に並び替えるリスト操作について説明する。リスト操作部２２１は、図１５の（Ｂ）に示すように、リンクリスト４０内のエントリ番号＃０の直後に新規のエントリ番号＃５３を配置するリスト操作を実行する。この際、エントリ番号＃５３の前方向ポインタ４１Ｂ及び後方向ポインタ４１Ｃの変更は勿論のこと、エントリ番号＃０の後方向ポインタ４１Ｃを＃１１→＃５３、エントリ番号＃１１の前方向ポインタ４１Ｂを＃０→＃５３に書き換える。その結果、リスト操作部２２１は、リンクリスト４０内のエントリ番号＃１０とエントリ番号＃１１との間に新規のエントリ番号＃５３を簡単に挿入できる。
【００８４】
また、リンクリスト４０内の第３位の優先度Ｌｖ３のエントリ番号＃７１及び＃３１を第１位の優先度Ｌｖ１に並び替えるリスト操作について説明する。リスト操作部２２１は、図１５の（Ｃ）に示すように、リンクリスト４０内のエントリ番号＃５３の直後にエントリ番号＃７１及び＃３１を配置するリスト操作を実行する。この際、エントリ番号＃７１及び＃３１の前方向ポインタ４１Ｂ及び後方向ポインタ４１Ｃの変更は勿論のこと、エントリ番号＃５３の後方向ポインタ４１Ｃを＃１１→＃７１、エントリ番号＃１１の前方向ポインタ４１Ｂを＃５３→＃３１に書き換える。その結果、リスト操作部２２１は、リンクリスト４０内の第３位の優先度Ｌｖ３のエントリ番号＃７１及び＃３１を第１位の優先度Ｌｖ１に簡単に設定できる。
【００８５】
図１６は、第１のパケット出力処理に関わる出力制御部３３の処理動作の一例を示すフローチャートである。第１のパケット出力処理は、発行クレジットを取得したクレジットカウンタ３３Ａに対応する出力キュー３２Ａからパケット単位でパケットを出力する処理である。
【００８６】
図１６において出力制御部３３は、発行部２２４から発行クレジットを取得したか否かを判定する（ステップＳ５１）。出力制御部３３は、発行クレジットを取得した場合に（ステップＳ５１肯定）、対象ユーザフロー対応の出力キュー３２Ａのクレジットカウンタ３３Ａの現在クレジット量に発行クレジット量を加算することで現在クレジット量を更新する（ステップＳ５２）。出力制御部３３は、現在クレジット量が正（プラス値）であるか否かを判定する（ステップＳ５３）。出力制御部３３は、現在クレジット量が正の場合に（ステップＳ５３肯定）、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがあるか否かを判定する（ステップＳ５４）。
【００８７】
出力制御部３３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがある場合に（ステップＳ５４肯定）、当該出力キュー３２Ａからパケットをパケット単位で出力する（ステップＳ５５）。出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量から出力パケット長を減算することで現在クレジット量を更新する（ステップＳ５６）。
【００８８】
出力制御部３３は、現在クレジット量の更新後、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがあるか否かを判定する（ステップＳ５７）。出力制御部３３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがない場合に（ステップＳ５７否定）、図１６に示す処理動作を終了する。
【００８９】
出力制御部３３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがある場合に（ステップＳ５７肯定）、対象ユーザフロー対応の現在クレジット量が正であるか否かを判定する（ステップＳ５８）。出力制御部３３は、現在クレジット量が正の場合に（ステップＳ５８肯定）、対象ユーザフロー対応の出力キュー３２Ａからパケット出力すべく、図中のＭ１に移行する。
【００９０】
出力制御部３３は、現在クレジット量が正でない場合に（ステップＳ５８否定）、発行クレジットを取得したか否かを判定すべく、ステップＳ５１に移行する。
【００９１】
出力制御部３３は、発行クレジットを取得しなかった場合に（ステップＳ５１否定）、図１６に示す処理動作を終了する。また、出力制御部３３は、現在クレジット量が正でない場合に（ステップＳ５３否定）、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがあるか否かを判定する（ステップＳ５９）。出力制御部３３は、出力キュー３２Ａ内に出力可能なパケットがある場合に（ステップＳ５９肯定）、発行クレジットを取得したか否かを判定すべく、ステップＳ５１に移行する。
【００９２】
出力制御部３３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがない場合に（ステップＳ５９否定）、図１６に示す処理動作を終了すべく、図中のＭ２に移行する。また、出力制御部３３は、対象ユーザフロー対応の出力キュー３２Ａ内に出力可能なパケットがない場合に（ステップＳ５４否定）、図１６に示す処理動作を終了する。
【００９３】
出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａの現在クレジット量が正、かつ、対応の出力キュー３２Ａ内に出力可能なパケットがある場合に、対象ユーザフロー対応の出力キュー３２Ａからパケット単位でパケットを出力する。その結果、出力制御部３３は、現在クレジット量が０以下になるまで対象ユーザフローのパケットをパケット単位で順次出力できる。
【００９４】
出力制御部３３は、現在クレジット量が０以下、かつ、対応の出力キュー３２Ａ内に出力可能なパケットがある場合に、発行部２２４からのクレジットを取得するまでパケット出力を待機する。出力制御部３３は、発行クレジットを取得した場合に、現在クレジット量に発行クレジット量を加算することで現在クレジット量を更新し、現在クレジット量が正となると、対応の出力キュー３２Ａからパケット単位でパケット出力する。その結果、出力制御部３３は、現在クレジット量が０以下になるまで対象ユーザフロー対応の出力キュー３２Ａのパケットをパケット単位で順次出力できる。
【００９５】
図１７は、第２のパケット出力処理に関わる出力制御部３３の処理動作の一例を示すフローチャートである。第２のパケット出力処理は、ＥｎＱ部３１からパケットを入力した場合に、対象ユーザフロー対応の出力キュー３２Ａからパケット単位でパケットを出力する処理である。
【００９６】
図１７において出力制御部３３は、ＥｎＱ部３１からパケットを入力したか否かを判定する（ステップＳ６１）。出力制御部３３は、パケットを入力した場合に（ステップＳ６１肯定）、入力パケットを対象ユーザフロー対応の出力キュー３２Ａ内に格納し（ステップＳ６２）、現在クレジット量が正であるか否かを判定する（ステップＳ６３）。
【００９７】
出力制御部３３は、現在クレジット量が正である場合に（ステップＳ６３肯定）、当該出力キュー３２Ａからパケットをパケット単位で出力する（ステップＳ６４）。出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａ内の現在クレジット量から出力パケット長を減算することで現在クレジット量を更新し（ステップＳ６５）、図１７に示す処理動作を終了する。出力制御部３３は、ＥｎＱ部３１からパケットを入力しなかった場合に（ステップＳ６１否定）、図１７に示す処理動作を終了する。出力制御部３３は、現在クレジット量が正でない場合に（ステップＳ６３否定）、図１７に示す処理動作を終了する。
【００９８】
出力制御部３３は、対象ユーザフロー対応のクレジットカウンタ３３Ａの現在クレジット量が正、かつ、対応の出力キュー３２Ａ内に出力可能なパケットがある場合に、対象ユーザフロー対応の出力キュー３２Ａからパケット単位でパケットを出力する。その結果、出力制御部３３は、現在クレジット量が０以下になるまで対象ユーザフローのパケットをパケット単位で順次出力できる。
【００９９】
出力制御部３３は、現在クレジット量が０以下、かつ、対応の出力キュー３２Ａ内に出力可能なパケットがある場合に、発行部２２４からのクレジットを取得するまでパケット出力を待機する。出力制御部３３は、発行クレジットを取得した場合に、現在クレジット量に発行クレジット量を加算することで現在クレジット量を更新し、現在クレジット量が正となると、対応の出力キュー３２Ａからパケット単位でパケット出力する。その結果、出力制御部３３は、現在クレジット量が０以下になるまで対象ユーザフロー対応の出力キュー３２Ａのパケットをパケット単位で順次出力できる。
【０１００】
尚、説明の便宜上、単一のキュー階層でユーザフローの出力順序を示すリンクリスト４０を例示したが、通常の伝送システムでは、例えば、物理ポート→仮想ポート→ユーザフローの複数段のキュー階層構造を有している。そこで、複数段のキュー階層構造のリンクリストに関わる全体リンクリストについて説明する。図１８は、キュー階層構造の一例を示す説明図である。図１８に示すキュー階層構造は、回線１００と、回線１００と下位階層関係にある物理ポート１０１と、物理ポート１０１と下位階層関係にある仮想ポート１０２と、仮想ポート１０２と下位階層関係にあるユーザフロー１０３とを含む階層構造である。
【０１０１】
伝送装置３は、キュー階層構造全体のリンクリストとして全体リンクリストを管理している。全体リンクリストは、回線１００を識別するエントリ３００と、物理ポート１０１の物理ポート番号を識別するエントリ３０１と、仮想ポート１０２の仮想ポート番号を識別するエントリ３０２と、ユーザフロー１０３のフロー番号を識別するエントリ３０３とを双方向ポインタで管理している。例えば、回線１００のエントリ３００の接続順序は、物理ポート１０１Ａのエントリ３０１Ａ→物理ポート１０１Ｂのエントリ３０１Ｂの順である。物理ポート１０１Ａのエントリ３０１Ａの接続順序は、仮想ポート１０２Ａのエントリ３０２Ａ→仮想ポート１０２Ｂのエントリ３０２Ｂの順である。更に、仮想ポート１０２Ａのエントリ３０２Ａの接続順序は、ユーザフロー１０３Ａのエントリ３０３Ａ→ユーザフロー１０３Ｂのエントリ３０３Ｂの順である。また、例えば、物理ポート１０１Ｂのエントリ３０１Ｂの接続順序は、仮想ポート１０２Ｄのエントリ３０２Ｄ→仮想ポート１０２Ｃのエントリ３０２Ｃの順である。また、仮想ポート１０２Ｃのエントリ３０２Ｃの接続順序は、ユーザフロー１０３Ｆのエントリ３０３Ｆ→ユーザフロー１０３Ｄのエントリ３０３Ｄ→ユーザフロー１０３Ｅのエントリ３０３Ｅの順である。
【０１０２】
図１９は、キュー階層構造上の全体リンクリストの参照動作の一例を示す説明図である。図１９に示す全体リンクリストの例として、回線のエントリ３００の接続順序は、物理ポートのエントリ３０１Ｃ→物理ポートのエントリ３０１Ｄの順である。物理ポートのエントリ３０１Ｃの接続順序は、仮想ポートのエントリ３０２Ｇ→仮想ポートのエントリ３０２Ｅの順である。更に、仮想ポートのエントリ３０２Ｇの接続順序は、ユーザフローのエントリ３０３Ｊ→ユーザフローのエントリ３０３Ｈ→ユーザフローのエントリ３０３Ｍの順である。リスト管理部２２は、全体リンクリストを参照し、回線のエントリ３００→物理ポートのエントリ３０１Ｃ→仮想ポートのエントリ３０２Ｇ→ユーザフローのエントリ３０３Ｊの伝送経路を識別する。更に、リスト管理部２２は、ユーザフローのエントリ３０３Ｊ→仮想ポートのエントリ３０２Ｇ→物理ポートのエントリ３０１Ｃ→回線のエントリ３００の逆経路も識別できる。尚、この場合、スケジュール管理部２０は、キュー階層毎に追加制御部２１及びリスト管理部２２を生成する。従って、スケジュール管理部２０は、複数のキュー階層を構築する場合に、キュー階層数分の追加制御部２１及びリスト管理部２２を生成する。全体管理部２３は、キュー階層毎の追加制御部２１及びリスト管理部２２を管理している。
【０１０３】
全体管理部２３は、キュー階層毎の追加制御部２１及びリスト管理部２２を管理し、出力可能なユーザフローが存在するか否かを判定する。全体管理部２３は、出力可能なユーザフローが存在する際、全体リンクリストを参照して、物理ポート、仮想ポート及びユーザフローのキュー階層毎の先頭エントリを辿って対象ユーザフローの出力キュー３２Ａのクレジットカウンタ３３Ａにクレジットを発行する。
【０１０４】
図２０は、キュー階層構造の一例を示す説明図である。伝送装置３は、全体リンクリストに示すようにキュー階層間の接続関係が固定的でないため、複数段のキュー構成に柔軟に対応できる。従来のＲＲ方式では、上位階層側のキューと下位階層側のキューとの関係が固定的で、例えば、連続性、接続数及び接続関係等の様々な制限がある。任意の上位階層側のキューに接続される下位階層側のキューを割り当てる際に連続性を持って割り当てられ、更に、各階層の接続数も固定的で、下位階層の大小関係と上位階層の大小関係とが交差しない接続関係となっている。しかも、上位階層側から目的のユーザフローを見つけ出すまでにキューの接続情報を逆に辿る逆引きの変換テーブルが必要であった。これに対して、本実施例の全体リンクリストを用いるキュー階層構造では、階層毎に任意のエントリ情報を追加可能とし、全体リンクリストを参照して全体の伝送経路は勿論のこと、逆経路も識別できる。図２０に示すキュー階層構造は、任意の上位階層側の接続ポートに下位階層側の接続ポートを自由に割り当て、各階層の接続数が自由で、しかも、下位階層の大小関係と上位階層の大小関係とが交差する接続関係も許容している。その結果、キュー階層構造では、例えば、連続性、接続数及び接続関係等の制約なく、複数段のキュー階層構造に柔軟に対応できる。しかも、伝送装置３は、全体リンクリスト内の先頭を参照することで、次に参照すべき接続ポートが判るため、逆引きのための変換テーブルを必要としない。
【０１０５】
本実施例の伝送装置３は、ユーザフロー毎に出力キュー３２Ａを生成し、入力したパケットを当該パケットが属するユーザフローに対応した出力キュー３２Ａに格納する。伝送装置３は、ユーザフローの出力順序を示すリンクリスト４０内の先頭エントリ４１を参照し、先頭エントリ４１のユーザフローに対応した出力キュー３２Ａのクレジットカウンタ３３Ａにクレジットを発行する。伝送装置３は、クレジットが発行された出力キュー３２Ａからパケットをパケット単位で出力する。その結果、リンクリスト４０内の先頭エントリ４１を参照して該当ユーザフローが見つかるため、パケット伝送性能の低下を防止できる。
【０１０６】
伝送装置３は、リンクリスト４０内の先頭エントリ４１を定期的に参照し、固定長のクレジットを先頭エントリ４１のユーザフローに対応したクレジットカウンタ３３Ａに発行し、クレジットのクレジット量相当の時間内にキュー選択する。その結果、固定長のクレジット量相当の時間内に出力キュー３２Ａの選択が完了すれば良く、パケット伝送性能の低下を防止できる。
【０１０７】
伝送装置３は、対象ユーザフロー対応のパケットを出力した場合に、対象ユーザフローに対応した現在クレジット量から出力パケット長を減算することで現在クレジット量を更新する。伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内にパケットがあり、かつ、対象ユーザフロー対応の現在クレジット量が正の場合に、出力キュー３２Ａ内のパケットをパケット単位で出力する。その結果、伝送装置３は、回線帯域を広くしたとしても、固定長のクレジット量相当の時間内に出力キュー３２Ａの選択を完了し、対象ユーザフローのパケットをパケット単位で順次出力するため、パケット伝送性能の低下を防止できる。
【０１０８】
伝送装置３は、リンクリスト４０内の先頭エントリ４１を定期的に参照し、先頭エントリ４１のユーザフローに対応したクレジットカウンタ３３Ａに固定長の発行クレジットを発行する。その結果、伝送装置３は、対象ユーザフロー対応の出力キュー３２Ａ内にパケットがある場合に、クレジット発行に応じて出力キュー３２Ａ内のパケットをパケット単位で出力できる。
【０１０９】
伝送装置３は、リンクリスト４０を用いて対象ユーザフロー対応の出力キュー３２Ａからパケット単位でパケットを出力する。その結果、伝送装置３は、従来のＲＲ方式に比較して、ユーザフローの数が増加した場合でも、リンクリスト４０内のエントリ数が増えるのみで、回路数を増やすことなく、ユーザフロー数の増加に柔軟に対応できる。
【０１１０】
伝送装置３は、リンクリスト４０を用いて先頭エントリ４１の対象ユーザフロー対応の出力キュー３２Ａからパケット単位でパケットを出力する。その結果、伝送装置３は、リンクリスト４０の配列を辿ることで入力ユーザフローのパケットを順次出力するため、従来のＲＲ方式に比較して入力順にパケットが出力できないようなパケット遅延を防止できる。
【０１１１】
伝送装置３は、異なるユーザフローのパケットを入力した場合でも、ＦＩＦＯ２１２Ａ内に各ユーザフローのエントリ４１を一時的に格納し、リスト操作部２２１側でリンクリスト４０のリスト操作の処理が可能となるまで待機する。その結果、伝送装置３は、リスト操作部２２１側での各ユーザフローのリンクリスト４０に対するリスト操作の処理負担を軽減できる。
【０１１２】
伝送装置３は、対象ユーザフロー対応の現在キュー長が正で、かつ、対象ユーザフロー対応の回線帯域がＯＫの場合に、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内にあるか否かを判定する。伝送装置３は、対象ユーザフローのエントリ４１がＦＩＦＯ２１２Ａ内に既にある場合に当該エントリ４１のＦＩＦＯ２１２Ａ内への登録を禁止し、当該エントリ４１がＦＩＦＯ２１２Ａ内にない場合に当該エントリ４１をＦＩＦＯ２１２Ａ内に登録する。その結果、伝送装置３は、ＦＩＦＯ２１２Ａ内のリンクリスト４０に対する同一エントリ４１の重複登録を防止して１エントリ／１フローを実現できる。
【０１１３】
伝送装置３は、ＦＩＦＯ２１２Ａ内にエントリがあり、かつ、リスト操作部２２１側で処理が可能な状態の場合に、ＦＩＦＯ２１２Ａ内のエントリ４１をリンクリスト４０の適切な位置に挿入するリスト操作を実行する。その結果、伝送装置３は、リスト操作部２２１側でのリンクリスト４０に対するリスト操作の処理負担を軽減できる。
【０１１４】
伝送装置３は、リンクリスト４０内の連続するエントリ４１に境界４４を指定可能とし、境界４４、先頭４２及び最後尾４３等で区分したエントリ４１の区間を優先度として設定する。その結果、伝送装置３は、ユーザフロー単位で優先度を簡単に設定できるため、従来のＲＲ方式に比較して、優先度変更に柔軟に対応できる。しかも、伝送装置３は、優先度の変更、例えば、優先度の新規追加、削除や並び替えが生じたとしても、回路構成を変更することなく、優先度変更に柔軟に対応できる。
【０１１５】
伝送装置３は、全体リンクリストに階層毎の任意のエントリを追加可能とし、全体リンクリストを参照して全体の伝送経路は勿論のこと、逆経路も識別できる。キュー階層構造は、任意の上位階層側の接続ポートに下位階層側の接続ポートを自由に割り当て、各階層の接続数が自由で、しかも、下位階層の大小関係と上位階層の大小関係とが交差する接続関係も許容している。その結果、キュー階層構造では、例えば、連続性、接続数及び接続関係等の制約なく、複数段のキュー階層構造に柔軟に対応できる。しかも、伝送装置３は、全体リンクリスト内の先頭を参照することで、次に参照すべき接続ポートが判るため、逆引きのための変換テーブルを必要としない。
【０１１６】
伝送装置３は、リンクリスト４０内のエントリ４１のエントリ番号４１Ａ毎に前後のエントリ４１に対応した前方向ポインタ４１Ｂ及び後方向ポインタ４１Ｃを管理した。その結果、リンクリスト４０内の各エントリ４１の前方向ポインタ４１Ｂ及び後方向ポインタ４１Ｃを書き換えることでエントリ４１の並び替えのリスト操作が容易となる。
【０１１７】
伝送装置３は、同一ユーザフローの短パケットが短い間隔で入力した場合でも、固定長のクレジット量単位で管理しているため、リスト操作を最短パケットの処理時間内で終わらせる必要はなく、固定長の処理時間内で終了すれば良い。従って、パケット伝送性能の低下を防止できる。
【０１１８】
伝送装置３では、キュー選択の処理においてパケットの概念を排除し、出力キュー選択に要する時間がパケットの長さに縛られずに済む。このため回線の高速化に伴う最短パケットの処理時間の短縮に影響されることなく、高速スケジューリングを実現できる。
【０１１９】
伝送装置３は、リンクリスト４０を用いるため、リンクリスト４０を格納するリストテーブル２２２へのアクセスが複数回必要となるが、パケット単位ではなく、ユーザフロー単位で実行することになるため、アクセス回数を最小限に抑制できる。
【０１２０】
従来のＲＲ方式では、ユーザフロー数分の検索処理が必要となり、処理の高速化やユーザフロー数の増加に限界が見えていた。これに対して、本実施例では、先頭４２からリンクリスト４０内のエントリ４１を辿るだけで、ユーザフロー数が増加したとしても、次に出力可能な出力キュー３２Ａを決定するまでの処理時間に影響はなく、多フローの高速処理が可能となる。
【０１２１】
また、従来のＲＲ方式では、選択順と到着順の関係によっては、先に到着していたデータの出力が待たされることがある。これに対して、本実施例では、優先度の設定がない場合、到着順にリンクリスト４０の最後尾４３に接続されていくため、データ遅延を防止できる。
【０１２２】
従来のＲＲ方式では、キュー階層を多段で構築する場合に、例えば、連続性、接続数及び接続関係等の制約を受けながら回路構成の変更を要するため、キュー構築の柔軟性が低い。これに対して、本実施例では、全体リンクリストを用いて、全体リンクリスト内の先頭を辿っていくことで目的のユーザフローを選択できる仕組みにしている。その結果、例えば、連続性、接続数及び接続関係等が自由であるため、キュー階層構造構築の柔軟性を高めることができる。
【０１２３】
尚、本実施例の伝送装置３は、例えば、ピザボックス型の伝送装置を例示したが、例えば、伝送装置３をラインカードに搭載したシャーシ型の伝送装置にも適用可能である。
【０１２４】
伝送装置３は、ユーザフロー毎に発行するクレジット量が１０２４バイトで説明したが、少なくともキュー選択の処理に要する時間よりも大の時間をデータ換算したデータ量であれば良い。
【０１２５】
伝送装置３は、可変長のパケットを伝送するパケット伝送装置を例示したが、固定長のパケットを伝送する伝送装置にも適用可能である。更に、伝送装置３は、パケットに限定されるものではなく、例えば、可変長や固定長のデータ単位でデータを伝送する伝送装置にも適用可能である。
【０１２６】
また、図示した各部の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各部の分散・統合の具体的形態は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。
【０１２７】
更に、各装置で行われる各種処理機能は、ＣＰＵ（Central  Processing  Unit）（又はＭＰＵ（Micro  Processing  Unit）、ＭＣＵ（Micro  Controller  Unit）等のマイクロ・コンピュータ）上で、その全部又は任意の一部を実行するようにしても良い。また、各種処理機能は、ＣＰＵ（又はＭＰＵ、ＭＣＵ等のマイクロ・コンピュータ）で解析実行するプログラム上、又はワイヤードロジックによるハードウェア上で、その全部又は任意の一部を実行するようにしても良いことは言うまでもない。
【０１２８】
ところで、本実施例で説明した各種の処理は、予め用意されたプログラムを伝送装置に組み込むことでも実現できる。そこで、以下では、上記実施例と同様の機能を有するプログラムを実行する伝送装置の一例について説明する。図２１は、伝送プログラムを実行する伝送装置２００を示す説明図である。
【０１２９】
図２１において伝送プログラムを実行する伝送装置２００では、通信インタフェース２０１と、ＲＯＭ２０２と、ＲＡＭ２０３と、ＣＰＵ２０４とを有する。
【０１３０】
そして、ＲＯＭ２０２には、上記実施例と同様の機能を発揮する伝送プログラムが予め記憶されている。尚、ＲＯＭ２０２ではなく、図示せぬドライブで読取可能な記録媒体に伝送プログラムが記録されていても良い。また、記録媒体としては、例えば、ＣＤ−ＲＯＭ、ＤＶＤディスク、ＵＳＢメモリ、ＳＤカード等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ等でも良い。また、伝送プログラムは、ネットワークを介して通信可能な記憶装置から取得されても良い。伝送プログラムとしては、図２１に示すように、格納プログラム２０２Ａ、発行プログラム２０２Ｂ及び出力制御プログラム２０２Ｃである。尚、プログラム２０２Ａ、２０２Ｂ及び２０２Ｃについては、適宜統合又は分散しても良い。
【０１３１】
そして、ＣＰＵ２０４は、これらのプログラム２０２Ａ、２０２Ｂ及び２０２ＣをＲＯＭ２０２から読み出し、これら読み出された各プログラムを実行する。そして、ＣＰＵ２０４は、格納プロセス２０４Ａ、発行プロセス２０４Ｂ及び出力制御プロセス２０４Ｃとして機能する。ＲＡＭ２０３には、ユーザフローの出力順序を示すリンクリストが記憶されている。
【０１３２】
ＣＰＵ２０４は、ユーザフロー毎にＲＡＭ２０３内のキューを有し、入力したデータを、当該データが属するユーザフローに対応したキューに格納する。ＣＰＵ２０４は、ユーザフローの出力順序を示すリンクリストを参照してユーザフローに対応したキューに所定の出力許可量を発行する。ＣＰＵ２０４は、出力許可量が発行されたキューからデータをデータ単位で出力する。その結果、伝送装置２００は、データ伝送性能の低下を防止できる。
【符号の説明】
【０１３３】
３  伝送装置
３２  バッファ
３２Ａ  出力キュー
３３  出力制御部
３３Ａ  クレジットカウンタ
４０  リンクリスト
４１  エントリ
４２  先頭
４３  最後尾
４４  境界
２１１Ａ  キュー長カウンタ
２１２  要求判定部
２１２Ａ  ＦＩＦＯ
２２１  リスト操作部
２２２  リストテーブル
２２４  発行部
【図１】
2015091061.tif 000003
【図２】
2015091061.tif 000004
【図３】
2015091061.tif 000005
【図４】
2015091061.tif 000006
【図５】
2015091061.tif 000007
【図６】
2015091061.tif 000008
【図７】
2015091061.tif 000009
【図８】
2015091061.tif 000010
【図９】
2015091061.tif 000011
【図１０】
2015091061.tif 000012
【図１１】
2015091061.tif 000013
【図１２】
2015091061.tif 000014
【図１３】
2015091061.tif 000015
【図１４】
2015091061.tif 000016
【図１５】
2015091061.tif 000017
【図１６】
2015091061.tif 000018
【図１７】
2015091061.tif 000019
【図１８】
2015091061.tif 000020
【図１９】
2015091061.tif 000021
【図２０】
2015091061.tif 000022
【図２１】
2015091061.tif 000023