scramblequeue.cc

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

/*
 * scramblequeue.{cc,hh} -- does network coding while enqueueing packets
 * i.e., xor's packets whose (prev hop, next hop) are in reverse order to each other. 
 * The encoded packet is expected to go to broadcast or pseudo-broadcast
 * 
 * Wenjun Hu
 *
 * Copyright (c) 2005 University of Cambridge
 * Copyright (c) 2005 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file is
 * legally binding.
*/

#include <click/config.h>
#include <click/confparse.hh>
#include <clicknet/ether.h>
#include <clicknet/ip.h>
#include <clicknet/tcp.h>
#include <click/ipaddress.hh>
#include <click/etheraddress.hh>
#include <click/error.hh>
#include <click/straccum.hh>
#include <click/timestamp.hh>
#include <click/string.hh>
#include <elements/wifi/sr/srpacket.hh>
#include <elements/wifi/sr/path.hh>

#include "xorer.hh"
#include "scramblequeue.hh"

CLICK_DECLS

ScrambleQueue::ScrambleQueue()
  : CodingManager(),
    _pulls(0),
    _avdepth(0),
    _pushes(0),
    _onlyack(0),
    _onlydata(0),
    _nxorattempts(0),
    _totencodedpkts(0), 
    _totunencodedpkts(0),
    _totrexmitpkts(0),
    _totencodedbytes(0), 
    _totunencodedbytes(0),
    _totrexmitbytes(0),
    //_scramble_enabled(true), 
  //    _use_bcast(false),
  // _enc_dst(),
    _ack_ethtype(0), 
    _recp_ethtype(0),
    _nothing_ethtype(0), 
    _myea(), 
    _gseq(0),
    _recvmgr(0),
    _max_ack_size(400),
    _max_recp_size(400),
    _min_timer_interval(10),
    _next_ack_time(0),
    _next_rexmit_time(0),
    _next_recp_time(0),
    _next_time_to_fire(0),
    _last_time_fired(0),
    _fair_queue_thresh(2500),
    _timer(this),
    _sleepiness(0),
    _useless_pulls(0)
{
  /*
     static unsigned char empty_addr[] = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 }; 
     _enc_dst = EtherAddress(empty_addr);
     */
  click_chatter("constr, totencoded is %u", _totencodedbytes);

}

ScrambleQueue::~ScrambleQueue()
{
}

  void *
ScrambleQueue::cast(const char *n)
{
  if (strcmp(n, "ScrambleQueue") == 0)
    return (ScrambleQueue *)this;
  else if (strcmp(n, Notifier::EMPTY_NOTIFIER) == 0)
    return static_cast<Notifier *>(&_empty_note);
  else if (strcmp(n, Notifier::NONFULL_NOTIFIER) == 0)
    return static_cast<Notifier *>(&_full_note);
  else
    return CodingManager::cast(n);
}

int
ScrambleQueue::configure(Vector<String> &conf, ErrorHandler *errh)
{
  click_chatter("starting scramble queue");
  _empty_note.initialize(router());

  _full_note.initialize(router());
  _full_note.set_signal_active(true);

  int new_capacity = 1000;
  uint32_t new_min_timer_interval = 0;

  int res = cp_va_parse(conf, this, errh,
      cpKeywords,
      "ENCETHTYPE", cpUnsigned, "Ethernet encapsulation type for encoded", &_enc_ethtype,
      "ACKETHTYPE", cpUnsigned, "Ethernet encapsulation type for ackhdr", &_ack_ethtype,
      "RECPETHTYPE", cpUnsigned, "Ethernet encapsulation type for reception reports", &_recp_ethtype,
      "NOTHINGETHTYPE", cpUnsigned, "Ethernet encapsulation type for no following packet", &_nothing_ethtype,
      "ETH", cpEtherAddress, "Ethernet address", &_myea,
      "IP", cpIPAddress, "IP address", &_myip,
      "SENDMGR", cpElement, "Sendmanager element", &_sendmgr,
      "RECVMGR", cpElement, "To Ack Table", &_recvmgr,
      "ALIASTABLE", cpElement, "Neighbor Alias", &_aliases,
      "LISTENMGR", cpElement, "Listen Manager for opp listening", &_listenmgr,
      "GUESSMGR", cpElement, "Guess Manager for coding decisions", &_guess_mgr,
      /* optional */
			//      "ENCODE", cpBool, "enable encoding", &_scramble_enabled,
			//			"BROADCAST", cpBool, "use broadcast", &_use_bcast,
      "CAPACITY", cpUnsigned, "maximum queue length", &new_capacity,
      "MINTIMERINTERVAL", cpUnsigned, "Minimum interval between timers (ms)", &new_min_timer_interval,
      "MAX_ACK_SIZE", cpUnsigned, "maximum size of a pure ack packet", &_max_ack_size,
      "MAX_RECP_SIZE", cpUnsigned, "maximum size of a pure reception report packet", &_max_recp_size,
      cpEnd); 

  if (!_enc_ethtype)
    return errh->error("ENCETHTYPE not specified");

  if (!_ack_ethtype)
    return errh->error("ACKETHTYPE not specified");

  if (!_nothing_ethtype)
    return errh->error("NOTHINGETHTYPE not specified");

  if (!_recp_ethtype)
    return errh->error("RECPETHTYPE not specified");

  if (!_myip)
    return errh->error("IP not specified");

  if (!_myea)
    return errh->error("ETH not specified");

  if (!_sendmgr) {
    return errh->error("SENDMGR not specified");
  }
  if (_sendmgr->cast("SendManager") == 0) {
    return errh->error("SENDMGR element is not a SendManager");
  }

  if (!_aliases) {
    return errh->error("ALIASTABLE not specified");
  }
  if (_aliases->cast("AliasTable") == 0) {
    return errh->error("ALIASTABLE element is not an AliasTable");
  }

  if (!_recvmgr) {
    return errh->error("RECVMGR not specified");
  }
  if (_recvmgr->cast("RecvManager") == 0) {
    return errh->error("RECVMGR element is not a RecvManager");
  }

  if (!_listenmgr) {
    return errh->error("LISTENMGR not specified");
  }
  if (_listenmgr->cast("ListenManager") == 0) {
    return errh->error("LISTENMGR element is not a ListenManager");
  }


  if (new_min_timer_interval) {
    _min_timer_interval = new_min_timer_interval;
  }


  _capacity = new_capacity;

  Vector<String> fnconf;
  fnconf.push_back(String(new_capacity));

  int res2 = _tbuf.configure(fnconf, errh);
  if (res2 < 0) {
    return -1;
  }

  click_chatter("scramble queue done");
  if (res < 0)
    return -1;
  else 
    return SimpleQueue::configure(fnconf, errh);
}

  int
ScrambleQueue::initialize(ErrorHandler *errh)
{
  _timer.initialize(this);

  int res = _tbuf.initialize(errh);
  if (res != 0) {
    return res;
  }
  return SimpleQueue::initialize(errh);
}

  Packet *
ScrambleQueue::find_xor_candidate(Packet *p)
{
  Packet *res = 0;

  _nxorattempts++;
  uint32_t prev_hop, next_hop;

  if (!_enable_coding) {
    return 0;
  }

  if (!xor_worthy(p, _myip.addr(), prev_hop, next_hop)) {
    click_chatter("%s: find_xor_candidate rejected p, too short/some zero hop", id().cc());
    return res;
  }
  click_chatter("%s: find_xor_candidate called with (%u, %u)", id().cc(), prev_hop, next_hop);

  while (Packet *q = deq()) {
    if (!xor_candidate(q, _myip.addr(), prev_hop, next_hop)) {
      _avdepth++;
      _tbuf.lifo_enq(q);
    } else {
      res = q;
      break;
    }
  }

  while (Packet *q = _tbuf.deq()) {
    lifo_enq(q);
  }

  return res;
}

  WritablePacket *
ScrambleQueue::combine(Packet *p1, Packet *p2)
{
  struct click_ether *eth_p1 = (struct click_ether *)p1->data();
  struct srpacket *srh_p1 = (struct srpacket *)(eth_p1 + 1);
  const struct click_ip *ip_p1 = p1->ip_header();
  uint16_t ipid_p1 = ip_p1->ip_id;
  uint32_t src_p1 = IPAddress(ip_p1->ip_src).addr();
  uint32_t ipdst_p1 = IPAddress(ip_p1->ip_dst).addr();
  uint16_t ethtype_p1 = eth_p1->ether_type;
  EtherAddress ea_p1 = EtherAddress(eth_p1->ether_dhost);
  uint8_t dst_p1 = _aliases->lookup(ea_p1);
  uint16_t p1len = p1->length();
  uint16_t sport_p1(0), dport_p1(0);
  tcp_seq_t seq_p1(0), ack_p1(0);
  if (ip_p1->ip_p == IP_PROTO_TCP) {
    const struct click_tcp *tcph = p1->tcp_header();
    sport_p1 = tcph->th_sport;
    dport_p1 = tcph->th_dport;
    seq_p1 = tcph->th_seq;
    ack_p1 = tcph->th_ack;
  }

  struct click_ether *eth_p2 = (struct click_ether *)p2->data();
  struct srpacket *srh_p2 = (struct srpacket *)(eth_p2 + 1);
  const struct click_ip *ip_p2 = p2->ip_header();
  uint16_t ipid_p2 = ip_p2->ip_id;
  uint32_t src_p2 = IPAddress(ip_p2->ip_src).addr();
  uint32_t ipdst_p2 = IPAddress(ip_p2->ip_dst).addr();
  uint16_t ethtype_p2 = eth_p2->ether_type;
  uint8_t dst_p2 = _aliases->lookup(EtherAddress(eth_p2->ether_dhost));
  uint16_t p2len = p2->length();
  uint16_t sport_p2(0), dport_p2(0);
  tcp_seq_t seq_p2(0), ack_p2(0);
  if (ip_p2->ip_p == IP_PROTO_TCP) {
    const struct click_tcp *tcph = p1->tcp_header();
    sport_p2 = tcph->th_sport;
    dport_p2 = tcph->th_dport;
    seq_p2 = tcph->th_seq;
    ack_p2 = tcph->th_ack;
  }

  click_chatter("%s: combine() called with (%u, %u, %u, %u, %#0x, %u, %u, %u) and (%u, %u, %u, %u, %#0x, %u, %u, %u) [IPSRC, IPID, DSTALIAS, SEQ, ETHTYPE, IPLEN, SRHLEN, PKTLEN]", id().cc(), src_p1, ntohs(ipid_p1), dst_p1, srh_p1->nseq(), ntohs(ethtype_p1), ntohs(ip_p1->ip_len), srh_p1->hlen_wo_data(), p1len, src_p2, ntohs(ipid_p2), dst_p2, srh_p2->nseq(), ntohs(ethtype_p2), ntohs(ip_p2->ip_len), srh_p2->hlen_wo_data(), p2len);

  WritablePacket *new_p = xor_encode(p1, p2);

  // now tack on encoding header in front
  new_p = new_p->push(sizeof(struct click_xor_header));
  struct click_xor_header *xorh = (struct click_xor_header *) new_p->data();

  xorh->_ether_type[0] = ethtype_p1;
  xorh->_ether_type[1] = ethtype_p2;

  xorh->_ipid[0] = ipid_p1;
  xorh->_ipid[1] = ipid_p2;

  xorh->_src[0] = src_p1;
  xorh->_src[1] = src_p2;

  xorh->_alias[0] = dst_p1;
  xorh->_alias[1] = dst_p2;

  p1len = p1len - sizeof(struct click_ether);
  p2len = p2len - sizeof(struct click_ether);

  /*
     xorh->_len[0] = p1len - 4;
     xorh->_len[1] = p2len - 4;
     */

  xorh->_len[0] = htons(p1len);
  xorh->_len[1] = htons(p2len);

  // add all the debug fields
  xorh->_dst[0] = ipdst_p1;
  xorh->_dst[1] = ipdst_p2;

  xorh->_tcp_sport[0] = sport_p1;
  xorh->_tcp_sport[1] = sport_p2;

  xorh->_tcp_dport[0] = dport_p1;
  xorh->_tcp_dport[1] = dport_p2;

  xorh->_tcp_seq[0] = seq_p1;
  xorh->_tcp_seq[1] = seq_p2;

  xorh->_tcp_ack[0] = ack_p1;
  xorh->_tcp_ack[1] = ack_p2;

  xorh->set_checksum();

  // tack on ether header
  new_p = new_p->push(sizeof(struct click_ether));
  struct click_ether *eth_h = (struct click_ether *)new_p->data();

  if (_fix_enc_dst) {
    memcpy(eth_h->ether_dhost, _enc_dst.data(), 6);
  } else {
    memcpy(eth_h->ether_dhost, ea_p1.data(), 6);