[go: up one dir, main page]

Liu et al., 2001 - Google Patents

Fast IP table lookup and memory reduction

Liu et al., 2001

Document ID
16023351601376233661
Author
Liu Y
Lea C
Publication year
Publication venue
2001 IEEE Workshop on High Performance Switching and Routing (IEEE Cat. No. 01TH8552)

External Links

Snippet

One of the time-consuming tasks in IP4 packet processing is maximum sequence matching. Fast routing requires tens of millions of routing lookups to be performed in one second. This paper describes an implementation of IP table lookup. The implementation is intended as …
Continue reading at ieeexplore.ieee.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
    • 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
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • 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
    • H04L29/12792—Details
    • H04L29/12801—Details about the structures and formats of addresses
    • 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
    • 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/40—Wormhole routing
    • 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/04—Interdomain routing, e.g. hierarchical 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/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
    • H04L49/00—Packet switching elements
    • H04L49/25—Routing or path finding through a switch fabric
    • 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
    • H04L61/00—Network arrangements or network protocols for addressing or naming
    • H04L61/35—Network arrangements or network protocols for addressing or naming involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
    • 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/02—Communication control; Communication processing contains provisionally no documents
    • H04L29/06—Communication control; Communication processing contains provisionally no documents characterised by a protocol
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication
    • H04L9/06—Cryptographic mechanisms or cryptographic arrangements for secret or secure communication the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
    • 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
EP1344152B1 (en) Apparatus and method for performing high-speed ip route lookup and managing routing/forwarding tables
US6934252B2 (en) Methods and systems for fast binary network address lookups using parent node information stored in routing table entries
Huang et al. A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers
Nilsson et al. IP-address lookup using LC-tries
US6985483B2 (en) Methods and systems for fast packet forwarding
US7315547B2 (en) Packet forwarding device
Huang et al. A fast IP routing lookup scheme for gigabit switching routers
Pao et al. Efficient hardware architecture for fast IP address lookup
Hayashi et al. High-speed table lookup engine for IPv6 longest prefix match
Sangireddy et al. High-speed IP routing with binary decision diagrams based hardware address lookup engine
Liu Reducing routing table size using ternary-cam
US20220109626A1 (en) Forwarding Rules Among Lookup Tables in a Multi-Stage Packet Processor
Sun et al. An on-chip IP address lookup algorithm
Lim et al. Binary searches on multiple small trees for IP address lookup
Liu et al. Fast IP table lookup and memory reduction
KR100493099B1 (en) Route lookup and routing/forwarding table management for high-speed internet protocol router
Lim et al. High-speed IP address lookup using balanced multi-way trees
KR100572693B1 (en) How to Look Up Internet Protocol Packets
Chang et al. Efficient IP routing table lookup scheme
Wuu et al. A fast IP lookup scheme for longest-matching prefix
Al-Khaffaf et al. Efficient partition based IPv6 lookup algorithm for packet forwarding
Papaefstathiou et al. An innovative low-cost Classification Scheme for combined multi-Gigabit IP and Ethernet Networks
Wang et al. Hardware-based IP routing lookup with incremental update
Yazdani et al. Performing IP lookup on very high line speed
Wuu et al. A fast IP lookup scheme for high speed routers