Dynamics of quota sharing in shared data plans

We consider the problem of managing the sharing of data among multiple users in a mobile shared data plan. Such plans allow for quota to be shifted from a user with only small requests in a given month to a user with larger requests. However, in the long run we wish for this sharing to be done in a fair manner. We begin with an intra-month problem in which requests arrive online during a single month and we wish to maximize fairness by the end of the month. For this case we describe an algorithm for which each user receives at least an I/O (log n) fraction of its optimal allocation and we also present a matching lower bound. We next consider a month-by-month version of the problem in which each user has a single usage request for each month and we wish to allocate the group quota in a way that satisfies each request as much as possible while also achieving long-term fairness (as defined by a utility function). For stochastic requests we present an optimal algorithm derived from the theory of wireless scheduling. In contrast, for adversarial requests we show that for any algorithm there may be a user that only receives a 1/n fraction of its optimal allocation. We conclude with the combined problem in which the requests arrive online during the month but we wish to achieve fairness over a longer timescale. For this case we derive the subproblem that must be solved in each individual month and derive a dynamic programming based solution. Our simulations show that our approaches perform well compared to the optimal offline approach that knows the request sequences in advance.