バッファ・サービス方法及び装置
【発明の詳細な説明】
【０００１】
【産業上の利用分野】この発明はディジタル通信ネットワークでバッファ・システムのリンクに関連した多数のバッファの要求を満たすためのサービス方式に関する。更に詳細に説明すれば、本発明はバッファの所要のサイズを可能な限り小さくし且つバッファをリンクの数及びそれらの相対速度と無関係にする。
【０００２】
【従来の技術】データ、音声又はビデオは、多くの場合、ディジタル化されたメッセージ、即ちパケットの形式で伝送される。パケットは、複数のソースの間で、通信チャネル即ちリンクによって相互接続される、多数の交換ノード、又は単純ノードを有するパケット交換ネットワークを介して交換される。リンクは情報ビットの伝送に用いる任意の伝送媒体である。あるシステムに関して、もし情報ビットが該システムに向かって流れれば、リンクは入力リンクと呼ばれる。さもなければ、当該リンクは出力リンクと呼ばれる。
【０００３】例えば、パケット交換ネットワークのパケット交換ノードのバッファ・システムは、各ｊ番目のリンクが速度Ｓj を有する２以上のリンクを有するシステムである。また、各リンクは別個の関連バッファを有する。このバッファは、入力リンクの場合は、関連した入力リンクから到来するビットの記憶に用い、出力リンクの場合は、バッファから関連出力リンクへのビットの転送に用いる。入力リンク及びその関連バッファの場合、バッファの要求を満たすことは、ビットがバッファから転送される、従ってバッファには入力リンクからのビットを受取る記憶空間があることを意味する。出力リンクに関連するバッファのサービスは、バッファにビットを記憶する、従ってビットはバッファから出力リンクに出ることを意味する。
【０００４】例えば、ノードは該ノードに到来するパケットを運ぶ２以上の入力リンクを有し、同時に該ノードから出るパケットを運ぶ１以上の出力リンクを有することができる。各リンクはその速度によって特徴づけられる。速度はビット／秒又はバイト／秒単位で測定され、パケットのビット又はバイトがリンクによって伝送される速度を表わす。リンクによっては、パケットのビット又はバイトは割込みなしに到着するかも知れない。このようなリンクは割込みできないリンクとして知られている。その他の場合は、リンクは割込みできる。
【０００５】あらゆるリンクは、入力リンクから到着するパケットのビットもしくはバイト、又は対応する出力リンクに出るパケットのビットもしくはバイトを記憶するために用いる記憶装置、即ちバッファに関連づけられる。
【０００６】一般に、ネットワークの各ノードは、ノードへ（から）パケットを転送する、サーバとして知られた装置を有する。パケットがノードの入力リンクから到着する場合は、サーバはバッファを空ける。パケットが出力リンクに出る場合は、サーバはバッファを満たす。従って、バッファ・システムが与えられると、バッファ１のバッファ・サービスはバッファを空ける必要があるかも知れないが、バッファ２のサービスはバッファを満たす必要があるかも知れない。
【０００７】このネットワークのバッファは、ビットの喪失を回避するか、少なくともビットの喪失を限定するように十分に大きくなければならない。ビット喪失は、入力リンクからパケットが到着するあるパターンではバッファ記憶装置が使い尽くされる場合はいつでも起きる可能性があり、それ以後に到着するビットはどれも失われる。この事象はオーバフローとして知られている。
【０００８】代わりに、出力リンクに関連するバッファの場合、サーバはバッファにビットを入れることができるが記憶空間が残されていない状況を回避するようにバッファは十分に大きくなければならない。
【０００９】ネットワークは絶えず変化するから、ノード中のリンクの数及び（又は）これらのリンクの速度は時々変るかも知れない。変化が起きると、既存のコンポーネントは置き換えなくてもよいことが重要である。従って、バッファ・システムの場合、バッファのサイズは入力リンク及びそれらの相対速度と無関係であることが望ましい。経済的な理由から、これらのバッファのサイズを最小にすることも望ましい。
【００１０】先着順サービス（ＦＣＦＳ）又は徹底的なラウンド・ロビン（ＲＲ）のような既存のサービス方式により、バッファのサイズは、リンクの数及びそれらの相対速度が増加するにつれて限度なしに大きくなる。従って、これらのサービス方式の使用により、ネットワーク構成が変るときネットワーク中のバッファを変更するだけでオーバフローを排除することができる。
【００１１】バッファの中にパケットの全ビットが入る前にサービス周期が開始するバッファ・サービス・システムもある。入力リンクに関連するバッファの場合、もし次のサービス周期にサーバがパケット全体を割込みなしに転送できることを保証するのに十分なビットがバッファにあれば、バッファは本質的に完全な(essentially complete)パケットを有すると言われる。もしサーバがパケットの一部だけを転送したときバッファにビットが存在しないケースでなければ、サーバはパケット全体を割込みなしに転送できる。出力リンクに関連するバッファの場合は、もし次のサービス周期にサーバがパケット全体を割込みなしに転送できることを保証するのに十分な自由記憶空間があれば、バッファは本質的に十分な(essentially sufficient)自由記憶空間を有する。もしサーバがパケットの一部だけを転送したときバッファに自由な記憶空間がないケースでなければ、サーバはパケット全体を割込みなしに転送できる。本質的に完全なパケットは、バッファに入力リンクから受信している速度よりも速い速度でサーバが該バッファからデータを送出する場合を考える。サーバが（サービス開始時点で全てのパケット・データがバッファに存在しなくても）バッファのデータを連続的に（止まらずに）サービスし、全体のパケットの完全なサービスが開始できる十分なビットがバッファにあると考えられるとき本質的に完全なパケットであるという。本質的に十分な自由記憶空間は、バッファから送出している速度よりも速い速度でサーバが該バッファへデータを格納する場合を考える。サーバが（サービス開始時点で、Ｍバイトの自由記憶空間がなくても）Ｍバイトのパケットをバッファに格納することができると考えられる場合、本質的に十分な記憶空間であるという。
【００１２】米国特許第４３７８５８８号は、同じサーバによってサービスされる入力及び出力トラフィックとバッファとの組合せについて開示している。
【００１３】
【発明が解決しようとする課題】本発明の目的はバッファ・システムのサービス方式を提供することである。より詳しくは、本発明の目的はオーバフローの可能性を無くし、必要なバッファの大きさを最小にし且つリンクの数及びそれらの相対速度とは無関係であるサービス方式を提供することである。
【００１４】
【課題を解決するための手段】この発明はバッファ・システムのリンクに関連するバッファの要求を満たす方法及び装置を提供する。この発明は、バッファのサブセットのθj の最小値であるθM を決定する必要がある。このサブセットにある各バッファは、もしそのビットがその関連入力リンクから入力しているならば、その中に少なくとも本質的に完全なパケットを有し、もしビットがバッファから出力しているならば、サブセットにある各バッファは本質的に十分な自由記憶空間を有する。入力リンクに関連しているバッファの場合は、もしビットが前記関連リンクからｊ番目のバッファに入力しているならば、θj はｊ番目のバッファがその境界に達するために必要な時間である。出力リンクに関連しているバッファの場合は、もしビットがｊ番目のバッファから前記関連出力リンクに出力しているならば、θj はｊ番目のバッファが空になるために必要とする時間である。そして、θj＝θMの値を持つサブセットにあるバッファのどれかがサービスされる。その場合、バッファにサービスすることは、入力リンクに関連するバッファからビットを取出すか又は出力リンクの関連バッファにビットを記憶することを含む。
【００１５】あるいは、パラメータθF の決定ができる。θF は異なるサブセットのバッファでのθj の最小値である。もしビットがその関連入力リンクからバッファに入力しているならば、異なるサブセットにある各バッファはその中に少なくともＭバイト（そのシステムの最大のパケット・サイズ）を有し、もしビットが当該バッファから関連出力リンクに出力しているならば、異なるサブセットにある各バッファは少なくともＭバイトの自由記憶空間を有する。
【００１６】そして、バッファはどれも、θFが完全なパケット或いは十分な自由記憶空間を有するバッファのθjの最小値であるから、本質的に完全なパケット或いは本質的に十分な自由記憶空間を考えた場合、θj≦θFの値を有し、該バッファが出力リンクに関連している場合は本質的に十分な自由記憶空間を有し、バッファが入力リンクに関連している場合は、少なくとも１つの本質的に完全なパケットを有する。
【００１７】ノードの入力リンクの数、ｊ番目のリンクの速度、及びサーバの速度をそれぞれＮ、Ｓj 及びＳとする。ここで、ｊは１≦ｊ≦Ｎであり、Ｓは次の関係式を満たすものとする。
【数１】
【００１８】割込みできないリンクで、長さＬのパケットは、そのビット又はバイトの少なくともＬ(１−Ｓj／Ｓ) がバッファに到着したとき、本質的に完全である。もしパケットの長さがその全てのビット又はバイトが到着するまで分からなければ、割込みできないリンク上のパケットは、そのバイトの少なくともＭ(１−Ｓj／Ｓ) がｊ番目のバッファに到着したとき本質的に完全である。ここで、Ｍは最大のパケットの長さである。バッファはもしパケットのビット又はバイトの全てが対応するバッファに到着したならばその中に完全なパケットを持つと言われる。
【００１９】もしｊ番目のバッファの各々にサイズ２Ｍのバッファを使用し、且つ前述のサービス方式のどちらかを使用すれば、オーバフローの可能性は排除される。
【００２０】
【実施例】図１において、パケット交換装置（バッファ・システム）は、１６の両方向性通信リンクに２組の端末：通信リンクの入力チャネルには端末 LIN(1)〜LIN(16)、通信リンクの出力チャネルには端末 LOUT(1)〜LOUT(16)によって接続される。良好な実施例では、通信リンクは割込みできず且つパケットの長さはそのビットの全部が到着するまで分からないものと仮定する。
【００２１】入力アダプタ１〜１６の機能は、通信リンクを介して入力パケット・トラフィックをビット直列ストリームの形式で受取り、パケットの開始と終了を識別し、これらのパケットを入力アダプタ内の専用記憶装置（バッファ）に記憶し、バス３３を介してバス・アービトレーション装置３４と通信して該記憶されたパケットを入力アダプタから転送する用意をし、最後に該記憶されたパケットを適切な時点でバス３３に転送することである。入力アダプタの動作は図２で更に詳細に説明する。
【００２２】バス３３は入力アダプタ１〜１６、出力アダプタ１７〜３２及びバス・アービトレーション装置３４の間の通信の媒体として役立つ。制御信号及びパケットはどちらもバス３３によって運ばれる。
【００２３】出力アダプタ１７〜３２の機能はバス・アービトレーション装置３４と通信してバス３３から出力アダプタにパケットを転送する用意をし、パケットをバス３３から出力アダプタに転送し、そして入力パケットをポート LOUT(1)〜LOUT(16)を介して通信リンクの出力チャネルに転送できるまで記憶することである。
【００２４】バス・アービトレーション装置３４の機能は入力アダプタ及び出力アダプタと通信してパケットをバス３３を介して転送する用意をすることである。バス・アービトレーション装置３３の動作は図３で更に詳細に説明する。
【００２５】図２は入力アダプタ１（図１）の内部構造を示す。これは入力アダプタ１〜１６に共通の内部構造である。バッファ・サービス方式は本明細書ではＭＩＮアルゴリズム（図４参照）による。
【００２６】ポートLIN(1)は通信リンクによって入力ビット・ストリームが入力アダプタ１に入る位置である。ポートLIN(1)はリンクによって直列受信部１０１の入力Ｉに接続される。直列受信部１０１の機能は、パケットの開始及び終了を識別し、ビット直列ストリームを８ビット・バイトの並列ストリームに変換することである。その結果、直列受信部１０１は下記の信号を生成する、即ち、入力パケットの現在のバイトを表わす８ビット信号（もしあれば）を出力Ｐに、活動化すると、出力Ｐのバイトがパケットの最初のバイトであることを知らせる信号を出力ＰＢに、出力Ｐのバイトがパケットの最後のバイトであることを知らせる信号を出力ＰＥに、そして有効なバイトが出力Ｐに存在することを知らせる信号を出力ＢＣＬに生成する。
【００２７】受信制御部１０２は、直列受信部１０１から、バイトが記憶されるパケットＦＩＦＯ １０３ (バッファ)へのパケットの転送を制御する。そのために、直列受信部１０１によって出力ＢＣＬ、ＰＢ及びＰＥに生成された信号は、リンクによって受信制御部１０２の対応する入力に運ばれ、同時に直列受信部１０１の出力ＰもリンクによってパケットＦＩＦＯ １０３ の入力Ｉに運ばれる。適切な時点で、受信制御部の出力ＡＢの信号は、パケットＦＩＦＯ １０３ の入力Ｗを活動化して入力のバイトを記憶させるのに用いる。
【００２８】デリミタＦＩＦＯ １０４ は、パケットＦＩＦＯ １０３ に記憶されたあらゆるバイトについて、直列受信部１０１の出力ＰＢ及びＰＥに生じる２つのビットを記憶する。もし入力ＢＩの信号が活動化されれば、ＢＩに対応するビットは１であり、パケットＦＩＦＯ １０３ に記憶されているバイトはパケットの最初のバイトであることを意味する。同様に、入力ＥＩに対応するビットはパケットの最後のバイトを表わす。デリミタＦＩＦＯ １０４ への書込み動作は受信制御部１０２の出力ＡＢの信号により制御される。この信号はリンクによりデリミタＦＩＦＯ １０４ の入力Ｗに運ばれる。
【００２９】パケットＦＩＦＯ（バッファのサービス）からポートA01P0〜A01P7へのパケットの転送は、転送制御部１０６でその出力ＤＢの信号によって制御される。この信号は、リンクによってパケットＦＩＦＯの入力Ｒに運ばれ、活動化されると、パケットＦＩＦＯ １０３ のＦＩＦＯメモリから読取り動作を生じさせ、その結果、パケットＦＩＦＯの出力Ｏから８ビット・リンクを介してラッチ１０７の入力Ｉにバイトが転送される。転送制御部１０６の出力ＤＢからの同じ信号によってラッチ１０７の入力Ｓは活動化されるので、転送されたバイトはラッチ１０７に記憶される。記憶されたバイトは８ビット・リンクによってラッチ１０７の出力ＯからポートA01P0〜A01P7に運ばれる。
【００３０】前述のようなパケットＦＩＦＯからバスへのパケット転送動作の開始は(ａ)転送制御部１０６はその入力ＡでポートA01A0〜A01A3からのアドレス、0000と1111の間の２進数を識別し、且つ(ｂ)転送制御部１０６はその入力ＧＯで、活動状態のときバス・アービトレーション装置３４で生成されパケット転送の進行を表わす信号（入力アダプタがバス・アービトレーション装置から受取ったバス制御信号）を検出することが条件である。そして転送制御部１０６は出力ＢＳＹを活動化（バスの制御を取得）し、その信号はポートA01BSYに送られる。
【００３１】パケット転送動作の終了はパケットＦＩＦＯ １０３ からパケットの最後のバイトが読取られ、同時にデリミタＦＩＦＯ １０４の出力ＥＯが活動化されたときトリガされる。従って、入力ＰＥの活動化を識別する転送制御部１０６は、バイトがラッチ１０７に転送された後、そのＢＳＹラインを非活動化して転送の終了をバス・アービトレーション装置３４に知らせる。
【００３２】ＴＲＢカウンタ１１０の内容は、限界に達する時間(ＴＲＢ)θ1に近い(入力アダプタｊのＴＲＢはθjで示される)。ＴＲＢカウンタの動作は３つのパラメータを含む。１つのパラメータは全ての入力アダプタについて同じ値であり、他の２つのパラメータはそれぞれの入力アダプタについて異なる値を持つかも知れない。
【００３３】第１のパラメータを示すＵはＴＲＢカウンタ１１０の単位カウントに対応する時間間隔を表わす。換言すれば、ＵをＴＲＢカウンタにある単位カウントに対応する時間とすると、θi＝ＮiＵになるようにＴＲＢカウンタの内容を整数、例えばＮiにとる。ここで、Ｎiは任意の時点における入力アダプタｉのＴＲＢカウンタの値を示す。ＴＲＢカウンタは、入力アダプタが異なっても、同じ（ビットの）長さ及び同じパラメータＵを有するものと仮定する。
【００３４】他の２つのパラメータはアダプタ毎に異なる値を持つことができる。Ｖi(i=1,...,16) は、始動時点（電源が投入される時点）において入力アダプタｉにあるＴＲＢカウンタの内容を表わすものとする。Ｆi(i=1,...,16) は、入力アダプタｉを特徴づける整数を表わすものであり、下記のように定められる。入力アダプタｉにあるパケットＦＩＦＯがＦi バイトずつ増加する毎に、ＴＲＢカウンタは１ずつ減少する。更に、入力アダプタｉにあるパケットＦＩＦＯがＦi バイトずつ減少する毎に、ＴＲＢカウンタは１ずつ増加する。Ｆi は入力アダプタｉのカウント係数と呼ぶ。
【００３５】最初にＵを決定する方法を説明する。ＳFは全てのＳiのうちの最小のものとする。ここでＳi はｉ番目の通信リンクの速度である(i=1,...,16)。ＴＲＢカウンタのどれかに記憶する必要がある最大のＴＲＢの値は、当該リンク速度に対応するアダプタで生じ、その値は２Ｍ／ＳF である。ここで、Ｍは最大のパケットのビットの長さ（バッファ・システムによって伝送される最も大きいメッセージのサイズ）である。ｂはＴＲＢカウンタのビットの長さとする。ＴＲＢは負ではないから、ＴＲＢカウンタに記憶できる最大の値は ２b−１である。従って、次の関係式が成立つ。
【数２】
【００３６】ｊ番目のアダプタにあるパケットＦＩＦＯの内容をＱj とする。全てのパケットＦＩＦＯが空である始動時に、Ｑj＝０とするＴＲＢの定義を用いて、ＶiＵ＝２Ｍ／Ｓi が得られる。従って、アダプタｉにあるＴＲＢカウンタの最初の値は次のようになる。
【数３】
【００３７】ＴＲＢカウンタ１１０は始動時に転送制御部１０６の出力ＩＮＩＴの信号によってＶi にセットされる。
【００３８】ある任意の時点でのｉ番目のアダプタにあるパケットＦＩＦＯの内容をＱi とし、ＴＲＢカウンタの値をＮi とすると、ＴＲＢの定義から次の式が成立つ。
【数４】
【００３９】カウント係数Ｆi の定義を用いて次の式が得られる。
【数５】
【００４０】そして、アダプタｉのカウント係数Ｆi＝ＵＳiである。
【００４１】速度Ｓi(i=1,...,16)はＳFの倍数、即ちある整数αiについてＳi＝αiＳFであると仮定する。Ｓi を参照するとき、情報（パケット）ビットが入力アダプタに到着する速度が考慮される。この速度は通信リンクで用いる媒体内のビット・ストリームの速度から僅かに異なるかも知れない。通常のキャリヤで用いるディジタル階層は、例えば、複数の等価音声回線で構築される。６４Ｋビット／秒のＤＳ−０は１回線を備え、１．５４４Ｍビット／秒のＤＳ−１は２４回線を備え、３．１５２Ｍビット／秒のＤＳ−１Ｃは４８回線を備える。よって、もしＵＳFが整数であることが確認されれば、ＵＳi(i=1,...,16) も整数である。
【００４２】ここで、Ｍ＝1000バイト、ｂ＝１０ビットとし、Ｓmax を最大のリンク速度、Ｓmax／ＳF＝２８とする。アダプタｉでＳi＝ＳFの場合に、ＵＳF≧２Ｍ／ (２b−１)が成立つと推論される。カウント係数は、２Ｍ／(２b− １) よりも大きいか又はそれに等しい最小の整数になるように選択される、この場合はＦi＝２ になる。例えば、アダプタｊでＳj＝Ｓmax の場合、Ｆj＝ＵＳmax＝２８ＵＳF＝５６になる。他の全てのアダプタのカウント係数は２と５６の間の整数である。
【００４３】パケットＦＩＦＯ １０３ がＦi だけ減少（増加）する毎に、ＴＲＢカウンタ１１０は１ずつ増加（減少）する。ＴＲＢカウンタ１１０の更新は増加カウンタ１１２、ＰＣＦ検出器１０８及びＮＣＦ検出器１０９によって行われる。ＰＣＦ検出器及びＮＣＦ検出器はそれぞれ正カウント係数検出器及び負カウント係数検出器を表わす。次に、これが入力アダプタ１によってどのように成し遂げられるかを説明する。
【００４４】増加カウンタ１１２は、パケットＦＩＦＯ １０３ にバイトが記憶される毎に１増加し且つバイトがパケットＦＩＦＯ １０３ から検索される毎に１減少する増／減カウンタである。増加信号は受信制御部１０２の出力ＡＢに生成され、減少信号は転送制御部１０６の出力ＤＢに生成される。増加カウンタ１１２によって提供する必要がある最大の数は（前述のように）５６であるから、増加カウンタ１１２は６ビットの長さになる。
【００４５】ＰＣＦ検出器１０８は増加カウンタ１１２にあるＦ1 のカウントを検出する論理回路から成る。前記カウントが検出されると、リセット信号がＰＣＦ検出器１０８の出力Ｓから増加カウンタ１１２の入力ＲＳＴに送られ、増加カウンタ１１２は０にリセットされる。更に、ＰＣＦ検出器１０８はＴＲＢカウンタ１１０の正（＋）入力を活動化させる。ＮＣＦ検出器１０９は増加カウンタ１１２にある−Ｆ1 のカウントを検出する論理回路から成る。同様に、前記カウントが検出されると、増加カウンタ１１２は０にリセットされ、ＴＲＢカウンタの負（−）入力が活動化される。
【００４６】パケット・カウンタ１０５はパケットＦＩＦＯ １０３ にあるパケットの数を保持する増／減カウンタである。その＋Ｐ入力は直列受信部１０１の出力ＰＥからの "受取ったパケットの終了" 信号によって活動化される。その−Ｐ入力はデリミタＦＩＦＯ １０４ の出力ＥＯからの "転送されたパケットの終了" 信号によって活動化される。そのＣＴ出力からの、現在のカウントが非０であることを知らせる信号は、リンクによって転送制御部１０６の入力ＣＴに送られる。
【００４７】バイト・カウンタ／検出器１１３はパケットＦＩＦＯ １０３ にあるバイトのカウントを保持する増／減カウンタである。そのＢ＋入力は受信制御部１０２の出力ＡＢからの信号によって活動化される。その−Ｂ入力は転送制御部１０６の出力ＤＢからの信号によって活動化される。そのＥＣ出力は、後で説明するようにパケットＦＩＦＯ １０３ は本質的に完全なパケットを有することをバイトのカウントが示す毎に活動化される。
【００４８】リンクｉ上のバッファが少なくともｘiビットを含む場合は、ｘiはそれが本質的に完全なパケットを含むように定め、通信リンクは割込みできず且つパケットの長さはそのビットが到着するまで分からないものと仮定すると、Ｍビットの要求を満たすのに必要な時間は、次の式に示すように、残余のパケットが到着するのに必要な時間に等しい。
【数６】
【００４９】ここで、Ｓi はリンク速度であり、Ｓはサーバの速度である。もしＭがバイトで示されれば、ｘiもバイトで示される。例えば、もしＭ＝1000バイト、且つＳi／Ｓ＝0.1ならば、ｘi＝900バイトである。
【００５０】場合によっては、パケットの長さは、あらゆるパケットの長さが、例えば、その最初の数バイトにコード化されると、その全てのビットが到着しないうちに分かる。従って、本明細書に記述された方式は次のように拡張することができる。値ｘi は、Ｍがパケットの実際の長さ、例えばＬに置換えらることを除けば、前述の式と類似の式を有する。ｘi はＬとともに変るから、入力パケット毎に計算し直してその値をバイト・カウンタ１１３に供給する必要がある。
【００５１】バイト・カウンタ／検出器１１３におけるロジックは、カウントがｘ1 よりも高ければ必ず出力ＥＣを活動化する（値ｘi はリンク速度によるのでアダプタによって異なるかも知れない）。クロック・サイクル（ＣＬ入力参照）毎に、転送制御部１０６は、そのＣＴ入力が活動化される（パケット・カウンタ１０５は少なくとも１つの完全なパケットがあることを示す）か又はそのＥＣ入力が活動化される（バイト・カウンタ１１３はほぼ完全なパケットがあることを示す）場合に、そのＰＫＴ出力を活動化させる。ＰＫＴ出力からの信号はリンクによってポートA01PKTに運ばれる。
【００５２】次に、図１のバス・アービトレーション装置３４の内部構造を示す図３について説明する。バッファ・サービス方式は本明細書ではＭＩＮアルゴリズム（図４参照）による。
【００５３】バス・アービトレーション装置３４のポートB01T0〜B01T9はバス３３により入力アダプタ１のポートA01T0〜A01T9にリンクされる（図２参照）。これらのポートで１０ビットの数は入力アダプタ１のＴＲＢに対応する。他の全てのアダプタにも類似のリンクが存在する。これらの１６の１０ビットの数はバス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号により定期的にラッチ２０１〜２１６に記憶される。これらのラッチの内容はリンクによりアービトレーション・ロジック２１８の入力Ｔ(1)〜Ｔ(16) に運ばれる。
【００５４】バス・アービトレーション装置３４のポートB01PKTはバス３３によって入力アダプタ１のポートA01PKTにリンクされる（図２参照）。この信号は、入力アダプタ１が少なくとも１つの完全なパケットを取得するか又は本質的に完全なパケットを取得し従って次のサービス周期でサービスされる候補であるときは必ず活動化される。他の全ての入力アダプタについて類似のリンクが存在する。これらの１６の１ビット信号はバス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号によって定期的にラッチ２０１Ａ〜２１６Ａに記憶される。これらのラッチの内容はリンクを介してアービトレーション・ロジック２１８の入力Ｃ(1)〜Ｃ(16) に運ばれる。
【００５５】アービトレーション・ロジック２１８はＭＩＮアルゴリズム（図４参照）に従って次にサービスされるバッファを選択する回路から成る。アービトレーション・ロジック２１８の出力ＡＮ１は、次のサービス周期でサービスされるアダプタの番号を表わす４ビットの数である。
【００５６】バス・アービトレーション制御部２１７はその入力Ｉの信号が活動状態であるかどうかを判定することによりパケット転送の終了を検出する（入力Ｉはバス・アービトレーション装置３４のポートＢＳＹ及び転送制御部１０６のＢＳＹ出力にリンクされる）。ＢＳＹが活動状態から非活動状態に変わると、これはバスの制御を持った入力アダプタが今それを放棄したことを示す。そしてアービトレーション・ロジック２１８の出力ＡＮ１はアービトレーション制御部２１７の制御の下にその出力ＷＯからの信号によって "活動状態のアダプタ番号" と表示されたラッチ２１９に記憶される。次に、バス・アービトレーション制御部２１７はその出力ＧＯを活動化させる。これは２１９で指定された入力アダプタがバスの制御を取得するための進行記号である。全てのバス動作のタイミングを供給するクロック信号も出力ＣＬで生成される。
【００５７】バス３３（図１）は入力アダプタ１〜１６、出力アダプタ１７〜３２及びバス・アービトレーション装置３４にあるポートをリンクするワイヤのセットから成る。即ち、バス・アービトレーション装置３４にあるポートＡ０〜Ａ３、Ｍ、ＣＬ、ＢＳＹは入力アダプタ１にあるポートA01A0〜A01A3、A01M、A01CL、A01BSY及び入力アダプタ２〜１６にある類似のポートにリンクされる。更に、バス・アービトレーション装置３４にあるポートB01T0〜B01T9は入力アダプタ１にあるポートA01T0〜A01T9にリンクされ、バス・アービトレーション装置３４にあるポートB02T0〜B02T9は入力アダプタ２にあるポートA02T0〜A02T9にリンクされる。以下、同様である。
【００５８】次に図４について説明する。図４は図３のアービトレーション・ロジック２１８で実現されるＭＩＮアルゴリズムの流れ図を示す。ここでは、θ1〜θ16 は図３の入力Ｔ(１)〜Ｔ(１６)の１０ビットの数の値を表わし、Ｃ(１)〜Ｃ(１６)は図３の入力Ｃ(１)〜Ｃ(１６)の２進値を表わす（対応する入力信号が活動化されている場合、この値は１である）。ＡＮ及びＡＮ１はそれぞれ図３の４ビット入力ＡＮ及び出力ＡＮ１の値を表わす。記号ｊ及びＭＩＮは計算に用いる変数である。ｊの値は１〜１６であるが、ＭＩＮはＴＲＢ(θjs)のセットから最小のＴＲＢθj の値を計算するために用いる。図３のバス・アービトレーション制御部２１７の制御の下にそれぞれ実行される計算はＡ（図４）で始まる。
【００５９】ステップ３０１で、変数ＭＩＮ及びｊは初期化される。変数ｊは値１を取得するのに対し、変数ＭＩＮは１０ビットの２進レジスタに記憶できる最大値、即ち２10−１が割当てられる。ステップ３０２で、条件Ｃ(ｊ)が検査される。もしＣ(ｊ)＝０であれば、これはｊ番目の入力アダプタがθM の決定に参加しないことを意味するのでステップ３０３及び３０４はスキップされ、計算の手順は直にステップ３０５に進む。しかしながら、もしＣ(ｊ)＝１であれば、手順はステップ３０３に進み、ＭＩＮはθ1と比較される。もしθ1の方が小さければ、ステップ３０４で、ＭＩＮは新しい値、即ちθ1 の値を取得する。さもなければ、ＭＩＮは変更されず、手順はステップ３０５に進む。ステップ３０５で、ｊは１だけ増加される。ステップ３０６で、ｊの値が検査される。もしｊが１６よりも大きければ、手順はステップ３０７に進む。さもなければ、手順はステップ３０２に戻る。この時点で、ＭＩＮの値はθM である。
【００６０】ステップ３０７で、ｊはＡＮ、現に活動状態の入力アダプタの番号の値が割当てられる。ステップ３０８で、ｊの値は１だけ増加される。ステップ３１０で、ｊの値が検査される。もしｊが１６よりも大きければ、ステップ３０９で、ｊは１が割当てられ、計算の手順はステップ３１１に進む。さもなければ、手順は直にステップ３１１に進む。ステップ３１１で、条件Ｃ(ｊ)が検査される。もしＣ(ｊ)が０であれば、手順はステップ３０８に戻る。さもなければ、手順はステップ３１２に進む。ステップ３１２で、値θj はＭＩＮの値と比較される。もし両者が等しければ、ｊは次にサービスされるアダプタの番号であるので、ステップ３１３で、ｊの値はＡＮ１が割当てられる。さもなければ、手順はステップ３０８に戻る。ステップ３１３で計算は終了する。
【００６１】次に、ＦＵＬＬアルゴリズムを用いる入力アダプタ１の内部構造を示す図５について説明する。ＦＵＬＬアルゴリズムを用いる入力アダプタ１の内部構造は図２の内部構造（ＭＩＮアルゴリズムを用いる）に極めて類似しているから、両者の間の相違点だけを説明する。
【００６２】バイト・カウンタ／検出器１１３は追加の出力Ｍを有する。出力Ｍはカウンタにあるバイトの数がパラメータＭの値に等しいか又はそれよりも大きいとき必ず活動化される。この信号はリンクによって転送制御部１０６の入力Ｍに運ばれる。もし入力Ｍが活動化されれば、クロック・サイクル（入力ＣＬ参照）毎に、転送制御部１０６はその出力ＭＣを活動化させる。ＭＣ信号はリンクによってポートA01MC に運ばれる。
【００６３】次に、ＦＵＬＬアルゴリズムを用いるバス・アービトレーション装置３４の内部構造を示す図６について説明する。これは図３の内部構造（ＭＩＮアルゴリズムを用いる）に極めて類似しているから、両者の間の相違点だけを説明する。
【００６４】ポートB01MCはバスによって入力アダプタ１のポートA01MCに接続される。他のアダプタについても同様である。従って、入力アダプタ１のバッファがＭ以上のバイトを含むとき、B01MC の信号は必ず活動化される。この信号に対応するビットは、バス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号によってラッチ２０１Ｂに記憶される。他のアダプタの対応するビットも同様にラッチ２０２Ｂ〜２１６Ｂに記憶される。これらのラッチの出力はアービトレーション・ロジック２１８の入力Ｍ(１)〜Ｍ(１６)から取出される。アービトレーション・ロジック２１８はＦＵＬＬアルゴリズム（後で図７に関連して説明する）によって次にサービスされるバッファを選択する回路から成る。
【００６５】次に、図６のアービトレーション・ロジック２１８によって実現されるＦＵＬＬアルゴリズムをブロック図形式で示す図７について説明する。ここでは、 θ1〜θ16は図３の入力Ｔ(１)〜Ｔ(１６)の値を表わし、Ｃ(１)〜Ｃ(１６)は図６の入力Ｃ(１)〜Ｃ(１６)の値を表わすのに対し、Ｍ(１)〜Ｍ(１６)は図６の入力Ｍ(１)〜Ｍ(１６)の値を表わす（対応する入力信号が活動化されている場合、この値は１である）。ＡＮ及びＡＮ１はそれぞれ図６の入力ＡＮ及び出力ＡＮ１の値を表わす。記号ｊ及びＭＩＮは計算で用いる変数である。ｊの値は１〜１６をとるのに対し、ＭＩＮは１セットのＴＲＢから最小のＴＲＢの値を計算するために用いられる。図６のバス・アービトレーション制御部２１７の制御の下に反復して実行される計算は図７のＡで始まる。図７の流れ図は、以下に説明する小さな相違点の外は、図４の流れ図に類似している。図４のステップ３０２ではＣ(ｊ)が０に等しいかどうかが検査されるが、図７のステップ４０２ではＭ(ｊ)が０に等しいかどうかが検査される。ステップ３０６に続いて、ＭＩＮの値はθF である。図４のステップ３１２ではθj がＭＩＮに等しいかどうかが検査されるのに対し、ステップ４１２ではθj がＭＩＮよりも小さいか又はそれに等しいかどうかが検査される。
【００６６】前述のパケット交換装置において、全ての入力アダプタは、図１の入力アダプタ１のように、関連した入力リンクを備え、該リンクでパケットはバッファ・システムに到着する。他の実施例のなかには、バッファ・システム内のバッファの幾つかは、入力するパケットのために関連入力リンクを備えるのに対し、他のバッファは出力するパケットのために出力リンクを備えることがある。サーバが提供するサービスは、前者の場合にはバッファを空にし、後者の場合にはバッファを満たす。後者の場合、このようなシステムの実施例は図２乃至図７に基づいて設計することができる。前記設計には下記に概略的に示すような小さな変更が必要になるだけである。
【００６７】後者の場合、図３、図４、図６及び図７は変更されない。図２および図５は、入力リンクを有するバッファについては変更されないが、出力リンクを有するバッファについては下記のような小変更を必要とする。図２で、入力リンクは出力リンクになり、従って転送制御部１０６はバス（ポートA01P0〜A01P7）から出力リンク(ポートLIN(1))へのバイトの転送を制御する。その結果、データ経路の矢印の方向は逆になる。例えば、バイトは、ポートA01P0〜A01P7からラッチ１０７の入力Ｏ（前記例では出力Ｏ）に、そしてラッチ１０７の出力Ｉ（前記例では入力Ｉ）からパケットFIFO １０３ の入力Ｏ（前記例では出力Ｏ）に送られる。同様に、転送制御部１０６の出力ＰＢ及びＰＥはそれぞれデリミタFIFO１０４ の入力ＢＯ及びＥＯに送られる。そしてデリミタFIFO １０４ の入力ＢＩ及びＥＩは出力となり、それぞれのリンクの方向は逆になる。受信制御部１０２の入力ＢＣＬは出力となり、直列受信部１０１を介して出力リンクのタイミングを制御する。パケットFIFO １０３ の入力Ｉは出力となり、直列受信部１０１の出力Ｐ、ＰＢ、ＰＥ及びＢＣＬは入力となる。ＦＵＬＬアルゴリズムの図５についても同一の変更が行われる。
【００６８】前述の良好な実施例で、ｂ(ＴＲＢカウンタ１１０（図２）にあるビットの数)＝１０と仮定した。更に、リンクｉ(ｉ＝1,...,16)の速度ＳiはＳFの倍数であると仮定した。これらの仮定の結果として、良好な実施例で実施される方式は前述のようにＬＴＲＢ方式に似ている。この良好な実施例は大部分の実際の場合に満足すべきものである。しかしながら、所望すれば、実施例の精度は次のようにかなり高めることができる。
【００６９】値ｂ（ＴＲＢカウンタ１１０のビット数）を増すことにより、このビット数の制限から生じる誤りを任意に小さくすることができる。ＴＲＢの計算は少しも行わない異なるアプローチも可能である。すなわち、アダプタｉがパケットFIFO中にＱi バイトを有すると仮定すると、アダプタｉとアダプタｊのＴＲＢを比較することは(２Ｍ−Ｑi)／Ｓiと(２Ｍ−Ｑj)／Ｓjとを比較することを意味する。これは乗算を含む演算(２Ｍ−Ｑi)Ｓjと(２Ｍ−Ｑj)Ｓiとを比較することに等しいので、良好な実施例で説明した演算よりも効率は低いが、正確に実行することができる。そして前記手順での比較は１５回まで実行され、従って最小のＴＲＢが提供される。
【００７０】
【発明の効果】本発明によれば、オーバフローの可能性を無くし、必要なバッファの大きさを最小にし且つリンクの数及びそれらの相対速度とは無関係であるサービス方式がバッファ・システムに提供される。
【図面の簡単な説明】
【図１】本発明で用いるパケット交換装置（バッファ・システム）の概要図である。
【図２】（ＭＩＮアルゴリズムと呼ばれる）θM を用いる本発明で使用する入力アダプタの概要図である。
【図３】ＭＩＮアルゴリズムを用いる本発明で使用するバス・アービトレーション装置の概要図である。
【図４】ＭＩＮアルゴリズムのアービトレーション・ロジックの流れ図である。
【図５】（ＦＵＬＬアルゴリズムと呼ばれる）θF を用いる本発明で使用する入力アダプタの概要図である。
【図６】ＦＵＬＬアルゴリズムのバス・アービトレーション装置の概要図である。
【図７】ＦＵＬＬアルゴリズムのアービトレーション・ロジックの流れ図である。
【符号の説明】
１ 入力アダプタ
１６ 入力アダプタ
１７ 出力アダプタ
３２ 出力アダプタ
３３ バス
３４ バス・アービトレーション装置
１０１ 直列受信部
１０２ 受信制御部
１０３ パケットＦＩＦＯ
１０４ デリミタＦＩＦＯ
１０５ パケット・カウンタ
１０６ 転送制御部
１０７ ラッチ
１０８ ＰＣＦ検出器
１０９ ＮＣＦ検出器
１１０ ＴＲＢカウンタ
１１２ 増加カウンタ
１１３ バイト・カウンタ／検出器
２０１ ラッチ
２０１Ａ ラッチ
２０１Ｂ ラッチ
２１６ ラッチ
２１６Ａ ラッチ
２１６Ｂ ラッチ
２１７ バス・アービトレーション制御部
２１８ アービトレーション・ロジック
２１９ ラッチ
【０００１】
【産業上の利用分野】この発明はディジタル通信ネットワークでバッファ・システムのリンクに関連した多数のバッファの要求を満たすためのサービス方式に関する。更に詳細に説明すれば、本発明はバッファの所要のサイズを可能な限り小さくし且つバッファをリンクの数及びそれらの相対速度と無関係にする。
【０００２】
【従来の技術】データ、音声又はビデオは、多くの場合、ディジタル化されたメッセージ、即ちパケットの形式で伝送される。パケットは、複数のソースの間で、通信チャネル即ちリンクによって相互接続される、多数の交換ノード、又は単純ノードを有するパケット交換ネットワークを介して交換される。リンクは情報ビットの伝送に用いる任意の伝送媒体である。あるシステムに関して、もし情報ビットが該システムに向かって流れれば、リンクは入力リンクと呼ばれる。さもなければ、当該リンクは出力リンクと呼ばれる。
【０００３】例えば、パケット交換ネットワークのパケット交換ノードのバッファ・システムは、各ｊ番目のリンクが速度Ｓj を有する２以上のリンクを有するシステムである。また、各リンクは別個の関連バッファを有する。このバッファは、入力リンクの場合は、関連した入力リンクから到来するビットの記憶に用い、出力リンクの場合は、バッファから関連出力リンクへのビットの転送に用いる。入力リンク及びその関連バッファの場合、バッファの要求を満たすことは、ビットがバッファから転送される、従ってバッファには入力リンクからのビットを受取る記憶空間があることを意味する。出力リンクに関連するバッファのサービスは、バッファにビットを記憶する、従ってビットはバッファから出力リンクに出ることを意味する。
【０００４】例えば、ノードは該ノードに到来するパケットを運ぶ２以上の入力リンクを有し、同時に該ノードから出るパケットを運ぶ１以上の出力リンクを有することができる。各リンクはその速度によって特徴づけられる。速度はビット／秒又はバイト／秒単位で測定され、パケットのビット又はバイトがリンクによって伝送される速度を表わす。リンクによっては、パケットのビット又はバイトは割込みなしに到着するかも知れない。このようなリンクは割込みできないリンクとして知られている。その他の場合は、リンクは割込みできる。
【０００５】あらゆるリンクは、入力リンクから到着するパケットのビットもしくはバイト、又は対応する出力リンクに出るパケットのビットもしくはバイトを記憶するために用いる記憶装置、即ちバッファに関連づけられる。
【０００６】一般に、ネットワークの各ノードは、ノードへ（から）パケットを転送する、サーバとして知られた装置を有する。パケットがノードの入力リンクから到着する場合は、サーバはバッファを空ける。パケットが出力リンクに出る場合は、サーバはバッファを満たす。従って、バッファ・システムが与えられると、バッファ１のバッファ・サービスはバッファを空ける必要があるかも知れないが、バッファ２のサービスはバッファを満たす必要があるかも知れない。
【０００７】このネットワークのバッファは、ビットの喪失を回避するか、少なくともビットの喪失を限定するように十分に大きくなければならない。ビット喪失は、入力リンクからパケットが到着するあるパターンではバッファ記憶装置が使い尽くされる場合はいつでも起きる可能性があり、それ以後に到着するビットはどれも失われる。この事象はオーバフローとして知られている。
【０００８】代わりに、出力リンクに関連するバッファの場合、サーバはバッファにビットを入れることができるが記憶空間が残されていない状況を回避するようにバッファは十分に大きくなければならない。
【０００９】ネットワークは絶えず変化するから、ノード中のリンクの数及び（又は）これらのリンクの速度は時々変るかも知れない。変化が起きると、既存のコンポーネントは置き換えなくてもよいことが重要である。従って、バッファ・システムの場合、バッファのサイズは入力リンク及びそれらの相対速度と無関係であることが望ましい。経済的な理由から、これらのバッファのサイズを最小にすることも望ましい。
【００１０】先着順サービス（ＦＣＦＳ）又は徹底的なラウンド・ロビン（ＲＲ）のような既存のサービス方式により、バッファのサイズは、リンクの数及びそれらの相対速度が増加するにつれて限度なしに大きくなる。従って、これらのサービス方式の使用により、ネットワーク構成が変るときネットワーク中のバッファを変更するだけでオーバフローを排除することができる。
【００１１】バッファの中にパケットの全ビットが入る前にサービス周期が開始するバッファ・サービス・システムもある。入力リンクに関連するバッファの場合、もし次のサービス周期にサーバがパケット全体を割込みなしに転送できることを保証するのに十分なビットがバッファにあれば、バッファは本質的に完全な(essentially complete)パケットを有すると言われる。もしサーバがパケットの一部だけを転送したときバッファにビットが存在しないケースでなければ、サーバはパケット全体を割込みなしに転送できる。出力リンクに関連するバッファの場合は、もし次のサービス周期にサーバがパケット全体を割込みなしに転送できることを保証するのに十分な自由記憶空間があれば、バッファは本質的に十分な(essentially sufficient)自由記憶空間を有する。もしサーバがパケットの一部だけを転送したときバッファに自由な記憶空間がないケースでなければ、サーバはパケット全体を割込みなしに転送できる。本質的に完全なパケットは、バッファに入力リンクから受信している速度よりも速い速度でサーバが該バッファからデータを送出する場合を考える。サーバが（サービス開始時点で全てのパケット・データがバッファに存在しなくても）バッファのデータを連続的に（止まらずに）サービスし、全体のパケットの完全なサービスが開始できる十分なビットがバッファにあると考えられるとき本質的に完全なパケットであるという。本質的に十分な自由記憶空間は、バッファから送出している速度よりも速い速度でサーバが該バッファへデータを格納する場合を考える。サーバが（サービス開始時点で、Ｍバイトの自由記憶空間がなくても）Ｍバイトのパケットをバッファに格納することができると考えられる場合、本質的に十分な記憶空間であるという。
【００１２】米国特許第４３７８５８８号は、同じサーバによってサービスされる入力及び出力トラフィックとバッファとの組合せについて開示している。
【００１３】
【発明が解決しようとする課題】本発明の目的はバッファ・システムのサービス方式を提供することである。より詳しくは、本発明の目的はオーバフローの可能性を無くし、必要なバッファの大きさを最小にし且つリンクの数及びそれらの相対速度とは無関係であるサービス方式を提供することである。
【００１４】
【課題を解決するための手段】この発明はバッファ・システムのリンクに関連するバッファの要求を満たす方法及び装置を提供する。この発明は、バッファのサブセットのθj の最小値であるθM を決定する必要がある。このサブセットにある各バッファは、もしそのビットがその関連入力リンクから入力しているならば、その中に少なくとも本質的に完全なパケットを有し、もしビットがバッファから出力しているならば、サブセットにある各バッファは本質的に十分な自由記憶空間を有する。入力リンクに関連しているバッファの場合は、もしビットが前記関連リンクからｊ番目のバッファに入力しているならば、θj はｊ番目のバッファがその境界に達するために必要な時間である。出力リンクに関連しているバッファの場合は、もしビットがｊ番目のバッファから前記関連出力リンクに出力しているならば、θj はｊ番目のバッファが空になるために必要とする時間である。そして、θj＝θMの値を持つサブセットにあるバッファのどれかがサービスされる。その場合、バッファにサービスすることは、入力リンクに関連するバッファからビットを取出すか又は出力リンクの関連バッファにビットを記憶することを含む。
【００１５】あるいは、パラメータθF の決定ができる。θF は異なるサブセットのバッファでのθj の最小値である。もしビットがその関連入力リンクからバッファに入力しているならば、異なるサブセットにある各バッファはその中に少なくともＭバイト（そのシステムの最大のパケット・サイズ）を有し、もしビットが当該バッファから関連出力リンクに出力しているならば、異なるサブセットにある各バッファは少なくともＭバイトの自由記憶空間を有する。
【００１６】そして、バッファはどれも、θFが完全なパケット或いは十分な自由記憶空間を有するバッファのθjの最小値であるから、本質的に完全なパケット或いは本質的に十分な自由記憶空間を考えた場合、θj≦θFの値を有し、該バッファが出力リンクに関連している場合は本質的に十分な自由記憶空間を有し、バッファが入力リンクに関連している場合は、少なくとも１つの本質的に完全なパケットを有する。
【００１７】ノードの入力リンクの数、ｊ番目のリンクの速度、及びサーバの速度をそれぞれＮ、Ｓj 及びＳとする。ここで、ｊは１≦ｊ≦Ｎであり、Ｓは次の関係式を満たすものとする。
【数１】
【００１８】割込みできないリンクで、長さＬのパケットは、そのビット又はバイトの少なくともＬ(１−Ｓj／Ｓ) がバッファに到着したとき、本質的に完全である。もしパケットの長さがその全てのビット又はバイトが到着するまで分からなければ、割込みできないリンク上のパケットは、そのバイトの少なくともＭ(１−Ｓj／Ｓ) がｊ番目のバッファに到着したとき本質的に完全である。ここで、Ｍは最大のパケットの長さである。バッファはもしパケットのビット又はバイトの全てが対応するバッファに到着したならばその中に完全なパケットを持つと言われる。
【００１９】もしｊ番目のバッファの各々にサイズ２Ｍのバッファを使用し、且つ前述のサービス方式のどちらかを使用すれば、オーバフローの可能性は排除される。
【００２０】
【実施例】図１において、パケット交換装置（バッファ・システム）は、１６の両方向性通信リンクに２組の端末：通信リンクの入力チャネルには端末 LIN(1)〜LIN(16)、通信リンクの出力チャネルには端末 LOUT(1)〜LOUT(16)によって接続される。良好な実施例では、通信リンクは割込みできず且つパケットの長さはそのビットの全部が到着するまで分からないものと仮定する。
【００２１】入力アダプタ１〜１６の機能は、通信リンクを介して入力パケット・トラフィックをビット直列ストリームの形式で受取り、パケットの開始と終了を識別し、これらのパケットを入力アダプタ内の専用記憶装置（バッファ）に記憶し、バス３３を介してバス・アービトレーション装置３４と通信して該記憶されたパケットを入力アダプタから転送する用意をし、最後に該記憶されたパケットを適切な時点でバス３３に転送することである。入力アダプタの動作は図２で更に詳細に説明する。
【００２２】バス３３は入力アダプタ１〜１６、出力アダプタ１７〜３２及びバス・アービトレーション装置３４の間の通信の媒体として役立つ。制御信号及びパケットはどちらもバス３３によって運ばれる。
【００２３】出力アダプタ１７〜３２の機能はバス・アービトレーション装置３４と通信してバス３３から出力アダプタにパケットを転送する用意をし、パケットをバス３３から出力アダプタに転送し、そして入力パケットをポート LOUT(1)〜LOUT(16)を介して通信リンクの出力チャネルに転送できるまで記憶することである。
【００２４】バス・アービトレーション装置３４の機能は入力アダプタ及び出力アダプタと通信してパケットをバス３３を介して転送する用意をすることである。バス・アービトレーション装置３３の動作は図３で更に詳細に説明する。
【００２５】図２は入力アダプタ１（図１）の内部構造を示す。これは入力アダプタ１〜１６に共通の内部構造である。バッファ・サービス方式は本明細書ではＭＩＮアルゴリズム（図４参照）による。
【００２６】ポートLIN(1)は通信リンクによって入力ビット・ストリームが入力アダプタ１に入る位置である。ポートLIN(1)はリンクによって直列受信部１０１の入力Ｉに接続される。直列受信部１０１の機能は、パケットの開始及び終了を識別し、ビット直列ストリームを８ビット・バイトの並列ストリームに変換することである。その結果、直列受信部１０１は下記の信号を生成する、即ち、入力パケットの現在のバイトを表わす８ビット信号（もしあれば）を出力Ｐに、活動化すると、出力Ｐのバイトがパケットの最初のバイトであることを知らせる信号を出力ＰＢに、出力Ｐのバイトがパケットの最後のバイトであることを知らせる信号を出力ＰＥに、そして有効なバイトが出力Ｐに存在することを知らせる信号を出力ＢＣＬに生成する。
【００２７】受信制御部１０２は、直列受信部１０１から、バイトが記憶されるパケットＦＩＦＯ １０３ (バッファ)へのパケットの転送を制御する。そのために、直列受信部１０１によって出力ＢＣＬ、ＰＢ及びＰＥに生成された信号は、リンクによって受信制御部１０２の対応する入力に運ばれ、同時に直列受信部１０１の出力ＰもリンクによってパケットＦＩＦＯ １０３ の入力Ｉに運ばれる。適切な時点で、受信制御部の出力ＡＢの信号は、パケットＦＩＦＯ １０３ の入力Ｗを活動化して入力のバイトを記憶させるのに用いる。
【００２８】デリミタＦＩＦＯ １０４ は、パケットＦＩＦＯ １０３ に記憶されたあらゆるバイトについて、直列受信部１０１の出力ＰＢ及びＰＥに生じる２つのビットを記憶する。もし入力ＢＩの信号が活動化されれば、ＢＩに対応するビットは１であり、パケットＦＩＦＯ １０３ に記憶されているバイトはパケットの最初のバイトであることを意味する。同様に、入力ＥＩに対応するビットはパケットの最後のバイトを表わす。デリミタＦＩＦＯ １０４ への書込み動作は受信制御部１０２の出力ＡＢの信号により制御される。この信号はリンクによりデリミタＦＩＦＯ １０４ の入力Ｗに運ばれる。
【００２９】パケットＦＩＦＯ（バッファのサービス）からポートA01P0〜A01P7へのパケットの転送は、転送制御部１０６でその出力ＤＢの信号によって制御される。この信号は、リンクによってパケットＦＩＦＯの入力Ｒに運ばれ、活動化されると、パケットＦＩＦＯ １０３ のＦＩＦＯメモリから読取り動作を生じさせ、その結果、パケットＦＩＦＯの出力Ｏから８ビット・リンクを介してラッチ１０７の入力Ｉにバイトが転送される。転送制御部１０６の出力ＤＢからの同じ信号によってラッチ１０７の入力Ｓは活動化されるので、転送されたバイトはラッチ１０７に記憶される。記憶されたバイトは８ビット・リンクによってラッチ１０７の出力ＯからポートA01P0〜A01P7に運ばれる。
【００３０】前述のようなパケットＦＩＦＯからバスへのパケット転送動作の開始は(ａ)転送制御部１０６はその入力ＡでポートA01A0〜A01A3からのアドレス、0000と1111の間の２進数を識別し、且つ(ｂ)転送制御部１０６はその入力ＧＯで、活動状態のときバス・アービトレーション装置３４で生成されパケット転送の進行を表わす信号（入力アダプタがバス・アービトレーション装置から受取ったバス制御信号）を検出することが条件である。そして転送制御部１０６は出力ＢＳＹを活動化（バスの制御を取得）し、その信号はポートA01BSYに送られる。
【００３１】パケット転送動作の終了はパケットＦＩＦＯ １０３ からパケットの最後のバイトが読取られ、同時にデリミタＦＩＦＯ １０４の出力ＥＯが活動化されたときトリガされる。従って、入力ＰＥの活動化を識別する転送制御部１０６は、バイトがラッチ１０７に転送された後、そのＢＳＹラインを非活動化して転送の終了をバス・アービトレーション装置３４に知らせる。
【００３２】ＴＲＢカウンタ１１０の内容は、限界に達する時間(ＴＲＢ)θ1に近い(入力アダプタｊのＴＲＢはθjで示される)。ＴＲＢカウンタの動作は３つのパラメータを含む。１つのパラメータは全ての入力アダプタについて同じ値であり、他の２つのパラメータはそれぞれの入力アダプタについて異なる値を持つかも知れない。
【００３３】第１のパラメータを示すＵはＴＲＢカウンタ１１０の単位カウントに対応する時間間隔を表わす。換言すれば、ＵをＴＲＢカウンタにある単位カウントに対応する時間とすると、θi＝ＮiＵになるようにＴＲＢカウンタの内容を整数、例えばＮiにとる。ここで、Ｎiは任意の時点における入力アダプタｉのＴＲＢカウンタの値を示す。ＴＲＢカウンタは、入力アダプタが異なっても、同じ（ビットの）長さ及び同じパラメータＵを有するものと仮定する。
【００３４】他の２つのパラメータはアダプタ毎に異なる値を持つことができる。Ｖi(i=1,...,16) は、始動時点（電源が投入される時点）において入力アダプタｉにあるＴＲＢカウンタの内容を表わすものとする。Ｆi(i=1,...,16) は、入力アダプタｉを特徴づける整数を表わすものであり、下記のように定められる。入力アダプタｉにあるパケットＦＩＦＯがＦi バイトずつ増加する毎に、ＴＲＢカウンタは１ずつ減少する。更に、入力アダプタｉにあるパケットＦＩＦＯがＦi バイトずつ減少する毎に、ＴＲＢカウンタは１ずつ増加する。Ｆi は入力アダプタｉのカウント係数と呼ぶ。
【００３５】最初にＵを決定する方法を説明する。ＳFは全てのＳiのうちの最小のものとする。ここでＳi はｉ番目の通信リンクの速度である(i=1,...,16)。ＴＲＢカウンタのどれかに記憶する必要がある最大のＴＲＢの値は、当該リンク速度に対応するアダプタで生じ、その値は２Ｍ／ＳF である。ここで、Ｍは最大のパケットのビットの長さ（バッファ・システムによって伝送される最も大きいメッセージのサイズ）である。ｂはＴＲＢカウンタのビットの長さとする。ＴＲＢは負ではないから、ＴＲＢカウンタに記憶できる最大の値は ２b−１である。従って、次の関係式が成立つ。
【数２】
【００３６】ｊ番目のアダプタにあるパケットＦＩＦＯの内容をＱj とする。全てのパケットＦＩＦＯが空である始動時に、Ｑj＝０とするＴＲＢの定義を用いて、ＶiＵ＝２Ｍ／Ｓi が得られる。従って、アダプタｉにあるＴＲＢカウンタの最初の値は次のようになる。
【数３】
【００３７】ＴＲＢカウンタ１１０は始動時に転送制御部１０６の出力ＩＮＩＴの信号によってＶi にセットされる。
【００３８】ある任意の時点でのｉ番目のアダプタにあるパケットＦＩＦＯの内容をＱi とし、ＴＲＢカウンタの値をＮi とすると、ＴＲＢの定義から次の式が成立つ。
【数４】
【００３９】カウント係数Ｆi の定義を用いて次の式が得られる。
【数５】
【００４０】そして、アダプタｉのカウント係数Ｆi＝ＵＳiである。
【００４１】速度Ｓi(i=1,...,16)はＳFの倍数、即ちある整数αiについてＳi＝αiＳFであると仮定する。Ｓi を参照するとき、情報（パケット）ビットが入力アダプタに到着する速度が考慮される。この速度は通信リンクで用いる媒体内のビット・ストリームの速度から僅かに異なるかも知れない。通常のキャリヤで用いるディジタル階層は、例えば、複数の等価音声回線で構築される。６４Ｋビット／秒のＤＳ−０は１回線を備え、１．５４４Ｍビット／秒のＤＳ−１は２４回線を備え、３．１５２Ｍビット／秒のＤＳ−１Ｃは４８回線を備える。よって、もしＵＳFが整数であることが確認されれば、ＵＳi(i=1,...,16) も整数である。
【００４２】ここで、Ｍ＝1000バイト、ｂ＝１０ビットとし、Ｓmax を最大のリンク速度、Ｓmax／ＳF＝２８とする。アダプタｉでＳi＝ＳFの場合に、ＵＳF≧２Ｍ／ (２b−１)が成立つと推論される。カウント係数は、２Ｍ／(２b− １) よりも大きいか又はそれに等しい最小の整数になるように選択される、この場合はＦi＝２ になる。例えば、アダプタｊでＳj＝Ｓmax の場合、Ｆj＝ＵＳmax＝２８ＵＳF＝５６になる。他の全てのアダプタのカウント係数は２と５６の間の整数である。
【００４３】パケットＦＩＦＯ １０３ がＦi だけ減少（増加）する毎に、ＴＲＢカウンタ１１０は１ずつ増加（減少）する。ＴＲＢカウンタ１１０の更新は増加カウンタ１１２、ＰＣＦ検出器１０８及びＮＣＦ検出器１０９によって行われる。ＰＣＦ検出器及びＮＣＦ検出器はそれぞれ正カウント係数検出器及び負カウント係数検出器を表わす。次に、これが入力アダプタ１によってどのように成し遂げられるかを説明する。
【００４４】増加カウンタ１１２は、パケットＦＩＦＯ １０３ にバイトが記憶される毎に１増加し且つバイトがパケットＦＩＦＯ １０３ から検索される毎に１減少する増／減カウンタである。増加信号は受信制御部１０２の出力ＡＢに生成され、減少信号は転送制御部１０６の出力ＤＢに生成される。増加カウンタ１１２によって提供する必要がある最大の数は（前述のように）５６であるから、増加カウンタ１１２は６ビットの長さになる。
【００４５】ＰＣＦ検出器１０８は増加カウンタ１１２にあるＦ1 のカウントを検出する論理回路から成る。前記カウントが検出されると、リセット信号がＰＣＦ検出器１０８の出力Ｓから増加カウンタ１１２の入力ＲＳＴに送られ、増加カウンタ１１２は０にリセットされる。更に、ＰＣＦ検出器１０８はＴＲＢカウンタ１１０の正（＋）入力を活動化させる。ＮＣＦ検出器１０９は増加カウンタ１１２にある−Ｆ1 のカウントを検出する論理回路から成る。同様に、前記カウントが検出されると、増加カウンタ１１２は０にリセットされ、ＴＲＢカウンタの負（−）入力が活動化される。
【００４６】パケット・カウンタ１０５はパケットＦＩＦＯ １０３ にあるパケットの数を保持する増／減カウンタである。その＋Ｐ入力は直列受信部１０１の出力ＰＥからの "受取ったパケットの終了" 信号によって活動化される。その−Ｐ入力はデリミタＦＩＦＯ １０４ の出力ＥＯからの "転送されたパケットの終了" 信号によって活動化される。そのＣＴ出力からの、現在のカウントが非０であることを知らせる信号は、リンクによって転送制御部１０６の入力ＣＴに送られる。
【００４７】バイト・カウンタ／検出器１１３はパケットＦＩＦＯ １０３ にあるバイトのカウントを保持する増／減カウンタである。そのＢ＋入力は受信制御部１０２の出力ＡＢからの信号によって活動化される。その−Ｂ入力は転送制御部１０６の出力ＤＢからの信号によって活動化される。そのＥＣ出力は、後で説明するようにパケットＦＩＦＯ １０３ は本質的に完全なパケットを有することをバイトのカウントが示す毎に活動化される。
【００４８】リンクｉ上のバッファが少なくともｘiビットを含む場合は、ｘiはそれが本質的に完全なパケットを含むように定め、通信リンクは割込みできず且つパケットの長さはそのビットが到着するまで分からないものと仮定すると、Ｍビットの要求を満たすのに必要な時間は、次の式に示すように、残余のパケットが到着するのに必要な時間に等しい。
【数６】
【００４９】ここで、Ｓi はリンク速度であり、Ｓはサーバの速度である。もしＭがバイトで示されれば、ｘiもバイトで示される。例えば、もしＭ＝1000バイト、且つＳi／Ｓ＝0.1ならば、ｘi＝900バイトである。
【００５０】場合によっては、パケットの長さは、あらゆるパケットの長さが、例えば、その最初の数バイトにコード化されると、その全てのビットが到着しないうちに分かる。従って、本明細書に記述された方式は次のように拡張することができる。値ｘi は、Ｍがパケットの実際の長さ、例えばＬに置換えらることを除けば、前述の式と類似の式を有する。ｘi はＬとともに変るから、入力パケット毎に計算し直してその値をバイト・カウンタ１１３に供給する必要がある。
【００５１】バイト・カウンタ／検出器１１３におけるロジックは、カウントがｘ1 よりも高ければ必ず出力ＥＣを活動化する（値ｘi はリンク速度によるのでアダプタによって異なるかも知れない）。クロック・サイクル（ＣＬ入力参照）毎に、転送制御部１０６は、そのＣＴ入力が活動化される（パケット・カウンタ１０５は少なくとも１つの完全なパケットがあることを示す）か又はそのＥＣ入力が活動化される（バイト・カウンタ１１３はほぼ完全なパケットがあることを示す）場合に、そのＰＫＴ出力を活動化させる。ＰＫＴ出力からの信号はリンクによってポートA01PKTに運ばれる。
【００５２】次に、図１のバス・アービトレーション装置３４の内部構造を示す図３について説明する。バッファ・サービス方式は本明細書ではＭＩＮアルゴリズム（図４参照）による。
【００５３】バス・アービトレーション装置３４のポートB01T0〜B01T9はバス３３により入力アダプタ１のポートA01T0〜A01T9にリンクされる（図２参照）。これらのポートで１０ビットの数は入力アダプタ１のＴＲＢに対応する。他の全てのアダプタにも類似のリンクが存在する。これらの１６の１０ビットの数はバス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号により定期的にラッチ２０１〜２１６に記憶される。これらのラッチの内容はリンクによりアービトレーション・ロジック２１８の入力Ｔ(1)〜Ｔ(16) に運ばれる。
【００５４】バス・アービトレーション装置３４のポートB01PKTはバス３３によって入力アダプタ１のポートA01PKTにリンクされる（図２参照）。この信号は、入力アダプタ１が少なくとも１つの完全なパケットを取得するか又は本質的に完全なパケットを取得し従って次のサービス周期でサービスされる候補であるときは必ず活動化される。他の全ての入力アダプタについて類似のリンクが存在する。これらの１６の１ビット信号はバス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号によって定期的にラッチ２０１Ａ〜２１６Ａに記憶される。これらのラッチの内容はリンクを介してアービトレーション・ロジック２１８の入力Ｃ(1)〜Ｃ(16) に運ばれる。
【００５５】アービトレーション・ロジック２１８はＭＩＮアルゴリズム（図４参照）に従って次にサービスされるバッファを選択する回路から成る。アービトレーション・ロジック２１８の出力ＡＮ１は、次のサービス周期でサービスされるアダプタの番号を表わす４ビットの数である。
【００５６】バス・アービトレーション制御部２１７はその入力Ｉの信号が活動状態であるかどうかを判定することによりパケット転送の終了を検出する（入力Ｉはバス・アービトレーション装置３４のポートＢＳＹ及び転送制御部１０６のＢＳＹ出力にリンクされる）。ＢＳＹが活動状態から非活動状態に変わると、これはバスの制御を持った入力アダプタが今それを放棄したことを示す。そしてアービトレーション・ロジック２１８の出力ＡＮ１はアービトレーション制御部２１７の制御の下にその出力ＷＯからの信号によって "活動状態のアダプタ番号" と表示されたラッチ２１９に記憶される。次に、バス・アービトレーション制御部２１７はその出力ＧＯを活動化させる。これは２１９で指定された入力アダプタがバスの制御を取得するための進行記号である。全てのバス動作のタイミングを供給するクロック信号も出力ＣＬで生成される。
【００５７】バス３３（図１）は入力アダプタ１〜１６、出力アダプタ１７〜３２及びバス・アービトレーション装置３４にあるポートをリンクするワイヤのセットから成る。即ち、バス・アービトレーション装置３４にあるポートＡ０〜Ａ３、Ｍ、ＣＬ、ＢＳＹは入力アダプタ１にあるポートA01A0〜A01A3、A01M、A01CL、A01BSY及び入力アダプタ２〜１６にある類似のポートにリンクされる。更に、バス・アービトレーション装置３４にあるポートB01T0〜B01T9は入力アダプタ１にあるポートA01T0〜A01T9にリンクされ、バス・アービトレーション装置３４にあるポートB02T0〜B02T9は入力アダプタ２にあるポートA02T0〜A02T9にリンクされる。以下、同様である。
【００５８】次に図４について説明する。図４は図３のアービトレーション・ロジック２１８で実現されるＭＩＮアルゴリズムの流れ図を示す。ここでは、θ1〜θ16 は図３の入力Ｔ(１)〜Ｔ(１６)の１０ビットの数の値を表わし、Ｃ(１)〜Ｃ(１６)は図３の入力Ｃ(１)〜Ｃ(１６)の２進値を表わす（対応する入力信号が活動化されている場合、この値は１である）。ＡＮ及びＡＮ１はそれぞれ図３の４ビット入力ＡＮ及び出力ＡＮ１の値を表わす。記号ｊ及びＭＩＮは計算に用いる変数である。ｊの値は１〜１６であるが、ＭＩＮはＴＲＢ(θjs)のセットから最小のＴＲＢθj の値を計算するために用いる。図３のバス・アービトレーション制御部２１７の制御の下にそれぞれ実行される計算はＡ（図４）で始まる。
【００５９】ステップ３０１で、変数ＭＩＮ及びｊは初期化される。変数ｊは値１を取得するのに対し、変数ＭＩＮは１０ビットの２進レジスタに記憶できる最大値、即ち２10−１が割当てられる。ステップ３０２で、条件Ｃ(ｊ)が検査される。もしＣ(ｊ)＝０であれば、これはｊ番目の入力アダプタがθM の決定に参加しないことを意味するのでステップ３０３及び３０４はスキップされ、計算の手順は直にステップ３０５に進む。しかしながら、もしＣ(ｊ)＝１であれば、手順はステップ３０３に進み、ＭＩＮはθ1と比較される。もしθ1の方が小さければ、ステップ３０４で、ＭＩＮは新しい値、即ちθ1 の値を取得する。さもなければ、ＭＩＮは変更されず、手順はステップ３０５に進む。ステップ３０５で、ｊは１だけ増加される。ステップ３０６で、ｊの値が検査される。もしｊが１６よりも大きければ、手順はステップ３０７に進む。さもなければ、手順はステップ３０２に戻る。この時点で、ＭＩＮの値はθM である。
【００６０】ステップ３０７で、ｊはＡＮ、現に活動状態の入力アダプタの番号の値が割当てられる。ステップ３０８で、ｊの値は１だけ増加される。ステップ３１０で、ｊの値が検査される。もしｊが１６よりも大きければ、ステップ３０９で、ｊは１が割当てられ、計算の手順はステップ３１１に進む。さもなければ、手順は直にステップ３１１に進む。ステップ３１１で、条件Ｃ(ｊ)が検査される。もしＣ(ｊ)が０であれば、手順はステップ３０８に戻る。さもなければ、手順はステップ３１２に進む。ステップ３１２で、値θj はＭＩＮの値と比較される。もし両者が等しければ、ｊは次にサービスされるアダプタの番号であるので、ステップ３１３で、ｊの値はＡＮ１が割当てられる。さもなければ、手順はステップ３０８に戻る。ステップ３１３で計算は終了する。
【００６１】次に、ＦＵＬＬアルゴリズムを用いる入力アダプタ１の内部構造を示す図５について説明する。ＦＵＬＬアルゴリズムを用いる入力アダプタ１の内部構造は図２の内部構造（ＭＩＮアルゴリズムを用いる）に極めて類似しているから、両者の間の相違点だけを説明する。
【００６２】バイト・カウンタ／検出器１１３は追加の出力Ｍを有する。出力Ｍはカウンタにあるバイトの数がパラメータＭの値に等しいか又はそれよりも大きいとき必ず活動化される。この信号はリンクによって転送制御部１０６の入力Ｍに運ばれる。もし入力Ｍが活動化されれば、クロック・サイクル（入力ＣＬ参照）毎に、転送制御部１０６はその出力ＭＣを活動化させる。ＭＣ信号はリンクによってポートA01MC に運ばれる。
【００６３】次に、ＦＵＬＬアルゴリズムを用いるバス・アービトレーション装置３４の内部構造を示す図６について説明する。これは図３の内部構造（ＭＩＮアルゴリズムを用いる）に極めて類似しているから、両者の間の相違点だけを説明する。
【００６４】ポートB01MCはバスによって入力アダプタ１のポートA01MCに接続される。他のアダプタについても同様である。従って、入力アダプタ１のバッファがＭ以上のバイトを含むとき、B01MC の信号は必ず活動化される。この信号に対応するビットは、バス・アービトレーション制御部２１７の制御の下にその出力ＷＩからの信号によってラッチ２０１Ｂに記憶される。他のアダプタの対応するビットも同様にラッチ２０２Ｂ〜２１６Ｂに記憶される。これらのラッチの出力はアービトレーション・ロジック２１８の入力Ｍ(１)〜Ｍ(１６)から取出される。アービトレーション・ロジック２１８はＦＵＬＬアルゴリズム（後で図７に関連して説明する）によって次にサービスされるバッファを選択する回路から成る。
【００６５】次に、図６のアービトレーション・ロジック２１８によって実現されるＦＵＬＬアルゴリズムをブロック図形式で示す図７について説明する。ここでは、 θ1〜θ16は図３の入力Ｔ(１)〜Ｔ(１６)の値を表わし、Ｃ(１)〜Ｃ(１６)は図６の入力Ｃ(１)〜Ｃ(１６)の値を表わすのに対し、Ｍ(１)〜Ｍ(１６)は図６の入力Ｍ(１)〜Ｍ(１６)の値を表わす（対応する入力信号が活動化されている場合、この値は１である）。ＡＮ及びＡＮ１はそれぞれ図６の入力ＡＮ及び出力ＡＮ１の値を表わす。記号ｊ及びＭＩＮは計算で用いる変数である。ｊの値は１〜１６をとるのに対し、ＭＩＮは１セットのＴＲＢから最小のＴＲＢの値を計算するために用いられる。図６のバス・アービトレーション制御部２１７の制御の下に反復して実行される計算は図７のＡで始まる。図７の流れ図は、以下に説明する小さな相違点の外は、図４の流れ図に類似している。図４のステップ３０２ではＣ(ｊ)が０に等しいかどうかが検査されるが、図７のステップ４０２ではＭ(ｊ)が０に等しいかどうかが検査される。ステップ３０６に続いて、ＭＩＮの値はθF である。図４のステップ３１２ではθj がＭＩＮに等しいかどうかが検査されるのに対し、ステップ４１２ではθj がＭＩＮよりも小さいか又はそれに等しいかどうかが検査される。
【００６６】前述のパケット交換装置において、全ての入力アダプタは、図１の入力アダプタ１のように、関連した入力リンクを備え、該リンクでパケットはバッファ・システムに到着する。他の実施例のなかには、バッファ・システム内のバッファの幾つかは、入力するパケットのために関連入力リンクを備えるのに対し、他のバッファは出力するパケットのために出力リンクを備えることがある。サーバが提供するサービスは、前者の場合にはバッファを空にし、後者の場合にはバッファを満たす。後者の場合、このようなシステムの実施例は図２乃至図７に基づいて設計することができる。前記設計には下記に概略的に示すような小さな変更が必要になるだけである。
【００６７】後者の場合、図３、図４、図６及び図７は変更されない。図２および図５は、入力リンクを有するバッファについては変更されないが、出力リンクを有するバッファについては下記のような小変更を必要とする。図２で、入力リンクは出力リンクになり、従って転送制御部１０６はバス（ポートA01P0〜A01P7）から出力リンク(ポートLIN(1))へのバイトの転送を制御する。その結果、データ経路の矢印の方向は逆になる。例えば、バイトは、ポートA01P0〜A01P7からラッチ１０７の入力Ｏ（前記例では出力Ｏ）に、そしてラッチ１０７の出力Ｉ（前記例では入力Ｉ）からパケットFIFO １０３ の入力Ｏ（前記例では出力Ｏ）に送られる。同様に、転送制御部１０６の出力ＰＢ及びＰＥはそれぞれデリミタFIFO１０４ の入力ＢＯ及びＥＯに送られる。そしてデリミタFIFO １０４ の入力ＢＩ及びＥＩは出力となり、それぞれのリンクの方向は逆になる。受信制御部１０２の入力ＢＣＬは出力となり、直列受信部１０１を介して出力リンクのタイミングを制御する。パケットFIFO １０３ の入力Ｉは出力となり、直列受信部１０１の出力Ｐ、ＰＢ、ＰＥ及びＢＣＬは入力となる。ＦＵＬＬアルゴリズムの図５についても同一の変更が行われる。
【００６８】前述の良好な実施例で、ｂ(ＴＲＢカウンタ１１０（図２）にあるビットの数)＝１０と仮定した。更に、リンクｉ(ｉ＝1,...,16)の速度ＳiはＳFの倍数であると仮定した。これらの仮定の結果として、良好な実施例で実施される方式は前述のようにＬＴＲＢ方式に似ている。この良好な実施例は大部分の実際の場合に満足すべきものである。しかしながら、所望すれば、実施例の精度は次のようにかなり高めることができる。
【００６９】値ｂ（ＴＲＢカウンタ１１０のビット数）を増すことにより、このビット数の制限から生じる誤りを任意に小さくすることができる。ＴＲＢの計算は少しも行わない異なるアプローチも可能である。すなわち、アダプタｉがパケットFIFO中にＱi バイトを有すると仮定すると、アダプタｉとアダプタｊのＴＲＢを比較することは(２Ｍ−Ｑi)／Ｓiと(２Ｍ−Ｑj)／Ｓjとを比較することを意味する。これは乗算を含む演算(２Ｍ−Ｑi)Ｓjと(２Ｍ−Ｑj)Ｓiとを比較することに等しいので、良好な実施例で説明した演算よりも効率は低いが、正確に実行することができる。そして前記手順での比較は１５回まで実行され、従って最小のＴＲＢが提供される。
【００７０】
【発明の効果】本発明によれば、オーバフローの可能性を無くし、必要なバッファの大きさを最小にし且つリンクの数及びそれらの相対速度とは無関係であるサービス方式がバッファ・システムに提供される。
【図面の簡単な説明】
【図１】本発明で用いるパケット交換装置（バッファ・システム）の概要図である。
【図２】（ＭＩＮアルゴリズムと呼ばれる）θM を用いる本発明で使用する入力アダプタの概要図である。
【図３】ＭＩＮアルゴリズムを用いる本発明で使用するバス・アービトレーション装置の概要図である。
【図４】ＭＩＮアルゴリズムのアービトレーション・ロジックの流れ図である。
【図５】（ＦＵＬＬアルゴリズムと呼ばれる）θF を用いる本発明で使用する入力アダプタの概要図である。
【図６】ＦＵＬＬアルゴリズムのバス・アービトレーション装置の概要図である。
【図７】ＦＵＬＬアルゴリズムのアービトレーション・ロジックの流れ図である。
【符号の説明】
１ 入力アダプタ
１６ 入力アダプタ
１７ 出力アダプタ
３２ 出力アダプタ
３３ バス
３４ バス・アービトレーション装置
１０１ 直列受信部
１０２ 受信制御部
１０３ パケットＦＩＦＯ
１０４ デリミタＦＩＦＯ
１０５ パケット・カウンタ
１０６ 転送制御部
１０７ ラッチ
１０８ ＰＣＦ検出器
１０９ ＮＣＦ検出器
１１０ ＴＲＢカウンタ
１１２ 増加カウンタ
１１３ バイト・カウンタ／検出器
２０１ ラッチ
２０１Ａ ラッチ
２０１Ｂ ラッチ
２１６ ラッチ
２１６Ａ ラッチ
２１６Ｂ ラッチ
２１７ バス・アービトレーション制御部
２１８ アービトレーション・ロジック
２１９ ラッチ
【特許請求の範囲】
【請求項１】Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくとも本質的に完全なパケットを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、本質的に十分な自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、上記Ｎ個のバッファを有するサブセットに関するθjの最小値であるθMを決定するステップと、（ｂ）バッファのサービスが入力リンクに対応したバッファからビット情報を取り除き、出力リンクに対応したバッファにビット情報を記憶させることであるとき、θj＝θMの値を持つバッファを上記サブセットのＮ個のバッファの中から選んでサービスするステップと、から成るバッファ・サービス方法。
【請求項２】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項１に記載のバッファ・サービス方法。
【請求項３】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであり、Ｍがそのシステムを介して転送される最大のパケットサイズであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくともＭバイトを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、少なくともＭバイトの自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、θFが上記Ｎ個のバッファを有するサブセットに関するθjの最小値で、ビット情報がｊ番目のバッファに対応するリンクの一定のリンク速度で上記ｊ番目のバッファへ連続的に到着し、叉は上記ｊ番目のバッファから連続的に送出されることを想定してθjを計算してθFを決定するステップと、（ｂ）ビット情報がバッファから対応する出力リンクへ送出されているとき、本質的に十分な自由記憶空間を有し、ビット情報が対応する入力リンクからバッファへ到着しているとき、本質的に完全なパケットを有するθj≦θFの値を持つバッファを上記バッファの中から選択してサービスするステップと、から成るバッファ・サービス方法。
【請求項４】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項３に記載のバッファ・サービス方法。
【請求項５】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくとも本質的に完全なパケットを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、十分な自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、上記Ｎ個のバッファを有するサブセットに関するθjの最小値であるθMを決定する手段と、（ｂ）バッファのサービスが入力リンクに対応したバッファからビット情報を取り除き、出力リンクに対応したバッファにビット情報を記憶させることであるとき、θj＝θMの値を持つバッファを上記サブセットのＮ個のバッファの中から選んでサービスする手段と、から成るバッファ・サービス装置。
【請求項６】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項５に記載のバッファ・サービス装置。
【請求項７】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであり、Ｍがそのシステムを介して転送される最大のパケットサイズであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくともＭバイトを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、少なくともＭバイトの自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されていとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、θFが上記Ｎ個のバッファを有するサブセットに関するθjの最小値で、ビット情報がｊ番目のバッファに対応するリンクの一定のリンク速度で上記ｊ番目のバッファへ連続的に到達し、叉は上記ｊ番目のバッファから連続的に送出されることを想定してθjを計算してθFを決定する手段と、（ｂ）ビット情報がバッファから対応する出力リンクへ送出されるとき、本質的に十分な自由記憶空間を有し、ビット情報が対応する入力リンクからバッファへ到達するとき、本質的に完全なパケットを有するθj≦θFの値を持つバッファを上記バッファの中から選択してサービスする手段と、から成るバッファ・サービス装置。
【請求項８】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項７に記載のバッファ・サービス装置。
【請求項１】Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくとも本質的に完全なパケットを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、本質的に十分な自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、上記Ｎ個のバッファを有するサブセットに関するθjの最小値であるθMを決定するステップと、（ｂ）バッファのサービスが入力リンクに対応したバッファからビット情報を取り除き、出力リンクに対応したバッファにビット情報を記憶させることであるとき、θj＝θMの値を持つバッファを上記サブセットのＮ個のバッファの中から選んでサービスするステップと、から成るバッファ・サービス方法。
【請求項２】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項１に記載のバッファ・サービス方法。
【請求項３】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであり、Ｍがそのシステムを介して転送される最大のパケットサイズであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくともＭバイトを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、少なくともＭバイトの自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、θFが上記Ｎ個のバッファを有するサブセットに関するθjの最小値で、ビット情報がｊ番目のバッファに対応するリンクの一定のリンク速度で上記ｊ番目のバッファへ連続的に到着し、叉は上記ｊ番目のバッファから連続的に送出されることを想定してθjを計算してθFを決定するステップと、（ｂ）ビット情報がバッファから対応する出力リンクへ送出されているとき、本質的に十分な自由記憶空間を有し、ビット情報が対応する入力リンクからバッファへ到着しているとき、本質的に完全なパケットを有するθj≦θFの値を持つバッファを上記バッファの中から選択してサービスするステップと、から成るバッファ・サービス方法。
【請求項４】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項３に記載のバッファ・サービス方法。
【請求項５】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくとも本質的に完全なパケットを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、十分な自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されているとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、上記Ｎ個のバッファを有するサブセットに関するθjの最小値であるθMを決定する手段と、（ｂ）バッファのサービスが入力リンクに対応したバッファからビット情報を取り除き、出力リンクに対応したバッファにビット情報を記憶させることであるとき、θj＝θMの値を持つバッファを上記サブセットのＮ個のバッファの中から選んでサービスする手段と、から成るバッファ・サービス装置。
【請求項６】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項５に記載のバッファ・サービス装置。
【請求項７】 Ｎ個のリンクに接続し、上記Ｎ個のリンクのうちのｊ番目のリンクがｊ番目のバッファと個々に対応し、上記Ｎ個のリンクのうちＸ個のリンクが入力リンクで、（Ｎ−Ｘ）個のリンクが出力リンクであり、Ｍがそのシステムを介して転送される最大のパケットサイズであるバッファ・システムにおいて、（ａ）上記Ｎ個のバッファを有するサブセットにおける各バッファは、ビット情報が対応する上記入力リンクから到着しているとき、少なくともＭバイトを有し、ビット情報が上記各バッファから上記出力リンクへ送出されているとき、少なくともＭバイトの自由記憶領域を有し、θjは、ビット情報が対応する上記ｊ番目の入力リンクから上記ｊ番目のバッファに到着しているとき、上記ｊ番目のバッファが限界に達するのに必要な時間で、ビット情報が上記ｊ番目のバッファから上記ｊ番目の出力リンクへ送出されていとき、上記ｊ番目のバッファが空になるのに必要な時間であるとき、θFが上記Ｎ個のバッファを有するサブセットに関するθjの最小値で、ビット情報がｊ番目のバッファに対応するリンクの一定のリンク速度で上記ｊ番目のバッファへ連続的に到達し、叉は上記ｊ番目のバッファから連続的に送出されることを想定してθjを計算してθFを決定する手段と、（ｂ）ビット情報がバッファから対応する出力リンクへ送出されるとき、本質的に十分な自由記憶空間を有し、ビット情報が対応する入力リンクからバッファへ到達するとき、本質的に完全なパケットを有するθj≦θFの値を持つバッファを上記バッファの中から選択してサービスする手段と、から成るバッファ・サービス装置。
【請求項８】Ｍが前記システムを介して転送される最大のパケットのサイズであるとき、上記各バッファが少なくとも２Ｍのバッファ・サイズを有する請求項７に記載のバッファ・サービス装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【特許番号】第２５５９９４０号
【登録日】平成８年（１９９６）９月５日
【発行日】平成８年（１９９６）１２月４日
【国際特許分類】
【出願番号】特願平４−２０７４２
【出願日】平成４年（１９９２）１月１０日
【公開番号】特開平５−６８０５８
【公開日】平成５年（１９９３）３月１９日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【参考文献】
【文献】 特開 平１−２０４５４８（ＪＰ，Ａ）
【文献】 特開 昭６３−３０１６４４（ＪＰ，Ａ）
【登録日】平成８年（１９９６）９月５日
【発行日】平成８年（１９９６）１２月４日
【国際特許分類】
【出願日】平成４年（１９９２）１月１０日
【公開番号】特開平５−６８０５８
【公開日】平成５年（１９９３）３月１９日
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレイション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【参考文献】
【文献】 特開 平１−２０４５４８（ＪＰ，Ａ）
【文献】 特開 昭６３−３０１６４４（ＪＰ，Ａ）
[ Back to top ]