Skip to content

Redesigning the server API

Jump to bottom
Christian Huitema edited this page Mar 5, 2018 · 3 revisions

If you look at the server implementation in picoquicdemo.c, you will see a fairly simple structure:

  1. Initialize the server,

  2. Until the server stops, run a loop:

  • Find the next wake up time, which should be the min of the wake up time of all connections;

  • Get all the incoming packets until that time;

  • Process potential transmissions from all the connections for which the wake time is lower than the current time.

  1. Release resources and memory.

The problem is with the last bullet. To list all relevant the connections, the code needs to maintain a list of connections, ordered by increasing wake time. The wake time changes when something changes the state of a connection. It could be a user interaction such as posting a message, the arrival of a message from the peer, or the sending of a message. For example, if a message is posted, the wake time will become the time to send the next message.The "potential transmissions" list was previously provided with two APIs, "picoquic_get_first_cnx" and "picoquic_get_next_cnx". The problem found in issue #83 is that the "get_next" is defined as "get next connection with smallest wake time", and the results changes constantly as the list gets updated. So we need something to change.

We now have two different API:

  • picoquic_get_first_cnx and picoquic_get_next_cnx can be used to enumerate connections in the quic context. The connections are listed in the reverse order from their creation, and are removed from the list if they are deleted through a call to picoquic_delete_cnx.

  • The new API, picoquic_get_earliest_cnx_to_wake(picoquic_quic_t* quic, uint64_t max_wake_time), returns a pointer to the connection with the earliest wake up time, i.e. the "most urgent connection". It will return NULL if the max_wake_time is specified and there are no connections ready before that time.

The list of urgent connections needs to be reordered frequently. The current implementation is simplistic -- a simple double linked list, with insertion by just scanning the list until the right position is found. The cost scales as O(N) with the number of connections, which is OK for the current test patterns but will have to change as we start considering production services. I can think of two possible solutions: a red-black tree ordered by wake up time, for which updates would be O(log N), or maybe a list of "time buckets", for which updates will be O(1) but the time precision subject to some quantization.

Clone this wiki locally