Randomized algorithms for stability and robustness analysis of high speed communication networks

This paper initiates a study toward developing and applying randomized algorithms for stability of high speed communication networks. We consider the discrete-time version of the nonlinear model introduced in which uses as feedback variations in queueing delay information from bottleneck nodes of the network. We then linearize this nonlinear model around its unique equilibrium point at a single bottleneck node, and perform a robustness analysis for a special, symmetric case, where certain utility and pricing parameters are the same across all active users. In this case, we derive closed-form necessary and sufficient conditions for stability and robustness under parameter variations. In addition, the ranges of values for the utility and pricing parameters for which stability is guaranteed are computed exactly. These results also admit counterparts for the case when the pricing parameters vary across users, but the utility parameter values are still the same. In the general non-symmetric case, when closed-form derivation is not possible, we construct specific randomized algorithms which provide a probabilistic estimate of the local stability of the network. In particular, we use Monte Carlo as well as Quasi-Monte Carlo techniques for the linearized model. The results obtained provide a complete analysis of congestion control algorithms for internet style networks with a single bottleneck node as well as for networks with general random topologies.