Corporate and Professional Publishing Group

An Engineering Approach to Computer Networking

by S. Keshav

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.

Switching and Scheduling


In this assignment, you will start with a working simulation of packet routing and enhance it in two ways. First, you should change the scheduling from first-come-first-served to round-robin. Then, you should change the buffer management so that the buffer is not infinitely large, and packet losses can occur.

How to do the assignment

The simulation consists of three sets of nodes: sources, routers, and receivers. The sources, called sender1, sender2, sender3 and sender4 send four packets each to a router, which forwards them to another router, and from there to one of four receivers. Sender1 sends all four packets to receiver 7, sender 2 sends one packet to receiver 7, and the rest to receiver 8, sender 3 sends one packet to receiver 7, and the rest to receiver 9, sender 4 sends one packet to receiver 7, and the rest to receiver 10. Thus, receiver 7 gets seven packets, and the others three each.

The router implements first-come-first-served (FCFS) scheduling. The start times of the senders are chosen so that the receiver 7 gets packets from sources in the order 1,1,1,1,4,3,2. Your first task is to implement round-robin scheduling. You can do so by modifying the functions t_enqueue and t_dequeue in the file ecn_router.c in any way you want. You may choose to use some of the data structures in the file routers/router.h and some of the algorithms in the file routers/queues.c, or can define your own. In any case, the resulting series of packets at node 7 should be 1,4,3,2,1,1,1. (due to randomness in the simulator, the first four packets might be reordered--the important point is that the second packet from 1 arrives only after one packet from each of the other sources).

Note that the choice of scheduling disciplines at a router is made in the input file, routing.l, by setting the variable sch_policy and this is available to a node in the variable policy[node]. Use policy 1 for FCFS and 2 for round robin.

Your second task is to put in buffer limits into the router. At the moment, the router does not check for buffer size when it enqueues packets. You should use the global variable op_qsize, which is set from the input file routing.l to determine the size of the shared buffer. If a packet arrives to the buffer when it is full, the packet should be dropped in the function t_enqueue. To check your code, set op_qsize to 2500 bytes (enough for five packets). This will cause several packets to be lost in the router, depending on their arrival order, and will be reflected in the printouts from receiver 7, which should read, with round robin service, something like 1,4,3,1,1,1 (the two packets from 1 will be separated by two packets from other sources, not necessarily 4 and 3). (It might help to think through why these are the packets that show up at 7 before you do the assignment.)

To help you debug the assignment, the variables START_R_DEBUG and END_R_DEBUG can be set to the start and end times when you want the router to print detailed arrival and departure information. These are set in the file kernel/switches.c, which you should modify after breaking the symbolic link. By default, START_R_DEBUG and END_R_DEBUG are chosen to print out information for all the packets. You can turn them off when your assignment works.


We will grade your submission by noting the series of arrivals at receiver 7. If your have modified the simulator correctly, you should receive packets in the order specified.