In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of Goldstein-Levitin-Poljak type formulated by Bertsekas (1982), Bertsekas and Gallager (1987) and Bertsekas et al. (1984) converges to within /spl epsi/ in relative accuracy in O(/spl epsi//sup -2/h/sub min/N/sub max/) number of iterations, where N/sub max/ 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, we 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, where n is the number of nodes in the network. The result of this paper argues for constructing networks with low diameter for the purpose of reducing complexity of the network control algorithms. The result also implies that parallelizing the optimal routing algorithm over the network nodes is beneficial.
展开▼
机译：在本文中，我们推导了用于数据网络中最佳路由的梯度投影方法的时间复杂性界。这个结果表明，由Bertsekas（1982），Bertsekas和Gallager（1987）以及Bertsekas等人提出的Goldstein-Levitin-Poljak型梯度投影算法。 （1984）在O（/ spl epsi // sup -2 / h / sub min / N / sub max /）迭代次数中，相对精度收敛到/ spl epsi /以内，其中N / sub max /是共享最大共享链接的路径，h / sub min /是网络的直径。根据此复杂度结果，我们还表明，一次一次更新策略的复杂度边界比一次一次更新策略的复杂度边界小O（n）倍，其中n是网络中的节点数。本文的结果为降低网络控制算法的复杂度而提出了构建小直径网络的建议。该结果还暗示在网络节点上并行化最佳路由算法是有益的。
展开▼
