snooptcp.cc

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

/*
 * snooptcp.{cc,hh} -- element implements Snoop TCP a la Balakrishnan
 * Alex Snoeren, Eddie Kohler
 *
 * Copyright (c) 1999-2000 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>
#ifdef __linux__
# define _BSD_SOURCE
#endif
#include "snooptcp.hh"
#include <click/ipaddress.hh>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <click/bitvector.hh>
#ifdef DEBUG
# define DEBUG_CHATTER(args...) click_chatter(args)
#else
# define DEBUG_CHATTER(args...) /* nothing */
#endif
CLICK_DECLS

SnoopTCP::SnoopTCP()
  : Element(2, 4)
{
}

SnoopTCP::~SnoopTCP()
{
}

int
SnoopTCP::initialize(ErrorHandler *errh)
{
  return errh->error("SnoopTCP is not ready to use");
}


inline void
SnoopTCP::SCacheEntry::clear()
{
  assert(packet);
  packet->kill();
  packet = 0;
}


SnoopTCP::PCB::PCB()
  : _head(0), _tail(0), _s_exists(0), _s_alive(0), _mh_exists(0), _mh_alive(0)
{
}

SnoopTCP::PCB::~PCB()
{
  for (int i = _tail; i != _head; i = next_i(i))
    _s_cache[i].packet->kill();
}

void
SnoopTCP::PCB::clear(bool is_s)
{
  if (is_s && _s_exists) {
    // XXX untimeout
    for (int i = _tail; i != _head; i = next_i(i))
      _s_cache[i].packet->kill();
    _head = _tail = 0;
    // XXX if (!_mh_alive) clear(false);
    _s_exists = _s_alive = false;
  } else if (!is_s && _mh_exists) {
    _mh_exists = _mh_alive = false;
  }
  // XXX remove from hashtable
}

void
SnoopTCP::PCB::initialize(bool is_s, const click_tcp *tcph, int datalen)
{
  unsigned seq = ntohl(tcph->th_seq);
  
  if (is_s) {
    assert(!_s_exists);
    _s_exists = _s_alive = true;
    //cs->alloc = 0;
    _s_max = seq + datalen;	// replaces cs->last_seen
    _mh_last_ack = seq - 1;
    _mh_expected_dup_acks = 0;
    _mh_dup_acks = 0;
    //cs->iss = seq;     
    //cs->expected_next_ack = cs->buftail;
    //if (tcpip_hdr->ti_flags & TH_ACK)
    //cs->wl_last_ack = ack;
    /* 
     * Ideally, this should be initialized to the rtt estimate 
     * from another connection to the same destination, if one 
     * exists. For now, choose an uninformed and conservative 
     * default.
     */
    //cs->srtt = SNOOP_RTTDEFAULT;
    //cs->rttdev = SNOOP_RTTDEVDEFAULT;
    //cs->timeout_pending = 0;
  } else {
    _mh_exists = _mh_alive = true;
  }
}

void
SnoopTCP::PCB::clean(unsigned ack, struct timeval *last_cleaned_time)
{
  //snoop_untimeout(cs);
  timerclear(last_cleaned_time);
  
  int i = _tail;
  while (i != _head && SEQ_LEQ(_s_cache[i].seq + _s_cache[i].size, ack)) {
    SCacheEntry &cache = _s_cache[i];
    if (timercmp(&cache.snd_time, last_cleaned_time, >))
      *last_cleaned_time = cache.snd_time;
    cache.clear();
    i = next_i(i);
  }
  _tail = i;
  
  // if (_head != _tail) snoop_timeout(cs);
}


void
SnoopTCP::PCB::s_ack(Packet *, const click_tcp *, int)
{
  // XXX rest
}


Packet *
SnoopTCP::PCB::s_data(Packet *p, const click_tcp *tcph, int datalen)
{
  // initialize if no connection (half-duplex, or Snoop came up in the middle
  // of a connection). always mark the connection alive
  if (!_s_exists)
    initialize(true, tcph, datalen);
  else
    _s_alive = true;
  
  bool full = next_i(_head) == _tail;
  int entry = -1;
  bool in_sequence = false;
  bool repeat_packet = false;
  unsigned seq = ntohl(tcph->th_seq);
  
  // insert the packet into the cache
  if (SEQ_GEQ(seq, _s_max)) {
    // common case
    // don't save packet if over high water mark
    // (at that point cache is reserved for earlier packets)
    if (s_cache_size() >= S_CACHE_HIGHWATER) return p;
    _s_max = seq + datalen;
    entry = _head;
    _head = next_i(_head);
    in_sequence = true;
    
  } else {
    for (int i = _tail; i != _head; i = next_i(i))
      if (_s_cache[i].seq == seq) {
	// a repeat packet
	// always keep the repeat (Hari does). an alternative would be
	// to keep the longer of the two
	_s_cache[i].packet->kill();
	repeat_packet = true;
	entry = i;
	break;
	
      } else if (SEQ_GT(_s_cache[i].seq, seq)) {
	// out-of-order packet
	if (full) return p;
	// XXX memmove??
	for (int j = _tail; j != i; j = next_i(j))
	  _s_cache[prev_i(j)] = _s_cache[j];
	entry = prev_i(i);
	_tail = prev_i(_tail);
	break;
      }
  }
  
  // cache packet at `_cache[entry]'
  assert(entry >= 0 && 0);
  _s_cache[entry].packet = p->clone();
  _s_cache[entry].seq = seq;
  _s_cache[entry].num_rxmit = 0;
  // mark as sender retransmission if it really was (we had cached the packet
  // before), or it was before all cached packets
  if (repeat_packet || (!in_sequence && entry == _tail))
    _s_cache[entry].sender_rxmit = 1;
  else
    _s_cache[entry].sender_rxmit = 0;
  click_gettimeofday(&_s_cache[entry].snd_time);
  DEBUG_CHATTER("\t%d at %d\n", seq, entry);
  
  // XXX if (!in_sequence) snoop_untimeout();
  // XXX snoop_timeout();
  
  return p;
}



void
SnoopTCP::PCB::mh_new_ack(unsigned ack)
{
  int old_tail = -1;
  if (_tail != _head && _s_cache[_tail].num_rxmit)
    old_tail = _tail;
  
  struct timeval last_cleaned_time;
  clean(ack, &last_cleaned_time);
  
  //if ((cs->wi_state & SNOOP_RTTFLAG) && timerisset(&sndtime))
  //snoop_rtt(cs, &sndtime);
  
  // check for burst loss
  if (old_tail >= 0 && s_cache_size() > 1 && next_i(old_tail) == _tail
      && _s_cache[_tail].num_rxmit == 0)
    //snoop_rexmt_pkt(cs, packet, 
    //IPTOS_LOWDELAY|IPTOS_RELIABILITY|
    //IPTOS_THROUGHPUT);
    /* do nothing */;
  
  //cs->wi_state |= SNOOP_RTTFLAG;
  _mh_expected_dup_acks = 0;
  _mh_dup_acks = 0;
  _mh_last_ack = ack;
}

#define SNOOP_RTX_THRESH 1

Packet *
SnoopTCP::PCB::mh_dup_ack(Packet *p, const click_tcp *tcph, unsigned ack)
{
  // if snoop cache empty, nothing to do
  if (_head == _tail)
    return p;
  
  // window change advertisements are not semantically duplicate acks
  if (_mh_last_win != ntohs(tcph->th_win))
    return p;
  
  // if we don't have the packet, nothing to do
  SCacheEntry &cache = _s_cache[_tail];
  if (SEQ_LT(ack, cache.seq))
    return p;
  
  // if sender retransmission, nothing to do
  if (cache.sender_rxmit)
    return p;
  
  // otherwise, a duplicate ack we can handle
  _mh_dup_acks++;
  
  if (_mh_dup_acks <= SNOOP_RTX_THRESH) {
    // ignore first SNOOP_RTX_THRESH duplicate acks
    p->kill();
    return 0;
    
  } else if (_mh_dup_acks == SNOOP_RTX_THRESH + 1) {
    // the SNOOP_RTX_THRESHth duplicate ack: calculate how many were
    // expected, generate a retransmission
    _mh_expected_dup_acks = s_cache_size() - _mh_dup_acks;
    if (!cache.num_rxmit)
      /*snoop_rexmt_pkt(cs, packet, IPTOS_LOWDELAY)*/;
    p->kill();
    return 0;
    
  } else if (_mh_dup_acks < _mh_expected_dup_acks) {
    // delete expected duplicate acks
    p->kill();
    return 0;
    
  } else {
    // too many duplicate acks; retransmit last packet once, then start
    // letting duplicate acks pass through
    // XXX COMPAT some changes here
    if (cache.num_rxmit < 2) {
      //snoop_rexmt_pkt(cs, packet, IPTOS_LOWDELAY|IPTOS_RELIABILITY|IPTOS_THROUGHPUT);
      p->kill();
      return 0;
    } else
      return p;
  }
}

Packet *
SnoopTCP::PCB::mh_ack(Packet *p, const click_tcp *tcph, int datalen)
{
  // if server connection is dead, do nothing
  if (!_s_exists)
    return p;
  
  unsigned ack = ntohl(tcph->th_ack);
  if (SEQ_GT(ack, _mh_last_ack))
    // new ack
    mh_new_ack(ack);