Performance of multiaccess dual slotted unidirectional bus networks

Abstract

Advances in optical fibre transmission system technology 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 (MAC), 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 accorded to the nodes at the beginning of the bus by regulating access to the bus. The performance of MAC protocols, and the performance of dual bus networks when stations with infinite backlog are connected to the network through low-speed bidirectional channels, are studied in this thesis. A distributed queueing MAC protocol is used in Distributed Queue Dual Bus (DQDB) networks. A modified distributed queueing MAC protocol for large dual bus networks is proposed and its performance is studied. Access of one bus, called the data bus, is considered. The other bus is called the request bus. The access delay of a packet at a node consists of two components: (i) request bus access delay, and (ii) data bus access delay. A few properties of the protocol that are independent of the traffic offered to the network are studied. Some of these properties are used to prove upper bounds on the data bus access delay. To achieve throughput fairness under heavy load, a rate control similar to the DQDB bandwidth balancing mechanism that retains the traffic-independent properties of the MAC protocol is described, along with the implementation procedure. Thus, at heavy load, equal throughputs result with bounded data bus access delay. Delay performance of the protocol is studied for Poisson offered traffic. The request bus access is modelled exactly as a slotted M/D/1 non-preemptive priority queueing system. Some results on slotted M/D/1 queues are derived and then used to study the performance of request bus access. Expected values of data bus access delay are obtained through simulation. The expected data bus access delay decreases, and the expected request bus access delay increases in the upstream direction. In a three-node dual bus network, the access delay profile of the two nodes accessing a single bus with Bernoulli arrival processes is studied. When control is absent, the expected delay of a packet at the downstream node is greater than that of a packet at the upstream node. For Bernoulli access control at the upstream node with parameter p, the steady-state departure process from that node is Bernoulli and is insensitive to the control parameter p. As a result, the queue lengths at the two nodes at any particular time in steady state are statistically independent, and the expected delay of a packet at the downstream node is insensitive to the value of parameter p. This delay is the same as that in the case without access control. Therefore, two control schemes are considered in which access control at the upstream node is Markovian with two parameters. In the first scheme, access at the upstream node is restricted to only one state of an independent two-state Markov chain. In the other scheme, access probability at the upstream node in any slot is chosen based on the transmission status of the node in the previous slot. In both schemes, the departure process from the upstream node is a function of the control parameters. In the first scheme, an upper bound on the expected delay at the downstream node is found analytically, and in both schemes the expected delays are found through simulation. It is found that there are ranges of values of the control parameters and packet arrival rates for which the expected delays at both nodes are less than the expected delay obtained at the downstream node without any access control. A method is devised to solve for the state probabilities of a certain class of multi-dimensional, irreducible, and positive recurrent Markov chains. The method uses a state variable approach. When the upstream node has an infinite number of buffers and the downstream node has a finite number of buffers, this method can be used to solve the three-dimensional Markov chain arising from a generalised version of the first of the Markovian access schemes. A discrete-time queueing system in which the arrival process is Bernoulli with rate ? and the service rate is ?, when the number of customers in the system is s, s ? 1, was considered in a paper by Hsu and Burke. The dynamics of the queue were modelled using a three-dimensional Markov chain and Burke’s theorem was proved. In this thesis, a detailed version of the proof is presented. When ?? = ? for all s ? 1, the queue becomes a Geometric/Geometric queue. In that case, the waiting time distribution is obtained. These results are used in the study of the access delay performance of the Bernoulli access scheme mentioned earlier. For the study of queue length fairness through dynamic access control, a dual bus network with three nodes is considered again and access of one of the buses by the two contending nodes is studied. Access of the bus by the two nodes is modelled as a two-queue single-server system, and the server problem is formulated as a total expected discounted cost minimisation problem. The optimal stationary policy in the case of independent arrival processes with arbitrary number of arrivals in a slot and with different arrival rates is obtained with the sum of the squares of the queue lengths as the one-step cost. The optimal policy is work-conserving, and it serves the longer queue when the queue lengths are unequal and serves the queue with larger arrival rate when the queue lengths are equal. In the case of 0–1 arrival processes, some sample path-wise results are obtained. Stations may be attached to nodes on a high-speed dual bus network through lower-speed local networks or input/output channels. The capacity limitation of the low-speed bidirectional channel that is to be shared for transmission and reception of packets between a station and its node can affect performance. Reception is assumed to be given higher priority than transmission. Each station is assumed to have a very large backlog of packets once it becomes active. The performance measures considered are the steady-state station throughputs, transmit buffer queue length at node, and the burst length. In a slotted dual bus network with two stations communicating with each other, in the absence of any control of packet transmission, the steady-state performance depends on the relative activity initiation times and the propagation delay between the nodes. A point of probabilistic control is introduced at the station, at the node, between the station and the node, or both between the station and the node and at the node. The performance is studied through analysis or simulation, for the case of equal channel and bus capacities. The schemes that have points of control at the station, between the station and the node, or both between the station and the node and at the node each result in the same steady-state performance for the two stations independent of the activity initiation times. The scheme that has points of control both between the station and the node and at the node yields the extra flexibility of controlling both throughput and burst length. In the scheme that has point of control between the station and the node, the burst length distribution converges to geometric when the size of the network is very large. But the channel is not fully utilised in these cases. However, the scheme that has point of control at the node results in different performance for the two stations for distinct activity initiation times, but in full channel utilisation. In a network with m, m ? 3, active stations, the steady-state performance depends on the traffic distribution matrix. Traffic distribution is uniform if every station chooses every other station as the packet destination with equal probability, independently for all packets. Conditions for throughput fairness in the case of uniform and general traffic distributions are obtained through analysis. As an example, with uniform traffic distribution, the scheme that has point of control between the station and the node results in equal station-to-station throughputs that depend on the value of the control parameter p, provided that m·x ? 4 or m·x > 4 and p ? 2/(m·x ? 2), where x is the ratio of the channel capacity to the bus capacity. However, the channel is not fully utilised when m·x > 4. With uniform traffic distribution, the scheme that has point of control at the node results in equal throughputs with full channel utilisation independent of the control parameter p?, provided that m·x ? 4 and p? ? max??i?m {2(m ? i)x / [4(m ? 1) ? (2m ? i)(i ? 1)x]}. In a three-node network, the burst length and transmit buffer queue length at the node for uniform traffic distribution are obtained through simulation.