[go: up one dir, main page]

JP2002334114A - テーブル管理方法及び装置 - Google Patents

テーブル管理方法及び装置

Info

Publication number
JP2002334114A
JP2002334114A JP2001139545A JP2001139545A JP2002334114A JP 2002334114 A JP2002334114 A JP 2002334114A JP 2001139545 A JP2001139545 A JP 2001139545A JP 2001139545 A JP2001139545 A JP 2001139545A JP 2002334114 A JP2002334114 A JP 2002334114A
Authority
JP
Japan
Prior art keywords
data
address
registered
tables
input
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP2001139545A
Other languages
English (en)
Inventor
Koichi Kagawa
幸一 香川
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Allied Telesis Holdings KK
Original Assignee
Allied Telesis KK
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Allied Telesis KK filed Critical Allied Telesis KK
Priority to JP2001139545A priority Critical patent/JP2002334114A/ja
Priority to US09/886,372 priority patent/US6910118B2/en
Priority to TW90120223A priority patent/TW581965B/zh
Priority to EP20010119626 priority patent/EP1256885A3/en
Priority to KR1020010051785A priority patent/KR20020086200A/ko
Publication of JP2002334114A publication Critical patent/JP2002334114A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/54—Organization of routing tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/45—Network directories; Name-to-address mapping
    • H04L61/4552—Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Small-Scale Networks (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

(57)【要約】 【課題】 効率的なハッシュ検索を可能にし、再ハッシ
ュ発生確率の低減させるテーブル管理技術を提供する。 【解決手段】 ＭＡＣアドレステーブルを複数のバンク
に分割し、当該複数のバンクがハッシュ出力をアドレス
として同時にアクセスされる。複数のバンクからそれぞ
れ読み出された登録ＭＡＣアドレスと入力ＭＡＣアドレ
スとを比較し、少なくとも１つの比較結果が一致を示す
ときに、入力ＭＡＣアドレスはＭＡＣアドレステーブル
に登録されていると判定され、それ以外は新規ＭＡＣア
ドレスと判定される。同時アクセスされた複数のバンク
の記憶スペースに空きがあれば、同一ハッシュ出力に対
して複数のＭＡＣアドレスを対応づけて登録することが
できる。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明はテーブルの管理技術
に係り、特に入力データより少ないビット数に縮退させ
たデータを用いてアクセスを行うテーブル管理方法及び
管理装置に関する。
【０００２】
【従来の技術】テーブル検索にハッシュ（Ｈａｓｈ）法
を用いることはよく知られている。たとえば、標準的な
ＬＡＮ（Local-Area Network）ではすべてのネットワー
クデバイスにユニークなＭＡＣ（Media Access Contro
l）アドレスが割り付けられているが、４８ビットのＭ
ＡＣアドレスをハッシュ法を用いて検索する方法が知ら
れている。
【０００３】図４は、従来のＭＡＣアドレステーブル管
理方法を示すブロック図である。４８ビットのＭＡＣア
ドレスはハッシュ関数１０によって１０ビットデータに
変換され、それをエントリテーブル１１のアドレスデー
タとして用いる。
【０００４】エントリテーブル１１は、ここでは１０２
４個のエントリからなり、１つのエントリは、１つのＭ
ＡＣアドレス（４８ビット）、当該ＭＡＣアドレスが属
するスイッチのポート番号（４ビット）、当該ＭＡＣア
ドレスへのアクセス履歴を示すアクセスビット（１ビッ
ト）、および登録の有効／無効を示すバリッドビット
（１ビット）からなる。ただし、ポート番号のビット数
はスイッチのポート数に依存する。ここでは最大１６ポ
ートを想定して４ビットとしている。
【０００５】したがって、ハッシュ関数１０によって得
られた１０ビットのアドレスに従ってエントリテーブル
１１から１つのエントリが決定され、その登録ＭＡＣア
ドレスが比較器１２へ読み出される。比較器１２は、登
録ＭＡＣアドレスと入力したＭＡＣアドレスとを比較し
て、一致／不一致を判定する。
【０００６】しかしながら、周知のように、ハッシュ関
数によって４８ビットデータが１０ビットデータに縮退
しているために、異なる入力ＭＡＣアドレスがエントリ
テーブル１１の同一アドレスにマッピングされる場合が
発生する。この衝突の発生頻度はハッシュ関数の選択に
依存するから、衝突が生じた場合には、互いに別の値が
生成されるようにハッシュ関数を変更する再ハッシュが
行われる。
【０００７】
【発明が解決しようとする課題】しかしながら、再ハッ
シュが生じた場合には、それまで記憶していたエントリ
テーブル１１の内容を全て無効にする必要があり、ＭＡ
Ｃアドレス学習のパフォーマンスの点で大きな損失であ
る。したがって、いかにして再ハッシュの発生を抑える
かがハッシュメカニズムを考える上で重要な課題であ
る。
【０００８】また、ハードウエア量を抑えて効率的なハ
ッシュ検索を可能にすることも重要な課題である。
【０００９】
【課題を解決するための手段】本発明によるテーブル管
理装置は、所定ビット数の入力データをそれより少ない
ビット数の縮退データに変換し、その縮退データをテー
ブルアクセスのためのアドレスとして使用するものであ
り、前記所定ビット数と同じビット数の登録データを所
定数だけそれぞれ格納可能であり、前記縮退データによ
り同時にアクセスされる複数個のテーブルと、前記複数
個のテーブルから前記縮退データに従ってそれぞれ読み
出された登録データと前記入力データとを比較する複数
の比較手段と、前記複数の比較手段の比較結果に基づい
て、前記入力データが前記複数個のテーブルに登録され
ているか否かを判定する判定手段と、を有することを特
徴とする。
【００１０】このように、複数のテーブルが縮退データ
により同時にアクセスされ、それぞれ読み出された登録
データが入力データと比較されることで登録済みか否か
が判定される。複数の登録データが同時にアクセスされ
て読み出されるために、極めて効率的なサーチを行うこ
とができる。
【００１１】さらに、本発明によれば、前記入力データ
が前記複数個のテーブルに登録されていない場合、前記
縮退データにより同時にアクセスされた複数個のテーブ
ルの記憶スペースに空きスペースがあれば、前記入力デ
ータを新規データとして登録する制御手段を有すること
を特徴とする。
【００１２】このように新規データを登録することで、
縮退データにより同時にアクセスされた複数個のテーブ
ルの記憶スペースに複数個の異なる登録データを格納す
ることができる。言い換えれば、１つの縮退データに複
数の異なる登録データを対応づけることが可能となり、
空きスペースがある限り再ハッシュが発生しない。
【００１３】本発明による複数のテーブルを管理する方
法は、入力データをそれより少ないビット数の縮退デー
タに変換し、前記縮退データをアドレスとして前記複数
のテーブルを同時にアクセスし、前記複数のテーブルか
ら前記縮退データに従ってそれぞれ読み出された登録デ
ータと前記入力データとを比較し、比較結果に基づい
て、前記入力データが前記複数のテーブルに登録されて
いるか否かを判定する、ことを特徴とする。
【００１４】本発明の別の観点によれば、複数のバンク
に分割されたアドレステーブルを管理する方法は、入力
アドレスデータをハッシュ処理によりそれより少ないビ
ット数のアドレスに変換し、前記アドレスによって前記
複数のバンクを同時にアクセスし、前記複数個のバンク
から前記アドレスに従ってそれぞれ読み出された登録ア
ドレスと前記入力アドレスデータとを比較し、比較結果
に基づいて、前記入力アドレスデータが前記アドレステ
ーブルに登録されているか否かを判定する、ことを特徴
とする。
【００１５】さらに、前記入力アドレスデータが前記ア
ドレステーブルに登録されていない場合、前記アドレス
により同時にアクセスされた前記複数のバンクの記憶ス
ペースに空きスペースがあるか否かを判定し、前記空き
スペースがあれば、当該空きスペースに前記入力アドレ
スデータを新規アドレスとして登録し、前記空きスペー
スがなければ、前記ハッシュ処理を変更する、ことを特
徴とする。
【００１６】ハッシュ処理が変更されるのは、前記アド
レスにより同時にアクセスされた前記複数のバンクの記
憶スペースに空きスペースがなくなった場合に限られ
る。したがって、再ハッシュの発生確率は従来に比べて
大幅に低減する。
【００１７】
【発明の実施の形態】図１は本発明によるアドレステー
ブル管理装置の一実施形態を示すブロック図である。本
実施形態におけるエントリテーブル１０２は４つのバン
クＢ１〜Ｂ４に分割され、各バンクに最大２５６エント
リを格納できる。従って、エントリテーブル１０２は合
計２５６×４＝１０２４エントリを格納可能である。各
エントリは、従来と同様に、登録ＭＡＣアドレス、ポー
ト番号、アクセスビット、およびバリッドビットからな
る（図３参照）。
【００１８】ハッシュ関数１０１は、４８ビットＭＡＣ
アドレスに対してＣＲＣ３２の計算を行い、それにより
得られる３２ビット出力のうち所定位置の８ビットを選
択してエントリテーブル１０２へ出力する。エントリテ
ーブル１０２のバンクＢ１〜Ｂ４は、ハッシュ関数１０
１の８ビット出力をアドレスビットとして同時に入力す
る。したがって、１つのハッシュ出力（アドレスビッ
ト）によって、アドレス指定されたバンクＢ１〜Ｂ４の
記憶領域を同時にアクセスすることができる。
【００１９】バンクＢ１〜Ｂ４のアクセスされた記憶領
域にそれぞれエントリが存在すれば、それらの登録ＭＡ
Ｃアドレスを同時に読み出す。なお、アドレスビット数
を８としたのは、各バンクの最大エントリ数が２５６で
あることによる。たとえば、１０２４エントリのテーブ
ルを８等分して、各バンクの最大エントリ数を１２８に
した場合には、ハッシュ関数１０１の出力を７ビットに
すればよい。
【００２０】比較器Ｃ１〜Ｃ４は、読み出された４個の
登録ＭＡＣアドレスと入力ＭＡＣアドレスとを比較し、
それぞれの比較結果（一致／不一致）をＯＲ回路１０３
へ出力する。ＯＲ回路１０３は、４つの比較結果のうち
少なくとも１つの比較結果が一致を検出していれば、一
致検出をプロセッサ１０４へ通知する。
【００２１】プロセッサ１０４はＣＰＵ等のプログラム
制御プロセッサあるいは専用ハードウエア回路であり、
エントリテーブル１０２を管理する。プロセッサ１０４
は、ＯＲ回路１０３からの検出結果（一致／不一致）を
モニタしながら、次に述べるようなバンクＢ１〜Ｂ４に
対する登録／学習処理及び検索処理を実行する。
【００２２】（登録／学習処理）エントリテーブル１０
２の各バンクには、いくつかのＭＡＣアドレスがすでに
登録されているものとする。この状態で新規のＭＡＣア
ドレスがバンクＢ１〜Ｂ４にどのように登録されるかを
図２及び図３を参照しながら説明する。
【００２３】図２は、本実施形態におけるＭＡＣアドレ
ステーブルの登録／学習動作を説明するためのフローチ
ャートである。
【００２４】図２において、あるパケットのソースＭＡ
Ｃアドレスを入力し（ステップＳ２０１）、上述したハ
ッシュ関数１０１により８ビットアドレスを計算する
（ステップＳ２０２）。その８ビットアドレスにより指
定されたバンクＢ１〜Ｂ４の記憶領域を同時にアクセス
し、ＭＡＣアドレスが有効に登録されていれば、それを
読み出す（ステップＳ２０３）。そして、比較器Ｃ１〜
Ｃ４により、読み出された登録ＭＡＣアドレスとソース
ＭＡＣアドレスとが比較され、それぞれの比較結果（一
致／不一致）がＯＲ回路１０３へ出力される。上述した
ように、４つの比較結果の少なくとも１つが一致を示し
ているか、あるいは全部不一致であるか、によってＯＲ
回路１０３は一致／不一致を検出する（ステップＳ１０
４）。
【００２５】ＯＲ回路１０３によって一致が検出された
場合は（ステップＳ２０４のＹＥＳ）、入力したソース
ＭＡＣアドレスは既にエントリテーブル１０２に登録済
みであるから、学習処理は行わない。
【００２６】ＯＲ回路１０３によって不一致が検出され
た場合は（ステップＳ２０４のＮＯ）、現在アクセスさ
れているバンクＢ１〜Ｂ４の４つの記憶スペースに空き
があるか否かを各バリッドビットを参照することで判定
する（ステップＳ２０５）。もし空きスペースがあれば
（ステップＳ２０５のＹＥＳ）、そこに学習処理として
新規にＭＡＣアドレスを登録する（ステップＳ２０
６）。
【００２７】４つの記憶スペースが全て登録済みである
場合（ステップＳ２０５のＮＯ）、再ハッシュが実行さ
れる（ステップＳ２０７）。たとえば、全てのバリッド
ビットをクリアし、ハッシュ関数１０１において３２ビ
ットのＣＲＣ３２出力のうち異なる位置の８ビットを選
択することで、再ハッシュが実行される。
【００２８】図３は新規アドレス登録動作を説明するた
めのエントリテーブルの模式図である。ソースＭＡＣア
ドレスのハッシュ関数値である８ビットアドレスによっ
てバンクＢ１〜Ｂ４の記憶スペース３０１がアクセスさ
れているものとする。ここでは、バンクＢ２およびＢ４
には既にアドレスＡａおよびＡｂが登録されているが、
バンクＢ１およびＢ３は空きスペース３０２および３０
３となっている。
【００２９】ソースＭＡＣアドレスＡｃが既に登録され
ているアドレスＡａおよびＡｂのいずれとも異なる場合
には（不一致：図２におけるステップＳ２０４のＮ
Ｏ）、このソースＭＡＣアドレスＡｃは、たとえばバン
クＢ１のスペース３０２に新規アドレスとして登録され
る。同様にして、ソースＭＡＣアドレスＡｄが同じハッ
シュ出力により同じ記憶スペース３０１にアドレス指定
されたとしても、それが既に登録されているアドレスＡ
ａ、Ａｂ，Ａｃのいずれとも異なる場合には、バンクＢ
３のスペース３０３に新規アドレスとして登録される。
こうして、同じハッシュ出力値に対して、ここでは４個
の異なるアドレスを登録することができる。
【００３０】再ハッシュが発生するのは、さらにソース
ＭＡＣアドレスＡｅが同じハッシュ出力により同じ記憶
スペース３０１にアドレス指定され、既に空きスペース
が存在しない場合のみである。すなわち、本実施形態で
は、同じハッシュ関数値に対して、４個まで確実に登録
することができ、再ハッシュの頻度を低下させることが
できる。
【００３１】また、本実施形態では、４個の登録ＭＡＣ
アドレスを同時に読み出し４個の比較器Ｃ１〜Ｃ４によ
りそれぞれソースＭＡＣアドレスと比較するために、高
速学習が可能となる。
【００３２】（検索処理）あるパケットのデスティネー
ションＭＡＣアドレスを入力し、上述したハッシュ関数
１０１により８ビットアドレスを計算する。その８ビッ
トアドレスにより指定されたバンクＢ１〜Ｂ４の記憶領
域を同時にアクセスし、ＭＡＣアドレスが有効に登録さ
れていれば、それを読み出す。そして、比較器Ｃ１〜Ｃ
４により、読み出された登録ＭＡＣアドレスとデスティ
ネーションＭＡＣアドレスとが比較され、それぞれの比
較結果（一致／不一致）がＯＲ回路１０３へ出力され
る。上述したように、４つの比較結果の少なくとも１つ
が一致を示しているか、あるいは全部不一致であるか、
によってＯＲ回路１０３は一致／不一致を検出する。
【００３３】一致が検出されたならば、プロセッサ１０
４は、当該登録ＭＡＣアドレスのポート番号を読み出
し、それを当該パケットの転送先とする。不一致が検出
されたならば、プロセッサ１０４は当該パケットをブロ
ードキャストパケットとして全てのスイッチポートに転
送する。
【００３４】なお、本実施形態では、エントリテーブル
１０２を４分割したが、任意の数Ｎに分割しても良い。
Ｎを４より大きな数にすれば、同じハッシュ関数値に対
して多くの異なるアドレスを登録することができ、再ハ
ッシュの発生確率をさらに下げることができる。なお、
バンク分割することで、比較器を同じ数だけ用意する必
要があるが、比較器は簡単な構成であるから、システム
全体としては大きな負担にはならない。
【００３５】本発明によるアーキテクチャは、ＭＡＣア
ドレステーブルの管理だけでなく、テーブルサーチおよ
びデータ登録一般に適用可能であり、またハッシュ関数
も任意のものを使用することができる。
【００３６】
【発明の効果】以上詳細に説明したように、本発明によ
るテーブル管理方法及び装置は、複数のテーブルが縮退
データにより同時にアクセスされ、それぞれ読み出され
た登録データが入力データと比較されることで登録済み
か否かが判定される。複数の登録データが同時にアクセ
スされて読み出されるために、極めて効率的なサーチを
行うことができる。
【００３７】さらに、本発明によれば、前記入力データ
が前記複数個のテーブルに登録されていない場合、前記
縮退データにより同時にアクセスされた複数個のテーブ
ルの記憶スペースに空きスペースがあれば、前記入力デ
ータを新規データとして登録する。したがって、縮退デ
ータにより同時にアクセスされた複数個のテーブルの記
憶スペースに複数個の異なる登録データを格納すること
ができる。言い換えれば、１つの縮退データに複数の異
なる登録データを対応づけることが可能となり、再ハッ
シュ発生確率を下げることができる。
【００３８】また、テーブルをバンク分割することで、
比較手段を同じ数だけ用意する必要があるが、比較手段
自体は簡単な構成であるから、システム全体としては大
きなハードウエア量の増大にはならない。
【図面の簡単な説明】
【図１】本発明によるアドレステーブル管理装置の一実
施形態を示すブロック図である。
【図２】本実施形態におけるＭＡＣアドレステーブルの
登録／学習動作を説明するためのフローチャートであ
る。
【図３】新規アドレス登録動作を説明するためのエント
リテーブルの模式図である。
【図４】従来のＭＡＣアドレステーブル管理方法を示す
ブロック図である。
【符号の説明】
１０１ ハッシュ関数 １０２ エントリテーブル １０３ ＯＲ回路 １０４ プロセッサ Ｂ１〜Ｂ４ バンク Ｃ１〜Ｃ４ 比較器

Claims (17)

    【特許請求の範囲】
  1. 【請求項１】 所定ビット数の入力データをそれより少
    ないビット数の縮退データに変換し、その縮退データを
    テーブルアクセスのためのアドレスとして使用するテー
    ブル管理装置において、 前記所定ビット数と同じビット数の登録データを所定数
    だけそれぞれ格納可能であり、前記縮退データにより同
    時にアクセスされる複数個のテーブルと、 前記複数個のテーブルから前記縮退データに従ってそれ
    ぞれ読み出された登録データと前記入力データとを比較
    する複数の比較手段と、 前記複数の比較手段の比較結果に基づいて、前記入力デ
    ータが前記複数個のテーブルに登録されているか否かを
    判定する判定手段と、 を有することを特徴とするテーブル管理装置。
  2. 【請求項２】 さらに、 前記入力データが前記複数個のテーブルに登録されてい
    ない場合、前記縮退データにより同時にアクセスされた
    複数個のテーブルの記憶スペースに空きスペースがあれ
    ば、前記入力データを新規データとして登録する制御手
    段を有することを特徴とする請求項１記載のテーブル管
    理装置。
  3. 【請求項３】 前記複数の比較手段の各々は、対応する
    登録データと前記入力データとを比較して一致及び不一
    致のいずれかを出力し、 前記判定手段は、前記複数の比較手段の比較結果のうち
    少なくとも１つが一致を示すときには前記入力データが
    前記複数のテーブルのいずれかに登録されていると判定
    し、それ以外は登録されていないと判定する、 ことを特徴とする請求項１または２記載のテーブル管理
    装置。
  4. 【請求項４】 複数のバンクに分割されたアドレステー
    ブルを管理する方法において、 入力アドレスデータをハッシュ処理によりそれより少な
    いビット数のアドレスに変換し、 前記アドレスによって前記複数のバンクを同時にアクセ
    スし、 前記複数個のバンクから前記アドレスに従ってそれぞれ
    読み出された登録アドレスと前記入力アドレスデータと
    を比較し、 比較結果に基づいて、前記入力アドレスデータが前記ア
    ドレステーブルに登録されているか否かを判定する、 ことを特徴とするアドレステーブル管理方法。
  5. 【請求項５】 さらに、 前記入力アドレスデータが前記アドレステーブルに登録
    されていない場合、前記アドレスにより同時にアクセス
    された前記複数のバンクの記憶スペースに空きスペース
    があるか否かを判定し、 前記空きスペースがあれば、当該空きスペースに前記入
    力アドレスデータを新規アドレスとして登録し、 前記空きスペースがなければ、前記ハッシュ処理を変更
    する、 ことを特徴とする請求項４記載のアドレステーブル管理
    方法。
  6. 【請求項６】 前記ハッシュ処理は、ＣＲＣ３２計算に
    より得られる３２ビットデータのうち、予め定められた
    位置の所望ビット数のデータを選択することにより実行
    されることを特徴とする請求項５記載のアドレステーブ
    ル管理方法。
  7. 【請求項７】 前記ハッシュ処理は、ＣＲＣ３２計算に
    より得られる３２ビットデータのうち、前記予め定めら
    れた位置とは別の位置にある前記所望ビット数のデータ
    を選択することにより変更されることを特徴とする請求
    項６記載のアドレステーブル管理方法。
  8. 【請求項８】 入力ＭＡＣ（メディアアクセスコントロ
    ール）アドレスをハッシュ関数により変換し、そのハッ
    シュ出力をＭＡＣアドレステーブルをアクセスするため
    のアドレスとして使用するテーブル管理装置において、 前記ＭＡＣアドレステーブルは複数のバンクに分割さ
    れ、当該複数のバンクが前記ハッシュ出力をアドレスと
    して同時にアクセスされ、 前記複数のバンクから前記ハッシュ出力に従ってそれぞ
    れ読み出された登録ＭＡＣアドレスと前記入力ＭＡＣア
    ドレスとを比較する複数の比較手段と、 前記複数の比較手段の比較結果に基づいて、前記入力Ｍ
    ＡＣアドレスが前記ＭＡＣアドレステーブルに登録され
    ているか否かを判定する判定手段と、 を有することを特徴とするテーブル管理装置。
  9. 【請求項９】 前記複数の比較手段の各々は、対応する
    登録ＭＡＣアドレスと前記入力ＭＡＣアドレスとを比較
    して一致及び不一致のいずれかを出力し、 前記判定手段は、前記複数の比較手段の比較結果のうち
    少なくとも１つが一致を示すときには前記入力ＭＡＣア
    ドレスが前記ＭＡＣアドレステーブルに登録されている
    と判定し、それ以外は登録されていないと判定する、 ことを特徴とする請求項８記載のテーブル管理装置。
  10. 【請求項１０】 複数のテーブルを管理する方法におい
    て、 入力データをそれより少ないビット数の縮退データに変
    換し、 前記縮退データをアドレスとして前記複数のテーブルを
    同時にアクセスし、 前記複数のテーブルから前記縮退データに従ってそれぞ
    れ読み出された登録データと前記入力データとを比較
    し、 比較結果に基づいて、前記入力データが前記複数のテー
    ブルに登録されているか否かを判定する、 ことを特徴とするテーブル管理方法。
  11. 【請求項１１】 さらに、 前記入力データが前記複数のテーブルに登録されていな
    い場合、前記縮退データにより同時にアクセスされた複
    数のテーブルの記憶スペースに空きスペースがあるか否
    かを判定し、 空きスペースがあれば、前記入力データを新規データと
    して登録する、 ことを特徴とする請求項１０記載のテーブル管理方法。
  12. 【請求項１２】 複数のテーブルを管理するプログラム
    において、 入力データをそれより少ないビット数の縮退データに変
    換するステップと、 前記縮退データをアドレスとして前記複数のテーブルを
    同時にアクセスするステップと、 前記複数のテーブルから前記縮退データに従ってそれぞ
    れ読み出された登録データと前記入力データとを比較す
    るステップと、 比較結果に基づいて、前記入力データが前記複数のテー
    ブルに登録されているか否かを判定するステップと、 をコンピュータに実行させることを特徴とするテーブル
    管理プログラム。
  13. 【請求項１３】 さらに、 前記入力データが前記複数のテーブルに登録されていな
    い場合、前記縮退データにより同時にアクセスされた複
    数のテーブルの記憶スペースに空きスペースがあるか否
    かを判定するステップと、 空きスペースがあれば、前記入力データを新規データと
    して登録するステップと、 をコンピュータに実行させることを特徴とする請求項１
    ２記載のテーブル管理プログラム。
  14. 【請求項１４】 複数のテーブルを管理するプログラム
    を記録した記録媒体において、 入力データをそれより少ないビット数の縮退データに変
    換するステップと、 前記縮退データをアドレスとして前記複数のテーブルを
    同時にアクセスするステップと、 前記複数のテーブルから前記縮退データに従ってそれぞ
    れ読み出された登録データと前記入力データとを比較す
    るステップと、 比較結果に基づいて、前記入力データが前記複数のテー
    ブルに登録されているか否かを判定するステップと、 をコンピュータに実行させるためのプログラムを記録し
    た記録媒体。
  15. 【請求項１５】 さらに、 前記入力データが前記複数のテーブルに登録されていな
    い場合、前記縮退データにより同時にアクセスされた複
    数のテーブルの記憶スペースに空きスペースがあるか否
    かを判定するステップと、 空きスペースがあれば、前記入力データを新規データと
    して登録するステップと、 をコンピュータに実行させるためのプログラムを記録し
    た請求項１４記載の記録媒体。
  16. 【請求項１６】 複数のテーブルとプロセッサとからな
    るコンピュータシステムにおいて、 前記プロセッサに実行させるプログラムが、 入力データをそれより少ないビット数の縮退データに変
    換するステップと、 前記縮退データによって前記複数のテーブルを同時にア
    クセスするステップと、 前記複数のテーブルから前記縮退データに従ってそれぞ
    れ読み出された登録データと前記入力データとを比較す
    るステップと、 比較結果に基づいて、前記入力データが前記複数のテー
    ブルに登録されているか否かを判定するステップと、 を有することを特徴とするコンピュータシステム。
  17. 【請求項１７】 前記プログラムは、さらに、 前記入力データが前記複数のテーブルに登録されていな
    い場合、前記縮退データにより同時にアクセスされた複
    数のテーブルの記憶スペースに空きスペースがあるか否
    かを判定するステップと、 空きスペースがあれば、前記入力データを新規データと
    して登録するステップと、 を有することを特徴とする請求項１６記載のコンピュー
    タシステム。
JP2001139545A 2001-05-10 2001-05-10 テーブル管理方法及び装置 Pending JP2002334114A (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP2001139545A JP2002334114A (ja) 2001-05-10 2001-05-10 テーブル管理方法及び装置
US09/886,372 US6910118B2 (en) 2001-05-10 2001-06-22 Table management technique
TW90120223A TW581965B (en) 2001-05-10 2001-08-17 Table management technique
EP20010119626 EP1256885A3 (en) 2001-05-10 2001-08-20 Table management technique
KR1020010051785A KR20020086200A (ko) 2001-05-10 2001-08-27 테이블 관리 기술

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2001139545A JP2002334114A (ja) 2001-05-10 2001-05-10 テーブル管理方法及び装置

Publications (1)

Publication Number Publication Date
JP2002334114A true JP2002334114A (ja) 2002-11-22

Family

ID=18986303

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2001139545A Pending JP2002334114A (ja) 2001-05-10 2001-05-10 テーブル管理方法及び装置

Country Status (5)

Country Link
US (1) US6910118B2 (ja)
EP (1) EP1256885A3 (ja)
JP (1) JP2002334114A (ja)
KR (1) KR20020086200A (ja)
TW (1) TW581965B (ja)

Cited By (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005236997A (ja) * 2004-02-20 2005-09-02 Fujitsu Ltd 高速なルーティングテーブル学習およびルックアップ
WO2007119540A1 (ja) * 2006-03-31 2007-10-25 Kyushu Institute Of Technology 連想メモリ
US7469243B2 (en) 2003-01-27 2008-12-23 International Business Machines Corporation Method and device for searching fixed length data
JP2009194773A (ja) * 2008-02-15 2009-08-27 Nec Access Technica Ltd 優先制御システム、優先制御装置、優先制御方法、及び優先制御プログラム
WO2009110445A1 (ja) * 2008-03-03 2009-09-11 日本電気株式会社 アドレス検索方法およびパケット処理装置
JP2009296131A (ja) * 2008-06-03 2009-12-17 Nec Corp Ｉｐパケット制御装置におけるソフトウェア検索方法
JP2010233083A (ja) * 2009-03-27 2010-10-14 Toshiba Corp ネットワークアドレス管理装置およびネットワークアドレス管理方法並びにネットワーク中継装置
JP2010278551A (ja) * 2009-05-26 2010-12-09 Fujitsu Ltd ネットワークスイッチ装置及びその方法
US7900052B2 (en) 2002-11-06 2011-03-01 International Business Machines Corporation Confidential data sharing and anonymous entity resolution
US8204831B2 (en) 2006-11-13 2012-06-19 International Business Machines Corporation Post-anonymous fuzzy comparisons without the use of pre-anonymization variants
JP2013242539A (ja) * 2012-05-20 2013-12-05 Internatl Business Mach Corp <Ibm> ハッシュ衝突低減システム、方法及びプログラム
JP2014082762A (ja) * 2012-10-15 2014-05-08 Samsung Electronics Co Ltd データ圧縮装置及び方法、データ圧縮装置を含むメモリシステム
US9413661B2 (en) 2013-03-28 2016-08-09 Hitachi Metals, Ltd. Network relay device
US9729445B2 (en) 2015-03-18 2017-08-08 Fujitsu Limited Communication device and communication control method
JP2019041176A (ja) * 2017-08-23 2019-03-14 株式会社ソフトクリエイト 不正接続遮断装置及び不正接続遮断方法

Families Citing this family (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3800198B2 (ja) * 2003-05-16 2006-07-26 ソニー株式会社 情報処理装置、およびアクセス制御処理方法、並びにコンピュータ・プログラム
US7565343B2 (en) * 2004-03-31 2009-07-21 Ipt Corporation Search apparatus and search management method for fixed-length data
US7624446B1 (en) * 2005-01-25 2009-11-24 Symantec Corporation Efficient signature packing for an intrusion detection system
TWI324471B (en) * 2006-06-01 2010-05-01 Via Tech Inc Mac address management method
CN101232444B (zh) * 2008-01-22 2012-03-21 杭州华三通信技术有限公司 哈希冲突解决方法、装置及具有该装置的交换设备
JP4995125B2 (ja) * 2008-03-12 2012-08-08 株式会社アイピーティ 固定長データの検索方法
US8667187B2 (en) * 2008-09-15 2014-03-04 Vmware, Inc. System and method for reducing communication overhead between network interface controllers and virtual machines
US8908564B2 (en) * 2010-06-28 2014-12-09 Avaya Inc. Method for Media Access Control address learning and learning rate suppression
US8312066B2 (en) * 2010-11-30 2012-11-13 Telefonaktiebolaget L M Ericsson (Publ) Hash collision resolution with key compression in a MAC forwarding data structure
CN102724106B (zh) * 2011-03-30 2015-03-11 华为技术有限公司 媒体接入控制地址的学习方法、网络侧设备和系统
JP6036525B2 (ja) * 2013-04-30 2016-11-30 日立金属株式会社 ネットワーク中継装置
JP6252223B2 (ja) * 2014-02-14 2017-12-27 富士通株式会社 制御方法、受信装置、及び通信システム
JP6666686B2 (ja) 2015-08-18 2020-03-18 株式会社ポコアポコネットワークス メモリ機器

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5032987A (en) 1988-08-04 1991-07-16 Digital Equipment Corporation System with a plurality of hash tables each using different adaptive hashing functions
US5649109A (en) 1992-10-22 1997-07-15 Digital Equipment Corporation Apparatus and method for maintaining forwarding information in a bridge or router using multiple free queues having associated free space sizes
US5633858A (en) 1994-07-28 1997-05-27 Accton Technology Corporation Method and apparatus used in hashing algorithm for reducing conflict probability
IL116989A (en) 1996-01-31 1999-10-28 Galileo Technology Ltd Switching ethernet controller
US6034957A (en) * 1997-08-29 2000-03-07 Extreme Networks, Inc. Sliced comparison engine architecture and method for a LAN switch
KR100268221B1 (ko) * 1998-08-13 2000-10-16 윤종용 순회 여분 검사를 이용한 랜 스위치의 맥 주소 해슁 방법 및장치
JP2000209216A (ja) * 1999-01-12 2000-07-28 Shimada Phys & Chem Ind Co Ltd アドレス管理方法及び装置、記録媒体
US6775281B1 (en) 1999-09-30 2004-08-10 Mosaid Technologies, Inc. Method and apparatus for a four-way hash table
US6678678B2 (en) * 2000-03-09 2004-01-13 Braodcom Corporation Method and apparatus for high speed table search

Cited By (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7900052B2 (en) 2002-11-06 2011-03-01 International Business Machines Corporation Confidential data sharing and anonymous entity resolution
US7469243B2 (en) 2003-01-27 2008-12-23 International Business Machines Corporation Method and device for searching fixed length data
JP2005236997A (ja) * 2004-02-20 2005-09-02 Fujitsu Ltd 高速なルーティングテーブル学習およびルックアップ
US8352677B2 (en) 2006-03-31 2013-01-08 Kyushu Institute Of Technology Associative memory
WO2007119540A1 (ja) * 2006-03-31 2007-10-25 Kyushu Institute Of Technology 連想メモリ
JP4934825B2 (ja) * 2006-03-31 2012-05-23 国立大学法人九州工業大学 連想メモリ
US8204831B2 (en) 2006-11-13 2012-06-19 International Business Machines Corporation Post-anonymous fuzzy comparisons without the use of pre-anonymization variants
JP2009194773A (ja) * 2008-02-15 2009-08-27 Nec Access Technica Ltd 優先制御システム、優先制御装置、優先制御方法、及び優先制御プログラム
US8526436B2 (en) 2008-03-03 2013-09-03 Nec Corporation Address search method and packet processing device
JP5035410B2 (ja) * 2008-03-03 2012-09-26 日本電気株式会社 アドレス検索方法およびパケット処理装置
WO2009110445A1 (ja) * 2008-03-03 2009-09-11 日本電気株式会社 アドレス検索方法およびパケット処理装置
JP2009296131A (ja) * 2008-06-03 2009-12-17 Nec Corp Ｉｐパケット制御装置におけるソフトウェア検索方法
JP2010233083A (ja) * 2009-03-27 2010-10-14 Toshiba Corp ネットワークアドレス管理装置およびネットワークアドレス管理方法並びにネットワーク中継装置
JP2010278551A (ja) * 2009-05-26 2010-12-09 Fujitsu Ltd ネットワークスイッチ装置及びその方法
JP2013242539A (ja) * 2012-05-20 2013-12-05 Internatl Business Mach Corp <Ibm> ハッシュ衝突低減システム、方法及びプログラム
JP2014082762A (ja) * 2012-10-15 2014-05-08 Samsung Electronics Co Ltd データ圧縮装置及び方法、データ圧縮装置を含むメモリシステム
US9413661B2 (en) 2013-03-28 2016-08-09 Hitachi Metals, Ltd. Network relay device
US9729445B2 (en) 2015-03-18 2017-08-08 Fujitsu Limited Communication device and communication control method
JP2019041176A (ja) * 2017-08-23 2019-03-14 株式会社ソフトクリエイト 不正接続遮断装置及び不正接続遮断方法

Also Published As

Publication number Publication date
TW581965B (en) 2004-04-01
US6910118B2 (en) 2005-06-21
EP1256885A2 (en) 2002-11-13
EP1256885A3 (en) 2004-05-12
KR20020086200A (ko) 2002-11-18
US20020169937A1 (en) 2002-11-14

Similar Documents

Publication Publication Date Title
JP2002334114A (ja) テーブル管理方法及び装置
Dai et al. Bloom filter with noisy coding framework for multi-set membership testing
US10110492B2 (en) Exact match lookup with variable key sizes
US7953077B2 (en) Network processor with single interface supporting tree search engine and CAM
EP2314027B1 (en) Switching table in an ethernet bridge
US20130031077A1 (en) Longest Prefix Match Scheme
US20020138648A1 (en) Hash compensation architecture and method for network address lookup
WO2010135082A1 (en) Localized weak bit assignment
JP4995125B2 (ja) 固定長データの検索方法
JPH0749812A (ja) ページテーブル中のハッシュアドレスタグを用いたメモリアドレス制御装置
US7600094B1 (en) Linked list traversal with reduced memory accesses
US20090282167A1 (en) Method and apparatus for bridging
CN113519144A (zh) 用于网络设备的精确匹配和三元内容可寻址存储器(tcam)混合查找
US11683039B1 (en) TCAM-based not logic
US6337862B1 (en) Network switch with truncated trie look-up facility
CN111541617B (zh) 一种用于高速大规模并发数据流的数据流表处理方法及装置
KR20000013760A (ko) 순회 여분 검사를 이용한 랜 스위치의 맥 주소 해슁 방법 및장치
CA2064957A1 (en) Method and apparatus for performing pattern search functions
EP0381245A2 (en) Address translation system
CN116415036B (zh) 一种数据存储方法、装置、存储介质及服务器
JP2004187114A (ja) アドレスフィルタリング装置
JP2002374289A (ja) 検索システム及びそれに用いる検索条件ｃａｍ登録方法並びにそのプログラム
JP3784054B2 (ja) Ｍａｃアドレスを並べ替えさせる方法および記録媒体
JPWO2005013566A1 (ja) データ検索方法及び装置
CN118250218A (zh) 规则表的维护方法、装置、电子设备及存储介质

Legal Events

Date Code Title Description
A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20060606

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20061128