We analyze the relationship between the expected packet delay in rooted tree networks and the distribution of time needed for a packet to cross an edge using convexity-based stochastic comparison methods. For this class of networks, we extend a previously known result that the expected delay when the crossing time is exponentially distributed yields an upper bound for the expected delay when the crossing time is constant using a different approach. An important aspect of our result is that unlike most other previous work, we do not assume Poisson arrivals. Our result also extends to a variety of service distributions, and it can be used to bound the expected value of all convex, increasing functions of the packet delays. An interesting corollary of our work is that in rooted tree networks, if the expectation of the crossing time is fixed, the distribution of the crossing time that minimizes both the expected delay and the expected maximum delay is constant. Our result also holds in multi-casting rooted tree networks, where a single message can have several possible destinations.
Besides offering a useful analysis on this restricted class of networks, we also provide a small improvement to the bounding technique. Surprisingly, this improvement is also applicable to previously developed comparison methods, leading to an improvement in the upper bounds for greedy routing on butterfly and hypercube networks given by Stamoulis and Tsitsiklis.
Originally appeared in the Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 162-169, 1996. Journal version: Distributed Computing, vol. 10:4, pp. 189-197, 1997. All rights reserved by them, only for use in accordance with DC, etc.