[go: up one dir, main page]

Liu, 2002 - Google Patents

Routing table compaction in ternary CAM

Liu, 2002

View PDF
Document ID
8868041903297705703
Author
Liu H
Publication year
Publication venue
IEEE Micro

External Links

Snippet

Techniques are presented for reducing the size of routing tables stored in ternary content- addressable memory (CAM), which result in decreased cost, power consumption, and thermal dissipation. CAM allows simultaneous comparison between all indexes and the key …
Continue reading at cial.csie.ncku.edu.tw (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
    • 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/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
    • 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/48—Routing tree calculation
    • 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/60—Router architecture
    • 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/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/60—Hybrid or multiprotocol packet, ATM or frame switches
    • H04L49/602—Multilayer or multiprotocol switching, e.g. IP switching
    • 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
    • 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
    • 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
    • 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

Similar Documents

Publication Publication Date Title
Liu Routing table compaction in ternary CAM
US6985483B2 (en) Methods and systems for fast packet forwarding
EP2517420B1 (en) Systolic array architecture for fast ip lookup
Ravikumar et al. EaseCAM: An energy and storage efficient TCAM-based router architecture for IP lookup
Fu et al. Efficient IP-address lookup with a shared forwarding table for multiple virtual routers
US7424468B2 (en) Internet protocol address look-up device
US7440460B2 (en) Apparatus and method for forwarding mixed data packet types in a high-speed router
Pao et al. Efficient hardware architecture for fast IP address lookup
Hayashi et al. High-speed table lookup engine for IPv6 longest prefix match
WO2002082709A2 (en) High-speed message forwarding lookups for arbitrary length strings using pipelined memories
US20060248095A1 (en) Efficient RAM lookups by means of compressed keys
US8599853B2 (en) System and method for an exact match search using pointer based pipelined multibit trie traversal technique
Liu Reducing routing table size using ternary-cam
Le et al. Scalable high throughput and power efficient ip-lookup on fpga
US7564841B2 (en) Apparatus and method for performing forwarding table searches using consecutive symbols tables
Yu et al. Forwarding engine for fast routing lookups and updates
Sun et al. An on-chip IP address lookup algorithm
US7702882B2 (en) Apparatus and method for performing high-speed lookups in a routing table
Veeramani et al. Minimization of flow table for TCAM based openflow switches by virtual compression approach
Le et al. Memory-efficient and scalable virtual routers using FPGA
Ray et al. Memory efficient hash-based longest prefix matching architecture with zero false+ ve and nearly zero false− ve rate for IP processing
Nakahara et al. A memory-based IPv6 lookup architecture using parallel index generation units
KR100493099B1 (en) Route lookup and routing/forwarding table management for high-speed internet protocol router
Sun et al. Content-based route lookup using CAMs
Tata MicroCuckoo Hash Engine for High-Speed IP Lookup