I came across this section in the paper Providing quality of service over a shared wireless link, IEEE Communications Magazine:
Consider a very simple system with two users. The service rate (in a time slot) for user 1 is either 76.8 kb/s or 153.6 kb/s with equal probabilities 0.5. For user 2 the rates are 153.6 kb/s or 307.2 kb/s, also with equal probabilities. (Thus, the channel quality of user 2 is better on average.) Assume that channels for both users are independent, and there is unlimited amount of data to transmit to each user. Then, a “naive” round-robin allocation of time slots to the users will result in users served at the average rates R1= 0.5 x(0.5 x 76.8 + 0.5 x 153.6)= 57.6 kb/s and R2= 0.5 x(0.5 x153.6 + 0.5 x307.2) = 115.2 kb/s, respectively. Consider another scheduling scheme where a user with a “relatively better” (in a current time slot) service rate (153.6 kb/s for user 1 and 307.2 kb/s for user 2) is scheduled. In case of a “tie” (i.e., if channels are relatively better or relatively worse for both users), the user to serve is chosen randomly with equal probabilities 0.5 . A straightforward calculation shows that with this scheduling, the average rates are R1 = 67.2 and R2 = 134.4 kb/s, which is 16 percent higher for each user than with the round-robin discipline. This is an example of proportionally fair scheduling.
I'm trying to figure out the rates (marked in bold) that have been obtained for the proportionally fair case. As per my understanding, user 1 would get selected over user 2 only 1/8th of the time (because with probability 0.5, user 1 sees a rate of 153.6 kb/s, which can get chosen over user 2 only 1/4th of the time since user 2 can see a rate of 153.6 with probabilty=0.5 and then user 1 is selected randomly with another probability of 0.5). Then, R1 = (1/8)x(0.5 x 76.8 + 0.5 x 153.6) = 14.4 kbps and R2 = (7/8)x(0.5 x153.6 + 0.5 x307.2) = 201.6 kbps.
What am I missing here? This seems to be a simple math problem, but I think I've not understood the concept of proportional fairness correctly.
Best Answer
I see how you came up with your result -- it is a different interpretation of the phrase "relatively better." It does not mean relatively better than the other user, but relatively better for the same user.
To calculate the speeds, look at a given time slot and randomly select a speed for both user 1 and user 2. One of four cases should occur, with equal probability (since speed selection is 0.5 for each):
User 1 at 76.8 (low for U1), user 2 at 153.6 (low for U2). Since both are "relatively low", choose between the users with equal probability.
User 1 at 153.6 (high for U1), user 2 at 153.6 (low for U2). Always choose U1.
User 1 at 76.8 (low for U1), user 2 at 307.2 (high for U2). Always choose U2.
User 1 at 153.6 (high for U1), user 2 at 307.2 (high for U2). Tie, so choose between the two with equal probability.
The resulting average speed is then:
$$\text{User 1 speed} = \frac{1}{4}\left(\frac{1}{2}\cdot76.8+153.6+0+\frac{1}{2}\cdot153.6\right)\text{ kbps} = 67.2\text{ kbps}$$
$$\text{User 2 speed} = \frac{1}{4}\left(\frac{1}{2}\cdot153.6+0+307.2+\frac{1}{2}\cdot307.2\right)\text{ kbps} = 134.4\text{ kbps}$$