Server placement in multiple-description-based media streaming

Multiple description coding (MDC) is a powerful source coding technique that involves encoding a media stream into r independently decodeable substreams. With every successful reception of a substream, decoded signal quality improves. We consider the problem of placing a set of servers in the network such that a desired quality of service can be provided to a community of clients. We formulate the server placement (SP) problem, whose goal is to identify the minimum number of server locations that can provide r descriptions to a set of clients such that the delay associated with each path from a chosen server location to a given client is bounded by a given delay constraint and the total "unreliability" associated with the group of paths to a given client is also upper bounded. We show that the SP problem is NP-complete. We propose a mixed-integer linear programming (MILP) formulation and heuristic solution for the SP problem. Simulations are conducted to evaluate the performance of the proposed algorithm and to compare it with the MILP solution.