Michael D. Dahlin Department of Computer Sciences University of Texas at Austin Taylor Hall 2.124 Austin, TX 78712-1188 dahlin@cs.utexas.edu (512)471-9549 (512)471-8885 (fax) Thanks. -mike Globally Efficient Resource Management for the Next Generation Internet Lorenzo Alvisi, Michael Dahlin, Calvin Lin Computer Sciences Department, University of Texas at Austin Andrew Whinston Management Science and Information Systems, Economics Department, and Computer Sciences Department University of Texas at Austin Dale Stahl Economics Department, University of Texas at Austin Jon Kay National Laboratory for Applied Network Research Introduction ------------ As the Internet is transformed from an academic and research network into a popular medium for education, communication, entertainment, and business, we face the critical issue of allocating resources among millions of competing users, services, and applications. In the past, the Internet community was small enough that "netiquette" combined with ample capacity sufficed to deliver resources to users. However, with more users and more demanding applications, demand for resources will overwhelm improvements in network bandwidth and latency. Therefore, to realize the potential of the Next Generation Internet, it is essential to develop methods that encourage globally efficient use of resources. Currently, the Internet fails to provide incentive compatibility: by trying to improve individual performance, users may hurt the performance of the system as a whole. Current systems therefore face the "tragedy of the commons" in which the net social benefits of the system are diminished by overuse and inefficient use. For example, while a single user might benefit from a browser that aggressively prefetches all links leading from the current page, such prefetching would increase the load on the servers, hurting other users: if too many users prefetch, they will all see degraded performance due to server overload. By the turn of the century, congestion and misallocation of Internet resources could cost the economy tens of billions of dollars per year [1]. We believe that economic theory provides an approach to solving such dilemmas. The basic principle is to maximize the net social benefits of the system by confronting users with the global cost of their usage. For example, the price of trying to use a congested link should reflect the social cost of congestion, ie, the congestion imposed on the rest of the users. Thus, low- value congestion-producing service requests will be voluntarily reallocated to off-peak time, while high-value low-load needs will be accommodated with minimal delay. Research Agenda --------------- To realize such a system, we must undertake a research agenda that leverages expertise in both computer systems and economic theory. Research issues in computer systems range from scheduling to network protocols to security. We must develop resource scheduling mechanisms for individual nodes that (1) coordinate multiple resources including the network, disk, memory, and processor, (2) dynamically allocate resources among hard-, soft-, and non-real-time applications, and (3) provide simple, predictable performance that the economic model can reason about. We must also develop distributed resource scheduling protocols that provide these properties across multiple nodes. Furthermore, we must develop network protocols that prioritize traffic in ways compatible with the economic model. And we must develop secure interfaces based on electronic cash algorithms to prevent cheating in a competitive environment. Finally, we must develop better understanding of how to model the Internet and its workloads so that we can reason about, simulate, and finally build this large-scale system. For the economic model, we plan to build on the dynamic optimal congestion pricing scheme developed under several NSF projects lead by Stahl and Whinston [1]. This model combines a theoretically optimal pricing scheme with priorities for different users and applications, and it provides a more scalable and theoretically well grounded approach than previous economics-based efforts such as continuous auctions. The research challenge is to extend this work to account for the details of large-scale computer and network architectures and to implement and test it in a realistic environment. In particular, the model must be extended to rely on probabilistic or less precise information about user requirements and system capacity, and it must be refined to account for the details of node and network scheduling, priority schemes, queue disciplines, and so on. Developing a practical system requires the two communities to work closely together. For example, we must balance the cost of making good resource allocation decisions against the benefits and overhead of making better allocation decisions. Solving this problem will require innovations in both the economic models (e.g., basing decisions on incomplete information) and the system protocols (e.g., making decisions on a network flow, but enforcing decisions on each individual packet). There is a potential social barrier to the adoption of a more rational, economics-based approach towards resource allocation. People have become accustomed to viewing network resources as "free" and may find even a nominal charge too annoying to bear. While significant, we believe that this problem is surmountable for both social and technical reasons. On the social side, we observe that the current system does, in fact, charge for use, but it does so in terms of time, not money. Economic theory suggests that people will be more satisfied if resources are rationed by a well structured price system rather than by queuing and delaying requests. Certainly, many users would be willing to a pay nominal charge (e.g., a dollar a day) to significantly reduce the latency of their accesses. On the technical side, the challenge is to provide unobtrusive mechanisms to account for usage. For example, it would not make sense for a browser to display a dialog box asking the user for a budget for each page fetched because in economic terms, the cost of interrupting the user would be higher than the gain of efficiency in the network. Instead, we must design agents that manage resources with minimal user intervention. Conclusion ---------- A simple brute-force approach to solving network congestion by building bigger and faster networks is doomed to fail because of the explosive increase in the numbers of users and the increasingly demanding applications they run. The only way to realize the full potential of the Next Generation Internet is to devise globally efficient resource management techniques. Any centralized management scheme is clearly not scalable. Our proposed use of economic models promises a distributed solution in which global objectives are achieved through local, independent choices. [1] Gupta, A, Stahl, D. and Whinston, A., "An Economic Approach to Network Computing with Priority Classes," Journal of Organizational Computing and Electronic Commerce, 6(1), 71-95, 1996.