Opened 8 years ago

Closed 8 years ago

Last modified 7 years ago

#4488 closed project (implemented)

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

Reported by: arma Owned by:
Priority: Medium Milestone:
Component: Core Tor/Tor Version:
Severity: Keywords: performance flowcontrol tor-relay SponsorF20121101
Cc: robgjansen, kevin Actual Points:
Parent ID: #4506 Points:
Reviewer: Sponsor:

Description

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 and #4487.

Child Tickets

Change History (20)

comment:1 Changed 8 years ago by arma

Keywords: performance, flowcontrolperformance flowcontrol

comment:2 Changed 8 years ago by karsten

Parent ID: #4506

comment:3 Changed 8 years ago by nickm

Milestone: Tor: 0.2.3.x-finalTor: unspecified

comment:4 Changed 8 years ago by robgjansen

Cc: jansen@… added

comment:5 Changed 8 years ago by arma

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.

comment:6 Changed 8 years ago by arma

Cc: robgjansen kevin added; jansen@… removed

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.

comment:7 Changed 8 years ago by arma

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

comment:8 Changed 8 years ago by arma

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.

Maybe this one will run better?

comment:9 Changed 8 years ago by arma

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?

comment:10 Changed 8 years ago by kevin

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);
}

comment:11 in reply to:  10 Changed 8 years ago by arma

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.

comment:12 in reply to:  9 Changed 8 years ago by arma

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.

comment:13 in reply to:  9 Changed 8 years ago by arma

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.

comment:14 Changed 8 years ago by arma

Resolution: implemented
Status: newclosed

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 for that work.

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

comment:15 Changed 7 years ago by karsten

Milestone: Tor: unspecifiedSponsor F: March 15, 2012
Type: taskproject

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.

comment:16 Changed 7 years ago by karsten

Keywords: SponsorF20120315 added
Milestone: Sponsor F: March 15, 2012

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

comment:17 Changed 7 years ago by karsten

Keywords: SponsorF20120315 removed
Type: projecttask

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 for the November milestone.

comment:18 Changed 7 years ago by nickm

Keywords: tor-relay added

comment:19 Changed 7 years ago by nickm

Component: Tor RelayTor

comment:20 Changed 7 years ago by karsten

Keywords: SponsorF20121101 added
Type: taskproject

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

Note: See TracTickets for help on using tickets.