Three algorithms for routing and flow control in virtual circuit networks

The problem of choosing a path and adjusting the input rate for each origin-destination pair in the network is solved. In the first model, the average number of packets in the network plus a throughput limitation cost are minimized. In the second model, the allocation to the most poorly treated user(s) subject to link utilization constraints is maximized. The third model, which is a variation of the second model, has an additional constraint which limits the average number of packets in the network. These joint routing and flow control problems are formulated as mixed integer programming problems. The emphasis of this work is to develop near-optimal algorithms to solve these three optimization problems. The basic approach is Lagrangian relaxation. In computational experiments, the algorithms determine solutions that are within a few percent of an optimal solution in minutes of CPU time for networks with 26 to 61 nodes