In the wireless world, we have limited transmission medium resources and bandwidth as compared to wired networks. Multi-hop mesh topologies can quickly use up channels and available bandwidth. This has led to various studies and technological developments into the efficient use of wireless resources.
Scheduling is an active line of study to enhance wireless resource use. Popular scheduling schemes focus on using various transmission rates to achieve the best balance between achievable performance and coverage, hopping between different channels to avoid interference or channel overloading, and regulating multiple flows to pass through a channel without suffering from performance degradation.
We, at the University of Auckland, investigated the transmission opportunity additionally achieved by scheduling flows when a wireless mesh network (WMN) is regarded as ‘saturated’ by traditional schemes.
Where is the opportunity?
We were motivated to undertake this investigation by the communication scenarios from a previous study (Figure 1).
Figure 1 — An example to illustrate the potential of flow scheduling in gaining extra transmission opportunity.
When s receives three flows, as shown in Figure 1 (a), if the aggregated input rate is larger than the capacity of the link between s and r (that is, θ>φ), s is not able to admit all three flows.
However, as shown in Figure 1 (b), if s sends the three flows via different time slots (that is, the zigzag curves in the figure) and buffers flows waiting for their time slots, the potential exists for s to admit all three flows with guaranteed performance (as the zigzag curves can overtake the input curves more quickly).
How to generalize a scheduling policy?
Our study was developed by using Network Calculus. We analysed the following two major issues in order to form the flow scheduling policy:
- The admission condition for a wireless mesh node to accept a new flow without sacrificing the performance of existing flow transmission.
- The time slots assigned for different flows in order to guarantee the end-to-end performance of each flow.
When developing the admission condition, we focused on enabling all data from the admitted flows to reach the receiver within accepted delays (that is, throughput and delay performance).
Although we do not discuss this complex analysis here, our admission condition concludes that the average transmission rate of an admissible flow is proportional to the output link bandwidth and the end-to-end delay bound but inversely proportional to the number of serving flows, and their packet sizes and average transmission rates.
For the scheduling plan of a wireless mesh node processing F flows, our analysis focused on the time slots that should be assigned to each of these F flows. We concluded that the time slot assigned for a flow should be proportional to the schedule period (that is, the sum of time slot lengths for F flows in one period) and the amount of input data of this flow within the schedule period. However, the time slot is inversely proportional to the output link’s capacity and the end-to-end delay bound.
Overall, our scheduling policy makes use of the performance gap, the difference between the acceptable performance bounds and the performance achievable when a wireless link is saturated, to enhance the ability of a wireless mesh path to transmit more performance-guaranteed traffic.
As compared to the time scheduling at the underlying layer (say TDMA), this scheduling policy is an upper layer scheme that takes end-to-end performance via multiple wireless hops and flow properties into account while allowing multiple flows to share a wireless link.
Wanqing Tu is a Senior Lecturer in the Department of Computer Science at the University of Auckland.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.