The Experts below are selected from a list of 36 Experts worldwide ranked by ideXlab platform

Howard Karloff - One of the best experts on this subject based on the ideXlab platform.

  • on the convergence time of a Path Vector Protocol
    Symposium on Discrete Algorithms, 2004
    Co-Authors: Howard Karloff
    Abstract:

    We study the running time of a particular Path-Vector Protocol for distributively and asynchronously computing shortest Paths in a network to a given target node t. We study two cases. In both, the Protocol starts with each node possibly knowing some Path to t, subject to conditions discussed in the paper. In the first case, the "withdrawal case," all edges incident to the target are cut. We prove that in this case, the Protocol always terminates but may need exponential time to do so, if the nodes "fire" (i.e., execute) in an adversarially chosen order, even if the initial Paths are shortest. If the graph is a clique, the Protocol terminates in polynomial time. If, on the other hand, the nodes fire in random order, and the graph is arbitrary, then the algorithm terminates in polynomial expected time. In the second case, the "announcement case," in which new edges incident to t appear, we prove that the Protocol terminates in polynomial time, regardless of the firing order.This Protocol is interesting since it models the shortest-Path Protocol used by BGP, the interdomain routing Protocol of the Internet, in the absence of policy.

Ruibing Hao - One of the best experts on this subject based on the ideXlab platform.

  • an approach to accelerate convergence for Path Vector Protocol
    Global Communications Conference, 2002
    Co-Authors: Jiazeng Luo, Junqing Xie, Ruibing Hao
    Abstract:

    BGP, a Path Vector Protocol, is the de facto inter-domain routing Protocol. However, slow convergence problem, the bigotry of Path Vector Protocol, has demonstrated a significant impact on the performance of BGP. In this paper, we propose an enhancement to Path Vector Protocol to alleviate the impact of slow convergence process. We compare the convergence time of the legacy Path Vector Protocol and the improved one for complete AS graph, meanwhile the upper and lower bound of convergence time for any AS graph are given for the improved Protocol. Simulation results reveal that the improved Path Vector Protocol has a much better performance than the original one.

Jiazeng Luo - One of the best experts on this subject based on the ideXlab platform.

  • an approach to accelerate convergence for Path Vector Protocol
    Global Communications Conference, 2002
    Co-Authors: Jiazeng Luo, Junqing Xie, Ruibing Hao
    Abstract:

    BGP, a Path Vector Protocol, is the de facto inter-domain routing Protocol. However, slow convergence problem, the bigotry of Path Vector Protocol, has demonstrated a significant impact on the performance of BGP. In this paper, we propose an enhancement to Path Vector Protocol to alleviate the impact of slow convergence process. We compare the convergence time of the legacy Path Vector Protocol and the improved one for complete AS graph, meanwhile the upper and lower bound of convergence time for any AS graph are given for the improved Protocol. Simulation results reveal that the improved Path Vector Protocol has a much better performance than the original one.

G. Wilfong - One of the best experts on this subject based on the ideXlab platform.

  • A safe Path Vector Protocol
    Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Socie, 2000
    Co-Authors: T.g. Griffin, G. Wilfong
    Abstract:

    An IP routing Protocol is safe if it is guaranteed to converge in the absence of network topology changes. BGP, currently the only interdomain routing Protocol employed on the Internet, is not safe in this sense. It may seem that the source of BGP's potential divergence is inherent in the requirements for any interdomain routing Protocol-policy-based metrics must be allowed to override distance-based metrics, and each autonomous system must be allowed to independently define its routing policies with little or no global coordination. In this paper we present a simple Path Vector Protocol (SPVP) that captures the underlying semantics of BGP by abstracting away all nonessential details. We then add a dynamically computed attribute to SPVP routing messages, called the route history. Protocol oscillations caused by policy conflicts produce routes whose histories contain cycles. These cycles identify the policy conflicts and the autonomous systems involved. SPVP is made safe by automatically suppressing routes whose histories contain cycles. We discuss how this safe SPVP can be used in the design of a safe BGP.

Chunhong Zhang - One of the best experts on this subject based on the ideXlab platform.

  • an approach to seeking policy disputes based on dispute cycle avoidance and configuration guideline
    Telecommunication Systems, 2003
    Co-Authors: Chunhong Zhang
    Abstract:

    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.