Alpcan Tansu, Başar Tamer, Tempo Roberto
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA.
IEEE Trans Neural Netw. 2005 Sep;16(5):1229-41. doi: 10.1109/TNN.2005.853412.
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.
本文开启了一项关于开发和应用随机算法以实现高速通信网络稳定性的研究。重点在于针对源端的基于拥塞和延迟的流量控制器，这些控制器是单个用户的“效用最大化器”。首先，我们为这种源端流量控制器引入一种非线性算法，该算法将网络瓶颈节点的聚合拥塞和延迟信息用作反馈，并依赖于多个参数，其中包括链路容量、用户对效用的偏好以及定价。然后，我们围绕其唯一平衡点对该非线性模型进行线性化，并针对具有单个瓶颈节点的特殊对称情况进行鲁棒性分析。这里的“对称性”描述了所有活跃用户的某些效用和定价参数相同的情形，针对这种情况，我们推导出了在参数变化下稳定性和鲁棒性的闭式充要条件。此外，还精确计算了保证稳定性的效用和定价参数的取值范围。这些结果在定价参数因用户而异但效用参数值仍相同的情况下也有相应的情况。在一般非对称情况下，当无法进行闭式推导时，我们构建特定的随机算法，这些算法提供了网络局部稳定性的概率估计。特别是，我们对线性化模型使用了蒙特卡罗以及拟蒙特卡罗技术。所获得的结果对具有单个瓶颈节点的互联网风格网络以及具有一般随机拓扑结构的网络的拥塞控制算法进行了全面分析。
