Analysis on ideal network structures to improve reliability by multi-path and multi-homing BGP routing in the Internet

We analyzed how reliability, defined as the probability of continuing transmissions on link failures, will be affected by inter-domain multi-path and multi-homing routing when the structure in the future Internet changes. The goal of this project is to find properties for the ideal network structure that maximizes the advantage of multi-path and multi-home routing. We focused on how each end-to-end path is built, how many multi-paths exist and how each multi-path consists of no multi-path and multi-path segments. The results of the analyses showed that multi-path and multi-home routing can improve the reliability by 10 to 30% in absolute probability of survivals on link failures, which were two to six times better than the existing no multi-path and no multi-home routing. After the analyses, several interesting properties are identified. It is important to keep the path length short to maximize the benefit from multi-path routing but a large number of multi-paths nor multi-homing connections are not necessary. The multi-homing configurations of degree three improved the reliability up to 50% for link failure rate up to 50% compared to degree of two in our analyses. It is found that single-path edge sections in a path should be short for multi-path routing. The results of this analysis can be a guide in structuring the future Internet.