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.
- On the convergence time of a path-vector protocol
Recommendations
Network routing with path vector protocols: theory and applications
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communicationsPath vector protocols are currently in the limelight, mainly because the inter-domain routing protocol of the Internet, BGP (Border Gateway Protocol), belongs to this class. In this paper, we cast the operation of path vector protocols into a broad ...
An analysis of convergence delay in path vector routing protocols
Path vector routing protocols such as the Border Gateway Protocol (BGP) are known to suffer from slow convergence following a change in the network topology or policy. Although a number of convergence enhancements have been proposed recently, there has ...
Multiconstraint QoS Routing Using a Path-Vector Protocol
ASIAN '02: Proceedings of the7th Asian Computing Science Conference on Advances in Computing Science: Internet Computing and Modeling, Grid Computing, Peer-to-Peer Computing, and ClusterIn this paper, we propose a path-vector protocol for multiconstraint QoS routing. The protocol allows nodes in the network to exchange paths, and constructs new paths using our distributed algorithm. Explicit paths provided by the protocol could be used ...
Comments