(57)【要約】【課題】MACブリッジデータベースのオーバーフローを減らすことで、ブリッジ機能を改善し、且つ比較的少ないハードウエアリソースを用いることで装置のコストを削減すること。【解決手段】MACブリッジフィルタ用のハッシュ関数は、MACブリッジデータベースのオーバーフローを減らすことでブリッジ機能を改善し、且つ比較的少ないハードウエアリソースを用いることで装置のコストを削減する。CRCハッシュ関数を用いてMACブリッジフィルタにおけるサーチストリングをランダム化し、ブリッジが使用される場所によらず、一貫したブリッジパフォーマンスが達成されるようにする。CRCをハッシュ関数として使用することで、効率的なハードウエア実現手段になる。更に本発明は如何なるブリッジフィルタ設計についてもCRC-Mをハッシュ関数として使用するよう一般化されてもよい。【選択図】図１
2007097188.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークトラフィックのパケットを受信する回路であって、前記パケットは該パケットのソースのＭＡＣアドレス及び該パケットの宛先のＭＡＣアドレスの少なくとも１つを有するところの回路と、
ＭＡＣアドレスを含むデータから生成される巡回冗長検査ハッシュを複数個格納するルックアップテーブルと、
前記ルックアップテーブル中のパケットのＭＡＣアドレスを探索する探索回路と、
を有するＭＡＣブリッジフィルタであって、前記探索回路は、
パケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュを生成する回路と、
パケットのＭＡＣアドレスを含むデータの生成された巡回冗長検査ハッシュを用いて、前記ルックアップテーブルでパケットのＭＡＣアドレスを探索する回路と、
パケットのＭＡＣアドレスが前記ルックアップテーブルで発見されたか否かに基づいて、各パケットを通過させる又は通過させないように機能する回路と、
を有することを特徴とするＭＡＣブリッジフィルタ。
【請求項２】
前記ＭＡＣアドレスを含む前記データがサービスプロバイダの識別子を含み、前記パケットのＭＡＣアドレスを含むデータが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子を含む
ことを特徴とする請求項１記載のＭＡＣブリッジフィルタ。
【請求項３】
前記ＭＡＣアドレスを含む前記データが顧客の識別子を含み、前記パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子を含む
ことを特徴とする請求項１記載のＭＡＣブリッジフィルタ。
【請求項４】
前記ＭＡＣアドレスを含むデータがサービスプロバイダの識別子及び顧客の識別子を含み、パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子と、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子とを含む
ことを特徴とする請求項１記載のＭＡＣブリッジフィルタ。
【請求項５】
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータから生成された巡回冗長検査ハッシュが、前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータより少ないデータを有する
ことを特徴とする請求項４記載のＭＡＣブリッジフィルタ。
【請求項６】
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子は、前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする請求項５記載のＭＡＣブリッジフィルタ。
【請求項７】
前記ＭＡＣアドレスを含むデータの巡回冗長検査ハッシュ及びパケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュの双方が、関数Ｇ（Ｘ）＝Ｘ１５＋Ｘ＋１を用いて生成される
ことを特徴とする請求項４記載のＭＡＣブリッジフィルタ。
【請求項８】
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、前記顧客の識別が１２ビットより成り、前記巡回冗長検査ハッシュが１５ビットより成る
ことを特徴とする請求項７記載のＭＡＣブリッジフィルタ。
【請求項９】
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、１２ビットより成る前記顧客の識別が、１５ビットより成る前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする請求項８記載のＭＡＣブリッジフィルタ。
【請求項１０】
ネットワークトラフィックのパケットを受信するステップであって、前記パケットは該パケットのソースのＭＡＣアドレス及び該パケットの宛先のＭＡＣアドレスの少なくとも１つを有するところのステップと、
ＭＡＣアドレスを含むデータから生成される巡回冗長検査ハッシュをルックアップテーブルに複数個格納するステップと、
前記ルックアップテーブル中のパケットのＭＡＣアドレスを探索する探索ステップと、
を有する方法であって、前記探索ステップは、
パケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュを生成し、
パケットのＭＡＣアドレスを含むデータの生成された巡回冗長検査ハッシュを用いて、前記ルックアップテーブルでパケットのＭＡＣアドレスを探索することで実行され、
パケットのＭＡＣアドレスが前記ルックアップテーブルで発見されたか否かに基づいて、各パケットを通過させる又は通過させないように判定がなされる、
ことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク管理システム(NMS:  Network  Management  System)におけるネットワーク要素から、ＮＭＳとの通信喪失後の通信再確立時に又はＮＭＳリスタート時に、データを復元するための方法及びシステムに関連する。
【背景技術】
【０００２】
光同期ネットワーク(SONET)は光ファイバネットワークでの同期データ伝送に関する規格である。SONETネットワークの一般的な構成は、リングトポロジに配列された光ファイバを含み、通常的にはワーキングファイバ及びプロテクティングファイバの２つの物理的なファイバ含む。ファイバリング上でデータを通信するために、電光素子を利用して、光信号を受信及び送信し、電気信号を受信及び送信し、そして光信号及び電気信号間でデータを変換する。典型的には、ソネット（SONET）プロトコルとは異なるイーサーネットのようなネットワークプロトコルを用いてそのような装置にデータが電気的に伝送される。かくてその装置は、光／電気変換に加えて、データ及びプロトコル変換を実行しなければならない。
【０００３】
そのような装置に含まれている１つの機能ブロックに、MACブリッジと呼ばれるものがある。媒体アクセス制御アドレス（MACアドレス）は、ほとんどの形式のネットワーク装置に付与された固有の識別子であり、一般に、データリングレイヤ（OSIモデルのレイヤ２）で使用される。ネットワークブリッジは、データリンクレイヤに沿って複数のネットワークセグメントを接続する装置である。かくて、MACブリッジは、電気ネットワークプロトコル、典型的には（イーサーネットのような）ローカルエリアネットワーク（LAN）プロトコルを、（ソネットのような）ファイバリングで使用される光ネットワークプロトコルにデータリンクレイヤで接続するために使用される。
【０００４】
MACブリッジに含まれる機能の１つに、MACブリッジフィルタ（MBF:  MAC  Bridge  Filter）として知られるフィルタリング機能がある。そのようなMACブリッジフィルタは、パケットのMACアドレスに基づいて、MACブリッジを介してパケットが伝搬することを許可する又は禁止する。この機能ブロックは、LAN（電気的な）側だけでなくリング（光学的な）側でも不要なパケットがあふれることを回避するように実現される。リングレットの他のMACステーションに宛てられたものを除くように、リング側から到来する通過パケットを選別するよう設計される。LAN側ローカルステーション間で、リングにパケットが入ることも防ぐことができる。
【０００５】
或るMACアドレスは４８ビット長であり、従って全体で2**48個のMACアドレスが存在する。現実には、MACブリッジデータベースは、ハードウエアリソース制約に起因して、限られたMACアドレス数しか格納できない。例えば、従来のMACブリッジフィルタのハードウエア設計では、ブリッジフィルタは３２ｋのバケット(bucket)に分割され、各バケットは、それらに付随するサービスプロバイダVLANID(SVID)及びカスタマVLANID(CVID)と共に４つのMACアドレスを保持する。４８ビットMACアドレス及び１２ビットCVIDと連結された１２ビットSVIDは、そのフィルタに関する固有のエントリを形成し、本質的には７２ビットストリングでアドレス指定されるハッシュテーブルである。バケット中に既に４エントリ存在し、別の異なる７２ビットストリングがそのバケットにハッシュされるとき、バケットオーバーフローが起こる。ハッシュテーブルに含まれる全エントリ数（上記の例では、１２８K）は、全ての可能なエントリ（２７２）よりもかなり小さく、MACブリッジバケットのオーバーフローは不可避的である。しかしながら、過剰なバケットオーバーフローは貧弱なブリッジ機能となってしまう。更に、MACブリッジフィルタ設計に関するハッシュ関数は、できるだけ少ないハードウエアリソースを使用するべきである。従って、MACブリッジデータベースのオーバーフローを減らすことで、ブリッジ機能を改善し、且つ比較的少ないハードウエアリソースを用いることで装置のコストを削減する、MACブリッジフィルタ用のハッシュ関数が望まれている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本願発明の課題は、MACブリッジデータベースのオーバーフローを減らすことで、ブリッジ機能を改善し、且つ比較的少ないハードウエアリソースを用いることで装置のコストを削減することである。
【課題を解決するための手段】
【０００７】
本発明はMACブリッジフィルタ用のハッシュ関数を実現し、MACブリッジデータベースのオーバーフローを減らすことでブリッジ機能を改善し、且つ比較的少ないハードウエアリソースを用いることで装置のコストを削減する。本発明では、CRC-15ハッシュ関数を用いてMACブリッジフィルタにおける７２ビットサーチストリングをランダム化し、ブリッジが使用される場所によらず、一貫したブリッジパフォーマンスが達成されるようにする。CRCをハッシュ関数として使用することで、効率的なハードウエア実現手段になる。更に本発明は如何なるブリッジフィルタ設計についてもCRC-Mをハッシュ関数として使用するよう一般化されてもよい。
【発明を実施するための最良の形態】
【０００８】
本発明の一形態では、ＭＡＣブリッジフィルタは、ネットワークトラフィックのパケットを受信する回路であって、前記パケットは該パケットのソースのＭＡＣアドレス及び該パケットの宛先のＭＡＣアドレスの少なくとも１つを有するところの回路と、ＭＡＣアドレスを含むデータから生成される巡回冗長検査ハッシュを複数個格納するルックアップテーブルと、前記ルックアップテーブル中のパケットのＭＡＣアドレスを探索する探索回路とを有するＭＡＣブリッジフィルタであって、前記探索回路は、パケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュを生成する回路と、パケットのＭＡＣアドレスを含むデータの生成された巡回冗長検査ハッシュを用いて、前記ルックアップテーブルでパケットのＭＡＣアドレスを探索する回路と、パケットのＭＡＣアドレスが前記ルックアップテーブルで発見されたか否かに基づいて、各パケットを通過させる又は通過させないように機能する回路とを有する。
【０００９】
本発明の一形態によれば、前記ＭＡＣアドレスを含む前記データがサービスプロバイダの識別子を含み、前記パケットのＭＡＣアドレスを含むデータは、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子を含でよい。前記ＭＡＣアドレスを含む前記データは顧客の識別子を含み、前記パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子を含んでよい。前記ＭＡＣアドレスを含むデータはサービスプロバイダの識別子及び顧客の識別子を含み、パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子と、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子とを含んでよい。
【００１０】
本発明の一形態では、前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータから生成された巡回冗長検査ハッシュが、前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータより少ないデータを有してよい。前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子は、前記巡回冗長検査ハッシュから復元可能でもよい。
【００１１】
本発明の一形態では、前記ＭＡＣアドレスを含むデータの巡回冗長検査ハッシュ及びパケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュの双方が、関数Ｇ（Ｘ）＝Ｘ１５＋Ｘ＋１を用いて生成されてよい。前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、前記顧客の識別が１２ビットより成り、前記巡回冗長検査ハッシュが１５ビットで構成されてもよい。前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、１２ビットより成る前記顧客の識別が、１５ビットより成る前記巡回冗長検査ハッシュから復元可能でもよい。
【実施例１】
【００１２】
以下、添付図面を参照しながら本発明の好適実施例が説明される。
【００１３】
本発明はMACブリッジフィルタ用のハッシュ関数を実現し、そのハッシュ関数はMACブリッジデータベースのオーバーフローを減らすことでブリッジ機能を改善し、比較的少ないハードウエアリソースを用いることで装置のコストを削減する。本発明では、CRC-15ハッシュ関数を用いてMACブリッジフィルタにおける７２ビットサーチストリングをランダム化し、ブリッジが使用される場所によらず、一貫したブリッジパフォーマンスが達成されるようにする。CRCをハッシュ関数として使用することで、効率的なハードウエア実現手段になる。更に本発明は如何なるブリッジフィルタ設計についてもCRC-Mをハッシュ関数として使用するよう一般化されてもよい。
【００１４】
本発明は、CRC-15関数を利用し、リジリエントパケットリング(RPR:  Resilient  Packet  Ring)サービスユニットで使用されるMACブリッジフィルタに特に有利に適用され、そのようなサービスユニットにおける本発明の実現例が本発明の実施例として使用される。しかしながらこれは単なる一例に過ぎず、本発明は他のシステム及びサービスユニットにも適用可能である。本発明は如何なるブリッジフィルタ設計での利用も想定している。
【００１５】
MACブリッジフィルタ（MBF）機能ブロックは、LAN側だけでなくリング側の不要なパケットのあふれ（flooding）を回避するように実現される。リングレットにおける他のMACステーションに宛てられているものを除いて、リング側から到来する通過パケットを選別するように設計がなされる。LAN側ローカルステーション間でリングに入ることも防ぐことができる。更に、静的なフィルタリングデータベースは、トラブルシューティング及びネトワークメンテナンスようの指標として、或るMACアドレスへの及びそのMACアドレスから発するフレームをブロックするよう用意されることが可能である。
【００１６】
ダイナミックLUT（DLUT）及びスタティックLUTの２つのルックアップテーブルがMBFの中にある。だ以内ミックLUTはAUXQDRメモリ内に格納され、スタティックLUTはERBFPGAブロックRAM内に格納される。MBFに入る各パケットは双方のLUTでのサーチを介して進行する。パケットを通す又は通さないことの判断は、双方のLUTからの組み合わせた結果に基づいてなされる。ダイナミックLUTはMACソースアドレス学習を介して自動的に確立され、スタティックLUTはユーザの用意したものを介してソフトウエアからダウンロードされる。
【００１７】
MBFに到来するフレームはイングレスルールチェックブロック及び以後のフィルタリングを介しているものとする。
【００１８】
好ましくは、RPRサービスユニットの３つの動作モードがあり、それらはａ）ＡＲＰＯＲＴ−ＰＲ，ｂ）ＡＲＰＯＲＴ−ＳＲ，ｃ）ＴＲＰＯＲＴ−ＳＲである。
【００１９】
ａ）ＡＲＰＯＲＴ−ＰＲモードでは、４つのブリッジインスタンスがあり、それぞれ１つのＬＡＮポート及び１つの論理リングポートに結合される。物理的には、ただ１つのリングポート（リングレット０及びリングレット１に併合される）があるが、それぞれ対応するブリッジ（ＬＡＮポート）に対するＳＶＩＤステアを用いて、リングイングレスルールチェックブロックにより４つの論理リングポートにまで分割される。
【００２０】
ＡＲＰＯＲＴ−ＰＲ及びＴＲＰＯＲＴ−ＳＲモードでは、唯１つのブリッジインスタンスがあり、それはＬＡＮポート１及びリングポートに結合される。
【００２１】
図１はＡＲＰＯＲＴ−ＳＲモードでの（ネイティブ）イーサーネットＭＡＣヘッダ処理例の概略を示す。ＬＡＮイングレスルールチェックブロック１０２内では、各ＬＡＮイングレスパケットは、割り当てられたサービスプロバイダＶＬＡＮＩＤ（ＳＶＩＤ）１０４と共にタグ付けされ、そのＬＡＮポートに関するＴＬ１コマンドによって用意される。かくてこのパケットのヘッダはＭＡＣブリッジフィルタリングブロック１０６に転送される。ＭＡＣブリッジフィルタリングブロックは、パケットが選別される（ドロップされる）べきか或いはリングに転送される（又は通される）べきかを判定するために、パケットの顧客ＶＬＡＮＩＤ（ＣＶＩＤ）と宛先アドレス（ＤＡ）又はソースアドレス（ＳＡ）とを結合し、その結合に関するサイクリック冗長チェック（ＣＲＣ）ハッシュを生成し、ブリッジに関するダイナミックルックアップテーブル（ＬＵＴ）１１２及びスタティックＬＵＴ内で探すためのキーを生成する。リングからの制御パケットはＣＰＵ（図示せず）に転送されるが、リングからのデータパケットはリングイングレスルールチェックブロック１０８を通じて進む。合致したＳＶＩＤを有するフレームは、ＭＡＣアドレスルックアップ用のＭＡＣブリッジフィルタリングブロック１０６に転送される。選別されていないフレームは、ＳＶＩＤが除去された後に、ＳＶＩＤ指定ＬＡＮポートに送信される。ダイナミックＬＵＴ１１２でのＭＡＣエントリのコンテンツ例（内容例）は、図中下側に示されている。スタティックＬＵＴ１１０は、ＴＬ１コマンドで指定されたＳＡ又はＤＡフィールドと共にフレームを取り出す（タップする）。
【００２２】
図２はＴＲＰＯＲＴ−ＳＲモードでの（ネイティブ）イーサーネットＭＡＣヘッダ処理例の概略を示す。この動作モード例では、唯１つのＬＡＮポート及び１つのリングポートがある。ＬＡＮイングレスルール検査ブロック１０２内では、各ＬＡＮ進入（イングレス）フレームはサービスプロバイダＶＬＡＮＩＤ（ＳＶＩＤ）テーブル１０４に対して有効にされ、ＬＡＮポート用ＴＬ１コマンドによって用意される。有効でないＳＶＩＤのフレームは除去（ドロップ）され、有効なパケットのヘッダはＭＡＣブリッジフィルタリングブロック１０６に転送される。フレームが選別（ドロップ）されるべきか或いはリングに転送される（通される）べきか否かを判定するために、ＭＡＣブリッジフィルタリングブロックは、フレームのＳＡ、ＣＶＩＤ及びＳＶＩＤを結合し、その結合に関する巡回冗長検査（ＣＲＣ）ハッシュを生成し、ダイナミックＬＵＴ１１２に対するキーを生成する。他の方向のトラフィックフローでは、リングからの制御フレームは、ＣＰＵ（図示せず）に転送され、リングからのデータフレームはリングイングレスルール検査ブロック１０８を介して進む。合致したＳＶＩＤを有するフレームは、ＭＡＣアドレスルックアップ用にＭＡＣブリッジフィルタリングフロック１０６に転送される。選別されてないフレームはＬＡＮポート優先キューに送信される。ダイナミックＬＵＴ１１２でのＭＡＣエントリコンテンツ例は図中下側に示されている。スタティックＬＵＴ１１０はＴＬ１コマンドで指定されたＳＡ又はＤＡフィールドと共にフレームを取り出す。
【００２３】
図３はＡＲＰＯＲＴ−ＰＲモードでの（ネイティブ）イーサーネットＭＡＣヘッダ処理例の概略を示す。このモードでは、唯１つのＬＡＮポート及び１つのリングポートがある。ＬＡＮイングレスパケットは、ネイティブ（顧客）ＶＬＡＮＩＤ（ＣＶＩＤ）を用いて３つのＣｏＳクラスの１つに対応付けられる（マッピングされる）。デフォルトのＣｏＳクラスはタグの付いていないパケットに割り当てられる。パケットのヘッダはＭＡＣブリッジフィルタリングブロック１０６に転送される。ＭＡＣブリッジフィルタリングブロック１０６は、パケットが選別（ドロップ）されるべきか或いはリングに転送される（通される）べきか否かを判別するために、パケットのＳＡ又はＤＡ及び顧客ＶＬＡＮ−ＩＤを結合し、ＬＵＴ１１０，１１２を探索するためのキーとして使用するために、その結合に関する巡回冗長検査（ＣＲＣ）を生成する。別の方向のトラフィックフローでは、リングからの制御パケットはＣＰＵ（図示せず）に転送され、データパケットはＭＡＣアドレスルックアップ用にＭＡＣブリッジフィルタリングブロック１０６に転送される。選別されてないパケットはＬＡＮポート優先キューに送信される。ＬＵＴ１１０，１１２内のＭＡＣエントリの内容の具体例は、図中下側に示されている。スタティックＬＵＴ１１０はＴＬ１コマンドで指定されたＳＡ又はＤＡフィールドと共にフレームを取り出す。
【００２４】
図４に示されるように、３つ全てのモードにおけるＭＡＣエントリデータフォーマットに共通性があり、図示の例はＭＡＣルックアップテーブルエントリデータフォーマットリストの具体例である。この設計内容と共に３つ全てのモードについて、適切なマスキングと共に１つの共通のフォーマットが使用可能である。
【００２５】
物理的には、ダイナミックルックアップテーブル中の１つのＭＡＣエントリが２つのワードより成り：ＨＢ，偶数ワード及びＡＤ，奇数ワードが図５に示され、これはＭＡＣダイナミックエントリコモンフォーマットビット定義のフォーマットである。図中、便宜上、ＨＢはヘッダブロックを表現し、ＡＤは関連するデータを表現するものとする。エントリは、以下の内容を含む：
・ＡＧＥ（エイジ）−エントリの年齢：００−古いエントリ又は無効なエントリ、０１，１０，１１−有効なエントリ
・ＢＰＯＲＴ（Ｂポート）−発信元ＭＡＣアドレスのブリッジポート
・ＡＶＡＩＬ−将来に備えた予約ビット
・ＰＡＲＩＴＹ（パリティ）−奇数パリティ、１ビットがエントリ及びそのバケットアドレスビット中の各ワードをカバーする
・ＭＡＣ＿ＡＤＤＲ−４８ビットＩＥＥＥ８０２．１ＤイーサーネットＭＡＣアドレスの上位３３ビット。
【００２６】
図６はＡＵＸＱＤＲメモリにおけるデータ構造図を示し、ブリッジ各々につき１つで計４つのルックアップテーブルを保持する。各ＬＵＴに３２Ｋハッシュバケットが存在し、各ハッシュバケットは７２ビットＭＡＣエントリを４つ保持している。ヘッダブロック（ＨＢ）は奇数メモリロケーション内にあり、関連データ（ＡＤ）は偶数メモリロケーション内にある。バケット番号はＬＵＴに対するインデックス（指標）である。１２ビットＳＶＩＤ、１ビットＣＶＩＤ及び４８ビットＭＡＣアドレスのシーケンスにおける７２ビットＭＡＣヘッダのＣＲＣ−１５関数は、以下の目的でランダム化されたバケット番号を生成するのに使用される：
１．独立のＶＬＡＮ学習をサポートすること。ＳＶＩＤはＡＲＰＯＲＴ−ＳＲ／ＰＲモードでゼロに設定され、ＣＶＩＤはＣＲＣ−１５を計算するためにタグ付けされていなければゼロに設定される。
【００２７】
２．ｌａｂテスト環境の中で過剰なバケットオーバーフローを回避すること及びハッシュテーブルの中で平等に分散及び学習されること。
【００２８】
ＣＲＣ−１５関数の特性は、ＭＡＣアドレスの下位１５ビットをハッシュテーブル中に格納しないことによって、メモリ空間の節約を可能にする。後続の探索の間に、ＭＡＣアドレスの下位１５ビットを復元又は比較する必要はない。なぜなら、バケット番号と共に合致するＭＡＣアドレスの上位３３ビット、ＣＶＩＤ及びＳＶＩＤの合致するものは、ＭＡＣアドレスの合致する下位１５ビットに導くことが数学的に証明されるからである。
【００２９】
ＭＡＣブリッジフィルタリングは以下の機能より成る：
・フレームヘッダを読み取るため及び分析結果を書き込むためのブリッジ／ＭＭＵデータパスブロックに対するインターフェース。
【００３０】
・外部ＱＤＲハッシュテーブルメモリ及びＢＩＳＴに対するインターフェース。１Ｍｘ３６ＱＤＲメモリは、各ブリッジにつき１つで計４つのＭＡＣルックアップテーブル（ＬＵＴ）までを保持するために使用される。各ＬＵＴは３２Ｋハッシュバケット（バケットにつき４つのエントリ）である。
【００３１】
・ＣＰＵ経過時間と共にダイナミックＭＡＣエントリエイジング(aging)及びＭＡＣアドレス学習をサポートすること。
【００３２】
・ＬＡＮポート及びリングポート双方における同一ブリッジポートフィルタリング(SBPF:  Same  Bridge  Port  Filtering)をサポートすること。
【００３３】
・フレームのＭＡＣソースアドレス（ＳＡ）及び宛先アドレス（ＤＡ）に基づいてＣＰＵによるスタティックエントリ挿入及びフィルタリングをサポートすること。
【００３４】
・ＳＡフィルタリング、ＤＡフィルタリング及びＳＢＰＦに起因するパケット破棄に関する個々の統計値を用意すること。
【００３５】
・ＭＡＣアドレスポート移動検出及び収集されたオシレーションカウントをサポートすること。
【００３６】
・ラブ（ｌａｂ）デバッギングを支援する他の機能。
【００３７】
ＭＡＣブリッジフィルタハードウエア設計では、ブリッジフィルタは３２Ｋバケットに分割され、各バケットはそれらの関連するＳＶＩＤ及びＣＶＩＤと共に４つのＭＡＣアドレスを保持する。４８ビットＭＡＣアドレス及び１２ビットＣＶＩＤと共に連結された１２ビットＳＶＩＤは、そのフィルタに関する固有のエントリを形成し、本質的にはそれは７２ビットストリングでアドレス指定されるハッシュテーブルになる。更に、到来するパケットとで伝送される７２ビットストリングが必ずしもランダム化される必要がない場合も考慮されなければならない。例えば、典型的なｌａｂテスト手順は、以下のシナリオ（筋書き）で検査することを望む。
【００３８】
・ウォーキングワンテスト(Walking  One  Test)：ＭＡＣアドレスの全てのビットをゼロに維持し（１ビットを除く）、その“１”ビットの位置を、ＭＡＣアドレスのビット０からビット４７まで変える。
【００３９】
・ＭＡＣアドレスインクリメント：何らかの連続的な１５ビットのＭＡＣアドレスを取り出し、ストリングの他の全てのビットを不変に維持しつつ、０から３２７６７まで増やす（我々は３２ＫＭＡＣアドレスだけをサポートするよう求められている。）。
【００４０】
・ＳＶＩＤインクリメント：ストリングの他の全てのビットを不変に維持しつつ、０から４０９５まで増やす。
【００４１】
・ＣＶＩＤインクリメント：ストリングの他の全てのビットを不変に維持しつつ、０から４０９５まで増やす。
【００４２】
ＭＡＣブリッジフィルタ設計に使用されるハッシュ関数は、上記のシナリオ全てについてバケットオーバーフローを最小化可能であるべきである。既に４つのエントリがバケット中にあり、別の異なる７２ビットストリングがこのバケットにハッシュされるならば、バケットはオーバーフローする。
【００４３】
ＣＲＣ−１５の以下の特性に起因して、ＭＡＣブリッジフィルタに対するハッシュ関数として選択される：
１．ウォーキングワンテストの場合に、７２ビットストリングの中で何らかの２ビットを検出する。
【００４４】
２．如何なる奇数のビットエラーも検出する。
【００４５】
３．MACアドレスインクリメント、SVIDインクリメント及びCVIDテストインクリメントの場合に、長さが１５未満の如何なるバーストエラーも検出する。
【００４６】
４．入力が充分にランダムならば、CRCの出力もランダムである。
【００４７】
５．所与のストリングの上位５７ビット及びそのCRC署名の下で、ストリングの下位１５ビットが固有に決定される。
【００４８】
巡回冗長検査（CRC）はチェックサムを生成するのに使用される或るタイプのハッシュ関数であり、チェックサムは、ネットワークトラフィックのパケットやコンピュータファイルのブロックのような大きなデータブロックからの少ないビット数であり、伝送又は記憶におけるエラーを検出するためのものである。CRCは算出され、伝送又は格納前に付加され、何の変化も生じていないことを確認するためにその後に検査される。CRCは、それらがバイナリハードウエアでの実現に簡易であること、数学的に分析しやすいこと及び特に伝送チャネルで生じた一般的なエラーを検出するのに有利なことに起因して、CRCは非常に一般的である。
【００４９】
CRC関数の具体例は以下のものを含む：
・ＣＲＣ−８：          Ｘ８＋Ｘ２＋Ｘ＋１
・ＣＲＣ−１５：        Ｘ１５＋Ｘ＋１
・ＣＲＣ−ＣＣＩＴＴ：  Ｘ１６＋Ｘ１２＋Ｘ５＋１
・ＣＲＣ−１６（ＩＢＭ）：Ｘ１６＋Ｘ１５＋Ｘ２＋１
・ＣＲＣ−３２（８０２．３）：Ｘ３２＋Ｘ２６＋Ｘ２３＋Ｘ２２＋Ｘ１６＋Ｘ１２＋Ｘ１１＋Ｘ１０＋Ｘ８＋Ｘ７＋Ｘ５＋Ｘ４＋Ｘ２＋Ｘ＋１
・ＣＲＣ３２ｃ：Ｘ３２＋Ｘ２８＋Ｘ２７＋Ｘ２６＋Ｘ２３＋Ｘ２２＋Ｘ２０＋Ｘ１９＋Ｘ１８＋Ｘ１４＋Ｘ１３＋Ｘ１１＋Ｘ１０＋Ｘ９＋Ｘ８＋Ｘ６＋１
ＭＢＦデザイン用のハッシュ関数として又は如何なるブリッジフィルタ設計用にも、如何なるＣＲＣ関数が使用されてもよい。５７ｍｓｂｓ及び１５ｌｓｂｓを有する７２ビットテーブルエントリに基づくこの特定の例では、ＣＲＣ−１５関数が特に適している。
【００５０】
ストリングの５７ｍｓｂｓ及びそのＣＲＣシグネチャの下で、ストリングの１５ｌｓｂｓは固有に決定されることが示される。ＣＲＣ−１５関数は次のように定義される：
Ｇ（Ｘ）＝  Ｘ１５＋Ｘ＋１
各々が７２ビットを有し且つ各々が同じ５７ｍｓｂを有する所与の２つのストリングの下で、それらのＣＲＣ−１５シグネチャが同じであったならば（ＣＲＣ−１５のＧ（Ｘ）＝  Ｘ１５＋Ｘ＋１）、それらは同じ１５ｌｓｂｓを所有しなければならない。即ち、２つのストリングは一致しなければならない。
【００５１】
証明：
１）先ず、ストリング１をＰ５７（Ｘ）＋Ｐ１（Ｘ）に、及びストリング２をＰ５７（Ｘ）＋Ｐ２（Ｘ）に分解し、Ｐ５７（Ｘ）は５７ｍｓｂｓで構成される多項式を表現し、Ｐ１（Ｘ）及びＰ２（Ｘ）は１５ｌｓｂｓで構成される多項式を表現する。
【００５２】
２）ＣＲＣ−１５から、次式がえら得る：
Ｘ１５*（Ｐ５７（Ｘ）＋Ｐ１（Ｘ））＝Ｑ１（Ｘ）*Ｇ（Ｘ）＋Ｒ（Ｘ）  ・・・（ｅｑ．１）
Ｘ１５*（Ｐ５７（Ｘ）＋Ｐ２（Ｘ））＝Ｑ２（Ｘ）*Ｇ（Ｘ）＋Ｒ（Ｘ）  ・・・（ｅｑ．２）
（ｅｑ．１）−（ｅｑ．２）＝＞Ｘ１５（Ｐ１（Ｘ）−Ｐ２（Ｘ））＝（Ｑ１（Ｘ）−Ｑ２（Ｘ））*Ｇ（Ｘ）  ・・・（ｅｑ．３）
３）Ｘ１５はＧ（Ｘ）で割り切れないので、（ｅｑ．３）を成立させるためには、Ｐ１（Ｘ）−Ｐ２（Ｘ）がＧ（Ｘ）で割り切れなければならない。更に、Ｇ（Ｘ）の最高指数は１５であり、Ｐ１（Ｘ）及びＰ２（Ｘ）の最高指数は１４であるので、Ｇ（Ｘ）によって割り切れるためにはＰ１（Ｘ）−Ｐ２（Ｘ）は０でなければならない。即ち、Ｐ１（Ｘ）はＰ２（Ｘ）に等しくなければならない。
【００５３】
その結果、７２ビットストリングの１５ｌｓｂｓは、ハードウエアリソースを節約するためにハッシュテーブル中に記載されない。しかしながら、或る状況では、デバッグ用に及び監視目的用に７２ビットヘッダ全てを見ることが有用かもしれない。７２ビットストリングの１５ｌｓｂｓを復元する或る単純な手法は、１５ビット全ての組み合わせを試行し、そのＣＲＣ−１５の値に合致するものを探すことである。しかしながらこれは最悪の場合、３２７６８回のＣＲＣ−１５計算を必要とし、平均でもその半数を要する。所与の５７ｍｓｂ及びＣＲＣ−１５シグネチャの下で７２ビットストリングの１５ｌｓｂを復元する高速な方法は、次の通りである：
Ｘ１５*（Ｐ５７（Ｘ）＋Ｐ１５（Ｘ））＝Ｑ（Ｘ）*Ｇ（Ｘ）＋Ｒ（Ｘ）  ・・・（ｅｑ．４）
ここで、
Ｐ５７（Ｘ）＝ａ５６Ｘ７１＋ａ５５Ｘ７０＋．．．＋ａ０Ｘ１５，ｉ＝０〜５６
Ｐ１５（Ｘ）＝ｂ１４Ｘ１４＋ｂ１３Ｘ１３＋．．．＋ｂｊＸｊ＋．．．＋ｂ０，ｊ＝０〜１４
Ｑ（Ｘ）＝ｑ７１Ｘ７１＋ｑ７０Ｘ７０＋．．．＋ｑｋＸｋ＋．．．＋ｑ０，ｋ＝０〜７１
Ｒ（Ｘ）＝ｒ１４Ｘ１４＋ｒ１３Ｘ１３＋．．．＋ｒｊＸｊ＋．．．＋ｒ０，ｊ＝０〜１４
及び  Ｇ（Ｘ）＝Ｘ１５＋Ｘ＋１。
【００５４】
ａｉ（ｉ＝０〜５６）及びｒｊ（ｊ＝０〜１４）の下で、ｂｊ（ｊ＝０〜１４）及びｂｋ（ｋ＝０〜７１）は、以下に示されるように、一群の線形方程式を解くことで一意に決定可能である。
【００５５】
１．次のように（ｅｑ．４）を書き直す（“−”はキャリーを除いてＣＲＣバイナリ演算における“＋”と同じ）。
【００５６】
ｘ１５（ａ５６Ｘ７１＋ａ５５Ｘ７０＋．．．＋ａ０Ｘ１５＋ｂ１４Ｘ１４＋ｂ１３Ｘ１３＋．．．＋ｂｊＸｊ＋．．．＋ｂ０）＋ｒ１４Ｘ１４＋ｒ１３Ｘ１３＋．．．＋ｒｊＸｊ＋．．．＋ｒ０
＝（ｑ７１Ｘ７１＋ｑ７０Ｘ７０＋．．．＋ｑｋＸｋ＋．．．＋ｑ０）（Ｘ１５＋Ｘ＋１）  ・・・（ｅｑ．５）
２．Ｘの同じ次数の係数を等しくすることで、次式を得る：
ａｉ＝ｑｉ＋１５，  （ｉ＝４３〜５６）  ・・・（ｅｑ．６）
ａ４２＝ｑ５７＋ｑ７１  ・・・（ｅｑ．７）
ａｉ＝ｑｉ＋１５＋ｑｉ＋２９＋ｑｉ＋３０  ，（ｉ＝０〜４１）  ・・・（ｅｑ．８）
ｒ０＝ｑ０  ・・・（ｅｑ．９）
ｒｉ＝ｑｉ−１＋ｑｉ  ，（ｉ＝１〜１４）・・・（ｅｑ．１０）
ｂｉ＝ｑｉ＋ｑｉ＋１４＋ｑｉ＋１５    ，（ｉ＝０〜１４）・・・（ｅｑ．１１）
３．（ｅｑ．６，７，８，９，１０）を並べ替え、未知数（ｑｉ）を左辺に、定数（ａｉ，ｒｊ）を右辺に移項すると、行列を用いて一群の方程式として表現できる：
ＰＱ＝Ｃ
４．Ｐは正方形の正則行列であり、ランク７２の下三角行列である。従ってＱは固有の解を有する。
【００５７】
５．（ｅｑ．１１）より、ｂｉ（ｉ＝０〜１４）は固有に決定可能である。
【００５８】
６．かくて７２ビットサーチストリングについてＱ（Ｘ）を導出し、更に外のストリングについて下位１５ビットを復元できる。
【００５９】
以上本発明の特定の実施例が説明されてきたが、説明された実施例に等価な他の実施例が存在することは当業者に理解されるであろう。従って本発明は説明された具体的な実施例に限定されず、添付の特許請求の範囲によってのみ限定されることが理解されるべきである。
【００６０】
以下、本発明により教示される手段が例示的に列挙される。
【００６１】
（付記１）
ネットワークトラフィックのパケットを受信する回路であって、前記パケットは該パケットのソースのＭＡＣアドレス及び該パケットの宛先のＭＡＣアドレスの少なくとも１つを有するところの回路と、
ＭＡＣアドレスを含むデータから生成される巡回冗長検査ハッシュを複数個格納するルックアップテーブルと、
前記ルックアップテーブル中のパケットのＭＡＣアドレスを探索する探索回路と、
を有するＭＡＣブリッジフィルタであって、前記探索回路は、
パケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュを生成する回路と、
パケットのＭＡＣアドレスを含むデータの生成された巡回冗長検査ハッシュを用いて、前記ルックアップテーブルでパケットのＭＡＣアドレスを探索する回路と、
パケットのＭＡＣアドレスが前記ルックアップテーブルで発見されたか否かに基づいて、各パケットを通過させる又は通過させないように機能する回路と、
を有することを特徴とするＭＡＣブリッジフィルタ。
【００６２】
（付記２）
前記ＭＡＣアドレスを含む前記データがサービスプロバイダの識別子を含み、前記パケットのＭＡＣアドレスを含むデータが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子を含む
ことを特徴とする付記１記載のＭＡＣブリッジフィルタ。
【００６３】
（付記３）
前記ＭＡＣアドレスを含む前記データが顧客の識別子を含み、前記パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子を含む
ことを特徴とする付記１記載のＭＡＣブリッジフィルタ。
【００６４】
（付記４）
前記ＭＡＣアドレスを含むデータがサービスプロバイダの識別子及び顧客の識別子を含み、パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子と、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子とを含む
ことを特徴とする付記１記載のＭＡＣブリッジフィルタ。
【００６５】
（付記５）
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータから生成された巡回冗長検査ハッシュが、前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータより少ないデータを有する
ことを特徴とする付記４記載のＭＡＣブリッジフィルタ。
【００６６】
（付記６）
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子は、前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする付記５記載のＭＡＣブリッジフィルタ。
【００６７】
（付記７）
前記ＭＡＣアドレスを含むデータの巡回冗長検査ハッシュ及びパケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュの双方が、関数Ｇ（Ｘ）＝Ｘ１５＋Ｘ＋１を用いて生成される
ことを特徴とする付記４記載のＭＡＣブリッジフィルタ。
【００６８】
（付記８）
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、前記顧客の識別が１２ビットより成り、前記巡回冗長検査ハッシュが１５ビットより成る
ことを特徴とする付記７記載のＭＡＣブリッジフィルタ。
【００６９】
（付記９）
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、１２ビットより成る前記顧客の識別が、１５ビットより成る前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする付記８記載のＭＡＣブリッジフィルタ。
【００７０】
（付記１０）
ネットワークトラフィックのパケットを受信するステップであって、前記パケットは該パケットのソースのＭＡＣアドレス及び該パケットの宛先のＭＡＣアドレスの少なくとも１つを有するところのステップと、
ＭＡＣアドレスを含むデータから生成される巡回冗長検査ハッシュをルックアップテーブルに複数個格納するステップと、
前記ルックアップテーブル中のパケットのＭＡＣアドレスを探索する探索ステップと、
を有する方法であって、前記探索ステップは、
パケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュを生成し、
パケットのＭＡＣアドレスを含むデータの生成された巡回冗長検査ハッシュを用いて、前記ルックアップテーブルでパケットのＭＡＣアドレスを探索することで実行され、
パケットのＭＡＣアドレスが前記ルックアップテーブルで発見されたか否かに基づいて、各パケットを通過させる又は通過させないように判定がなされる、
ことを特徴とする方法。
【００７１】
（付記１１）
前記ＭＡＣアドレスを含む前記データがサービスプロバイダの識別子を含み、前記パケットのＭＡＣアドレスを含むデータが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子を含む
ことを特徴とする付記１０記載の方法。
【００７２】
（付記１２）
前記ＭＡＣアドレスを含む前記データが顧客の識別子を含み、前記パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子を含む
ことを特徴とする付記１０記載の方法。
【００７３】
（付記１３）
前記ＭＡＣアドレスを含むデータがサービスプロバイダの識別子及び顧客の識別子を含み、パケットのＭＡＣアドレスを含む前記データが、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連するサービスプロバイダの識別子と、前記パケットが受信されるネットワークポート或いは前記パケットが伝送されるネットワークポートに関連する顧客の識別子とを含む
ことを特徴とする付記１０記載の方法。
【００７４】
（付記１４）
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータから生成された巡回冗長検査ハッシュが、前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子を含むデータより少ないデータを有する
ことを特徴とする付記１３記載の方法。
【００７５】
（付記１５）
前記ＭＡＣアドレス、前記サービスプロバイダの識別子及び前記顧客の識別子は、前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする付記１４記載の方法。
【００７６】
（付記１６）
前記ＭＡＣアドレスを含むデータの巡回冗長検査ハッシュ及びパケットのＭＡＣアドレスを含むデータの巡回冗長検査ハッシュの双方が、関数Ｇ（Ｘ）＝Ｘ１５＋Ｘ＋１を用いて生成される
ことを特徴とする付記１３記載の方法。
【００７７】
（付記１７）
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、前記顧客の識別が１２ビットより成り、前記巡回冗長検査ハッシュが１５ビットより成る
ことを特徴とする付記１６記載の方法。
【００７８】
（付記１８）
前記ＭＡＣアドレスが４８ビットより成り、前記サービスプロバイダの識別子が１２ビットより成り、１２ビットより成る前記顧客の識別が、１５ビットより成る前記巡回冗長検査ハッシュから復元可能である
ことを特徴とする付記１７記載の方法。
【図面の簡単な説明】
【００７９】
【図１】イーサーネットMACヘッダ処理例のブロック図である。
【図２】イーサーネットMACヘッダ処理例のブロック図である。
【図３】イーサーネットMACヘッダ処理例のブロック図である。
【図４】MACルックアップテーブルエントリデータフォーマットリストのフォーマット例を示す図である。
【図５】MACダイナミックエントリ共通フォーマットビット定義のフォーマット例を示す図である。
【図６】メモリ中のルックアップテーブルデータベース構造を例示する図である。
【符号の説明】
【００８０】
１０２  ＬＡＮイングレスルール検査ブロック
１０４  サービスプロバイダＶＬＡＮＩＤ
１０６  ＭＡＣブリッジフィルタリングブロック
１０８  リングイングレスルール検査ブロック
１１０，１１２  ルックアップテーブル
【図１】
2007097188.tif 000003
【図２】
2007097188.tif 000004
【図３】
2007097188.tif 000005
【図４】
2007097188.tif 000006
【図５】
2007097188.tif 000007
【図６】
2007097188.tif 000008