1st International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Stability of multi-path dual congestion control algorithms

  • @INPROCEEDINGS{10.1145/1190095.1190167,
        author={Thomas  Voice},
        title={Stability of multi-path dual congestion control algorithms},
        proceedings={1st International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ACM},
        proceedings_a={VALUETOOLS},
        year={2012},
        month={4},
        keywords={Internet dynamic routing flow control stability},
        doi={10.1145/1190095.1190167}
    }
    
  • Thomas Voice
    Year: 2012
    Stability of multi-path dual congestion control algorithms
    VALUETOOLS
    ACM
    DOI: 10.1145/1190095.1190167
Thomas Voice1,*
  • 1: Cambridge University Statistical Laboratory, CMS Wilberforce Road, Cambridge, UK.
*Contact email: t.voice@statslab.cam.ac.uk

Abstract

This paper investigates fair, scalable, stable congestion controls which achieve high bandwidth utilisation over networks of operating multi-path routing. The aim is to take advantage of path diversity to achieve efficient bandwidth allocation without causing instability. Two multi-path extensions to the class of dual algorithms are considered. The first is a natural extension previously proposed in the literature, which we show to be similar to a continuous time sub-gradient method for solving a network-wide optimisation problem. We establish that the continuous time fluid model possesses a weak stability property. This analysis assumes the absence of propagation delays. We then show that when propagation delays are present, even the weak stability property disappearsWe develop an alternative multi-path extension of the dual algorithm, which considers path diversity when evaluating fairness. This algorithm is shown to be globally stable in the absence of propagation delays and a sufficient condition for local stability, when heterogeneous propagation delays are present, is found. The sufficient condition we present is decentralised in the following sense: the gain parameter for each dynamic variable is restricted by the average round-trip time of packets passing through the link or source it represents, but not by the round-trip times of any other packets. The delay stability analysis is an extension of results for single-path congestion control. It is obtained by treating possible routes that belong to a given origin-destination pair as behaving as separate sources which pass through a virtual link located at the origin.The models considered apply to networks consisting of arbitrary interconnections of sources and links, with arbitrary, heterogeneous propagation delays.