(Consider CSMA/CD) Let A and B be two nodes attempting to transmit on an Etherne
ID: 3780387 • Letter: #
Question
(Consider CSMA/CD) Let A and B be two nodes attempting to transmit on an Ethernet. Each has two frames ready to send; A’s frames will be numbered A1 and A2, and B’s similarly. Let T= 50s be the exponential backoff base unit. Suppose A and B simultaneously attempt to send frame 1, collide, and happen to choose backoff times of 0 and 50s, respectively, so A wins the race and transmits A1 while B waits. At the end of this transmission, B attempts to retransmit B1 while A attempts to transmit A2, and they collide again. Give the probability that A wins this second backoff race based on the CSMA/CD algorithm.
Explanation / Answer
The solution to the above problem goes like this:
At every attempt to transit a frame, both A and B chooses value of ‘k’ randomly. Based on the value of ‘k’, back-off time is calculated as a multiple of ‘k’. The station or node having the smaller back-off time gets to send the frames eariler.
1st attempt:
Value of ‘k’ would be k=0 or k=1 (0 <= k <= 2^n-1; where n=nth attempt).
Since A won the first race, A must have chosen k=0 and B must have chosen k=1 (A wins here with probability 0.25). As A won, A will again choose k=0 or k=1 for its 2nd frame, but B will choose k=0,1,2 or 3 as B failed to send its first frame in the first attempt.
2nd attempt:
Let kA= value of k chosen by A and kB = value of k chosen by B.
We will use notation (kA,kB) to show the possible values. Now the sample space for the 2nd attempt is (kA,kB) = (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2) or (1,3) i.e. 8 possible outcomes.
For A to win, kA should be less than kB (kA < kB). Thus, our event space is (kA, kB) = (0,1),(0,2),(0,3),(1,2),(1,3) i.e. 5 possible outcomes because here only value of A's backoff is less than B's backoff.
Thus the probability that A wins the 2nd back-off race = 5/8 = 0.625.
Note:- Probability = Prob of possible outcomes/prob of total outcomes.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.