(57)【特許請求の範囲】
【請求項１】
Ｎ本の入力回線のそれぞれに対応して設けられ、対応する前記入力回線を介して入力されるユニキャストパケットおよびマルチキャストパケットを格納するＮ個の入力バッファ部と、
前記Ｎ個の入力バッファ部のそれぞれから前記ユニキャストパケットが入力された場合にはその送出先となるＭ本の出力回線の中のいずれかに前記ユニキャストパケットを出力し、前記マルチキャストパケットが入力された場合にはその送出先となる前記Ｍ本の出力回線の中の複数本に前記マルチキャストパケットを出力するスイッチ部と、
前記ユニキャストパケットについては前記入力回線と前記出力回線の両方が競合しないように、前記マルチキャストパケットについては前記入力回線が競合しないように、前記Ｎ個の入力バッファ部のそれぞれから出力する前記ユニキャストパケットあるいは前記マルチキャストパケットのいずれかを選択するスケジューラ部と、
を備え、前記スケジューラ部によって前記マルチキャストパケットについて行われるスケジューリング処理では、前記マルチキャストパケットの送出先となる複数の出力回線について競合制御を行わないことを特徴とするパケットスイッチ。
【請求項２】
請求項１において、
前記スイッチ部は、前記Ｍ本の出力回線のそれぞれに対応して前記ユニキャストパケットを格納する第１の格納部と、前記Ｎ本の入力回線のそれぞれに対応して前記マルチキャストパケットを格納する第２の格納部とを備えることを特徴とするパケットスイッチ。
【請求項３】
請求項１において、
前記スケジューラ部は、前記入力バッファ部から前記スイッチ部に前記マルチキャストパケットを入力したときに、前記マルチキャストパケットの送出先となる複数の前記出力回線について、このマルチキャストパケット以外のパケットが送出されないタイミングを確保することを特徴とするパケットスイッチ。
【請求項４】
請求項１〜３のいずれかにおいて、
前記スイッチ部が複数設けられており、
一の前記スイッチ部には、前記入力回線を介して入力される一の前記ユニキャストパケットあるいは前記マルチキャストパケットが複数単位時間かけて転送されており、
複数の前記スイッチ部を用いて、異なるパケットを並行して転送することを特徴とするパケットスイッチ。
【請求項５】
請求項４において、
複数の前記パケットが集まって一のフレームを構成している場合に、
複数の前記パケットのそれぞれには、このフレームの順番を識別する第１のシーケンス番号と、このフレーム内での前記パケットの順番を識別する第２のシーケンス番号とが付されており、
前記出力回線側で、前記第２のシーケンス番号に基づいて前記フレーム内での前記パケットの並べ替えを行うとともに、前記第１のシーケンス番号に基づいて前記フレームの並べ替えを行うフレーム組立部をさらに備えることを特徴とするパケットスイッチ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチキャスト機能を有し、入力回線を介して入力されたパケットを出力回線に振り分けるパケットスイッチに関する。
【０００２】
【従来の技術】
近年、インターネットの急激な普及により、回線の通信トラヒック量が急増しており、高速・大容量のパケットスイッチの実現が望まれている。一般に、パケットスイッチを実現するバッファ構成は、出力バッファ型、共通バッファ型、クロスポイントバッファ型、入力バッファ型に大きく分類される。スループットの観点から、従来は出力バッファ型や共通バッファ型のパケットスイッチが汎用的に用いられてきた。しかしながら、近年では回線速度が高速化し、しかも回線数が増加しており、メモリアクセス速度が比較的低速な入力バッファ型のパケットスイッチが見直されている。例えば、出力バッファ型のパケットスイッチのメモリアクセス速度は、回線速度のＮ＋１倍（Ｎは回線数）となる。共通バッファ型のパケットスイッチのメモリアクセス速度は、回線速度の２Ｎ倍となる。これに対して、入力バッファ型のメモリアクセス速度は回線速度の２倍であって、出力バッファ型や共通バッファ型の各パケットスイッチのメモリアクセス速度に比べて低速である。
【０００３】
入力バッファ型のパケットスイッチでは、一般にＨＯＬ（Head of Line）ブロッキングにより、スループットが５８．６％に低下することが知られているが、入力バッファにおけるＦＩＦＯを出力バッファ毎に論理的に分離することにより、１００％のスループットが得られることが知られている。
【０００４】
また、クロスポイントバッファ型のパケットスイッチは、メモリアクセス速度やスループットについては入力バッファ型のパケットスイッチと同等の特性を有するが、各クロスポイント毎にバッファが必要になるため、入力回線数と出力回線数をともにＮとした場合には、Ｎ×Ｎ個のバッファが必要になり、ハードウエア規模が大きくなってしまう。
【０００５】
図２８は、従来の入力バッファ型のパケットスイッチの構成を示す図である。入力回線から入力されたパケットを複数の出力回線にコピーして出力するマルチキャスト機能を実現するための構成が示されている。この構成は、「KR.Ahuja,B.Prabhakar and N.McKeown,“Multicast scheduling for input-queued switches“,IEEE J.Selected Areas Com.,May 1996.」で提案されたものである。
【０００６】
図２８に示したパケットスイッチは、ユニキャストキュー（ＵＣ queue）とマルチキャストキュー（ＭＣ queue）を有する入力バッファを備えている。マルチキャストキューから読み出されたパケットがクロスバースイッチ内でコピーされて、複数の出力回線に送られる。
【０００７】
また、図２９は従来の入力バッファ型のパケットスイッチの他の構成を示す図である。この構成は、「松岡直樹他、“A Study on Multicast Structure for Input Queued Switches”，電子情報通信学会総合大会，B-6-65,1999.」で提案されたものである。
【０００８】
図２９に示したパケットスイッチは、ユニキャストキューとマルチキャストキューを有する入力バッファを備える点は、図２８に示した構成と同じであるが、マルチキャストパケットが各入力バッファ内でコピーされて各出力回線に向けて出力される点が異なっている。
【０００９】
【発明が解決しようとする課題】
ところで、図２８に示した従来のパケットスイッチでは、各入力バッファ毎に設けられたスケジューラ、あるいは各入力バッファに共通に設けられたスケジューラは、１単位時間内に全ての入力バッファについてマルチキャストパケットのコピー先となる出力回線について競合制御を行う必要があるため、この競合制御が複雑になり、処理の負担が大きいという問題があった。このため、特に１単位時間が短く、競合数も多くなる高速・大容量のパケットスイッチには向いていない。
【００１０】
また、図２９に示した従来のパケットスイッチでは、各入力バッファ内でマルチキャストパケットがコピーされるため、実際に送受信されるパケットの数が多くなり、マルチキャストパケットに許容される入力レートが低下し、高速化が難しいという問題があった。
【００１１】
本発明は、このような点に鑑みて創作されたものであり、その目的は、マルチキャストパケットに許容される入力レートを低下させることなく、処理の負担を軽減することができるパケットスイッチを提供することにある。
【００１２】
【課題を解決するための手段】
上述した課題を解決するために、本発明のパケットスイッチは、Ｎ個の入力バッファ部とスイッチ部とスケジューラ部とを備えている。Ｎ個の入力バッファ部は、Ｎ本の入力回線のそれぞれに対応して設けられ、対応する入力回線を介して入力されるユニキャストパケットおよびマルチキャストパケットを格納する。スイッチ部は、Ｎ個の入力バッファ部のそれぞれからユニキャストパケットが入力された場合にはその送出先となるＭ本の出力回線の中のいずれかにユニキャストパケットを出力し、マルチキャストパケットが入力された場合にはその送出先となるＭ本の出力回線の中の複数本にマルチキャストパケットを出力する。スケジューラ部は、ユニキャストパケットについては入力回線と出力回線の両方が競合しないように、マルチキャストパケットについては入力回線が競合しないように、Ｎ個の入力バッファ部のそれぞれから出力するユニキャストパケットあるいはマルチキャストパケットのいずれかを選択する。ユニキャストパケットとマルチキャストパケットが混在して入力される場合に、スケジューラ部では、ユニキャストパケットについては入力回線と出力回線の両方が競合しないように、マルチキャストパケットについては入力回線が競合しないようにスケジューリング処理を行っており、マルチキャストパケットの送出先となる複数の出力回線を競合制御の対象から除外することにより、スケジューリング処理の負担を大幅に軽減することができる。また、マルチキャストパケットについては、入力バッファ部内でのコピーは行わないため、入力バッファ部とスイッチ部との間のデータ量が増加することがなく、マルチキャストパケットに許容される入力レートが低下することを防止することができる。
【００１３】
上述したスイッチ部は、Ｍ本の出力回線のそれぞれに対応してユニキャストパケットを格納する第１の格納部と、Ｎ本の入力回線のそれぞれに対応してマルチキャストパケットを格納する第２の格納部とを備えることが望ましい。ユニキャストパケット同士については出力回線の競合がないため、出力回線毎に格納部を設けることにより、それぞれの容量を低減することができる。同様に、マルチキャストパケット同士については入力回線の競合がないため、入力回線毎に格納部を設けることにより、それぞれの容量を低減することができる。
【００１４】
また、上述した入力バッファ部とスイッチ部内の第１および第２の格納部の少なくとも一方をサービス品質毎に分割することにより、優先制御を行うことが望ましい。サービス品質毎に優先制御を行うことにより、多様な通信サービスを提供することが可能になる。また、サービス品質毎にあらかじめ格納部が分割されているため、各サービス品質毎に分離した制御やパケットの格納動作が可能であり、それぞれに対して別々にパケットの格納や読み出しを行えばよいため、構造の簡略化が可能になる。
【００１５】
また、上述した第１の格納部および第２の格納部のいずれかが輻輳したときに、スイッチ部から入力バッファ部およびスケジューラ部の少なくとも一方に輻輳情報を通知することにより、入力バッファ部からスイッチ部に対するユニキャストパケットあるいはマルチキャストパケットの入力を停止することが望ましい。輻輳したときにパケットの入力を停止することにより、スイッチ部内でのパケットの廃棄を防止することができる。
【００１６】
さらに上述したように、入力バッファ部とスイッチ部内の第１および第２の格納部の少なくとも一方がサービス品質毎に分割されているときは、スイッチ部内の格納部の輻輳の通知および入力バッファ部のパケットの出力の停止をサービス品質毎に行うことが望ましい。
【００１７】
また、上述したスケジューラ部は、入力バッファ部からスイッチ部にマルチキャストパケットを入力したときに、マルチキャストパケットの送出先となる複数の出力回線について、このマルチキャストパケット以外のパケットが送出されないタイミングを確保することが望ましい。これにより、マルチキャストパケットとユニキャストパケットとがスイッチ部内で競合して、いずれかの格納部がオーバーフローしてしまう可能性を低減することができる。また、ある出力回線について選択対象から除外する制御を行うだけであるため、複雑な制御が不要であり、処理の高速化が可能になる。
【００１８】
また、上述したスイッチ部が複数設けられており、一のスイッチ部には、入力回線を介して入力されるユニキャストパケットあるいはマルチキャストパケットが複数に分割されてその一部が入力されており、複数のスイッチ部を用いて、一のパケットに対応する複数の分割データを並行して転送することが望ましい。複数のスイッチ部で並行してパケットの転送を行うことができるため、低速のスイッチ部を用いて高速転送を行うことが可能になる。
【００１９】
また、上述したスイッチ部が複数設けられており、一のスイッチ部には、入力回線を介して入力される一のユニキャストパケットあるいはマルチキャストパケットが複数単位時間かけて転送されており、複数のスイッチ部を用いて、異なるパケットを並行して転送することが望ましい。一のパケットを一のスイッチ部を用いて転送することにより、いずれかのスイッチ部に障害が発生した場合であっても、それ以外のスイッチ部を用いて正常にパケットを転送することができる。
【００２０】
また、上述した複数のパケットが集まって一のフレームを構成している場合に、複数のパケットのそれぞれには、このフレームの順番を識別する第１のシーケンス番号と、このフレーム内でのパケットの順番を識別する第２のシーケンス番号とが付されており、出力回線側で、第２のシーケンス番号に基づいてフレーム内でのパケットの並べ替えを行うとともに、第１のシーケンス番号に基づいてフレームの並べ替えを行うフレーム組立部をさらに備えることが望ましい。複数のスイッチ部を用いて複数のパケットを転送する場合であって、転送順番が逆転してしまうような場合であっても、正しいフレーム順、パケット順となるため、出力回線側において正常なフレームを組み立てることができる。
【００２１】
また、上述した複数のパケットが集まって一のフレームを構成している場合に、複数のパケットのそれぞれには、このフレームの順番を識別する第１のシーケンス番号と、このフレーム内でのパケットの順番を識別する第２のシーケンス番号とが付されており、出力回線側で、第１および第２のシーケンス番号に基づいてパケットの並べ替えを行う際に、並べ替え中のフレームの数が所定値以上になったときに、対応するスイッチ部に対して転送動作の停止を指示することが望ましい。フレームの組み立て（パケットの並べ替え）の対象となるフレーム数を所定数以下に抑えることができるため、フレーム組立を行う際の管理が容易となる。
【００２２】
また、上述した複数のパケットが集まって可変長の一のＩＰパケットを構成しており、入力回線側で、ＩＰパケットのフロー識別子を用いて、同一のスイッチ部に同一フローに属するパケットを入力することが望ましい。フローレベルでパケットの順番が逆転することを防止できるため、フレーム組立側において多くの到着パケットを格納する必要がなく、バッファ等の容量を最小限にすることができる。
【００２３】
【発明の実施の形態】
以下、本発明を適用した一実施形態のパケットスイッチについて詳細に説明する。
〔第１の実施形態〕
図１は、本発明を適用した第１の実施形態のパケットスイッチの構成を示す図である。図１に示すように、本実施形態のパケットスイッチは、Ｎ個の入力バッファ部１００、スケジューラ部２００、クロスバースイッチ部３００、Ｍ個のフレーム組立バッファ部４００、Ｍ個のフレーム化処理部５００を含んで構成されている。
【００２４】
Ｎ個の入力バッファ部１００は、Ｎ本の入力回線＃１〜＃Ｎのそれぞれに対応して設けられており、対応する入力回線を介して入力される可変長フレームを固定長パケットに分割して格納する。各入力バッファ部１００は、パケット分割部１１０とパケットバッファ１２０を含んで構成されている。パケット分割部１１０は、対応する入力回線を介して入力される可変長フレームを、１あるいは複数の固定長パケットに分割する。
【００２５】
図２は、可変長フレームの一例を示すフォーマット図であり、ＩＰｖ４フォーマット（Internet Society ＲＦＣ７９１）のパケットフォーマットが示されている。図２に示すように、このＩＰパケットは、バージョン（Vers）、ヘッダ長（ＩＨＬ）、タイプオブサービス（Type of Service）、ペイロード長（Total Length）、識別子（Identification）、フラグ（Flags）、フラグメントオフセット（Flagment Offset）、生存時間（Time to Live）、プロトコル（Protocol）、ヘッダチェックサム（Header Checksum）、送信元アドレス（Source Address）、宛先アドレス（Destination Address）、ＩＰオプション（ＩＰ Option）、ペイロード（Payload）によって構成されている。ＩＰヘッダとペイロードのそれぞれが可変長であるため、パケット（フレーム）全体も可変長となる。
【００２６】
また、図３はパケット分割部１１０による分割によって生成される本実施形態の固定長パケットの具体例を示す図である。図３に示すように、本実施形態で用いられる固定長パケットは、空きセル識別子（ＥＮ）、フレームタイプ（ＦＲＩ）、マルチキャスト識別子（Ｍ）、サービス品質（ＱｏＳ；Quality of Service）、ペイロード長（ＰＫＬ）、ＴＡＧ識別子（ＴＡＧ）、シーケンス番号（ＳＮ）、ペイロード（Payload）によって構成されている。空きセル識別子は、各タイムスロットに固定長パケットを対応させた場合に、各固定長パケットが空きセルであるか（ＥＮビットが０）、有効セルであるか（ＥＮビットが１）を識別するために用いられる。フレームタイプは、この固定長パケットが可変長フレームのどの部分に対応しているかを示すものである。中間の場合には“００”が、先頭の場合には“０１”が、最終の場合には“１０”が、先頭および最終の両方に対応している場合には“１１”が格納される。マルチキャスト識別子は、この固定長パケットがマルチキャストパケットであるかユニキャストパケットであるかを識別するために用いられる。マルチキャストパケットの場合には“１”が格納される。サービス品質は、各固定長パケットの優先度に差を設けたい場合に用いられる。例えば、帯域確保が指示された優先度が高い固定長パケットであるか否か等を示す情報が格納される。ＴＡＧ識別子は、この固定長パケットの送出先となる出力回線を特定する情報を格納する。例えば、ユニキャストパケットについてはいずれか一の出力回線が特定され、マルチキャストパケットについては複数の出力回線が特定される。シーケンス番号は、可変長フレームを複数の固定長パケットに分割した場合に、その先頭側から順番に付された通し番号である。
【００２７】
また、図１に示すパケットバッファ１２０は、対応する入力回線を介して入力されるユニキャストパケットとマルチキャストパケットを格納するために、（Ｍ＋１）個のキューを有している。これらのキューの中のＭ個が、Ｍ本の出力回線＃１〜＃Ｍのそれぞれに対応した論理キューＶＯＱ（Virtual Output Queue）＃１〜＃Ｍであり、それぞれの出力回線が出力先として指定されたユニキャストパケットが格納される。また、これらのキューの中の残りの１個がマルチキャストパケット用の論理キューＶＯＱであり、対応する入力回線を介して入力されるマルチキャストパケットが入力順に格納される。以後、ユニキャストパケット用の論理キューＶＯＱ＃１〜＃ＮをユニキャストキューＵＣＱ＃１〜＃Ｎと称するものとする。また、マルチキャストパケット用の論理キューＶＯＱをマルチキャストキューＭＣＱと称する。
【００２８】
スケジューラ部２００は、各入力バッファ部１００から通知されるスケジューリング要求に基づいて、各入力バッファ部１００に格納されたユニキャストパケットおよびマルチキャストパケットの競合制御を行う。具体的には、スケジューラ部２００は、ユニキャストパケットについては入力回線と出力回線の両方が競合しないように、マルチキャストパケットについては入力回線が競合しないように、Ｎ個の入力バッファ部１００のそれぞれについて出力対象となるユニキャストパケットあるいはマルチキャストパケットを決定するスケジューリング処理を行う。
【００２９】
クロスバースイッチ部３００は、スケジューリング処理結果に基づいて各入力バッファ部１００から読み出されたユニキャストパケットあるいはマルチキャストパケット（固定長パケット）の出力先情報（図３に示したフォーマット中のＴＡＧ識別子）に基づいて、固定長パケット単位で方路の切り替えを行う。また、クロスバースイッチ部３００は、マルチキャストパケットがいずれかの入力バッファ部１００から入力された場合には、このマルチキャストパケットをその出力先として指定された出力回線の数だけコピーして、それぞれの出力回線に向けて出力する。さらに、クロスバースイッチ部３００は、各出力回線毎もしくは各入力回線毎に競合したパケットを格納するキュー（バッファ）を有している。
【００３０】
Ｍ個のフレーム組立バッファ部４００は、Ｍ本の出力回線＃１〜＃Ｍのそれぞれに対応して設けられており、Ｎ個のユニキャストキューＵＣＱとＮ個のマルチキャストキューＭＣＱを有している。Ｎ個のユニキャストキューＵＣＱは、Ｎ本の入力回線＃１〜＃Ｎのそれぞれに対応しており、対応する出力回線に向けて出力されたユニキャストパケットを入力回線毎に格納する。同様に、Ｎ個のマルチキャストキューＭＣＱは、Ｎ本の入力回線＃１〜＃Ｎのそれぞれに対応しており、対応する出力回線に向けて出力されたマルチキャストパケットを入力回線毎に格納する。クロスバースイッチ部３００から各出力回線には、各入力回線に対応するユニキャストパケットあるいはマルチキャストパケットがインタリーブされた状態で出力される。フレーム組立バッファ部４００では、これらのパケットを入力回線毎、パケット種別（ユニキャスト／マルチキャスト）毎に分類して組み立てる処理を行う。各可変長フレームを構成する複数の固定長パケットが到着したものから順に、１フレーム分まとめて次段のフレーム化処理部５００に送られる。フレーム化処理部５００は、各固定長パケットのヘッダ部を取り除いて、元の可変長フレームを生成する。
【００３１】
図４は、スケジューラ部２００の詳細な構成図である。図４に示すように、スケジューラ部２００は、Ｎ本の入力回線＃１〜＃Ｎのそれぞれに対応したＮ個のスケジューラ処理部＃１〜＃Ｎを有している。各スケジューラ処理部は同じ構成を有しており、代表してスケジューラ処理部＃１の構成および動作を説明する。
【００３２】
スケジューラ処理部＃１は、対応する入力バッファ部＃１（入力回線＃１〜＃Ｎのそれぞれに対応する入力バッファ部１００のそれぞれを入力バッファ部＃１〜＃Ｎとする）内のパケットバッファ１２０に含まれるＭ個のユニキャストキューＵＣＱおよび１個のマルチキャストキューＭＣＱのそれぞれに対応するスケジューリング要求の個数をカウントする要求数カウンタ２１０と、複数のスケジューリング要求があったときに所定のスケジューリングアルゴリズムにしたがってその中の一つを選択して次に読み出すパケットを決定するスケジューリング処理部２１２と、いずれかのユニキャストパケットの送出先として確定していない出力回線を管理する未確定管理部２１４とを有している。
【００３３】
入力バッファ部＃１のパケットバッファ１２０内のいずれかのユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱに固定長パケットが格納されると、それぞれの格納動作に対応したスケジューリング要求がスケジューラ処理部＃１に通知される。この通知には、入力回線や出力回線を特定する情報が含まれており、スケジューラ処理部２００内の要求数カウンタ２１０は、ユニキャストパケットについては出力回線毎に、マルチキャストパケットについては全体をまとめて、スケジューリング要求数をカウントする。スケジューリング処理部２１２は、未確定管理部２１４によって提供される未確定情報（未確定の出力回線を特定する情報）に基づいて、例えばラウンドロビンポインタを用いたスケジューリング処理を行い、次に読み出すパケットを決定する。決定された内容は、スケジューリング結果通知として入力バッファ部＃１に送られる。このスケジューリング結果には、パケット種別を特定するマルチキャスト識別子と、ユニキャストパケットの場合には出力回線番号とが含まれる。また、このスケジューリング結果は、未確定管理部２１４に送られ、他のスケジューラ処理部＃２〜＃Ｎにおけるスケジューリング処理に用いられる。
【００３４】
上述した説明では、スケジューラ処理部＃１に着目したが、他のスケジューラ処理部＃２〜＃Ｎについても同様であり、これらＮ個のスケジューラ処理部＃１〜＃Ｎのそれぞれにおけるスケジューリング処理が一巡して、各入力バッファ部１００におけるパケットの送出間隔に対応する１パケット時間（１単位時間）毎の読み出しパケットを決定する。
【００３５】
本実施形態のパケットスイッチはこのような構成を有しており、次にその動作を説明する。
図５は、本実施形態のパケットスイッチの概略的な動作を示す説明図である。例えば、３本の入力回線＃１〜＃３と４本の出力回線＃１〜＃４がクロスバースイッチ部３００に収容されているものとする。
【００３６】
入力バッファ部＃１は、４本の出力回線＃１〜＃４のそれぞれに対応した４個のユニキャストキューＵＣＱと、マルチキャストパケット用の単一のマルチキャストキューＭＣＱとを有しており、パケット分割部１１０から出力される固定長パケットをパケット種別、出力回線別に格納する。この格納動作と並行して入力バッファ部＃１からスケジューラ処理部＃１にスケジューリング要求が通知される。スケジューラ処理部＃１では、その時点で存在する複数のスケジューリング要求に基づいて次に出力対象となるいずれかのパケットを選択し、この選択内容がスケジューリング結果として入力バッファ部＃１に送り返される。入力バッファ部＃１は、このようにして送られてくるスケジューリング結果に基づいて、４個のユニキャストキューＵＣＱあるいは１個のマルチキャストキューＭＣＱのいずれか一つからパケットを読み出して、クロスバースイッチ部３００に転送する。このような処理が各入力バッファ部および各スケジューラ処理部において行われる。
【００３７】
一方、クロスバースイッチ部３００では、各パケットに付与された宛先情報（ＴＡＧ識別子）にしたがって、このパケットの出力先を切り替える。マルチキャストパケットについてはその宛先となる出力回線の数だけコピーされる。このとき、同じ出力回線を宛先とする複数のパケットが生成された場合には、いずれか一のパケットのみがこの出力回線に送出され、それ以外のパケットは出力回線毎もしくは入力回線毎にクロスバースイッチ部３００内に設けられたキューに格納され、送出タイミングが次回以降に変更される。
【００３８】
図６は、スケジューラ部２００におけるスケジューリング処理の具体例を示す流れ図であり、ラウンドロビンポインタを用いた場合の動作手順が示されている。また、図７はラウンドロビンポインタを用いたスケジューリング処理の具体的な様子を示す図である。図７（Ａ）〜図７（Ｄ）のそれぞれにおいて、大円は、各入力回線に対応するユニキャストキューＵＣＱおよびマルチキャストキューＭＣＱの中でパケットが格納されてスケジューリング要求が通知されていることを示しており、その中で黒く塗りつぶされたものがスケジューリング処理によって選択されていることを表している。また、小円は、ラウンドロビンポインタを示しており、処理対象となる入力回線を選択するために一つ、各入力回線毎にパケットを読み出すキューを選択するために各入力回線毎に一つが含まれている。
【００３９】
スケジューラ処理部＃１〜＃Ｎは、全入力回線について読み出し対象となるキューの選択動作を行ったか否かを判定する（ステップＳ１００）。キューの選択動作を行っていない入力回線が存在する場合には否定判断が行われ、この入力回線に対応するスケジューラ処理部による動作が開始される。
【００４０】
まず、各スケジューラ処理部＃１〜＃Ｎは、ラウンドロビンポインタに従って、スケジューリング処理の対象となる一の入力回線を選択する（ステップＳ１０１）。図７（Ａ）に示した例では、入力回線＃１の位置に、入力回線選択用のラウンドロビンポインタがあるため、まず最初に入力回線＃１が処理対象として選択される。
【００４１】
次に、この選択された入力回線＃１に対応するスケジューラ処理部＃１は、ラウンドロビンポインタに従って、Ｍ個のユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱの中から読み出し対象となる一のキューを選択する（ステップＳ１０２）。図７（Ａ）に示した例では、Ｍ番目のユニキャストキューＵＣＱに対応する位置にラウンドロビンポインタがあるが、このＭ番目のユニキャストキューＵＣＱに対応するスケジューリング要求が存在しないため、所定の順番で辿っていって最初にスケジューリング要求が存在するキュー（例えばマルチキャストキューＭＣＱ）が選択される。このようにしてマルチキャストキューＭＣＱが選択されると、スケジューラ処理部＃１は、図７（Ｂ）に示すように、この選択されたマルチキャストキューＭＣＱが最も優先順位が低くなるように、ラウンドロビンポインタを１番目のユニキャストキューＵＣＱの位置に移動する（ステップＳ１０３）。ここでユニキャストキューＵＣＱについては、スケジューラ処理部間でやりとりされる未確定情報を参照して、出力回線が確定していないものの中から選択する。
【００４２】
入力回線＃１に対応するスケジューリング処理が終わると、ステップＳ１００に戻って、読み出し対象となるキューが選択されていない他の入力回線についてもスケジューリング処理が行われる。このようにして、Ｎ本の入力回線＃１〜＃Ｎのそれぞれについて、パケットの読み出し対象となるキューが選択される。例えば、図７（Ｃ）に示した例では、入力回線＃１に対応してマルチキャストキューＭＣＱが、入力回線＃２に対応してユニキャストキューＵＣＱ＃２が、…、入力回線＃Ｎに対応してマルチキャストキューＭＣＱがそれぞれ選択される。
【００４３】
全入力回線について選択処理が終了すると、ステップＳ１００の判定において肯定判断が行われ、次に、各スケジューラ処理部＃１〜＃Ｎは、今回優先順位が最も高かった入力回線の優先度が、次回最も低くなるように、ラウンドロビンポインタの位置を移動する（ステップＳ１０４）。図７（Ａ）〜図７（Ｃ）に示した例では、それまでの優先度は入力回線＃１が最も高く設定されているため、図７（Ｄ）に示すように、次の入力回線＃２の優先度が最も高く、入力回線＃１の優先度が最も低くなるようにラウンドロビンポインタの位置が変更される。
【００４４】
なお、上述したスケジューリング処理の具体例では、ラウンドロビンポインタを用いた場合について説明したが、他のスケジューリングアルゴリズムを用いるようにしてもよい。
次に、クロスバースイッチ部３００内のバッファ構成について説明する。
【００４５】
図８は、本実施形態のクロスバースイッチ部３００の詳細な構成を示す図である。ユニキャストパケットについては出力回線毎にバッファを設け、マルチキャストパケットについては入力回線毎にバッファを設けた場合の構成が示されている。
【００４６】
図８に示すクロスバースイッチ部３００は、出力回線＃１〜＃Ｍのそれぞれに対応して設けられたＭ個のユニキャストキューＵＣＱ＃１〜＃Ｍと、入力回線＃１〜＃Ｎのそれぞれに対応して設けられたＮ個のマルチキャストキューＭＣＱ＃１〜＃Ｎと、Ｍ個のユニキャストキューＵＣＱ＃１〜＃Ｎのそれぞれの前段に設けられたＭ個のセレクタ３１０および後段に設けられたＭ個のセレクタ３２０と、入力回線＃１〜＃Ｎのそれぞれから入力されたパケットの種別を識別してユニキャストキューＵＣＱ側あるいはマルチキャストキューＭＣＱ側に振り分けるＮ個のパケット種別識別部＃１〜＃Ｎとを有している。
【００４７】
入力バッファ部＃１〜＃Ｎのそれぞれからクロスバースイッチ部３００に入力されたパケットは、各入力回線毎に設けられたパケット種別識別部＃１〜＃Ｎにおいて、パケット種別（ユニキャスト／マルチキャストの別）が識別される。この識別の結果、ユニキャストパケットである場合には、セレクタ３１０を介してこのパケットの宛先となる出力回線に対応したユニキャストキューＵＣＱに送られ、入力順に格納される。ユニキャストキューＵＣＱ＃１〜＃Ｍのそれぞれに格納されたパケットは、先頭から順に読み出され、後段のセレクタ３２０に入力される。また、識別の結果、マルチキャストパケットである場合には、入力回線＃１〜＃Ｎのそれぞれに１対１に対応するマルチキャストキューＭＣＱに送られて、入力順に格納される。マルチキャストキューＭＣＱ＃１〜＃Ｎのそれぞれに格納されたパケットは、先頭から順に読み出され、それぞれの宛先分の個数がコピーされて、各宛先に１対１に対応するセレクタ３２０に入力される。
【００４８】
Ｍ個のセレクタ３２０のそれぞれは、１対１に対応するユニキャストキューＵＣＱと、Ｎ個のマルチキャストキューＭＣＱ＃１〜＃Ｎのそれぞれから出力されるパケットが入力されており、いずれか一のパケットを選択して、１対１に対応する出力回線に出力する。
【００４９】
このように、クロスバースイッチ部３００は、内部にユニキャストキューＵＣＱおよびマルチキャストキューＭＣＱを備えており、宛先となる出力回線が同じであるパケットが競合した場合に、所定の順番で選択されたパケットが順番に出力される。
【００５０】
なお、ユニキャストキューＵＣＱやマルチキャストキューＭＣＱのそれぞれにおけるパケットの格納量は、図示しないキュー管理部によって管理されている。キュー管理部は、容量以上のパケットが入力されて輻輳が生じる場合に、パケットの入力元となる入力バッファ部＃１〜＃Ｎに対して、輻輳情報としてのバックプレッシャ指示ＢＰを送る。この指示を受け取った入力バッファ部＃１〜＃Ｎでは、この指示の送信元となるユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱに対するパケットの送出を停止する。また、このバックプレッシャ指示ＢＰは、入力バッファ部＃１〜＃Ｎの代わりに、それぞれに対応するスケジューラ処理部＃１〜＃Ｎに送るようにしてもよい。この指示を受け取ったスケジューラ処理部＃１〜＃Ｎでは、この指示の送信元となるユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱに対するパケットの送出を停止するようにスケジューリング処理を行う。
【００５１】
図９は、クロスバースイッチ部の変形例を示す部分的な構成図である。図９には、図８に示したクロスバースイッチ部３００に含まれるＮ個のマルチキャストキューＭＣＱ＃１〜＃Ｎに対応する構成が示されている。例えば、図９に示したコピー部＃１および２つのマルチキャストキューＭＣＱ＃１−１、＃１−２が、図８に示したマルチキャストキューＭＣＱ＃１に対応している。コピー部＃１は、入力バッファ部＃１内のマルチキャストキューＭＣＱ＃１から読み出されてクロスバースイッチ部３００に入力されたマルチキャストパケットを２個にコピーして、２つのマルチキャストキューＭＣＱ＃１−１、＃１−２に格納する。一方のマルチキャストキューＭＣＱ＃１−１は、宛先となる出力回線番号が奇数のマルチキャストパケットを格納する。他方のマルチキャストキューＭＣＱ＃１−２は、宛先となる出力回線番号が偶数のマルチキャストパケットを格納する。なお、宛先となる出力回線番号が奇数のみである場合には、奇数用のマルチキャストキューＭＣＱ＃１−１のみにコピーされたパケットが格納され、偶数用のマルチキャストパケットＭＣＱ＃１−２にはこのコピーされたパケットが格納されない。偶数の場合も同様である。
【００５２】
このように、入力されたマルチキャストパケットをコピーして複数に分割することにより、ＨＯＬブロッキングが発生する割合を低減することができ、スループットの向上を図ることができる。
従来から入力回線毎に単一のバッファにパケットを格納すると、先頭のパケットが競合することにより後続のパケットが読み出せないＨＯＬブロッキングにより、最悪の場合にスループットが５８．６％まで低下することが知られている。しかしながら、図９に示すように、各入力回線に対応させて複数のマルチキャストキューＭＣＱに分割すると、競合するパケットの割合が減って、スループットが以下に示す式のように改善される。
【００５３】
スループット（％）＝（１−（１−０．５８６）／分割数））×１００
例えば、２分割の場合には、スループットを７９．３％まで向上させることができる。
なお、上述した例では、宛先となる出力回線番号を奇数と偶数に分けてマルチキャストキューＭＣＱを２分割する場合を示したが、異なる分割数、あるいは異なる内容の分割方法を採用するようにしてもよい。例えば、出力回線を回線番号が小さい方から順に使うような場合には、出力回線番号を分割数のモジョロで割った値により、コピーしたパケットの格納先を振り分けるようにしてもよい。
【００５４】
ところで、上述した実施形態では、各パケットの優先度に差を設けなかったが、例えばサービス品質ＱｏＳ毎に優先度に差を設けるようにしてもよい。
図１０は、パケットの優先度に差を設けるようにしたパケットスイッチの変形例を示す図であり、パケットスイッチに含まれる入力バッファ部とクロスバースイッチ部の構成が示されている。入力バッファ部＃１〜＃Ｎのそれぞれは、Ｍ本の出力回線のそれぞれに対応して設けられたＭ組のユニキャストキューＵＣＱ＃１〜＃Ｍと、マルチキャストパケット用に設けられた一組のマルチキャストキューＭＣＱとを有している。一組のユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱは、優先度の低いサービス品質ＱｏＳのパケットを格納する論理キューＶＯＱ＃１（図１０ではＱｏＳ＃１）と、優先度の高いサービス品質ＱｏＳのパケットを格納する論理キューＶＯＱ＃Ｋ（ＱｏＳ＃Ｋ）を含んでいる。例えば、帯域保証を行う必要があるパケットは、論理キューＶＯＱ＃Ｋに格納される。また、ベストエフォートで通信を行えばよいパケットは、論理キューＶＯＱ＃１に格納される。優先度が高いか否かは、図３に示した固定長パケット内のサービス品質ＱｏＳに基づいて判断される。
【００５５】
このように、優先度が異なるパケットを別々に格納することにより、優先度を考慮した動作が可能になる。
例えば、スケジューラ部２００から各入力バッファ部＃１〜＃Ｎにスケジューリング結果が通知されて、いずれかのユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱからのパケットの読み出しが指示された場合に、論理キューＶＯＱ＃１と論理キューＶＯＱ＃Ｋの両方にパケットが格納されている場合には、論理キューＶＯＱ＃Ｋに格納されている優先度が高いパケットの読み出しを優先させるようにする。これにより、パケット毎の優先度を考慮したパケットの転送処理が可能となる。
【００５６】
また、クロスバースイッチ部３００内のユニキャストキューＵＣＱやマルチキャストキューＭＣＱに格納されているパケットを読み出す際に、論理キューＶＯＱ＃１と論理キューＶＯＱ＃Ｋの両方にパケットが格納されている場合には、論理キューＶＯＱ＃Ｋに格納されている優先度が高いパケットの読み出しを優先させるようにする。これにより、パケット毎の優先度を考慮したパケットの出力動作が可能となる。
【００５７】
次に、マルチキャストパケットがクロスバースイッチ部３００内でコピーされた際に、他のユニキャストパケットとの競合を回避するための手法について説明する。
図１１は、マルチキャストパケットとユニキャストパケットとの競合を回避するスケジューリング処理の概要を示す図である。
【００５８】
（１）入力バッファ部（例えば＃１）は、マルチキャストパケットをマルチキャストキューＭＣＱに格納する際に、スケジューラ部２００に対してスケジューリング要求を送る。
（２）スケジューラ部２００は、送られてくるスケジューリング要求に応じて、マルチキャストパケットについてのスケジューリング処理を行う。
【００５９】
（３）スケジューラ部２００は、スケジューリング処理の結果に基づいて、マルチキャストパケットの読み出し指示を入力バッファ部＃１に送る。
（４）入力バッファ部＃１は、スケジューラ部２００から送られてくる読み出し指示に応じて、マルチキャストキューＭＣＱの先頭に格納されているマルチキャストパケットを読み出して、クロスバースイッチ部３００に転送する。
【００６０】
（５）入力バッファ部＃１は、読み出したマルチキャストパケットの送出先となる出力回線（例えば出力回線＃１、＃２、＃３）に対応する１タイムスロット分のスケジューリング停止指示をスケジューラ部２００に送る。
図１２は、スケジューリング停止指示に応じたスケジューリング処理を行うスケジューラ処理部の構成を示す図である。図１２では、入力バッファ部＃１に対応するスケジューラ処理部＃１について示したが、スケジューラ部２００内の他のスケジューラ処理部＃２〜＃Ｎについても同様である。
【００６１】
スケジューラ処理部＃１は、要求数カウンタ２１０、スケジューリング処理部２１２、未確定管理部２１４、空き要求数カウンタ２１６を含んで構成されている。図４に示した構成に対して、空き要求数カウンタ２１６が追加された点が異なっている。空き要求数カウンタ２１６は、入力バッファ部＃１からスケジューリング停止指示が送られてきたときに、対象となる出力回線毎にこの停止指示の受付回数（以後、この受付回数を「空き要求数」と称する）をカウントする。もしくは、（５）のスケジューリング停止指示を行う代わりに、スケジューリング処理部２１２で各マルチキャストパケットに対する出力回線情報を管理して、（３）のマルチキャスト読み出し指示を出力する際にスケジューリング処理部２１２より空き要求数カウンタにカウントを指示してもよい。スケジューリング処理部２１２は、出力回線毎の空き要求数が１以上である出力回線をスケジューリング処理の対象から除外して、他の出力回線を対象にしたスケジューリング処理を実施する。なお、１パケット時間内で行われる入力バッファ部＃１〜＃Ｎのそれぞれのスケジューリング処理において、スケジューリング停止時の対象となる出力回線を処理対象から除外する必要があるため、上述した空き要求数カウンタ２１６の情報は、入力バッファ部＃１から他の入力バッファ部＃２〜＃Ｎに転送される。この転送は、例えば未確定管理部２１４によって行われる。
【００６２】
このように、マルチキャストパケットが入力バッファ部＃１から読み出されてクロスバースイッチ部３００に入力されたときに、このマルチキャストパケットの送出先となる出力回線が競合するユニキャストパケットの読み出しを一時的に停止することにより、クロスバースイッチ３００内での出力回線の競合を低減することができる。これにより、クロスバースイッチ３００内に備えるバッファの容量を少なくすることができる。
【００６３】
図１３は、スケジューラ部２００における空き要求数を考慮したスケジューリング処理の具体例を示す流れ図であり、ラウンドロビンポインタを用いた場合の動作手順が示されている。また、図１４はラウンドロビンポインタを用いたスケジューリング処理の具体的な処理の様子を示す図である。図１４（Ａ）〜図１４（Ｃ）のそれぞれにおいて、四角で囲まれた出力回線番号は、この出力回線に対してスケジューリング停止指示が行われていることを示している。
【００６４】
スケジューラ部２００内の各スケジューラ処理部＃１〜＃Ｎのうちラウンドロビンポインタで最も優先度の高い入力回線に対応したものについては、空き要求数カウンタ２１６を参照し、空き要求数が１以上であるか否かを判定する（ステップＳ２００）。少なくとも一の出力回線に対応する空き要求数が１以上である場合には肯定判断を行い、次に各スケジューラ処理部＃１〜＃Ｎは、空き要求数が１以上である出力回線を選択対象外としてマスク設定を行うとともに（ステップＳ２０１）、このマスク設定を行った出力回線に対応する空き要求数から１を減じる（ステップＳ２０２）。図１４（Ａ）に示した例では、出力回線＃２と＃Ｍにマスク設定が行われている。
【００６５】
次に、各スケジューラ処理部＃１〜＃Ｎは、全入力回線について読み出し対象となるキューの選択動作を行ったか否かを判定する（ステップＳ２０３）。キューの選択動作を行っていない入力回線が存在する場合には否定判断が行われ、この入力回線に対応するスケジューラ処理部による動作が開始される。
【００６６】
まず、各スケジューラ処理部＃１〜＃Ｎは、ラウンドロビンポインタに従って、スケジューリング処理の対象となる一の入力回線を選択する（ステップＳ２０４）。図１４（Ａ）に示した例では、入力回線＃１の位置に、入力回線選択用のラウンドロビンポインタがあるため、まず最初に入力回線＃１が処理対象として選択される。
【００６７】
次に、この選択された入力回線＃１に対応するスケジューラ処理部＃１は、ラウンドロビンポインタに従って、マスク設定されていないユニキャストキューＵＣＱあるいはマルチキャストキューＭＣＱの中から読み出し対象となる一のキューを選択する（ステップＳ２０５）。図１４（Ａ）に示した例では、Ｍ番目のユニキャストキューＵＣＱに対応する位置にラウンドロビンポインタがあるが、出力回線Ｍはマスク設定がなされているため、所定の順番で辿っていって最初にスケジューリング要求が存在し、しかもマスク設定がなされていない出力回線に対応するキュー（例えばマルチキャストキューＭＣＱ）が選択される。このようにしてマルチキャストキューＭＣＱが選択されると、スケジューラ処理部＃１は、図１４（Ｂ）に示すように、この選択されたマルチキャストキューＭＣＱが最も優先順位が低くなるように、ラウンドロビンポインタを１番目のユニキャストキューＵＣＱの位置に移動する。もしくは、図のように、パケットがあるにもかかわらずマスクもしくは他の入力回線で出力回線が確定したことにより選択できない場合には、次回に当該パケットの優先度が高くなるようにラウンドロビンポインタを移動しなくてもよい（ステップＳ２０６）。
【００６８】
入力回線＃１に対応するスケジューリング処理が終わると、ステップＳ２０３に戻って、読み出し対象となるキューが選択されていない他の入力回線についてもスケジューリング処理が行われる。このようにして、Ｎ本の入力回線＃１〜＃Ｎのそれぞれについて、パケットの読み出し対象となるキューが選択される。例えば、図１４（Ｃ）に示した例では、入力回線＃１に対応してマルチキャストキューＭＣＱが、入力回線＃２に対応してユニキャストキューＵＣＱ＃１が、…、入力回線＃Ｎに対応してマルチキャストキューＭＣＱがそれぞれ選択される。
【００６９】
全入力回線について選択処理が終了すると、ステップＳ２０３の判定において肯定判断が行われ、次に、各スケジューラ処理部＃１〜＃Ｎは、今回優先順位が最も高かった入力回線の優先度が、次回最も低くなるように、ラウンドロビンポインタの位置を移動する（ステップＳ２０７）。図１４（Ａ）〜図１４（Ｃ）に示した例では、それまでの優先度は入力回線＃１が最も高く設定されているため、図１４（Ｄ）に示すように、次の入力回線＃２の優先度が最も高く、入力回線＃１の優先度が最も低くなるようにラウンドロビンポインタの位置が変更される。その後、各スケジューラ処理部＃１〜＃Ｎは、いずれかの出力回線に対して行っていたマスク設定を解除する（ステップＳ２０８）。
【００７０】
〔第２の実施形態〕
次に、本発明を適用した第２の実施形態のパケットスイッチについて説明する。本実施形態のパケットスイッチは、第１の実施形態のクロスバースイッチ部３００を複数個並列に使用することにより、処理の高速化を実現したものである。
【００７１】
図１５は、本実施形態のパケットスイッチの構成を示す図である。また、図１６は本実施形態のパケットスイッチの動作原理を示す図である。なお、図１５に示す構成は、図１に示したパケットスイッチの一部に対応する構成を示したものであり、パケットスイッチ全体としては、これ以外の入力バッファ部１００、スケジューラ部２００、フレーム組立バッファ部４００、フレーム化処理部５００が含まれる。また、図１５に示したＬ個のスイッチ面＃１〜＃Ｌのそれぞれは、機能的には図１等に示したクロスバースイッチ部３００と同じであり、内容の詳細な説明は省略する。
【００７２】
分離部＃１〜＃Ｎのそれぞれは、Ｎ個の入力バッファ部＃１〜＃Ｎのそれぞれの後段に設けられており、対応する入力バッファ部＃１〜＃Ｎから出力される固定長パケットが入力される。分離部＃１〜＃Ｎは、入力される固定長パケットをその先頭位置からビット単位でＬ分割し、それぞれの分割データ１〜Ｌに所定のタグ情報（ＴＡＧ）を付加して出力する。なお、ここで付加するタグ情報は、図３に示した固定長フォーマットに含まれるＴＡＧ識別子をそのまま、あるいは同等の内容を有するものが用いられる。すなわち、このタグ情報には、ユニキャストパケットについてはいずれか一の出力回線（出力ポート）を特定する情報が含まれており、マルチキャストパケットについては複数の出力回線（出力ポート）を特定する情報が含まれている。また、各スイッチ面＃１〜＃Ｌにおいて方路の切り替えが行われた後は、送出先となる出力ポートの情報は不要となるため、代わりに固定長パケットが入力された入力回線（入力ポート）を特定する情報がこのタグ情報に上書きされる。この上書きされた情報は、後段のフレーム組立バッファ部４００において可変長フレームを再構成する際に参照される。
【００７３】
このように、Ｌ個のスイッチ面＃１〜＃Ｌを用いて、固定長パケットに対して並行してスイッチング処理を行うことにより、一つ一つのスイッチ面における処理の負担を軽減することができ、転送速度の高速化が可能になる。特に、スイッチ面の個数Ｌを増減することにより、数々の通信速度に対応することができるため、汎用性の高いパケットスイッチを実現することが可能になる。
【００７４】
図１７は、本実施形態のパケットスイッチの変形例を示す図である。上述したように、入力される固定長パケットの先頭から順にビット単位で分割する、いわゆにビットスライスの手法を用いた場合には、一つの固定長パケットがＬ分割されてＬ個のスイッチ面＃１〜＃Ｌのそれぞれに送られる。この場合に、スイッチ面＃１〜＃Ｌのいずれかに障害が発生すると、全てのデータが正常に転送されなくなるが、図１７に示す構成を用いることにより、このような不都合を回避することができる。
【００７５】
図１７に示すパケットスイッチは、図１５に示した構成に対して、分離部＃１〜＃Ｎの前段にＮ個の変換部＃１１〜＃１Ｎを設けるとともに、多重部＃１〜＃Ｍの後段にＭ個の変換部＃２１〜＃２Ｍを設けた点が異なっている。変換部＃１１〜＃１Ｎのそれぞれは、入力される固定長パケットを、スイッチ面の数Ｌを単位として並べ替える処理を行う。例えば、４個のスイッチ面＃１〜＃４が備わっている場合には、４個の固定長パケットが入力される毎に、これら４個の固定長パケットを構成する各ビットデータが並行して出力されるようにビット単位でデータの並べ替えが行われる。なお、複数の固定長パケットが並行して出力されるため、一の固定長パケットは複数のパケット時間かけて出力されることになる。
【００７６】
また、変換部＃２１〜＃２Ｍのそれぞれは、対応する多重部＃１〜＃Ｍのそれぞれから出力されるデータを並べ替えて、固定長パケット単位で出力する。分離部＃１〜＃Ｎのそれぞれにおいて行われたデータの並べ替え処理によって、各スイッチ面＃１〜＃Ｌのそれぞれからは、異なる固定長パケットの各分割データが並行に出力される。変換部＃２１〜＃２Ｍのそれぞれでは、これらの同時に出力されるデータの再配置を行うことにより、各固定長パケットの出力タイミングを時間的に分離する。
【００７７】
このように、変換部＃１１〜＃１Ｎのそれぞれにおいて並べ替えられたデータを分離部＃１〜＃Ｎに入力することにより、各分離＃１〜＃Ｎから出力される各固定長パケットが分割されて複数のスイッチ面に分かれて入力されることを回避することができる。したがって、いずれかのスイッチ面に障害が発生した場合であっても、正常なスイッチ面を用いて固定長パケットを転送することができるようになる。
【００７８】
図１８は、図１７に示したパケットスイッチの動作を実現する入力バッファ部の構成を示す図である。図１７に示した構成では、各入力回線に対応して設けられた入力バッファ部から出力された固定長パケットに対して、変換部＃１１〜＃１Ｎおよび分離部＃１〜＃Ｎにおける各種の処理を行うようにしたが、図１８では、これらの機能を入力バッファ部に持たせている。なお、図１８では入力バッファ部＃１の構成のみが示されているが、他の入力バッファ部＃２〜＃Ｎも同じ構成を有している。
【００７９】
図１８に示す入力バッファ部＃１は、Ｍ本の出力回線のそれぞれに対応するＭ個のユニキャストキューＵＣＱ＃１〜＃Ｍと、単一のマルチキャストキューＭＣＱと、これら各種のキューに格納されているパケットを選択的に読み出して出力するセレクタ１３０とを含んで構成されている。
【００８０】
ユニキャストキューＵＣＱ＃１〜＃Ｍのそれぞれは、Ｌ個のスイッチ面＃１〜＃Ｌのそれぞれに１対１に対応するＬ個の格納領域（スライス＃１〜＃Ｌ）を有している。例えば、出力回線＃１を送出先とする固定長パケットが入力された場合には、最初の１個についてはユニキャストキューＵＣＱ＃１のスライス＃１で特定される格納領域に格納され、次の１個についてはスライス＃２で特定される格納領域に格納される。３個以降の固定長パケットについても同様であり、順番にスライス＃３以降の格納領域に格納される。そして、スライス＃Ｌで特定される格納領域に対する固定長パケットの格納が終了すると、これらＬ個の固定長パケットに対応するスケジューリング要求がスケジューラ部２００に送られる。また、スケジューラ部２００から出力回線＃１について読み出しを指示するスケジューリング結果が送られてくると、セレクタ１３０は、ユニキャストキューＵＣＱ＃１のＬ個の格納領域に格納されているパケットを同時に読み出して、Ｌ個のスイッチ面＃１〜＃Ｌのそれぞれに送出する。他のユニキャストキューＵＣＱ＃２〜＃ＭやマルチキャストキューＭＣＱについても同様であり、Ｌ個の固定長パケットが格納されたときにこれらのパケットが同時に読み出される。
【００８１】
なお、図１７および図１８に示した例では、一の固定長パケットは、複数のスイッチ面に分割されずに一のスイッチ面に向けて送出される。したがって、これらの場合には、図１５や図１６に示したような新たなタグ情報を付加する必要がないという利点もある。
【００８２】
ところで、図１７に示したパケットスイッチでは、各スイッチ面＃１に異なる固定長パケットが送出されるため、同じ出力回線を宛先とした場合であってもパケットの順番が前後する場合があり、このような場合には到着順に並んだパケットの順番を並べ替える必要がある。
【００８３】
図１９は、パケットの順番を考慮してフレームの組み立てを行うパケットスイッチの構成を示す図である。図１９に示すパケットスイッチは、図１７に示したパケットスイッチに対して、多重部＃１〜＃Ｍの後段に設けられていた変換部＃２１〜＃２Ｍをフレーム組立部＃１〜＃Ｍに置き換えた点が異なっている。フレーム組立部＃１〜＃Ｍのそれぞれは、変換部＃２１等の機能を有しているとともに、順番が前後して到着する複数の固定長パケットを並べ替えて可変長フレームを組み立てる動作を行う。
【００８４】
フレーム組立部＃１〜＃Ｍのそれぞれは、対応する多重部＃１〜＃Ｍから並列に出力される複数の固定長パケットを時間的に分離した後に、順番に格納するパケットバッファと、このパケットバッファの格納アドレスを管理するアドレス管理テーブルと、パケットバッファに格納されたパケットを所定の順番で読み出す読み出し管理部を有している。
【００８５】
図２０は、図１９に示した各フレーム組立部の内部構成を示す図である。
図２０に示すように、パケットバッファ７００は、各種のパケットが到着順（分離順）に入力されたパケットがキー情報（Ｋｅｙ）とともに所定のアドレスに格納される。このキー情報は、対応するパケットの見出しとなるものであり、マルチキャスト識別Ｍ、入力回線番号、フレーム番号（フレームの順番を識別するシーケンス番号）が含まれている。マルチキャスト識別Ｍは、ユニキャストパケットの場合には“１”が、マルチキャストパケットの場合には“０”が格納される。また、パケットバッファ７００には、１フレームを構成するパケットのつながりを示すポインタチェーン情報が格納される。このポインタチェーン情報は、一の着目パケットの次のパケットがどのアドレスに格納されているかを示すものであり、これを辿っていくことにより、１フレームを構成する複数のパケットを次々に読み出すことができる。
【００８６】
また、アドレス管理テーブルは、格納された各パケット毎の詳細情報を格納するものであり、Head（ヘッド）アドレス、Tail（テール）アドレス、フレームポインタ、エンドパケット到着フラグ、エンドパケットＳＮ（シーケンス番号）値、受信パケット数、フレーム内アドレス管理情報が含まれている。Headアドレスは、１フレームを構成する先頭のパケットの格納アドレスを、Tailアドレスは最後尾のパケットの格納アドレスを示している。フレームポインタは、複数の構成パケットが全て到着して読み出し可能な状態になっていることを示す場合に“１”がセットされる。エンドパケット到着フラグは、最後尾のパケットの格納が終了したときにセットされる。エンドパケットＳＮ値は、最後尾のパケットに割り振られたシーケンス番号であり、先頭のパケットから順に０、１、２…となるため、ｎ個のパケットによって１フレームが構成される場合には、この値はｎ−１となる。受信パケット数は、その時点で格納済みのパケット数であり、この数が、最後尾のパケットが格納された後のエンドパケットＳＮ値に１を加えた数に一致すると、１フレームを構成する全てのパケットが到着したものと判定される。また、アドレス管理テーブル７１０には、空き管理キューのHeadアドレスとTailアドレスが含まれており、パケットバッファ７００のどの領域がパケットの未格納領域であるかがわかるようになっている。
【００８７】
図２１および図２２は、図１９に具体例を示したフレーム組立部の動作手順を示す流れ図である。
フレーム組立部は、到着パケットをパケットバッファ７００の空き領域の先頭に格納するとともに、アドレス管理テーブルのキー情報を、この到着パケットのヘッダ情報に基づいて作成する（ステップＳ３００）。また、フレーム組立部は、キー情報に対応するフレーム内アドレス管理情報の到着パケットのＳＮ値に対応するエリアに、パケットバッファ７００の書き込みアドレスを登録する（ステップＳ３０１）。
【００８８】
次に、フレーム組立部は、キー情報に対応する受信パケット数を１インクリメントした後（ステップＳ３０２）、この到着パケットが最終パケットか否かを判定する（ステップＳ３０３）。最終パケットである場合には肯定判断が行われ、フレーム組立部は、キー情報に対応するエンドパケット到着フラグをセットし、到着パケットのパケット番号を、キー情報に対応するエンドパケットＳＮ値にセットする（ステップＳ３０４）。
【００８９】
次に、フレーム組立部は、エンドパケットＳＮ値に１を加えた値と受信パケット数とが一致するか否かを調べることにより、１フレーム内の全てのパケットが到着したか否かを判定する（ステップＳ３０５）。全てのパケットが到着していない場合には否定判断が行われた後、フレーム組立部は待機状態になる。
【００９０】
また、全てのパケットが到着した場合にはステップＳ３０５の判定において肯定判断が行われ、次に、フレーム組立部は、キー情報に対応するフレーム内アドレス管理情報の登録アドレスを、ＳＮ値を順次インクリメントしながらエンドパケットＳＮ値に達するまで順次読み出し、１フレーム分のポインタチェーンを構築する（ステップＳ３０６）。このとき、アドレス管理テーブルのHeadアドレスにＳＮ値が０の登録アドレスが格納され、Tailアドレスに読み出し中の最終アドレスが格納される。
【００９１】
次に、フレーム組立部は、フレームポインタが１になっているか否かを判定する（ステップＳ３０７）。１でない場合には否定判断が行われ、フレーム組立部は待機状態になる。
また、フレームポインタが１の場合にはステップＳ３０７の判定において肯定判断が行われ、次に、フレーム組立部は、キー情報に対応するHeadアドレスを読み出し管理部７２０に転送する。読み出し管理部７２０は、Headアドレスから順に辿っていくことにより、受信パケット数をデクリメントしながら、パケットバッファ７００からパケットの読み出しを開始する（ステップＳ３０８）。このとき、読み出し管理部７２０は、パケットの読み出しが終了したパケットバッファ７００のアドレスを、アドレス管理テーブルに空き管理キューのTailアドレスとして格納する（ステップＳ３０９）。また、読み出し管理部７２０は、１フレーム分のパケットを読み出した後に、アドレス管理テーブルの該当項目（エンドパケット到着フラグ、エンドパケットＳＮ値、フレームポインタ）の内容を全てクリアするとともに、次のフレーム情報を（例えば（キー番号＋１）％フレーム番号最大値で求めて）検索し、この検索したキー情報に対応するフレームポインタに“１”をセットする（ステップＳ３１０）。
【００９２】
次に、フレーム組立部は、このキー情報に対応するエンドパケットＳＮ値に１を加えた値と受信パケット数とが一致するか否かを調べることにより、次の１フレーム内の全てのパケットが到着したか否かを判定する（ステップＳ３１１）。全てのパケットが到着していない場合には否定判断が行われた後、フレーム組立部は待機状態になる。また、到着している場合には、ステップＳ３０８のパケットの読み出し処理以降が繰り返される。
【００９３】
このように、フレーム組立部において１フレームを構成する各パケットの順番等を管理して順番にパケットの読み出しを行うことにより、パケットの到着順にかかわらず、常に１フレームの先頭から順番にパケットを読み出すことができる。
【００９４】
なお、上述したキー情報に含まれるフレーム番号の数（最大値）は、サポートする最大サイズのフレームが各スイッチ面に割り振られて転送される際に、あるスイッチ面が輻輳したことによりかかる時間内に、最大で何個の最小サイズのフレームに追い抜かれるかを見積もることによって、以下の式で求めることができる。
【００９５】
フレーム番号の数＝（最大サイズのフレームのパケット数／スイッチ面数）×出力回線数
また、フレームの組み立てが終了したフレーム番号を、対応する入力回線側に通知するようにしてもよい。入力回線側（例えば入力バッファ部やスケジューラ部）では、このフレーム番号の通知が行われるまで、同じフレーム番号を用いることを禁止することにより、フレーム番号の重複を防止することができる。
【００９６】
図２３は、図１９に示したパケットスイッチの変形例を示す図である。図１９に示した構成に対して、変換部＃１１〜＃１Ｎにおけるパケットの再配置の方法が異なっている。すなわち、図２２に示したパケットスイッチでは、変換部＃１１〜＃１Ｎのそれぞれにおいて、同じフレームに含まれる複数のパケットが同じスイッチ面に送られるようにパケットの再配置が行われる。これにより、Ｌ個のスイッチ面＃１〜＃Ｌを介してパケットが転送された際に、フレーム内でその順番が反対になることを確実に防止することができる。
【００９７】
図２４は、図２３に示した各フレーム組立部の内部構成を示す図である。図２４に示した内容は、図２０に示した内容に対して、アドレス管理テーブルに含まれるフレーム内アドレス管理情報が削除された点と、スイッチ面管理テーブル７３０が追加された点が異なっている。スイッチ面管理テーブル７３０は、各入力回線から各スイッチ面を経由してフレーム組立部に入力されるフレーム数を管理するためものであり、マルチキャスト種別Ｍ、入力回線番号、対応するスイッチ面番号、このスイッチ面に入力されているフレーム数が組になって格納されている。
【００９８】
図２５および図２６は、図２４に具体例を示したフレーム組立部の動作手順を示す図である。
フレーム組立部は、到着パケットをパケットバッファ７００の空き領域の先頭に格納するとともに、アドレス管理テーブルのキー情報を、この到着パケットのヘッダ情報に基づいて作成する（ステップＳ４００）。また、フレーム組立部は、キー情報に対応したTailアドレスに、到着パケットの書き込みアドレスを格納する（ステップＳ４０１）。なお、到着パケットが先頭パケットの場合には、書き込みアドレスをHeadアドレスにも格納する。
【００９９】
次に、フレーム組立部は、到着パケットが先頭パケットか否かを判定する（ステップＳ４０２）。先頭パケットである場合には肯定判断が行われ、フレーム組立部は、アドレス管理テーブルに到着パケットのスイッチ面情報を書き込むとともにスイッチ面管理テーブル７３０の対応スイッチ面のフレーム数を１インクリメントし、フレーム数が規定値（＝最大フレーム数／スライス数）以上であれば、対応スイッチ面に対してバックプレッシャ要求を送る（ステップＳ４０３）。
【０１００】
次に、あるいは到着パケットが先頭パケットでない場合にはステップＳ４０２において否定判断を行った後に、フレーム組立部は、到着パケットが最終パケットか否かを判定する（ステップＳ４０４）。最終パケットである場合には肯定判断が行われ、フレーム組立部は、キー情報に対応するエンドパケット到着フラグをセットし、到着パケットのパケット番号を、キー情報に対応するエンドパケットＳＮ値にセットする（ステップＳ４０５）。
【０１０１】
次に、フレーム組立部は、エンドパケットＳＮ値に１を加えた値と受信パケット数とが一致するか否かを調べることにより、１フレーム内の全てのパケットが到着したか否かを判定する（ステップＳ４０６）。全てのパケットが到着していない場合には否定判断が行われた後、フレーム組立部は待機状態になる。
【０１０２】
また、全てのパケットが到着した場合にはステップＳ４０６の判定において肯定判断が行われ、次に、フレーム組立部は、フレームポインタが１になっているか否かを判定する（ステップＳ４０７）。１でない場合には否定判断が行われ、フレーム組立部は待機状態になる。
【０１０３】
また、フレームポインタが１の場合にはステップＳ４０７の判定において肯定判断が行われ、次に、フレーム組立部は、キー情報に対応するHeadアドレスを読み出し管理部７２０に転送する。読み出し管理部７２０は、Headアドレスから順に辿っていくことにより、受信パケット数をデクリメントしながら、パケットバッファ７００からパケットの読み出しを開始する（ステップＳ４０８）。このとき、読み出し管理部７２０は、パケットの読み出しが終了したパケットバッファ７００のアドレスを、アドレス管理テーブルに空き管理キューのTailアドレスとして格納する（ステップＳ４０９）。また、読み出し管理部７２０は、１フレーム分のパケットを読み出した後に、アドレス管理テーブルの該当項目（エンドパケット到着フラグ、エンドパケットＳＮ値、フレームポインタ、スイッチ面）の内容を全てクリアするとともに、次のフレームのフレーム情報を（例えば（キー番号＋１）％フレーム番号最大値で求めて）検索し、この検索したキー情報に対応するフレームポインタに“１”をセットする（ステップＳ４１０）。
【０１０４】
次に、フレーム組立部は、一連のパケットの読み出しが終了したフレームについて、スイッチ管理テーブルの対応するフレーム数を１デクリメントし、バックプレッシャ要求が送られている場合にはこれを解除する（ステップＳ４１１）。次に、フレーム組立部は、このキー情報に対応するエンドパケットＳＮ値に１を加えた値と受信パケット数とが一致するか否かを調べることにより、次の１フレーム内の全てのパケットが到着したか否かを判定する（ステップＳ４１２）。全てのパケットが到着していない場合には否定判断が行われた後、フレーム組立部は待機状態になる。また、到着している場合には、ステップＳ４０８のパケットの読み出し処理以降が繰り返される。
【０１０５】
このように、フレーム組立部において各スイッチ面で取り扱うフレーム数に上限（規定値）を設け、それ以上のフレーム数のパケットが入力される場合にはこのスイッチ面にバックプレッシャ要求を送っている。したがって、フレーム数を管理する手間を低減することができる。また、規定値以内の数のフレームについては継続的にパケットの転送が行われることから、スループットが低下することを防止することができる。
【０１０６】
図２７は、パケットスイッチの変形例を示す図である。図２７に示すパケットスイッチでは、同一の可変長フレームに関してフロー識別を行うことにより、一の可変長フレームを構成する複数のパケットを同じスイッチ面を用いて転送するようにしたものである。このフロー識別は、変換部＃１〜＃Ｎのそれぞれにおいて行われる。また、フロー識別は、例えば図２に示したフォーマットに含まれるタイプオブサービスフィールドの値や、プロトコル番号、送信元アドレス、宛先アドレス等をフロー識別子として用いて行うことが考えられる。また、ＴＣＰ（Transmission Control Protocol）フレームやＵＤＰ（User Datagram Protocol）フレームの場合には、送信元ポートアドレスや宛先ポートアドレスを用いてフロー識別を行うようにしてもよい。これらの情報をキーとして、予め固定的に割り当てられたスイッチ面番号を検索するか、このキーをハッシュ関数を用いて演算してスイッチ面番号を取得することにより、フロー毎に同一のスイッチ面にパケットを振り分けることが可能になり、スイッチ面の後段でパケットの到着順番が逆転することを防止することができる。また、フレーム組立部＃１〜＃Ｍには、フレームの先頭から順番にパケットが到着するため、パケットの並べ替えを行うために必要なバッファが不要になる。
【０１０７】
なお、本発明は上記実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形実施が可能である。例えば、上述した各実施形態では、ユニキャストパケットとマルチキャストパケットが混在して入力される場合について考えたが、マルチキャストパケットには全ての出力回線を送出先とするブロードキャストパケットも含まれる。
【０１０８】
（付記１）Ｎ本の入力回線のそれぞれに対応して設けられ、対応する前記入力回線を介して入力されるユニキャストパケットおよびマルチキャストパケットを格納するＮ個の入力バッファ部と、
前記Ｎ個の入力バッファ部のそれぞれから前記ユニキャストパケットが入力された場合にはその送出先となるＭ本の出力回線の中のいずれかに前記ユニキャストパケットを出力し、前記マルチキャストパケットが入力された場合にはその送出先となる前記Ｍ本の出力回線の中の複数本に前記マルチキャストパケットを出力するスイッチ部と、
前記ユニキャストパケットについては前記入力回線と前記出力回線の両方が競合しないように、前記マルチキャストパケットについては前記入力回線が競合しないように、前記Ｎ個の入力バッファ部のそれぞれから出力する前記ユニキャストパケットあるいは前記マルチキャストパケットのいずれかを選択するスケジューラ部と、
を備えることを特徴とするパケットスイッチ。
【０１０９】
（付記２）付記１において、
前記スイッチ部は、前記Ｍ本の出力回線のそれぞれに対応して前記ユニキャストパケットを格納する第１の格納部と、前記Ｎ本の入力回線のそれぞれに対応して前記マルチキャストパケットを格納する第２の格納部とを備えることを特徴とするパケットスイッチ。
【０１１０】
（付記３）付記２において、
前記入力バッファ部と前記スイッチ部内の前記第１および第２の格納部の少なくとも一方をサービス品質毎に分割することにより、優先制御を行うことを特徴とするパケットスイッチ。
【０１１１】
（付記４）付記２において、
前記第１の格納部および前記第２の格納部のいずれかが輻輳したときに、前記スイッチ部から前記入力バッファ部および前記スケジューラ部の少なくとも一方に輻輳情報を通知することにより、前記入力バッファ部から前記スイッチ部に対する前記ユニキャストパケットあるいは前記マルチキャストパケットの入力を停止することを特徴とするパケットスイッチ。
【０１１２】
（付記５）付記１において、
前記スケジューラ部は、前記入力バッファ部から前記スイッチ部に前記マルチキャストパケットが入力されたときに、前記マルチキャストパケットの送出先となる複数の前記出力回線について、このマルチキャストパケット以外のパケットが送出されないタイミングを確保することを特徴とするパケットスイッチ。
【０１１３】
（付記６）付記１〜５のいずれかにおいて、
前記スイッチ部が複数設けられており、
一の前記スイッチ部には、前記入力回線を介して入力される前記ユニキャストパケットあるいは前記マルチキャストパケットが複数に分割されてその一部が入力されており、
複数の前記スイッチ部を用いて、一のパケットに対応する複数の分割データを並行して転送することを特徴とするパケットスイッチ。
【０１１４】
（付記７）付記１〜６のいずれかにおいて、
前記スイッチ部が複数設けられており、
一の前記スイッチ部には、前記入力回線を介して入力される一の前記ユニキャストパケットあるいは前記マルチキャストパケットが複数単位時間かけて転送されており、
複数の前記スイッチ部を用いて、異なるパケットを並行して転送することを特徴とするパケットスイッチ。
【０１１５】
（付記８）付記７において、
複数の前記パケットが集まって一のフレームを構成している場合に、
複数の前記パケットのそれぞれには、このフレームの順番を識別する第１のシーケンス番号と、このフレーム内での前記パケットの順番を識別する第２のシーケンス番号とが付されており、
前記出力回線側で、前記第２のシーケンス番号に基づいて前記フレーム内での前記パケットの並べ替えを行うとともに、前記第１のシーケンス番号に基づいて前記フレームの並べ替えを行うフレーム組立部をさらに備えることを特徴とするパケットスイッチ。
【０１１６】
（付記９）付記７において、
複数の前記パケットが集まって一のフレームを構成している場合に、
複数の前記パケットのそれぞれには、このフレームの順番を識別する第１のシーケンス番号と、このフレーム内での前記パケットの順番を識別する第２のシーケンス番号とが付されており、
前記出力回線側で、前記第１および第２のシーケンス番号に基づいて前記パケットの並べ替えを行う際に、並べ替え中の前記フレームの数が所定値以上になったときに、対応する前記スイッチ部に対して転送動作の停止を指示することを特徴とするパケットスイッチ。
【０１１７】
（付記１０）付記７において、
複数の前記パケットが集まって可変長の一のＩＰパケットを構成しており、
前記入力回線側で、前記ＩＰパケットのフロー識別子を用いて、同一の前記スイッチ部に同一フローに属する前記パケットを入力することを特徴とするパケットスイッチ。
【０１１８】
【発明の効果】
上述したように、本発明によれば、ユニキャストパケットとマルチキャストパケットが混在して入力される場合に、スケジューラ部では、ユニキャストパケットについては入力回線と出力回線の両方が競合しないように、マルチキャストパケットについては入力回線が競合しないようにスケジューリング処理を行っており、マルチキャストパケットの送出先となる複数の出力回線を競合制御の対象から除外することにより、スケジューリング処理の負担を大幅に軽減することができる。また、マルチキャストパケットについては、入力バッファ部内でのコピーは行わないため、入力バッファ部とスイッチ部との間のデータ量が増加することがなく、マルチキャストパケットに許容される入力レートが低下することを防止することができる。
【図面の簡単な説明】
【図１】第１の実施形態のパケットスイッチの構成を示す図である。
【図２】可変長フレームの一例を示すフォーマット図である。
【図３】パケット分割部によって生成される固定長パケットの具体例を示す図である。
【図４】スケジューラ部の詳細な構成図である。
【図５】本実施形態のパケットスイッチの概略的な動作を示す説明図である。
【図６】スケジューラ部におけるスケジューリング処理の具体例を示す流れ図である。
【図７】ラウンドロビンポインタを用いたスケジューリング処理の具体的な処理の様子を示す図である。
【図８】本実施形態のクロスバースイッチ部の詳細な構成を示す図である。
【図９】クロスバースイッチ部の変形例を示す部分的な構成図である。
【図１０】パケットの優先度に差を設けるようにしたパケットスイッチの変形例を示す図である。
【図１１】マルチキャストパケットとユニキャストパケットとの競合を回避するスケジューリング処理の概要を示す図である。
【図１２】スケジューリング停止指示に応じたスケジューリング処理を行うスケジューラ処理部の構成を示す図である。
【図１３】スケジューラ部における空き要求数を考慮したスケジューリング処理の具体例を示す流れ図である。
【図１４】ラウンドロビンポインタを用いたスケジューリング処理の具体的な処理の様子を示す図である。
【図１５】第２の実施形態のパケットスイッチの構成を示す図である。
【図１６】本実施形態のパケットスイッチの動作原理を示す図である。
【図１７】本実施形態のパケットスイッチの変形例を示す図である。
【図１８】図１７に示したパケットスイッチの動作を実現する入力バッファ部の構成を示す図である。
【図１９】パケットの順番を考慮してフレームの組み立てを行うパケットスイッチの構成を示す図である。
【図２０】図１９に示した各フレーム組立部の内部構成を示す図である。
【図２１】図１９に具体例を示したフレーム組立部の動作手順を示す流れ図である。
【図２２】図１９に具体例を示したフレーム組立部の動作手順を示す流れ図である。
【図２３】図１９に示したパケットスイッチの変形例を示す図である。
【図２４】図２３に示した各フレーム組立部の内部構成を示す図である。
【図２５】図２４に具体例を示したフレーム組立部の動作手順を示す図である。
【図２６】図２４に具体例を示したフレーム組立部の動作手順を示す図である。
【図２７】パケットスイッチの変形例を示す図である。
【図２８】従来の入力バッファ型のパケットスイッチの構成を示す図である。
【図２９】従来の入力バッファ型のパケットスイッチの構成を示す図である。
【符号の説明】
１００  入力バッファ部
１１０  パケット分割部
１２０  パケットバッファ
２００  スケジューラ部
３００  クロスバースイッチ部
４００  フレーム組立バッファ部
５００  フレーム化処理部
【図１】
0004489308.tif 000002
【図２】
0004489308.tif 000003
【図３】
0004489308.tif 000004
【図４】
0004489308.tif 000005
【図５】
0004489308.tif 000006
【図６】
0004489308.tif 000007
【図７】
0004489308.tif 000008
【図８】
0004489308.tif 000009
【図９】
0004489308.tif 000010
【図１０】
0004489308.tif 000011
【図１１】
0004489308.tif 000012
【図１２】
0004489308.tif 000013
【図１３】
0004489308.tif 000014
【図１４】
0004489308.tif 000015
【図１５】
0004489308.tif 000016
【図１６】
0004489308.tif 000017
【図１７】
0004489308.tif 000018
【図１８】
0004489308.tif 000019
【図１９】
0004489308.tif 000020
【図２０】
0004489308.tif 000021
【図２１】
0004489308.tif 000022
【図２２】
0004489308.tif 000023
【図２３】
0004489308.tif 000024
【図２４】
0004489308.tif 000025
【図２５】
0004489308.tif 000026
【図２６】
0004489308.tif 000027
【図２７】
0004489308.tif 000028
【図２８】
0004489308.tif 000029
【図２９】
0004489308.tif 000030