Opened 6 months ago

Closed 4 months ago

#29298 closed defect (fixed)

Explicitly specify histogram bin endpoints/widths

Reported by: mikeperry Owned by:
Priority: Very High Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: wtf-pad 041-proposed network-team-roadmap-2019-Q1Q2
Cc: asn Actual Points: 6
Parent ID: #28631 Points: 5
Reviewer: mikeperry Sponsor: Sponsor2

Description

George has convinced me that we should explicitly specify the bin labels of our histograms rather than rely on a formula and lots of special cases for short histogram lengths.

The most straight-forward thing is to let researchers specify a list of bin labels.. It might be more compact to encode if this list is a list of widths, but that may just be an encoding decision for the consensus. We should probably choose simplest possible representation here.

Child Tickets

Change History (17)

comment:1 Changed 5 months ago by asn

Parent ID: #28631

comment:2 Changed 5 months ago by gaba

Keywords: network-team-roadmap-2019-Q1Q2 added

comment:3 Changed 5 months ago by asn

Also related to #29122 which revealed the underlying issue.

comment:4 Changed 5 months ago by asn

Spec branch pushed in https://github.com/asn-d6/torspec/tree/bug29298 .

Mike do you like it?

comment:5 in reply to:  4 ; Changed 5 months ago by mikeperry

Replying to asn:

Spec branch pushed in https://github.com/asn-d6/torspec/tree/bug29298 .

Mike do you like it?

We should provide arrays with the example: https://github.com/mikeperry-tor/torspec/tree/bug29298

There's also the question as to if the infinity bin should be forced to have Infinity-1 as its left endpoint, or if we should allow this discontinuity as we have there..

comment:6 in reply to:  5 Changed 5 months ago by asn

Replying to mikeperry:

Replying to asn:

Spec branch pushed in https://github.com/asn-d6/torspec/tree/bug29298 .

Mike do you like it?

We should provide arrays with the example: https://github.com/mikeperry-tor/torspec/tree/bug29298

Nice! That looks real good!

There's also the question as to if the infinity bin should be forced to have Infinity-1 as its left endpoint, or if we should allow this discontinuity as we have there..

Yep, that would be an alternative. Let's consider it:

Alternative #1:

  Tokens    +
         10 |    +----+
          9 |    |    |           +---------+
          8 |    |    |           |         |
          7 |    |    |     +-----+         |
          6 +----+ Bin+-----+     |         +----+---------------+
          5 |    | #1 |     |     |         |    |               |
            | Bin|    | Bin | Bin |  Bin #4 |Bin |    Bin #6     |
            | #0 |    | #2  | #3  |         |#5  | (infinity bin)|
            |    |    |     |     |         |    |               |
            |    |    |     |     |         |    |               |
          0 +----+----+-----+-----+---------+----+---------------+
            0   100  200   350   500      1000   ∞               ∞     microseconds

Positives:

  • The final bin is now well defined since it makes sense to always return infinite delay.

Negatives:

  • There will need to be special rules for the next-to-last bin which is now from 1000 -> ∞, so we still don't get a proper object.
  • We are now adding another bin to the histogram that was not explicitly added by the histogram designer, which might be confusing.

Personally, I prefered the approach that is in the spec above because it's kinda easier to grasp and explain.

Another alternative, would be to leave all the edges of the histogram to be specified by the histogram designer, including the rightmost one. If the designer wanted an infinity bin they could add an infinity value to that edge to make one. I think that would also be a clean solution, but it would be a bit of a hassle to apply the special rules (e.g. token removal, etc.) of the infinity bin in this solution since the designer would basically have to decide whether they want the rules or not, and that might complicate the "API".

For now, I'd go with the one we specified in the spec above, see how that works out, and potentially iterate on the future as researchers use it.

Version 0, edited 5 months ago by asn (next)

comment:7 Changed 5 months ago by asn

Status: newneeds_review

Hey Mike, please check my branch bug29298: https://github.com/torproject/tor/pull/705

It implements the above! I still consider it a draft because I want to take a second good look to make sure I'm not screwing something up.

But I think it looks pretty OK.

Also, Mike, I remember you saying something about being able to simplify circpad_machine_setup_tokens() through this change but it was not obvious to me how. Let me know if you can help me here.

I also have another branch that does some validation of histograms before registering them, but I decided to not fold it in to make it as light as possible.

Last edited 5 months ago by asn (previous) (diff)

comment:8 Changed 5 months ago by dgoulet

Milestone: Tor: 0.4.1.x-final
Reviewer: mikeperry

comment:9 Changed 5 months ago by mikeperry

Status: needs_reviewneeds_revision

asn: this looks great! I have some minor comment change requests in the review on the PR. Code looks really good though. Such improved much simplified!

comment:10 Changed 5 months ago by asn

Status: needs_revisionneeds_review

Thanks for review. I pushed fixups which hope work for you.

Check them out, and if they work for you, I will squash the whole thing into the final thing to be merged.

comment:11 Changed 5 months ago by mikeperry

Priority: MediumVery High

comment:12 Changed 5 months ago by mikeperry

Status: needs_reviewmerge_ready

Looks great now!

comment:13 Changed 5 months ago by nickm

Status: merge_readyneeds_revision

I've added a couple of comments on the PR. Most will probably not be things that need to change.

comment:14 Changed 4 months ago by asn

Status: needs_revisionmerge_ready

Pushed fixups for the review. Let me know if you want anything else, or you want me to open tickets for something.

comment:15 Changed 4 months ago by nickm

LGTM; merging! Please set actual points and take whatever action is appropriate with the child ticket.

comment:16 Changed 4 months ago by asn

Actual Points: 6

Child ticket #29527 needs to be merged after this get merged, so perhaps we can close this one after #29527 gets merged as well? Or I can remove the child ticket?

comment:17 Changed 4 months ago by nickm

Resolution: fixed
Status: merge_readyclosed

Squashed and merged the child.

Note: See TracTickets for help on using tickets.