6.02 - Miscellaneous notes related to the ALOHA protocol Katrina LaCurts - lacurts@mit.edu ====================================================================== Determining the maximum value of p ====================================================================== U = N * p * (1-p)^(N-1) dU/dp: Let f(p) = N * p f'(p) = N Let g(p) = (1-p)^(N-1) g'(p) = (N-1) * -1 * (1-p)^(N-2) = (1-N) * (1-p)^(N-2) dU/dp = f(p)g'(p) + f'(p)g(p) = N * p * (1-N) * (1-p)^(N-2) + N * (1-p)^(N-1) = (1-p)^(N-2) * [ N * p * (1-N) + N * (1-p) ] = (1-p)^(N-2) * [ Np - N^2p + N - Np ] = (1-p)^(N-2) * (N - N^2p) = N * (1-p)^(N-2) * (1 - N*p) dU/dp = 0 when p = 1 or p = 1/N. d2U/dp: Let f(p) = (1-p)^(N-2) f'(p) = (N-2) * (1-p)^(N-3) * -1 = (2-N) * (1-p)^(N-3) Let g(p) = N * (1 - Np) = N - N^2p g'(p) = -N^2 d2U/dp = f(p)g'(p) + f'(p)g(p) = (1-p)^(N-2) * -N^2 + (2-N)*(1-p)^(N-3)*(N-N^2p) = (1-p)^(N-3) * [(1-p)*-N^2 + (2-N)*(N-N^2p) ] = (1-p)^(N-3) * [pN^2 - N^2 + 2N - 2N^2p -N^2 + N^3p] = (1-p)^(N-3) * [2N - pN^2 - 2N^2 + N^3p] = (1-p)^(N-3) * N * [2 - pN - 2N + N^2p] = (1-p)^(N-3) * N * [2(1-N) + pN(N-1)] = (1-p)^(N-3) * N * [2(1-N) - pN(1-N)] = (1-p)^(N-3) * N * (1-N) * (2 - pN) At p=1/N, d2U/dp is < 0 ==> p=1/N is max. d2U/dp @ p=1/N = (1 - 1/N) ^ (N-3) * N * (1-N) * (2 - 1) |_______________| |_| |___| |_____| > 0 >0 <0 >0 At p=1, d2U/dp = 0, but it's easy to see that this is a min. ====================================================================== Determining the maximum utilization ====================================================================== When p = 1/N, U = (1 - 1/N)^(N-1) Let g(N) = ln ( (1-1/N)^(N-1) ). Then the limit of g(N) is ln(lim of f(N) ) 1. lim g(N) = -1 Pf. We get to use some Taylor series: g(N) = (N-1) ln (1-1/N) = (N-1) ((-1/N)/1 - (-1/N)^2/2 + (-1/N)^3/3 - (-1/N)^4/4 + ...) = (N-1)(-1/N - 1/2N^2 - 1/3N^3 - 1/4N^4 - ...) = -(N-1)/N - (N-1)/2N^2 -(N-1)/3N^3 - (N-1)/4N^4 - ... = (1-N)/N + (1-N)/2N^2 + (1-N)/3N^3 + (1-N)/4N^4 + ... = 1/N - 1 + 1/2N^2 - 1/2N + 1/3N^2 - 1/3N^2 + 1/4N^4 - 1/4N^3 + ... = -1 + (1/N - 1/2N) + (1/2N^2 - 1/3N^2) + (1/3N^3 - 1/4N^3) + (1/4N^4 - 1/5N^4) + ... = -1 + 1/N + 1/6N^2 + 1/12N^3 + 1/20N^4 + .. As N -> inf, this approaches -1. 2. lim(f(N)) = 1/e, since lim(g(N)) = -1 and lim(g(N)) = ln(lim(f(N))) (i.e., -1 = ln(lim(f(N)))). ====================================================================== Unslotted ALOHA ====================================================================== Question: what happens in ALOHA when packets are bigger than one slot? Why do we even need slots? Consider a protocol known as Purely Unslotted ALOHA. In this protocol, each node can send any time it wants (literally any time; there are no slots). Will this protocol have better or worse utilization than Slotted ALOHA? To analyze the utilization, we'll use a slight different protocol: Almost Unslotted ALOHA: Packet sizes are T slots long, with T very large. I.e., time slots are very small in relation to the packet size. If we let the length of our time slot approach zero (and thus our packet size approach infinitely many time slots), this protocol is equivalent to Purely Unslotted ALOHA. To analyze utilization in Almost Unslotted ALOHA, we need to decide how packets can collide. When packets are only 1 timeslot long (as in Slotted ALOHA), this is an easy question: Packet X and Packet Y can only collide if they're sent in exactly the same time slot. But suppose the packets are 5 time slots long. Let's say Packet X takes up these time slots: x x x x x | | | | | | | | | | | | | | | | If packet Y starts here, it will collide with X: x x x x x | | | | | | | | | | | | | | | | y y y y y Similarly, if it starts here: x x x x x | | | | | | | | | | | | | | | | y y y y y And even here: x x x x x | | | | | | | | | | | | | | | | y y y y y There are 2*5-1 possible timeslots that Y can start in and collide with X: Any of the slots occupied by X -- of which there are 5, and any of the (5-1) slots preceding X. In general, if the packet length is T, there are 2T-1 different starting timeslots for packet Y to collide with packet X. So, should utilization increase or decrease with this protocol, compared to Slotted ALOHA? It should decrease; there are more chances for packets to collide now. By how much will it decrease? Let's figure it out. If I send, what is the probability that no one else will send in the surrounding 2T-1 timeslots? ( (1-p)^(N-1))^(2T-1) = (1-p)^{(2T-1)(N-1)} Note: this assumes that each node sends independently in each timeslot with probability p. Even though there's no sensing, we still wouldn't expect self interference, but this formula allows it. Utilization = throughput / maximum rate. = Np(1-p)^{(2T-1)(N-1)} / (1/T) Why 1/T? The maximum rate is the fraction of a packet in any one timeslot. = T*N*p(1-p)^{(2T-1)(N-1)} If we do algebra and take some derivatives, we get U = T/(2T-1)*e. With N large, this is roughly 1/2e, or half the utilization of Slotted ALOHA.