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

Zhao et al., 2010 - Google Patents

Achieving O (1) IP lookup on GPU-based software routers

Zhao et al., 2010

View PDF
Document ID
15248546675427159568
Author
Zhao J
Zhang X
Wang X
Xue X
Publication year
Publication venue
Proceedings of the ACM SIGCOMM 2010 Conference

External Links

Snippet

IP address lookup is a challenging problem due to the increasing routing table size, and higher line rate. This paper investigates a new way to build an efficient IP lookup scheme using graphics processor units (GPU). Our contribution here is to design a basic architecture …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0875—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with dedicated cache, e.g. instruction or stack
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30949—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing 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/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • H04L45/7453—Address table lookup or address filtering using hashing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • 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

Similar Documents

Publication Publication Date Title
Wang et al. Wire Speed Name Lookup: A {GPU-based} Approach
US10397362B1 (en) Combined cache-overflow memory structure
Jiang et al. Beyond TCAMs: An SRAM-based parallel multi-pipeline architecture for terabit IP lookup
Zhao et al. Exploiting graphics processors for high-performance IP lookup in software routers
JP5529976B2 (en) Systolic array architecture for high-speed IP lookup
US20070171911A1 (en) Routing system and method for managing rule entry thereof
US20220255721A1 (en) Acceleration unit and related apparatus and method
US10515015B2 (en) Hash table-based mask length computation for longest prefix match caching
EP2288092A1 (en) Method and device for improving scalability of longest prefix match
Zhao et al. Achieving O (1) IP lookup on GPU-based software routers
Le et al. A sram-based architecture for trie-based ip lookup using fpga
US7680806B2 (en) Reducing overflow of hash table entries
Tong et al. High-throughput online hash table on FPGA
Luo et al. A trie merging approach with incremental updates for virtual routers
Jiang et al. Parallel IP lookup using multiple SRAM-based pipelines
Dann et al. GraphScale: Scalable bandwidth-efficient graph processing on FPGAs
Chen et al. Investigating route cache in named data networking
Tzeng Routing table partitioning for speedy packet lookups in scalable routers
Zhang et al. Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network
Ghosh et al. A hash based architecture of longest prefix matching for fast IP processing
Chang et al. Dynamic multiway segment tree for IP lookups and the fast pipelined search engine
Jiang et al. Sequence-preserving parallel IP lookup using multiple SRAM-based pipelines
Vijay et al. Implementation of memory-efficient linear pipelined IPv6 lookup and its significance in smart cities
Jiang et al. Multi-terabit IP lookup using parallel bidirectional pipelines
Chu et al. IP address lookup by using GPU