Opened 3 years ago

Closed 5 weeks ago

Last modified 5 weeks ago

#12541 closed enhancement (implemented)

Integrate KIST socket/circuit scheduling

Reported by: robgjansen Owned by: dgoulet
Priority: Medium Milestone: Tor: 0.3.2.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: performance, tcp, kist, scheduling, tor-relay, term-project-ideas, review-group-22, review-group-23
Cc: nikita Actual Points:
Parent ID: Points:
Reviewer: Sponsor:

Description

This ticket is a parent for tracking work needed to implement/test/simulate/integrate the new global scheduling and write-limiting techniques for handling kernel output. This is funded by Sponsor F.

The initial design is from Rob's USENIX Security 2014 paper entitled "Kernel-Informed Socket Transport", which will be available here:
http://www.robgjansen.com/publications/kist-sec2014.pdf
and the appendices here:
http://www.cs.umn.edu/tech_reports_upload/tr2014/14-012.pdf

Child Tickets

TicketTypeStatusOwnerSummary
#9262enhancementclosedandreaRefactor cell scheduling to consider all connections at once
#12889taskclosedrobgjansenSimulate global circuit scheduling from #9262
#12890enhancementclosedDesign and implement optimizations for socket write limits
#12891taskclosedSimulate KIST - global scheduling (#9262) and socket write limits (#12890)
#12892taskclosedRun KIST on some fast live relays, measure congestion
#17598enhancementclosedpastlyTrace cell queue times in Tor to measure Tor application "congestion"
#23163defectclosedWrong name for new tor config options

Attachments (6)

cmux-highwater.shadowtor.pdf.xz-part0 (2.4 MB) - added by robgjansen 3 years ago.
cmux-highwater.shadowtor.pdf.xz-part1 (2.1 MB) - added by robgjansen 3 years ago.
cmux-lowwater.shadowtor.pdf.xz-part0 (2.4 MB) - added by robgjansen 3 years ago.
cmux-lowwater.shadowtor.pdf.xz-part1 (2.1 MB) - added by robgjansen 3 years ago.
cmux-maxflush.shadowtor.pdf.xz-part0 (2.4 MB) - added by robgjansen 3 years ago.
cmux-maxflush.shadowtor.pdf.xz-part1 (2.0 MB) - added by robgjansen 3 years ago.

Change History (47)

comment:1 Changed 3 years ago by nikita

Cc: nikita added

comment:2 Changed 3 years ago by yawning

Cc: yawning added

comment:3 Changed 3 years ago by nickm

Keywords: tor-relay 026-triaged-1 added

comment:4 Changed 3 years ago by nickm

Milestone: Tor: 0.2.6.x-finalTor: 0.2.7.x-final

Timeframewise, I think this won't be ready by the January cutoff for 0.2.6. But if I'm wrong, we can merge it.

comment:5 Changed 3 years ago by robgjansen

Making serious progress on this will become my top priority after the Oakland deadline tomorrow. You can expect frequent updates from me starting then.

Changed 3 years ago by robgjansen

Changed 3 years ago by robgjansen

Changed 3 years ago by robgjansen

Changed 3 years ago by robgjansen

Changed 3 years ago by robgjansen

Changed 3 years ago by robgjansen

comment:6 Changed 3 years ago by robgjansen

Whoops, those files were supposed to be attached to #12889. Push the wrong button in trac and everything is set in stone...

comment:7 Changed 3 years ago by nickm

Status: newassigned

comment:8 Changed 3 years ago by nickm

Keywords: 027-triaged-1-out added

Marking triaged-out items from first round of 0.2.7 triage.

comment:9 Changed 3 years ago by nickm

Milestone: Tor: 0.2.7.x-finalTor: 0.2.???

Make all non-needs_review, non-needs_revision, 027-triaged-1-out items belong to 0.2.???

comment:10 Changed 21 months ago by nickm

Keywords: 6s194 added

comment:11 Changed 21 months ago by nickm

Keywords: term-project-ideas added; 6s194 removed

These tickets were tagged "6s194" as ideas for possible term projects for students in MIT subject 6.S194 spring 2016. I'm retagging with term-project-ideas, so that the students can use the 6s194 tag for tickets they're actually working on.

comment:12 Changed 11 months ago by teor

Milestone: Tor: 0.2.???Tor: 0.3.???

Milestone renamed

comment:13 Changed 10 months ago by nickm

Keywords: tor-03-unspecified-201612 added
Milestone: Tor: 0.3.???Tor: unspecified

Finally admitting that 0.3.??? was a euphemism for Tor: unspecified all along.

comment:14 Changed 5 months ago by nickm

Keywords: tor-03-unspecified-201612 removed

Remove an old triaging keyword.

comment:15 Changed 5 months ago by nickm

Keywords: 027-triaged-in added

comment:16 Changed 5 months ago by nickm

Keywords: 027-triaged-in removed

comment:17 Changed 5 months ago by nickm

Keywords: 027-triaged-1-out removed

comment:18 Changed 5 months ago by nickm

Keywords: 026-triaged-1 removed

comment:19 Changed 5 months ago by nickm

Status: assignednew

Change the status of all assigned/accepted Tor tickets with owner="" to "new".

comment:20 Changed 5 months ago by nickm

Keywords: kist added
Severity: Normal

comment:21 Changed 3 months ago by pastly

Milestone: Tor: unspecifiedTor: 0.3.2.x-final
Owner: set to pastly
Status: newassigned

comment:22 Changed 3 months ago by pastly

Cc: dgoulet added
Status: assignedneeds_review

See

Adding dgoulet who wants to review KIST.

The difference between -01 and -02 is just rebasing from master ~4w ago to master today.

comment:23 Changed 3 months ago by dgoulet

Cc: dgoulet removed
Reviewer: dgoulet

comment:25 Changed 2 months ago by nickm

Hi, pastly & dgoulet! I just skimmed over the merge request on oniongit and added a few comments and questions. It's not a thorough review; just a cursory inspection. I'm sure dgoulet will have more questions and comments when he's back from vacation.

comment:26 Changed 2 months ago by nickm

Keywords: review-group-22 added

comment:27 Changed 8 weeks ago by dgoulet

Status: needs_reviewneeds_revision

Just went over the whole thing. Many things to discuss! but overall, I'm very happy and optimistic about this change. It makes things so much easier to understand, nice interface and design imo.

We can either discuss on IRC if you want to go faster than the back and forth on Gitlab. I'm good either way but ping me (us) when you have replied. Thanks!

comment:28 Changed 7 weeks ago by dgoulet

Owner: changed from pastly to dgoulet
Status: needs_revisionaccepted

Progress addressing all the review in ticket12541_032_01.

It's missing few things so not ready for review.

comment:29 Changed 6 weeks ago by dgoulet

Reviewer: dgoulet
Status: acceptedneeds_review

Ok, I've gone through all the things, did some fixup on pastly branch, he reviewed it and everything got addressed (I hope!).

Time for more reviews.

Branch: ticket12541_032_01
https://oniongit.eu/dgoulet/tor/merge_requests/7

comment:30 Changed 6 weeks ago by nickm

Keywords: review-group-23 added

Put 0.3.2 needs_review and merge_ready tickets into review-group-23.

comment:31 Changed 6 weeks ago by pastly

sooo... did you change anything in the vanilla scheduler? It's impossible to tell with the diffs. Wasn't there a bug in there you fixed? (https://oniongit.eu/pastly/tor/merge_requests/1#note_863)

I removed the SchedulerLowWaterMark__, SchedulerHighWaterMark__, and SchedulerMaxFlushCells__ options. They were ineffective and never meaningful.

Low: Tor had to have less than this in its outbufs or else it wouldn't start a scheduling round. High: Tor would stop a scheduling round if it hit this. MaxFlush: Tor would flush this many cells at maximum from a circuit queue to its outbuf at a time before moving on to another channel.

They were all set so high that they didn't matter.

I'm pretty sure the bug you are thinking of is #20459 fixed in c09993fdf6.


"What if ms >= 1000?" (https://oniongit.eu/pastly/tor/merge_requests/1#note_869)

I'm assuming you mean "what if diff >= 1000"

sched_run_interval (or _freq as it was called then) has a maximum of 100 ms. If diff is larger than sched_run_interval, the code block with event_active is called instead so it doesn't matter.


I've put off mucking around with int types still.

Last edited 6 weeks ago by pastly (previous) (diff)

comment:32 Changed 6 weeks ago by yawning

Cc: yawning removed

comment:33 Changed 6 weeks ago by pastly

I switched to monotonic time and tweaked/added some comments and log messages on top of dgoulet's branch. Ready for review so it can slip into 032 <3

https://oniongit.eu/pastly/tor/merge_requests/2

comment:34 Changed 6 weeks ago by pastly

KIST deployment paper: https://arxiv.org/abs/1709.01044

comment:35 Changed 5 weeks ago by nickm

Status: needs_reviewneeds_revision

reviewed; left comments on branch.

comment:36 Changed 5 weeks ago by dgoulet

Status: needs_revisionneeds_review

comment:37 Changed 5 weeks ago by nickm

Status: needs_reviewneeds_revision

reviewed; left more comments on branch. also please see threads that didn't get checked off; I thought those had open questions when I looked. Also this needs a changes file.

comment:38 Changed 5 weeks ago by dgoulet

Status: needs_revisionneeds_review

Answered. Fixup are in my kist-fortor-03 and pastly just pushed it to oniongit.

comment:39 Changed 5 weeks ago by nickm

Status: needs_reviewmerge_ready

Merging!

Please close this ticket once the new tickets from the review are open, and once appropriate child tickets are closed or unparented.

comment:40 Changed 5 weeks ago by pastly

Resolution: implemented
Status: merge_readyclosed

Sweet glorious day

comment:41 in reply to:  40 Changed 5 weeks ago by cypherpunks

Replying to pastly:

Sweet glorious day

Congrats pastly and rob, good stuff! :)

Note: See TracTickets for help on using tickets.