Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider implementing something like Tuple Space Search for ternary table lookups #1260

Open
jafingerhut opened this issue Jul 13, 2024 · 0 comments

Comments

@jafingerhut
Copy link
Contributor

jafingerhut commented Jul 13, 2024

The current implementation of lookups in ternary tables is to:

  • do an exact match lookup in a cache of full exact match lookup keys that have been searched before
  • if there is a miss in that cache, do a linear scan through all ternary entries, I believe in decreasing priority order, so that you can stop at the first matching entry, if there is one.

However, if you do a test like this:

  • add N entries to a ternary table
  • send N packets to the table, one that should match each of the entries

then it takes O(N^2) time to do that, because every one of the packets misses in the cache.

There are people from Keysight trying to use BMv2 for the DASH project [1] that are trying exactly this for large N, e.g. a few million, but it is unacceptably slow.

They might also be trying this for tables with some ternary keys and some range keys, too. I am not sure.

In either case, using an algorithm like Tuple Space Search would significantly speed up the process of lookups, in the quite common case where there are only relatively few distinct masks used for entries.

If anyone is interested in working on this, I'm happy to give advice.

[1] https://github.com/sonic-net/DASH
[2] Research paper on Tuple Space Search algorithm: https://dl.acm.org/doi/10.1145/316194.316216

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant