Strategic fairness in network resource allocation
Sujet proposé par
Directeur de thèse:
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6
Domaine: Sciences et technologies de l'information et de la communication
Communication networks are evolving so that edge network devices, such as mobile phones, tablets but also network access points and virtualization servers are able to be programmed and personalized from the one hand, and to program and customize the downstream network channels themselves from the other hand. The edge network node to transport network interface becomes the border where interactive decision-making problems arise, where network resource sharing becomes a challenging decision in many settings: when the overall demand overcomes the available resource, when the demand can be unjustified, or when the demand is unbounded.
Therefore, fairness shall be ensured. The classical models to define fairness typically are built around the notions of proportional fairness or max-min fairness, which are however biased toward single-decision making thinking. Indeed, the way to measure fairness are also typically biased toward verifying how much proportional or max-min fairness properties are met. In fact, when configuring network allocations, the canonical assumption is that a network provider has full control on all the network devices, including customer's devices and edge network nodes. Such approaches are no longer appropriate in networks where nodes can take unilateral choices such as access a network interface or provider rather than another alternative one, clearly undermining the legacy single-decision making thinking and fairness qualification.
In this research project, the goals are: - to lead to a novel definition of network strategic fairness that can be provably acceptable for all the stake-holders in a reference set of interactive networking problems; - to design a portfolio of network resource allocation algorithms that are coherent to the strategic fairness definition.
A number of application use-cases will be considered, starting from the management of shared computing capacity in network functions virtualization infrastructures and the management of shared wireless spectrum in orthogonal and non-orthogonal spectrum allocation.
References:  Gupta, A., Jukic, B., Parameswaran, M., Stahl, D. O., & Whinston, A. B. (1997). Streamlining the digital economy: how to avert a tragedy of the commons. IEEE Internet Computing, (6), 38-46.  Nace, D., & Pióro, M. (2008). Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial. Communications Surveys & Tutorials, IEEE, 10(4), 5-17.  A. B. Atkinson. On the measurement of inequality. Journal of Economic Theory, 2(3): 244–263, 1970.  Jain, R., Chiu, D., & Hawe, W. (1998). A Quantitative Measure Of Fairness And Discrimination For Resource Allocation In Shared Computer Systems. arXiv research report cs/9809099.  Saad, W., Han, Z., Debbah, M., Hjørungnes, A., & Başar, T. (2009). Coalitional game theory for communication networks. Signal Processing Magazine, IEEE, 26(5), 77-97.  Saad, W., Han, Z., Debbah, M., Hjorungnes, A., & Başar, T. (2009, April). Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks. In Proc. of INFOCOM 2009. IEEE.  Saad, W., Han, Z., Poor, H. V., & Başar, T. (2012). Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications. Signal Processing Magazine, IEEE, 29(5), 86-105.  Hoteit, S., Secci, S., Langar, R., & Pujolle, G. (2013). A nucleolus-based approach for resource allocation in OFDMA wireless mesh networks. Mobile Computing, IEEE Trans. on, 12(11), 2145-2154.  Langar, R., Secci, S., Boutaba, R., & Pujolle, G. (2015). An operations research game approach for resource and power allocation in cooperative femtocell networks. Mobile Computing, IEEE Transactions on, 14(4), 675-687.  Hoteit, S., El Chamie, M., Saucez, D., & Secci, S. (2015). On Fair Network Cache Allocation to Content Providers. hal-01112367 HAL Open Archive. 2015.  Shneidman, J., & Parkes, D. C. (2004, July). Specification faithfulness in networks with rational nodes. In Proc. of the 23rd annual symposium on Principles of distributed computing. ACM.  Stoica, I., et al. (1996). A proportional share resource allocation algorithm for real-time, time-shared systems. In Proc. of Real-Time Systems Symposium. IEEE.  Aumann, R. J., & Maschler, M. (1985). Game theoretic analysis of a bankruptcy problem from the Talmud. Journal of economic Theory, 36(2), 195-213.  L. Shapley, A value for n-person games, H Kuhn and A Tucker, eds, Contributions to the Theory of Games, Vol. 2 of Annals of Mathematics Studies, Princeton U Press., 1953.  T. Driessen, Cooperative Games, Solutions and Applications, Kluwer Academic Publishers, 1988.  Mijumbi, R., et al. (2015). Network Function Virtualization: State-of-the-art and Research Challenges. IEEE Communications Survey and Tutorials, on-line first.  Lan, T., Kao, D., Chiang, M., & Sabharwal, A. (2010). An axiomatic theory of fairness in network resource allocation (pp. 1-9). In Proc. of INFOCOM 2010. IEEE.  Benjebbour, A., et al. (2013, November). Concept and practical considerations of non-orthogonal multiple access (NOMA) for future radio access. In Proc. of ISPACS 2013. IEEE.  Moretti, S. (2015). An Axiomatic Approach to Social Ranking Under Coalitional Power Relations. Homo Oeconomicus 32 (2), 183.  Lucchetti, R., Moretti, S., & Patrone, F. (2014). Ranking sets of interacting objects via semivalues. TOP, 1-24.  Michalak, T. P., Rahwan, T., Moretti, S., Narayanam, R., Skibski, O., Szczepański, P., Wooldridge, M. (2015). A new approach to measure social capital using game-theoretic techniques. ACM SIGecom Exchanges, 14(1), 95-100.
Defining a new notion of network fairness is an ambitious goal and requires a detailed and in-depth review of a large state of the art in both networking literature and game/decision theory literature. Approximately the first year of the research project will be spent in setting the basis of a new notion of strategic fairness, with a methodology to be defined and that could be an axiomatic approach.
The design of network resources allocation algorithms around a few reference use-cases will take the last two years of the PhD, in order to position the contribution with respect to specific solutions that are already proposed in the literature of the precise networking research area covering the use-case, which can range from network virtualization research (in particular Network Functions Virtualization Infrastructure sharing) to wireless networking areas (in particular unlicensed wireless spectrum sharing).