Homework 8 Medium Access Control

In this homework, we design a medium access control mechanism for a simulated channel. First, get a copy of the hw8 template, as in previous homeworks. The files hw8.c and hw8.h are not to be changed - your turn-in will be graded with the original files. Your contribution belongs in the files hw8_client.h and hw8_client.c.

The goal of this exercise is to achieve maximum throughput over the shared medium. In each time-slot, each client can transmit a single 'packet'. However, if two clients transmit at the same time, the result is a collision, which does not count toward the throughput. Similarly, if no client sends, no throughput is achieved.

The simulation proceeds through a number of turns that is specified on the command line:

./hw8 <#clients> <#turns> [random_seed]

for example:

./hw8 10 10 4489475

every turn, each 'client' gets to decide whether it wants to listen or transmit. After all clients have made their decisions, they received feedback: is the channel silent, did a single client transmit, or did several transmissions collide. A good client would base its decision in the next turn on what happened in the previous turn.

Clients do not, and should not have any prior knowledge of the number of clients contending for the channel, or the number of slots. You may try to estimate the number of clients based only on your decisions and the feedback you receive.

Your program should produce no output other than what is already being output from hw8.c. For example, the following:

/hw8/> ./hw8 2 10 4489475
2
0
0
0
1
1
0
255
0
2

This shows that in the first slot, client 2 sent a packet. Then there were three empty slots, followed by two transmissions by client 1, an empty slot, a collision, an empty slot, and a transmission by client 2.

You will find that using some command line tools to process the output is helpful. For example:


./hw8 10 100000 4489475 |  awk '{sum[$1]++} END {for(sender in sum){print sender,sum[sender]}}' | sort -n
0 15769
1 10160
2 4870
3 10760
4 3620
5 13720
6 8694
7 5200
8 5680
9 11250
10 10100
255 177

is the output of my current solution. Out of 100,000 slots, about 16,000 were wasted on silence or collisions, for a 'channel efficiency' of 84%.

Grading

Your solution will be graded based on (a) channel efficiency under a variety of conditions, and (b) fairness under a variety of conditions. We will measure fairness as the ratio of the highest and lowest throughput clients. For example, in the above results, fairness is 3620/15769 = 23%, and efficiency is 84%.

Conditions tested will include: (1) a set of several different random seeds, (2) a number of clients varying between 1 and 1000, (3) a number of slots varying between 1000 and 1000000.

Edit | Attach | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2010-11-10 - 19:46:07 - Main.jakob
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF