JP3652245B2

JP3652245B2 - Packet switch

Info

Publication number: JP3652245B2
Application number: JP2000378448A
Authority: JP
Inventors: 正美 ▲高▼橋; 明生牧本; 尚彦小崎; 隆行菅野; 康生荻沼
Original assignee: Hitachi Communication Technologies Ltd
Current assignee: Hitachi Communication Technologies Ltd
Priority date: 2000-12-13
Filing date: 2000-12-13
Publication date: 2005-05-25
Anticipated expiration: 2020-12-13
Also published as: JP2002185495A

Description

【０００１】
【発明の属する技術分野】
本発明は、可変長パケット通信ネットワークにおけるノード装置として適用されるパケットスイッチに関し、更に詳しくは、受信パケットを一時的に蓄積するためのメモリとして共通バッファメモリを使用した共通バッファ型の可変長パケットスイッチに関する。
【０００２】
【従来の技術】
近年、注目されているインターネットプロトコル（Internet Protocol：以下、ＩＰと言う）では、ＩＰデータグラムと呼ばれる可変長のパケット（ＩＰパケット）を転送単位として、メッセージ転送が行われる。ＩＰパケット網を構成する従来のノード装置では、ソフトウェア処理によって受信パケットの宛先方路へのスイッチングが行われているが、スイッチングの高速化要求に伴って、ノード装置内では固定長のパケット（データブロック）を転送単位としてスイッチングを行う装置構成が提案されている。
【０００３】
ＩＰパケットを高速度で転送するノード装置として、例えば、"A 50-Gb/s IP Router"（Craig Partridge他著、IEEE/ACM TRANSACTIONS ON NETWORKING, Vol.6,No.3,June 1998）の論文には、それぞれ複数のネットワーク・インタフェースをサポートする複数の回線カード（ボード）と、ルーティングテーブルを備えた転送エンジン（Forwarding Engine）カードとを、例えば、クロスバスイッチに代表されるポイント・ツー・ポイント型のスイッチで結合し、各回線カードが受信パケットのヘッダ部を含むデータブロックを上記転送エンジンに送信し、転送エンジンで更新処理された新たなヘッダ情報を含むデータブロックをパケット入力側の回線カードに返送し、入力側の各回線カードが、上記新たなヘッダ情報を含むデータブロックとパケット残部とを出力側回線カードに転送するようにした構成のルータ装置が提案されている。
【０００４】
上記論文によると、入力側の各回線カードが、パケットを６４バイト単位の連鎖されたページ（データブロック）に解体して送出すること、出力側の各回線カードが、これらのページをパケットを表すリンクド・リストに組立て、組立てたパケットをＱｏＳプロセッサに渡し、ＱｏＳプロセッサが、パケット長、宛先および転送エンジンが指定したフロー識別子に基づいて、上記パケットを送信キュー内の適当な位置に置くことが開示されている。
【０００５】
パケットの転送単位を固定長にしたスイッチング装置として、ＡＴＭ(Asynchronous Transfer Mode)スイッチがあげられる。ＡＴＭスイッチでは、各入力回線から受信された５３バイトの固定長パケット（ＡＴＭセル）をバッファメモリに一時的に蓄積した後、蓄積セルをセルヘッダに含まれるコネクション識別情報（ＶＰＩ／ＶＣＩ）によって決まる特定の出力回線にルーティングしている。
【０００６】
ＡＴＭスイッチにおいて、複数の入力回線でバッファメモリを共用する共通バッファ型の構造を採用すると、バッファメモリ内に各出力回線毎に可変長のキューを形成できるため、例えば、同一出力回線に向かうセル列が複数の入力回線から同時に受信された場合でも、共通バッファ全体として空き領域がある限り、各入力回線からの受信セルを廃棄することなくバッファリングすることが可能となり、メモリ資源を有効に利用したスイッチを実現できる。
【０００７】
特開平１１−２６１５８４号公報には、上記共通バッファメモリの利点を活かした可変長メッセージ用のスイッチング装置が提案されている。上記従来技術では、共通バッファメモリをメッセージ対応の複数のメモリブロックに分割し、各受信メッセージに対して空き状態の１つのメモリブロックを割り当て、各入力回線から受信されたメッセージを固定長の複数のセルに分割し、同一メッセージに属するセルを同一のメモリブロックに順次に格納する構成となっている。
【０００８】
【発明が解決しようとする課題】
上述したＩＥＥＥ文献に記載されたルータ装置では、入力側の回線カードが、各パケットの送信に先立って、スイッチ・アロケータを介して出力側回線カードと折衝し、出力側カードがパケットの受信を了承した場合に送信を開始しているため、パケットのスイッチング処理速度に問題がある。また、入力側の各回線カードにはパケットを待機させるためのバッファが必要となり、出力側の各回線カードにもパケット組立てのためのバッファが必要となるため、バッファメモリの使用効率に問題がある。
【０００９】
一方、上記特開平１１−２６１５８４号公報に記載されたスイッチング装置では、各メッセージの末尾部分が入力された時、受信メッセージと対応するメモリブロックに蓄積されている全てのセルを別のメモリ領域（メッセージキュー）に移す構成となっているため、メモリ領域間でのメッセージの転送所要時間とバッファメモリの利用効率に問題があった。
【００１０】
本発明の目的は、共通バッファメモリを効率的に利用し、可変長パケットを高速スイッチング可能なパケットスイッチを提供することにある。
本発明の他の目的は、共通バッファメモリを効率的に利用し、可変長パケットのマルチキャストを可能にしたパケットスイッチを提供することにある。
【００１１】
【課題を解決するための手段】
上記目的を達成するために、本発明のパケットスイッチは、複数の入力回線に共用される共通バッファメモリと、各入力回線からの受信パケットを固定長のデータブロック単位で多重化して上記共通バッファメモリに供給する多重化手段と、上記共通バッファメモリへの上記各固定長データブロックの書込みと読出しを制御するバッファ制御手段とからなり、上記バッファ制御手段が、上記多重化手段から出力された各固定長データブロックを上記共通バッファに書き込む時に可変長パケット別の入力キューを形成しておき、可変長パケットの最終データブロックが入力キューに登録された時点で、該入力キューを可変長パケットの転送先出力回線と対応した出力キューに登録することを特徴とする。
【００１２】
更に詳述すると、上記バッファ制御手段は、上記共通バッファメモリにおける各固定長データブロックの書込みアドレスを可変長パケット別にリンクすることによって複数の入力キューを形成し、可変長パケットの最後の固定長データブロックが上記共通バッファメモリに書き込み済みとなった入力キューを転送先出力回線と対応する待機バッファを備えた出力キューに登録する第１制御手段と、出力回線対応に形成された複数の出力キューを所定の順序でアクセスし、各出力キューが示すリンクド・アドレスに基づいて上記共通バッファメモリから固定長データブロックを読み出す第２制御手段とを備える。
上記可変長パケット別の入力キューは、例えば、空きアドレスメモリから取り出した書込みアドレスに基づいて上記共通バッファメモリに各固定長データブロックを書き込み、上記各書込みアドレスと対応して同一可変長パケットにおける次の固定長データブロックの書込みアドレスを次アドレスメモリに記憶することにより形成される。
【００１３】
本発明において、各出力キューは、例えば、可変長パケットの先頭データブロックの書込みアドレスと最終データブロックの書込みアドレスとを一時的に記憶するための待機バッファと、次に読み出すべきデータブロックを示す次読出しアドレスと最後のデータブロックを示す最終読出しアドレスとを記憶するアドレスメモリとからなり、上記第１制御手段が、各可変長パケットの先頭データブロックの書込みアドレスと最終データブロックの書込みアドレスをそれぞれ転送先出力回線と対応する待機バッファに登録し、これに付随するアドレスメモリが空き状態となった時、上記第２制御手段が、上記待機バッファから取り出した１対のアドレスを新たなデータブロック群の次読出しアドレスおよび最終読出しアドレスとしてアドレスメモリに設定する。この場合、第２制御手段は、各出力キューに登録された次読出しアドレスに基づいて、共通バッファメモリと次アドレスメモリからそれぞれ固定長データブロックと次の固定長データブロックのアドレスとを読み出し、上記次アドレスメモリから読み出されたアドレスを当該出力キューにおける新たな次読出しアドレスとすることによって、各可変長パケットを構成するデータブロックを次々と読み出すことが可能となる。
【００１４】
尚、受信パケットがマルチキャストパケットの場合、最後のデータブロックが共通バッファメモリに書き込まれた時点で、上記第１制御手段によって、同一入力キューをマルチキャスト出力回線と対応する複数の出力キューに登録することにより、マルチキャスト転送が可能となる。この場合、パケットスイッチに、共通バッファメモリにおける各固定長データブロックの読出し回数をカウントし、読出し回数が指定値に達した時、読出しアドレスを解放するアドレス解放制御手段を設けることによって、共通バッファメモリの空きアドレスを管理できる。
【００１５】
【発明の実施の形態】
以下、本発明の実施例について図面を参照して詳細に説明する。
図１は、本発明によるパケットスイッチの１実施例を示す。
パケットスイッチ１は、それぞれ入力回線ＬＩ−１〜ＬＩ−ｎから入力された可変長パケット１００を固定長の複数のデータブロック１１０に分割し、各データブロックに内部ヘッダ１１０Ａを付加して出力する複数の入力回線インタフェース１０−１〜１０−ｎと、上記入力回線インタフェース１０−１〜１０−ｎから入力されたデータブロックを時分割多重して信号線Ｌ２１に出力する多重化部２１と、上記信号線Ｌ２１に接続された共通バッファメモリ２２と、上記共通バッファメモリ２２から信号線Ｌ２２に読み出されたデータブロックを複数の出力回線インタフェース２０−１〜２０−ｎに順次に振り分ける分離部２３と、上記共通バッファメモリ２２へのデータブロックの書込みと読出しを制御するバッファ制御部３０と、書込みサイクルを示すクロックＣＬＫ０をカウントして入力回線選択信号を発生する入力カウンタ２４と、読出しサイクルを示すクロックＣＬＫ１をカウントして出力回線選択信号を発生する出力カウンタ２５とからなっている。
【００１６】
各入力回線ＬＩ−ｉ（ｉ＝１〜ｎ）から入力される可変長パケットは、宛先アドレスを含むパケットヘッダ１００Ａとデータ部１００Ｂとからなる。各入力回線インタフェース１０−ｉ（ｉ＝１〜ｎ）は、入力回線ＬＩ−ｉから受信した可変長パケット１００を固定長の複数のデータブロック１１０に分割し、例えば、入力回線番号と、パケットヘッダ１００Ａから抽出された宛先アドレスによって決まる出力回線番号と、各データブロック１１０が可変長パケットにおける先頭ブロック、中間ブロック、最終ブロックの何れに該当するかを示すブロック位置表示情報とを含む内部ヘッダ１１０Ａを生成し、これを各データブロックに付加して出力する。
【００１７】
共通バッファメモリ２２へのデータブロックの書込みと読出しは、クロックＣＬＫ０とＣＬＫ１に従って交互に行われる。多重化部２１は、入力カウンタ２４が信号線Ｌ２４に発生する入力回線選択信号に応じて、入力回線インタフェース１０−１〜１０−ｎを循環的に選択し、各入力回線インタフェースから出力されたデータブロック１１０を順次に信号線Ｌ２１に多重化する。一方、分離部２３は、共通バッファメモリ２２から信号線Ｌ２２に読み出されたデータブロックを、出力カウンタ２５が信号線Ｌ２５に発生する出力回線選択信号によって特定される出力回線インタフェース２０−ｊ（ｊ＝１〜ｎ）に振り分ける。
出力回線インタフェース２０−１〜２０−ｎは、分離部２３から受け取ったデータブロック１１０から内部ヘッダ１１０Ａを取り除き、それぞれと対応する出力回線ＬＯ−１〜ＬＯ−ｎに送出する。
【００１８】
バッファ制御部３０は、クロックＣＬＫ０が示す各書込みサイクルにおいて、信号線Ｌ２１に現れる内部ヘッダ１１０Ａが示す入力回線番号ｉと対応するリンクド・アドレスリストを形成しながら、データブロックを共通バッファメモリ２２に書き込む。
上記バッファ制御部３０は、後述するように、信号線Ｌ２１に受信パケットの先頭ブロックが現れる都度、入力回線対応の新たな入力キューを形成し、後続する中間ブロックと最終ブロックのデータを入力回線対応の入力キューに次々と登録し、受信パケットの最終ブロックが共通バッファメモリ２２に書き込まれた時点で、入力キューを上記受信パケットの転送先出力回線と対応した出力キューにリンクするように、リンクド・アドレスリストをダイナミックに制御する。
【００１９】
共通バッファメモリ２２からのデータブロックの読出しは、各出力回線と対応して形成された出力キュー・アドレスリストに基づいて行なわれる。バッファ制御部３０は、信号線Ｌ２５で与えられる出力回線選択信号と対応した出力キューについて、読み出すべきデータブロックの有無をチェックし、もし、出力キューにデータブロックアドレスがリンクされていた場合は、出力キュー・アドレスリストに登録された次読出しアドレスを読出しアドレスＲＡとして、共通バッファメモリ２２から１つのデータブロックを信号線Ｌ２２に読み出し、アドレスリストの次読出しアドレスをリンクド・アドレスリストにおける次のデータブロックアドレスに書き換える。
【００２０】
図２は、バッファ制御部３０の詳細を示すブロック図である。
バッファ制御部３０は、ヘッダ解析部３１と、入力キュー制御部３２と、出力キュー制御部３３と、次アドレス管理部３４と、共通バッファメモリ２０の空きアドレスを格納するための空アドレスメモリ（ＦＩＦＯ）３５とからなる。
【００２１】
ヘッダ解析部３１は、信号線Ｌ２１に現れる各データブロックの内部ヘッダを解析して、入力回線番号ＩＮ−ｉと、出力回線番号ＯＵＴ−ｊと、入力データブロックが受信パケットの先頭ブロックか否かを示す先頭表示フラグ信号ＦＰと、入力データブロックが受信パケットの最終ブロックか否かを示す最終表示フラグ信号ＥＰとを発生する。
入力キュー制御部３２は、入力回線毎に、入力キューに登録された先頭データブロックのアドレス（パケット先頭アドレス：ＢＡｉ（ｉ＝１〜ｎ））３０１と、上記入力キューに登録された最新データブロックのアドレス（最新アドレス：ＷＡｉ（ｉ＝１〜ｎ））３０２とを示す入力キュー・アドレステーブル３００を備えている。
出力キュー制御部３３は、出力キュー・アドレステーブル３１０と出力待機バッファ３３０とを備えている。
【００２２】
出力キュー・アドレステーブル３１０は、出力回線毎に、出力キューの先頭に位置したデータブロックの読出しアドレス（次読出しアドレスＲＡｊ（ｊ＝１〜ｎ））３１１と、出力キューの最後に位置したデータブロックの読出しアドレス（最終読出しアドレスＥＡｊ（ｊ＝１〜ｎ））３１２とを記憶するためのものである。以下の説明では、出力キュー・アドレステーブル３１０における第ｊ出力回線ＬＯ−ｊと対応したテーブル領域を符号３１０−ｊで表す。
【００２３】
出力待機バッファ３３０は、出力キュー・アドレステーブル３１０−ｊに先行パケットを読み出すためのアドレスＲＡｊ、ＥＡｊが残っている時、同一出力回線に送出すべき後続パケットの読み出しアドレスをＦＩＦＯ形式で待機させるためのものであり、各出力回線と対応して、パケットの先頭データブロックの読み出しアドレスＢＡｊを蓄積するためのバッファ領域３３０Ｂ−ｊと、パケットの最後のデータブロックの読み出しアドレスＷＡｊを蓄積するためのバッファ領域３３０Ｗ−ｊとが用意されている。バッファ領域３３０Ｂ−ｊ、３３０Ｗ−ｊに蓄積された読出しアドレスは、先行パケットの全てのデータブロックが共通バッファメモリから読み出され、実質的に出力キュー・アドレステーブルが空き状態となった時点で、出力キュー・アドレステーブルのテーブル領域３１０−ｊに移される。
【００２４】
次アドレス管理部３４は、共通バッファメモリ２２に蓄積可能なデータブロック数ｍに等しい複数のアドレス記憶領域ＮＡ１〜ＮＡｍからなる次アドレスメモリ３４０を備える。次アドレスメモリ３４０の各記憶領域は、入力キューに登録されたデータブロック列を登録順に読み出すためのリンクド・アドレスリストを形成するために利用される。
【００２５】
以下、入力回線ＬＩ−１とＬＩ−２から同一の出力回線ＬＯ−３に向かう可変長パケットが入力された場合を仮定して、入力回線ＬＩ−１と対応する入力キューのパケット先頭アドレスＢＡ１および最新アドレスＷＡ１と、入力回線ＬＩ−２と対応する入力キューのパケット先頭アドレスＢＡ２および最新アドレスＷＡ２と、出力回線ＬＯ−２と対応する出力キューの次読出しアドレスＲＡ３および最終読出しアドレスＥＡ３に着目して、図２と図３〜図５を参照しながら上記バッファ制御部３０の機能について詳述する。
【００２６】
ヘッダ解析部３１は、信号線Ｌ２１に出力された各データブロックの内部ヘッダ１１０Ａを解析し、入力回線番ＩＮ−ｉと出力回線番号ＯＵＴ−ｉを発生する。上記データブロックが可変長パケットの先頭ブロックであれば先頭表示フラグ信号ＦＰがオン状態となり、最終ブロックであれば最終表示フラグ信号ＥＰがオン状態となる。
信号線Ｌ２１に出力されたデータブロックは、空アドレスＦＩＦＯ３５から取り出された空きアドレスを書込みアドレスＷＡとして、共通バッファメモリ２０に書き込まれる。この時、入力キュー制御部３２は、ヘッダ解析部３１から出力された入力回線番号ＩＮ−ｉと先頭表示フラグ信号ＦＰの状態に応じて、入力キュー・アドレステーブル３００を更新する。
先頭表示フラグ信号ＦＰがオン状態であれば、空きアドレスＦＩＦＯ３５から取り出された書込みアドレスＷＡを上記入力回線番号ＩＮ−ｉと対応するテーブル領域３００−ｉにパケット先頭アドレスＢＡｉと最新アドレスＷＡｉとして書き込む。先頭表示フラグ信号ＦＰがオフ状態であれば、上記書込みアドレスＷＡを最新アドレスＷＡｉに書き込む。
【００２７】
入力キュー・アドレステーブル３００に新たなアドレスＷＡが書き込まれた時、最新アドレスＷＡｉとしてそれまで記憶されていたアドレスが次アドレス管理部３４に出力される。次アドレス管理部３４は、上記アドレスＷＡｉと対応する記憶領域ＮＡｉに、空きアドレスＦＩＦＯ３５から取り出された新たな書込みアドレスＷＡを記憶する。
これによって、１つの可変長パケットから分割された固定長のデータブロックが共通バッファメモリ２２に書込まれる度に、データブロックの書込みアドレスが次アドレスメモリ３４０に記憶され、最新アドレスＷＡｉが更新され、最終的には、パケット先頭アドレスＢＡｉが可変長パケットの先頭データブロックのアドレスを指し、最新アドレスＷＡｉが可変長パケットの最終データブロックのアドレスを指すことになる。
【００２８】
図３は、共通バッファメモリ２２に、入力回線インタフェース１０−１から出力されたデータブロックＤ１−１〜Ｄ１−４と、入力回線インタフェース１０−２から出力されたデータブロックＤ２−１〜Ｄ２−２が書き込まれた時点での、入力キュー・アドレステーブル３００の状態を示す。
ここで、ＷＡ１−１〜ＷＡ１−４は、空きアドレスＦＩＦＯ３５から得られたデータブロックＤ１−１〜Ｄ１−４の書込みアドレスＷＡの値、ＷＡ２−１〜ＷＡ２−２はデータブロックＤ２−１〜Ｄ２−２の書込みアドレスＷＡの値を示す。また、ＲＡ３とＥＡ３は、上記データブロックＤ１−１〜Ｄ１−４、Ｄ２−１〜Ｄ２−２の転送先出力回線ＬＯ−３と対応した出力キュー・アドレステーブルエントリ３１０−３の内容を示している。
【００２９】
入力回線ＬＩ−１と対応する入力キュー・アドレステーブルでは、先頭データブロックＤ１−１の書込みアドレスＷＡ１−１がパケット先頭アドレスＢＡ１として記憶され、最新アドレスＷＡ１の内容はデータブロックの書込みの都度更新されて、ＷＡ１−１、ＷＡ１−２、ＷＡ１−３、ＷＡ１−４と変化する。
次アドレスメモリ３４０では、図３に示すように、最新アドレスＷＡ１と対応する記憶領域に、次データブロックの書込みアドレスが次々と記憶される。従って、入力キュー・アドレステーブル３００のパケット先頭アドレスＢＡ１と次アドレスメモリ３４０とによって、入力回線毎のリンクド・アドレスリストが形成される。
【００３０】
例えば、パケット先頭アドレスＢＡ１が示すアドレスＷＡ１−１に基づいて共通バッファメモリ２２と次アドレスメモリ３４０をアクセスすることによって、先頭データブロックＤ１−１と、次のデータブロックＤ１−２のアドレスＷＡ１−２とを読み出すことができ、このアドレスＷＡ１−２を次回の読出しサイクルにおける読出しアドレスＲＡとして利用することにより、次のデータブロックＤ１−２と、更に次のデータブロックＤ１−３のアドレスＷＡ１−３とを読み出すことができ、同様の動作を繰り返すことによって、入力キューに登録された全てのデータブロックを読み出すことが可能となる。
【００３１】
入力回線ＬＩ−１と同様、入力回線ＬＩ−２と対応する入力キュー・アドレステーブルでは、先頭データブロックＤ２−１の書込みアドレスＷＡ２−１がパケット先頭アドレスＢＡ２として記憶され、最新アドレスＷＡ１の内容は、データブロックの書込みの都度更新され、ＷＡ２−１、ＷＡ２−２、…と変化する。
【００３２】
図３は、入力回線インタフェース１０−１と１０−２が可変長パケットの最終データブロックを出力する前の状態を示しており、出力回線ＬＯ−３と対応した出力キューには有効データがなく、出力待機バッファ３３０−３と出力キュー・アドレステーブル３１０−３が空き状態となっている。
本発明は、共通バッファメモリ２２にパケットの最終データブロックが書き込まれた時、バッファ制御部３０が、上記最終データブロックの入力キューにおけるパケット先頭アドレスＢＡｉと最新アドレスＷＡｉ（＝ＷＡ）を出力待機バッファ３３０を介して出力キュー・アドレステーブル３１０に移すことを特徴としている。
【００３３】
図４は、入力回線インタフェース１０−１から出力された可変長パケットの最終データブロックＤ１−５が共通バッファメモリ２２に書き込まれた時点でのバッファ制御部３０の動作を示す。
この場合、バッファ制御部３０は、最終データブロックＤ１−５の書込みアドレスＷＡ１−５を次アドレスメモリ３４０に記憶した後、入力キューのパケット先頭アドレスＢＡ１の内容（ＷＡ１−１）と最新アドレスＷＡ１の内容（ＷＡ１−５）を出力待機バッファ３３０−３に移す。出力待機バッファ３３０−３に蓄積されたアドレスは、もし、出力キュー・アドレステーブル３１０−３が空き状タであれば、図４に示すように、出力キュー・アドレステーブルのＲＡ３、ＥＡ３に移される。尚、最新アドレスＷＡ１の内容は、今回、空きアドレスＦＩＦＯ３５から取り出された新たな書込みアドレスＷＡとなっているため、出力キュー・アドレステーブルのＥＡ３には、上記最新アドレスＷＡ１に代えて、空きアドレスＦＩＦＯ３５から取り出された書込みアドレスＷＡを記憶してもよい。
【００３４】
図５は、出力回線ＬＯ−３の出力キューが既に使用状態にある時、入力回線インタフェース１０−２から出力された可変長パケットの最終データブロックＤ２−３を共通バッファメモリ２２に書き込む場合のバッファ制御部３０の動作を示す。この場合、バッファ制御部３０は、最終データブロックＤ２−３の書込みアドレスＷＡ２−３を次アドレスメモリ３４０に記憶した後、入力キューのパケット先頭アドレスＢＡ２の内容（ＷＡ２−１）と最新アドレスＷＡ２の内容（ＷＡ２−３）を出力待機バッファ３３０−３に移す。
上記出力待機バッファ３３０−３に蓄積されたアドレスＷＡ２−１、ＷＡ２−３は、出力キュー・アドレステーブル３１０−３が空き状態となった時、すなわち、次読み出しアドレスＲＡ３と最終読み出しアドレスＥＡ３の値が一致した読み出しサイクルで、出力キュー・アドレステーブル３１０−３に移される。
【００３５】
回線インタフェースが受信した可変長パケットが短く、受信パケット全体が固定長の１つのデータブロックに収まる場合は、このデータブロックの書込みサイクルで、ヘッダ解析部３１から出力される先頭表示フラグ信号ＦＰと最終表示フラグ信号ＥＰが同時にオン状態となる。この場合、先頭表示フラグ信号ＦＰに応答して入力キュー・アドレステーブル３００に登録されたパケット先頭アドレスＢＡｉと最新アドレスＷＡｉの内容が、最終表示フラグ信号ＥＰに応答して出力待機バッファ３３０−ｊに直ちに移される。
【００３６】
もし、待機バッファ３３０−ｊに蓄積されたパケット先頭アドレスＢＡｉと最新アドレスＷＡｉの内容は、データブロックの転送先となる出力回線ＬＯ−ｊの出力キューが空状態であれば、図４と同様、出力キュー・アドレステーブル３１０−ｊに書き込まれ、上記出力キューが既に使用状態にあれば、図５と同様、出力待機バッファ３３０−ｊに留まる。
【００３７】
共通バッファメモリ２２からのデータブロックの読出しは、出力キュー制御部３３によって行われる。出力キュー制御部３３は、読出しサイクルに信号線Ｌ２５に出力される出力回線選択信号で特定される出力キュー・アドレステーブル領域３１０―ｊを参照し、次読出しアドレスＲＡｊに従って、共通バッファメモリ２２からデータブロックを読み出し、次アドレスメモリ３４０から次アドレスＮＡｊを読み出す。
使用済みとなった次読出しアドレスＲＡｊは、空きアドレスＦＩＦＯ３５に解放され、次アドレスメモリ３４０から読み出された次アドレスＮＡｊは、新たな次読出しアドレスＲＡｊとして出力キュー・アドレステーブル３１０−ｊに記憶される。但し、各パケットの最後のデータブロックの読出しサイクルでは、次アドレスメモリ３４０から読み出された次アドレスＮＡｊは無効となり、待機バッファから取り出された次パケットの先頭アドレスが、次読出しアドレスＲＡｊとして出力キュー・アドレステーブル３１０−ｊに設定される。
【００３８】
図６は、入力キュー制御部３２の１実施例を示す。
入力キュー制御部３２は、パケット先頭アドレスＢＡ１〜ＢＡｎを記憶するためのレジスタ３０１−１〜３０１−ｎと、最新アドレスＷＡ１〜ＷＡｎを記憶するためのレジスタ３０２−１〜３０２−ｎと、ヘッダ解析部３１から受信した入力回線番号ＩＮ−ｉをデコードし、イネーブル信号ＷＥＮ−１〜ＷＥＮ−ｎのうちの１つをオン状態とするデコーダ３２１と、レジスタ３０２−１〜３０２−ｎからの出力アドレスのうちの１つを選択するためのセレクタ３２２と、レジスタ３０１−１〜３０１−ｎからの出力アドレスのうちの１つを選択するためのセレクタ３２３と、パケット先頭アドレスの書込みイネーブル信号を制御するためのＡＮＤ回路３２４−１〜３２４−ｎとからなっている。
【００３９】
最新アドレスを記憶するレジスタ３０２−１〜３０２−ｎには、空きアドレスＦＩＦＯ３５から取り出されたアドレスＷＡが入力されており、それぞれデコーダ３２１から出力されるイネーブル信号ＷＥＮ−１〜ＷＥＮ−ｎによって、最新アドレスの更新が制御されている。入力回線番号ＩＮ−ｉが第ｉ番目の入力回線を示した場合、イネーブル信号ＷＥＮ―ｉがオン状態となり、空きアドレスＦＩＦＯ３５から取り出されたアドレスＷＡがレジスタ３０２−ｉに設定される。この時、それまでレジスタ３０２−ｉに記憶されていた前データブロックの書込みアドレス｛ＷＡｉ｝がセレクタ３２２によって選択され、次アドレス（ポインタアドレス）書込み用アドレスＷＡｉとして次アドレス管理部３４に供給される。
【００４０】
空きアドレスＦＩＦＯ３５から取り出されたアドレスＷＡは、パケット先頭アドレスＢＡ１〜ＢＡｎを記憶するためのレジスタ３０１−１〜３０１−ｎにも入力されている。これらのレジスタへの書込みは、ＡＮＤ回路３２４−１〜３２４−ｎによって制御されており、ヘッダ解析部３１から出力される先頭表示フラグＦＰがオン状態となった書込みサイクルに限り、入力回線番号ＩＮ−ｉと対応するレジスタ３０１−ｉへのアドレスＷＡの書込みが行われる。セレクタ３２３は、入力回線番号ＩＮ−ｉと対応するレジスタ３０１−ｉからの出力アドレスを選択し、パケット先頭アドレスＢＡｉとして出力する。
【００４１】
図７は、出力キュー制御部３３の１実施例を示す。
出力キュー制御部３３は、次読出しアドレスＲＡ１〜ＲＡｎを記憶するためのレジスタ３１１−１〜３１１−ｎと、最終読出しアドレスＥＡ１〜ＥＡｎを記憶するためのレジスタ３１２−１〜３１２−ｎと、パケット先頭アドレス用の出力待機バッファ（ＦＩＦＯ）３３０Ｂ−１〜３３０Ｂ−ｎと、パケット最終アドレス用の出力待機バッファ（ＦＩＦＯ）３３０Ｗ−１〜３３０Ｗ−ｎとからなっている。
【００４２】
また、上記出力キュー制御部３３は、レジスタ３１１−１〜３１１−ｎからの出力アドレスのうちの１つを選択するためのセレクタ３３１と、レジスタ３１２−１〜３１２−ｎからの出力アドレスのうちの１つを選択するためのセレクタ３３２と、レジスタ３１３−１〜３１３−ｎからの出力フラグのうちの１つを選択するためのセレクタ３３３と、出力カウンタ２５から信号線２５に出力された出力回線選択信号をデコードするためのデコーダ３３４と、ヘッダ解析部３１から出力される出力回線番号ＯＵＴ−ｊをデコードして、イネーブル信号ＥＮ−１〜ＥＮ−ｎのうちの１つをオン状態とするデコーダ３３５と、ヘッダ解析部３１から出力される最終表示フラグ信号ＥＰがオン状態となった時、上記イネーブル信号ＥＮ−１〜ＥＮ−ｎを有効にするためのＡＮＤ回路３３６−１〜３３６−ｎと、セレクタ３３１から出力される読出しアドレスＲＡｊとセレクタ３３２から出力されるパケット最終アドレスＥＡｊとを比較し、ＲＡｊとＥＡｊが一致した時、イネーブル信号ＥＮ−０をオン状態とする比較器３１５と、上記イネーブル信号ＥＮ−０がオフ状態の時、次アドレス管理部３４から出力された次アドレスＮＡｊをレジスタ３１１−１〜３１１−ｎに供給するＡＮＤ回路３１６と、上記イネーブル信号ＥＮ−０がオン状態の時、デコーダ３３４の出力信号を通すＡＮＤ回路３３９−１〜３３９−ｎとを備えている。
【００４３】
出力待機バッファ３３０−ｊ（３３０Ｂ−ｊと３３０Ｗ−ｊ、ｊ＝１〜ｎ）は、それぞれＡＮＤ回路３３６−１〜３３６−ｎの出力信号が書込みイネーブル信号ＷＥＮとして与えられている。書込みサイクルにおいて、最終表示フラグ信号ＥＰがオン状態となった時、出力回線番号ＯＵＴ−ｊと対応するＡＮＤ回路３３６−ｊからの書込みイネーブル信号ＷＥＮが有効となり、バッファ領域３３０Ｂ−ｊに入力キュー制御部３２から出力されたパケット先頭アドレスＢＡｉが設定され、バッファ領域３３０Ｗ−ｊに空きアドレスＦＩＦＯ３５から出力された書込みアドレスＷＡが設定される。
【００４４】
出力待機バッファ３３０−ｊ（３３０Ｂ−ｊと３３０Ｗ−ｊ）には、それぞれＡＮＤ回路３３９−１〜３３９−ｎの出力信号が読出しイネーブル信号ＲＥＮとして与えられている。読出しサイクルにおいて、比較器３１５の出力信号ＥＮ−０がオン状態となった時、出力回線番号ＯＵＴ−ｊと対応するＡＮＤ回路３３９−ｊの出力信号がオン状態となる。これによって、バッファ領域３３０Ｂ−ｊ、３３０Ｗ−ｊから１組のアドレスＢＡｊとＷＡｊが読み出され、それぞれ次読出しアドレスＲＡｊ、最終読み出しアドレスＥＡｊとしてレジスタ３１１−ｊ、３１２−ｊに設定される。
【００４５】
レジスタ３１１−１〜３１１−ｎには、デコーダ３３４の出力がリード・イネーブル信号として与えてあり、これらのレジスタ出力は、信号線Ｌ２５から供給される出力回線選択信号を制御信号とするセレクタ３３１に接続されている。従って、各読出しサイクルにおいて、上記出力回線選択信号で指定されたレジスタ３１１−ｊの内容が次読出しアドレスＲＡｊとして出力される。上記アドレスＲＡｊによって、共通バッファメモリ２２から、出力回線ＬＯｊに出力すべきデータブロックが読み出され、分離部２３を介して出力回線インタフェース２０−ｊに供給される。また、上記アドレスＲＡｊによって、次アドレス管理部３４から、上記出力回線ＬＯｊに出力すべき次のデータブロックを指すアドレスＮＡｊが読み出される。上記アドレスＮＡｊは、ＡＮＤ回路３１６を介してレジスタ３１１−１〜３１１−ｎに供給されている。
【００４６】
レジスタ３１１−１〜３１１−ｎと同様に、レジスタ３１２−１〜３１２−ｎにも、デコーダ３３４の出力がリード・イネーブル信号として与えてあり、これらのレジスタ出力は、出力回線選択信号を選択信号とするセレクタ３３２に接続されている。これによって、各読出しサイクルで、上記出力回線選択信号で指定されたレジスタ３１２−ｊの内容がセレクタ３３２から最終読出しアドレスＥＡｊとして出力される。
【００４７】
比較器３１５の出力信号ＥＮ−０は、セレクタ３３１から出力される次読出しアドレスＲＡｊと、セレクタ３３２から出力される最終読出しアドレスＥＡｊとが一致した時、すなわち、各パケットの最終データブロックの読出しサイクルにおいてオン状態となり、前述したように、出力待機バッファ３３０Ｂ−ｊにあるパケット先頭アドレスＢＡｉがレジスタ３１１−ｊに移される。上記比較器３１５の出力信号ＥＮ−０がオフ状態となる読出しサイクル、すなわち、パケットの先頭データブロックまたは中間データブロックの読出しサイクルでは、ＡＮＤ回路３１６が開かれ、次アドレス管理部３４から読み出された次アドレスＮＡｊが上記レジスタ３１１−ｊに設定される。これによって、出力回線ＬＯ−ｊと対応した出力キューのデータブロックを次々と読み出すことが可能となる。
【００４８】
図８は、次アドレス管理部３４の１実施例を示す。
次アドレス管理部３４は、次アドレスＮＡ１〜ＮＡｍを記憶するためのレジスタ３４０−１〜３４０−ｍと、これらのレジスタからの出力アドレスを選択するセレクタ３４１と、入力キュー制御部３２から供給される最新アドレスＷＡｉをデコードし、上記最新アドレスＷＡｉと対応するレジスタ３４０−ｉに書込みイネーブル信号を与えるデコーダ３４４とからなる。
【００４９】
次アドレス管理部３４は、各書込みサイクルにおいて、入力キューにおける前データブロックの書込みアドレスＷＡｉと対応した記憶領域（レジスタ３４０−ｋ）に最新データブロックの書込みアドレスＷＡを記憶し、これによって、図３に示した入力キュー毎のリンクド・アドレスリストを形成する。読出しサイクルでは、セレクタ３４１が、出力キュー制御部３３から供給された読出しアドレスＲＡｊと対応したレジスタ３４０−ｐを選択し、上記レジスタに３４０−ｐに記憶されたアドレスを次アドレスＮＡｊとして出力キュー制御部３３に戻す。上記次アドレスＮＡｊは、出力キュー制御部３３において、次回の読出しサイクルで使う新たな次読出しアドレスＲＡｊとして、レジスタ３１１−ｊに記憶される。
【００５０】
図９は、本発明の第２の実施例として、同一受信パケットを複数の出力回線に転送する同報機能（またはマルチキャスト機能）を備えたパケットスイッチのバッファ制御部３０Ｂの構成を示す。
ここに示したバッファ制御部３０Ｂは、図２に示した第１実施例のバッファ制御部３０と同様、ヘッダ解析部３１、入力キュー制御部３２、出力キュー制御部３３、次アドレス管理部３４、空きアドレスＦＩＦＯ３５を有し、新たな要素として、読出しアドレス解放制御部３６を備えている。
【００５１】
各入力回線インタフェース１０−ｉ（ｉ＝１〜ｎ）では、入力回線ＬＩ−ｉからの受信パケットが複数の出力回線に転送すべき同報（マルチキャスト）パケットの場合、受信パケットを分割して得られた各データブロックに複数の出力回線を指定した内部ヘッダを付加する。複数の出力回線を同時に指定するためには、例えば、内部ヘッダの出力回線番号フィールドを出力回線ＬＯ−１〜ＬＯ−ｎと対応するｎビットで構成し、パケット転送先となる出力回線をビット“１”で表すビットパターン形式を採用すればよい。
【００５２】
ヘッダ解析部３１は、多重化部２１から信号線Ｌ２１に出力された各データブロックの内部ヘッダを解析し、入力回線番号ＩＮ−ｉ、出力回線番号ＯＵＴ−ｊ、先頭表示フラグ信号ＦＰ、最終表示フラグ信号ＥＰと、受信パケットの転送先出力回線数ＮＴＲを発生する。上記出力回線番号ＯＵＴ−ｊとしては、上述した内部ヘッダの出力回線番号フィールドが示すビットパターンを出力する。この場合、転送先出力回線数ＮＴＲは、上記出力回線番号フィールドに含まれるビット“１”の個数を示す。
【００５３】
多重化部２１から信号線Ｌ２１に出力された各データブロックは、第１実施例と同様、空きアドレスＦＩＦＯ３５から取り出されたアドレスＷＡを書込みアドレスとして共通バッファメモリ２２に蓄積され、入力キュー制御部３２と次アドレス管理部３４によって、入力回線番号ＩＮ−ｉと対応した入力キューが形成される。
共通バッファメモリ２２に蓄積されたデータブロックが可変長パケットの最終データブロックの場合、最終表示フラグ信号ＥＰがオン状態となるため、入力キュー制御部３２から出力されたパケット先頭アドレスＢＡｉと、空きアドレスＦＩＦＯ３５から取り出された最新アドレスＷＡ（＝ＷＡｉ）が出力キュー制御部３３の出力待機バッファ３３０に設定される。
【００５４】
図７に示した出力キュー制御部３３において、デコーダ３３５に入力する出力回線番号ＯＵＴ−ｊが転送先出力回線をビット“１”で表すビットパターンとなっていた場合、上記デコーダ３３５から出力されるイネーブル信号群を上記ビットパターンに従ってオン状態にすることができる。上記デコーダ３３５から出力されるイネーブル信号ＥＮ−１〜ＥＮ−ｎは、最終表示フラグ信号ＥＰがオン状態となった時、ＡＮＤ回路３３６−１〜３３６−ｎを通って出力待機バッファ３３０−１（３３０Ｂ−１、３３０Ｗ−１）〜３３０−ｎ（３３０Ｂ−ｎ、３３０Ｗ−ｎ）に書込みイネーブル信号ＷＥＮとして与えられる。
【００５５】
最終データブロックがユニキャストパケットに属していた場合、該ユニキャストパケットの出力回線と対応した１つのイネーブル信号ＥＮ−ｊだけがオン状態となるため、アドレスＢＡｉ、ＷＡは、第１実施例と同様、上記イネーブル信号ＥＮ−ｊが与えられている特定の出力待機バッファ３３０Ｂ−ｊ、３３０Ｗ−ｊに設定される。もし、最終データブロックが同報パケットに属していた場合は、出力回線番号ＯＵＴ−ｊのビットパターンと対応した複数のイネーブル信号ＥＮ−ｊ（ｊ＝ｊ１、ｊ２、ｊ３、…）が同時にオン状態となるため、アドレスＢＡｉとＷＡは、オン状態のイネーブル信号が与えられている複数の出力待機バッファ３３０Ｂ−ｊ、３３０Ｗ−ｊ（ｊ＝ｊ１、ｊ２、ｊ３、…）に同時に設定されることになる。
【００５６】
出力待機バッファ３３０−１〜３３０−ｎに設定されたアドレスＢＡｉとＷＡは、第１実施例と同様に、次読出しアドレスレジスタ３１１−１〜３１１−ｎと最終読出しアドレスレジスタ３１２−１〜３１２−ｎに移され、次読出しアドレスレジスタ３１１−１〜３１１−ｎが示す読出しアドレスＲＡｊに従って、共通バッファメモリ２２からのデータブロックの読出しが行なわれる。同報パケットに属したデータブロックは、上述したように、リンクド・アドレスリストが複数の出力キューに登録されているため、同一のデータブロックが複数回繰り返して読み出されることになる。
【００５７】
ユニキャストパケットだけを対象とした第１の実施例では、図２に示したように、共通バッファメモリ２２からのデータブロックを読出した時点で、読出しアドレスＲＡｊを空きアドレスＦＩＦＯ３５に解放すればよかった。これに対して、本実施例のように同報パケットを扱う場合は、指定された複数の出力回線へのマルチキャストが完了したことを確認して、上記読出しアドレスＲＡｊを空きアドレスＦＩＦＯ３５に解放する必要がある。
【００５８】
読出しアドレス解放制御部３６は、データブロック毎にマルチキャストの完了を確認して読出しアドレスＲＡｊを解放するためのものである。
図１０は、読出しアドレス解放制御部３６の１実施例を示す。
ここに示した読出しアドレス解放制御部３６は、書込みアドレスＷＡと対応してデータブロックの読出し回数ＲＣを記憶するためのレジスタ（メモリ領域）３６０−１〜３６０−ｍと、上記レジスタ３６０−１〜３６０−ｍへの入力を選択するためのセレクタ３６１−１〜３６１−ｍと、上記レジスタ３６０−１〜３６０−ｍの値をデクリメント（−１）するための減算器３６２−１〜３６２−ｍと、書込みアドレスＷＡおよび読出しアドレスＲＡｊをデコードし、これらのアドレスと対応したイネーブル信号を発生するデコーダ３６３と、上記レジスタ３６０−１〜３６０−ｍのうち、読出しアドレスＲＡｊと対応したレジスタ３６０−ｑの設定値（読出し回数ＲＣ）を選択するセレクタ３６４と、比較器３６５およびゲート３６６からなっている。
【００５９】
各セレクタ３６１−ｋ（ｋ＝１〜ｍ）には、書込みサイクルを示すクロックＣＬＫ０が選択制御信号として与えてあり、書込みサイクルでは、ヘッダ解析部３１から出力された転送先出力回線数ＮＴＲが選択され、読出しサイクルでは、減算器３６２−ｋ（ｋ＝１〜ｍ）の出力が選択され、それぞれ読出し回数レジスタ３６０−ｋ（ｋ＝１〜ｍ）に入力される。読出し回数レジスタ３６０−１〜３６０−ｍには、デコーダ３６３の出力が書込みイネーブル信号として与えてあり、書込みサイクルでは、書込みアドレスＷＡと対応したレジスタ３６０−ｐに出力回線数ＮＣＰが設定される。読出しサイクルでは、読出しアドレスＲＡｊと対応したレジスタ３６０−ｑの値がセレクタ３６４で選択され、比較器３６５に入力される。この時、レジスタ３６０−ｑの値が減算器３６２−ｑに入力され、読出し回数ＲＣｑをデクリメント（−１演算）した値がレジスタ３６０−ｑに再設定される。
【００６０】
例えば、ユニキャストパケットに属したデータブロックの書込みサイクルでは、書込みアドレスＷＡと対応した読出し回数レジスタ３６０−ｐに、転送先出力回線数ＮＴＲの値（＝１）が読出し回数ＲＣｐとして設定され、上記データブロックが読出しサイクルでアドレスＲＡｊに従って読み出された時、ＲＣｐ＝１が比較器３６５に入力される。比較器３６５は、共通バッファメモリ２２から読み出されたデータブロックの読出し回数ＲＣｐの値が「１」になった時、ゲート３６６を開き、読出しアドレスＲＡｊを空きアドレスＦＩＦＯ３５に解放する。従って、ユニキャストパケットに属したデータブロックの書込みアドレス（読出しアドレスＲＡｊ）は、データブロックの読出しの都度、直ちに解放される。
【００６１】
同報（マルチキャスト）パケットに属したデータブロックの書込みサイクルでは、書込みアドレスＷＡと対応した読出し回数レジスタ３６０−ｐに、読出し回数ＲＣｐとして、「１」より大きい値をもったＮＴＲが設定される。従って、共通バッファ２２から上記データブロックが読み出されても、デクリメントされたＲＣｐ値が「１」に達しない限り、ゲート３６６は閉じたままとなり、読出し回数がＮＴＲで指定された回数（ＲＣｐ＝１）となった時点で、読出しアドレスＲＡｊの空きアドレスＦＩＦＯ３５へ解放される。
【００６２】
以上の実施例では、バッファ制御部３０が、入力回線番号毎に入力キューを形成し、可変長パケットの最後のデータブロックが到着した時点で、入力キューのリンクド・アドレスリストを出力キューに移すようにしたが、本発明において、各入力キューは可変長パケット毎に形成できればよいため、上記入力回線番号に代えて、各可変長パケットに固有の他の識別情報を使用してもよい。
実施例では、各データブロックの内部ヘッダに入力回線番号を設定し、ヘッダ解析部３１が上記内部ヘッダに基づいて入力回線番号ＩＮ−ｊを出力したが、入力回線番号ＩＮ−ｊは、入力カウンタ２４から出力される入力回線選択信号に基づいて生成するようにしてもよい。
【００６３】
また、上述した実施例では、各入力回線インタフェース１０−ｉ（ｉ＝１〜ｎ）で、受信パケット１００を固定長の複数のデータブロック１１０に分割し、各データブロックに内部ヘッダ１１０Ａを付して多重化部２１に出力し、内部ヘッダ付きのデータブロックを共通バッファメモリ２２にリード、ライトする構成となっているが、本発明の他の実施形態として、例えば、図１１に示すように、多重化部２１でデータブロック１１０と内部ヘッダ１１０Ａを分離し、内部ヘッダ１１０Ａはバッファ制御部３０のヘッダ解析部３１に供給し、共通バッファメモリ２２にはデータブロック１１０部分のみを入力するようにしてもよい。
上記構成によれば、共通バッファメモリ２２のメモリ容量を有効に利用でき、各出力回線インタフェース２０―ｉでデータブロックから内部ヘッダを除去する必要がなくなる。
【００６４】
本発明の更に他の実施形態として、各入力回線インタフェース１０−ｉが、固定長データブロック１１０を内部ヘッダを付すことなく多重化部２１に出力し、バッファ制御部３０のヘッダ解析部３１が、各可変長パケットの先頭データブロックに含まれるパケットヘッダを解析し、入力回線毎に出力回線番号と後続データブロック数を管理テーブル上で管理しておき、入力カウンタ２４から与えられる入力回線選択信号に応じて上記管理テーブルを参照し、前述したＩＮ−ｉ、ＦＰ、ＥＰ、ＯＵＴ−ｊ等の制御信号を生成するようにしてもよい。また、可変長パケット１００から固定長のデータブロック１１０への変換は、各入力回線インタフェース１０−ｉで行う代わりに、多重化部２１で行うようにしてもよい。
実施例では、複数の入出力回線に接続されるパケットスイッチについて説明したが、本発明のバッファ制御は、複数の入力回線から受信した可変長パケットを１つの出力回線に出力するスイッチ構造（多重化装置）にも適用可能である。
【００６５】
以上のように、本発明の実施例では、可変長パケット毎の入力キューを形成し、１つの可変長パケットの最後のデータブロックがバッファメモリに書き込まれた時点で、入力キューに登録されたリンクド・アドレスを出力キューに移すようにしている。従って、同一の出力回線に向かう複数の可変長パケットが並列的に入力された場合でも、出力キュー内で１つの可変長パケットに属したデータブロック列に他のパケットのデータブロックが混入するのを防止でき、出力キューから取り出したデータブロックを順次に出力回線に送出することによって、受信パケットを正しく宛先装置に転送することが可能となる。
【００６６】
また、実施例のように、出力キューを待機バッファとアドレステーブル（またはレジスタ）で構成し、出力待機中の可変長パケットの先頭データブロックと最終データブロックのアドレスを待機バッファに一時的に蓄積し、出力中の可変長パケットの次読出しアドレスと最終読出しアドレスを上記アドレステーブルで管理する方式とした場合、同一の出力回線に向かう多数の可変長パケットが受信された場合でも、各パケットを確実に転送処理できる。
【００６７】
また、第２実施例で示したように、同一可変長パケットのリンクド・アドレスを複数の出力キューに登録し、同一データブロックの読出し回数が指定値に達した時点で読出しアドレスを開放することによって、共通バッファメモリを有効に利用したマルチキャスト転送が可能となる。
【００６８】
【発明の効果】
以上の説明から明らかなように、本発明によれば、入力回線から受信した可変長パケットを固定長のデータブロックに分割し、固定長のブロック単位で共通バッファメモリに蓄積しておき、可変長パケットの最後のデータブロックが蓄積された時点で、共通バッファメモリ内に蓄積済みのデータブロック列を移動することなく、上記データブロック列を読み出すためのリンクド・アドレスリストのみを出力キューに移す構成となっているため、可変長パケットの高速スイッチングが可能となる。また、同一リンクド・アドレスリストを複数の出力キューに登録することによって、容易にマルチキャスト機能を実現できる。
【図面の簡単な説明】
【図１】本発明を適用したパケットスイッチの１実施例を示す図。
【図２】図１に示したパケットスイッチのバッファ制御部３０の詳細を示す図。
【図３】共通バッファメモリ２２に蓄積されるデータブロックと、次アドレスメモリ３４０および入力キュー・アドレステーブル３００の状態を説明するための図。
【図４】可変長パケットの最後のデータブロックが到着した場合の入力キュー・アドレステーブル３００と出力キュー・アドレステーブル３１０との関係を説明するための図。
【図５】出力キューが使用状態にある時に他の可変長パケットの最後のデータブロックが到着した場合の入力キュー・アドレステーブル３００と出力キュー・アドレステーブル３１０との関係を説明するための図。
【図６】図２に示した入力キュー制御部３２の１実施例を示す図。
【図７】図２に示した出力キュー制御部３３の１実施例を示す図。
【図８】図２に示した次アドレス管理部３４の１実施例を示す図。
【図９】マルチキャスト用バッファ制御部３０Ｂの１実施例を示す図。
【図１０】図９における読出しアドレス解放制御部３５の１実施例を示す図。
【図１１】本発明を適用したパケットスイッチの他の実施例を示す図。
【符号の説明】
１：パケットスイッチ、１０：入力回線インタフェース、
２０：出力回線インタフェース、２１：多重化部、２２：共通バッファメモリ、
２３：分離部、２４：入力カウンタ、２５：出力カウンタ、
３０、３０Ｂ：バッファ制御部、ＬＩ：入力回線、ＬＯ：出力回線、
３１：ヘッダ解析部、３２：入力キュー制御部、３３：出力キュー制御部、
３４：次アドレス管理部、３５：空きアドレスＦＩＦＯ、３６：読出しアドレス解放制御部、３００：入力キュー・アドレステーブル、
３０１（ＢＡ１〜ＢＡｎ）：パケット先頭アドレス、
３０２（ＷＡ１〜ＷＡｎ）：最新アドレス、
３１０：出力キュー・アドレステーブル、
３１１（ＲＡ１〜ＲＡｎ）：次読出しアドレス、
３１２（ＥＡ１〜ＥＡｎ）：最終読出しアドレス、
３１３（Ｆ１〜Ｆｎ）：キューフラグ。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a packet switch applied as a node device in a variable-length packet communication network, and more particularly, to a common buffer type variable-length packet switch using a common buffer memory as a memory for temporarily storing received packets. About.
[0002]
[Prior art]
2. Description of the Related Art In recent years, an Internet protocol (Internet Protocol: hereinafter referred to as IP), which has attracted attention, performs message transfer using a variable length packet (IP packet) called an IP datagram as a transfer unit. In a conventional node device constituting an IP packet network, switching of a received packet to a destination route is performed by software processing. However, in response to a request for high-speed switching, a fixed-length packet (data There has been proposed an apparatus configuration that performs switching using a block as a transfer unit.
[0003]
For example, "A 50-Gb / s IP Router" (Craig Partridge et al., IEEE / ACM TRANSACTIONS ON NETWORKING, Vol.6, No.3, June 1998) is a node device that transfers IP packets at high speed. Includes a plurality of line cards (boards) each supporting a plurality of network interfaces and a forwarding engine card with a routing table, for example, a point-to-point type represented by a crossbar switch Each line card transmits a data block including the header portion of the received packet to the transfer engine, and the data block including new header information updated by the transfer engine is transmitted to the line card on the packet input side. Each line card on the input side returns and transfers the data block including the new header information and the remainder of the packet to the output line card. The configuration of the router device was so that has been proposed.
[0004]
According to the above paper, each line card on the input side disassembles and sends out packets into 64 byte unit chained pages (data blocks), and each line card on the output side represents these pages as packets. Assembling into a linked list, passing the assembled packet to a QoS processor, which places the packet in the appropriate position in the transmit queue based on the packet length, destination and flow identifier specified by the forwarding engine Has been.
[0005]
As a switching device having a fixed packet transfer unit, an ATM (Asynchronous Transfer Mode) switch can be mentioned. In the ATM switch, a 53-byte fixed-length packet (ATM cell) received from each input line is temporarily stored in the buffer memory, and then the storage cell is specified by connection identification information (VPI / VCI) included in the cell header. Routed to the output line.
[0006]
In the ATM switch, if a common buffer type structure in which a buffer memory is shared by a plurality of input lines is adopted, a variable length queue can be formed for each output line in the buffer memory. Even if received from multiple input lines at the same time, as long as there is free space in the entire common buffer, it is possible to buffer the received cells from each input line without discarding them, effectively using memory resources. A switch can be realized.
[0007]
Japanese Patent Laid-Open No. 11-261484 proposes a switching device for variable length messages that takes advantage of the common buffer memory. In the above prior art, the common buffer memory is divided into a plurality of memory blocks corresponding to messages, one empty memory block is allocated to each received message, and a message received from each input line is divided into a plurality of fixed lengths. The cell is divided into cells, and cells belonging to the same message are sequentially stored in the same memory block.
[0008]
[Problems to be solved by the invention]
In the router device described in the IEEE document described above, the input side line card negotiates with the output side line card via the switch allocator prior to transmission of each packet, and the output side card acknowledges reception of the packet. In this case, since transmission is started, there is a problem in the packet switching processing speed. Further, each line card on the input side needs a buffer for waiting for a packet, and each line card on the output side also needs a buffer for assembling the packet. .
[0009]
On the other hand, in the switching device described in Japanese Patent Application Laid-Open No. 11-261484, when the tail part of each message is input, all cells stored in the memory block corresponding to the received message are stored in another memory area ( Therefore, there is a problem in the time required to transfer messages between the memory areas and the efficiency of using the buffer memory.
[0010]
An object of the present invention is to provide a packet switch that can efficiently switch a variable-length packet by efficiently using a common buffer memory.
Another object of the present invention is to provide a packet switch that efficiently uses a common buffer memory and enables multicast of variable-length packets.
[0011]
[Means for Solving the Problems]
In order to achieve the above object, a packet switch of the present invention includes a common buffer memory shared by a plurality of input lines, and the common buffer memory by multiplexing received packets from each input line in units of fixed-length data blocks. And a buffer control means for controlling writing and reading of each fixed-length data block to and from the common buffer memory, and the buffer control means outputs each fixed data output from the multiplexing means. When the long data block is written to the common buffer, an input queue for each variable length packet is formed, and when the last data block of the variable length packet is registered in the input queue, the input queue is transferred to the variable length packet destination. It is registered in an output queue corresponding to the output line.
[0012]
More specifically, the buffer control means forms a plurality of input queues by linking the write address of each fixed-length data block in the common buffer memory for each variable-length packet, and the last fixed-length data of the variable-length packet. First control means for registering an input queue whose block has been written to the common buffer memory in an output queue having a standby buffer corresponding to the transfer destination output line, and a plurality of output queues formed corresponding to the output line Second control means for accessing in a predetermined order and reading out the fixed-length data block from the common buffer memory based on the linked address indicated by each output queue.
The input queue for each variable length packet, for example, writes each fixed length data block to the common buffer memory based on the write address fetched from the free address memory, and the next variable in the same variable length packet corresponding to each write address. Is formed by storing the write address of the fixed length data block in the next address memory.
[0013]
In the present invention, each output queue includes, for example, a standby buffer for temporarily storing the write address of the first data block and the write address of the last data block of the variable-length packet, and the next data block to be read next An address memory for storing a read address and a final read address indicating the last data block. The first control means transfers the write address of the first data block and the write address of the last data block of each variable length packet. When the address memory associated with the destination output line is registered in the standby buffer and the associated address memory becomes empty, the second control means sets the pair of addresses fetched from the standby buffer to a new data block group. Address memo as next read address and last read address It is set to. In this case, the second control means reads the fixed length data block and the address of the next fixed length data block from the common buffer memory and the next address memory, respectively, based on the next read address registered in each output queue, By using the address read from the next address memory as a new next read address in the output queue, it is possible to read data blocks constituting each variable-length packet one after another.
[0014]
If the received packet is a multicast packet, the first control means registers the same input queue in a plurality of output queues corresponding to the multicast output line when the last data block is written to the common buffer memory. Thus, multicast transfer is possible. In this case, the common buffer memory is provided with an address release control means for counting the number of reads of each fixed-length data block in the common buffer memory and releasing the read address when the number of reads reaches a specified value in the packet switch. Can manage free addresses.
[0015]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 1 shows an embodiment of a packet switch according to the present invention.
The packet switch 1 divides the variable-length packet 100 input from the input lines LI-1 to LI-n into a plurality of fixed-length data blocks 110, and outputs a plurality of data blocks with an internal header 110A added thereto. Input line interfaces 10-1 to 10-n, a multiplexing unit 21 that time-division-multiplexes the data blocks input from the input line interfaces 10-1 to 10-n and outputs them to the signal line L21, and the signal A common buffer memory 22 connected to the line L21; a separation unit 23 that sequentially distributes the data blocks read from the common buffer memory 22 to the signal line L22 to a plurality of output line interfaces 20-1 to 20-n; A buffer control unit 30 for controlling writing and reading of data blocks to and from the common buffer memory 22; An input counter 24 which generates the input line selection signal by counting the clock CLK0 indicating a cycle, and an output counter 25 for generating an output line selection signal by counting the clock CLK1 indicating a read cycle.
[0016]
A variable length packet input from each input line LI-i (i = 1 to n) includes a packet header 100A including a destination address and a data portion 100B. Each input line interface 10-i (i = 1 to n) divides the variable-length packet 100 received from the input line LI-i into a plurality of fixed-length data blocks 110, for example, an input line number and a packet header. An internal header 110A including an output line number determined by a destination address extracted from 100A and block position display information indicating whether each data block 110 corresponds to a head block, an intermediate block, or a last block in a variable-length packet. It is generated and added to each data block for output.
[0017]
Writing and reading data blocks to and from the common buffer memory 22 are performed alternately according to clocks CLK0 and CLK1. The multiplexing unit 21 cyclically selects the input line interfaces 10-1 to 10-n according to the input line selection signal generated on the signal line L24 by the input counter 24, and the data output from each input line interface The blocks 110 are sequentially multiplexed on the signal line L21. On the other hand, the separation unit 23 outputs the data block read from the common buffer memory 22 to the signal line L22, and the output line interface 20-j (j specified by the output line selection signal generated by the output counter 25 on the signal line L25. = 1 to n).
The output line interfaces 20-1 to 20-n remove the internal header 110A from the data block 110 received from the separation unit 23, and send it to the corresponding output lines LO-1 to LO-n.
[0018]
The buffer control unit 30 writes the data block to the common buffer memory 22 while forming a linked address list corresponding to the input line number i indicated by the internal header 110A appearing on the signal line L21 in each write cycle indicated by the clock CLK0. .
As will be described later, the buffer control unit 30 forms a new input queue corresponding to the input line each time the first block of the received packet appears on the signal line L21, and the data of the subsequent intermediate block and the final block are input line compatible. In order to link the input queue to the output queue corresponding to the transfer destination output line of the received packet when the last block of the received packet is written in the common buffer memory 22 one after another. Dynamically control the address list.
[0019]
Reading of the data block from the common buffer memory 22 is performed based on an output queue address list formed corresponding to each output line. The buffer control unit 30 checks whether or not there is a data block to be read for the output queue corresponding to the output line selection signal given by the signal line L25. If the data block address is linked to the output queue, the buffer control unit 30 outputs The next read address registered in the queue address list is used as the read address RA, one data block is read from the common buffer memory 22 to the signal line L22, and the next read address in the address list is the next data block address in the linked address list. Rewrite to
[0020]
FIG. 2 is a block diagram showing details of the buffer control unit 30.
The buffer control unit 30 includes a header analysis unit 31, an input queue control unit 32, an output queue control unit 33, a next address management unit 34, and an empty address memory (FIFO) for storing free addresses of the common buffer memory 20. 35).
[0021]
The header analysis unit 31 analyzes the internal header of each data block appearing on the signal line L21, and determines whether the input line number IN-i, the output line number OUT-j, and the input data block are the first block of the received packet. And a final display flag signal EP indicating whether or not the input data block is the final block of the received packet.
For each input line, the input queue control unit 32 addresses the head data block registered in the input queue (packet head address: BAi (i = 1 to n)) 301 and the latest data block registered in the input queue. Input queue address table 300 indicating the latest address (latest address: WAi (i = 1 to n)) 302.
The output queue control unit 33 includes an output queue / address table 310 and an output standby buffer 330.
[0022]
The output queue address table 310 includes, for each output line, a data block read address (next read address RAj (j = 1 to n)) 311 positioned at the head of the output queue and a data block positioned at the end of the output queue. Read address (final read address EAj (j = 1 to n)) 312 is stored. In the following description, a table area corresponding to the j-th output line LO-j in the output queue / address table 310 is denoted by reference numeral 310-j.
[0023]
When the addresses RAj and EAj for reading the preceding packet remain in the output queue address table 310-j, the output standby buffer 330 waits in the FIFO format for the read address of the subsequent packet to be sent to the same output line. Corresponding to each output line, a buffer area 330B-j for accumulating the read address BAj of the first data block of the packet and a buffer for accumulating the read address WAj of the last data block of the packet An area 330W-j is prepared. The read addresses stored in the buffer areas 330B-j and 330W-j are read when all the data blocks of the preceding packet are read from the common buffer memory, and the output queue address table becomes substantially empty. It is moved to the table area 310-j of the output queue address table.
[0024]
The next address management unit 34 includes a next address memory 340 including a plurality of address storage areas NA1 to NAm equal to the number m of data blocks that can be stored in the common buffer memory 22. Each storage area of the next address memory 340 is used to form a linked address list for reading out the data block sequence registered in the input queue in the order of registration.
[0025]
Hereinafter, assuming that variable length packets directed to the same output line LO-3 are input from the input lines LI-1 and LI-2, the packet head address BA1 of the input queue corresponding to the input line LI-1 and Focusing on the latest address WA1, the packet start address BA2 and latest address WA2 of the input queue corresponding to the input line LI-2, the next read address RA3 and the final read address EA3 of the output queue corresponding to the output line LO-2 The function of the buffer control unit 30 will be described in detail with reference to FIGS. 2 and 3 to 5.
[0026]
The header analysis unit 31 analyzes the internal header 110A of each data block output to the signal line L21, and generates an input line number IN-i and an output line number OUT-i. If the data block is the first block of the variable-length packet, the first display flag signal FP is turned on. If the data block is the last block, the last display flag signal EP is turned on.
The data block output to the signal line L21 is written into the common buffer memory 20 using the empty address taken out from the empty address FIFO 35 as the write address WA. At this time, the input queue control unit 32 updates the input queue / address table 300 according to the state of the input line number IN-i output from the header analysis unit 31 and the head display flag signal FP.
If the head display flag signal FP is in the ON state, the write address WA extracted from the empty address FIFO 35 is written as the packet head address BAi and the latest address WAi in the table area 300-i corresponding to the input line number IN-i. If the head display flag signal FP is in the OFF state, the write address WA is written to the latest address WAi.
[0027]
When a new address WA is written in the input queue / address table 300, the address stored so far as the latest address WAi is output to the next address management unit 34. The next address management unit 34 stores the new write address WA extracted from the empty address FIFO 35 in the storage area NAi corresponding to the address WAi.
As a result, each time a fixed-length data block divided from one variable-length packet is written into the common buffer memory 22, the write address of the data block is stored in the next address memory 340, and the latest address WAi is updated. Eventually, the packet head address BAi points to the address of the head data block of the variable length packet, and the latest address WAi points to the address of the last data block of the variable length packet.
[0028]
FIG. 3 shows data blocks D1-1 to D1-4 output from the input line interface 10-1 and data blocks D2-1 to D2-2 output from the input line interface 10-2 in the common buffer memory 22. The state of the input queue / address table 300 at the time when is written is shown.
Here, WA1-1 to WA1-4 are values of the write address WA of the data blocks D1-1 to D1-4 obtained from the empty address FIFO 35, and WA2-1 to WA2-2 are data blocks D2-1 to D2. -2 indicates the value of the write address WA. RA3 and EA3 indicate the contents of the output queue / address table entry 310-3 corresponding to the transfer destination output line LO-3 of the data blocks D1-1 to D1-4 and D2-1 to D2-2. Yes.
[0029]
In the input queue address table corresponding to the input line LI-1, the write address WA1-1 of the head data block D1-1 is stored as the packet head address BA1, and the contents of the latest address WA1 are updated each time the data block is written. And WA1-1, WA1-2, WA1-3, and WA1-4.
In the next address memory 340, as shown in FIG. 3, the write address of the next data block is successively stored in the storage area corresponding to the latest address WA1. Therefore, a linked address list for each input line is formed by the packet head address BA1 of the input queue address table 300 and the next address memory 340.
[0030]
For example, by accessing the common buffer memory 22 and the next address memory 340 based on the address WA1-1 indicated by the packet head address BA1, the addresses WA1-2 of the head data block D1-1 and the next data block D1-2 are accessed. By using this address WA1-2 as the read address RA in the next read cycle, the next data block D1-2 and further the address WA1-3 of the next data block D1-3 By repeating the same operation, all data blocks registered in the input queue can be read.
[0031]
As with the input line LI-1, in the input queue address table corresponding to the input line LI-2, the write address WA2-1 of the head data block D2-1 is stored as the packet head address BA2, and the contents of the latest address WA1 are The data block is updated each time the data block is written, and changes to WA2-1, WA2-2,.
[0032]
FIG. 3 shows a state before the input line interfaces 10-1 and 10-2 output the final data block of the variable length packet, and there is no valid data in the output queue corresponding to the output line LO-3. The output standby buffer 330-3 and the output queue / address table 310-3 are empty.
In the present invention, when the last data block of a packet is written in the common buffer memory 22, the buffer control unit 30 outputs the packet head address BAi and the latest address WAi (= WA) in the input queue of the last data block as an output standby buffer. It is characterized in that it is transferred to the output queue address table 310 via 330.
[0033]
FIG. 4 shows the operation of the buffer control unit 30 when the final data block D1-5 of the variable-length packet output from the input line interface 10-1 is written into the common buffer memory 22.
In this case, after storing the write address WA1-5 of the final data block D1-5 in the next address memory 340, the buffer control unit 30 then stores the contents (WA1-1) of the packet head address BA1 of the input queue and the latest address WA1. The contents (WA1-5) are moved to the output standby buffer 330-3. The address stored in the output standby buffer 330-3 is moved to RA3 and EA3 in the output queue address table as shown in FIG. 4 if the output queue address table 310-3 is empty. . Since the contents of the latest address WA1 are the new write address WA extracted from the empty address FIFO 35 this time, the empty address FIFO 35 is substituted for the latest address WA1 in the EA3 of the output queue address table. The write address WA taken out from may be stored.
[0034]
FIG. 5 shows a buffer when the final data block D2-3 of the variable length packet output from the input line interface 10-2 is written in the common buffer memory 22 when the output queue of the output line LO-3 is already in use. The operation of the control unit 30 is shown. In this case, after storing the write address WA2-3 of the final data block D2-3 in the next address memory 340, the buffer control unit 30 then stores the contents (WA2-1) of the packet start address BA2 of the input queue and the latest address WA2. The contents (WA2-3) are moved to the output standby buffer 330-3.
The addresses WA2-1 and WA2-3 stored in the output standby buffer 330-3 are the values of the next read address RA3 and the last read address EA3 when the output queue / address table 310-3 becomes empty. Are read cycles in which they match, the data is moved to the output queue address table 310-3.
[0035]
When the variable-length packet received by the line interface is short and the entire received packet fits in one fixed-length data block, the head display flag signal FP and the final display flag signal FP output from the header analysis unit 31 are written in this data block write cycle. The display flag signal EP is simultaneously turned on. In this case, the contents of the packet head address BAi and the latest address WAi registered in the input queue address table 300 in response to the head display flag signal FP are stored in the output standby buffer 330-j in response to the last display flag signal EP. Immediately moved.
[0036]
If the contents of the packet head address BAi and the latest address WAi stored in the standby buffer 330-j are empty when the output queue of the output line LO-j to which the data block is transferred is empty, as in FIG. If it is written in the output queue address table 310-j and the output queue is already in use, it remains in the output standby buffer 330-j, as in FIG.
[0037]
Reading of the data block from the common buffer memory 22 is performed by the output queue control unit 33. The output queue control unit 33 refers to the output queue / address table area 310-j specified by the output line selection signal output to the signal line L25 in the read cycle, and reads data from the common buffer memory 22 according to the next read address RAj. The block is read and the next address NAj is read from the next address memory 340.
The used next read address RAj is released to the free address FIFO 35, and the next address NAj read from the next address memory 340 is stored in the output queue / address table 310-j as a new next read address RAj. The However, in the read cycle of the last data block of each packet, the next address NAj read from the next address memory 340 becomes invalid, and the start address of the next packet fetched from the standby buffer becomes the output queue as the next read address RAj. Set in the address table 310-j.
[0038]
FIG. 6 shows an embodiment of the input queue control unit 32.
The input queue control unit 32 includes registers 301-1 to 301-n for storing the packet head addresses BA1 to BAn, registers 302-1 to 302-n for storing the latest addresses WA1 to WAn, and header analysis. Decoder 311, which decodes input line number IN-i received from unit 31 and turns on one of enable signals WEN-1 to WEN-n, and output addresses from registers 302-1 to 302-n A selector 322 for selecting one of the registers, a selector 323 for selecting one of the output addresses from the registers 301-1 to 301-n, and a write enable signal for the packet head address. AND circuits 324-1 to 324-n for the purpose.
[0039]
The registers 302-1 to 302-n for storing the latest addresses are supplied with the address WA taken out from the empty address FIFO 35, and the latest signals are sent by the enable signals WEN-1 to WEN-n output from the decoder 321, respectively. Address update is controlled. When the input line number IN-i indicates the i-th input line, the enable signal WEN-i is turned on, and the address WA extracted from the empty address FIFO 35 is set in the register 302-i. At this time, the write address {WAi} of the previous data block previously stored in the register 302-i is selected by the selector 322 and supplied to the next address management unit 34 as the next address (pointer address) write address WAi. .
[0040]
The address WA extracted from the empty address FIFO 35 is also input to registers 301-1 to 301-n for storing the packet head addresses BA1 to BAn. Writing to these registers is controlled by AND circuits 324-1 to 324 -n, and the input line number IN is limited only to the writing cycle in which the head display flag FP output from the header analysis unit 31 is turned on. The address WA is written to the register 301-i corresponding to -i. The selector 323 selects the output address from the register 301-i corresponding to the input line number IN-i, and outputs it as the packet head address BAi.
[0041]
FIG. 7 shows an embodiment of the output queue control unit 33.
The output queue control unit 33 includes registers 311-1 to 311-n for storing next read addresses RA1 to RAn, registers 312-1 to 312-n for storing final read addresses EA1 to EAn, a packet It consists of output standby buffers (FIFOs) 330B-1 to 330B-n for head addresses and output standby buffers (FIFOs) 330W-1 to 330W-n for final packet addresses.
[0042]
The output queue control unit 33 includes a selector 331 for selecting one of the output addresses from the registers 311-1 to 311-n and the output address from the registers 312-1 to 312-n. , A selector 332 for selecting one of the registers, a selector 333 for selecting one of the output flags from the registers 313-1 to 313-n, and an output output from the output counter 25 to the signal line 25. The decoder 334 for decoding the line selection signal and the output line number OUT-j output from the header analysis unit 31 are decoded, and one of the enable signals EN-1 to EN-n is turned on. When the final display flag signal EP output from the decoder 335 and the header analysis unit 31 is turned on, the enable signals EN-1 to EN-n The AND circuits 336-1 to 336-n for enabling are compared with the read address RAj output from the selector 331 and the packet final address EAj output from the selector 332. When the RAj and EAj match, the enable circuit The comparator 315 that turns on the signal EN-0 and the next address NAj output from the next address manager 34 when the enable signal EN-0 is off are supplied to the registers 311-1 to 311-n. An AND circuit 316 and AND circuits 339-1 to 339-n for passing an output signal of the decoder 334 when the enable signal EN-0 is in an ON state are provided.
[0043]
The output standby buffers 330-j (330B-j and 330W-j, j = 1 to n) are supplied with the output signals of the AND circuits 36-1 to 336-n as the write enable signal WEN, respectively. In the write cycle, when the final display flag signal EP is turned on, the write enable signal WEN from the AND circuit 336-j corresponding to the output line number OUT-j becomes valid, and the input queue control is performed in the buffer area 330B-j. The packet head address BAi output from the unit 32 is set, and the write address WA output from the empty address FIFO 35 is set in the buffer area 330W-j.
[0044]
The output standby buffers 330-j (330B-j and 330W-j) are supplied with the output signals of the AND circuits 339-1 to 339-n as read enable signals REN, respectively. In the read cycle, when the output signal EN-0 of the comparator 315 is turned on, the output signal of the AND circuit 339-j corresponding to the output line number OUT-j is turned on. As a result, one set of addresses BAj and WAj is read from the buffer areas 330B-j and 330W-j, and set in the registers 311-j and 312-j as the next read address RAj and the final read address EAj, respectively.
[0045]
The outputs of the decoder 334 are given to the registers 311-1 to 311-n as read enable signals, and these register outputs are sent to the selector 331 which uses the output line selection signal supplied from the signal line L25 as a control signal. It is connected. Accordingly, in each read cycle, the contents of the register 311-j designated by the output line selection signal are output as the next read address RAj. The data block to be output to the output line LOj is read from the common buffer memory 22 by the address RAj and supplied to the output line interface 20-j via the separation unit 23. Further, the address NAj indicating the next data block to be output to the output line LOj is read from the next address management unit 34 by the address RAj. The address NAj is supplied to the registers 311-1 to 311-n via the AND circuit 316.
[0046]
Similar to the registers 311-1 to 311-n, the outputs of the decoder 334 are also supplied to the registers 312-1 to 312-n as read enable signals, and these register outputs receive the output line selection signal as a selection signal. Is connected to the selector 332. As a result, in each read cycle, the contents of the register 312-j specified by the output line selection signal are output from the selector 332 as the final read address EAj.
[0047]
The output signal EN-0 of the comparator 315 is output when the next read address RAj output from the selector 331 matches the final read address EAj output from the selector 332, that is, the read cycle of the last data block of each packet. The packet head address BAi in the output standby buffer 330B-j is moved to the register 311-j as described above. In a read cycle in which the output signal EN-0 of the comparator 315 is turned off, that is, in a read cycle of the first data block or intermediate data block of the packet, the AND circuit 316 is opened and read from the next address management unit 34. The next address NAj is set in the register 311-j. As a result, the data blocks in the output queue corresponding to the output line LO-j can be read one after another.
[0048]
FIG. 8 shows an embodiment of the next address management unit 34.
The next address management unit 34 is supplied from the registers 340-1 to 340 -m for storing the next addresses NA 1 to NAm, the selector 341 for selecting output addresses from these registers, and the input queue control unit 32. The decoder 344 decodes the latest address WAi and gives a write enable signal to the register 340-i corresponding to the latest address WAi.
[0049]
In each write cycle, the next address management unit 34 stores the write address WA of the latest data block in the storage area (register 340-k) corresponding to the write address WAi of the previous data block in the input queue. The linked address list for each input queue shown in FIG. In the read cycle, the selector 341 selects the register 340-p corresponding to the read address RAj supplied from the output queue control unit 33, and performs output queue control using the address stored in the register 340-p as the next address NAj. Return to section 33. The next address NAj is stored in the register 311-j as a new next read address RAj to be used in the next read cycle in the output queue control unit 33.
[0050]
FIG. 9 shows a configuration of a buffer control unit 30B of a packet switch having a broadcast function (or multicast function) for transferring the same received packet to a plurality of output lines as a second embodiment of the present invention.
The buffer control unit 30B shown here is similar to the buffer control unit 30 of the first embodiment shown in FIG. 2, and includes a header analysis unit 31, an input queue control unit 32, an output queue control unit 33, a next address management unit 34, A free address FIFO 35 is provided, and a read address release control unit 36 is provided as a new element.
[0051]
In each input line interface 10-i (i = 1 to n), when the received packet from the input line LI-i is a broadcast (multicast) packet to be transferred to a plurality of output lines, it is obtained by dividing the received packet. An internal header designating a plurality of output lines is added to each data block. In order to specify a plurality of output lines simultaneously, for example, the output line number field of the internal header is composed of n bits corresponding to the output lines LO-1 to LO-n, and the output line serving as the packet transfer destination is set to bit A bit pattern format represented by 1 ″ may be employed.
[0052]
The header analysis unit 31 analyzes the internal header of each data block output from the multiplexing unit 21 to the signal line L21, and inputs line number IN-i, output line number OUT-j, head display flag signal FP, and final display. The flag signal EP and the number NTR of transfer destination output lines of the received packet are generated. As the output line number OUT-j, the bit pattern indicated by the output line number field of the internal header described above is output. In this case, the transfer destination output line number NTR indicates the number of bits “1” included in the output line number field.
[0053]
Each data block output from the multiplexing unit 21 to the signal line L21 is accumulated in the common buffer memory 22 with the address WA taken out from the empty address FIFO 35 as a write address, as in the first embodiment, and the input queue control unit 32 Then, the next address management unit 34 forms an input queue corresponding to the input line number IN-i.
When the data block stored in the common buffer memory 22 is the last data block of the variable-length packet, the final display flag signal EP is turned on, so the packet head address BAi output from the input queue control unit 32 and the free address The latest address WA (= WAi) extracted from the FIFO 35 is set in the output standby buffer 330 of the output queue control unit 33.
[0054]
In the output queue control unit 33 shown in FIG. 7, when the output line number OUT-j input to the decoder 335 has a bit pattern representing the transfer destination output line by the bit “1”, it is output from the decoder 335. The enable signal group can be turned on according to the bit pattern. The enable signals EN-1 to EN-n output from the decoder 335 pass through the AND circuits 336-1 to 336-n and output standby buffers 330-1 (when the final display flag signal EP is turned on. 330B-1, 330W-1) to 330-n (330B-n, 330W-n) are provided as the write enable signal WEN.
[0055]
When the last data block belongs to a unicast packet, only one enable signal EN-j corresponding to the output line of the unicast packet is turned on, so that the addresses BAi and WA are the same as in the first embodiment. The specific output standby buffers 330B-j and 330W-j to which the enable signal EN-j is applied are set. If the last data block belongs to the broadcast packet, a plurality of enable signals EN-j (j = j1, j2, j3,...) Corresponding to the bit pattern of the output line number OUT-j are simultaneously turned on. Therefore, the addresses BAi and WA are simultaneously set in the plurality of output standby buffers 330B-j and 330W-j (j = j1, j2, j3,...) To which the ON state enable signal is given. Become.
[0056]
The addresses BAi and WA set in the output standby buffers 330-1 to 330-n are the next read address registers 311-1 to 311-n and the final read address registers 312-1 to 312- The data block is read from the common buffer memory 22 in accordance with the read address RAj indicated by the next read address registers 311-1 to 311-n. As described above, since the linked address list is registered in a plurality of output queues for the data block belonging to the broadcast packet, the same data block is repeatedly read out a plurality of times.
[0057]
In the first embodiment targeting only unicast packets, the read address RAj may be released to the free address FIFO 35 when the data block is read from the common buffer memory 22 as shown in FIG. On the other hand, when handling a broadcast packet as in the present embodiment, it is necessary to confirm that multicasting to a plurality of designated output lines has been completed and to release the read address RAj to the free address FIFO 35. There is.
[0058]
The read address release control unit 36 confirms the completion of multicast for each data block and releases the read address RAj.
FIG. 10 shows an embodiment of the read address release control unit 36.
The read address release control unit 36 shown here includes registers (memory areas) 360-1 to 360-m for storing the read count RC of the data block corresponding to the write address WA, and the registers 360-1 to 360-1 described above. Selectors 361-1 to 361-m for selecting an input to 360-m and subtractors 362-1 to 362-m for decrementing (-1) the values of the registers 360-1 to 360-m. The decoder 363 which decodes the write address WA and the read address RAj and generates an enable signal corresponding to these addresses, and the register 360-q corresponding to the read address RAj among the registers 360-1 to 360-m. , A selector 364 for selecting a set value (number of read times RC), a comparator 365 and a gate 366. To have.
[0059]
Each selector 361-k (k = 1 to m) is supplied with a clock CLK0 indicating a write cycle as a selection control signal, and the transfer destination output line number NTR output from the header analysis unit 31 is selected in the write cycle. In the read cycle, the outputs of the subtracters 362-k (k = 1 to m) are selected and input to the read count registers 360-k (k = 1 to m), respectively. The output of the decoder 363 is given as a write enable signal to the read count registers 360-1 to 360-m, and in the write cycle, the output line number NCP is set in the register 360-p corresponding to the write address WA. In the read cycle, the value of the register 360-q corresponding to the read address RAj is selected by the selector 364 and input to the comparator 365. At this time, the value of the register 360-q is input to the subtractor 362-q, and the value obtained by decrementing the read count RCq (-1 operation) is reset in the register 360-q.
[0060]
For example, in the write cycle of the data block belonging to the unicast packet, the value (= 1) of the transfer destination output line number NTR is set as the read count RCp in the read count register 360-p corresponding to the write address WA. When the data block is read according to the address RAj in the read cycle, RCp = 1 is input to the comparator 365. The comparator 365 opens the gate 366 and releases the read address RAj to the free address FIFO 35 when the value of the read count RCp of the data block read from the common buffer memory 22 becomes “1”. Therefore, the write address (read address RAj) of the data block belonging to the unicast packet is immediately released every time the data block is read.
[0061]
In the write cycle of the data block belonging to the broadcast (multicast) packet, NTR having a value larger than “1” is set as the read count RCp in the read count register 360-p corresponding to the write address WA. Therefore, even if the data block is read from the common buffer 22, the gate 366 remains closed as long as the decremented RCp value does not reach “1”, and the number of readings specified by the NTR (RCp = At 1), the free address FIFO 35 of the read address RAj is released.
[0062]
In the above embodiment, the buffer control unit 30 forms an input queue for each input line number, and moves the linked address list of the input queue to the output queue when the last data block of the variable length packet arrives. However, in the present invention, each input queue only needs to be formed for each variable length packet, and therefore, other identification information unique to each variable length packet may be used instead of the input line number.
In the embodiment, the input line number is set in the internal header of each data block, and the header analysis unit 31 outputs the input line number IN-j based on the internal header. The input line number IN-j is an input counter. It may be generated based on an input line selection signal output from the output 24.
[0063]
In the above-described embodiment, each input line interface 10-i (i = 1 to n) divides the received packet 100 into a plurality of fixed-length data blocks 110 and attaches an internal header 110A to each data block. Is output to the multiplexer 21 and the data block with the internal header is read and written to the common buffer memory 22, but as another embodiment of the present invention, for example, as shown in FIG. The multiplexing unit 21 separates the data block 110 and the internal header 110A, the internal header 110A is supplied to the header analysis unit 31 of the buffer control unit 30, and only the data block 110 part is input to the common buffer memory 22. Also good.
According to the above configuration, the memory capacity of the common buffer memory 22 can be used effectively, and it is not necessary to remove the internal header from the data block at each output line interface 20-i.
[0064]
As still another embodiment of the present invention, each input line interface 10-i outputs the fixed-length data block 110 to the multiplexing unit 21 without adding an internal header, and the header analysis unit 31 of the buffer control unit 30 The packet header included in the head data block of each variable-length packet is analyzed, the output line number and the number of subsequent data blocks are managed on the management table for each input line, and the input line selection signal given from the input counter 24 is Accordingly, the control table such as IN-i, FP, EP, OUT-j described above may be generated by referring to the management table. Further, the conversion from the variable-length packet 100 to the fixed-length data block 110 may be performed by the multiplexing unit 21 instead of by each input line interface 10-i.
In the embodiment, the packet switch connected to a plurality of input / output lines has been described. However, the buffer control of the present invention has a switch structure (multiplexing) that outputs variable-length packets received from a plurality of input lines to one output line. (Apparatus).
[0065]
As described above, in the embodiment of the present invention, an input queue for each variable length packet is formed, and when the last data block of one variable length packet is written to the buffer memory, the linked queue registered in the input queue is registered. -The address is moved to the output queue. Therefore, even when a plurality of variable length packets directed to the same output line are input in parallel, data blocks of other packets are mixed in the data block sequence belonging to one variable length packet in the output queue. This can be prevented, and by sequentially sending the data blocks taken out from the output queue to the output line, the received packet can be correctly transferred to the destination device.
[0066]
Also, as in the embodiment, the output queue is composed of a standby buffer and an address table (or register), and the addresses of the first data block and the last data block of the variable length packet waiting for output are temporarily stored in the standby buffer. When the method of managing the next read address and the last read address of the variable length packet being output by the above address table is used, even if a large number of variable length packets directed to the same output line are received, Can be transferred.
[0067]
Also, as shown in the second embodiment, by registering linked addresses of the same variable length packet in a plurality of output queues and releasing the read address when the read count of the same data block reaches a specified value. Multicast transfer using the common buffer memory effectively becomes possible.
[0068]
【The invention's effect】
As is apparent from the above description, according to the present invention, the variable-length packet received from the input line is divided into fixed-length data blocks and stored in the common buffer memory in fixed-length block units. A configuration in which only the linked address list for reading the data block sequence is moved to the output queue without moving the data block sequence already stored in the common buffer memory when the last data block of the packet is accumulated. Thus, high-speed switching of variable-length packets is possible. Also, a multicast function can be easily realized by registering the same linked address list in a plurality of output queues.
[Brief description of the drawings]
FIG. 1 is a diagram showing an embodiment of a packet switch to which the present invention is applied.
FIG. 2 is a diagram showing details of a buffer control unit 30 of the packet switch shown in FIG. 1;
FIG. 3 is a diagram for explaining data blocks stored in a common buffer memory 22, and states of a next address memory 340 and an input queue / address table 300;
FIG. 4 is a diagram for explaining the relationship between an input queue / address table 300 and an output queue / address table 310 when the last data block of a variable-length packet arrives;
FIG. 5 is a diagram for explaining the relationship between the input queue address table 300 and the output queue address table 310 when the last data block of another variable-length packet arrives when the output queue is in use.
6 is a diagram showing an embodiment of the input queue control unit 32 shown in FIG. 2. FIG.
FIG. 7 is a diagram showing an embodiment of the output queue control unit 33 shown in FIG.
FIG. 8 is a diagram showing an example of the next address management unit shown in FIG. 2;
FIG. 9 is a diagram illustrating an example of a multicast buffer control unit 30B.
10 is a diagram showing an example of a read address release control unit 35 in FIG. 9;
FIG. 11 is a diagram showing another embodiment of a packet switch to which the present invention is applied.
[Explanation of symbols]
1: packet switch, 10: input line interface,
20: output line interface, 21: multiplexing unit, 22: common buffer memory,
23: separation unit, 24: input counter, 25: output counter,
30, 30B: buffer control unit, LI: input line, LO: output line,
31: Header analysis unit, 32: Input queue control unit, 33: Output queue control unit,
34: Next address management unit, 35: Empty address FIFO, 36: Read address release control unit, 300: Input queue address table,
301 (BA1 to BAn): packet head address,
302 (WA1 to WAn): Latest address,
310: Output queue address table,
311 (RA1 to RAn): next read address,
312 (EA1 to EAn): last read address,
313 (F1 to Fn): a queue flag.

Claims

In a packet switch that transfers variable-length packets received from a plurality of input lines to at least one output line in units of fixed-length data blocks,
A common buffer memory shared by the plurality of input lines;
Multiplexing means for multiplexing received packets from each input line in units of fixed-length data blocks and supplying the multiplexed packets to the common buffer memory;
Buffer control means for controlling the writing and reading of each fixed-length data block to the common buffer memory,
The buffer control means links the write address of each fixed length data block in the common buffer memory for each variable length packet to form a plurality of input queues, and the last fixed length data block of the variable length packet is the common First control means for registering an input queue that has been written to the buffer memory in an output queue having a standby buffer corresponding to the transfer destination output line, and a plurality of output queues formed for the output line in a predetermined order A packet switch comprising: second control means for accessing and reading a fixed-length data block from the common buffer memory based on a linked address indicated by each output queue.

The buffer control means has an empty address memory for holding an empty address in the common buffer memory, and a next address memory for storing a write address of a fixed-length data block in the common buffer memory;
The first control means writes each fixed length data block to the common buffer memory based on the write address taken out from the empty address memory, and in the same variable length packet corresponding to each write address to the next address memory. The packet switch according to claim 1, wherein the input queue is formed by storing a write address of a next fixed-length data block.

Each output queue includes a standby buffer for temporarily storing the write address of the first data block and the write address of the last data block of the variable length packet, the next read address indicating the data block to be read next, and the last data. An address memory for storing a final read address indicating a block;
The first control means registers the write address of the first data block and the write address of the last data block of the variable length packet in each input queue in the standby buffer corresponding to the transfer destination output line, and the associated address memory is empty. 3. The packet switch according to claim 2, wherein the second control unit sets a pair of addresses fetched from the standby buffer in the address memory when a state is reached.

The second control means reads out the fixed-length data block and the address of the next fixed-length data block from the common buffer memory and the next address memory, respectively, based on the next read address registered in each output queue, 4. The packet switch according to claim 2, wherein a next read address is released, and an address read from the next address memory is set as a new next read address in the output queue.

5. The packet switch according to claim 1, further comprising separation means for distributing the fixed-length data block read from the common buffer memory to a plurality of output lines.

In a packet switch that transfers variable-length packets received from a plurality of input lines to at least one output line in units of fixed-length data blocks,
A common buffer memory shared by the plurality of input lines;
Multiplexing means for multiplexing received packets from each input line in units of fixed-length data blocks and supplying the multiplexed packets to the common buffer memory;
Buffer control means for controlling the writing and reading of each fixed-length data block to the common buffer memory,
The buffer control means links the write address of each fixed length data block in the common buffer memory for each variable length packet to form a plurality of input queues, and the last fixed length data block of the variable length packet is the common The first control means for registering the input queue that has been written in the buffer memory in the output queue corresponding to the transfer destination output line, and the plurality of output queues formed for the output line are accessed in a predetermined order, and each output Second control means for reading a fixed-length data block from the common buffer memory based on a linked address indicated by a queue, wherein the first control means has one input for which the last fixed-length data block has been written. A packet switch having a function of registering a queue in a plurality of output queues.

The buffer control means has an empty address memory for holding an empty address in the common buffer memory, and a next address memory for storing a write address of a fixed-length data block in the common buffer memory;
The first control means writes each fixed length data block to the common buffer memory based on the write address taken out from the empty address memory, and in the same variable length packet corresponding to each write address to the next address memory. The packet switch according to claim 6, wherein the input queue is formed by storing a write address of a next fixed-length data block.

Each output queue includes a standby buffer for temporarily storing the write address of the first data block and the write address of the last data block of the variable length packet, the next read address indicating the data block to be read next, and the last data. An address memory for storing a final read address indicating a block;
The first control means registers the write address of the first data block and the write address of the last data block of the variable length packet in each input queue in the standby buffer corresponding to the transfer destination output line, and the associated address memory is empty. 8. The packet switch according to claim 7, wherein the second control unit sets a pair of addresses taken out from the standby buffer in the address memory when a state is reached.

The second control means reads the fixed-length data block and the address of the next fixed-length data block from the common buffer memory and the next address memory, respectively, based on the next read address registered in each output queue; 9. The packet switch according to claim 7, wherein an address read from the next address memory is set as a new next read address in the output queue.

6. The address release control means for counting the number of reads of each fixed-length data block in the common buffer memory and releasing the read address when the number of reads reaches a specified value. The packet switch according to any one of 9.