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.

Sign up for GitHub

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

Jump to bottom

New Path Registration and Path Lookup strategy for Down Segments #3731

Closed
shitz opened this issue Apr 28, 2020 · 1 comment
Closed

New Path Registration and Path Lookup strategy for Down Segments #3731

shitz opened this issue Apr 28, 2020 · 1 comment
Labels
design doc

Comments

@shitz
Copy link
Contributor

shitz commented Apr 28, 2020

Currently, non-core ASes register their down-segments with a single core AS only (not specified which). Core ASes run a syncing protocol to exchange registered down-segments amongst them. The property intended to be achieved is: each core AS of an ISD has all down-segments for that ISD. The advantage of this property is that during path lookup, any requester, ISD-local and ISD-remote, can ask any core AS of an ISD about any down-segment. However, this approach also has some short-comings:

  1. The segment syncing protocol is highly complex. In essence, it needs to implement a distributed consistent DB for down-segments across multiple organization.
  2. It's unclear how useful it is for a core AS to return down-segments that originate in a different core-AS, since it cannot be combined with core-segments that terminate in the replying core AS.

We thus propose a change to path registration (for down-segments) and path lookup:

  1. During registration, a non-core AS only registers down-segments with the core AS they originate from.
  2. There is no segment synchronization protocol between core ASes. Each core AS only has the down-segments for which it received an explicit registration.
  3. During path lookup, a requester asks each core AS for which it wants to include down-segments to a non-core AS. By default, a requester asks all core ASes of an ISD.

The trade-offs are the following:

  • We get rid of the highly complex and brittle down-segment synchronization (big win)
  • The answer of each core AS is guaranteed to be useful, since its existence implies also the existence of a core-segment that can be used to connect with the returned down-segments.
  • Path lookup gets slightly more complex, since it now needs to go to multiple core ASes.

We are convinced that the advantages far outweigh the disadvantages.
This was referenced Apr 29, 2020
Closed
Closed
Closed
Merged
scrye added a commit that referenced this issue Apr 29, 2020
@scrye
remove segment synchronization from PS docs (#3736)
2b13e1b 
The down-segment synchronization mechanism in the core is
deprecated (see #3731).
@matzf matzf mentioned this issue May 13, 2020
Merged
This was referenced Jun 17, 2020
Merged
Merged
lukedirtwalker pushed a commit that referenced this issue Jul 14, 2020
@matzf
cs/sd: implement new path lookup strategy (#3792)
c65501c 
Remove segment synchronization and adapt the path lookup strategy accordingly

1. During registration, a non-core AS only registers down-segments with the core AS they originate from.
2. Each core AS only has the down-segments for which it received an explicit registration.
3. During path lookup, a requester asks each core AS for which it wants to include down-segments to a non-core AS. By default, a requester asks all core ASes of an ISD.

Furthemore, the down-segment requests in remote ISDs where previously handled by a core AS of the local ISD, forwarding and caching the request. This intermediary has now been removed, down-segment requests are sent directly to core AS in the remote ISD.

There are two distinct segment request handlers:
* authoritative: returns core- and down-segments registered with this core AS -- this is a trivial DB lookup
* forwarder: handles requests from hosts in the local AS (TCP only). This forwards and caches core- and down-segment requests to the authoritative core AS (i.e. the AS at the start of the segment). Up-segment requests are always answered from DB.
This handler expands wildcard requests to a request to each authoritative core AS. In order to forward requests to an authoritative core AS, an additional (recursive) request for the corresponding core segments is made.

Further documentation will be added in #3747.

#### Notes

* a single path request can now entail multiple down-segment requests (one for each core AS). The `segfetcher.RequestSet` data structure did not allow for this. Thus it was replaced with a simpler flat list of typed segment requests. Analogously, `segfetcher.Segments` is now a flat list of typed segments instead of one separate list of segments per type.
* the `segfetcher.Resolver` can now be dumber because it no longer needs to keep track of the order in which segments of different can be fetched. The state machine of the requests in the `Fetcher` and `Resolver` is now trivial, segments are either loaded from the DB or else fetched. This is possible because of the aforementioned "recursive" use of the `segfetcher.Fetcher` and (thus the `segfetcher.Resolver`) for a core-segment lookup when forwarding down-segment requests.
* the `segfetcher` module is now much dumber/simpler overall. This is reflected with a somewhat reduced set of test cases for the `segfetcher.Resolver`
* the `segfetcher.Splitter` which splits a path request into segment requests is no longer part of the `Fetcher`, but only of the `Pather` (one abstraction level higher). This allows to re-use the simplifed `Fetcher` for the implementation of the forwarding segment request handler.
* The lookup strategy employed by sciond is to make (up to three) independent, concurrent wildcard requests (by means of the `segfetcher.Pather` mentioned above). Assuming everything is cached in the local path server, this finds all paths with minimal latency. Other strategies, such as a depth-first-search that could perhaps find a single path more quickly could be implemented without further changes to the protocol.

Contributes to #3731
lukedirtwalker pushed a commit that referenced this issue Jul 21, 2020
@matzf
doc: new path lookup strategy (#3747)
23448ee 
Documentation for #3792
Contributes to #3731
@lukedirtwalker
Copy link
Collaborator

This is documented in #3747 and implemented in #3792

@mlegner mlegner mentioned this issue Jan 8, 2021
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
design doc
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@lukedirtwalker @shitz