1 Your Task

1. Download the skeleton code here (last updated 5 October 2024 3:30pm).

   This code includes a setup for a simulator (the same as for the reliable assignment), which is configured to have two connections, called c1 and c2, between the same two hosts. Each connection sends packets from a sender to receiver on a shared link. Unlike the reliable assignment, there is no flow or congestion control; instead packets are generated at a rate specified when running the simulation.

   The simulation allows for interchangeable buffer implementations on the simulated link. The default is a simple drop-tail, first-in-first-out scheme implemented in the DropTailBuffer in buffer.py.

   See the instructions under the heading running the template code regarding how to use the template code.

2. Add a new buffer implementation in buffer.py called PriorityQueueBuffer

   In this implementation, implement a strict priority scheme where packets from connection c1 are serviced before packets from connection c2. You can identify which connection a packet is from using packet.label which will be c1 for connection c1 and c2 for connection c2.

   When the queue capacity is exceeded, your implementation must discard the newest packet from connection c2, if possible; otherwise, it should discard the newest packet from connection c1.

   If you are successsful:

   • no packet should be received out-of-order by connection c1 or c2

   • as long as the rate of c1 is less than the link bandwidth, it should achieve its full bandwidth (in terms of messages received/time unit) and have a latency close to the link delay.

     This should occur:

     • regardless of the rate of c2, even if the rate of c2 substantially exceeds the available bandwidth
     • even if the rate of c1 is very small

   • as long as the rate of c1 is substantially less than the link bandwidth, c2 should be able to use the remainder of the link bandwidth

3. Add a new buffer implementation in buffer.py called WeightedFairQueuingBuffer.

   In this implementation, implement weighted fair queuing, where packets from connection c1 get twice the bandwidth as packets from connection c2.

   You can identify which connection a packet is from using packet.label which will be c1 for connection c1 and c2 for connection c2.

   Since our simulated packets have variable size, you will need to retrieve the packet sizes using packet.size.

   When a packet is inserted in the buffer and the buffer has reached its capacity, you should

   • drop the incoming packet if its scheduled transmission time (as computed using the virtual time method discussed in lecture) would be higher than any packet currently in the buffer;
   • drop the packet with the highest scheduled tranmission time currently in the buffer otherwise.

   If you are successful:

   • no packet should be received out-of-order by connection c1 or c2
   • if c1’s rate is more than 67% of the capacity of the link and c2’s rate is more than 34% of the capacity of the link, then c1 should achieve around 66% of the capacity of the link and c2 around 33% of the capacity of the link (in terms of messages/time unit)
   • if c1’s rate is less than 66% of the capacity of the link, then:
     • c1’s latency should be close to the link delay, and
     • c2 should recieve the remainder of the bandwidth of the link (if its rate is high enough)

4. Submit your modified buffer.py.

2 Running the template code

1. When you run main.py, it will run the simulation with default settings and output information about what happened and the configuration:

   forward link: 1000.0 size units/sec; link delay 1.0 +/- 0.0; 60-entry buffer.DropTailBuffer
   c1: generated 5.0 packets/sec with average size 100
   c1: received 2302 packets (126679 total size) in 5000.2 (25.3 size units/time unit; 0.5 messages/time unit)
   c1: latency: mean 1.00  +/- sd 0.01
   c1: 22851 messages skipped, 9 not received at end, 0 corrupt or received out-of-order
   c2: generated 5.0 packets/sec with average size 100
   c2: received 2236 packets (123110 total size) in 5000.2 (24.6 size units/time unit; 0.4 messages/time unit)
   c2: latency: mean 1.00  +/- sd 0.01
   c2: 22513 messages skipped, 26 not received at end, 0 corrupt or received out-of-order

   In this default configuration, the rate of messages being sent seem like they should exactly fill the link. But, there is randomness in the interval between packets and the exact size of packets. This means that sometimes packets cluster up enough to cause some to be dropped and sometimes there are periods when the link is underutilized.

2. Unlike the reliable assignment, the length of the simulation is controlled by the --time-limit parameter, by default this is 5000; you can adjust it to something shorter like --time-limit=100 if you want a faster simulation.

3. You can edit the other simulation parameters with the various options listed with python3 main.py --help.

4. The two connections are controlled by two parameters:

   • --cX-rate=RATE: the mean number of packets to send per unit time. The actual time between packets will be determined using a exponential distribution.
   • --cX-size=SIZE: the mean size of packets (in arbitrary size units); the actual size will vary from 50% and 150% of SIZE, chosen uniformly for each packet. The minimum supported size is 40.

5. You should notice that, with the default DropTailBuffer strategy, increasing the rate for one connection while leaving the other the same will cause both connections to drop a larger portion of packets (messages skipped), and will result in the higher sending rate connnection achieving a higher effective bandwidth.

   If these connections used TCP-style congestion control, then most likely both settle on approximately the same bandwidth. (The simulation should support plugging in your reliable part 3 implementation using the --sender-class and --receiver-class options, but that is not part of this assignment.)

6. You can use the --buffer-class=... option to change to your own buffers in buffer.py.

3 Hints/Notes

1. Unrealistically, our supplied DropTailBuffer and what we require you to implement have a capacity measured in packets, not size units. So you do not need to take into account packet size when deciding whether to drop packets.

2. We don’t have a particular compute-time requirements, so it’s allowed for your implementation not to use optimal data structures.

3. One strategy for storing the queue for the priority queue and the weighted fair queuing part is to keep two separate sub-queues for each of the two classes. Another would be keep to one sorted list.

4. If you want a list you can efficiently add/remove from both ends, the deque class provided by Python’s collections library is useful.

5. If you want an implementation of a heap (a data structure that can efficiently remove the minimum item), you can use Python’s heapq. It, unfortunately, is not also efficient for removing the maximum item (which you might want for drops). The way Python’s heap is implemented, however, you can inefficiently remove the maximum item by sorting it and then truncating away the last item.

6. To control how Python sorts values by default, you can define a custom < operator or just represent your values as careful ordered tuples or similar. See the heading Comparable custom types in Python for some options to do this.

   For using heapq, this seems to be the only way to control the sort order. For Python’s sorting functions, you can also change the sort order with the key or cmp arguments.

7. I wish I could point to a convenient balanced binary tree in Python standard library (that could provide efficient removal of both minimum and maximum values), but I do not believe there is one.

3.1 Common issues computing virtual times

1. In weighted fair queuing, we often compute a packet’s virtual time based on a previous packet’s virtual time. A common mistake is to use the virtual time of packet which has been dropped from the queue for this rather than finding the correct packet to use in the queue.

3.2 Comparable custom types in Python

1. Python tuples implement the < operator automatically, so for example:

   return (a, b, c) < (d, e, f)

   is basically equivalent to:

   if a < d:
       return True
   elif a == d and b < e:
       return True
   elif a == d and b == e and c < f:
       return True
   else:
       return False

   Note that this triggers an error when it’s not possible to compare some the values used. To help make this strategy possible, Packet objects in the skeleton code implement a < operator that choses an arbitrary order.

2. You can make a custom type in Python that has a custom < operation using something like:

   class MyType(object):
       def __init__(self, field1, field2, non_compared_field):
           self.field1 = field1
           self.field2 = field2
           self.non_compared_field = non_compared_field
   
       def __lt__(self, other):
           if self.field1 < other.field1:
               return True
           elif self.field1 == other.field1 and self.field2 < other.field2:
               return True
           else:
               return False

   Then you can create instances of MyType using something like variable = MyType(field1=10, field2=20, non_compared_field=30) and access the fields using variable.field1 and variable.field2 and variable.non_compared_field.

   Alternately, the standard dataclasses module can automate this process for you:

   from dataclasses import dataclass, field
   
   ...
   
   @dataclass(order=True)
   class MyType:
       field1 = field()
       field2 = field()
       non_compared_field = field(compare=False)