Advertising interdomain QoS routing information

To enable end-to-end quality-of-service (QoS) guarantees in the Internet, based on the border gateway protocol (BGP), interdomain QoS information advertising, and routing are important. However, little research has been done in this area so far. Two major challenges, scalability and heterogeneity, make the QoS extension to BGP difficult. In the existing routing schemes, static and instantaneous QoS metrics, such as link capacity and available bandwidth, are used to represent QoS routing information, but neither of them can solve the two challenges well. In this paper, BGP is extended to advertise available bandwidth and delay information of routes, but, instead of using the traditional deterministic metrics, a series of statistical metrics, available bandwidth index (ABI), delay index (DI), available bandwidth histogram (ABH), and delay histogram (DH), are defined and applied to QoS information advertising and routing. Two major contributions of the proposed statistical metrics are: 1) QoS information is abstracted into one or several probability intervals and, thus, the heterogeneous and dynamic QoS information can be represented more flexibly and precisely and 2) by capturing the statistical property of the detailed distribution of QoS information, these new metrics are efficient and they can highly decrease the message overhead in routing, thereby making the QoS advertising and routing scalable. Our extensive simulations confirm both contributions of the QoS extension to BGP very well. Moreover, besides BGP, these statistical metrics can be applied to other networks and protocols to represent QoS information in a more scalable and precise way.     

Class-based multicast routing in interdomain scenarios

DiffServ-like domains bring new challenges to quality of service (QoS) multicast routing simply by shifting the focus from individual flows into classes of flows. Packets are marked at edge routers and receive differentiated treatment according to the class and not the flow that they belong to. DiffServ therefore became adverse to multicast, as packet replication inside the domain may require classification and remarking functions not present in core nodes. At the interdomain level, no doubt multicast QoS complexity is increased by the interleaving of DiffServ and non-Diffserv domains, making it more difficult to address QoS multicast in an end-to-end perspective. In today’s real interconnection world, classes of service have no meaning in certain links of a full interdomain path. While the problem is not new, as already pointed out, there are no real efforts to bring multicast back to a class-of-service domain without compromising its model of operation. In this article, we present an innovative multicast QoS routing strategy, clearly designed for the new class-of-service paradigm. The solution is based upon the construction of multiple trees, one per class of service available, while still allowing receivers to shift for source-specific trees in its own class of service. The strategy is presented in a full end-to-end perspective. Intradomain trees use differentiated routing paths thus helping traffic differentiation. Intradomain receivers are allowed to shift from shared trees into an adequate class-of-service source tree. At interdomain level, each class-of-service interdomain tree branch is accomplished by means of an improved path probing strategy enabling for QoS path establishment. This paper presents this new strategy, and associated protocols, for constructing several multicast and directed distribution trees, one per class of service, within each multicast group. This new strategy and associated protocols are then simulated using NS-2 platform. Simulation results are analyzed and compared with other multicast routing solutions, both at intra- and interdomain levels.     

A QoS-aware multicast routing protocol

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intradomain and interdomain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees     

A Survey of BGP Security Issues and Solutions

As the Internet's de facto interdomain routing protocol, the Border Gateway Protocol (BGP) is the glue that holds the disparate parts of the Internet together. A major limitation of BGP is its failure to adequately address security. Recent high-profile outages and security analyses clearly indicate that the Internet routing infrastructure is highly vulnerable. Moreover, the design of BGP and the ubiquity of its deployment have frustrated past efforts at securing interdomain routing. This paper considers the current vulnerabilities of the interdomain routing system and surveys both research and standardization efforts relating to BGP security. We explore the limitations and advantages of proposed security extensions to BGP, and explain why no solution has yet struck an adequate balance between comprehensive security and deployment cost.     

分布式服务质量路由预计算算法

服务质量路由作为下一代IP互联网提供服务质量(QoS)控制的一种重要方案,如何提高其可扩展性和路由性能是有待解决的难题.本文提出了基于聚类的分布式预计算算法,以具有多种QoS参数的路由表预计算为目标,引入了支持QoS参数的扩展距离向量,通过网络中各个节点的分布式协同计算,大大降低了单个路由器的计算复杂度.文章分析了优势路径及其选取策略,给出了路由计算中优势路径聚集的聚类方法,实现了QoS路由表的高效聚集压缩.实验结果进一步验证了该算法具有计算量小和QoS路由性能高的优点,在QoS度量维数和网络规模方面均具有良好的可扩展性,并对域间算法研究提供了重要依据.     

An Approach to Seeking Policy Disputes Based on Dispute Cycle Avoidance and Configuration Guideline

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol used to exchange network reachability information between ASes in the global Internet. However, Varadhan et al. [19] has shown that the conflict of BGP routing policies can cause BGP to diverge. This paper presents an approach to seek the set of conflict routing policies based on dispute cycle avoidance. The stable paths problem, a static formalism that captures the semantics of interdomain routing protocol, provides the theoretical foundation for this approach. And this approach draws on the simple path vector protocol to identify the dispute cycles that cause routing oscillation first, and then queries which routing policies lead to these cycles in a distributed manner. Finally, it determines conflict routing policies based on dispute cycle avoidance. Moreover, we present a method to determine the severity level of dispute routing policies based on AS relationships and configuration guidelines of routing policy presented by Gao and Rexford [4]. And this method can help Network administrators determine the top-priority routing policies to be fixed and improve the efficiency of debugging routing policies. In addition, a simulation instance is given in order to explain results of this method.     

An overview of quality of service routing for next-generationhigh-speed networks: problems and solutions

The upcoming gigabit-per-second high-speed networks are expected to support a wide range of communication-intensive real-time multimedia applications. The requirement for timely delivery of digitized audio-visual information raises new challenges for next-generation integrated services broadband networks. One of the key issues is QoS routing. It selects network routes with sufficient resources for the requested QoS parameters. The goal of routing solutions is twofold: (1) satisfying the QoS requirements for every admitted connection, and (2) achieving global efficiency in resource utilization. Many unicast/multicast QoS routing algorithms have been published, and they work with a variety of QoS requirements and resource constraints. Overall, they can be partitioned into three broad classes: (1) source routing, (2) distributed routing, and (3) hierarchical routing algorithms. We give an overview of the QoS routing problem as well as the existing solutions. We present the strengths and weaknesses of different routing strategies, and outline the challenges. We also discuss the basic algorithms in each class, classify and compare them, and point out possible future directions in the QoS routing area     

A cascading failure model for interdomain routing system

There have been many researches on border gateway protocol (BGP) security, most of which mainly focused on how to enhance the security of the BGP protocol or the interdomain routing system. However, few works studied the vulnerabilities especially the production mechanism of security events in the interdomain routing system. It takes many obstacles to understand and improve the security of the interdomain routing system. This paper explores the cascading failure phenomenon of the interdomain routing system. First, we devise a state machine to describe the state transition of BGP nodes and then give a detailed analysis of the BGP failure. Second, on the basis of the preferential attachment characteristic, we propose a cascading failure model for the interdomain routing system, which depicts the production mechanism of cascading failure, and introduce two evaluating indicators, the proportion of failed nodes and the proportion of failed links, to assess the scale of cascading failure. Furthermore, we apply the cascading failure model to display two different cascading failure scenes. The experimental results show that random failure has less influence on the interdomain routing system, while its robustness against hostile attack is weak. Copyright ©2011 John Wiley & Sons, Ltd.     

对新型网络路由机制的思考

路由是网络的结构基石,新型网络路由机制是构建新型网络体系的必需。目前网际层的路由本质上是所谓的"单下一跳路由"机制,解决网络传输拥塞问题的一个根本措施在于改变当前网络单下一跳的选路模式,允许多条路径的并行传输。边界网关协议(BGP)是目前Internet唯一采用的域间路由协议,针对当前域间路由系统面临的规模可扩展性问题,文章提出了一个规模可扩展的新型分层域间路由架构(s-idra)。除了可扩展性以外,路由体系还面临其他挑战,比如安全性、服务质量(QoS)、组播、移动、动态网络拓扑等等。路由协议尤其是未来新型信息网络体系结构的路由协议的研究任重而道远。     

QoS routing in networks with uncertain parameters

We consider the problem of routing connections with quality of service (QoS) requirements across networks when the information available for making routing decisions is inaccurate. Such uncertainty about the actual state of a network component arises naturally in a number of different environments. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end-to-end delay guarantees, this problem is intractable. However, we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. Moreover, we argue that such decomposition better reflects the interoperability between the routing and reservation phases. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which includes typical distributions, and restricting ourselves to that class, we are able to establish efficient and exact solutions. We then consider the general problem of combined path optimization and delay decomposition and present efficient solutions. Our findings are applicable also to a broader problem of finding a path that meets QoS requirements at minimal cost, where the cost of each link is some general increasing function of the QoS requirements from the link     

The stable paths problem and interdomain routing

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists     

On Understanding Transient Interdomain Routing Failures

The convergence time of the interdomain routing protocol, BGP, can last as long as 30 minutes. Yet, routing behavior during BGP route convergence is poorly understood. During route convergence, an end-to-end Internet path can experience a transient loss of reachability. We refer to this loss of reachability as transient routing failure. Transient routing failures can lead to packet losses, and prolonged packet loss bursts can make the performance of applications such as Voice-over-IP and interactive games unacceptable. In this paper, we study how routing failures can occur in the Internet. With the aid of a formal model that captures transient failures of the interdomain routing protocol, we derive the sufficient conditions that transient routing failures could occur. We further study transient routing failures in typical BGP systems where commonly used routing policies are applied. Network administrators can apply our analysis to improve their network performance and stability.     

QoS-aware routing in emerging heterogeneous wireless networks[Quality-of-Service-Based Routing Algorithms for Heterogeneous Networks]

The integration of different kinds of wireless mobile networks, or heterogeneous wireless networks (HWNs), is emerging. However, a systematic discussion with regard to the special requirements and the complexity of QoS-aware routing in such networks and how QoS is blended with routing is still largely missing. This article aims to cast some light on these aspects. Based on an analysis of the basic architecture of an emerging heterogeneous wireless network and its new requirements on QoS-aware routing, a policy-based QoS supporting system infrastructure and a QoS-aware routing algorithm called QRA are presented in this article. The presentation is specifically given to these issues and components that are unique to HWNs and its QoS routing. The evaluation results show the impact of different network parameters on the performance of QoS-aware routing in HWNs     

A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks

Due to the recent developments in wireless technology and electronics, it is feasible to develop pervasive algorithms for satellite environments. Multi-Layered Satellite Networks (MLSNs) that consist of low earth orbit and medium earth orbit satellites are becoming increasingly important since they have higher coverage and better service than single-layered satellite networks. One of the challenges in MLSNs is the development of specialized and efficient routing algorithms. In this paper, we improved the virtual topology strategy and import heuristic algorithm to satisfy the QoS requirements of the MLSN users. The QoS requirements include end to end delay; link utilization, bandwidth, and package loss rate are mainly focused in this paper. To satisfy the QoS requirements is a multi-parameter optimization problem, and it is convinced as a Non-deterministic Polynomial Complete problem already. As a solution, three typical heuristic algorithms—Ant Colony Algorithm, Taboo Search Algorithm and Genetic Algorithm are applied in the routing scheme in order to reduce package loss, link congestion and call blocking. Simulation results show that heuristic routing algorithm can provide more QoS guarantees than shortest path first algorithm on package loss rate, link congestion and call blocking.     

Design for configurability: rethinking interdomain routing policies from the ground up

Giving ISPs more fine-grain control over interdomain routing policies would help them better manage their networks and offer value-added services to their customers. Unfortunately, the current BGP route-selection process imposes inherent restrictions on the policies an ISP can configure, making many useful policies infeasible. In this paper, we present Morpheus, a routing control platform that is designed for configurability. Morpheus enables a single ISP to safely realize a much broader range of routing policies without requiring changes to the underlying routers or the BGP protocol itself. Morpheus allows network operators to: (1) make flexible trade-offs between policy objectives through a weighted-sum based decision process, (2) realize customer-specific policies by supporting multiple route-selection processes in parallel, and allowing customers to influence the decision processes, and (3) configure the decision processes through a simple and intuitive configuration interface based on the Analytic Hierarchy Process, a decision-theoretic technique for balancing conflicting objectives. We also present the design, implementation, and evaluation of Morpheus as an extension to the XORP software router.     

Multicast routing and its QoS extension: problems, algorithms, andprotocols

Multicast services have been increasingly used by various continuous media applications. The QoS requirements of these continuous media applications prompt the necessity for QoS-driven, constraint-based multicast routing. This article provides a comprehensive overview of existing multicast routing algorithms, protocols, and their QoS extension. In particular, we classify multicast routing problems according to their optimization functions and performance constraints, present basic routing algorithms in each problem class, and discuss their strengths and weaknesses. We also categorize existing multicast routing protocols, outline the issues and challenges in providing QoS in multicast routing, and point out possible future research directions     

Delayed Internet routing convergence

This paper examines the latency in Internet path failure, failover, and repair due to the convergence properties of interdomain routing. Unlike circuit-switched paths which exhibit failover on the order of milliseconds, our experimental measurements show that interdomain routers in the packet-switched Internet may take tens of minutes to reach a consistent view of the network topology after a fault. These delays stem from temporary routing table fluctuations formed during the operation of the border gateway protocol (BGP) path selection process on the Internet backbone routers. During these periods of delayed convergence, we show that end-to-end Internet paths will experience intermittent loss of connectivity, as well as increased packet loss and latency. We present a two-year study of Internet routing convergence through the experimental instrumentation of key portions of the Internet infrastructure, including both passive data collection and fault-injection machines at major Internet exchange points. Based on data from the injection and measurement of several hundred thousand interdomain routing faults, we describe several unexpected properties of convergence and show that the measured upper bound on Internet interdomain routing convergence delay is an order of magnitude slower than previously thought. Our analysis also shows that the upper theoretic computational bound on the number of router states and control messages exchanged during the process of BGP convergence is factorial with respect to the number of autonomous systems in the Internet. Finally, we demonstrate that much of the observed convergence delay stems from specific router vendor implementation decisions and ambiguity in the BGP specification     

Distributed schemes for diverse path computation in multidomain MPLS networks

MPLS is currently used by several JSPs to carry some high-value traffic components, such as telephony over IP trunks and VPNs. For this type of traffic, service availability is a critical QoS dimension that needs to be protected from network failures. With MPLS-TE, this can be achieved by means of path protection schemes, where active and backup LSPs are routed along diverse paths. Besides protection, path diversity can be exploited for load balancing, another common means of QoS improvement. In order to preserve other QoS requirements, the paths must meet certain constraints (e.g., bandwidth availability, low load) and/or minimize some metric (e.g., hop count). This requires the ability to establish path diversity in an optimal way. In many cases of practical interest, the QoS traffic has an interdomain scope. This is the case for ToIP and VPN traffic between different carriers, or between different ASs owned by the same carrier, as found, for example, after corporate acquisitions or mergers. Therefore, path diversity is a requirement for interdomain traffic engineering. In this work we address path diversity in a multidomain network, where individual domains are capable of connection-oriented forwarding and endowed with an MPLS-TE control plane. For administrative and/or scalability reasons intradomain routing information is not disseminated externally, so dynamic path computation must be achieved by a distributed scheme based on interdomain collaboration. We briefly describe three alternative schemes recently proposed for interdomain diverse path computation, and quantitatively assess their performance with simulations over real ISP topologies.     

GMCAR: Grid-based multipath with congestion avoidance routing protocol in wireless sensor networks

Recently, the interest in wireless sensor networks has been magnetized in the delay sensitive applications such as real-time applications. These time critical applications crave certain QoS requirements as though end-to-end delay guarantee and network bandwidth reservation. However, the severe resource constraints of the wireless sensor networks pose great challenges that hinder supporting these requirements. In this paper, we propose a Grid-based Multipath with Congestion Avoidance Routing protocol (GMCAR) as an efficient QoS routing protocol that is suited for grided sensor networks. We employ the idea of dividing the sensor network field into grids. Inside each grid, one of the sensor nodes is selected as a master node which is responsible for delivering the data generated by any node in that grid and for routing the data received from other master nodes in the neighbor grids. For each master node, multiple diagonal paths that connect the master node to the sink are stored as routing entries in the routing table of that node. The novelty of the proposed protocol lies behind the idea of incorporating the grids densities along with the hop count into the routing decisions. A congestion control mechanism is proposed in order to relieve the congested areas in case of congestion occurrence. Simulation results show that our proposed protocol has the potential to achieve up to 19.5% energy saving, 24.7% reduction in the delay and up to 8.5% enhancement in the network throughput when compared to another QoS routing protocol. However, when compared to the basic grid-based coordinated routing protocol, it achieves 23% energy saving. In addition, the proposed protocol shows its superiority in achieving better utilization to the available storage.     

Managing interdomain traffic in Latin America: a new perspective based on LISP [Topics in Network and Service Management]

The characteristics of Latin American network infrastructures have global consequences, particularly in the area of interdomain traffic engineering. As an example, Latin America shows the largest de-aggregation factor of IP prefixes among all regional Internet registries, being proportionally the largest contributor to the growth and dynamics of the global BGP routing table. In this article we analyze the peculiarities of LA interdomain routing architecture, and provide up-to-date data about the combined effects of the multihoming and TE practices in the region. We observe that the Internet Research Task Force initiative on the separation of the address space into locators and identifiers can not only alleviate the growth and dynamics of the global routing table, but can also offer appealing TE opportunities for LA. We outline one of the solutions under discussion at the IRTF, the Locator/Identifier Separation Protocol, and examine its potential in terms of interdomain traffic management in the context of LA. The key advantage of LISP is its nondisruptive nature, but the existing proposals for its control plane have some problems that may hinder its possible deployment. In light of this, we introduce a promising control plane for LISP that can solve these issues, and at the same time has the potential to bridge the gap between intradomain and interdomain traffic management.