lookupiprouteron.cc

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

}
void LookupIPRouteRON::push_reverse_rst(Packet *p) 
{
  const click_tcp *tcph;
  FlowTableEntry *match = NULL;
  tcph = p->tcp_header();
  match = _flow_table->lookup(p->dst_ip_anno(),IPAddress(p->ip_header()->ip_src),
			      ntohs(tcph->th_dport), ntohs(tcph->th_sport));
  
  rtprintf("REV TCP RST\n");

  if (match) {
    if (!match->is_pending()) {
      rtprintf(" found match, not pending, ending reverse direction\n");
      match->saw_reply_packet();
      match->forw_alive = 0;
      match->rev_alive = 0;
      output(0).push(p);
      return;
    }
  }

  rtprintf(" could not find non-pending match. Killing pkt.\n");
  p->kill();
}
void LookupIPRouteRON::push_reverse_normal(Packet *p) 
{
  const click_tcp *tcph;
  FlowTableEntry *match = NULL;
  tcph = p->tcp_header();
 
  match = _flow_table->lookup(p->dst_ip_anno(),IPAddress(p->ip_header()->ip_src),
			      ntohs(tcph->th_dport), ntohs(tcph->th_sport));

  rtprintf("REV TCP normal pkt\n");

  if (match) {
    if (!match->is_pending()) {
      rtprintf("found match, not pending, forwarding...\n");
      match->saw_reply_packet();
      output(0).push(p);
      return;
    }
  }
  
  rtprintf("could not find non-pending match. Killing packet\n");
  p->kill();
}


void LookupIPRouteRON::push_reverse_packet(int inport, Packet *p) 
{
  const click_tcp *tcph;

  // if non-TCP just forward direct 
  // (YIPAL: perhaps this could be more intelligent)
  if (p->ip_header()->ip_p != IP_PROTO_TCP) {
    rtprintf("non-TCP proto(%d)\n", p->ip_header()->ip_p);
    output(0).push(p);
    return;
  }

  // Switch on TCP packet type
  tcph = p->tcp_header();
  if ((tcph->th_flags & TH_SYN) && (tcph->th_flags & TH_ACK)) {
    push_reverse_synack(inport, p);
  } else if (tcph->th_flags & TH_FIN) {
    push_reverse_fin(p);
  } else if (tcph->th_flags & TH_RST) {
    push_reverse_rst(p);
  } else {
    push_reverse_normal(p);
  }
  return;
}

void
LookupIPRouteRON::push(int inport, Packet *p)
{
  //click_tcp *tcph;
  //FlowTableEntry *e;
  //int matchState;

  if (inport == 0) {
    push_forward_packet(p);
  } else {
    push_reverse_packet(inport, p);
  }

  /*
  //// ---- TEST CODE -----  
  rtprintf("adding address to table(%u): \n", click_jiffies());
  tcph = p->tcp_header();
  
  _t->add(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(), 
	  ntohs(tcph->th_sport), ntohs(tcph->th_dport), 10, 
	  11, 12, click_jiffies(), 1, 1, 1);

  _t->print();
  //_t->del(IPAddress("1.1.1.1"));
  //_t->print();  
  matchState = _t->lookup(IPAddress("18.7.0.12"), IPAddress("18.239.0.139"), 
			  80, 1410, &e);
  
  if (e)
    rtprintf("match type(%d) ports %u -> %u\n",matchState, e->sport, e->dport);
  else
    rtprintf("no match\n");
  */

  
#ifdef 0
  _flow_table->print();  
  _dst_table->print();
  rtprintf("\n");
#endif
}

void LookupIPRouteRON::send_rst(Packet *p, FlowTableEntry *match, int outport) {
  WritablePacket *rst_pkt;
  click_ip *iphdr;
  click_tcp *tcphdr;

  rst_pkt = WritablePacket::make(40);
  rst_pkt->set_network_header(rst_pkt->data(), 20);
  iphdr  = rst_pkt->ip_header();
  tcphdr = rst_pkt->tcp_header();

  tcphdr->th_sport = p->tcp_header()->th_dport;	
  tcphdr->th_dport = p->tcp_header()->th_sport;
  tcphdr->th_seq   = htonl(match->syn_seq);
  tcphdr->th_ack   = htonl(ntohl(p->tcp_header()->th_seq) + 1);
  tcphdr->th_off   = 5;
  tcphdr->th_flags  = TH_RST | TH_ACK;
  tcphdr->th_win   = ntohs(16384);
  tcphdr->th_urp   = 0;
  tcphdr->th_sum   = 0;
	
  memset(iphdr, '\0', 9);
  iphdr->ip_sum = 0;
  iphdr->ip_len = htons(20);
  iphdr->ip_p   = IP_PROTO_TCP;
  iphdr->ip_src = p->ip_header()->ip_dst;
  iphdr->ip_dst = p->ip_header()->ip_src;

  //set tcp checksum
  tcphdr->th_sum = click_in_cksum((unsigned char *)iphdr, 40);
  iphdr->ip_len = htons(40);

  iphdr->ip_v   = 4;
  iphdr->ip_hl  = 5;
  iphdr->ip_id  = htons(0x1234);
  iphdr->ip_off = 0; 
  iphdr->ip_ttl = 32;
  iphdr->ip_sum = 0;

  // set ip checksum
  iphdr->ip_sum = click_in_cksum(rst_pkt->data(), 20);

  p->kill();
  output(outport).push(rst_pkt);
  return;
}

void LookupIPRouteRON::expire_hook(Timer *, void *thunk) 
{
  /*
  Packet *p;
  Vector<FlowTableEntry*> syn_waiting;
  LookupIPRouteRON *rt = (LookupIPRouteRON *) thunk;
  */
}

static String
read_handler(Element *, void *)
{
  return "false\n";
}

void
LookupIPRouteRON::add_handlers()
{
  // needed for QuitWatcher
  add_read_handler("scheduled", read_handler, 0);
}


// ------ FlowTable methods -------
LookupIPRouteRON::FlowTable::FlowTable() {
  _last_entry = NULL;

}

LookupIPRouteRON::FlowTable::~FlowTable() {
}

void
LookupIPRouteRON::FlowTableEntry::saw_first_syn() 
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  first_syn_sec = tv.tv_sec;
  first_syn_usec = tv.tv_usec;
}

LookupIPRouteRON::FlowTableEntry *
LookupIPRouteRON::FlowTable::lookup(IPAddress src, IPAddress dst,
				    unsigned short sport, unsigned short dport){
  rtprintf("LOOKUP: %d.%d.%d.%d(%d) -> %d.%d.%d.%d(%d)\n",
	   src.data()[0], src.data()[1], src.data()[2], src.data()[3], sport,
	   dst.data()[0], dst.data()[1], dst.data()[2], dst.data()[3], dport);

  // check cache first
  if (_last_entry && _last_entry->is_valid() && 
      (_last_entry->src   == src) && 
      (_last_entry->dst   == dst) && 
      (_last_entry->sport == sport) && 
      (_last_entry->dport == dport)) {
    return _last_entry;
  }

  // find a valid match
  for (int i = 0; i < _v.size(); i++){
    
    if (_v[i].is_valid() && 
	(src == _v[i].src) && (dst == _v[i].dst) && 
	(sport == _v[i].sport) && (dport == _v[i].dport)) {

	// exact match is found
      _last_entry = &_v[i]; // cache this match
      return &_v[i];
    }
  }
  // no match found
  return 0;
}

LookupIPRouteRON::FlowTableEntry*
LookupIPRouteRON::FlowTable::add(IPAddress src, IPAddress dst, 
				 unsigned short sport, unsigned short dport, 
				 unsigned probe_time, unsigned syn_seq) {

  FlowTableEntry e;
  e.src = src;
  e.dst = dst;
  e.sport = sport;
  e.dport = dport;
  e.outgoing_port = 0;
  e.oldest_unanswered = 0;
  e.last_reply = 0; 
  e.forw_alive = 1;
  e.rev_alive = 1;
  e.outstanding_syns = 0;
  e.probe_time = probe_time;
  e.syn_seq = syn_seq;
  //e.clear_waiting();

  // replace duplicate entry first
  for (int i = 0; i < _v.size(); i++)
    if ((src == _v[i].src) && (dst == _v[i].dst) && 
	(sport == _v[i].sport) && (dport == _v[i].dport)) {
      _v[i] = e;
      rtprintf("  replacing existing entry in table\n");
      return &_v[i];
    }

  // replace invalid entries
  for (int i = 0; i < _v.size(); i++)
    if (!_v[i].is_valid() || (!_v[i].is_active() && _v[i].is_old()) ) {
      _v[i] = e;
      rtprintf("  replacing invalid entry in table\n");
      return &_v[i];
    }

  // just push new entry onto back of table.
  rtprintf("  adding new entry to table\n");
  _v.push_back(e);
  return &_v[_v.size()-1];

}

void 
LookupIPRouteRON::FlowTable::del(IPAddress src, IPAddress dst, 
				 unsigned short sport, unsigned short dport){
  // find a match
  for (int i = 0; i < _v.size(); i++){
    
    if ( (src == _v[i].src) && (dst == _v[i].dst) && 
	 (sport == _v[i].sport) && (dport == _v[i].dport)) {
      // exact match is found
      _v[i].dst = IPAddress(1);
      _v[i].forw_alive = 0;
      _v[i].rev_alive  = 0;
      _v[i].invalidate(); // this "deletes" the entry
      return;
    }
  }
}

void
LookupIPRouteRON::FlowTable::print() {
  rtprintf("  Table contents size(%d):\n", _v.size());
  for (int i = 0; i < _v.size(); i++) {
    if (_v[i].is_valid()) {
      //rtprintf( "    [%d] %02x%02x%02x%02x(%u) -> %02x%02x%02x%02x(%u) ",
      rtprintf( "    [%d] %d.%d.%d.%d(%u) -> %d.%d.%d.%d(%u) \t",
	      //_v[i].get_state(),
	      0,
	      _v[i].src.data()[0],_v[i].src.data()[1], 
	      _v[i].src.data()[2],_v[i].src.data()[3],
	      _v[i].sport,

	      _v[i].dst.data()[0],_v[i].dst.data()[1], 
	      _v[i].dst.data()[2],_v[i].dst.data()[3],
	      _v[i].dport);
      rtprintf("outport(%d) pending(%d) waiting(%d) \tage(%u) FR = %d%d\n", 
	     _v[i].outgoing_port, _v[i].outstanding_syns,
	     //_v[i].waiting.size(), 
	     0,
	     _v[i].get_age(), 	     
	     _v[i].forw_alive, _v[i].rev_alive);

      //if (_v[i].get_state() == FlowTableEntry::INVALID) exit(0);
    }
  }
}

LookupIPRouteRON::DstTable::DstTable() {
  _last_entry = NULL;
}
LookupIPRouteRON::DstTable::~DstTable() {
}

LookupIPRouteRON::DstTableEntry*
LookupIPRouteRON::DstTable::lookup(IPAddress dst, bool only_valid) {

  // check cache first.
  if (_last_entry && 
      (!only_valid || _last_entry->is_valid()) &&
      _last_entry->is_recent() &&
      _last_entry->dst == dst) {
    return _last_entry;
  }

  // search
  for(int i=0; i<_v.size(); i++) {
    if ((!only_valid || _v[i].is_valid()) &&
	_v[i].is_recent() &&
	_v[i].dst == dst) {
      
      _last_entry = &_v[i]; // cache last match
      return &_v[i];
    }
  }
  return 0;
}

LookupIPRouteRON::DstTableEntry*
LookupIPRouteRON::DstTable::insert(IPAddress dst, unsigned short assigned_port) {
  int replaceme = -1;
  struct LookupIPRouteRON::DstTableEntry::ProbeInfo *p, *tp;
  DstTableEntry e;

  for(int i=0; i<_v.size(); i++) {
    if (_v[i].dst == dst) {
      _v[i].outgoing_port = assigned_port;
      _v[i].probe_time = click_jiffies();
      return &_v[i];
    }
    if (!_v[i].is_recent()) {
      replaceme = i;
    }
  }
  
  if (replaceme != -1) {
    _v[replaceme].dst = dst;
    _v[replaceme].outgoing_port = assigned_port;
    _v[replaceme].probe_time = click_jiffies();
    for(p = _v[replaceme].probes; p != NULL;) {
      tp = p->next;
      free(p);
      p = tp;
    }
    _v[replaceme].probes = NULL;
    return &_v[replaceme];
  }
  
  e.dst = dst;
  e.outgoing_port = assigned_port;
  e.probe_time = click_jiffies();
  e.probes = NULL;
  _v.push_back(e);
  return &_v.back();
}

void
LookupIPRouteRON::DstTable::print() {
  rtprintf("DST Table Contents(%d)\n", _v.size());
  for(int i=0; i<_v.size(); i++) {
    rtprintf("  %d.%d.%d.%d \t port(%d) valid(%d) recent(%d)\n", 
	     _v[i].dst.data()[0], _v[i].dst.data()[1], 
	     _v[i].dst.data()[2], _v[i].dst.data()[3], 
	     _v[i].outgoing_port, _v[i].is_valid(), _v[i].is_recent());
  }
}

void
LookupIPRouteRON::DstTableEntry::add_probe_info(int port, long rtt_sec, long rtt_usec)
{
  struct timeval tv;
  struct ProbeInfo *p, *prev = NULL;

  gettimeofday(&tv, NULL);

  for(p = probes; p != NULL; p = p->next) {
    if (p->port_number == port)
      break;
    prev = p;
  }

  if (p != NULL) {
    if (prev) { // move to front
      prev->next = p->next;
      p->next = probes;
      probes = p;
    } 
  
  } else { // create new probe info and place it at the front
    p = (struct ProbeInfo *) malloc(sizeof (struct ProbeInfo));
    p->next = probes;
  }

  p->rtt_sec  = rtt_sec;
  p->rtt_usec = rtt_usec;
  p->last_probe_time = tv.tv_sec;
}

void
LookupIPRouteRON::DstTableEntry::sent_probe(int port) 
{
  struct ProbeInfo *p, *prev = NULL;
  struct timeval tv;
  gettimeofday(&tv, NULL);

  for(p = probes; p != NULL; p = p->next) {
    if (p->port_number == port) {
      p->last_probe_time = tv.tv_sec;
      p->rtt_sec = 0xffff;
      p->rtt_usec = 0xffff;
      p->first_syn = true;
      if (prev) {
	prev->next = p->next;
	p->next = probes;
	probes = p;
      }
      
      return;
    }
    prev = p;
  }

  //click_chatter("creating new ProbeInfo in sent_probe");
  p = (struct ProbeInfo *) malloc(sizeof (struct ProbeInfo));
  p->port_number = port;
  p->last_probe_time = tv.tv_sec;
  p->rtt_sec = 0xffff;
  p->rtt_usec = 0xffff;
  p->first_syn = true;

  p->next = probes;
  probes = p;
  return;
}

void
LookupIPRouteRON::DstTableEntry::save_rtt(int port, long sec, long usec)
{
  struct ProbeInfo *p;

  for(p = probes; p != NULL; p = p->next) {
    //click_chatter("checking port %d to %d", p->port_number, port);
    if (p->port_number == port) {
      if (p->first_syn) {
	p->rtt_sec = sec;
	p->rtt_usec = usec;
	p->first_syn = false;
      }
      return;
    }
  }

  click_chatter("creating new ProbeInfo in save_rtt: THIS SHOULD NOT HAPPEN");
  assert(0);
  /*
  p = (struct ProbeInfo *) malloc(sizeof (struct ProbeInfo));
  p->port_number = port;
  p->last_probe_time = tv.tv_sec;
  p->rtt_sec = sec;
  p->rtt_usec = usec;

  p->next = probes;
  probes = p;
  */
  return;
}

int 
LookupIPRouteRON::DstTableEntry::choose_fastest_port() 
{
  struct ProbeInfo *p;
  int port = 1;
  unsigned long fastest_sec = 0xffffffff, fastest_usec = 0xffffffff;

  click_chatter("rtt table");
  for(p = probes; p != NULL; p = p->next)
    click_chatter(" port %d %06d.%06d", p->port_number, p->rtt_sec, p->rtt_usec);

  for(p = probes; p != NULL; p = p->next) {
    if ( ((p->rtt_sec <= fastest_sec) && (p->rtt_usec < fastest_usec)) ||
	 (p->rtt_sec < fastest_sec)) {
      fastest_sec = p->rtt_sec;
      fastest_usec = p->rtt_usec;
      port = p->port_number;
      continue;
    }
  }
  return port; 
}

int 
LookupIPRouteRON::DstTableEntry::choose_least_recent_port(int noutputs, int not1, int not2)
{
  int last_used = 0;
  int matches=0, i, q;
  struct ProbeInfo *p;
  Bitvector bv(noutputs - 1);
  bv.clear();

  if (not1 > 0) {
    bv[not1-1] = true;
    matches++;
  }
  if (not2 > 0) {
    bv[not2-1] = true;
    matches++;
  }
    
  for(p = probes; p != NULL; p = p->next) {
    if (p->port_number != not1 && p->port_number != not2) {
      last_used = p->port_number;
      matches++;
    }
    bv[p->port_number - 1] = true;
  }

  if (matches == noutputs - 1)
    return last_used;

  q = LookupIPRouteRON::myrandom(noutputs - 1 - matches); // randomly choose port
  for(i=0; i<bv.size(); i++) {
    if ( !bv[i] && (not1-1 != i) && (not2-1 != i) ){
      if (!q)
	break;
      else
	q--;
    }
  }
  
  return i+1;
}

void 
LookupIPRouteRON::print_time(char* s) {
  struct timeval tp;
  gettimeofday(&tp, NULL);
  click_chatter("%s (%ld.%06ld)", s, tp.tv_sec & 0xffff, tp.tv_usec);
}


// generate Vector template instance
#include <click/vector.cc>
// must always generate the whole instance! LookupIPRoute demands it
template class Vector<LookupIPRouteRON::FlowTableEntry>;


EXPORT_ELEMENT(LookupIPRouteRON)