(57)【特許請求の範囲】
【請求項１】
多重化され、入力データ流の一部分を形成する対応している各個々のデータ流から個々のパケット流のパケットを生成する少なくとも１つのパケット化デバイスを含み、前記パケットのそれぞれ１つが前記対応している各個々のデータ流の次の１組のデータ部分を含んでいるパケット化装置において、
前記パケット化デバイスは、前記１つのパケットの直前のパケットが生成された後の実質上の時間間隔に入るものとして前記１組に含まれるべき最後のデータ部分を決定する処理手段を含み、前記時間間隔が前記パケットの長さに対応していることを特徴とするパケット化装置。
【請求項２】
前記パケットが、前記次のデータ部分を含む可変長のデータ部分を有することを特徴とする請求項１記載のパケット化装置。
【請求項３】
前記パケットが、前記次のデータ部分を少なくとも部分的に含む予め定められた長さのデータ部分をそれぞれ有する請求項１記載のパケット化装置。
【請求項４】
前記個々のデータ流のビット速度が実質上一定であり、前記各パケットに関しては前記データ部分が予め定められたデータ部分で開始することを特徴とする請求項３記載のパケット化装置。
【請求項５】
前記個々のデータ流の前記ビット速度間に予め定められた比例が存在し、前記各個々のデータ流の前記データ部分が前記入力データ流にわたって実質上均等に拡散していることを特徴とする請求項４記載のパケット化装置。
【請求項６】
パケットスイッチの入力にそれぞれ結合され、それにパケットを供給して前記パケットスイッチの出力に切換えられる前記複数のパケット化デバイスを含み、同じ個々のパケット流のパケットが前記パケットスイッチの同じ出力に切換えられ、前記各パケット化デバイスに対しては供給された前記個々のデータ流の第１のパケットの前記最後のデータ部分がランダムに選択されることを特徴とする請求項１記載のパケット化装置。
【請求項７】
パケットスイッチの入力にそれぞれ結合され、それにパケットを供給して前記パケットスイッチの出力に切換えられる前記複数のパケット化デバイスを含み、同じ個々のパケット流のパケットが前記パケットスイッチの同じ出力に切換えられ、前記各パケット化デバイスに対して供給された前記個々のパケット流の第１のパケットの前記最後のデータ部分が、後者の第１のパケットが切換えられるべきパケットスイッチ出力で利用可能な帯域幅によって決定されることを特徴とする請求項１記載のパケット化装置。
【請求項８】
前記各パケットは前記パケットスイッチ入力から前記パケットスイッチ出力に切換えられるときに予め定められた遅延を受け、前記第１のパケットの前記スイッチングの前に、タイミングメッセージが切換えられるべき出力から供給されるべき入力に伝送され、前記タイミングメッセージはパケットが後者の出力で受信される瞬間の時間を示すことによって後者の出力で利用可能な前記帯域幅を示し、パケットの数が受信されることを特徴とする請求項７記載のパケット化装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、多重化され、入力データ流の一部を形成するそれぞれ対応している個々のデータ流からの個々のデータ流のパケットであり、各１つが前記対応している各個々のデータ流の１組の後続するデータ部分を含んでいるパケットを生成する少なくとも１つのパケット化デバイスを含んでいるパケット化装置に関する。
【０００２】
【従来の技術】
このようなパケット化装置は、B.Pauwels 氏らによる文献（1992年10月の横浜においてのInternational Switching Symposium の第１巻、324 乃至328 頁における「Application of the multipath self-routing switch in a combined STM/ATM cross-connect system 」）から既に知られている。入力データ流はＳＴＭ−Ｎ（同期転送モジュールＮ）フレームによる同期デジタル階級（ＳＤＨ）信号によって構成されており、それにおけるＶＣ−ｎ（仮想容器ｎ）は写像され、個々のデータ流はこれらのＶＣ−ｎ中に写像される。パケット流はパケットスイッチに供給され、同じ個々のデータ流の全データ部分、すなわち同じパケット流の全パケットはこのパケットスイッチの同じ出力にスイッチされる。このパケットスイッチはいわゆるマルチパス自己経路設定（ＭＰＳＲ）スイッチであり、同じパケット流の異なるパケットが通過する通路は異なることができ（マルチパス）、パケットは入力からこのパケットに含まれた自己経路設定タグに基づいてパケットスイッチの出力に導かれている。入力からパケットスイッチの出力へ個々のデータ流またはＶＣ−ｎを切換えるため、ＶＣ−ｎはパケット流のパケットを構成するマルチスロットセル（ＭＳＣ）中にパケット化される。各パケットは、パケットが切換えられるべきパケットスイッチ出力を示している自己経路設定タグを含んでいる第１のスロットと、個々のデータ流に属している多数の連続的なバイトを含んでいる別のスロットとを含み、これらのバイトは次のデータ部分のセットを構成している。
【０００３】
【発明が解決しようとする課題】
個々のデータ流（ＶＣ−ｎ）が入力データ流（ＳＴＭ−Ｎフレーム）において多重化される方法により、複数のパケットはほぼ同時に、すなわち１バイトのみの間隔でパケットスイッチに転送される準備ができる。それによって入力データ流において多重化される個々のデータ流の数は、同時にパケットスイッチに転送されることができるパケットの数を超え、全てのパケットがその準備をするときにパケットスイッチに転送されるとは限らないので、それらの幾つかは入力バッファにおいてバッファされなければならない。それによって、これらのパケットはほぼパケット化遅延に等しい付加的な遅延を受ける。すなわち、パケット化デバイスからの個々のデータ流出力のデータの最大ビット速度は、このデータがこのパケット化デバイスに入力されているビット速度に少なくとも等しくなければならないという事実によって、パケットはこの最大の付加的な遅延内のパケットスイッチに常に転送されることができる。さらに、パケット流の次のパケットがパケット化遅延にほぼ等しい間隔で形成されることに注意すべきであるので、付加的な遅延は、パケットの順序の指示が失われないようにパケット化遅延より長くは許容されない。
【０００４】
一方、パケットスイッチは、供給される個々のデータ流からパケット化装置によって得られた各パケットへの複数の入力を有する。さらに、使用されたパケットスイッチは、その入力のいずれかと出力のいずれかとの間のスイッチング遅延が鋭いピークを有する分布に従う特性を有している。すなわち実質上一定な特性を有する。同じスイッチ出力に予定された異なるパケットがパケット化装置によって異なるパケットスイッチ入力に同時に放出され、後者の同じ出力によって実質上同時に受けられるとき、衝突が生じる。すなわち、パケットはこの出力でバッファされなければならない。それ故、多数のパケットのこのような同時到着を処理することができるような大きさのバッファがパケットスイッチに含まれている。このようなバッファにもかかわらずパケット損失が生じる。しかしながら、入力データ流がＳＴＭデータ流であるとき、パケットのトラフィックパターンは不変である。すなわち、パケット損失は規則的に生じる。この不変的な特性を壊すため、パケットがパケット化装置からパケットスイッチに転送される瞬間のランダム化が入力で導入される。これは、上述された入力バッファによって行われることができる。ランダム化は、導入されたランダム化遅延がゼロとパケット化遅延との間に均等に分配されるとき、すなわち、上記付加的な遅延の最大値ができる限り大きくされるときに最も有効である。この最大値がパケット化遅延を超えてはならないという既に上記された制限を思い出すと、最大の付加的な遅延はパケット化遅延に等しく選択されることが効果的である。
【０００５】
さらに、パケットスイッチへのパケットの転送の瞬間が上記されたようにランダム化されるときでさえ、パケットの転送の瞬間は時間的に均等には分配されていない。すなわち、パケット化は、パケットスイッチにおける増加したパケット損失率と、パケットスイッチの入力から出力までの増加したスイッチング遅延とを生じるパケットスイッチにバーストで転送され、パケット損失率とスイッチング遅延はパケットがさらに均等に拡がりまたは一定の速度でパケットスイッチに転送される状況に関する。
【０００６】
本発明の目的は、上記既知のタイプのパケット化装置であるが、そこから出力するパケット間の衝突は実質上付加的な遅延が導入されることなしに回避されることのできるパケット化装置を提供することである。
【０００７】
【課題を解決するための手段】
本発明によれば、この目的は、前記１つのパケットの直前のパケットが生成された後に前記パケット化デバイスが実質上時間間隔に入るものとして前記セットに含まれるべき最後のデータ部分を決定する処理手段を含み、前記時間間隔が前記パケットの長さに対応するという事実により達成される。
【０００８】
この方法において、時間間隔の適当な選択により、入力データ流から得られるパケットは、時間的に実質上均等に拡散した瞬間にパケット化装置から出力する準備ができる。それによって、パケットは、そこに含まれるべき最後のデータ部分の到着においてパケット化装置から実質上直ちに出力されることができる。すなわち、実質上パケットのバッファリングは必要とされない。それ故、パケット化装置から出力されるべきパケット間の衝突は、実質上付加的な遅延が導入されることなしに回避される。
【０００９】
さらに、パケットはバーストでパケット化装置から出力されるのではなく、実質上時間的に均等に拡散される。結果として、パケット流が供給されるパケットスイッチにおけるパケット損失率、およびその入力と出力との間の最大のスイッチング遅延は、パケットがこのパケットスイッチにバーストモードで転送される状況において減少され、およびパケットがさらに均等に拡散する速度でこのパケットスイッチに転送される状況において僅かしか増加され、または増加されない。
【００１０】
本発明の別の特徴は、前記パケットが次のデータ部分の前記セットを含む可変長のデータ部分を有することである。
【００１１】
それ故、パケットがパケットスイッチに転送される準備がされた瞬間はデータパートの長さを簡単に変更することによって選択されることができ、それによってパケットに含まれた最後のデータ部分を構成するデータ部分を示し、または選択する。
【００１２】
本発明のさらに別の特徴は、前記パケットが前記次のデータ部分を少なくとも部分的に含む予め定められた長さのデータ部分をそれぞれ有することである。
【００１３】
それ故、パケットが多少のデータ部分を有するデータ部分を単に満たすことによって、すなわち、このデータ部分を完全には満たさない可能性によって選択されることができる。それによって、パケットに含まれた最後のデータ部分を構成するデータ部分が選択される。
【００１４】
本発明のさらに別の特徴は、前記個々のデータ流のビット速度が実質上一定であり、前記各パケットに関しては前記データ部分が予め定められたデータ部分で開始することである。
【００１５】
この方法において、パケットの予め定められた長さのデータ部分が完全に満たされるとき、パケットに対する予め定められたデータ部分の選択は、最後のデータ部分が到着するとき、すなわち、後者の予め定められたデータ部分後の固定した時間間隔の経過したときに決定する。それ故、予め定められたデータ部分を適当に選択することによって、後者のデータ部分は、他にパケットがスイッチに転送されないときに到着することが保証されている。
【００１６】
本発明のさらに別の特徴は、パケットスイッチの入力にそれぞれ結合され、それにパケットを供給して前記パケットスイッチの出力に切換えられる前記複数のパケット化装置を含み、同じ個々のパケット流のパケットが前記パケットスイッチの同じ出力に切換えられ、前記各パケット化デバイスに関して、供給される前記個々のデータ流の第１のパケットの前記最後のデータ部分がランダムに選択されることである。
【００１７】
それによって、個々のデータ流の第１のパケットの最後のデータ部分の選択はランダム化されるので、パケットスイッチの出力において、さらにパケットが同時に出力されることができるという事実による衝突が生じる確率は低く、これらのパケットは異なるパケット化装置から生じ、このパケットスイッチ出力に同時に到着する。この確率は、このようなランダム化が適用されていない状況に関して減少されることに注意すべきである。
【００１８】
本発明のさらに別の特徴は、パケットスイッチの入力にそれぞれ結合され、それにパケットを供給して前記パケットスイッチの出力に切換えられる前記複数のパケット化装置を含み、同じ個々のパケット流のパケットが前記パケットスイッチの同じ出力に切換えられ、前記各パケット化デバイスに関して、供給される前記個々のパケット流の第１のパケットの前記最後のデータ部分が、最後の第１のパケットが切換えられるパケットスイッチ出力で利用可能な帯域幅によって決定されることである。
【００１９】
それによって、最後のデータ部分の選択はパケットが切換えられるパケットスイッチ出力での帯域幅有効性によって決定されるので、さらにパケットが同時に出力されることができるという事実による衝突が生じる確率は減少され、これらのパケットは異なるパケット化デバイスから始まり、このパケットスイッチ出力に同時に到達する。
【００２０】
本発明のさらに別の実施例において、前記各パケットは前記パケットスイッチ入力から前記パケットスイッチ出力に切換えられるときに予め定められた遅延を受け、前記第１のパケットの前記スイッチングの前に、タイミングメッセージが切換えられるべき出力から供給される入力に伝送され、前記タイミングメッセージはパケットが後者の出力で受信される瞬間を時間的に示すことによって後者の出力で利用可能な前記帯域幅を示し、パケットの数が受信される。
【００２１】
この方法において、パケットが受信される瞬間および受信されるパケットの数を示すことによって、パケットが出力で衝突することを回避するためにパケットスイッチに転送されるべき瞬間は、後者の出力でパケットを受信する最適な瞬間から予め定められた遅延を単に減算することによって決定されることができる。すなわち、最後のデータ部分が選択されることができる。出力でそれぞれの瞬間に受信されるパケットの数が高過ぎるとき、この瞬間および最後のデータ部分をランダムに選択することによって衝突は最小にされる。
【００２２】
本発明の上記およびその他の目的および特徴はさらに明瞭となり、発明自体は添付図面と共に実施例の以下の説明を参照することによって良く理解されるであろう。
【００２３】
【実施例】
図１に示されたスイッチングノードは、パケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭを備えた入力パケット化装置と、Ｍ個の入力Ｉ１乃至ＩＭおよびＭ個の出力Ｏ１乃至ＯＭを備えたパケットスイッチＰＳＷと、パケット化デバイスＰＤＰＯ１乃至ＰＤＰＯＭを備えた出力パケット化装置とを含む。パケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭは、スイッチングノードの各入力ＩＮ１乃至ＩＮＭとパケットスイッチＰＳＷの入力Ｉ１乃至ＩＭのそれぞれ１つとの間に接続されている。同様に、パケット化デバイスＰＤＰＯ１乃至ＰＤＰＯＭは、パケットスイッチＰＳＷの出力Ｏ１乃至ＯＭのそれぞれ１つとスイッチングノードの各出力ＯＵＴ１乃至ＯＵＴＭとの間に接続されている。種々のパケット化デバイスとパケットスイッチとの間の全リンクは４線式の両方向性リンクであり、パケットスイッチＰＳＷの全入力および出力は４端子入力−出力によって実際に構成される。同様に、スイッチングノードの全入力および出力は、実際に入力−出力端子である。任意の入力ＩＮ１乃至ＩＮＭに供給されるデータ流はパケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭでパケット化され、パケットスイッチＰＳＷによってその１以上の出力に切換えられる。後者のパケットは、パケット化デバイスＰＤＰＯ１乃至ＰＤＰＯＭのそれぞれ１つによって出力データ流中に非パケット化される。同様に、実際に入力として動作するスイッチングノードの任意の出力ＯＵＴ１乃至ＯＵＴＭに供給されるデータ流はパケット化デバイスＰＤＰＯ１乃至ＰＤＰＯＭによってパケットにおいて配列され、その後これらのパケットは出力として動作する１以上の入力Ｉ１乃至ＩＭにＰＳＷによって切換えられる。後者のパケットは、パケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭのそれぞれ１つによってデータ流中に非パケット化される。それ故、パケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭおよびＰＤＰＯ１乃至ＰＤＰＯＭは、パケット化および非パケット化動作をそれぞれ実行する。
【００２４】
パケット化デバイスＰＤＰＩ１はパケット化器ＰＭを含み、そのデータ入力はＰＤＰＩ１の入力ＩＮ１を構成する。さらにパケット化器ＰＭは、パケット化デバイスＰＤＰＩ１に含まれている４つのバッファＢＵＦ１乃至ＢＵＦ４のそれぞれ１つを介してＰＳＷの４端子入力−出力Ｉ１の４つの端子のそれぞれ１つにそれぞれ結合された４つのデータ出力を有する。最後に、パケット化デバイスはパケット化器ＰＭおよびバッファＢＵＦ１乃至ＢＵＦ４の動作を制御する制御手段ＯＢＣを含む。パケット化デバイスＰＤＰＩ２乃至ＰＤＰＩＭおよびＰＤＰＯ１乃至ＰＤＰＯＭは、ＰＤＰＩ１と同様の方法で形成されている。
【００２５】
パケットスイッチＰＳＷはB.Pauwels 氏らによる文献（1992年10月の横浜においてのInternational Switching Symposium の第１巻、324 乃至328 頁における「Application of the multipath self-routing switch in a combined STM/ATM cross-connect system 」）に記載されているようないわゆるマルチパス自己経路設定（ＭＰＳＲ）スイッチである。このようなＭＰＳＲスイッチの入力に供給されるパケットは、多数のいわゆるスロットを含んでいるマルチスロットセル
（ＭＳＣ）である。各マルチスロットセルは、切換えられるべきスイッチの１以上の出力Ｏ１乃至ＯＭを示す自己経路設定タグ、およびパケットが属する接続を識別する接続基準番号を含む。
【００２６】
スイッチングノードの動作を、図１および２を参照して以下説明する。
複合データ流、例えば図２に示された複合データ流ＣＤＳは、スイッチングノードの各入力ＩＮ１乃至ＩＮＭに供給される。例えば、この複合データ流ＣＤＳは、ＶＣ−ｎ（仮想容器−ｎ）が写像される、すなわちＶＣ−ｎおよび複合オーバーヘッドデータを構成するＳＴＭ−Ｎ（同期転送モジュール−Ｎ）フレームを有する同期デジタル階級（ＳＤＨ）信号である。個々のデータ流ＩＤＳ１乃至ＩＤＳＮおよび個々のオーバーヘッドデータはＶＣ−ｎ中に写像される。それ故、図示されていないオーバーヘッドデータに加えて、複合データ流ＣＤＳは、データ部分がそれぞれ数字１乃至Ｎで示されているＮ個のインターリーブされた個々のデータ流ＩＤＳ１乃至ＩＤＳＮを含む。ＶＣ−ｎにおける個々のデータ流ＩＤＳ１乃至ＩＤＳＮおよびＳＴＭ−ＮフレームにおけるＶＣ−ｎのこのような写像は、M.Sexton氏らによる文献（1992年、ボストンのArtech House社出版の「Transmission networking: SONET and the Synchronous Digital Hierarchy」、第3.4 乃至3.8 章）に記載されている。
【００２７】
パケットスイッチＰＳＷによって切換えられることができるように、複合データ流ＣＤＳは多数のスロットをそれぞれ具備しているパケットにおいて整列されている。さらに、各個々のデータ流ＩＤＳ１乃至ＩＤＳＮは接続基準番号によって示された別々の接続に属する。すなわち、同じ個々のデータ流のデータは同じ出力にスイッチされるが、それは異なる個々のデータ流に関しては異なっていてもよい。それ故、各パケットは、自己経路設定タグおよび接続基準番号を含んでいるオーバーヘッドデータの次に、同じ個々のデータ流のデータ部分のみを含む。複合データ流ＣＤＳの配列およびオーバーヘッドデータの付加は、複合データ流ＣＤＳが供給されるパケット化デバイスにおいて実行される。例えば、入力ＩＮ１に供給された複合データ流ＣＤＳはパケット化デバイスＰＤＰＩ１においてパケットに整列され、その後これらのパケットはパケットスイッチＰＳＷの入力Ｉ１に供給される。同じパケット流、すなわち同じ個々のデータ流から得られる異なるパケットによって後続される通路は異なるが、スイッチの入力と出力との間のパケットの遅延は鋭いピークの分布を有する。すなわちその値は実質上一定である。
【００２８】
第１の実施例において、このパケット化装置ＰＤＰＩ１における再整列動作はパケットスイッチの出力上の負荷を考慮に入れずに実行される。複合データ流ＣＤＳが入力ＩＮ１に供給され、Ｋバイトの予め定められた一定の長さを有するパケットにＰＤＰＩにおいて整列され、個々のデータ流ＩＤＳ１乃至ＩＤＳＮは複合データ流ＣＤＳにおいてバイトインターリーブされる、すなわち各個々のデータ流ＩＤＳ１乃至ＩＤＳＮのバイトは複合データ流ＣＤＳにおいてＮバイト毎に１度現れると想定すると、任意の個々のデータ流のパケットは少なくともＮ×Ｋバイト毎に１度パケットスイッチへ転送されるべきである。各パケットに含まれるべきバイトは、最後のこのようなバイトの到着によりパケットがパケットスイッチＰＳＷに実質上直ちに転送されるように選択される。それ故、（図２に示されたように）第１の個々のデータ流ＩＤＳ１のバイトで始まるＮ×Ｋバイトの時間窓を考慮すると、上記最後のバイトの到達によりＯＢＣはパケットスイッチＰＳＷにそれらの内容を転送するようにＯＢＣによって制御されているバッファＢＵＦ１乃至ＢＵＦ４の１つに第１の個々のデータ流ＩＤＳ１用の第１のパケットを転送するようにＰＤＰＩ１を制御する。ＰＳＷの４端子入力出力、付随した４線式リンク、およびバッファＢＵＦ１乃至ＢＵＦ４はＰＳＷとの間でのデータ速度を係数４だけ減少させることに注意すべきである。しかしながら、第１の実施例における動作は、ＰＳＷの１端子入力出力、付随する１線リンクおよび単一のバッファを有する状況を参照してここに説明される。この第１のパケットは最後が後者の第１のバイトであるＩＤＳ１のＫバイトを含み、時間窓の（Ｋ＋１）番目のバイトの到着によりパケットスイッチに完全に転送される。そのとき第２の個々のデータ流ＩＤＳ２用の第１のパケットは、ＰＳＷに転送される。後者の第１のパケットに含まれた最後のバイトは時間窓のｘ番目のバイトであり、ｘ＝ｊ×Ｎ＋２において、ｘがＫ＋１より小さいまたは等しいためｊは最大の整数である。それによって、後者の第１のパケットの転送はＩＤＳ１の第１のパケットが完全に転送されるまで延期されなければならないので、ｘ番目のバイトの到着においてＰＤＰＩ１によってバッファに既に送られたＩＤＳ２の第１のパケットは、Ｋ−ｊ×Ｎ−１バイト中バッファされる。それ故、（Ｋ−１）／Ｎが整数であるときバッファは必要とされず、この場合においてｊは（Ｋ−１）／Ｎに等しく選択されるのでｘはＫ＋１に等しい。同様に、別の個々のデータ流ＩＤＳ３乃至ＩＤＳＮの第１のパケットは続いてパケットスイッチＰＳＷに転送される。例えば、ｋが３乃至Ｎの整数である個々のデータ流ＩＤＳｋの第１のパケットに含まれた最後のバイトは時間窓のｙ番目のバイトであり、ここでｙ＝ｊ×Ｎ＋ｋであり、ｙが（ｋ−１）×Ｋ＋１より小さいまたは等しいためｊは最大の整数である。ｙ番目のバイトの到着においてＰＤＰＩ１によってバッファに既に送られた後者の第１のパケットは、（ｋ−１）×（Ｋ−１）／Ｎが整数であるときにゼロである（ｋ−１）×Ｋ−ｊ×Ｎ−ｋ＋１バイトに対してバッファされなければならない。すなわち、この場合においてｊは｛（ｋ−１）×Ｋ−ｋ＋１｝／Ｎに等しく���択されるので、ｙは（ｋ−１）×Ｋ＋１に等しく、バッファは必要とされない。それ故、（Ｋ−１）／Ｎが整数であるとき、バッファは必要とされない。（Ｋ−１）／Ｎが整数でないとき、最小のバッファが上記方法によって得られる。さらに、スイッチングノードに最初に供給されたときに複合データ流ＣＤＳから得られた第１のパケットが少ないデータ部分を含むことは明瞭である。それ故、上記されたように一定長のパケットが使用される場合、これらの第１のパケットはデータ部分で完全には満たされていない。一方、これらの第１のパケットが後続するパケットより短い長さを有する場合には可変長パケットを使用する。
【００２９】
出力上の負荷制限が考慮に入れられている別の実施例を、ここに詳細に記載する。
【００３０】
例えば、図２に示された複合データ流ＣＤＳがスイッチングノードの入力ＩＮ１に供給されるとき、多数のスロットから成るパケットにおいて整列され、これらのパケットはパケットスイッチＰＳＷを介して１以上の出力に切換えられる。その場合、接続はＣＤＳの各個々のデータ流ＩＤＳ１乃至ＩＤＳＮに対して設定されなければならない。すなわち、様々な個々のデータ流ＩＤＳ１乃至ＩＤＳＮから得られたパケットが入力パケット化装置においても出力パケット化装置においても衝突を生じさせないためにパケットスイッチＰＳＷに供給されることができる時間が計算されなければならない。同様に、新しい個々のデータ流が複合データ流ＣＤＳ中に含まれるとき、新しい接続はこの新しい個々のデータ流に対して設定されなければならない。
【００３１】
例えばスイッチングノードの入力ＩＮ１と出力ＯＵＴ２との間の新しい個々のデータ流ＩＤＳ１に対する新しい接続が設定される各個々のデータ流に関して、以下のアルゴリズムが実行される。
【００３２】
先ず、メッセージは、発生源制御手段ＯＢＣｏと呼ばれているパケット化デバイスＰＤＰＩ１の制御手段ＯＢＣから、目的地制御手段ＯＢＣｄと呼ばれているパケット化デバイスＰＤＰＯ２の制御手段に送られる。このメッセージは、パケットが既にＰＤＰＩによって送信されている時点をＣＢＣｄに通信する。ＯＢＣｄにおける新しい個々のデータ流ＩＤＳ１から得られたパケットを送信するための新しい時点は、後に説明されるリセットタイミングアルゴリズムによって計算される。この新しい時点は、周期ＴＳＴＰＲを有する周期的に再発生する時間基準に関する時間値ＴＳＴＴＰＶＡＬとして表される。それ故、新しい時点は、事実上周期ＴＳＴＰＲで周期的に再発生する時点に関係し、ここではリセット時点と呼ばれている。ＯＢＣｄはＯＢＣｄの図示されていないメモリにこの新しい時点ＴＳＴＰＶＡＬを記憶し、それにＴＳＴＰＶＡＬを通信するＯＢＣｏにメッセージを送り、その後新しい時点ＴＳＴＰＶＡＬはＯＢＣｏの図示されていないメモリに記憶される。全パケットはパケットスイッチＰＳＷの入力と出力との間の実質上一定値の遅延を受けるから、ＰＤＰＩ１とＰＤＰＯ２との間に固定した時間関係が存在する、すなわちＰＤＰＩ１によってＰＳＷに送られたパケットはＰＤＰＯ２の後に固定した時間、すなわち一定値の遅延を生ずる。さらに、複合データ流ＣＤＳは固定ビット速度を有するＳＤＨ流であるので、そこから得られる次のパケット間の時間関係も実質上固定されるが、ＳＴＭ−１フレームにおけるオーバーヘッドバイトと、いわゆるポインタデクレメントまたはポインタインクレメントと、後に明瞭となるように個々のデータ流ＩＤＳ１を具備している複合データ流のビット速度とＰＳＷに伝送されたパケットのデータ速度との間の周波数シフトとにより完全ではない。それによって、実質上固定された時間関係が同じ個々のデータ流から得られた次のパケット間に存在する。
【００３３】
ＩＤＳ１から得られた第１のパケットは、新しい時点でＰＤＰＩ１によってパケットスイッチＰＳＷに伝送される。この第１のパケットは、新しい時点でＰＤＰＩ１に既に到着している新しい個々のデータ流ＩＤＳ１のデータ部分を含む。第１のパケットは上記リセット時点において伝送された多数のパケットの最初のものあり、後者のパケットはここではリセットパケットと呼ばれている。ここで中間パケットと呼ばれている別のパケットは、リセット時点間の中間時点でＰＳＷに伝送される。後者の中間時点は、以下説明する中間タイミングアルゴリズムにしたがってＯＢＣｏによって計算される。
【００３４】
２つのリセットパケット間のパケットスイッチＰＳＷに伝送されなければならない中間パケットの数ｓはｓ＝ｒ（ｂ／ｐ）であり、ｒ（ξ）＝ｉｎｔ（ξ）＋１−ｉｎｔ（１−ξ＋ｉｎｔ（ξ））である。ｂ＝Ｂ  Ｘ  ＴＳＴＰＲは２つのリセットパケット間のパケットスイッチに伝送されなければならない新しい個々のデータ流ＩＤＳ１のバイトの数であり、ＢはＩＤＳ１の有効なバイト速度、すなわちＰＳＷに伝送されるバイトのバイト速度であり、このＩＤＳ１の有効なバイト速度ＢはＰＳＷに伝送されていないオーバーヘッドの原因となるＩＤＳ１の全体のビット速度に必ずしも等しくなく、ＴＳＴＰＲは上述された時間基準周期であり、すなわち２つのリセット時点間の時間の間隔であり、ｐは１パケット当りの使用可能なバイトの数である。ｂ／ｐが整数であるときはｓ＝ｂ／ｐであり、ｂ／ｐが整数でないときはｓ＝ｉｎｔ（ｂ／ｐ）＋１である。
【００３５】
パケットは１５５．５２メガビット毎秒で伝送されており、それぞれ６８ビットの２つのスロットで構成されている。各パケットに含まれた１つのスロットおよび各スロットにおける１バイトおよび４ビットのオーバーヘッドにより、各パケットはｐ＝７の使用可能なバイトを伝える。時間間隔ＴＳＴＰＲは５１２スロット、すなわち２２４．８μ秒に対応する。例えば個々のデータ流ＩＤＳ１が１２５μ秒のＳＴＭ−１フレーム周期当り２６バイトを含むいわゆる仮想容器ＶＣ−１１において写像され、有効なバイト速度Ｂは２６／１２５メガバイト毎秒に等しく、バイトの数ｂは４６．５６５に等しい。それ故、中間パケットの数ｓは７に等しい。バイトの数ｂは平均数であり、ＳＴＭ−１フレームにおけるオーバーヘッドバイトと、いわゆるポインタデクレメントまたはポインタインクレメントと、個々のデータ流ＩＤＳ１を含む複合データ流のデータ速度とＰＳＷに伝送されたパケットのデータ速度との間の周波数シフトとにより、時間間隔ＴＳＴＰＲにおけるパケットに含まれるべきバイトの数は変化できる。一般に、これは中間パケットの数を変えさせる。その場合、余分のパケットはリセットパケットの直前にパケットスイッチＰＳＷに伝送されなければならないかも知れない。ＳＴＭ−１フレームにおいて写像するＶＣ−１１の上記例に関して、２つのリセットパケット間に伝送されるべき全体のバイト数は４５乃至４９の間で変化するような変化が生じる。この中間パケットの数ｓは、２つのリセットパケット間、すなわち時間間隔ＴＳＴＰＲ内のパケットスイッチＰＳＷに伝送されなければならない。
【００３６】
パケットスイッチＰＳＷ内のパケットの損失および遅延を最小にするため、中間パケットは、リセット時点で伝送されるリセットパケットと共にパケット流ができる限り同期されるような中間時点でパケットスイッチＰＳＷに伝送されるべきである。パケットは、できる限りバッファ作用を避けるためにその中に含まれるべき個々のデータ流ＩＤＳ１の最後のバイトの到着において直ちに伝送されるべきであるので、これらの中間時点は、ＩＤＳ１のバイトが受信される時点と一致しなければならない。それ故、これらの中間時点は両方向性ダイアグラムにおける線に隣接している点によって表され、座標は、ＩＤＳ１のバイトがＰＤＰＩ１によって受信される時間および最後のリセット時点後ＰＳＷに転送された中間パケットの数である。両方の座標はディスクリートな値、すなわちＩＤＳ１のバイトがＰＤＰＩ１によって受信されているディスクリートな時間であり、中間パケットの数に関する０乃至ｓの数は最後のリセットパケット後ＰＳＷに送られ、０はリセットパケットを示し、ｓは次のリセットパケットを示す。中間タイミングアルゴリズムは、以下に示されるようなバイトアルゴリズムをＩＤＳ１の各新しいバイトに関して実行することにおいて存在し、当業者に知られているいわゆるBresenham アルゴリズムに基づいており、W.M.Newman氏らによる文献（1979年、McGraw-Hill International Student Editionsの「Principles of Interactive Computer Graphics 」の25乃至27頁）に記載されている。
ＴＩＭＥＲＥＬ＝（ＢＹＴＥＴＩＭＥ−ＴＳＴＰＶＡＬ）ｍｏｄ５１２
（（０≦ＴＩＭＥＲＥ＜２５６）および（ＲＥＳＰＡＣＫ＝１））ならば
パケット準備
ｅ＝ｄｘ
ＲＥＳＰＡＣＫ＝０
ｅ＝ｅ＋ｄｙ
（ｅ≧０）ならば
パケット準備
ｅ＝ｅ−ｄｘ
（２５６≦ＴＩＭＥＲＥＬ）ならば
ＲＥＳＰＡＣＫ＝１
このバイトアルゴリズムにおいて、ＢＹＴＥＴＩＭＥは、バイトアルゴリズムが実行されるバイトがＰＤＰＩ１によって受信された最後に始まる時間間隔ＴＳＴＰＲに関してスロットの数で時間を示している０乃至５１１の整数である。ＴＳＴＰＶＡＬは既に上述されており、最後のリセットパケットがパケットスイッチＰＳＷに伝送された最後に始まる時間間隔ＴＳＴＰＲに関してスロットの数でリセット時点を示す。ＴＳＴＰＶＡＬは、後に説明される既に上述されたリセットタイミングアルゴリズムによって決定される。それ故、ＴＩＭＥＲＥＬは、バイトアルゴリズムが実行されているためのバイトがＰＤＰＩ１によって受信された時間を最後のリセット時点に関してスロットの数で示している０乃至５１１の整数である。ＲＥＳＰＡＣＫは、リセットパケットがそれぞれ２進の１または０に等しいときにパケットスイッチＰＳＷに伝送されなければならないまたは伝送されないことを示している１ビットの値である。ＲＥＳＰＡＣＫはリセットパケットがＰＳＷに伝送されているときに０にリセットされ、スロットの数が２５６に等しく選択された後に１に設定される。このスロットの数は見付けられるスロットの数より小さいＴＩＭＥＲＥＬの値を確認するのに十分な大きさでなければならないが、５１２より小さくなければならない。すなわち、個々のデータ流ＩＤＳ１のバイトは、ＴＩＭＥＲＥＬが０に等しい最後のリセット時点と、ＴＩＭＥＲＥＬが上記例に関する２５６に等しい最後のリセット時点の後のスロットの数と間でＰＤＰＩ１に到達すべきである。命令「パケット準備」は、パケットがパケットスイッチＰＳＷに伝送される準備がされたことを示す。バイトアルゴリズムが後者の命令が実行されることなしに実行されるとき、バイトアルゴリズムが実行された新しいバイトはパケット化器ＰＭに記憶される。一方、命令「パケット準備」が実行されるとき、後者の新しいバイトはすでにパケット化器ＰＭに集められ、ＩＤＳ１に割当てられたバッファＢＵＦ１乃至ＢＵＦ４のそれぞれ１つを介してＰＳＷに伝送されたバイトと共にパケット中に含まれている。値ｅは、バイトアルゴリズムにおいて使用される整数変数を表す。値ｄｙおよびｄｘはそれぞれ分子および上記隣接する線の傾斜を表す。これらの値ｄｙおよびｄｘは、少数のビットによってのみ表され、値ｄｘ／ｄｙが１時間間隔ＴＳＴＰＲ当りに伝送されるべきパケットの平均値ｂ／ｐに近接するように選択される。例えば、中間パケットの数ｓが７に等しい上記例に関して、ｄｙは３に等しく、ｄｘは２０に等しく選択される。
【００３７】
それ故、ＰＤＰＩ１に到達するＩＤＳ１のそれぞれ新しいバイトに関して、ＴＩＭＥＲＥＬの値が計算される。リセット時点後に到着した第１の新しいバイトに関して、０乃至２５６の間にあるＴＩＭＥＲＥＬの値およびＲＥＳＰＡＣＫの値は１であり、それによってリセットパケットはＰＳＷに送られ、ｅの値は−ｄｘに設定され、ＲＥＳＰＡＣＫは０にリセットされる。次のリセット時点までのＰＤＰＩ１に到達するＩＤＳ１の別のバイトに関して、ｅはｄｙによってインクレメントされ、バイトはパケット化器ＰＭ（バイトアルゴリズムにおいて示されていない）ｅの値が正となるまでに記憶され、その場合においてパケットはパケットスイッチＰＳＷに転送され、ｅの値はｄｘによってデクレメントされる。さらに、ＴＩＭＥＲＥＬが十分に大きい、すなわち２５６より大きいとき、ＲＥＳＰＡＣＫは１に再び設定される。
【００３８】
「ｐａｃｋｎｕｍ」は、表において０に等しい「ｐａｃｋｎｕｍ」の値によって示されている最後のリセットパケットの後に伝送される中間パケットの数を示す。「Ｔｒｉｇｂｙｔｅ」は、最後のリセットパケットの後に受信されるＩＤＳ１のバイトの数を示し、上記命令「パケット準備」は実行される。それ故、「ｔｒｉｇｂｙｔｅ」は、「ｐａｃｋｎｕｍ」の数を有してパケットに含まれたＩＤＳ１の最後のバイトを示す。「ｐａｃｋｂｙｔｅ」は、「ｐａｃｋｎｕｍ」の数を有してパケットに含まれたバイトの数を示す。
【００３９】
0003676422.tif 000002
ここで、次の式が当てはまる。
【００４０】
【数１】
0003676422.tif 000003
「ｐａｃｋｂｙｔｅ」は「ｔｒｉｇｂｙｔｅ」と「ｔｒｉｇｂｙｔｅ」の前の値との間の差である。「ｐａｃｋｎｕｍ」が７に等しい表の最後の行は、次のリセットパケットの前、すなわち時間間隔ＴＳＴＰＲ内にパケットスイッチＰＳＷに伝送されるべきＩＤＳ１のバイトの数が４７より大きいときにパケットスイッチＰＳＷに伝送されるべき可能な余分の中間パケットを示す。その場合、この余分の中間パケットの後に伝送されるリセットパケットは、時間間隔ＴＳＴＰＲ中にＰＳＷに伝送されるべきバイトの全体の数に依存して１または２バイトのみを含むことができる。例えば、４５バイトのみがこの時間間隔ＴＳＴＰＲ内にＰＳＡＷに送られなければならないとき、リセットパケットは５バイトのみを含むことに注意すべきである。これは、表における０に等しい「ｐａｃｋｎｕｍ」に対する「ｐａｃｋｂｙｔｅ」の変数から明らかである。
【００４１】
それ故、２つのリセット時点間の中間時点のシーケンスはほぼ同期シーケンスを構成し、その同期性はＳＴＭ−１フレームにおける既に前述されたオーバーヘッドバイトと、ポインタデクレメントおよびインクレメントと、パケットがその中に含まれるべき最後のバイトの到着においてのみ伝送されるという事実とによって乱されるだけである。
【００４２】
上記を参照してリセット時点を決定するリセットタイミングアルゴリズムをここで詳細に説明する。
各パケットは２つのスロットを含むので、可能なリセット時点はＴＳＴＰＶＡＬの偶数値によって示される。５１２個のスロットに対応している時間間隔ＴＳＴＰＲおよびこの時間間隔ＴＳＴＰＲにおける７に等しい中間パケットの数ｓを有する上記実施例に関して、パケットは平均してＳ＝７３．１４３のスロット毎にＰＳＷに伝送される。それ故、長さＳの時間間隔内のＴＳＴＰＶＡＬの３６の可能な値は、値７３．１４３は７３．１４３個のスロットの次の間隔に対して値０に対応し、この値と７２との間の差は２つのスロットより小さいので、値７２を除いた０乃至７３．１４３の偶数が識別される。それ故、減少したリセット時点ＴＳＴＰＲＥＤと呼ばれる長さＳの時間間隔内のＴＳＴＰＶＡＬの可能な値は０とＴとの間の偶数値であり、ここでＴは上記実施例において７０に等しい。ＴＳＴＰ−過剰と呼ばれている差Ｓ−Ｔは、上記実施例において３．１４３に等しい。
【００４３】
ＴＳＴＰＲＥＤのこれらの可能な値は次の要求によって選択される。
【００４４】
−ＴＳＴＰＲＥＤの各可能な値において多くて３つのパケットがＰＳＷに送られるので、パケット化装置をパケットスイッチＰＳＷに接続する４本の線の多くて３本が使用され、それによってこれらの線の１本の故障はなんら問題とならない。
【００４５】
−ＰＳＷに伝送されるパケットの数はＴＳＴＰＲＥＤの全ての可能な値にわたってできるだけ均等に分配されなければならない。
【００４６】
ＴＳＴＰＲＥＤの全ての可能な値にわたってパケットの平滑な分布を得るために、ξがＴＳＴＰＲＥＤの選択された候補値ｘに対するスロットの数の距離である加重関数ｗ（ξ）は次のように選択される。
【００４７】
【数２】
0003676422.tif 000004
位相分布関数ｆ（ｘ）の関数である位相影響関数ｃ（ｆ，ｘ）が計算される。種々のこのような様々な位相分布関数ｆ（ｘ）が識別されることができる。すなわちｆｏ（ｘ）は時間ｘで発生源パケット化装置ＰＤＰＩ１からＰＳＷに伝送されるパケットの数の値であり、ｆｄ（ｘ）はＩＤＳ１からのパケットが受信される同じリンク上の目的地パケット化デバイスＰＤＰＯ２における時間ｘにおいてＰＳＷから受信されるパケットの数の値であり、ｆｄ' （ｘ）、ｆｄ''（ｘ）およびｆｄ''' （ｘ）はＩＤＳ１からのパケットが受信されるリンクと異なる各リンク上の目的地パケット化デバイスＰＤＰＯ２における時間ｘにおけるＰＳＷから受信されるパケットの数の値である。位相影響関数ｃ（ｆ，ｘ）は、上記長さＳを有する間隔におけるξの値に対してｗ（ξ）によって加重され、ｘに対して対称的に延在している位相分布ｆ（ξ）の値の合計である。位相分布ｆ（ξ）は、この長さＳに等しい周期で周期的である。それ故、ｆ（ξ）が０とＳとの間のξを有する基準間隔Ｒにおいて知られているとき、
0003676422.tif 000005
であり、ｃ０（ｆ，ｘ）＝２ｆ（ｘ）はｘにおける位相分布の影響を表す。
【００４８】
【数３】
0003676422.tif 000006
は、基準間隔Ｒの左の第１の拡張間隔における位相分布の影響を表し、
【数４】
0003676422.tif 000007
は、基準間隔Ｒ中の位相分布の影響を表し、
【数５】
0003676422.tif 000008
は、基準間隔Ｒの右の第２の拡張間隔における位相分布の影響を表す。
【００４９】
ここで、既に上述されたようなｒ（ξ）＝ｉｎｔ（ξ）＋１−ｉｎｔ（１−ξ＋ｉｎｔ（ξ））によって、ｉ１，ｉ２，ｉ３およびｉ４の値は、次の通りである。
【００５０】
【数６】
0003676422.tif 000009
ＴＳＴＰＲＥＤは、次のように決定される。値ｆ（ｘ）が３より小さいＴＳＴＰＲＥＤの全ての可能な値ｘに関して、ｃｄｏ（ｘ）＝ｃ（９ｆｄ＋ｆｄ＋ｆｄ' ＋ｆｄ''＋ｆｄ''' ＋ｆｏ，ｘ）を計算し、ｃｄｏ（ｘ）が最小値に達するそれらの値ｘのみをＴＳＴＰＲＥＤに関する可能な値として保持する。ｆｄ（ｘ）に割当てられた９の加重は、ｆｄ（ｘ）の高い値を補償するために位相分布関数ｆｄ' （ｘ）、ｆｄ''（ｘ）およびｆｄ''' の低い値を避けることに注意すべきである。さらに、パケットは、３つの他のリンクにわたって均等に拡散されるときより３倍遅くＩＤＳ１に関係したリンクを介してパケットスイッチＰＳＷのみに転送され、この加重は実際にｆｄ' （ｘ）、ｆｄ''（ｘ）およびｆｄ''' の合計した加重の３倍に大きくすべきである。しかしながら、ｆｄ（ｘ）に割当てられた加重の他の値が、多少変更した位相拡張特性を有してリセットタイミングアルゴリズムを均等に良好に実行させることは明らかである。残りの可能な値ｘに関して、ｃｄ（ｘ）＝ｃ（ｆｄ，ｘ）を計算し、ｃｄ（ｘ）が最小値ｍｄに達する値ｘのみをＴＳＴＰＲＥＤの可能な値として保持する。この最小値は、出力パケット化装置におけるパケットのオーバーフローを避けるためにしきい値より小さくすべきである。ｍｄがこのしきい値より大きいとき、ＩＤＳ１に対する新しい接続は設定されない。ｘの１つの可能な値のみが残存する場合、これはＴＳＴＰＲＥＤとして選択される。ｘの１以上の可能な値が残存する場合、ｃｏ（ｘ）＝ｃ（ｆｏ，ｘ）を計算し、ｃｏ（ｘ）が最小値ｍｏに達するｘの値をＴＳＴＰＲＥＤの値として選択する。
【００５１】
ＴＳＴＰＲＥＤのこのように計算した値から、ＴＳＴＰＶＡＬは次のように計算される。全体の位相影響関数Ｃ（ｆ，ｘ）は次のように計算される。
【００５２】
【数７】
0003676422.tif 000010
ここで、ｘ＜２５６であるとき：Ｉ１＝ｘ＋２５６＝Ｉ３およびＩ２＝０＝Ｉ４であり、ｘ＞２５６であるとき：Ｉ１＝５１１＝Ｉ３およびＩ２＝ｘ−２５６＝Ｉ４である。
【００５３】
ＴＳＴＰＶＡＬの各可能な値ｘ、すなわち各値ＴＳＴＰＲＥＤ＋ｊ×Ｓに関して、ｊは６に等しい０からｓ−１までの整数であり、ｓおよびＳは既に上述されており、Ｃ（ｆｏ，ｘ）は計算される。Ｃ（ｆｏ，ｘ）が最小値に達するｘの値は、ＴＳＴＰＶＡＬに対する値として選択される。
【００５４】
ＩＤＳ１のバイトがリセット時点でＰＤＰＩ１に達するとき、リセットパケットおよび次の中間パケットはバッファＢＵＦ１乃至ＢＵＦ４においてバッファされる必要はないことを注意すべきである。しかしながら、リセットパケットがリセット時点ではＰＳＷに送られず、このリセット時点またはその後のＩＤＳ１の第１のバッファの到着においてＰＳＷに送られるという事実により、バッファ動作はバッファＢＵＦ１乃至ＢＵＦ４において依然必要である。さらに、上記リセットタイミングアルゴリズムにおける位相影響関数ｃｄ（ｘ）の値がＴＳＴＰＶＡＬのすべての残存する可能な値に対して大き過ぎるとき、これらの残存する可能な値ｘの１つはＴＳＴＰＶＡＬの値としてランダムに選択されることができる。その場合、この接続に対するパケットはＰＳＷに送られるまでバッファＢＵＦ１乃至ＢＵＦ４においてバッファされなければならない。
【００５５】
本発明の原理が特定の装置に関して上記説明されているが、この説明が単なる例示として行われ、本発明の技術的範囲を限定するものではないことは明瞭に理解されるべきである。
【図面の簡単な説明】
【図１】パケット化デバイスＰＤＰＩ１乃至ＰＤＰＩＭおよびＰＤＰＯ１乃至ＰＤＰＯＭを含む本発明によるパケット化装置を有するスイッチングノードのブロック図。
【図２】図１のスイッチングノードに供給された入力複合データ流ＣＤＳを示す図。
【図１】
0003676422.tif 000011
【図２】
0003676422.tif 000012