Ph.D Thesis

Ph.D StudentBortnikov Edward
SubjectDynamic Service Management in Infrastructure-Based Mobile
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROFESSOR EMERITUS Israel Cidon
PROF. Idit Keidar


The paradigm of delivering real-time applications through clouds of geographically distributed service points is becoming increasingly attractive for mobile operators. Our research explores distributed management of quality of service (QoS) requirements through this infrastructure. The anticipated system scale and the need to adapt to changing behavior of mobile users raise novel problems and call for local and adaptive distributed optimization algorithms behind the cloud framework.

We focus on problems of dynamic assignment of mobile users and groups thereof to application-level service points. In contrast with link-layer associations, which are primarily driven by physical proximity to the infrastructure, application session assignment must jointly consider network distances, congestion, and handoff costs to optimize the QoS in the long run. We combine theoretical approaches with simulation and prototype system implementations.

We first consider a single-user case, namely, the problem of dynamic balancing between the desire to always assign the user to the closest server, and the need to reduce the number of handoffs. We propose an optimal offline solution, and a tightly competitive and efficient online algorithm, DTrack. We also demonstrate motion-aware algorithms, which achieve a near-optimal result using a very limited and noisy movement prediction.

Next, we address the problem of assigning multiple users to servers. This assignment must jointly consider loads and distances, which we call load-distance balancing, or LDB. We analyze multiple flavors of this optimization problem in the centralized setting, and provide efficient polynomial algorithms for them. Following this, we present a scalable distributed solution, Ripple, which can use any sequential algorithm as a local building block. Ripple adapts its overhead to network congestion, and constructs a local assignment whenever possible.

Finally, we propose a comprehensive handoff management framework, QMesh, which addresses all assignment factors in the context of a large-scale wireless mesh network (WMN). We perform a comprehensive simulation study of QMesh based on real location and mobility data, and demonstrate its significant advantage over traditional approaches. We also present a QMesh software prototype implemented within the Win32 kernel, which harnesses multiple desktops as a QoS-aware WMN infrastructure.