Skip to content

Fix fifo qdisc#3489

Merged
robgjansen merged 2 commits intoshadow:mainfrom
robgjansen:fix-fifo-qdisc
Jan 12, 2025
Merged

Fix fifo qdisc#3489
robgjansen merged 2 commits intoshadow:mainfrom
robgjansen:fix-fifo-qdisc

Conversation

@robgjansen
Copy link
Copy Markdown
Member

Our fifo qdisc violates the assumption that a queued item's priority does not change while the item is enqueued. This allows a socket that had only bad priority packets when it was initially pushed into the queue to move up in priority when it suddenly has new packets with better priority. This case can happen often in the legacy TCP stack because it assigns priority=0 to control packets (ACKS) without data. This means we can be more responsive to TCP controls.

This PR does two things:

  1. Fixes the fifo qdisc so that it always produces a non-equal sort order over sockets. This is done by tracking the push order of the sockets and using the push order to break equality ties.
  2. Tracks the socket priority that existed at push time to enable us to show the performance difference when sorting based on that priority vs the priorities that are recomputed every time the priority queue rebalances and calls the compare function on a socket.

If we only apply the first commit, the performance should be identical to nightly. If we apply both commits, the performance should be identical to #3480.

@robgjansen robgjansen self-assigned this Jan 10, 2025
@github-actions github-actions bot added Component: Testing Unit and integration tests and frameworks Component: Main Composing the core Shadow executable labels Jan 10, 2025
@robgjansen
Copy link
Copy Markdown
Member Author

The first commit 3d73420 keeps the current prioritization but fixes the equality case. We can see in the TGen benchmark that the TGen performance is still mostly the same as the nightly before the change.

time_to_last_byte_recv_1048576_cdf

The second commit 10db06a changes the prioritization so that we do not modify the socket priority after it has already been pushed into the queue, meaning that the priority is set at the time it enters the queue and stays static until the socket is dequeued. We can see in the TGen benchmark that the TGen performance gets slightly worse because we are no longer able to move the socket ahead in priority when it needs to send control packets (ACKS) in response to incoming packets. That makes TCP slightly less responsive. This performance matches the Rust impl in #3480.

time_to_last_byte_recv_1048576_cdf

@robgjansen
Copy link
Copy Markdown
Member Author

@stevenengler do we want to merge one or both of these commits before we merge #3480? I think it would be good to have especially 10db06a in the git history since that is the minimal change that is responsible for the performance change, so I think I would lean toward merging this before #3480, even though we're basically going to remove the code in #3480 anyway.

@robgjansen robgjansen marked this pull request as ready for review January 11, 2025 01:25
Copy link
Copy Markdown
Contributor

@stevenengler stevenengler left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice find! I'm glad there's a good explanation for the difference in graphs.

This allows a socket that had only bad priority packets when it was initially pushed into the queue to move up in priority when it suddenly has new packets with better priority.

Ah I didn't realize (or forgot) that this is what the C version did. I'm not sure which behaviour we want, but I think the new one is more realistic?

@stevenengler do we want to merge one or both of these commits before we merge #3480?

I agree, I think it's good to merge this first.

@robgjansen
Copy link
Copy Markdown
Member Author

Ah I didn't realize (or forgot) that this is what the C version did. I'm not sure which behaviour we want, but I think the new one is more realistic?

I think the "old" design is "better" in the sense that it produces a result that is likely closer to a true pfifo_fast qdisc that linux uses. The reason is that priority band 0 packets should always be sent ahead of the others, and the "old" design made that possible, but that is no longer possible after merging this PR. However, I think we should merge anyway, assuming that we'll get a much more accurate pfifo_fast design when we implement #3490.

@robgjansen robgjansen merged commit 6887d3d into shadow:main Jan 12, 2025
@robgjansen robgjansen deleted the fix-fifo-qdisc branch January 12, 2025 22:27
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Component: Main Composing the core Shadow executable Component: Testing Unit and integration tests and frameworks

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants