일시 : 2014년 07월 31일 (목) 14:00 ~ 15:00

장소 : 제2공학관 B701

제목 : Randomized Load Balancing in Large Bandwidth Sharing Systems

초록 : Processor sharing models occur in a wide variety of situations for example in models of internet bottlenecks. They are good models for bandwidth sharing as well as being solutions to NUM for logarithmic utilities. In addition they possess the desirable stochastic property of the stationary distribution being insensitive to the service time distribution. In this talk I will discuss new advances in understanding and characterizing the behavior of randomized routing to PS servers that are heterogeneous in terms of their server speeds. We will rst discuss the so-called Power-of-two rule in the homogeneous case of identical servers where routing to the least occupied server amongst two randomly chosen servers results in a very low server occupancy and a so-called propagation of chaos or asymptotic independence. There were no known characterizations about the heterogeneous case. In the heterogeneous case we will see that the stability region for randomized routing is strictly included in the maximal stability region that can be achieved by state independent routing. Therefore the average sojourn of tasks can be longer in randomized routing in heterogeneous systems. When the system is stable we completely characterize the steady-state behavior of the server occupancies and show that it exhibits super-exponential decay and asymptotic independence among servers. To overcome the reduction in the stability region we show that a combination of state independent routing (biased sampling) to a server class combined with JSQ within the class recovers the stability region as well as the benets of small server occupancies. The techniques are based on a mean eld analysis and an ansatz based on propagation of chaos that then establishes the asymptotic independence between servers.

Joint work with Arpan Mukhopadhyay (Waterloo)

강연자 : Ravi Mazumdar, Professor / ECE, University of Waterloo, Canada

초청자 : 전기전자공학과 교수 이장원