Bringing order to BGP: Decreasing time and message complexity

The Border Gateway Protocol (BGP), the de facto routing protocol of the internet, generates excessive amount of traffic following changes in the underlying backbone. Previous papers [C. Labovitz, R. Wattenhofer, S. Venkatachary, A. Ahuja, The impact of internet policy and topology on delayed routing convergence, in: Proceedings of the INFOCOM, April 2001; C. Labovitz, A. Ahuja, A. Bose, F. Jahanianitz, Delayed internet routing convergence, in: Sigcomm, September 2000.] show that BGP suffers from high convergence delay and high message complexity after a fail down (detachment) of a network, due to path exploration caused by a limited version of the counting to infinity problem.Surprisingly, we show in this paper that BGP suffers from a high message complexity also after an up event (reattachment of a network). We analyze BGP dynamics data from raw update dumps and show that race conditions cause extensive path exploration that increases the amount of redundant updates. We show, based on these BGP dynamics, that up to 26% of the updates sent during up events are redundant. We also find that the effect of this phenomenon is bigger when the change occurs at the edge of the network.We suggest a minor modification to the waiting rule of BGP that pseudo orders the network and reduces the convergence latency of up events by half and the message complexity from O(DE) to O(E), where D is the Diameter of the internet and E is the number of connections between ASes. Our simulation results suggest that our modification may improve the convergence messages and time during all events, with the most noted improvement of up to 36% in the number of messages and 81% in time to convergence during up events in Internet like topologies. We show that our results hold also for partial deployment of the modification in only some of the routers.     

域间路由协议BGP收敛时间的定量分析及预测

本文对因特网的域间路由协议-BGP的收敛问题进行了研究,提出了一种新的BGP收敛模型,考虑了BGP报文的处理和等待时间以及各种延迟对收敛时间的影响,给出了一种更精确的BGP的收敛时间上界,进而根据域间路由系统的幂率特性和BGP协议标准分析了影响收敛性的各个因素,并在此基础上对BGP的收敛性问题今后的发展趋势进行了预测。理论分析和模拟实验显示,BGP的收敛时间最终会受到CPU处理效率、AS度数以及MRAI的影响,而传输路径长度和链路延迟反而会使收敛时间越来越小。     

受BGP策略影响的路由稳定性仿真数据分析

BGP是一个基于策略的路由协议，目前，由于BGP策略所引发的路由振荡在Internet中非常普遍，给网络稳定性健壮性都带来了很多负面的影响。网络仿真在路由稳定性研究中充当着相当重要的角色。用网络仿真的方法来研究和分析影响BGP路由稳定性的因素，是一个非常科学实用的研究方法和途径。     

MED诱发Ⅱ型路由振荡的分析与研究

边界网关协议（BGP）是目前用于广域网中最主要的域间分布式动态路由协议,具有丰富的路由控制机制.为了更好地控制路由策略,当前大部分的营运商均将BGP部署到骨干路由器.随着网络的不断扩展,路由器数目的增多以及路由信息条目的激增,解决BGP的扩展问题变得越来越重要.在采用路由反射和路由联盟方法中,MED属性的使用通常会引起路由持久的振荡.介绍了含有MED属性的路由选择算法,给出了常见的MED配置方案,分析了MED诱发Ⅱ型路由持久振荡的过程,提出了如何避免此类路由振荡的一般方法.     

BA-BGP:一种基于备份AS通告的域间路由协议

BGP协议通过触发全局、反应式收敛应对网络拓扑和策略变化,然而由于其收敛时间过长、收敛过程中大量AS经历不可达、环路,造成大量转发中断,难以支持VoIP、远程医疗等关键业务的应用。本文提出了一种基于备份AS通告的新型域间路由协议BA-BGP,在不影响BGP协议动态性的基础上,通过在更新报文中增加备份AS属性,使AS节点可以获取到达目标的备份AS地址,当节点面临瞬时失效时可将报文封装转发到与备份AS关联的路径,从而降低了转发中断。大量模拟实验证明,通过采用具有互联网特征的拓扑以及广泛采用的BGP策略,BA-BGP有效降低了链路失效引起的瞬时失效率与转发中断时间,增强了网络可靠性。     

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

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

边界网关协议BGP4路由收敛问题研究进展

边界网关协议BGP4是目前Internet最主要的域问路由协议，其路由正确性和稳定性直接关系到Internet能否正常运行．作为一个域问路由协议，BGP协议必须支持策略路由，允许各个自治系统独立的制定他们的路由策略，而且允许这些策略优先于路径尺度．由于各个自治系统制定策略的角度不同，这些路由策略之间可能存在冲突，从而导致BGP协议发散及路由振荡．此外，BGP协议本身也存在一些内在机制的不完善，并可能导致在某些情况下路由不收敛或收敛速度缓慢．随着网络规模越来越大，拓扑越来越复杂，BGP路由收敛问题日趋严重，目前国内外对此展开了大量的研究，并提出了多种分析模型和解决方案．本文首先全面总结了BGP协议面临的主要的收敛问题，主要包括策略冲突和协议机制造成的不收敛问题和收敛缓慢问题，然后全面介绍了针对这些问题的现有的解决方案，分析比较了这些方案的优点和缺点，最后提出了进一步的研究设想．     

MED诱发II型路由振荡的分析与研究

边界网关协议(BGP)是目前用于广域网中最主要的域间分布式动态路由协议,具有丰富的路由控制机制。为了更好地控制路由策略,当前大部分的营运商均将BGP部署到骨干路由器。随着网络的不断扩展,路由器数目的增多以及路由信息条目的激增,解决BGP的扩展问题变得越来越重要。在采用路由反射和路由联盟方法中,MED属性的使用通常会引起路由持久的振荡。介绍了含有MED属性的路由选择算法,给出了常见的MED配置方案,分析了MED诱发II型路由持久振荡的过程,提出了如何避免此类路由振荡的一般方法。     

Incentive-compatible interdomain routing

The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP, Rekhter and Li in RFC 4271 of the Internet Engineering Task Force, 2006). Using BGP, ASes can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains?? autonomy in network operations and in business decisions, but it comes at a price: The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence (see, e.g., Varadhan et?al. in Comput Networks 32(1):1?C16, 2000). Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy (see, e.g., Gao and Rexford in IEEE/ACM Trans Network 9(6):681?C692, 2001; Griffin et?al. in Proceedings of 9th ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM??03), pp. 61?C72. ACM Press, New York, 2003). In addition to taking this engineering or ??protocol- design?? approach, researchers have approached interdomain routing from an economic or ??mechanism-design?? point of view. It is known that lowest-cost-path (LCP) routing can be implemented in an incentive-compatible, BGP-compatible manner (Feigenbaum et?al. in Distribut. Comput 18(1):61?C72, 2005; Shneidman and Parkes in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC??04), pp. 88?C97. ACM Press, New York, 2004) but that several other natural classes of policies cannot (Feigenbaum et?al. in Theor Comput Sci 378(2):175?C189, 2007; Feigenbaum et?al. in Distribut Comput 18(4):293?C305, 2006). In this paper, we present the first example of a class of interdomain-routing policies that is more general than LCP routing and for which BGP itself is both incentive-compatible and guaranteed to converge. We also present several steps toward a general theory of incentive-compatible, BGP-compatible interdomain routing.     

Persistent route oscillations in inter-domain routing

Hop-by-hop inter-domain routing protocols, such as border gateway protocol (BGP) and inter-domain routing protocol (IDRP), use independent route selection to realize domains' local policies. A domain chooses its routes based on path attributes present in a route. It is widely believed that these inter-domain routing protocols always converge. We show that there exist domain policies that cause BGP/IDRP to exhibit persistent oscillations. In these oscillations, each domain repeatedly chooses a sequence of routes to a destination. Complex oscillation patterns can occur even in very simple topologies. We analyze the conditions for persistent route oscillations in a simple class of inter-domain topologies and policies. Using this analysis, we evaluate ways to prevent or avoid persistent oscillations in general topologies. We conclude that if a hop-by-hop inter-domain routing protocol allows unconstrained route selection at a domain, the protocol may be susceptible to route oscillations. Constraining route selection to a provably “safe” procedure (such as shortest path) can reduce the number of realizable policies. Alternatively, a routing policy registry can help detect unsafe policies.     

Preventing persistent oscillations and loops in IBGP configuration with route reflection

Internal Border Gateway Protocol (IBGP) is responsible for distributing external reachability information, obtained via External-BGP (EBGP) sessions, within an autonomous system (AS). To avoid a full mesh of IBGP sessions between all the BGP speakers of an AS, scaling schemes such as route reflection and AS confederations have been proposed. But it has been observed that employing these schemes may result in problems such as routing oscillations and forwarding loops due to Multi-Exit Discriminator (MED) attribute and path asymmetry in IBGP. In this paper we study the pathologies observed in IBGP when route reflection is used. We model the AS using the Interior Gateway Protocol (IGP) connectivity graph G_I and IBGP peering graph G_L. Then we state some simple conditions on G_I and G_L and prove that these conditions guarantee the absence of any persistent routing oscillations and forwarding loops due to MED attribute and IBGP path asymmetry. We consider the problem of constructing an IBGP configuration given the IGP connectivity such that there are no persistent oscillations and loops, and apply the conditions developed in the paper on this problem. We prove that solving the problem while minimizing some appropriate cost function is NP hard. We then give an Integer Linear Program (ILP) to construct a forwarding loop and persistent routing oscillation free IBGP configuration, for an AS with given IGP connectivity graph, which minimizes some appropriate cost while satisfying the resource constraints on all the BGP speaking nodes.     

Competitive routing over time

Congestion games are a fundamental and widely studied model for selfish allocation problems like routing and load balancing. An intrinsic property of these games is that players allocate resources simultaneously and instantly. This is particularly unrealistic for many network routing scenarios, which are one of the prominent application scenarios of congestion games. In many networks, load travels along routes over time and allocation of edges happens sequentially. In this paper, we consider two frameworks that enhance network congestion games with a notion of time. We introduce temporal network congestion games that are based on coordination mechanisms — local policies that allow to sequentialize traffic on the edges. In addition, we consider congestion games with time-dependent costs, in which travel times are fixed but quality of service of transmission varies with load over time. We study existence and complexity properties of pure Nash equilibria and best-response strategies in both frameworks for the special case of linear latency functions. In some cases our results can be used to characterize convergence properties of various improvement dynamics, by which the population of players can reach equilibrium in a distributed fashion.     

BGP协议配置及其对路由器性能的影响

BGP协议作为一个域间选路协议,很大程度上影响着Internet路由在延迟时间,有效性上的表现。研究表明,很多网络路由的延迟并非由因特网骨干路由器的BGP的路由决策导致的,而大多由于不恰当的路由器协议参数引发。论文主要阐述了路由器的参数配置如何影响路由数据报的网络带宽占用率,以及为了提高路由器的响应速度,和路由的收敛速度,在路由器的参数配置,策略配置上应该注意的问题。     

利用MinRouteAdvertisementInterval增强BGP收敛性的研究

本文首先分析一例典型的GBP路由振荡,然后研究了如何利用BGP路由最小通告时间间隔定时器来改善GBP收敛性的方法。     

Robust optimal design and convergence properties analysis of iterative learning control approaches

In this paper, we address four major issues in the field of iterative learning control (ILC) theory and design. The first issue is concerned with ILC design in the presence of system interval uncertainties. Targeting at time-optimal (fastest convergence) and robustness properties concurrently, we formulate the ILC design into a min-max optimization problem and provide a systematic solution for linear-type ILC consisting of the first-order and higher-order ILC schemes. Inherently relating to the first issue, the second issue is concerned with the performance evaluation of various ILC schemes. Convergence speed is one of the most important factors in ILC. A learning performance index—Q-factor—is introduced, which provides a rigorous and quantified evaluation criterion for comparing the convergence speed of various ILC schemes. We further explore a key issue: how does the system dynamics affect the learning performance. By associating the time weighted norm with the supreme norm, we disclose the dynamics impact in ILC, which can be assessed by global uniform bound and monotonicity in iteration domain. Finally we address a rather controversial issue in ILC: can the higher-order ILC outperform the lower-order ILC in terms of convergence speed and robustness? By applying the min-max design, which is robust and optimal, and conducting rigorous analysis, we reach the conclusion that the Q-factor of ILC sequences of lower-order ILC is lower than that of higher-order ILC in terms of the time-weighted norm.     

Intra-domain routing convergence with centralized control

The decentralized control scheme for routing in current IP networks has been questioned, and a centralized routing scheme has been proposed as an alternative. In this paper, we compare the convergence of centralized control scheme with decentralized link-state routing protocols. We first review the architectural advantages and challenges of centralized control. Thereafter, we identify and discuss the components of the convergence time in both schemes. We present how to achieve fast routing convergence in networks with centralized control. In particular, we analyze how to distribute forwarding information efficiently. Finally, we perform simulation studies on the convergence time for both real and synthetic network topologies and study the impact of control element location, link weights, and number of failures on the convergence time. The results show that the centralized control scheme can provide faster routing convergence than link-state routing protocols.     

解决策略冲突导致BGP路由发散的自适应机制

BGP(border gateway protocol)作为一种基于策略的协议,允许每个自治系统独立地选择本地路由策略.自治系统之间可能存在的路由策略冲突会引起BGP路由持续不稳定.当前提出的解决办法要么需要增加额外的通信开销,要么限制自治系统自由的选择路由策略.提出了一种解决策略冲突引起BGP路由不收敛的自适应方法,既不损害自治系统选择路由策略的灵活性,也不需要在BGP消息中增加额外信息.路由的稳定性被加入到BGP的判决过程中,不稳定路由的优先级被降低,使更加稳定的路由得以被选为最优路由,终止路由策略冲突引起的争执.在网络拓扑发生改变的情况下,这种新方法能够自适应地调整路由选择,重新收敛到新的稳定状态.     

BGP收敛性质改善的MRAI时钟设置方案

针对当前边界网关协议(BGP)路由存在慢收敛会引起网络数据转发层服务质量下降问题,基于一个简化的BGP路由模型和核心网络拓扑结构,提出一个新的MRAI时钟设置方案。该方案需要根据已知网络条件先计算后设置。通过使用ssfnet仿真软件测试表明,与RFC1771中时钟抖动方案相比,该方案能够减少BGP平均网络收敛延时和更新消息交互数量.     

The convergence analysis and specification of the Population-Based Incremental Learning algorithm

In this paper, we investigate the global convergence properties in probability of the Population-Based Incremental Learning (PBIL) algorithm when the initial configuration p⁽⁰⁾ is fixed and the learning rate α is close to zero. The convergence in probability of PBIL is confirmed by the experimental results. This paper presents a meaningful discussion on how to establish a unified convergence theory of PBIL that is not affected by the population and the selected individuals.     

Stability and convergence of the two parameter cubic spline collocation method for delay differential equations

In this paper, we propose the cubic spline collocation method with two parameters for solving delay differential equations (DDEs). Some results of the local truncation error and the convergence of the spline collocation method are given. We also obtain some results of the linear stability and the nonlinear stability of the method for DDEs. In particular, we design an algorithm to obtain the ranges of the two parameters α,β which are necessary for the P-stability of the collocation method. Some illustrative examples successfully verify our theoretical results.