| The Internet is composed of many distinct networks operated by independent business entities, also referred to as the Internet Service Providers (ISPs). The ISPs' incentives interact in many ways, in particular in interconnection agreements that ensure end-to-end connectivity as well as in inter domain traffic routing decisions that ensure end-to-end routing. This interaction of incentives manifests itself as conflict of interests and it becomes imperative to look into contracts and mechanisms that not only acknowledge the conflict of interests but also work well in its presence. The tools of micro-economic theory, especially game theoretic approaches are particularly suitable for this purpose. In this thesis, we apply game theoretic tools at two specific problems: one related to interconnection agreements and another related to interdomain traffic engineering.; We first analyze a specific interconnection agreement, called peering, under the non-cooperative game theory framework, using Nash games of complete information as well as a simple two provider model where cost functions absorb network complexity. We start by looking at ISP peering in absence of competition for customers and provide an intuitive sufficient condition for the ubiquitous Bill-and-Keep peering to be individually rational. However, we show that participation in Bill-and-Keep peering is not guaranteed, and introduction of access pricing is necessary. That is, paid peering is always mutually beneficial. We then analyze peering in presence of access pricing and show that it has the following properties: first, the ISP with the lower marginal cost in the absence of peering has no incentive to use the resources of the other supplier and effectively acts as a resource supplier; and second, under certain conditions not only the effective supplier has an incentive to upgrade the capacity of its links but also this incentive is higher when the effective supplier is in a peering relationship. Finally, we look at ISP peering in presence of competition for customers and present some preliminary results. These results suggest that paid peering should be encouraged since not only it is Pareto superior to Bill-and-Keep peering but also it encourages investment in capacity upgrades.; We also present a new inter-domain traffic engineering protocol based on the concepts of Nash bargaining and dual decomposition. Under this scheme, ISPs use an iterative procedure to jointly optimize a social cost function, referred to as the Nash product. We show that the global optimization problem can be separated into sub-problems by introducing appropriate shadow prices on the inter-domain flows. These sub-problems can then be solved independently and in a decentralized manner by the individual ISPs. Our approach is not only Pareto-efficient and fair but also it does not require the ISPs to share any sensitive internal information. However, it suffers from the limitation that it is not incentive compatible---we plan to address this in future work. We conduct simulation studies of our approach over several real ISP topologies. Our evaluation shows that the approach converges quickly, offers equitable performance improvements to ISPs, is significantly better than unilateral approaches (e.g. hot potato routing) and offers the same performance as a centralized solution with full knowledge. |
