JP2001060967A

JP2001060967A - パケットスイッチ装置

Info

Publication number: JP2001060967A
Application number: JP23559699A
Authority: JP
Inventors: Hiroshi Tomonaga; 博朝永; Naoki Matsuoka; 直樹松岡; Kenichi Kawarai; 健一瓦井; Tsugio Kato; 次雄加藤
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1999-08-23
Filing date: 1999-08-23
Publication date: 2001-03-06
Also published as: US6963577B1

Abstract

(57)【要約】【課題】メモリアドレスをブロック単位で管理し、ブ
ロック内の個別のアドレスは書き込み時または読み出し
時にキュー毎に与えることでメモリ量を削減するなど。【解決手段】パケットスイッチ装置は、出力回線対応
の論理的なキューを有する入力バッファメモリ手段と、
スケジューリング開始入力回線を示す第１のポインタの
制御手段と、スケジューリング対象回線のスケジューリ
ング開始出力回線を示す第２のポインタの制御手段と、
所望の出力回線に対する送出要求情報を保持する要求管
理制御手段と、複数の送出要求情報の中から前記第２の
ポインタが示す出力回線から検索を開始し、他の入力回
線に確保されていない出力回線を選択するスケジューリ
ング処理手段と、複数の固定長パケットを一時的に保持
し順次に出力するパケットバッファメモリ手段と、前記
パケットバッファメモリ手段から出力された固定長パケ
ットをスイッチングするスイッチ手段と、前記パケット
バッファメモリ手段のアドレスを複数パケット分の固定
長ブロックに分け、アドレス管理をブロック単位に行う
アドレス管理手段とを備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は広帯域交換機、クロ
スコネクトスイッチ装置、及びルータ装置などに適用さ
れ、固定長パケット（セル）を伝送（特に、限定しない
ときは、伝達及び転送を含む）するパケットスイッチ装
置に関し、特に大規模パケットスイッチ装置の一構成法
である入力バッファ型や入出力バッファ型スイッチ装置
に関する。

【０００２】

【従来の技術】近年、インターネットの爆発的な普及や
大容量・高品質な情報を扱うメディアの登場により、大
容量データを柔軟に扱うことのできる大規模な通信ネッ
トワークインフラの整備に期待が寄せられている。そし
て、実現の鍵となる数百ギガ〜数テラオーダのスイッチ
イング容量を持つ広帯域交換機に関心が集まっている。

【０００３】この交換機などに適用され、固定長パケッ
トを伝送するパケットスイッチ装置において、入力方路
（入力回線：ＨＷ）毎にＦＩＦＯ型の単一の入力バッフ
ァメモリを有する基本的な入力バッファ型スイッチ（図
１参照）は、ＨＯＬ(Head OfLine)ブロッキングの問題
があり、スループットが５８．６％までしか上がらない
ことが知られている。このＨＯＬブロッキングを回避す
る手法として、入力バッファ部の各入力バッファメモリ
を論理的に出力方路（出力回線）対応のキューに分割
し、所定のアルゴリズムに従って送出権をスケジューリ
ングすることが知られている（図２参照）。

【０００４】これにより、入力バッファ部の動作速度を
低減し、汎用メモリを使用した大容量入力バッファ部の
構築が可能となる。また、共通スイッチ部となるコアス
イッチ（ＣｏｒｅＳｗｉｔｃｈ）はバッファレスであ
り、ハードウェアを極小化でき、またスケジューラ（Ｓ
ｃｈｅｄｕｌｅｒ）は分散パイプライン構成により動作
速度を低減できる（図３参照）。

【０００５】ここで、入力バッファメモリは論理出方路
キュー間で共用して使用されるため、キュー毎の使用ア
ドレスを管理する必要があるが、入力バッファメモリが
大容量になると、アドレス管理メモリ（ＦＩＦＯ）も大
きくなる（図４参照）。従来、このアドレス管理メモリ
の容量削減のために、ポインタを用いたアドレスリンク
方式が知られている（図５参照）。

【０００６】入力バッファ部を構成するための汎用メモ
リとしては、比較的小容量だが高速でランダムアクセス
可能なＳＲＡＭと、大容量だが高速でアクセスするため
にはバーストアクセスが必要なＤＲＡＭとがある。パケ
ット（セル）バッファメモリをＤＲＡＭにより大容量化
する場合、パケット長の範囲でバーストアクセスを可能
にしている（図６参照）。

【０００７】また、冗長構成としては、共通装置には二
重化構成を採り、ブロック毎に交絡を設け、セレクタを
通して切り替えを行うことにより、装置の信頼性を上げ
ている（図７参照）。入力バッファ部においては、全て
のパッケージカードで同一速度により読み出しを行って
いる。

【０００８】

【発明が解決しようとする課題】さらに、サービスの多
様化に伴って、低速から高速の様々な速度のインタフェ
ースが提供されている。このような回線速度の異なるイ
ンタフェースを共通のルータ装置やクロスコネクトスイ
ッチ装置に効率よく混在収容することが望まれている。

【０００９】従来の混在収容の手法では、複数の低速回
線を多重化してルータ装置やクロスコネクトスイッチ装
置のポート速度まで速度を上げて収容するものや、回線
インタフェースに備えられるバッファメモリで速度変換
を行って混在収容を行っていた。しかし、前者は、比較
的少ない回線インタフェースを収容する場合でも、一旦
高速多重化するためのパケット多重部（ＭＵＸ）が必要
となり、また後者は、比較的安価に提供できる低速イン
タフェースに高速なバッファメモリが必要であった。

【００１０】メモリのアドレス管理については、アドレ
スリンク手法を用いる場合でも、バッファメモリ容量分
のアドレス管理メモリが必要になる。これに対し、バッ
ファメモリ領域の一部をアドレス管理メモリとして使用
する手法があるが、この手法では、パケットバッファメ
モリのアクセス数が増えてしまい、高速アクセスのボト
ルネックになる（図８参照）。

【００１１】また、マルチキャスト機能を実現する場
合、複数の論理出方路キューで同一のパケットバッファ
メモリを使用することになるため、アドレスリンクが形
成できず、アドレスリンク手法が適用できなかった（図
９参照）。

【００１２】パケットバッファメモリについては、メモ
リを可能な限り高速に使おうとすると、パラレル化する
必要がある。しかし、パケットを処理するためのパラレ
ル度はパケット長で制限される。例えば、ＡＴＭ（非同
期転送モード）では５３ｂｙｔｅである。その時、全ビ
ットパラレルで処理すると、一回のアクセスで全データ
を読むことになる。このように、パラレル度を増やした
場合、ＤＲＡＭでのバーストアクセスは適用できなくな
り、高速アクセスを不可能にする（図１０参照）。

【００１３】入力バッファ部の冗長構成については、二
重化構成を採るため、ハードウェア量及びブロック間接
続数が共に２倍となり、コストアップになる。ここで、
コストダウンのために、Ｎ＋１冗長構成の採用が考えら
れるが、入力バッファ部の後段配置の共通スイッチ部
（コアスイッチ）全体で１つの固まりであり、この冗長
構成の適用は難しかった。

【００１４】また、スケジューラを各入力バッファ部に
分散配置する場合、スケジューリング情報の伝達路がリ
ング状に接続されるため、入力バッファ部間のパッケー
ジカードの一枚を抜いてしまうと、伝達情報が途切れて
しまうことを免れない（図１１参照）。

【００１５】本発明の第１の課題は、メモリアドレスを
ブロック単位で管理し、ブロック内の個別のアドレスは
書き込み時または読み出し時にキュー毎に与えることで
メモリ量を削減することが可能なパケットスイッチ装置
を提供することにある。

【００１６】本発明の第２の課題は、少数の回線収容時
でも必要となっていたパケット多重部（ＭＵＸ）や低速
インタフェースにおける高速バッファメモリの配置を不
要とし、低速から高速まで全ての回線インタフェースを
混在収容することを可能にするパケットスイッチ装置を
提供することにある。

【００１７】本発明の第３の課題は、高速アクセスを実
現しつつ大容量のパケット（セル）バッファメモリを構
成することができるパケットスイッチ装置を提供するこ
とにある。

【００１８】本発明の第４の課題は、出力側のパケット
多重分離部（ＤＭＵＸ）における所要バッファメモリ量
を削減することを可能にするパケットスイッチ装置を提
供することにある。

【００１９】

【課題を解決するための手段】上記課題を解決するため
に、本発明のパケットスイッチ装置は、出力回線対応の
論理的なキューを有する入力バッファメモリ手段と；ス
ケジューリング開始入力回線を示す第１のポインタの制
御手段と；スケジューリング対象回線のスケジューリン
グ開始出力回線を示す第２のポインタの制御手段と；所
望の出力回線に対する送出要求情報を保持する要求管理
制御手段と；複数の送出要求情報の中から前記第２のポ
インタが示す出力回線から検索を開始し、他の入力回線
に確保されていない出力回線を選択するスケジューリン
グ処理手段と；複数の固定長パケットを一時的に保持し
順次に出力するパケットバッファメモリ手段と；前記パ
ケットバッファメモリ手段から出力された固定長パケッ
トをスイッチングする共通スイッチ手段と；前記パケッ
トバッファメモリ手段のアドレスを複数パケット分の固
定長ブロックに分け、アドレス管理をブロック単位に行
うアドレス管理手段とを備える。

【００２０】この構成において、前記アドレス管理手段
は、更にブロック内でどのシーケンス番号のどのアドレ
スがマルチキャストを完了したかを示すフラグにより管
理することもできる。

【００２１】また、本発明のパケットスイッチ装置は、
出力回線対応の論理的なキューを有する入力バッファメ
モリ手段と；スケジューリング開始入力回線を示す第１
のポインタの制御手段と；スケジューリング対象回線の
スケジューリング開始出力回線を示す第２のポインタの
制御手段と；所望の出力回線に対する送出要求情報を保
持する要求管理制御手段と；複数の送出要求情報の中か
ら前記第２のポインタが示す出力回線から検索を開始
し、他の入力回線に確保されていない出力回線を選択す
るスケジューリング処理手段と；複数の固定長パケット
を一時的に保持し順次に出力するパケットバッファメモ
リ手段と；前記パケットバッファメモリ手段から出力さ
れた固定長パケットをスイッチングする共通スイッチ手
段と；複数の出力回線にマルチキャストするために、一
旦マルチキャスト用のメモリに前記パケットを書き込
み、それをマルチキャスト数読み出して、それぞれを所
望のＦＩＦＯメモリに振り分けを行うとき、振り分けは
実際の前記パケットでなくアドレスのみで行うことを論
理的に実現するために、振り分け後のアドレス毎にマル
チキャスト数とそのアドレスとを保持し、前記パケット
バッファメモリ手段のアドレス管理を行うアドレス管理
手段とを備える。

【００２２】上記各パケットスイッチ装置において、前
記パケットバッファメモリ手段は、バーストアクセス時
のみ高速アクセス可能な大容量メモリを前段に、高速ラ
ンダムアクセス可能なメモリを後段に配し、通常は後段
のメモリのみ使用し、後段メモリが一杯になったときは
前段メモリに一時的に保持し、後段メモリに空きができ
た時点で移し替える。

【００２３】また、前記パケットバッファメモリ手段
は、高速ランダムアクセス可能な小容量メモリを用いた
待ち合わせキューを前段に、アクセスが低速な大容量メ
モリをパラレルに後段に配し、後段メモリへの書き込み
動作は、前段メモリからパラレルに行い、後段メモリの
読み出し動作は競合が起こらないキューのみを選択して
読み出しを行う。

【００２４】また、前記パケットバッファメモリ手段
は、高速ランダムアクセス可能な小容量メモリを用いた
待ち合わせキューを前段に、バーストアクセス時のみ高
速アクセス可能な大容量メモリを用いた待ち合わせキュ
ーを後段に配し、後段メモリへの書き込み動作は、前段
メモリに複数パケット溜まった時点でまとめて行い、後
段メモリの読み出し動作は、複数パケットまとめて行
う。

【００２５】さらに、前記パケットバッファメモリ手段
は、複数の入力回線の固定長パケットを１つの入力回線
上に確定的に時分割多重し、多重前の入力回線毎にメモ
リをパラレルに配置し、書き込み及び読み出しを各メモ
リでパラレルに行うことができる。

【００２６】また、前記共通スイッチ手段は、ビットス
ライス構成であり、スライスされた少なくとも１つのス
イッチ手段を冗長に持つことにより、スライスされたス
イッチ手段毎の保守・故障時の切り替えを可能とする。

【００２７】また、前記パケットバッファメモリ手段
は、前記共通スイッチ手段の入力側及び出力側において
それぞれ二重化され、出力側配置の前記パケットバッフ
ァメモリ手段へのデータ分配は予め前記共通スイッチ手
段に設定した方路に基づいて行うことにより、保守・故
障時の切り替えを可能とする。

【００２８】また、前記第１及び第２のポインタの制御
手段と前記要求管理制御手段と前記スケジューリング処
理手段とを含むスケジューラを分散配置し、かつ前記入
力バッファメモリ手段を含む入力バッファ部の隣接する
前記入力バッファ部間のスケジューリング情報を選択す
るためのスイッチ手段を更に設け、保守・故障時の切り
替えを可能とする。

【００２９】本発明の他のパケットスイッチ装置は、出
力回線対応の論理的なキューを有する入力バッファメモ
リ手段と；スケジューリング開始入力回線を示す第１の
ポインタの制御手段と；スケジューリング対象回線のス
ケジューリング開始出力回線を示す第２のポインタの制
御手段と；所望の出力回線に対する送出要求情報を保持
する要求管理制御手段と；複数の送出要求情報の中から
前記第２のポインタが示す出力回線から検索を開始し、
他の入力回線に確保されていない出力回線を選択するス
ケジューリング処理手段と；複数の固定長パケットを一
時的に保持し順次に出力するパケットバッファメモリ手
段と；前記パケットバッファメモリ手段から出力された
固定長パケットをスイッチングする共通スイッチ手段
と；前記パケットバッファメモリ手段のアドレス管理を
行うアドレス管理手段とを備え；前記パケットバッファ
メモリ手段は、バーストアクセス時のみ高速アクセス可
能な大容量メモリを前段に、高速ランダムアクセス可能
なメモリを後段に配し、通常は後段のメモリのみ使用
し、後段メモリが一杯になったときは前段メモリに一時
的に保持し、後段メモリに空きができた時点で移し替え
る。

【００３０】本発明の他のパケットスイッチ装置は、出
力回線対応の論理的なキューを有する入力バッファメモ
リ手段と；スケジューリング開始入力回線を示す第１の
ポインタの制御手段と；スケジューリング対象回線のス
ケジューリング開始出力回線を示す第２のポインタの制
御手段と；所望の出力回線に対する送出要求情報を保持
する要求管理制御手段と；複数の送出要求情報の中から
前記第２のポインタが示す出力回線から検索を開始し、
他の入力回線に確保されていない出力回線を選択するス
ケジューリング処理手段と；複数の固定長パケットを一
時的に保持し順次に出力するパケットバッファメモリ手
段と；前記パケットバッファメモリ手段から出力され
た固定長パケットをスイッチングする共通スイッチ手段
と；前記パケットバッファメモリ手段のアドレス管理を
行うアドレス管理手段とを備え；前記パケットバッファ
メモリ手段は、高速ランダムアクセス可能な小容量メモ
リを用いた待ち合わせキューを前段に、アクセスが低速
な大容量メモリをパラレルに後段に配し、後段メモリへ
の書き込み動作は、前段メモリからパラレルに行い、後
段メモリの読み出し動作は競合が起こらないキューのみ
を選択して読み出しを行う。

【００３１】本発明の他のパケットスイッチ装置は、出
力回線対応の論理的なキューを有する入力バッファメモ
リ手段と；スケジューリング開始入力回線を示す第１の
ポインタの制御手段と；スケジューリング対象回線のス
ケジューリング開始出力回線を示す第２のポインタの制
御手段と；所望の出力回線に対する送出要求情報を保持
する要求管理制御手段と；複数の送出要求情報の中から
前記第２のポインタが示す出力回線から検索を開始し、
他の入力回線に確保されていない出力回線を選択するス
ケジューリング処理手段と；複数の固定長パケットを一
時的に保持し順次に出力するパケットバッファメモリ手
段と；前記パケットバッファメモリ手段から出力された
固定長パケットをスイッチングする共通スイッチ手段
と；前記パケットバッファメモリ手段のアドレス管理を
行うアドレス管理手段とを備え；前記パケットバッファ
メモリ手段は、高速ランダムアクセス可能な小容量メモ
リを用いた待ち合わせキューを前段に、バーストアクセ
ス時のみ高速アクセス可能な大容量メモリを用いた待ち
合わせキューを後段に配し、後段メモリへの書き込み動
作は、前段メモリに複数パケット溜まった時点でまとめ
て行い、後段メモリの読み出し動作は、複数パケットま
とめて行う。

【００３２】本発明の他のパケットスイッチ装置は、出
力回線対応の論理的なキューを有する入力バッファメモ
リ手段と；スケジューリング開始入力回線を示す第１の
ポインタの制御手段と；スケジューリング対象回線のス
ケジューリング開始出力回線を示す第２のポインタの制
御手段と；所望の出力回線に対する送出要求情報を保持
する要求管理制御手段と；複数の送出要求情報の中から
前記第２のポインタが示す出力回線から検索を開始し、
他の入力回線に確保されていない出力回線を選択するス
ケジューリング処理手段と；複数の固定長パケットを一
時的に保持し順次に出力するパケットバッファメモリ手
段と；前記パケットバッファメモリ手段から出力された
固定長パケットをスイッチングする共通スイッチ手段
と；前記パケットバッファメモリ手段のアドレス管理を
行うアドレス管理手段とを備え；前記パケットバッファ
メモリ手段は、複数の入力回線の固定長パケットを１つ
の入力回線上に確定的に時分割多重し、多重前の入力回
線毎にメモリをパラレルに配置し、書き込み及び読み出
しを各メモリでパラレルに行う。

【００３３】上記本発明の他のパケットスイッチ装置の
それぞれの構成において、前記共通スイッチ手段は、ビ
ットスライス構成であり、スライスされた少なくとも１
つのスイッチ手段を冗長に持つことにより、スライスさ
れたスイッチ手段毎の保守・故障時の切り替えを可能と
する。

【００３４】また、前記パケットバッファメモリ手段
は、前記共通スイッチ手段の入力側及び出力側において
それぞれ二重化され、出力側配置の前記パケットバッフ
ァメモリ手段へのデータ分配は予め前記共通スイッチ手
段に設定した方路に基づいて行うことにより、保守・故
障時の切り替えを可能とする。

【００３５】また、前記第１及び第２のポインタの制御
手段と前記要求管理制御手段と前記スケジューリング処
理手段とを含むスケジューラを分散配置し、かつ前記入
力バッファメモリ手段を含む入力バッファ部の隣接する
前記入力バッファ部間のスケジューリング情報を選択す
るためのスイッチ手段を更に設け、保守・故障時の切り
替えを可能とする。

【００３６】本発明の別のパケットスイッチ装置は、あ
る一定速度でスケジューリング処理を行うスケジューリ
ング処理手段と；入力回線速度分のスケジューリング速
度で求められるパケットスロット時間を計測する第１の
タイマ処理手段と；出力回線速度分のスケジューリング
速度で求められるパケットスロット時間を計測する第２
のタイマ処理部とを備え；ある入力回線に対するスケジ
ューリング処理が行われたとき、前記第１のタイマ処理
手段が計測を開始し、以降前記第１のタイマ処理手段が
所定時間を計測する間は、その入力回線に対するスケジ
ューリング処理を停止し、入力回線速度に応じたスケジ
ューリングを実現する。

【００３７】この構成において、ある出力回線に対する
確定が行われたとき、その出力回線に対する前記第２の
タイマ処理手段の計測を開始し、以降前記第２のタイマ
処理手段が所定時間を計測する間は、同一出力回線に対
する確定を停止し、同一出力回線へのトラヒック流を出
力回線速度以下に抑える。

【００３８】また、前記第１及び第２のタイマ処理手段
の計測開始契機をスケジューリング時あるいは確定時と
せずに、固定的な時間間隔とする。さらに、パイプライ
ン的にスケジューリング処理を行う際、スケジューリン
グ速度と入力回線速度との比に基づく前後Ｎ段のパイプ
ライン処理の該当入力回線に対するスケジューリングを
停止し、入力回線速度に応じたスケジューリングを実現
する。

【００３９】前記第２のタイマ処理手段は、パイプライ
ン的にスケジューリング処理を行う際、パイプライン番
号と出力回線番号とに基づきパイプライン処理毎に独立
に制御し、各パイプライン処理内で所定の間隔を守るこ
とで、平均的に各出力回線速度に応じたスケジューリン
グを実現する。

【００４０】

【発明の実施の形態】次に、本発明の実施の形態につい
て図面を参照して説明する。〔パケットスイッチ装置のアドレス管理構成〕本発明の
一実施の形態のパケットスイッチ装置において、メモリ
アドレスについては、アドレスをブロック単位で管理
し、ブロック内の個別のアドレスは書き込み時または読
み出し時にキュー毎に与えることでメモリ量を削減す
る。

【００４１】図１２にブロック単位のアドレス管理手法
を示す。アドレス管理メモリ１２を構成する空きアドレ
スブロック管理メモリ（単に、空きアドレスＦＩＦＯと
記載することもある）１２１及び論理出方路アドレス管
理（読出アドレスブロック管理）メモリ（単に、論理出
方路または読出アドレスＦＩＦＯと記載することもあ
る）１２２は、それぞれブロック番号を管理する。ま
た、論理出方路対応に、ブロック内アドレスを示すシー
ケンスナンバー（ＳＮ）管理ポインタＰＮＴを、書き込
み・読み出し用にそれぞれ用意する。

【００４２】書き込み時は、該当する論理出方路キュー
の書込ブロックアドレスと書込シーケンスナンバー（Ｓ
Ｎ）とにより書込アドレスを発行し、書込ＳＮをインク
リメントする。読み出し時は、該当する論理出方路キュ
ーの読出ブロックアドレスと読出シーケンスナンバー
（ＳＮ）とにより読出アドレスを発行し、読出ＳＮをイ
ンクリメントする。

【００４３】読み出し時または書き込み時において、読
出ＳＮまたは書込ＳＮが一周したら、次のブロックアド
レスを獲得する。これにより、例えば１ブロックを１０
パケットとすれば、アドレス管理メモリ１２の容量を１
／１０に削減することができる。ここで、読出ＳＮ及び
書込ＳＮと読出ブロックアドレス及び書込ブロックアド
レスとは出方路数に対応して用意すればよく、メモリ増
加量は小さい。しかも、アドレスリンク方式を採る場
合、そもそも出方路対応にスタートポインタ及びエンド
ポインタを用意する必要があり、この数とＳＮ及びブロ
ックアドレスのメモリ量とは同一であるため、メモリ量
の増加は発生しない。

【００４４】アドレスリンク方式におけるマルチキャス
ト（ＭＣ）実現手法について図１３を参照して説明す
る。マルチキャストは入力するマルチキャストパケット
を一旦マルチキャストキューに格納し、それを各出方路
の論理出方路キューに振り分けることで実現する。ここ
で、バッファメモリ（セルバッファメモリ１３１）のア
クセス速度を抑えるため、パケット自体は振り分けを行
わず、アドレスのみ各論理出方路アドレスＦＩＦＯ１３
２に振り分ける。論理出方路アドレスＦＩＦＯ１３２は
アドレスリンクにより構成されているため、異なる論理
出方路のアドレスＦＩＦＯは同一のアドレスを使用でき
ない。

【００４５】そこで、振り分け時には新たに空きアドレ
スＦＩＦＯ１３３よりアドレスを取得することとし、そ
のアドレスと実際にパケットが格納されているアドレス
との対応をとるためのバッファアドレステーブル１３４
を用意し、振り分け時にこのテーブル１３４を設定して
おく。読み出し時には、バッファアドレステーブル１３
４で示されるアドレスよりパケットを読み出すことで、
マルチキャストを実現することができる。

【００４６】ここで、バッファアドレステーブル１３４
の同一バッファアドレスに対し、指定された全出方路へ
のマルチキャスト読み出しが終了しない限りは、読出ア
ドレスを空きアドレスＦＩＦＯ１３３に返却できない。
そこで、読み出し数を管理するためのマルチキャスト数
管理テーブル（ビットマップ）１３５をバッファアドレ
ス対応に用意し、全方路への読み出しが終了した時点で
読出アドレスを返却する。この手法はアドレスリンクを
適用しない場合も同様である。

【００４７】次に、アドレスをブロック管理するときの
マルチキャスト手法について図１４を参照して説明す
る。基本的には、図１３を参照して説明したマルチキャ
スト手法と同様であるが、アドレスがブロック管理され
ているため、振り分け時のアドレスは書込ブロックアド
レスと書込ＳＮとから取得する。また、ブロックアドレ
スの空きアドレスＦＩＦＯ１３３への返却は、同一ブロ
ックに含まれるアドレスのマルチキャストが全て終了し
ないと行うことができない。そこで、ブロックアドレス
毎に、各ＳＮの読み出しが終了したかどうかを管理する
ためのマルチキャスト数管理テーブル１３６を持ち、全
ＳＮへの読み出しが終わった時点でブロックアドレスを
返却する。これにより、ブロックアドレス管理でのマル
チキャストを実現することができる。

【００４８】〔パケット（セル）バッファメモリ構成〕
パケット（セル）バッファメモリを構成するために、大
容量のＤＲＡＭをバックアップとして使用した例を図１
５に示す。このセルバッファメモリ１５は通常、小容量
のＳＲＡＭで構成する入力バッファメモリ１５１を用
い、入力回線ＩＨＷからのセル（パケット）のバッファ
リングを行うが、ＳＲＡＭが一杯になった場合、一時的
にＤＲＡＭで構成する入力バッファメモリ１５２にバー
ストアクセスで入力回線ＩＨＷからのセルデータを保持
する。ＳＲＡＭにバースト長分の空きが生じた時点で、
ＤＲＡＭからＳＲＡＭに動作を移し替える。これによ
り、高速アクセスを実現しつつ大容量のセルバッファメ
モリ１５を構成することができる。

【００４９】また、セルバッファメモリを構成するため
に、ＳＲＡＭの入力バッファメモリを入力回線ＩＨＷか
らのセルの一時保持用として使用した例を図１６に示
す。入力回線ＩＨＷからのセルは、論理出方路キュー毎
にＳＲＡＭで構成する一時保持用の入力バッファメモリ
１６１に格納され、キュー毎にバースト数分溜まった時
点で大容量のＤＲＡＭで構成する入力バッファメモリ１
６２にセルデータを移し替える。ＤＲＡＭからの読み出
しは、バースト数分（複数パケット（セル）分）まとめ
て行う。これにより、高速アクセスを実現しつつ大容量
のセルバッファメモリ１６を構成することができる。

【００５０】ここで、負荷の低いケースでは、前段のＳ
ＲＡＭにバースト数分のセルデータが溜まるのに時間が
かかる可能性がある。これに対し、タイマを設け規定時
間を超えたら溜まる前に後段のＤＲＡＭに書き込んでし
まう方法と、前段のＳＲＡＭもスケジューリング対象と
し、その時点で溜まっているセルデータを読み出してし
まう方法により対処可能である。

【００５１】セルバッファメモリを構成するために、複
数のＤＲＡＭをパラレルに配置した例を図１７に示す。
使用するＤＲＡＭは論理出方路対応で分け、例えば全部
で１２８個の回線対応の出力方路の場合は、回線０−３
１対応の出力方路は論理出方路キューＲＡＭ０、回線３
２−６３対応の出方路は論理出方路キューＲＡＭ１、回
線６４−９５対応の出方路は論理出方路キューＲＡＭ
２、及び回線９６−１２７対応の出方路は論理出方路キ
ューＲＡＭ３に割り当てる。

【００５２】入力バッファメモリ１７２を構成するＤＲ
ＡＭの前段には、一時保持用の入力バッファメモリ１７
１を構成するＳＲＡＭが同じ割り当てでパラレルに用意
される。入力したセルは、論理出方路に対応するＳＲＡ
Ｍに書き込まれ、一つずつパラレル配置のＤＲＡＭに移
し替えられる。ＤＲＡＭからの読み出しは、スケジュー
リング時に分割ＲＡＭ間でぶつからないように割り当て
る。つまり、ある回線が選択されたら、その後３回は、
スケジューラがその回線と同一のＲＡＭを使用している
回線を対象としない。これにより、高速アクセスを実現
しつつ大容量セルバッファメモリ１７を構成することが
できる。

【００５３】セルバッファメモリを構成するために、出
力回線ＯＨＷ上に確定的な位置にセルを時分割多重した
場合の例を図１８に示す。この構成は図１７に示した構
成に類似しているが、あらかじめ確定的に分離されてい
るため、パラレル化したＤＲＡＭ１８２に対応するセル
が連続で到着することはない。よって、前段配置のＳＲ
ＡＭが不要になる。その代わり、パラレル化された各Ｄ
ＲＡＭ１８２から任意の出方路に出力されるため、それ
ぞれのＤＲＡＭ１８２を論理出方路キューに分割する必
要がある。これにより、高速アクセスを実現しつつ大容
量セルバッファメモリ１８を構成することができる。

【００５４】〔冗長構成〕スイッチ部のコアスイッチの
冗長構成例を図１９に示す。スイッチ部１９１のコアス
イッチ１９１１についてＮ＋１ビットスライスで構成し
た場合、同一のスライススイッチ１９１１が複数（Ｎ個
＝１６）並列に配置されることになる。このスライスス
イッチ１９１１を1つあるいは複数余計に用意すること
により、切り替えが可能となる。切り替えは、入力バッ
ファ部１９２の任意のビットにおいてＮ個の現用系スラ
イススイッチから冗長（予備系）スライススイッチ１９
１２に出力することを選択するセレクタ１９２１と、入
力バッファ部１９２の受け側で各ビットか冗長スライス
スイッチ１９１２からのデータかを選択するセレクタ１
９２２，１９２３とを用意することで可能となる。

【００５５】また、それぞれセレクタを任意のビットか
ら任意のスライススイッチに切り替えできるようにする
と、どのスライススイッチが冗長スライススイッチかを
意識することなく切り替えることも可能である。

【００５６】入力バッファ部のパケット（セル）バッフ
ァメモリ２０２の冗長構成を図２０に示す。送信回線側
及び受信回線側については対向の二重化装置との関係で
二重化したいケースもあるが、スイッチ部２０１のコア
スイッチがＮ＋１冗長構成であるため、交絡を設けられ
ない。そこで、コアスイッチにコピー機能を設けてお
き、現用（ＡＣＴ）系からの入力セルのみを、スイッチ
部２０１に通すことで、二重化することができる。スイ
ッチ部２０１のコピー方法は、セルにコピー制御ビット
を付与する方法と、スイッチ部自体に設定する方法とが
ある。

【００５７】スケジューリング情報の切り替え構成を図
２１に示す。入力バッファ部のパッケージ化されたパケ
ットバッファメモリ２１１を抜いてもスケジューリング
情報の受け渡しができるように、パケットバッファメモ
リ２１１対応にバイパススイッチ（スケジューリング情
報切替部）２１２を設ける。そして、バイパスするとき
は、パケット（セル）バッファメモリ２１１における制
御遅延分を加味することにより、途中で動作を止めるこ
となく切り替えることが可能になる。

【００５８】図２１におけるバイバススイッチ２１２の
詳細構成例を示す図２２を参照すると、バイパススイッ
チ２１２には隣接バイパススイッチ及び入力バッファ部
からの２系統のスケジューリング信号が入力される。そ
れぞれのスケジューリング信号の同期信号を同期信号抽
出部２１２０，２１２１で抽出し、図示省略の制御部か
らの基準フレーム信号との位相差を位相差検出部２１２
２，２１２３で検出する。その結果を位相調整バッファ
２１２４，２１２５の読出制御部２１２６，２１２７に
通知し、位相差を吸収する。

【００５９】また、タイミング調整部２１２８において
基準フレーム信号に同期した上記制御部からの切替信号
によって、出力スケジューリング信号の切替えをセレク
タ２１２９により行う。スケジューリング信号の同期信
号としては、フレーム信号の並走や周期的な同期パター
ン（例えば、固定パターンやＣＲＣ）などがある。書込
制御部２１３０，２１３１は位相調整バッファ２１２
４，２１２５へのスケジューリング信号の書き込みを制
御する。

【００６０】図２３に上記バイパススイッチ２１２の動
作例を示す。（ａ）初期状態では、基準フレーム信号に従いセレクタ
２１２９を通してでループを構成する。（ｂ）入力バッファ部を構成する新しいパッケージが組
み込まれると、まず入力バッファ部においてスケジュー
リング信号のフレーム検出により、同期確立を行う。（ｃ）次に、バイパススイッチ２１２において、入力バ
ッファ部側についてスケジューリング信号のフレーム検
出により、同期確立を行う。（ｄ）同期確立後、バイパススイッチ２１２のセレクタ
２１２９を切り替えることにより、増設した入力バッフ
ァ部のスケジューリング信号が送出される。（ｅ）入力バッファ部を構成する新しいパッケージを更
に増設するときは、同様の手順を踏む。（ｆ）パッケージの取り替えは、バイパススイッチ２１
２のセレクタ２１２９の切替後に行う。

【００６１】〔第１のスケジューラの構成・動作〕本発
明の一実施の形態のパケットスイッチ装置における入力
バッファ部のスケジューラの構成を示す図２４を参照す
ると、要求管理部２２１は入力バッファメモリから通知
される送出要求数を管理する。第１のタイマ処理部
（１）２２２は自己入力回線ＩＨＷに対するスケジュー
リング周期を計測する。第２のタイマ処理部（２）２２
３は各論理出方路対応に備えられ、その出力回線に対す
るスケジューリング割り当ての周期を計測する。スケジ
ューリング処理部２２４はタイマ処理部（１）２２２で
スケジューリング可能と判断されたときにスケジューリ
ング処理を行い、要求管理部２２１に送出要求のある出
力回線で、かつタイマ処理部（２）２２３で割り当て可
能と指示された出方路のなかからスケジューリングアル
ゴリズムに従って出方路を確定するものである。各スケ
ジューラ２２は入力回線（入力方路）ＩＨＷ対応に設け
られる。

【００６２】この構成において、ある入力回線に対する
スケジューリング処理を行ったとき、タイマ処理部
（１）２２２において、所定時間（スケジューリング速
度／入力回線速度）の計測を開始する。そして、所定時
間が経過するまでは、スケジューリング処理部２２４に
対してスケジューリング処理不可の停止指示を行って入
力回線速度以上の速度でスケジューリングを行わないよ
うにする。したがって、スケジューラ２２から入力バッ
ファメモリに対して送出要求を通知する契機も入力回線
速度となり、その結果、低速回線インタフェースには高
速な入力バッファメモリが不要となる（動作例１）。

【００６３】また、ある入力回線のスケジューリング処
理過程において、ある出力回線（出方路）ＯＨＷが確定
されたとき、タイマ処理部（２）２２３において、所定
時間（スケジューリング速度／出力回線速度）の計測を
開始する。そして、所定時間が経過するまでは、スケジ
ューリング処理部２２４に対して、その出力回線に対す
る割り当て不可の停止指示を行って、出力回線速度以上
でスケジューリングが行われないようにしている。した
がって、スケジューラ２２が入力バッファメモリに対し
て、その出力回線に送出せよという指示の周期も、出力
回線速度以下となり、その結果、出力回線に対してその
回線速度以上のトラヒック流入を抑止でき、大容量の入
力バッファメモリが不要となる（動作例２）。

【００６４】スケジューリング周期が１単位時間では完
結せず、数単位時間かけてパイプライン処理を行う際
に、上記動作例１で説明した動作を行うために、あるパ
イプライン処理段のある入力回線のスケジューリング処
理が行われたとき、そのパイプライン処理段の前後Ｎ
（スケジューリング速度／入力回線速度）段のスケジュ
ーラに対して、その入力回線に対するスケジューリング
処理不可を指示する。この結果、スケジューラから入力
バッファメモリに対して行われる読み出し指示が入力回
線速度以上で行われることを抑制できる（動作例３）。

【００６５】また、スケジューリング周期が１単位時間
では完結せず、数単位時間かけてパイプライン処理を行
う際に、上記動作例２で説明した動作を行うために、あ
るパイプライン処理段のある入力回線のスケジューリン
グ処理において、ある出力回線が確定されたとき、その
パイプライン段のスケジューラ２２に対して、Ｎ（スケ
ジューリング速度／出力回線速度）パイプライン周期の
間、その出力回線に対する割り当て不可を指示する。こ
の結果、出力回線に対してその回線速度以上のトラヒッ
ク流が流入しなくなり、大容量の入力バッファメモリが
不要となる（動作例４）。

【００６６】タイマ処理部（１）２２２及びタイマ処理
部（２）２２３の計測契機を周期的に行うようにし、タ
イマ処理部２２２，２２３の負荷軽減を図る。この結
果、上記動作例２及び４に比べると、出力トラヒック流
のバースト性が強まる傾向にあるが、タイマ処理部の負
荷軽減を図るとともに、周期的にスケジューリングまた
は割り当て許可の指示が現れるため、他のスケジューラ
にどの出力回線が確定不可であるかを通知する必要がな
く、スケジューラ間の情報受け渡しの量を削減すること
ができる（動作例５）。

【００６７】〔パケットスイッチ装置の動作〕本発明の
一実施の形態のパケットスイッチ装置の動作について、
図２５から図３７を順次参照して説明する。図２５は書
き込み動作手順、図２６，図２７に書き込み動作例、図
２８にマルチキャスト動作手順、図２９から図３２にマ
ルチキャスト動作例、図３３に読み出し動作手順、図３
４から図３７に読み出し動作例を示す。

【００６８】（ポインタ基本処理）まず、アドレスＦＩ
ＦＯへの追加動作及びアドレスＦＩＦＯからの読出動作
について説明する。

【００６９】（１）アドレスＦＩＦＯへの追加動作：ア
ドレスＦＩＦＯが空のときは、追加するアドレスをスタ
ート（ＳＴＡＲＴ）ポインタＳ−ＰＮＴ及びエンド（Ｅ
ＮＤ）ポインタＥ−ＰＮＴにそれぞれ設定する。一方、
アドレスＦＩＦＯが空で無いときは、ＥＮＤポインタが
示すアドレスリンクに追加するアドレスを設定する。更
に、ＥＮＤポインタに追加するアドレスを設定する。

【００７０】（２）アドレスＦＩＦＯから読出動作：Ｓ
ＴＡＲＴポインタが示すアドレスを獲得する。ＳＴＡＲ
Ｔポインタが示すアドレスリンクより、ＮＥＸＴアドレ
スを獲得する。更に、ＳＴＡＲＴポインタにＮＥＸＴア
ドレスを設定する。

【００７１】アドレスＦＩＦＯが空かどうかは、キュー
長カウンタより識別する。ただし、空きアドレスＦＩＦ
Ｏ（空きアドレスブロック管理メモリ）はキュー長カウ
ンタを持たない。そこで、空きアドレスＦＩＦＯは必ず
空きにならないように、次のように管理する。つまり、
初期はアドレス０番を空きアドレスＦＩＦＯに割り当て
る。空きアドレス生成カウンタはアドレス１番から書込
アドレスを生成する。書込アドレス獲得時、ＳＴＡＲＴ
ポインタとＥＮＤポインタとが等しいならば、入力セル
を廃棄する。

【００７２】（書き込み動作）到着セルをセルバッファ
メモリに書き込み、対応する論理出方路キューのアドレ
スリンクを更新する。書込アドレスは空きアドレスＦＩ
ＦＯの先頭より獲得する。ただし、初期状態では空きア
ドレスＦＩＦＯには何も設定されていない。そこで、初
期動作用に書込アドレスを生成するカウンタ、つまり初
期アドレス生成カウンタＩＮＩ−ＣＮＴを設ける。初期
アドレス生成カウンタＩＮＩ−ＣＮＴが最大（ＭＡＸ）
値になるまでは、このカウンタより書き込みアドレスを
獲得し、ＭＡＸ値になったらカウンタを止め、以降は空
きアドレスＦＩＦＯより書き込みアドレスを獲得する。

【００７３】空きアドレスＦＩＦＯから書込アドレスを
獲得できなかった場合は、入力セルを廃棄する。また、
マルチキャスト（ＭＣ）動作との整合のため、バッファ
アドレス領域にも書込アドレスを保持する。更に、ＭＣ
ルーティングビット領域に対し、ユニキャストセルの場
合は出方路番号をビットマップに変換した値を、マルチ
キャストセルの場合はＭＣルーチングビットを保持す
る。

【００７４】書き込み手順は次に示すＳ１からＳ７であ
る。つまり、Ｓ１：書込アドレスの獲得、Ｓ２：到着セルを書込アドレスに対応するセルバッファ
メモリに書き込む、Ｓ３：到着セルのヘッダ情報に対応する論理キューのア
ドレスＦＩＦＯに書込アドレスを追加、Ｓ４：書込アドレスをバッファアドレス領域に保持、Ｓ５：入力セルがユニキャストセルの場合、出方路番号
に対応するＭＣルーチングビットをセット、Ｓ６：入力セルがマルチキャストセルの場合、ＭＣルー
チングビットを保持、Ｓ７：対応する論理キュー、共通バッファ（セルバッフ
ァメモリ）のキュー長カウンタをインクリメントする。

【００７５】（マルチキャスト動作）論理マルチキャス
トキューのアドレスＦＩＦＯよりＭＣアドレスを読み出
し、これをＭＣ先頭アドレスとしてレジスタに保持す
る。次に、対応するＭＣルーティングビットをＳＳＲＡ
Ｍより読み出し、ＭＣ残ルーティングビットとしてレジ
スタに保持する。そして、ＭＣ残ルーティングビットを
参照し、対応する論理出方路キューにアドレスを振り分
ける。振り分けは、１パケット（セル）時間に１出方路
づつ行う。振り分けるアドレスは、最初の出方路はＭＣ
先頭アドレスを、２回目以降は新たに空きアドレスＦＩ
ＦＯから取得したＭＣ追加アドレスを使用する。

【００７６】ただし、実際のセルはＭＣ先頭アドレスに
対応するセルバッファメモリに書き込まれているため、
バッファアドレスとしてＭＣ先頭アドレスを新たに取得
したアドレス毎に保持する。マルチキャストの１セル目
であるかどうかは、ＭＣ先頭アドレス有効レジスタによ
り判断する。

【００７７】マルチキャスト処理手順は次に示すＳ１１
からＳ１８及びＳ２１からＳ２６である。つまり、１セル目：Ｓ１１：論理マルチキャストキューのＭＣア
ドレスをＭＣ先頭アドレスレジスタに保持、Ｓ１２：ＭＣ先頭アドレスに対応するＭＣルーティンク
ビットをＭＣ残ルーティングビットレジスタに保持、Ｓ１３：ＭＣ残ルーティンクビットが立っている回線の
うち、一番若い回線を選択、Ｓ１４：選択回線に対応する論理キューのアドレスＦＩ
ＦＯにＭＣ先頭アドレスを追加、Ｓ１５：ＭＣ先頭アドレスに対応するバッファアドレス
領域にＭＣ先頭アドレスを設定、Ｓ１６：ＭＣ残ルーティンクビットに対し、選択回線に
対応するビットを「０」に更新、Ｓ１７：対応するＭＣキューのキュー長カウンタをデク
リメント、Ｓ１８：対応する論理キューのキュー長カウンタをイン
クリメントする。２セル目以降：Ｓ２１：空きアドレスＦＩＦＯよりＭＣ追加アドレスを
獲得、Ｓ２２：ＭＣ残ルーティンクビットが立っている回線の
うち、一番若番の回線を選択、Ｓ２３：選択回線に対応する論理キューのアドレスＦＩ
ＦＯにＭＣ追加アドレスを追加、Ｓ２４：ＭＣ追加アドレスに対応するバッファアドレス
領域にＭＣ先頭アドレスを設定、Ｓ２５：ＭＣ残ルーティンクビットに対し、選択回線に
対応するビットを「０」に更新、Ｓ２６：対応する論理キュー、共通バッファのキュー長
カウンタをインクリメントする。

【００７８】ＭＣ残ルーティンクビットがオール「０」
になるまでこの動作を続ける。オール「０」になった
ら、そのセルのマルチキャストは終了し、ＭＣ先頭アド
レス有効レジスタをリセットする。次のスロットで新た
なＭＣアドレスを論理マルチキャストキューより獲得
し、始めの動作に戻る。また、空きアドレスＦＩＦＯよ
りアドレスが獲得できなかった場合は、そのスロットで
のマルチキャスト動作を止め、アドレスが獲得できるま
で待つ。

【００７９】（読み出し動作）対応する論理出方路キュ
ーのアドレスＦＩＦＯより読出アドレスを獲得し、読出
アドレスに対応するバッファアドレスのセルバッファメ
モリより、セル読み出しを行う。その後、読出アドレス
がバッファアドレスに一致しないときのみ、読出アドレ
スの返却を行う。さらに、バッファアドレスに対応する
ＭＣビットマップの読出回線に対応するビットをクリア
する。その結果、オール「０」であれば、対応するセル
の読み出しが全て完了したと判定し、バッファアドレス
を空きアドレスＦＩＦＯに返却する。

【００８０】読み出し手順は次に示すＳ３１からＳ３６
である。つまり、Ｓ３１：論理出方路キューのアドレスＦＩＦＯより、読
出アドレスを獲得、Ｓ３２：読出アドレスに対応するバッファアドレスよ
り、セルを読み出す、Ｓ３３：バッファアドレスと読出アドレスとが一致しな
い場合、読出アドレスをアドレスＦＩＦＯに追加し、共
通バッファのキュー長カウンタをデクリメント、Ｓ３４：バッファアドレスに対応するＭＣビットマップ
に対し、読出回線に対応するビットをクリア、Ｓ３５：クリア後のＭＣビットマップがオール「０」な
ら、バッファアドレスをアドレスＦＩＦＯに追加し、共
通バッファのキュー長カウンタをデクリメント、Ｓ３６：対応する論理キューのキュー長カウンタをデク
リメントする。

【００８１】〔第２のスケジューラの構成・動作〕本発
明の一実施の形態のパケットスイッチ装置における入力
バッファ部のスケジューラの構成を示す図３８を参照す
ると、要求管理部３６１は入力バッファメモリから通知
される送出要求数を管理する。第１のタイマ処理部
（１）３６２は自己入力回線に対するスケジューリング
周期を計測する。第２のタイマ処理部（２）３６３は各
論理出方路対応に備えられ、その出力回線に対するスケ
ジューリング割り当ての周期を計測する。スケジューリ
ング処理部３６４はタイマ処理部（１）３６２でスケジ
ューリング可能と判断されたときにスケジューリング処
理を行い、要求管理部３６１に送出要求のある出力回線
で、かつタイマ処理部（２）３６３で割り当て可能と指
示された出方路のなかからスケジューリングアルゴリズ
ムに従って出方路を確定するものである。

【００８２】各スケジューラ（ＳＣＨ）３６は入力回線
（入力方路）ＩＨＷ対応に設けられ、１単位時間内、こ
こでは、１パケット（セル）時間内、各入力回線で出力
方路が競合しない様に、自己入力回線のパケット送出出
方路を決定すべく、スケジューリングアルゴリズムに従
って出力回線を確定する。

【００８３】（入力回線速度スケジューリングの必要
性）図３９は９．６Ｇｂｐｓの伝送速度のポートを有す
るＮ×Ｎコアスイッチ（スイッチ部）３７１に、伝送速
度の異なる入力回線を入力バッファ部３７２，３７３，
３７４を通して収容した例を示す。この例では、伝送速
度２．４Ｇｂｐｓのインタフェースの入力回線＃０及び
伝送速度４．８Ｇｂｐｓのインタフェースの入力回線＃
５が伝送速度の異なる入力回線として収容されている。

【００８４】この入力回線の収容形態において、何も速
度制御を行わなければ、各スケジューラ（ＳＣＨ）３７
２１，３７３１は単位時間（ここでは、９．６Ｇｂｐ
ｓ）の速度で、各入力回線に対してスケジューリングを
行ってしまい、２．４Ｇｂｐｓのバッファリング能力し
か持たない入力回線＃０や４．８Ｇｂｐｓのバッファリ
ング能力しかない入力回線＃５に対して、９．６Ｇｂｐ
ｓの速度で送出指示を送ってしまう。すなわち、入力バ
ッファ部３７２，３７３に高速な入力バッファメモリ３
７２２，３７３２が必要になる。

【００８５】（入力回線速度でスケジューリングを行う
動作）図４０を用いて入力回線速度でスケジューリング
を行う例を説明する。入力バッファ部に高速バッファメ
モリを設置することを回避するためには、各入力回線は
下記のパケット（セル）時間間隔以上でスケジューリン
グされなければいけない。入力回線＃０：４パケット時間（＝９．６Ｇｂｐｓ／
２．４Ｇｂｐｓ）入力回線＃５：２パケット時間（＝９．６Ｇｂｐｓ／
４．８Ｇｂｐｓ）時刻Ｔ＝１において、入力回線＃０に対するスケジュー
リング処理が行われたとする。ただし、スケジューリン
グの結果、実際に割り当てが行われたか否かは問わな
い。このとき、スケジューラ＃０のタイマ処理部（１）
３６２（図３９参照）は、所定間隔の計測を開始し、ス
ケジューリング処理部３６４に対してスケジューリング
停止信号を通知する。所定時間の計測は、パケット時間
毎にカウンタのインクリメントを行う単純なカウンタ回
路で実現できる。そして、スケジューリング停止信号
は、スケジューリング処理が行われたときにセットさ
れ、所定の計測時間経過した時点で解除される。

【００８６】時刻Ｔ＝２では、まだ所定の時間が経過し
ていない、つまりスケジューリング停止信号がＬｏｗ
（０）レベルであるため、スケジューリングを行うこと
ができない。このように、スケジューリング処理部３６
４は、スケジューリング停止信号をスケジューリング処
理のイネーブル信号として用いており、停止信号がＬｏ
ｗレベルの時はスケジューリング処理を行わない。

【００８７】入力回線＃０のスケジューリング停止信号
は、時刻Ｔ＝５において解除される、つまりＨｉｇｈ
（１）レベルになるため、時刻Ｔ＝５では入力回線＃０
のスケジューリングを行うことができる。上記制御によ
って、入力回線＃０のスケジューリング処理周期は、４
パケット時間間隔となる。図４０中、スケジューリング
処理が行われるタイムスロットを斜線で示している。

【００８８】入力回線＃５の処理も上記と同様であり、
時刻Ｔ＝１において、入力回線＃５のスケジューリング
処理が行われたとすると、スケジューラ＃５のタイマ処
理部（１）３６２が所定時間の計測を開始して時刻Ｔ＝
２経過までスケジューリング停止信号を送出し、スケジ
ューラ３６４は、時刻Ｔ＝２においては入力回線＃５の
スケジューリングを行わない。

【００８９】上記の様に、スケジューリング処理が行わ
れた時点から所定時間の間、スケジューリング停止信号
をタイマ処理部（１）３６２からスケジューリング処理
部３６４に通知することで、スケジューリング契機が入
力回線速度周期で行われるため、必然的にスケジューラ
３６から入力バッファ部への読み出し指示の契機も入力
回線速度となる。この結果、入力バッファ部には、その
入力回線速度と同じ速度で読み出し可能なバッファメモ
リだけがあればよい。

【００９０】入力回線速度に応じたスケジューリングの
処理手順Ｓ３９１からＳ３９８を図４１に示す。Ｓ３９
２からＳ３９５はスケジューリング処理プロセスであ
る。単位時間毎にイベントが発生すると（Ｓ３９１）、
Ｓ３９２において、スケジューリング停止信号の論理で
現在のスケジューリング状態を判定し、判定結果が
「１」の場合、すなわち、スケジューリング可能状態で
あればＳ３９３からＳ３９５の処理を行う。一方、判定
結果が「０」の場合（スケジューリング不可）には、ス
ケジューリング処理を行わない。

【００９１】上記判定結果、「１」のケースでは、Ｓ３
９３で所定の入力回線のスケジューリング処理を行い、
Ｓ３９４及びＳ３９５で、スケジューリング停止信号及
びスケジューリング停止区間を管理するタイマ（タイマ
１）を「０」にセットする。

【００９２】Ｓ３９６からＳ３９８は、スケジューリン
グ停止信号の更新処理である。パケット時間ごとにタイ
マをインクリメントし（Ｓ３９６）、その結果が所定の
時間を超えているか否かを判定する（Ｓ３９７）。タイ
マ値が所定時間を超えていた場合には、スケジューリン
グ停止信号を「１」にセットする（Ｓ３９８）。

【００９３】このように、タイマ処理によって、所定時
間（＝１／入力回線速度）の間はスケジューリング停止
信号が「０」にセットされる。この結果、所定時間の間
は、スケジューリング処理が実行されないため、入力回
線以上の速度でスケジューリング処理を行わないように
制御することができる。

【００９４】（出力回線速度スケジューリングの必要
性）図４２には伝送速度２．４Ｇｂｐｓの出力回線＃Ｃ
に対して、伝送速度２．４Ｇｂｐｓの入力回線＃Ａと伝
送速度４．８Ｇｂｐｓの入力回線＃Ｂとからのパケット
をコアスイッチ４０１を通して送出した例を示してい
る。この場合、入力回線＃Ａ対応の入力バッファ部４０
２からはコアスイッチ４０１に伝送速度２．４Ｇｂｐｓ
でパケットが送出され、かつ入力回線＃Ｂ対応の入力バ
ッファ部４０３からはコアスイッチ４０１に伝送速度
４．８Ｇｂｐｓでパケットが送出されるため、出力回線
＃Ｃ対応の出力バッファ部４０４の出力バッファメモリ
４０４１には、合計７．２Ｇｂｐｓのトラヒックが流入
することになる。

【００９５】この７．２Ｇｂｐｓのトラヒック流を受信
する出力回線＃Ｃ対応の出力バッファ部４０４は、２．
４Ｇｂｐｓの読出速度しかもっておらず、パケット廃棄
を回避するためには大容量の出力バッファメモリ４０４
１が必要となる。

【００９６】（出力回線速度でスケジューリング処理の
確定を行う動作）図４３を参照して出力回線速度に応じ
たスケジューリング動作を説明する。出力側のバッファ
メモリ量を小さくするためには、その出力回線に流入す
るトラヒックを出力回線速度以下に抑えなければならな
い。したがって、全入力回線においてひとつの出力回線
に送出する間隔をその出力回線速度に制御すべく、この
例では、各出力回線へのスケジューリング割り当ての間
隔を以下の時間で設ける必要がある。出力回線＃２：２パケット時間（＝９．６Ｇｂｐｓ／
４．８Ｇｂｐｓ）出力回線＃４：４パケット時間（＝９．６Ｇｂｐｓ／
２．４Ｇｂｐｓ）時刻Ｔ＝２において、入力回線＃１のスケジューリング
処理が行われ出力回線＃２が確定したとする。この時、
入力回線＃１のスケジューラは、他の全スケジューラに
対して出力回線＃２を確定したことを通知する。そし
て、この通知を受信した各スケジューラは、自己タイマ
処理部（１）の出力回線（この例では、出力回線＃２）
に対応するタイマの計測を開始し、自己スケジューリン
グ処理部に対して割り当て停止信号を通知する。タイマ
処理部（１）と同様に、タイマ処理部（２）もパケット
時間毎にインクリメントを行う、カウンタ回路を用いて
所定時間の計測を行うことができる。

【００９７】割り当て停止信号は、スケジューリング割
り当てが行われるか、他スケジューラからの確定通知を
受信した際にセットされ、タイマ処理部（２）の所定時
間経過した後に解除される。スケジューリング処理部
は、この割り当て停止信号が通知されていない（すなわ
ち停止状態でない）出力回線に対して送出確定を行う。

【００９８】この例の時刻Ｔ＝３では、出力回線＃２の
割り当て停止信号（Ｌｏｗレベル）が通知されているた
め、どのスケジューラも出力回線＃２に対する割り当て
は行えない。そして、時刻Ｔ＝４において、タイマ処理
部（２）の計測が完了し、出力回線＃２の割り当て停止
信号が解除されている。その結果、時刻Ｔ＝４の入力回
線＃５において、あらためて出力回線＃２への割り当て
が行われている。図４３中、出力回線＃２への割り当て
を斜線で示している。

【００９９】一方、出力回線＃４への割り当ても同様の
手順で処理が行われる。時刻Ｔ＝２において入力回線＃
５のスケジューリング処理が行われ、出力回線＃４の確
定が行われたとき、同様の手順で、全スケジューラに対
して出力回線＃４の確定を行ったことを通知する。前述
した様に各スケジューラのタイマ処理部（２）の出力回
線＃４に対する所定時間の計測を開始し、出力回線＃４
の割り当て停止信号をスケジューリング処理部に通知す
る。図４３中、出力回線＃４に対する割り当てをクロス
斜線で示す。

【０１００】このように、この例においては、時刻Ｔ＝
３では、出力回線＃２及び出力回線＃４の割り当てを行
うことができず、また時刻Ｔ＝４〜Ｔ＝５では、出力回
線＃４の割り当てが行われない。

【０１０１】同図中の斜線部とクロス斜線部とをそれぞ
れ個別に見てみると、出力回線＃２への割り当て契機
（図中、斜線ブロック）は、少なくとも２パケット時間
以上あいており、また出力回線＃４への割り当ては、４
パケット以上あいている。この時間間隔は、それぞれの
出力回線にパケットが到着することと等価であり、各出
力方路へのトラヒックを出力回線速度以下に抑えること
ができることを示している。

【０１０２】出力回線速度に応じたスケジューリングの
処理手順Ｓ４２０１からＳ４２１４を図４４に示す。Ｓ
４２０２からＳ４２０４は割り当て停止タイマ処理の初
期化シーケンスである。単位時間毎にイベントが発生す
ると（Ｓ４２０１）、Ｓ４２０２において、他スケジュ
ーラから確定通知を受信したときに、自スケジューラの
割り当て停止信号を「０」にセットし（Ｓ４２０３）、
タイマ（タイマ２）を「０」にセットする（Ｓ４２０
４）。確定通知を受信しなかった場合は、何も処理を行
わない。

【０１０３】Ｓ４２０５からＳ４２０８はスケジューリ
ング処理及びスケジューリング処理後の割り当て停止タ
イマ処理の初期化シーケンスである。Ｓ４２０５では、
自スケジューラの割り当て停止信号＃Ｎ＿Ｍ（Ｎ：入力
回線番号、Ｍ：出力回線番号）が「１」にセットされて
いる出力回線の中から送出回線を確定するようにスケジ
ューリング処理を行う。そして、スケジューリング処理
が確定した後、確定した出力回線に対応する割り当て停
止信号＃Ｎ＿Ｍ（Ｎ：確定入力回線番号、Ｍ：確定出力
回線番号）、及び対応するタイマ（Ｎ：確定入力回線番
号、Ｍ：確定出力回線番号）を「０」にセットする（Ｓ
４２０７，Ｓ４２０８）。

【０１０４】Ｓ４２０９からＳ４２１３は次時刻のスケ
ジューリング停止信号を更新するシーケンスである。Ｓ
４２０９において、入力回線数（Ｋ）分の処理が終了し
たかを判定し、全入力回線の更新処理が終了した後、出
力回線番号ｍを「０」にセット（Ｓ４２１４）して処理
を終了する。本図では、処理をシリーズに行っている
が、並列処理で行っても良い。Ｓ４２１０は、入力回線
数（Ｋ）分の処理を行ったか否かをカウントするカウン
タであり、上記並列処理の際には不要となる。

【０１０５】Ｓ４２１１からＳ４２１３は、スケジュー
リング停止信号の更新シーケンスである。Ｓ４２１１に
おいて、パケット時間毎にタイマ値をインクリメントし
（Ｓ４２１１）、その結果が所定時間（＝１／出力回線
レート）を超えているかを判定する（Ｓ４２１２）。Ｓ
４２１２において、所定時間を超過していると判定され
た場合には、対応する割り当て停止信号を「１」にセッ
トする（Ｓ４２１３）。

【０１０６】このように、Ｓ４２１１からＳ４２１３に
おいて、所定時間（＝１／出力回線レート）の間、割り
当て停止信号を「０」にセットして、Ｓ４２０５におい
て各々のスケジューラが、各出力回線に対して各出力回
線レート以上で割り当てを行わないように、割り当て停
止信号が「０」の出力回線に対して割り当てを行わない
ように制御している。

【０１０７】〔第３のスケジューラの構成・動作〕本発
明の一実施の形態のパケットスイッチ装置における入力
バッファ部のスケジューラの構成を示す図４５を参照す
ると、このスケジューラ４３は各パイプライン処理ごと
にスケジューリング処理部４３４とタイマ処理部（２）
４３３とをそれぞれ有している。要求管理部４３１及び
タイマ処理部（１）４３２は図３８に示す第２のスケジ
ューラと同様に動作する。

【０１０８】次に、１回のスケジューリング処理をＭパ
ケット時間かけて、パイプライン的にスケジューリング
を行う場合の回線速度に応じたスケジューリング方式に
ついて説明する。

【０１０９】図４６にパイプラインシーケンスを示す。
同図中、各時刻（Ｔ）対応の四角の中の数字は、スケジ
ューリング対象の入力回線番号を示す。ここでは、４×
４スイッチを想定して、４パケット時間かけて１回のス
ケジューリングを完了させる例をとって説明する。４パ
ケット時間費やしてスケジューリング処理を行い、パケ
ット時間毎に結果を得るために、４倍の並列度を持つパ
イプライン構成となる。

【０１１０】各スケジューラ４３は、自分の入力回線番
号の位置でスケジューリング処理を行う。例えば、時刻
Ｔ＝１では、入力回線＃０のパイプライン処理＃０、入
力回線＃１のパイプライン処理＃０、入力回線＃３のパ
イプライン処理＃２、及び入力回線＃２のパイプライン
処理２のスケジューリング処理が行われる。同図中の太
線ＴＴは、スケジューラ４３から入力バッファメモリに
送出指示を通知することを表しており、時刻Ｔ＝１〜Ｔ
＝３のパイプライン処理＃０のスケジューリング結果が
時刻Ｔ＝４で対応の入力バッファメモリに通知されるこ
とを意味する。また、空欄の時刻にはスケジューリング
処理を行わないことを示している。

【０１１１】（入力回線速度に応じたスケジューリング
割り当ての方法）図４６に示す上記パイプライン構成に
おいて、例えば、時刻Ｔ＝８かつパイプライン処理＃３
において、入力回線＃３のスケジューリング処理が行わ
れたとする。入力回線＃３は４．８Ｇｂｐｓの回線速度
であるため、スケジューリング間隔は２パケット時間
（スケジューリング速度／入力回線速度＝９．６Ｇｂｐ
ｓ／４．８Ｇｂｐｓ）に制限しなければならない。ここ
で確定した結果は、実際には、時刻Ｔ＝１１で入力バッ
ファメモリに通知されるため、時刻Ｔ＝１０及びＴ＝１
２では、入力回線＃３に対する読出指示を与えないよう
にする必要がある。

【０１１２】そのため、時刻Ｔ＝８でスケジューリング
処理が行われた後、そのパイプライン処理段の前後Ｎ段
（ここで、Ｎはスケジューリング速度／入力回線速度で
求められ、この例では１）のパイプライン処理内で入力
回線＃３に対するスケジューリングを行わないように、
入力回線＃３のスケジューリング処理を行ったとき、前
後１段、すなわちパイプライン＃２とパイプライン＃０
に対して、入力回線＃３に対するスケジューリング不可
信号を通知する。同図中、入力回線＃３に対するスケジ
ューリング不可の区間を斜線で表記した。

【０１１３】同様に入力回線＃０の場合も、その回線が
スケジューリングされた時点から前後Ｎ段（Ｎ＝３）の
パイプライン処理段に対してスケジューリング停止信号
を通知し、入力回線＃０へのスケジューリングを行わな
いように制御する。

【０１１４】このように、パイプライン構成を用いる場
合でも、そのパイプライン段の前後Ｎ段のスケジューリ
ング処理部４３４にスケジューリング停止信号を通知す
ることで、入力回線速度に応じたスケジューリングが可
能となる。

【０１１５】（入力回線速度でスケジューリングを行う
動作）入力回線速度に応じたスケジューリング動作の処
理手順Ｓ４５１からＳ４５６を図４７に示す。同図中、
条件１は、停止信号を送出するスケジューリング周期を
示している。例えば、図４６において、時刻Ｔ＝２０で
伝送速度６２２Ｍｂｐｓの入力回線＃１のスケジューリ
ングが行われたとする。この場合、上述したようにスケ
ジューリング確定点から前後１６段（９．６Ｇｂｐｓ／
６２２Ｍｂｐｓ）のパイプライン処理の間、スケジュー
リング停止を行わなければならない。

【０１１６】そこで、各パイプライン処理部（タイマ処
理部）が、それぞれ幾つ分のパイプライン処理時間待た
なければならないかの停止パイプライン周期を下記の式
で求める。

【０１１７】停止パイプライン周期＝（ＦｓｔＰＰＬ＋
Ｋ−ＰＰ）／ＰＰＬＮここで、ＦｓｔＰＰＬ：スケジューリング処理を行った
パイプライン番号Ｋ：スケジューリング速度／入力回線速度ＰＰ：自己パイプライン番号ＰＰＬＮ：総パイプライン段数この例における停止パイプライン周期はそれぞれ次のよ
うになる。パイプライン＃０：（１＋１６−０）／４＝４．２５＝
４周期パイプライン＃１：（１＋１６−１）／４＝４．００＝
４周期パイプライン＃２：（１＋１６−２）／４＝３．７５＝
３周期パイプライン＃３：（１＋１６−３）／４＝３．５０＝
３周期（出力回線速度に応じたスケジューリング割り当ての方
法）パイプライン構成を採る場合は、各パイプライン処
理ごとに独立に出力速度を守るように制御する。図４８
を参照して出力回線速度に応じたスケジューリング処理
を説明する。例えば、時刻Ｔ＝８かつパイプライン処理
＃３の入力回線＃２のスケジューリング結果が出力回線
＃０に確定されたとき、そのパイプライン周期の次のＮ
パイプライン周期の間、パイプライン処理＃３では出力
回線＃０に対する割り当てを行わないようにする。出力
回線＃２の回線速度が２．４Ｇｂｐｓのため、上記Ｎ周
期は次式で求められる。

【０１１８】Ｎ＝スケジューリング速度／出力回線速度
（Ｎ＝９．６Ｇｂｐｓ／２．４Ｇｂｐｓ＝４）時刻Ｔ＝１０において、パイプライン処理＃３かつ入力
回線＃１のスケジューリング処理時、出力回線＃３が確
定したときも同様の手段で次の１周期の間、パイプライ
ン処理＃３では出力回線＃３に対する割り当てを行わな
い。ここで、時刻Ｔ＝９でも、パイプライン処理＃０か
つ入力回線＃０のスケジューリング処理において、同一
出力回線＃３への割り当てが行われており、その結果、
時刻Ｔ＝１１及びＴ＝１２で連続して出力回線＃３へパ
ケットが流入する。しかし、これは長い周期でみれば、
平均的に出力回線速度のレートで送出されている。

【０１１９】このように、パイプライン構成では、各パ
イプライン処理毎に所定の間隔で割り当てを行うこと
で、平均的にその出力回線速度以下の速度でパケットが
流入するため、出力バッファメモリ量は少なくて済む。

【０１２０】図４９に出力回線速度に応じたスケジュー
リング動作の処理手順Ｓ４７１からＳ４７９を示す。Ｓ
４７２からＳ４７４はスケジューリング処理及びスケジ
ューリング確定後の割り当て停止信号、タイマの初期化
シーケンスである。単位時間毎にイベントが発生すると
（Ｓ４７１）、Ｓ４７２では、現時刻のスケジューリン
グ対象の入力回線について、割り当て停止信号が「１」
にセットされている出力回線の中から送出回線を確定す
る。そして、確定したパイプライン処理段、入力回線、
出力回線に対応する割り当て停止信号、及びタイマ値を
「０」にセットする（Ｓ４７３，Ｓ４７４）。

【０１２１】Ｓ４７５からＳ４７９は割り当て停止信号
の更新プロセスである。Ｓ４７５において、全パイプラ
イン処理段分の処理が終了したかを判定し、全パイプラ
イン処理段分の処理が完了した後、処理を終了する。Ｓ
４７６は、パイプライン処理の終りであるかを判定する
プロセスであり、通常、Ｎ段のパイプライン処理段があ
ると、ひとつのパイプライン処理はＮ単位時間で完結す
る。このプロセスは各パイプライン処理の最終時刻を判
定するものであり、最終時刻の判定は各パイプライン処
理毎にカウンタを持って、カウンタ値がＮになった時に
最終時刻と判定しても良いし、外部からパイプライン処
理の最終時刻である旨の指示を与えても良い。

【０１２２】Ｓ４７７からＳ４７９は割り当て停止信号
の更新プロセスであり、Ｓ４７６において、パイプライ
ン処理の最終時刻に、対応するタイマ値をインクリメン
トし（Ｓ４７７）、その結果が所定の周期（＝１／出力
回線レート）を超えているかを判定する（Ｓ４７８）。
所定の周期を超えている場合には、対応する割り当て停
止信号を「１」にセットする。

【０１２３】このように、Ｓ４７７からＳ４７９におい
て、所定の周期の間、割り当て停止信号を「０」にセッ
トして、各パイプライン処理段のスケジューリング処理
Ｓ４７２において、各出力回線に対して各出力回線レー
ト以上で割り当てを行わないように、割り当て停止信号
が「０」の出力回線に対して割り当てを行わないように
制御し、この制御を各パイプライン処理段毎に独立に行
うことによって、平均的に所定の出力回線レート以上の
割り当てを行わないように制御することが可能となる。

【０１２４】〔第４のスケジューラの構成・動作〕上記
第３のスケジューラにおいては、スケジューリング割り
当てを契機として、タイマ処理部（２）のタイマ計測を
開始しており、パケットが読み出されてから計測を行う
ため、出力回線の入り口でみたとき、バースト性の低い
トラヒックとなる。しかし、同一パイプライン処理内の
異なるスケジューラに対して、あとどれくらい停止信号
を送出すべきかを伝達する必要があり、隣接スケジュー
ラに対して情報通知を行う必要がある。

【０１２５】次に述べる第４のスケジューラでは、この
情報通知を削減すべく、全スケジューラで共通のフレー
ム信号を持ち、そのフレーム信号に従って出力回線の割
り当てを行う。そのフレーム信号の形式を図５０に示し
ている。なお、第４のスケジューラの構成は図４５に示
す第３のスケジューラの構成と同一である。

【０１２６】（出力回線速度に応じたスケジューリング
処理）各スケジューラ内にパイプライン処理ごとに１パ
ケット時間づつ位相がずれている出力回線速度に応じた
固定フレーム信号を有している。図５０中のフレーム信
号ＦＲはパイプライン処理＃３のものである。この信号
のＨｉｇｈレベルの領域でその出力回線に対するスケジ
ューリング割り当てが可能な領域とし、Ｌｏｗレベルの
区間を停止区間とすることで、前述のスケジューラ間の
情報伝達が不要になる。同図中、各パイプライン処理の
フレーム信号のＬｏｗレベルの領域を斜線で示してい
る。しかし、同図からも分かるように、ひとつの出力回
線に連続してＮ個（Ｎ：パイプライン数）割り当てが行
えるため、Ｎ個連続してパケットが送出され、トラヒッ
ク流のバースト性が強くなる。

【０１２７】〔変形例〕上記実施の形態では、パイプラ
イン処理内の入力回線番号の並びは一例であり、どのよ
うな並びであってもよい。また、上記実施の形態では、
入力回線速度に応じたスケジューリングと出力回線速度
に応じたスケジューリングとの動作について、それぞれ
個別に説明しているが、入力回線速度に応じてスケジュ
ーリング対象入力回線を決定し、出力回線速度に応じて
スケジューリング割り当てを確定することで、入出力と
もに速度対応のスケジューリングを行うことができる。

【０１２８】さらに、上記実施の形態では、入力バッフ
ァ型スイッチ装置について詳述したが、出力バッファ部
に入力バッファ部と同様の構成を採用した入出力バッフ
ァ型スイッチ装置（図５１参照）にもこの発明は適用で
きる。

【０１２９】

【発明の効果】以上説明したように、本発明によれば、
メモリアドレスをブロック単位で管理し、ブロック内の
個別のアドレスは書き込み時または読み出し時にキュー
毎に与えることでメモリ量を削減することができる。

【０１３０】また、本発明によれば、少数の回線収容時
でも必要となっていたパケット多重部（ＭＵＸ）や低速
インタフェースにおける高速バッファメモリの配置を不
要とし、低速から高速まで全ての回線インタフェースを
混在収容することができる。

【０１３１】また、本発明によれば、高速アクセスを実
現しつつ大容量のパケット（セル）バッファメモリを構
成することができる。

【０１３２】さらに、本発明によれば、出力側のパケッ
ト多重分離部（ＤＭＵＸ）における所要バッファメモリ
量を削減することができる。

【図面の簡単な説明】

【図１】パケットスイッチ装置の入力バッファ部を説
明するためのブロック図。

【図２】パケットスイッチ装置の入力バッファ部を説
明するためのブロック図。

【図３】パケットスイッチ装置の入力バッファ部及び
スイッチ部を説明するためのブロック図。

【図４】パケットスイッチ装置の入力バッファ部を説
明するためのブロック図。

【図５】パケットスイッチ装置のアドレス管理ＦＩＦ
Ｏを説明するための図。

【図６】パケットスイッチ装置のＤＲＡＭのバースト
アクセスを説明するための図。

【図７】パケットスイッチ装置の入力バッファ部及び
スイッチ部の二重化構成を説明するためのブロック図。

【図８】パケットスイッチ装置のパケットバッファメ
モリとアドレスリンクとの共用を説明するためのブロッ
ク図。

【図９】パケットスイッチ装置のマルチキャスト時の
アドレス管理ＦＩＦＯを説明するための図。

【図１０】パケットスイッチ装置のＤＲＡＭのパラレ
ルアクセスを説明するための図。

【図１１】パケットスイッチ装置のスケジューリング
情報の切断を説明するための図。

【図１２】本発明のパケットスイッチ装置のアドレス
ブロック管理手法を説明するための図。

【図１３】アドレスリンクにおけるマルチキャストを
説明するための図。

【図１４】ブロック管理手法におけるマルチキャスト
を説明するための図。

【図１５】セルバッファメモリの構成例を示すブロッ
ク図。

【図１６】セルバッファメモリの構成例を示すブロッ
ク図。

【図１７】セルバッファメモリの構成例を示すブロッ
ク図。

【図１８】セルバッファメモリの構成例を示すブロッ
ク図。

【図１９】コアスイッチの冗長構成例を示すブロック
図。

【図２０】セルバッファメモリの冗長構成例を示すブ
ロック図。

【図２１】スケジューリング情報の切替構成を示すブ
ロック図。

【図２２】バイパススイッチの詳細構成を示すブロッ
ク図。

【図２３】バイパススイッチの動作例を示すブロック
図。

【図２４】第１のスケジューラの構成を示すブロック
図。

【図２５】書込動作を説明するための図。

【図２６】ユニキャスト書込動作を説明するための
図。

【図２７】マルチキャスト書込動作を説明するための
図。

【図２８】マルチキャスト動作を説明するための図。

【図２９】マルチキャスト動作を説明するための図。

【図３０】マルチキャスト振り分け動作を説明するた
めの図。

【図３１】マルチキャスト振り分け動作を説明するた
めの図。

【図３２】マルチキャスト振り分け動作を説明するた
めの図。

【図３３】読出動作を説明するための図。

【図３４】読出動作を説明するための図。

【図３５】読出動作を説明するための図。

【図３６】読出動作を説明するための図。

【図３７】読出動作を説明するための図。

【図３８】第２のスケジューラの構成を示すブロック
図。

【図３９】入力バッファ部の処理能力の問題を説明す
るための図。

【図４０】入力回線速度に応じたスケジューリング処
理を説明するための図。

【図４１】入力回線速度に応じたスケジューリング処
理手順を説明するための図。

【図４２】出力トラヒック流の問題を説明するための
図。

【図４３】出力回線速度に応じたスケジューリング処
理を説明するための図。

【図４４】出力回線速度に応じたスケジューリング処
理手順を説明するための図。

【図４５】第３のスケジューラの構成を示すブロック
図。

【図４６】入力回線速度に応じたスケジューリング処
理を説明するための図。

【図４７】入力回線速度に応じたスケジューリング処
理手順を説明するための図。

【図４８】出力回線速度に応じたスケジューリング処
理を説明するための図。

【図４９】出力回線速度に応じたスケジューリング処
理手順を説明するための図。

【図５０】第４のスケジューラにおける出力回線速度
に応じたスケジューリング処理を説明するための図。

【図５１】入出力バッファ型スイッチ装置の構成例を
示すブロック図。

【符号の説明】

１２アドレス管理メモリ１２１空きアドレスブロック管理メモリ１２２読出アドレスブロック管理メモリ１３１，１５，１６，１７，１８，１９２，２０２，２
１１セルバッファメモリ１３２アドレスＦＩＦＯ１３３空きアドレスＦＩＦＯ１９１，２０１スイッチ部２２，３６，４３スケジューラ２２１，３６１，４３１要求管理部２２２，３６２，４３２タイマ処理部（１）２２３，３６３，４３３タイマ処理部（２）２２４，３６４，４３４スケジューリング処理部

───────────────────────────────────────────────────── フロントページの続き (72)発明者瓦井健一神奈川県川崎市中原区上小田中４丁目１番１号富士通株式会社内 (72)発明者加藤次雄神奈川県川崎市中原区上小田中４丁目１番１号富士通株式会社内Ｆターム(参考） 5K030 GA06 HA10 HB29 JA01 KA21 KX01 KX12 KX18 LD06 LE06 MA13 MB13 MB15

Claims

【特許請求の範囲】

【請求項１】出力回線対応の論理的なキューを有する
入力バッファメモリ手段と；スケジューリング開始入力
回線を示す第１のポインタの制御手段と；スケジューリ
ング対象回線のスケジューリング開始出力回線を示す第
２のポインタの制御手段と；所望の出力回線に対する送
出要求情報を保持する要求管理制御手段と；複数の送出
要求情報の中から前記第２のポインタが示す出力回線か
ら検索を開始し、他の入力回線に確保されていない出力
回線を選択するスケジューリング処理手段と；複数の固
定長パケットを一時的に保持し順次に出力するパケット
バッファメモリ手段と；前記パケットバッファメモリ手
段から出力された固定長パケットをスイッチングする共
通スイッチ手段と；前記パケットバッファメモリ手段の
アドレスを複数パケット分の固定長ブロックに分け、ア
ドレス管理をブロック単位に行うアドレス管理手段と；
を備えることを特徴とするパケットスイッチ装置。
【請求項２】出力回線対応の論理的なキューを有する
入力バッファメモリ手段と；スケジューリング開始入力
回線を示す第１のポインタの制御手段と；スケジューリ
ング対象回線のスケジューリング開始出力回線を示す第
２のポインタの制御手段と；所望の出力回線に対する送
出要求情報を保持する要求管理制御手段と；複数の送出
要求情報の中から前記第２のポインタが示す出力回線か
ら検索を開始し、他の入力回線に確保されていない出力
回線を選択するスケジューリング処理手段と；複数の固
定長パケットを一時的に保持し順次に出力するパケット
バッファメモリ手段と；前記パケットバッファメモリ手
段から出力された固定長パケットをスイッチングする共
通スイッチ手段と；複数の出力回線にマルチキャストす
るために、一旦マルチキャスト用のメモリに前記パケッ
トを書き込み、それをマルチキャスト数読み出して、そ
れぞれを所望のＦＩＦＯメモリに振り分けを行うとき、
振り分けは実際の前記パケットでなくアドレスのみで行
うことを論理的に実現するために、振り分け後のアドレ
ス毎にマルチキャスト数とそのアドレスとを保持し、前
記パケットバッファメモリ手段のアドレス管理を行うア
ドレス管理手段と；を備えることを特徴とするパケット
スイッチ装置。
【請求項３】前記アドレス管理手段は、更にブロック
内でどのシーケンス番号のどのアドレスがマルチキャス
トを完了したかを示すフラグにより管理することを特徴
とする請求項１記載のパケットスイッチ装置。
【請求項４】前記パケットバッファメモリ手段は、バ
ーストアクセス時のみ高速アクセス可能な大容量メモリ
を前段に、高速ランダムアクセス可能なメモリを後段に
配し、通常は後段のメモリのみ使用し、後段メモリが一
杯になったときは前段メモリに一時的に保持し、後段メ
モリに空きができた時点で移し替えることを特徴とする
請求項１または２記載のパケットスイッチ装置。
【請求項５】前記パケットバッファメモリ手段は、高
速ランダムアクセス可能な小容量メモリを用いた待ち合
わせキューを前段に、アクセスが低速な大容量メモリを
パラレルに後段に配し、後段メモリへの書き込み動作
は、前段メモリからパラレルに行い、後段メモリの読み
出し動作は競合が起こらないキューのみを選択して読み
出しを行うことを特徴とする請求項１または２記載のパ
ケットスイッチ装置。
【請求項６】前記パケットバッファメモリ手段は、高
速ランダムアクセス可能な小容量メモリを用いた待ち合
わせキューを前段に、バーストアクセス時のみ高速アク
セス可能な大容量メモリを用いた待ち合わせキューを後
段に配し、後段メモリへの書き込み動作は、前段メモリ
に複数パケット溜まった時点でまとめて行い、後段メモ
リの読み出し動作は、複数パケットまとめて行うことを
特徴とする請求項１または２記載のパケットスイッチ装
置。
【請求項７】前記パケットバッファメモリ手段は、複
数の入力回線の固定長パケットを１つの入力回線上に確
定的に時分割多重し、多重前の入力回線毎にメモリをパ
ラレルに配置し、書き込み及び読み出しを各メモリでパ
ラレルに行うことを特徴とする請求項１または２記載の
パケットスイッチ装置。
【請求項８】前記共通スイッチ手段は、ビットスライ
ス構成であり、スライスされた少なくとも１つのスイッ
チ手段を冗長に持つことにより、スライスされたスイッ
チ手段毎の保守・故障時の切り替えを可能とすることを
特徴とする請求項１または２記載のパケットスイッチ装
置。
【請求項９】前記パケットバッファメモリ手段は、前
記共通スイッチ手段の入力側及び出力側においてそれぞ
れ二重化され、出力側配置の前記パケットバッファメモ
リ手段へのデータ分配は予め前記共通スイッチ手段に設
定した方路に基づいて行うことにより、保守・故障時の
切り替えを可能とすることを特徴とする請求項１または
２記載のパケットスイッチ装置。
【請求項１０】前記第１及び第２のポインタの制御手
段と前記要求管理制御手段と前記スケジューリング処理
手段とを含むスケジューラを分散配置し、かつ前記入力
バッファメモリ手段を含む入力バッファ部の隣接する前
記入力バッファ部間のスケジューリング情報を選択する
ためのスイッチ手段を更に設け、保守・故障時の切り替
えを可能とすることを特徴とする請求項１または２記載
のパケットスイッチ装置。
【請求項１１】出力回線対応の論理的なキューを有す
る入力バッファメモリ手段と；スケジューリング開始入
力回線を示す第１のポインタの制御手段と；スケジュー
リング対象回線のスケジューリング開始出力回線を示す
第２のポインタの制御手段と；所望の出力回線に対する
送出要求情報を保持する要求管理制御手段と；複数の送
出要求情報の中から前記第２のポインタが示す出力回線
から検索を開始し、他の入力回線に確保されていない出
力回線を選択するスケジューリング処理手段と；複数の
固定長パケットを一時的に保持し順次に出力するパケッ
トバッファメモリ手段と；前記パケットバッファメモリ
手段から出力された固定長パケットをスイッチングする
共通スイッチ手段と；前記パケットバッファメモリ手段
のアドレス管理を行うアドレス管理手段とを備え；前記
パケットバッファメモリ手段は、バーストアクセス時の
み高速アクセス可能な大容量メモリを前段に、高速ラン
ダムアクセス可能なメモリを後段に配し、通常は後段の
メモリのみ使用し、後段メモリが一杯になったときは前
段メモリに一時的に保持し、後段メモリに空きができた
時点で移し替えることを特徴とするパケットスイッチ装
置。
【請求項１２】出力回線対応の論理的なキューを有す
る入力バッファメモリ手段と；スケジューリング開始入
力回線を示す第１のポインタの制御手段と；スケジュー
リング対象回線のスケジューリング開始出力回線を示す
第２のポインタの制御手段と；所望の出力回線に対する
送出要求情報を保持する要求管理制御手段と；複数の送
出要求情報の中から前記第２のポインタが示す出力回線
から検索を開始し、他の入力回線に確保されていない出
力回線を選択するスケジューリング処理手段と；複数の
固定長パケットを一時的に保持し順次に出力するパケッ
トバッファメモリ手段と；前記パケットバッファメモリ
手段から出力された固定長パケットをスイッチングする
共通スイッチ手段と；前記パケットバッファメモリ手段
のアドレス管理を行うアドレス管理手段とを備え；前記
パケットバッファメモリ手段は、高速ランダムアクセス
可能な小容量メモリを用いた待ち合わせキューを前段
に、アクセスが低速な大容量メモリをパラレルに後段に
配し、後段メモリへの書き込み動作は、前段メモリから
パラレルに行い、後段メモリの読み出し動作は競合が起
こらないキューのみを選択して読み出しを行うことを特
徴とするパケットスイッチ装置。
【請求項１３】出力回線対応の論理的なキューを有す
る入力バッファメモリ手段と；スケジューリング開始入
力回線を示す第１のポインタの制御手段と；スケジュー
リング対象回線のスケジューリング開始出力回線を示す
第２のポインタの制御手段と；所望の出力回線に対する
送出要求情報を保持する要求管理制御手段と；複数の送
出要求情報の中から前記第２のポインタが示す出力回線
から検索を開始し、他の入力回線に確保されていない出
力回線を選択するスケジューリング処理手段と；複数の
固定長パケットを一時的に保持し順次に出力するパケッ
トバッファメモリ手段と；前記パケットバッファメモリ
手段から出力された固定長パケットをスイッチングする
共通スイッチ手段と；前記パケットバッファメモリ手段
のアドレス管理を行うアドレス管理手段とを備え；前記
パケットバッファメモリ手段は、高速ランダムアクセス
可能な小容量メモリを用いた待ち合わせキューを前段
に、バーストアクセス時のみ高速アクセス可能な大容量
メモリを用いた待ち合わせキューを後段に配し、後段メ
モリへの書き込み動作は、前段メモリに複数パケット溜
まった時点でまとめて行い、後段メモリの読み出し動作
は、複数パケットまとめて行うことを特徴とするパケッ
トスイッチ装置。
【請求項１４】出力回線対応の論理的なキューを有す
る入力バッファメモリ手段と；スケジューリング開始入
力回線を示す第１のポインタの制御手段と；スケジュー
リング対象回線のスケジューリング開始出力回線を示す
第２のポインタの制御手段と；所望の出力回線に対する
送出要求情報を保持する要求管理制御手段と；複数の送
出要求情報の中から前記第２のポインタが示す出力回線
から検索を開始し、他の入力回線に確保されていない出
力回線を選択するスケジューリング処理手段と；複数の
固定長パケットを一時的に保持し順次に出力するパケッ
トバッファメモリ手段と；前記パケットバッファメモリ
手段から出力された固定長パケットをスイッチングする
共通スイッチ手段と；前記パケットバッファメモリ手段
のアドレス管理を行うアドレス管理手段とを備え；前記
パケットバッファメモリ手段は、複数の入力回線の固定
長パケットを１つの入力回線上に確定的に時分割多重
し、多重前の入力回線毎にメモリをパラレルに配置し、
書き込み及び読み出しを各メモリでパラレルに行うこと
を特徴とするパケットスイッチ装置。
【請求項１５】前記共通スイッチ手段は、ビットスラ
イス構成であり、スライスされた少なくとも１つのスイ
ッチ手段を冗長に持つことにより、スライスされたスイ
ッチ手段毎の保守・故障時の切り替えを可能とすること
を特徴とする請求項１１，１２，１３または１４記載の
パケットスイッチ装置。
【請求項１６】前記パケットバッファメモリ手段は、
前記共通スイッチ手段の入力側及び出力側においてそれ
ぞれ二重化され、出力側配置の前記パケットバッファメ
モリ手段へのデータ分配は予め前記共通スイッチ手段に
設定した方路に基づいて行うことにより、保守・故障時
の切り替えを可能とすることを特徴とする請求項１１，
１２，１３，１４または１５記載のパケットスイッチ装
置。
【請求項１７】前記第１及び第２のポインタの制御手
段と前記要求管理制御手段と前記スケジューリング処理
手段とを含むスケジューラを分散配置し、かつ前記入力
バッファメモリ手段を含む入力バッファ部の隣接する前
記入力バッファ部間のスケジューリング情報を選択する
ためのスイッチ手段を更に設け、保守・故障時の切り替
えを可能とすることを特徴とする請求項１１，１２，１
３，１４，１５または１６記載のパケットスイッチ装
置。
【請求項１８】ある一定速度でスケジューリング処理
を行うスケジューリング処理手段と；入力回線速度分の
スケジューリング速度で求められるパケットスロット時
間を計測する第１のタイマ処理手段と；出力回線速度分
のスケジューリング速度で求められるパケットスロット
時間を計測する第２のタイマ処理部とを備え；ある入力
回線に対するスケジューリング処理が行われたとき、前
記第１のタイマ処理手段が計測を開始し、以降前記第１
のタイマ処理手段が所定時間を計測する間は、その入力
回線に対するスケジューリング処理を停止し、入力回線
速度に応じたスケジューリングを実現することを特徴と
するパケットスイッチ装置。
【請求項１９】ある出力回線に対する確定が行われた
とき、その出力回線に対する前記第２のタイマ処理手段
の計測を開始し、以降前記第２のタイマ処理手段が所定
時間を計測する間は、同一出力回線に対する確定を停止
し、同一出力回線へのトラヒック流を出力回線速度以下
に抑えることを特徴とする請求項１８記載のパケットス
イッチ装置。
【請求項２０】前記第１及び第２のタイマ処理手段の
計測開始契機をスケジューリング時あるいは確定時とせ
ずに、固定的な時間間隔とすることを特徴とする請求項
１８記載のパケットスイッチ装置。
【請求項２１】パイプライン的にスケジューリング処
理を行う際、スケジューリング速度と入力回線速度との
比に基づく前後Ｎ段のパイプライン処理の該当入力回線
に対するスケジューリングを停止し、入力回線速度に応
じたスケジューリングを実現することを特徴とする請求
項１８記載のパケットスイッチ装置。
【請求項２２】前記第２のタイマ処理手段は、パイプ
ライン的にスケジューリング処理を行う際、パイプライ
ン番号と出力回線番号とに基づきパイプライン処理毎に
独立に制御し、各パイプライン処理内で所定の間隔を守
ることで、平均的に各出力回線速度に応じたスケジュー
リングを実現することを特徴とする請求項１８記載のパ
ケットスイッチ装置。