ATE439719T1 - Verfahren zur trie-erzeugung mit einer reduzierten trie-blockzahl - Google Patents

Verfahren zur trie-erzeugung mit einer reduzierten trie-blockzahl

Info

Publication number
ATE439719T1
ATE439719T1 AT04756462T AT04756462T ATE439719T1 AT E439719 T1 ATE439719 T1 AT E439719T1 AT 04756462 T AT04756462 T AT 04756462T AT 04756462 T AT04756462 T AT 04756462T AT E439719 T1 ATE439719 T1 AT E439719T1
Authority
AT
Austria
Prior art keywords
trie
entry
blocks
pruned
generating
Prior art date
Application number
AT04756462T
Other languages
English (en)
Inventor
Makaram Raghunandan
Original Assignee
Intel Corp
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 Intel Corp filed Critical Intel Corp
Application granted granted Critical
Publication of ATE439719T1 publication Critical patent/ATE439719T1/de

Links

Classifications

    • 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
    • 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
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/74591—Address table lookup; Address filtering using content-addressable memories [CAM]

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Cylinder Crankcases Of Internal Combustion Engines (AREA)
  • Stored Programmes (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
AT04756462T 2003-06-30 2004-06-29 Verfahren zur trie-erzeugung mit einer reduzierten trie-blockzahl ATE439719T1 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US10/611,818 US20040264479A1 (en) 2003-06-30 2003-06-30 Method for generating a trie having a reduced number of trie blocks
PCT/US2004/021085 WO2005006681A1 (en) 2003-06-30 2004-06-29 Method for generating a trie having a reduced number of trie blocks

Publications (1)

Publication Number Publication Date
ATE439719T1 true ATE439719T1 (de) 2009-08-15

Family

ID=33541386

Family Applications (1)

Application Number Title Priority Date Filing Date
AT04756462T ATE439719T1 (de) 2003-06-30 2004-06-29 Verfahren zur trie-erzeugung mit einer reduzierten trie-blockzahl

Country Status (7)

Country Link
US (1) US20040264479A1 (de)
EP (1) EP1642428B1 (de)
CN (1) CN1312890C (de)
AT (1) ATE439719T1 (de)
DE (1) DE602004022552D1 (de)
TW (1) TW200508912A (de)
WO (1) WO2005006681A1 (de)

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7564841B2 (en) * 2004-03-05 2009-07-21 Samsung Electronics Co., Ltd. Apparatus and method for performing forwarding table searches using consecutive symbols tables
US7515588B2 (en) * 2004-03-18 2009-04-07 Intel Corporation Method and apparatus to support a large internet protocol forwarding information base
US7376657B1 (en) * 2004-04-30 2008-05-20 Sun Microsystems, Inc. Fast IPv6 address lookup using skip level processing on multi-bit tries
US8380488B1 (en) 2006-04-19 2013-02-19 Google Inc. Identifying a property of a document
US8442965B2 (en) * 2006-04-19 2013-05-14 Google Inc. Query language identification
US8762358B2 (en) * 2006-04-19 2014-06-24 Google Inc. Query language determination using query terms and interface language
US8255376B2 (en) * 2006-04-19 2012-08-28 Google Inc. Augmenting queries with synonyms from synonyms map
US7720854B2 (en) * 2006-08-25 2010-05-18 Intel Corporation Techniques for accessing a table
EP3627343A1 (de) * 2018-09-19 2020-03-25 censhare AG Effiziente speicherinterne multiversion-gleichzeitigkeitssteuerung für eine datenbank auf basis von trie-datenstruktur
JP2023086507A (ja) * 2021-12-10 2023-06-22 キオクシア株式会社 情報処理装置および方法

Family Cites Families (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5666516A (en) * 1993-12-16 1997-09-09 International Business Machines Corporation Protected programmable memory cartridge having selective access circuitry
US5787430A (en) * 1994-06-30 1998-07-28 International Business Machines Corporation Variable length data sequence backtracking a trie structure
US6172990B1 (en) * 1997-06-19 2001-01-09 Xaqti Corporation Media access control micro-RISC stream processor and method for implementing the same
US5953335A (en) * 1997-02-14 1999-09-14 Advanced Micro Devices, Inc. Method and apparatus for selectively discarding packets for blocked output queues in the network switch
JPH11261649A (ja) * 1998-03-12 1999-09-24 Hitachi Ltd データ処理装置及びそれを適用したルータ・ブリッジ
US6430184B1 (en) * 1998-04-10 2002-08-06 Top Layer Networks, Inc. System and process for GHIH-speed pattern matching for application-level switching of data packets
US6167047A (en) * 1998-05-18 2000-12-26 Solidum Systems Corp. Packet classification state machine
US6347087B1 (en) * 1998-10-05 2002-02-12 Packet Engines Incorporated Content-based forwarding/filtering in a network switching device
US6304878B1 (en) * 1998-11-23 2001-10-16 Microsoft Corporation Method and system for improved enumeration of tries
TW468116B (en) * 1999-02-08 2001-12-11 Wen-Shian Chen High speed Internet protocol address lookups method for saving memory
GB9912129D0 (en) * 1999-05-26 1999-07-28 3Com Corp Communication device with forwarding database having having a trie search facility
FI991261L (fi) * 1999-06-02 2000-12-03 Nokia Networks Oy Trie-rakenteeseen perustuva funktionaalinen muisti
US6789116B1 (en) * 1999-06-30 2004-09-07 Hi/Fn, Inc. State processor for pattern matching in a network monitor device
US6560610B1 (en) * 1999-08-10 2003-05-06 Washington University Data structure using a tree bitmap and method for rapid classification of data in a database
US6700897B1 (en) * 1999-10-29 2004-03-02 Advanced Micro Devices, Inc. Apparatus and method for identifying data packet types in real time on a network switch port
US6570884B1 (en) * 1999-11-05 2003-05-27 3Com Corporation Receive filtering for communication interface
GB2359693B (en) * 2000-02-26 2003-07-16 3Com Corp Network switch with truncated trie look-up facility
US6741594B1 (en) * 2000-06-15 2004-05-25 Advanced Micro Devices, Inc. Arrangement for identifying data packet types from multiple protocol formats on a network switch port
US6693906B1 (en) * 2000-07-17 2004-02-17 Advanced Micro Devices, Inc. Apparatus and method for buffer-free evaluation of packet data bytes with multiple min terms
US6963565B1 (en) * 2000-08-14 2005-11-08 Advanced Micro Devices, Inc. Apparatus and method for identifying data packet at wire rate on a network switch port
US6735595B2 (en) * 2000-11-29 2004-05-11 Hewlett-Packard Development Company, L.P. Data structure and storage and retrieval method supporting ordinality based searching and data retrieval
US6671694B2 (en) * 2001-06-04 2003-12-30 Hewlett-Packard Development Company, L.P. System for and method of cache-efficient digital tree with rich pointers
EP1485827A2 (de) * 2002-02-14 2004-12-15 Transwitch Corporation Effizientes ipv4/ipv6-best-matching prefix-verfahren und vorrichtung
US6928430B1 (en) * 2002-04-23 2005-08-09 Integrated Silicon Solution, Inc. Prefix match search scheme

Also Published As

Publication number Publication date
CN1312890C (zh) 2007-04-25
US20040264479A1 (en) 2004-12-30
WO2005006681A1 (en) 2005-01-20
EP1642428B1 (de) 2009-08-12
CN1578257A (zh) 2005-02-09
DE602004022552D1 (de) 2009-09-24
EP1642428A1 (de) 2006-04-05
TW200508912A (en) 2005-03-01

Similar Documents

Publication Publication Date Title
DE60322537D1 (de) Verfahren zur herstellung von kohlenstoffnanoröhren
ATE341529T1 (de) Verfahren zur herstellung von ultrahochreinem isopropanol
DE60312970D1 (de) Verfahren zur herstellung von gefärbten artikeln
DE60137136D1 (de) Verfahten zur herstellung von butyl-kautschuk mit verbesserter verarbeitbarkeit
ATE439719T1 (de) Verfahren zur trie-erzeugung mit einer reduzierten trie-blockzahl
DE60203721D1 (de) Verfahren zur herstellung einer versetzten wellenförmigen rippe
AT7110U9 (de) Verfahren zur herstellung von amlodipinmaleat
DE60220792D1 (de) Verfahren zur herstellung von dieselbrennstoff aus bitumen
ATE337270T1 (de) Verfahren zur herstellung von eisenoxiden
DE502005010519D1 (de) Verfahren zur herstellung hochtexturierter, bandförmiger hochtemperatur-supraleiter
BR0205346B1 (pt) método de condução de gás com injeção de tensoativo.
DE60125906D1 (de) Verfahren zur Verbesserung von Leistung
DE60126336D1 (de) Verfahren zur herstellung von hochreinen durchscheinenden perfluorelastomer-gegenständen
ATE432918T1 (de) Verfahren zur herstellung von cpla 2-inhibitoren
ATE553103T1 (de) Verfahren zur herstellung von (s)-pantoprazol
DE50102444D1 (de) Verfahren zur herstellung von isocyanatoorganosilanen
ATE328010T1 (de) Verfahren zur herstellung von polyisobuten
DE60211031D1 (de) Verfahren zur herstellung von hydraulischem zementklinker mit hohem eisengehalt
ATE478063T1 (de) Verfahren zur herstellung von alkylencarbonat
ATE349442T1 (de) Verbessertes verfahren zur herstellung von alpha- polymorphem eletriptan hydrobromid
ATE402138T1 (de) Verfahren zur herstellung von 2- aminoindanderivaten
DE60230422D1 (de) Verfahren zur herstellung von kohlenwasserstoffen
ATE301626T1 (de) Verfahren zur disproportionierung von isopentan
DE60105991D1 (de) Verfahren zur herstellung von 6-aminocapronamid
ATE352573T1 (de) Verfahren zur herstellung von copolymerisaten

Legal Events

Date Code Title Description
RER Ceased as to paragraph 5 lit. 3 law introducing patent treaties