|
|||||
|
|
A biased random‐key genetic algorithm for OSPF and DEFT routing to minimize network congestion |
|
| Authors: | Roger Reis Marcus Ritt Luciana S. Buriol Mauricio G. C. Resende |
| Affiliation: | 1. Universidade Federal do Rio Grande do Sul, Instituto de Informática, Av. Bento Goncalves, 9500, Campus do Vale, Bloco IV, Bairro Agronomia, Porto Alegre, RS, Brazil E‐mail: rsreis@inf.ufrgs.br, mrpritt@inf.ufrgs.br, buriol@inf.ufrgs.br;2. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ 07932, USA E‐mail: mgcr@research.att.com |
| Abstract: | Interior gateway routing protocols like Open Shortest Path First (OSPF) and Distributed Exponentially Weighted Flow Splitting (DEFT) send flow through forward links toward 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 (WSP). In this paper, we present a biased random‐key genetic algorithm for WSP 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, however, yielding larger delays. |
| Keywords: | networks networking telecommunication networks routing genetic algorithm biased random‐key genetic algorithm local search metaheuristics |