[go: up one dir, main page]

Pao et al., 2003 - Google Patents

Efficient hardware architecture for fast IP address lookup

Pao et al., 2003

Document ID
6287142701469411950
Author
Pao D
Liu C
Wu A
Yeung L
Chan K
Publication year
Publication venue
IEE Proceedings-Computers and Digital Techniques

External Links

Snippet

A multi-gigabit internet protocol (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. An efficient hardware …
Continue reading at digital-library.theiet.org (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
    • 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
    • G06F17/30985—Query processing by using string matching techniques
    • 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
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • 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
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • 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/20—Support for services or operations
    • H04L49/201—Multicast or broadcast
    • 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

Similar Documents

Publication Publication Date Title
Pao et al. Efficient hardware architecture for fast IP address lookup
US6697363B1 (en) Method and apparatus for longest matching prefix determination in a communication network
US6934252B2 (en) Methods and systems for fast binary network address lookups using parent node information stored in routing table entries
Nilsson et al. IP-address lookup using LC-tries
US6985483B2 (en) Methods and systems for fast packet forwarding
CN1316390C (en) Performance and memory bandwidth utilization for tree searches using tree fragmentation
US8089961B2 (en) Low power ternary content-addressable memory (TCAMs) for very large forwarding tables
US6430527B1 (en) Prefix search circuitry and method
US20030174717A1 (en) System and method for longest prefix match for internet protocol lookup
US20040085953A1 (en) Longest prefix matching (LPM) using a fixed comparison hash table
US7249149B1 (en) Tree bitmap data structures and their use in performing lookup operations
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
US20050083937A1 (en) IP address lookup method using pipeline binary tree, hardware architecture, and recording medium
Lim et al. Priority tries for IP address lookup
CN104954200A (en) A high-speed matching method and device for multi-type rules of network data packets
Pao et al. Efficient hardware architecture for fast IP address lookup
Xu et al. A multi-dimensional progressive perfect hashing for high-speed string matching
US7478109B1 (en) Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes
US20070121632A1 (en) Method and system for routing an IP packet
Yu et al. Forwarding engine for fast routing lookups and updates
EP1111877A2 (en) IP address resolution methods and apparatus
Vijay et al. Implementation of memory-efficient linear pipelined IPv6 lookup and its significance in smart cities
Le et al. Memory-efficient ipv4/v6 lookup on fpgas using distance-bounded path compression
Li et al. Address lookup algorithms for IPv6
Pao et al. Enhanced prefix inclusion coding filter-encoding algorithm for packet classification with ternary content addressable memory