Loose-strain loop-free conditions for multiple path IP routing

In shortest path (SP) routing, only the shortest path p_o between a source-and-destination pair is used to route traffic. However, if all data is ´selfishly´ routed through p_o, degradation of network performance due to unregulated traffic along p_o may result. Recent studies show that multipath routing approaches that observe loop-free invariant (LFI) conditions improve network performance. Two new sets of criteria, loose-strain loop-free (LSLF) conditions and simple loose-strain loop-free (SLSLF) conditions, are defined. It is proved that in any given network, P^LFI_i→j⊆P^LSLF_i→j and P^LFI_i→j⊆P^SLSLF_i→j, where P^LFI_i→j, P^LSLF_i→j and P^SLSLF_i→j are the sets of paths from i to j found under LFI, LSLF and SLSLF conditions and also that any path p_i→j∈P^LSLF_i→j or p_i→j∈P^SLSLF_i→j is loop-free. A series of simulations were performed on many practical network topologies (e.g. APRANET and NSFNET). Favourable empirical results show that LSLF and SLSLF conditions outperform both LFI and SP in terms of average maximum flow and resource utilisation.