快速数据包分流算法研究

基于“流”的数据包分类算法已经在第四层交换等领域中得到了应用,该类算法的特点是流表的容量大,流表的更新速度较快.“快速的数据包分流算法”采用了散列算法的基本思想,并引入了流的局部性原理来加速散列查找的过程,用软件对该算法进行了仿真测试,并在最后从时间复杂度和空间复杂度两个方面对其进行了性能分析.实验结果表明,该算法具有良好的时间复杂度和空间复杂度,可以实现快速的分流.     

Session level flow classification by packet size distribution and session grouping

Classifying traffic into specific network applications is essential for application-aware network management and it becomes more challenging because modern applications complicate their network behaviors. While port number-based classifiers work only for some well-known applications and signature-based classifiers are not applicable to encrypted packet payloads, researchers tend to classify network traffic based on behaviors observed in network applications. In this paper, a session level flow classification (SLFC) approach is proposed to classify network flows as a session, which comprises of flows in the same conversation. SLFC first classifies flows into the corresponding applications by packet size distribution (PSD) and then groups flows as sessions by port locality. With PSD, each flow is transformed into a set of points in a two-dimension space and the distances between each flow and the representatives of pre-selected applications are computed. The flow is recognized as the application having a minimum distance. Meanwhile, port locality is used to group flows as sessions because an application often uses consecutive port numbers within a session. If flows of a session are classified into different applications, an arbitration algorithm is invoked to make the correction. The evaluation shows that SLFC achieves high accuracy rates on both flow and session classifications, say 99.9% and 99.98%, respectively. When SLFC is applied to online classification, it is able to make decisions quickly by checking at most 300 packets for long-lasting flows. Based on our test data, an average of 72% of packets in long-lasting flows can be skipped without reducing the classification accuracy rates.     

基于网络处理器的高速包分类机制设计

三元按内容寻址寄存器(TCAM)是内容寻址存储器(CAM)的一种变形,较CAM而言可以使查找更加灵活,对其工作（如包处理）效率的提高也起着极大的优化作用。文章从TCAM的原理及结构特点出发,阐述了其适用于提高NP性能的原因,通过一个设计实例说明了采用TCAM协处理器在网络处理器中加速包处理过程的方法和技术。     

一种数值属性的深度置信网络分类方法

深度置信网络是个包含多个受限玻尔兹曼机的深层架构。针对深度置信网络分类时由于受限玻尔兹曼机的输入一般是二值向量而造成的信息的丢失从而使分类效果降低的问题,提出了通过在sigmoid单元中增加噪声来将输入缩放到[0,1]区间,使用带有一个高斯隐藏节点的顶层受限玻尔兹曼机实现分类功能的一种数值属性深度置信网络分类方法。深度置信网络和受限玻尔兹曼机可以作为特征提取方法也可以认为是带有训练的初始权值的神经网络。由于连接权值的初始化而不仅仅是神经网络的随机权值,深度置信网络分类应该比原有的传统的神经网络分类拥有更好的性能。在UCI的多个数据集上进行对比验证,实验结果表明深度置信网络分类方法比传统的SVM算法拥有更高的准确性。     

Fast and scalable conflict detection for packet classifiers

Packet filters provide rules for classifying packets based on header fields. High speed packet classification has received much study. However, the twin problems of fast updates and fast conflict detection have not received much attention. A conflict occurs when two classifiers overlap, potentially creating ambiguity for packets that match both filters. For example, if Rule 1 specifies that all packets going to CNN be rate controlled and Rule 2 specifies that all packets coming from Walmart be given high priority, the rules conflict for traffic from Walmart to CNN. There has been prior work on efficient conflict detection for two-dimensional classifiers. However, the best known algorithm for conflict detection for general classifiers is the naive O(N²) algorithm of comparing each pair of rules for a conflict. In this paper, we describe an efficient and scalable conflict detection algorithm for the general case that is significantly faster. For example, for a database of 20 000 rules, our algorithm is 40 times faster than the naive implementation. Even without considering conflicts, our algorithm also provides a packet classifier with fast updates and fast lookups that can be used for stateful packet filtering.     

网络处理器中传递包编辑命令的一种新方法

在多进程工作方式下，针对网络处理器中传递包编辑命令所采用的串行处理方式存在着传输效率低下的严重缺陷。本文提出了一种新型的快速并行传递命令的硬件实现方案。这种机制使得在网络处理器的包编辑器和包编辑命令发生器之间传递包编辑命令的效率得到了大幅度的提高。这对于实际网络处理器的设计有很重要的参考价值。     

LIPS: A lightweight permit system for packet source origin accountability

One of key security issues on the current Internet is unwanted traffic, the forerunner of unauthorized accesses, scans, and attacks. It is vitally important but extremely challenging to fight such unwanted traffic. We need a series of defensive mechanisms to identify unwanted packets, filter them out, and further defeat their associated attacks. In this paper, we propose a lightweight, scalable packet authentication mechanism, named Lightweight Internet Permit System (LIPS), as a first line of defense to effectively filter out the most common forms of unwanted traffic, spoofed and unsolicited packets, such that in-depth security schemes can take care of the remaining issues more efficiently. LIPS is a simple extension of IP, in which each packet carries an access permit issued by its destination host or gateway, and the destination verifies the access permit to determine to accept or drop the packet. LIPS provides preliminary traffic-origin accountability that supports two salient features to confine unwanted traffic: (1) filter out the most common forms of unwanted packets and defeat associated attacks; (2) help us identify compromised hosts/domains such that we are able to build active defense schemes to deal with various attacks through real-time inter-domain collaboration. In this paper, we first present the design and prototype implementation of LIPS on Linux 2.4 kernel, and then use analysis, simulations, and experiments to demonstrate the efficacy of LIPS in protecting critical resources with light overheads.     

NP防火墙协议栈驱动模块的设计与实现

彻底打通网络处理器光口到本地协议栈间通路需要协议栈驱动提供支持。针对协议栈驱动基本组成和内在驱动机制,同时确保遵循Intel IXA软件架构分层设计原则,该文提出了在Linux平台上的实现方案并进行了分析,指出了实现过程中牵涉的关键技术。Enp2611评估板上硬件光口打通测试表明设计达到了预先要求。     

A robust packet scheduling algorithm for proportional delay differentiation services

Proportional delay differentiation (PDD) model is an important approach to relative differentiated services provisioning on the Internet. It aims to maintain pre-specified packet queueing-delay ratios between different classes of traffic at each hop. Existing PDD packet scheduling algorithms are able to achieve the goal in long time-scales when the system is highly utilized. This paper presents a new PDD scheduling algorithm, called Little’s average delay (LAD), based on a proof of Little’s Law. It monitors the arrival rate of the packets in each traffic class and the cumulative delays of the packets and schedules the packet according to their transient queueing properties in order to achieve the desired class delay ratios in both short and long time-scales. Simulation results show that LAD is able to provide predictable and controllable services in various system conditions and that such services, whenever feasible, can be guaranteed, independent of the distributions of packet arrivals and sizes. In comparison with other PDD scheduling algorithms, LAD can provide the same level of service quality in long time-scales and more accurate and robust control over the delay ratio in short time-scales. In particular, LAD outperforms its main competitors significantly when the desired delay ratio is large.     

Reliability improvement in private non-uniform cache architecture using two enhanced structures for coherence protocols and replacement policies

In this paper, a comprehensive study is first conducted to investigate the effects of cache coherence protocols and cache replacement policies on the characteristics of NUCA in current many-core processors. The main focus of this study is to analyze the effects of coherence protocols and replacement policies on the vulnerability of caches. The outcomes of this analysis indicate two facts: (i) Differences in handling write operations play an important role to make distinction in favor of or against a cache coherence protocol; (ii) Near-optimal solutions for replacement problem, aimed at enhancing the performance, can also make positive influence on reduction of cache vulnerability factor. Based on the results of first step, two schemes are introduced to enhance the reliability of caches by applying some modification on the structures of cache coherence protocols and cache replacement policies. The first scheme tries to manage sharing of the dirty data items among different same-level caches. The second helps to give priority and more opportunity to old dirty blocks than clean blocks for replacement. The proposed schemes reveal about 18% improvement in MTTF, with negligible performance, bandwidth and energy consumption overhead compared to previous cache structures.     

密码嵌入式处理器中高速缓存的研究与设计

为了提高密码嵌入式处理器的运行效率,给出了一种哈佛结构的高速缓存(Cache)设计,包括指令Cache(iCache)和数据Cache(dCache)。采用双端口RAM和较低的硬件开销设计了标签存储器和指令/数据存储器,并描述了iCache和dCache控制流程。实现时配置iCache容量为4KB、dCache容量为8KB,并完成了向密码嵌入式处理器的集成。FPGA验证结果表明其满足处理器的应用要求;性能分析结果表明,采用Cache比处理器直接访问主存在速度上至少提高5.26倍。     

A new algorithm for packet routing problems using chaotic neurodynamics and its surrogate analysis

We propose a new algorithm for routing packets which effectively avoids packet congestion in computer networks. The algorithm involves chaotic neurodynamics. To realize effective packet routing, we first composed a basic method by a neural network, which routes packets with shortest path information between two nodes in the computer network. When the computer network has an irregular topology, the basic routing method does not work well, because most of packets cannot be transmitted to their destinations due to packet congestion in the computer network. To avoid such an undesirable problem, we employed chaotic neurodynamics to extend the basic method. Numerical experiments show that our proposed method exhibits good performance for scale-free networks. We also analyze why the proposed routing method is effective, comparing the proposed method with several stochastic methods. We introduced the method of surrogate data, a statistical hypothesis testing which is often used in the field of nonlinear time-series analysis. Analysis of the proposed method by the method of surrogate data reveals that the chaotic neurodynamics is most effective to decentralize the packet congestion in the computer network.     

A lightweight mechanism for detection of cache pollution attacks in Named Data Networking

Content-Centric Networking (CCN) is an emerging paradigm being considered as a possible replacement for the current IP-based host-centric Internet infrastructure. In CCN, named content – rather than addressable hosts – becomes a first-class entity. Content is therefore decoupled from its location. This allows, among other things, the implementation of ubiquitous caching.     

Victim retention for reducing cache misses in tiled chip multiprocessors

This paper presents CMP-VR (Chip-Multiprocessor with Victim Retention), an approach to improve cache performance by reducing the number of off-chip memory accesses. The objective of this approach is to retain the chosen victim cache blocks on the chip for the longest possible time. It may be possible that some sets of the CMPs last level cache (LLC) are heavily used, while certain others are not. In CMP-VR, some number of ways from every set are used as reserved storage. It allows a victim block from a heavily used set to be stored into the reserve space of another set. In this way the load of heavily used sets are distributed among the underused sets. This logically increases the associativity of the heavily used sets without increasing the actual associativity and size of the cache. Experimental evaluation using full-system simulation shows that CMP-VR has less off-chip miss-rate as compared to baseline Tiled CMP. Results are presented for different cache sizes and associativity for CMP-VR and baseline configuration. The best improvements obtained are 45.5% and 14% in terms of miss rate and cycles per instruction (CPI) respectively for a 4 MB, 4-way set associative LLC. Reduction in CPI and miss rate together guarantees performance improvement.     

A cache invalidation scheme for continuous partial match queries in mobile computing environments

The continuous partial match query is a partial match query whose result remains consistently in the client’s memory. Conventional cache invalidation methods for mobile clients are record ID-based. However, since the partial match query uses content-based retrieval, the conventional ID-based approaches cannot efficiently manage the cache consistency of mobile clients. In this paper, we propose a predicate-based cache invalidation scheme for continuous partial match queries in mobile computing environments. We represent the cache state of a mobile client as a predicate, and also construct a cache invalidation report (CIR), which the server broadcasts to clients for cache management, with predicates. In order to reduce the amount of information that is needed for cache management, we propose a set of methods for CIR construction (in the server) and identification of invalidated data (in the client). Through experiments, we show that the predicate-based approach is very effective for the cache management of mobile clients.     

Compensation for control packet dropout in networked control systems

With the integration of communication networks and distributed control in modern manufacturing and process industries, networked control systems (NCSs) are becoming increasingly important due to its simplicity, scalability, flexibility, and cost effectiveness. However, there are still significant technical barriers that limit the applications of NCS technologies. Two challenges are network-induced time delay and data packet dropout. Applying a real-time queuing protocol that we developed recently, we are able to limit the sum of the network-induced communication delay and the control computation delay within a control period. This one-period delay is further guaranteed by well designed compensation for control packet dropout. Then, this paper proposes to compensate for the control packet dropout at the actuator using past control signals. Three model-free strategies for control packet dropout compensation, namely, PD (proportional plus derivative), PD2 (proportional plus up to the second-order derivative), and PD3 (proportional plus up to the third-order derivative) are developed. They are suitable for a large number of NCSs without the need to tune the compensator parameters. The proposed dropout compensation schemes are demonstrated through numerical examples.     

一种用于大规模图像分类的可扩展学习算法

随着大规模图像分类数据集的出现,设计一种可扩展的、高效的多类分类算法成为目前一个重要的挑战。基于迹范数正则惩罚函数,提出了一种新的大规模多类图像分类的可扩展学习算法。把具有挑战性的非光滑优化问题重构为一个带l1正则惩罚的无穷维优化问题,进而设计了一个简单而有效的加速坐标下降算法。展示了如何在量化的密集视觉特征的压缩域中进行高效的矩阵计算,该压缩域有100000个例子,1000多维特征和100多类图片。在图像网的子集“Fungeus”,“Ungulate”和“Vehicles”上的实验结果表明,提出方法的性能明显优于目前最先进的16高斯Fisher向量方法。     

Deadline guaranteed packet scheduling for overloaded traffic in input-queued switches

Many applications need to solve the deadline guaranteed packet scheduling problem. However, it is a very difficult problem if three or more deadlines are present in a set of packets to be scheduled. The traditional approach to dealing with this problem is to use EDF (Earliest Deadline First) or similar methods. Recently, a non-EDF based algorithm was proposed that constantly produces a higher throughput than EDF-based algorithms by repeatedly finding an optimal scheduling for two classes. However, this new method requires the two classes be non-overloaded, which greatly restricts its applications. Since the overloaded situation is not avoidable from one iteration to the next in dealing with multiple classes, it is compelling to answer the open question: Can we find an optimal schedule for two overloaded classes efficiently? This paper first proves that this problem is NP-complete. Then, this paper proposes an optimal preprocessing algorithm that guarantees to drop a minimum number of packets from the two classes such that the remaining set is non-overloaded. This result directly improves on the new method.     

基于超曲面的分类算法研究进展

综述了基于超曲面的分类算法，该算法通过区域合并计算获得多个超平面组成的双侧闭曲面作为分类超曲面对空间进行划分．分类超曲面可以有效地解决在有限连通区域分布很复杂的非线性数据多类分类问题，分析了算法准确率与极小样本集的关系，总结了已有成就和最新进展，指出了基于超曲面的分类算法进一步发展的方向．