CPSC 441: Computer Communications

Professor Carey Williamson

Winter 2013

Assignment 4: Adaptive Tree Walk Protocol (24 marks)

Due: Tuesday, April 9, 2013 (11:59pm)

The purpose of this assignment is to learn about Medium Access Control (MAC) protocols. Along the way, you will also learn how to develop and use a simple discrete-event simulation for the performance analysis of network protocols.

Your particular task is to study the performance of the Adaptive Tree Walk channel access protocol. This MAC protocol is quite different from Ethernet's CSMA/CD or WiFi's CSMA/CA, but is also a bit simpler, since it is a discrete-time (slotted) protocol. While this specific protocol will not be covered in class, the general design principles and performance tradeoffs of channel access protocols will be discussed during the lectures on MAC protocols, and should be helpful to you when undertaking this assignment. However, the assignment is adequately self-contained that you can probably start on it either before or after we cover this lecture material in class.

In this assignment, you will reinforce key concepts regarding multiple-access protocols (e.g., shared channel, multiple stations, random access, collisions, successes, idle slots, utilization, efficiency), and determine how such protocols perform across a wide range of network loads. Finally, you will develop some intuition regarding how to make such a protocol adaptive (i.e., provide reasonable performance in the presence of widely varying network load).

Consider a simple bus-based linear-topology LAN with N nodes, where N is a power of 2 (e.g., N = 8). Attached to one end of this network is a special master controller C that is in charge of coordinating access to the shared bus channel for the N nodes. Assume that the stations are numbered from 0 to N -1 in binary (e.g., from '000' to '111' if N = 8).

The Adaptive Tree Walk Protocol conceptually arranges these stations into a complete binary tree configuration. For example, if N = 8, there are 8 (real) leaf nodes at Level 3, there are 4 virtual nodes (each with 2 children) above them at Level 2, there are 2 virtual nodes above these at Level 1, and 1 virtual node at Level 0, which is the root of the binary tree.

Each virtual node in this binary tree represents a particular subset of the real nodes (stations) in the network. For example, the root node represents "all stations in the network", while the leftmost virtual node on Level 1 represents "all stations with an address of the form 0XX", and the rightmost virtual node on Level 1 represents "all stations with an address of the form 1XX", where 'X' denotes a wild-card (i.e., Don't Care) condition. Similar reasoning applies recursively for other levels of the tree. For example, the rightmost virtual node on Level 2 represents "all stations with an address of the form 11X". Note that the virtual binary tree structure is conceptual only; the physical layout of the network is simply a linear bus with N nodes.

The controller regulates channel access on this LAN by polling (querying) certain subsets of the nodes in subsequent steps of the protocol, giving them permission to transmit their pending data frames, if any. These polling steps are referred to as probes in the following description of the protocol. For example, suppose that stations 1, 5, and 6 all have frames ready to send. If the controller starts the probing at the root of the tree (Level 0), a collision would occur on the first probe attempt, since three ready stations all try to seize the channel at the same time. Subsequent recursive probes to the two individual nodes on Level 1 would result in a successful transmission for station 1 in the first time slot (since it is the only ready station in the left half of the logical subtree), followed by another collision probe for stations 5 and 6 in the next time slot (since two of the four nodes in the right subtree attempt transmission). Further recursive probes down the right subtree to Level 2 will resolve the channel access, with a successful transmission by station 5 followed by a successful transmission by station 6. In this scenario, resolving the three original data frame transmissions required a total of 5 probe slots: 2 collisions, 3 successes, and 0 idle. Had the controller started at Level 2 initially, the same three station transmissions could have been resolved in 4 probes: 1 success, 1 idle (for stations 2 and 3), and 2 more successes. Continuing the example, if the controller were to start at Level 3 for the given initial scenario, there would be 8 probes required: 3 of these would lead to successful transmissions (stations 1, 5, and 6), and 5 of these would be idle (wasted) probe slots.

Clearly, starting somewhere in between Level 0 and Level 3 is the best strategy in this particular example. Intuition suggests that when the network is lightly loaded (i.e., very few stations have data frames ready to send), the central controller should start at or near the top (root) of the tree. When the network is heavily loaded (i.e., many stations ready), the controller should start at or near the bottom of the tree (close to or at the leaf level).

Your task in this assignment is to study the effect of the starting level on the performance of the Adaptive Tree Walk protocol. You will write a simple computer simulation program in C or C++ to study this problem.

You will evaluate a network with N = 1024 stations, studying it over many rounds of possible frame transmission scenarios. Stations generate frames randomly and independently from each other, and each station is equally likely to generate a frame in each round. You are to evaluate the performance of the protocol for several different values of aggregate offered load. In particular, you should evaluate the performance for when the number of ready stations in each round is k = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, and 1024.

For each load level specified by k, you should determine the average case performance of the protocol. In your simulation, you can do this by generating 100 random test scenarios of which stations are ready to transmit. For each scenario, your program should count the total number of probes required to successfully resolve all transmissions in that scenario. You can then compute the percentage of the total probes that are successful probes, averaging over the 100 trials. Do this for several possible starting levels for the algorithm, namely i = 0, 2, 4, 6, 8, and 10.

Plot the results from your analysis on a graph. The graph should have the successful probe percentage on the vertical axis (from 0% to 100%, on a linear scale) and the offered load k (i.e., the number of ready stations) on the horizontal axis (from 1 to 1024, on a logarithmic scale). Use your favourite graphing package (e.g., gnuplot, Excel, MatLab, or by hand).

You can put multiple lines on the same graph. Each line on the graph should show the percentage of successful probes as a function of offered load, for a given starting level i. Such a graph will help you determine (for each level of network load) what level of the tree the controller should start probing in order to maximize the successful probe percentage.

When you are finished, please email your solution in electronic form to your TA, attaching a single gzipped tar file. Your submission should include the source code for your MAC protocol simulator, a very brief user manual, and your simulation results (in graphical and tabular form).

The proposed grading scheme for the assignment is as follows:

Up to 4 bonus marks are available if you can think of a clever way to improve the overall performance of the Adaptive Treewalk Protocol, and demonstrate its effectiveness using simulation.

Tip: When debugging your code, use a small network topology (such as N = 8, or smaller) as your example. When you are sure your results make sense, scale up the network size and do your final runs.