CS447/CS642 Homework Set 2 — Winter 2001

Due: Tuesday, January 16

  1. Suppose that each station in a group of 5 broadcast stations broadcasts packets of 0.1 seconds duration. Stations choose at random whether or not to broadcast in any 0.1 second period, and all stations which choose to broadcast are synchronized to begin broadcasting at the start of the same 0.1 second intervals. If each station chooses independently to broadcast with probability 0.2 in each slot, what proportiuon of intervals is wasted due to multiple colliding broadcasts in those slots?

    2. We need to calculate either:

    1 - ( P(0) + P(1) ) or,

    sum up all other cases.

    P(0) = 0.85 = 10-5*215 = 0.32

    P(1) = 5*0.2*0.84 = 0.41 Note: 5 is the number of ways only one station can be broadcasting.

    So the result we want is: 1 - 0.73 = 0.27

  2. A message is split into 10 packets, each of which has 80% chance of arriving undamaged. Assuming no error control, how many attempts to send the message are required for the entire message to arrive intact?

    3. P(all correct) = 0.810 ~ 0.1

    Therefore the average number of attempts is 1/P ~ 10

  3. A router is a device which connects together a group of Local Area Networks (LAN). In a router which connects a 10 Mbps LAN to the internet over a T1 (1.544 Mbps) link, how much memory is needed so that on average, only 5% of frames are lost? Assume that both LAN and T1 frames are always 1500 bytes and, that on average, they arrive 10 msec apart.

    4. lambda = 1/arrival time = 1/10ms = 100 frames/s

    u = 1.544 * 106 bps / (1500 B * 8b / B) = 128.7/s

    a = lambda/u = .78

    p = (1-a)aN / (1-a(N+1))

    .05 = (1-.78) * .78N / (1 - .78(N+1) )

    if N = 7 then .05 = (.22 ) * .18 / ( 1 - .14)

    Therefore we need to hold 7 packets which is 7 * 1500 = 10500 bytes.

    Reference: The Finite Buffer Case from Vastola's "Probability and Queuing" (RPI).

  4. In the diagram below, the numbers represent line reliability expressed as the probability of each line remaining intact during bad weather. To preserve (direct or indirect) communication among all nodes, no more than 1 line may break. If the probability of communication among all nodes must be no less than 72% during bad weather, what is the minimum reliability required of line QT?

    5. P = P(none bad) + (P one bad)

    .72 = 0.5*0.8*0.9*X + 0.5*0.8*0.9*(1-X) + 0.5*0.8*(1-0.9)*X + 0.5*(1-0.8)*0.9*X + (1-0.5)*0.8*0.9*X

    .72 = 0.36X + .36 - 0.36X + 0.04X + 0.09X + 0.36X

    0.72 = 0.36+0.49X

    X = 0.36/0.49 = 0.735

    Therefore, the reliability of X must be better than 0.735

Home Page