How is Path Selection done in Tor?

Question

Can anybody explain how path selection is done in Tor because the man page fail to specify in detail on how certain probabilities are calculated etc.

In the man page there are a set of equations:

Wgg*G + Wgd*D == M + Wmd*D + Wme*E + Wmg*G  (guard bw = middle bw)
Wgg*G + Wgd*D == Wee*E + Wed*D              (guard bw = exit bw)
Wed*D + Wmd*D + Wgd*D == D                  (aka: Wed+Wmd+Wdg = 1)
Wmg*G + Wgg*G == G                          (aka: Wgg = 1-Wmg)
Wme*E + Wee*E == E                          (aka: Wee = 1-Wme)

I wanted to know the reasoning behind them?

Answer 1

Route calculations are based around the available bandwidth of each of the candidate nodes for a given circuit. In the formulae in your question, W is the weight ascribed to a given node, with full decodes being shown below:

   List of optional weights to apply to router bandwidths during path
   selection. They are sorted in lexical order (as ASCII byte strings) and
   values are divided by the consensus' "bwweightscale" param. Definition
   of our known entries are...

     Wgg - Weight for Guard-flagged nodes in the guard position
     Wgm - Weight for non-flagged nodes in the guard Position
     Wgd - Weight for Guard+Exit-flagged nodes in the guard Position

     Wmg - Weight for Guard-flagged nodes in the middle Position
     Wmm - Weight for non-flagged nodes in the middle Position
     Wme - Weight for Exit-flagged nodes in the middle Position
     Wmd - Weight for Guard+Exit flagged nodes in the middle Position

     Weg - Weight for Guard flagged nodes in the exit Position
     Wem - Weight for non-flagged nodes in the exit Position
     Wee - Weight for Exit-flagged nodes in the exit Position
     Wed - Weight for Guard+Exit-flagged nodes in the exit Position

     Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
     Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
     Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
     Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes

     Wbg - Weight for Guard flagged nodes for BEGIN_DIR requests
     Wbm - Weight for non-flagged nodes for BEGIN_DIR requests
     Wbe - Weight for Exit-flagged nodes for BEGIN_DIR requests
     Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests

The algorithms used, together with the constraints placed on them, are explained in great detail in the Tor directory protocol document. I'd recommend taking a look at section "3.8.3. Computing Bandwidth Weights".

[The above list of decodes can be found in "3.4.1. Vote and consensus status document formats".]

The algorithms don't really lend themselves to concise explanations, so I won't go into further details here.

If you want to see the code, have a look at ./src/or/dirvote.c