search

private-octopus / picoquic

Minimal implementation of the QUIC protocol
MIT License
523 stars 153 forks source link

HyStart implementation Linux vs. picoquic #1694

Open joergdeutschmann-i7 opened 1 month ago

joergdeutschmann-i7 commented 1 month ago

We just compared the Linux and picoquic HyStart implementation. https://github.com/torvalds/linux/blob/ea5f6ad9ad9645733b72ab53a98e719b460d36a6/net/ipv4/tcp_cubic.c#L427-L445 https://github.com/private-octopus/picoquic/blob/c306ab45c1c6ae528e2877d8d69e98e5405b832a/picoquic/cc_common.c#L138 We wondered to which extend the picoquic implementation is aligned with the Linux code.

Two specific questions:

1) https://github.com/private-octopus/picoquic/blob/c306ab45c1c6ae528e2877d8d69e98e5405b832a/picoquic/cc_common.c#L150-L151 Why is rtt_track->rtt_filtered_min compared/set to rtt_track->sample_max and not rtt_track->sample_min?

2) In Linux, the delay threshold is ca->delay_min >> 3 while in picoquic there is delta_max = rtt_track->rtt_filtered_min / 4. We wondered why these dividers are different.

PS: Sorry for posting three issues in a row :-)

huitema commented 1 month ago

No need to be sorry for posting issues!

About the 'filtered min'. The idea there is to remove the delay jitter common in wireless links, see https://www.privateoctopus.com/2019/11/11/implementing-cubic-congestion-control-in-quic/. So instead of comparing max to the "recent max", it is compared to the "recent min", trying to minimize the effect of jitter.

The threshold is a bit arbitrary. Neither 1/4th or 1/8th is based on science. Too low and you get false positives and exit too early, too high and you wait too long and cause queue overflow. I guess what is really needed is to implement Hystart++.

huitema commented 1 month ago

I have been thinking about this "hystart++" problem for a while. Of course, the first step would be to implement RFC 9406. But if the goal is "proceed safely and find the limit", there may be a bit more research to do. My main concern is that when the node probes for 25% larger window, it will only see the results after 2 RTT, by which time another 25% increase will have been started. During that second RTT, we might get a window 50% larger than ideal. That will probably not cause packet losses if the buffers are ready to absorb at least 1 BDP, but it will be creating queues. Maybe we could lift some ideas from BBR and prevent that.

hfstco commented 3 weeks ago

I have been thinking about this "hystart++" problem for a while. Of course, the first step would be to implement RFC 9406.

I already have implemented RFC 9406 in one of my branches. (https://github.com/hfstco/picoquic/tree/hystart%2B%2B) I want to compare HyStart and HyStart++ for high BDP connections. But I'm a bit busy at the moment. So there is no time to finish, refactor and test it right now. (Currently only works for cubic and newreno.) I might be able to finish it in the next few weeks.