Abstract
Network convergence and new applications running on end-hosts result in increasingly variable and unpredictable traffic patterns. By providing origin-destination pairs with several possible paths, load-balancing has proved itself an excellent tool to face this uncertainty. Formally, load-balancing is defined in terms of a convex link cost function of its load, where the objective is to minimize the total cost. Typically, the link queueing delay is used as this cost since it measures its congestion. Over-simplistic models are used to calculate it, which have been observed to result in suboptimal resource usage and total delay. In this paper we investigate the possibility of learning the delay function from measurements, thus converging to the actual minimum. A novel regression method is used to make the estimation, restricting the assumptions to the minimum (e.g. delay should increase with load). The framework is relatively simple to implement, and we discuss some possible variants.
Chapter PDF
Similar content being viewed by others
Keywords
References
Elwalid, A., Jin, C., Low, S., Widjaja, I.: MATE: MPLS adaptive traffic engineering. In: INFOCOM 2001, vol. 3, pp. 1300–1309 (2001)
Kandula, S., Katabi, D., Davie, B., Charny, A.: Walking the tightrope: responsive yet stable traffic engineering. In: ACM SIGCOMM 2005, pp. 253–264 (2005)
Fischer, S., Kammenhuber, N., Feldmann, A.: Replex: dynamic traffic engineering based on wardrop routing policies. In: CoNEXT 2006, pp. 1–12 (2006)
Ben-Ameur, W., Kerivin, H.: Routing of uncertain traffic demands. Optimization and Engineering 6(3), 283–313 (2005)
Larroca, F., Rougier, J.L.: A fair and dynamic Load-Balancing mechanism. In: International Workshop on Traffic Management and Traffic Engineering for the Future Internet (FITRAMEN) 2008, Porto, Portugal (December 2008)
Cassandras, C., Abidi, M., Towsley, D.: Distributed routing with on-line marginal delay estimation. IEEE Trans. Comm. 38(3), 348–359 (1990)
Altman, E., Boulogne, T., El-Azouzi, R., Jiménez, T., Wynter, L.: A survey on networking games in telecommunications. Comput. Oper. Res. 33(2), 286–311 (2006)
Wardrop, J.: Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, Part II 1(36), 352–362 (1952)
Fischer, S., Räcke, H., Vöcking, B.: Fast convergence to wardrop equilibria by adaptive sampling methods. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 653–662 (2006)
Kuosmanen, T.: Representation theorem for convex nonparametric least squares. Econometrics Journal 11(2), 308–325 (2008)
Wasserman, L.: All of Nonparametric Statistics: A Concise Course in Nonparametric Statistical Inference. Springer, Heidelberg (2006)
The MOSEK Optimization Software, http://www.mosek.com/
Cho, K.: WIDE-TRANSIT 150 Megabit Ethernet Trace 2008-03-18, http://mawi.wide.ad.jp/mawi/samplepoint-F/20080318/
The Network Simulator - ns, http://nsnam.isi.edu/nsnam/index.php/Main_Page
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Larroca, F., Rougier, JL. (2009). Minimum-Delay Load-Balancing through Non-parametric Regression. In: Fratta, L., Schulzrinne, H., Takahashi, Y., Spaniol, O. (eds) NETWORKING 2009. NETWORKING 2009. Lecture Notes in Computer Science, vol 5550. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01399-7_61
Download citation
DOI: https://doi.org/10.1007/978-3-642-01399-7_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01398-0
Online ISBN: 978-3-642-01399-7
eBook Packages: Computer ScienceComputer Science (R0)