[go: up one dir, main page]

Pao et al., 2002 - Google Patents

Efficient hardware architecture for fast IP address lookup

Pao et al., 2002

View PDF
Document ID
7379298328160561285
Author
Pao D
Liu C
Wu A
Yeung L
Chan K
Publication year
Publication venue
Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies

External Links

Snippet

A multigigabit IP router may receive several million packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet's next-hop. In this paper, we present an efficient hardware …
Continue reading at hub.hku.hk (PDF) (other versions)

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/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • H04L45/7457—Address table lookup or 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 or address filtering
    • H04L45/7453—Address table lookup or address filtering using hashing
    • 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/742—Route cache and its operation
    • 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
    • H04L29/00—Arrangements, apparatus, circuits or systems, not covered by a single one of groups H04L1/00 - H04L27/00 contains provisionally no documents
    • H04L29/12—Arrangements, apparatus, circuits or systems, not covered by a single one of groups H04L1/00 - H04L27/00 contains provisionally no documents characterised by the data terminal contains provisionally no documents
    • H04L29/12009—Arrangements for addressing and naming in data 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
    • 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/30964—Querying
    • G06F17/30979—Query processing
    • 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/40—Wormhole routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L69/00—Application independent communication protocol aspects or techniques in packet data networks
    • H04L69/22—Header parsing or analysis
    • 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
    • H04L61/00—Network arrangements or network protocols for addressing or naming
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security

Similar Documents

Publication Publication Date Title
Pao et al. Efficient hardware architecture for fast IP address lookup
US6934252B2 (en) Methods and systems for fast binary network address lookups using parent node information stored in routing table entries
US7089240B2 (en) Longest prefix match lookup using hash function
US6633548B2 (en) Method and apparatus for ternary content addressable memory (TCAM) table management
US6985483B2 (en) Methods and systems for fast packet forwarding
CN1316390C (en) Performance and memory bandwidth utilization for tree searches using tree fragmentation
KR100586461B1 (en) Method, Hardware Architecture and Recording Medium for Searching IP Address by Using Pipeline Binary Tree
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
US20110128960A1 (en) Hash-based prefix-compressed trie for ip route lookup
Xu et al. A multi-dimensional progressive perfect hashing for high-speed string matching
CN100496019C (en) A Method for Rapid Search and Update of IPv6 Routing Table
Yu et al. Forwarding engine for fast routing lookups and updates
Pao et al. A multi-pipeline architecture for high-speed packet classification
Pao et al. Efficient hardware architecture for fast IP address lookup
Vijay et al. Implementation of memory-efficient linear pipelined IPv6 lookup and its significance in smart cities
Sun et al. An on-chip IP address lookup algorithm
Chang Efficient multidimensional packet classification with fast updates
Li et al. Address lookup algorithms for IPv6
Nie et al. IP address lookup using a dynamic hash function
Lin et al. Improved IP lookup technology for trie-based data structures
Saxena et al. Scalable, high-speed on-chip-based NDN name forwarding using FPGA
Erdem et al. Value-coded trie structure for high-performance IPv6 lookup
Sun et al. Content-based route lookup using CAMs
US9444731B2 (en) Methods and systems for data packet routing
Lin et al. IP Lookup Technology for Internet Computing