TR201209797T2 - Hızlı IP arama için sistolik dizilim mimarisi. - Google Patents

Hızlı IP arama için sistolik dizilim mimarisi.

Info

Publication number
TR201209797T2
TR201209797T2 TR2012/09797T TR201209797T TR201209797T2 TR 201209797 T2 TR201209797 T2 TR 201209797T2 TR 2012/09797 T TR2012/09797 T TR 2012/09797T TR 201209797 T TR201209797 T TR 201209797T TR 201209797 T2 TR201209797 T2 TR 201209797T2
Authority
TR
Turkey
Prior art keywords
architecture
tree
systolic array
search
sram
Prior art date
Application number
TR2012/09797T
Other languages
English (en)
Inventor
Erdem O�Uzhan
Fehm� Bazlama�Ci C�Neyt
Original Assignee
Fehm� Bazlama�Ci C�Neyt
Erdem O�Uzhan
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 Fehm� Bazlama�Ci C�Neyt, Erdem O�Uzhan filed Critical Fehm� Bazlama�Ci C�Neyt
Publication of TR201209797T2 publication Critical patent/TR201209797T2/tr

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
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/66—Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
    • 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]
    • 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/3009—Header conversion, routing tables or routing tags
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/60—Software-defined switches
    • H04L49/602—Multilayer or multiprotocol switching, e.g. IP switching

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

Bu buluş, ilk olarak çoklu boru hatlarının paralelleştirilmesi fikrini kullanan bir SRAM tabanlı sistolik dizilim mimarisi içeren SRAM tabanlı internet protokolü (IP) arama mimarisini sunar ve temel mimarinin ayrıntılarına inerek avantajlarını vurgular. Bu temel mimaride, farklı uzunluklarda ve birbirini kesen çoklu boru hatları, işlem elemanlarından oluşan bir iki boyutlu dizi üzerine döngüsel biçimde inşa edilmiştir. Bu mimari geleneksel ikili ontakı ağacı yerine herhangi bir çeşit ontakı arama ağacının kullanımını destekler. Bu buluş, ikinci olarak önemli ölçüde performans artışı kazanmak için alternatif ve daha avantajlı iki terimli kapsayan ağaç tabanlı ontakı ağacının kullanımını önerir. Bu yeni yaklaşım, dört taraflı giriş ve üç işaretçili kullanım gibi iyileştirmeler ile temel mimarinin arama kapasitesini ve paralelliği arttırmakta ve 7 Tbps yönlendirici IP arama hızı ile tüm mevcut IP arama yaklaşımlarından daha yüksek çıkan iş oranı sağlamaktadır. Bu sistolik dizilim yapısında, arama gecikmesi en kötü durumda teorik olarak yüksek olmasına rağmen, ortalama gecikme oldukça düşüktür, büyük gecikmeler nadiren gözlenmektedir. Bu yapı, yeni formu ile işlem elemanları bakımından ölçeklenebilir ve IPv6 adresleme yapısı için uygundur.
TR2012/09797T 2009-12-22 2009-12-22 Hızlı IP arama için sistolik dizilim mimarisi. TR201209797T2 (tr)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/TR2009/000157 WO2011078812A1 (en) 2009-12-22 2009-12-22 Systolic array architecture for fast ip lookup

Publications (1)

Publication Number Publication Date
TR201209797T2 true TR201209797T2 (tr) 2013-01-21

Family

ID=42261933

Family Applications (1)

Application Number Title Priority Date Filing Date
TR2012/09797T TR201209797T2 (tr) 2009-12-22 2009-12-22 Hızlı IP arama için sistolik dizilim mimarisi.

Country Status (5)

Country Link
US (1) US8724624B2 (tr)
EP (1) EP2517420B1 (tr)
JP (1) JP5529976B2 (tr)
TR (1) TR201209797T2 (tr)
WO (1) WO2011078812A1 (tr)

Families Citing this family (63)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10721269B1 (en) 2009-11-06 2020-07-21 F5 Networks, Inc. Methods and system for returning requests with javascript for clients before passing a request to a server
US8599853B2 (en) * 2010-04-16 2013-12-03 Wipro Limited System and method for an exact match search using pointer based pipelined multibit trie traversal technique
US9420049B1 (en) 2010-06-30 2016-08-16 F5 Networks, Inc. Client side human user indicator
US9503375B1 (en) 2010-06-30 2016-11-22 F5 Networks, Inc. Methods for managing traffic in a multi-service environment and devices thereof
WO2012158854A1 (en) 2011-05-16 2012-11-22 F5 Networks, Inc. A method for load balancing of requests' processing of diameter servers
US9065860B2 (en) 2011-08-02 2015-06-23 Cavium, Inc. Method and apparatus for multiple access of plural memory banks
US8954492B1 (en) 2011-11-30 2015-02-10 F5 Networks, Inc. Methods for inlining content externally referenced in a web page prior to providing the web page to a requestor and devices thereof
US10230566B1 (en) 2012-02-17 2019-03-12 F5 Networks, Inc. Methods for dynamically constructing a service principal name and devices thereof
US9020912B1 (en) 2012-02-20 2015-04-28 F5 Networks, Inc. Methods for accessing data in a compressed file system and devices thereof
US9244843B1 (en) * 2012-02-20 2016-01-26 F5 Networks, Inc. Methods for improving flow cache bandwidth utilization and devices thereof
US20130246698A1 (en) * 2012-03-14 2013-09-19 Broadcom Corporation Hybrid Memory for Search Operations
WO2013163648A2 (en) 2012-04-27 2013-10-31 F5 Networks, Inc. Methods for optimizing service of content requests and devices thereof
JP5888134B2 (ja) * 2012-06-11 2016-03-16 富士通株式会社 通信制御装置、及び通信制御方法
US10033837B1 (en) 2012-09-29 2018-07-24 F5 Networks, Inc. System and method for utilizing a data reducing module for dictionary compression of encoded data
US9578090B1 (en) 2012-11-07 2017-02-21 F5 Networks, Inc. Methods for provisioning application delivery service and devices thereof
US10375155B1 (en) 2013-02-19 2019-08-06 F5 Networks, Inc. System and method for achieving hardware acceleration for asymmetric flow connections
US9531647B1 (en) 2013-03-15 2016-12-27 Cavium, Inc. Multi-host processing
US9276846B2 (en) 2013-03-15 2016-03-01 Cavium, Inc. Packet extraction optimization in a network processor
US9355279B1 (en) 2013-03-29 2016-05-31 Secturion Systems, Inc. Multi-tenancy architecture
US9798899B1 (en) * 2013-03-29 2017-10-24 Secturion Systems, Inc. Replaceable or removable physical interface input/output module
US9317718B1 (en) 2013-03-29 2016-04-19 Secturion Systems, Inc. Security device with programmable systolic-matrix cryptographic module and programmable input/output interface
US9374344B1 (en) 2013-03-29 2016-06-21 Secturion Systems, Inc. Secure end-to-end communication system
US9524399B1 (en) 2013-04-01 2016-12-20 Secturion Systems, Inc. Multi-level independent security architecture
US9348602B1 (en) 2013-09-03 2016-05-24 Amazon Technologies, Inc. Resource allocation for staged execution pipelining
US10187317B1 (en) 2013-11-15 2019-01-22 F5 Networks, Inc. Methods for traffic rate control and devices thereof
IN2014CH01654A (tr) * 2014-03-28 2015-10-09 Tejas Networks Ltd
US11838851B1 (en) 2014-07-15 2023-12-05 F5, Inc. Methods for managing L7 traffic classification and devices thereof
CN105701040B (zh) * 2014-11-28 2018-12-07 杭州华为数字技术有限公司 一种激活内存的方法及装置
US10182013B1 (en) 2014-12-01 2019-01-15 F5 Networks, Inc. Methods for managing progressive image delivery and devices thereof
US11895138B1 (en) 2015-02-02 2024-02-06 F5, Inc. Methods for improving web scanner accuracy and devices thereof
US10834065B1 (en) 2015-03-31 2020-11-10 F5 Networks, Inc. Methods for SSL protected NTLM re-authentication and devices thereof
US11350254B1 (en) 2015-05-05 2022-05-31 F5, Inc. Methods for enforcing compliance policies and devices thereof
US10505818B1 (en) 2015-05-05 2019-12-10 F5 Networks. Inc. Methods for analyzing and load balancing based on server health and devices thereof
EP3269100A4 (en) * 2015-07-17 2018-10-31 Hewlett-Packard Enterprise Development LP Combining prefix lengths into a hash table
US11283774B2 (en) 2015-09-17 2022-03-22 Secturion Systems, Inc. Cloud storage using encryption gateway with certificate authority identification
US10476798B1 (en) * 2015-09-22 2019-11-12 Amazon Technologies, Inc. Network switch with deterministic longest prefix match lookup
US10516613B1 (en) 2015-10-14 2019-12-24 Innovium, Inc. Network device storage of incremental prefix trees
US10708236B2 (en) * 2015-10-26 2020-07-07 Secturion Systems, Inc. Multi-independent level secure (MILS) storage encryption
US11757946B1 (en) 2015-12-22 2023-09-12 F5, Inc. Methods for analyzing network traffic and enforcing network policies and devices thereof
US10404698B1 (en) 2016-01-15 2019-09-03 F5 Networks, Inc. Methods for adaptive organization of web application access points in webtops and devices thereof
US12464021B1 (en) 2016-01-20 2025-11-04 F5, Inc. Methods for providing secure access using preemptive measures and devices thereof
US11178150B1 (en) 2016-01-20 2021-11-16 F5 Networks, Inc. Methods for enforcing access control list based on managed application and devices thereof
US10149226B2 (en) 2016-03-15 2018-12-04 King Fahd University Of Petroleum And Minerals ID-based routing protocol for wireless network with a grid topology
US11063758B1 (en) 2016-11-01 2021-07-13 F5 Networks, Inc. Methods for facilitating cipher selection and devices thereof
US10505792B1 (en) 2016-11-02 2019-12-10 F5 Networks, Inc. Methods for facilitating network traffic analytics and devices thereof
US10812266B1 (en) 2017-03-17 2020-10-20 F5 Networks, Inc. Methods for managing security tokens based on security violations and devices thereof
US11343237B1 (en) 2017-05-12 2022-05-24 F5, Inc. Methods for managing a federated identity environment using security and access control data and devices thereof
US11122042B1 (en) 2017-05-12 2021-09-14 F5 Networks, Inc. Methods for dynamically managing user access control and devices thereof
US10230639B1 (en) 2017-08-08 2019-03-12 Innovium, Inc. Enhanced prefix matching
US12061990B2 (en) * 2017-10-17 2024-08-13 Xilinx, Inc. Static block scheduling in massively parallel software defined hardware systems
WO2019101350A1 (en) * 2017-11-24 2019-05-31 Fraunhofer-Gesellschaft zur Förderung der angewandten Forschung e.V. Data bus with multi-input pipeline
CN108021507B (zh) * 2017-12-25 2020-07-28 首都师范大学 符号执行的并行路径搜索方法及装置
CN108337176B (zh) * 2017-12-27 2021-04-20 华为技术有限公司 一种报文处理方法和装置
US11494620B2 (en) 2018-02-08 2022-11-08 Western Digital Technologies, Inc. Systolic neural network engine capable of backpropagation
US11461579B2 (en) 2018-02-08 2022-10-04 Western Digital Technologies, Inc. Configurable neural network engine for convolutional filter sizes
US11140078B1 (en) 2018-10-18 2021-10-05 Innovium, Inc. Multi-stage prefix matching enhancements
CN109905497B (zh) * 2019-03-05 2021-08-20 长沙学院 一种IPv6活跃地址动态发现方法
US10929058B2 (en) 2019-03-25 2021-02-23 Western Digital Technologies, Inc. Enhanced memory device architecture for machine learning
US11783176B2 (en) 2019-03-25 2023-10-10 Western Digital Technologies, Inc. Enhanced storage device memory architecture for machine learning
US12039430B2 (en) * 2019-11-15 2024-07-16 Samsung Electronics Co., Ltd. Electronic device and method for inference binary and ternary neural networks
US11392569B2 (en) * 2020-03-19 2022-07-19 Alibaba Group Holding Limited Tree partitioning of the succinct trie
WO2022267018A1 (zh) * 2021-06-25 2022-12-29 新华三技术有限公司 一种报文匹配方法、装置、网络设备及介质
CN121125612B (zh) * 2025-08-28 2026-02-24 中国科学院计算机网络信息中心 一种ip地址查找方法及装置

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6711153B1 (en) * 1999-12-13 2004-03-23 Ascend Communications, Inc. Route lookup engine
US6581106B1 (en) * 2000-01-13 2003-06-17 Pierluigi Crescenzi Fast address lookup in routing tables
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
US7069372B1 (en) 2001-07-30 2006-06-27 Cisco Technology, Inc. Processor having systolic array pipeline for processing data packets
US7382787B1 (en) 2001-07-30 2008-06-03 Cisco Technology, Inc. Packet routing and switching device
US7418536B2 (en) 2001-07-30 2008-08-26 Cisco Technology, Inc. Processor having systolic array pipeline for processing data packets
US7525904B1 (en) 2002-06-20 2009-04-28 Cisco Technology, Inc. Redundant packet routing and switching device and method
US8477780B2 (en) * 2003-03-26 2013-07-02 Alcatel Lucent Processing packet information using an array of processing elements
US8625604B2 (en) * 2009-12-01 2014-01-07 Polytechnic Institute Of New York University Hash-based prefix-compressed trie for IP route lookup

Also Published As

Publication number Publication date
JP5529976B2 (ja) 2014-06-25
JP2013515430A (ja) 2013-05-02
US20120257506A1 (en) 2012-10-11
EP2517420B1 (en) 2014-03-19
US8724624B2 (en) 2014-05-13
WO2011078812A1 (en) 2011-06-30
EP2517420A1 (en) 2012-10-31

Similar Documents

Publication Publication Date Title
TR201209797T2 (tr) Hızlı IP arama için sistolik dizilim mimarisi.
Luo et al. IPREDS: efficient prediction system for Internet-wide port and service scanning
Kini et al. A torus embedded hypercube scalable interconnection network for parallel architecture
Yarmish et al. A distributed, scaleable simplex method
Shekhar et al. Parallel binary search trees for rapid IP lookup using graphic processors
JP2012141715A5 (tr)
US10917345B2 (en) Generating a hash table in accordance with a prefix length
Zhou et al. Scalable GPU-accelerated IPv6 lookup using hierarchical perfect hashing
Feng et al. A fast name lookup method in NDN based on hash coding
Yang et al. Scalable architecture for 135 GBPS IPv6 lookup on FPGA
Kirillova et al. Reproductive biology of Cypripedium guttatum Sw.(Orchidaceae, Monocotyledones) at the northern border of its habitat
Evans EFFECTS OF FLORAL DIVERSIFICATION ON ARTHROPOD COMMUNITY COMPOSITION, ECOSYSTEM SERVICES AND PLANT REPRODUCTION IN THE EDAMAME AGROECOSYSTEM
CN108055126A (zh) 基于随机加法链的抗功耗攻击的方法
Tobola et al. Effective hash-based IPv6 longest prefix match
Al-Jammal Variable range hopping kinetics in CdSe optoelectronic switches under photonic excitations
최정원 High-Throughput Non-Binary LDPC Decoder Architecture Using Dual-Message EMS Algorithm
Rillema et al. Dye sensitized solar photoelectrochemical cells
Verma et al. Conformational dynamics of E. coli YqhD oxidoreductase in the presence of substrates
Guliyeva Genesis of print elements in independent Azerbaijan (on the sample of font)
Boldosova Looking beyond traditional network relationships: Online Subcontracting Platform as an unconventional tool for connecting and benefiting actors in the network.
Gadzhieva et al. VOSPOMINANIYa ALI USTA O ShEYKhE ShARAPUDDINE KIKUNINSKOM KAK ISTOChNIK PO ISTORII DAGESTANSKOGO MUKhADZhIRSTVA KONTsA XIX–NAChALA XX VV
Prasanna SHF: Small: Hardware-Software Co-Design for Next Generation Packet Forwarding Engines
Bonizzoni et al. HAPCOL: Accurate and Memory-efficient Haplotype Assembly from Long Reads
SocMan et al. A Method for Synthesis of Renewable Cu2O Junction Composite Electrodes and Their Photoelectrochemical Properties
Choe et al. Two-dimensional binary search on length using bloom filter for packet classification