A biased random-key genetic algorithm for OSPF and DEFT routing to minimize network congestion

 R. Reis, M. Ritt, L.S. Buriol, and M. G. C. Resende

International Transactions in Operational Research, vol. 18, pp. 401-423, 2011.


Interior gateway routing protocols like OSPF (Open Shortest Path First) and DEFT (Distributed Exponentially-Weighted Flow Splitting) send flow through forward links towards the destination node. OSPF routes only on shortest-weight paths, whereas DEFT sends flow on all forward links, but with an exponential penalty on longer paths. Finding suitable weights for these protocols is known as the weight setting problem. In this paper, we present a biased random-key genetic algorithm for the weight setting problem using both protocols. The algorithm uses dynamic flow and dynamic shortest path computations. We report computational experiments that show that DEFT achieves less network congestion when compared with OSPF, while yielding larger delays.

PDF file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 17 May 2011

Copyright Notice