Question

Give an intuitive explanation of why the maximum throughput, for small beta, is approximately the same for CSMA slotted Aloha and FCFS splitting with CSMA. Show the optimal expected number of packets transmitted after a state transmission in an Aloha is the same at the beginning of a CRP for FCFS splitting. Note that after a collision, the expected numbers are slightly different in two systems, but the difference is unimportant since collisions are rare.

Answer 1

Carrier Sensing We assume that a node can hear whether other nodes are transmitting after some small propagation and detection delay We allow nodes to initiate transmission after detecting an idle period, no need to wait for slot boundary This strategy is called Carrier Sense Multiple Access (CSMA), even though it doesn’t necessarily imply using a carrier but only some possibility to detect idle periods quickly Information Networks – p.1/42 Carrier Sensing Let β denote the propagation and detection delay measured in expected packet transmission time units, thus with τ this time in second, C the raw channel bit rate in bits/second and L the expected number of bits in a packet β = τCL The performance of CSMA degrades with increasing β, thus with increasing channel rate and with decreasing packet size A simple model for CSMA is to model it as a slotted system where idle slots terminates after β time units, we thus no longer assume equal-duration time slots Information Networks – p.2/42 CSMA, assumptions Slotted system but not with equal-duration time slots We no longer assume data packets of equal length but normalize time so that expected packet transmission is 1 time unit (0, 1, e)-feedback with a maximum delay β For simplicity we assume infinite set of nodes Poisson arrivals with overall intensity λ Information Networks – p.3/42 CSMA Slotted Aloha Major difference to slotted Aloha is that idle slots have duration β Another difference is that newly arriving packets when channel is busy are regarded as backlogged and will transmit with probability qr after each subsequent idle slot; packets arriving during an idle slot will be transmitted in next slot as usual This is called nonpersistent CSMA to distinguish from two slight variations Information Networks – p.4/42 CSMA Slotted Aloha, variants Persistent CSMA: arrivals during busy slot transmit at end of that slot, thus causing collision with relatively high probability P-persistent CSMA: collided packets and newly arrived packets waiting for the end of a busy period use different probabilities for transmission in next slot We will focus on nonpersistent CSMA Information Networks – p.5/42 Nonpersistent CSMA Slotted Aloha W e again use Mar k o v chain with number of backlogged pac kets, n, as state and end of idle slots as state transition times Each busy slot (success or collision) must be follo wed b y an idle slot (since this is nonpersistent CSMA) For simplicity assume all data pac kets ha v e unit length Time between state transitions are either β (idle slot) or 1 + β (busy slot follo wed b y idle slot) Information Networks – p.6/42 Nonpersistent CSMA Slotted Aloha Probability of idle slot is probability of no arrivals in previous idle slot and no retransmissions b y backlogged nodes, thus e −λβ(1 − q r ) n Expected time between state transitions in state n is β + (1 − e −λβ(1 − q r ) n ) Expected number of arrivals between state transitions is λ ( β + 1 − e −λβ(1 − q r ) n ) Expected number of departures between state transitions in state n is probability of successful transmission λβ + q r n 1 − q r e −λβ(1 − q r ) n Information Networks – p.7/42 Nonpersistent CSMA Slotted Aloha The drift in state n is as before the expected number of arrivals less expected numbers of departures D n = λ ( β + 1 − e −λβ(1 − q r ) n ) − λβ + q r n 1 − q r e −λβ(1 − q r ) n For small q r w e mak e the approximation (1 − q r ) n − 1 ≈ (1 − q r ) n ≈ e − q r n and get D n ≈ λ ( β + 1 − e − g(n) ) − g ( n ) e − g(n) where g ( n ) = λβ + q r n is expected number of attempted transmissions Information Networks – p.8/42 Nonpersistent CSMA Slotted Aloha The drift is negativ e if λ < g ( n ) e − g(n) β + 1 − e − g(n) where the numerator is the expected number of departures per state transition and the denominator is the expected duration of a state transition, so it can be interpreted as the departure rate in state n W e can plot departure rate as function of attempted rate as before, for small β this function has a maximum of approximately 1 /(1 + √ 2 β ) for g = √ 2 β Information Networks – p.9/42 Nonpersistent CSMA Slotted Aloha 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Information Networks – p.10/42 Nonpersistent CSMA Slotted Aloha W e ha v e the same stability problem as in ordinar y slotted Aloha For fixed q r, g ( n ) grows with n and when n becomes too large, departure rate is less than arrival rate, leading to yet larger backlogs Expected idle time that a backlogged node must wait before attempting retransmission is β ( q r + 2 q r(1 − q r ) + 3 q r(1 − q r ) 2 + . . .) = β/q r, for small β and modest λ, q r can be quite small without causing appreciable dela y, this means that backlog must be ver y large before instability sets in and the problem is less serious than for ordinar y Aloha Information Networks – p.11/42 CSMA Slotted Aloha P-persistent CSMA, in which packets are transmitted after idle slots with probability p if they are new arrivals and with some much smaller probability qr if they have had collisions will give a little extra protection against instability A more fundamental way to achieve stability is to do a pseudo-Bayesian stabilization as for the ordinary slotted Aloha All packets are considered backlogged immediately after entering the system At end of each idle slot, each backlogged packet is transmitted with probability qr which will vary with the estimated channel backlog nˆ Information Networks – p.12/42 Pseudo-Bayesian stabilization In state n, expected number of packets transmitted at end of idle slot is g(n) = nqr, packet departure rate is maximized (for small β and qr) when g(n) = √2β so we choose qr(nˆ) = min √2βnˆ ,p2β Backlog estimate is updated according to n ˆ k+1 = nˆk(1 − qr(nˆk)) + λβ, for idle nˆk(1 − qr(nˆk)) + λ(1 + β), for success nˆk + 2 + λ(1 + β), for collision Information Networks – p.13/42 Pseudo-Bayesian stabilization Again the update rule for this Pseudo-Bayesian stabilization can be motivated by showing that for an a priori Poisson distribution of nk with mean nˆk, the a posteriori distribution of nk is Poisson with mean nˆk(1 − qr(nˆk)) given an idle slot Poisson with mean 1 + nˆk(1 − qr(nˆk)) given a successful transmission approximately Poisson with mean nˆk + 2 given a collision Adding the expected arrivals in the three cases yields the suggested update rule Information Networks – p.14/42 Pseudo-Bayesian stabilization When nk and nˆk are small then qr is relatively large and new arrivals are scarcely delayed at all When nˆk ≈ nk and nk is large, the departure rate is approximately 1/(1 + √2β), so for λ < 1/(1 + √2β) the backlog decreases on average If |nk − nˆk| is large the expected change in backlog can be positive, but the expected change in |nk − nˆk| is negative so eventually nˆk will be close to nk and backlog will decrease; similar to pseudo-Bayesian stabilization of ordinary slotted Aloha Information Networks – p.15/42 Delay for Pseudo-Bayesian stabilization We can do a similar analysis of the expected queueing delay as for pseudo-Bayesian stabilization of ordinary slotted Aloha Let Wi be the delay from arrival of ith packet until beginning of ith successful transmission Average of Wi over all i is the expected queueing delay W Let ni be the number of backlogged packets at the instant before packet i’s arrival, not counting any packet currently in successful transmission Information Networks – p.16/42 Delay for Pseudo-Bayesian stabilization Wi = Ri +X ni j=1 tj + yi where Ri is residual time until next state transition, tj is the sequence of subsequent intervals until each of the next ni successful transmissions are completed, and yi is the remaining interval until the ith successful transmission starts The backlog is at least 1 in all of the state transition intervals and we make the simplifying approximation that the number of attempted transmissions in each of these intervals are Poisson with parameter g Information Networks – p.17/42 Delay for Pseudo-Bayesian stabilization The difference from analysis of ordinary slotted Aloha is that there we assumed a successful transmission always occurred, this is motivated by our new qr is kept small The expected value for each tj is given by E[t] = e−g(β+E[t])+ge−g(1+β)+[1−(1+g)e−g](1+β+E[t]) The first term corresponds to an idle transmission in first state transmission interval, second term for a success, and third term for collision Information Networks – p.18/42 Delay for Pseudo-Bayesian stabilization Solving for E[t] gives E[t] = 1 + β − e−g ge−g This is the reciprocal of expected departure rate and thus is approximately minimized by g = √2β Averaging over i and using Little’s theorem we get W(1 − λE[t]) = E[R] + E[y] Information Networks – p.19/42 Delay for Pseudo-Bayesian stabilization The expected residual time E[R] is approximated by observing that the system spends a fraction λ(1 + β) of the time in successful state transition intervals, and the expected residual time for arrivals in these intervals is (1 + β)/2 The fraction of time spend in collision intervals is negligible (for small β) compared with that for success, and residual time for idle intervals is negligible too Thus, E[R] ≈ λ(1 + β)2 2 Information Networks – p.20/42 Delay for Pseudo-Bayesian stabilization Finally E[y] is just E[t] less the time for a successful transmission, E[y] = E[t] − (1 + β) Putting all this together we get W ≈ λ(1 + β)2 + 2(E[t] − (1 + β)) 2(1 − λE[t]) This expression is minimized over g by minimizing E[t] which is 1 + √2β at g = √2β (for small β), thus W ≈ λ + 2√2β 2(1 − λ(1 + √2β)) Information Networks – p.21/42 Delay for Pseudo-Bayesian stabilization The delay for stabilized CSMA Aloha W ≈ λ + 2√2β 2(1 − λ(1 + √2β)) is similar to the M/D/1 queueing delay with service time µ = 1 (we assumed time measured in average packet transmission time) W = λ 2(1 − λ) By stabilizing CSMA Aloha we modify qr with the backlog to maintain a departure rate close to 1/(1 + √2β) whenever a backlog exists Information Networks – p.22/42 Unslotted CSMA Aloha In slotted CSMA Aloha we assumed that all nodes were synchronized to start transmissions only at time multiples of β in idle period, we now remove that restriction and assume that when a packet arrives its transmission starts immediately if it senses the channel to be idle If the channel is sensed to be busy, or if transmission results in a collision, the packet is regarded as backlogged Each backlogged packet repeatedly attempts to retransmit at randomly selected times separated by independent exponentially distributed random waiting times τ with probability density xe−xτ Information Networks – p.23/42 Unslotted CSMA Aloha If the channel is idle at one of these times the packet is transmitted and this continues until the packet has been successfully transmitted We again assume propagation and detection delay of β, so if one transmission starts at time t, another one will not detect channel as busy until time t + β thus causing the possibility of collisions For an idle period that starts with a backlog of n the time until first transmission starts is exponentially distributed with rate G(n) = λ + nx Note that G(n) is now attempt rate in packets per unit time, previously g(n) was packets per idle slot Information Networks – p.24/42 Unslotted CSMA Aloha After initiation of this first transmission, the backlog is either n (if a new arrival started the transmission) or n − 1 (if a backlogged packet started) The time from this first transmission until next new arrival or backlogged node is exponentially distributed with rate G(n) or G(n − 1), this difference is small if βx is small and we neglect it Collision occurs if this time is less than β, thus probability of collision is 1 − e−βG(n) and probability for successful transmission is e−βG(n) Information Networks – p.25/42 Unslotted CSMA Aloha The expected time from beginning of one idle period until next is 1/G(n) + (1 + β) where 1/G(n) is the time until first transmission and (1 + β) is time until first transmission ends and the channel is detected as idle again If a collision occurs there is a slight additional time, less than β, until the packets causing the collision are no longer detected, this time is however negligible since already β is negligible The departure rate when backlog is n is then e −βG(n) 1/G(n) + (1 + β) Information Networks – p.26/42 Unslotted CSMA Aloha For small β the maximum value of this departure rate is approximately 1/(1 + 2√β) occuring when G(n) ≈ 1/√β This maximum departure rate is slightly lower than for the slotted case; the reason is the same as when CSMA is not used, the probability for collisions for an unslotted system is slightly higher for a given attempt rate For CSMA, with small β, this difference is quite small and further in a slotted system β has to be larger due to synchronization inaccuracies and worst-case propagation delay Information Networks – p.27/42 Unslotted CSMA Aloha Thus unslotted CSMA Aloha is a natural choice Also unslotted CSMA Aloha has stability problems, and these can be solved with a pseudo-Bayesian stabilization strategy similar to the slotted case Information Networks – p.28/42 FCFS splitting algorithm for CSMA Relatively little can be gained by using splitting algorithms with CSMA For FCFS splitting algorithm the maximum stable throughput is approximately the same as for slotted Aloha This is not surprising when realizing that without CSMA the major advantage of FCFS algorithm is its efficiency in resolving collisions, and with CSMA collisions rarely occur When collisions do occur they are resolved in both strategies by retransmission with small probability Information Networks – p.29/42 Multiaccess reservations It’s quite obvious that if packet lengths are large it’s inefficient to waste time on sending colliding packets during an entire slot time It’s far more efficient to send very short packets in either contention mode or a TDM mode to reserve longer noncontending slots for the actual data In this way the slots wasted by idles or collisions are all short leading to a higher overall efficiency Assume reservation packets require v time units which is much less than the one time unit needed for data packets Information Networks – p.30/42 Multiaccess reservations Let Sr be the maximum throughput for the reservation packets of the algorithm used for reservation packets (i.e. 1/e for slotted Aloha, 0.478 for splitting, etc) Over a large number of reservations the time required per reservation approaches v/Sr, and an additional unit of time for the data packet, thus the total time per data packet approaches 1 + v/Sr and the maximum throughput S in data packets per unit time is S = 1 1 + v/Sr Information Networks – p.31/42 CSMA/CD Ethernet is a widely used technique for local area networks, a number of nodes are all connected onto a common cable so that when one node transmits a packet (and all others are silent), all the other nodes hear that packet In addition, as in carrier sensing, a node can listen to the cable before transmitting Finally because of the physical properties of the cable, it is possible for a node to listen to the cable while transmitting Thus, if two nodes start to transmit almost simultaneously, they will shortly detect a collision in process and both cease transmitting Information Networks – p.32/42 CSMA/CD This technique is called CSMA/Collision Detection (CSMA/CD) If one node starts transmitting and no other node starts before the first node’s signal has propagated throughout the cable, the first node is guaranteed to finish its packet without collision Thus, we can view the first portion of a packet as making a reservation for the rest For analytic purposes it’s easiest to visualize Ethernet in terms of slots and minislots, the minislots are of duration β which denotes the time for the signal to propagate throughout the cable and be detected Information Networks – p.33/42 Slotted CSMA/CD If the nodes are synchronized into minislots of duration β, and if only one node transmits in a minislot, all the other nodes will detect the transmission and not use subsequent minislots until the entire packet completed If more than one node transmits in a minislot, each transmitting node will detect this and cease transmitting by the end of the minislot Thus the minislots are used in contention mode, and when a successful transmission occurs in a minislot it reserves the channel for the completion of the packet CSMA/CD can be analyzed with a Markov chain in the same way as CSMA Aloha Information Networks – p.34/42 Slotted CSMA/CD We assume that each backlogged node transmits after each idle slot with probability qr, and that the number of nodes transmitting after an idle slot is Poisson with parameter g(n) = λβ + nqr If no transmission occurs the idle slot ends after time β, if one transmission occurs the next idle slots ends after time 1 + β We can assume variable-length packets, but to correspond to the slotted assumption the packet durations should be multiples of β, as before we assume expected packet duration is 1 If collision occurs, next idle slot ends after time 2β, this is because nodes must hear an idle slot after the collision to know that it’s safe to transmit Information Networks – p.35/42 Slotted CSMA/CD The expected length of the interval between state transitions is then E[interval] = β + g(n)e−g(n) + β(1 − (1 + g(n))e−g(n)) The expected number of arrivals between state transmissions is λ times this interval, so the drift in state n is λE[interval] − Psucc, the probability of success is g(n)e−g(n), so we get that the drift is negative if λ < g(n)e−g(n) β + g(n)e−g(n) + β(1 − (1 + g(n))e−g(n)) The right-hand side of the inequality can be interpreted as the departure rate in state n Information Networks – p.36/42 Slotted CSMA/CD The departure rate is maximized over g(n) at g(n) = 0.77 and the resulting maximum is 1/(1 + 3.31β) CSMA/CD can be stabilized with e.g. the pseudo-Bayesian technique and then the maximum λ for which the system is stable is λ < 1/(1 + 3.31β) The expected queueing delay can be calculated the same way as for CSMA, the result for small β and mean-square packet duration X2 is W ≈ λX2 + β(4.62 + 2λ) 2(1 − λ(1 + 3.31β)) Information Networks – p.37/42 Slotted CSMA/CD The constant 3.31 is dependent on the detailed assumptions about the system, different values can be obtained by making different assumptions If β is very small, as usual in Ethernet, this value is not very important However, unslotted CSMA/CD makes considerably more sense than the slotted version, both because of the difficulty of synchronizing on short minislots and the advantages of capitalizing on shorter than maximum propagation delays when possible Information Networks – p.38/42 Unslotted CSMA/CD The exact analysis of unslotted CSMA/CD is somewhat messy and complicated, e.g. nodes closer together on the cable detect collisions faster than those more spread apart A conservative bound on throughput can be obtained by finding bounds on all relevant parameters from the end of one transmission to the end of next Assume that each node initiates transmissions according to independent Poisson processes whenever it senses the channel idle, assume G is overall Poisson intensity All nodes sense beginning of idle period at most β after end of transmission, expected time to beginning of next transmission is an additional 1/G Information Networks – p.39/42 Unslotted CSMA/CD This next packet will collide with some later starting packet with probability at most 1 − e−βG and the colliding packets will cease transmission after at most 2β The packet will be successful with probability at least e −βG and will occupy 1 time unit Departure rate is success probability divided by expected time of a success or collision; so S > e −βG β + 1/G + 2β(1 − e−βG) + e−βG Information Networks – p.40/42 Unslotted CSMA/CD This departure rate will be maximized at βG = 0.43 and the maximum value is 1/(1 + 6.2β) The analysis is very conservative, but if β is small throughput close to 1 can be achieved and the difference compared to the result for slotted CSMA/CD is not large Maximum stable throughput approaches 1 with decreasing β as a constant times β for CSMA/CD, whereas the approach is as a constant times √β for CSMA, the reason is that collisions are not very costly with CSMA/CD and thus a higher attempt rate can be used Information Networks – p.41/42 Unslotted CSMA/CD CSMA/CD (and CSMA) becomes increasingly inefficient with increasing bus length, increasing data rate, and decreasing packet size Recall that β is in units of data packet duration, thus if τ is propagation delay and detection time in seconds, C is raw data rate on the bus, and L is average packet length, then β = τC/L Neither CSMA nor CSMA/CD are reasonable system choices if β is more than a few tenths Information Networks – p.42/42