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 on stdout other than what is already being output from hw8.c. For example, the following:

/hw8/> ./hw8 2 10 4489475 2> /dev/null
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%.

Hints

  • If you want debug output, put it on stderr, like this:
fprintf(stderr,"my format %d", myint);
  • For improving efficiency, you may find it helpful to have a client send in more than one consecutive slot. For example, say you had your clients keep sending forever once they got one successful transmission through. This would give you near 100% efficiency, at the cost of 0% fairness.
  • For handling a variable number of clients, you may want to adjust your transmission probability based on your collision statistics (too many collisions => lower tx probability).
  • Friday's lecture will discuss several solutions used in practice.

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.

Cautions

The only allowable means of communication between clients is through the action decision (SEND, LISTEN). In particular, no global variables, static variables, files, sockets, locks, semaphores are allowed. Nor are any other means of coordination or communication.

Note: You may introduce as many variables as you like, but they must either be local variables in your functions, or fields in the client_state struct, not globals!

Topic revision: r2 - 2010-11-10 - 21:11:24 - 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