Packet Classification Tuple Space Search Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Routers classify packets to determine which flow they belong to and to decide what service they should receive. Various researches have been proposed for packet classification based on the category such as a basic search algorithms, heuristic algorithms, hardware-specific search algorithms, or geometric algorithms. Packet classification is needed for firewalls and quality of service to distinguish and isolate traffic in different flows for suitable processing.

In this project, we describe tuple space search algorithm for multi-field packet classification. Tuples in the filter set is partitioned into different tuple groups based on the tuple specification. Each tuple group can perform packet classification based on the predefined rule set. A pipeline mapping scheme is carefully designed to maximize the memory utilization and improve the performance of the multi-field packet classification.

Index Terms--Packet classification, tuple space search,SRAM, pipeline, firewall.

INTRODUCTION

The internet is comprised of a mesh of routers interconnected by links. Communication among nodes on the Internet takes place using the Internet Protocol, commonly known as IP. IP datagram's (packets) travel over links from one router to the next on their way towards their final destination. Each router performs a forwarding decision on incoming packets to determine the packet's next-hop router.

The capability to forward packets is a requirement for every IP router. Additionally, an IP router may also choose to perform special processing on incoming packets. Examples of special processing include filtering packets for security reasons, delivering packets according to a pre-agreed delay guarantee, treating high priority packets preferentially, and maintaining statistics on the number of packets sent by different networks. Such special processing requires that the router classify incoming packets into one of several flows- all packets of a flow obey a pre-defined rule and are processed in a similar manner by the router. For example, all packets with the same source IP address may be defined to form a flow. A flow could also be defined by specific values of the destination IP address and by specific protocol values.

Routers are now called upon to provide different qualities of service to different applications which means routers need new mechanisms such as admission control, resource reservation, per-flow queuing, and fair scheduling. All of these mechanisms require the router to distinguish packets belonging to different flows. Flows are specified by rules applied to incoming packets. We call a collection of rules a classifier. Each rule specifies a flow that a packet may belong to base on some criteria applied to the packet header, as shown in Table I

TABLE I

SOME OF THE PACKET HEADER FIELDS

PAYLOAD

L4-SP

16b

L4-DP

16b

L4-PROT

8b

L3-SA

32b

L3-DA

32b

L3-PROT

8b

L2-SA

48b

L2-DA

48b

L2=Layer 2(e.g. Ethernet) DA=Destination Address

L3= Layer 3(e.g. IP) SA=Source Address

L4= Layer 4(e.g. TCP) PROT=Protocol

SP=Source Port

DP=Destination Port

In order to provide differentiated services, routers require additional mechanisms. The mechanisms such as admission control, conditioning (metering, marking, shaping, and policing), resource reservation (optional),queue management and fair scheduling (such as weighted fair queuing)require, the capability to distinguish and isolate traffic belonging to different users based on service agreements negotiated between the ISP and its customer. This has led to demand for flow-aware routers that negotiate these service agreements, express them in terms of rules or policies configured on incoming packets, and isolate incoming traffic according to these rules [3].

Flows are specified by rules applied to incoming packets. We call a collection of rules a classifier. Each rule specifies a flow that a packet may belong to based on some criteria applied to the packet header. The rules classify which flow a packet belongs to base on the contents of the packet header(s) [4]. For example, a flow could be defined by particular values of source and destination IP addresses, and by particular transport port numbers. Or a flow could be simply defined by a destination prefix and a range of port values. As we shall see, a number of different types of rules are used in practice. This project describes a method for fast packet classification based on an almost arbitrary set of rules. We focus here only on the problem of identifying the class to which a packet belongs.

TUPLE SPACE SEARCH

The tuple space search algorithm is a hash-based algorithm. A tuple is defined as a vector of k lengths, where k is the number of fields in a filter. For example, in a 5-field filter set, the tuple [7, 12, 8, 0, 16] means the length of the source IP address prefix is 7, the length of the destination IP address prefix is 12, the length of the protocol prefix is 8 (an exact protocol value), the length of the source port prefix is 0 (wildcard or "don't care"), and the length of the destination port prefix is 16 (an exact port value).

We can partition the filters in a filter set to the different tuple groups. Since the filters in a same tuple group have the same tuple specification, they are mutual exclusive and none of them overlaps with others in this tuple group. Now we can perform the packet classification across all the tuples to find the best matched filter. If multiple tuple groups report matches, we resolve the best matched filter by comparing their priorities.

The filters in a tuple can be easily organized into a hash table, where we use the tuple specification to extract the proper number of bits from each field as the hash key. Assume there is no hash collision in the hash tables. One memory access can determine if there is a matched filter in a hash table so the lookup performance is only determined by the number of tuple specifications. If the hash tables are properly implemented, this algorithm gives an excellent storage performance, which is linear to the filter set size.

Typically, a filter has its port fields specified as ranges, which cannot be mapped to the tuple definition directly. The projects suggest encoding the ranges based on the nesting levels. We resolve this by converting the range specification to prefixes. Although this will result in an expanded filter set and more tuples, it avoids the necessity to decode the port range ID, which is often implemented by a direct lookup table with 64K entries.

TABLE II

LIST OF PACKET HEADER FIELD

Header field

Notation

# of bits

Ingress port

Variable

Source Ethernet address

Eth src

48

Destination Ethernet address

Eth dst

48

Ethernet type

Eth type

16

VLAN ID

12

VLAN Priority

3

Source IP address

SA

32

Destination IP address

DA

32

IP Protocol

Prtl

8

IP Type of Service

ToS

6

Source port

SP

16

Destination port

DP

16

In 5-tuple packet classification, an IP packet is usually classified based on the 5 fields in the packet header: the 32-bit source/destination IP addresses (denoted SA/DA), 16-bit source/ destination port numbers (denoted SP/DP), and 8-bit transport layer protocol. Individual entries for classifying a packet are called rules. Each rule can have one or more fields and their associated values, a priority, and an action to be taken if matched.

Different fields in a rule require different kinds of matches: prefix match for SA/DA, range match for SP/DP, and exact match for the protocol field. Table 2.2 shows a simplified example, where each rule contains match conditions for 5 fields: 8-bit source and destination addresses (SA/DA), 4-bit source and destination port numbers (SP/DP), and a 2-bit protocol value.

TABLE III

TUPLE RULE SET

Rule

SA

DA

SP

DP

Protocol

R1

*

*

2-9

6-11

*

R2

1*

0*

3-8

1-4

0x0812

R3

0*

0110*

9-12

10-13

0x0813

R4

011*

11*

1-4

9-15

0x0814

R5

0*

11*

11-14

4-8

*

R6

011*

11*

1-4

4-15

0x0812

R7

110*

00*

1-15

5-6

0x0815

R8

110*

0110*

0-15

5-6

*

R9

*

*

2-9

6-11

0x0812

R10

1*

0*

3-8

1-4

*

R11

011*

0110*

9-12

10-13

0x0813

R12

011*

11*

1-4

9-15

0x0816

R13

0*

11*

11-14

4-8

0x0814

R14

011*

11*

1-4

4-15

*

R15

110*

00*

1-15

5-6

0x0812

R16

110*

0110*

1-15

5-6

0x0815

R17

111*

0110*

0-15

7-9

*

R18

111*

00*

1-15

4-9

0x0812

R19

0*

0110*

9-12

10-13

*

R20

011*

110*

3-8

9-15

0x0816

R21

0110*

11*

11-14

4-8

0x0814

R22

011*

11*

1-4

4-15

0x0814

R23

110*

00*

4-15

5-6

0x0817

R24

1100*

0110*

1-15

5-6

0x0815

The basic Tuple Space Search technique introduced by Srinivasan, Suri, and Varghese performs an exhaustive search of the tuple space. For our example filter set in Table 2.3, a search would have to probe seven tuples instead of searching all 12 filters. Using a modest set of real filter sets, the authors found that tuple space search reduced the number of searches by a factor of four to seven relative to an exhaustive search over the set of filters6. The basic technique can provide adequate performance for large filter sets given favorable filter set properties and a massively parallel implementation.

TABLE IV

EXAMPLE FILTER SET ADDRESS FIELDS ARE 4-BITS AND PORT RANGES COVER 4-BIT PORT NUMBERS.

Motivated by the observation that no address has more than six matching prefixes in backbone route tables, the authors introduced techniques to limit the number of tuples that need to be searched exhaustively. Pruned tuple space search reduces the scope of the exhaustive search by performing searches on individual filter fields to find a subset ofcandidate tuples. While any field or combinations of fields may be used for pruning, the authors found that pruning on the source and destination address strikes a favorable balance between the reduction in candidate tuples and overhead for the pruning steps [13]. We provide an example of pruning on the source and destination addresses in Figure 1. In this case, we begin by constructing tries for the source and destination address prefixes in the filter set in Table IV. Nodes representing valid prefixes store a list of tuples containing filters that specify the prefix 7.

Figure 1 An example of pruning on the source and destination addresses.

We begin a Pruned Tuple Space Search byperforming independent search of the source and destination tries. The result of each search is a list of all possible candidate tuples for each field. In order to construct the list of candidate tuples for the packet, we compute the intersection of the tuple lists returned by each search. The key difference is that Pruned Tuple Space Search computes the candidate tuples rather than the overlapping filters. We demonstrate pruning for a packet with source address 1001 and destination address 1101. In this case, we only have to probe two tuples instead of seven in the basic search. Using a modest set of real filter sets, the authors found that Pruned Tuple Space Search reduced the number of searches by a factor of three to five relative to the basic Tuple Space Search, and a factor of 13 to 26 relative to an exhaustive search over the set of filters.

Simulation Results

We conducted extensive experiments to evaluate the performance of our schemes including the algorithms and FPGA prototype of the architecture for both 5-tuple and next generation 12-tuple packet classification problems. Due to the lack of large-scale real-life OpenFlow rule sets, we generated synthetic 5-tuple partitioning rules to examine the effectiveness of our TSS based schemes for next generation packet classification.

Figure 2 Classification of first packet

Each rule was composed of 5 header fields that follow the current rule set partitioning algorithm as shown in the Figure 2.

We used 48 bit source/destination address, 16 bit source/ destination port, Ethernet type and randomly set each field value. Concretely, we generated each rule as follows.

Each field is randomly set as a wildcard. When the field is not set as a wildcard, the following steps are executed.

For source/destination IP address fields, the prefix length is set randomly from between 1 and 48, and then the value is set randomly from its possible values as shown in the Figure 3.2.

For other fields, the value is set randomly from its possible values.

In these report, we set rule list of size 24, which was optimal according to a series of tests where we found that a larger list size resulted in lower memory requirement. The memory reduction became unremarkable when list size >8 our algorithm kept the memory requirement to be linear with the number of rules, and thus achieved much better scalability than the original HyperCuts algorithm.

Figure 3 Classification of second packet

As the Figure 2 and Figure 3 satisfies the rule set partitioning algorithm, the packets shall be understand by our engine at the lower level and the system will give detail of the received packet. If the incoming packet does not satisfy the rule set, then it blocks the corresponding packets. Hence it shows source/destination address and Ethernet type fields as zero.

CONCLUSION

This project introduced novel tuple space search based architecture on FPGAs for wire speed multifield packet classification. We considered the next generation packet classification problems where more than 5-tuple packet header fields would be classified. Several optimization techniques were proposed to reduce the memory requirement of the packet classification algorithm, so that 10K 5-tuple rules or 1K 12-tuple rules could fit in the on-chip memory of a single FPGA. Our architecture provided on-the-fly reconfiguration due to the linear memory based architecture. Extensive simulation and FPGA implementation results demonstrate the effectiveness of our solution. The FPGA design supports 10K 5-tuple rules or 1K OpenFlow like complex rules and sustains over 40 Gbps throughput for minimum size (40 bytes) packets.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.