In this paper, we derive a time-complexity bound for the gradient projectio
n method for optimal routing in data networks. This result shows that the g
radient projection algorithm of the Goldstein-Levitin-Poljak type formulate
d by Bertsekas converges to within epsilon in relative accuracy in O(epsilo
n(-2)h(min)N(max)) number of iterations, where N-max is the number of paths
sharing the maximally shared link, and h(min) is the diameter of the netwo
rk. 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.