Optimal control for queue length fairness in dual bus networks

Abstract

Advances in optical fibre transmission have created interest in a class of multiple access local and metropolitan area networks called unidirectional bus networks. In the absence of medium access control, the nodes closer to the beginning of the bus (upstream nodes) have priority in accessing the bus compared to those away from the beginning of the bus (downstream nodes). All MAC protocols for unidirectional bus networks aim at controlling this natural priority by regulating access to the bus. For the study of queue length fairness through dynamic access control, a dual bus network with three nodes is considered and access of one of the buses by two contending nodes is studied. Access of the bus by two nodes is modelled as a two-queue single-server system and the service problem is formulated as a total expected discounted cost minimisation problem. The optimal stationary policy in the case of slotwise independent Bernoulli arrival processes at the nodes (or queues) is obtained with sum of the squares of the queue lengths as one-step cost using Markov Decision Theory. The structural properties of optimal value function are derived. It is shown that an optimal access policy serves the longer queue when queue lengths are unequal, serves the queue with higher arrival rate when queue lengths are equal and non-zero, and serves one of the two queues when queue lengths are equal, non-zero and arrival rates are equal. In the case of unequal arrival rates, the uniqueness of the optimal policy is also shown. In a four-node network with three contending active nodes, it is shown that in the case of slotwise independent Bernoulli arrivals with equal arrival rates, ‘serve one of the longest queues’ policy is optimal. It minimises total expected discounted cost over an infinite horizon. The one-step cost here also is the sum of the squares of the queue lengths. Queue length fairness is studied in the case of half-slot propagation delay between nodes and slotwise independent arrivals with arbitrary number of arrivals per slot. With upstream queue denoted by queue 1 and downstream queue by queue 2, let X1(k)=N1(k)X_1(k) = N_1(k)X1?(k)=N1?(k), X2(k)=(N2(k?1/2)?U3(k?1))+X_2(k) = (N_2(k - 1/2) - U_3(k - 1))^+X2?(k)=(N2?(k?1/2)?U3?(k?1))+; where Ni(k)N_i(k)Ni?(k), Ui(k)U_i(k)Ui?(k) are the queue lengths at time kkk at queue iii, arrival rate at queue iii, and control at queue iii at time kkk respectively. X1(k)+?1X_1(k) + \lambda_1X1?(k)+?1? and X2(k)+2?2X_2(k) + 2\lambda_2X2?(k)+2?2? are named as conditional expected anticipated queue lengths of the respective queues. It is shown using ‘sample-path dominance’ technique that ‘serve the queue with longer conditional expected anticipated length when (X1(k),X2(k))?(0,0)(X_1(k), X_2(k)) \neq (0,0)(X1?(k),X2?(k))?=(0,0), and allot the slot to queue 2 when (X1(k),X2(k))=(0,0)(X_1(k), X_2(k)) = (0,0)(X1?(k),X2?(k))=(0,0)’ policy is the unique optimal stationary policy that minimises total expected discounted cost over an infinite horizon. Here one-step cost is E[N1(k)+N2(k)?X1(k),X2(k)]E[N_1(k) + N_2(k) | X_1(k), X_2(k)]E[N1?(k)+N2?(k)?X1?(k),X2?(k)]. The analysis is valid under the restriction 1+?1>2?21 + \lambda_1 > 2\lambda_21+?1?>2?2? and ?1?2?2\lambda_1 \leq 2\lambda_2?1??2?2?. A routing problem is considered with deterministic arrival process, a router, and two output queues with their own servers whose service times are geometrically distributed. With randomisation at only the (0,0)(0,0)(0,0) state, it is shown that ‘join the shorter queue in case of unequal queue lengths, the queue with higher service rate in the case of equal queue lengths, and either queue in the case of equal service rate and equal queue length’ policy minimises the total expected discounted cost over any finite horizon. Here one-step cost is the sum of the squares of queue lengths.