Home Problem Statement
Multihoming is an increasingly popular method for large enterprises, stub ISPs and even small businesses to connect to the Internet. Recent studies suggest that the potential performance benefits of multihoming can be quite significant. However, it remains an open problem how to achieve such benefits in practice, and what impacts multihoming will have on the Internet.
How to optimize cost and performance for multihomed networks?
We design a series of novel smart routing algorithms to optimize cost and performance for multihomed users. We evaluate our algorithms through both analysis and extensive simulations based on realistic charging models, traffic demands, performance data, and network topologies. Our results suggest that these algorithms are very effective in minimizing cost and at the same time improving performance. We further evaluate smart routing in a global setting and show that a smart routing user can improve its
How to optimally multihome to multiple providers?
This is the so-called ISP subscription problem, i.e., how to choose the optimal set of ISPs to subscribe to. We design a dynamic programming algorithm to solve the ISP subscription problem optimally. We also design a more efficient algorithm for a large class of common pricing functions. Using real traffic traces and realistic pricing data, we show that our algorithm reduces users' cost.
How multihoming will affect ISP pricing models?
This is so-called ISP pricing problem, i.e., how ISPs respond to users' optimal ISP subscription by adjusting their pricing strategies.
Using a realistic charging model, we formulate the problem as a non-cooperative game. We first prove that if cost is the only criterion used by a user to determine which subset of ISPs to subscribe to, at any equilibrium all ISPs receive zero revenue.
We then study a more practical formulation in which different ISPs provide different levels of reliability and users choose ISPs to both improve reliability and reduce cost. We analyze this problem and show that at any equilibrium an ISP's revenue is positive and determined by its reliability.
Paper Toys
- Optimal ISP Subscription for Internet Multihoming: Algorithm Design and Implication Analysis.
Hao Wang, Haiyong Xie, Lili Qiu, Avi Silberschatz, and Yang Richard Yang.
In Proceedings of IEEE INFOCOM '05, Miami, Florida, March 2005.
(PDF)
)
- Optimizing Cost and Performance for Internet Multihoming, David Goldenberg, Lili Qiu, Haiyong Xie, Yang Richard Yang, and Yin Zhang. In Proceedings of ACM SIGCOMM '04, Portland, Oregon, August 2004. (PDF)
- Optimal ISP Subscription for Internet Multihoming: Algorithm Design and Implication Analysis, Hao Wang, Haiyong Xie, Lili Qiu, Avi Silberschatz, Yang Richard Yang, Yale Computer Science Technical Report YALEU/DCS/TR-1299, July 2004. (PDF)