Can Multipath Mitigate Power Law Delays? — Effects of Parallelism on Tail Performance

摘要

Parallelism has often been used to improve the reliability and efficiency of a variety of different engineering systems. In this paper, we quantify the efficiency of parallelism in systems that are prone to failures and exhibit power law processing durations. We focus on the context of transmitting a data unit in communication networks, where parallelism can be achieved by multipath transmission (e.g., multipath routing). We investigate two types of transmission schemes: redundant and split transmission techniques. We find that the power-law transmission delay phenomenon still persists with multipath transmission. In particular, we show that when the transmission delays of each path are characterized by the same power law, redundant multipath transmission can only result in a constant factor performance gain, while order gains are possible when the delays are light tailed. We further compare the performance of redundant transmission and split transmission, and show that there is no clear winner. Depending on the packet size distribution properties and the manner in which splitting is performed, one scheme results in greater performance over the other. Specifically, split transmission is effective in mitigating power law delays if the absolute value of the logarithm of the packet size probability tail is regularly varying with positive index, and becomes ineffective if the above quantity is slowly varying. Based on our analysis, we develop an optimal split transmission strategy, and show that this strategy always outperforms redundant transmission.