多维IP包分类算法研究

IP包分类算法是应用在路由器数据平面的核心算法,其中一维的IP包分类算法就是路由地址查找算法,为路由器的基本转发功能提供支持,与此对应的多维的IP包分类算法是为支持第4层交换的路由器提供对IP数据报的分类,使路由器能对每一个特定的数据报作出预先定义好的处理,以便为了新的网络应用提供数据包过滤、防火墙、基于策略的路由、区分服务、QoS、流量计费等功能。本文介绍了两种典型的多维IP包分类算法在国内外研究现状及综述研究。     

一种基于跳转表的多维IP分类算法

网络应用的发展要求路由器必须有能力支持防火墙、提供QoS、流量计费等一系列功能,这些功能都要求路由器对IP包进行分类来完成对数据包的不同处理,本文提出的算法直接从多维IP分别问题入手,经过一个跳转表,把多维IP分类问题转化为二维的IP分类问题,从而提高了分类速度,该算法可以充分发挥二维分类算法高效率的特点,从而可以极大地提高多维分类的速度。     

一种适用于多维的快速IP分类算法

网络应用的发展要求路由器必须有能力支持防火墙、提供QoS、流量计费等一系列功能,这些功能都要求路由器对IP包进行分类以完成对数据包的不同处理.在Grid of Tries算法的基础上,提出了一种新的IP分类算法.该算法不仅克服了Grid of Tries算法在多维IP分类方面的局限性,而且在时间和空间性能上都优于Grid ofTries,是目前综合性能比较好的分类算法.     

一种用于大规模规则库的快速包分类算法

网络应用的发展，要求路由器必须有能力支持防火墙、入侵检测、提供QoS、流量计费等一系列功能，这些功能都要求路由器对IP包进行分类来完成对数据包的不同处理。目前的包分类算法不适用于火规模的规则数据库。该文在现有的一种基于位串的包分类算法上做了两个改进，位串的聚合和过滤规则的重排列。从而生成了一种新的包分类机制-AVA（Aggregated Bit Vector).通过评测可看出这种新的算法可以很好地应用在大规模规则数据库上，性能比原先有很大提升。     

基于Hash_tree的多维IP包分类算法

随着各种网络应用的发展,路由器必须能够快速完成对IP数据包的分类,以支持如防火墙、QoS等服务。文章分析了多维IP包分类中Hash算法的应用,在此基础上提出了一种基于Hash_tree的多维IP包分类算法。该算法充分发挥了Hash函数查找快速的特点,对IP数据包的分类能够以T位的线速进行处理,同时算法还具有支持较大的匹配规则集、支持增量更新等特点。     

高性能网包分类理论与算法综述

随着IP网络架构的不断演进以及网络业务和安全需求的不断增长,高性能网包分类在下一代交换机、路由器、防火墙等网络基础设备中有着越来越广的应用.网包分类算法作为高性能网包分类的核心技术,具有重要的研究价值和实践意义.文中从理论分析和算法设计两方面介绍了高性能网包分类的最新研究成果.在理论分析层面,依据计算几何理论对网包分类问题的数学解法及复杂度进行了归纳,总结了网包分类算法的理论依据及性能评价方法.在算法设计层面,对具有影响力的网包分类算法按照不同的研究方向进行了归类和介绍,并结合自身研究成果对不同类别的算法设计思路行了深入分析.作者在多核网络处理器平台以及FPGA平台上实现了几类具有代表性的网包分类算法,并通过真实的网络流量测试比较了不同类型算法在不同系统平台上的实际性能.最后,作者总结并展望了高性能网包分类的下一步发展方向.     

IPSec和IP Filter在路由器中部署策略的研究

IPSec和IP Filter是IPv6路由器中的重要安全部件．IPSec的安全关联查找引擎具有类似于IP Filter的功能,也需要对IP包进行过滤和匹配,路由器中流动的IP包可能需要经过这两个部件的重复过滤,因此,这两个部件之间的部署策略将会直接影响到IP包的处理效率．从路由器整体安全的角度分析了两个安全部件之间的相互关系,提出了一个新的部署策略．与国际上著名的开放源码IPv6协议栈KAME相比较,该部署策略可以提高IPSec的处理效率,减轻IP Filter对IPSec的负面影响,同时,也减少了IP包在路由器中的重复过滤,提高了IP包的处理效率．     

实时IP反向追踪的研究方法

实时性对于在DoS或DDoS网络攻击申发送假源地址包的主机进行IP反向追踪非常重要。实时的IP反向追踪可在洪水源头处阻止攻击，是建立对网络攻击的网络范围的有效、快速、自动响应的基础。本文分析了IP反向追踪的模型和分类，在比较当前关于提高IP反向追踪实时性研究的基础上，针对其计算复杂性、路由器开销、误报率等，提出实时IP反向追踪需解决的关键问题。为了说明IP反向追踪实时性的重要性和可行性，建立了一个随机包标记算法测试环境。     

IPv6包的分段及重组过程详解

IP分组在进入某个具体的网络时一般都需要进行分段，在IPv4中，分段的任务通常由路由器来完成，并且所有的分段信息都保存在IP头中。为加快路由器对IP分组的处理速度，IPv6对IP协议头部进行了简化，不再处理分段的信息，分段的任务最终通过IPv6的分段头来完成，文章详细介绍了分段头如何完成对IP包的分段和重组。     

基于无冲突哈希Trie树的IP分类算法的研究

随着计算机网络的快速发展，IP分类算法被广泛地应用于路由器、防火墙和流量计费等软件中。本文在基于无冲突哈希Trie树的快速IP分类算法的基础上给出了一组哈希函数，进一步增强了算法的灵活性。     

A Non-Collision Hash Trie-Tree Based Fast IP Classification Algorithm

With the developemnt of network applications,routers must support such functions as firewalls,provision of QoS,traffic billing,etc.All these functions need the classification of IP packets,according to how different the packetes are processd subsequently,which is determined.In this article,a novle IP classification algorithm is proposed based on the Grid of Tries algorithm.The new algorithm not only eliminates original limitations in th case of multiple fields but also shows better performance in regard to both and space.It has better overall performance than many other algorithms.     

IP地址查找算法的分析

由于lnternet中通信量的迅速增加。千兆网已被越来越多地采用。为了处理千兆／s的通信速度,中心路由器必须能够每秒转发几百万个包。因而快速的IP地址查找。就成为获得所需的数据包转发率的关键。文章分析了几种高效的IP地址查找算法,并从查找速度、可量测性、更新速度方面。对它们的性能进行了比较。     

Ordered lookup with bypass matching for scalable per-flow classification in layer 4 routers

In order to provide different service treatments to individual or aggregated flows, layer 4 routers in Integrated Services networks need to classify packets into different queues. The classification module of layer 4 routers must be fast enough to support gigabit links at a rate of millions of packets per second. In this work, we present a new software method OLBM to lookup multiple fields of a packet, in a dynamically pre-defined order, against the classification database. This algorithm also uses a technique called bypass matching and can classify packets at a rate of well over one million packets per second while scaling to support more than 300k flows. Complexity analysis and experiment measurements are also presented in this study.     

宽带IP路由器的体系结构分析

随着宽带技术的不断发展,组建主干网的路由器必然需要以千兆比特以上的速率转发分组,而基于总线和中央处理器的路由器具有无法克服的局限,这就对传统的路由器体系结构提出了严峻的挑战.该文全面综述了近年来在宽带IP(Internet protocol)路由器方面研究的最新进展,详细分析了用于主干网互连的宽带IP路由器的体系结构设计,最后,指出了该领域中需要进一步研究的问题.     

IP routers: new tool for gigabit networking

IP routing continues to receive much attention from the research and vendor communities. Its primary function-forwarding packets between networks-must keep pace with the demands of the exponentially growing end user population. It must accommodate attachment of gigabit data link technologies such as ATM, packet Sonet, Gigabit Ethernet, and dense wave division multiplexing, and fill those links at full capacity. As network providers introduce new services supporting multicast, QoS, voice, and security, IP routing-and more specifically the IP forwarding function-will be called upon to analyze additional packet information at gigabit rates to determine how each packet should be handled. Performing these new functions while maintaining parity with the advances in available bandwidth will present an interesting challenge for the forwarding capabilities of IP routers. Indeed, for the Internet to scale, we must scale all dimensions of the IP routing process     

An intelligent method to block e-mail bombs

It is hard to block e-mail bombs because they are usually sent by normal SMTP (Simple Mail Transfer Protocol) applications with fake mail sender addresses and IP addresses. Fortunately, original network packets contain real IP address information anyway. Collecting and analyzing these packet contents can help an administrator to realize where the e-mail bombs are coming from and block them. This article presents a simple method that uses a bandwidth manager device to collect and analyze packets to get e-mail bombs information as well as to block e-mail bomb source IP addresses in routers. In practical application experiences at the computer center in a university, this method blocked e-mail bombs simply and effectively. Furthermore, a fuzzy inference system was also designed to help identify e-mail bombs. Its fuzzy membership functions could be adapted using the fuzzy neural network learning method. In brief, the proposed method affords an automatic and adaptable alarm to find e-mail bombs.     

An IP Traceback Protocol using a Compressed Hash Table,a Sinkhole Router and Data Mining based on Network Forensics against Network Attacks

The Source Path Isolation Engine (SPIE) is based on a bloom filter. The SPIE is designed to improve the memory efficiency by storing in a bloom filter the information on packets that are passing through routers, but the bloom filter must be initialized periodically because of its limited memory. Thus, there is a problem that the SPIE cannot trace back the attack packets that passed through the routers earlier. To address this problem, this paper proposes an IP Traceback Protocol (ITP) that uses a Compressed Hash Table, a Sinkhole Router and Data Mining based on network forensics against network attacks. The ITP embeds in routers the Compressed Hash Table Module (CHTM), which compresses the contents of a Hash Table and also stores the result in a database. This protocol can trace an attack back not only in real time using a hash table but also periodically using a Compressed Hash Table (CHT). Moreover, the ITP detects a replay attack by attaching time-stamps to the messages and verifies its integrity by hashing it. This protocol also strengthens the attack packet filtering function of routers for the System Manager to update the attack list in the routers periodically and improves the Attack Detection Rate using the association rule among the attack packets with an Apriori algorithm.     

A More Practical Approach for Single-Packet IP Traceback using Packet Logging and Marking

Tracing IP packets to their origins is an important step in defending Internet against denial-of-service attacks. Two kinds of IP traceback techniques have been proposed as packet marking and packet logging. In packet marking, routers probabilistically write their identification information into forwarded packets. This approach incurs little overhead but requires large flow of packets to collect the complete path information. In packet logging, routers record digests of the forwarded packets. This approach makes it possible to trace a single packet and is considered more powerful. At routers forwarding large volume of traffic, the high storage overhead and access time requirement for recording packet digests introduce practicality problems. In this paper, we present a novel scheme to improve the practicality of log-based IP traceback by reducing its overhead on routers. Our approach makes an intelligent use of packet marking to improve scalability of log-based IP traceback. We use mathematical analysis and simulations to evaluate our approach. Our evaluation results show that, compared to the state-of-the-art log-based approach called hash-based IP traceback, our approach maintains the ability to trace single IP packet while reducing the storage overhead by half and the access time overhead by a factor of the number of neighboring routers.