Internet and graphs are very much related. The graphical structure of internet has been studied extensively to provide efficient solutions to routing and other problems. But most of these studies assume a central authority which controls and manages the internet. In the recent years game theoretic models have been proposed which do not require a central authority and the users are assumed to be routing their flows selfishly. The existence of Nash Equilibria, congestion and the amount of inefficiency caused by this selfish routing is a major concern in this field. A type of paradox in the selfish routing networks, Braess' Paradox, first discovered by Braess, is a major contributor to inefficiency. Several pricing mechanisms have also been provided which give a game theoretical model between users(consumers) and ISPs ( Internet Service Providers or sellers) for the internet. We propose a novel pricing mechanism, based on real world Internet network architecture, which reduces the severity of Braess' Paradox in selfish routing game theoretic networks. It's a pricing mechanism between combinatorial users and ISPs. We prove that Nash equilibria exists in this network and provide bounds on inefficiency . We use graphical properties of internet to prove our result. Several interesting extensions and future work have also been discussed.
Hayrapetyan et. al @cite_10 analyze among similar lines as us but for their cost function they assume a constant term for the per unit flow price charged by ISPs but in the real world scenario generally the per unit charge decreases if the flow required by the user increases i.e. ISPs provide concession for more flow. Our model captures this. They have not done any analysis of the effect of Braess' Paradox in their network, too. We show that in our model the severity of Braess' Paradox is reduced.
@cite_10
2144615311
Selfish routing is a classical mathematical model of how self-interested users might route traffic through a congested network. The outcome of selfish routing is generally inefficient, in that it fails to optimize natural objective functions. The price of anarchy is a quantitative measure of this inefficiency. We survey recent work that analyzes the price of anarchy of selfish routing. We also describe related results on bounding the worst-possible severity of a phenomenon called Braess's Paradox, and on three techniques for reducing the price of anarchy of selfish routing. This survey concentrates on the contributions of the author's PhD thesis, but also discusses several more recent results in the area. We consider a network where each user is charged a fixed price per unit of bandwidth used, but where there is no congestion-dependent pricing. However, the transmission rate of each user is assumed to be a function of network congestion (like TCP), and the price per unit bandwidth. We are interested in answering the following question: how should the network choose the price to maximize its overall revenue? To obtain a tractable solution, we consider a single link accessed by many users where the capacity is increased in proportion to the number of users. We show the following result: as the number of users increases, the optimal price per unit bandwidth charged by the service provider may increase or decrease depending upon the bandwidth of the link. However, for all values of the link capacity, the service provider's revenue per unit bandwidth increases and the overall performance of each user (measured in terms of a function of its throughput, the network congestion and the cost incurred by the user for bandwidth usage) improves. Since the revenue per unit bandwidth increases, it provides an incentive for the service provider to increase the available bandwidth in proportion to the number of users. Network congestion is a fundamental problem facing Internet users today. A network where users are selfish, and thus reluctant to defer to other users, may result in the famous "tragedy of the commons", where, in the absence of controls, a shared resource is overconsumed by individuals who consider only their personal costs and not the cost to society as a whole. In terms of the Internet, the "tragedy" could be viewed as congestive collapse, resulting from overconsumption of the shared network resource. It is important to distinguish congestion pricing from other forms of network pricing. Charging network users for the congestion they cause can lead to more efficient network utilization by forcing them to take social costs into account. In a congestion-pricing framework, the congestion charge would replace usage and QoS charges. Users would pay their ISPs a subscription charge to cover fixed costs and a congestion charge only when appropriate. This pricing scheme is feasible because, in the absence of congestion, the marginal cost of a network link is practically zero. Congestion pricing can also benefit network operators. By indicating the level of congestion and the user tolerance of it in their networks, congestion pricing can inform operators about when to re-provision and increase network capacity. Pricing content-providers for connectivity to end- users and setting connection parameters based on the price is an evolving model on the Internet. The implications are heavily debated in telecom policy circles, and some advocates of "Network Neutrality" have opposed price based differentiation in connectivity. However, pricing content providers can possibly subsidize the end-user's cost of connectivity, and the consequent increase in end-user demand can benefit ISPs and content providers. This paper provides a framework to quantify the precise trade-off in the distribution of benefits among ISPs, content-providers, and end-users. The framework generalizes the well-known utility maximization based rate allocation model, which has been extensively studied as an interplay between the ISP and the end-users, to incorporate pricing of content-providers. We derive the resulting equilibrium prices and data rates in two different ISP market conditions: competition and monopoly. Network neutrality based restriction on content-provider pricing is then modeled as a constraint on the maximum price that can be charged to content-providers. We demonstrate that, in addition to gains in total and end- user surplus, content-provider experiences a net surplus from participation in rate allocation under low cost of connectivity. The surplus gains are, however, limited under monopoly conditions in comparison to competition in the ISP market.