Combinatorics and Algorithms for Video-on-Demand
The project involves constructing and evaluating mathematical algorithms for scheduling media content (TV shows, sports games, movies) in video-on-demand systems, typically on virtual machines in the cloud. Although the problem is stated as a real-world problem, it is, at heart, a mathematical onean understanding of the real-world issues is easy enough to acquire if the student already is keen on and knowledgeable in mathematics. This is a project for a student who loves mathematics and is curious about how theoretical mathematics can actually create an impact in the real world.
The specific project is to use combinatorics to construct new algorithms to allocate programmes to servers in the video-on-demand environment. Video-on-demand is an important new way of serving content to users, and provides programmes only when users request them. It thus offers users flexibility and freedom, but the downside is that it is more difficult for providers to anticipate and serve demand while keeping costs down. For example, we could satisfy all users by giving each user a server dedicated to her or him alone, but the cost would be prohibitive. The key to solving this is an efficient assignment of programmes to servers, but such an assignment is challenging in an environment where demand is constantly in flux as users come and go, and where users get impatient if their content is not served immediately. From a technical perspective, this is a bi-criteria optimization problem: we need to minimize cost to providers, but also minimize delay of users.
This kind of scheduling is an old problem in mathematical optimization, and many techniques are already known for circumstances such as scheduling jobs on machines in a factory. Thus there are good starting points for approaching the problem. However, the video-on-demand situation creates new challenges with regard to speed, cost, availability,
