Assignment 3: Router Buffer Management (24 marks)

Due: Tuesday, March 26, 2013 (11:59pm)

The purpose of this assignment is to learn about the basic operation of routers and to understand some of the design tradeoffs for routers in packet-switched networks. Along the way, you will also gain familiarity with simple computer simulations, by conducting a multi-factor simulation experiment to evaluate different buffer management strategies for a simple packet-switching router.

Imagine that you have just started a summer job as a network administrator for a local Calgary company. One of your first tasks it to upgrade the backbone router in the company's rather large corporate network. Two vendors (A and B) have been short-listed as potential suppliers of the router that you need. Their prices are comparable, but the designs of their routers are different. You need to decide which design (A or B) is better for your network.

From your discussion with the vendors, you have learned that there are two different ways to organize the output buffering in a shared-memory packet-switching router. In complete partitioning, there are b buffers physically dedicated (e.g., as a hardware FIFO buffer) to each of the N output ports, for a total of B = N b buffers. In complete sharing, there is a central pool of B buffers that can be dynamically shared amongst all the output ports under software control. Examples of these two approaches are illustrated in a PowerPoint diagram, specifically for N = 4 and b = 5. Note that the total number of buffers B in the two designs is the same.

For this assignment, you are to simulate these two buffer management strategies to decide which approach (partitioned or shared) is better for a fast packet-switching router architecture.

The key factors in your experiment are:

• the input offered load L (between 0% and 100%)
• the router dimension N (number of input ports)
• the aggregate buffer capacity B (b per port, on average)
• the buffer management strategy (partitioned or shared)

You will use these factors in a set of simulation experiments to understand the packet loss performance of the router, and to evaluate the buffer management strategies. For simplicity, we will assume that all packets are the same size.

In particular, you should simulate a shared-memory packet-switching router with N inputs and N outputs. The router switch fabric is internally non-blocking, and operates synchronously, in a slotted fashion. That is, in one time step, the router does all of the following actions, in the order described.

• First, the router scans in numerical order all of the N output ports, to see which ports have packets queued and waiting to be transmitted. For each non-empty queue found, the router removes the frontmost packet from the queue, transmits the packet onto the corresponding output link, and then updates the queue (e.g., in complete partitioning, this means moving any waiting packets at that output port forward, making room for an additional arrival at the end of the queue; in complete sharing, it means freeing a buffer, and keeping track of the new head of the queue).
• Second, the router scans in numerical order all of the N input ports to see which ports have an arriving packet (at most one packet per port in each time slot). For each arriving packet, the router determines the desired output port for the packet, and transfers the packet to the corresponding output port, queuing it for transmission (if buffer space permits).
• Finally, the router updates its statistics about incoming packets received, outgoing packets transmitted, and packets lost due to buffer overflow.

The foregoing loop operates repeatedly for successive time slots, until the end of the simulation.

You will use your simulation to study the relationship between the probability p of packet loss (due to buffer overflow) and the number of buffers b per output port, as a function of offered load L. In the complete sharing approach, this implies an aggregate shared pool of B = N b buffers. Make sure that you can vary the number of buffers b from 1 to 20 per output port. Plan to run your simulation long enough (e.g., 100,000 time slots) to obtain statistically meaningful simulation results. However, you do not need to worry about startup effects, run length, multiple replications, batch means, or confidence intervals.

Test your simulation for four values of N, namely 2, 4, 8, and 16. Assume that the input traffic to the router is Bernoulli, with an average utilization of L on each input port, with L ranging from 0.5 to 1.0, in steps of 0.1. Bernoulli arrivals on a given input port means that the probability of a packet arriving in a given slot is always L. When L = 0.5, this is like a coin flip: 'Heads' means there is a packet; 'Tails' means there is no packet. For larger values of L, it is like flipping a biased coin (i.e., 'Heads' is more likely than 'Tails'). All time slots are independent (i.e., new coin flips). Assume also that packet arrivals on each input port are independent from other input ports. Finally, assume that an arriving packet is equally likely to choose any of the N possible output ports (uniformly at random, independently).

The specific steps required to complete the assignment are:

• (10 marks) Write a simple discrete-event simulation program (8 marks) to model the buffer management in a packet-switching router. You may write this program in either C or C++. (My solution required less than 200 lines of code.) Include a brief user manual (2 marks) describing how to compile, configure, and run your simulation program.
• (4 marks) Set N = 4 and b = 5. Conduct a one-factor simulation experiment by varying the offered load L to study its effect on the packet loss ratio p. Do this first for the complete partitioning strategy, and then for the complete sharing strategy. Plot your results using a graph, with the two lines (one for each of the two buffer management strategies) on the same graph (and clearly labeled). Include the graph in the materials that you submit, along with a short paragraph (1-3 sentences) containing your observations about the results obtained.
• (4 marks) Conduct a two-factor simulation experiment to study the impacts of offered load L and router size N on the packet loss ratio for the complete partitioning strategy when b = 5. Use N = 2, 4, 8, and 16. Plot your results using a graph. Include the graph in the materials you submit, along with a short paragraph containing your observations about the results obtained. Briefly explain your results, as best you can.
• (4 marks) Conduct a two-factor simulation experiment to study the impacts of offered load L and router size N on the packet loss ratio for the complete sharing strategy when b = 5. Use N = 2, 4, 8, and 16. Plot your results using a graph. Include the graph in the materials you submit, along with a short paragraph containing your observations about the results obtained. Briefly explain your results, as best you can.
• (2 marks) Write a brief summary (maximum one page) of your recommendation to your manager regarding the routers from vendor A and vendor B. Which one should you buy? Make sure to indicate which of the two (complete partitioning or complete sharing) exhibits better packet loss performance, and why.

When you are finished, please email your solution in electronic form to your TA. Your submission should include the source code for your router simulation, and the requested set of results from your simulation experiments. The proposed grading scheme for the assignment is as indicated above. (Up to 4 bonus marks are available if you also conduct simulation experiments to evaluate the performance of these two router buffer management strategies under a scenario with non-uniform traffic destinations.)

TIPS: If you have never written a simulation program before, you might want to take a look at this simple poker.c simulation example, which was discussed in your March 13 tutorial sessions. It is a time-driven simulation, operating in discrete-time rounds, much like you need for this assignment. For a more elaborate discrete-event simulation, operating in continuous-time, check out this barber.c simulation example. This one is probably more complicated than you will need, but instructive nonetheless.