Packet Classification: Problem and Resolution

INTRODUCTION
This chapter covers the introduction to packet classification. Problems for packet classification, objectives to overcome the problem involved in packet classification, motivation to do the project on packet classification and also the organization of the project.
The development of the internet grows for every year, because of the easy access of the internet. The gain of the internet can be obtained through the smartphones, netbooks, notebooks. For processing the packets, network processor is used, and it will carry out the tasks as to convert the packets into fragments, reassembling these fragments, forwarding, encryption and packet classification. Due to increased line rates, pressure is increased on line rates and it in turn pressure on network processor. The pressure can be relieved in two ways:

By inserting more processing cores and it increases power consumption.
Increasing the clock speed, but it creates difficulty due to the physical limitation in the silicon.

So that it can be relieved in two different ways:

Insert the clock gating, which reduces the power consumption.
Insert the buffer, to form the pipelining and it also increases the speed.

1.1 PROBLEM DEFINITION

Network processors are getting more strain, due to more use of internet and the strain needs to be reduce.
To give the security for the network packets.
To minimize the power required for packet classification.
To achieve high speed and also high throughput for packet classification.

1.2 OBJECTIVES

Understood the concept of hypercut algorithm for packet classification and also analyzed the flow chart for packet classification.
Understood the verilog code and Xilinx tool.
Wrote the verilog code for hypercut algorithm.
The simulation results for hypercut algorithm is verified in Xilinx tool.
Clock gating circuit is inserted in the architecture of the classifier, it reduces the power consumption.
Pipelining concept is used in proposed architecture of the classifier and the simulation results are verified in Xilinx.

1.3 MOTIVATION
The network traffic is doubling for each six to nine months. Also traditional algorithms are not supporting the increasing network traffic on core and edge devices.

Large number of rulesets: Due to increased access of the network, the more services need to be implement in network device, so that more number of rules are needed. It creates the difficulty for classifying the packets.
Flexibility: Traditional algorithms are particularly designed for IPV4, so that novel solutions are required to manage both IPV4 and IPV6 addresses.
Scalability: As the network services are increasing, there is requirement to add or delete the rules. So that, good scalability is required for packet classification.

1.4 Organization of the thesis
The thesis contains 6 chapters
Chapter 1, it will covers the introduction of packet classification, problems involved in packet classification, objective to the packet classification and motivation for choosing the packet classification.
Chapter 2, it will covers the basics of existing packet classification and also the basics of proposed packet classification.
Chapter 3, it will covers the method used to do the packet classification, proposed architecture and also it tells how proposed architecture is better compared to previous algorithms.
Chapter 4, it discusses the simulation the simulation results obtained for existing and proposed architecture of the classifier.
Chapter 5, it covers the conclusion and future scope of the project.
Chapter 6, It lists the reference papers used for literature review of the packet classification.
Chapter 2
BASICS
It covers the basics of packet classification. It also explains the structure of packet header, brief introduction to internet, the mode of information transmission through the internet, OSI layers, the type of matching, software and hardware implementation of packet classification , Clock gating and pipelining are also discussed. It also covers the review of different packet classification algorithms, by reading this the user can select the algorithm, which is best suit for his application.

Get Help With Your Essay
If you need assistance with writing your essay, our professional essay writing service is here to help!
Essay Writing Service

The internet is a global system. It is consists of inter connected computer networks, which uses the protocols(TCP/IP), to match several billion devices all over the world. It is also termed as networks of network. Access of internet is a process of connecting mobile devices, computers and computer terminals to the internet. Internet access will enables the users to access the internet services such as email and world wide web. Using various technologies, internet service providers will access the internet. A packet is a formatted unit of data, which is carried by the packet switched network. By formatting of the data, the bandwidth of communication medium can be increased. The structure of the packet contains the two varieties of data

Control information
User data

2.1 Control information
This will provide the information, on where to send the data. Example, It provides the source and destination IP addresses, sequencing information and error codes. Fig 2.1 shows the structure of the packet

Fig 2.1 structure of the packet
2.2 Payload
The maximum size of the packet is 64 K bytes. The payload of the packet is variable. Example IPV4 typically adds the 20 bytes of payload to every packet. The packet is passed through the network using three devices such as hub, switch and router.
2.3 The modes of information transmission through the internet
2.3.1 Hub
Hub is a central device, for which all other devices are connected. It is called the star system. It is very simple, when any device sends the data, it will send the data to all other devices and all other devices needs to decide whether the data is belonging to them, if it is not belonging to them, they will ignore it. It will present in physical layer. Fig 2.3.1 shows the structure of the hub.
.
Fig 2.3.1 shows the structure of the hub
2.3.2 Switch
The switch is smarter compared to hub. First it creates the table, which records the IP/MAC addresses of the devices(PC’s) connected together. At the start, when any device sends the data, that time switch will not be knowing the destination IP addresses. So it will forwards the packets to all other devices, which are connected to it and it also records the IP address of the device. Next when packet belonging to those destination IP addresses comes, it will directly forward the packets to destination devices It is present in data link layer of OSI layer. Fig 2.3.2 shows the structure of the switch.
2.3.3 Router
It is the smartest device compared to hub and switch. The router will record the address of all the devices which are connected to it. The router will read the information present in packet header and it will decide , where the packet needs to be sent and how to process the packet. It provides the security. While in hub, switch the destination IP address is known, hacker may hack the destination device, it will consider both destination and source IP address of the devices and it will decide whether the source device is hacker or not. If it is hacker, it will deny the packet. Fig 2.3.3 shows the structure of router.

Fig 2.3.3 shows the structure of router.
2.4 OSI LAYERS
It consist of seven layer

Application layer
Presentation layer
Session layer
Transport layer
Network layer
Data link layer
Physical layer

The Fig 2.4 for OSI model is shown below as

Fig 2.4 OSI layers
Application layer: This layer will provide the interface to application programmes.
Presentation layer:

In this layer , it converts the data from system specific format to the format which is suitable for application.
It also provides encryption and compression.

Session layer:

Which facilitates the starting, managing and ending of connection between the two nodes.
Ex: For a video session, it will synchronize the related stream of data such as audio and video.

Transport layer:

It will break the data into segments
It will decide about how much information can be sent to email server and how much information can be received back.

The responsibility of transport layer are:

Reliability
Flow control
Fragmentation

Network layer:

Here the segments are broken into packets by adding the source and destination IP address to them.
Next the packets are sent to data link layer. Here router is working in this layer.

Data link layer:

In this layer, the packets are broken into the frames, which are created for the specific network.
The frames are assigned the address of two nodes, the data is moving in between.

Physical layer:

The frames given by the data link layer are converted into bits in physical medium.

UDP: User datagram protocol
It is light weight and connectionless.
Advantages:

The packet size is small.

UDP header- 8 bytes
TCP header- 20 bytes

There is no requirement to create and maintain the connection.
It has more control over the data

Disadvantages:

It does not provide error recovery.
It does not compensate for lost data packets.
Packets can arrive at out of order, so that data loses meaning.
There is no control of congestion.

Transmission control Protocol:
It is reliable and connection based.
Advantages:

It delivers the acknowledgements.
It provides retransmission.
It provides in order delivery.
It will delays the transmission when the network is busy.
It provides error recovery.

Disadvantages:

It has bigger header.
It doesn’t always get sent out quickly. It is the side effect of congestion.
It has bigger overhead.

UDP is message oriented

It sends the data in distinct chunks.

Ex: Email.

For multimedia applications, UDP is used, because of these reasons as:

It has less overhead.
Data loss can be masked.

UDP is used in small transmission.
It is also used in bandwidth intensive applications, that tolerate packet loss.

TCP is stream oriented

It can be used in continuous flow of data.

Ex: Phone conversation.

For text communication, TCP is better.

Ex: File transfers, Remote access.

TCP is used when delivery acknowledgement are needed.

In physical layer, information is transmitted in bit stream using hub. In data link layer information is transmitted in frames using switches. In network layer information is transmitted in packets using router. A router is a device that forwards the packet. A router is connected between two networks namely LAN’s or WAN’s. network processors are specialized CPU, which is optimized to support the implementation of network protocols at maximum speed. The function of network processor is to carry out the tasks such as packet separation, reassembly, encryption and classification. Packet classification is the process of categorizing the packets into flows in internet router. Packet will be classified in network layer. Packet has five fields as shown in fig

Source IP address: It indicates the IP address of the sender .
Destination IP address: It indicates the IP address of the destination.
Source port: It indicates the port number of sender.
Destination port: It indicates the port number of destination.
Protocol: Which specifies the type of transport packet being carried.

The incoming packet to router will matches the specific rule if the distinct field in the packet will match corresponding field in the rule. There are three matches

Exact match: The values present in rule field header are same as the values present in packet header.
Prefix match: The values of rule field header are prefix for header fields of the packet.
Range match: The packet header field values must be lie in the range which is specified by the rule.

2.5 The types of packet classification algorithms
Packet classification algorithm can be implemented in two major types

Software based
Hardware based

2.5.1 Software Implementation
This can be used with general purpose processor and network processor. The software based algorithm can be divided into two types as

Field dependent Algorithm
Field independent Algorithm

Field Independent Algorithm: For each field in the rule, these algorithms will build the index table separately.
Ex: RFC
Field dependent Algorithm: In these algorithm, the fields of the rule will be matched in dependent manner and there is no need to group the result in final stage. The memory requirement for these algorithms is less than field independent algorithms.
Ex: Hypercut, Hicut
2.5.2 Hardware based implementation
This is used with ASIC or with FPGA. This implementation is used with internet routers for the high speed that supports to handle the packet.
The reasons to use software implementation

Programmability: ASIC architectures has small Programming capacity, Because ASICs have special design.
Special chips: To accelerate the packet processing speed, special chips called TCAMS are used.

The proposed algorithm uses clock gating circuit to reduce power consumption and pipelining to increase the speed.
2.6 Clock gating
Clock gating is a technique, which is used in synchronous circuits to minimize the power consumption. This technique is used to prune the clock, it disables the port of the circuitary, so that flip flops present in the circuitry will not switch the states. When switching is absent, the dynamic power consumption is reduced, but the leakage currents are present. Clock gating works by taking the enable signal of the circuitry, so that flip flops or devices present in latches will not switch the states, so that switching power reduces. So it is necessary to have enable conditions in order to get benefit from clock gating. The clock gating saves the power. Clock gating can be added in two ways:

By writing the RTL code, the synthesis tool automatically translates the RTL code into clock gating logic.
In order to gate the clock of specific modules or registers manually clock gating circuit can be inserted by instantiating library the specific ICG cells.
Using automated the clock gating tools, clock gating is inserted in semi automatic fashion. These tools will insert ICG cells to RTL code or directly add the enable conditions to RTL code.

2.7 Pipelining
It is group of data processing elements, which are connected in series, so that output of one element is the input to next element. We build a pipeline by dividing the complex operation into simple operation. Here instead of taking bulk thing and executing it, the bulk thing is break up into smaller pieces and process it one after another.
For example Consider a calculation c= log(|a+b|), which consist of three operations, which are shown in fig 2.7.

Fig 2.7 Pipelining example

Add a and b to get a+b, it takes 40ns.
Take the magnitude, we get as |a+b|, it takes 35 ns.
Take the log we get as log(|a+b|), it takes 60ns.

Consider a situation when we need to carry out for 100 such pairs. Without pipelining , it would take a total of 100*135= 13500ns. By realization, it is found that it is whole sequential process. Let the values evaluated to be a1 to a100 and we need to add values to be b1 to b100.
In first evaluation, ( a1+b1)is calculated, In next evaluation, |a1+b1|,(a2+b2) is calculated, in third evaluation log|a1+b1|,|a2+b2|, ( a3+b3) is evaluated. After the first output data that is log|(a1+b1)|, the subsequent outputs are log|(a2+b2)|, log|(a3+ b3)| will now start arriving at a gap of 60ns . All the 100 inputs can be applied in 199*60=5940ns and the total time taken to evaluate 100 data will be 5940+180= 6120ns. This time is half compared without pipelining. This process of evaluation is called pipelinlng.
2.8 Literature review
Algorithms are classified in 4 classes:

Basic structures
Geometry based
Heuristics
Hardware based

2.8.1 Basic structures
a. Linear search: This algorithm[1], is very simple. It contains all the rules. Here each packet is matched opposite to all the rules until the corresponding fields of the packet should match to the rule. Although, it is simple, it is not widely used. Because, it takes the large time for matching with the rule. Consider N is the number of rules, “the worst case space and time complexity is O(N),where O is the order and N is the number of rules. Fig below shows the linear structure.

Fig 2.8.1.a Linear search algorithm
b. Hierarchial trie: It is an extension part of the binary trie. By using the individual bits of the search key, the branches of the trie can be traversed. In the d dimensional hierarchial trie[2], first bulid the one dimensional hierarchial trie which is called F1 trie. Foe each prefix P in the F1 trie, there is a recursively (d-1) dimensional hierarchial tries are present(Tp). For example, if the data structure is 2 dimensional the only one F1 trie is present. Hierarchial tries are also termed as multilevel tries or backtracking tries or tries of trie.