(57)【要約】【課題】  受信されたパケットデータを行き先別に発信しやすい形式に整形処理する際のデータ欠損の発生を効果的に防止可能な構成を提供することを目的とする。【解決手段】  大容量メモリ１３に格納された入力データを読み出してこれを行き先別に分類し、各分類毎に順次バッファ１６の各面に書き込む際、読み出したデータの行き先が異なった場合には次の面に書き込む構成を有する。【選択図】  図５
2005175938.tif 000002
【特許請求の範囲】
【請求項１】
入力データを格納する第１の格納手段と、
第１の格納手段に格納された入力データを読み出してこれを所定の法則に従って分類し、各分類毎に順次所定の記憶単位に書き込む第２の格納手段とよりなり、
前記第１の格納手段は第２の格納手段より大きな記憶容量を有する構成とされてなるデータ処理装置。
【請求項２】
第２の格納手段の記憶容量が不足すると判断された際に前記第１の格納手段からの読み出しを停止し、当該不足状態が解消した後、前記停止前に第２の格納手段に最後に書き込まれたデータが第１の格納手段から読み出された読み出し位置に遡って第１の格納手段からの読出しを再開する構成とされてなる請求項１に記載のデータ処理装置。
【請求項３】
第２の格納手段にデータを書き込む際には、その複数の記憶単位に対して所定の順序で書き込む構成とされ、前記第２の格納手段の記憶容量の不足の判断は、第１の格納手段から読み出されたデータを書き込んでいる記憶単位の番号と、このようにして書き込まれたデータが所定の処理のために読み出される記憶単位の番号との差の大小によって行なうものとされてなる請求項１又は２に記載のデータ処理装置。
【請求項４】
入力データを第１の格納手段に格納する段階と、
第１の格納手段に格納された入力データを読み出してこれを所定の法則に従って分類し、各分類毎に順次第２の格納手段の所定の記憶単位に書き込む段階とよりなり、
前記第１の格納手段は第２の格納手段より大きな記憶容量を有する構成とされてなるデータ処理方法。
【請求項５】
更に第２の格納手段の記憶容量が不足すると判断された際に前記第１の格納手段からの読み出しを停止し、当該不足状態が解消した後、前記停止前に第２の格納手段に最後に書き込まれたデータが第１の格納手段から読み出された読み出し位置に遡って第１の格納手段からの読出しを再開する各段階よりなる請求項４に記載のデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
データ処理装置及びデータ処理方法に係り、特に入力データを所定の法則に従って分類し、その分類結果に基づいて当該データを整形した後に出力するデータ処理装置及びデータ処理方法に関する。
【背景技術】
【０００２】
例えばＴＣＰ／ＩＰなどに用いられる可変長のパケットデータを扱う技術分野では、各パケットデータをその行き先毎に分類し、当該行き先毎に発信するのに適した形式に加工する所謂整形処理を施すことが行なわれる。即ち、例えば図１に示すように、高速シリアル形式（例えば図２（ａ）に示される状態）で到着したパケットデータを複数の送信先毎にスイッチ１２０で振り分ける処理が行なわれる。このような処理は、通常受信された高速シリアル状態のデータを一旦低速のパラレルデータに変換してから行なわれる。この場合、パケットデータは可変長であるため、パラレル化部１１０においては単純なシリアル／パラレル変換だけではなく、図２（ｂ）に示される如く、シリアル／パラレル変換で得られたパラレルデータをそのままクロック毎に行き先別に切り分けができるような形式に変換する処理、所謂整形処理を施す。
【０００３】
この整形処理とは、データを送り出すクロック毎に同一の行き先のデータを纏める処理である。即ち、図２（ｂ）の状態を見ると、同じ時刻では必ず同一行き先のデータのみが存在する構成とされている。尚、図２において、大文字の各アルファベットＡ、Ｂ，Ｃ、Ｄ等は夫々行き先を示し、小文字の各アルファベットａ，ｂ，ｃ，ｄ等は夫々行き先Ａ，Ｂ，Ｃ，Ｄに対して送出すべきデータを示す。また、図２（ｂ）の上部の各下向きの矢印は夫々基準クロックによって画定される各データ処理サイクルを示している。
【０００４】
この場合、例えば図３に示すように、シリアル／パラレル変換部１１１でのデータ変換後、一旦ＲＡＭ等のメモリ１１４に蓄積してから整形処理を行うことが行なわれる。このメモリ１１４の前後には書き込み処理部１１２と読み出し処理部１１５とが設けられる。この構成において、上記整形処理は、メモリ１１４に対する書き込み処理部１１２にて行われる。
【０００５】
この場合、例えば図４（ｂ）の２サイクル目のように、1サイクル中に存在するパケットの行き先が１つであれば、図４（ｃ）に示す如く、メモリ１１４の１領域（記憶単位）にそのまま格納する。即ちこの場合、図４（ｂ）に示すパラレル化されたデータの２サイクル目には行き先Ａを有するデータａのみが含まれるため、これをメモリ１１４の２番目の記憶領域に格納する。他方図４（ｂ）に示す３サイクル目のように、１サイクル中に存在するパケットの行き先が２つに分かれるようであれば、図４（ｃ）に示す如くメモリの２領域に分割して格納する。即ちこの場合、図４（ｂ）に示すパラレル化されたデータの３サイクル目には行き先Ａを有するデータａと行き先Ｂを有するデータｂとが混在しているため、これを分割してメモリ１１４の３番目と４番目の記憶領域に夫々格納する。
【０００６】
このよう分割格納することで、メモリ１１４の読み出し側１１５ではメモリに格納されたデータをシーケンシャルに読み出すだけでよいため、非常に単純な構成を採ることができる。尚、上記の如くの現象、即ち同一サイクル内に行き先が異なるデータが混在するような現象が生ずる原因は、パケットデータが可変長であることによる。即ち、図２（ａ）、図４（ａ）に示す如く、各データパケット、即ち行き先Ａを有するデータａ，行き先Ｂを有するデータｂ，行き先Ｃを有するデータｃ等、各パケット毎に任意のパケット長を有する。このため、これを単純にパラレル化した場合、上記整形処理を行わないと図４（ｂ）に示すごとく、処理サイクルによっては同一サイクル内に異なる行き先を有するデータが混在する状態が起こり得る。
【特許文献１】特開２００３−１７４４７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
例えば図４に示す例における行き先Ｃ，Ｄ，Ｅを有するデータｃ，ｄ，ｅの如く短いパケットが連続して到着した場合、これに対処するために図４（ｃ）に示す如く書き込みの分割格納処理が頻発することになる。その結果書き込み処理が余分な時間を要することとなり、メモリ１１４への書き込み処理が実データの到着時間よりも長引く事象が起こりえる。即ち、図４に示した例では、結果的に１０サイクルにて到着したパケットデータを格納するのに１２サイクルを要している。
【０００８】
通常、このような事態を避ける為、書き込み側では図３に示す如く、書き込みきれなかった余りデータを保持するためのある程度の容量を持ったバッファ１１３を設けることを行う。しかしながらこのようにバッファ１１３を設けた場合であっても、短いパケットが連続して到着した場合、このバッファ１１３が短期間で溢れる可能性がある。このような事態を完全に避けるためには理論上このバッファ１１３の格納容量を無限大にする必要があるがそれは不可能であるため、有限の格納容量を有するバッファ１１３を設けた場合、結果的に短パケットの連続到着時には対処しきれずにパケットロスを引き起こす可能性が残ることになる。
【課題を解決するための手段】
【０００９】
本発明では上記問題の解決のため、入力データを格納する第１の格納手段と、第１の格納手段に格納された入力データを読み出してこれを所定の法則に従って分類し、各分類毎に順次所定の記憶単位に書き込む第２の格納手段とを設け、前記第１の格納手段は第２の格納手段より大きな記憶容量を有する構成とした。
【発明の効果】
【００１０】
このように本発明では最初に入力データを格納する第１の格納手段の容量を、整形処理部との間に設ける第２の格納手段より大きくした。その結果入力データは一旦比較的大容量の第１の格納手段に格納されることになる。したがってデータ受信の段階でパケットロスが起こる可能性を効果的に低減可能である。
【００１１】
また、第１の格納手段に格納されたデータを順次読み出して所定の分類毎に第２の格納手段の異なる記憶単位に書き込むため、その後の整形処理の効率化が図れる。その結果、一旦第１の格納手段に格納されたデータを第２の格納手段を介して整形する段階で上記の如く短いパケットの頻発等により処理の遅延が発生したとしても、それによるパケットロス発生の可能性を効果的に低減可能となる。
【００１２】
更にまた、度重なる短いパケットの頻発等によってデータ入力に整形処理が追いつかなくなり第２の格納手段のオーバーフローが発生しそうな場合には一旦第１の格納手段からの読み出しを中断し、その間の整形処理の進行に伴い第２の格納手段の記憶容量に余裕が出来た段階で、最後に第２の格納手段に書き込まれたデータが第１の格納手段から読み出された際の読み出し位置に遡って第１の格納手段からの読み出しを再開するようにすることが可能である。その結果更に効果的にパケットロスの発生を防止可能である。
【００１３】
尚、この場合においても前記の如く第１の格納手段の記憶容量が比較的大きいため第１の格納手段がバッファの機能を果たし得る。即ち、上記の如く第１の格納手段からの読み出しを中断するとその間第１の格納手段に新たな空き容量を発生させることが出来ない。そのため第１の格納手段は入力データの書き込みによってその空き容量が一方的に消費され、結果的にその空き容量は次第に減少してゆくこととなる。しかしながら予め第１の格納手段の容量を大きく設定しておくことにより、そのように一方的に空き容量が消費される事態が発生しても、最終的に第１の格納手段の容量の枯渇が生ずるまでの時間を効果的に確保可能となる。
【発明を実施するための最良の形態】
【００１４】
本発明の実施の形態によれば、パケットデータを一旦バッファに格納し、それを行き先別に整形して出力する機能を有するパケットデータ交換装置において、バッファとして１段目に大容量のメモリを設け、２段目にフリップフロップなどで構成された小容量のバッファを設けた２段構成にすることで、パケットロスの発生を効果的に防止可能とする。
【００１５】
尚、「パケットロス」という用語の意味は以下の通りである。即ち、例えば図３の構成において、シリアル／パラレル変換部１１１でパラレル化された受信パケットデータを書き込み部１１２にて大規模メモリ１１４に書き込む際、その時点で整形処理の遅れ等により読出し部１１５によるメモリ１１４からの読み出し速度が追いつかない場合を想定する。そのような場合メモリ１１４の次第に空き容量が不足してゆき、その結果書き込むことが出来なくなった受信データパケットは一旦バッファ１１３に格納される。しかしながら上記の如くのメモリ１１４の空き容量不足の状態が解消せずに長引いた場合、メモリ１１４に書き込むことが出来なかった受信パケットデータを一時的に格納するバッファ１１３自体の空き容量が不足する事態が発生し得る。そのような場合には、例えば既にメモリ１１４とバッファ１１３とに格納されたデータを保護するためには、新たに受信されたパケットデータを書き込み部１１２にて破棄する必要が生じ得る。このような原因で生じる、受信パケットデータが破棄される現象をパケットロスと称する。
【００１６】
尚、上記説明は一例であり、これ以外にもパケットデータの受信速度と、その後の処理速度との間の不整合に起因して中間に設けられたバッファメモリに空き容量不足が生じ、それにより一部のデータを破棄せざるを得ない状態は様々に想定され得る。それらの事態にてパケットデータが破棄される現象を総じてパケットロスと称することが出来る。
【００１７】
本発明の実施の形態では、上記パケット整形機能を有するパケットデータ交換装置において、予め１段目メモリの過去の読み出し位置を記憶しておき、２段目のバッファがオーバーフローしそうな時に応じてその読み出しを停止した後、この読み出し位置に遡って読み出しを再開することで、パケットロスの発生を未然に防止する。
【実施例１】
【００１８】
以下、図面と共に本発明の一実施例について説明する。
【００１９】
図５は本発明の一実施例によるデータ処理装置のブロック図である。図５に示す装置構成は、例えば上述の、高速シリアル状態の受信パケットをパラレル化し（１１０）、その行き先別に整形し（１２０）、更に各行き先毎にシリアル化して発信する（１３０）機能を有するパケットデータ交換装置において、シリアル形式で受信されたパケットデータをパラレル化する手段１１０として適用され得る。
【００２０】
図５に示すデータ処理装置はシリアル／パラレル変換部１１、大規模メモリ（ＲＡＭ）１３、同メモリ１３に対してパラレル化されたパケットデータを書き込む書き込み部１２、同メモリ１３からパケットデータを読み出す読出し部１５、メモリ１３から読出し部１５にてデータを読み出す際の、メモリ１３における読み出しアドレスを保持記憶する読み出しアドレス保持部１４とを有する。
【００２１】
また、図５に示すデータ処理装置は、更に、読出し部１５によりメモリ１３から読み出されたパケットデータを、その行き先別に格納するための複数面の記憶領域を有する小バッファ１６を有する。この各小バッファ１６は、書く記憶領域を担う面を各々独立した記憶装置で構成しても良いし、一つの記憶装置を分割管理する手段を用いてその複数の記憶領域を見かけ上複数の独立した記憶装置、即ち格納面として利用する構成として実現してもよい。
【００２２】
図５に示すデータ処理装置は更に、各小バッファ１６の格納面からデータを読み出して上記の如く、各々の行き先毎に順次送出し易くするための整形処理を施す読み出し整形部１７を有する。
【００２３】
図６は上記シリアル／パラレル変換部１１にてパラレル化されたパケットデータを書き込み部１２にてメモリ１３に書き込む様子を説明するための図である。尚、図６（ａ）に示すデータは上述の図４（ｂ）に示すデータと同様なものである。即ちこの場合、メモリ１３に対する書き込み時には、特に図４（ｃ）と共に説明した如くの行き先別の分割格納は行なわず、パラレル化された１０サイクル分のデータをそのまま１０ワード分の記憶領域に書き込む。したがってメモリ１３に書き込まれた状態では、例えば第３、第５、第６の各ワードでは、一ワード中に行き先の異なるデータが混在した状態となっている。
【００２４】
このようにしてメモリ１３に書き込むことにより、実質的に書き込み時の処理速度の遅延は発生せず、また図４（ｃ）の場合と異なり、メモリ１３の記憶容量を最大限に利用可能となる。したがってメモリ１３をバッファとして見た場合、その機能を効果的に活かすことが可能となる。
【００２５】
このように本発明の実施例ではパケットデータの整形処理（１７）をメモリ１３の書き込み側ではなく読み出し側で行い、更にパケット整形を行うために小規模のフリップフロップで形成されたバッファ１６を設けている。またメモリ１３にはパラレル変換後のデータをそのまま書き込み、そのままの形で読み出し（１５）を行う。この場合、読み出し側に備えられた小規模バッファ１６を構成する各格納面は、各々最大でメモリ１３から１回（１サイクル）で読み出したデータを格納できるだけの容量を持つ。
【００２６】
ここで、図７と共に後述する如く、メモリ１３の読み出し側においてメモリ１３から各ワード毎に読み出したデータが全て同一パケットに属する、即ち同一の行き先を有するものであれば、複数の格納面あるうちの１つのバッファ１６の面に全て格納する。他方、ワード毎に読み出したデータが複数パケットに跨るもの、即ち複数の異なる行き先を有するものであれば、これらを各々複数のバッファ１６の格納面に分割して格納する処理を行う。そして読み出し整形部１７では、このバッファ１６に格納されたデータの情報を判断した上で複数のバッファ１６の面に格納されたパケットデータを組み合わせる等の処理を施してパケットデータを整形した上で下流側に送信する。
【００２７】
尚、この場合、読み出し整形部１７によるこのような整形処理に比べ、上記の如くメモリ１３から読み出したデータを適宜分割して各バッファ１６に格納する処理の方が速い事態（処理速度の不整合）が発生し得る。その場合、小規模バッファ１６が枯渇する可能性があり、最悪の場合、その時点でメモリ１３から既に読み出してしまったデータをバッファ１６に書き込むことが出来ず、結果的にデータが消滅することが考えられる。本発明の実施例ではこのような事態に対処するため、読み出しメモリアドレス保持部１４にて、メモリ１３の読み出し位置を記憶しておく。そして、図８と共に後述するように、バッファ１６のオーバフローの恐れがある際には一旦メモリ１３からの読み出しを停止し、その間の整形処理の進行に伴ってバッファ１６の空き容量、即ち空きバッファ（１６）面の数量が所定数量となった後、バッファ１６に最後に書き込まれたデータがメモリ１３から読み出されたアドレスに遡り、その位置から読み出しを開始する。その結果、仮にバッファ１６がオーバフローして既に読み出し済みのデータが消滅した場合であっても、それらが上記読み出しアドレスの遡及によって再度読み出されるため、パケットロスは確実に防止され得る。
【００２８】
図７と共に、図５に示す本発明の一実施例によるデータ処理装置における、読み出し部１５と、小規模のバッファ１６を用いたパケット整形方法について説明する。メモリ１３には、図７の左上に示す通り、４並列のパラレルデータが６サイクル分格納されていたと仮定する。尚、データの先頭文字として“Ｃ”と記しているものはパケットのヘッダ情報(コントロールワード)を示し、“Ｄ”と記しているものはパケットのペイロード情報(データワード)を示す。そしてそれらに添えられた数字が共通のものは、同一パケットのデータであることを示している。また、同図では左端から順により古い格納データを示す。
【００２９】
まずメモリ１３の読み出し部１５でヘッダ１ワードＣ１とペイロード３ワードＤ１とを読み出す（ステップＳ１）。このデータの行き先（添え数字：１）は1つであり、分割不可能であるため、０番目のバッファ１６の格納面（Ｂ０）へこれをそのまま保持する（ステップＳ２）。その後バッファ１６の読み出し側、つまり読み出し整形部１７では、このようにしてバッファ１６にデータが格納されたことを認識する。但しデータの出力形式として、パケットの末尾でない限りヘッダ１ワードに加えてペイロードを４ワード単位で出力するものとした場合、読み出し整形部１７では、この時点では上記条件に満たないためバッファ１６からのデータ出力を行わない。
【００３０】
次に読み出し部１５でペイロード４ワードＤ１を読み出す（ステップＳ３）。この場合も同じく行き先（添え数字：１）は1つで分割不可能であるため、１番目のバッファ１６の面（Ｂ１）へこれをそのまま保持する（ステップＳ４）。この時読み出し整形部１７ではバッファＢ０（０番目格納面）とバッファＢ１（１番目格納面）のデータを組み合わせることでペイロードとして合計４ワードを取得し、これを上記一単位として出力が可能となると判定し、このようにデータを組み合わせて後段に出力する（ステップＳ５）。
【００３１】
更にメモリ１３からデータを読み出した結果（ステップＳ６）、前回読み出したパケットと同一パケットのデータが１ワードＤ１と、新たなパケットのヘッダ1ワードＣ２とペイロード２ワードＤ２とが読み出されたこととなる。但しこのデータ群は添え数字が１と２との別々のパケットに属するため、パケットの続きの1ワードはバッファの２番面（Ｂ２）へ、新たなパケットのヘッダ＋ペイロードの合計３ワードはバッファの３番面（Ｂ３）へ夫々格納される（ステップＳ７）。
【００３２】
同様に整形部１７ではバッファ1番面（Ｂ１）と２番面（Ｂ２）のデータを組み合わせると、パケット末尾までデータを出力することができると判断し、このようにして組み合わせたデータを後段に出力する（ステップＳ８）。以下、このような流れでメモリ１３からのデータ読み出し、バッファ１６への分割格納を行い、更にバッファ１６からの読み出しと整形を行なう。この処理はメモリ１３内にデータが存在する限り続けられる（ステップＳ９乃至Ｓ１９）。
【００３３】
一方、この整形処理では、図７の例に示す通り、メモリ１３からの読み出しが６サイクルであるのに対し、整形および出力処理に７サイクル以上の処理過程を要するような現象が有り得る。従って、このような現象が続いた場合、複数面持っている小規模バッファ１６が枯渇する可能性がある。その場合、パケットデータの欠落等の状況を招くことになってしまう。
【００３４】
これを防ぐため、メモリ１３から読み出したデータを分割保持しようとするバッファ１６の面番号（即ちバッファの番号Ｂ０，Ｂ１、Ｂ２，Ｂ３，．．．）と、その時点で整形対象として参照されているバッファ面番号とを比較照合し、その差の値が所定値より小さい場合に小規模バッファの空き面数が枯渇しつつあると判定する構成とする。
【００３５】
しかしながらこのような構成によりバッファ１６の枯渇を検出した際にメモリ１３からの読み出しを中断した場合であっても、メモリ１３に用いるＲＡＭの特性上、当該枯渇が検出された時点で既に数サイクル分のデータをメモリ１３から読み出してしまっていると考えられる。その場合、それらのデータは上記枯渇によりバッファ１６に書き込めず、消滅することとなる。これを防止するために、このように枯渇検出時点で未だバッファ１６に書き込まれていない分のデータを収容できるだけの余裕を持たせてバッファ１６の面数を用意しておくことも可能である。しかしながら、それでは徒に回路規模を増大させることになる。
【００３６】
そこで、常時、バッファ１６に分割格納したデータを読み出した時のメモリ１３の読み出しポインタの位置をアドレス保持部１４にて保持しておく。そして、バッファ１６の枯渇が予測された時にはその時点で既に読み出されたが未だバッファ１６に格納されていないデータを一旦廃棄する。そして、その後整形処理の進行に伴って当該枯渇が解消された時にはメモリ１３の読み出しポインタを前記保持した位置に戻し、そこから読み出しを再開する構成とする。
【００３７】
このような構成につき、具体的な動作例と共に図８のタイムチャートを参照して以下に説明する。
【００３８】
図８（ａ）はメモリ１３の現在読み出しているアドレスの変化を示し、（ｂ）はメモリ読み出しイネーブル信号波形を示し、（ｃ）はメモリ１３から読み出されたデータを示し、（ｄ）は同じくメモリ１３から読み出されたデータを示す値を１サイクル分シフトしたものを示し、（ｅ）はバッファ１６に既に書き込まれたデータがメモリ１３から読み出された際のメモリ１３内のアドレスを示し、（ｆ）はメモリ１３から読み出されたデータが書き込まれているバッファ１６の面番号を示し、（ｇ）は読み出し整形部１７がデータを読み出して整形するために参照しているバッファ１６の面番号を示す。また、図８（ｈ）はバッファ１６の各面にデータが格納される様子を示す。
【００３９】
図示の如く、メモリ１３のアドレス“Ｂ“により時刻ｔ０で読み出し開始されたデータ“ｂ”につき、２サイクル後の時刻ｔ１にてバッファ１６に対する分割対象データとして読み出しが完了し、バッファ９とバッファ１０とに亘って書き込まれる（図８（ｈ））。その結果、次のデータ格納先となるバッファ１６の面番号が“１１”に変化している（図８（ｆ））。なお、ここでは一例としてバッファ１６の総面数は１６としている。
【００４０】
この時、整形対象として参照されているバッファ１６の面番号が“０”であり（図８（ｇ））、空き面数が少ないと判断される。即ち、この場合総バッファ面数１６（０乃至１５）のうち、書き込み面が「１１」であり、読み出し面が「０」（リングバッファと考えれば「１６」と等価）であるため、その差は１６−１１＝５である。そしてこの場合、一例として上記差の値が５以下となった場合にバッファ空き面数が不足と判定するものとする。その結果、この場合差が５となったため、バッファ空き面数不足と判定する。その結果メモリ読み出しイネーブル信号（図８（ｂ））は無効化され、メモリ１３からのデータ読み出しは停止される。
【００４１】
しかしながらこの時点（時刻ｔ１）ではメモリ１３のアドレス“Ｃ，Ｄ，Ｅ”からの読み出し動作は完了している（図８（ａ））。またこれにより読み出されたデータ“ｃ，ｄ，ｅ”（図８（ｃ））はバッファ１６には収容しきれないことが予想される。そこでこのデータ“ｃ，ｄ，ｅ”を一旦廃棄する一方、最後の有効読み出しアドレスである“Ｂ”をアドレス保持部１４にて保持しておく（図８（ｅ））。即ちここではバッファ１６に最後に書き込まれたデータ“ｂ”がメモリ１３から読み出されたアドレス“Ｂ”を上記最後の有効アドレスと判断する。
【００４２】
そして、時刻ｔ２にてバッファ１６の上記バッファ空き面数不足検出が解消した後、上記最後の有効アドレスとして保持されていた“Ｂ”をインクリメントして得られた次アドレス“Ｃ”から読み出しを再開する。その結果バッファ１６の空き容量不足によるデータの欠落を防止することが可能である。
【００４３】
尚、上記バッファ空き面数不足解消の検出は以下の如くに実施される。即ち、時刻ｔ２にてバッファ１６の参照面（図８（ｇ））が０から２（上記と同様の論理にて１７と等価）にインクリメントされており、バッファ１６の格納面１１との差が６に増加している。これは上記閾値である５を超えているため、バッファ空き面数不足は解消と判定できる。
【００４４】
上記空き面数不足解消判定の結果、時刻ｔ３にて読み出しイネーブル信号（図８（ｂ））は有効化され、上記の如くメモリ１３からの読み出しが再開される。その結果メモリ１３のアドレス“Ｃ，Ｄ，Ｅ”から再びデータ“ｃ，ｄ，ｅ”が読み出され（図８（ｃ）），これらが順次時刻ｔ４，ｔ５等にてバッファ１１，１２，１３等に格納される。
【００４５】
このように、バッファ１６の空き容量不足の検出によりメモリ１３からのデータ読み出しを停止すると共に、その段階でバッファ１６に最後に格納されたデータがメモリ１３から読み出された読み出し位置を保持しておき、当該バッファ空き容量不足解消時にはメモリ１３の上記保持された読み出し位置から読み出しを再開する。その結果、バッファ１６の空き容量不足の際にも確実にデータの欠損を防止可能である。
【００４６】
以下図９乃至図１１と共に、図７と共に説明したバッファ１６に対する書き込み、読み出し動作の流れ、及び図８と共に説明したメモリ１３からの読み出し動作の流れについて説明する。
【００４７】
図９は、バッファ１６に対する書き込み動作の流れを示す。同図中、ステップＳ２１にて書き込みポインタＮの値を０に初期化し、ステップＳ２２にて、メモリ１３に読み出すべきデータが存在するか否かを判断する。読み出すべきデータがあればステップＳ２３にてバッファ１６に空き容量が存在するか否かを判定する。その結果空き容量が無ければメモリ１３から読み出されたデータは廃棄される（ステップＳ２４）。但し、図８と共に上述の如くバッファ１６の空き容量不足の判定がなされると、その際最後にバッファ１６に書き込まれたデータがメモリ１３から読み出された読み出し位置が保持され、その後に当該空き容量不足状態解消時に再度上記読み出し位置に遡って読み出しが再開される。このため、上記ステップＳ２４にて廃棄されたデータも再び読み出されてバッファ１６に書き込まれる。その結果実際のデータ欠損は発生しない。
【００４８】
次にステップＳ２５にて、メモリ１３から読み出された１サイクル分のデータのセグメント数が判定される。これは、具体的には当該データが有する行き先が一箇所か２箇所かを判定する。その結果セグメント数が１、即ち行き先が一箇所であればステップＳ２６にて、当該データ全てをバッファ１６の一面（番号Ｎ）に書き込む。そして書き込みポインタＮをインクリメントする（ステップＳ２７）。他方、ステップＳ２５の判定が「２セグメント」或いは「行き先を２箇所有する」であった場合、ステップＳ２８にて当該データを各セグメントごと、或いは行き先別に二つの面（番号：Ｎ，Ｎ＋１）に書き込む。その結果、書き込みポインタはこの場合「２」インクリメントされる（ステップＳ２９）。その後ステップＳ２２に戻り、上記動作を繰り返す。
【００４９】
次にこのようにしてバッファ１６に書き込まれたデータが読み出される動作につき、図１０と共に説明する。
【００５０】
ステップＳ３１にて読み出しポインタＮが０にインクリメントされ、ステップＳ３２にてバッファ１６のＮ面に読み出すべきデータがあるか否かが判定される。その結果読み出すべきデータが存在すればステップＳ３３にて、当該バッファ１６のＮ面に保持されたデータがセグメントの最後のデータか否かを判定する。即ち、当該データの行き先と次にバッファの面に保持されたデータの行き先とを見比べ、異なれば当該Ｎ面のデータがセグメントの最後のデータであると判定できる。判定の結果がＹｅｓの場合、そのままデータを読み出して整形部１７に送出し（ステップＳ３５）、読み出しポインタＮをインクリメントする（ステップＳ３６）。
【００５１】
他方、ステップＳ３３の判定結果がＮｏの場合、ステップＳ３４にて、当該データの量が一定量以上か否かを判定する。その結果一定量に満たない場合、そのまま出力することはせずにステップＳ３７に進む。即ち、図７の例では上記の如くパケットの末尾でない限りヘッダに加えてペイロード４ワードを一単位として出力する設定となっているため、図７のステップＳ２にてバッファＢ０に書き込まれた分はペイロードが３ワードでこの条件に満たない。そのため、出力されないのである。
【００５２】
ステップＳ３７では当該バッファ１６のＮ面の保持データと次のＮ＋１面の保持データとを加えて一定量のデータとなるか否かを判定する。その結果がＹｅｓの場合、ステップＳ３９にてＮ＋１面のデータを加えて上記一定量として出力する（ステップＳ３９）。即ち、図７の例ではステップＳ５にてＢ０面のデータにＢ１面のデータを一部加えて上記規定のデータ量（ペイロード：４ワード）として出力する。
【００５３】
次にステップＳ４０にて、バッファのＮ＋１面に未出力データがあるか否かを判定し、ある場合には当該面番号Ｎ＋１を読み出しポインタＮに代入した上で（ステップＳ４２）ステップＳ３２以降の動作を繰り返す。他方、ステップＳ４０の結果がＮｏの場合、ステップＳ４１にて次の面番号Ｎ＋２を読み出しポインタＮに代入した上で（ステップＳ４１）ステップＳ３２以降の動作を繰り返す。
【００５４】
次に図１１と共にメモリ１３からのデータ読み出し動作について説明する。
【００５５】
ステップＳ５１にて読み出しポインタを初期化し、メモリ１３中に読み出すべきデータがあるか否かにつき判定を行なう（ステップＳ５２）。その結果「有り」の場合、ステップＳ５３にて、現在読み出し停止状態か否かにつき判定する。即ち、上記の如く、バッファ１６の空き容量不足が判断された場合読み出し停止状態となるため、この点につき判定している。
【００５６】
次に上記判定の結果がＹｅｓの場合、ステップＳ５４にて、バッファ１６の空き容量が回復したか否かを判定し、回復していればステップＳ５５にて上記読み出し停止状態を解除し、ステップＳ５７に進む。他方、ステップＳ５３の判定結果がＮｏの場合、ステップＳ５６にて、当該読み出しポインタＮのデータ読み出しを行なった際にそれがバッファ１６に書き込まれた結果バッファ１６の空き容量不足が発生するか否かを予測判定する。その判定の結果がＹｅｓの場合現在の読み出しポインタＮが示すメモリ１３の領域に格納されたデータの読み出しを行わずに、ステップＳ５９にて当該読み出しポインタＮの値を次回の読み出しポインタＮの値に代入し、ステップＳ６０にて読み出し停止状態を設定してステップＳ５２以降の動作を繰り返す。
【００５７】
他方、ステップＳ５６の判定結果がＮｏの場合、ステップＳ５７にて現在の読み出しポインタＮが示すメモリ１３の領域に格納されたデータの読み出しを実施し、ステップＳ５８にて読み出しポインタをインクリメントしてステップＳ５２以降の動作を繰り返す。
【００５８】
尚、図１１と共に説明したメモリ１３からのデータ読み出し及び図９と共に説明したバッファ１６に対する書き込み動作は図５に示す読み出し部１５にて行い、図１０と共に説明したバッファ１６からの読み出し動作は読み出し整形部１７にて行なう。
【００５９】
このように本発明の実施例によれば、従来はパケットデータのパラレル化後の整形を大容量メモリの前段で行っていたのに対して、同整形動作を大容量メモリ（１３）の後段で行い、その代わりに小規模バッファ（１６）を多面構成で設けることによりパケットデータの欠落を効果的に防ぎ、正常な通信を確保することが可能となる。
【００６０】
本発明は以下の付記に示す構成を含む。
（付記１）
入力データを格納する第１の格納手段と、
第１の格納手段に格納された入力データを読み出してこれを所定の法則に従って分類し、各分類毎に順次所定の記憶単位に書き込む第２の格納手段とよりなり、
前記第１の格納手段は第２の格納手段より大きな記憶容量を有する構成とされてなるデータ処理装置。
（付記２）
第２の格納手段の記憶容量が不足すると判断された際に前記第１の格納手段からの読み出しを停止し、当該不足状態が解消した後、前記停止前に第２の格納手段に最後に書き込まれたデータが第１の格納手段から読み出された読み出し位置に遡って第１の格納手段からの読出しを再開する構成とされてなる付記１に記載のデータ処理装置。
（付記３）
第２の格納手段にデータを書き込む際には、その複数の記憶単位に対して所定の順序で書き込む構成とされ、前記第２の格納手段の記憶容量の不足の判断は、第１の格納手段から読み出されたデータを書き込んでいる記憶単位の番号と、このようにして書き込まれたデータが所定の処理のために読み出される記憶単位の番号との差の大小によって行なうものとされてなる請求項１乃至３の内の何れか一項に記載のデータ処理装置。
（付記４）
入力データを第１の格納手段に格納する段階と、
第１の格納手段に格納された入力データを読み出してこれを所定の法則に従って分類し、各分類毎に順次第２の格納手段の所定の記憶単位に書き込む段階とよりなり、
前記第１の格納手段は第２の格納手段より大きな記憶容量を有する構成とされてなるデータ処理方法。
（付記５）
更に第２の格納手段の記憶容量が不足すると判断された際に前記第１の格納手段からの読み出しを停止し、当該不足状態が解消した後、前記停止前に第２の格納手段に最後に書き込まれたデータが第１の格納手段から読み出された読み出し位置に遡って第１の格納手段からの読出しを再開する各段階よりなる付記４に記載のデータ処理方法。
（付記６）
第２の格納手段にデータを書き込む際には、その複数の記憶単位に対して所定の順序で書き込む構成とされ、前記第２の格納手段の記憶容量の不足の判断は、第１の格納手段から読み出されたデータを書き込んでいる記憶単位の番号と、このようにして書き込まれたデータが所定の処理のために読み出される記憶単位の番号との差の大小によって行なうものとされてなる付記４又は５に記載のデータ処理方法。
【図面の簡単な説明】
【００６１】
【図１】従来のパケットデータ交換装置のブロック図である。
【図２】図１に示す構成における、パケットデータのシリアル・パラレル変換と行き先別への整形動作を説明するためのタイムチャートである。
【図３】図１に示す構成に含まれる、従来のパケット整形処理部のブロック図である。
【図４】図３に示す構成による従来のパケット整形方式（メモリの前段で整形を行う際のメモリへの格納手順）を説明するための図である。
【図５】本発明の一実施例によるデータ処理装置のブロック図である。
【図６】図５の構成によるパケット整形（メモリの後段で整形を行う際のメモリへの格納手順）を説明するための図である。
【図７】図５の構成によるメモリの後段での分割整形処理の具体的動作例を説明するための図である。
【図８】図５の構成による小規模バッファ枯渇時の処理タイムチャートである。
【図９】図５に示すバッファに対する書き込み動作のフローチャートである。
【図１０】図５に示すバッファからの読み出し動作のフローチャートである。
【図１１】図５に示すメモリからの読み出し動作のフローチャートである。
【符号の説明】
【００６２】
１２  書き込み部
１３  メモリ
１４  読み出しアドレス保持部
１５  読出し部
１６  バッファ
１７  読み出し整形部
【図１】
2005175938.tif 000003
【図２】
2005175938.tif 000004
【図３】
2005175938.tif 000005
【図４】
2005175938.tif 000006
【図５】
2005175938.tif 000007
【図６】
2005175938.tif 000008
【図７】
2005175938.tif 000009
【図８】
2005175938.tif 000010
【図９】
2005175938.tif 000011
【図１０】
2005175938.tif 000012
【図１１】
2005175938.tif 000013