[go: up one dir, main page]

Sahni - Google Patents

Recursively Partitioned Static IP Router-Tables

Sahni

View PDF
Document ID
11493444034922195224
Author
Sahni W

External Links

Snippet

We propose a method–recursive partitioning–to partition a static IP router table so that when each partition is represented using a base structure such as a multibit trie or a hybrid shape shifting trie there is a reduction in both the total memory required for the router table as well …
Continue reading at www.cise.ufl.edu (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
    • 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/12—Shortest path evaluation
    • 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/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/30—Special provisions for routing multiclass traffic
    • H04L45/302—Route determination based on requested QoS
    • 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/20—Hop count for routing purposes, e.g. TTL
    • 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/34—Source 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/46—Cluster building
    • 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

Similar Documents

Publication Publication Date Title
US7990979B2 (en) Recursively partitioned static IP router tables
US7418505B2 (en) IP address lookup using either a hashing table or multiple hash functions
US8089961B2 (en) Low power ternary content-addressable memory (TCAMs) for very large forwarding tables
Zane et al. CoolCAMs: Power-efficient TCAMs for forwarding engines
Basu et al. Fast incremental updates for pipelined forwarding engines
Tzeng et al. On fast address-lookup algorithms
US6594655B2 (en) Wildcards in radix- search tree structures
US7948980B2 (en) Succinct representation of static packet classifiers
US5983223A (en) Method and apparatus for determining a longest matching prefix from a dictionary of prefixes
US7356033B2 (en) Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
Sahni et al. Efficient construction of multibit tries for IP lookup
Warkhede et al. Multiway range trees: scalable IP lookup with fast updates
US20030174717A1 (en) System and method for longest prefix match for internet protocol lookup
US20040105422A1 (en) Dynamic IP router tables using highest-priority matching
US20100100569A1 (en) Method of Accelerating the Shortest Path Problem
KR100512949B1 (en) Apparatus and method for packet classification using Field Level Trie
US7444318B2 (en) Prefix partitioning methods for dynamic router tables
Veeramani et al. Hybrid trie based partitioning of TCAM based openflow switches
Hsieh et al. A classified multisuffix trie for IP lookup and update
Veeramani et al. Efficient IP lookup using hybrid trie-based partitioning of TCAM-based open flow switches
Lim et al. NXG06-1: An efficient IP address lookup algorithm using a priority trie
Sahni Recursively Partitioned Static IP Router-Tables
Lu et al. Recursively Partitioned Static IP Router Tables
Sahni et al. IP router tables
Lu et al. Packet classification using space-efficient pipelined multibit tries