lookupiprouteron.cc

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

/*
 * lookupiprouteron.{cc,hh} -- element looks up next-hop address for NAT-RON
 * Alexander Yip
 *
 * Copyright (c) 2001 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 "lookupiprouteron.hh"
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <clicknet/tcp.h>
#include <click/string.hh>
#include <click/straccum.hh>
#include <click/bitvector.hh>

#define rtprintf if(0)printf
#define MEASURE_NATRON 0
#define MULTI_POLICY 1 

LookupIPRouteRON::LookupIPRouteRON() 
  : _expire_timer(expire_hook, (void *) this)
{
  add_input();
  _flow_table = new FlowTable();
  _dst_table  = new DstTable();
}

LookupIPRouteRON::~LookupIPRouteRON()
{
  delete(_flow_table);
  delete(_dst_table);
  _expire_timer.unschedule();
}

int
LookupIPRouteRON::configure(const Vector<String> &conf, ErrorHandler *errh)
{
  int n = noutputs();
  if (cp_va_parse(conf, this, errh,
		  cpOptional,
		  cpUnsigned, "number of ports", &n,
		  cpEnd) < 0)
    return -1;
  if (n < 1)
    return errh->error("number of ports must be at least 1");

  set_noutputs(n+1);
  set_ninputs(n+1);
  return 0;
}

int
LookupIPRouteRON::initialize(ErrorHandler *)
{
  /*
  _last_addr = IPAddress();
#ifdef IP_RT_CACHE2
  _last_addr2 = _last_addr;
#endif
  */
  _expire_timer.initialize(this);
  //_expire_timer.schedule_after_ms(EXPIRE_TIMEOUT_MS);

  return 0;
}

int
LookupIPRouteRON::myrandom(int x) {
  return (int) (x * ( (float)(random() & 0xfffe) / (float)(0xffff)));
}

void LookupIPRouteRON::policy_handle_syn(FlowTableEntry *flow, Packet *p, bool first_syn)
{
  int i;
  DstTableEntry *dst_entry;

  //click_chatter("handle syn");

  switch (flow->policy) {
  case POLICY_LOCAL: 
    flow->outgoing_port = 1;
    output(1).push(p);
    break;
  case POLICY_RANDOM:
    flow->outgoing_port = 1 + myrandom(noutputs()-1);
    click_chatter("Random(%d)", flow->outgoing_port);
    output(flow->outgoing_port).push(p);
    break;

  case POLICY_PROBE3:
    if (noutputs() - 1 < 3) {
      click_chatter("not enough output ports to choose from");
      assert(0);
    }      

    // Choose 3 random unique ports
    // TODO: optimize this. It's really dumb.
    if (first_syn) {
      click_chatter("noutputs: %d", noutputs());
      flow->probed_ports[0] = 1 + myrandom(noutputs()-1);
      fprintf(stderr," probing %d ", flow->probed_ports[0]);
      for (flow->probed_ports[1] = 1 + myrandom(noutputs()-1);
	   flow->probed_ports[1] == flow->probed_ports[0]; 
	   flow->probed_ports[1] = 1 + myrandom(noutputs()-1));
      fprintf(stderr,"%d ", flow->probed_ports[1]);
      
      for (flow->probed_ports[2] = 1 + myrandom(noutputs()-1);
	   (flow->probed_ports[2] == flow->probed_ports[0] || 
	    flow->probed_ports[2] == flow->probed_ports[1]);
	   flow->probed_ports[2] = 1 + myrandom(noutputs()-1));
      fprintf(stderr,"%d\n", flow->probed_ports[2]);
    }

    for(i=1; i<3; i++) { 
      if (Packet *q = p->clone())
	output(flow->probed_ports[i]).push(q);
    }
    output(flow->probed_ports[0]).push(p);
    break;

  case POLICY_PROBE3_LOCAL:
    if (noutputs() - 1 < 3) {
      click_chatter("not enough output ports to choose from");
      assert(0);
    }      

    // Choose 3 random unique ports
    // TODO: optimize this. It's really dumb.
    if (first_syn) {
      flow->probed_ports[0] = 1;
      fprintf(stderr," probing %d ", flow->probed_ports[0]);
      for (flow->probed_ports[1] = 1 + myrandom(noutputs()-1);
	   flow->probed_ports[1] == flow->probed_ports[0]; 
	   flow->probed_ports[1] = 1 + myrandom(noutputs()-1));
      fprintf(stderr,"%d ", flow->probed_ports[1]);
      
      for (flow->probed_ports[2] = 1 + myrandom(noutputs()-1);
	   (flow->probed_ports[2] == flow->probed_ports[0] || 
	    flow->probed_ports[2] == flow->probed_ports[1]);
	   flow->probed_ports[2] = 1 + myrandom(noutputs()-1));
      fprintf(stderr,"%d\n", flow->probed_ports[2]);
    }

    for(i=1; i<3; i++) { 
      if (Packet *q = p->clone())
	output(flow->probed_ports[i]).push(q);
    }
    output(flow->probed_ports[0]).push(p);
    break;

  case POLICY_PROBE_ALL:
    duplicate_pkt(p);
    break;

  case POLICY_PROBE3_UNPROBED:
    // create entry in dst table
    dst_entry = _dst_table->insert(p->dst_ip_anno(), 0);
    if (first_syn) {
      flow->saw_first_syn();

      // get best guess port (lowest rtt of recently probed paths)
      flow->probed_ports[0] = dst_entry->choose_fastest_port();

      // choose 2 unprobed paths
      flow->probed_ports[1] = 
	dst_entry->choose_least_recent_port(noutputs(), 
					    flow->probed_ports[0], 0);
      flow->probed_ports[2] = 
	dst_entry->choose_least_recent_port(noutputs(), 
					    flow->probed_ports[0], 
					    flow->probed_ports[1]);
    }

    // forward <p> to these three chosen paths
    fprintf(stderr," probing: %d ", flow->probed_ports[0]);
    for(i=1; i<3; i++) { 
      if (Packet *q = p->clone()) {
	fprintf(stderr,"%d ", flow->probed_ports[i]);
	dst_entry->sent_probe(flow->probed_ports[i]);
	output(flow->probed_ports[i]).push(q);
      }
    }
    fprintf(stderr,"\n");
    dst_entry->sent_probe(flow->probed_ports[0]);
    output(flow->probed_ports[0]).push(p);
    break;
    
  default:
    click_chatter("Unknown policy syn");
    assert(0);
    break;
  }
  return;
    
}

void
LookupIPRouteRON::policy_handle_synack(FlowTableEntry *flow, unsigned int port, Packet *p)
{
  struct timeval tv;
  DstTableEntry *dst_match;

  switch (flow->policy) {
  case POLICY_LOCAL:
  case POLICY_RANDOM:
    if (port == flow->outgoing_port) {
      flow->outstanding_syns = 0;
      output(0).push(p);
    } else { // Wrong incoming port: send reset
      send_rst(p, flow, port);
    }
    break;

  case POLICY_PROBE3:
  case POLICY_PROBE3_LOCAL:
    // if this is the first synack returned, choose this port
    if (flow->outstanding_syns > 0) {
      flow->outstanding_syns = 0;
      flow->outgoing_port = port;
    }

    if (port == flow->outgoing_port) {
      flow->outgoing_port = port;
      output(0).push(p);
    } else { // Wrong incoming port: send reset
      send_rst(p, flow, port);
    }
    break;

  case POLICY_PROBE_ALL:

    if (flow->outstanding_syns > 0) {
      click_chatter("FirstSyn(%d)", port);
      // dont save to dst_table
      // _dst_table->insert(IPAddress(p->ip_header()->ip_src), portno); 
      
      // remember which port the first syn-ack came back on
      flow->outgoing_port = port;
      flow->outstanding_syns = 0;
    }    

    if (flow->outgoing_port == port)
      output(0).push(p);
    else {
      // send RST to first replier
      send_rst(p, flow, port);
    }
    break;

  case POLICY_PROBE3_UNPROBED:
    // get DstTable entry for this IP target
    dst_match = _dst_table->lookup(IPAddress(p->ip_header()->ip_src), false);

    if (dst_match) {
      // If this is the first synack, save rtt for this synack on this port
      gettimeofday(&tv, NULL);
      dst_match->save_rtt(port, 
			  (tv.tv_usec - flow->first_syn_usec < 0) ? tv.tv_sec - flow->first_syn_sec - 1 : 
			  tv.tv_sec - flow->first_syn_sec,
			  (tv.tv_usec - flow->first_syn_usec < 0) 
			  ? tv.tv_usec - flow->first_syn_usec + 1000000 : 
			  tv.tv_usec - flow->first_syn_usec);
    } else { 
      click_chatter("Could not find match in dst_table! Will not save rtt info.");
      //_dst_table->insert(IPAddress(p->ip_header()->ip_src), port); 
    }


    // If this is the first synack, choose this port number
    if (flow->outstanding_syns > 0) {
      click_chatter("FirstSyn(%d)", port);
      // dont save to dst_table
      // _dst_table->insert(IPAddress(p->ip_header()->ip_src), portno); 
      
      // remember which port the first syn-ack came back on
      flow->outgoing_port = port;
      flow->outstanding_syns = 0;
    }    
    
    if (flow->outgoing_port == port)
      output(0).push(p);
    else {
      // send RST to first replier
      send_rst(p, flow, port);
    }

    
    break;
    
  default:
    click_chatter("Unknown policy synack");
    assert(0);
    break;
  }
  return;
}

void LookupIPRouteRON::duplicate_pkt(Packet *p) {
  // send <p> out on all outgoing ports except 0

  int n = noutputs();
  for (int i =1; i < n - 1; i++)
    if (Packet *q = p->clone())
      output(i).push(q);
  output(n - 1).push(p);
}

void LookupIPRouteRON::push_forward_syn(Packet *p) 
{
  // what to do in the case of a forward direction syn.
  FlowTableEntry *match = NULL;
  FlowTableEntry *new_entry = NULL;
  DstTableEntry  *dst_match = NULL;
  const click_ip  *iph = p->ip_header();
  const click_tcp *tcph= p->tcp_header();
  unsigned tcp_seq = ntohl(tcph->th_seq) + 
    ntohs(iph->ip_len) - (iph->ip_hl << 2) - (tcph->th_off << 2)+1;

  print_time("SAWSYN:");

  tcph = p->tcp_header();

  match = _flow_table->lookup(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(),
			      ntohs(tcph->th_sport), ntohs(tcph->th_dport));
  
  rtprintf ("FOR TCP SYN\n");

  if (match) {
    // Match found
    match->saw_forward_packet();
    
    if (match->is_pending()){
      rtprintf("FLOW match(pending), send PROBE\n");
      match->outstanding_syns++;
      
#if MULTI_POLICY
      // We're seeing retransmitted syns, let the policy handle it
      policy_handle_syn(match, p, false);
#else
      // retransmit SYN
      duplicate_pkt(p);
#endif
    } else {
      // this can happen if an identical flow is started before the last one
      // was removed from the flow table.
      click_chatter("FLOW match, port (%d) {%s}->{%s}", 
		    match->outgoing_port,
		    IPAddress(p->ip_header()->ip_src).s().cc(), 
		    p->dst_ip_anno().s().cc());
      return;
    }
      
  } else {
    // NO match, Look into Dst Table
    dst_match = _dst_table->lookup(p->dst_ip_anno(), true);
    
    // Add new entry to Flow Table
    new_entry = _flow_table->add(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(),
				 ntohs(tcph->th_sport), ntohs(tcph->th_dport),
				 click_jiffies(),tcp_seq);
    new_entry->saw_forward_packet();
      
    if (dst_match){
      new_entry->outgoing_port = dst_match->outgoing_port;
      click_chatter("DST match, port (%d) {%s}->{%s}", 
		    new_entry->outgoing_port,
		    IPAddress(p->ip_header()->ip_src).s().cc(), 
		    p->dst_ip_anno().s().cc() );
      output(new_entry->outgoing_port).push(p);
      return;
      
    } else {
      rtprintf("DST nomatch, send PROBE\n");
      new_entry->outgoing_port = 0;
      new_entry->outstanding_syns++;

#if MULTI_POLICY
      // We're seeing the first syn, choose policy
      new_entry->policy = myrandom(NUM_POLICIES);
      new_entry->policy = POLICY_PROBE_ALL;
      click_chatter("Policy(%d)", new_entry->policy);
      policy_handle_syn(new_entry, p, true);
#else
      duplicate_pkt(p);
#endif
    }
  }
  return;
}


void LookupIPRouteRON::push_forward_fin(Packet *p) 
{
  const click_tcp *tcph;
  FlowTableEntry *match = NULL;

  tcph = p->tcp_header();
  
  rtprintf("FOR TCP FIN\n");

  match = _flow_table->lookup(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(),
			      ntohs(tcph->th_sport), ntohs(tcph->th_dport));
  if (match) {
    if (!match->is_pending()) {
      rtprintf(" found non-pending match, ending forward connection\n");
      match->saw_forward_packet();
      match->forw_alive = 0; // forward flow is over
      output(match->outgoing_port).push(p);
      return;
    } 
  }
  rtprintf(" could not find non-pending match, killing pkt.\n");
  p->kill();
  return;
}

void LookupIPRouteRON::push_forward_rst(Packet *p) 
{
  const click_tcp *tcph;
  FlowTableEntry *match = NULL;

  tcph = p->tcp_header();
  rtprintf("FOR TCP RST\n");

  match = _flow_table->lookup(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(),
			      ntohs(tcph->th_sport), ntohs(tcph->th_dport));
  
  if (match) {
    if (!match->is_pending()) {
      rtprintf("found match, non-pending, forwarding...\n");
      match->saw_forward_packet();
      match->forw_alive = 0; // forward & reverse flows are over
      match->rev_alive = 0; 
      output(match->outgoing_port).push(p);
      return;
    }
  }
  
  rtprintf("could not find non-pending match. Killing packet\n");
  p->kill();
}

void LookupIPRouteRON::push_forward_normal(Packet *p) 
{
  // what to do in the case of a forward direction syn.
  const click_tcp *tcph;
  FlowTableEntry *match = NULL;

  tcph = p->tcp_header();

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

  match = _flow_table->lookup(IPAddress(p->ip_header()->ip_src), p->dst_ip_anno(),
			      ntohs(tcph->th_sport), ntohs(tcph->th_dport));
  
  if (match) {
    if (!match->is_pending()) {
      rtprintf("found match, not pending, forwarding...\n");
      match->saw_forward_packet();
      output(match->outgoing_port).push(p);
      return;
    }
  }
  
  rtprintf("could not find non-pending match. Killing packet\n");
  p->kill();

}

void LookupIPRouteRON::push_forward_packet(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(1).push(p);
    return;
  }

  // Switch on TCP packet type
  tcph = p->tcp_header();
  if (tcph->th_flags & TH_SYN) {
    push_forward_syn(p);
  } else if (tcph->th_flags & TH_FIN) {
    push_forward_fin(p);
  } else if (tcph->th_flags & TH_RST) {
    push_forward_rst(p);
  } else {
    push_forward_normal(p);
  }
  return;
}

void LookupIPRouteRON::push_reverse_synack(unsigned inport, Packet *p) 
{
  char buf[128];
  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));
  
  sprintf(buf, "REV TCP SYN-ACK inport(%d)", inport);
  print_time(buf);
  
  if (match) { 
    match->saw_reply_packet();
    
#if MULTI_POLICY
    policy_handle_synack(match, inport, p);
    return;
#else

    if (match->is_pending()) {
      click_chatter("FLOW match(pending), port(%d) {%s}->{%s}", 
	     inport, 
	     p->dst_ip_anno().s().cc(), 
	     IPAddress(p->ip_header()->ip_src).s().cc() );

      // save to dst_table
      _dst_table->insert(IPAddress(p->ip_header()->ip_src), inport); 
      // remember which port the first syn-ack came back on
      match->outgoing_port = inport;

      match->outstanding_syns = 0;
      output(0).push(p);
      return;

    } else {
      // FLOW not pending
      if (inport == match->outgoing_port){
	rtprintf("Correct return port, forwarding reverse SYN-ACK\n");
	output(0).push(p);
	return;
      } else {
	rtprintf("Incorrect return port, replying with RST\n");
	send_rst(p, match, inport);
	return;
      }    

    }
#endif
    
  } else {
    rtprintf("FLOW no match, killing SYN-ACK\n");
    p->kill();
  }

}
void LookupIPRouteRON::push_reverse_fin(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 FIN\n");

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

  rtprintf(" could not find non-pending match. Killing pkt.\n");
  p->kill();