[go: up one dir, main page]

Cheung et al., 1999 - Google Patents

Optimal routing table design for IP address lookups under memory constraints

Cheung et al., 1999

View PDF
Document ID
5104307629155461199
Author
Cheung G
McCanne S
Publication year
Publication venue
IEEE INFOCOM'99. Conference on Computer Communications. Proceedings. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. The Future is Now (Cat. No. 99CH36320)

External Links

Snippet

The design of lookup tables for fast IP address lookup algorithms using a general processor is formalized as an optimization problem. A cost model that models the access times and sizes of the hierarchical memory structure of the processor is formulated. Two algorithms …
Continue reading at www.researchgate.net (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]
    • 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/30958—Graphs; Linked lists
    • 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/30961—Trees
    • 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
    • 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/04—Interdomain routing, e.g. hierarchical 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/40—Wormhole routing
    • 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
    • H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching

Similar Documents

Publication Publication Date Title
Cheung et al. Optimal routing table design for IP address lookups under memory constraints
Basu et al. Fast incremental updates for pipelined forwarding engines
Zane et al. CoolCAMs: Power-efficient TCAMs for forwarding engines
Ruiz-Sánchez et al. Survey and taxonomy of IP address lookup algorithms
Shiloach et al. An O (n2log n) parallel max-flow algorithm
US7509300B2 (en) Dynamic IP router tables using highest-priority matching
Waldvogel et al. Scalable high-speed prefix matching
US6018524A (en) Scalable high speed IP routing lookups
US8089961B2 (en) Low power ternary content-addressable memory (TCAMs) for very large forwarding tables
US7356033B2 (en) Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
Gupta Algorithms for routing lookups and packet classification
US6243720B1 (en) Address translation method and system having a forwarding table data structure
Jiang et al. Large-scale wire-speed packet classification on FPGAs
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
Hasan et al. Dynamic pipelining: Making IP-lookup truly scalable
CN101491015A (en) Dynamic tree bitmap for IP lookup and update
Lu et al. Enhanced interval trees for dynamic IP router-tables
SK3692000A3 (en) Method and system for fast routing lookups
Sahni et al. Data structures for one-dimensional packet classification using most-specific-rule matching
Taylor Models, algorithms, and architectures for scalable packet classification
Pierre et al. An Artificial Intelligence approach to improving computer communications network topologies
Hsieh et al. Multiprefix trie: A new data structure for designing dynamic router-tables
Buchsbaum et al. Fast prefix matching of bounded strings
Donnelly et al. IP route lookups as string matching
Ahmad et al. An efficient approach to on-chip logic minimization