[go: up one dir, main page]

Mun et al., 2015 - Google Patents

New approach for efficient ip address lookup using a bloom filter in trie-based algorithms

Mun et al., 2015

Document ID
13178223621717387361
Author
Mun J
Lim H
Publication year
Publication venue
IEEE Transactions on Computers

External Links

Snippet

IP address lookup operation determines the longest prefix matching each incoming destination address. As a fundamental operation for packet forwarding at Internet routers, search speed for routing table lookup is the most important performance metric. Previous …
Continue reading at ieeexplore.ieee.org (other versions)

Classifications

    • 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
    • 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/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • 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/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30587—Details of specialised database models
    • G06F17/30589—Hierarchical databases, e.g. IMS, LDAP data stores, Lotus Notes
    • 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
    • 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
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • 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
    • 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
    • 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

Similar Documents

Publication Publication Date Title
Mun et al. New approach for efficient ip address lookup using a bloom filter in trie-based algorithms
Lim et al. On adding bloom filters to longest prefix matching algorithms
US7089240B2 (en) Longest prefix match lookup using hash function
US6553370B1 (en) Flexible search engine having sorted binary search tree for perfect match
US6434144B1 (en) Multi-level table lookup
Qiao et al. Fast Bloom filters and their generalization
Lee et al. Name prefix matching using bloom filter pre-searching for content centric network
Lim et al. Complement Bloom filter for identifying true positiveness of a Bloom filter
Lim et al. Priority tries for IP address lookup
Le et al. Scalable tree-based architectures for IPv4/v6 lookup using prefix partitioning
Pao et al. Efficient hardware architecture for fast IP address lookup
CN101621502A (en) Method and device for storing and searching routing table
CN111817978B (en) Flow classification method and device
CN108134739B (en) Route searching method and device based on index trie
Yoon et al. Bloom tree: A search tree based on bloom filters for multiple-set membership testing
Lim et al. Reducing false positives of a Bloom filter using cross-checking Bloom filters
Shubbar et al. Efficient name matching based on a fast two-dimensional filter in named data networking
Lee et al. Dual-load Bloom filter: Application for name lookup
Song et al. Packet classification using coarse-grained tuple spaces
CN111490906A (en) Method and device for analyzing gateway equipment policy and readable storage medium
Gosselin-Lavigne et al. A performance evaluation of hash functions for IP reputation lookup using bloom filters
CN103842990B (en) The method and apparatus of the virtual addressing based on index
US20160301658A1 (en) Method, apparatus, and computer-readable medium for efficient subnet identification
CN115714752B (en) Packet classification method and device, forwarding chip and electronic equipment
Byun et al. IP address lookup algorithm using a vectored bloom filter