ecnprobe/history.c

   1 /*
   2  Copyright (c) 2000
   3  International Computer Science Institute
   4  All rights reserved.
   5
   6  This file may contain software code originally developed for the
   7  Sting project. The Sting software carries the following copyright:
   8
   9  Copyright (c) 1998, 1999
  10  Stefan Savage and the University of Washington.
  11  All rights reserved.
  12
  13  Redistribution and use in source and binary forms, with or without
  14  modification, are permitted provided that the following conditions
  15  are met:
  16  1. Redistributions of source code must retain the above copyright
  17     notice, this list of conditions and the following disclaimer.
  18  2. Redistributions in binary form must reproduce the above copyright
  19     notice, this list of conditions and the following disclaimer in the
  20     documentation and/or other materials provided with the distribution.
  21  3. All advertising materials mentioning features or use of this software
  22     must display the following acknowledgment:
  23       This product includes software developed by ACIRI, the AT&T
  24       Center for Internet Research at ICSI (the International Computer
  25       Science Institute). This product may also include software developed
  26       by Stefan Savage at the University of Washington.
  27  4. The names of ACIRI, ICSI, Stefan Savage and University of Washington
  28     may not be used to endorse or promote products derived from this software
  29     without specific prior written permission.
  30
  31  THIS SOFTWARE IS PROVIDED BY ICSI AND CONTRIBUTORS ``AS IS'' AND
  32  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  33  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  34  ARE DISCLAIMED.  IN NO EVENT SHALL ICSI OR CONTRIBUTORS BE LIABLE
  35  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  36  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  37  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  38  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  39  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  40  OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  41  SUCH DAMAGE.
  42 */
  43 #include <sys/types.h>
  44 #include <sys/param.h>
  45 #include <sys/time.h>
  46 #include <string.h>
  47 #include <stdio.h>
  48 #include <unistd.h>
  49 #include "base.h"
  50 #include "inet.h"
  51 #include "session.h"
  52 #include "support.h"
  53 #include "history.h"
  54
  55 extern struct TcpSession session;
  56 struct History history[MAXHSZ];
  57
  58 void StorePacket (struct IPPacket *p) {
  59
  60   uint32 src, dst, seq, ack ;
  61   uint16 sport, dport, win, urp, datalen, optlen;
  62   uint16 ip_optlen;
  63   uint8 flags;
  64
  65   ReadIPPacket(p,
  66                &src, &dst,
  67                &sport, &dport,
  68                &seq,
  69                &ack,
  70                &flags,
  71                &win,
  72                &urp,
  73                &datalen,
  74                &ip_optlen,
  75                &optlen);
  76
  77   if (src == session.src) {
  78     history[session.hsz].type = SENT;
  79   } else {
  80     history[session.hsz].type = RCVD ;
  81   }
  82
  83   history[session.hsz].timestamp = GetTime () - session.epochTime;
  84   history[session.hsz].seqno = seq;
  85   history[session.hsz].nextbyte = seq + datalen;
  86   history[session.hsz].ackno = ack ;
  87   history[session.hsz].fin = (flags & TCPFLAGS_FIN) ? 1 : 0;
  88   history[session.hsz].syn = (flags & TCPFLAGS_SYN) ? 1 : 0;
  89   history[session.hsz].rst = (flags & TCPFLAGS_RST) ? 1 : 0;
  90   history[session.hsz].psh = (flags & TCPFLAGS_PSH) ? 1 : 0;
  91   history[session.hsz].ack = (flags & TCPFLAGS_ACK) ? 1 : 0;
  92   history[session.hsz].urg = (flags & TCPFLAGS_URG) ? 1 : 0;
  93   history[session.hsz].ecn_echo = (flags & TCPFLAGS_ECN_ECHO) ? 1:0;
  94   history[session.hsz].cwr = (flags & TCPFLAGS_CWR) ? 1 : 0;
  95   history[session.hsz].ip_optlen = ip_optlen;
  96   history[session.hsz].optlen = optlen ;
  97
  98   /* Grab IP Options from Ip Header - New */
  99   if (ip_optlen > 0) {
 100     if ((history[session.hsz].ip_opt = calloc(sizeof(uint8), ip_optlen)) == NULL) {
 101       printf("StorePacket Error: Could not allocate history memory\nRETURN CODE: %d\n", ERR_MEM_ALLOC);
 102       Quit (ERR_MEM_ALLOC);
 103     }
 104     memcpy(history[session.hsz].ip_opt, (char *)p->ip + sizeof(struct IpHeader), ip_optlen);
 105   }
 106
 107
 108   /* Grab TCP options from TCP Header */
 109   if (optlen > 0) {
 110     if ((history[session.hsz].opt = calloc(sizeof(uint8), optlen)) == NULL) {
 111       Quit (ERR_MEM_ALLOC);
 112     }
 113
 114     memcpy(history[session.hsz].opt, (char *)p->tcp + sizeof(struct TcpHeader), optlen);
 115   }
 116
 117   history[session.hsz].dlen = datalen;
 118
 119   if ((history[session.hsz].data = calloc(sizeof(uint8), datalen)) == NULL) {
 120     Quit (ERR_MEM_ALLOC);
 121   }
 122
 123   /* Copy data bytes */
 124   memcpy(history[session.hsz].data,
 125          (char *)p->tcp + sizeof(struct TcpHeader) + optlen,
 126          datalen);
 127
 128   session.hsz++;
 129
 130   if (session.hsz >= MAXHSZ) {
 131     Quit(TOO_MANY_PKTS);
 132   }
 133
 134 }
 135
 136 int reordered(struct IPPacket *p) {
 137
 138   int i;
 139   int count = 0;
 140   double ts = -99999;
 141
 142   /*
 143    * This might be either an unwanted packet drop, or just a reordering.
 144    * Test:
 145    *  If we have not sent three acks for this packet
 146    *  AND the gap between this packet and previous one is "small" (i.e. not a timeout)
 147    *  then its a reordering, and not a retransmission.
 148    */
 149
 150   /* count the number of (dup) ACKs sent */
 151   for (i = 0; i < session.hsz; i++) {
 152     if ((history[i].type == SENT) &&
 153         (history[i].ack)) {
 154       if (history[i].ackno == history[session.hsz - 1].seqno)
 155         count += 1;
 156     }
 157   }
 158
 159   if (count > 0) {
 160
 161     session.num_dup_acks += count - 1;
 162
 163     switch (count) {
 164     case 1: /* no dup acks */
 165       session.num_pkts_0_dup_acks += 1;
 166       break;
 167
 168     case 2: /* 1 dup acks */
 169       session.num_pkts_1_dup_acks += 1;
 170       break;
 171
 172     case 3: /* 2 dup acks */
 173       session.num_pkts_2_dup_acks += 1;
 174       break;
 175
 176     case 4: /* 3 dup acks */
 177       session.num_pkts_3_dup_acks += 1;
 178       break;
 179
 180     default:
 181       session.num_pkts_4_or_more_dup_acks += 1;
 182       break;
 183     }
 184   }
 185
 186   /* 3 dup acks? => Fast retransmission */
 187   if (count > 3) {
 188     printf("Fast retransmit...\n");
 189     return 3;
 190   }
 191
 192   /* Compute elapsed time between this packet and the previously RCVD packet */
 193   for (i = (session.hsz - 2); i >= 0; i--) {
 194     if ((history[i].type == RCVD) && (history[i].dlen > 0)) {
 195       ts = history[i].timestamp;
 196       break;
 197     }
 198   }
 199
 200   if ((history[session.hsz - 1].timestamp - ts) > RTT_TO_MULT * (session.rtt + PLOTDIFF)) {
 201     printf ("RTO ===> %f %f\n", history[session.hsz - 1].timestamp, ts);
 202     return 2;
 203   }
 204
 205   printf ("#### Acks %d\n", count);
 206   printf ("#### reordering detected\n");
 207   session.num_reordered++;
 208
 209   return 1;
 210
 211 }