Corporate and Professional Publishing Group
ISBN 0-201-63442-2 * Hardcover * 688 pages * 1997
Book Description
· Preface
· Glossary
· Bibliography
· Solutions
· Slides
· Simulator
· Exercises
· Errata
· Cover
(73K) · Ordering
Information · C&P
Welcome Page.
9/30/97: Corrections are in red.
Your assignment is to study the behavior of CSMA/CD as you change the network load and network diameter. The network load is the amount of traffic that stations want to send on the network. The network diameter is the time it takes for a packet to travel from one end of the network to the other (this controls the parameter 'a', which was described in class).
REAL does not allow direct simulation of a broadcast medium, since it only supports point-to-point links. Instead, the CSMA protocol is simulated with the help of a node called ecn_master that represents the medium. When a station (also called a slave) puts a packet on the medium (by sending a DATA packet to the master), the medium becomes busy and all other stations need to be informed of this condition. To simulate this, when a slave wants to send a data packet, it sends it to the master. The master computes the delay from the transmitting station to each of the other stations on the network. It then sends them a BUSY packet. Stations are not allowed to send a packet until they get an IDLE packet, which corresponds to seeing the last bit of a data packet. If a packet is transmitted successfully (that is, without collisions), a station eventually receives an IDLE packet from the master. In case of a collision, it receives a NACK packet from the master (all other stations also receive this packet, which is called jamming).
Thus, the sequence of packets received by a slave from the master (whether or not it sent a data packet to the master) can either be
BUSY -> NACK ->
IDLE
/* collision */
Note that though the simulation uses a master-slave configuration, in practice, CSMA/CD is a distributed protocol, and all stations are peers, with no master. We use the master-slave paradigm purely for the purposes of simulation.
Packets are generated at each slave according to the Possion distribution. If a slave has a packet to send, it waits till the line is idle and sends the packet. While waiting, it can accumulate several packets to send, and this is kept track of by putting it in a local node queue. A slave keeps trying to send a packet as long as it has a non-empty queue.
Slaves do exponential backoff when a collision happens. This is done by doubling a variable called retry_interval, and setting a timer with a random value in the range [0, retry_interval]. A timed-out slave will not send a packet until the timer expires, even if the line is idle. The retry interval is reset to the initial value on a successful packet transmission.
The directory sim/sources contains two files ecn_master.c and ecn_slave.c, which contain the code for the medium and the station respectively. Study the code carefully to see how they work.You need not modify the code in any way.
To run the simulation, type
The results of the simulation will appear in a directory
called csma in your sim directory. There are two result
files. One of them is called dump, and the other is
called plot. Ignore the dump file. You have to extract
some files from the plot file using the sim/kernel/demux utility.
Type
This will create some files in the csma directory. The files of interest are seq2, seq3, seq4, seq5, seq6, and busy1 (ignore seq1). The seq files are traces of the sequence number vs. time for each CSMA/CD station. An entry of the form <time seq> means that the packet with that sequence number was sent at that time. The busy file records the times when the medium is busy (the start of a busy time is marked with a 0-1 transition, and the end by a 1-0 transition).
The last sequence number sent by a source before the end of the simulation (chosen by the end_simulation parameter in csma.l) is the last entry in this file (for instance, if the last entry is 9.9995 64.000, this means that a packet with sequence number 64 was sent at time 9.9995, and this was the last packet sent by this node). The throughput obtained by this source, therefore, is this sequence number, multplied by the packet size in bits (the parameter ftp_size in csma.l) divided by the length of the simulation interval (end_simulation). For example, if the last sequence number sent in a simulation of length 10 seconds was 24, and the packet size is 500 bytes = 4000 bits, the throughput achieved is 4000 * 24/10 bits/s = 9600 bits/s. The total carried load is the sum of these throughputs over all the sources. The offered load of a source is chosen by the average_rate parameter in the csma.l file. Thus, the total average rate is the sum of the average rates over all the sources. Your goal is to study the carried load as a function of the offered load and the network diameter.
The six major parameters that you can control in the simulation are (a) the number of stations (b) the average rate of each station, (c) the diameter of the network, (d) the packet size, (e) the number of packets sent from each station and (f) the length of the simulation. An increase in either (a) or (b) increases the offered load. An increase in (c) or a decrease in (d) increases the parameter 'a'. (Do not confuse the diameter with 'a'! Increasing the diameter increases the propagation delay, which is just the numerator of the formula for 'a'. Decreasing the packet size decreases the transmission time, which increases 'a'.)
If you choose a very high link capacity, then many more packets will be sent per unit time. So, you should also choose a smaller end time for the simulation. You want all sources to send essentially an infinite number of packets. So, set parameter (e) very high. Note also that if the link capacity is very low, then the backoff timer can be very large. The simulator cannot timers larger than about a million seconds, which overflows the timer value. You will then get an error message of the form "settimer got a negative value". If you get this message, resize the simulation so that the link capacity is higher (and the diameter and simulation running times are proportionately reduced).
By running simulations with different choices of these parameters, you can plot the carried load as a function of the offered load for different choices of the parameter 'a'. Your assignment is to create this family of curves by carrying out the necessary simulations. Please set random_seed in csma.l to 0 in order to randomize your choice of configurations.
A better appreciation of the system can be gained by reducing the length of the simulation, and turning on the debugging of the ecn_slave and ecn_master nodes. You can do this by setting CSMA_DEBUG to 1 in the file kernel/switches.c and recompiling the simulator. Observe how the nodes progress through different states in response to incoming messages. You can also study the sequence number traces in detail by using a plotting program such as xgraph or gnuplot, and zooming in on a small interval. What happens when source gets a TIMEOUT? How does the choice of retry_interval change the carried load? What happens when the number of sources increases? What happens when the number of sources is small, but the sum of their load increases? Try to answer these questions by running sets of simulations.
Hints
Grading
We will grade you based on a one page (and one side) hardcopy report. The report should have the following format. (Please use exactly these headings in your submission.)
Header
Your name and email address
A. Curves
In this section, plot the results of your
simulation in a graph of size roughly 3" x 5". On the X
axis, show the offered load on a scale from 0.0 to 5.0,
normalized to the link bandwidth (i.e., if the sum of average
rates is 500 Kbps, and the link capacity is 1 Mbps, then the
normalized offered load is 0.5). On the Y axis, show the carried
load, normalized to the link bandwidth. Compute this using the
technique described earlier. Plot a set of
3 curves corresponding to 'a' values of 0.01, 0.1, and 0.49.
You can vary 'a' for a simulation by appropriately choosing the
'diameter' parameter in the input file. Use the same link
capacity for the entire set of simulations (a good choice is
40,000 bps, so that a 500 byte = 4000 bit packet has a
transmission time of 100 ms.) Please label each curve (you can
plot values using a tool such as gnuplot, or on graph paper).
B. Choice of parameters
In this section, describe how you computed 'a', and how
you changed the offered load. How many simulations did you run?
How confident are you of your results?
C. Conclusions
Interpret the curves in section A to draw some conclusions
about (a) the range of utilizations and (b) the range of 'a'
values for which CSMA/CD is a useful multiple access technique.
Also (c) comment on the fairness of CSMA/CD.
Your grade will be based on the completeness and clarity of your report.
