The projects should be done in groups of 2 students. 3 student groups are also acceptable, but then additional work is expected. Pointers for the additional work is given in the project document. Or, you are encouraged to discuss with the instructor. Working solo is acceptable. However this will typically amount to more work on your part. If you choose to work alone, you still have to complete the project and write a report. You should not expect any leniency in grading just because you worked alone.
You do not need to maintain the same group for all projects.
You are allowed and encouraged to use your own machine to run ns2. Most laptops are quite capable of running ns2. You do not necessarily have to use minix. However, we will not be able to provide set up help for your machines. However, in case of questions, you are expected to be able to demo your work to the TA or the instructor. Do not use a system that you cannot bring and cannot remotely access. You can also develop elsewhere, but finally run on minix. Codes should be pretty portable.
Introduction: In this project, you will use ns-2 to simulate an Ethernet LAN and evaluate its performance. We assume that you have basic familiarity with the CSMA/CD based protocol that 802.3-based Ethernet uses. Review this material from the textbook. The 802.3 Ethernet simulation model is already built in ns-2. So you will not need to develop the model. ns-2 uses tcl scripts to configure the simulator (such as construct the network to simulate, specify the protocol to use, specify traffic sources etc.). To make your job easier, we have created a tcl script (etherlan.tcl) that describes an Ethernet with n nodes, where n-1 nodes send Ethernet frames to one designated node acting as receiver.
Your first step will be to familiarize yourself with running ns-2 and understanding the traces it produces. As specified in etherlan.tcl, the trace of the simulation will be produced in file "trace". Your goal is to interpret the trace and analyze it to derive some interesting performance measures. More on this later. Note that you may need to modify/extend etherlan.tcl to suit your needs.
Analysis: You will primarily need to evaluate primarily the throughput, delay and drop characteristics of the above Ethernet LAN as the offered load (load generated by the application) increases. Use aggregate throughput (Mbits/sec received at the receiver) and aggregate offered load (Mbits/sec generated by all sources combined). These should be easy to calculate from trace by counting the total #frames received at the receiver or generated by the sources, and observing the frame size and simulation time (the latter two are parameters set in the input script). The delay calculation is probably more involved. Each traffic source generates frames that goes into the Ethernet via a network interface which has a fixed size buffer (see the above figure). The reason we need a buffer is because the interface may often be busy, e.g., with a frame that is on backoff. If other frames are generated by the traffic source in the meanwhile they have to be temporarily buffered. This FIFO buffer at the interface should increase in length on average as load goes up. Also, packets may be dropped from this queue if the buffer is full. This possibility evidently goes up with increasing load.
The delay is the difference between the time the source enqueues the frame at the interface and the time the receiver receives it. The frame may, however, be dropped on enqueue (if the buffer is full). If not dropped, it will finally make its way through the front of the buffer, be dequeued, and then transmitted using the CSMA/CD MAC protocol. Note that here the frame may collide and be retransmitted several times, before finally showing up completely and correctly at the receiver. It may even be dropped by the MAC if the maximum retransmission count is exceeded. But this phenomenon probably will be rare.
In addition to the source to receiver delay (end-to-end delay) as above, we would also like to know the delay purely on the network. This is the delay between the dequeue and final receive. This is basically the above delay minus the queuing delay at the buffer.
The tracing support you will use will not trace anything that goes on the MAC layer. It would be a nice thing to trace the activity on the MAC, but we will hold off on that for another assignment. So the trace events are only the enqueue and dequeue at the interface buffer and the final receive at the receiver. Each trace record has. among other things, the event type (`+' for enqueue, `-' for dequeue, `d' for drops and `r' for receive), timestamp of the event, source and destination of the packet, plus a packet id to enable you to trace a particular packet. You will note that the trace events are ordered by timestamps.
The total offered load generated by the sources is nl. Not all of it reaches the Ethernet because some frames may be dropped. We are also interested in evaluating the drop probability against the load generated by the source. The fraction of frames dropped can be used as an estimate of drop probability. Note that the drop probability should be controlled by the buffer size, and you should plan on some experiments to demonstrate this.
All these evaluations should be repeated for different frame sizes. You should experiment with at least three frame sizes (say, 64 bytes, 512 bytes and 1500 bytes). We have reasons to believe that things should look somewhat different for different frame sizes (why?). Thus to summarize, you should plan on generating at least the following four sets of performance plots: (a) throughput vs. offered load, (b) two different types of delay vs. offered load, (c) drop probability vs. offered load, each experiment for at least three frame sizes and a fixed buffer size (say, 10). (d) In addition, you should do at least one set of experiments to demonstrate the effect of buffer size on drop probability, where you should keep the offered load constant at a high value, but lower than the network capacity (say, 8-10 Mbits/sec) and use medium sized frame (around 512 bytes).
The offered load for your experiments should be varied from a very low value to a very high value to see interesting things. We recommend varying from 0.2 Mb/s to about 20 Mb/s at suitable steps. Simulations should be run long enough for data to stabilize, but very long runs will generate very large trace files. It appears just a few seconds run should be enough. But you can experiment with that.
Reading: The following two papers are very instructive for this
project as
they also analyze Ethernet performance using simulation and/or direct
measurements.
Here, you will investigate the short-term unfairness problem in Ethernet using the ns2 simulator. The tech report in the following reference is an excellent article to understand this problem. For your report (see below), you can use presentations along the line of Figure 4 and Tables 1, 2 in the referenced tech report. For the MRU stack depth vs acquisition probability plot, try a few different offered loads, e.g., very small 0.2 Mbits/sec, medium small 1 Mbits/sec, small 2 Mbits/sec, medium 5 Mbits/sec, and high 8 Mbits.sec. You should also present statistics of run lengths in terms of relative frequency of occurrences (i.e., histogram or probability density function).
Reference:
Also implement the proposed solution to address the unfairness problem and observe the effects. This will require you to modify the Ethernet model in ns2. and re-complie ns2 using your own copy of ns2 (i.e., don't use the public copy on ns2). If you have other ideas for additional work, send me an email.
You will need to summarize everything you did in a brief report, which must be wordproceesed. Of course, the emphasis in your report will be on the results which must be presented in the form of plots. Plots must be carefully presented, for example, similar plots (e.g., throughput vs. load for different packet sizes) should go in the same figure so that they can be easily compared. They should be clearly labeled. Look at the papers for ideas on presentation. All important and interesting observations should be summarized carefully (e.g., do different packets sizes behave differently? should they? does throughput go up or down with load? should it? what is the maximum throughput we get? is it reasonable? does it stabilize at high value of offered load? Is your observation on fairness different from the published work? Why? etc. etc.) Bulk of your grade in this project will depend on your plots, presentation and readability of plots and your interpretations and/or observations.
The report need not be long. I expect it to be less than 5 pages including plots (assuming that you do put a lot of white spaces around and don't make the plots unnecessarily large), though I do not want to specify any limit. No need to include any code you developed, though a short description as a part of the report is expected. However, be prepared to demo everything you developed, in case of questions. If we want you to demo, you will be asked.
Note that the project should be the sole of you and your partner(s) in the project. You should reference all materials (e.g., papers, books, manuals, Internet sites) you took help from. You are encouraged to get help from your classmates on running or debugging ns2, understanding ns2 code, understanding and interpreting traces, etc., so long as it is not specific to the project.
The FAQ will be updated as we get questions.