reorderer.hh

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

#ifndef CLICK_REORDERER_HH
#define CLICK_REORDERER_HH
#include <click/element.hh>
#include <click/string.hh>
#include <click/vector.hh>
#include <click/bighashmap.hh>
#include <click/timestamp.hh>
//#include <click/etheraddress.hh>
#include <clicknet/tcp.h>

CLICK_DECLS

/*
 * =c
 * Reorderer()
 * =s 
 * =d
 * Buffers TCP packets received from the router and sort them 
 * in the right order before passing to applications
 *
 * output 0: non-TCP packets
 * output 1: reordered TCP packets
 *
 * Keyword arguments are:
 *
 * =over 8
 *
 * =a
 * Print 
 */

class Timer;

class Reorderer : public Element {
  
public:
  
  Reorderer();
  ~Reorderer();
  
  const char *class_name() const		{ return "Reorderer"; }
  const char *processing() const		{ return PUSH; }
  
  int configure(Vector<String> &, ErrorHandler *);
  int initialize(ErrorHandler *errh);
  void run_timer();

  void reset();
  
  void push(int, Packet *);

  void add_handlers();
  static String stats(Element *, void *);
  static int static_clear(const String &arg, Element *e,
                          void *, ErrorHandler *errh);
  static int enable(const String &arg, Element *e,
		    void *, ErrorHandler *errh);
  static int set_timeout(const String &arg, Element *e,
			 void *, ErrorHandler *errh);

  bool _on;   // whether to enable the reordering capability
  uint16_t _timeout;  // fixed for now

  class PacketEntry { public:
    Packet* _p;
    tcp_seq_t _tcpseq; // tcp seq 
    uint16_t _pktlen;
    int32_t _timestamp; // in ms

    PacketEntry(Packet* p, tcp_seq_t tcpseq, uint16_t pktlen) 
      : _p(p), _tcpseq(tcpseq), _pktlen(pktlen), _timestamp(Timestamp::now().msec1()) {} 

  }; 

  // for stats
  int _udp_seen;         // number of UDP packets seen
  int _tcp_seen;         // number of TCP packets seen
  int _ordered;          // number of TCP packets in order
  int _late;        // number of TCP packets which arrive after later packets have arrived and been passed to the host (too late to be reordered)
  int _reordered;        // number of packets reordered
  int _timedout;         // number of packets timed out
  int _dups;             // number of duplicate TCP packets seen
  int _rst_set;          // number of TCP packets with rst flag set
  // _tcp_seen = _ordered + _late + _reordered + _dups + _rst_set + _timedout

private:

  typedef Vector<PacketEntry *> PktVector;

  class FlowState { public:
    PktVector *_pktv;
    int _start_offset; // where shall we start looking in _pkt_vector, mainly for when sequence number wraps around
    tcp_seq_t _next_seq; // next expected seq

    // in case we've released a packet before earlier ones arrive
    // we'll need to skip it eventually...
    tcp_seq_t _skip_seq_start; 
    tcp_seq_t _skip_seq_end;
    // assuming we won't get more than one gap, ie, packets sent as a, b, c but received as c, b, a

    // whether we've seen fin/fin ack
    bool _seen_fin;

    // how many packets we've seen after fin/fin ack
    // on the sender side, this should be 0 (see fin ack)
    // on the received side, this should be 1 (see fin, then ack)
    // to make life easier, this number gets deducted if we see syn - i.e., we're the receiver
    // so now delete the flow state after this number turns 0.
    int8_t _num_pkt_post_fin;

    FlowState() : _start_offset(0), _next_seq(0), _skip_seq_start(0), _skip_seq_end(0) {
      _num_pkt_post_fin = -1;
      _seen_fin = false;
      _pktv = new PktVector;
    }

    ~FlowState() {
      while (_pktv->size()) {
	PacketEntry *pe = (*_pktv)[0];
	_pktv->erase(_pktv->begin());
	if (pe)  // just in case this point has been deleted elsewhere, but not properly cleaned here
	  delete pe;
      }

      delete _pktv;
    }

    // indicate whether there's a gap in the seq numbers among packets already sent out
    bool has_hole() {
      return (_next_seq < _skip_seq_end);
    }
  };

  typedef HashMap<String, FlowState*> PktMap;
  // key is a string of src port concat'ed with dest port
  // value is vector of packets(+info) from this flow
  PktMap _pkt_table;

  // timeout related...
  Timer _timer;

  typedef Vector<int32_t> TimeVector;
  typedef TimeVector::iterator TimeVecIter;

  // a vector of times to schedule the timer
  TimeVector _time_vec;

  typedef HashMap<String, PacketEntry*> PktReg;  // key is string of sport+dport+tcpseq
  typedef PktReg::iterator PktRegIter;
  typedef HashMap<int32_t, PktReg*> TimeoutReg;

  // key is time to timeout, value is HashMap of all packets to be sent out if they're 
  // still stuck in the reordering buffer
  TimeoutReg _timeout_reg;

  // returns the pointer to the PacketEntry created if an insertion took place
  PacketEntry *insert(FlowState *, PktVector *, Packet *, tcp_seq_t, uint16_t);

  void register_timeout(String, PacketEntry *);
  void deregister_timeout(int32_t, String);
  void schedule_timer();

  void drop(Packet *);
};

CLICK_ENDDECLS
#endif