Position statement for Strategic directions in Computing Symposium Baruch Awerbuch Dept. of Computer Science Johns Hopkins University 3400 N. Charles str Baltimore MD 21218 202 321 4444 (mobile) 410 516 8038 (office) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% MAXIMIZING GROSS NETWORK PRODUCT (GNP): RESOURCE MANAGEMENT ON THE GII %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PROBLEM: ONLINE DISTRIBUTED ACCESS TO HETEROGENEOUS RESOURCES. ------------------------------------------------------------------- The ``information revolution'' and the emerging Global Information Infrastructure enable ubiquitous access to highly heterogeneous resources, such as processing, communicating, and storage. The result is a "metacomputing" environment where user requests are generated and served in an online and distributed fashion by currently available remote resources. The question is, how does one efficiently resolve conflicting demands from different users for the common resource pool ? This question arises in a variety of contexts, such as multiprocessor job scheduling, network bandwidth management, and mass-storage systems management. IS FAIRNESS FAIR ? --------------------- ``Fair'' allocation, namely, allocating same amount of resources to each user, is the obvious idea, but it appears difficult to define in a natural way. The basic difficulty is that fairness may provide the incentive to ``over-subscribe'' in order to achieve the required service level. This is pretty much how the bandwidth is currently allocated on the Internet. Is this a viable approach in view of the exponential growth in the Internet population ? DOES GREED PAY OFF ? -------------------------- Another problem is the availability of the scarce system resources. The natural approach is to use the ``greedy'' policy and to serve the users as long as resources are available. The obvious disadvantage is that some users may consume a lot of resources, and thus ``fairness'' to the future users suggests that resources may need to be rationed. GNP: MAXIMIZE COMMUNAL WELL-BEING ------------------------------------ Since neither ``greed'' nor fairness appear to be satisfactory in a multi-user environment with heterogeneous resources, we suggest using the ``Gross Network Product'' as the a different indicator of effectiveness for a network resource management policy. Specifically, ``service value'' is assigned by each user to any given level of service. ``Gross Network Product'' (GNP) is the total sum of the values of the services provided, The goal of a policy is to maximize the GNP. The system thus should price its services in a certain way that will impose a self-discipline for the users and discourages them from excessive resource consumption. GAME-THEORETIC FRAMEWORK. ------------------------------- One can look on it differently: say, network establishes a price for each level of service based on the availability of resources and the current demand, and tries to maximize its own revenues. Observe that if the users only purchase services whose price is lower than their value, then network revenue must be greater or equal than the GNP. In effect, this is a classic non-zero sum two players game. In fact, in presence of competitions for network resources and multiple users we have a multi-player game scenario. COMPETITIVE ANALYSIS FRAMEWORK. ----------------------------------- The big question is how to guarantee that in spite of seeing requests online the system is maximizing its profits. A number of results in the theoretical computer science literature, most notably, [AAP-93] address this question by showing that the mechanism of ``opportunity cost'' can be used for the online profit maximization problem. The essence of this mechanism is that opportunity cost assigned to a unit of resource is increasing exponentially with past utilization of this resource. This leads to ``competitive'' online algorithms, whose revenue is comparable to that of an optimal prescient strategy on each input. The issue of multi-player games and competition is addressed in [AA-96]. EXTRAPOLATION OF PAST INTO THE FUTURE ------------------------------------ It appears to be complex to deal with aggregation of services. For example, say that many users would like to watch the same movie. Assigning certain amount of bandwidth to popular movie becomes very profitable if the movie is popular. This, however, may be determined by future access pattern, which is currently not known. The only think that is know is PAST access pattern. Can we infer future from the past, WITHOUT knowing the correlation between the future and the past ? Quite surprisingly, the answer (in this context) is: YES, we can. The first step in this direction (in the context of full-connectivity network) was made in [AAFL]. This was further extended in [AS] to networks with arbitrary topology. This should enable us to design solutions for bandwidth management (routing and admission control) for pay-per-view movies-on-demand environment. CONCLUSIONS ----------------- The above is simply an example of a particular approach, Many other approaches are possible. Whichever ones ends being used, it appears that electronic payment mechanisms are essential for such methods to be implemented. With such mechanisms in place, we expect to see Internet as ``meta-computer'' on which computing, storage and communications resource will be freely traded on this new ``electronic market-place''. This will finally accomplish the goals of information revolution: defeating the tyranny of geography. BIBLIOGRAPHY ------------------------ [AAP-93] B. Awerbuch, Y. Azar and S. Plotkin ``Online Admission Control for Virtual Circuits'', IEEE FOCS 93. [AA-96] B. Awerbuch, and Y. Azar ``Blind Bidding and Competitive Online Pricing'', unpublished manuscript, 1996. [AAFL] B.Awerbuch, Y.Azar, A.Fiat and T.Leighton, ``Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time'' 28'th ACM Symposium on Theory of Computing, May 1996, Philadelphia, PA [AS] B.Awerbuch, T. Singh, ``Online cable wiring'', unpublished manuscript.