# Torflow aggregation and scaling

See also

How aggregation and scaling works and Differences between Torflow and sbws.

Torflow aggregation or scaling goal is:

From Torflow’s README.spec.txt (section 2.2):

    In this way, the resulting network status consensus bandwidth values
    are effectively re-weighted proportional to how much faster the node
    was as compared to the rest of the network.

## Initialization

Constants in consensus that Torflow uses and don’t change:

    bandwidth-weights Wbd=0 Wbe=0 [] Wbm=10000 Wdb=10000 Web=10000 Wed=10000 Wee=10000 Weg=10000 Wem=10000 Wgb=10000 Wgd=0 Wgg=5852 [] Wmb=10000 Wmd=0 Wme=0 [] Wmm=10000

    params [] bwauthpid=1

Constants in the code:

    IGNORE_GUARD = 0
    GUARD_SAMPLE_RATE = 2*7*24*60*60 # 2wks
    MAX_AGE = 2*GUARD_SAMPLE_RATE;  # 4 weeks

    K_p = 1.0
    T_i = 0
    T_i_decay = 0
    T_d = 0

Initialization `ConsensusJunk`:

    self.bwauth_pid_control = True
    self.group_by_class = False
    self.use_pid_tgt = False
    self.use_circ_fails = False
    self.use_best_ratio = True
    self.use_desc_bw = True
    self.use_mercy = False
    self.guard_sample_rate = GUARD_SAMPLE_RATE
    self.pid_max = 500.0
    self.K_p = K_p = 1.0
    self.T_i = T_i = 0
    self.T_d = T_d = 0
    self.T_i_decay = T_i_decay = 0

    self.K_i = 0
    self.K_d = self.K_p*self.T_d = 0

Initialization `Node`:

    self.sbw_ratio = None
    self.fbw_ratio = None
    self.pid_bw = 0
    self.pid_error = 0
    self.prev_error = 0
    self.pid_error_sum = 0
    self.pid_delta = 0
    self.ratio = None
    self.new_bw = None
    self.use_bw = -1
    self.flags = ""

    # measurement vars from bwauth lines
    self.measured_at = 0
    self.strm_bw = 0
    self.filt_bw = 0
    self.ns_bw = 0
    self.desc_bw = 0
    self.circ_fail_rate = 0
    self.strm_fail_rate = 0
    self.updated_at = 0

## Descriptor values for each relay

From TorCtl.py code, it is the minimum of all the descriptor bandwidth values:

    bws = map(int, g)
    bw_observed = min(bws)

    [snip]

    return Router(ns.idhex, ns.nickname, bw_observed, dead, exitpolicy,
    ns.flags, ip, version, os, uptime, published, contact, rate_limited,
    ns.orhash, ns.bandwidth, extra_info_digest, ns.unmeasured)

`ns.bandwidth` is the consensus bandwidth, already multiplied by 1000:

    yield NetworkStatus(*(m.groups()+(flags,)+(int(w.group(1))*1000,))+(unmeasured,))

Because of the matched regular expression, `bws` is not all the descriptor bandwidth values, but the average bandwidth and the observed bandwidth, ie., it does not take the average burst, what seems to be a bug in Torflow.

Eg. `bandwidth` line in a descriptor:

    bandwidth 1536000 4096000 1728471

Only takes the first and last values, so:

    bw_observed = min(bandwidth-avg, bandwidth-observed)

This is passed to `Router`, in which the descriptors bandwidth is assigned to the consensus bandwidth when there is no consensus bandwidth:

    (idhex, name, bw, down, exitpolicy, flags, ip, version, os, uptime,
       published, contact, rate_limited, orhash,
       ns_bandwidth,extra_info_digest,unmeasured) = args

    [snip]

    if ns_bandwidth != None:
      self.bw = max(ns_bandwidth,1) # Avoid div by 0
    else:
      self.bw = max(bw,1) # Avoid div by 0

    [snip]

    self.desc_bw = max(bw,1) # Avoid div by 0

So:

    self.bw = ns_bwandwidth or min(bandwidth-avg, bandwidth-observed) or 1
    desc_bw = min(bandwidth-avg, bandwidth-observed) or 1

And written by SQLSupport.py as descriptor and conensus bandwidth:

    f.write(" desc_bw="+str(int(cvt(s.avg_desc_bw,0))))
    f.write(" ns_bw="+str(int(cvt(s.avg_bw,0)))+"\n")

### Descriptor bandwidth with PID control

Even though README.spec.txt talks about the consensus bandwidth, in aggregate.py code, the consensus bandwidth is never used, since `use_desc_bw` is initialized to True and never changed:

    if cs_junk.bwauth_pid_control:
      if cs_junk.use_desc_bw:
        n.use_bw = n.desc_bw
      else:
        n.use_bw = n.ns_bw

So:

    n.use_bw = n.desc_bw = min(bandwidth-avg, bandwidth-observed) or 1

## Scaling the raw measurements

### Overview

This diagram also includes Descriptor bandwidth with PID control, Ratio for each relay and Scaled bandwidth for each relay with PID control.

Simplified image from:

./_images/activity_torflow_scaling_simplified.svg

./_images/activity_torflow_scaling.svg

### Stream and filtered bandwidth for each relay

They are calculated in the same way whether or not PID controller feedback is used.

From Torflow’s README.spec.txt (section 1.6):

    The strm_bw field is the average (mean) of all the streams for the relay
    identified by the fingerprint field.

    The filt_bw field is computed similarly, but only the streams equal to
    or greater than the strm_bw are counted in order to filter very slow
    streams due to slow node pairings.

In the code, SQLSupport.py, `strm_bw` is `sbw` and `filt_bw` is `filt_sbws`:

    for rs in RouterStats.query.filter(stats_clause).\
          options(eagerload_all('router.streams.circuit.routers')).all():
      tot_sbw = 0
      sbw_cnt = 0
      for s in rs.router.streams:
        if isinstance(s, ClosedStream):
          skip = False
          #for br in badrouters:
          #  if br != rs:
          #    if br.router in s.circuit.routers:
          #      skip = True
          if not skip:
            # Throw out outliers < mean
            # (too much variance for stddev to filter much)
            if rs.strm_closed == 1 or s.bandwidth() >= rs.sbw:
              tot_sbw += s.bandwidth()
              sbw_cnt += 1

    if sbw_cnt: rs.filt_sbw = tot_sbw/sbw_cnt
    else: rs.filt_sbw = None

This is also expressed in pseudocode in the bandwidth file spec, section B.4 step 1.

Calling `bwstrm_i` to `strm_bw` and `bwfilt_i` to `filt_bw`, if `bw_j` is a measurement for a relay `i`, then::

    bwstrm_i = mean(bw_j)  # for a relay, the average of all its measurements
    bwfilt_i = mean(max(bwstrm_i, bw_j))

### Stream and filtered bandwidth for all relays

From README.spec.txt (section 2.1):

    Once we have determined the most recent measurements for each node, we
    compute an average of the filt_bw fields over all nodes we have measured.

In Torflow’s aggregate.py code:

    for cl in ["Guard+Exit", "Guard", "Exit", "Middle"]:
      c_nodes = filter(lambda n: n.node_class() == cl, nodes.itervalues())
      if len(c_nodes) > 0:
        true_filt_avg[cl] = sum(map(lambda n: n.filt_bw, c_nodes))/float(len(c_nodes))
        true_strm_avg[cl] = sum(map(lambda n: n.strm_bw, c_nodes))/float(len(c_nodes))
        true_circ_avg[cl] = sum(map(lambda n: (1.0-n.circ_fail_rate),
                              c_nodes))/float(len(c_nodes))

The following code it’s actually used later to set the `filt_avg` and `strm_avg` for each class:

    filt_avg = sum(map(lambda n: n.filt_bw, nodes.itervalues()))/float(len(nodes))
    strm_avg = sum(map(lambda n: n.strm_bw, nodes.itervalues()))/float(len(nodes))

Because `cs_junk.group_by_class` is False, it runs:

    for cl in ["Guard+Exit", "Guard", "Exit", "Middle"]:
      true_filt_avg[cl] = filt_avg
      true_strm_avg[cl] = strm_avg
      true_circ_avg[cl] = circ_avg
      pid_tgt_avg[cl] = pid_avg

So `filt_avg` and `strm_avg` are calculated not by class in either case, with and without PID control.

Calling `bwstrm` to `strm_avg` and `bwfilt` to `fitl_avg`, without taking into account the different types of nodes:

    bwstrm = mean(bwstrm_i)
    bwfilt = mean(bwfilt_i)

This is also expressed in pseudocode in the bandwidth file spec, section B.4 step 2.

### Ratio for each relay

From README.spec.txt (section 2.2):

    These averages are used to produce ratios for each node by dividing the
    measured value for that node by the network average.

In Torflow’s aggregate.py code:

    for n in nodes.itervalues():
        n.fbw_ratio = n.filt_bw/true_filt_avg[n.node_class()]
        n.sbw_ratio = n.strm_bw/true_strm_avg[n.node_class()]

    [snip]

    # Choose the larger between sbw and fbw
      if n.sbw_ratio > n.fbw_ratio:
        n.ratio = n.sbw_ratio
      else:
        n.ratio = n.fbw_ratio

So:

    n.ratio = max(n.sbw_ratio, n.fbw_ratio)

This is also expressed in pseudocode in the bandwidth file spec, section B.4 step 2 and 3.

### Scaled bandwidth for each relay without PID control

From README.spec.txt (section 2.2):

    These ratios are then multiplied by the most recent observed descriptor
    bandwidth we have available for each node, to produce a new value for
    the network status consensus process.

In aggregate.py code:

    n.new_bw = n.desc_bw*n.ratio

So:

    n.new_bw = (
        min(bandwidth-avg, bandwidth-observed) or 1 \
        * max(bwstrm_i / bwstrm, bwfilt_i / bwfilt)
    )

This is also expressed in pseudocode in the bandwidth file spec, section B.4 step 5.

### Scaled bandwidth for each relay with PID control

From README.spec.txt section 3.1:

    The bandwidth authorities measure F_node: the filtered stream
    capacity through a given node (filtering is described in Section 1.6).

    [snip]

    pid_error = e(t) = (F_node - F_avg)/F_avg.

    [snip]

    new_consensus_bw = old_consensus_bw +
                         old_consensus_bw * K_p * e(t) +
                         old_consensus_bw * K_i * \integral{e(t)} +
                         old_consensus_bw * K_d * \derivative{e(t)}

    [snip]

    For the case where K_p = 1, K_i=0, and K_d=0, it can be seen that this
    system is equivalent to the one defined in 2.2, except using consensus
    bandwidth instead of descriptor bandwidth:

        new_bw = old_bw + old_bw*e(t)
        new_bw = old_bw + old_bw*(F_node/F_avg - 1)
        new_bw = old_bw*F_node/F_avg
        new_bw = old_bw*ratio

In Torflow’s code, this is actually the case and most of the code is not executed because the default `K` values.

It seems then that `F_node` is `filt_bw` in Torflow’s code or `bwfilt_i` here, and `F_avg` is `filt_avg` in Torflow’s code or `bwfilt` here.

In aggregate.py code, pid error also depends on which of the ratios is greater:

    if cs_junk.use_best_ratio and n.sbw_ratio > n.fbw_ratio:
            n.pid_error = (n.strm_bw - true_strm_avg[n.node_class()]) \
                            / true_strm_avg[n.node_class()]
            else:
            n.pid_error = (n.filt_bw - true_filt_avg[n.node_class()]) \
                            / true_filt_avg[n.node_class()]

    [snip]

    n.new_bw = n.use_bw + cs_junk.K_p*n.use_bw*n.pid_error

So:

    if (bwstrm_i / bwstrm) > (bwfilt_i / bwfilt):
        pid_error = (bwstrm_i - bwstrm) / bwstrm = (bwstrm_i / bwstrm) - 1
    else:
        pid_error = (bwfilt_i - bwfilt_i) / bwfilt = (bwfilt_i / bwfilt) - 1

    new_bw = use_bw + use_bw * pid_error

Or:

    if (bwstrm_i / bwstrm) > (bwfilt_i / bwfilt):
        new_bw = use_bw + use_bw * ((bwstrm_i / bwstrm) - 1)
        new_bw = use_bw + use_bw * (bwstrm_i / bwstrm) - use_bw
        new_bw = use_bw * (bwstrm_i / bwstrm)
    else:
        new_bw = use_bw + use_bw * ((bwfilt_i / bwfilt) - 1)
        new_bw = use_bw + use_bw * (bwfilt_i / bwfilt) - use_bw
        new_bw = use_bw * (bwfilt_i / bwfilt)

Or:

    new_bw = use_bw * max(bwstrm_i / bwstrm, bwfilt_i / bwfilt)
    new_bw = (
        min(bandwidth-avg, bandwidth-observed) or 1
        * max(bwstrm_i / bwstrm, bwfilt_i / bwfilt)
    )

Note

So, the new scaled bandwidth is the same for both cases with and without PID controller!

## Other pid KeyValues in the Bandwidth File

Note

From the Overview it seems that the only variable needed to calculate the new scaled bandwidth is the `pid_error`, and from Descriptor bandwidth with PID control, it can be substituted by the stream and filtered bandwidths.

This are the variables that can then be ignored:

    pid_error_sum
    pid_delta
    prev_error

## Limit scaled bandwidth for each relay

It’s calculated the same with and without PID control

Once each relay bandwidth is scaled, it is limited to a maximum, that is calculated as the sum of all the relays in the current consensus scaled bandwidth per 0.05.

From aggregate.py code:

    NODE_CAP = 0.05

    [snip]

    if n.idhex in prev_consensus:
      if prev_consensus[n.idhex].bandwidth != None:
        prev_consensus[n.idhex].measured = True
        tot_net_bw += n.new_bw

    [snip]

    if n.new_bw > tot_net_bw*NODE_CAP:
      [snip]
      n.new_bw = int(tot_net_bw*NODE_CAP)

## Round the scaled bandwidth for each relay

Finally, the new scaled bandwidth is expressed in kilobytes and rounded a number of digits.