JPH09186612A - セグメント化メッセージのフレーム検査シーケンスを高速に検査する方法及び装置 - Google Patents

セグメント化メッセージのフレーム検査シーケンスを高速に検査する方法及び装置

Info

Publication number
JPH09186612A
JPH09186612A JP8234147A JP23414796A JPH09186612A JP H09186612 A JPH09186612 A JP H09186612A JP 8234147 A JP8234147 A JP 8234147A JP 23414796 A JP23414796 A JP 23414796A JP H09186612 A JPH09186612 A JP H09186612A
Authority
JP
Japan
Prior art keywords
fcs
message
packet
result
connection
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP8234147A
Other languages
English (en)
Inventor
Greces G
ジー・グレーセ
Lallement Eric
エリック・ラレマン
Toboru Guilet
ギレ・トボル
Berpranken Fabrice
ファブリス・バープランケン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH09186612A publication Critical patent/JPH09186612A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
    • H03M13/091—Parallel or block-wise CRC computation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/0078—Avoidance of errors by organising the transmitted data in a format specifically designed to deal with errors, e.g. location
    • H04L1/0083—Formatting with frames or packets; Protocol or part of protocol for error control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/5652—Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)
  • Computer And Data Communications (AREA)

Abstract

(57)【要約】 【課題】 パケット・ネットワーク上を搬送される有限
数のパケットへセグメント化されたメッセージのＦＣＳ
エラー検査コードを計算する方法及び装置を提供する。 【解決手段】 本方法は、ＡＴＭネットワークの境界に
配置されたＡＴＭネットワーク・アクセス・ノード
(２、４)のアダプタ・カードにおいて具現化される。こ
れらのノードは、ＡＡＬ５形式のＡＴＭ接続をサポート
する場合、ネットワークに入るときセグメント化された
メッセージを再生し、データ保全性検査のためそのメッ
セージ・セル・ペイロードのＦＣＳを計算する役割をも
つ。本発明のプロセスでは、接続制御ブロックフェッチ
段階(４０)と並行して実行される部分的ＦＣＳ計算(１
０)を各セルの受信時点で開始する。これら２つの並行
オペレーションによって媒体及び高速ライン上に設定さ
れた接続のセル処理時間の間にＦＣＳ検査が可能とな
る。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、高速パケット・ネ
ットワークにおいてパケット化されたメッセージのデー
タ保全性を検査するためのフレーム検査シーケンス(Ｆ
ＣＳ)によるエラー・コード計算に関する。特に、本発
明は、非同期転送モード適応層５(ＡＡＬ５)形式のセル
により搬送されたメッセージの再生を行う非同期転送モ
ード(ＡＴＭ)・ネットワーク・アクセス・ノードに対し
て適用される。
【０００２】
【従来の技術】ＡＴＭネットワークにおいては、ネット
ワークの一端から他端へと設定された接続を通してセル
が伝送される。１つの接続に対応するセルは、一連のネ
ットワーク・ノードを介して搬送される。図１のノード
１及び４は、ＡＴＭネットワークの境界に配置されてお
り、ネットワークへのユーザ・インタフェースを可能と
するアクセス・ノードである。他のノード（２及び３）
は、ＡＴＭネットワーク中間ノードである。図１には、
ユーザＡとユーザＢとの間に設定された接続が示されて
いる。ＡＴＭネットワークのアクセス・ノードは、ＦＣ
Ｓにより多くのデジタル伝送ネットワークにおいて行わ
れるデータ保全性検査を担う。ＦＣＳとは、巡回冗長検
査(ＣＲＣ)コードに基づいたデータ保全性検査コードで
ある。ＣＲＣコードは、ＣＲＣのタイプを特徴づける生
成多項式により生成される。その計算は、Henri Nussba
umerによる「Teleinformatique Ｉ」(1987, Presses in
formatiques romandes CH-1015 Lausanne)に記述されて
いる。ＣＲＣから導出されたコードであるＦＣＳは、AN
SI X3.139-1987文書２８乃至２９頁及び補遺Ｂに記述さ
れているデータ保全性検査について標準化されている。
【０００３】ＡＴＭネットワークにおいては、必要とさ
れるサービスの質に依存して様々な形式の接続を設定す
ることが可能である。幾つかのＡＴＭ標準化機構(国際
電気通信連合(ＩＴＵ−Ｔ)及び欧州電気通信標準化機構
(ＥＴＳＩ)）は、ＡＴＭネットワークを通して一般化さ
れた相互作業を可能とするために異なるＡＴＭ適応層
(ＡＡＬ)を標準化している。データの場合、このＡＡＬ
機能は、ＡＴＭネットワークへ配信されるデータのフレ
ーム(ブロック)を取上げ、それらをセルへと分割し、そ
して受信器において元のブロックに再構成できるように
必要なヘッダ情報をそれらのセルに追加する。通常、セ
ルのヘッダは、セグメント化されたメッセージを再構成
するための順序情報を含む。ＡＡＬ機能は、エラーの検
査を含む。この機能は、図１ではアクセス・ノード１及
び４において実施される。異なるＡＡＬは、異なるトラ
フィック形式に対応する。例えば、サービス・クラスＡ
の回線エミュレーションについてＡＡＬ１が用いられる
場合、ＡＡＬ３／４は、接続指向データ(クラスＣ)及び
無接続データ(クラスＤ)の双方についてのエンド・ツー
・エンド伝送を行う。ＡＡＬ５は、ＡＡＬ３／４よりも
極めて効率的に動作するように設計されている。これ
は、I.364 ITU-T標準となった。アクセス・ノードにお
けるＡＡＬ５機能の具体化は、ネットワーク・ノードに
おけるオーバヘッドに関して他のＡＡＬ機能の具体化よ
りも低コストであることを特徴とする。特に、ＦＣＳコ
ードは、既にイーサネット・プロトコルにおいて用いら
れている３２次の生成多項式により生成されたＣＲＣ−
３２コードを用いて計算され、エラー検査のために用い
られる。
【０００４】図１においては、送信元Ａから１つのＡＡ
Ｌ５接続を通して送られるメッセージは、アクセス・ノ
ード１において４８バイトからなるセグメントのシーケ
ンスへと分割される。ＡＴＭセルのペイロードを構成す
るこれらのセグメントは、順次接続を通して送られる。
ＡＡＬ５の場合、１つのメッセージの最後のセルのみ
が、そのセルのヘッダにある「メッセージ終了ビット」
等により識別される。アクセス・ノード１においてメッ
セージをセグメント化する間、そのメッセージの最後の
セグメントを構成する最後のセルには必要であれば
「０」が埋め込まれ、そのメッセージのＦＣＳが計算さ
れるとそのペイロードの最後の４バイトとして追加され
る。ネットのもう一方の末端においては、第２のユーザ
Ｂの近傍におけるネットワーク・アクセス・ノード４が
このメッセージを含むセルを受信し、受信されたセルか
らこのメッセージを再生する。図２には、メッセージに
対するオペレーションのセグメント化及びその再生を示
す。斜線領域は、データ・セルのペイロードにより搬送
される元のメッセージの各部分を表している。図２の例
においては、メッセージが４個のセルへ分割されてい
る。セルの流れの中で先頭の方の各セルは、それらのペ
イロード（２１、２２、２３）により４８バイトのメッ
セージを搬送する。最後のセルは、４４バイト以下を搬
送し、残りのバイトには「０」が埋め込まれる。最後の
セルの最後の４バイトは、メッセージのビット・ストリ
ームに関して計算されたＦＣＳである。このコードは、
３２次の標準生成多項式に基づいたＣＲＣ-３２コード
によるものである。ＦＣＳは、セグメント化を行うアク
セス・ノードにおいてＡＴＭネットワークに入るときに
計算される。再生を行うアクセス・ノードは、セルによ
り搬送されたメッセージ・セグメントから、正しい順序
でメッセージ全体を再生する。再生を行うアクセス・ノ
ードにおいては、メッセージ保全性検査のために、整列
セル・ペイロード(最後のセル・ペイロードについての
内容及びＦＣＳフィールドを含む)から構成されたビッ
ト・ストリームからなるＦＣＳを計算する必要がある。
ＦＣＳの周知の特性により、再生ノードにおいて計算さ
れたＦＣＳは、既知の定数値となるはずである。
【０００５】後述するが、再生ノードにおけるデータ保
全性検査のためのＦＣＳの計算は、ＡＡＬ５形式のセル
が到着する毎に連続的に行われることになる。ＦＣＳの
連続的計算のための従来技術による方法は、媒体及び高
速ＡＴＭライン(ＯＣ３及び前述のもの)のセル速度を十
分にサポートできるほど効率的ではない。
【０００６】ＡＡＬ５接続のＦＣＳは、ＣＲＣ-３２計
算に基づく。ビット・ストリームは、「０」又は「１」
の係数をもつ多項式として表すことができ、そしてＸの
累乗の各項は、ビット・ストリーム中の各ビットの重み
を表す。このような多項式の和は、その係数に関する論
理和(ＸＯＲ)に相当する。ＡＡＬ５形式のセルを介して
搬送されるメッセージのＦＣＳコードは、次の生成多項
式により生成されるガロア体に属する。 Ｇ(Ｘ)＝Ｘ32＋Ｘ26＋Ｘ23＋Ｘ22＋Ｘ16＋Ｘ12＋Ｘ11＋
Ｘ10＋Ｘ8＋Ｘ7 ＋Ｘ5＋Ｘ4＋Ｘ2＋Ｘ＋１
【０００７】この３２次の生成多項式は、イーサネット
におけるエラー検査のために標準化され、そしてＡＡＬ
５エラー検査のためにＡＴＭ規格により選ばれたもので
ある。
【０００８】多項式Ｐ(Ｘ)により表されるビット・スト
リームのＣＲＣコードの多項式表現は、多項式Ｐ(Ｘ)を
生成多項式Ｇ(Ｘ)で割った余りである。３２次よりも小
さい次数の余りは、有限の要素数をもつガロア体を形成
する。ガロア体の性質の１つは、根「α」すなわちその
ガロア体の既約多項式を有し、そのガロア体の各要素が
「αd」で表されることを特徴とする。ここで「ｄ」
は、「０」より大きいか又は等しくかつそのガロア体の
要素数よりも小さい１つの整数である。図７は、３２次
の生成多項式Ｇ(Ｘ)により生成されるガロア体の最初の
３５個の要素を示している。３２次の生成多項式Ｇ(Ｘ)
は、２32−１＝４，２９４，９６７，２９３個の要素を
含むガロア体を生成する。
【０００９】多項式Ｐ(Ｘ)で表されるデータ・ビット・
ストリームのＣＲＣ-３２コードをＲｅｍG(Ｐ(Ｘ))とす
ると、ＣＲＣ-３２に基づく対応するＦＣＳコードは、
次の通りである。 ＦＣＳ(Ｐ(Ｘ))＝ＲｅｍG(Ｘ32Ｐ(Ｘ)＋ＸkＬ(Ｘ)) ｋ：Ｐ(Ｘ)の次数 Ｌ(Ｘ)＝Ｘ31＋Ｘ30＋．．．＋Ｘ2＋Ｘ＋１
【００１０】メッセージのＦＣＳを計算するための標準
的回路は、線形フィードバック・シフト・レジスタ(Ｌ
ＦＳＲ)であり、この回路は、ガロア体におけるビット
乗算を実行する。メッセージの各ビットは、最上位ビッ
ト(ＭＳＢ)から先にＬＦＳＲに入力される。フィードバ
ックにより除算が行われる。プロセスが終了したとき、
ＬＦＳＲ内にＦＣＳ（除算の余り）が得られる。この回
路の方法及び形式については、例えば、「Error Checki
ng Codes」(Peterson and Weldon, the MIT Press, 2nd
edition, 1972)に記載がある。この方法は、単純では
あるが明白な欠点がある。それは、各シフトにつき１つ
のビットしか処理されないため、メッセージのビット数
と同じ数のシフトがＬＦＳＲに必要なことである。３２
ビットＣＲＣが用いられるので、３２ビット・レジスタ
が必要となる。ＣＲＣを計算するには、メッセージ内の
ビット数と同じ数のクロック・パルスだけかかる。
【００１１】ヨーロッパ特許出願公開明細書第０６１４
２９４号は、より高速のＣＲＣ計算を提示しており、１
バイト(又は複数バイト)をベースとするＦＣＳ計算を開
示している。この方法は、ＬＦＳＲによるような１ビッ
トをベースとするＦＣＳ計算よりも効率的である。この
特許出願は、ガロア体における演算の性質を利用してい
る。図４に示すように、この特許出願の好適例によれ
ば、バイト・ストリームのＦＣＳの計算は、バイト毎に
行うことができ、読み取られた各新たなバイト４２は、
前のＦＣＳ値とガロア体のα8要素との乗算結果を用い
てＸＯＲ演算処理される（４３）。乗算器４１は、ガロ
ア体におけるα8乗算を具現化したものである。このこ
とは、生成多項式Ｇ(Ｘ)をモジュロとすることを意味す
る。この方法を示す数式は、ガロア体において次のよう
に表記される。
【００１２】
【数１】
【００１３】上式で、ＦＣＳ(Ｎ)は、Ｎ個の先行するバ
イトからなるメッセージのＦＣＳであり、そしてＢ(Ｎ
＋１)は、メッセージの次のバイト（新たなバイト）の
多項式表現である。
【００１４】
【数２】 は、ガロア体における多項式の乗算記号である。これに
は２つのステップが含まれ、第１のステップでは２つの
多項式を乗算するか又は加算し、そして第２のステップ
ではＧで割った結果の余りを得る。αは、既約多項式で
あり、Ｇにより生成されたガロア体の根である。α
8は、ガロア体の９番目の要素である。
【００１５】ＦＣＳのこのバイト単位の計算は、アクセ
ス・ノードにおいて所与のＡＡＬ５形式接続機構用のＡ
ＴＭネットワークに入る時点で効率的に用いることがで
き、受信された１つのメッセージのＦＣＳを計算するこ
とができる。再生を行うアクセス・ノードにおいてメッ
セージが受信されると、全てのセルが受信された時点で
はなく新たなセルが受信される毎にこのノードにおいて
「即座に」ＦＣＳ検査が行われる。ＦＣＳ検査が適用さ
れる場合、参照した従来技術の最良の方法は、次のよう
なセル・プロセスを示唆している。メッセージの第１の
セルを受信した時点で、例えば、図４の方法に従ってＦ
ＣＳがセル・ペイロードのバイト・ストリームからバイ
ト毎に計算される。そしてその結果が接続制御ブロック
に「中間ＦＣＳ」の値として記憶される。各新たなセル
の受信時に、接続制御ブロックから「中間ＦＣＳ」の値
が読み取られ、そして、従来技術の一方法を用いて前の
「中間ＦＣＳ」の値及び受信されたセル・ペイロードか
ら新たな「中間ＦＣＳ」の値が計算される。更新された
「中間ＦＣＳ」の値は、接続制御ブロックに戻され記憶
される。最後のセルが読み取られると、前述のプロセス
による計算の結果が、ＦＣＳ検査の最終的な予想値を戻
す。
【００１６】ＡＴＭネットワークの出力においてアクセ
ス・ノードのアダプタ・カード内で実行されるＦＣＳ検
査は、高速リンクのサポートを実現するために十分効率
的でなければならない。一例として、ＯＣ３の１５５．
５２Mbpsリンクを用いた場合、各セルの到着する間の経
過時間は、２．７μsであり、ＯＣ１２リンク(６２２．
０６Mbps)に関してセルを処理するために利用できる時
間は０．７μsだけである。従来技術における改善され
た方法であるバイト毎のＦＣＳ計算を用いた場合でさ
え、各セルの処理のために上述の「中間ＦＣＳ」計算を
２．７μsの間に実行できなければならない。上記のＦ
ＣＳ検査プロセスにおいては、１つの新たな「中間ＦＣ
Ｓ」計算は、前の「中間ＦＣＳ」の値が接続制御ブロッ
クから読み取られるまでは、開始することができない。
この際、制御ブロックをフェッチする必要がある。図３
は、このフェッチ・オペレーションを示す。先ず、仮想
パス識別子(８ビット又は１２ビットのＶＰＩ)及び接続
を識別する仮想チャネル識別子(ＶＣＩ)をセル・ヘッダ
の中から読み取る。そして、識別された接続に対応する
接続制御ブロックのアドレスを見出すために、接続探索
テーブル内で分類が行われる。こうして接続制御ブロッ
クがフェッチされ、このブロック内の「中間ＦＣＳ」の
値が読み取られる。この値は、先行するセルの受信時に
ＦＣＳ計算されたものである。制御ブロックのフェッチ
及び「中間ＦＣＳ」の値の読取りは、セル処理に利用可
能時間の大きな部分を占める。「中間ＦＣＳ」の値が読
み取られると、新たな「中間ＦＣＳ」の値が計算され、
そして他のセル処理ステップは残りの時間で実行されな
ければならない。事実、処理サイクル数に関する制約
は、ＦＣＳ検査を具現化する装置（通常はノードのアダ
プタ・カード）で使用されるプロセッサの性能（タイム
・サイクル）に依存する。記憶手段等の他の必要な演算
資源もまた、具現化のために使用される設備の形式と互
換性がなければならない。
【００１７】
【発明が解決しようとする課題】以上のように、従来技
術の方法及び現在の技術によっては、ＡＴＭネットワー
ク（さらに一般的にはパケット・ネットワーク）内でＡ
ＡＬ５形式のセル（さらに一般的には固定サイズ・パケ
ット）で搬送されるメッセージのデータ保全性検査にお
いて、媒体及び高速ライン(ＯＣ３及び前述のもの)に関
して利用可能なセル(パケット)の処理時間の間に「中間
ＦＣＳ」の計算を実行することが極めて困難である。
【００１８】本発明の第１の目的は、データ・パケット
・ストリームにセグメント化されたメッセージのＦＣＳ
を計算することである。
【００１９】本発明の第２の目的は、媒体及び高速ライ
ンの速度をサポートするために、メッセージのＦＣＳ計
算を、各パケット受信の際に効率的な方法により実行さ
れる「中間ＦＣＳ」計算の各ステップへと分割すること
である。
【００２０】本発明の別の目的は、記憶装置等の他の演
算資源の使用を最小限としながらＦＣＳ計算を実行する
ことである。
【００２１】
【課題を解決するための手段】本発明の方法は、パケッ
ト再生ネットワーク・ノードにおいて、有限数のパケッ
トのペイロードへとセグメント化されたメッセージのＦ
ＣＳを、生成多項式Ｇ(Ｘ)に基づいて検査するための効
率的な方法からなる。最後のパケットがそのヘッダ内の
フィールドにより識別され、これらのパケットはＡＴＭ
ネットワーク上に設定された同じ接続に属し、その接続
は当該接続専用の制御情報（接続制御ブロック）へアク
セスするための情報を与えるパケットのヘッダ内の識別
子により識別される。この本発明による方法は、メッセ
ージの１つのパケットを受信するステップと、受信パケ
ットから読み取られたペイロードのＦＣＳを計算するス
テップとを含み、ＦＣＳを計算するステップと並行し
て、パケットのヘッダから接続を識別するステップと、
識別された接続の制御情報を読み取るステップとを実行
し、さらに並行して計算されたＦＣＳと制御情報の内容
との加算モジュロＧ(Ｘ)演算を実行するステップと、受
信パケットがメッセージの最後のパケットであるか否か
を調べるステップと、受信パケットがメッセージの最後
のパケットであれば、加算モジュロＧ(Ｘ)演算の結果を
最終結果、すなわちそのメッセージの予想されるＦＣＳ
として出力すると共に、そのモジュロＧ(Ｘ)演算の結果
の全てのビットを「１」にセットするステップと、Ｇ
(Ｘ)により生成されるガロア体の根をαとし、要素α
384の行列表現を加算モジュロＧ(Ｘ)の結果に対して行
列乗算するステップとを含む。
【００２２】本発明の装置は、上述のプロセスの各ステ
ップを実行する手段を有する。
【００２３】セルの受信時点でＦＣＳの計算を開始する
ことにより、接続制御ブロックのフェッチ段階の終了を
待つ無駄な時間を省くことができる。受信された最後の
セルがそのメッセージの最後のセルであるならば、フェ
ッチ段階の後、ＦＣＳ計算を完了するために必要なステ
ップは、２つのステップのみである。
【００２４】ＡＴＭネットワークの境界に位置するＡＴ
Ｍネットワーク・アクセス・ノードのアダプタは、ＦＣ
Ｓ計算時間を短縮することにより、ＡＴＭネットワーク
(ＯＣ３及び上記)において益々利用されつつある媒体及
び高速ラインをサポートすることができる。
【００２５】
【発明の実施の形態】本発明のプロセスが、ＡＴＭネッ
トワークにおけるＡＡＬ５形式のセルにセグメント化さ
れたメッセージのＦＣＳ検査に適用される場合、１つの
セルの受信時点でＦＣＳ計算を行うことができる。その
際に、対応する接続制御ブロックをフェッチしてそのメ
ッセージの前のセルの処理により既に記憶された「中間
ＦＣＳ」の値を読み取る段階が完了するのを待つ必要が
ない。
【００２６】本発明の一好適例は、メッセージのＦＣＳ
検査を実行するアクセス・ノードの高速ラインのアダプ
タ内に配置される。図５に示すように、新たなセルの受
信時に、そのセルのペイロードのＦＣＳである「部分Ｆ
ＣＳ」が直ちに計算される（１０）。この４８バイト・
ストリームのＦＣＳ計算は、従来技術の任意の方法によ
り行うことができる。ＬＦＳＲを用いるビット毎の方法
に比べて好適な前述のバイト毎の方法でもよい。これに
並行して、そのセルの接続が、そのセル・ヘッダのＶＰ
／ＶＣフィールドを読み取ることにより識別される。そ
の接続の制御ブロックのアドレスに対するポインタを記
憶する接続探索テーブルにおいて探索が実行される（２
０）。この探索オペレーションは、テーブル内を分類す
ることを含み、そして探索手段は、従来技術における既
知の効率的探索手段の中から選択される。接続に関する
全ての情報を有する制御ブロックがフェッチされ（３
０）、その中の「中間ＦＣＳ」の値が読み取られ、そし
て４バイトのいわゆる「ＦＣＳレジスタ」に書き込まれ
る（４０）。ＦＣＳレジスタ６０の内容は、部分ＣＲＣ
計算の結果に対して加算される（５０）。当業者であれ
ば、３２×ｎウェイＸＯＲを用いてこの加算（５０）を
具現化できるであろう。例えば、図１０に示す３２×２
ウェイＸＯＲである。２つの３２ビット・ベクトル５
１、５２の加算結果が、３２ビットのＦＣＳレジスタ６
０に記憶される。ＦＣＳレジスタ６０の各ビットは、ベ
クトル５１とベクトル５２の同じ位置にある２つのビッ
トのＸＯＲの結果である。
【００２７】次に、現在処理されているセルがそのメッ
セージの最後のセルであるか否かを調べる（７０）。Ａ
ＡＬ５形式については、最後のセルが、そのヘッダにメ
ッセージ終了ビットを有する。セグメント化されたメッ
セージの最後のセルを識別するための別の手段もある。
例えば、他のプロトコルの場合、メッセージの各セルの
ヘッダが、そのセグメント範囲情報を記憶するフィール
ドを含む。周知の検査手段を用いてステップ７０の検査
が行われる。現在処理されているセルがそのメッセージ
の最後のセルでなければ、ＦＣＳレジスタの内容にガロ
ア体におけるα384要素を掛ける。このオペレーション
は、３２ビット・ベクトル(４バイト)に対して、ガロア
体要素α384による乗算を表す３２×３２行列を掛ける
行列乗算により数学的に表現することができる。この乗
算の結果は、３２ビットベクトルとなる。本発明の好適
例においてこの計算は、３２ビット・ストリームにα
384を掛ける乗算に対応する行列を、ハードウェアによ
り具現化したものを用いる。この乗算に用いられる行列
は、図８に表されている。行列乗算の実施は、図９に示
される。例として、３２ビットの結果ベクトルのビット
７を計算するためには、３２ビットの入力ベクトルの並
んだ各ビットに対して、行列のライン７上の対応する位
置の値「０」又は「１」を掛ける。そして、これらの３
２個の結果が加算される。ハードウェアによる具現化
は、図９に示された組合せ装置である。入力ベクトルの
ビットは、行列のライン７に従って選択されており、得
られたビットは、図９における選択された範囲のもの
（０、１、３、５、７、９、１０、１１、１５、１６、
２５、２６、２７、２９）であり、各々、ライン７上の
「１」の値に対応する。これらのビットの加算は、一連
の論理ＸＯＲゲートにより具現化される。最後のＸＯＲ
ゲート９１は、３２ビットの結果ベクトルのビット７の
値を出力する。結果ベクトルの各ビットは同様に計算さ
れ、図８の行列の具現化は、図９に示したように構築さ
れた３２個の組合せ装置となる。再び、図５を参照する
と、乗算（８０）の結果は「中間ＦＣＳ」の値であり、
セル接続の制御ブロックに書き戻される（９０）。制御
ブロックは、制御ブロック読取りオペレーションのステ
ップ３０においてフェッチされたものである。
【００２８】図５の検査ステップ７０に戻って、現在処
理されているセルがそのメッセージの最後のセルであれ
ば、本発明の方法に従ってＦＣＳレジスタ６０に記憶さ
れた値は、そのメッセージのデータ保全性検査のために
計算されたＦＣＳのはずである。その後、ＦＣＳレジス
タの３２ビットを全て「１」にセットし（１００）、Ｆ
ＣＳレジスタの全ての「１」のビットにガロア体のα
384を掛ける（８０）ことにより、「中間ＦＣＳ」の初
期値が計算される。この乗算の結果は、制御ブロックに
書き戻される（９０）。次に到着するメッセージの最初
のセルを受信した時点で、この初期「中間ＦＣＳ」値を
用いて本発明の方法に従ってＦＣＳの計算が開始される
ことになる。
【００２９】このプロセスは、ｎ個の４８バイト(すな
わち３８４ビット)のセル・ペイロードを有する１つの
メッセージのＦＣＳを、ｎ−１個のペイロードのＦＣＳ
を知って計算できることを特徴とする。図６に示すよう
に、メッセージｗがｎ個のセルで搬送されると仮定し
て、ｗ１が最初からｎ−１個までのセル・ペイロードか
ら再生されたメッセージであり、ｗ２が読み取られた最
後の(ｎ番目の)セル・ペイロードであるとすれば、ｎ個
のセルを有するメッセージｗのＦＣＳは、図６に示すよ
うに、３８４ビットのシフト・ステップと、これら３８
４ビットを受信されたばかりのセル・ペイロードに対応
するｗ２ビット・ストリームにより置換するステップと
により構築される。ビット・ストリームの多項式表現を
用いると、ＦＣＳ検査を次のように数学的に表すことが
できる。
【００３０】 ｗ＝ｗ２＋Ｘ384ｗ１ ＦＣＳの線形性により、 ＦＣＳ(ｗ)＝ＦＣＳ(ｗ２)＋ＦＣＳ(Ｘ384ｗ１) ＦＣＳ(ｗ)＝ＦＣＳ(ｗ２)＋ＲｅｍG(Ｘ384ｗ１＋Ｘ384nＬ(Ｘ)) Ｌ(Ｘ)＝Ｘ31＋Ｘ30＋...＋Ｘ2＋Ｘ＋１ ＦＣＳ(ｗ)＝ＦＣＳ(ｗ２)＋ＲｅｍG(Ｘ384(ｗ１＋Ｘ384(n-1)Ｌ(Ｘ)) ＦＣＳ(ｗ)＝ＦＣＳ(ｗ２)＋α384ＲｅｍG(ｗ１＋Ｘ384(n-1)Ｌ(Ｘ)) ＦＣＳ(ｗ)＝ＦＣＳ(ｗ２)＋α384ＦＣＳ(ｗ１) 式２
【００３１】式２において、ＦＣＳの「＋」オペレーシ
ョンが、図５のオペレーション５０の３２個のＸＯＲに
対応し、そしてα384による乗算が、行列計算８０に対
応することを注記する。ＦＣＳを全て「１」に初期化す
ることは、オペレーション１００で用いられるＬ(Ｘ)の
多項式加算に対応する。受信される次のメッセージの最
初のセル・ペイロードのＦＣＳは、式２に示されるよう
にｗ＝ｗ２、ｗ１＝０、ｎ＝１である。従って、次の通
りである。
【００３２】ＦＣＳ(ｗ)＝ＦＣＳ(ｗ)＋α384Ｒｅｍ
G(０＋Ｘ0Ｌ(Ｘ)) ＦＣＳ(ｗ)＝ＦＣＳ(ｗ)＋α384ＲｅｍG(Ｌ(Ｘ)) ＦＣＳ(ｗ)＝ＦＣＳ(ｗ)＋α384Ｌ(Ｘ) α384Ｌ(Ｘ)は、初期化のオペレーションのステップ１
００の結果である。
【００３３】まとめとして、本発明に関して以下の事項
を開示する。
【００３４】（１）パケット・ネットワークのノードに
おいて、接続を識別する識別情報をヘッダに含む複数の
パケットのペイロードへセグメント化されたメッセージ
のフレーム検査シーケンス（ＦＣＳ）を生成多項式Ｇ
(Ｘ)に基づいて検査する方法であって、 前記メッセー
ジの１のパケットを受信するステップと、前記１のパケ
ットから読み取られたペイロードのＦＣＳを計算するス
テップと、前記１のパケットのヘッダから接続を識別す
るステップと、識別された接続の制御情報を読み取るス
テップと、計算された前記ＦＣＳと前記制御情報の内容
との加算モジュロＧ(Ｘ)演算を実行するステップと、前
記１のパケットが前記メッセージの最後のパケットであ
るか否かを調べるステップと、前記１のパケットが前記
メッセージの最後のパケットであれば、前記加算モジュ
ロＧ(Ｘ)演算の結果を最終結果として出力するととも
に、前記加算モジュロＧ(Ｘ)演算の結果の全てのビット
を「１」にセットするステップと、Ｇ(Ｘ)により生成さ
れるガロア体の根をαとし、要素α384の行列表現を前
記加算モジュロＧ(Ｘ)演算の結果に対して行列乗算する
ステップと、前記行列乗算の結果の値を前記制御情報の
内容として記憶するステップとを含むセグメント化メッ
セージのＦＣＳ検査方法。 （２）前記ペイロードのＦＣＳを計算するステップがビ
ット毎に実行される上記（１）に記載の方法。 （３）前記ペイロードのＦＣＳを計算するステップがバ
イト毎に実行される上記（１）に記載の方法。 （４）パケット・ネットワークのノードにおいて、接続
を識別する識別情報をヘッダに含む複数のパケットのペ
イロードへセグメント化されたメッセージのフレーム検
査シーケンス（ＦＣＳ）を生成多項式Ｇ(Ｘ)に基づいて
検査する装置であって、前記メッセージの１のパケット
を受信する手段と、前記１のパケットから読み取られた
ペイロードのＦＣＳを計算する手段と、前記１のパケッ
トのヘッダから接続を識別する手段と、識別された接続
の制御情報を読み取る手段と、計算された前記ＦＣＳと
前記制御情報の内容との加算モジュロＧ(Ｘ)演算を実行
する手段と、前記１のパケットが前記メッセージの最後
のパケットであるか否かを調べる手段と、前記１のパケ
ットが前記メッセージの最後のパケットであれば、前記
加算モジュロＧ(Ｘ)演算の結果を最終結果として出力す
るとともに、前記加算モジュロＧ(Ｘ)演算の結果の全て
のビットを「１」にセットする手段と、Ｇ(Ｘ)により生
成されるガロア体の根をαとし、要素α384の行列表現
を前記加算モジュロＧ(Ｘ)演算の結果に対して行列乗算
する手段と、前記行列乗算の結果の値を前記制御情報の
内容として記憶する手段とを有するセグメント化メッセ
ージのＦＣＳ検査装置。
【図面の簡単な説明】
【図１】ＡＴＭネットワークを示す図である。
【図２】ＡＡＬ５形式のセルを介して搬送されるメッセ
ージの再生を示す図である。
【図３】接続の制御ブロックをフェッチし、「中間ＦＣ
Ｓ」の値を読み取る段階を示す図である。
【図４】従来技術で知られたＦＣＳバイト計算の一実施
例を示す概略図である。
【図５】本発明によるＦＣＳ計算のプロセスの論理ブロ
ック図である。
【図６】新たなセルの受信時におけるそのメッセージの
中間的再生を示す図である。
【図７】３２次の生成多項式により生成されたガロア体
の最初の３５個の要素を示す図である。
【図８】ガロア体乗数α384の行列表現を示す図であ
る。
【図９】本発明で用いられたα384と３２ビット・ベク
トルとの乗算の結果により、３２ビット・ベクトルの
内、ビット７を得るためのハードウェア実施例を示す図
である。
【図１０】３２次の多項式Ｇ(Ｘ)により生成されたガロ
ア体における加算のハードウェア実施例を示す図であ
る。
【符号の説明】
２１、２２、２３、２４ セル
───────────────────────────────────────────────────── フロントページの続き (72)発明者 エリック・ラレマン フランス国06610、ラ・ゴード、シュマ ン・ド・バレストレーシュ・57、マ・キャ ブリ (72)発明者 ギレ・トボル フランス国066270、ビレヌーブ−ルーベ、 シュマン・ド・ピエール・ノワール、レ・ アスパラ (72)発明者 ファブリス・バープランケン フランス国06610、ラ・ゴード、ルート・ ド・サン−ローレン・1706

Claims (4)

    【特許請求の範囲】
  1. 【請求項１】パケット・ネットワークのノードにおい
    て、接続を識別する識別情報をヘッダに含む複数のパケ
    ットのペイロードへセグメント化されたメッセージのフ
    レーム検査シーケンス（ＦＣＳ）を生成多項式Ｇ(Ｘ)に
    基づいて検査する方法であって、 前記メッセージの１
    のパケットを受信するステップと、 前記１のパケットから読み取られたペイロードのＦＣＳ
    を計算するステップと、 前記１のパケットのヘッダから接続を識別するステップ
    と、 識別された接続の制御情報を読み取るステップと、 計算された前記ＦＣＳと前記制御情報の内容との加算モ
    ジュロＧ(Ｘ)演算を実行するステップと、 前記１のパケットが前記メッセージの最後のパケットで
    あるか否かを調べるステップと、 前記１のパケットが前記メッセージの最後のパケットで
    あれば、前記加算モジュロＧ(Ｘ)演算の結果を最終結果
    として出力するとともに、前記加算モジュロＧ(Ｘ)演算
    の結果の全てのビットを「１」にセットするステップ
    と、 Ｇ(Ｘ)により生成されるガロア体の根をαとし、要素α
    384の行列表現を前記加算モジュロＧ(Ｘ)演算の結果に
    対して行列乗算するステップと、 前記行列乗算の結果の値を前記制御情報の内容として記
    憶するステップとを含むセグメント化メッセージのＦＣ
    Ｓ検査方法。
  2. 【請求項２】前記ペイロードのＦＣＳを計算するステッ
    プがビット毎に実行される請求項１に記載の方法。
  3. 【請求項３】前記ペイロードのＦＣＳを計算するステッ
    プがバイト毎に実行される請求項１に記載の方法。
  4. 【請求項４】パケット・ネットワークのノードにおい
    て、接続を識別する識別情報をヘッダに含む複数のパケ
    ットのペイロードへセグメント化されたメッセージのフ
    レーム検査シーケンス（ＦＣＳ）を生成多項式Ｇ(Ｘ)に
    基づいて検査する装置であって、 前記メッセージの１
    のパケットを受信する手段と、 前記１のパケットから読み取られたペイロードのＦＣＳ
    を計算する手段と、 前記１のパケットのヘッダから接続を識別する手段と、 識別された接続の制御情報を読み取る手段と、 計算された前記ＦＣＳと前記制御情報の内容との加算モ
    ジュロＧ(Ｘ)演算を実行する手段と、 前記１のパケットが前記メッセージの最後のパケットで
    あるか否かを調べる手段と、 前記１のパケットが前記メッセージの最後のパケットで
    あれば、前記加算モジュロＧ(Ｘ)演算の結果を最終結果
    として出力するとともに、前記加算モジュロＧ(Ｘ)演算
    の結果の全てのビットを「１」にセットする手段と、 Ｇ(Ｘ)により生成されるガロア体の根をαとし、要素α
    384の行列表現を前記加算モジュロＧ(Ｘ)演算の結果に
    対して行列乗算する手段と、 前記行列乗算の結果の値を前記制御情報の内容として記
    憶する手段とを有するセグメント化メッセージのＦＣＳ
    検査装置。
JP8234147A 1995-12-20 1996-09-04 セグメント化メッセージのフレーム検査シーケンスを高速に検査する方法及び装置 Pending JPH09186612A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
EP95480180 1995-12-20
FR95480180.9 1995-12-20

Publications (1)

Publication Number Publication Date
JPH09186612A true JPH09186612A (ja) 1997-07-15

Family

ID=8221627

Family Applications (1)

Application Number Title Priority Date Filing Date
JP8234147A Pending JPH09186612A (ja) 1995-12-20 1996-09-04 セグメント化メッセージのフレーム検査シーケンスを高速に検査する方法及び装置

Country Status (2)

Country Link
US (1) US5912881A (ja)
JP (1) JPH09186612A (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1786109A1 (en) * 2005-11-15 2007-05-16 STMicroelectronics N.V. Block encoding and decoding method and apparatus, with controllable decoding latency

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2759227B1 (fr) * 1997-02-04 1999-04-16 Fihem Procede pour associer des donnees a des cellules atm
US6097725A (en) * 1997-10-01 2000-08-01 International Business Machines Corporation Low cost searching method and apparatus for asynchronous transfer mode systems
US6075774A (en) * 1997-11-18 2000-06-13 3Com Corporation Method and device for generating a frame check sequence
US6094685A (en) * 1998-04-14 2000-07-25 Ascend Communications, Inc. Use of control blocks to map multiple unidirectional connections
US6584124B1 (en) 1998-06-30 2003-06-24 Cisco Technology, Inc. Method and system for accessing ports of a fixed-size cell switch
DE69841981D1 (de) * 1998-09-16 2010-12-16 Ibm Verfahren und Vorrichtung zur Erzeugung und Prüfung vom Datenprüffeld
GB2360177B (en) * 2000-03-07 2003-08-06 3Com Corp Fast frame error checker for multiple byte digital data frames
US8364342B2 (en) * 2001-07-31 2013-01-29 Immersion Corporation Control wheel with haptic feedback
US7016967B2 (en) * 2001-11-08 2006-03-21 Northrop Grumman Corporation Methodology for fast file transfer protocol
US8676357B2 (en) * 2005-12-20 2014-03-18 Fieldbus Foundation System and method for implementing an extended safety instrumented system
WO2009001288A2 (en) * 2007-06-26 2008-12-31 Nokia Corporation Apparatus, method and computer program product providing distribution of segmented system information
JP2009033644A (ja) * 2007-07-30 2009-02-12 Nec Electronics Corp パケット通信装置、通信回線品質解析方法
US8064599B2 (en) * 2007-08-29 2011-11-22 Red Hat, Inc. Secure message transport using message segmentation
US9065784B2 (en) * 2012-09-11 2015-06-23 Gilat Satellite Networks Ltd. Efficient payload reassembly
KR101551831B1 (ko) * 2015-06-16 2015-09-09 충남대학교산학협력단 순환 중복 검사 장치 및 방법

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE69124743T2 (de) * 1991-11-29 1997-08-14 Ibm Vorrichtung zur Speicherung und Durchschaltung und Verfahren zur Datensicherung während der Speicherung
EP0614294A1 (en) * 1993-03-03 1994-09-07 International Business Machines Corporation Method for generating a frame check sequence
US5742765A (en) * 1996-06-19 1998-04-21 Pmc-Sierra, Inc. Combination local ATM segmentation and reassembly and physical layer device

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1786109A1 (en) * 2005-11-15 2007-05-16 STMicroelectronics N.V. Block encoding and decoding method and apparatus, with controllable decoding latency

Also Published As

Publication number Publication date
US5912881A (en) 1999-06-15

Similar Documents

Publication Publication Date Title
US5867509A (en) Communication control apparatus in ATM communication
US6014767A (en) Method and apparatus for a simple calculation of CRC-10
JPH09186612A (ja) セグメント化メッセージのフレーム検査シーケンスを高速に検査する方法及び装置
JP2837650B2 (ja) ルーティング情報の格納及び取り出しのシステム及び方法
US6209114B1 (en) Efficient hardware implementation of chien search polynomial reduction in reed-solomon decoding
EP0609595B1 (en) Method and apparatus for verifying CRC codes by combination of partial CRC codes
US6317433B1 (en) Method and system for optimizing transmission link bandwidth occupation in high speed digital networks
JP3404642B2 (ja) Ｃｒｃ−３２の２段階計算の方法および装置
US7336667B2 (en) Apparatus, method and program product to generate and use CRC in communications network
US5951707A (en) Method of partitioning CRC calculation for a low-cost ATM adapter
US5539756A (en) Method to ensure data integrity in a telecommunications network
US6097725A (en) Low cost searching method and apparatus for asynchronous transfer mode systems
US5694407A (en) Method and an apparatus for modifying a FCS
US20020129315A1 (en) Packet based ATM CRC-32 calculator
US5642347A (en) Approach to direct performing asynchronous transfer mode (ATM) adaptation layer 5 reassembly
JP3270966B2 (ja) エラー補正回路
JP4587427B2 (ja) 復号方法及びその装置とそれを用いたシステム
EP0840462B1 (en) A method and apparatus for a two-step calculation of CRC-32
Doumenis et al. Efficient implementation of the SAR sublayer and the ATM layer in high speed broadband ISDN data terminal adapters
KR970005732B1 (ko) 비동기전달모드 시스템에서의 순환잉여검사 코드 계산 및 검출장치
JPH07321809A (ja) Ａｔｍセル化装置
JPH1065713A (ja) Ａｔｍシステム用セル検出方法
Dravida Error control aspects of high speed networks
EP0923271B1 (en) An ATM reassembly circuit and method
KR100470331B1 (ko) Ａａｌ０와 ａａｌ１ ｓａｒ 계층에서 셀 송신 스케쥴링장치 및 방법