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

Tansu Alpcan, Tamer Başar, Roberto Tempo

Research output: Contribution to journalArticlepeer-review


This paper initiates a study toward developing and applying randomized algorithms for stability of high-speed communication networks. The focus is on congestion and delay-based flow controllers for sources, which are "utility maximizers" for individual users. First, we introduce a nonlinear algorithm for such source flow controllers, which uses as feedback aggregate congestion and delay information from bottleneck nodes of the network, and depends on a number of parameters, among which are link capacities, user preference for utility, and pricing. We then linearize this nonlinear model around its unique equilibrium point and perform a robustness analysis for a special symmetric case with a single bottleneck node. The "symmetry" here captures the scenario when certain utility and pricing parameters are the same across all active users, for which 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 nonsymmetric 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.

Original languageEnglish (US)
Pages (from-to)1229-1241
Number of pages13
JournalIEEE Transactions on Neural Networks
Issue number5
StatePublished - Sep 2005


  • Communication systems
  • Congestion control
  • Distributed control
  • Monte Carlo methods
  • Pricing
  • Robustness

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Randomized algorithms for stability and robustness analysis of high-speed communication networks'. Together they form a unique fingerprint.

Cite this