ATE304276T1 - Speicher zur informationssuche durch präfixanalyse für knoten von hochgeschwindigkeitsnetzwerken - Google Patents

Speicher zur informationssuche durch präfixanalyse für knoten von hochgeschwindigkeitsnetzwerken

Info

Publication number
ATE304276T1
ATE304276T1 AT99121337T AT99121337T ATE304276T1 AT E304276 T1 ATE304276 T1 AT E304276T1 AT 99121337 T AT99121337 T AT 99121337T AT 99121337 T AT99121337 T AT 99121337T AT E304276 T1 ATE304276 T1 AT E304276T1
Authority
AT
Austria
Prior art keywords
information
target
memory
next row
nodes
Prior art date
Application number
AT99121337T
Other languages
English (en)
Inventor
Enrica Filippi
Viviana Innocenti
Original Assignee
Telecom Italia Spa
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 Telecom Italia Spa filed Critical Telecom Italia Spa
Application granted granted Critical
Publication of ATE304276T1 publication Critical patent/ATE304276T1/de

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/104—Asynchronous transfer mode [ATM] switching fabrics
    • H04L49/105—ATM switching elements
    • 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
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3081—ATM peripheral units, e.g. policing, insertion or extraction
    • H04L49/309—Header conversion, routing tables or routing tags
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y10S707/99936—Pattern matching access

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Instructional Devices (AREA)
  • Computer And Data Communications (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
AT99121337T 1998-10-27 1999-10-26 Speicher zur informationssuche durch präfixanalyse für knoten von hochgeschwindigkeitsnetzwerken ATE304276T1 (de)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
IT1998TO000909A IT1305140B1 (it) 1998-10-27 1998-10-27 Memoria per la ricerca di informazioni mediante analisi di prefissi inparticolare per la realizzazione di tabelle di instradamento in nodi

Publications (1)

Publication Number Publication Date
ATE304276T1 true ATE304276T1 (de) 2005-09-15

Family

ID=11417138

Family Applications (1)

Application Number Title Priority Date Filing Date
AT99121337T ATE304276T1 (de) 1998-10-27 1999-10-26 Speicher zur informationssuche durch präfixanalyse für knoten von hochgeschwindigkeitsnetzwerken

Country Status (7)

Country Link
US (1) US6571313B1 (de)
EP (1) EP0998162B1 (de)
JP (1) JP3299528B2 (de)
AT (1) ATE304276T1 (de)
CA (1) CA2287041C (de)
DE (1) DE69927109T2 (de)
IT (1) IT1305140B1 (de)

Families Citing this family (38)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1174587C (zh) * 1999-12-10 2004-11-03 睦塞德技术公司 最长匹配地址查询的方法和装置
US6947931B1 (en) * 2000-04-06 2005-09-20 International Business Machines Corporation Longest prefix match (LPM) algorithm implementation for a network processor
US6880064B1 (en) 2000-06-21 2005-04-12 Mosaid Technologies, Inc. Method and apparatus for physical width expansion of a longest prefix match lookup table
JP2002026973A (ja) * 2000-07-12 2002-01-25 Nec Corp 経路検索システム及びその方法並びにそれに使用するルータ装置
KR100686732B1 (ko) * 2000-08-26 2007-02-23 삼성전자주식회사 복수의 프리픽스로부터 데이터 패킷을 라우팅하기 위한데이터베이스 생성방법과 라우팅 방법 및 그 방법을이용한 라우터
US20020089937A1 (en) 2000-11-16 2002-07-11 Srinivasan Venkatachary Packet matching method and system
US6888838B1 (en) * 2000-11-16 2005-05-03 Tensilica, Inc. Fast IP route lookup with configurable processor and compressed routing table
US7274697B2 (en) * 2000-11-16 2007-09-25 Tensilica, Inc. Fast IP route lookup with 16/K and 16/Kc compressed data structures
RU2233473C2 (ru) * 2000-12-22 2004-07-27 Самсунг Электроникс Ко., Лтд. Устройство и способ выполнения высокоскоростного поиска маршрутов протокола интернет и управления таблицами маршрутизации/пересылки
KR100493099B1 (ko) * 2000-12-22 2005-06-02 삼성전자주식회사 고속 인터넷프로토콜 라우터의 라우팅/포워딩 룩업 및라우팅 테이블 관리
US7031320B2 (en) * 2000-12-22 2006-04-18 Samsung Electronics Co., Ltd. Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables
US7227842B1 (en) 2001-04-24 2007-06-05 Tensilica, Inc. Fast IP packet classification with configurable processor
US7230912B1 (en) * 2001-06-14 2007-06-12 Juniper Networks, Inc. Sampling to a next hop
US6985483B2 (en) * 2001-07-31 2006-01-10 North Carolina State University Methods and systems for fast packet forwarding
US20030031179A1 (en) * 2001-08-08 2003-02-13 Jintae Oh Self-updateable longest prefix matching method and apparatus
US7007101B1 (en) 2001-11-09 2006-02-28 Radisys Microware Communications Software Division, Inc. Routing and forwarding table management for network processor architectures
US7180887B1 (en) 2002-01-04 2007-02-20 Radisys Patent Properties Routing and forwarding table management for network processor architectures
US20030174717A1 (en) * 2002-03-15 2003-09-18 Boris Zabarski System and method for longest prefix match for internet protocol lookup
US6925464B2 (en) * 2002-06-13 2005-08-02 Intel Corporation Method and system for performing inserts and lookups in memory
US7162481B2 (en) * 2002-12-06 2007-01-09 Stmicroelectronics, Inc. Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes
KR100918733B1 (ko) * 2003-01-30 2009-09-24 삼성전자주식회사 포워딩정보를 동적으로 관리하는 분산구조라우터 및 그방법
US7426518B2 (en) * 2003-03-28 2008-09-16 Netlogic Microsystems, Inc. System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size
US7571156B1 (en) * 2003-03-28 2009-08-04 Netlogic Microsystems, Inc. Network device, storage medium and methods for incrementally updating a forwarding database
CN100452732C (zh) * 2003-08-19 2009-01-14 华为技术有限公司 路由查找方法及其系统
US7702882B2 (en) * 2003-09-10 2010-04-20 Samsung Electronics Co., Ltd. Apparatus and method for performing high-speed lookups in a routing table
US8024176B2 (en) * 2003-09-30 2011-09-20 Dictaphone Corporation System, method and apparatus for prediction using minimal affix patterns
US7694068B1 (en) 2005-12-08 2010-04-06 Netlogic Microsystems, Inc. Re-entrant processing in a content addressable memory
US7904642B1 (en) 2007-02-08 2011-03-08 Netlogic Microsystems, Inc. Method for combining and storing access control lists
US8862685B2 (en) * 2008-11-21 2014-10-14 Continental Teves Ag & Co. Ohg Data transmission protocol for synchronization communication between two communication devices
US8438330B2 (en) 2010-05-17 2013-05-07 Netlogic Microsystems, Inc. Updating cam arrays using prefix length distribution prediction
DE102011009518B4 (de) * 2011-01-26 2013-09-12 Ruprecht-Karls-Universität Heidelberg Schaltungsanordnung für Verbindungsschnittstelle
CN103973571A (zh) * 2013-02-05 2014-08-06 中兴通讯股份有限公司 网络处理器及其路由查找方法
CN103458479A (zh) * 2013-09-17 2013-12-18 清华大学 Wsn中基于内容的路由表的数据路由方法及系统
US10496631B2 (en) 2017-03-10 2019-12-03 Symphony Communication Services Holdings Llc Secure information retrieval and update
US10776185B2 (en) 2018-12-10 2020-09-15 International Business Machines Corporation Messaging software management for network devices supporting hardware tag matching
US11126374B2 (en) * 2019-03-28 2021-09-21 Intel Corporation Technologies for efficient stochastic associative search operations
CN115665033A (zh) * 2021-07-07 2023-01-31 中兴通讯股份有限公司 跨设备链路聚合报文处理方法、系统、交换机及存储介质
CN117056443B (zh) * 2023-07-20 2026-05-29 福建大数据一级开发有限公司 一种地址标准化的方法及装置

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU620994B2 (en) * 1989-07-12 1992-02-27 Digital Equipment Corporation Compressed prefix matching database searching
US5787430A (en) * 1994-06-30 1998-07-28 International Business Machines Corporation Variable length data sequence backtracking a trie structure
US6052683A (en) * 1998-02-24 2000-04-18 Nortel Networks Corporation Address lookup in packet data communication networks
US6396842B1 (en) * 1998-04-30 2002-05-28 3Com Corporation Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability
US6430527B1 (en) * 1998-05-06 2002-08-06 Avici Systems Prefix search circuitry and method
US6434115B1 (en) * 1998-07-02 2002-08-13 Pluris, Inc. System and method for switching packets in a network
US6237061B1 (en) * 1999-01-05 2001-05-22 Netlogic Microsystems, Inc. Method for longest prefix matching in a content addressable memory

Also Published As

Publication number Publication date
US6571313B1 (en) 2003-05-27
JP3299528B2 (ja) 2002-07-08
EP0998162A2 (de) 2000-05-03
DE69927109T2 (de) 2006-06-29
EP0998162A3 (de) 2004-06-23
IT1305140B1 (it) 2001-04-10
DE69927109D1 (de) 2005-10-13
ITTO980909A1 (it) 2000-04-27
CA2287041A1 (en) 2000-04-27
CA2287041C (en) 2003-12-30
JP2000151691A (ja) 2000-05-30
EP0998162B1 (de) 2005-09-07

Similar Documents

Publication Publication Date Title
DE69927109D1 (de) Speicher zur Informationssuche durch Präfixanalyse für Knoten von Hochgeschwindigkeitsnetzwerken
JP3735471B2 (ja) パケット中継装置およびｌｓｉ
US7418505B2 (en) IP address lookup using either a hashing table or multiple hash functions
US6728732B1 (en) Data structure using a tree bitmap and method for rapid classification of data in a database
Zane et al. CoolCAMs: Power-efficient TCAMs for forwarding engines
US7111071B1 (en) Longest prefix match for IP routers
US20020129086A1 (en) Cluster-based aggregated switching technique (CAST) for routing data packets and information objects in computer networks
US20040254909A1 (en) Programming routes and access control lists in comparison tree data structures and their use such as in performing lookup operations
US7249149B1 (en) Tree bitmap data structures and their use in performing lookup operations
US20050083937A1 (en) IP address lookup method using pipeline binary tree, hardware architecture, and recording medium
EP1002402A4 (de) Verbindingsunterstützung in einer hochleistungsnetzwerkvorrichtung
KR100512949B1 (ko) 필드레벨 트리를 이용한 패킷분류장치 및 방법
CN112667640A (zh) 一种路由地址存储方法及装置
US6941417B1 (en) High-speed low-power CAM-based search engine
JP3691018B2 (ja) 最長一致検索回路および方法およびプログラムおよび記録媒体
SE9703293D0 (sv) A lookup device and a method for classification and forwarding of packets in packet-switched networks
SE511972C2 (sv) Uppslagningsanordning och förfarande för att klassificera och vidarebefordra datapaket
ATE272920T1 (de) Verfahren und anordnung zur verkehrsweglenkung von nachrichtenpaketen mit durch numerische ketten repräsentierten adressen
KR100662254B1 (ko) 라우팅 시스템에서의 패킷 분류 장치 및 이를 위한 룰 구축 방법
US6549536B1 (en) Method of address compression for cell-based and packet-based protocols and hardware implementations thereof
RU2002122720A (ru) Устройство и способ выполнения высокоскоростного поиска маршрутов протокола интернет и управления таблицами маршрутизации/пересылки
US6967959B2 (en) Method for forming a database to route a data packet and method for routing and a router using the method thereof
Smiljanić et al. A comparative review of scalable lookup algorithms for IPv6
CN109194574B (zh) 一种IPv6路由查找方法
JP3795881B2 (ja) テーブル検索方法および装置

Legal Events

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