In the context of networking, research has focused on non-cooperative games, where the selfish agents cannot reach a binding agreement on the way they would share the infrastructure. Many approaches have been proposed for mitigating the typically inefficient operating points. However, in a growing number of networking scenarios, selfish agents are able to communicate and reach an agreement. Hence, the degradation of performance should be considered at an operating point of a cooperative game. Accordingly, our goal is to lay foundations for the application of the cooperative game theory to fundamental problems in networking. We explain our choice of the Nash bargaining scheme (NBS) as the solution concept, and introduce the price of selfishness (PoS), which considers the degradation of performance at the worst NBS. We focus on the fundamental load balancing game of routing over parallel links. First, we consider agents with identical performance objectives. We show that, while the price of anarchy (PoA) here can be large, through bargaining, all agents, and the system, strictly improve their performance. Interestingly, in a two-agent system or when all the agents have identical demands, we establish that they reach social optimality. We then consider agents with different performance objectives and demonstrate that the PoS and PoA can be unbounded, yet we explain why both measures are unsuitable. Accordingly, we introduce the price of heterogeneity (PoH), as an extension of the PoA. We establish an upper bound on the PoH and indicate its further motivation for bargaining. Finally, we discuss network design guidelines that follow from our findings.

Stackable Routers, i.e. a class of independent routing units operating together as a single router, constitute an affordable scalable approach for coping with the growing networking requirements of organizations. In this study, we investigate several design problems of stackable routers and develop novel schemes for improving their performance. First, we formalize a mathematical model for optimizing the network topology in terms of throughput and delay, while obeying constraints in the number of ports of each internal routing unit. We then consider the problem of minimizing the diameter of the interconnection topology, as a measure of maximum delay, and establish efficient near-to optimal (explicit) topologies. Furthermore, we also consider the problem of maximizing the throughput of a stackable router. We show its hardness and derive bounds for the optimal solution. While, traditionally, the different routing units of a stackable router are linked together in a ring topology, through simulations we show that a major improvement in the diameter of stackable routers can be accomplished even through the employment of randomly-generated topologies. Finally, we investigate the basic problem of constructing a feasible stackable router and establish some fundamental properties of the required structure of the routing units.

Game theoretic models have been widely employed in many networking contexts. Research to date has mainly focused on non-cooperative networking games, where the selfish agents cannot reach a binding agreement on the way they would share the network infrastructure and the operating points are the Nash equilibria. These are typically inefficient, as manifested by large values of the Price of Anarchy (PoA). Many approaches have been proposed for mitigating this problem, however under the standing assumption of a non-cooperative game. In a growing number of networking scenarios it is possible for the selfish agents to communicate and reach an agreement, i.e., play a cooperative game. Therefore, the degradation of performance should be considered at an operating point that is a cooperative game solution. Accordingly, our goal is to lay foundations for the application of cooperative game theory to fundamental problems in networking. We explain our choice of the Nash Bargaining Scheme (NBS) as the solution concept, and we introduce the Price of Selfishness (PoS), which considers the degradation of performance at an NBS. We focus on the fundamental load balancing game of routing over parallel links. First, we study the classical scenario of agents that consider the same performance objectives. While the PoA here can be very large, we establish that, under plausible assumptions, the PoS attains its minimum value, i.e., through bargaining, the selfish agents reach social optimality. We then extend our study to consider the “heterogeneous” case, where agents may consider vastly different performance objectives. We demonstrate that the PoS and PoA can be unbounded, yet we explain why both measures may now be unsuitable. Accordingly, we introduce the Price of Heterogeneity (PoH), as a proper extension of the PoA. We establish an upper-bound on the PoH for a general class of heterogeneous performance objectives, and indicate that it provides incentives for bargaining also in this general case. We discuss network design guidelines that follow from our findings.

The Internet has evolved towards a unique technology base for creating value-added services with worldwide connectivity. These services, enabled by the increasing bandwidth of access networks, result in new high-performance applications (e.g. e-health, high definition video streaming, network gaming etc.) To support and materialize the value of these emerging services, it is important for the operators to be able to provide some form of Quality of Service (QoS) assurance. This paper presents the main economic issues regarding the efficient provisioning of such services in inter-domain level and overviews some candidate economic mechanisms and game-theoretic tools that could be adopted.