Track down the N23 patch, then update it for modern Tor

This summer, Mashael, Kevin et al published the Defenestrator paper, where they proposed the N23 algorithm to improve Tor's flow control.

They did their simulations using ExperimenTor, and the paper says "we use the latest development branch of the Tor source code (version 0.2.3.0-alpha-dev)".

We should get a copy of their patch, and then update it to apply cleanly to current git.

Then we'll have a common ground for the N23 simulations in #4486 (moved) and #4487 (moved).

added SponsorF20121101 component::core tor/tor flowcontrol parent::4506 performance priority::medium resolution::implemented status::closed tor-relay type::project labels

Trac:
Keywords: performance, flowcontrol deleted, performance flowcontrol added

Trac:
Parent: N/A to #4506 (moved)

Trac:
Milestone: Tor: 0.2.3.x-final to Tor: unspecified

Trac:
Cc: N/A to jansen@cs.umn.edu

Update: I'm flying to Waterloo this Sunday to spend Monday with Ian, Kevin, Mashael and teach them git and make this patch into something we can test.

The "n23" branch in my git repo is the result of yesterday's work.

I expect Ian will update it more, possibly including rebasing it. Beware.

If somebody wants to hack up a n23 that's rebased to maint-0.2.2 (or release-0.2.2), that would be grand -- then we could get some experiments going on it despite all the "testingtornetwork + 0.2.3" bugs.

Trac:
Cc: jansen@cs.umn.edu to robgjansen, kevin

I opened ticket #5379 (moved) with some hints on how to do the adaptive N23 algorithm better. I think we should drop it from this patch for now.

Kevin said he tried it in Experimentor and his Tor crashed. No further details yet.

Kevin, can you distinguish between "seg fault" and "assert" when you say crash? If seg fault, any chance we can get a core the next time?

I just pushed a new "n23-2" branch (available at git://git.torproject.org/arma/tor) to fix compile warnings, rip out the (unfinished) adaptive n23 code, and change one assert to a return. I also rebased it onto master so it would get the fix for #5373 (moved).

Maybe this one will run better?

Mashael suggested these parameters for the simulations:

UseN23 1
CircuitWindowSize 1000000
StreamWindowSize 1000000

I believe with some more hacking on the code we can make the "set circ and stream window really high so they never run out" hack obsolete. But I think we're not there yet.

In this case we're using N2 of 10 and initial N3 of 500. Are these plausible numbers?

The crash was a failed assertion at connection_or.c:1866, which corresponds to the tor_assert(conn) within connection_or_send_flowcontrol().

This should be easy to fix: the caller should just ensure that conn is not null.

Here is the code in question:

void
connection_or_send_flowcontrol(circid_t circ_id, or_connection_t *conn, uint32_t cells_fwded)
{
  cell_t cell;
 
  tor_assert(conn);

  memset(&cell, 0, sizeof(cell_t));
  cell.circ_id = circ_id;
  cell.command = CELL_FLOWCONTROL;
  set_uint32(cell.payload, htonl(cells_fwded));
  connection_or_write_cell_to_buf(&cell, conn);
}

Replying to kevin:

The crash was a failed assertion at connection_or.c:1866, which corresponds to the tor_assert(conn) within connection_or_send_flowcontrol().

Great. My n23-2 branch above included an "if that's null, just return" line.

Replying to arma:

In this case we're using N2 of 10 and initial N3 of 500. Are these plausible numbers?

Mashael guesses an N3Initial value of between 50 and 100 is smarter.

Replying to arma:

I believe with some more hacking on the code we can make the "set circ and stream window really high so they never run out" hack obsolete. But I think we're not there yet.

I just pushed an update to my n23-2 branch that, I believe, makes the circwindow and streamwindow hack unnecessary.

If you're already simulating on the previous version of the branch, I believe there's no need to change.

Ok. I declare the n23 patch located and updated.

I can't do any more fixing on the patch until Mashael answers the questions at the top of connection_or_consider_sending_flowcontrol_cell(), so I know what it's supposed to be doing. In particular,

/* IG: Mashael should explain the algorithm here: what it should do in
 * each case and why. */

I opened #5392 (moved) for that work.

Simulation results of this patch should go on #4486 (moved) (and #4487 (moved), once we get to it).

Trac:
Status: new to closed
Resolution: N/A to implemented

Making this the new project ticket for Sponsor F: March 15, 2012 task 9. The task was to evaluate feasibility of simulating N23, not to run the simulations, which is blocking on simulator improvements independent of N23.

Trac:
Milestone: Tor: unspecified to Sponsor F: March 15, 2012
Type: task to project

Switching from using milestones to keywords for sponsor deliverables. See #6365 (moved) for details.

Trac:
Keywords: performance flowcontrol deleted, performance flowcontrol SponsorF20120315 added
Milestone: Sponsor F: March 15, 2012 to N/A

Roger and I discussed sponsor F deliverables at the Florence hackfest. This ticket was the ticket for sponsor F deliverable 9, but really, we should do its parent ticket #4506 (moved) for the November milestone.

Trac:
Keywords: performance flowcontrol SponsorF20120315 deleted, performance flowcontrol added
Type: project to task

Trac:
Keywords: performance flowcontrol deleted, performance flowcontrol tor-relay added

Trac:
Component: Tor Relay to Tor

Making #4488 (moved), not #4506 (moved), the project ticket for sponsor F year 2 item 9.

Trac:
Keywords: performance flowcontrol tor-relay deleted, performance flowcontrol tor-relay SponsorF20121101 added
Type: task to project

closed

mentioned in issue #4506 (moved)

mentioned in issue #5333 (moved)

mentioned in issue #5379 (moved)

mentioned in issue #5392 (moved)

moved to tpo/core/tor#4488 (closed)

mentioned in issue tpo/core/tor#5379 (closed)

mentioned in issue tpo/core/tor#5392 (closed)