Search

We study a synchronous process called dispersion. Initially M particles are placed at a distinguished origin vertex of a graph G. At each time step, at each vertex v occupied by more than one particle at the beginning of this step, each of these particles moves to a neighbor of v chosen independently and uniformly at random. The process ends at the first step when no vertex is occupied by more than one particle. For the complete graph Kn, for any constant δ > 1, with high probability, if M ≤ n/2(1 − δ), the dispersion process finishes in O(logn) steps, whereas if M ≥ n/2(1 + δ), the process needs eΩ(n) steps to complete, if ever. A lazy variant of the process exhibits analogous behavior but at a higher threshold, thus allowing faster dispersion of more particles. For paths, trees, grids, hypercubes, and Abelian Cayley graphs of large enough size, we give bounds on the time to finish and the maximum distance traveled from the origin as a function of M. [ABSTRACT FROM AUTHOR]

Numerous studies have shown that packet reordering is common, especially in networks where there is high degree of parallelism and different link speeds. Reordering of packets decrease the TCP performance of a network, mainly because it leads to overestimation of the congestion in the network. In this paper, we analyse the performance of networks when reordering of packets occur. We propose a proactive solution that could significantly improve the performance of the network when reordering of packets occurs. We report results of our simulation experiments, which support this claim. Our solution is based on enabling the senders to distinguish between dropped packets and reordered packets. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]