Simulate Multiple Virtual Timers with one Physical Timer

Question

I am trying to implement a Selective Repeat Protocol using C for an networking assignment but am stumped at how to simulate the timer for each individual packets. I only have access to a single timer and can only call the functions as described below.

/* start timer at A or B (int), increment in time*/
extern void starttimer(int, double);       

/* stop timer at A or B (int) */
extern void stoptimer(int);             

Kurose and Ross mentioned in their networking textbook that

A single hardware timer can be used to mimic the operation of multiple logical timers [Varghese 1997].

And I found the following hint for a similar assignment

You can simulate multiple virtual timers using a single physical timer. The basic idea is that you keep a chain of virtual timers ordered in their expiration time and the physical timer will go off at the first virtual timer expiration.

However, I do not have access to any time variables other than RTT as the emulator is on another layer of abstraction. How can I implement the timer for individual packets in this case?

Answer 1

You can do that in the same way it is implemented at Kernel level. You need to have a linked list of "timers" where each timer has a timeout relative to the preceding one. It would be something like: Timer1: 500 ms from t0, Timer2: 400 ms from t0, Timer3 1000 ms from t0.

Then you will have a linked list in which each element has the timeout relative to the previous one, like this:

HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)

Every element contains minimum: timerID, relative timeout, absolute init time (timestamp from epoch). You can add a callback pointer per timer.

You use your only timer and set the timeout to the relative timeout of the first element in the list: 400ms (Timer2)

After timeout you will remove first element, probably execute a callback related to Timer2, ideally this callback is executed with another worker thread. Then you set the new timeout at the relative timeout of the next element, Timer1: 100ms.

Now, when you need to create a new timer, say at 3,000 ms, after 300 ms from t0, you need to insert it in the proper position navigating the linked list of timers. The relative timeout in Timer4 will be 2,300. This is calculated with (Timer2.RelativeTimeout - (now - Timer2.AbsoluteTimeout)) and going through the linked list to find the corresponding position, adding relative timeouts of each previous element. Your linked list will become:

HEAD->Timer2(400ms)->Timer1(100ms)->Timer3(500ms)->Timer4(2,300)

In this way you implement many logical timers with one physical timer. Your timer create and find time will be O(n) but you can add various improvements for insertion performance. The most important is that timers timeout handling and update is O(1). Delete complexity will be O(n) for finding the timer and O(1) for delete.

You have to take care of possible race conditions between the thread controlling the timer and a thread inserting or deleting a timer. One way to implement this timer in user space is with condition variables and wait timeout.