(57)【特許請求の範囲】
【請求項１】
非同期データブロックスイッチングシステムにおいて、データブロックを再シーケンシングする方法であって、
ソースシーケンス中のデータブロックの元の位置をシーケンス位置と呼び、
スイッチングシステムが、マルチパススイッチングシステムの場合のように、前記データブロックを出力ポートに転送する時に、前記データブロックの元のシーケンス順序を考慮しないこともあり、さらに、少なくとも２つのスイッチングエレメントを含む少なくとも１つのスイッチング段によって接続された入力端末モジュールと出力端末モジュールとを含み、
前記スイッチングエレメントを互いに接続する内部リンクの各々で、および前記スイッチングエレメントを前記入力端末モジュール及び前記出力端末モジュールに接続する内部リンクの各々で、前記データブロックの各々が、
前記内部リンクでその後に転送される全てのデータブロックのシーケンス位置が、その再シーケンシング時間境界よりも前にならないように、及び、
前記内部リンクで前記データブロックまでに送信され、それぞれのシーケンス位置が前記再シーケンシング時間境界に等しいかまたはそれよりも小さい、全てのデータブロックを再シーケンシングできるように、
再シーケンシング時間境界を決定することを可能にする再シーケンシング情報を含む再シーケンシング方法。
【請求項２】
前記データブロックの各々がまた、ブロックのシーケンス位置を特徴づけるタイムスタンプを含み、
前記タイムスタンプが、前記データブロックが入力端末モジュールによって送信されたクロック時間位置によって特徴づけられ、
前記クロック時間位置が、全ての入力端末モジュールのための同期化された時間基準で与えられる請求項１に記載の再シーケンシング方法。
【請求項３】
前記再シーケンシング情報が、前記データブロックの各々に関連付けられた再シーケンシング点標識であり、
前記データブロックのいくつかが、再シーケンシングデータブロックであり、
再シーケンシングデータブロックが、スイッチングシステムの内部リンクごとに、
その内部リンク上の再シーケンシング時間境界が、その再シーケンシングデータブロックのタイムスタンプに暗黙的に対応することと、
該内部リンクでその後に転送される全てのデータブロックのタイムスタンプが、その再シーケンシングデータブロックのタイムスタンプよりも前にないことと、
そのデータブロックまでに送信された全てのデータブロックを再シーケンシングできることとを示し、
入力端末モジュールの各々が、出力データブロックの各々にしるし付けをして、前記出力データブロックがまだ再シーケンシングデータブロックであることを指定する再シーケンシング点標識を前記出力データブロックに系統的に割り当て、
スイッチングエレメントの各々が、その出力リンクの各々の出力データブロックの各々にしるし付けをして、前記出力データブロックが再シーケンシングデータブロックであるか否かを指定する再シーケンシング点標識を前記出力データブロックに割り当て、さらに、
各出力端末モジュールが、その入力リンクで受信された各データブロックにおけるしるし付けをされた前記再シーケンシング点標識を監視し、前記再シーケンシング点標識がデータブロックが再シーケンシングデータブロックであることを示すたびに、それらのデータブロックのそれぞれのタイムスタンプに基づいて、受信したデータブロックの全てを再シーケンシングする請求項２に記載の再シーケンシング方法。
【請求項４】
空データブロックも、再シーケンシング点標識でしるし付けをされる請求項３に記載の再シーケンシング方法。
【請求項５】
前記スイッチングエレメントの各々が、それぞれのタイムスタンプに従って、格納されたデータブロックを選択するスケジューリング手段によって管理されるバッファメモリを含み、
さらに、前記再シーケンシング方法が、現在のデータブロックに対して、
前記スイッチングエレメントの入力リンクごとに、その再シーケンシング情報が再シーケンシングデータブロックであることを示す最後のデータブロックに含まれたタイムスタンプである、その入力リンクの最後の浮動再シーケンシング点を格納するステップと、
全ての入力リンクに関係する全ての前記最後の浮動再シーケンシング点から、より小さな最後の浮動再シーケンシング点に対応する境界を連続的に決定するステップと、
前記出力リンクの各々で、前記現在のブロックの再シーケンシング情報に、
そのタイムスタンプが前記境界に等しいかまたはそれよりも小さい場合に、再シーケンシングデータブロックとしてしるし付けをし、
そのタイムスタンプが前記境界よりも大きい場合に、再シーケンシングデータブロックでないデータブロックとしてしるし付けをするステップと、
を含む請求項４に記載の再シーケンシング方法。
【請求項６】
前記スイッチングエレメントの各々が、出力宛先ごとにＦＩＦＯ待ち行列タイプのバッファメモリ管理を使用し、
さらに、前記再シーケンシング方法が、現在のデータブロックに対して、
データブロックをＦＩＦＯ待ち行列に書き込む時に、入力しるし付けをするステップと、
ＦＩＦＯ待ち行列のデータブロックを読み出す時に、出力しるし付けをするステップを含む請求項４に記載の再シーケンシング方法。
【請求項７】
スイッチングエレメントにおける前記入力しるし付けステップが、
前記スイッチングエレメントの入力リンクごとに、その再シーケンシング情報が再シーケンシングデータブロックであることを示す最後のデータブロックに含まれたタイムスタンプである、その入力リンクの最後の浮動再シーケンシング点を格納するステップと、
全ての入力リンクに関係する全ての前記最後の浮動再シーケンシング点から、より小さな最後の浮動再シーケンシング点に対応する境界を連続的に決定するステップと、
前記スイッチングエレメントの出力リンクごとに、前記ＦＩＦＯ待ち行列に格納された全てのデータブロックに関連付けられたタイムスタンプの中で最も大きな受信されたセルのタイムスタンプを格納するステップと、
そのタイムスタンプが、前記境界に等しくかつ最も大きな受信されたセルのタイムスタンプに等しいかそれより大きい場合で、そのタイムスタンプが前記ＦＩＦＯ待ち行列に書き込まれる時に、再シーケンシング点検出標識で、前記現在のデータブロックにしるし付けをするステップと、
を含む請求項６に記載の再シーケンシング方法。
【請求項８】
スイッチングエレメントにおける前記出力しるし付けステップが、前記出力リンクの各々で、前記現在のデータブロックの再シーケンシング情報に、
その再シーケンシング点検出標識が、そのデータブロックが再シーケンシングデータブロックであることを示す場合、または、
そのデータブロックが、関係する出力宛先のためのＦＩＦＯ待ち行列に格納された最後のデータブロックであり、そのタイムスタンプが、前記境界に等しいかまたはそれよりも小さい場合に、
再シーケンシングデータブロックとして、
そうでない場合に、再シーケンシングデータブロックでないデータブロックとして、
しるし付けをするステップを含む請求項６に記載の再シーケンシング方法。
【請求項９】
出力空データブロックが、
各入力端末モジュールで、系統的に再シーケンシングデータブロックとして、該出力空データブロックが伝送されたクロック時間位置に等しいタイムスタンプで、しるし付けをされ、かつ、
各スイッチングエレメントで、その出力リンクの各々で、前記境界が、伝送された最後の空でないデータブロックのタイムスタンプに等しいかまたはそれよりも大きい場合のみ、再シーケンシングデータブロックとして、前記境界に等しいタイムスタンプで、しるし付けをされる、
請求項４に記載の再シーケンシング方法。
【請求項１０】
前記再シーケンシング情報が、
スイッチングシステムの内部リンクごとに、データブロックの前記浮動再シーケンシング境界が、
そのデータブロックのタイムスタンプに等しいかまたはそれよりも小さく、
そのリンクで送信された先行するデータブロックの浮動再シーケンシング境界に等しいかまたはそれより大きく、
そのデータブロックまでに転送され、それぞれのタイムスタンプがそのデータブロックの浮動再シーケンシング境界に等しいかまたはそれよりも小さな、全てのデータブロックを再シーケンシングできることを示すように、
前記データブロックの各々に関連付けられた明示的な浮動再シーケンシング境界であり、
各入力端末モジュールが、各出力データブロックに、しるし付けをして、そのタイムスタンプに常に等しい再シーケンシング情報として、浮動再シーケンシング境界を系統的に割り当て、
各スイッチングエレメントが、その出力リンクの各々で、各出力データブロックに、しるし付けをして、再シーケンシングできるデータブロックのタイムスタンプの最大値を指定する浮動再シーケンシング境界を割り当て、
各出力端末モジュールが、その入力リンクで受信された各データブロックにおけるしるし付けをされた再シーケンシング情報として、前記浮動再シーケンシング境界を監視し、それぞれのタイムスタンプが受信された最後のデータブロックの浮動再シーケンシング境界に等しいかまたはそれよりも小さな受信されたデータブロックを、それぞれのタイムスタンプに基づいて、再シーケンシングする請求項２に記載の再シーケンシング方法。
【請求項１１】
前記浮動再シーケンシング境界が、前記データブロックの各々のヘッダに挿入される請求項１０に記載の再シーケンシング方法。
【請求項１２】
空データブロックが、浮動再シーケンシング境界で、しるし付けをされる請求項１０に記載の再シーケンシング方法。
【請求項１３】
空データブロックが、浮動再シーケンシング境界で、しるし付けをされ、
各スイッチングエレメントが、それぞれのタイムスタンプに応じて、格納されたデータブロックを選択するスケジューリング手段によって管理されるバッファメモリを含み、
前記再シーケンシング方法が、現在のデータブロックに対して、
前記スイッチングエレメントの入力リンクごとに、その入力リンクで受信されたデータブロックによって再シーケンシング情報として与えられた最後の浮動再シーケンシング境界を格納するステップと、
全ての入力リンクに関係する受信されたデータブロックによって与えられた全ての前記最後の浮動再シーケンシング境界の中から受信された最も小さな最後の浮動再シーケンシング境界に対応する境界を連続的に決定するステップと、
前記出力データブロックにおけるしるし付けをされた浮動再シーケンシング境界値が、そのタイムスタンプが前記境界に等しいかまたはそれよりも小さい時にはそのタイムスタンプになるように、または、そのタイムスタンプが前記境界よりも大きい場合には前記境界に等しくなるように、各出力リンクで、前記現在のブロックの再シーケンシング情報として、前記浮動再シーケンシング境界に、しるし付けをするステップと、
を含む請求項１１に記載の再シーケンシング方法。
【請求項１４】
空データブロックが、浮動再シーケンシング境界で、しるし付けをされ、
前記スイッチングエレメントの各々が、出力宛先ごとにＦＩＦＯ待ち行列タイプのバッファメモリ管理を使用し、
前記再シーケンシング方法が、現在のデータブロックに対して、
前記スイッチングエレメントの入力リンクごとに、その入力リンクで受信されたデータブロックによって、再シーケンシング情報として与えられた受信された最後の浮動再シーケンシング境界を格納するステップと、
全ての入力リンクに関係する受信されたデータブロックによって与えられた全ての前記最後の浮動再シーケンシング境界の中から受信された最も小さな最後の浮動再シーケンシング境界に対応する閾値を連続的に決定するステップと、
前記出力データブロックにおけるしるし付けをされた浮動再シーケンシング境界値が、
関係するＦＩＦＯ待ち行列に格納されたデータブロックのタイムスタンプの最も小さなものが前記境界よりも大きい場合には、その最も小さなタイムスタンプに等しくなるように、または、
最も小さなタイムスタンプが前記閾値に等しいかまたはそれよりも小さい場合には、前記境界に等しくなるように、
各出力リンクで、前記現在のブロックの再シーケンシング情報として、前記浮動再シーケンシング境界に、しるし付けをするステップと、
を含む請求項１１に記載の再シーケンシング方法。
【請求項１５】
出力空データブロックが、
各入力端末モジュールで、該出力空データブロックが送信されたクロック時間位置に等しい浮動再シーケンシング境界で、系統的にしるし付けをされ、
各スイッチングエレメントで、その出力リンクの各々で、前記境界に等しい浮動再シーケンシング境界で、系統的にしるし付けをされる、
請求項１０に記載の再シーケンシング方法。
【請求項１６】
スイッチングシステムが、リアルタイム制約に敏感な第１のタイプのデータブロックとリアルタイム制約に比較的敏感でない第２のタイプのデータブロックを、別々に再シーケンシングし、
前記再シーケンシング方法が、前記第２のタイプのデータブロックに適用され、
前記第１のタイプのデータブロックが、出力ポートのレベルで転送遅延を等しくすることに基づいた第１の方法で再シーケンシングされる請求項１に記載の再シーケンシング方法。
【請求項１７】
前記第１と第２のタイプのデータブロックが、同じタイムスタンプを使用して再シーケンシングされる請求項１６に記載の再シーケンシング方法。
【請求項１８】
リアルタイム制約に敏感な第１のタイプのデータブロックとリアルタイム制約に比較的敏感でない第２のタイプのデータブロックを別々に再シーケンシングするために、スイッチングシステムが、データブロックのタイプごとに別々に管理された同じ浮動再シーケンシング方法を使用し、
各データブロックが、
単一のタイムスタンプと、
空でないデータブロックにおける関連するデータブロックのタイプの標識を持つ単一の浮動再シーケンシング境界と、
空データブロックにおけるそれぞれがデータブロックの１つのタイプに関係する２つの浮動再シーケンシング境界とを含む請求項１に記載の再シーケンシング方法。
【請求項１９】
マルチパススイッチングシステムの場合のように、出力ポートにデータブロックを転送する時に、そのデータブロックの元のシーケンス順序を考慮しないことがある非同期データブロックスイッチングシステム中でデータブロックを再シーケンシングする方法であって、
スイッチングエレメントの入力リンクまたは出力リンクで、その後に転送される全てのデータブロックのシーケンス位置が、関係するデータブロックのシーケンス位置の前に有り得ないかどうかを決定するための再シーケンシング情報をデータブロックへ含めるステップを有する、方法。
【請求項２０】
マルチパススイッチングシステムの場合のように、出力ポートにデータブロックを転送する時に、そのデータブロックの元のシーケンス順序を考慮しないことがある非同期スイッチングシステムのスイッチングエレメントであって、
前記スイッチングエレメントが、各データブロックに関連付けられた再シーケンシング情報を処理するデータブロック再シーケンシング手段を含み、
前記データブロック再シーケンシング手段が、
各入力リンクで、受信されたデータブロックごとに、その入力リンクでその後に受信される全てのデータブロックのシーケンス位置が、前記受信されたデータブロックのシーケンス位置よりも前になり得ないかどうかを、示すか又は決定できるようにする前記関連付けられた再シーケンシング情報を分析する手段と、
各出力リンクで、転送されたデータブロックごとに、その出力リンクでその後に送信される全てのデータブロックのシーケンス位置が、前記送信されたデータブロックのシーケンス位置よりも前になり得ないかどうかを、示すか又は決定できるようにする前記関連付けられた再シーケンシング情報を生成する手段とを含む、スイッチングエレメント。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明の分野は、データブロックが宛先出力ポートに転送される間にデータブロックの元のシーケンス順序が保持されないことがあるシステムでのデータブロックの非同期スイッチングの分野である。これは、例えば、データブロックが、複数考えられるパスの１つを介して、その宛先出力ポートに転送されるマルチパススイッチングシステムの場合である。本発明は、固定長であろうと可変長であろうと、パケット又はセルなどのあらゆるタイプのデータブロックの非同期スイッチングに関する（本説明の残りの部分で、「データブロック」および「セル」という用語は交換可能に使用される）。
【０００２】
より詳細には、本発明は、上記の種類のスイッチングシステム中で転送されるデータブロックを再シーケンシング（ｒｅｓｅｑｕｅｎｃｉｎｇ）する（元のシーケンスに戻す）ことに関する。例えばマルチパスセルフルーティングスイッチのようなマルチパススイッチなどの、各データブロックを転送するために、複数の考えられるパスを動的に提供するシステムでは、各パスが変化する転送遅延を導入し、したがって、出力ポートで受信されるデータブロックの順序は入力ポートでの元のシーケンスに対応していないこともある。その時に、データブロックの元のシーケンスを復元するために、再シーケンシング（ｒｅｓｅｑｕｅｎｃｉｎｇ）が必要になる。
【０００３】
【従来の技術】
１つの再シーケンシング方法が、特許出願ＥＰ０４３８４１５に記載されている。そこでは、装置の出力（特に、スイッチング網の出力）で転送遅延を等しくする手段を使用する。等しくする手段の目的は、変化する転送遅延と重み付け遅延の合計が所定の固定総転送遅延に等しくなるように、再シーケンシングメモリのそれぞれのデータブロックの変化する転送遅延に、補足的な重み付け遅延を加えることである。それで、各データブロックは、同じ固定遅延で転送されるので、各データブロックは、もとあったのと同じシーケンス位置にある。このようにして、再シーケンシングされる。
【０００４】
したがって、データブロックが再シーケンシングメモリでその補足的な重み付け遅延を受けた時に、そのデータブロックを出力バッファメモリに転送することができる。
【０００５】
この結果を得るためには、再シーケンシングメモリが適用する補足的な遅延を決定するために、出力端末は、各データブロックが経験した変化する転送遅延を知っていなければならない。重み付け遅延を決定する２つの方法が提案された。すなわち、
−  各スイッチングエレメントにおいて経験した部分遅延の全てが合計される「遅延標識（カウンタ）」を各データブロックで使用する方法と、
−  ブロックのシーケンス位置を特徴づける時間情報に基づいた「タイムスタンプ」を使用する方法であって、その時間情報を、入力端末モジュールがデータブロックを送信したクロック時間位置で特徴づけ、そのクロック時間位置を、全ての入力端末モジュールのための同期化された時間基準で与える方法とが提案された。
【０００６】
上記の従来技術の方法には、区別なしに、特に受信した全てのデータブロックに対して包括的に、すなわち、様々な個々のコネクションと無関係に、各データブロックで簡単に使用できるという利点がある。
【０００７】
さらに、リアルタイム制約に敏感なデータブロック（すなわち、転送遅延および／またはその揺らぎに敏感な）とリアルタイム制約に比較的敏感でなくより長い転送遅延に対応できる他のデータブロックを同時に転送することが必要な時に、固定総転送遅延を使用することは現実的である。したがって、２つの別個の総転送遅延値を使用し、データブロックがリアルタイム制約に敏感であるか比較的敏感でないかどうかによって、それらを選択的にデータブロックに適用することができる。
【０００８】
【発明が解決しようとする課題】
しかし、これには非常に大きな再シーケンシングメモリが必要になる。これは、リアルタイム制約に比較的敏感でないデータブロックを再シーケンシングできなければならず、それは長い固定総転送遅延につながる場合もあるからである。
【０００９】
本発明の目的はとりわけ、従来技術の上記の欠点を軽減することである。
【００１０】
より正確に言えば、本発明の目的は、マルチパスシステムで非同期に転送されるデータブロックを再シーケンシングする方法を提供することであり、その方法の課す最大遅延は、従来の方法に比べて短い。
【００１１】
本発明の他の目的は、簡単に実現でき、特に、大きな再シーケンシングメモリを必要としない上記の種類の再シーケンシング方法を提供することである。
【００１２】
本発明の他の目的、すなわち本発明の少なくともいくつかの実施形態は、２つのタイプのデータブロック（リアルタイム制約に敏感なものと比較的敏感でないもの）の再シーケンシングを最適化することである。
【００１３】
本発明は、さらに、区別なしに、特に全ての受信されたデータブロックに対して包括的に、すなわち、様々な個々のコネクションと無関係に、各データブロックで簡単に使用できるという特性を提供しようとする。
【００１４】
【課題を解決するための手段】
上記の目的、および以下で明らかになる他の目的は、非同期データブロックスイッチングシステムでデータブロックを再シーケンシングする方法を使って達成され、ソースシーケンス中のデータブロックの元の位置を「シーケンス位置」と呼び、そのスイッチングシステムは、マルチパススイッチングシステムの場合のように、出力ポートにデータブロックを転送する時にデータブロックの元のシーケンス順序を考慮しないことがあり、少なくとも２つのスイッチングエレメントを含む少なくとも１つのスイッチング段によって接続された入力及び出力端末モジュールを含む。
【００１５】
本発明によれば、スイッチングエレメントを互いに接続する内部リンクの各々で、およびスイッチングエレメントを入力及び出力端末モジュールに接続する内部リンクの各々で、前記データブロックの各々は、
−  前記リンクでその後に転送される全てのデータブロックのシーケンス位置が、再シーケンシング時間境界よりも前にならないように、及び、
−  前記データブロックまでに前記リンクで転送され、それぞれのシーケンス位置が再シーケンシング時間境界に等しいかまたはそれよりも小さな、全てのデータブロックが再シーケンシングされることができるように、
「再シーケンシング時間境界（ｒｅｓｅｑｕｅｎｃｉｎｇ  ｔｉｍｅ  ｂｏｕｎｄａｒｙ）」を決定することを可能にする再シーケンシング情報（ＲＰＩ、ＦＲＢ）を含む。
【００１６】
留意しなければならないことは、「再シーケンシング時間境界を決定できるようにする」という表現は、様々な手法を包含するということである。それは、再シーケンシング情報が、明示的に時間境界を示すことができること、及び時間境界を計算できるようにする暗黙の手段を与えることができることを意味する。
【００１７】
また、前記データブロックの各々は、ブロックのシーケンス位置を特徴づけるタイムスタンプ（ＴＳＴＰ）を含むのが有利であり、前記タイムスタンプは、入力端末モジュールがデータブロックを送信した時のクロック時間位置で特徴づけられ、前記クロック時間位置は、全ての入力端末モジュールのための同期化された時間基準で与えられる。
【００１８】
本発明の１つの変形では、シーケンス情報を時間情報の代わりに使用することができる。
【００１９】
本発明の第１の好ましい実施形態では、前記再シーケンシング情報は、前記データブロックの各々に関連付けられた再シーケンシング点標識（ＲＰＩ）であり、前記データブロックのいくつかは、再シーケンシングデータブロックであり、さらに、再シーケンシングデータブロックは、スイッチングシステムの内部リンクごとに、
−  そのリンク上の再シーケンシング時間境界が、再シーケンシングデータブロックのタイムスタンプ（ＴＳＴＰ）に暗黙的に対応することと、
−  そのリンクでその後に転送される全てのデータブロックのタイムスタンプ（ＴＳＴＰ）が、その再シーケンシングデータブロックのタイムスタンプ（ＴＳＴＰ）よりも前にないことと、
−  そのデータブロックまでに送信された全てのデータブロックが、再シーケンシングされることができることとを示し、
入力端末モジュールの各々は、出力データブロックの各々にしるし付けをして、前記出力データブロックもまだ再シーケンシングデータブロックであることを指定する再シーケンシング点標識（ＲＰＩ）を前記データブロックに系統的に割り当て、
スイッチングエレメントの各々は、その出力リンクの各々で、出力データブロックの各々にしるし付けをして、前記データブロックが再シーケンシングデータブロックであるか否かを指定する再シーケンシング点標識（ＲＰＩ）を前記データブロックに系統的に割り当て、
さらに、各出力端末モジュールは、その入力リンクで受信された各データブロックにおけるしるし付けをされた再シーケンシング点標識を監視し、再シーケンシング点標識（ＲＰＩ）が前記データブロックが再シーケンシングデータブロックであることを示すたびに、それらのデータブロックの各タイムスタンプ（ＴＳＴＰ）に基づいて、受信したデータブロックの全てを再シーケンシングする。
【００２０】
本発明の上記の第１の実施形態では、このようにして、データブロックが再シーケンシングデータブロックであれば、そのデータブロックのタイムスタンプによって再シーケンシング境界が暗黙的に決定される。
【００２１】
留意すべきことであるが、本発明の第１の実施形態は、タイムスタンプが使用されるという仮定に基づいて説明されている。しかし、この手法を、必ずしも時間でないシーケンス位置情報を使用することに一般化することができる。
【００２２】
この場合に、そのメカニズムをつぎのように説明することができる。すなわち、前記再シーケンシング情報は、前記データブロックの各々に関連付けられた再シーケンシング点標識（ＲＰＩ）であり、前記データブロックのいくつかは、再シーケンシングデータブロックであり、再シーケンシングデータブロックは、スイッチングシステムの内部リンクごとに、
−  そのリンク上の再シーケンシング時間境界が、再シーケンシングデータブロックのシーケンス位置に暗黙的に対応することと、
−  そのリンクでその後に転送される全てのデータブロックのシーケンス位置が、その再シーケンシングデータブロックのシーケンス位置よりも前にないことと、
−  そのデータブロックまでに送信された全てのデータブロックが、再シーケンシングされることができることとを示す。
【００２３】
この場合に、スイッチングシステムの入力で、
入力端末モジュールの各々は、出力データブロックの各々にしるし付けをして、前記出力データブロックがまだ再シーケンシングデータブロックであることを指定する再シーケンシング点標識（ＲＰＩ）を前記データブロックに系統的に割り当て、
スイッチングエレメントの各々は、その出力リンクの各々で、出力データブロックの各々にしるし付けをして、前記データブロックが再シーケンシングデータブロックであるか否かを指定する再シーケンシング点標識（ＲＰＩ）を前記データブロックに割り当て、さらに、
各出力端末モジュールは、その入力リンクで受信された各データブロックにおけるしるし付けをされた前記再シーケンシング点標識を監視し、再シーケンシング点標識（ＲＰＩ）が、前記データブロックが再シーケンシングデータブロックであることを示すたびに、それらのデータブロックの各シーケンス位置に基づいて、受信したデータブロックの全てを再シーケンシングする。
【００２４】
一般化するのが容易であると仮定して、以下で「タイムスタンプ」の態様だけを説明する。
【００２５】
本発明の１つの好ましい実施形態では、空データブロックにもまた再シーケンシング点標識（ＲＰＩ）でしるし付けをする。
【００２６】
この場合に、前記スイッチングエレメントの各々は、それぞれのタイムスタンプ（ＴＳＴＰ）に従って格納されたデータブロックを選択するスケジューリング手段によって管理されるバッファメモリを含むのが有利であり、
さらに、スイッチングエレメントでの再シーケンシングプロセスは、現在のデータブロックに対して、
−  前記スイッチングエレメントの各入力リンクごとに、その入力リンクの最後の浮動再シーケンシング点（ＬＦＲＰ）を格納するステップであって、前記最後の浮動再シーケンシング点が、それが再シーケンシングデータブロックであることを示す再シーケンシング情報を持つ最後のデータブロックに含まれるタイムスタンプ（ＴＳＴＰ）であるステップと、
−  全ての入力リンクに関係する全ての前記最後の浮動再シーケンシング点（ＬＦＲＰ）からより小さな最後の浮動再シーケンシング点（ＳＬＦＲＰ）に対応する境界を連続的に決定するステップと、
−  出力リンクの各々で、前記現在のブロックの再シーケンシング情報に、
−  そのタイムスタンプ（ＴＳＴＰｔ）が、前記境界（ＳＬＦＲＰ）に等しいかまたはそれよりも小さい場合には、再シーケンシングデータブロックとして、及び、
−  そのタイムスタンプ（ＴＳＴＰｔ）が、前記境界（ＳＬＦＲＰ）よりも大きな場合には、再シーケンシングデータブロックでないデータブロックとして、しるし付けをするステップとを含む。
【００２７】
本発明の他の好ましい実施形態では、前記スイッチングエレメントの各々が、バッファメモリを含み、出力宛先ごとにＦＩＦＯ待ち行列タイプのバッファメモリ管理を使用し、さらに、再シーケンシング方法が、現在のデータブロックに対して、データブロックをＦＩＦＯ待ち行列に書き込む時の「入力しるし付けステップ」およびＦＩＦＯ待ち行列のデータブロックを読み出す時の「出力しるし付けステップ」を含む。
【００２８】
この場合に、スイッチングエレメントにおける前記入力しるし付けステップが、
−  前記スイッチングエレメントの各入力リンクごとに、その入力リンクの最後の浮動再シーケンシング点（ＬＦＲＰ）を格納するステップであって、前記最後の浮動再シーケンシング点が、それが再シーケンシングデータブロックであることを示す再シーケンシング情報を持つ最後のデータブロックに含まれるタイムスタンプ（ＴＳＴＰ）であるステップと、
−  全ての入力リンクに関係する全ての前記最後の浮動再シーケンシング点（ＬＦＲＰ）からより小さな最後の浮動再シーケンシング点（ＳＬＦＲＰ）に対応する境界を連続的に決定するステップと、
−  前記スイッチングエレメントの各出力リンクごとに、ＦＩＦＯ待ち行列に格納された全てのデータブロックに関連付けられたタイムスタンプ（ＴＳＴＰ）の中で最も大きな受信されたセルのタイムスタンプ（ＨＲＣＴ）を格納するステップと、
−  前記現在のデータブロックのタイムスタンプ（ＴＳＴＰｒ）が、前記境界（ＳＬＦＲＰ）に等しく、かつ最も大きな受信されたセルのタイムスタンプ（ＨＲＣＴ）よりも大きいかまたは等しい場合に、待ち行列に書き込まれる時に、前記現在のデータブロックに再シーケンシング点検出（ＲＰＤ）標識で、しるし付けをするステップとを含むことが有利である。
【００２９】
スイッチングエレメントにおける前記出力しるし付けステップが、
−  出力リンクの各々で、前記現在のブロックの再シーケンシング情報に、
−  その再シーケンシング点検出（ＲＰＤ）標識が、それが再シーケンシングデータブロックであることを示す場合、または、そのデータブロックが、関係する出力宛先のためのＦＩＦＯ待ち行列に格納された最後のデータブロックであり、そのタイムスタンプ（ＴＳＴＰｔ）が前記境界（ＳＬＦＲＰ）に等しいかまたはそれよりも小さい場合に、再シーケンシングデータブロックとして、
−  そうでない場合に、再シーケンシングデータブロックでないデータブロックとして、しるし付けをするステップを含むことが有利である。
【００３０】
出力空データブロックに、
−  各入力端末モジュールで、系統的に再シーケンシングデータブロックとして、さらに、それが送信されたクロック時間位置に等しいタイムスタンプ（ＴＳＴＰ）で、しるし付けをし、
−  各スイッチングエレメントで、その出力リンクの各々で、前記境界（ＳＬＦＲＰ）が送信された最後の空でないデータブロック（ＬＳＣＴ）のタイムスタンプに等しいかまたはそれよりも大きい場合にのみ再シーケンシングデータブロックとして、さらに、この場合に、前記境界（ＳＬＦＲＰ）に等しいタイムスタンプ（ＴＳＴＰ）で、しるし付けをすることが好ましい。
【００３１】
本発明の方法に対する第２の手法によれば、
前記再シーケンシング情報は、スイッチングシステムの内部リンクごとに、データブロックの浮動再シーケンシング境界（ＦＲＢ）が、
−  そのブロックのタイムスタンプ（ＴＳＴＰ）に等しいかまたはそれよりも小さく、
−  そのリンクで送信された前のデータブロックの浮動再シーケンシング境界（ＦＲＢ）に等しいかまたはそれよりも大きく、さらに、
−  そのブロックまでに送信され、それぞれのタイムスタンプ（ＴＳＴＰ）がそのブロックの浮動再シーケンシング境界（ＦＲＢ）に等しいかまたはそれよりも小さな、全てのデータブロックが再シーケンシングされることができることを示す、
前記データブロックの各々に関連付けられた明示的な浮動再シーケンシング境界（ＦＲＢ）であり、
各入力端末モジュールは、各出力データブロックにしるし付けをして、それに、そのタイムスタンプ（ＴＳＴＰ）に常に等しい再シーケンシング情報として浮動再シーケンシング境界（ＦＲＢ）を系統的に割り当て、
各スイッチングエレメントは、その出力リンクの各々で、各出力データブロックにしるし付けをして、それに、再シーケンシングできるデータブロックのタイムスタンプの最大値を指定する浮動再シーケンシング境界（ＦＲＢ）を割り当て、さらに、
各出力端末モジュールは、前記浮動再シーケンシング境界（ＦＲＢ）をその入力リンクで受信された各データブロックにおいて、しるし付けをされた再シーケンシング情報として監視し、それぞれのタイムスタンプ（ＴＳＴＰ）が最後のデータブロックの浮動再シーケンシング境界（ＦＲＢ）に等しいかまたはそれよりも小さな受信されたデータブロックを再シーケンシングし、該再シーケンシングが、データブロックの各タイムスタンプ（ＴＳＴＰ）に基づいて行われる。
【００３２】
この第２の手法によれば、このようにして時間再シーケンシング境界は、各データブロックの浮動境界によって明示的に決定される。以下で明らかになるように、この手法は、より効果的である。
【００３３】
再度、タイムスタンプを使用するという想定で、本発明のこの実施形態を説明する。しかしながら、この手法は、また、必ずしも時間でないシーケンス位置情報を使用することに一般化することができる。
【００３４】
本発明の方法に対するこの第２の手法では、そのメカニズムは次のように説明することができる。前記再シーケンシング情報は、スイッチングシステムの内部リンクごとに、データブロックの前記浮動再シーケンシング境界（ＦＲＢ）が、−  そのブロックのシーケンス位置より前のシーケンス位置またはそのブロックのシーケンス位置と同じシーケンス位置に対応し、
−  そのリンクで送信された前のデータブロックの浮動再シーケンシング境界（ＦＲＢ）に等しいかまたはそれよりも大きく、さらに、
−  そのブロックまでに送信され、それぞれのシーケンス位置がそのブロックの浮動再シーケンシング境界（ＦＲＢ）よりも前であるかまたはそれと同じである、全てのデータブロックを再シーケンシングできることを示す、
前記データブロックの各々に関連付けられた明示的な浮動再シーケンシング境界（ＦＲＢ）である。
【００３５】
この場合に、各入力端末モジュールは、各出力データブロックにしるし付けをして、それに、そのシーケンス位置に常に対応する再シーケンシング情報として、浮動再シーケンシング境界（ＦＲＢ）を系統的に割り当て、
各スイッチングエレメントは、その出力リンクの各々で、出力データブロックの各々にしるし付けをして、それに、再シーケンシングできるデータブロックのタイムスタンプの最大値を指定する浮動再シーケンシング境界（ＦＲＢ）を割り当て、さらに、
各出力端末モジュールは、前記浮動再シーケンシング境界（ＦＲＢ）をその入力リンクで受信された各データブロックにおいて、しるし付けをされた再シーケンシング情報として監視し、それぞれのシーケンス位置が最後のデータブロックの浮動再シーケンシング境界（ＦＲＢ）よりも前であるかまたはそれと同じである受信されたデータブロックを再シーケンシングし、該再シーケンシングは、それらのデータブロックのそれぞれのシーケンス位置に基づいて行われる。
【００３６】
再度、容易に一般化できると仮定して、以下に、「タイムスタンプ」の態様だけを説明する。
【００３７】
本発明の第２の実施形態では、前記浮動再シーケンシング境界（ＦＲＢ）を前記データブロックの各々のヘッダに挿入するのが好ましい。
【００３８】
また、空データブロックに浮動再シーケンシング境界（ＦＲＢ）でしるし付けをするのが好ましい。
【００３９】
本発明の１つの特別の実施形態では、各スイッチングエレメントが、格納されたデータブロックをそれぞれのタイムスタンプ（ＴＳＴＰ）に応じて選択するスケジューリング手段によって管理されるバッファメモリを含み、さらに、再シーケンシング方法が、現在のデータブロックに対して、
−  前記スイッチングエレメントの入力リンクごとに、その入力リンクで受信されたデータブロックによって、再シーケンシング情報として与えられた最後の浮動再シーケンシング境界（ＬＦＲＢ）を格納するステップと、
−  全ての入力リンクに関係する受信されたデータブロックによって、与えられた全ての前記最後の浮動再シーケンシング境界（ＬＦＲＢ）の中から受信された最も小さな最後の浮動再シーケンシング境界（ＳＬＦＲＢ）に対応する境界を連続的に決定するステップと、
−  出力データブロックにおいてしるし付けをされた浮動再シーケンシング境界値が、前記境界（ＳＬＦＲＢ）に等しいかまたはそれよりも小さい時にはそのタイムスタンプ（ＴＳＴＰｔ）に等しくなるように、または、そのタイムスタンプ（ＴＳＴＰｔ）が前記境界（ＳＬＦＲＢ）よりも大きい場合には前記境界（ＳＬＦＲＢ）に等しくなるように、各出力リンクで、前記現在のブロックの再シーケンシング情報として、浮動再シーケンシング境界にしるし付けをするステップとを含む。
【００４０】
本発明の他の実施形態では、前記スイッチングエレメントの各々が、出力宛先ごとに、ＦＩＦＯ待ち行列タイプのバッファメモリを含む。この場合に、その方法は、現在のデータブロックに対して、
−  前記スイッチングエレメントの入力リンクごとに、その入力リンクで受信されたデータブロックによって、再シーケンシング情報として与えられた受信された最後の浮動再シーケンシング境界（ＬＦＲＢ）を格納するステップと、
−  全ての入力リンクに関係する受信されたデータブロックによって、与えられた全ての前記最後の浮動再シーケンシング境界（ＬＦＲＢ）の中から受信された最も小さな最後の浮動再シーケンシング境界（ＳＬＦＲＢ）に対応する閾値を連続的に決定するステップと、
−  出力データブロックのしるし付けをされた浮動再シーケンシング境界値が、ＦＩＦＯ待ち行列に格納されたデータブロックのタイムスタンプの最も小さなもの（ＴＳＴＰｍ）が前記境界（ＳＬＦＲＢ）よりも大きい場合には、関係するＦＩＦＯ待ち行列に格納されたデータブロックのタイムスタンプの最も小さなもの（ＴＳＴＰｍ）に等しくなるように、または、最も小さなタイムスタンプ（ＴＳＴＰｍ）が前記閾値（ＳＬＦＲＢ）に等しいかまたはそれよりも小さい場合には、前記境界（ＳＬＦＲＢ）に等しくなるように、各出力リンクで、前記現在のブロックの再シーケンシング情報として、前記浮動再シーケンシング境界にしるし付けをするステップとを含むことができる。
【００４１】
出力空データブロックに、
−  各入力端末モジュールで、それが送信されるクロック時間位置に系統的に等しい浮動再シーケンシング境界（ＦＲＢ）でしるし付けをし、さらに、
−  各スイッチングエレメントで、その出力リンクの各々で、前記境界（ＳＬＦＲＰ）に系統的に等しい浮動再シーケンシング境界（ＦＲＢ）でしるし付けをするのが有利である。
【００４２】
本発明の好ましい実施形態では、リアルタイム制約に敏感な第１のタイプのデータブロックとリアルタイム制約に比較的敏感でない第２のタイプのデータブロックを別々に再シーケンシングするスイッチングシステムが、前記第２のタイプのデータブロックに適用され、第１のタイプのデータブロックが、出力ポートのレベルで転送遅延を等しくすることに基づいた第１の方法で再シーケンシングされる。
【００４３】
この場合に、前記第１と第２のタイプのデータブロックを同じタイムスタンプ（ＴＳＴＰ）を使用して再シーケンシングするのが有利である。
【００４４】
リアルタイム制約に敏感な第１のタイプのデータブロックとリアルタイム制約に比較的敏感でない第２のタイプのデータブロックを別々に再シーケンシングするために、スイッチングシステムが、データブロックのタイプごとに別々に管理された同じ再シーケンシング方法を使用するのが有利であり、さらに、それぞれのデータブロックが、
−  単一のタイムスタンプ（ＴＳＴＰ）と、
−  空でないデータブロックに、関連するデータブロックのタイプの標識を持つ単一の浮動再シーケンシング境界（ＦＲＢ）と、
−  空データブロックに、それぞれデータブロックの１つのタイプに関係する２つの浮動再シーケンシング境界（ＦＲＢ）とを含む。
【００４５】
また、本発明は、上で説明した再シーケンシングの方法で処理されるデータブロックに関係する。
【００４６】
この種のデータブロックは、マルチパススイッチングシステムの場合のように、出力ポートにデータブロックを転送する時にそのデータブロックの元のシーケンス順序を考慮しないことがあることもある非同期スイッチングシステム中で転送されるように構成され、スイッチングエレメントの入力リンクまたは出力リンクで、その後に転送される全てのデータブロックのシーケンス位置が関係するデータブロックのシーケンス位置の前に有り得ないかどうかを決定するための再シーケンシング情報（ＲＰＩ、ＦＲＢ）を含む。
【００４７】
本発明は、また、本発明の方法を使用するスイッチングエレメントに関する。
【００４８】
この種のスイッチエレメントは、それぞれのデータブロックに関連付けられた再シーケンシング情報（ＲＰＩ、ＦＲＢ）を処理するデータブロック再シーケンシング手段を含み、前記処理が、
−  各入力リンクで、受信された各データブロックに対して、その入力リンクで、その後に受信された全てのデータブロックのシーケンス位置が、受信されたデータブロックのシーケンス位置よりも前にないことがあるかどうかを、示すか又は決定できるようにする前記関連する再シーケンシング情報を分析する操作と、−  各出力リンクで、それぞれの送信されたデータブロックに対して、その出力リンクで、その後に送信された全てのデータブロックのシーケンス位置が、送信されたそのデータブロックのシーケンス位置よりも前にないことがあるかどうかを、示すか又は決定できるようにする前記関連する再シーケンシング情報を生成する操作とを含む。
【００４９】
本発明のその他の特徴および利点は、説明するための非制限的な実施例としてのみ与えられる本発明の好ましい実施形態についての下記の説明を読む時に、および添付の図面からより明らかになるであろう。
【００５０】
【発明の実施の形態】
１．  用語集
様々な実施形態を詳細に説明する前に、以下で使用される略語を下に定義する。ＦＲＢ：浮動再シーケンシング境界
ＦＲＰ：浮動再シーケンシング点
ＨＲＣＴ：最も大きな受信されたセルのタイムスタンプ
ＩＥＲ：再シーケンシング中の状態標識
ＬＦＲＢ：最後の浮動再シーケンシング境界
ＬＦＲＰ：最後の浮動再シーケンシング点
ＬＳＣＴ：最後に取り扱われたセルのＴＳＴＰ
ＲＧ：経路指定グループ
ＲＰＤ：検出された再シーケンシング点
ＲＰＩ：再シーケンシング点標識
ＳＥ：スイッチングエレメント
ＳＬＦＲＰ：より小さな最後の浮動再シーケンシング点
ＳＬＦＲＢ：最も小さな最後の浮動再シーケンシング境界
ＴＳＴＰ：タイムスタンプ
ＴＳＴＰｍ：ＦＩＦＯ待ち行列に存在する全てのセルの中でＴＳＴＰの最も小さな値
ＴＳＴＰｒ：受信されたセルのＴＳＴＰ値
ＴＳＴＰｔ：出力に送信するために取り扱われるセルのＴＳＴＰ値
【００５１】
２．  第１の実施形態
２．１  出力バッファ管理のタイプへの依存性
プリアンブルで説明した転送時間を等しくする原理の制限に加えて、本発明は、特に、出力ポートでデータブロックを再シーケンシングするための要求は、全ての種類の出力バッファメモリ管理について、同じようには特徴つけられないという考えに基づいている。標準的なＦＩＦＯ出力待ち行列タイプの管理の場合には、データブロックが取り扱われる順序がそれらの到着の順序によって決定されるのであれば、データブロックは、シーケンシャルに待ち行列に到着しなければならない。
【００５２】
一方、出力バッファメモリを管理するためにシーケンサを使用すれば、出力に送信するためにデータブロックを取り扱う順序は、そのデータブロックが、シーケンサに着いた時ではなくて、（データブロックに関連付けられたシーケンシング時間パラメータに基づいて）取り扱われる時にだけ、それぞれのデータに対して決定される。この場合には、到着するデータブロックは、たとえ未だ再シーケンシングされていなくとも、
−  シーケンサが、コネクションごとに、データブロックのシーケンスを暗黙的に重んじるシーケンシング時間パラメータに従って、データブロックを取り扱う場合（通常はこの場合になる）、および、
−  データブロックが既に再シーケンシングされたか否かに従って、出力に送信するために、それを選択することを許可するかまたは許可しないように、シーケンサ内のそれぞれのデータブロックに「再シーケンシング中」の状態標識を付与する場合に、
シーケンサに容易に直接入れられることができる。
【００５３】
つまり、転送遅延を等しくすることに基づいた再シーケンシングをしないシーケンサの場合には、その原理の相違は、その後に受信されたデータブロックが、関係したデータブロックのシーケンス位置の前のシーケンス位置を持たないということが確実になると直ちに、データブロックを「再シーケンシングされた」（もとのシーケンスに戻された）ものと考えることができるということから生じている。このようにして、出力でデータブロックの間違った再シーケンシングをするいう危険性なしに、シーケンサは、全てのこれらの「再シーケンシングされた」データブロックに、その選択プロセスを適用することができる。
【００５４】
２．２  本発明の浮動再シーケンシングのメカニズムの特徴
本発明の再シーケンシングの原理では、出力バッファメモリを管理するためにシーケンサを使用すること（従来の遅延を等しくすることを必要としない）の有利さを活かす。スイッチング網の中のそれぞれの内部リンクで（入力端末モジュールと第１の段のスイッチングエレメント（ＳＥ）の間で、２つの連続した段のＳＥの間で、および最終の段のＳＥと出力端末モジュールの間で）浮動再シーケンシング点（ＦＲＰ）を管理することを基本的に特徴とする。
【００５５】
浮動再シーケンシング点の概念
次の説明は、データブロックの例としてセルを考えることに基づいている。
【００５６】
ＦＲＰの概念は、次のように要約することができる。すなわち、送信リンクで必ずしもシーケンス通りに転送されない連続するセルを考えると、特定のセルの後に送信されたどのセルのシーケンス位置もそのセルのシーケンス位置の前でない場合には、その特定のセルは「再シーケンシング点」（ＲＰ）（または、再シーケンシング時間位置）を構成すると考えられる。
【００５７】
図１の簡単な実施例は、ＲＰセルを図示し、図で、セルは、そのシーケンス位置で識別される（理解を容易にするために）。この実施例では、
−  セル８の後に転送された全てのセルは、セル８に対して正しい位置にあり、−  セル１４の後に転送された全てのセルは、セル１４に対して正しい位置にあるので、セル８と１４が再シーケンシング点（ＲＰ）を構成する。
【００５８】
実際は、上記をシーケンス通りに並んだセルの流れと比較すると、ＲＰセルだけが正しいシーケンス位置を持ち、その他のセルは正しいシーケンス位置を持たないことが分かる。
【００５９】
再シーケンシング点の値は、先行する全てのセルを別個に（ＲＰセルから後に続くセルに無関係に）再シーケンシングできる「浮動」時間位置を決定するような値である。
【００６０】
次に、本発明は、２つの連続したＲＰで区切られたセル再シーケンシンググループを処理することに基づいている。この種の再シーケンシンググループの中では、セルはシーケンス通りに並んでいない。しかし、連続した再シーケンシンググループは、それ自身シーケンス通りに並んでいる。
【００６１】
例えば、図１で、５つのセル１２、１０、９、１３、１１は、ＲＰセル８の後に受信される。これらは、シーケンス通りに並んでいない。次に、ＲＰセル１４が受信される。その時、６つのセル１２から１４は、セルがシーケンス通りに並んでいないが、その中で再シーケンシングを独立に行うことができるセル再シーケンシンググループ１１を構成する。さらに、この種のセル再シーケンシンググループは、他の同じ種類のグループに対して、それ自身シーケンス通りに並んでいる。
【００６２】
前記のように、上記の種類のセル再シーケンシンググループの中での再シーケンシング操作は、必ずしも転送時間を等しくすることに基づく必要はなく、出力シーケンサでセルごとに「再シーケンシング中」の状態標識（ＩＥＲ）ビットを使用するのにずっと適していると思われるであろう。
【００６３】
前述の実施例で、第１の５つのセル１２、１０、９、１３、１１がシーケンサに入る時に、それらは、出力で選択されるように、その関連するＩＥＲビットで、その妥当性をまだ確認されていない。６番目のセル１４（これは、ＲＰセルである）が到着した時に、再シーケンシンググループを形成する１２から１４の６つの関係したセルは、それらのＩＥＲ標識ビットをアクティブにすることによって、シーケンサ内で、同時にその妥当性を確認されることができる。そして、シーケンサによるそれらのセルの選択を許可する。
【００６４】
実際には、ＲＰセルを受信した時のＩＥＲビットのこのアクティブ化は、関係するリンクで、前に受信された全てのセル（既にその状態にある前のセル８、５、３、７、４．．．．を含む）の全てのＩＥＲビットをアクティブ化するただ１つの命令で容易に行うことができる。
【００６５】
２．２．２  スイッチ内のリンクごとの再シーケンシング点（ＲＰ）の管理
ＲＰの概念を定義し、ＲＰが出力シーケンサに固有な再シーケンシング機能に適している様子を説明したので、マルチパススイッチング網の様々な内部リンクで、ＲＰセルを適切に管理する方法を示す。
【００６６】
２．２．２．１  それぞれのＳＥでのＲＰの管理
対処すべき基本的な問題は、それぞれのｎ×ｎ（または、ｎ１×ｎ２）のスイッチングエレメント（ＳＥ）で、出力リンクに向かって、または経路指定グループ（ＲＧ）と呼ばれる出力リンクのグループに向かって、経路指定される様々なセルの動的な分配に関係する。ＳＥの入力リンクを考えると、それぞれの受信されたセルは、特定の宛先すなわち、出力リンクまたは出力リンクのグループ（ＲＧ）に経路指定され、それに応じて、その全てのセルは分配される。これは、それぞれの入力リンクに当てはまる。
【００６７】
また、例えば、前のステップで、それぞれのＲＰセルに入れられたＲＰ標識（ＲＰＩ）ビットによって、各入力リンクで、ＲＰセルを検出することができると想定すれば、解決すべき問題は、各出力リンクで送信された連続したセルが、全く新しいシーケンスを持った新しいセルの流れを構成し（入力リンクと出力リンクの間のセルの分配のために）、それに対して、その出力リンクでどのセルがＲＰセル（すなわち、ＲＰＩビットを１に設定しなければならないセル）であるかを決定する必要があるということである。
【００６８】
上の問題に対する解決法を提案する前に、留意しなければならないことは、それぞれの第１の内部リンク（入力端末モジュールと第１の段のＳＥとの間の）が、全てシーケンス通りに並んでおり、したがって、第１の段のＳＥのそれぞれの入力リンク上の全てがＲＰセルである、セルの流れを転送する。
【００６９】
セルがシーケンス通りであるかないかを認識する補足的な手段として、入力端末モジュールによって、それぞれのセルに関連付けられたタイムスタンプ（ＴＳＴＰ）を使用することもここで想定する。他の方法も同様に実施可能である。
【００７０】
さて、一般に任意の所与のＳＥを考えると、ｎ１の入力リンクの各々で、セルの到着を監視して、受信されたＲＰセルを検出し、受信された最後のＲＰセルの関連するタイムスタンプ値（ＴＳＴＰ）を記録する。その結果として、いつでも、ＳＥでは、それぞれの入力リンクについて、受信された最後のＲＰセル（最後の浮動再シーケンシング点（ＬＦＲＰ）と呼ばれる）に関連付けられたＴＳＴＰ値が分かっている。
【００７１】
したがって、ｎ１の入力リンクの全てについて、様々なＬＦＲＰ値を比較する時に、ＳＥのレベルでのＬＦＲＰの最も小さな値（ＳＬＦＲＰ）は、この時までにＳＥに転送されたそのセルの全てに対して全体的に有効な最後のＦＲＰのＴＳＴＰ値を示す。
【００７２】
このようにして、各出力リンクで、送信されるそれぞれのセルがＲＰセルであるか否かを決定するために、このＳＬＦＲＰ値を使用することができる。これは、次のように、ＳＥで使用されるバッファメモリの管理方法によって決定される。
【００７３】
Ａ．  ＳＥでの「シーケンサ」タイプのバッファ管理
ＳＥで、出力の宛先ごとの個々のシーケンサは、それぞれの出力リンクのサーバまたは経路指定グループの複数のサーバが、常に最初に最小のＴＳＴＰ値（これは、ＴＳＴＰ値順の取り扱い規則に対応する）を持つセルを選択するように動作する。
【００７４】
出力宛先（出力リンク、または経路指定グループと呼ばれる出力リンクのグループ）ごとの個々のシーケンサは、バッファメモリで待機しているセルを、その関連するタイムスタンプ（ＴＳＴＰ）に従って、出力に送信するために使用されるので、取り扱われたセルのタイムスタンプ値ＴＳＴＰｔを、ＳＥの現在のＳＬＦＲＰ値と比較するだけで十分であり、
−  ＴＳＴＰｔがＳＬＦＲＰに等しいかまたはそれよりも小さい場合には、シーケンサが常にセルを増加するＴＳＴＰ順で取り扱い、さらに、現在の最小ＬＦＲＰ（ＳＬＦＲＰ）よりも小さなＴＳＴＰを持つセルがその後でＳＥに受信されない（したがって、関係するバッファに受信されない）限りでは、出力セルはＲＰセルであり（ＲＰＩビットを１に設定するように、しるし付けをされる）、
−  ＴＳＴＰｔがＳＬＦＲＰより大きい場合には、現在のＳＬＦＲＰより大きいが第３番目のセルのＴＳＴＰｔよりも小さなＴＳＴＰを持つ新しいセルが、その後にバッファに受信されることがない理由がない限りは（したがって、これは、第３番目のセルに比べてシーケンスが乱れている）、取り扱われたセルはＲＰセルではない（ＲＰＩビットは０である）。
【００７５】
共用バッファメモリを持つＳＥの場合には、これは、ＳＥの出力宛先（出力リンクまたは経路指定グループ）ごとの個々の「論理的な」バッファメモリを示すことに留意する必要がある。
【００７６】
また、実際に送信される正常なセルがなくとも、それぞれのリンクの再シーケンシング点に関係する情報を送信することも同様に重要なので、それぞれのＳＥができるだけ速く（受信される次の正常なセルを待つ必要なしに）それぞれの入力リンクの新しいＲＰ値を検出できるように、それぞれの空セル（または、スイッチ内に複数のタイムスライスを有するセルに基づいた内部転送モードの場合には、それぞれの空タイムスライス）にＲＰＩビットおよびＴＳＴＰ値を同様に使用しなければならない。
【００７７】
バッファメモリを管理するためにシーケンサを使用する場合には、シーケンサが空セルを出力に送信する時に（バッファメモリにセルがない）、シーケンサはどの空セルにＲＰセルであるとしてしるし付けをしなければならないかを決定しなければならない。このために、出力シーケンサ（出力宛先に関係する）ごとに、ＬＳＣＴと呼ばれる取り扱われた最後のセルのＴＳＴＰの記録を保存する。次に、空セルを送信する際に、
−  ＬＳＣＴがＳＬＦＲＰに等しいかまたはそれよりも小さい場合には、その後に受信された新しいセルがＳＬＦＲＰよりも小さなＴＳＴＰを持つことがなければ、ＲＰＩビットが１で、ＴＳＴＰが現在のＳＬＦＲＰに等しいＲＰセルとして、空セル（または、タイムスライス）にしるし付けをする。したがって、留意しなければならないことは、空バッファメモリの条件が持続すれば、ＳＬＦＲＰがＳＥで増加するたびに、生成された空ＲＰセルは、ＳＬＦＲＰと同じ様に増加するＴＳＴＰを含むということである。
−  ＬＳＣＴがＳＬＦＲＰよりも大きい限りでは、その後に受信されたセルが、ＳＬＦＲＰよりも大きいがＬＳＣＴよりも小さなＴＳＴＰをもつことができるということから（したがって、これは、送信された最後のセルに対してシーケンス通りに並んでいないだろう）、空セル（または、タイムスライス）にＲＰセルとしてしるし付けをしない。
【００７８】
Ｂ．  ＳＥでの「ＦＩＦＯ待ち行列」タイプのバッファ管理
この場合には、ＦＩＦＯ待ち行列にはシーケンス通りに受信されないセルも有り得るということから、バッファメモリを管理する出力宛先ごとのそれぞれのＦＩＦＯ待ち行列で、（一般には）そのＴＳＴＰ順でなく到着順で、待っているセルが取り扱われるので、出力宛先（出力リンクまたはＲＧ）ごとのＲＰセルの決定は様々であり、余り効果的でない。
【００７９】
出力宛先（出力リンクまたはリンクのグループ）ごとのＦＩＦＯ待ち行列の現在の場合には、バッファメモリのそれぞれの待ち行列に存在する全てのセルの中で最も大きなＴＳＴＰ（ＨＲＣＴと呼ぶ）の記録が保存される。
【００８０】
新しい受信されたセルがバッファメモリ待ち行列に格納される時に、
−  ＴＳＴＰｒと呼ばれる受信されたセルのＴＳＴＰが、ＳＬＦＲＰに等しく、さらに、
−  受信されたセルのＴＳＴＰｒが、ＨＲＣＴに等しいかまたはそれよりも大きい、という２つの条件が満たされる場合、それもその場合だけに、そのセルはＲＰセルである。
【００８１】
このことは、バッファメモリの待ち行列内の入力セルに関連付けられたＲＰ検出（ＲＰＤ）標識を１に設定することで確認される。
【００８２】
その後、セルをＦＩＦＯ待ち行列から出力に送信するように取り扱う時に、関連するＲＰＤフラグが１であるか、または、
−  そのセルが取り扱うべき最後のセルであり（バッファメモリの待ち行列で単一のセルだけが待っている）、さらに、
−  そのセルのＴＳＴＰがＳＬＦＲＰに等しいかまたはそれよりも小さい、という２つの条件が満たされるか、いずれかの場合には、送信されたセルはＲＰセルである（ＲＰＩビットが１であるように、しるし付けをされる）。
【００８３】
さらに、（バッファメモリが空の時に生成される）空セル（または、タイムスライス）に、下記のように（全く上記の状態Ａのように）空ＲＰセル（または、タイムスライス）として、しるし付けをする。すなわち、
−  ＬＳＣＴが、ＳＬＦＲＰに等しいかまたはそれよりも小さい場合には、空セル（または、タイムスライス）に、ＲＰＩビットが１で、ＴＳＴＰが現在のＳＬＦＲＰに等しい、ＲＰセルであるとして、しるし付けをする。
−  ＬＳＣＴがＳＬＦＲＰよりも大きい場合には、空セル（または、タイムスライス）に、ＲＰセルであるとして、しるし付けをしない。
【００８４】
したがって、バッファメモリ管理方法の両方のタイプ（シーケンサ、またはＦＩＦＯ待ち行列）によって、ＳＥの入力リンクと出力リンクの間のＲＰの相互関係を管理することができるようになることに留意する必要がある。ＳＥでのＲＰの内部処理は同じではないが（Ａの場合またはＢの場合）、ＲＰを信号で伝えるために各リンクで使用されるプロトコルは正確に同じで有り得る。
【００８５】
しかし、より優れた動作は、ＳＥにおいて、ＦＩＦＯ待ち行列よりもシーケンサで得られることに留意することが重要である。これは、再シーケンシングのメカニズムがそれぞれのＳＥのシーケンサによってバッファメモリで待っている全てのセルに適用される場合に、各出力リンクで、それぞれのＳＥによって送信される出力セルの流れが、部分的に再シーケンシングされるためである（取り扱われるセルのＴＳＴＰがＳＬＦＲＰよりも大きい場合には、シーケンサで取り扱われたセルはＲＰセルではなく、取り扱われたセルのＴＳＴＰよりも小さなＴＳＴＰを持つ新しいセルがその後まだ受信される可能性があるから（すなわち、それに対してシーケンス通りに並んでいない）そのように部分的になる）。
【００８６】
したがって、その中でセルがシーケンス通りに並んでいない送信された再シーケンシンググループ（例えば、図１に示されているように、各ブロックが２つの連続したＲＰで区切られている）は、ＳＥのバッファメモリを管理するためにシーケンサ（ＦＩＦＯ待ち行列ではなくて）を使用すれば、一般に短くなる。
【００８７】
２．２．２．２  スイッチ内で得られる浮動再シーケンシング点（ＦＲＰ）
スイッチング網の全てのＳＥで、上述のセクション２．２．２．１で定義されたＲＰ管理を、連続したＳＥの段の間のそれぞれのリンクに対して適用すれば、２つのＲＰの間のシーケンス通りに並んでいないセルの連続した再シーケンシンググループを区切るために、上流のＳＥにより浮動再シーケンシング点（ＦＲＰ）が、特定の（正常な、または空の）セル上を信号で伝えられる。しかし、ＲＰによって、セルの流れを上述の種類の再シーケンシンググループにセグメント化することは、上流のＳＥと下流のＳＥの間の特定のリンクに対してのみ有効でる。
【００８８】
それぞれのＳＥが、受信された入力セルを再び様々な出力に分配して、それによって出力リンク上に新しいセルの流れを生成するので、そこでの再シーケンシンググループへのＲＰセグメント化は、入力リンクでのそれと異なっている。それにも拘わらず、それぞれのＳＥにおいてＲＰを管理することによって、受信された（入力リンク上の）ＲＰセルと送信された（出力リンク上の）ＲＰセルの間に適切な相互関係が作られる。これにより、複数の段を有するスイッチング網の一般的な場合を考える時に、浮動再シーケンシング方法がこのように呼ばれる理由が説明される。
【００８９】
２．３  従来技術との比較
提案された浮動再シーケンシング方法には、遅延を等しくすることに基づいた標準的な再シーケンシング方法と比べて次の特徴がある。すなわち、
−  スイッチング網の連続した段での待ち時間の分布が、ＳＥでシーケンサまたはＦＩＦＯ待ち行列タイプのバッファメモリの管理を使用する従来の再シーケンシング方法と正確に同じであれば、本発明の再シーケンシング方法を使用すれば、スイッチング網のＳＥの段を横切る転送性能は変化していない。
−  出力端末モジュールで、セルごとに必要とされる再シーケンシングの遅延は、標準的な方法によるよりも新しい方法で一般に短くなるが、再シーケンシング遅延を含む総転送遅延は、短く一定ではない（それは、所定の固定総転送遅延に等しくない）。
【００９０】
このようにして、後者の特性は、出力バッファメモリ（シーケンサ）内の「再シーケンシングされた」セルの時間位置が、それらのセルが入力端末モジュールに到達した時のそれらセルの時間位置と一致していないことを意味している（それぞれのセルについて、２つの時間位置は、固定総転送遅延だけ離れているのではない）。
【００９１】
新しい再シーケンシング方法に関して、出力ポートのバッファメモリへのセルの到着は、セルがそれぞれの宛先出力ポートに経路指定される時に、ＳＥにおけるセル間のアクセスの競合を反映する遅延の変動（すなわち、転送遅延の揺らぎ）を受けやすい入力へのセルの到着に対応する。
【００９２】
２．４  応用
リアルタイム制約に敏感な（すなわち、転送遅延および／またはその揺らぎに敏感な）セルとリアルタイム制約に比較的敏感でない（すなわち、転送遅延および／またはその揺らぎに比較的敏感でない）セルの同時転送を考えると、後者のタイプ（より低い遅延についての優先順位を有する）は、スイッチ中でより大きく変化する転送遅延を経験することがあり、リアルタイム制約に比較的敏感でなく、ＳＥでの待ち遅延が広く分布している、セルの流れが存在することで、シーケンス通りに並んでいないセル再シーケンシンググループの長さが長くなる傾向がある（そして、その結果として、全てのセルに対して出力で再シーケンシング遅延が増加する傾向がある）場合には、提案された浮動再シーケンシング方法をセルの全体的な流れに直接応用することでは（すなわち、再シーケンシングを行うためにセルの流れのそれぞれのタイプを区別することなしに）、最適の性能は得られない。
【００９３】
したがって、結果として生じる転送遅延の変動は、リアルタイム制約に敏感なセルの流れに対しては大きくなりすぎるだろう。
【００９４】
リアルタイム制約に敏感なセルの転送時のこの影響をなくするという問題に対して２つの解決法がある。すなわち、
Ａ．  出力末端で、２つの異なる再シーケンシング方法を選択的に適用する。すなわち、リアルタイム制約に敏感なセルを転送するための遅延を等しくする標準的な方法とリアルタイム制約に比較的敏感でないセルを転送するための浮動方法とを適用する（実際に、同じタイムスタンプ（ＴＳＴＰ）を使用すれば、２つの再シーケンシング方法をセルの異なる流れに互換可能に使用することができる）。
Ｂ．  両方のタイプのセルの転送に同じ浮動再シーケンシング方法を適用するが、スイッチの全体で、および出力端末モジュールで、タイプごとに別々に管理する。
【００９５】
解決法Ａを採用すれば、リアルタイム制約に敏感なセルの転送遅延は、リアルタイム制約に比較的敏感でないセルの存在に影響されないだけでなく、また、所定の固定総転送遅延に等しい一定の転送遅延を維持する（言い換えると、リアルタイム制約に敏感なセルの転送遅延の揺らぎがスイッチ中で加わらない）。
【００９６】
この状態を図２Ａから２Ｄで図示する。ここで、「上側の」セル２１は、リアルタイム制約に比較的敏感でないセルであり、「下側の」セル２２は、リアルタイム制約に敏感なセルである。図２Ａは、セルの流れの１つの例を示し、図２Ｂから２Ｄは、本発明の異なる実施形態のセル再シーケンシンググループを識別する方法を示す。
【００９７】
ＳＥでの再シーケンシング点（ＲＰ）の管理を、セルの全体的な流れに適用する（セルの２つの流れを区別しないで、図２Ｂのブロック２３１および２３２を参照のこと）か、または、リアルタイム制約に比較的敏感でないセルだけに選択的に適用する（すなわち、ＲＰの管理において、リアルタイム制約に敏感なセルを無視する、図２Ｃのブロック２４１および２４２を参照のこと）か、いずれかに適用することができる。
【００９８】
解決法Ｂが採用されると、ＳＥで２つの別個のＲＰ管理方法が、同時に、別々に、セルの流れのタイプごとに１つ、適用されなければならない。したがって、この場合に、
−  それぞれのＳＥが、入力リンクごとに２つのＬＦＲＰパラメータ、ＳＥのレベルで２つのＳＬＦＲＰパラメータ、出力リンクごとに２つのＬＳＣＴパラメータ、および（ＦＩＦＯ待ち行列の状況でのみ）出力リンクごとに２つのＨＲＣＴパラメータ（セクション２．３．２．１参照のこと）を管理し、
−  正常なセルが、そのセルがリアルタイム制約に敏感であるか、それとも比較的敏感でないかを示す特性情報も伝達するものと想定すれば、正常なセルごとに単一のＲＰＩビットで十分であり、さらに、
−  他方で、空セルが、両方のタイプのセルの流れに対して同時に再シーケンシング点（ＲＰ）を構成できるように、２つのＲＰＩビットおよび２つのＴＳＴＰフィールドを空セル（または、タイムスライス）に設けなければならない。
【００９９】
したがって、各出力端末モジュールで、両方のタイプのシーケンス通りに並んでいないセル再シーケンシンググループ（セルの流れのタイプごとの）は、そのセルが受信されたセルの全体的な流れの中で多重化されているが、分離され、そのセルが、それぞれのＲＰに基づいて選択的に再シーケンシングされる（図２Ｄ参照のこと）。
【０１００】
３．  第２の実施形態
３．１  はじめに
第１の実施形態で、ＲＰセルを指定するために使用される特に簡単な方法は、セルが再シーケンシング点としてその妥当性を確認される時に、そのセルにおいてＲＰ標識（ＲＰＩ）ビットを１に設定することである。
【０１０１】
しかし、一見してこの簡単な方法の利点と思われること（セルごとに単一のＲＰＩビットが必要であること）は、この方法では全ての可能な再シーケンシング点を識別できるわけではない確率が無視することのできないために、いくつかの実際の応用では性能が制限される可能性があることである。それで、識別されないＲＰにより、シーケンス通りに並んでいないセル再シーケンシンググループの大きさが過度に大きくなり、したがって、再シーケンシング遅延がより大きくなるになる可能性がある。
【０１０２】
第１の実施形態について説明した原理の不利をもたらす可能性のある効果は、表１に従う所与の出力リンク（または、経路指定グループ）のためのＳＥで生成されるセルの流れの実施例で説明することができる。
【０１０３】
実施例では、セルの時間位置１から２０までの２０の連続したセルのストリングを参照する（簡単にするために、空セルはないものと想定する）。表の第２番目の行に、シーケンス通りに並んでいないセルを強調するためだけに、セルのそれぞれのシーケンス位置を示す。表の第３番目の行に、それぞれのＴＳＴＰの仮定の値を示す。
【０１０４】
ここで、４つの連続した再シーケンシング点（ＲＰ）すなわちセル位置１、７、１３および２０で区切られた（シーケンス通りに並んでいないセルから成る）３つの連続したグループに留意しなければならない。また、表の第４番目の行に、２つの僅かに異なった実施例ＡとＢについて、セル時間位置ごとに、ＳＥバッファのレベルの現在の仮定のＳＬＦＲＰ（より小さな最後の再シーケンシング点）を示す（セクション２．３．２．１のＳＬＦＲＰの定義を参照のこと）。
【０１０５】
次に、表の第５番目の行に、最初の提案の原理を使用して識別することができた、その結果の再シーケンシング点を示す。簡単にするために、ＳＥバッファメモリの各セルについて、待ち遅延がないと想定されている。
【０１０６】
セル位置７と１３において可能な再シーケンシング点は、実施例Ｂでは識別することができないので（実施例Ａではできるが）、このために、（シーケンス通りに並んでいないセルの）再シーケンシンググループの長さが２０セルまで（この実施例では）増えるということを理解できる。したがって、表の第６番目の行に、Ｂの場合には、セル２から２０が、２０番目のセルを受信した時にのみ再シーケンシングされることを示す。これに対して、Ａの場合には、再シーケンシングは、より段階的である（セル２から７、次に、８から１３、そして最後に、１４から２０）。
【０１０７】
セル位置７と１３に仮定されたＳＬＦＲＰ値をより注意深く調べることで、Ｂの場合の不適当な動作を説明できる。セル位置７で、セルのＴＳＴＰは１４３である。Ａの場合に、ＳＬＦＲＰは同じ様に１４３に等しいものと想定されている。したがって、より小さなＴＳＴＰを持つ他のセルが到着することはなく、現在調べているセルを新しいＲＰとして識別する。
【０１０８】
逆に言えば、Ｂの場合には、ＳＬＦＲＰが１４１に等しいとだけ想定されている。したがって、１４３よりも小さなＴＳＴＰを持つ別のセルが到着するかどうか分からないので、現在調べているセルを新しいＲＰと識別することができない。
【０１０９】
【表１】
0003834175.tif 000002
同様に、セル位置１３で、セルのＴＳＴＰは、Ａの場合には１６８であり、ＳＬＦＲＰ＝１６８によって新しいＲＰが識別される。これに対して、Ｂの場合には、ＳＬＦＲＰ＝１６５であり、新しいＲＰは識別されない。
【０１１０】
言い換えると、新しいＲＰに対応する可能性のあるセルについて、セルのＴＳＴＰがＳＥのレベルの現在のＳＬＦＲＰを超える場合にだけいつも、新しいＲＰを識別することができる。そのような状況の確率は、ＳＥの実際の動作で無視することができないので、下記に説明されるようなより効果的な原理を使用することができる。
【０１１１】
３．２  原理
本発明の改善された第２の実施形態では、浮動再シーケンシングパラメータ（セル再シーケンシングプロセスを制御するために使用される）を識別する方法は、下記の特徴に基づいている。すなわち、
−  それぞれのセルに関連付けられた現在の「浮動再シーケンシング境界」（ＦＲＢ）を識別すること。ここで、２つの連続したセルのＦＲＢ値は一定であるか、増加しているかいずれかである（決して、減少していることはない）。
−  任意のセルについて、ＦＲＢは、ＴＳＴＰに等しいかまたはそれよりも小さい。
−  出力端末モジュールのレベルで、出力シーケンサは、受信された最後のＦＲＢに等しいかまたはそれよりも小さなＴＳＴＰを持つ全ての受信されたセルを「再シーケンシング中」の状態に入れることができる。
−  それぞれのセルに関連付けられたＦＲＢを転送するために使用される方法は、セルのヘッダにそのパラメータを付け加えることにある、という特徴に基づいている。
【０１１２】
この新しい方法では、セルに固有のＴＳＴＰから浮動再シーケンシングパラメータ（ここでは、ＦＲＢ）を切り離し、その結果、第１の実施形態の制限をなくす。さらに、実際、第２の方法では、浮動再シーケンシング点の原理に基づいた第１の方法よりも再シーケンシング遅延についての解決を提供できる。
【０１１３】
第１と第２の実施形態の比較をよりはっきりと示すために、図３Ａと３Ｂおよび表２は、それぞれ全ての点で図１および表１のものと同一である実施例に対する新しい原理の応用を示す。
【０１１４】
図３Ａと３Ｂでは、新しい方法の原理に従った、セルのシーケンスに対する浮動再シーケンシング操作の典型的な展開を示す。それは、受信されたセルのＴＳＴＰに関して、ＦＲＢを仮定的にセルごとに展開することによる。
【０１１５】
より正確に言えば、図３Ａは、シーケンス内のそれぞれのセルの連続するシーケンス位置（元のシーケンスに従って番号が付けられた）、ＴＳＴＰ、仮定されたＦＲＢ、および「再シーケンシングされた」状態のセル（そのシーケンス位置で識別される）を示す。考察した実施例は、図１に示したものと同じである。セル８と１４（星印が付いている）は、第１の実施形態の原理による浮動再シーケンシング点である。
【０１１６】
図３Ｂは、実線で、それぞれの正常なセルのＴＳＴＰを示し、破線で、全ての連続したセル（正常なセルおよび空セル）のＦＲＢを示す。
【０１１７】
また、表２は、セルの流れにおける浮動再シーケンシング境界の推移を示す。ここで留意すべきことは、この推移の動作が仮定されたＡとＢの場合の両方について、いくぶん似ていることであり、これは第２の方法が、全ての考えられる再シーケンシング境界を識別する能力の点で、不適当な制限による影響を受けないことを意味している。
【０１１８】
【表２】
0003834175.tif 000003
【０１１９】
３．３  第２の実施形態の説明
３．３．１  スイッチでの浮動再シーケンシング境界（ＦＲＢ）の管理
新しく提案したＦＲＢの概念を概説した後で、その後のセクションで、マルチパススイッチング網の様々な内部リンクで、出力モジュールの出力シーケンサまで、ＦＲＢを正しく管理する方法を説明する。
【０１２０】
３．３．１．１  各スイッチングエレメント（ＳＥ）でのＦＲＢの管理
述べるべき基本的な問題は、それぞれのｎ×ｎ（または、ｎ１×ｎ２）のスイッチングエレメント（ＳＥ）で、異なった入力リンクで受信され、様々な出力リンクまたは経路指定グループ（ＲＧ）と呼ばれる様々な出力リンクのグループに経路指定されるセルの分配に関する。ＳＥの入力リンクを考えると、受信されたそれぞれのセルは、特定の宛先リンクまたはリンクのグループに経路指定され、その全てのセルは、それ応じて分配される。これは、それぞれの入力リンクに当てはまる。
【０１２１】
各入力リンクで引き続いて受信されたセルは、それぞれの関連するＦＲＢを供給するが、それぞれの出力リンクのレベルで生成されたセルの新しい流れは、セルの全く新しいシーケンスを持ち（入力と出力の間の分配のために）、出力に転送されるそれぞれのセルに割り当てられる適切なＦＲＢを再定義することを必要とする。
【０１２２】
これらのＦＲＢを決定するために使用できる解決法を説明する前に、留意すべきことは、スイッチング網の第１の内部リンク（すなわち、入力端末モジュールを第１の段のＳＥの入力に接続するリンク）は、全てシーケンス通りに並んでいるセルを転送することである。したがって、これらの第１のリンク上では、それぞれのセルに関連付けられたＦＲＢは、そのセルのＴＳＴＰに常に等しい。
【０１２３】
ここで、空セル（または、タイムスライス）にも、現在のＴＳＴＰカウンタに等しいＦＲＢを割り当てる（すなわち、あたかもそれらが正常なセルであるかのように）。
【０１２４】
さて、一般に、任意の所定のセルを考えると、受信された最後のＦＲＢを記録するために（２つの連続した（正常なまたは空）セルの間で、ＦＲＢは常に同じであるかまたは増加しており、決して減少していることがないということを忘れないで）、ｎ１の入力リンクの各々にセルが到着するのを監視する。
【０１２５】
したがって、いつでも、ＳＥには、それぞれの入力リンクについて、受信された最後のＦＲＢ（ＬＦＲＢ）が分かっている。したがって、その全てのｎ１の入力リンクについての全てのＬＦＲＢを連続的に比較することで、ＳＥのレベルの最小のＬＦＲＢ（ＳＬＦＲＢ）が、ＳＥによって現在転送されている全てのセルに対して全体的に有効な現在の最小のＦＲＢを示す。このようにして、いつでも、ＳＥの受信された新しいセルが、ＳＬＦＲＢよりも小さなＴＳＴＰを持つことはない。
【０１２６】
その結果、ＳＥのレベルで、ＳＬＦＲＢのパラメータは、各出力リンクで転送されるそれぞれのセルに割り当てるべきＦＲＢを決定する際の基本的なパラメータである。
【０１２７】
バッファメモリを持たないＳＥ（または、アクセスの競合なしに待ち遅延なしでセルを転送するバッファメモリを持つ等価なＳＥ）の簡単な場合を考えると、出力セルごとのＦＲＢは、そのＳＬＦＲＢに系統的に等しいであろう。
【０１２８】
セル間でアクセスの競合が起きるバッファメモリを持つ実際的なＳＥの場合には、転送されるセルのＦＲＢの決定は、バッファメモリの管理方法によって決まる。ここで再び、２つの主要な場合を想像する。すなわち、ＴＳＴＰに基づいたシーケンサタイプの管理のＳＥと、ＦＩＦＯ待ち行列タイプの管理のＳＥとである。
【０１２９】
Ａ．  ＳＥでの「シーケンサ」タイプのバッファ管理
ＳＥで、出力宛先ごとの個々のシーケンサは、それぞれの出力リンクのサーバまたは経路指定グループの複数のサーバが、最小のＴＳＴＰを持つセルを常に最初に選択するように動作する（これは、ＴＳＴＰ順の取り扱い規則に対応する）。
【０１３０】
留意しなければならないことであるが、ＴＳＴＰに基づいた上記の種類のシーケンサは、ＳＥのレベルで、いくつかのセルの再シーケンシングを行う。しかし、ここで、バッファメモリにセルがある限りは、シーケンサが、常にセルを取り扱うと想定すれば、シーケンサは、その時にバッファメモリにあるセルにだけ専念するので、再シーケンシングは、部分的なままである。
【０１３１】
上記の種類のＴＳＴＰをベースにしたシーケンサでは、出力に転送するために取り扱われるそれぞれのセルのＦＲＢは、Ｍｉｎ［ＳＬＦＲＢ；ＴＳＴＰｔ］に等しいとしてセルを取り扱う時に、簡単に決定することができる。ここで、ＴＳＴＰｔは、出力に転送するために取り扱われるセルのＴＳＴＰとして定義される。
【０１３２】
これは次の理由による。すなわち、
−  ＳＬＦＲＢがＴＳＴＰｔに等しいかまたはそれよりも大きい場合には、シーケンサがバッファからのセルを増加するＴＳＴＰの順で取り扱うので、さらに、ＳＬＦＲＢよりも小さなＴＳＴＰを持つ新しいセルが到着しないので、サーバは、ＴＳＴＰｔよりも小さなＴＳＴＰを持つセルを扱うことはない。したがって、取り扱われるセルに割り当てるＦＲＢは、ＴＳＴＰｔに等しい。
−  ＳＬＦＲＢがＴＳＴＰｔよりも小さい場合には、ＴＳＴＰｔよりも小さな（しかし、ＳＬＦＲＢに等しいかまたはそれよりも大きい）ＴＳＴＰを持つ新しいセルがまだバッファメモリに到着することもあるので、取り扱われるセルに割り当てるＦＲＢは、ＳＬＦＲＢに等しい。
【０１３３】
さらに、実際に転送されるセルがなにもなくても、それぞれのリンクでＦＲＢに関係する情報を転送することが、すなわち、サーバがバッファメモリが空いているのを見出した場合に生成されるそれぞれの空セル（または、タイムスライス）とＦＲＢを関連づけることが、同様に重要である。これによって、最も新しいＦＲＢをできるだけ早く（転送される次のセルを待つ必要なしに）供給することができるようになる。
【０１３４】
したがって、現在ＳＬＦＲＢに等しいＦＲＢが、生成される空セル（または、タイムスライス）と系統的に関連づけられる。
【０１３５】
Ｂ．  ＳＥでの「ＦＩＦＯ待ち行列」タイプのバッファ管理
ＦＩＦＯ待ち行列タイプのバッファメモリ管理の標準的な場合には、出力宛先（出力リンクまたは出力経路指定グループ）ごとの待ち行列のサーバは、セルが待ち行列に到着する順序に従って常にセルを選択する（すなわち、それぞれのＴＳＴＰとは無関係に）。
【０１３６】
この場合に、取り扱われるそれぞれのセルに関連付けられるＦＲＢを決定することは、それが待ち行列にこの時に存在する連続するセルのＴＳＴＰの展開に依存している場合には、ＴＳＴＰをベースにしたシーケンサの場合よりも複雑になる。このため、関係する出力宛先のためのＦＩＦＯ待ち行列にこの時に存在する全てのセルの中で最小のＴＳＴＰとしてＴＳＴＰｍを定義すれば、セルを取り扱う時に決定されるＦＲＢは、下記の理由に基づいて、Ｍｉｎ［ＳＬＦＲＢ；ＴＳＴＰｍ］に等しくなる。すなわち、
−  ＳＬＦＲＢがＴＳＴＰｍよりも小さい場合には、ＴＳＴＰｍよりも小さな（しかし、ＳＬＦＲＢに等しいかまたはそれよりも大きい）ＴＳＴＰｍを持つ新しいセルがまだ待ち行列に到着し得るので、取り扱われるセルに割り当てるＦＲＢは、ＳＬＦＲＢに等しい。
−  ＳＬＦＲＢがＴＳＴＰｍに等しいかまたはそれよりも大きい場合には、この時に待ち行列に存在する全てのセルがＴＳＴＰｍに等しいかまたはそれよりも大きなＴＳＴＰ値を持つので、さらに、ＳＬＦＲＢよりも小さなＴＳＴＰを持つ新しいセルが到着しないので、サーバは、ＴＳＴＰｍよりも小さなＴＳＴＰを持つセルを取り扱うことはない。したがって、取り扱われるセルに割り当てるべきＦＲＢは、ＴＳＴＰｍに等しい。
【０１３７】
したがって、ＦＩＦＯ待ち行列タイプの管理の場合には、パラメータＴＳＴＰｍ（すなわち、バッファメモリのそれぞれの待ち行列にその時に存在する全てのセルの最も小さなＴＳＴＰ）を連続的に決定する必要がある。セルごとにＴＳＴＰｍを決定する様々な方法を考えることができる。最も簡単な解決法は、セルを取り扱う時に、セルのＴＳＴＰの中で最も小さい値、すなわちＴＳＴＰｍを決定するために、ＦＩＦＯ待ち行列に存在するセルのＴＳＴＰを分類するための装置を使用することである。
【０１３８】
さらに、ＴＳＴＰをベースにしたシーケンサの上記の場合には、ＳＬＦＲＢに等しいＦＲＢを、ＦＩＦＯ待ち行列が空である時に生成されるそれぞれの空セルと系統的に関連づける。
【０１３９】
このようにして、バッファメモリ管理方法の両方のタイプ（シーケンサまたはＦＩＦＯ待ち行列）によって、ＳＥの入力リンクと出力リンクの間のＦＲＢの相互関係を管理することが可能になることが分かる。ＳＥでのＦＲＢの内部処理は同じでないが（Ａの場合、またはＢの場合）、ＦＲＢを信号で伝えるために、それぞれのリンクで使用されるプロトコルは同一で有り得る。
【０１４０】
３．３．１．２  スイッチ内で得られる浮動再シーケンシング境界（ＦＲＢ）スイッチング網の全てのＳＥによって、連続するＳＥの段の間のそれぞれのリンクで、上述のセクション３．３．１．１で定義されているＦＲＢが管理される場合に、浮動再シーケンシング境界（ＦＲＢ）が、それぞれの（正常または空）セルに割り当てられる。そのＦＲＢは、それぞれの内部リンクに固有であり、それぞれのセルがＳＥで１つの入力リンクから出力リンクに転送される時に、セルごとに再定義される。
【０１４１】
言い換えると、入力リンクから出力リンクにセルを分配しながら、それぞれのＳＥは、セルに関連付けられた受信されたＦＲＢ間の必要な相互関係をつくって、それぞれの出力リンク上で新しいＦＲＢを決定する。このことは、マルチパススイッチング網の一般的な場合を考える時に、浮動再シーケンシング境界の方法がこのように呼ばれる理由を説明している。
【０１４２】
３．３．２  従来技術との比較
本発明による第２の浮動再シーケンシングの方法は、遅延を等しくすることに基づいた標準的な再シーケンシングの方法に比較して、下記の特徴を持つ。
−  スイッチング網の連続する段の待ち時間の分布が、ＳＥでシーケンサまたはＦＩＦＯ待ち行列タイプの管理を使用する標準的な再シーケンシング方法と正確に同じである場合には、本発明の再シーケンシングの方法を使用すれば、スイッチング網のＳＥの段を横切る転送に関する性能は変らない。出力端末モジュールで、それぞれのセルに必要となる再シーケンシング遅延は、標準的な方法よりも新しい方法で一般に短くなるが、再シーケンシング遅延を含む総転送遅延は、短く一定ではない（それは、所定の固定総転送遅延に等しくない）。
【０１４３】
このようにして、この後者の特性は、出力バッファメモリ（シーケンサ）の「再シーケンシングされた」セルの時間位置は、それらのセルが入力端末モジュールに到着した時のそれらのセルの時間位置ともはや一致しない（それぞれのセルのこれら２つの時間位置は、もはや固定総転送遅延だけ離れてはいない）ことを意味する。
【０１４４】
本発明の新しい再シーケンシング方法に関して、セルがポートのバッファメモリに到着することは、セルがそのそれぞれの宛先出力ポートに経路指定される時に、ＳＥでセル間のアクセスの競合を反映する遅延の変動（すなわち、転送遅延の揺らぎ）を受けやすい入力にセルが到着することに対応する。
【０１４５】
これは、アクセスの競合がなければ、すべてのセルは連続するＳＥ段をシーケンス通りに並んで通って経路指定され得るだろうし、その時に出力のレベルで再シーケンシング遅延は必要でないであろうからである。
【０１４６】
３．２．３  応用
リアルタイム制約に敏感なセル（すなわち、転送遅延および／またはその揺らぎに敏感なセル）とリアルタイム制約に比較的敏感でないセル（すなわち、転送遅延および／またはその揺らぎに比較的敏感でないセル）の同時転送を考えると、リアルタイム制約に比較的敏感でなくＳＥで広い分布の待ち遅延を有するセルの流れが存在するために、ＦＲＢが遅れる傾向がある（したがって、全てのセルについて出力のレベルで再シーケンシング遅延が大きくなる傾向がある）場合には、後者のタイプ（遅延に関する優先順位が低い）がスイッチ中でより大きく変化する転送遅延を経験し、提案された浮動再シーケンシング方法をセルの全体的な流れに直接応用することで（すなわち、セルの流れのそれぞれのタイプを区別しないで再シーケンシングを行うことで）、最適な動作を得ることはできない。
【０１４７】
このようにして、リアルタイム制約に敏感なセルの流れに対して、結果として、転送遅延の変動は過大になるだろう。
【０１４８】
リアルタイム制約に敏感なセルの転送に対するこの影響をなくすという問題に対して次の２つの解決法がある。
【０１４９】
Ａ．  出力端末モジュールで、２つの異なる再シーケンシング方法を選択的に使用する。すなわち、リアルタイム制約に敏感なセルを転送するための標準的な遅延を等しくする方法、およびリアルタイム制約に比較的敏感でないセルを転送するための浮動再シーケンシングの方法である。実際、同じタイムスタンプ（ＴＳＴＰ）を使用すれば、両方の再シーケンシングの方法を、セルの異なる流れに対して、互換可能に使用することができる。
【０１５０】
Ｂ．  同じ浮動再シーケンシング方法を、両方のタイプのセルの転送に適用するが、全体としてのスイッチで、および出力端末モジュールで、タイプごとに別々に管理する。
【０１５１】
解決法Ａを採用すれば、リアルタイム制約に敏感なセルの転送遅延は、リアルタイム制約に比較的敏感でないセルの存在による影響を受けないだけでなく、その転送遅延は相変わらず一定で、かつ所定の固定総転送遅延に等しい（すなわち、リアルタイム制約に敏感なセルの転送遅延の揺らぎが、スイッチ中で発生しない）。
【０１５２】
この場合に、ＳＥでのＦＲＢの管理を、セルの全体的な流れ（セルの２つの流れを区別しないで）に適用するか、またはリアルタイム制約に比較的敏感でないセルだけに選択的に（すなわち、ＦＲＢの管理でリアルタイム制約に敏感なセルを無視して）適用するか、いずれかができる。
【０１５３】
解決法Ｂを採用すれば、２つの別個のＦＲＢ管理方法を同時に使用しなければならないが、しかしＳＥで、別々に、すなわちセルの流れごとに、１つの方法を使用しなければならない。したがって、この場合に、
−  それぞれのＳＥが、入力リンクごとに２つのＬＦＲＢパラメータ、ＳＥのレベルの２つのＳＬＦＲＢパラメータ、および（ＦＩＦＯ待ち行列の場合だけ）出力リンクごとの２つのＴＳＴＰｍパラメータを管理し、
−  リアルタイム制約に敏感なセルであるか比較的敏感でないセルであるかを示す特性情報も正常なセルが伝達すると想定すれば、正常なセルごと単一のＦＲＢで十分であり、さらに、
−  他方では、空セル（または、タイムスライス）で２つのＦＲＢを、すなわち、セルの流れのタイプごとに１つを設けなければならない。
【０１５４】
したがって、各出力端末モジュールで、シーケンス通りに並んでいない両方のタイプのセル（セルの流れのタイプごとに）が、受信されるセルの全体的な流れで多重化されているが、分離されて、それぞれのＦＲＢに基づいて選択的に再シーケンシングされる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態を使用する再シーケンシングの１つの実施例を示す図である。
【図２Ａ】本発明の第１の実施形態の様々な使用を示す図である。
【図２Ｂ】本発明の第１の実施形態の様々な使用を示す図である。
【図２Ｃ】本発明の第１の実施形態の様々な使用を示す図である。
【図２Ｄ】本発明の第１の実施形態の様々な使用を示す図である。
【図３Ａ】本発明の第２の実施形態を使用する再シーケンシングの１つの実施例を示す図である。
【図３Ｂ】本発明の第２の実施形態を使用する再シーケンシングの１つの実施例を示す図である。
【符号の説明】
１１  再シーケンシンググループ
２１  リアルタイム制約に敏感なセル
２２  リアルタイム制約に比較的敏感でないセル
２３１  （２つのセルの流れを区別しない）ブロック
２３２  （２つのセルの流れを区別しない）ブロック
２４１  （リアルタイム制約に敏感なセルを無視した）ブロック
２４２  （リアルタイム制約に敏感なセルを無視した）ブロック
２４３  ブロック
２４４  ブロック
ＲＰ  再シーケンシング点（ＲＰセル）
【図１】
0003834175.tif 000004
【図２Ａ】
0003834175.tif 000005
【図２Ｂ】
0003834175.tif 000006
【図２Ｃ】
0003834175.tif 000007
【図２Ｄ】
0003834175.tif 000008
【図３Ａ】
0003834175.tif 000009
【図３Ｂ】
0003834175.tif 000010