Biblio

As the core infrastructure of cloud data operation, exchange and storage, data centerneeds to ensure its security and reliability, which are the important prerequisites for the development of cloud computing. Due to various illegal accesses, attacks, viruses and other security threats, it is necessary to protect the boundary of cloud data center through security gateway. Since the traffic growing up to gigabyte level, the secure gateway must ensure high transmission efficiency and different network services to support the cloud services. In addition, data center is gradually evolving from IPv4 to IPv6 due to excessive consumption of IP addresses. Packet classification algorithm, which can divide packets into different specific streams, is very important for QoS, real-time data stream application and firewall. Therefore, it is necessary to design a high performance IPv6 packet classification algorithm suitable for security gateway.AsIPv6 has a128-bitIP address and a different packet structure compared with IPv4, the traditional IPv4 packet classification algorithm is not suitable properly for IPv6 situations. This paper proposes a fast packet classification algorithm for IPv6 - PCHA (packet classification based on hash andAdelson-Velsky-Landis Tree). It adopts the three flow classification fields of source IPaddress(SA), destination IPaddress(DA) and flow label(FL) in the IPv6 packet defined by RFC3697 to implement fast three-tuple matching of IPv6 packet. It is through hash matching of variable length IPv6 address and tree matching of shorter flow label. Analysis and testing show that the algorithm has a time complexity close to O(1) in the acceptable range of space complexity, which meets the requirements of fast classification of IPv6 packetsand can adapt well to the changes in the size of rule sets, supporting fast preprocessing of rule sets. Our algorithm supports the storage of 500,000 3-tuple rules on the gateway device and can maintain 75% of the performance of throughput for small packets of 78 bytes.

Packet classification is used to determine the behavior of incoming packets to network devices. Because it is achieved using a linear search on a classification rule list, a larger number of rules leads to a longer communication latency. To decrease this latency, the problem is generalized as Optimal Rule Ordering (ORO), which aims to identify the order of rules that minimizes the classification latency caused by packet classification while preserving the classification policy. Because ORO is known to be NP-complete by Hamed and Al-Shaer [Dynamic rule-ordering optimization for high-speed firewall filtering, ASIACCS (2006) 332-342], various heuristics for ORO have been proposed. Sub-graph merging (SGM) by Tapdiya and Fulp [Towards optimal firewall rule ordering utilizing directed acyclical graphs, ICCCN (2009) 1-6] is the state of the art heuristic algorithm for ORO. In this paper, we propose a novel heuristic method for ORO. Although most heuristics try to recursively determine the maximum-weight rule and move it as far as possible to an upper position, our algorithm pairs rules that cause policy violations until there are no such rules to simply sort the rules by these weights. Our algorithm markedly decreases the classification latency and reordering time compared with SGM in experiments. The sets consisting of thousands of rules that require one or more hours for reordering by SGM can be reordered by the proposed method within one minute.

Due to improving computational capacity of supercomputers, transmitting encrypted packets via one single network path is vulnerable to brute-force attacks. The versatile attackers secretly eavesdrop all the packets, classify packets into different streams, performs an exhaustive search for the decryption key, and extract sensitive personal information from the streams. However, new Internet Protocol (IP) brings great opportunities and challenges for preventing eavesdropping attacks. In this paper, we propose a Programming Protocol-independent Packet Processors (P4) based Network Immune Scheme (P4NIS) against the eavesdropping attacks. Specifically, P4NIS is equipped with three lines of defense to improve the network immunity. The first line is promiscuous forwarding by splitting all the traffic packets in different network paths disorderly. Complementally, the second line encrypts transmission port fields of the packets using diverse encryption algorithms. The encryption could distribute traffic packets from one stream into different streams, and disturb eavesdroppers to classify them correctly. Besides, P4NIS inherits the advantages from the existing encryption-based countermeasures which is the third line of defense. Using a paradigm of programmable data planes-P4, we implement P4NIS and evaluate its performances. Experimental results show that P4NIS can increase difficulties of eavesdropping significantly, and increase transmission throughput by 31.7% compared with state-of-the-art mechanisms.

The emergence of integrated space-ground network (ISGN), with more complex network conditions compared with tradition network, requires packet classification to achieve high performance. Packet classification plays an important role in the field of network security. Although several existing classification schemes have been proposed recently to improve classification performance, the performance of these schemes is unable to meet the high-speed packet classification requirement in ISGN. To tackle this problem, a hybrid packet classification algorithm based on hash table and geometric space partition (HGSP) is proposed in this paper. HGSP falls into two sections: geometric space partition and hash matching. To improve the classification speed under the same accuracy, a parallel structure of hash table is designed to match the huge packets for classifying. The experimental results demonstrate that the matching time of HGSP algorithm is reduced by 40%-70% compared with traditional Hicuts algorithm. Particularly, with the growth of ruleset, the advantage of HGSP algorithm will become more obvious.

Deep packet inspection (DPI) is a critical component to prevent intrusion detection. This requires a detailed analysis of each network packet header and body. Although this is often done on dedicated high-power servers in most networked systems, mobile systems could potentially be vulnerable to attack if utilized on an unprotected network. In this case, having DPI hardware on the mobile system would be highly beneficial. Unfortunately, DPI hardware is generally area and power consuming, making its implementation difficult in mobile systems. We developed a memristor crossbar-based approach, inspired by memristor crossbar neuromorphic circuits, for a low-power, low-area, and high-throughput DPI system that examines both the header and body of a packet. Two key types of circuits are presented: static pattern matching and regular expression circuits. This system is able to reduce execution time and power consumption due to its high-density grid and massive parallelism. Independent searches are performed using low-power memristor crossbar arrays giving rise to a throughput of 160Gbps with no loss in the classification accuracy.

Packet classification is a core function in network and security systems; hence, hardware-based solutions, such as packet classification accelerator chips or Ternary Content Addressable Memory (T-CAM), have been widely adopted for high-performance systems. With the rapid improvement of general hardware architectures and growing popularity of multi-core multi-threaded processors, software-based packet classification algorithms are attracting considerable attention, owing to their high flexibility in satisfying various industrial requirements for security and network systems. For high classification speed, these algorithms internally use large tables, whose size increases exponentially with the ruleset size; consequently, they cannot be used with a large rulesets. To overcome this problem, we propose a new software-based packet classification algorithm that simultaneously supports high scalability and fast classification performance by merging partition decision trees in a search table. While most partitioning-based packet classification algorithms show good scalability at the cost of low classification speed, our algorithm shows very high classification speed, irrespective of the number of rules, with small tables and short table building time. Our test results confirm that the proposed algorithm enables network and security systems to support heavy traffic in the most effective manner.

Concise is a Forwarding information base (FIB) design that uses very little memory to support fast query of a large number of dynamic network names or flow IDs. Concise makes use of minimal perfect hashing and the SDN framework to design and implement the data structure, protocols, and system. Experimental results show that Concise uses significantly smaller memory to achieve faster query speed compared to existing FIB solutions and it can be updated very efficiently.

The key challenge to a datacenter network is its scalability to handle many customers and their applications. In a datacenter network, packet classification plays an important role in supporting various network services. Previous algorithms store classification rules with the same length combinations in a hash table to simplify the search procedure. The search performance of hash-based algorithms is tied to the number of hash tables. To achieve fast and scalable packet classification, we propose an algorithm, encoded rule expansion, to transform rules into an equivalent set of rules with fewer distinct length combinations, without affecting the classification results. The new algorithm can minimize the storage penalty of transformation and achieve a short search time. In addition, the scheme supports fast incremental updates. Our simulation results show that more than 90% hash tables can be eliminated. The reduction of length combinations leads to an improvement on speed performance of packet classification by an order of magnitude. The results also show that the software implementation of our scheme without using any hardware parallelism can support up to one thousand customer VLANs and one million rules, where each rule consumes less than 60 bytes and each packet classification can be accomplished under 50 memory accesses.
 

The emergence of new network applications, such as the network intrusion detection system and packet-level accounting, requires packet classification to report all matched rules instead of only the best matched rule. Although several schemes have been proposed recently to address the multimatch packet classification problem, most of them require either huge memory or expensive ternary content addressable memory (TCAM) to store the intermediate data structure, or they suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multimatch packet classification from the complicated multidimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree across multiple hash tables at different stages, the pipeline can achieve a high throughput via the interstage parallel access to hash tables. To exploit further intrastage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables. To avoid collisions involved in hash table lookup, a hybrid perfect hash table construction scheme is proposed. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCuts and B2PC schemes in classification speed by at least one order of magnitude, while having a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 26.8 and 93.1 Gb/s using perfect hash tables.