(57)【要約】【課題】通信制御装置に設けられたメモリを効率的に使用する。【解決手段】実施の１形態のスイッチ装置１０は、固定長のセグメントを記憶領域の管理単位として、中継すべきパケットを一時的に保持するための複数のセグメントを含むパケットバッファ３４と、中継すべきパケットを外部の通信ノード１２から受け付け、あるセグメントにおける空き領域の開始位置を示すオフセットを参照して、そのセグメントにおけるオフセットが示す開始位置から第１のパケットを格納するとともにそのパケット長に応じてオフセットが示す開始位置を更新し、そのセグメントにおける更新後の開始位置から第２のパケットを格納する入力処理部４４と、パケットバッファ３４から第１および第２のパケットを読み出して通信ノード１２へ送出する出力処理部４６とを備える。【選択図】図２
2011130249.tif 000002
【特許請求の範囲】
【請求項１】
固定長のセグメントを記憶領域の管理単位として、中継すべきパケットを一時的に保持するための複数のセグメントを含むメモリと、
中継すべきパケットを外部から受け付けるパケット受付部と、
あるセグメントにおける空き領域の開始位置を示すオフセットを参照して、前記セグメントにおける前記オフセットが示す開始位置からパケットを格納するとともにそのパケット長に応じて前記オフセットが示す開始位置を更新し、前記セグメントにおける更新後の開始位置から別のパケットを格納するパケット書込部と、
前記開始位置から前記パケットを読み出し、前記更新後の開始位置から前記別のパケットを読み出して、それぞれのパケットを外部へ送出するパケット送出部と、
を備えることを特徴とする通信制御装置。
【請求項２】
前記パケット書込部は、前記オフセットにより特定されるセグメントの空き容量をパケット長が超過する場合、超過したパケットのデータを別のセグメントへ格納するとともに、前記オフセットが示す開始位置を、前記別のセグメントに残存する空き領域の開始位置を示すよう更新することを特徴とする請求項１に記載の通信制御装置。
【請求項３】
前記複数のセグメントのそれぞれに対応づけて、各セグメントに格納された各パケットが読み出されるべき回数の合計値を保持する読み出し回数保持部と、
セグメント解放部と、をさらに備え、
前記パケット書込部は、前記パケット受付部において受け付けられたパケットをセグメントへ格納する際、当該セグメントに対応づけられた前記合計値を増加させ、
前記パケット送出部は、セグメントに格納されたパケットを読み出した際、当該セグメントに対応づけられた前記合計値を減少させ、
前記セグメント解放部は、前記合計値が０になったセグメントを新たに空き領域として設定することを特徴とする請求項１または２に記載の通信制御装置。
【請求項４】
前記パケット書込部は、複数の出力ポートから送出されるべきパケットをセグメントへ格納する際、当該セグメントに対応づけられた前記合計値を、当該パケットが送出されるべき出力ポートの数に応じて増加させ、
前記パケット送出部は、前記複数の出力ポートのいずれかから前記パケットを送出すべき際、前記セグメントから前記パケットを読み出すとともに、前記セグメントに対応づけられた前記合計値を逐次減少させることを特徴とする請求項３に記載の通信制御装置。
【請求項５】
空き領域として設定されたセグメントの情報を保持する空きセグメント情報保持部と、
前記空き領域として設定されたセグメントのうちパケットを格納すべきセグメントの情報を指し示す先頭ポインタと、新たに空き領域として設定されたセグメントの情報を格納すべき位置を指し示す末尾ポインタと、をさらに備え、
前記パケット書込部は、前記先頭ポインタにより特定されるセグメントへパケットを格納し、
前記セグメント解放部は、新たに空き領域として設定したセグメントの情報を前記末尾ポインタの指し示す位置へ格納し、当該セグメントが前記先頭ポインタにより特定されるものである場合はさらに、別のセグメントの情報を指し示すよう前記先頭ポインタを更新することを特徴とする請求項３または４に記載の通信制御装置。
【請求項６】
固定長のセグメントを記憶領域の管理単位として、中継すべきパケットを一時的に保持するための複数のセグメントを含むメモリを備える通信装置を制御するプログラムであって、
中継すべきパケットを外部から受け付けるパケット受付機能と、
あるセグメントにおける空き領域の開始位置を示すオフセットを参照して、前記セグメントにおける前記オフセットが示す開始位置からパケットを格納するとともにそのパケット長に応じて前記オフセットが示す開始位置を更新し、前記セグメントにおける更新後の開始位置から別のパケットを格納するパケット書込機能と、
前記開始位置から前記パケットを読み出し、前記更新後の開始位置から前記別のパケットを読み出して、それぞれのパケットを外部へ送出するパケット送出機能と、
を前記通信装置に実現させることを特徴とする通信制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データ通信技術に関し、特に、通信パケットを中継するための通信制御技術に関する。
【背景技術】
【０００２】
近年、高速インターネットやＩＰ（Internet Protocol）電話が普及してきている。これに伴って、イーサネットパケット（「イーサネット」は登録商標）やＩＰパケット等の通信パケット（以下、単に「パケット」とも呼ぶ。）の高速な伝送が必要になっている。そのため、レイヤ２スイッチ・レイヤ３スイッチ・ルータ等の通信制御装置においてパケット中継処理の高速化が求められている。
【０００３】
通信制御装置には、その内部に、パケットのデータを一時的に保持するためのメモリ（以下、「パケットバッファ」とも呼ぶ）が設けられている。一般的にパケットのデータは可変長であるが、通信制御装置において可変長の記憶領域を管理することは処理の複雑化を招く。そのため、パケットバッファを固定長の管理単位（以下、「セグメント」とも呼ぶ）に分割し、１パケットを１以上のセグメントに割り当て、１セグメントには１パケットの構成データを格納して管理していた。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１３０３６６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
通信制御装置が高速・大容量になるに伴いパケットバッファも大容量化し、セグメントで保持可能なデータサイズも増大している。本発明者は、１セグメントに対し１パケットの構成データを格納する方式では、セグメントに生じる未使用領域が大きいという課題を認識した。
【０００６】
本発明は、こうした課題に鑑みてなされたものであり、その主たる目的は、通信制御装置に設けられたメモリを効率的に使用する技術を提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明のある態様の通信制御装置は、固定長のセグメントを記憶領域の管理単位として、中継すべきパケットを一時的に保持するための複数のセグメントを含むメモリと、中継すべきパケットを外部から受け付けるパケット受付部と、あるセグメントにおける空き領域の開始位置を示すオフセットを参照して、セグメントにおけるオフセットが示す開始位置からパケットを格納するとともにそのパケット長に応じてオフセットが示す開始位置を更新し、セグメントにおける更新後の開始位置から別のパケットを格納するパケット書込部と、開始位置からパケットを読み出し、更新後の開始位置から別のパケットを読み出して、それぞれのパケットを外部へ送出するパケット送出部と、を備える。
【０００８】
通信制御装置は、外部の通信ノードから受け付けられた通信パケットを一時的にバッファリングし、別の通信ノードへ中継するスイッチ装置であってもよい。例えば、レイヤ２スイッチ、レイヤ３スイッチ、ブリッジ、ルータ等であってもよい。セグメントは、パケットのバッファリング処理に対して、メモリの記憶領域が割り当てられる単位であってもよく、その割り当てが解放される単位であってもよい。この態様によると、１つのセグメントに複数のパケットのデータを格納することにより、セグメントの空き領域サイズを低減し、メモリを効率的に使用できる。
【０００９】
パケット書込部は、オフセットにより特定されるセグメントの空き容量をパケット長が超過する場合、超過したパケットのデータを別のセグメントへ格納するとともに、オフセットが示す開始位置を、別のセグメントに残存する空き領域の開始位置を示すよう更新してもよい。
【００１０】
別のセグメントは、空き領域として設定されたセグメントの情報を保持するテーブルにおいて、パケットの格納優先順位が最上位、もしくはオフセットが指し示すセグメントに続く次点のセグメントであってもよい。この態様によると、セグメントの空き容量がパケット長よりも短い場合は、そのセグメントには空き容量分のパケットのデータが格納され、残りは別のセグメントに格納される。これにより、１つのセグメントにおけるパケット格納領域の全体を有効に活用でき、メモリを効率的に使用できる。
【００１１】
複数のセグメントのそれぞれに対応づけて、各セグメントに格納された各パケットが読み出されるべき回数の合計値を保持する読み出し回数保持部と、セグメント解放部と、をさらに備えてもよい。パケット書込部は、パケット受付部において受け付けられたパケットをセグメントへ格納する際、当該セグメントに対応づけられた合計値を増加させ、パケット送出部は、セグメントに格納されたパケットを読み出した際、当該セグメントに対応づけられた合計値を減少させ、セグメント解放部は、合計値が０になったセグメントを新たに空き領域として設定してもよい。
【００１２】
新たに空き領域として設定するとは、空き領域として設定されたセグメントの情報を保持するテーブルへ、合計値が０になったセグメントの情報を追加することでもよい。また、セグメントとして割り当てられたメモリの記憶領域を適宜解放してもよい。この態様によると、セグメントに格納された複数のパケットそれぞれの読み出しが完了すると、言い換えれば、セグメントの格納データに対する最後の参照が完了すると、そのセグメントが空き領域として設定されて、新たなパケットが格納される。これにより、セグメントに格納されたパケットを保護しつつ、そのセグメントの再利用を実現できる。
【００１３】
パケット書込部は、複数の出力ポートから送出されるべきパケットをセグメントへ格納する際、当該セグメントに対応づけられた合計値を、当該パケットが送出されるべき出力ポートの数に応じて増加させ、パケット送出部は、複数の出力ポートのいずれかからパケットを送出すべき際、セグメントからパケットを読み出すとともに、セグメントに対応づけられた合計値を逐次減少させてもよい。
【００１４】
この態様によると、マルチキャストパケットやブロードキャストパケットの中継処理において、複数の出力ポートへの送出が完了するまではそれらのパケットの保持を継続し、また、それらのパケットを含むセグメントの適切な再利用を実現できる。
【００１５】
空き領域として設定されたセグメントの情報を保持する空きセグメント情報保持部と、空き領域として設定されたセグメントのうちパケットを格納すべきセグメントの情報を指し示す先頭ポインタと、新たに空き領域として設定されたセグメントの情報を格納すべき位置を指し示す末尾ポインタと、をさらに備えてもよい。パケット書込部は、先頭ポインタにより特定されるセグメントへパケットを格納し、セグメント解放部は、新たに空き領域として設定したセグメントの情報を末尾ポインタの指し示す位置へ格納し、当該セグメントが先頭ポインタにより特定されるものである場合はさらに、別のセグメントの情報を指し示すよう先頭ポインタを更新してもよい。
【００１６】
この態様によると、セグメント情報保持部における同一セグメントの二重管理を排除できる。二重管理が発生すると、先頭ポインタが指し示すエントリにより特定されるセグメントにパケットが格納されて、そのセグメントが空き領域でなくなっても、そのセグメントに関する別のエントリにより空き領域として把握されてしまうことがある。その結果、読み出しが未完了のパケットが上書きされる等、問題を生ずることがある。この態様では、このような問題の発生を回避でき、堅牢なセグメント管理を実現できる。
【００１７】
なお、以上の構成要素の任意の組合せ、本発明の表現を装置、方法、システム、プログラム、プログラムを格納した記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１８】
本発明によれば、通信制御装置に設けられたメモリを効率的に使用できる。
【図面の簡単な説明】
【００１９】
【図１】実施の形態の通信システムの構成を示す図である。
【図２】図１のスイッチ装置の機能構成を示すブロック図である。
【図３】空き領域情報保持部に保持されるデータを模式的に示す図である。
【図４】キュー情報保持部に保持されるデータを模式的に示す図である。
【図５】図２の入力処理部の詳細を示すブロック図である。
【図６】図２の出力処理部の詳細を示すブロック図である。
【図７】スイッチ装置の動作を示すフローチャートである。
【図８】図７のＳ１４の詳細を示すフローチャートである。
【図９】スイッチ装置の動作を示すフローチャートである。
【図１０】図９のＳ４２の詳細を示すフローチャートである。
【図１１】図９のＳ４６の詳細を示すフローチャートである。
【発明を実施するための形態】
【００２０】
本発明の実施の形態について、その構成を説明する前に概要を説明する。
スイッチ等の通信制御装置では、パケット伝送の信頼性を高めるために、パケットバッファにおける固定長のセグメントに対して、パケットのデータ（以下、単に「パケット」とも呼ぶ）を一時的に格納することが多い。従来、１セグメント長よりも長いパケットは複数のセグメントに分割して格納されていたが、１つのセグメントへ格納されるデータは１つのパケットを構成するデータであった。
【００２１】
例えば、５１２バイトが固定的に確保されるセグメントに対し６４バイトのパケットが格納されると、そのセグメント容量の９割弱は未使用の状態になってしまっていた。すなわち、実際にパケットが格納されるのはパケットバッファ容量の一部であり、メモリが非効率に使用されることがあった。特に、パケットバッファが大容量化している現在、１つのセグメントに対し１つのパケットの構成データのみを格納する方式では、セグメントに生じる未使用領域が大きくなってしまう。
【００２２】
そこで本実施の形態では、セグメントにおける空き領域の開始位置を示すオフセットを管理し、オフセットが示す位置からパケットを格納する。これにより、１つのセグメントに対して複数パケットを格納し、そのセグメント容量を有効に活用して、効率的なメモリの使用を実現する。
【００２３】
図１は、実施の形態の通信システムの構成を示す。通信システム１００は、スイッチ装置１０と、複数の通信ノード１２とを含む。スイッチ装置１０は、ある通信ノード１２から送信されたレイヤ２パケットやレイヤ３パケットを、そのパケットに設定された宛先アドレスにしたがって、別の通信ノード１２へ中継する通信制御装置である。
【００２４】
通信ノード１２は、スイッチ装置１０を介して他の通信ノード１２とパケットを送受する情報処理装置であり、例えばＰＣ端末でもよく、スイッチ装置１０とは異なる別のスイッチ装置でもよい。すなわち通信システム１００においては、スイッチ装置１０を介して、ＬＡＮ・ＷＡＮ・インターネット等、種々の通信網内に設置された通信ノード１２が相互に接続される。
【００２５】
図２は、図１のスイッチ装置１０の機能構成を示すブロック図である。スイッチ装置１０は、入力ポート２０で総称される第１入力ポート２０ａ・第２入力ポート２０ｂ・第３入力ポート２０ｃと、出力ポート２２で総称される第１出力ポート２２ａ・第２出力ポート２２ｂ・第３出力ポート２２ｃと、データ保持部３０とデータ処理部４２とを備える。なお、入力ポート２０および出力ポート２２は、説明の便宜上３個図示しているが、特定の個数に制限されないことはもちろんである。
【００２６】
本明細書のブロック図において示される各ブロックは、ハードウェア的には、コンピュータのＣＰＵやメモリをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組合せによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００２７】
例えば、図２の入力ポート２０および出力ポート２２は、通信ノード１２からの通信ケーブルが接続される接続ポートであってもよい。またデータ保持部３０の機能は、メモリにより実現されてもよい。またデータ処理部４２の機能は、プログラムとして実装され、スイッチ装置１０のメモリに保持され、プロセッサにより実行されてもよく、ＬＳＩ等の電子回路で実装されてもよい。
【００２８】
入力ポート２０は、通信ノード１２から送信されたパケットを受信して、そのパケットをデータ処理部４２へ送出する。出力ポート２２は、データ処理部４２から送出されたパケットを通信ノード１２へ送信する。
【００２９】
データ保持部３０は、各種データが格納されて保持される記憶領域である。データ保持部３０は、経路決定テーブル３２と、パケットバッファ３４と、空き領域情報保持部３６と、キュー情報保持部３８と、読み出し回数保持部４０とを含む。
【００３０】
経路決定テーブル３２は、通信ノード１２から送信されたパケットに設定された宛先アドレス（例えばＭＡＣアドレスやＩＰアドレス）と、そのパケットを送出すべき出力ポート２２とを対応づけて保持する。経路決定テーブル３２は、例えばレイヤ２スイッチにおけるＭＡＣアドレステーブルでもよく、レイヤ３スイッチやルータにおけるルーティングテーブルであってもよい。
【００３１】
パケットバッファ３４は、固定長のセグメントを記憶領域の管理単位として、複数のセグメントのそれぞれに１以上のパケットのデータを保持する。本実施の形態では、各セグメントに対し、他のセグメントと識別するためのＩＤ（以下、「セグメント番号」とも呼ぶ）が割り当てられる。以下、１〜Ｎ番のセグメント番号が割り当てられたセグメントを、セグメント＃１〜＃Ｎとも称する。また本実施の形態でのセグメント長は、５１２バイトであることとする。
【００３２】
空き領域情報保持部３６は、空き領域を有するセグメント（以下、「空きセグメント」とも呼ぶ）の情報を保持する。図３は、空き領域情報保持部３６に保持されるデータを模式的に示す。空き領域管理テーブル５０は、空きセグメントとして指定されたセグメントについて、そのセグメント番号が順次記録される記憶領域である。先頭ポインタ５２には、パケットを格納すべき空きセグメントのエントリとして、空き領域管理テーブル５０における先頭エントリのアドレスが格納される。この先頭エントリは、空きセグメントの指定が維持されているセグメントのうち最先に記録されたエントリである。
【００３３】
空き領域オフセット５４には、先頭ポインタ５２により示された空きセグメントについて、その空き領域の開始位置を示すデータが格納される。例えば、空き領域オフセット５４の値が１００の場合、空きセグメントの１００バイト目以降が空き領域であることを示す。末尾ポインタ５６には、新たに空きセグメントして指定されたセグメントについて、そのセグメント番号を記録すべきアドレスが格納される。
【００３４】
図２に戻りキュー情報保持部３８は、出力ポート２２のそれぞれからパケットを送出する際に参照される、出力ポート２２のそれぞれに対応するキューの管理情報を保持する。
図４は、キュー情報保持部３８に保持されるデータを模式的に示す。キュー管理テーブル６０は、各出力ポート２２から送出されるべき各パケットについて、そのパケット長と、格納されたセグメント番号と、セグメントでの格納開始位置を示すオフセット値とが対応づけられたエントリを保持する。以下、特定の出力ポート２２に対応するキュー管理テーブル６０のエントリ全体を、その出力ポート２２に対応するキューと称する。
【００３５】
図４のキュー先頭ポインタ６２は、各出力ポート２２に対応するキューのそれぞれにおける先頭エントリのアドレスを示す。キュー末尾ポインタ６４は、各キューのそれぞれに対し新たなエントリが追加されるべきアドレスを示す。キュー管理テーブル６０のエントリにおいては、基本的に、１パケットについてパケット長とセグメント番号とオフセットとが対応づけて設定される。セグメントの空き容量をパケット長が超過する場合は、その超過分を格納したセグメント番号が後続のエントリとして追加される。
【００３６】
例えば、図４の第１出力ポート２２ａに対応するキューには３つのパケットの情報が含まれている。第１のパケットは１０２４バイトであり、セグメント＃９の４００バイト目から格納されている。セグメント＃９を超過するパケットデータはセグメント＃１１の先頭から格納され、さらにセグメント＃１１を超過するパケットデータはセグメント＃１４の先頭から格納されている。第２のパケットは６４バイトであり、セグメント＃１４の４００バイト目から格納されている。また第２のパケットは、マルチキャストパケットでもある。すなわち、第２出力ポート２２ｂに対応するキューおよび第３出力ポート２２ｃに対応するキューでも同様のエントリがあり、この第２のパケットを複数の出力ポート２２から出力すべきことが記録されている。
【００３７】
図２に戻り読み出し回数保持部４０は、パケットバッファ３４における複数のセグメントのそれぞれについて、各セグメントに保持された複数のパケットのそれぞれで予定される読み出し回数の合計値を保持する。この読み出し回数は、言い換えれば、各パケットを送出すべき出力ポート２２の数であり、ユニキャストパケットの場合は１となり、マルチキャストパケットおよびブロードキャストパケットの場合は２以上となる。また、セグメントの読み出し回数が０であれば、そのセグメントに格納されたパケットが読み出されることはない、すなわちそのセグメントの格納パケットを解放・上書き可能であることを示している。
【００３８】
データ処理部４２は、通信ノード１２間でやりとりされるパケットを中継するための各種データ処理を実行する。データ処理部４２は、入力処理部４４で総称される第１入力処理部４４ａ・第２入力処理部４４ｂ・第３入力処理部４４ｃと、出力処理部４６で総称される第１出力処理部４６ａ・第２出力処理部４６ｂ・第３出力処理部４６ｃとを含む。
【００３９】
入力処理部４４のそれぞれは、対応する入力ポート２０からパケットを受け付けて、そのパケットに関連するデータをデータ保持部３０へ格納する。ある入力処理部４４は、他の入力処理部４４とは独立しており、各々並行して動作する。図５は、図２の入力処理部４４の詳細を示すブロック図である。入力処理部４４は、パケット受付部７０と、方路決定部７２と、パケット書込部７４とを含む。
【００４０】
パケット受付部７０は、対応する入力ポート２０を介して、通信ノード１２から送信されたパケットを受け付ける。方路決定部７２は、経路決定テーブル３２を参照し、パケット受付部７０において受け付けられたパケットで指定された宛先アドレスにしたがって、そのパケットの転送先を決定する。具体的には、複数の出力ポート２２のいずれから、そのパケットを送出すべきかを決定する。
【００４１】
パケット書込部７４は、送出先の出力ポート２２が決定されたパケットをデータ保持部３０へ格納する。以下詳細に説明する。まずパケット書込部７４は、空き領域情報保持部３６を参照して、パケットバッファ３４に十分な空き領域が有るか否かを判定する。具体的には、先頭ポインタ５２が示すアドレスと末尾ポインタ５６が示すアドレスとが異なる場合は空き領域が有ると判定し、両アドレスが合致する場合は空き領域が無いと判定する。次に空き領域の全体容量、すなわち（セグメント長×空きセグメント数−空き領域オフセット５４）を算出し、空き領域の全体容量がパケット長以上である場合は空き領域が有ると判定し、パケット長未満である場合は空き領域が無いと判定する。
【００４２】
続いてパケット書込部７４は、キュー情報保持部３８を参照して、キュー管理テーブル６０に十分な空き領域があるか否かを判定する。具体的には、パケットを送出すべき出力ポート２２に対応するキューについて、そのキュー末尾ポインタ６４が示すアドレスとキュー先頭ポインタ６２が示すアドレスとの差からキューの現在のデータサイズを特定する。そしてそのデータサイズと、キューへ新規追加すべきエントリのデータサイズとの合計値が、予め定められたキューの最大サイズ以内である場合は空き領域があると判定し、キューの最大サイズを超過する場合は空き領域が無いと判定する。
【００４３】
キュー管理テーブル６０へ新規追加すべきエントリのデータサイズは、新規追加すべきエントリ数と正相関するため、例えば、そのエントリ数に対し１エントリのデータサイズを示す所定値を乗じて算出してもよい。新規追加すべきエントリ数は、パケットの格納に用いられるセグメント数と同数であり、下記の式（以下、「式１」とも呼ぶ）により算出する。
（パケット長＋空き領域オフセット５４の値）／セグメント長＋１
したがって、図４で示したように、パケット長が１０２４バイト、空き領域オフセット５４の値が４００、セグメント長が５１２バイトである場合、（キューへ新規追加すべきエントリ数）＝（パケットを格納するセグメント数）＝３となる。
【００４４】
パケット書込部７４は、パケットバッファ３４とキュー管理テーブル６０との少なくとも一方に十分な空き領域がなければ、ユニキャストパケットの書き込み処理を中止してそのユニキャストパケットを廃棄する。パケットバッファ３４に十分な空き領域があり、かつ、キュー管理テーブル６０に十分な空き領域がある場合、パケット書込部７４は、ユニキャストパケットの書き込み処理を続行する。
【００４５】
なお、マルチキャストパケットまたはブロードキャストパケットのデータをデータ保持部３０へ格納すべき際には、パケット書込部７４は、パケットを送出すべき複数の出力ポート２２に対応する複数のキューそれぞれの空き領域を判定する。そして、空き領域があると判定したキューが１つでもあれば、そのキューをエントリ追加対象キューとして特定するとともにパケットの書き込み処理を続行する。
【００４６】
パケットの書き込み処理を続行する場合、パケット書込部７４は、まず上述の式１によりパケットを格納すべきセグメント（以下、「書き込みセグメント」とも呼ぶ）の数を算出する。パケット書込部７４は、書き込みセグメント数が２以上である場合、その書き込みセグメント数が１になるまで以下の処理を繰り返す。
【００４７】
ステップ１：空き領域情報保持部３６の先頭ポインタ５２を参照して書き込みセグメントを特定する。そして、その書き込みセグメントにおいて、空き領域オフセット５４が示す位置以降にパケットを書き込む。
ステップ２：先頭ポインタ５２の値を加算する（すなわち、次の空きセグメントの情報を示すように更新する）とともに、空き領域オフセット５４の値を０に更新する（すなわち、空きセグメントの先頭を示すように更新する）。
ステップ３：書き込みセグメント数を１減算する。
【００４８】
書き込みセグメント数が１の場合、上記ステップ２において、空き領域オフセット５４の値が、パケットの末尾データを格納した次の位置を示すよう、空き領域オフセット５４を更新する。その一方で、先頭ポインタ５２の値は変更しない。
【００４９】
続いてパケット書込部７４は、キュー情報保持部３８のデータを更新する。具体的には、パケットを送出すべき出力ポート２２に対応するキュー管理テーブル６０のキューについて、そのキュー末尾ポインタ６４が指し示すアドレス以降に、書き込みセグメントに対応する新たなエントリを追加する。パケット書込部７４は、パケットを書き込んだセグメントのセグメント番号を各エントリへ記録する。そのパケットに関する先頭のエントリに対しては、パケット長と、書き込みを開始した位置、すなわち書き込みの開始時点における空き領域オフセット５４の値をさらに記録する。
【００５０】
なお、マルチキャストパケットまたはブロードキャストパケットの場合、パケット書込部７４は、新規エントリの追加により最大値の制限を超過しないキュー、すなわちエントリ追加対象キューに対してのみ新たなエントリの追加を行う。これにより、本来これらのパケットを送出すべき複数の出力ポート２２のうち、エントリ追加対象キューに対応する出力ポート２２からのみパケットが送出されることになる。
【００５１】
最後にパケット書込部７４は、読み出し回数保持部４０のデータを更新する。具体的には、各キューへ追加した新たなエントリごとに、そのエントリに記録したセグメント、すなわちパケットを格納したセグメントに対する読み出し回数を１加算する。
【００５２】
例えば、ユニキャストパケットをセグメント＃１とセグメント＃２とに格納し、それぞれのセグメント番号が記録された２つのエントリを１つのキューへ追加した場合、セグメント＃１の読み出し回数とセグメント＃２の読み出し回数の両方へ１を加算する。また、マルチキャストパケットをセグメント＃１とセグメント＃２とに格納し、上記と同様の２つのエントリを２つのキューのそれぞれへ追加した場合、セグメント＃１の読み出し回数とセグメント＃２の読み出し回数の両方へ２を加算する。
【００５３】
出力処理部４６のそれぞれは、データ保持部３０からパケット関連データを読み出して、対応する出力ポート２２へパケットを送出する。ある出力処理部４６は、他の出力処理部４６とは独立しており、各々並行して動作する。図６は、図２の出力処理部４６の詳細を示すブロック図である。出力処理部４６は、パケット読出し部８０と、パケット送出部８２と、セグメント解放部８４とを含む。
【００５４】
パケット読出し部８０は、対応する出力ポート２２のキューについて、そのキュー末尾ポインタ６４が示すアドレスに変更があるか否かを定期的に監視する。キュー末尾ポインタ６４が示すアドレスが変更された場合、新たなエントリが監視対象のキューに追加された旨を検出し、キュー先頭ポインタ６２が指すエントリを特定する。
【００５５】
続いてパケット読出し部８０は、キュー先頭ポインタ６２が指すエントリの、パケット長とオフセット値とを上記の式１へ代入し、１パケットに対応するエントリの数を特定する。そして、各エントリを参照し、それぞれに設定されたセグメント番号に対応するパケットバッファ３４のセグメントから１パケット分のデータを読み出す。例えば、１パケットに対応するキューのエントリのうち、先頭のエントリに対応するセグメントからは、（セグメント長−オフセット値）のデータを読み出す。またエントリが複数存在する場合、末尾のエントリに対応するセグメントからは、（パケット長＋オフセット値−セグメント長×（エントリ数−１））のデータを読み出す。先頭と末尾の間のエントリに対応するセグメントからはセグメント長（すなわちセグメント全体）のデータを読み出す。
【００５６】
パケットの読み出し後、パケット読出し部８０は、そのパケットを読み出す際に参照したエントリ数だけ、キュー情報保持部３８のキュー先頭ポインタ６２が示す位置を更新する。またパケット読出し部８０は、読み出し回数保持部４０を更新して、参照済の各エントリで指定されたセグメントの読み出し回数を１ずつ減算する。
【００５７】
パケット送出部８２は、読出し部８０により読み出されたパケットを、対応する出力ポート２２を介して、通信ノード１２へ送出する。１つのパケットのデータが分割され、複数のセグメントに分散して格納されていた場合は、個々のセグメントから読み出されたデータを合成し、１つのパケットのデータとして通信ノード１２へ送出する。
【００５８】
セグメント解放部８４は、読み出し回数保持部４０における各セグメントの読み出し回数を定期的に参照して、読み出し回数が１以上から０に変化したセグメントを特定する。セグメント解放部８４は、読み出し回数が０に変化したセグメントのセグメント番号を、空き領域情報保持部３６において末尾ポインタ５６が示す位置へ記録する。それとともに、次に読み出し回数が０になったセグメントの記録位置を示すように、末尾ポインタ５６が示すアドレスを１エントリ分増加させる。
【００５９】
なおセグメント解放部８４は、読み出し回数が０になったセグメントが、空き領域情報保持部３６において先頭ポインタ５２が示すセグメントでもあった場合は、先頭ポインタ５２が指し示すセグメントを１エントリ分増加させる。すなわち、先頭ポインタ５２が示すセグメントが、空き領域情報保持部３６において読み出し回数が０になったセグメントの次に設定されたセグメントとなるように、先頭ポインタ５２を更新する。
【００６０】
以上の構成による動作を以下説明する。
図７は、スイッチ装置１０の動作を示すフローチャートである。同図は、１つの入力処理部４４の動作を示している。通信ノード１２から送信されたパケットがパケット受付部７０において受け付けられると（Ｓ１０のＹ）、方路決定部７２は経路決定テーブル３２を参照して、そのパケットを送出すべき出力ポート２２を決定する（Ｓ１２）。パケット書込部７４は、方路決定部７２における決定内容にしたがって、後述するパケット書き込み処理を実行する（Ｓ１４）。パケット受付部７０においてパケットが受け付けられなければ（Ｓ１０のＮ）、以降の処理はスキップされて本図のフローを終了する。
【００６１】
図８は、図７のＳ１４の詳細を示すフローチャートである。パケット書込部７４は、空き領域情報保持部３６を参照して、パケットバッファ３４に空きセグメントが存在するか否か、また、パケットバッファ３４の空き容量がパケット長以上か否かを判別する。空きセグメントが存在し（Ｓ２０のＹ）、その空き容量がパケット長以上である場合（Ｓ２２のＹ）、パケット書込部７４は、キュー情報保持部３８を参照して、キュー管理テーブル６０に対して新規エントリの追加が可能か否かを判別する。新規エントリを追加可能であれば（Ｓ２４のＹ）、パケットのデータを空きセグメントへ格納し（Ｓ２６）、キュー管理テーブル６０へ新規エントリを追加する（Ｓ２８）。そして、キュー管理テーブル６０に対する新規エントリに設定されたセグメントについて、読み出し回数保持部４０の読み出し回数を１ずつ加算する（Ｓ３０）。
【００６２】
パケットバッファ３４に空きセグメントが存在しない（Ｓ２０のＮ）、または、その空き容量がパケット長未満（Ｓ２２のＮ）、または、キューに対し新規エントリ追加ができない場合（Ｓ２４のＮ）は、パケットを廃棄して（Ｓ３２）、本図のフローを終了する。なお図８には図示しないが、マルチキャストパケットやブロードキャストパケットの場合、パケットを送出すべき複数の出力ポート２２それぞれに対応するキューについてＳ２４の判定を行う。そして、エントリが追加可能なキューが存在すればＳ２６〜Ｓ３０を実行する。
【００６３】
図９は、スイッチ装置１０の動作を示すフローチャートである。同図は、１つの出力処理部４６の動作を示している。パケット読出し部８０は、キュー管理テーブル６０における監視対象キューに新たなエントリが追加されたことを検出すると（Ｓ４０のＹ）、後述するパケット読み出し処理を実行する（Ｓ４２）。パケット送出部８２は、パケット読出し部８０により読み出されたパケットデータを、対応する出力ポート２２を介して、通信ノード１２へ送信する（Ｓ４４）。セグメント解放部８４は、後述するセグメント解放処理を実行する（Ｓ４６）。監視対象キューに新たなエントリの追加がなければ（Ｓ４０のＮ）、以降の処理はスキップされて本図のフローを終了する。
【００６４】
図１０は、図９のＳ４２の詳細を示すフローチャートである。パケット読出し部８０は、キュー管理テーブル６０におけるエントリを参照して、パケットを読み出すべき１以上のセグメントを特定する（Ｓ５０）。そして、キュー管理テーブル６０におけるエントリで指定された順にセグメントからパケットデータを読み出し（Ｓ５２）、そのセグメントについて読み出し回数保持部４０の読み出し回数を１減算する（Ｓ５４）。キュー管理テーブル６０におけるエントリで指定されたセグメントの全てからパケットデータを読み出した場合は（Ｓ５６のＹ）、本図のフローを終了する。パケットデータを未読み出しのセグメントが残っていれば（Ｓ５６のＮ）、Ｓ５２へ戻る。
【００６５】
図１１は、図９のＳ４６の詳細を示すフローチャートである。セグメント解放部８４は、読み出し回数保持部４０における各セグメントの読み出し回数を定期的に参照し、その読み出し回数が１以上から０に変化したセグメント（以下、「読み出し完了セグメント」とも呼ぶ）を検出する。読み出し完了セグメントを検出すると（Ｓ６０のＹ）、セグメント解放部８４は、その読み出し完了セグメントを空き領域として、空き領域情報保持部３６における末尾ポインタ５６が指定する位置にそのセグメント番号を格納する（Ｓ６２）。
【００６６】
その読み出し完了セグメントのセグメント番号が、空き領域情報保持部３６における先頭ポインタ５２でも指定されていた場合（Ｓ６４のＹ）、セグメント解放部８４は、空き領域情報保持部３６におけるパケット格納順位が次点のセグメント番号を示すよう、先頭ポインタ５２を更新する（Ｓ６６）。読み出し完了セグメントのセグメント番号が、先頭ポインタ５２によって指定されていなければ（Ｓ６４のＮ）、Ｓ６６はスキップされる。読み出し完了セグメントが検出されなければ（Ｓ６０のＮ）、以降の処理はスキップされて本図のフローを終了する。
【００６７】
本実施の形態のスイッチ装置１０によれば、セグメントの空き領域の開始位置を示すオフセットを管理し、そのオフセットが示す位置からパケットを格納することにより、１つのセグメントに複数のパケットを格納できる。これにより、セグメントの容量全体をパケットの格納に有効活用でき、メモリの効率的な使用を実現する。例えば、本実施の形態で提案した技術によりメモリの使用効率がＮ倍になれば、スイッチ装置１０に搭載すべきメモリ容量は１／Ｎになり、必要なハードウェアリソース量を低減できる。
【００６８】
またスイッチ装置１０によれば、複数のセグメントそれぞれからのパケットデータの読み出し予定数が、読み出し回数保持部４０において一元的に保持される。これにより、複数の入力処理部４４のそれぞれが並行動作し、複数の出力処理部４６のそれぞれが並行動作し、さらに複数の出力ポート２２から出力すべきマルチキャストパケットやブロードキャストパケットと、ユニキャストパケットとが混在する場合でも、適切なタイミングで空きセグメントを設定でき、その再利用を実現できる。
【００６９】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００７０】
上記実施の形態では、入力ポート２０および出力ポート２２は、外部の通信ノード１２と直接接続されることとしたが、スイッチ装置１０の態様はこれに限られない。変形例として、スイッチ装置１０内部に論理的に構成された入出力ポートであってもよい。具体的には、入力ポート２０と出力ポート２２との少なくとも一方が、スイッチ装置１０における他の通信制御処理と接続されるものであってもよい。すなわち、スイッチ装置１０における他の通信制御処理後、入力ポート２０〜入力処理部４４〜出力処理部４６〜出力ポート２２でのパケット中継処理が実行されてもよい。また、入力ポート２０〜入力処理部４４〜出力処理部４６〜出力ポート２２でのパケット中継処理後、スイッチ装置１０における他の通信制御処理が実行されてもよい。
【００７１】
請求項に記載の各構成要件が果たすべき機能は、実施の形態および変形例において示された各構成要素の単体もしくはそれらの連係によって実現されることも当業者には理解されるところである。
【符号の説明】
【００７２】
１０  スイッチ装置、  １２  通信ノード、  ２２  出力ポート、  ３２  経路決定テーブル、  ３４  パケットバッファ、  ３６  空き領域情報保持部、  ３８  キュー情報保持部、  ４０  読み出し回数保持部、  ５０  空き領域管理テーブル、  ５２  先頭ポインタ、  ５４  空き領域オフセット、  ５６  末尾ポインタ、  ７０  パケット受付部、  ７２  方路決定部、  ７４  パケット書込部、  ８０  パケット読出し部、  ８２  パケット送出部、  ８４  セグメント解放部、  １００  通信システム。
【図１】
2011130249.tif 000003
【図２】
2011130249.tif 000004
【図３】
2011130249.tif 000005
【図４】
2011130249.tif 000006
【図５】
2011130249.tif 000007
【図６】
2011130249.tif 000008
【図７】
2011130249.tif 000009
【図８】
2011130249.tif 000010
【図９】
2011130249.tif 000011
【図１０】
2011130249.tif 000012
【図１１】
2011130249.tif 000013