CS 4873 Computer Networks, Fall 1997 Assignment 4

Due Thursday, November 13 at the start of class

Print out the postscript file: /usr/local/courses/cs4873/fall97/cover4.ps and use it as your cover sheet. Make sure you show how you got your answer to each problem.

  1. Five identical stations share a slotted Aloha channel. Note that 5 is not a large number.
    1. Write down an equation giving the relationship between S and G.
    2. Show that the maximum value of S occurs when G = 1.
    3. What is the maximum value of S?
    4. Is this maximum value bigger or smaller than in the case of an infinite number of users?

  2. Suppose that the slotted Aloha system in the previous problem is running at maximum efficiency, G = 1.
    What is the probability that a given slot will have:
    1. no transmissions
    2. a successful transmission
    3. a collision

  3. A pure Aloha system has 1000 identical stations. Frames are 100 bits each and the data rate of the channel is 4 Mbps. A measurement of the system shows that the probability that a transmitted frame will be transmitted successfully is 0.8.
    1. What is the channel load, G?
    2. What is the throughput, S?
    3. What is the average number of attempts needed for a successful transmission?

  4. A slotted Aloha system has 1000 identical stations. Frames are 100 bits each and the data rate of the channel is 4 Mbps. A measurement of the system shows that 81.24 percent of the slots are empty.
    1. What is the channel load, G?
    2. What is the throughput, S?
    3. What is the average number of attempts needed for a successful transmission?

  5. A slotted Aloha system has 1000 identical stations. Frames are 100 bits each and the data rate of the channel is 4 Mbps. A measurement of the system shows that 6 percent of the slots are empty.
    1. What is the channel load, G?
    2. What is the throughput, S? Compare your answer to 4b.
    3. What is the average number of attempts needed for a successful transmission?

  6. A slotted Aloha system has 1000 identical stations. Frames are 100 bits each and the data rate of the channel is 4 Mbps. Each station generates 5 new frames per second.
    1. What is the channel load, G?
    2. What is the throughput, S?
    3. What is the average number of attempts needed for a successful transmission?
    Hint: Be careful on this one. Explain how you got your answers.

  7. A CSMA/CD system has a 100 meter cable, a fixed frame size of 1000 bits, runs at 10 Mbps, and has a propagation speed of 200 meters per microsecond.
    1. How does the propagation speed compare to that of the speed of light?
    2. How long is a contention slot?
    3. How long does it take to send a frame?
    4. All other things being as described above, what cable lengths would have the contention slot smaller than the frame time?
    5. All other things being as described above, what frame sizes would have the contention slot smaller than the frame time?

  8. Suppose that X and Y are events and PX is the probability that event X occurs and PY is the probability that event Y occurs. Let PXY be the probability of both event X and Y occurring and PX+Y be the probability that either event X or event Y (or both) occur. You probably know that
    PX+Y = PX + PY - PXY.
    Write down the corresponding formula for 3 events. That is give a formula for PX+Y+Z in terms of PX, PY, PZ, PXY, PXZ, PYZ, and PXYZ.

  9. Consider 10 identical stations contending for a channel using linear backoff. On the first round they all transmit and collide. On the second round there are two slots in which the stations can contend. On round k there are k slots in which the stations can contend.
    1. What is the probability that a given station will be successful on round 2?
      Show how you got your answer.
    2. What is the probability that at least one station will be successful on round 2?
      Show how you got your answer.
    3. Assume that no station was successful on round 2.
      What is the probability that a given station will be successful on round 3?
      Show how you got your answer.
    4. Assume that no station was successful on round 2.
      What is the probability that the first slot will have exactly one station transmitting?
    5. Assume that no station was successful on round 2.
      What is the probability that the first two slots will both have exactly one station transmitting?
    6. Assume that no station was successful on round 2.
      What is the probability that the first three slots will have exactly one station transmitting?
    7. Assume that no station was successful on round 2.
      What is the probability that at least one station will be successful on round 3?
      Show how you got your answer.
    8. What is the probability that the first round in which there is a successful transmission is round 3? Show how you got your answer.

  10. Extra Credit.
    Redo all of the parts of the previous problem for binary exponential backoff. On round k there are 2k-1 slots. Sorry, no extra credit for just doing parts a) and b) since these are the same as in problem 9.