Gupta and Kumar (2000) introduced a random network model to study how throughput scales in a fixed wireless network when nodes are fixed, and showed that when n distinct source-destination pairs are chosen at random the throughput per source-destination pair is Θ(1/ (n log n)~(1/2)). Grossglauser and Tse (2001) showed that in the presence of mobility throughput per source-destination pair increases all the way to Θ(1). In this paper, we study the throughput region of fixed random networks, that is the set of all possible achievable rate-tuple λ = (λ_(ij))_(1 ≤ i,j ≤ n), where λ_(ij) is the rate at which node i sends data to node j. We show that λ is achievable as long as net rate at which data sent from any node and net rate at which data is received at any node is O(1/ (n log n)~(1/2)), that is ∑_k λ_(ik) and ∑_k λ_(ki) are O(1/ (n log n)~(1/2)) for all i. To demonstrate achievability, we present a scheme based on idea of Valiant and Brenber (1982) for oblivious routing in grid-networks. The maximal throughput achieving scheme of Grossglauser and Tse (2001) utilizes a similar idea. Thus, in addition to characterizing the throughput region, this work also provides a conceptual unification of the throughput maximal schemes for fixed and mobile networks. Another important performance metric is delay. For fixed random networks, El Gamal, Mammen, Prabhakar and Shah (2004) obtained the optimal delay scaling of Θ((n/log n)~(1/2)) at the throughput of Θ (1/ (n log n)~(1/2)) when packet size is allowed to scale down. We show that this delay scaling is achievable even when the packets are of fixed size. This requires a non-trivial scheduling scheme in addition to a routing scheme. We obtain such a scheduling scheme by simulating a last come first serve (LCFS) continuous network. We use results of Kelly (1979) regarding the product form of queue-size distribution in a network of symmetric queues to analyze the delay of our scheme.
展开▼
