Resource Allocation lies at the heart of network control. In the early days of the Internet the scarcest resource was bandwidth, but as the network has evolved to become an essential utility in the lives of billions, the nature of the resource allocation problem has changed. This book attempts to describe the facets of resource allocation that are most relevant to modern networks. It is targeted at graduate students and researchers who have an introductory background in networking and who desire to internalize core concepts before designing new protocols and applications. We start from the fundamental question: what problem does network resource allocation solve? This leads us, in Chapter 1, to examine what it means to satisfy a set of user applications that have different requirements of the network, and to problems in Social Choice Theory. We find that while capturing these preferences in terms of utility is clean and rigorous, there are significant limitations to this choice. Chapter 2 focuses on sharing divisible resources such as links and spectrum. Both of these resources are somewhat atypical -- a link is most accurately modeled as a queue in our context, but this leads to the analytical intractability of queueing theory, and spectrum allocation methods involve dealing with interference, a poorly understood phenomenon. Chapters 3 and 4 are introductions to two allocation workhorses: auctions and matching. In these chapters we allow the users to game the system (i.e., to be strategic), but don't allow them to collude. In Chapter 5, we relax this restriction and focus on collaboration. Finally, in Chapter 6, we discuss the theoretical yet fundamental issue of stability. Here, our contribution is mostly on making a mathematically abstruse subdiscipline more accessible without losing too much generality.

Autorentext

Abhay Parekh received his Ph.D. in EECS from MIT in 1992. His graduate work was in the area of network resource allocation and papers from his dissertation won the IEEE William Bennett award and the Infocom Best Paper award. After spending time in research at Bell Labs, IBM Thomas J. Watson Research Center, and Sun Microsystems, he cofounded FastForward Networks, which built the first products for application-level multicasting. He has also been on the faculty at the University of California, Berkeley, as an Adjunct Professor of EECS since 2003, where he has worked in areas such as wireless interference management and peer-to-peer networks. In addition to his academic affiliation, Abhay has been a Venture Partner at Accel Partners and the founding CEO of several startup companies. Jean Walrand received his Ph.D. in EECS from UC Berkeley, and has been on the faculty of that department since 1982. He is the author of An Introduction to Queueing Networks (Prentice Hall, 1988) and of Communication Networks: A First Course (2nd ed. McGraw-Hill,1998), and co-author of High-Performance Communication Networks (2nd ed, Morgan Kaufman, 2000) and of Scheduling and Congestion Control for Communication and Processing Networks (Morgan & Claypool, 2010). His research interests include stochastic processes, queuing theory, communication networks, game theory and the economics of the Internet. Prof. Walrand is a Fellow of the Belgian American Education Foundation and of the IEEE, and a recipient of the Lanchester Prize and of the Stephen O. Rice Prize.