Question

Consider a CSMA-like protocol with n nodes. Assume that the length of a time step equals twice the maximum propagation delay between any two nodes. Recall that if the medium is sensed busy, the node continuously monitors the medium until it becomes idle. When the medium becomes idle, the node sends the frame with probability p and defers it for a later slot with probability 1 − p. Assume that each node has an infinite number of frames to send, and that all frames are of the same size. Also, assume that each frame takes exactly one time step to be completely transmitted. Assume that when the medium experiences a collision during a current time step, it must stay idle during the next time step before it can proceed with transmission attempts again. But when the medium experiences a successful transmission during a current time step, nodes can immediately proceed with transmission attempts without needing to go idle for one time step. Also, assume that when a collision occurs during a time step, each node is able to detect it by the end of the time step during which the collision has occurred. Since the current state of the system depends only on its immediate past state, we can use Markov chains to model and analyze the performance of this system. For this, consider that the system has 3 states: idle i, colliding c, and transmitting t. All answers must be expressed in terms of p and n.

1. Draw the Markov state transition diagram and show the state transition probabilities?

2.Write the balance equation for each state, and derive the stationary probabilities for all states?

3.Derive the system throughput, defined as the average number of successfully delivered frames per time step?

4.Derive the system utilization, defined as the fraction of time the medium is being used for successful transmissions?

5.Drive the average waiting time, defined as the average time from when a frame is ready to be transmitted until the time the frame is transmitted successfully?

Answer 1

The carrier sense multiple access protocol
with collision detections (CSMA/CD) often suffers
from performance issues when it comes to
transmission collisions within a network. This paper
proposes a solution to the packet starvation effect
[3], which is similar to Ethernet capture [2] of
CSMA/CD by combining findings from previously
performed research to improve CSMA/CD. The
proposed solution, carrier sense multiple access with
collision detection and network queue
(CSMA/CDNQ) modifies the current CSMA/CD
protocol by using a network queue to avoid multiple
collisions while allowing behavior to resort back to
IEEE standard 802.3 (CSMA/CD) in the event of
queue failure, thus classifying it as a sometimes
centralized, sometimes decentralized multiple access
protocol. The Binary Exponential Backoff algorithm
is slightly modified in CSMA/CDNQ to allow the
queue dominance over the network and each node on
the channel will utilize a lock, which is also referred
to as the send variable, that controls when the node

The carrier sense multiple access protocol
with collision detections (CSMA/CD) often suffers
from performance issues when it comes to
transmission collisions within a network. This paper
proposes a solution to the packet starvation effect
[3], which is similar to Ethernet capture [2] of
CSMA/CD by combining findings from previously
performed research to improve CSMA/CD. The
proposed solution, carrier sense multiple access with
collision detection and network queue
(CSMA/CDNQ) modifies the current CSMA/CD
protocol by using a network queue to avoid multiple
collisions while allowing behavior to resort back to
IEEE standard 802.3 (CSMA/CD) in the event of
queue failure, thus classifying it as a sometimes
centralized, sometimes decentralized multiple access
protocol. The Binary Exponential Backoff algorithm
is slightly modified in CSMA/CDNQ to allow the
queue dominance over the network and each node on
the channel will utilize a lock, which is also referred
to as the send variable, that controls when the node

CSMA/CD is least efficient when the
network is busy, due to collisions wasting bandwidth
and Ethernet capture allowing one host to dominate
the channel. Many proposed modifications to
CSMA/CD would work well in a busy network, but
decrease CSMA/CDs efficiency in low to medium
traffic networks [6]. Thus the difficulty in resolving
the issues with CSMA/CD is finding the right
balance to optimally utilize the available resources in
high network occupancy while not impairing
performance during low occupancy. My solution
includes introducing a network-wide queue to and
altering the behavior of the existing CSMA/CD
protocol

The queue is originally empty, and will
receive input only after a packet collision has
occurred. The queue acts similarly to nodes on the
network, but with precedence and authority over the
other transmitters. In current CSMA/CD, when a
node is ready to transmit a frame, it listens to the
network and if it detects the channel is empty it
begins transmitting. I propose setting a flag, or ‘send
variable,’ in each host with the default value equal to
true. When the value is true, the host can send as
soon as it senses an empty channel. The only
incident that changes the value to false is when the
queue sends out a signal similar to a jam signal. The
signal notifies all the hosts in the network that the
queue is preparing to transmit. The only time the
queue will transmit a packet is subsequent to a
collision. Once the queue finishes all its
transmissions, it sends another signal that resets the
send variable back to the default value and hosts may
once again transmit as in regular CSMA/CD.

CSMA/CDNQ can be considered a hybrid
multiple access protocol, since it has features of two
of the three multiple access protocol categories,
including random access and taking turns protocols
[5]. Most of CSMA/CDNQ’s behavior would lean
towards its classification as a random access
protocol, considering that CSMA already belongs to
this group and that the nodes are free to transmit
close to whenever they choose. Also, when an
adapter transmits a frame it uses the full bandwidth
available since it is not divided amongst the nodes
into different frequencies. For example, if the nodes
are connected through a 100 Mbps channel, each
transmission of every node will broadcast at a rate of
100 Mbps. CSMA/CDNQ has characteristics
belonging to the taking-turns protocol group during
the time when the network queue has control. This is
because only one adapter is able to transmit at a time,
even if other nodes have frames ready to transmit.