On Minimum-Delay Data Block Transport over Two-Connected Mesh Networks

In this paper we investigate the problem of sending data blocks containing finite number of packets over two independent routing paths in mesh networks. The objective is to minimize the average block delay by allocating packets into the two routing paths optimally. Previous researchers have shown that using more paths can reduce packet delay and the rate-based allocation policy is optimal, based on the delay metric solely depending on delay mean of each path. In our research, generalizing the multi-path routing scheme to accommodate data block transport, we first establish an upper bound for the average block delay, depending on both delay mean and variance of each path, and then solve a non-linear optimization problem to obtain the optimal packet allocation policy, which either allocates all the packets to the faster path for blocks of small size or allocate all the packets to both paths in proportion to their service rates for blocks of large size. Contrary to conventional results, our analysis suggests that using additional slower routing path could increase the average block delay in some cases. We further characterize the whole spectrum of optimal packet allocation policies as a function of block sizes, and conclude that the existing rate-based allocation policy is a special case for large data block.