Stable Matching in Networking
Matching is perhaps one of the most important functions of markets. The stable marriage problem, introduced by Gale and Shapley, is arguably one of the most interesting and successful abstractions of such markets. There are men and women, looking for partners, as shown in the figure below. Each has a ranking, or preference, over agents of the opposite gender. Given marriages that assign each man to a woman, the following is certainly not desirable with respect to individual rationality: there exists a pair of man and woman who both prefer each other to their assigned partners. Such a pair is unstable in the sense that they have a clear incentive to break up from the current marriage and marry each other instead. Therefore, a good marriage does not induce any such unstable pairs: it is stable. When the problem is extended beyond a one-to-one setting (such as in the college admissions problem), it is more generally referred to as stable matching.
An example of a marriage market. The matching shown is a stable matching.
Matching problems also exist pervasively in networking, ranging from assigning channels to users and flows in wireless scheduling, to mapping video segments to servers in video-on- demand streaming systems. In many cases, network elements are controlled by some central entity, and a metric of utility may be easily defined. The problem can then be formed into an optimization problem that can be systematically solved in a centralized or distributed manner, without paying respect to individual rationality.
However, as technologies evolve and networks become complex, optimization becomes monolithic, sometimes even inept, to be used in practice. Its effectiveness hinges upon the availability of complete and accurate information, which may not be realistic in practical settings. Parameter values serving as inputs may be distorted by delayed, noisy, or inaccurate measurements, which may lead to a significant “drift” in a computed optimal solution from the actual optimum. Further, an optimization algorithm needs to enumerate combinations of agents from both sides to find the optimal solution, which is computationally expensive.
Many large-scale networked systems, such as peer-to-peer networks, consist of numerous autonomous components. The interests of these selfish agents are not aligned, and individual rationality needs to be taken into account. While game theory is widely adopted in such scenarios, its existing use often relies on some rigorous definition of utility. Oftentimes it is difficult to quantize and unify the effects of various factors into a single utility function, not to mention the stringent requirement of complete information that is implicitly assumed. In practice, these techniques are not widely adopted due to these difficulties though theoretically sound.
Seen As Stable Marriages: As our first milestone, in this INFOCOM 2011 mini-conference paper, we advocate the use of stable matching as a general framework to tackle networking problems, where preferences are used to model each agent’s interest, and stability serves as the solution concept instead of optimality. The use of the stable matching framework is a substantial and likely controversial shift from utility-based optimization or game-theoretic solution methods. Merits of the stable matching framework lie in the competitiveness of outcomes, generality of the preferences, efficiency and simplicity of its algorithmic implementations, and most importantly, its overall practicality. Stable matchings are in the core of the market that cannot be improved upon by a coalition of agents. The generic preferences embrace many heterogeneous and complex considerations that different agents may have. The classical deferred acceptance algorithm can be applied in a centralized manner with little complexity. In addition, we propose a new decentralized mechanism that yields exactly the same outcome without centralized coordination at the helm. As a case study, we present a problem related to content-eyeball ISP peering, and illustrate how it can be modelled and solved as a variant of stable matching problems.
Anchor: A Stable Matching Framework for Managing Cloud Resources: In this work, we present a novel architecture that decouples policies from mechanisms when it comes to managing resources in a public cloud, based on stable matching. Stakeholders in the cloud, including both cloud operators and their clients, are able to express and configure their high-level resource management policies. These policies are abstracted as preferences in the stable matching framework. A new set of deferred acceptance algorithms, serving as the underly mechanisms of the resource market, are developed to deal with the size heterogeneity of virtual machines, which has not been studied and modeled in previous work in both economics and computer science. Anchor has been implemented and evaluated on our 20-node cloud tested based on Oracle VirtualBox.
