Basic Data Communications Series
2.0 Protocol Performance Introduction
We now move on to looking at some of the more common protocols and look at the performance in terms of queuing delay and queue length.
Consider first the conflict free protocols. That is protocols in which the channel is orderly allocated to a node in turn.
2.1 Conflict Free Protocols
2.1.1 Frequency Division Multiple Access
FDMA divides the available frequency band into a number of discrete sub-frequencies, each one allocated to a user. The advantages of FDMA are simplicity, however when a user is idle a portion of the available bandwidth is lost.
In the following analysis assume that the whole channel can sustain a rate of:
R bits/sec
Which equally divided between M users:
R/M bits/sec for each.
Assume also that users are independent and can therefore be viewed as M independent queues.
The total throughput is just M times the individual throughputs and the average packet delay can be obtained by applying Little’s result to the individual queue.
Consider a typical user that generates packets according to a Poisson distribution with rate l packets sec. The time required for the transmission of a packet is T. The expected delay of a packet is:
If all packets are of equal length P bits then the transmission time of every packet is equal to T = MP/R. The queuing model therefore corresponds to an M/D/1 queue and:
Where r is equal to the individuals throughput (traffic intensity). Normalizing the expected delay by P/R, the time required to transmit a packet with rate R is:
From Littles result the average queue length is:
2.1.2 Time Division Multiple Access
TDMA divides the channel access into a number of time slots repeated cyclically as a frame. Each time slot is uniquely allocated to a user.
To analyze a the performance of TDMA scheme consider a system consisting of M users each transmitting equally long packets of P bits long. If the total rate of transmission is:
R bits/sec
Then the packet transmission time is:
T=P/R which is taken to be the slot size.
The duration of the entire cycle therefore
TC = MT
Assume also that the packet arrival process is independent to different users.
Consider a typical packet generate by a user, the delay suffered has three components
The time between its generation and the end of the current frame
The queuing time to allow all the packets already queued to be transmitted
The packet transmission time itself.
The expected queuing time of a packet is given by:
Where r = lTC= lMP/R
The total expected delay time is therefore:
From Littles result the average queue length is:
2.1.3 Token Passing Ring
A token ring network consists of a point-to-point ring of nodes in which a token message is passed from each node to its neighbor. A sending node stops the token circulation and transmits its data then passes the token as before.
The time required to repeat the frame at a station i.e. the delay through the station is known as the station latency. The Ring Latency is as follows:
Where t is the channel propagation delay, N the number of stations, SLat is the station latency in bits.
The transfer time has been analyzed by BUX and is given by:
Application of Little’s Result gives the average queue occupancy as follows:
LF is the frame length in bits, C is the channel capacity in bits/s, t is the propagation time of the ring, n is the number of stations.
2.2 Contention Protocols
2.2.1 Pure Aloha
The oldest contention multiple access protocol is aloha in which nodes are allowed to transmit at will and detect collisions on the channel by concurrently receiving the transmitted message. When collisions occur they are randomly rescheduled to be re-transmitted at some time in the future. The advantage of aloha is its simplicity however its performance is poor due to the number of collisions and retransmissions that are necessary.
Consider a packet to be transmitted at some time t. The packet will be successful if no other packet is scheduled for transmission in the period (t - T, t + T).
The probability of success PSUC is the probability that no packet is scheduled in the interval 2T which is known as the vulnerable period. The scheduling corresponds to a poisson process, hence:
Psuc = exp(-2gT) at a scheduled rate of g packets per second of which only a fraction are successful.
When a packet is successful the channel carries useful information for a period T secs. Hence the throughput S:
The normalised offered load G = gt, Hence the throughput S:
2.2.2 Slotted Aloha
Slotted aloha is pure Aloha with slot times imposed; a user is constrained to transmit only at the beginning of a slot.
The throughput S is:
2.2.3 One persistent CSMA
Carrier Sense protocols are a large class of Multiple Access schemes in which nodes are allowed to transmit at will but only if the channel is sensed and found idle. Collisions will still occur but not to the same extent as pure aloha.
With NP-CSMA there are times when the channel is idle due to the static re-scheduling of the re-transmission. In 1P-CSMA the node on sensing the channel busy persists in sensing the channel and transmits as soon as the channel becomes free.
1P-CSMA has been analysed by Sohraby.
The normalised throughput S:
note the parameter ‘a’ is related to the time required to sense a channel free and the transmission time of a message and has a value ranging from 0 – 1.
2.2.4 Collision Detect CSMA
In CSMA/CD the overhead caused by collisions is reduced by terminating an unsuccessful transmission (due to collision) as soon as possible. This is done by detecting the collision as soon as it happens and then randomly re-scheduling the transmission to a later time. Another feature is that of consensus reinforcement: after a collision all nodes generate a jam signal for a period tcr in order to ensure that all network nodes confirm that a collision has taken place. This protocol is thus an example of a dynamic resolution contention protocol.
LAMS Equation for throughput delay of CSMA/CD has been modified as a function of C, r, and n, as follows:
Application of Little’s Result gives the average queue occupancy as follows:
LF is the frame length in bits, C is the channel capacity in bits/s, t is the propagation time of the channel, n is the number of stations