(57)【要約】【課題】パケット送信時に周期を有する順序番号を付加し、受信時に該順序番号に基づいてパケットを送信順に並べ替えるパケット送信システムにおいて、順序番号の周期より大きなパケット順序の入れ替わりが発生した際の伝送効率を向上させることを目的とする。【解決手段】受信パケット用の記憶手段と受信パケットの順序番号に対応するフラグ用のメモリと次に読み出すパケットの順序番号を示すカウンタからなるパケットバッファ部を複数と、順序番号の周期より大きな順序入れ替わりを起こしたパケット用の記憶手段とを設け、順序入れ替わりを起こしたとみなされるパケットを複数のパケットバッファ部に属するパケットとして複数回読み出す。【選択図】        図１
2004248026.tif 000002
【特許請求の範囲】
【請求項１】
受信パケットを記憶する第１の記憶手段と、第１の記憶手段に記憶されたパケットに対応するフラグを記憶する第２の記憶手段と、第１の記憶手段から読み出すパケットの順序情報を示す第１のカウンタにより構成されるパケットバッファ部複数と、順序情報の周期を超えて遅延しているパケットの有無を示すフラグを記憶する第４の記憶手段と、該順序情報の周期を超えて遅延しているパケットの順序情報を記憶する第５の記憶手段と、該順序情報の周期を超えて遅延しているパケットを記憶する第６の記憶手段と、第６の記憶手段に書き込まれたパケットの個数を示す第２のカウンタ及び制御部によって構成されるパケット並べ替え手段。
【請求項２】
請求項１において、パケットを受信すると第１の記憶手段にパケットを書き込むとともに、該パケットに対応するフラグを第２の記憶手段に書き込み、任意の順序情報を有するパケットを受信する前に少なくとも一組の同一順序番号を有するパケットを受信すると順序情報の周期を超えて遅延しているパケットが発生したとみなし、第４の記憶手段に順序情報の周期を超えて遅延しているパケットが発生している旨を示すフラグを立て、第５の記憶手段に該順序情報の周期を超えて遅延しているパケットの順序情報を書き込み、第５の記憶手段に書き込まれている順序情報のパケットを受信したら第６の記憶手段に書き込み、第２のカウンタをインクリメントさせ、第５の記憶手段に書き込まれている順序情報以外の順序情報一周期分のパケットに関しては、順序情報の周期を超えて遅延しているバケットが発生する以前に書き込み対象としていたパケットバッファ部とは異なるバケットバッファ部に属する第１の記憶手段パケットに書き込み、対応するフラグを第２の記憶手段に書き込む書き込み制御方法と、第４の記憶手段に順序情報の周期を超えて遅延しているパケットがあることを示すフラグが立っていない場合には、第１のカウンタに示されている順序情報と第２の記憶手段に記憶されている受信パケットに対応するフラグとに基づいて第１の記憶手段から所定の順序でパケットを読み出し、第４の記憶手段にフラグが立っている場合には、第３のカウンタの値を監視し、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして読み出した後、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第４の記憶手段にフラグが立てられる以前に読み出し対象としていたパケットバッファ部とは異なるパケットバッファ部に属する第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして読み出した後、該第１の記憶手段から全てのパケット読み出すと、以降は第４の記憶手段にフラグが立てられる以前の読み出し対象であったパケットバッファ部に属する第１の記憶手段からパケットの読み出しを続ける読み出し制御方法とからなるパケット並べ替えのための制御方法。
【請求項３】
請求項１において、パケットを受信すると第１の記憶手段にパケットを書き込むとともに、パケットに対応するフラグを第２の記憶手段に書き込み、任意の順序情報を有するパケットを受信する前に少なくとも一組の同一順序番号を有するパケットを受信すると順序情報の周期を超えて遅延しているパケットが発生したとみなし、第４の記憶手段に順序情報の周期を超えて遅延しているパケットが発生している旨を示すフラグを立て、第５の記憶手段に該遅延パケットの順序情報を書き込み、第５の記憶手段に書き込まれている順序情報のパケットを受信したら第６の記憶手段に書き込み、第２のカウンタをインクリメントさせ、以後再度順序情報の周期を超えて遅延しているパケットの発生を検出するまでは、第４の記憶手段にフラグを立てる以前に書き込み対象としていたパケットバッファ部とは異なるパケットバッファ部に属する第１の記憶手段に受信パケットを書き込み、対応するフラグを第２の記憶手段に書き込む書き込み制御方法と、第４の記憶手段に順序情報の周期を超えて遅延しているパケットがあることを示すフラグが立っていない場合には、第１カウンタに示されている順序情報と第２の記憶手段に記憶されている受信パケットに対応するフラグとに基づいて第１の記憶手段から所定の順序でパケットを読み出し、第４の記憶手段にフラグが立っている場合には、第３のカウンタの値を監視し、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第１の記憶手段に記憶されてしくるパケット群の所定の位置のパケットとして読み出した後、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第４の記憶手段にフラグが立てられる以前に読み出し対象としていたパケットバッファ部とは異なるパケットバッファ部に属する第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして読み出し、以降は再度第４の記憶手段にフラグが立てられるまでは読み出し対象とするパケットバッファ部の切り替えを行わない読み出し制御方法とからなるパケッ卜並べ替えのための制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信ネットワークに関し、更に詳しくは、受信側における受信パケットの順序が送信側における送信パケットの順序と一致することが保証されないネットワークにおけるパケットの並べ替え手段に関する。
【０００２】
【従来の技術】
近年、簡易な構成の大容量ネットワークシステムとして、ノード装置を並列多重伝送路でリング状に接続したネットワークシステムが検討されている。このネットワークシステムの詳細は、特開平８−１７２３９４号公報「ネットワークシステム及びノード装置及びコンセントレータ及びネットワークシステムにおける伝送制御方法」、特開平８−２３７３０６号公報「ネットワークシステム及びノード装置及び伝送制御方法」において述べられている。以下に、特開平８−２３７３０６号公報「ネットワークシステム及びノード装置及び伝送制御方法」で述べられているネットワークシステムを例として挙げる。
【０００３】
図６は従来のネットワークにおけるノード装置の構成図であり、ノード装置６００にサブ伝送路を介して端末６５１〜６５８を接続している例を示している。符号６０１〜６０８は、分離挿入手段であるところの分離挿入部であり、並列多重伝送路から入力されるパケットのアドレスを検出し、サブ伝送路を介して端末へ伝送させるパケットとバッファへ入力させるパケットに分離すると共に、端末から伝送されてくるパケットを、並列多重伝送路から入力されるパケット流に挿入する機能を有している，符号６１１〜６１８は、バッファ手段であるところのバッファであり、分離挿入部から出力されるパケット屋スイッチ６４１の出力端に対応した記憶領域に一時記憶する機能を有している。符号６２１〜６２８、６３１〜６３８はノード間を接続するための並列多重伝送路であり、例えば空間的に分離された複数の光ファイバ伝送路であったり、あるいは１本の光ファイバ上に波長分割されて多重化された波長多重伝送路であったりする。符号６４１はスイッチであり、スイッチ制御部６４２に制御されて、入力ＩＮ１〜ＩＮ８に入力したパケットを任意の出力端ＯＵＴｌ〜ＯＵＴ８へ接続するものである。スイッチ６４１は、並列多重伝送路に複数の光ファイバ伝送路を用いるときには、空間スイッチ等を用いて交換を行う。また、波長多重伝送路を用いる場合には、図６とは若干構成が異なるが、複数の可変波長レーザダイオードと合波器からなる送信部を波長多重伝送路へ接続し、波長多重伝送路の受信部で分波器により各波長を分離することでノード間でスイッチを構成し、可変波長レーザダイオードの送信波長を波長λ１〜λ８の任意の波長に設定することで交換を行う。符号６４２はスイッチ制御部であり、例えば図９の制御パターンに従ってスイッチを制御する。符号６４３はバッファ制御部であり、各バッファに接続されたスイッチの入力端が所望の出力端に接続されたときに、バッファから記憶されているパケットを読み出すように制御するものである。
【０００４】
図７は分離挿入部６０１〜６０８の内部構成を示す図であり、７０１はパケットのヘッダから宛先アドレスを検出するヘッダ検出部、７０２、７０３は入力信号を出力または遮断するためのゲート、７０４は２つの入力信号のどちらか一方を出力するセレクタ、７０５はパケットを一時記憶するためのＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）である。分離挿入部６０１〜６０８において、並列多重伝送路より入力したパケットはヘッダ検出部７０１においてヘッダが検出され、ヘッダの内容によりゲート７０２と７０３の開閉の処理を行う。ヘッダ検出部７０１にはあらかじめその分離挿入部に接続されている端末のアドレスが記憶されており、検出した宛先アドレスが記憶しているアドレスと一致したときには、ゲート７０３を開き且つゲート７０２を閉じて端末方向のみにそのパケットを出力する。また、検出した宛先アドレスが記憶しているアドレスと一致しない場合は、ゲート７０２を開き且つゲート７０３を閉じて、セレクタ７０４のみにそのパケットを出力してセレクタ７０４を通ってバッファへ送られる。一方端末から伝送されてきたパケットはＦＩＦＯ７０５に一時記憶し、ゲート７０２からセレクタ７０４に入力したパケット流にすき間があるときにＦＩＦＯ７０５から読み出され、セレクタ７０４を通ってバッファへ送られるように動作する。
【０００５】
図８はバッファ６１１〜６１８の内部構成であり、８０１はスイッチ６４１の出力端に対応した記憶領域１〜記憶領域８からなるバッファメモリ、８０２はパケットのヘッダから宛先アドレスを検出するヘッダ検出部、８０３はバッファメモリ８０１に書き込みアドレスを供給するためのアドレスカウンタである。バッファ６１１〜６１８において、分離挿入部より入力したパケットはヘッダ検出部８０２においてヘッダが検出され、ヘッダの内容によりそのパケットを記憶する記憶領域が決定される。ヘッダ検出部８０２にはあらかじめ隣接する下流ノードに接続される端末のアドレスが記憶されており、検出した宛先が記憶しているアドレスと一致したときには、その端末が接続されている伝送路つまりスイッチ６４１の出力端に対応した記憶領域を指定し、アドレスカウンタ８０３より書き込みアドレスを発生させてバッファメモリ８０１に記憶させる。また、検出した宛先アドレスが記憶しているアドレスと一致しないときには、任意の記憶領域にそのパケットを記憶させるごとく制御する。
【０００６】
図９はスイッチ６４１の入出力の接続関係を示す制御パターンであり、制御アドレスＡｌ〜Ａ８によりスイッチの入出力接続関係が変更される。入力端ＩＮｌ〜ＩＮ８はバッファ６１１〜６１８に対応しており、出力端ＯＵＴｌ〜ＯＵＴ８（または送信波長λ１〜λ８）は各バッファの記憶領域１〜記憶領域８に対応している。
【０００７】
図１０は、図６に示したノード装置を用いたネットワークシステムの構成例であり、４つのノード装置１００１〜１００４を並列多重伝送路１００５〜１００８によってリング型に接続し、各ノード装置にはそれぞれ８本のサブ伝送路を介して８台の端末が接続されている。端末１０１１〜１０１８は端末６５１〜６５８に対応し、同様に１０２１〜１０２８、１０３１〜１０３８、１０４１〜１０４８も端末６５１〜６５８に対応している。
【０００８】
図１１はこのネットワークの通信原理を説明するための図であり、１１０１〜１１０４はノード装置、１１０５〜１１０８はスイッチ６４１に対応した交換スイッチ、１１０９〜１１１２はバッファ６１１〜６１８に対応したバッファ、１１２１〜１１３６は端末、Ａ，Ｂ，Ｃ，Ｄはリングを成す並列伝送路である。
【０００９】
まず、図１１を用いてこのネットワークの通信原理について説明する。このネットワークは複数のリングＡ，Ｂ，Ｃ，Ｄを有し、各リング間は交換スイッチ１１０５〜１１０８によって相互に接続されている。各端末は並列伝送路Ａ，Ｂ，Ｃ，Ｄの中の１つのリング伝送路に接続されており、他のリングに接続された端末と通信を行う場合は、少なくとも１回、任意の交換スイッチで他のリングに交換されることで通信が行われる。交換が行われる位置は特定されないが、宛先ノードの１つ手前のノードで宛先の伝送路へ乗り換えて、他のノードでは任意の伝送路へ乗り換えるようにすると通信制御が容易になる。このネットワークはノード装置を簡略化するため、交換スイッチ１１０５〜１１０８は入力信号とは無関係に入出力の接続関係を特定の巡回パターンにしたがって一定周期に変更し、バッファ１１０９〜１１１２で入力信号を一時蓄積して、交換スイッチの入出力接続関係が所望の関係になったときにバッファからパケットを読み出すようにして交換が行われる。
【００１０】
例えば、端末１１２２から端末１１３２へ通信する場合は、端末１１２２から出力されたパケットではノード１１０１のバッファ１１０９に蓄積され、スイッチ１１０５の入力端ＩＮ２が例えば出力端ＯＵＴ２に接続されたときにバッファから読み出されて伝送路Ｂに出力され、ノード１１０２のバッファ１１１０へ入力してスイッチ１１０６のＩＮ２とＯＵＴ４が接続されたときにバッファから読み出されることにより、伝送路Ｄへ出力されて端末１１３２へパケットが送られる。
【００１１】
このように、それぞれのノード装置で任意のリング伝送路に乗り換えることにより通信が行われる。
【００１２】
次に、図６、図１０を用いて詳細を説明する。説明においては並列多重伝送路は空間的に分離された複数の光ファイバ伝送路、スイッチは空間スイッチとして説明するが、波長多重伝送路を用いる場合も上記原理に基づいており、ほぼ同様の動作が行われる。仮に、端末１０１２から端末１０３５へ通信する場合の動作例について説明する。
【００１３】
端末１０１２からの送信データは固定長のパケットに分割され、各パケットのヘッダに宛先アドレスが記載されて出力される。出力されたパケットはサブ伝送路を通ってノード装置１００１へ入力し、分離送入部６０２のＦＩＦＯ７０５に一時記憶される。記憶されたパケットは、ゲート７０２からセレクタ７０４に入力したパケット流にすき間があるときにＦＩＦＯ７０５から読み出され、セレクタ７０４を通ってバッファへ送られる。
【００１４】
バッファ６１２のヘッダ検出部８０２は、入力したパケットのヘッダを検出すると検出した宛先アドレスが記憶しているアドレスと一致しないので、任意の記憶領域を指定する。書き込みアドレスカウンタ８０３はその情報を受けて書き込みアドレスを発生させ、そのパケットをバッファメモリ８０１の記憶領域に書き込ませる。ここでは仮に記憶領域１に記憶されるとする。
【００１５】
バッファ制御部６４３はスイッチ６４１の入力端ＩＮ２が出力端ＯＵＴｌに接続されるまでそのパケットの読み出しを待機させ、接続された時にパケットを読み出す。
【００１６】
スイッチ制御部６４２は、図９に示すテーブルのように制御アドレスをＡ１，Ａ２，Ａ３，Ａ４，Ａ５，Ａ６，Ａ７，Ａ８と順次供給してスイッチ６４１の接続関係を変更させ、かつ制御アドレスを例えば１パケット長周期に供給することで、８パケット周期で同じパターンを繰り返すように制御している。その情報をバッファ制御部６４３へ通知することでバッファからの読み出しタイミングが制御される。ここではスイッチ６４１の入力端ＩＮ２が出力端ＯＵＴｌに接続されたときにバッファ６１２の記憶領域１からパケットが読み出されることにより、そのパケットはスイッチ６４１を通って伝送路６３１へ出力される。
【００１７】
伝送路６３１を伝送されたパケットは、ノード装置１００２の分離送入部６０１に入力し、ヘッダ検出部７０１においてパケットのヘッダが検出される。検出した宛先アドレスは記憶しているアドレスと一致しないので、ゲート７０２を開きゲート７０３を閉じてセレクタ７０４へそのパケットを出力する。分離挿入部６０１のセレクタ７０４へ出力されたパケットは、セレクタ７０４を通りバッフア６１１へ入力する。
【００１８】
ヘッダ検出部８０２はヘッダを検出すると検出した宛先アドレスが記憶しているアドレスと一致しているので、宛先アドレスの端末が接続される伝送路に対応する記憶領域を指定する。ここでは宛先の端末が伝送路６３５に接続されているので記憶領域５に記憶させる。
【００１９】
バッファ制御部６４３はスイッチ６４１のＩＮ１がＯＵＴ５に接続されたときにバッファ６１１の記憶領域５からパケットを読み出すことで、パケットはスイッチ６４１を通って伝送路６３５へ出力される。伝送路を通ってノード装置１００３の分離送入部６０５に入力したパケットは、ヘッダ検出部７０１でヘッダが検出され、検出した宛先アドレスが記憶しているアドレスと一致したので、ゲート７０３を開き且つゲート７０２を閉じて端末方向のみにそのパケットを出力する。分離挿入部６０５から端末方向へ出力されたパケットは、サブ伝送路を通って端末１０３５へ送られ受信される。
【００２０】
このようにして通信が行われる。
【００２１】
しかしながら、図１１を用いて説明したようなネットワークシステムにおいてパケットの送受信を行う場合、送信側におけるパケットの送出順序と受信側におけるパケットの受信順序とが必ずしも一致しないという問題がある。そこで、「ノード装置及び複数のノード装置を有する通信ネットワーク及びそれらの制御方法」において図１２に示すように分離挿入部と端末との間に並べ替え処理部１２０１〜１２０８を設けたノード装置１２００が提案されている。ノード装置１２００の内部では、パケット送信時にはヘッダ変換部１２１１〜１２１８において送出パケットのヘッダにモジュロｎ（ｎ＝１，２，…）のシーケンシャル番号を付与し、受信時には並べ替え処理部１２０１〜１２０８において分離挿入部から受信したパケット列を一時蓄積し該シーケンシャル番号順に並べ替えて端末へ送出することにより、送受信間でのパケットの順序を一致させている。
【００２２】
【発明が解決しようとする課題】
しかしながら、従来例ではシーケンシャル番号の周期を超えてパケットの到着順序が入れ替わった場合の動作に関しては考慮していなかった。特にシーケンシャル番号の周期を超えて遅延したパケットが発生すると、該遅延パケットが到着したとき、そのパケットが前の周期のシーケンシャル番号のものか処理中の周期のシーケンシャル番号のものか判別することが困難であり、前述の２つの同一シーケンシャル番号のパケットの順序が入れ替わっていると、少なくとも端末での受信データの２個所で誤りが生じるという問題点があった。
【００２３】
【課題を解決するための手段】
受信パケットを記憶する第１の記憶手段と、第１の記憶手段に記憶されたパケットに対応するフラグを記憶する第２の記憶手段と、第１の記憶手段から読み出すパケットの順序情報を示す第１のカウンタからなるパケットバッファ部複数と、順序情報の周期を超えて遅延しているパケットの有無を示すフラグを記憶する第４の記憶手段と、順序情報の周期を超えて遅延しているパケットの順序情報を記憶する第５の記憶手段と、順序情報の周期を超えて遅延しているパケットを記憶する第６の記憶手段と、第６の記憶手段に書き込まれたパケットの個数を示す第２のカウンタ及び制御部によりパケット並べ替え手段を構成し、初期状態ではバケットを受信すると第１の記憶手段にパケットを書き込むとともに、該パケットに対応するフラグを第２の記憶手段に書き込み、任意の順序情報を有するパケットを受信する前に少なくとも一組の同一順序番号を有するパケットを受信すると順序情報の周期を超えて遅延しているパケットが発生したとみなし、第４の記憶手段に順序情報の周期を超えて遅延しているバケットが発生している旨を示すフラグを立て、第５の記憶手段に該遅延パケットの順序情報を書き込み、第５の記憶手段に書き込まれている順序情報のパケットを受信したら第６の記憶手段に書き込み、第２のカウンタをインクリメントさせ、第５の記憶手段に書き込まれている順序情報以外のパケットに関しては書き込み対象とするパケットバッファ部を変更して、第４の記憶手段にフラグが立てられる以前のパケット書き込みと同様の書き込み処理を行う書き込み制御方法と、第４の記憶手段にフラグが立てられていない場合には、第１のカウンタに示されている順序情報と第２の記憶手段に記憶されている受信パケットに対応するフラグとに基づいて第１の記憶手段から所定の順序でパケットを読み出し、第４の記憶手段にフラグが立てられている場合には、第３のカウンタの値を監視し、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして読み出した後、第６の記憶手段から第５の記憶手段に記憶されている順序番号のパケットを第４の記憶手段にフラグが立てられる以前に読み出し対象としていたパケットバッファ部とは異なるパケットバッファ部に属する第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして読み出す読み出し制御方法とにより、端末が正しい順序のパケット列を受信できる確率を向上させる。
【００２４】
（作用）
端末間で誤り検出または誤り訂正機能を有する上位層プロトコルを使用している状況下で、端末において、第６の記憶手段に記憶されているバケットを第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして挿入することにより得られたデータと、第６の記憶手段に記憶されているパケットを順序情報の周期を超える遅延パケット発生以前の読み出し対象であったパケットバッファ部と異なるパケットバッファ部に属する第１の記憶手段に記憶されているパケット群の所定の位置のパケットとして挿入することにより得られたデータとに対して誤り検出処理を実行することにより、第６の記憶手段に記憶されていた順序番号のパケットが前者の第１の記憶手段に記憶されていたパケット群か後者の第１の記憶手段に記憶されていたパケット群のどちらかに属するパケットであった場合、少なくとも正しいデータを得ることができ、ノード間のバケット伝送中に生じたパケットの順序入れ替わりに起因するデータ損失が減少する。
【００２５】
【発明の実施の形態】
（実施形態１）
図１は本実施形態の並べ替え処理部の構成図である。図１の並べ替え処理部は、ヘッダ情報として少なくとも送信順序を示すモジュロｎ（ｎ＝１，２，…）のシーケンシャル番号とパケットの基となるデータ単位を識別する情報とが記述されているパケットを受信して、シーケンシャル番号順に該パケットを送出するものである。さらにパケットの基となるデータ単位には誤り検出または誤り訂正に必要な処理がなされている。
【００２６】
符号１０１は書き込み・読み出し制御部であり、後述する制御方法に従って、後述のパケットメモリへの入力パケットの書き込み及びパケットメモリからのパケットの読み出しを行う。
【００２７】
符号１０２は第１のパケットメモリであり、入力パケットをシーケンシャル番号に対応した領域に一時的に記憶する。また１周期分のシーケンシャル番号に対応するパケットを記憶できるだけの領域を有する。
【００２８】
符号１０３は第１のストアフラグメモリであり、どのシーケンシャル番号のパケットが第１のパケットメモリ１０２に書き込まれているかを示すフラグが記憶される。
【００２９】
符号１０４は第１の読み出しカウンタであり、第１のパケットメモリ１０２から次に読み出すべきパケットのシーケンシャル番号を示し、第１のパケットメモリ１０２から１つのパケットが読み出される毎に値がインクリメントされる。また後述の遅延パケットメモリ１０８からパケットを読み出した際にもインクリメントされる。
【００３０】
符号１０５は遅延フラグメモリであり、受信パケットの順序がシーケンシャル番号の周期（ｎパケット）を超えて入れ替わった（以下、周期超遅延と記す）ときにフラグが立てられる。
【００３１】
符号１０６は遅延シーケンスメモリであり、周期超遅延が発生したときに該当するシーケンシャル番号を記憶する。
【００３２】
符号１０７は遅延パケットカウンタであり、後述の遅延パケットメモリ１０８に書き込まれているパケットの数を示す。
【００３３】
符号１０８は遅延パケットメモリであり、周期超遅延が発生中に遅延シーケンスメモリ１０６に記憶されたシーケンシャル番号のパケットを受信した際に該パケットが記憶される。少なくともパケット２個に相当する記憶領域を有する。
【００３４】
符号１０９は第２のパケットメモリであり、シーケンシャル番号の任意の周期のパケットを受信している際に周期超遅延が発生したときに次の周期のシーケンシャル番号の入力パケットからシーケンシャル番号１周期分のパケットをシーケンシャル番号に対応した領域に一時的に記憶する。
【００３５】
符号１１０は第２のストアフラグメモリであり、どのシーケンシャル番号のパケットが第２のパケットメモリ１０９に書き込まれているかを示すフラグが記憶される。
【００３６】
符号１１１は第２の読み出しカウンタであり、第２のパケットメモリ１０９から次に読み出すべきパケットのシーケンシャル番号を示し、第２のパケットメモリ１０９から１つのパケットが読み出される毎に値がインクリメントされる。また後述の遅延パケットメモリ１０８からパケットを読み出した際にもインクリメントされる。
【００３７】
符号１１２は第１のパケットバッファ部であり、パケットメモリ、ストアフラグメモリと読み出しにより構成される。
【００３８】
符号１１３は第２のパケットバッファ部であり、パケットメモリ、ストアフラグメモリと読み出しカウンタにより構成される。
【００３９】
図２は書き込み・読み出し制御部１０１において実行される書き込み制御のフローチャートである。パケット待機状態（Ｓ２０１）から、読み出し制御部１０１にパケットが入力されると該パケットのヘッダ内に記述されているシーケンシャル番号（Ｓとする）を読み取り（Ｓ２０２）、周期超遅延の発生を検査し（Ｓ２０３）、周期超遅延が発生していれば遅延フラグメモリ１０５にフラグを立て（Ｓ２０４）、遅延シーケンスメモリ１０６にｉを書き込む（Ｓ２０５）。ただし周期超遅延とは、シーケンシャル番号ｉ（ｉは１以上ｎ以下の整数）のパケットを受信する前に重複するシーケンシャル番号ｉ＋１〜ｎまたは１〜ｉ−１のパケットを受信した状態を持す。周期超遅延が起こっていなければ、第１のパケットメモリ１０２のアドレスとしてｆ（Ｓ）を生成し（Ｓ２０６）、第１のストアフラグメモリ１０３のｇ（Ｓ）で表されるアドレスにフラグを立てる（Ｓ２０８）とともに、アドレスｆ（Ｓ）に該パケットが書き込まれる（Ｓ２０７）。ただしｆ（）、ｇ（）は任意の関数とする。遅延フラグメモリ１０５にフラグが立つとｉ＋１からシーケンシャル番号１周期分（詳しくはシーケンシャル番号ｉ＋１〜ｎおよび１〜ｉ−１であり、１周期より１少ない）の入力パケットを第二のパケットメモリ１０９のアドレスＦ（Ｓ）に書き込み（Ｓ２０９，Ｓ２１１）、第２のストアフラグメモリ１１０のアドレスＧ（Ｓ）のフラグを立てる（Ｓ２１０）。ただしＦ（），Ｇ（）は任意の関数である。遅延フラグメモリ１０５にフラグが立てられているときにシーケンシャル番号ｉのパケットが入力されると、該シーケンシャル番号ｉのパケットは遅延パケットメモリ１０８のアドレスｆｄ（Ｃ）（Ｃは遅延パケットカウンタの値）に書き込まれ（Ｓ２１２，Ｓ２１３）、遅延パケットカウンタ１０７の値がインクリメントされる（Ｓ２１４）。ただしｆｄ（）は任意の関数であり、初期状態では遅延パケットカウンタ１０７の値は０を示しているものとする。
【００４０】
図３は書き込み・読み出し制御部１０１において実行される読み出し制御のフローチャートである。初期状態において第１の読み出しカウンタ１０４は１にセットされている。第１のストアフラグメモリ１０３を監視し最初のパケットであるシーケンシャル番号１のパケットに対応するフラグが立つまで待機状態となり、シーケンシャル番号１に対応するフラグが立つと（Ｓ３０４）、第１のパケットメモリ１０２からパケットを読み出し（Ｓ３０５、Ｓ３０７）、第１のストアフラグメモリ１０３のシーケンシャル番号１に対応するフラグを落とす（Ｓ３０６）。以下、遅延フラグメモリのフラグが立てられていない場合、最初のパケットを読み出すときと同様に第１の読み出しカウンタ１０４の値がｊ（ｊは１以上ｎ以下の整数）であるときに、第１のストアフラグメモリ１０３のシーケンシャル番号ｊに対応するフラグが立っていれば（Ｓ３０４）第１のパケットメモリからシーケンシャル番号ｊのパケットを読み出し（Ｓ３０５、Ｓ３０７）、第１のストアフラグメモリ１０３のシーケンシャル番号ｊに対応するフラグを落とす（Ｓ３０６）。遅延フラグメモリ１０５にフラグが立っている場合、第２のストアフラグメモリ１１０のｉ（遅延シーケンスメモリに記憶されているシーケンシャル番号）以外の全てのシーケンシャル番号のパケットに対応するフラグが立っているかを監視し続け（Ｓ３１２）、ｉ以外の全てのフラグが立っていれば第１のパケットメモリからシーケンシャル番号ｉ＋１〜ｎ及び１〜ｉ−１のパケットを読み出した後（Ｓ３２３，Ｓ３２４，Ｓ３２５，Ｓ３２６）、第２のパケットメモリからの読み出しモードに遷移し（Ｓ３２８）、遅延フラグメモリ１０５のフラグを落とし（Ｓ３３６）、第２のパケットメモリからシーケンシャル番号ｉ＋１〜ｎ及び１〜ｉ−１のパケットを読み出し（Ｓ３０１，Ｓ３０２，Ｓ３０３，Ｓ３０８〜Ｓ３１１、Ｓ３０１〜Ｓ３０３）、第１のパケットメモリ１０２からのパケット読み出しモードに遷移する（Ｓ３０３→Ｓ３０４）。第２のストアフラグメモリ１１０のｉ以外のフラグのいずれかが立っていない場合は、遅延パケットカウンタ１０７の値が１以上になるまで待機状態となる（Ｓ３１３）。遅延パケットカウンタ１０７の値が１になると（Ｓ３１４）、遅延パケットメモリ１０８からシーケンシャル番号ｉのパケット（パケットｉ１とする）を読み出した（Ｓ３１５、Ｓ３１６）後、遅延パケットメモリ１０８から読み出したパケットｉ１が送信データ単位の末尾を含むパケットであれば待機状態となり（Ｓ３１７→Ｓ３１２）、該パケットｉ１が送信データ単位の末尾を含むパケットでなければシーケンシャル番号ｉ＋１から該送信データ単位の末尾を含むパケットまでを第１のパケットメモリ１０２から読み出し（Ｓ３１７→Ｓ３１８〜Ｓ３２０）、待機状態となる（Ｓ３１７→Ｓ３１２）。続いて第２のストアフラグメモリ１１０においてシーケンシャル番号ｉのパケットに対応するフラグ以外の全てのフラグが立つ前に遅延パケットカウンタ１０７の値が再度インクリメントされると（Ｓ３１２→Ｓ３１３）、第１の読み出しカウンタ１０４に遅延シーケンスメモリ１０６からｉがロードされ、遅延パケットメモリ１０８から読み出されていない方のシーケンシャル番号ｉのバケット（パケットｉ２とする）を読み出した（Ｓ３２１，Ｓ３２２）後、第１のパケットメモリ１０９からシーケンシャル番号ｉ＋１〜ｎ続いてシーケンシャル番号１〜ｉ−１のパケットを読み出し、第１のストアフラグメモリの対応するフラグを落とした後（Ｓ３２３〜Ｓ３２７）、第２のパケットメモリ１０９からのパケット読み出しモードに遷移し（Ｓ３２８）、遅延パケットメモリ１０８からパケットｉ１を読み出し（Ｓ３３０，Ｓ３３１）、遅延パケットカウンタ１０７をデクリメントし（Ｓ３３２）、パケットｉ１が送信データ単位の末尾を含むパケットであれば第２の読み出しカウンタ１１１に遅延シーケンスメモリ１０６からｉをロードし（Ｓ３３７→Ｓ３２９）、遅延バケットメモリ１０８からパケットｉ２を読み出し（Ｓ３３３，Ｓ３３４）、遅延パケットカウンタ１０７をデクリメントし（Ｓ３３５）、遅延フラグメモリ１０５のフラグを落とし（Ｓ３３６）、第２のストアフラグメモリ１１０を参照しながら第２のパケットメモリ１０９からパケットの読み出しを続ける（Ｓ３０１，Ｓ３０２，Ｓ３０３→Ｓ３０８〜Ｓ３１１）。また、パケットｉ１が送信データ単位の末尾を含むパケットでなければ（Ｓ３３７→Ｓ３３８）、パケットｉ１の読み出し後、第２のパケットメモリ１０９から送信データ単位の末尾を含むパケットまでを読み出し（Ｓ３〜３７〜Ｓ３４０）、第２の読み出しカウンタ１１１に遅延シーケンスメモリ１０６からｉをロードし（Ｓ３３７→Ｓ３２９）、遅延パケットメモリ１０８からパケットｉ２を読み出し（Ｓ３３３，Ｓ３３４）、遅延パケットカウンタ１０７をデクリメントし（Ｓ３３５）、遅延フラグメモリ１０５のフラグを落とした（Ｓ３３６）後、第２のストアフラグメモリ１１０を参照しながら第２のパケットメモリ１０９からパケットの読み出しを続ける（Ｓ３０１，Ｓ３０２，Ｓ３０３→Ｓ３０８〜Ｓ３１１）。第２のパケットメモリからシーケンシャル番号ｉ−１までのパケットを読み出すと、次のシーケンシャル番号ｉのパケットからは第１のパケットメモリから読み出しを行う（Ｓ３０３→Ｓ３０４）。また、第２のストアフラグメモリ１１０においてシーケンシャル番号ｉのパケットに対応するフラグ以外の全てのフラグが立つまでに遅延パケットカウンタ１０７の値が再度インクリメントされない場合は（Ｓ３１２→Ｓ３２３）、第１のパケットメモリ１０２からシーケンシャル番号ｉ−１までのデータを読み出し（Ｓ３２３〜Ｓ３２７）、遅延パケットメモリ１０８からパケットｉ１を読み出し（Ｓ３３３，Ｓ３３４）、遅延パケットカウンタ１０７をデクリメントし（Ｓ３３５）、遅延フラグメモリ１０５のフラグを落とし（Ｓ３３６）、第２のパケットメモリ１０９からパケットの読み出しを行う（Ｓ３０１，Ｓ３０２，Ｓ３０３→Ｓ３１１，Ｓ３０１〜Ｓ３０３）。第２のパケットメモリからシーケンシャル番号ｉ−１までのパケットを読み出すと、次のシーケンシャル番号ｉのパケットからは第１のパケットメモリから読み出しを行う（Ｓ３０３−Ｓ３０４）。
【００４１】
ただし第１の読み出しカウンタ１０４及び第２の読み出しカウンタ１１１は、その値がｎであるときにインクリメントされると値は０となる。
【００４２】
以上説明した動作により、シーケンシャル番号ｉｊのパケットが周期超遅延を起こした場合に、端末が受け取るシーケンシャル番号ｉのパケットを含むパケット列は以下の通りとなる。（ただし、ｊはシーケンシャル番号の周期を表し、ｉは周期内でのシーケンシャル番号を表すものとする。）
▲１▼…（ｉ−２）ｊ、（ｉ−１）ｊ、ｉｊ、（ｉ＋１）ｊ…
▲２▼…（ｉ−２）ｊ、（ｉ−１）ｊ、ｉ（ｊ＋１）、（ｉ＋１）ｊ…
▲３▼…（ｉ−２）（ｊ＋１）、（ｉ−１）（ｊ＋１）、ｉｊ、（ｉ＋１）（ｊ＋１）…
▲４▼…（ｉ−２）（ｊ＋１）、（ｉ−１）（ｊ＋１）、ｉ（ｊ＋１）、（ｉ＋１）（ｊ＋１）…
端末では誤り検出機能があることを仮定しているため、（▲２▼と▲３▼はデータ単位として誤ったものであること検出し廃棄することが可能セあり、正しいデータ単位を送信順に受け取ることが可能となる。
【００４３】
また、シーケンシャル番号ｉｊのパケットが廃棄されていた場合には、端末が受け取るシーケンシャル番号ｉ付近のパケット列は以下の通りとなる。
▲１▼…（（ｉ−２）ｊ、（ｉ−１）ｊ、ｉ（ｊ＋１）、（ｉ＋１）ｊ…
▲２▼…（ｉ−２）（ｊ＋１）、（ｉ−１）（ｊ＋１）、ｉ（ｊ＋１）、（ｉ＋１）（ｊ＋１）…
このうち▲１▼は誤り検出で誤りと判定され廃棄することが可能であり、少なくともシーケンシャル番号ｉｊのパケットを含むデータ単位以外は送信順に受け取ることが可能である。
【００４４】
（実施形態２）
図４は書き込み・読み出し制御部１０１において実行される書き込み制御のフローチャートである。パケット待機状態（Ｓ４０１）から、読み出し制御部１０１パケットが入力されると該パケットのヘッダ内に記述されているシーケンシャル番号（Ｓとする）を読み取り（Ｓ４０２）、周期超遅延の発生を検査し（Ｓ４０３）、周期超遅延が発生していれば遅延フラグメモリ１０５にフラグを立て（Ｓ４０４）、遅延シーケンスメモリ１０６にｉを書き込み（Ｓ４０５）、パケットメモリ書き込みアドレス生成関数をｆ（）からＦ（）に切り替え、ストアフラグメモリの書き込みアドレス生成関数をｇ（）からＧ（）に切り替える（Ｓ４０６）。入力バケットのシーケンシャル番号がｉでなければパケットメモリへの書き込みアドレスを生成し（Ｓ４０７）、ストアフラグメモリの対応フラグを立てる（Ｓ４０８）とともに、パケットメモリに該パケットが書き込まれる（Ｓ４０９）。遅延フラグメモリ１０５にフラグが立てられているときにシーケンシャル番号ｉのバケットが入力されると、該シーケンシャル番号ｉのパケットは遅延パケットメモリ１０８に書き込まれ（Ｓ４１０，Ｓ４１１）、遅延パケットカウンタ１０７の値がインクリメントされる（Ｓ４１２）。ただし初期状態では遅延パケットカウンタ１０７の値は０を示しているものとする。
【００４５】
図５は書き込み・読み出し制御部１０１において実行される読み出し制御のフローチャートである。初期状態においてカレントシステム（パケットメモリ、ストアフラグメモリ、読み出しカウンタ）は第１のシステムとなっており、第１の読み出しカウンタ１０４は１にセットされている。第１のストアフラグメモリ１０３を監視し最初のパケットであるシーケンシャル番号１のバケットに対応するフラグが立つまで待機状態となり、シーケンシャル番号１に対応するフラグが立つと（Ｓ５０２）、第１のパケットメモリ１０２からパケットを読み出し（Ｓ５０３、Ｓ５０５）、第１のストアフラグメモリ１０３のシーケンシャル番号１に対応するフラグを落とす（Ｓ５０４）。以下、遅延フラグメモリのフラグが立っていない場合、最初のパケットを読み出すときと同様に第１の読み出しカウンタ１０４の値がｊ（ｊは１以上ｎ以下の整数）であるときに、第１のストアフラグメモリ１０３のシーケンシャル番号ｊに対応するフラグが立っていれば（Ｓ５０２）第１のパケットメモリからシーケンシャル番号ｊのパケットを読み出し（Ｓ５０３、Ｓ５０５）、第１のストアフラグメモリ１０３のシーケンシャル番号ｊに対応するフラグを落とす（Ｓ５０４）。遅延フラグメモリ１０５にフラグが立っている場合、第２のストアフラグメモリ１１０のｉ（遅延シーケンスメモリに記憶されているシーケンシャル番号）以外の全てのシーケンシャル番号のパケットに対応するフラグが立っているかを監視し続け（Ｓ５０６）、ｉ以外の全てのフラグが立っていれば第１のパケットメモリからシーケンシャル番号ｉ＋１〜ｎ及び１〜ｉ−１のパケットを読み出した後（Ｓ５１７〜Ｓ５２１）、カレントシステムを第１のシステムから第２のシステムに切り替え（Ｓ５２２）、遅延フラグメモリ１０５のフラグを落とし（Ｓ５３０）、以降第２のシステムをカレントシステムとして読み出し制御を続ける。先のＳ５０６において第２のストアフラグメモリ１１０のｉ以外のフラグのいずれかが立っていない場合は、遅延パケットカウンタ１０７の値が１以上になるまで待機状態となる（Ｓ５０７）。遅延パケットカウンタ１０７の値が１になると（Ｓ５０８→Ｓ５０９）、遅延パケットメモリ１０８からシーケンシャル番号ｉのパケット（パケットｉ１とする）を読み出した（Ｓ５０９、Ｓ５１０）後、遅延パケットメモリ１０８から読み出したパケットｉ１が送信データ単位の末尾を含むパケットであれば待機状態となり（Ｓ５１１→Ｓ５０６）、該パケットｉ１が送信データ単位の末尾を含むパケットでなければシーケンシャル番号ｉ＋１から該送信データ単位の末尾を含むパケットまでを第１のパケットメモリ１０２から読み出し（Ｓ５１１→Ｓ５１２〜Ｓ５１４）、待機状態となる（Ｓ５１１→Ｓ５０６）。続いて第２のストアフラグメモリ１１０においてシーケンシャル番号ｉの／パケットに対応するフラグ以外の全てのフラグが立つ前に遅延パケットカウンタ１０７の値が再度インクリメントされると（Ｓ５０７、Ｓ５０８→Ｓｊ１５）、第１の読み出しカウンタ１０４に遅延シーケンスメモリ１０６からｉがロードされ、遅延パケットメモリ１０８から読み出されていない方のシーケンシャル番号ｉのパケット（パケットｉ２とする）を読み出した（Ｓ５１５，Ｓ５１６）後、第１のパケットメモリ１０９からシーケンシャル番号ｉ＋１〜ｎ続いてシーケンシャル番号１〜ｉ−１のバケットを読み出し、第１のストアフラグメモリの対応するフラグを落とした後（Ｓ５１７〜Ｓ５２１）、カレントシステムを第１のシステムから第２のシステムに切り替え（Ｓ５２２）、遅延パケットメモリ１０８からパケットｉ１を読み出し（Ｓ５２４，Ｓ５２５、遅延パケットカウンタ１０７をデクリメントし（Ｓ５２６）、バケットｉ１が送信データ単位の末尾を含むパケットであれば第２の読み出しカウンタ１１１に遅延シーケンスメモリ１０６からｉをロードし（Ｓ６３１→Ｓ５２３）、遅延パケットメモリ１０８からパケットｉ２を読み出し（Ｓ５２７，Ｓ５２８）、遅延パケットカウンタ１０７をデクリメントし（Ｓ５２９）、遅延フラグメモリ１０５のフラグを落とし（Ｓ５３０）、第２のシステムをカレントシステムとして読み出し制御を続ける。また、パケットｉ１が送信データ単位の末尾を含むパケットでなければ（Ｓ５３１→Ｓ５３２）、パケットｉ１の読み出し後、第２のパケットメモリ１０９から送信データ単位の末尾を含むパケットまでを読み出し（Ｓ５３２〜Ｓ５３４）、第２の読み出しカウンタ１１１に遅延シーケンスメモリ１０６からｉをロードし、遅延パケットメモリ１０８からパケットｉ２を読み出し（Ｓ５２７，Ｓ５２８）、遅延パケットカウンタ１０７をデクリメントし（Ｓ５２９）、遅延フラグメモリ１０５のフラグを落とした（Ｓ５３０）後、第２のシステムをカレントシステムとして読み出し制御を続ける。また、先のＳ５０６において第２のストアフラグメモリ１１０においてシーケンシャル番号ｉのパケットに対応するフラグ以外の全てのフラグが立つまでに遅延パケットカウンタ１０７の値が再度インクリメントされない場合は（Ｓ５０６→Ｓ５１７）、第１のパケットメモリ１０２からシーケンシャル番号ｉ−１までのデータを読み出し（Ｓ５１７〜Ｓ５２１）、遅延パケットメモリ１０８からパケットｉ１を読み出し（Ｓ５２７，Ｓ５２８）、遅延パケットカウンタ１０７をデクリメントし（Ｓ５２９）、遅延フラグメモリ１０５のフラグを落とし（Ｓ５３０）、第２のシステムをカレントシステムとして読み出し制御を続ける。後に再度遅延フラグメモリ１０５にフラグが立った場合は、以上説明してきたのと同様な動作のもとにカレントシステムが第２のシステムから第１のシステムに切り替えられる。
【図面の簡単な説明】
【図１】実施形態１の並べ替え手段の構成図。
【図２】実施形態１の書き込み制御方法のフローチャート。
【図３】（１）実施形態１の読み出し制御方法のフローチャート。
（２）実施形態１の読み出し制御方法のフローチャート。
【図４】実施形態２の書き込み制御方法のフローチャート。
【図５】（１）実施形態２の読み出し制御方法のフローチャート。
（２）実施形態の読み出し制御方法のフローチャート。
【図６】従来例のネットワークにおけるノード装置の構成図。
【図７】図６のノード装置内の分離挿入部の内部構成図。
【図８】図６のノード装置内のバッファ部の内部構成図。
【図９】従来例のノード装置のスイッチの入出力の接続関係を示す制御パターン。
【図１０】従来例のネットワークシステムの構成図。
【図１１】従来例のネットワークの通信原理を説明するための図。
【図１２】並べ替え処理を有する従来例のノード装置の構成図。
【符号の説明】
１０１  書き込み・読み出し制御部
１０２，１０９  パケットメモリ
１０３，１１０  ストアフラグメモリ
１０４，１１１  読み出しカウンタ
１０５  遅延フラグメモリ
１０６  遅延シーケンスメモリ
１０７  遅延パケットカウンタ
１０８  遅延パケットメモリ
１１２，１１３  パケットバッファ部
６００  ノード装置
６０１〜６０８  分離挿入部
６１１〜６１８  バッファ部
６２１〜６２β  伝送路
６３１〜６３８  伝送路
６４１  スイッチ
６４２  スイッチ制御部
６４３  バッファ制御部
７０１  ヘッダ検出部
７０２  ゲート
７０３  ゲート
７０４  セレクタ
７０５  ＦＩＦＯ
８０１  バッファメモリ
８０２  ヘッダ検出部
８０３  アドレスカウンタ
１００１〜１００４  ノード装置
１０１１〜１０１８  端末
１０２１〜１０２８  端末
１０３１〜１０３８  端末
１０４１〜１０４８  端末
１００５〜１００８  並列多重伝送路
１１０１〜１１０４  ノード装置
１１０５〜１１０８  スイッチ
１１０９〜１１１２  バッファ部
１１２１〜１１３６  端末
１２０１〜１２０８  並べ替え処理部
１２１１〜１２１８  ヘッダ変換部
【図１】
2004248026.tif 000003
【図２】
2004248026.tif 000004
【図３】
2004248026.tif 000005
【図４】
2004248026.tif 000006
【図５】
2004248026.tif 000007
【図６】
2004248026.tif 000008
【図７】
2004248026.tif 000009
【図８】
2004248026.tif 000010
【図９】
2004248026.tif 000011
【図１０】
2004248026.tif 000012
【図１１】
2004248026.tif 000013
【図１２】
2004248026.tif 000014