Fair allocation of utilities in multirate multicast networks: a framework for unifying diverse fairness objectives

Saswati Sarkar, Leandros TassiulasIEEE Trans. Automatic Control 2002 · DOI · OpenReview

TL;DR

This paper introduces a unified framework for fair resource allocation in multirate multicast networks, where different users can receive data at varying rates. They propose a novel algorithm that guarantees a maximally fair utility allocation in polynomial time, even for complex, non-strictly increasing utility functions, addressing a significant challenge in modern network management.

What Problem Does This Paper Address?

In today's diverse network environments, multicast applications (like video conferencing or streaming) serve groups of users with vastly different capabilities and connection speeds. A single transmission rate for all users is inefficient, either overwhelming slow receivers or underutilizing fast ones. This heterogeneity necessitates sophisticated resource allocation strategies that go beyond simple rate fairness. The challenge lies in defining and achieving "fairness" when users have different needs and preferences, which can be modeled as arbitrary "utility functions" of bandwidth. Existing fairness notions, like max-min fairness, often struggle with these general utility functions, and their computation can be computationally intractable. This paper aims to bridge this gap by providing a general framework and an efficient algorithm for fair utility allocation in such complex scenarios.

Methods

The core of this paper is a novel algorithm designed to compute a "maximally fair" utility allocation. This algorithm operates iteratively, progressively assigning utilities to virtual sessions (a source-destination pair within a multicast session). Key aspects of the method include:

  • Utility Functions: The framework accommodates general utility functions, which can be non-continuous, non-strictly increasing, and have discrete "jumps" representing layers of data. This is a significant departure from prior work that often assumed simpler, strictly increasing functions.
  • Maximally Fair Allocation: Instead of relying on max-min fairness (which may not exist for general utilities), the paper introduces and focuses on "maximal fairness." This notion ensures that no user's utility can be increased without decreasing another user's utility in a way that violates fairness principles.
  • Iterative Algorithm: The algorithm works by classifying sessions as "saturated" or "unsaturated." In each iteration, it computes "fair shares" for sessions at each network link, considering link capacities and session utility functions. The algorithm progressively refines these allocations, aiming to saturate sessions according to fairness criteria.
  • Generalized Bottleneck Link: A key theoretical concept introduced is the "generalized bottleneck link." The paper proves that a utility allocation is maximally fair if and only if every virtual session has such a link. This concept helps in understanding the conditions under which fairness is achieved.
  • Polynomial Time Convergence: A crucial contribution is the proof that the proposed algorithm converges to a maximally fair allocation in a polynomial number of iterations, making it practical for real-world network deployment.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and algorithmic design, using illustrative examples and network topologies rather than empirical datasets.

Key Insights and Ideas

  • Unified Fairness Framework: The concept of "utility" provides a powerful, unifying abstraction for diverse fairness objectives. By considering arbitrary utility functions, the framework can encompass notions like proportional fairness, max-min fairness, and even user-defined preferences based on willingness to pay or quality of service.
  • General Utility Functions are Crucial: The paper highlights that real-world scenarios often involve non-strictly increasing and discontinuous utility functions (e.g., due to layered encoding). Ignoring this complexity leads to incomplete or incorrect fairness guarantees.
  • Maximally Fair is Achievable and Practical: While max-min fairness might be ideal, it's not always achievable or computationally feasible. Maximal fairness offers a robust alternative that is both theoretically sound and algorithmically tractable, providing a practical target for network resource allocation.
  • The Power of "Generalized Bottleneck Links": This theoretical construct elegantly captures the conditions for maximal fairness, linking network topology, link capacities, and user utilities to the fairness outcome.

Key Results

  • Algorithm for Maximally Fair Allocation: The paper presents an algorithm that computes a maximally fair utility allocation for multirate multicast networks with general utility functions.
  • Polynomial Time Convergence: The algorithm is proven to terminate in a polynomial number of iterations, making it efficient. The bound on iterations is O(|L|²M³), where |L| is the number of links and M is the number of virtual sessions.
  • Theoretical Guarantees: The output allocation is proven to be maximally fair. Furthermore, if a max-min fair allocation exists, the algorithm will find it.
  • Illustrative Example: A concrete example demonstrates the algorithm's operation and the difference between max-min and maximally fair allocations in a specific network scenario.

Limitations and Future Work

  • Computational Complexity: While polynomial, the O(|L|²M³) complexity might still be high for very large networks. The authors suggest exploring lower-complexity algorithms or approximation schemes.
  • Distributed Implementation: The paper notes that the algorithm is amenable to distributed implementation, but the proof of maximal fairness relies on some global information in step 8. Further work could explore fully distributed versions.
  • NP-Hardness of Lexicographical Optimality: The paper acknowledges that computing a lexicographically optimal utility allocation is NP-hard for general utility functions. Future research could focus on approximation algorithms or heuristics for this more stringent fairness criterion.
  • Connection to Pricing: The authors suggest exploring the connection between utility functions and pricing mechanisms as a promising avenue for future research.

Summary updated

Abstract

We study fairness in a multicast network. We assume that different receivers of the same session can receive information at different rates. We study a fair allocation of utilities, where the utility of a bandwidth is an arbitrary function of the bandwidth. The utility function is not strictly increasing, nor continuous in general. We discuss fairness issues in this general context. Fair allocation of utilities can be modeled as a nonlinear optimization problem. However, nonlinear optimization techniques do not terminate in a finite number of iterations in general. We present an algorithm for computing a fair utility allocation. Using specific fairness properties, we show that this algorithm attains global convergence and yields a fair allocation in polynomial number of iterations.
BibTeX
@article{sarkar2002fair,
  author = {Saswati Sarkar and Leandros Tassiulas},
  title = {{Fair allocation of utilities in multirate multicast networks: a framework for unifying diverse fairness objectives}},
  journal = {IEEE Trans. Automatic Control},
  year = {2002},
  doi = {10.1109/tac.2002.1008359},
}
Figure