Computer Networking

Research Focus

As concrete exampls, I am interested in six of Craig Partridge's Forty Data Communications Research Questions as follows.
  • How to identify tussle spaces?
  • What are the incentives for an implementation to faithfully follow the protocol specification?
  • Topology over time?
  • Resource auctions.
  • How do we place information in a network so that users can access it efficiently?
  • What is the right abstraction for programming the cloud?
The first two and the fourth questions are related to Network Economics, the third question is related to the Evolution of the Internet, the fifth one is related to Content Centric Networking, and the final one is related to Big Data Analytics and Cloud Computing.

Auction-Based Resource Allocation for Cloud Service Differentiation

Most existing cloud systems don't recognize users with different preferences or jobs of different natures. This doesn't permit the cloud system to provide service differentiation, which allows a company to pay more in order to get better service, such as more space, faster connections or fewer delays. The lack of service differentiation leads to an inefficient allocation of cloud resources. Abacus is a generic resource management framework that interacts with users to allow them to specify their priorities and job characteristics. Based on this information, Abacus is able to allocate and schedule resources most efficiently.


In Abacus, different jobs receive different quality of service, based on the amount of money the owners of the jobs pay to the cloud platform. Through a carefully designed auction mechanism, Abacus ensures that every job owner's best bidding strategy is to simply tell their true valuation of the job, thus eliminating the need to play price games. To determine pricing of cloud resources, Abacus uses an auction, where users bid more to get more resources, and consequently, better service. The auction mechanism ensures nice properties for users, such as monotonicity, which is when a user pays more, they always receive better service, and truth-telling, which is where a user bids on what they can afford, without studying what other users are bidding. In a poorly designed auction, each user needs to monitor what others bid and respond accordingly and the price often fluctuates a lot; however, Abacus ensures that a user only needs to bid according to her own budget and the price is relatively stable over time.

References


The Public Option: An Alternative to Network Neutrality

Because the Internet only offers a single class of "best-effort" service, it has been a real challenge to enable seamless end-to-end communications and guarantee quality of service (QoS) for real-time immersive telepresence. Besides the engineering factors, this goal becomes even more difficult to be accomplished under the Network Neutrality principle which disallows Internet Service Providers (ISPs) to offer premium services to companies that choose to pay higher fees. While the potential Network Neutrality legislation is still hotly debated in the US and worldwide, We have found a less-intrusive regulatory alternative for the Internet industry: the introduction of a Public Option ISP, which provides higher socio-economic values to Internet users and allows ISPs to efficiently differentiate prices/services.

A Public Option ISP implements a network-neutral policy that does not prioritize traffic and can be run by either government or a private organization. Based on detailed modeling, analysis and experimentations for ISP strategies and user utilities, the Public Option alternative has shown great advantages over Network Neutrality for Internet users under various types of ISP market structures. In monopolistic markets, we found that the ISP's selfish non-neutral prioritization hurts user utilities. Although network neutral regulation can restrict the ISP's malpractice, the existence of a Public Option ISP incentivizes the existing ISP's strategy to be aligned with user utility, and achieve higher user utility than that under network neutral regulations. In oligopolistic competitions, we showed that the market force influences ISPs' non-neutral strategies to be aligned with user utility. Under this case, implementing a neutral Public Option can avoid mistakes or accidental "collusion" with the existing ISPs in the market. In contrast, if network neutral regulation is enforced, all ISPs will be forced to perform neutral but inefficient operation, which would reduce the user utility substantially.

The success of the Public Option approach will have multifold potential impacts on reshaping the landscape of the Internet ecosystem. It will create more competitive and efficient ISP markets and allow diversity in the Internet industry. It will also provide new economic incentives and enable new business models for ISPs to provide new services and better utilities for users. Through competition, more innovative applications will emerge and be supported by the future Internet. Most importantly, the Public Option ISP always plays a role as a safety net for the users by implementing a network-neutral policy which does not prioritize content traffic. The presence of the Public Option will incentivize profit-seeking ISPs in the market to perform paid prioritizations that benefit users; otherwise, they will switch to the Public Option for a better single class service.

References


Economics of the Internet and ISP Settlements

The Internet is composed of thousands of network systems operated by autonomous Internet Service Providers (ISPs). ISPs have to interconnect to and interact with each other to provide Internet services for their customers. Due to the selfish profit-seeking nature of the ISPs, the cooperation among ISPs does not happen voluntarily. In fact, various selfish behaviors encumber the cooperation and induce multiple consequences on the Internet.

Problems

  • The Selfish Routing Problem
    ISPs can make routing decisions by forwarding packets to different neighboring ISPs. Instead of choosing the best path to forward packets, ISPs make choose the least costly routing path to traverse inside its own network. This is often done by using "hot-potato" routing which always forward packets through the nearest egress point to save routing costs. These selfish routing behaviors make the Internet extremely inefficient.

  • The ISP De-peering Problem
    Decades ago, ISPs were homogenous and the traffic pattern was symmetric. They used to interconnect with each other by zero-dollar peering agreements. However, today's ISPs differ dramatically by their characteristics. For example, we can classify ISPs into three categories by the customers they serve: 1) eyeball ISPs that serve individual home-users to get Internet access, 2) content ISPs that serve content providers like Google/Yahoo and Content Distribution Networks (CDNs) like Arkamia, and 3) transit ISPs that serve other ISPs for transit services. ISPs start to charge each other, but not all ISPs are willing to pay what the other party charges. In Oct. 2005, one of the largestest transit ISPs LEVEL 3 unilaterally disconnected all peering links with another transit ISP Cogent, resulting at least 15% of the Internet unreachable for the customers of both ISPs at that time. Without an appropriate compensation structure, ISPs don't have incentive to cooperate by interconnecting and the Internet will start to Balkanize.

  • The Network Neutrality Debate
    Another unsolved problem that hinders the development of the Internet is the debate of network neutrality, which argues whether service differentiations should be provided for Internet services. Eyeball ISPs and transit ISPs support for providing differentiated services, since they want to recoup their investment through differentiated prices. However, content providers advocate the neutrality of the network, which prohibits the discriminations on delivering different contents on the network. They worry about the market power of the incumbent ISPs and their ability to extract profit. Again, without an appropriate compensation structure for the ISPs to share profits, it's difficulty for all ISPs to cooperate and provide better services for customers.

Solutions

  • The Shapley Value Solution
    Proposed by Lloyd Shapley, the Shapley value solution can be used to share profit among a group of cooperative entities. This solution satisfies multiple desirable properties. We introduce three desirable properties that uniquely define the Shapley value solution. We use the following simple example to explain. For a simplified PC industry, we have Microsoft that produces the operating system, i.e. Windows, and Intel and AMD that produce micro-processors. Suppose the profit V from the industry is the total revenue minus the total cost incurred in all firms. The Shapley value solution tells what is the appropriate profit sharing solution for all three firms.
    • Efficiency Property: The profit of all three firms should sum up to V.
    • Symmetry Property: The two symmetric processor producer should obtain the same amount of profit.
    • Fairness Property: For any pair of firms, their marginal contribution to each other should be the same.

    The Shapley value suggests that the unique solution satisfying all above three properties is to give Microsoft 2/3 of the total profit, and 1/6 for both AMD and Intel. By checking the balanced contribution property, we know that without the help of Intel, Microsoft had to evenly share profit with AMD, so the marginal profit is 2/3 - 1/2 = 1/6. It is also the marginal profit Microsoft provides to Intel, because without Microsoft, both processor makers will earn zero profit.

  • The Shapley Mechanism
    Given any static settings of a market structure, we can find the ideal Shapley value profit sharing solutions for all participating entities. We consider the Internet as a group of cooperative ISPs generating profits by serving customers. Each ISP can make selfish decisions on routing and interconnecting. We explore the behaviors of the ISPs and the evolution of the Internet under the policy where a Shapley value profit-sharing is enforced.

    From the figure above, we can enforce a financial settlement mechanism based on the Shapley value solution. Each individual ISPs make various selfish decisions, including routing and interconnecting decision. We have shown that the whole Internet will evolve to converge to a Nash equilibrium where the social welfare is maximized and the global cost is minimized. This means that under the Shapley value mechanism, each ISP's individual profit objective coincides with the global optimality of the Internet.

References