On the competitiveness of AIMD-TCP within a general network

This paper studies the performance of AIMD (Additive Increase Multiplicative Decrease) TCP as an online distributed scheduling algorithm for allocating transmission rate to sessions/jobs running on a general network. The network consists of a set of routers which in this context act only as bottlenecks, i.e. when a router’s capacity has been reached, it informs the jobs passing through it to multiplicatively back off transmission rates. The analysis is easier when this AIMD algorithm is modeled by a continuous algorithm. We improve on that presented by Kelly to better capture the interconnectedness of the network. Extending the paper by Edmonds, Datta, and Dymond that solves the single-bottleneck case, we prove that with extra resources, this algorithm AIMDEQUI is competitive against the optimal global algorithm in minimizing the average transmission time of the jobs. We also bound the fairness of this resource allocation according to three different definitions of fairness.