[go: up one dir, main page]

Draves et al., 1999 - Google Patents

Constructing optimal IP routing tables

Draves et al., 1999

View PDF
Document ID
11808630036065714505
Author
Draves R
King C
Venkatachary S
Zill B
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 Border Gateway Protocol (BGP) populates Internet backbone routers with routes or prefixes. We present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably contain the minimal number of prefixes. For large …
Continue reading at www.microsoft.com (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
    • 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
    • H04L69/00—Application independent communication protocol aspects or techniques in packet data networks
    • H04L69/30—Definitions, standards or architectural aspects of layered protocol stacks
    • H04L69/32—High level architectural aspects of 7-layer open systems interconnection [OSI] type protocol stacks
    • 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/02—Topology update or discovery
    • 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/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
    • 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
    • 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
    • H04L61/00—Network arrangements or network protocols for addressing or naming

Similar Documents

Publication Publication Date Title
Draves et al. Constructing optimal IP routing tables
US7509300B2 (en) Dynamic IP router tables using highest-priority matching
US7990979B2 (en) Recursively partitioned static IP router tables
JP4268337B2 (en) Router and method for optimal routing table compression
US7089240B2 (en) Longest prefix match lookup using hash function
JP4565793B2 (en) Method and apparatus for longest match address lookup
Sahni et al. Efficient construction of multibit tries for IP lookup
US7039641B2 (en) Modular packet classification
US6728732B1 (en) Data structure using a tree bitmap and method for rapid classification of data in a database
Huang et al. A fast IP routing lookup scheme for gigabit switching routers
US6792423B1 (en) Hybrid longest prefix match and fixed match searches
US20040254909A1 (en) Programming routes and access control lists in comparison tree data structures and their use such as in performing lookup operations
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
US20040230583A1 (en) Comparison tree data structures of particular use in performing lookup operations
US7474657B2 (en) Partitioning methods for dynamic router tables
US7249149B1 (en) Tree bitmap data structures and their use in performing lookup operations
EP1063827B1 (en) Method for address lookup
JP3881663B2 (en) Packet classification apparatus and method using field level tree
US7444318B2 (en) Prefix partitioning methods for dynamic router tables
Hsieh et al. A classified multisuffix trie for IP lookup and update
Lu et al. Enhanced interval trees for dynamic IP router-tables
US20060200581A1 (en) Prefix processing technique for faster IP routing
US7376657B1 (en) Fast IPv6 address lookup using skip level processing on multi-bit tries
Pao et al. Enabling incremental updates to LC-trie for efficient management of IP forwarding tables
Lee et al. A simple and scalable algorithm for the IP address lookup problem