Proposal 146: Add new flag to reflect long-term stability

[Nick Mathewson <nickm@xxxxxxxxxxxxx>]

Filename: 146-long-term-stability.txt
Title: Add new flag to reflect long-term stability
Version: $Revision: 15606 $
Last-Modified: $Date: 2008-07-02 14:04:01 -0400 (Wed, 02 Jul 2008) $
Author: Nick Mathewson
Created: 19-Jun-2008
Status: Draft

Overview

  This document proposes a new flag to indicate that a router has
  existed at the same address for a long time, describes how to
  implement it, and explains what it's good for.

Motivation

  Tor has had three notions of "stability" for servers.  Older
  directory protocols based a server's stability on its
  (self-reported) uptime: a server that had been running for a day was
  more stable than a server that had been running for five minutes,
  regardless of their past history.  Current directory protocols track
  weighted mean time between failure (WMTBF) and weighted fractional
  uptime (WFU).  WFU is computed as the fraction of time for which the
  server is running, with measurements weighted to exponentially
  decay such that old days count less.  WMTBF is computed as the the
  average length of intervals for which the server runs between
  downtime, with old intervals weighted to count less.

  WMTBF is useful in answering the question: "If a server is running
  now, how long is it likely to stay running?"  This makes it a good
  choice for picking servers for streams that need to be long-lived.
  WFU is useful in answering the question: "If I try connecting to
  this server at an arbitrary time, is it likely to be running?"  This
  makes it an important factor for picking guard nodes, since we want
  guard nodes to be usually-up.

  There are other questions that clients want to answer, however, for
  which the current flags aren't very useful.   The one that this
  proposal addresses is,

       "If I found this server in an old consensus, is it likely to
       still be running at the same address?"

  This one is useful when we're trying to find directory mirrors in a
  fallback-consensus file.  This property is equivalent to,

       "If I find this server in a current consensus, how long is it
       likely to exist on the network?"

  This one is usefule if we're trying to pick introduction points or
  something and care more about churn rate than about whether every IP
  will be up all the time.

Implementation:

  I propose we add a new flag, called "Longterm."  Authorities should
  set this flag for routers if their Longevity is in the upper
  quartile of all routers.  A router's Longevity is computed as the
  total amount of days in the last year or so[*] for which the router has
  been Running at least once at its current IP:orport pair.

  Clients should use directory servers from a fallback-consensus only
  if they have the Longterm flag set.

  Authority ops should be able to mark particular routers as not
  Longterm, regardless of history.  (For instance, it makes sense to
  remove the Longterm flag from a router whose op says that it will
  need to shutdown in a month.)

  [*] This is deliberately vague, to permit efficient implementations.

Compatibility and migration issues:

  The voting protocol already acts gracefully when new flags are
  added, so no change to the voting protocol is needed.

  Tor won't have collected this data, however.  It might be desirable
  to bootstrap it from historical consensuses.  Alternatively, we can
  just let the algorithm run for a month or two.

Issues and future possibilities:

  Longterm is a really awkward name.