(57)【要約】リングをなす一連のサブアドレス発生器を使用する一連のデータパケットのアドレス指定技法である。この技法は、特に、共用メモリ出力バッファ型スイッチ構造及び関連するメモリに適合する。一連のサブアドレス発生器の各々は、一連のタイムスロットで受信された所定サイズのデータバイトパケットに対してアドレスを割り当てる。この技法は、これらのパケットから到着時間に基づいて配列されたスーパーパケットを生成し、このパケットに対して、パケット間にオーバーラップがなく、かつ、隣接するパケット間に隙間がないようにして、共用メモリ内のメモリを順次割り当て、各スーパーパケットについてメモリのアドレスが割り当てられると、スーパーパケット内の個々のパケットに対してアドレスを割り当てる。
2005539405.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力データラインカードからの一連のデータパケットをアドレス指定して、出力バッファ型スイッチ構造の一連の共用メモリブロックセクションにおけるそれらのパケットのメモリ記憶を可能にする方法であって、共用メモリブロックセクションの各々は、出力ポート専用のキューに割り当てられており、前記方法が、
閉じたリング構造をなすように複数の同様のサブアドレス発生器を順次接続するステップであって、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受信された入力データトラフィックの所定サイズのデータバイトパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへとパケット合成を行うことができることからなる、ステップと、
サブアドレス発生器から宛先のキュー内の最初のスーパーパケットアドレスを割り当てることにより、スーパーパケットに対して連続するメモリブロックを割り当てるステップと、
前記割り当てるステップに続いて、前記最初の開始アドレスにスーパーパケットのサイズを加え、前記リングをなす一連のサブアドレス発生器に沿った次のサブアドレス発生器へと順次移動することにより、前記リングに沿ってサブアドレス発生器からサブアドレス発生器へと前記共用メモリセクション内のメモリを順次割り当てることによって、次のスーパーパケットの開始アドレスを生成するステップと、
各スーパーパケットにアドレスが割り当てられると、スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、アドレスを同時に割り当てることによって、対応するサブアドレス発生器においてパケット分解を行うステップ
を含む、方法。
【請求項２】
すべてのサブアドレス発生器が、それらの各々の前記パケット合成とパケット分解を同時に実行するよう動作する、請求項１の方法。
【請求項３】
前記パケットが、パケット間にオーバーラップがなく、かつ、隣接するパケット間に隙間がないように、前記共用メモリセクションに書き込まれる、請求項１の方法。
【請求項４】
前記メモリ割り当てが、タイムスロット毎に次のサブアドレス発生器に移動して行われる、請求項１の方法。
【請求項５】
前記メモリ割り当ては、１タイムスロットより大きな割り当て時間期間後に、次のサブアドレス発生器に移動して行われ、前記時間期間は、スーパーパケットの最大サイズに比例することからなる、請求項１の方法。
【請求項６】
アドレス生成の並列処理が、サブアドレス発生器、ポート数、及び帯域幅に関してスケーラブルに実施される、請求項５の方法。
【請求項７】
すべてのスーパーパケットについて、どの２つのパケットもオーバーラップせず、かつ、隣接するパケット同士の共用メモリに隙間がないように、各パケットに独自のアドレスが与えられる、請求項１の方法。
【請求項８】
前記パケット分解の速度が、前記パケット合成の速度に一致する、請求項３の方法。
【請求項９】
64 OC192（１０Gbps）I/Oポートをサポートし、４０バイトパケットが、４０ｎｓ（ナノ秒）毎に前記ラインカードから受け取られる、請求項２の方法。
【請求項１０】
前記アドレス割り当ての能力が、すべてのパケットが同じキューに属する場合に、６４パケット／４０ｎｓ（ナノ秒）まで拡張される、請求項９の方法。
【請求項１１】
複数の入力データラインカードからの一連のデータパケットをアドレス指定して、出力バッファ型スイッチ構造の一連の共用メモリブロックセクションにおけるそれらのパケットのメモリ記憶を可能にするシステムにおいて、共用メモリブロックセクションの各々は、出力ポート専用のキューに割り当てられており、アドレス発生器が、前記システムとの組み合わせにおいて、
閉じたリング構造をなすように順次接続された複数の同様のサブアドレス発生器であって、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受信された入力データトラフィックの所定サイズのバイトパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへとパケット合成を行うことができることからなる、複数の同様のサブアドレス発生器と、
サブアドレス発生器から宛先のキュー内の最初の開始アドレスを割り当てることにより、スーパーパケットに対して連続するメモリブロックを割り当てることによって、前記リングに沿ってサブアドレス発生器からサブアドレス発生器へと共用メモリセクション内のメモリを順次割り当て、これに続いて、前記最初の開始アドレスにスーパーパケットのサイズを加えることによって、次のスーパーパケットの開始アドレスを生成し、前記サブアドレス発生器のリングに沿って次のサブアドレス発生器へと順次移動するための手段と、
各スーパーパケットにアドレスが割り当てられると、前記スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、アドレスを同時に割り当てるよう動作可能なパケット分解手段
を備える、アドレス発生器。
【請求項１２】
すべてのサブアドレス発生器が、それらの各々の前記パケット合成とパケット分解を同時に実行するよう動作する、請求項１１のアドレス発生器。
【請求項１３】
前記パケットが、パケット間にオーバーラップがなく、かつ、隣接するパケット間に隙間がないように、前記共用メモリセクションに書き込まれる、請求項１１のアドレス発生器。
【請求項１４】
前記メモリを割り当てるための手段が、タイムスロット毎に次のサブアドレス発生器に移動する、請求項１１のアドレス発生器。
【請求項１５】
前記メモリを割り当てるための手段は、１タイムスロットより大きな割り当て時間期間後に、次のサブアドレス発生器に移動し、前記時間期間は、スーパーパケットの最大サイズに比例することからなる、請求項１１のアドレス発生器。
【請求項１６】
アドレス生成の並列処理が、サブアドレス発生器、ポート数、及び帯域幅に関してスケーラブルに実施される、請求項１５のアドレス発生器。
【請求項１７】
すべてのスーパーパケットについて、どの２つのパケットもオーバーラップせず、かつ、隣接するパケット同士の共用メモリに隙間がないように、各パケットに独自のアドレスが与えられる、請求項１１のアドレス発生器。
【請求項１８】
前記パケット分解の速度が、前記パケット合成の速度に一致する、請求項１２のアドレス発生器。
【請求項１９】
64 OC192（１０Gbps）I/Oポートをサポートし、４０バイトパケットが、４０ｎｓ（ナノ秒）毎に前記ラインカードから受け取られる、請求項１２のアドレス発生器。
【請求項２０】
前記アドレス割り当ての能力が、すべてのパケットが同じキューに属する場合に、６４パケット／４０ｎｓ（ナノ秒）まで拡張される、請求項１９のアドレス発生器。
【請求項２１】
一連のデータパケットをアドレス指定してそれらのパケットを記憶できるようにするためのアドレス発生器において、
閉じたリング構造をなすように順次接続された複数の同様のサブアドレス発生器であって、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受信された所定サイズのバイトデータパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへとパケット合成を行うことができることからなる、複数の同様のサブアドレス発生器と、
サブアドレス発生器から宛先のキュー内の最初の開始アドレスを割り当てることにより、スーパーパケットに対して、前記リングに沿ってサブアドレス発生器からサブアドレス発生器へとメモリを順次割り当て、これに続いて、前記最初の開始アドレスにスーパーパケットのサイズを加えることによって、次のスーパーパケットの開始アドレスを生成し、前記サブアドレス発生器のリングに沿って次のサブアドレス発生器へと順次移動するための手段と、
各スーパーパケットにアドレスが割り当てられると、前記スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、アドレスを同時に割り当てるよう動作可能なパケット分解手段
を備える、アドレス発生器。
【請求項２２】
一連のデータパケットをアドレス指定してそれらのメモリ記憶を可能にする方法であって、
閉じたリング構造をなすように複数の同様のサブアドレス発生器を順次接続するステップであって、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受信された入力データトラフィックの所定サイズのデータバイトパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへとパケット合成を行うことができることからなる、ステップと、
サブアドレス発生器から宛先のキュー内の最初の開始アドレスを割り当てることにより、スーパーパケットに対して、連続するメモリブロックを割り当て、これに続いて、前記最初の開始アドレスにスーパーパケットのサイズを加えることによって、次のスーパーパケットについての開始アドレスを生成し、前記サブアドレス発生器のリングに沿って次のサブアドレス発生器へと順次移動するステップと、
各スーパーパケットにアドレスが割り当てられると、前記スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、アドレスを同時に割り当てることにより、対応するサブアドレス発生器においてパケット分解を行うステップ
を含む、方法。
【請求項２３】
すべてのサブアドレス発生器が、それらの各々の前記パケット合成とパケット分解を同時に実行するよう動作する、請求項２２の方法。
【請求項２４】
複数のデータトラフィックストリームを受信し出力するための電子データスイッチ構造であって、該ストリームは、前記スイッチ構造によってデータトラフィックラインカードの入力ポートから出力ポートへと切り換えられ、前記スイッチ構造が、
前記スイッチ構造内においてデータキューに割り当てられた共用メモリセクションであって、前記出力ポートへと切り換えられるデータの出力バッファリング機能を有する、共用メモリセクションと、
複数の入力データラインカードからの一連のデータパケットをアドレス指定して、出力バッファ型スイッチ構造の一連の共用メモリブロックセクションにおけるそれらのパケットのメモリ記憶を可能にするためのアドレス発生器であって、各共用メモリブロックセクションは出力ポートに専用のキューに割り当てられ、該アドレス発生器は、閉じたリング構造をなすように順次接続された複数の同様のサブアドレス発生器を有し、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受信された入力データトラフィックの所定サイズのバイトパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへとパケット合成を行うことができることからなる、アドレス発生器と、
サブアドレス発生器から宛先のキュー内の最初の開始アドレスを割り当てることにより、スーパーパケットに対して連続するメモリブロックを割り当てることによって、前記リングに沿ってサブアドレス発生器からサブアドレス発生器へと共用メモリセクション内のメモリを順次割り当て、これに続いて、前記最初の開始アドレスにスーパーパケットのサイズを加えることによって、次のスーパーパケットの開始アドレスを生成し、前記サブアドレス発生器のリングに沿って次のサブアドレス発生器へと順次移動するための、前記アドレス発生器内の手段と、
各スーパーパケットにアドレスが割り当てられると、前記スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、アドレスを同時に割り当てるよう動作可能なパケット分解手段と、
前記それぞれの入力データパケットにアドレスを与えて、前記共用メモリの対応するセクション、及び、前記それぞれの出力ポートに専用の対応するキューにおけるそれらのパケットの格納を可能にするための手段
を備える、電子データスイッチ構造。
【請求項２５】
一連のデータパケットのアドレス指定方法であって、該方法は、特に、共用メモリ出力バッファ型スイッチ構造及び関連するメモリに適合するものであり、該方法は、
一連のサブアドレス発生器のリングを使用して、各々のサブアドレス発生器が、連続するタイムスロットで受信された所定サイズのデータバイトパケットに対してアドレスを割り当てるようにするステップと、
それらのパケットから、到着時間に基づいて配列されるスーパーパケットを生成するステップと、
それらスーパーパケットに対して、パケット間にオーバーラップがなく、かつ、隣接するパケット間に隙間がないようにして、共用メモリ内のメモリを順次割り当るステップと、
各スーパーパケットに対してメモリのアドレスが割り当てられると、前記スーパーパケット内の個々のパケットに対してアドレスを割り当てるステップ
を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の入力データラインカード、または、他のソースからのシーケンシャルなデータパケットにメモリ記憶アドレスを割り当てるためのシステム及び技法に関し、より詳細には、共用メモリ選択、好ましくは、METHOD SCALABLE NON-BLOCKING SHARED MEMORY OUTPUT-BUFFERED SWITCHING OF VARIABLE LENGTH DATA PACKETS FOR PLURALITIES OF PORTS AT FULL LINE RATE, AND APPARATUS THEREFORと題する係属中の下記米国特許出願第09/941,144号（2001年8月28日に出願され、本願と譲受人が同じである）に記載ざれたタイプの如き出力バッファ型（output-buffered）スイッチ構造の選択された共用メモリへデータパケットを書き込みのためのアドレス指定に関し、パケット間にオーバーラップがなく、隣接するデータパケット間に隙間すなわちギャップが存在しないようにするものである。
【背景技術】
【０００２】
本発明のアドレス指定方法は、より一般的な応用形態を有するものであるが、本明細書では、上述したタイプの出力バッファ型スイッチ構造（または出力バッファ型スイッチファブリック）と共に使用される好適な態様及び最良の態様を参照して本発明を例示的に説明する。この態様では、メモリ空間を画定する複数の同様の連続するデータメモリチャンネルから構成される中央共用メモリアーキテクチャが利用され、入力ポートから連続的に、連続するメモリチャンネルの連続するメモリセルにデータが伝送される時間は一定の限定された時間であり、メモリ空間中を交互に横断して伝送される。これにより、共用メモリの無閉塞の出力バッファ型データスイッチングが可能となり、この場合、データは、メモリチャンネルに均一に記憶される。このように、入力ポートから連続する各々のメモリチャンネルにデータを記憶する時間を制限することにより、メモリ空間全体にわたって無閉塞かつ有限の遅延をもってデータをメモリに書き込むことを保証するという課題が見事に解決される。
【０００３】
上記の同時係属出願に記載されているように、この技法は、データトラフィックラインカードの入力ポートから出力ポートに切り換えられるデータトラフィックストリームの複数のｍ個のキューを受け取り、及び出力する方法を含む。ｎ個の複数の同様の連続するデータメモリチャンネルが提供されるが、そのメモリチャンネルの各々は、上記ｍ個のキューに割り当てられた共用メモリ空間を画定する複数のメモリセルを有する。バッファリング（緩衝機能）は、ｍ個のメモリセルについて実施され、各メモリチャンネルの前に置かれて、ラインカードトラフィックストリームから各メモリチャンネルに切り換えられるデータを受け取ると共にそのデータをバッファリングし、十分なバッファリングを提供して、最大ｎ個のラインカードからのバーストを吸収する。連続するデータは、連続するメモリチャンネルの各々の対応する連続するセルに対してのみ、一定の限定された時間中に、上述したように、メモリ空間全体を交互に横断するやり方で各キューに分配され、これによって、無閉塞の共用メモリ出力バッファ型データスイッチングI/O（入力／出力）ポートが提供される。入力ポートからの各パケットは、アドレス発生器から、パケットが格納されることになる共用メモリ内の位置を画定する宛先キュー内のアドレスを取得する。出力バッファ型スイッチ構造をこのように使用することにより、あるキュー向けのパケットがすべての入力ポートから到来するようにすることができ、これらのすべてのパケットは、上述したように、パケット間のオーバーラップがなく、かつ、隣接するパケット間に隙間すなわちギャップがないようにして、共用メモリに書き込まれる。したがって、どのパケットのアドレスも、既にアドレスが割り当てられているすべてのパケットに依存し、パケットは順番に割り当てられることになる。
【０００４】
一例として、本発明のアドレス発生方法と共に動作する共用メモリを具現化するシステムは、スイッチ構造の性能に影響を与えることなく最低４０バイトのパケットをサポートすることができ、各１０Ｇbpsポートから、４０ns（ナノ秒）の一定タイムスロット毎に４０バイトのパケットを受け取り、４０ns毎に６４個のパケットにアドレスを割り当てる能力を有する。そして、この場合において、これらすべてのパケットは同じキューに属する。
【０００５】
本発明は、これを、他の従来のアプローチにおいて提案されているような技術を押し進めようとすることなく実施する。それらのアプローチとは異なり、本発明は、後述するように、並列処理アルゴリズムを用いるものであり、本発明のアドレス発生器は、ポートの数及び帯域幅の両方に対してスケーラブルである。
【特許文献１】米国特許出願第09/941,144号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、本発明の主な目的は、特に、出力バッファ型共用メモリスイッチ構造においてパケットのアドレス指定を可能にするのに適した（但し、これに限定するわけではない）新規かつ改良されたアドレス発生方法を、新規な並列処理によるスケーラブルなアプローチにより、連続的にアドレス指定されたパケット間にオーバーラップがなく、かつ、隣接するパケット間に隙間すなわちギャップが存在しないようにして、提供することである。
【０００７】
更なる目的は、本発明のアドレス指定技法を実施するための新規なアドレス発生器であって、サブアドレス発生器が順次接続されたリング構造を具現し、メモリ割り当てが、サブアドレス発生器からサブアドレス発生器にリングに沿って順次実施される、アドレス発生器を提供することである。
【０００８】
さらに他の目的は、先行するサブアドレス発生器のアドレス割り当て値に対してパケットの現在のサイズを加えることにより、連続するアドレス指定を、リングをなす順次配置されたサブアドレス発生器において実施する新規なアドレス発生であって、したがって、パケットのアドレスは、既にアドレスが割り当てられているすべてのパケットに依存し、そのような割り当てが連続的に行われる、アドレス発生を提供することである。
【０００９】
他の及び更なる目的については後述するが、特許請求の範囲に特に詳しく記載されている。
【００１０】
以下、添付図面を参照して本発明を説明する。
【課題を解決するための手段】
【００１１】
しかしながら、本発明の重要な局面の１つから要約すると、本発明は、複数の入力データラインカードからの連続するデータパケットをアドレス指定して、出力バッファ型スイッチ構造の一連の共用メモリブロックセクションにおけるそれらのデータパケットのメモリ記憶を可能にする方法であり、この一連の共用メモリブロックセクション（またはデータパケット）の各々は、出力ポート専用のキューに割り当てられる。この方法は、閉じたリング構造をなすように複数の同様のサブアドレス発生器を順次接続するステップであって、各サブアドレス発生器は、複数の連続するタイムスロットにおいて受け取られた入力データトラフィックの所定のサイズのデータバイトパケットに対してアドレスを割り当てて、到着時間に基づいて配列されるスーパーパケットへのパケット合成を行うことが可能である、ステップと、サブアドレス発生器から宛先キュー内の最初のスーパーパケットアドレスを割り当てることによって、スーパーパケットに対して連続するメモリブロックを割り当てるステップと、その後すぐに、スーパーパケットのサイズをその上記最初の開始アドレスに加えることによって次のスーパーパケットの開始アドレスを生成するステップと、リングの順次配置されたサブアドレス発生器に沿って次のサブアドレス発生器に順次移動するステップと、これによって、このリングに沿ってサブアドレス発生器から次のサブアドレス発生器へと共用メモリセクションにメモリを順次割り当てるステップと、各スーパーパケットにアドレスが割り当てられると、スーパーパケット内の個々のパケットに対して、それらのパケットの到着順に基づいて、同時にアドレスを割り当てることによって対応するサブアドレス発生器においてパケットの分解を行うステップとを含む。
【００１２】
好適な実施形態及び最良モードの構成については後述する。
【実施例】
【００１３】
図８には、（出願人である譲受人によって「Agora ESF」（ESFは電子スイッチ構造）と命名された全体システムが示されている。このシステムは、本発明のアドレス発生器出力AGSによってアドレス指定されるよう接続された、上述のＭにおける出力バッファ型共用メモリを備える。しかしながら、完全なシステムを説明する前に、本発明のアドレス発生システムを先ず検討することが有用であろう。
【００１４】
前述のアドレス発生システムのアドレス発生器リング構造を図１に示すが、これは、閉じたリング構造をなすように順次接続された複数のサブアドレス発生器AG0〜AGnを有する。前述の例では、各サブアドレス発生器は、ラインカードまたは他のデータパケット源からの４０Gbpsの入力トラフィックデータに対してアドレスを割り当てることが可能であろう。
【００１５】
本発明の技術によれば、全てのアドレス割り当てが３つの部分に分割される。すなわち、パケット合成、メモリ割り当て、パケット分解の３つである。パケット合成（図２）は、到来するデータパケットを、パケットが到着時間に基づいて配列された「スーパーパケット」に組みたてる。メモリ割り当て（図３）は、アドレス指定リングに沿ったサブアドレス発生器からサブアドレス発生器への順次的な手順（図１においてAG0からAG１へ、AG１からAG２へなど）である。これは、開始アドレスを割り当てることによってスーパーパケットに対して連続するメモリブロックを割り当て、現在のスーパーパケットのサイズにその開始アドレスを加えることによって次のスーパーパケットの開始アドレスを生成し、次に、リングの次のサブアドレス発生器に移動する。最後に、パケット分解（図４）が、到着順に基づいてスーパーパケット内の各パケットのアドレスを割り当てる。リングをなすすべてのサブアドレス発生器は、パケット合成機能及びパケット分解機能を同時に実行する。
【００１６】
一例として、図２乃至図４の４つのサブアドレス発生器AG0、AＧ１、AG２及びAＧ３を考える。これらの各々のサブアドレス発生器は、４つの連続する一定のタイムスロットにおいて、キューQ０内の合成された（または組み立てられた）スーパーパケットブロックa0、a1、a2、及びa3と、b0、b1、b2及びb3と、c0、c1、c2及びc3と、d0、d1、d2及びd3によってそれぞれ表される、アドレス要求にある新しいパケットを受け取る。図の右側の時間グラフ（「ｔ」）を参照すると、図２及び図３のパケット合成及びパケット割り当て機能は、サブアドレス発生器AＧ０から開始する。タイムスロット０において、１つのパケットのみがサブアドレス発生器AＧ０に現れており、このため、スーパーパケットはパケットを１つだけ含む。タイムスロット１では、各サブアドレス発生器は、異なる陰影を施された、スーパーパケットを構成する２つのパケットを受け取っている。サブアドレス発生器AＧ０からメモリ割り当てが開始する場合、各サブアドレス発生器が、これら２つのパケットからなるスーパーパケットを受け取ると、メモリ割り当てはサブアドレス発生器AＧ１に移動する（図３）。メモリ割り当ては、図１のアドレス発生器のリングに沿って移動するので、これまでいずれのスーパーパケットにもないパケットが、新しいスーパーパケットを形成する（各スーパーパケットは、異なる陰影で示されている）。こうして、メモリ割り当ては、各スーパーパケットに対してメモリ空間を割り当てる。この例では、メモリ割り当ては、スーパーパケット０にアドレス０を割り当て、次に、開始アドレスにスーパーパケットのサイズa0を加算し、この加算結果が、メモリ割り当てが次のサブアドレス発生器に移動したときの開始アドレスとして使用されることになる。より詳しくは、上記のタイムスロット１において、メモリ割り当てはサブアドレス発生器１に移動し、図２の陰影を施されたスーパーパケットに開始アドレス
【００１７】
【数１】
2005539405.tif 000003
【００１８】
を割り当てる。メモリ割り当ては、次に、開始アドレス
【００１９】
【数２】
2005539405.tif 000004
【００２０】
に、スーパーパケットのサイズ
【００２１】
【数３】
2005539405.tif 000005
【００２２】
を加えて、次のサブアドレス発生器の開始アドレスを設定する。すべてのタイムスロットにおいて、メモリ割り当ては、アドレス発生器のリングに沿って次のサブアドレス発生器に移動し、開始アドレスにスーパーパケットのサイズを加えて、次のサブアドレス発生器の開始アドレスとする。したがって、図には、各タイムスロット毎の各サブアドレス発生器についてのメモリ割り当てと、次のサブアドレス発生器に対する開始アドレスが示されている。
【００２３】
縦方向の時間軸ｔに沿ったすべてのタイムスロット毎に、メモリ割り当ては、アドレス発生器のリングに沿って次のサブアドレス発生器に移動する。合計を計算するブロックは、各タイムスロットにおいてメモリ割り当てを実行するサブアドレス発生器と、それに対応する次のサブアドレス発生器に対する開始アドレスを示している。
【００２４】
上述したように、図２のパケット合成及び前述の図４のパケット分解は同時に行われる。したがって、パケット分解に関しては、図４に示されるように、スーパーパケットに対する開始アドレスが割り当てられると、各サブアドレス発生器におけるパケット分解は、スーパーパケット内の個々のパケットに対して同時にアドレスを割り当てる。この例では、小文字（a0、b0など）は、前述のようにパケットとそのサイズを表し、対応する大文字（A0、B0など）は、（図４において）スーパーパケットの個々のパケットに割り当てられたアドレスを表すために用いられる。このようなアドレス発生器AG0における最初のスーパーパケットの開始アドレスはA0＝０であり、これは、このスーパーパケット及びパケット分解において唯一のパケットa0としてスーパーパケットに割り当てられる。２番目のスーパーパケットAG0の開始アドレスA1は、A1＝D3＋d3として示されており、これは、パケットa1に割り当てられる。パケットサイズa1に開始アドレスを加えたものは、同じスーパーパケット内の次のパケットa2のアドレスA2、すなわち、すなわち、A2＝A1＋a1である（以下同様）。各スーパーパケットの各パケットは独自のアドレスを取得するため、どの２つのパケットもオーバーラップすることはなく、隣接するパケット同士に割り当てられた共用メモリには隙間すなわちギャップは存在しない。
【００２５】
これまで説明したアルゴリズム的な観点からは、メモリ割り当ては、リング内を各タイムスロット毎に次のサブアドレス発生器に向けて移動する。しかしながら、これは要件ではない。なぜなら、メモリ割り当て期間、すなわち、サブアドレス発生器における２つの連続するメモリ割り当ての間の時間は、スーパーパケットの最大サイズに比例するからである。この特性は、本発明のアドレス発生の同時処理を可能にし、かつ、ポート数またはサブアドレス発生器の数に関してシステムをスケーラブル（拡張可能）にする。しかしながら、パケットの到着からアドレスを返すまでの待ち時間は、サブアドレス発生器の数とともに増加する。
【００２６】
さらに、前述した動作は、パケット合成とパケット分解について、単一のキューQ0の場合について説明された。しかしながら、前述したように、複数のキューシステムを同様に使用することも可能である。図６、５及び７は、複数のキュー（この例では、上述した図２、３及び４のそれぞれの単一キューシステムに関して同じアルゴリズム的アプローチを例示する２キューシステム）について、パケット合成、メモリ割り当て及びパケット分解をそれぞれ示す。実際、各々が、１つのデータキューに対応し、かつ、各々が、異なるタイムスロットで開始する、多くの同一のアドレス発生器を使用することができる。
【００２７】
図６、５及び７の例示的な２キューシステム（Q0、Q1）において、各キューへの入力パターンは、前述した動作と全く同じであろう。図５のメモリ割り当ては、タイムスロット０においてQ0で開始し、（異なる陰影を施されている）タイムスロット１においてQ1で開始する。さらに、両方のキューの入力パターンは同じであるが、各々のキューのスーパーパケットは、図６により詳しく示すように異なるであろう。このような複数キューシステム（図７）のパケット分解に関しては、スーパーパケットの個々のパケットにアドレスを割り当てる方法は、単一キューシステムの場合に図４に関して説明したのと同じであろう。もちろん、より多くのキューを使用すれば、メモリ割り当て期間はより長くなるであろう。これは、当然のことながら、最大サイズ、パケット、及びアドレス割り当て待ち時間が増大するであろうことを意味する。しかしながら、本発明の方法のアプローチでは、前述のように、パケット分解の速度は、パケット合成の速度と一致しなければならない。
【００２８】
ここで、上記係属出願、及び、図８に示されたタイプの、前述した好適な無無閉塞共用メモリ出力バッファ型データスイッチングシステムＭを対象とする本発明のアドレス発生システムAGSの全体アーキテクチャについて説明する。説明のため、２つの入力ポートすなわち入口ポートＡ及びＣは左側に示されており、受信されたデータパケットは、遠くに離れた右側の出力すなわち出口ポートＢに送られるものとする。共用メモリＭ内のQn及びQn+1キューは、出力ポートＢに専用のものとして例示的に示されている。
【００２９】
動作時、受信されたパケットAP1及びAP2は、ラインカードから順次入力ポートＡに到来する。これらのパケットは、出力ポートＢ専用の共用メモリ内のキューQnに向けて送られる。個別に受信されたパケットCP1及びCP2は、入力ポートＣに順次到来し、共用メモリのキューQnに送られる。入力ポートAは、前述した本発明のアドレス発生システムAGSに対して、上記同時係属出願に記載されたように、例示的なパケットAP1及びAP2のためにアドレスに関する要求を行う。
【００３０】
同様に、入口ポートＣは、パケットCP1及びCP2のためにAGSに対してアドレスに関する要求を行う。これらのパケットAP1、AP2、CP1及びCP2のサイズは異なるものとすることができる。
【００３１】
アドレス要求は、同時にまたは任意の順序で生じ得、本発明のアドレス発生器AGSは、要求された時間でポートＡからのこれらの要求を処理し、前述したやり方で入力ポートＡに対してアドレスA1及びA2を生成し、ポートＢからの要求もまた要求された時間で処理し、入力ポートＣに対してアドレスC1及びC2を生成する。
【００３２】
アドレスA1及びA2は入力ポートＡに戻され、アドレスC1及びC2は個別に入力ポートＣに戻されるが、これは、任意の順序で生じうる。ここで、アドレスを取得するために入力ポートＡで待機しているパケットAP1及びAP2は、これらのパケットの対応するアドレスタグA1及びA2を有する共用メモリＭに向かう。同様に、アドレスを取得するためにポートＣで待機しているパケットCP1及びCP2は、これらのパケットの対応するアドレスタグC1及びC2を有する共用メモリに向かう。共用メモリシステムは、これらのパケットを無閉塞方式で伝送し、これらのパケットは、出力ポートＢに専用のキューQn内に格納され、上記の係属出願に詳細に記載されているように、共用メモリへのパケットの書き込み動作を完了する。
【００３３】
アドレスA1、A2、C1、C2は、Qnにおいて連続するアドレスである必要はない。なぜなら、A1、A2、C1、C2間の領域を占有する可能性がある、他の入力ポートすなわち入口ポートからのパケットが存在しうるからである。出力ポートすなわち出口ポートＢは、その帯域幅割り当て（図８の例では２０％）に基づいてキューQnの内容を取り出すようプログラムされる。この速度（レート）にしたがって、出力ポートＢは、キューQnからのデータについてデータ要求を行い、共用メモリシステムＭは、キューQnから適切なデータを適切な時間で出力ポートＢに返す。他の出口ポートを同時に活性化する（起動する）こともでき、この場合、共用メモリは、これらのすべての読み出し要求を適切に処理する。やがて、パケットAP1、AP2、CP1、CP2は、出力ポートＢによって取り出され、出力ポートＢに対するQnの割り当てられた帯域幅にしたがって、入力ポートＡ及びＣから出力ポートＢへの意図された伝送が完了する。このシステムは、本発明の譲受人による現在の実験的な実施における64 OC-192について、これらの動作を行うが、前述したように、この方式は、既存の半導体技術に対してスケーラブルであり、64 OC-192ポートより多くのポートに拡張可能である。
【００３４】
当業者には、さらなる変更形態が想起されるであろうが、そのような変更形態は、特許請求の範囲において画定される本発明の思想及び範囲内のものとみなされる。
【図面の簡単な説明】
【００３５】
【図１】本発明のアドレス発生器リング構造部分を拡大した図である。
【図２】図１のリング構造をなすべてのアドレス発生器による単一のキューに関するパケット合成機能の実行を説明する図であり、スーパーパケットは、到着時間に基づいて順序付けされた、受信したデータパケットから構成される。
【図３】スーパーパケットの各々に対するメモリ空間のメモリ割り当てを示す図であり、メモリ割り当てが次のサブアドレス発生器に移動するときに開始アドレスとして使用するために、スーパーパケットのサイズを以前のスーパーパケットのアドレスに加えることが示されており、図の上部はアドレス要求を示し、下部の加算表現は、連続するタイムスロットにおいて次の段に渡されるアドレスオフセットを示している。
【図４】各サブアドレス発生器のパケット分解機能を示す図であり、スーパーパケットに対する開始アドレスがサブアドレス発生器によって割り当てられると、スーパーパケット内の個々のパケットに対して同時にアドレスが割り当てられることを示している。
【図５】アドレスオフセットが次の段に渡される、複数（２）キューシステムに対するメモリ割り当てを示す、図３に対応する図である。
【図６】２キューシステムのパケット合成を示す図２に対応する図である。
【図７】２キューシステムのパケット分解を示す図４に対応する図である。
【図８】上述の出力バッファ型共用メモリスイッチ構造のためのアドレス発生器として本発明を使用する好適な全体システムの動作を示す全体ブロック図である。
【図１】
2005539405.tif 000006
【図２】
2005539405.tif 000007
【図３】
2005539405.tif 000008
【図４】
2005539405.tif 000009
【図５】
2005539405.tif 000010
【図６】
2005539405.tif 000011
【図７】
2005539405.tif 000012
【図８】
2005539405.tif 000013
【国際調査報告】
2005539405.tif 000014
2005539405.tif 000015
2005539405.tif 000016