(57)【要約】【課題】パケットの輻輳状態を容易に緩和する。【解決手段】ＦＥＣを用いて符号化されたパケットの優先順位を反映して待ち行列を演算する複数の待ち行列演算部３，４を備え、分配器２において、受信部１の受信パケットについてペイロードが情報か訂正符号かを識別し、複数の待ち行列それぞれの状態を監視して、優先度の高い待ち行列の水位を判断し、その水位が基準値より高いとき、一部の訂正符号をより低い待ち行列に移動するまたは消去する。このように、待ち行列の状態を監視して、優先度の高い待ち行列の水位が高いとき、一部の訂正符号をより優先度の低い待ち行列に移動させる、または待ち行列から削除する処理を実行することで、確達性とのトレードオフにおいて輻輳状態を緩和する。【選択図】図１
2007243452.tif 000002
【特許請求の範囲】
【請求項１】
前方誤り訂正符号を用いて符号化されたパケットを伝送する通信装置において、
前記パケットの優先順位を反映して待ち行列を演算する複数の待ち行列演算手段と、
個々のパケットのペイロードが情報か訂正符号かを識別する識別手段と、
前記複数の待ち行列演算手段それぞれの状態を監視して、優先度の高い待ち行列の水位を判断し、その水位が基準値より高いとき、一部の訂正符号をより低い待ち行列に移動する訂正符号処置手段と
を具備することを特徴とする通信装置。
【請求項２】
前記訂正符号処置手段は、前記前記水位が基準値より高いとき、前記一部の訂正符号を削除することを特徴とする請求項１記載の通信装置。
【請求項３】
前方誤り訂正符号を用いて符号化されたパケットを伝送する通信方法において、
前記パケットの優先順位を反映して待ち行列を演算する複数の待ち行列ステップと、
個々のパケットのペイロードが情報か訂正符号かを識別する識別ステップと、
前記複数の待ち行列それぞれの状態を監視して、優先度の高い待ち行列の水位を判断し、その水位が基準値より高いとき、一部の訂正符号をより低い待ち行列に移動する訂正符号処置ステップと
を具備することを特徴とする通信方法。
【請求項４】
前記訂正符号処置ステップは、前記前記水位が基準値より高いとき、前記一部の訂正符号を削除することを特徴とする請求項３記載の通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＦＥＣ（前方誤り訂正符号）方式を利用した高信頼性を有する通信装置に係り、特に帯域利用の適正化に関する。
【背景技術】
【０００２】
近年の通信装置、例えば中継器、送信機及び端末間のインタフェース機器にあっては、特に高信頼性を得るため、系統的かつ短ブロックの符号化方式（例えば、ＲＳＥ）のＦＥＣが採用されつつある。ところが、ＦＥＣは、その動作原理上、常に冗長な訂正コードを生成する。このため、そのままでは複数の送信機からのパケットが合流する中継器等において、メッセージ間で占有帯域の調整を行って輻輳状態の緩和を図ることは困難であった。
【０００３】
尚、ＦＥＣの動作原理については、非特許文献１にその詳細が記載されている。
【特許文献１】A. J. McAuley, "Reliable Broadband Communication Using a Burst Erasure Correcting Code", In Proc. ACM SIGCOMM '90, pp. 297--306, Philadelphia, PA, September 1990. http://citeseer.ist.psu.edu/mcauley90reliable.html
【発明の開示】
【発明が解決しようとする課題】
【０００４】
以上述べたように、従来のＦＥＣ方式採用の通信装置では、メッセージ間で占有帯域の調整を行ってパケットの輻輳状態の緩和を図ることが困難であった。
【０００５】
本発明は、上記の問題を解決し、パケットの輻輳状態を容易に緩和することのできる通信装置及び通信方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記問題を解決するために、本発明は、前方誤り訂正符号を用いて符号化されたパケットを伝送する通信装置において、前記パケットの優先順位を反映して待ち行列を演算する複数の待ち行列演算手段と、個々のパケットのペイロードが情報か訂正符号かを識別する識別手段と、前記複数の待ち行列演算手段それぞれの状態を監視して、優先度の高い待ち行列の水位を判断し、その水位が基準値より高いとき、一部の訂正符号をより低い待ち行列に移動するまたは消去する訂正符号処置手段とを具備することを特徴とする。
【０００７】
また、前方誤り訂正符号を用いて符号化されたパケットを伝送する通信方法において、前記パケットの優先順位を反映して待ち行列を演算する複数の待ち行列ステップと、個々のパケットのペイロードが情報か訂正符号かを識別する識別ステップと、前記複数の待ち行列それぞれの状態を監視して、優先度の高い待ち行列の水位を判断し、その水位が基準値より高いとき、一部の訂正符号をより低い待ち行列に移動するまたは消去する訂正符号処置ステップとを具備することを特徴とする。
【０００８】
上記構成による通信装置では、待ち行列の状態を監視して、優先度の高い待ち行列の水位が高いとき、一部の訂正符号をより優先度の低い待ち行列に移動させる、または待ち行列から削除する処理を実行することで、確達性（データが確実に届く確率）とのトレードオフにおいて輻輳状態を緩和することが可能となる。
【発明の効果】
【０００９】
本発明によれば、パケットの輻輳状態を容易に緩和することのできる通信装置及び通信方法を提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照して本発明の一実施形態を詳細に説明する。
【００１１】
図１は本発明を適用した中継器の内部構成を示すもので、受信部１は、系統的かつ短ブロックの符号化方式（例えば、ＲＳＥ）のＦＥＣが採用された伝送信号（パケット）を受信するもので、受信したパケットは分配器２に送られる。この分配器２は、その優先度に従って、受取ったパケットを優先度高の待ち行列演算部３または優先度低の双頭待ち行列演算部４に振り分ける処理を行う。一方、選択器５は、適宜定められるスケジューリングポリシー（例えば、優先度高の待ち行列が空の場合に限り、優先度低の待ち行列からパケットを取り出してdequeue（待機解除）にセットする等）に従って、どちらかの待ち行列演算部３，４からパケットを選択的に取り出し、dequeueにセットして送信部６に渡す動作を繰り返す。送信部６は、渡されたパケットの送信を行う。
【００１２】
図２に優先度高の待ち行列の構成を示す。優先度高の待ち行列は、enqueue（挿入）入力（７）、dequeue（取り出し）及びpush（先頭挿入）（１５）の出力の標準的なオペレーションの他、キューイングされているパケットに対する特殊操作として、特定の属性を持つパケットを指定された数だけ待ち行列から削除した上で、ベクタ（９）に詰めて返す操作（makespace（１０））を持つ。また、優先度高の待ち行列は、格納されているデータの量に応じて、水位高（１１）および水位低（１２）というインディケータを持つ。
【００１３】
図３は優先度低の待ち行列の構成を示すものである。まず、優先度低の待ち行列は、いわゆる双頭待ち行列であり、enqueue入力（１３）、dequeue出力（１４）およびpush（１５）の標準的なオペレーションの他、キューイングされているパケットに対する特殊操作として、特定の属性を持つパケットを指定された数だけ、待ち行列から削除する操作（makespace（１６））を持つ。また、優先度低の待ち行列は、格納されているデータの量に応じて、水位高（１７）および水位低（１８）というインディケータを持つ。
【００１４】
図４は本発明で用いるパケット形式の一例である。ヘッダ領域先頭には、訂正シンボル（４ビット）、フラグメントＩＤ（６ビット）、フラグメント（６ビット）に続いてＴＯＩシンボルが配置され、続いて最後のブロックか否かを判別するための１ビット、優先度を表す１ビット（１９）、データであれば１，訂正コードであれば０を表す（１ビット）が配置され、さらにソースブロック番号（Source Block Number）、トータル長（バイト単位で）（Total Length (in bytes)）が続き、最後のペイロードにエンコードされたシンボル（Encoding Symbols）が格納される。このパケット形式で特徴とする点は、優先度を示すビット（以下、優先度ビット）（１９）及びデータか訂正符号かを示すビット（データ／訂正ビット）（２０）が設けられている点にある。
【００１５】
上記構成において、分配器２は、受信部１からパケットを受取ると、パケットのタイプと優先度に応じて、図５〜図１２に示すような処理を実行する。  
図５は、分配器２がパケットを受け取った場合の基本処理動作を示すフローチャートである。図５において、パケットの受領があると、まずデータ／訂正ビット（２０）から入力パケットのペイロードの内容がデータ（情報）か否かを判断し（ステップＳ１１）、データであれば優先度ビット（１９）から優先度が高か低かを判断する（ステップＳ１２）。優先度が高ならばパターン１を実行する（ステップＳ１３）。優先度が低ならばパターン２を実行する（ステップＳ１４）。
【００１６】
一方、ステップＳ１１で入力パケットのペイロードの内容がデータ（情報）でない、すなわち訂正符号であると判断された場合には、優先度ビット（１９）から優先度が高か低かを判断する（ステップＳ１５）。優先度が高ならばパターン３を実行する（ステップＳ１６）。優先度が低ならばパターン４を実行する（ステップＳ１７）。
【００１７】
図６は図５に示すパターン１の処理内容を示すフローチャートである。図６において、優先度高の待ち行列（以下、単に高行列と記す）は満杯か判断し（ステップＳ２１）、満杯ならば高行列のmakespace（詳細は後述する）を実行して返ったベクタの要素を優先度低の待ち行列（以下、単に低行列と記す）にpush（詳細は後述する）を指示する（ステップＳ２２）。ステップＳ２１で満杯でないと判断された場合には、高行列にenqueueをセットして（ステップＳ２３）、一連の処理を終了する。ステップＳ２２の処理後、再度、高行列は満杯か判断し（ステップＳ２４）、満杯ならばパターン２の処理に移行して（ステップＳ２５）、一連の処理を終了する。ステップＳ２４で満杯でないと判断された場合には、高行列にenqueueをセットして（ステップＳ２６）、一連の処理を終了する。
【００１８】
図７は図５に示すパターン２の処理内容を示すフローチャートである。図７において、低行列は満杯か判断し（ステップＳ３１）、満杯ならば低行列のmakespaceを実行する（ステップＳ３２）。ステップＳ３１で満杯でないと判断された場合には、低行列にenqueueをセットして（ステップＳ３３）、一連の処理を終了する。ステップＳ３２の処理後、再度、低行列は満杯か判断し（ステップＳ３４）、満杯ならば一連の処理を終了する。ステップＳ３４で満杯でないと判断された場合には、低行列にenqueueをセットして（ステップＳ３５）、一連の処理を終了する。
【００１９】
図８は図５に示すパターン３の処理内容を示すフローチャートである。図８において、高行列の水位（いわゆるウォーターマーク）は「高」か否かを判断し（ステップＳ４１）、「高」以外の場合には高行列にenqueueをセットして（ステップＳ４２）、一連の処理を終了する。ステップＳ４１で「高」と判断された場合には、低行列の水位は「高」か否かを判断し（ステップＳ４３）、「高」以外の場合には低行列にenqueueをセットして（ステップＳ４４）、一連の処理を終了する。ステップＳ４３で「高」と判断された場合には、低行列にmakespaceを実行して（ステップＳ４５）、再度、低行列の水位は「高」か否かを判断する（ステップＳ４６）。この判断で「高」以外の場合には低行列にenqueueをセットして（ステップＳ４７）、一連の処理を終了する。ステップＳ４６で「高」と判断された場合には、そのまま一連の処理を終了する。
【００２０】
図９は図５に示すパターン４の処理内容を示すフローチャートである。図９において、低行列の水位は「高」か否かを判断し（ステップＳ５１）、「高」以外の場合には低行列にenqueueをセットして（ステップＳ５２）、一連の処理を終了する。ステップＳ５１で「高」と判断された場合には、そのまま一連の処理を終了する。
【００２１】
図１０は、図６で使われている、優先度高の待ち行列のmakespaceのフローチャートである。図１０において、まず各要素のスコア（ｓ）を計算する（ステップＳ６１）。ここで、ｓは  
ｓ＝ｗ*(n-1)  
ｗ：タイプ別の重み  
データ：ｗ＝ｐ＞ｎ  
訂正コード：ｗ＝１  
ｉ：待ち行列内での位置  
ｎ：待ち行列の内容  
で表される。このようにしてスコア（ｓ）の計算が終了した場合には、スコアの低い順番に水位が「高」でなくなるまでベクタに移動する（ステップＳ６２）。
【００２２】
図１１は、図７および図８で使われている、優先度低の待ち行列のmakespaceのフローチャートである。図１１において、まず各要素のスコア（ｓ）を計算する（ステップＳ７１）。ここで、ｓは図１０と同様に  
ｓ＝ｗ*(n-1)  
ｗ：タイプ別の重み  
データ：ｗ＝ｐ＞ｎ  
訂正コード：ｗ＝１  
ｉ：待ち行列内での位置  
ｎ：待ち行列の内容  
で表される。このようにしてスコア（ｓ）の計算が終了した場合には、スコアの低い順番に水位が「高」でなくなるまで削除する（ステップＳ７２）。
【００２３】
図１２は、図６で用いられている優先度低の待ち行列のpushのフローチャートである。図１２において、まず低行列の水位が「高」か否かを判断し（ステップＳ８１）、「高」ならば低行列にmakespaceを実行し（ステップＳ８２）、再度、低行列の水位が「高」か否かを判断する（ステップＳ８３）。ここで低行列の水位が「高」と判断された場合には一連の処理を終了し、「高」以外と判断された場合には、低行列にpushを指示して（ステップＳ８４）、一連の処理を終了する。また、最初のステップＳ８１で「高」以外と判断された場合には、上記ステップＳ８４に移行する。
【００２４】
以上の処理手順から明らかなように、上記実施形態の構成によれば、中継器あるいは無線通信における端末・送信機間インタフェースにおいて輻輳が発生する場合でも、訂正コードパケットの優先度を低下させる、あるいは訂正コードパケットの一部を廃棄する、等の調整が可能になり、確達性とのトレードオフにおいて、中継器等におけるパケットの輻輳を緩和することができる。
【００２５】
尚、上記実施形態では中継器に本発明を適用した場合について説明したが、本発明はこれに限定されるものではなく、例えば送信機及び端末間のインタフェース機器等にも適用可能である。
【００２６】
その他、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００２７】
【図１】本発明を適用した中継器の内部構成を示すブロック図。
【図２】図１に示す優先度高の待ち行列の構成を示す概念図。
【図３】図１に示す優先度低の待ち行列の構成を示す概念図。
【図４】本発明で用いるパケット形式の一例を示す図。
【図５】図１に示す分配器がパケットを受け取った場合の基本処理動作を示すフローチャート
【図６】図５に示すパターン１の処理内容を示すフローチャート。
【図７】図５に示すパターン２の処理内容を示すフローチャート。
【図８】図５に示すパターン３の処理内容を示すフローチャート。
【図９】図５に示すパターン４の処理内容を示すフローチャート。
【図１０】図６で使われている、優先度高の待ち行列のmakespaceのフローチャート。
【図１１】図７および図８で使われている、優先度低の待ち行列のmakespaceのフローチャート。
【図１２】図６で用いられている優先度低の待ち行列のpushのフローチャート。
【符号の説明】
【００２８】
１…受信部、２…分配器、３…優先度高の待ち行列演算部、４…優先度低の双頭待ち行列演算部、５…選択器、６…送信部、７…enqueue入力、８…dequeue出力、９…ベクタ、１０…makespace、１１…水位高、１２…水位低、）１３…enqueue入力、１４…dequeue出力、１５…push、１６…makespace、１７…水位高マーク、１８…水位低マーク。
【図１】
2007243452.tif 000003
【図２】
2007243452.tif 000004
【図３】
2007243452.tif 000005
【図４】
2007243452.tif 000006
【図５】
2007243452.tif 000007
【図６】
2007243452.tif 000008
【図７】
2007243452.tif 000009
【図８】
2007243452.tif 000010
【図９】
2007243452.tif 000011
【図１０】
2007243452.tif 000012
【図１１】
2007243452.tif 000013
【図１２】
2007243452.tif 000014