ISP and Egress Path Selection for Multihomed Networks
Amogh D. Dhamdhere, Constantine Dovrolis · 2006
Multihoming has been used by stub networks for several years as a form of redundancy, improving the availability of Internet access. More recently, Intelligent Route Control (IRC) products allow multihomed networks to dynamically switch parts of their egress or ingress traffic between ISPs, also improving cost and performance. IRC products assume that the set of upstream ISPs is given and fixed. Typically, however, a multihomed network has several ISP choices and the actual selection of ISPs can significantly affect cost, availability, and performance. In the first part of this work, we develop a methodology to select the best set of upstream ISPs, optimizing monetary cost and availability. Our results, based on measurements of actual Internet traffic and topology, show that the proposed algorithm selects the best possible set of ISPs in terms of resiliency to inter-AS single-link failures. The algorithm also performs well in the presence of double or triple link failures. In the second part of this work, we focus on the egress path selection problem. Specifically, we propose a stochastic search algorithm, based on simulated annealing, to allocate the network’s egress traffic between upstream ISPs. The objectives are to minimize cost, also ensuring that the selected paths to the major destinations of egress traffic are congestion-free. Simulation results show that the proposed algorithm performs very well in meeting the previous objectives, when congestion-free paths exist.