We consider the routing problem in wireline, packet-switched communication networks. We cast our optimal routing
problem in a multicommodity network flow optimization framework. Our cost function is related to the congestion
in the network, and is a function of the flows on the links of the network. The optimization is over the set of flows
in the links corresponding to the various destinations of the incoming traffic. We separately address the
single commodity and the multicommodity versions of the routing problem. We consider the dual problems,
and using dual decomposition techniques, we provide primal-dual algorithms that converge to the optimal solutions
of the problems. Our algorithms, which are subgradient algorithms to solve the corresponding dual
problems, can be implemented in a distributed manner by the nodes of the network. For online, adaptive
implementations of our algorithms, the nodes in the network need to utilize ‘locally available
information’ like estimates of queue lengths on outgoing links. We show convergence to the optimal
routing solutions for synchronous versions of the algorithms, with perfect (noiseless) estimates of
the queueing delays. Every node of the network controls the flows on the outgoing links using the
distributed algorithms. For both the single commodity and multicommodity cases, we show that our
algorithm converges to a loop-free optimal solution. Our optimal solutions also have the attractive
property of being multipath routing solutions.