flashflood.cc

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

/*
 * FlashFlood.{cc,hh} -- DSR implementation
 * John Bicket
 *
 * Copyright (c) 1999-2001 Massachusflashfloods 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 "flashflood.hh"
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <click/straccum.hh>
#include <clicknet/ether.h>
#include "srpacket.hh"
CLICK_DECLS


FlashFlood::FlashFlood()
  :  Element(2,2),
     _en(),
     _et(0),
     _link_table(0),
     _packets_originated(0),
     _packets_tx(0),
     _packets_rx(0)
{

  static unsigned char bcast_addr[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
  _bcast = EtherAddress(bcast_addr);
}

FlashFlood::~FlashFlood()
{
}

int
FlashFlood::configure (Vector<String> &conf, ErrorHandler *errh)
{
  int ret;
  _debug = false;
  _history = 100;
  _min_p = 50;
  _lossy = true;
  _threshold = 100;
  _neighbor_threshold = 66;
  _pick_slots = false;
  _slots_nweight = false;
  _slots_erx = false;
  _slot_time_ms = 15;
  _process_own_sends = false;

  ret = cp_va_parse(conf, this, errh,
                    cpKeywords,
		    "ETHTYPE", cpUnsigned, "Ethernet encapsulation type", &_et,
                    "IP", cpIPAddress, "IP address", &_ip,
                    "BCAST_IP", cpIPAddress, "IP address", &_bcast_ip,
		    "ETH", cpEtherAddress, "EtherAddress", &_en,
		    "LT", cpElement, "Linktable", &_link_table,
		    /* below not required */
		    "MIN_P", cpInteger, "Min P", &_min_p,
		    "DEBUG", cpBool, "Debug", &_debug,
		    "HISTORY", cpUnsigned, "history", &_history,
		    "LOSSY", cpBool, "mist", &_lossy,
		    "THRESHOLD", cpInteger, "Threshold", &_threshold,
		    "NEIGHBOR_THRESHOLD", cpInteger, "Neighbor Threshold", &_neighbor_threshold,
		    "PICK_SLOTS", cpBool, "Wait time selection", &_pick_slots,
		    "SLOTS_NEIGHBOR_WEIGHT", cpBool, "use max neighbor weight for slots", &_slots_nweight,
		    "SLOTS_EXPECTED_RX", cpBool, "foo", &_slots_erx,
		    "SLOT_TIME_MS", cpInteger, "time (in ms) for a slot", &_slot_time_ms,
		    "PROCESS_OWN_SENDS", cpBool, "foo", &_process_own_sends,
                    cpEnd);

  if (!_et) 
    return errh->error("ETHTYPE not specified");
  if (!_ip) 
    return errh->error("IP not specified");
  if (!_bcast_ip) 
    return errh->error("BCAST_IP not specified");
  if (!_en) 
    return errh->error("ETH not specified");
  if (_link_table == 0) 
    return errh->error("no LinkTable element specified");
  if (_link_table->cast("LinkTable") == 0)
    return errh->error("LinkTable element is not a LinkTable");

  if (_pick_slots && !(_slots_erx ^ _slots_nweight)) {
    return errh->error("One of SLOTS_NEIGHBOR_WEIGHT or SLOTS_EXPECTED_RX may be true");
  }

  if (_slot_time_ms < 0) {
    return errh->error("SLOT_TIME_MS must be positive\n");
  }
  return ret;
}

int
FlashFlood::initialize (ErrorHandler *)
{
  return 0;
}

FlashFlood::SeqProbMap *
FlashFlood::findmap(uint32_t seq) 
{
  int index = -1;
  for (int x = 0; x < _mappings.size(); x++) {
    if (_mappings[x]._seq == seq) {
      index = x;
      break;
    }
  }
  
  if (index == -1) {
    return 0;
  }
  return &_mappings[index];
}


bool
FlashFlood::get_prob(uint32_t seq, IPAddress src, int *p)
{
  if (!p) {
    click_chatter("%{element} error, seq %d p is null\n",
		  this,
		  seq);
    return false;
  }
  SeqProbMap *m = findmap(seq);
  if (!m) {
    click_chatter("%{element} error, couldn't find seq %d in get_prob\n",
		  this,
		  seq);
    return false;
  }

  int *p_ptr = m->_node_to_prob.findp(src);
  *p = (p_ptr) ? *p_ptr : 0;
  return true;
  
}

bool
FlashFlood::set_prob(uint32_t seq, IPAddress src, int p)
{
  SeqProbMap *m = findmap(seq);
  if (!m) {
    click_chatter("%{element} error, couldn't find seq %d in set_prob\n",
		  this,
		  seq);
    return false;
  }
  m->_node_to_prob.insert(src, p);
  return true;
}

int 
FlashFlood::expected_rx(uint32_t seq, IPAddress src) {


  SeqProbMap *m = findmap(seq);
  if (!m) {
    click_chatter("%{element} error, couldn't find seq %d in expected_rx\n",
		  this,
		  seq);
    return 0;

  }

  Vector<IPAddress> neighbors = _link_table->get_neighbors(src);
  int my_expected_rx = 0;
  
  for (int x = 0; x < neighbors.size(); x++) {
    if (neighbors[x] == src || neighbors[x] == _ip) {
      continue;
    }
    int *p_ever_ptr = m->_node_to_prob.findp(neighbors[x]);
    if (!p_ever_ptr) {
      m->_node_to_prob.insert(neighbors[x], 0);
      p_ever_ptr = m->_node_to_prob.findp(neighbors[x]);
    }
    int p_ever = *p_ever_ptr;
    if (p_ever > 100) {
      click_chatter("%{element} p_ever is %d\n",
		    this,
		    p_ever);
      sr_assert(false);
    }
    int metric = get_link_prob(src, neighbors[x]);
    int neighbor_expected_rx = ((100 - p_ever) * metric)/100;
    my_expected_rx += neighbor_expected_rx;
  }

  return my_expected_rx;
}


int 
FlashFlood::neighbor_weight(IPAddress src) {
  Vector<IPAddress> neighbors = _link_table->get_neighbors(src);
  int src_neighbor_weight = 0;
  
  for (int x = 0; x < neighbors.size(); x++) {
    int metric = get_link_prob(src, neighbors[x]);
    src_neighbor_weight += metric;
  }

  return src_neighbor_weight;
}

void
FlashFlood::forward(Broadcast *bcast) {
  
  int my_expected_rx = expected_rx(bcast->_seq, _ip);

  if (my_expected_rx < _threshold) {
    if (_debug) {
      click_chatter("%{element} seq %d my_expected_rx %d not_sending\n",
		    this,
		    bcast->_seq,
		    my_expected_rx);
    }

    bcast->_sent = true;
    bcast->_scheduled = false;
    bcast->del_timer();
    return;
  }
  if (_debug) {
    click_chatter("%{element} seq %d my_expected_rx %d sending\n",
		  this,
		  bcast->_seq,
		  my_expected_rx);
  }


  Packet *p_in = bcast->_p;
  click_ether *eh_in = (click_ether *) p_in->data();
  struct srpacket *pk_in = (struct srpacket *) (eh_in+1);

  int hops = 1;
  int len = 0;
  if (bcast->_originated) {
    hops = 1;
    len = srpacket::len_with_data(hops, p_in->length());
  } else {
    hops = pk_in->num_links() + 1;
    len = srpacket::len_with_data(hops, pk_in->data_len());
  }

  WritablePacket *p = Packet::make(len + sizeof(click_ether));
  if (p == 0)
    return;

  click_ether *eh = (click_ether *) p->data();
  struct srpacket *pk = (struct srpacket *) (eh+1);

  memset(pk, '\0', len);

  pk->_version = _sr_version;
  pk->_type = PT_DATA;
  pk->_flags = 0;
  pk->_qdst = _bcast_ip;
  pk->set_num_links(hops);
  for (int x = 0; x < hops; x++) {
    pk->set_link_node(x, pk_in->get_link_node(x));
    //pk->set_hop_seq(x, 0);
  }

  pk->set_link_node(hops,_ip);
  pk->set_next(hops);
  pk->set_seq(bcast->_seq);
  uint32_t link_seq = random();
  pk->set_seq2(link_seq);
  //pk->set_hop_seq(hops - 1, link_seq);
  bcast->_sent_seq.push_back(link_seq);

  if (bcast->_originated) {
    memcpy(pk->data(), p_in->data(), p_in->length());
    pk->set_data_len(p_in->length());

  } else {
    memcpy(pk->data(), pk_in->data(), pk_in->data_len());
    pk->set_data_len(pk_in->data_len());
  }
  
  eh->ether_type = htons(_et);
  memcpy(eh->ether_shost, _en.data(), 6);
  memset(eh->ether_dhost, 0xff, 6);


  bcast->_sent = true;
  bcast->_scheduled = false;
  bcast->_num_tx++;
  _packets_tx++;
  bcast->del_timer();


  if (_process_own_sends) {
    Packet *p_copy = p->clone();
    /* now let ourselves know we sent a packet */
    process_packet(p_copy); 
  } else {
    update_probs(bcast->_seq, link_seq, _ip);
  }
  output(0).push(p);
}

void
FlashFlood::forward_hook() 
{
    Timestamp now = Timestamp::now();
    for (int x = 0; x < _packets.size(); x++) {
	if (_packets[x]._to_send <= now) {
	    /* this timer has expired */
	    if (!_packets[x]._sent && _packets[x]._scheduled) {
		/* we haven't sent this packet yet */
		forward(&_packets[x]);
	    }
	}
    }
}


void
FlashFlood::trim_packets() {
  /* only keep track of the last _max_packets */
  while ((_packets.size() > _history)) {
    /* unschedule and remove packet*/
    if (_debug) {
      click_chatter("%{element} removing packet seq %d\n",
		    this,
		    _packets[0]._seq);
    }
    _packets[0].del_timer();
    if (_packets[0]._p) {
      _packets[0]._p->kill();
    }
    _packets.pop_front();
  }

  while ((_mappings.size() > _history)) {
    /* unschedule and remove packet*/
      click_chatter("%{element} removing mapping seq %d\n",
		    this,
		    _mappings[0]._seq);
    _mappings.pop_front();
  }
}

void
FlashFlood::push(int port, Packet *p_in)
{
  struct timeval now;
  click_gettimeofday(&now);
  
  if (port == 1) {
    start_flood(p_in);
  } else {
    process_packet(p_in);
  }
  trim_packets();

}

void 
FlashFlood::start_flood(Packet *p_in) 
{
  _packets_originated++;
  /* from me */
  int seq = random();
  
  int map_index = _mappings.size();
  _mappings.push_back(SeqProbMap());
  _mappings[map_index]._seq = seq;
  
  
  int bcast_index = _packets.size();
  _packets.push_back(Broadcast());
  _packets[bcast_index]._seq = seq;
  _packets[bcast_index]._originated = true;
  _packets[bcast_index]._p = p_in;
  _packets[bcast_index]._num_rx = 0;
  _packets[bcast_index]._num_tx = 0;
  _packets[bcast_index]._first_rx = Timestamp::now();
  _packets[bcast_index]._actual_first_rx = true;
  _packets[bcast_index]._sent = false;
  _packets[bcast_index]._scheduled = false;
  _packets[bcast_index].t = NULL;
  _packets[bcast_index]._to_send = _packets[bcast_index]._first_rx;
  forward(&_packets[bcast_index]);
  
}
void
FlashFlood::process_packet(Packet *p_in) 
{
    _packets_rx++;

    click_ether *eh = (click_ether *) p_in->data();
    struct srpacket *pk = (struct srpacket *) (eh+1);
    uint32_t seq = pk->seq();
    uint32_t link_seq = pk->seq2();
    IPAddress src = pk->get_link_node(pk->num_links() - 1);

    Timestamp now = Timestamp::now();

    int map_index = -1;
    for (int x = 0; x < _mappings.size(); x++) {
      if (_mappings[x]._seq == seq) {
	map_index = x;
	break;
      }
    }

    bool seen_seq_before = false;
    if (map_index == - 1) {
      map_index = _mappings.size();
      _mappings.push_back(SeqProbMap());
      _mappings[map_index]._seq = seq;
    }


    int bcast_index = -1;
    for (int x = 0; x < _packets.size(); x++) {
      if (_packets[x]._seq == seq) {
	seen_seq_before = true;
	if (_packets[x]._scheduled) {
	  bcast_index = x;
	  break;
	}
      }
    }

    for (int x = 0; x < pk->num_links(); x++) {
      //IPAddress prev_src = pk->get_hop(x);
      //uint32_t prev_link_seq = pk->get_hop_seq(x);
      //update_probs(seq, prev_link_seq, prev_src);
    }
    update_probs(seq, link_seq, src);