WO2008017045A3 - Succinct representation of static packet classifiers - Google Patents

Succinct representation of static packet classifiers Download PDF

Info

Publication number
WO2008017045A3
WO2008017045A3 PCT/US2007/075107 US2007075107W WO2008017045A3 WO 2008017045 A3 WO2008017045 A3 WO 2008017045A3 US 2007075107 W US2007075107 W US 2007075107W WO 2008017045 A3 WO2008017045 A3 WO 2008017045A3
Authority
WO
WIPO (PCT)
Prior art keywords
data
computer
packet classifier
classifier rule
memory
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US2007/075107
Other languages
French (fr)
Other versions
WO2008017045A2 (en
WO2008017045A9 (en
Inventor
Wencheng Lu
Sartaj Sahni
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University of Florida
University of Florida Research Foundation Inc
Original Assignee
University of Florida
University of Florida Research Foundation Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by University of Florida, University of Florida Research Foundation Inc filed Critical University of Florida
Priority to EP07840670A priority Critical patent/EP2074767A2/en
Priority to US12/375,623 priority patent/US7948980B2/en
Publication of WO2008017045A2 publication Critical patent/WO2008017045A2/en
Anticipated expiration legal-status Critical
Publication of WO2008017045A9 publication Critical patent/WO2008017045A9/en
Publication of WO2008017045A3 publication Critical patent/WO2008017045A3/en
Ceased legal-status Critical Current

Links

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/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/14—Routing performance; Theoretical aspects
    • 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/74—Address processing for routing
    • H04L45/742—Route cache; Operation thereof

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

A computer-implemented method of classifying packets of data transmitted over a data communications network includes providing a memory-storable packet classifier rule defined by a plurality of filters, each filter uniquely corresponding to a one of a plurality of actions to be taken in transmitting the data packets over the data communications network; and classifying a data packet according to the packet classifier rule by generating at least one supernode trie subject to a predetermined constraint for reducing accesses to a memory in which the packet classifier rule is stored. A system including a combination of hardware and software modules is provided for carrying out the method. A computer-readable storage medium is also provided for storing a computer program for carrying out the method.
PCT/US2007/075107 2006-08-02 2007-08-02 Succinct representation of static packet classifiers Ceased WO2008017045A2 (en)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP07840670A EP2074767A2 (en) 2006-08-02 2007-08-02 Succinct representation of static packet classifiers
US12/375,623 US7948980B2 (en) 2006-08-02 2007-08-02 Succinct representation of static packet classifiers

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US82122006P 2006-08-02 2006-08-02
US60/821,220 2006-08-02

Publications (3)

Publication Number Publication Date
WO2008017045A2 WO2008017045A2 (en) 2008-02-07
WO2008017045A9 WO2008017045A9 (en) 2009-03-12
WO2008017045A3 true WO2008017045A3 (en) 2009-04-30

Family

ID=38961257

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2007/075107 Ceased WO2008017045A2 (en) 2006-08-02 2007-08-02 Succinct representation of static packet classifiers

Country Status (4)

Country Link
US (1) US7948980B2 (en)
EP (1) EP2074767A2 (en)
CN (1) CN101554021A (en)
WO (1) WO2008017045A2 (en)

Families Citing this family (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100205135A1 (en) * 2008-03-07 2010-08-12 Barracuda Inc. Determining best match among a plurality of pattern rules using wildcards with a text string
WO2011032954A1 (en) * 2009-09-15 2011-03-24 Napatech A/S An apparatus for analyzing a data packet, a data packet processing system and a method
US8990526B2 (en) * 2010-10-06 2015-03-24 Quantum Corporation Merging data volumes and derivative versions of the data volumes
US9361578B2 (en) * 2011-07-13 2016-06-07 Palo Alto Research Center Incorporated Memory efficient state-set representation for planning
US9183244B2 (en) 2011-08-02 2015-11-10 Cavium, Inc. Rule modification in decision trees
US9208438B2 (en) 2011-08-02 2015-12-08 Cavium, Inc. Duplication in decision trees
US9525630B2 (en) 2011-08-02 2016-12-20 Cavium, Inc. Method and apparatus for assigning resources used to manage transport operations between clusters within a processor
US10229139B2 (en) 2011-08-02 2019-03-12 Cavium, Llc Incremental update heuristics
WO2013119173A2 (en) * 2012-02-07 2013-08-15 Oricane Ab Classification engine for data packet classification
WO2014117353A1 (en) * 2013-01-31 2014-08-07 Hewlett-Packard Development Company, L.P. Incremental update of a shape graph
US10083200B2 (en) * 2013-03-14 2018-09-25 Cavium, Inc. Batch incremental update
US10229144B2 (en) 2013-03-15 2019-03-12 Cavium, Llc NSP manager
US9195939B1 (en) 2013-03-15 2015-11-24 Cavium, Inc. Scope in decision trees
US9595003B1 (en) 2013-03-15 2017-03-14 Cavium, Inc. Compiler with mask nodes
US9275336B2 (en) 2013-12-31 2016-03-01 Cavium, Inc. Method and system for skipping over group(s) of rules based on skip group rule
US9544402B2 (en) 2013-12-31 2017-01-10 Cavium, Inc. Multi-rule approach to encoding a group of rules
US9667446B2 (en) 2014-01-08 2017-05-30 Cavium, Inc. Condition code approach for comparing rule and packet data that are provided in portions
US11023594B2 (en) * 2017-05-22 2021-06-01 Georgetown University Locally private determination of heavy hitters
CN107835175B (en) * 2017-11-09 2020-09-22 深圳市云盾科技有限公司 Network connection tracking method adopting balanced binary tree algorithm
US11240143B2 (en) * 2019-05-02 2022-02-01 Fungible, Inc. Embedded network packet data for use of alternative paths within a group of network devices
US11392569B2 (en) * 2020-03-19 2022-07-19 Alibaba Group Holding Limited Tree partitioning of the succinct trie
CN113515495B (en) * 2021-04-14 2024-03-19 暨南大学 Data file distribution method and device, intelligent equipment and computer storage medium

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1999066681A1 (en) * 1998-06-19 1999-12-23 Unisphere Solutions, Inc. Network packet forwarding lookup with a reduced number of memory accesses
US20050083935A1 (en) * 2003-10-20 2005-04-21 Kounavis Michael E. Method and apparatus for two-stage packet classification using most specific filter matching and transport level sharing
US20050163122A1 (en) * 2003-12-31 2005-07-28 University Of Florida Research Foundation, Inc. System and methods for packet filtering

Family Cites Families (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5995971A (en) 1997-09-18 1999-11-30 Micdrosoft Corporation Apparatus and accompanying methods, using a trie-indexed hierarchy forest, for storing wildcard-based patterns and, given an input key, retrieving, from the forest, a stored pattern that is identical to or more general than the key
US6041053A (en) 1997-09-18 2000-03-21 Microsfot Corporation Technique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcards
US6341130B1 (en) 1998-02-09 2002-01-22 Lucent Technologies, Inc. Packet classification method and apparatus employing two fields
FI982095A7 (en) 1998-09-29 2000-03-30 Nokia Corp Method for implementing memory and memory arrangement
FR2789778B1 (en) 1999-02-12 2001-09-14 France Telecom METHOD FOR ASSOCIATING ROUTING REFERENCES WITH DATA PACKETS BY MEANS OF A SORTED MEMORY, AND PACKET ROUTER APPLYING THIS METHOD
US6633860B1 (en) 1999-04-22 2003-10-14 Ramot At Tel Aviv University Ltd. Method for fast multi-dimensional packet classification
US6765909B1 (en) 1999-04-22 2004-07-20 Nortel Networks Limited Method and apparatus for providing support for multiple QoS levels within a third generation packet data session
GB9912129D0 (en) 1999-05-26 1999-07-28 3Com Corp Communication device with forwarding database having having a trie search facility
US6587466B1 (en) 1999-05-27 2003-07-01 International Business Machines Corporation Search tree for policy based packet classification in communication networks
FI991261L (en) 1999-06-02 2000-12-03 Nokia Networks Oy Functional memory based on a trie structure
US6850513B1 (en) 1999-12-30 2005-02-01 Intel Corporation Table-based packet classification
EP1128608B1 (en) 2000-01-27 2006-03-01 International Business Machines Corporation Method and means for classifying data packets
TW498650B (en) 2000-03-22 2002-08-11 Ind Tech Res Inst Flexible and highly efficient packet classification method
US6970462B1 (en) 2000-04-24 2005-11-29 Cisco Technology, Inc. Method for high speed packet classification
US6925085B1 (en) 2000-06-07 2005-08-02 Advanced Micro Devices, Inc. Packet classification using hash key signatures generated from interrupted hash function
US6697363B1 (en) 2000-06-28 2004-02-24 Alcatel Canada Inc. Method and apparatus for longest matching prefix determination in a communication network
US7002965B1 (en) 2001-05-21 2006-02-21 Cisco Technology, Inc. Method and apparatus for using ternary and binary content-addressable memory stages to classify packets
US6985483B2 (en) 2001-07-31 2006-01-10 North Carolina State University Methods and systems for fast packet forwarding
US7054315B2 (en) * 2001-09-17 2006-05-30 Pmc-Sierra Ltd. Efficiency masked matching
US7007101B1 (en) 2001-11-09 2006-02-28 Radisys Microware Communications Software Division, Inc. Routing and forwarding table management for network processor architectures
US6996225B1 (en) 2002-01-31 2006-02-07 Cisco Technology, Inc. Arrangement for controlling congestion in an SS7 signaling node based on packet classification
US6691171B1 (en) 2002-02-01 2004-02-10 Micrel, Inc. Method and system for address lookup in data communication
US6694323B2 (en) 2002-04-25 2004-02-17 Sybase, Inc. System and methodology for providing compact B-Tree
US7480302B2 (en) 2004-05-11 2009-01-20 Samsung Electronics Co., Ltd. Packet classification method through hierarchical rulebase partitioning

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1999066681A1 (en) * 1998-06-19 1999-12-23 Unisphere Solutions, Inc. Network packet forwarding lookup with a reduced number of memory accesses
US20050083935A1 (en) * 2003-10-20 2005-04-21 Kounavis Michael E. Method and apparatus for two-stage packet classification using most specific filter matching and transport level sharing
US20050163122A1 (en) * 2003-12-31 2005-07-28 University Of Florida Research Foundation, Inc. System and methods for packet filtering

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
ANDREJ BRODNIK, J. IAN MUNRO: "Neighbours on a Grid", LULEA UNIVERSITY, July 1996 (1996-07-01), pages 1 - 12, XP002466442 *
ROHAN JUDE FERNANDES: "Succinct balanced binary tree and packed memory structure", CS 514 PROJECT, 2003, pages 1 - 8, XP002466441 *
WENCHENG LU, SARTAJ SAHNI: "Succinct Representation Of Static Packet Classifiers", DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE AND ENGINEERING, 19 July 2006 (2006-07-19), Gainesville, Florida, pages 1 - 37, XP002466440 *

Also Published As

Publication number Publication date
EP2074767A2 (en) 2009-07-01
WO2008017045A2 (en) 2008-02-07
CN101554021A (en) 2009-10-07
WO2008017045A9 (en) 2009-03-12
US20100034202A1 (en) 2010-02-11
US7948980B2 (en) 2011-05-24

Similar Documents

Publication Publication Date Title
Gao et al. A new delay system approach to network-based control
WO2008151321A3 (en) Systems, methods, and media for enforcing a security policy in a network including a plurality of components
WO2012092556A3 (en) System and method for online communications management
WO2012015657A3 (en) Systems and methods for managing electronic content
WO2012111905A3 (en) Distributed memory cluster control device and method using mapreduce
WO2008146807A1 (en) Ontology processing device, ontology processing method, and ontology processing program
WO2011030100A3 (en) Analysis of communications in a social network
WO2010006112A3 (en) Secure high performance multi-level security database systems and methods
WO2009032776A3 (en) Power management of data processing resources, such as power adaptive management of data storage operations
WO2010132456A3 (en) System and method for priority delivery of load management messages on ip-based networks
WO2009052189A3 (en) External referencing by portable program modules
WO2007018919A3 (en) Dynamically balancing user experiences in a multi-user computing system
WO2012177204A8 (en) Methods and apparatuses for accounting of cell change information
WO2009032491A3 (en) Module hosting and content generation platform
WO2009114436A3 (en) Method and system for secure data exfiltration from a closed network or system
WO2011123361A3 (en) Mapping rdma semantics to high speed storage
WO2008052908A3 (en) Method and system for optimizing metadata of audio-video asset in television network
WO2012138588A3 (en) Modeling and consuming business policy rules
WO2013118141A3 (en) System and method for optimizing customer engagement
WO2011070334A9 (en) Accessing stored electronic resources
WO2007046595A3 (en) Method for generating/changing transport connection identifier in portable internet network and portable subscriber station therefor
Zhang et al. Analysis and design of energy harvesting wireless sensor networks with linear topology
CN102447641B (en) Flow control system for computer room
WO2009123998A3 (en) Command and control systems for cyber warfare
WO2013019070A3 (en) Method and system for scalable information packetization and aggregation for information transmission in communication networks

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200780028490.4

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 114/KOLNP/2009

Country of ref document: IN

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2007840670

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: RU

WWE Wipo information: entry into national phase

Ref document number: 12375623

Country of ref document: US