[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN106416152A - 一种查找装置、查找配置方法和查找方法 - Google Patents

一种查找装置、查找配置方法和查找方法 Download PDF

Info

Publication number
CN106416152A
CN106416152A CN201480079291.6A CN201480079291A CN106416152A CN 106416152 A CN106416152 A CN 106416152A CN 201480079291 A CN201480079291 A CN 201480079291A CN 106416152 A CN106416152 A CN 106416152A
Authority
CN
China
Prior art keywords
prefix
node
prefix node
searching unit
searching
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.)
Granted
Application number
CN201480079291.6A
Other languages
English (en)
Other versions
CN106416152B (zh
Inventor
张文勇
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.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
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 Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Publication of CN106416152A publication Critical patent/CN106416152A/zh
Application granted granted Critical
Publication of CN106416152B publication Critical patent/CN106416152B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

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
    • H04L45/48—Routing tree calculation
    • 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]
    • 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/748—Address table lookup; Address filtering using longest matching prefix

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一种查找装置、查找配置方法和查找方法，所述查找装置包括N个流水线级，每个流水线级包括一个查找单元，每级查找单元中配置前缀节点，第N‑1级查找单元配置的前缀节点是通过对查找表构成的多位Trie树进行子树划分得到的，第N‑2级查找单元中配置的前缀节点是通过对第N‑1级查找单元中配置的前缀节点的关联前缀构成的多位Trie树进行子树划分得到的，通过多次迭代进行前缀节点配置。采用本发明提供的查找装置，可以减少内存资源的占用和流水线级数，进而减少查找延迟并降低实现难度。

Description

PCT国内申请，说明书已公开。

Claims (1)

  1. PCT国内申请，权利要求书已公开。
CN201480079291.6A 2014-06-10 2014-06-10 一种查找装置、查找配置方法和查找方法 Active CN106416152B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/CN2014/079624 WO2015188319A1 (zh) 2014-06-10 2014-06-10 一种查找装置、查找配置方法和查找方法

Publications (2)

Publication Number Publication Date
CN106416152A true CN106416152A (zh) 2017-02-15
CN106416152B CN106416152B (zh) 2019-09-27

Family

ID=54832699

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201480079291.6A Active CN106416152B (zh) 2014-06-10 2014-06-10 一种查找装置、查找配置方法和查找方法

Country Status (4)

Country Link
US (1) US10164884B2 (zh)
EP (1) EP3145134B1 (zh)
CN (1) CN106416152B (zh)
WO (1) WO2015188319A1 (zh)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115086221A (zh) * 2022-07-27 2022-09-20 新华三半导体技术有限公司 一种报文处理方法、装置、转发设备和存储介质

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10924381B2 (en) 2015-02-19 2021-02-16 Arista Networks, Inc. System and method of processing in-place adjacency updates
US10516613B1 (en) 2015-10-14 2019-12-24 Innovium, Inc. Network device storage of incremental prefix trees
US10230639B1 (en) * 2017-08-08 2019-03-12 Innovium, Inc. Enhanced prefix matching
CN108153907B (zh) * 2018-01-18 2021-01-22 中国计量大学 通过16位Trie树实现空间优化的词典存储管理方法
US11140078B1 (en) 2018-10-18 2021-10-05 Innovium, Inc. Multi-stage prefix matching enhancements
US20210021517A1 (en) * 2019-07-19 2021-01-21 Arista Networks, Inc. Avoiding recirculation of data packets in a network device
CN112804153A (zh) * 2020-12-30 2021-05-14 中国科学院计算机网络信息中心 一种面向gpu加速ip查找的更新方法及系统
US12003418B2 (en) 2021-06-25 2024-06-04 New H3C Technologies Co., Ltd. Method and apparatus for packet matching, network device, and medium

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1063827A2 (en) * 1999-05-11 2000-12-27 Nec Corporation Method for address lookup
US20040100960A1 (en) * 2002-11-22 2004-05-27 Mehta Ashish K. Method and apparatus for performing an address lookup using a multi-bit trie with backtracking
EP1434148A3 (en) * 2002-12-06 2008-01-09 STMicroelectronics, Inc. Apparatus and method of implementing a multi-bit trie algorithmic network search engine
US20140003436A1 (en) * 2012-06-27 2014-01-02 Futurewei Technologies, Inc. Internet Protocol and Ethernet Lookup Via a Unified Hashed Trie

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7899067B2 (en) 2002-05-31 2011-03-01 Cisco Technology, Inc. Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match
US7299227B2 (en) * 2003-09-09 2007-11-20 Stmicroelectronics, Inc. Method and system for providing cascaded trie-based network packet search engines
CN101572647B (zh) * 2008-04-30 2012-07-04 华为技术有限公司 一种数据查找的方法及装置
CN102484610B (zh) * 2010-04-12 2015-01-21 华为技术有限公司 路由表建立方法和装置及路由表查找方法和装置
CN102307149B (zh) * 2011-09-23 2014-05-07 中国科学院计算技术研究所 Ip查找方法和装置以及路由更新方法和装置
US8923298B2 (en) * 2012-05-04 2014-12-30 Futurewei Technoligies, Inc. Optimized trie-based address lookup
CN102739550B (zh) * 2012-07-17 2015-11-25 中山大学 基于随机副本分配的多存储器流水路由体系结构

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1063827A2 (en) * 1999-05-11 2000-12-27 Nec Corporation Method for address lookup
US20040100960A1 (en) * 2002-11-22 2004-05-27 Mehta Ashish K. Method and apparatus for performing an address lookup using a multi-bit trie with backtracking
EP1434148A3 (en) * 2002-12-06 2008-01-09 STMicroelectronics, Inc. Apparatus and method of implementing a multi-bit trie algorithmic network search engine
US20140003436A1 (en) * 2012-06-27 2014-01-02 Futurewei Technologies, Inc. Internet Protocol and Ethernet Lookup Via a Unified Hashed Trie

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115086221A (zh) * 2022-07-27 2022-09-20 新华三半导体技术有限公司 一种报文处理方法、装置、转发设备和存储介质
CN115086221B (zh) * 2022-07-27 2022-11-22 新华三半导体技术有限公司 一种报文处理方法、装置、转发设备和存储介质

Also Published As

Publication number Publication date
US10164884B2 (en) 2018-12-25
EP3145134A1 (en) 2017-03-22
WO2015188319A1 (zh) 2015-12-17
EP3145134B1 (en) 2019-12-18
EP3145134A4 (en) 2017-06-28
US20170142013A1 (en) 2017-05-18
CN106416152B (zh) 2019-09-27

Similar Documents

Publication Publication Date Title
CN106416152A (zh) 一种查找装置、查找配置方法和查找方法
CN102484610B (zh) 路由表建立方法和装置及路由表查找方法和装置
KR100745693B1 (ko) Ｔｃａｍ 테이블 관리 방법
US6728732B1 (en) Data structure using a tree bitmap and method for rapid classification of data in a database
US7356033B2 (en) Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
US6434144B1 (en) Multi-level table lookup
US8780926B2 (en) Updating prefix-compressed tries for IP route lookup
US20020191605A1 (en) Packet classification
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
CN105141525B (zh) IPv6路由查找方法及装置
CN105512229B (zh) 一种ip地址的地域信息的存储、查询方法及装置
JP3881663B2 (ja) フィールドレベルツリーを用いたパケット分類装置及び方法
CN106302172A (zh) 同时支持哈希查找和路由查找的存储、查找方法和装置
Le et al. Memory-efficient and scalable virtual routers using FPGA
EP3280104B1 (en) Ip routing lookup
Le et al. Scalable high throughput and power efficient ip-lookup on fpga
Pao et al. IP address lookup using bit-shuffled trie
CN105227468B (zh) 一种查找装置、查找方法和配置方法
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
CN102904812B (zh) 路由表项的存储方法、查找方法、装置及系统
CN110995876B (zh) 一种ip存储与查找的方法及装置
CN104090942A (zh) 应用于网络处理器中的Trie搜索方法及装置
CN102739550B (zh) 基于随机副本分配的多存储器流水路由体系结构
Erdem Pipelined hierarchical architecture for high performance packet classification
CN106330721B (zh) Ip路由查找方法及装置

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant