####
Constant time per edge is optimal on rooted tree networks

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.