CONSTANT-TIME PER EDGE IS OPTIMAL ON ROOTED TREE NETWORKS

We analyze the relationship between the expected packet delay in roote d tree networks and the distribution of time needed for a packet to cr oss an edge using convexity-based stochastic comparison methods. For t his class of networks, we extend a previously known result that the ex pected delay when the crossing time is exponentially distributed yield s an upper bound for the expected delay when the crossing time is cons tant [20] using a different approach. An important aspect of our resul t is that unlike most other previous work, we do not assume Poisson ar rivals. Our result also extends to a variety of service distributions, and it can be used to bound the expected value of all convex, increas ing functions of the packet delays. An interesting corollary of our wo rk is that in rooted tree networks, if the expectation of the crossing time is fixed, the distribution of the crossing time that minimizes b oth the expected delay and the expected maximum delay is constant. Our result also holds in multicasting rooted tree networks, where a singl e message can have several possible destinations. Besides offering a u seful analysis on this restricted class of networks, we also provide a small improvement to the bounding technique. Surprisingly, this impro vement is also applicable to previously developed comparison methods, leading to an improvement in the upper bounds for greedy routing on bu tterfly and hypercube networks given by Stamoulis and Tsitsiklis [20].