在BGP／MPLS VPNs中用BGP实现域间流量工程

在BGP／MPLS VPNs中，用MPLS实现的流量工程主要被限止在单个管理域内。然而，随着企业规模的不断扩大，VPN跨越越来越多的管理域，急需管理域间流量的有效方法。以BGP属性、BGP策略和AS关系为基础的，一方面通过配置LOCAL-PREF属性值，运用输入策略，控制AS的出界流量；另一方面，保证客户AS不在提供者间或对等体间过渡流量，或允许客户AS向它的部分提供者通告路由，或人为增长AS-PATH，控制AS的入界流量。仿真表明此方法能有效地在BGP／MPLS VPNs中用BGP实现域间流量工程。     

BGP-XM: BGP eXtended Multipath for transit Autonomous Systems

Multipath interdomain routing has been proposed to enable flexible traffic engineering for transit Autonomos Systems (ASes). Yet, there is a lack of solutions providing maximal path diversity and backwards compatibility at the same time. The BGP-XM (Border Gateway Protocol-eXtended Multipath) extension presented in this paper is a complete and flexible approach to solve many of the limitations of previous BGP multipath solutions. ASes can benefit from multipath capabilities starting with a single upgraded router, and without any coordination with other ASes. BGP-XM defines an algorithm to merge into regular BGP updates information from paths which may even traverse different ASes. This algorithm can be combined with different multipath selection algorithms, such as the K-BESTRO (K-Best Route Optimizer) tunable selection algorithm proposed in this paper. A stability analysis and stable policy guidelines are provided. The performance evaluation of BGP-XM, running over an Internet-like topology, shows that high path diversity can be achieved even for limited deployments of the multipath mechanism. Further results for large-scale deployments reveal that the extension is suitable for large deployment since it shows a low impact in the AS path length and in the routing table size.     

一种自治系统分类方法

提出了一种使用BGP路由表对自治系统进行分类的方法。按照自治系统在Internet中所起的作用，将Internet层次模型分为5层。利用多个BGP路由表生成自治系统拓扑图，根据BGP路由表中自治系统路径的结构特点和传输自治系统的拓扑特点，结合随机扰动方法，对自治系统进行层次分类。与同类算法对比表明，该算法简洁有效。     

A power efficiency routing and maintenance protocol in wireless multi-hop networks

In wireless multi-hop networks, selecting a path that has a high transmission bandwidth or a high delivery rate of packets can reduce power consumption and shorten transmission delay during data transmission. There are two factors that influence the transmission bandwidth: the signal strength of the received packets and contentions in the contention-based MAC layer. These two factors may cause more power to be consumed during data transmission. We analyze these two factors and propose a power-aware routing protocol called MTPCR. MTPCR discovers the desired routing path that has reduced power consumption during data transmission. In addition to finding a desired path to reduce power consumption, MTPCR also takes into account the situations in which the transmission bandwidth of the routing path may decrease, resulting in much power consumption during data transmission because of the mobility of nodes in a network. MTPCR is thus useful in a network: it analyzes power consumption during data transmission with the help of neighboring nodes, and it uses a path maintenance mechanism to maintain good path bandwidth. The density of nodes in a network is used to determine when to activate the path maintenance mechanism in order to reduce the overhead of this mechanism. With the proposed path maintenance mechanism, power consumption during data transmission can be efficiently reduced, as well as the number of path breakages. In our simulation, we compared our proposed routing protocol, MTPCR, with the following protocols: two classical routing protocols, AODV and DSR; two power-aware routing protocols, MMBCR and xMBCR; and one multiple path routing protocol, PAMP. The comparisons are made in terms of throughput of the routing path, power consumption in path discovery, power consumption in data transmission, and network lifetime.     

域间路由协同监测中的信息共享机制

路由协同监测通过在自治系统之间共享路由监测信息来形成更为完整的全局监测视图,从而克服域间路由系统自治性的制约,提高单个自治系统的路由监测能力.针对路由协同监测的核心问题——监测信息共享,基于自组织思想设计了信息共享机制CoISM.该机制利用BGP路由策略引起的信息局部性对路由监测信息的传播范围进行裁减和控制,在被动查询的基础上增加了信息"反射"行为,利用路由监测信息之间的相关性实现信息的主动推送,将自治系统的利益建立在主动信息共享这一利他行为的基础上.CoISM能够引导自治系统实现路由监测信息的自组织聚合与按需共享,具有激励性,能够促进自治系统之间的协同.该机制采用分布式体系结构,具有良好的扩展性和较低的通信开销,不需要修改BGP协议,支持可渐进部署,适用于域间路由协同监测、路由故障协同分析、协同入侵检测等多种跨域协同管理应用.     

区分自治系统关系的域间路由体系研究

BGP-4是Internet采用的惟一域间路由协议，但它并不能确保路由收敛，复杂的网络结构加剧了路由潜在振荡的危险性．为此，提出了一种自约束的域间选路机制，在不违反传统流量工程原则和自治系统间结算原则的前提下，通过抑制违背自治系统间关系的路由通告和路由选择，达到维护全系统路由稳定的目的；对昕提方案的技术可行性进行论证，给出了新的选路机制原型系统的定义和关键算法的实现．区分自治系统关系的域间路由体系有效回避了路由策略一致性全局检测这一NP-complete问题．     

On a Self-Organizing Multipath Routing Protocol in Mobile Wireless Networks

In this paper, we present a self-organizing multipath (SOMP) routing protocol aiming at enhancing success rates of delivery of data packets end-to-end, restricting the routing overhead, and being robust to unstable network conditions. In this SOMP protocol, each mobile host sets up multiple beacons at other hosts to indicate routes to reach it. A beacon is an ordered list of mobile hosts along a path going from the host which holds the beacon, to the host which sets up the beacon. Two functionalities are used for routing data packets to their destinations. The first functionality is a beacon-seeking mechanism, which helps data packets to obtain beacons leading to the destinations of the data packets. The second functionality is a source routing mechanism, which is similar to the one used in Dynamic Source Routing (DSR) protocol and is used to forward data packets to their destinations using the beacons obtained. A balanced binary search tree is used in the SOMP protocol as the embedded forwarding structure, which is built on the identifiers of mobile hosts. This search tree serves for both distributing beacon updates and routing data packets to obtain beacons. The actual routes taken by data packets are jointly determined by the embedded forwarding structure and the underlying network connectivity.     

能量驱动的移动Ad Hoc网络概率组播路由协议

在ODMRP协议中，由于采用周期性地广播Join-Query包来更新成员信息和路由信息，因此网络中流动着大量平凡的Join-Query控制包，造成网络开销增大，网络拥塞。采用能量驱动的概率转发的方法，根据每个节点的能量资源信息为每个节点设置相应的转发投递概率，抑制网络中的Join-Query控制包。模拟结果显示，能量驱动的MANET概率组播路由协议(p-ODMRP)在投递率满足需求的情况下，网络的控制开销减小20%左右，增加了网络寿命，协议的综合性能有明显提高。     

BGP路由策略对路由稳定性的影响分析

在Internet中,域间的路由是由域间路由协议控制的。边界网关协议（BGP）是广泛使用的用于在各个自治系统之间交换网络可达信息的域间路由协议。BGP允许每个自治系统实施各种本地路由策略。用以进行路由的选择和传播。然而,不同的自治系统所制定的本地路由策略可能存在潜在的冲突,从而导致路由的振荡。该文给出了一个BGP的抽象模型,并通过实例分析BGP路由策略对路由稳定性的影响。     

An economic analysis of routing conflict and its resolution

Thousands of competing autonomous systems (ASes) must cooperate with each other to provide global Internet connectivity. Each AS has independent economic objectives and retains autonomy in setting their routing policies independently to maximize its profit. However, such autonomy enables ASes to produce conflicting routing polices and thus raises route oscillations between them (i.e., routing divergence). This paper studies the basic problem of routing divergence by investigating real ISP pricing data. We first demonstrate that routing divergences occur under economic dependency cycles, i.e., provider–customer cycles, of different ASes which are raised by economic conflicts between themselves. We then propose a provable cycle-breaking routing mechanism to detect and solve economic conflicts and route divergence. We show that every cycle-breaking strategy allows ASes to maximize their own profits to converge to a Nash equilibrium with a profit-sharing mechanism derived from the coalition game concept of Shapley value. At the Nash equilibrium point, the cycle-breaking strategies maximize ASes’ profits and encourage ASes so as to ensure divergence-free routing.     

基于GPS的启发式Ad hoc路由算法研究*

为了使移动Ad hoc网络中的节点在寻找路径时能获得较高的可用性和更低的开销,提出了一个新的路由算法,应用全球定位系统（GPS）提供的信息作为启发式信息,节点使用不同的概率转发路由信息,从而大大减少网络维护路由信息的总量,算法选择一个或两个路径记录在本地路由表中以提高其鲁棒性,当遇到连接断开,采取修复机制创建新的路径以提高数据包传输的成功率。仿真结果表明,该算法取得了较好的数据包传输成功率与较低的通信延迟。     

Secure Interdomain Routing Registry

The current Internet has no secure way to validate the correctness of routing information. We propose a mechanism that supports secure validation of routing information in the interdomain routing protocol of the Internet. Our mechanism focuses on alleviating obstacles which previously prevent the complete and correct construction of the Internet routing information. In particular, we present a registry with authorized and verifiable search (RAVS) by which routing information can be constructed securely. We give an efficient RAVS scheme and prove its securities in the random oracle model. By our scheme, the routing information can be securely stored and tested without revealing contents of registry entries and search queries. Only legal autonomous systems (ASes) can construct valid registry entries and a single compromised AS can be detected. Our experiment shows that our RAVS scheme can be implemented efficiently and the incurred overhead, in terms of time and space, is acceptable in practice.     

面向拓扑聚焦的网络流量模拟方法

为降低复杂网络模拟的计算开销,保证网络流量中数据包模拟的真实性,提出了一种面向拓扑聚焦的网络流量模拟方法。根据网络流量中数据包的路由路径所在区域,将数据包分为三种类型,对于每种类型的数据包采用不同的模拟方法。基于网络拓扑的实验表明,该方法适用于复杂网络的模拟,保证数据包模拟的真实性。     

基于域间路由的分布式分组过滤有效性研究

消除伪造源地址分组是互联网安全可信的内在要求.基于路由的分布式分组过滤具有良好的效果,但是目前对其有效性缺乏严密的理论分析.基于域间路由传播和互联网拓扑的分层特征,建立路由传播数模型和理想AS图模型,以此为工具分析了基于域间路由的最大过滤和半最大过滤有效性.结论印证并从理论上解释了前人研究中的实验结果.最大过滤能够消除绝大多数的伪造分组,虽然无法达到100％,但可以将伪造成功的自治系统数量限制为互联网AS路径的平均长度.在理想AS图上,半最大过滤与最大过滤的有效性相同,但是存储和计算开销要小很多,为实际中部署半最大过滤提供了理论依据.理论模型分析揭示了基于域间路由的分布式分组过滤的内在优缺点,有助于设计辅助措施和在整个互联网全面而合理地部署.     

一个基于身份的安全域间路由协议

提出了一个采用基于身份密码体制的安全域间路由协议——基于身份域间路由协议(identity-based inter-domain routing,简称id²r).id²r协议包括密钥管理机制、源AS验证机制LAP(the longest assignment path)和AS_PATH真实性验证机制IDAPV(identity-based aggregate path verification).密钥管理机制采用一个分布式层次密钥分发协议(distributed and hierarchical key issuing,简称DHKI),以解决基于身份密码系统固有的密钥托管问题.LAP的基本思想是,任一发出前缀可达路由通告的自治系统都必须提供该前缀的分配路径及证明,只有提供前缀最长有效分配路径的自治系统才是该前缀的合法源AS.IDAPV采用基于身份的聚合签名体制,生成保证AS_PATH路径属性真实性的路由聚合证明.性能评估结果显示,基于2007年12月7日的RouteViews数据,id2r路由器仅额外消耗1.71Mbytes内存,是S-BGP的38%;更新报文长度明显短于S-BGP;当硬件实现密码算法时,收敛时间几乎接近于BGP.     

Overhead reduction in a distributed path management system

CEAS (cross entropy ant system) is a distributed, robust and adaptive swarm intelligence system for path management in communication networks. This paper focuses on strategies for handling the overhead in terms of processing cycles, memory storage, and number of management packets (ants) generated by CEAS when the state of the network changes.Pheromone sharing is introduced such that virtual connections with common sub-paths are sharing information and cooperate in the path finding when the paths have the same destination and the same objective function. The sharing of information reduces the required memory in each node significantly on the expense of an increase in the size of the management packets. However, the packets are still rather small. The cooperation also leads to an improvement in convergence rates which again results in reduced transmission overhead.A rate adjustment scheme is also proposed. The scheme is self-tuned and detects state changes implicitly and sets packet rates accordingly by monitoring parameter values in the management system. Rate adaptation can be done both in the network nodes and at the end-points of a virtual path. Compared to a fixed rate strategy the self-tuned strategies show a significant reduction in the number of packets generated, while maintaining the same data packet delay and service availability level. The self-tuned rate adjustment in the network nodes provides fast restoration with short path detection times, which ensures high service availability. The self-tuned ant rate in the end-points avoids flooding the network with management packets when these are not required.The performance and overhead of CEAS are compared to those of the link state routing currently in use in today’s networks. The results show that CEAS outperforms link state routing both with respect to performance and overhead when the network experiences transient link failures, while the opposite is the case with long lived failures.     

A direction-based geographic routing scheme for intermittently connected mobile networks

In an intermittently connected mobile network, a complete routing path from a source to a destination cannot be guaranteed most of the time. Therefore, traditional routing methods for mobile ad hoc networks are not applicable in such a network. Current approaches for intermittently connected mobile networks are primarily based on redundant transmission and single-copy opportunistic routing. However, they incur either high overhead due to excessive transmissions, or long delay due to incorrect path choices during forwarding. In this paper, we propose a direction-based geographic (DIG) routing scheme for intermittently connected mobile networks. Relying on geographic location information, the packets are routed in a path approximately to the shortest path from the source node to the destination, which significantly reduces the overhead in redundant transmission and decreases the transmission delay in the single-copy opportunistic routing. Theoretical analysis and trace-driven experimental results show that DIG provides low transmission delay with low overhead in comparison with the schemes in the redundant transmission and single-copy opportunistic routing.     

On improving the efficiency of truthful routing in MANETs with selfish nodes

In Mobile Ad Hoc Networks (MANETs), nodes depend upon each other for routing and forwarding packets. However, nodes belonging to independent authorities in MANETs may behave selfishly and may not forward packets to save battery and other resources. To stimulate cooperation, nodes are rewarded for their forwarding service. Since nodes spend different cost to forward packets, it is desirable to reimburse nodes according to their cost so that nodes get incentive while the least total payment is charged to the sender. However, to maximize their utility, nodes may tell lie about their cost. This poses the requirement of truthful protocols, which maximizes the utility of nodes only when they declare their true cost. Anderegg and Eidenbenz recently proposed a truthful routing protocol, named ad hoc-VCG. This protocol incurs the route discovery overhead of O(n³), where n is the number of nodes in the network. This routing overhead is likely to become prohibitively large as the network size grows. Moreover, it leads to low network performance due to congestion and interference. We present a low-overhead truthful routing protocol for route discovery in MANETs with selfish nodes by applying mechanism design. The protocol, named LOTTO (Low Overhead Truthful rouTing prOtocol), finds a least cost path for data forwarding with a lower routing overhead of O(n²). We conduct an extensive simulation study to evaluate the performance of our protocol and compare it with ad hoc-VCG. Simulation results show that our protocol provides a much higher packet delivery ratio, generates much lower overhead and has much lower end-to-end delay.     

基于区块链的域间路由策略符合性验证方法

域间路由系统自治域(ASes)间具有不同的商业关系和路由策略.违反自治域间出站策略协定的路由传播可能引发路由泄露,进而导致网络中断、流量窃听、链路过载等严重后果.路由策略符合性验证对于保证域间路由系统安全性和稳定性至关重要.但自治域对本地路由策略自主配置与隐私保护的双重需求增加了验证路由策略符合性的难度,使其一直是域间路由安全领域尚未妥善解决的难点问题.提出一种基于区块链的域间路由策略符合性验证方法.该方法以区块链和密码学技术作为信任背书,使自治域能够以安全和隐私的方式发布、交互、验证和执行路由策略期望,通过生成对应路由更新的路由证明,保证路由传播过程的真实性,从而以多方协同的方式完成路由策略符合性验证.通过实现原型系统并基于真实路由数据开展实验与分析,结果表明该方法可以在不泄露自治域商业关系和本地路由策略的前提下针对路由传播出站策略符合性进行可追溯的验证,以合理的开销有效抑制策略违规路由传播,在局部部署情况下也具有显著的策略违规路由抑制能力.     

基于首选路由的AS 重要性评估方法

准确评估节点的重要性,是增强网络生存性的基础.由于域间路由系统路由策略的复杂性,已有的面向静态拓扑的节点重要性评估方法不能真实反映各个自治系统(autonomous systems,简称AS)在路由中的重要性.首次从动态路由的角度基于AS之间的最优路径从路由上评估各个AS的重要性,经过AS的最优路径数量越多,它就越重要.提出了基于首选路由的AS重要性评估方法,其时间复杂性为O(l×nm),它与面向静态拓扑的评估方法中最好的时间复杂性相同,并且能够更准确地描述节点的实际重要性.通过真实路由数据进行实验,与两种典型的面向静态拓扑的基于顶点度、强度中心性的评估方法对比,其结果表明,基于首选路由的评估方法可以有效发现AS网络中连接较少但很重要的节点,并且评估的重要性与实际的重要性更吻合.