dsdvroutetable.hh

COPE the first practical network coding scheme which is developped on click

#ifndef CLICK_DSDVROUTETABLE_HH
#define CLICK_DSDVROUTETABLE_HH
#include <click/bighashmap.hh>
#include <click/etheraddress.hh>
#include <click/ipaddress.hh>
#include <clicknet/ether.h>
#include <elements/grid/grid.hh>
#include <elements/grid/gridgenericrt.hh>
#include <click/timer.hh>
#include <elements/grid/gridgenericlogger.hh>
#include <click/dequeue.hh>
#include <elements/grid/gridgenericmetric.hh>
CLICK_DECLS

/*
 * =c
 * DSDVRouteTable(TIMEOUT, PERIOD, JITTER, MIN_TRIGGER_PERIOD, ETH, IP [, I<KEYWORDS>])
 *
 * =s Grid
 * Run DSDV local routing protocol
 *
 * =d 
 *
 * This is meant to be an `official' implementation of DSDV.  It is
 * intended to exactly replicate the behavior of DSDV as described in
 * the original Perkins paper, the CMU ad-hoc bakeoff paper, and the
 * CMU ns implementation.  I make no guarantees that any of the above
 * are actually achieved.
 *
 * DSDVRouteTable expects the Paint annotation to be set on Grid
 * packets arriving from the network.
 *
 * There must only be one of DSDVRouteTable or GridRouteTable in a
 * grid configuration.
 *
 * Regular arguments are:
 *
 * =over 8
 *
 * =item TIMEOUT
 * 
 * Unsigned integer.  Milliseconds after which to expire route entries.
 *
 * =item PERIOD
 *
 * Unsigned integer.  Milliseconds between full dumps, plus/minus some jitter (see below).
 *
 * =item JITTER
 *
 * Unsigned integer.  Maximum milliseconds by which to randomly jitter full dumps.
 *
 * =item MIN_TRIGGER_PERIOD
 *
 * Unsigned integer.  Minimum milliseconds between triggered updates.
 *
 * =item ETH
 *
 * This node's ethernet hardware address.
 *
 * =item IP
 *
 * This node's IP address.
 *
 * =back
 *
 * Keywords arguments are:
 *
 * =over 8
 *
 * =item GW
 *
 * GridGatewayInfo element.  Determines whether or not this node is a
 * gateway.  If this argument is not provided, the node is not a
 * gateway.
 *
 * =item MAX_HOPS
 * 
 * Unsigned integer.  The maximum number of hops for which a route
 * should propagate.  The default number of hops is 3.
 *
 * =item METRIC
 *
 * GridGenericMetric element.  The metric element that should be used
 * to compare two routes.  If not specified, minimum hop-count is
 * used.
 *
 * =item USE_SEQ_METRIC
 *
 * Boolean.  Iff true, use the `dsdv_seqs' metric, and ignore the
 * METRIC keyword.  Defaults to false.
 *
 * =item IGNORE_INVALID_ROUTES
 *
 * Boolean.  Iff true, don't advertise or use routes with invalid
 * route metrics.  Defaults to false.
 *
 * =item LOG
 *
 * GridGenericLogger element.  If provided, Grid events are logged to
 * this element.
 *
 * =item WST0 (zero, not `oh')
 * 
 * Unsigned integer.  Initial weighted settling time in milliseconds.
 * Defaults to 6,000 (6 seconds).
 *
 * =item ALPHA
 * 
 * Unsigned integer.  DSDV settling time weighting parameter, in
 * percent, between 0 and 100 inclusive.  Defaults to 88%.
 *
 * =item SEQ0 (zero, not `oh')
 *
 * Unsigned integer.  Initial sequence number used in advertisements.
 * Defaults to 0.  Must be even.
 *
 * =item MTU
 *
 * Unsigned integer.  Maximum packet size (`mtu') allowed by
 * interface; route broadcasts will not exceed this size.  Defaults to
 * 2000.
 *
 * =item VERBOSE
 *
 * Boolean.  Be verbose about warning and status messages?  Defaults
 * to true.
 *
 * =back
 *
 * =h nbrs read-only
 * Print 1-hop routes.  `nbrs_v' is more verbose.
 * =h rtes read-only
 * Print route table.  `rtes_v' is more verbose.
 * =h links read-only
 * Print this node's link table.
 * =h ip read-only
 * Print this node's IP address.
 * =h eth read-only
 * Print this node's Ethernet address.
 * =h seqno read/write
 * Get/set this node's current sequence number (unsigned int, must be even).
 *
 * =h paused read/write
 *
 * Get/set this node's pause status (boolean).  After the node is
 * paused, subsequent data packets are routed using a snapshot of the
 * route table taken at the pause time; however, the real route table
 * continues to be updated and route ads continue to be sent.  When
 * the node becomes unpaused, packets are routed using the real route
 * table.  The node is initially unpaused.  This functionality may be
 * disabled at compile-time.
 *
 * =h use_old_route read/write
 *
 * Unsigned integer 0-2.  If 0 (default), immediately use routes with
 * newer sequence numbers.  If 1, only use new routes after the
 * settling time has passed and they can be advertised.  If 2,
 * immediately use routes with newer sequence numbers only if their
 * metric is better than the last route; otherwise wait until the
 * settling time has passed before using the new route.  This
 * functionality may be disabled at compile-time.
 *
 * =a
 * SendGridHello, FixSrcLoc, SetGridChecksum, LookupLocalGridRoute, LookupGeographicGridRoute
 * GridGatewayInfo, HopcountMetric, GridLogger, Paint */

// if 1, enable `paused' handler
#define ENABLE_PAUSE 1

// if 1, don't use routes until it's also okay to advertise them
// (enable `use_old_route handler' functionality).
#define USE_OLD_SEQ 1

// if 1, use new routes even if it's not okay to advertise them, as
// long as they have a better metric.  This is a modification of the
// USE_OLD_SEQ functionality.
#define USE_GOOD_NEW_ROUTES 1

// if 1, enable `dsdv_seq' metric, which only uses routes from nodes
// who deliver OLD_BCASTS_NEEDED out of every MAX_BCAST_HISTORY route
// ads.
#define SEQ_METRIC 1
#define MAX_BCAST_HISTORY 3
#define OLD_BCASTS_NEEDED 2

// if 1, enable `seen' link handshaking, described in Chin, Judge,
// William, and Kermode 2002.
#define ENABLE_SEEN 1

class GridGatewayInfo;


class DSDVRouteTable : public GridGenericRouteTable {

public:
  // generic rt methods
  bool current_gateway(RouteEntry &entry);  
  bool get_one_entry(const IPAddress &dest_ip, RouteEntry &entry);
  void get_all_entries(Vector<RouteEntry> &vec);
  unsigned get_number_direct_neigbors();

  DSDVRouteTable();
  ~DSDVRouteTable();

  const char *class_name() const		{ return "DSDVRouteTable"; }
  void *cast(const char *);
  const char *processing() const		{ return "h/h"; }
  const char *flow_code() const                 { return "x/y"; }
  
  int configure(Vector<String> &, ErrorHandler *);
  int initialize(ErrorHandler *);

  virtual bool can_live_reconfigure() const { return false; }

  Packet *simple_action(Packet *);

  void add_handlers();
  
private:

#if SEQ_METRIC
  bool _use_seq_metric; // use the `dsdv_seqs' metric
  HashMap<IPAddress, DEQueue<unsigned> > _seq_history;
#endif

  typedef GridGenericMetric::metric_t metric_t;
  
  /* 
   * route table entry
   */
  class RTEntry : public RouteEntry {
  private:
    bool                _init;

  public:
    class EtherAddress  dest_eth;              // hardware address of destination; 
                                               // may be all 0s if we don't hear any ads...
    bool                is_gateway;

    unsigned int        ttl;                   // msecs
    unsigned int        last_updated_jiffies;  // last time this entry was updated

    // metrics are invalid until updated to incorporate the last hop's
    // link, i.e. by calling initialize_metric or update_metric.
    metric_t            metric;

    // DSDV book-keeping
    unsigned int        wst;                   // weighted settling time (msecs)
    metric_t            last_adv_metric;       // last metric we advertised
    unsigned int        last_seq_jiffies;      // last time the seq_no changed
    unsigned int        advertise_ok_jiffies;  // when it is ok to advertise route
    bool                need_seq_ad;
    bool                need_metric_ad;
    unsigned int        last_expired_jiffies;  // when the route was expired (if broken)

#if ENABLE_SEEN
    unsigned int        last_seen_jiffies;     // last time this dest said it `saw' us (advertised a route to us)
#endif

    bool broken() const { check(); return num_hops() == 0; }
    bool good()   const { check(); return num_hops() != 0; }

    String dump()  const; 
    void   check() const { 
      assert(_init); 
      assert((num_hops() > 0) != (seq_no() & 1)); 
      assert((num_hops() != 1) || (dest_ip == next_hop_ip && dest_eth == next_hop_eth));
      // only check if last_seq_jiff has been set
      assert(last_seq_jiffies ? last_updated_jiffies >= last_seq_jiffies : true); 
    } 

    void invalidate(unsigned int jiff) {
      check();
      assert(num_hops() > 0);
      _num_hops = 0;
      _seq_no++;
      last_expired_jiffies = jiff;
      check();
    }