TABLE OF CONTENTS The capacity-delay tradeoff in Proposition 2.5 is better than those reported in [3] and [4]. Assuming that the delay bound is ?( n d), 0 ? d < 1, the achievable per-node capacity is O( n - (1- d )) by the scheme in [3], and O( n -(1- d )/2) by the scheme in [4]. Our upper bound, however, implies a per-node capacity of O( n - (1- d )/3) (we have ignored all log n factors). Since d < 1, there is clearly room to substantially improve existing schemes (see Fig. 2.1).
In this section, we will show how the study of the upper bound also helps us to develop a new scheme that can achieve a capacity-delay tradeoff that is close to the upper bound. Precisely, we met several inequalities (2.10) (2.18) during the derivation of the upper bound. By studying the conditions under which these inequalities are tight, we will be able to identify the optimal choices of various key parameters of the scheduling policy. In the end, the knowledge of the optimal choices of the parameters will help us develop a new scheme that is superior to existing ones.
Assume that the mean delay is bounded by n d, d < 1. By Proposition 2.5, we have,
In order to achieve the maximum capacity on...
