Survey and Taxonomy of Packet

Please download to get full document.

View again

of 42
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Similar Documents
Information Report



Views: 65 | Pages: 42

Extension: PDF | Download: 0

Survey & Taxonomy of Packet Classification Techniques David E. Taylor WUCSE-2004-24 May 10, 2004 Applied Research Laboratory Department of Computer Science and Engineering Washington University in Saint Louis Campus Box 1045 One Brookings Drive Saint Louis, MO 63130 Abstract Packet classification is an enabling function for a variety of Internet applications including Quality of Service, security, monitoring, and multimedia communications. In order to classify a packet as be
  Survey & Taxonomy of Packet Classification Techniques David E. TaylorWUCSE-2004-24May 10, 2004Applied Research LaboratoryDepartment of Computer Science and EngineeringWashington University in Saint LouisCampus Box 1045One Brookings DriveSaint Louis, MO Abstract Packet classification is an enabling function for a variety of Internet applications including Quality of Ser-vice, security, monitoring, and multimedia communications. In order to classify a packet as belonging to aparticular flow or set of flows, network nodes must perform a search over a set of filters using multiple fieldsof the packet as the search key. In general, there have been two major threads of research addressing packetclassification: algorithmic and architectural. A few pioneering groups of researchers posed the problem,provided complexity bounds, and offered a collection of algorithmic solutions. Subsequently, the designspace has been vigorously explored by many offering new algorithms and improvements upon existing al-gorithms. Given the inability of early algorithms to meet performance constraints imposed by high speedlinks, researchers in industry and academia devised architectural solutions to the problem. This thread of research produced the most widely-used packet classification device technology, Ternary Content Address-able Memory (TCAM). New architectural research combines intelligent algorithms and novel architecturesto eliminate many of the unfavorable characteristics of current TCAMs. We observe that the communityappears to be converging on a combined algorithmic and architectural approach to the problem. Using a tax-onomy based on the high-level approach to the problem and a minimal set of running examples, we providea survey of the seminal and recent solutions to the problem. It is our hope to foster a deeper understanding of the various packet classification techniques while providing a useful framework for discerning relationshipsand distinctions.1  Table 1: Example filter set of 16 filters classifying on four fields; each filter has an associated flow identifier( Flow ID ) and priority tag ( PT  ) where † denotes a non-exclusive filter; wildcard fields are denoted with ∗ . Filter ActionSA DA Prot DP FlowID PT  11010010 * TCP [3:15] 0 310011100 * * [1:1] 1 5101101* 001110* * [0:15] 2 8 † 10011100 01101010 UDP [5:5] 3 2* * ICMP [0:15] 4 9 † 100111* 011010* * [3:15] 5 6 † 10010011 * TCP [3:15] 6 3* * UDP [3:15] 7 9 † 11101100 01111010 * [0:15] 8 2111010* 01011000 UDP [6:6] 9 2100110* 11011000 UDP [0:15] 10 2010110* 11011000 UDP [0:15] 11 201110010 * TCP [3:15] 12 4 † 10011100 01101010 TCP [0:1] 13 301110010 * * [3:3] 14 3100111* 011010* UDP [1:1] 15 4 1 Introduction Packet classification is an enabling function for a variety of Internet applications including Quality of Ser-vice, security, monitoring, and multimedia communications. Such applications typically operate on packetflows or sets of flows; therefore, network nodes must classify individual packets traversing the node in orderto assign a flow identifier, FlowID . Packet classification entails searching a table of filters which binds apacket to a flow or set of flows and returning the FlowID for the highest priority filter or set of filters whichmatch the packet. Note that filters are also referred to as rules in some of the packet classification literature.Likewise, a FlowID is synonymous with the action applied to the packet. At minimum, filters contain mul-tiple field values that specify an exact packet header or set of headers and the associated FlowID for packetsmatching all the field values. The type of field values are typically prefixes for IP address fields, an exactvalue or wildcard for the transport protocol number and flags, and ranges for port numbers. An examplefilter table is shown in Table 1. In this simple example, filters contain field values for four packet headersfields: 8-bit source and destination addresses, transport protocol, and a 4-bit destination port number.Filter priority may be implied by the order of filters in the filter set. Note that the filters in Table 1 containan explicit priority tag PT  and a non-exclusive flag denoted by † . Priority tags allow filter priority to beindependent of filter ordering. Non-exclusive flags allow filters to be designated as either exclusive or non-exclusive. Packets may match only one exclusive filter, allowing Quality of Service and security applicationsto specify a single action for the packet. Packets may also match several non-exclusive filters, providingsupport for transparent monitoring and usage-based accounting applications. Note that a parameter maycontrol the number of non-exclusive filters, r  , returned by the packet classifier. Like exclusive filters, thepriority tag is used to select the r  highest priority non-exclusive filters. Consider an example search throughthe filter set in Table 1 for a packet with the following header fields: source address 10011100, destinationaddress 01101010, protocol UDP, destination port 1. This packet matches the filters with FlowID 5 and2  15 with priority tags 5 and 4, respectively. Since both are exclusive filters, FlowID 15 is applied to thepacket, assuming that the highest priority level is 0. Given that no non-exclusive filters match the packet,we return only one FlowID . Any packet classification technique that supports multiple matches can supportnon-exclusive filters; however, techniques which employ precomputation to encode priority into the searchmay preclude their use.Due to the complexity of the search, packet classification is often a performance bottleneck in network infrastructure; therefore, it has received much attention in the research community. In general, there havebeen two major threads of research addressing this problem: algorithmic and architectural. A few pioneeringgroups of researchers posed the problem, provided complexity bounds, and offered a collection of algorith-mic solutions [1, 2, 3, 4]. Subsequently, the design space has been vigorously explored by many offeringnew algorithms and improvements upon existing algorithms [5, 6, 7]. Given the inability of early algorithmsto meet the performance constraints discussed in Section 1.1, researchers in industry and academia devisedarchitectural solutions to the problem. This thread of research produced the most widely-used packet clas-sification device technology, Ternary Content Addressable Memory (TCAM) [8, 9, 10, 11].Some of the most promising algorithmic research embraces the practice of leveraging the statisticalstructure of filter sets to improve average performance [1, 5, 12, 2, 13]. Several algorithms in this classare amenable to high-performance hardware implementation. We discuss these observations in more detailand provide motivation for packet classification on larger numbers of fields in Section 2. New architecturalresearch combines intelligent algorithms and novel architectures to eliminate many of the unfavorable char-acteristics of current TCAMs [14]. We observe that the community appears to be converging on a combinedalgorithmic and architectural approach to the problem [14, 15, 16]. In order to lend structure to our discus-sion, we develop a taxonomy in Section 3 that frames each technique according to its high-level approachto the problem. The presentation of this taxonomy is followed by a survey of the seminal and recent solu-tions to the packet classification problem. Throughout our presentation we attempt to use a minimal set of running examples to provide continuity to the presentation and highlight the distinctions among the varioussolutions. 1.1 Constraints Computational complexity is not the only challenging aspect of the packet classification problem. Increas-ingly, traffic in large ISP networks and the Internet backbone travels over links with transmission rates inexcess of one billion bits per second (1 Gb/s). Current generation fiber optic links can operate at over 40Gb/s. The combination of transmission rate and packet size dictate the throughput, the number of packetsper second, routers must support. A majority of Internet traffic utilizes the Transmission Control Protocolwhich transmits 40 byte acknowledgment packets. In the worst case, a router could receive a long stream of TCP acknowledgments, therefore conservative router architects set the throughput target based on the inputlink rate and 40 byte packet lengths. For example, supporting 10 Gb/s links requires a throughput of 31million packets per second per port. Modern Internet routers contain tens to thousands of ports. In suchhigh-performance routers, route lookup and packet classification is performed on a per-port basis.Many algorithmic solutions to the route lookup and packet classification problems provide sufficientperformance on average. Most techniques suffer from poor performance for a pathological search. Forexample, a technique might employ a decision tree where most paths through the tree are short, howeverone path is significantly long. If a sufficiently long sequence of packets that follows the longest path throughthe tree arrives at the input port of the router, then the throughput is determined by the worst-case searchperformance. It is this set of worst-case assumptions that imposes the so-called “wire speed requirement” forroute lookup and packet classification solutions. In essence, solutions to these search problems are almost3  always evaluated based on the time it takes to perform a pathological search. In the context of networksthat provide performance guarantees, engineering for the worst case logically follows. In the context of the Internet, the protocols make no performance guarantees and provide “best-effort” service to all traffic.Furthermore, the switching technology at the core of routers cannot handle pathological traffic. Imaginea sufficiently long sequence of packets in which all the packets arriving at the input ports are destined forthe same output port. When the buffers in the router ports fill up, it will begin dropping packets. Thus,the “wire speed requirement” for Internet routers does not logically follow from the high-level protocols orthe underlying switching technology; it is largely driven by network management and marketing concerns.Quite simply, it is easier to manage a network with one less source of packet losses and it is easier to sellan expensive piece of network equipment when you don’t have to explain the conditions under which thesearch engines in the router ports will begin backlogging. It is for these reasons that solutions to the routelookup and packet classification problems are typically evaluated by their worst-case performance.Achieving tens of millions of lookups per second is not the only challenge for route lookup and packetclassificationsearchengines. DuetotheexplosivegrowthoftheInternet, backboneroutetableshaveswelledto over 100k entries. Likewise, the constant increase in the number of security filters and network serviceapplications causes packet classification filter sets to increase in size. Currently, the largest filter sets containa few thousand filters, however dynamic resource reservation protocols could cause filter sets to swell intothe tens of thousands. Scalability to larger table sizes is a crucial property of route lookup and packetclassification solutions; it is also a critical concern for search techniques whose performance depends uponthe number of entries in the tables.As routers achieve aggregate throughputs of trillions of bits per second, power consumption becomesan increasingly critical concern. Both the power consumed by the router itself and the infrastructure todissipate the tremendous heat generated by the router components significantly contribute to the operatingcosts. Given that each port of high-performance routers must contain route lookup and packet classificationdevices, the power consumed by search engines is becoming an increasingly important evaluation parameter. 2 Observations of Filter Set Characteristics Recent efforts to identify better packet classification techniques have focused on leveraging the character-istics of real filter sets for faster searches. While the lower bounds for the general multi-field searchingproblem have been established, observations made in recent packet classification work offer enticing newpossibilities to provide significantly better average performance.Gupta and McKeown published a number of observations regarding the characteristics of real filter setswhich have been widely cited [1]. Others have performed analyses on real filter sets and published theirobservations [12, 5, 16, 7]. The following is a distillation of observations relevant to our discussion: ã Current filter set sizes are small, ranging from tens of filters to less than 5000 filters. It is unclear if thesize limitation is “natural” or a result of the limited performance and high expense of existing packetclassification solutions. ã The protocol field is restricted to a small set of values. In most filter sets, TCP, UDP, and the wildcardare the most common specifications; other specifications include ICMP, IGMP, (E)IGRP, GRE andIPINIP. ã Transport-layer specifications vary widely. Common range specifications for port numbers such as‘gt 1023’ (greater than 1023) suggest that the use of range to prefix conversion techniques may beinefficient.4
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!