Evolutionary algorithms for globally optimised multipath routing

Abstract

With the ever increasing rise of traffic generated on the Internet, the efficiency with which a network operates has become of great importance. The use of a distributed network architecture and single path routing algorithms limits the level of efficiency a network is able to sustain. To tackle this problem, a set of novel, globally optimal, multipath capable routing algorithms are proposed. The routing algorithms are designed to increase the total network flow routed over a given network, while giving preference to lower delay paths. Two routing algorithm frameworks are proposed in this work; one using Linear Programming (LP) and the other using a Multi-Objective Evolutionary Algorithm (MOEA). Compared to Evolutionary Algorithms (EAs), which are inherently sub-optimal, the LP routing algorithm is guaranteed to find a solution with the maximum load a network is able to handle without exceeding the link’s capacity. However, LP solvers are unable to concurrently optimise for more than one objective. On the other hand, EAs are able to handle multiple, possibly non-linear objectives, and generate multiple viable solutions from a single run. Even though EAs are inherently sub-optimal, the EAs designed here manage to satisfy, on average, 98% of the demand found by the optimal LP generated solution. All routing algorithms designed in this work make use of Per-Packet multipath because of its increased flexibility when compared to its Per-Flow multipath counterpart. It is well known that connection oriented protocols, such as TCP, suffer from severe performance degradation when used in conjunction with a Per-Packet multipath routing solution. This problem is solved by adding a custom scheduler to the Multipath TCP (MPTCP) protocol. Using the modified MPTCP protocol, TCP flows are able to reach a satisfaction rate of 100%, with very high probability even when that flow is transmitted over multiple paths. The combination of the modified MPTCP protocol and the designed routing algorithm(s) led to a network that is able to handle more load without sacrificing delay, when compared to OSPF under all the conditions tested in this work using network simulations.