Derives a time complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of the Goldstein-Levitin-Poljak type formulated by Bertsekas (1982) converges to within /spl epsiv/ in relative accuracy in O(/spl epsiv//sup 2/h/sub min/N/sub max//sup L/) iterations, where N/sub max//sup L/ is the number of paths sharing the maximally shared link, and h/sub min/ is the diameter of the network. Based on this complexity result, the authors also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy [Bertsekas, 1982], where n is the number of nodes in the network. The result of the paper argues for constructing networks with low diameter for the purpose of reducing the complexity of the network control algorithms. The result also implies that parallelizing the optimal rotating algorithm over the network nodes is beneficial.
展开▼
机译：推导了梯度投影方法的时间复杂度界限，以实现数据网络中的最佳路由。该结果表明，由Bertsekas（1982）提出的Goldstein-Levitin-Poljak类型的梯度投影算法在O（/ spl epsiv // sup 2 / h / sub min / N / sub max // sup L /）迭代，其中N / sub max // sup L /是共享最大共享链路的路径数，h / sub min /是网络的直径。基于这种复杂性结果，作者还表明，一次一次更新策略的复杂度比一次一次更新策略的复杂度小O（n）倍[Bertsekas （1982年），其中n是网络中的节点数。论文的结果为降低网络控制算法的复杂性提出了构建低直径网络的建议。该结果还暗示在网络节点上并行化最佳旋转算法是有益的。
展开▼
