Statistical delay budget partitioning in wireless mesh networks

Wireless Mesh Networks (WMN) have great potential to support high quality multimedia delivery. However, multimedia applications require Quality of Service (QoS) guarantees for end-to-end (E2E) transmission. An important element in providing such guarantees is mapping E2E transmission requirements to link QoS requirements. While different algorithms have been proposed for mapping in connection oriented wired networks, it is yet to be addressed in multihop wireless networks. Even algorithms proposed for QoS partitioning in wired networks are either near optimal or heuristic, and only yield solutions for a single E2E QoS requirement. In this paper, we propose a partitioning algorithm capable of partitioning multiple E2E QoS requirements simultaneously. We define QoS as the pair of required E2E delay and the probability to violate this delay requirement, i.e. violation probability. Our approach is motivated by experiments concluding that the delay probability distribution is accurately characterized by a gamma distribution. This conclusion is used to formulate a mathematical linear program that optimally partitions the E2E delay and the logarithm of the E2E violation probability into link delays and the logarithm of the link violation probabilities. Extensive simulation verify the effectiveness of the algorithm compared to two QoS partitioning algorithms. The proposed algorithm outperforms the other algorithms for loose and stringent QoS requirements and over different path lengths.