(57)【要約】各同期フロー（ｉ＝１，２，．．．，ＮＳ）は、サーバーが先に進む前に非同期フローがサービスを受けることができる期間に関係したそれぞれの同期容量値（Ｈｉ）に関連付けられる。この値は、ローカル割当基準又はグローバル割当基準に従って選択することができる。各非同期フロー（ｉ＝１，２，．．．，ＮＡ）は、それぞれの待ち行列がサービスを受ける権利を有するように実施されるべき遅延を示すそれぞれの第１値、及びサーバーが前のサイクルにてそれぞれの待ち行列にアクセスした瞬間を示す別の値に関連付けられる。次に、非同期フロー（ｈ）に関連した各待ち行列は、前記同期容量値に関係した期間の間サービスを受け、一方、非同期フロー（ｉ）に関連した各待ち行列は、予想される時間の前にサーバーのアクセスが行われた場合にのみ、サービスを受ける。利用可能なリソースの使用を最適化するためには、同期待ち行列へのサーバーのアクセス（１０）は、連続した２サイクル中に行うのが好ましい。
2005522946.tif 000002
【特許請求の範囲】
【請求項１】
それぞれの関連待ち行列を生成する複数の情報パケットフロー間で共用されるサービスリソースのスケジューリング手順であって、前記フローは、保証された最小サービス率（ｒｉ）を要求する同期フロー（ｉ＝１，２，．．．，ＮＳ）と、同期フローにより使用されずに残った前記リソースのサービス容量を使用する非同期フロー（ｊ＝１，２，．．．，ＮＡ）とを含み、該手順はサーバー（１０）を利用し、かつ以下の操作、すなわち
-  サーバー（１０）が前記それぞれの待ち行列へのアクセスサイクルを完了するのに必要な時間を特定する目標回転時間値（ＴＴＲＴ）に基づいて、前記サーバー（１０）が前記フロー（ｉ，ｊ）に関連したそれぞれの待ち行列を連続サイクルにてアクセスするようにし、
-  各同期フロー（ｉ）を、サーバーが先に進む前にそれぞれの同期フローがサービスを受けることができる最大期間を示すそれぞれの同期容量値（Ｈｉ）と関連付け、
-  各非同期フロー（ｊ）を、それぞれの待ち行列がサービスを受ける権利を有するように設定しなければならない値を特定する夫々の第１遅延値（Ｌｊ）と、前のサイクルにおいてサーバー（１０）がそれぞれの待ち行列にアクセスした瞬間を示す夫々の第２値（ｌａｓｔ＿ｖｉｓｉｔ＿ｔｉｍｅ）に関連付け、前記それぞれの待ち行列に対してサーバーの前のアクセスからの経過時間を求め、
-  同期容量（Ｈｉ）の前記夫々の値に対して最大サービス時間の間、同期フロー（ｉ）に関連した各待ち行列にサービスを行い、そして
-  予想される瞬間に先行してサーバー（１０）のアクセスが行われた場合にのみ、非同期フロー（ｊ）に関連した各待ち行列にサービスを行い、この先行は、前記目標回転時間値（ＴＴＲＴ）とサーバー（１０）の前のアクセスからの経過時間及び累積遅延との差として求められ、もし正ならば、この差が各非同期待ち行列の最大サービス時間を定める、
操作を含み、前記手順はまた、ｉ番目の同期フローに関連した待ち行列の前記それぞれの同期容量値（Ｈｉ）を、以下の事項、すなわち
-ｉ）次式
【数１】
2005522946.tif 000028
-ｉｉ）また、次式の少なくとも１つ
【数２】
2005522946.tif 000029
及び
【数３】
2005522946.tif 000030
ここで、
-  Ｈｉは、ｉ番目の同期フローに関連した待ち行列の前記それぞれの同期容量値（Ｈｉ）であり、
-  総和は、ＮＳに等しい総ての同期フローに亘ってとり、
-  ＮＡは、前記非同期フローの数であり、
-  τｍａｘは、前記共用サービスリソースによる最長パケットサービスの期間であり、
-  ＴＴＲＴは、前記目標回転時間値であり、
-  Ｃは、前記共用サービスリソースのサービス容量であり、
-  ｒｉは、ｉ番目の同期フローにより要求される最小サービス率であり、次式を満たし、
【数４】
2005522946.tif 000031
-  αは、次式を与えるパラメータである、
【数５】
2005522946.tif 000032
を満たすことによって定める操作をも含む前記手順。
【請求項２】
前記連続サイクルの各サイクル中、前記サーバー（１０）が、前記同期フロー（ｉ＝１，２，．．．，ＮＳ）に関連する総ての待ち行列に二重スキャンを実行し、次いで前記非同期フロー（ｊ＝１，２，．．．，ＮＡ）に関連した待ち行列にアクセスすることを特徴とする請求項１に記載の手順。
【請求項３】
-  各同期フロー（ｉ）に対し、それぞれのフローに利用可能なサービス時間量を示す別の値（Δｉ）を関連付ける操作、
-  前記二重スキャンの大サイクル中、最大の前記別の値（Δｉ）に等しい期間の間、同期フロー（ｉ）に関連した各待ち行列にサービスを行う操作、及び
-  前記二重スキャンの小サイクル中、前記別の値（Δｉ）が厳密に正ならば、同期フロー（ｉ）に関連した各待ち行列のただ１つのパケットにサービスを行う操作、
を含むことを特徴とする請求項２に記載の手順。
【請求項４】
前記二重スキャンの大サイクル中に待ち行列がアクセスされるとき、同期容量（Ｈｉ）の前記それぞれの値だけ前記別の値（Δｉ）をインクリメントする操作を含むことを特徴とする請求項３に記載の手順。
【請求項５】
サービスを受けた各パケットだけ伝送時間の前記別の値（Δｉ）をデクリメントする操作を含むことを特徴とする請求項３又は４に記載の手順。
【請求項６】
前記二重スキャンの大サイクル中、同期フロー（ｉ）に関連した各待ち行列のサービスが、以下の条件、すなわち、
-  待ち行列が空である、
-  前記別の値（Δｉ）により表される利用可能な時間が、待ち行列の最前部のパケットにサービスを行うには十分でない、
のうちの１つが生じたときに終了することを特徴とする請求項３〜５のいずれか一項に記載の手順。
【請求項７】
それぞれの待ち行列が空のとき、前記別の値（Δｉ）をリセットする操作を含むことを特徴とする請求項６に記載の手順。
【請求項８】
前記二重スキャンの小サイクル中に所与のサービスの存在下、前記別の値（Δｉ）のサービス時間をデクリメントする操作を含むことを特徴とする請求項３〜７のいずれか一項に記載の手順。
【請求項９】
前記同期フロー（ｉ）に関連した総ての待ち行列の前記二重スキャン中、前記小サイクルが、以下の条件、すなわち
-  同期フロー（ｉ）に関連した最後の待ち行列がアクセスされたこと、
-  前記同期フロー（ｉ）に関連した総ての待ち行列の容量（Ｈｉ）の合計以上の期間が、前記二重スキャンの前記大サイクルの開始から経過したこと、
のうちの１つが満たされるときに終了することを特徴とする請求項３〜８のいずれか一項に記載の手順。
【請求項１０】
前記別の値（Δｉ）をゼロに初期化する操作を含むことを特徴とする請求項３〜９のいずれか一項に記載の手順。
【請求項１１】
前記差が負の場合、非同期フロー（ｊ）に関連した各前記待ち行列がサービスを受けず、前記差の値が前記遅延（Ｌｊ）と累積されることを特徴とする請求項１〜１０のいずれか一項に記載の手順。
【請求項１２】
非同期フロー（ｊ）に関連した待ち行列のサービスは、以下の条件、すなわち
-  待ち行列が空である、
-  利用可能な時間が、待ち行列の最前部にあるパケットを伝送するのに十分でない、
のうちの１つが満たされたときに終了することを特徴とする請求項１〜１１のいずれか一項に記載の手順。
【請求項１３】
前記それぞれの第１値（Ｌｊ）及び前記それぞれの第２値（ｌａｓｔ＿ｖｉｓｉｔ＿ｔｉｍｅ）が、当該フローが始動されるとき、それぞれゼロ及び現在のサイクルの開始の瞬間に初期化されることを特徴とする請求項１〜１２のいずれか一項に記載の手順。
【請求項１４】
それぞれの関連の待ち行列を生成する複数の情報パケット間で共用されるサービスリソースのスケジューリングシステムであって、前記フローが、保証された最小サービス率を要求する同期フロー（ｉ＝１，２，．．．，ＮＳ）と、同期フローにより使用されずに残った前記リソースのサービス容量を使用するようにされた非同期フロー（ｊ＝１，２，．．．，ＮＡ）を含み、該システムはまた、連続サイクルにて前記フロー（ｉ，ｊ）に関連したそれぞれの待ち行列にアクセスすることができるサーバー（１０）を備え、該サーバーは、以下の操作、すなわち、
-  サーバー（１０）が前記それぞれの待ち行列のアクセスサイクルを完了するのに必要な時間を特定する目標回転時間値（ＴＴＲＴ）を求める操作、
-  各同期フロー（ｉ）に対し、次に進む前に同期フローがサービスを受けることができる最大時間量を示すそれぞれの同期容量値（Ｈｉ）を関連付ける操作、
-  各非同期フロー（ｊ）に対し、それぞれの待ち行列がサービスを受ける権利を有するべく為されなければならない遅延を特定する夫々の第１遅延値（Ｌｊ）、及び、前のサイクル中にサーバー（１０）がそれぞれの待ち行列にアクセスした瞬間を示す夫々の第２値（ｌａｓｔ＿ｖｉｓｉｔ＿ｔｉｍｅ）を関連付け、前記それぞれの待ち行列について、サーバー（１０）の前のアクセスからの経過時間を求める操作、
-  前記それぞれの同期容量値（Ｈｉ）に関係した最大期間の間、同期フロー（ｉ）に関連した各待ち行列にサービスを行う操作、及び
-  予想される瞬間に先行してサーバー（１０）のアクセスが行われた場合にのみ、非同期フロー（ｊ）に関連した各待ち行列にサービスを行う操作であって、この先行は、前記目標回転時間（ＴＴＲＴ）とサーバー（１０）の前のアクセスからの経過時間及び累積遅延との差として求められ、もし正ならば、この差が各前記非同期待ち行列の最大サービス時間を定める前記操作
を実行するように構成され、
該システムは、以下の事項、すなわち
-  ｉ）次式、
【数６】
2005522946.tif 000033
-  ｉｉ）加えて次式のうちの少なくとも１つ、
【数７】
2005522946.tif 000034
及び
【数８】
2005522946.tif 000035
ここで、
-  Ｈｉは、ｉ番目の同期フローに関連した待ち行列についての前記それぞれの同期容量値（Ｈｉ）であり、
-  総和は、ＮＳに等しい全同期フローに亘ってとられ、
-  ＮＡは、前記非同期フローの数であり、
-  τｍａｘは、前記共用サービスリソースによる最長パケットのサービス期間であり、
-  ＴＴＲＴは、前記目標回転時間値であり、
-  Ｃは、前記共用サービスリソースのサービス容量であり、
-  ｒｉは、ｉ番目の同期フローにより要求される最小サービス率であり、
【数９】
2005522946.tif 000036
を満たし、
−  αは、
【数１０】
2005522946.tif 000037
を与えるパラメータである、
を満足すべく、ｉ番目の同期フローに関連した待ち行列に対して前記それぞれの同期容量値（Ｈｉ）を定めるように構成されている前記システム。
【請求項１５】
前記連続サイクルの各サイクル中、前記サーバー（１０）が、前記同期フロー（ｉ＝１，２，．．．，ＮＳ）に関連した総ての待ち行列に二重スキャンを行い、次いで前記非同期フロー（ｊ＝１，２，．．．，ＮＡ）に関連した待ち行列にアクセスすることを特徴とする請求項１４に記載のシステム。
【請求項１６】
-  それぞれのフローに利用可能なサービス時間量を示す別の値（Δｉ）が、各同期フロー（ｉ）に関連付けられており、
-  前記二重スキャンの大サイクル中、同期フロー（ｉ）に関連した各待ち行列が、最大の別の値（Δｉ）に等しい期間の間、サービスを受け、
-  前記二重スキャンの小サイクル中、該システムが、前記別の値（Δｉ）が厳密に正の場合に同期フロー（ｉ）に関連した各待ち行列のただ１つのパケットにサービスを行う、
ことを特徴とする請求項１５に記載のシステム。
【請求項１７】
二重スキャンの大サイクル中に待ち行列がアクセスされたとき、前記別の値（Δｉ）が前記それぞれの同期容量値（Ｈｉ）だけインクリメントされることを特徴とする請求項１６に記載のシステム。
【請求項１８】
前記別の値（Δｉ）が、サービスされる各パケットの伝送時間だけデクリメントされることを特徴とする請求項１６又は１７に記載のシステム。
【請求項１９】
前記二重スキャンの大サイクル中、同期フロー（ｉ）に関連した各待ち行列のサービスが、以下の条件、すなわち
-  待ち行列が空であること、
-  前記別の値（Δｉ）により表される利用可能な時間が、待ち行列の最前部のパケットにサービスを行うのに十分でないこと、
のうちの１つが生じたときに終了するように構成されることを特徴とする請求項１６〜１８のいずれか一項に記載のシステム。
【請求項２０】
それぞれの待ち行列が空のとき、前記別の値（Δｉ）がリセットされることを特徴とする請求項１９に記載のシステム。
【請求項２１】
前記二重スキャンの小サイクル中に与えられたサービスの存在下、前記別の値（Δｉ）がサービス時間量だけデクリメントされることを特徴とする請求項１６〜２０のいずれか一項に記載のシステム。
【請求項２２】
前記同期フロー（ｉ）に関連した総ての待ち行列についての前記二重スキャン中、前記小サイクルが、以下の条件、すなわち
-  同期フロー（ｉ）に関連した最後の待ち行列がアクセスされたこと、
-  前記同期フロー（ｉ）に関連した総ての待ち行列の容量（Ｈｉ）の合計以上の期間が、前記二重スキャンの前記大サイクルの開始から経過したこと、
のうちの１つが満たされたときに終了することを特徴とする請求項１６〜２１のいずれか一項に記載のシステム。
【請求項２３】
前記別の値（Δｉ）がゼロに初期化されることを特徴とする請求項１６〜２２のいずれか一項に記載のシステム。
【請求項２４】
もし前記差が負ならば、非同期フロー（ｊ）に関連した各前記待ち行列はサービスを受けず、前記差の値が前記遅延（Ｌｉ）と累積されることを特徴とする請求項１６〜２３のいずれか一項に記載のシステム。
【請求項２５】
非同期フロー（ｊ）に関連した待ち行列のサービスは、以下の条件、すなわち
-  待ち行列が空である、
-  利用可能な時間が、待ち行列の最前部にあるパケットを伝送するのに十分でない、
のうちの１つが満たされたときに終了することを特徴とする請求項１４〜２４のいずれか一項に記載のシステム。
【請求項２６】
当該フローが始動させられたとき、前記それぞれの第１値（Ｌｊ）と前記それぞれの第2値（ｌａｓｔ＿ｖｉｓｉｔ＿ｔｉｍｅ）が、それぞれゼロ及び現在のサイクルの開始の瞬間に初期化されることを特徴とする請求項１４〜２５のいずれか一項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信システムに関し、特に、共用リソースのスケジューリング基準、すなわち発生時間ごとにリソースを割り付けるべきパケットを選択するのに使用される基準に関する。
【背景技術】
【０００２】
本発明において与えられる解決策は、無線リソーススケジューリング（例えば、ＭＡＣすなわち媒体アクセス制御レベルスケジューリング）と、ネットワークノードにおける計算及び伝送用リソースのスケジューリング、例えば、インターネットプロトコルルータ（ＩＰ）上での異なるサービス品質を有するフロースケジューリングの両方のために開発された。以下の説明は、後者の用途例に基づいてはいるが、単に例として与えられたものであり、本発明の範囲を制限するものではない。
【０００３】
序文
ここ数年の間での、パケットネットワークの広範囲な適用と急速な発展により、旧世代のパケットネットワークにより提供される従来のサービス（電子メール、ネットサーフィンなど）と、回線交換ネットワークのために事前に用意された新しいサービス（リアルタイムビデオ、電話技術など）とをいわゆる統合サービスネットワークに統合するという問題が生じた。
【０００４】
例えば固定したパケットネットワークコンポーネント（コアネットワーク）が想定されるＵＭＴＳのようなシステムは、同時に音声とデータのサービスを取り扱い、リアルタイムであろうとなかろうと新しいサービスのサポートを提供しなければならない。
【０００５】
よって、この統合サービスネットワークは、様々な特性のトラヒックフローを取り扱うことができ、かつ、適切なサービスの品質を、すなわち、合意した期間内は保証されなければならないユーザーとサービス提供者の間で取り決められた１組の性能指数を、各種のフローに提供できなければならない。
【０００６】
要求されるサービスの品質を提供する上で重要な要素の一つは、ネットワークノード上にて実現されるスケジューリングシステム、すなわち、伝送すべきパケットをノード上に存在するものから選択するのに用いるシステムである。よって、明らかに、このシステムは、様々な種類のサービスを提供する能力に関する柔軟性、単純性、すなわち、高い伝送速度と多くの伝送フローの取り扱いが要求される環境における使用を可能にする特性、共用リソース（例えば伝送手段）の使用における効率性などのような対照的な特性を具体化しなければならない。
【０００７】
例えば文献ＵＳ-Ａ-６０９１７０９、ＵＳ-Ａ-６１４７９７０又はＥＰ-Ａ-１０３５７５１から分かるように、パケットネットワークにおけるサービスの品質（すなわちＱＯＳ）の所与のレベルを保証するニーズは、絶えず強まっている。
【０００８】
実際、本発明は、産業上の発明の特許出願ＴＯ２０００Ａ００１０００及び対応する出願ＰＣＴ／ＩＴ０１／００５３６に記載された解決策の発展したものである。
【０００９】
基本的に、以前の解決策は、複数の情報パケットフロー間で共用されるサービスリソースのスケジューリングに適用される、その際、これらの情報パケットフローが、それぞれの関連の待ち行列を発生させ、サーバーが伝送の許可を与えたときにサービスを受ける。
【００１０】
当該フローは、最小サービス率の保証を要求する同期フローと、同期フローにより使用されずに残っているリソースのサービス容量を用いる非同期フローとに分割される。当該解決策は、以下の事項を含む：
-  連続サイクルにて当該フローに関連した待ち行列にアクセスするサーバーを提供し、各待ち行列に対し、サーバーが待ち行列のアクセスサイクルを完了するのに要する時間を特定するＴＴＲＴと称する目標トークン回転時間（又は「循環（ｒｅｖｏｌｕｔｉｏｎ）」）を認め、
-  各同期フローを、伝送許可がサーバーにより取り消される前に同期フローがサービスを受けることができる最大時間を示す同期容量値と関連付け、
-  各非同期フローを、サービスを受ける権利をそれぞれの待ち行列が有するように実施されなければならない遅延を示す第１遅れ（ｉ）値と、前のサイクルにおいてサーバーがそれぞれの待ち行列にアクセスした瞬間を示す別の値（ＬＡＳＴ＿ＴＯＫＥＮ＿ＴＩＭＥ）とを加えたもの（これはサーバーの前のアクセスからの経過時間を決める）に関連付け、
-  上記同期容量値に等しい最大期間の間、同期フローに関連した各待ち行列にサービスを行い、そして
-  予想される瞬間に先行してサーバーのアクセスが行われた場合にのみ、非同期フローに関連した各待ち行列にサービスを行う。この先行は、前記ＴＴＲＴ時間とサーバーの前のアクセスからの経過時間及び累積遅延との差から得られる。
【００１１】
この差が正ならば、この差が、非同期フローに関連した各待ち行列に対する最大サービス時間を定める。
【００１２】
上述した解決策は、運転上の観点から完全に満足のいくものであると分かった。しかしながら、「出願人」により得られたこの経験は、さらにこの解決策を発展させ、本願発明において説明するように改善することができることを示している。
【００１３】
特に、このことは、以下の面に当てはまる。
-  計算コストを低く保ちつつ異なる種類のサービスを提供する可能性。これは、Ｉｎｔｓｅｒｖ（ＩＥＴＦ規格による統合サービス）若しくはＤｉｆｆｓｅｒｖ（ＩＥＴＦ規格による差別化統合サービス）を有するＩＰネットワークのような、ユーザーにサービスの品質を保証しなければならないコンピュータネットワーク用途の場合、又はＭＡＣレベルスケジューリングアルゴリズムなどのような無線リソーススケジューリングシステム（Ｗ-ＬＡＮシステム、第３世代無線モバイルサービス）の場合には重要な特徴である。
-  同期トラヒックのために、種々のフローのビットレート、最大待ち遅延及び各フローのバッファの最大占有を保証する可能性。
-  特にサービス統合ネットワークにおいて、レートの保証され（同期フローに適する）、公平な待ちの（非同期フローに適する）、２つの種類のサービスを同時に提供する能力に関する柔軟性。
-  伝送フローを分離する可能性。すなわち、これは、単一のフローに提供されるサービスを、他のフローの存在及び挙動から独立させる。
-  伝送されるべきパケットを選択するのに必要な操作の数の観点において計算が複雑でないこと。この特徴により、ハードウエアでの可能な実現性をも考慮すると、高い伝送速度と多くの伝送フローの取り扱いが要求される環境において使用できる。
-  複雑な手順を用いることなくそのリソースを再分配することによって動作パラメータ（例えば、存在するフローの数）の変化を取り扱うことができるという意味における適応性。
-  分析的記述可能性（ｄｅｓｃｒｉｂａｂｉｌｉｔｙ）。すなわち、これはシステムの挙動の完全な分析的記述を与え、これにより、サービスの品質の測定値をシステムパラメータに関係付けることができる。
【００１４】
別の重要な面は、公平性、すなわち、レート保証されたサービスを受ける伝送フローと、公平な待ちサービスを受ける伝送フローとの両方を同様に管理し、異なる長さのパケットの存在下でさえ、要求されるサービスに比例したサービスレベルを各々のものに与える可能性である。
【特許文献１】ＵＳ-Ａ-６０９１７０９
【特許文献２】ＵＳ-Ａ-６１４７９７０
【特許文献３】ＥＰ-Ａ-１０３５７５１
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の説明
本発明の目的は、上述した面に特に留意しつつ上記公知の解決策をさらに発展させることである。
【課題を解決するための手段】
【００１６】
本発明によると、この目的は、特に特許請求の範囲に述べた特徴を有するスケジューリング手順を用いることにより達成し得る。
【００１７】
本発明はまた、関連のシステムにも関する。
【００１８】
要するに、本発明で与えられる解決策は、本特許出願において導入された名称、Pａｃｋｅｔ  Tｉｍｅｄ  Tｏｋｅｎ  Sｅｒｖｉｃｅ  DｉｓｃｉｐｌｉｎｅすなわちＰＴＴＳＤにより定めることができるスケジューリングシステムを操作する。
【００１９】
現在、このスケジューリングシステムは、パケット-コンピュータネットワーク切換ノード上にて働くように設計され、また、１つの伝送チャンネルを複数の伝送フローに多重化することができる。
【００２０】
本システムは、２つの異なる種類のサービス、すなわち、最小サービス率の保証を要求する伝送フローに適したレート保証されたサービス（以下「同期フロー」という）と、最小サービス率の保証は要求しないが、利用可能なより大きな伝送容量の恩恵を受ける伝送フローに適した公平な待ちサービス（以下「非同期フロー」という）とを提供する。しかしながら、本システムは、同期フローにより使用されない伝送容量の平等な共用にて後者を提供する。
【００２１】
当該ノード上の各伝送フロー入力からのトラヒックが、それ自身の待ち行列（同期又は非同期待ち行列）中に挿入され、それから取り出されて伝送される。サーバーは、固定した周期的な順序にて待ち行列にアクセスし、各アクセス時での正確なタイミング制約に従って設定されたサービス時間を各待ち行列に認可する。
【００２２】
サーバーは、まず、１回転中に２回ほど同期待ち行列にアクセスすることで、大サイクル及び小又は回復サイクルを完了し、次いで先に進んで非同期待ち行列にアクセスする。
【００２３】
図面の簡単な説明
本発明の以下の説明は、添付図面に関して非制限的な例として与えられており、添付図面には、本発明に従って作動するシステムの動作基準を説明する１つのブロック図が含まれる。
【発明を実施するための最良の形態】
【００２４】
本発明で与えられるスケジューリングシステムは、１つの伝送チャンネルを複数の伝送フローに多重化することができる。
【００２５】
本システムは、２つの異なる種類のサービス、すなわち、最小サービス率の保証を要求する伝送フローに適したレート保証されたサービス（以下、ｉ同期フロー、ここでｉ＝１，２，．．．，ＮＳ）と、サービス率の保証は要求しない伝送フローに適したベストエフォート（ｂｅｓｔ-ｅｆｆｏｒｔ）サービス（以下ｊ非同期フロー、ここでｊ＝１，２，．．．，ＮＡ）とを提供する。しかし、本システムは、同期フローにより使用されない伝送容量の平等な共用にて後者を提供する。
【００２６】
ＮＳとＮＡは負でない整数であり、各同期フローｉ＝１．．．ＮＳはｒｉに等しいサービス率を要求し、同期フローにより要求されるサービス率の合計がチャンネル容量Ｃを越えないこと
【数１】
2005522946.tif 000003
が仮定される。
【００２７】
当該ノード上の各伝送フロー入力からのトラヒックは、それ自身の待ち行列（後に説明する同期又は非同期待ち行列）に挿入され、そこから取り出されて伝送される。サーバー１０は、固定した周期的な順序にて（図面中にて軌道Ｔと矢印Aで理想的に示されている）待ち行列にアクセスし、各アクセス時での正確なタイミング制約に従って設定されるサービス待ち時間を各待ち行列に認可する。
【００２８】
本発明において参照される手順は、初期化段階とその後の待ち行列への周期的なアクセスとを含む。これらの手順は後に説明する。
【００２９】
初期化
まず、動作条件に関する情報、すなわち、いくつの同期フローが存在するのか（一般にはＮＳ）、どれだけの伝送速度が各同期フローにより要求されるか、いくつの非同期フローが存在するか、目標回転時間（ＴＴＲＴ）、すなわちサーバーがすべての待ち行列を１回アクセスする完全な１サイクルはどのくらいの長さ存続するか、をシステムに与える必要がある。
【００３０】
同期フロー
各同期フローｉ，ｉ＝１．．．ＮＳは、適当な割当方針に従って、サーバーが伝送許可を取り除く前に同期フローのトラヒックが伝送され得る最大時間を示す変数Ｈｉ（同期容量）に関連付けられる。可能な割当方針は後に説明する。変数Δｉ（初めはゼロ）が、各同期フローに関連付けられ、当該フローに利用可能な伝送時間量を記憶する。
【００３１】
非同期フロー
各非同期フローｊ，ｊ＝１．．．ＮＡは、２つの変数Ｌｉ及びｌａｓｔ＿ｖｉｓｉｔ＿ｔｉｍｅｊに関連する。第１の変数は、非同期待ち行列がサービスを受ける権利を有するために実施されなければならない遅延又は遅れを記憶する。第２の変数は、前のサイクルにおいてサーバーが非同期待ち行列ｊにアクセスした瞬間を記憶する。これらの変数はそれぞれ、ゼロに、及びフローが始動させられたとき進行中の回転（ｒｅｖｏｌｕｔｉｏｎ）の瞬間に初期化される。
【００３２】
この手順の方法は、必ずしもシステムの立ち上げ時でなくてもいつでも非同期フローを始動できることを意味している。
【００３３】
大サイクル中での一般同期待ち行列ｉ（ｉ＝１．．．ＮＳ）へのアクセス
同期待ち行列は、変数Δｉの最大値に等しい期間の間サービスを受けることができる。この変数は、待ち行列が大サイクル中にアクセスされるときＨｉ（初期化中に決められる値）だけインクリメントされ、伝送される各パケットの伝送時間だけデクリメントされる。
【００３４】
大サイクル中の待ち行列のサービスは、待ち行列が空のとき（この場合には変数Δｉはリセットされる）、又は利用可能な時間（Δｉの現在の値により表される）が待ち行列の最前部にあるパケットを伝送するのに十分でないとき、終了する。
【００３５】
小サイクル中での一般同期待ち行列ｉ（ｉ＝１．．．ＮＳ）へのアクセス
小（又は回復）サイクル中、同期待ち行列は、変数Δｉが厳密に正の値を有するという条件で１つのパケットのみを伝送することができる。もし伝送が行われるならば、変数Δｉは当該伝送時間だけデクリメントされる。
【００３６】
一般非同期待ち行列ｊ（ｊ＝１，．．．，ＮＡ）へのアクセス
非同期待ち行列は、予想される瞬間より前にサーバーのアクセスが行われた場合にのみ、サービスを受けることができる。サーバーのアクセスが先行しているか否かを計算するために、前のアクセスからの経過時間と累積遅延Ｌｊを目標回転時間ＴＴＲＴから差し引く。
【００３７】
もしこの差が正ならば、これが、非同期待ち行列ｊがサービスを受ける権利を有する期間であり、この場合、変数Ｌｊはリセットされる。
【００３８】
もしこの差が負ならば、サーバーが遅れており、待ち行列ｊはサービスを受けることができず、この場合、その遅延が変数Ｌｊに記憶される。非同期待ち行列サービスは、待ち行列が空のとき、又は利用可能な時間（これはパケットが伝送される度にデクリメントされる）が、待ち行列の最前部にあるパケットを伝送するには十分でないとき、終了する。
【００３９】
１回転中のアクセスシーケンス
１回転中にすべての同期待ち行列（大及び小サイクル）に二重スキャンが実施され、次に非同期待ち行列にアクセスされる。小サイクルは、次の事象の一つが発生したときに終了する：
-  最後の同期待ち行列にアクセスされたこと、
-  大サイクルの開始から総ての同期待ち行列の容量の合計以上の期間が経過したこと。
【００４０】
分析的保証
同期容量は、常に検証されなければならない次の不等式により、目標回転時間ＴＴＲＴ、及び最長パケットの伝送期間τｍａｘに結合される。
【数２】
2005522946.tif 000004
【００４１】
同期フローの最小伝送速度
仮定（１）において、ここに記載のシステムは、以下の標準化された伝送速度が各同期フローに対して保証されることを保証する。
【数３】
2005522946.tif 000005
ここで、
Ｘｉ＝Hｉ／ＴＴＲＴ
α＝τｍａｘ／ＴＴＲＴ
であり、一般同期待ち行列ｉが決して空ではない任意の期間［ｔ１，ｔ２］が与えられた場合に［ｔ１，ｔ２］において待ち行列ｉから受け取ったサービス時間Ｗｉ（ｔ１，ｔ２）が次の不等式を満たすことをも保証できる。
【数４】
2005522946.tif 000006
ここで、
【数５】
2005522946.tif 000007
であり、τｉは、フローｉの最長パケットの伝送時間である。
【００４２】
上記式（２）は、ここに記載の種類のｉ同期フローシステムにより供給されるサービスが、本発明で示したシステムにより管理されるチャンネルの容量のγｉ倍に等しい容量を有するプライベート伝送チャンネルの唯一のオーナーであったならば、同じフローが経験するであろうようなサービスとはΛｉより大きく相違することを明らかにする。よって、Λｉは、理想的な状況に対する最大サービス差を表す。
【００４３】
よって、同期フローは、次の通り計算されるレイテンシー（ｌａｔｅｎｃｙ）と称されるパラメータを特徴とし得る。
【数６】
2005522946.tif 000008
又は、ＮＡ→∞の場合
【数７】
2005522946.tif 000009
【００４４】
ここに記載の解決策を実施する切換ノードが与えられたなら、当該ノード上での同期フロー上のトラヒック入力が、パラメータ（σ，ρ）のいわゆる「漏れバケツ（ｌｅａｋｙ-ｂｕｃｋｅｔ）」により制限される場合に、以下の保証を与えることができる。
ａ）同期フローの単一ノード上での最大遅延
各パケットは、
【数８】
2005522946.tif 000010
以下の遅延を有する。
ｂ）同期フローのノード上での最大メモリ占有
同期フローパケットにおけるパケットにより占有されたメモリ量は、
【数９】
2005522946.tif 000011
である。
ｃ）同期フローのＮノードのルート上での最大遅延
Φ１．．．ΦＮ  Ｎをここに記載のシステムを実現する切換ノードとし、
【数１０】
2005522946.tif 000012
をΦｊノードの各々につき計算したレイテンシーとし、
【数１１】
2005522946.tif 000013
とする。
【００４５】
この場合、第１ノード上のトラヒック入力がパラメータ（σ，ρ）の漏れバケツにより制限されると仮定すると、Ｎノードと交差するパケットの最大遅延に対する上限を定めることができ、この制限は、
【数１２】
2005522946.tif 000014
である。
【数１３】
2005522946.tif 000015
なる値を、３つの保証ａ）、ｂ）、ｃ）の各々において用いることができ、このことは、アクティブな非同期フローの数に依存しない制限を計算することができることを意味する。
【００４６】
パラメータ選択
同期フローが要求されるもの以上の最小サービス率を受けることを保証する能力は、同期容量Ｈｉ，ｉ＝１．．．ＮＳの正しい選択に付随している。各同期フローｉが最小伝送速度ｒｉを要すると仮定すると、次の不等式を満たすべく同期容量を割り当てる必要がある。
【数１４】
2005522946.tif 000016
ここに記載の解決策は、それぞれローカル割付及びグローバル割付と称される２つの異なるスキームに従って同期容量を割り当てる。
【００４７】
ローカル割当
同期容量は次のように選択される。
【数１５】
2005522946.tif 000017
【００４８】
この様にして、もし要求される伝送速度が次の不等式を満たすならば、不等式（１）が満たされる。
【数１６】
2005522946.tif 000018
【００４９】
各同期フローは、次式に等しい標準化されたサービス率が保証される。
【数１７】
2005522946.tif 000019
【００５０】
式（５）により与えられたγｉの値は、不等式（３）を満たす。
【００５１】
グローバル割当
ＮＡ＞０を要求するこのスキームに従って、同期容量が次のようにして選択される。
【数１８】
2005522946.tif 000020
【００５２】
グローバル割当スキームでは、要求される伝送速度の合計はまた、不等式（４）より小さいままでなければならない。もし（４）が満たされたなら、同期したフローの標準化サービス率は、γｉ＝ｒｉ／Ｃとなる。
【００５３】
グローバルスキームは、より少ない容量を同期フローに割り当て、非同期フロー伝送に対してより広いバンド幅を残すという点において、チャンネルの伝送容量の使用がローカルスキームよりも多いことを保証する。
【００５４】
一方、グローバルスキームの使用は、システム内に存在するフロー（同期又は非同期）の数が変わる度に、すべての同期容量が再計算されることを意味するが、しかし、ローカルスキームの使用は、システム内のフローの数とは独立に当該容量を設定し得ることを意味する。
【００５５】
ＴＴＲＴの選択
本発明による解決策におけるＴＴＲＴの選択を示すために、以下のスキームを提示できる。
【００５６】
次の不等式
【数１９】
2005522946.tif 000021
を満たす要求伝送速度を有する１組の同期フローが与えられたなら、ＴＴＲＴは、次の不等式に従って選択されなければならない。
【数２０】
2005522946.tif 000022
【００５７】
以下に示す疑似コードは、本発明において与えられたシステムの挙動を分析的に記述する。
【００５８】
フロー初期化
【表１】
2005522946.tif 000023
【００５９】
大サイクル中における一般同期待ち行列ｉ（ｉ＝１．．．ＮＳ）へのアクセス
【表２】
2005522946.tif 000024
【００６０】
小サイクル中における一般同期待ち行列ｉ（ｉ＝１．．．ＮＳ）へのアクセス
【表３】
2005522946.tif 000025
【００６１】
一般非同期待ち行列ｊ（ｊ＝１．．．ＮＡ）へのアクセス
【表４】
2005522946.tif 000026
【００６２】
１回転中のアクセスシーケンス
【表５】
2005522946.tif 000027
【００６３】
しかしながら、明らかに、いかにしてこのことを行うかの詳細は、本発明の範囲を逸脱することなく、これまで説明してきたことに関して変更し得る。
【図面の簡単な説明】
【００６４】
【図１】本発明に従って作動するシステムの動作基準を説明するブロック図である。
【符号の説明】
【００６５】
１０  サーバー
【図１】
2005522946.tif 000038
【国際調査報告】
2005522946.tif 000039
2005522946.tif 000040
2005522946.tif 000041