summaryrefslogtreecommitdiff
path: root/src/lib/frct.c
diff options
context:
space:
mode:
authorDimitri Staessens <dimitri.staessens@ugent.be>2019-02-08 10:47:42 +0100
committerSander Vrijders <sander.vrijders@ugent.be>2019-02-08 12:39:23 +0100
commite00c9b13acad23e14df9d5cf4c7868dfd6e1bc55 (patch)
tree1447e0402a78b79edd03cd8f72bc6c236df81a4c /src/lib/frct.c
parent5dd086aa679e3e05d20ef6a19f3fefbe46ffe40e (diff)
downloadouroboros-e00c9b13acad23e14df9d5cf4c7868dfd6e1bc55.tar.gz
ouroboros-e00c9b13acad23e14df9d5cf4c7868dfd6e1bc55.zip
lib: Add initial rtt estimator to FRCT
This adds a simple round-trip time estimator to FRCT. The estimate is a weighted average with deviation. The retransmission is scheduled after rtt + 2 times the deviation. A retransmit doubles the rtt estimate to avoid the no-update case when rtt suddenly increases. The rtt is estimated in microseconds and the granularity for retransmits is 256 microseconds. Signed-off-by: Dimitri Staessens <dimitri.staessens@ugent.be> Signed-off-by: Sander Vrijders <sander.vrijders@ugent.be>
Diffstat (limited to 'src/lib/frct.c')
-rw-r--r--src/lib/frct.c75
1 files changed, 63 insertions, 12 deletions
diff --git a/src/lib/frct.c b/src/lib/frct.c
index 02c101c8..bd08d86a 100644
--- a/src/lib/frct.c
+++ b/src/lib/frct.c
@@ -50,7 +50,11 @@ struct frcti {
time_t a;
time_t r;
- time_t rto; /* ms */
+ time_t srtt_us; /* smoothed rtt */
+ time_t mdev_us; /* mdev */
+ uint32_t rttseq;
+ struct timespec t_probe; /* probe time */
+ bool probe; /* probe active */
struct frct_cr snd_cr;
struct frct_cr rcv_cr;
@@ -110,8 +114,11 @@ static struct frcti * frcti_create(int fd)
frcti->snd_cr.inact = 3 * delta_t;
frcti->snd_cr.act = now.tv_sec - (frcti->snd_cr.inact + 1);
- /* Initial rto. FIXME: recalc using Karn algorithm. */
- frcti->rto = 120;
+ /* rtt estimator. rto is currently srtt + 2 * mdev */
+ frcti->srtt_us = 0; /* updated on first ACK */
+ frcti->mdev_us = 100000; /* initial rxm will be after 200 ms */
+ frcti->rttseq = 0;
+ frcti->probe = false;
if (ai.flows[fd].spec.loss == 0) {
frcti->snd_cr.cflags |= FRCTFRTX;
@@ -200,6 +207,18 @@ static struct frct_pci * frcti_alloc_head(struct shm_du_buff * sdb)
return pci;
}
+static bool before(uint32_t seq1,
+ uint32_t seq2)
+{
+ return (int32_t)(seq1 - seq2) < 0;
+}
+
+static bool after(uint32_t seq1,
+ uint32_t seq2)
+{
+ return (int32_t)(seq2 - seq1) < 0;
+}
+
static int __frcti_snd(struct frcti * frcti,
struct shm_du_buff * sdb)
{
@@ -219,7 +238,7 @@ static int __frcti_snd(struct frcti * frcti,
if (pci == NULL)
return -1;
- clock_gettime(CLOCK_REALTIME_COARSE, &now);
+ clock_gettime(CLOCK_REALTIME, &now);
pthread_rwlock_wrlock(&frcti->lock);
@@ -244,12 +263,20 @@ static int __frcti_snd(struct frcti * frcti,
pci->seqno = hton32(snd_cr->seqno);
if (!(snd_cr->cflags & FRCTFRTX)) {
snd_cr->lwe++;
- } else if (now.tv_sec - rcv_cr->act <= rcv_cr->inact) {
- rxmwheel_add(frcti, snd_cr->seqno, sdb);
- if (rcv_cr->lwe <= rcv_cr->seqno) {
- pci->flags |= FRCT_ACK;
- pci->ackno = hton32(rcv_cr->seqno);
- rcv_cr->lwe = rcv_cr->seqno;
+ } else {
+ if (!frcti->probe) {
+ frcti->rttseq = snd_cr->seqno;
+ frcti->t_probe = now;
+ frcti->probe = true;
+ }
+
+ if (now.tv_sec - rcv_cr->act <= rcv_cr->inact) {
+ rxmwheel_add(frcti, snd_cr->seqno, sdb);
+ if (rcv_cr->lwe <= rcv_cr->seqno) {
+ pci->flags |= FRCT_ACK;
+ pci->ackno = hton32(rcv_cr->seqno);
+ rcv_cr->lwe = rcv_cr->seqno;
+ }
}
}
@@ -261,6 +288,26 @@ static int __frcti_snd(struct frcti * frcti,
return 0;
}
+static void rtt_estimator(struct frcti * frcti,
+ time_t mrtt_us)
+{
+ time_t srtt = frcti->srtt_us;
+ time_t mdev = frcti->mdev_us;
+
+ if (srtt != 0) {
+ srtt -= (srtt >> 3);
+ srtt += mrtt_us >> 3; /* rtt = 7/8 rtt + 1/8 new */
+ mdev -= (mdev >> 2);
+ mdev += ABS(srtt - mrtt_us) >> 2;
+ } else {
+ srtt = mrtt_us << 3; /* take the measured time to be rtt */
+ mdev = mrtt_us >> 1; /* take half mrtt_us as deviation */
+ }
+
+ frcti->srtt_us = MAX(1U, srtt);
+ frcti->mdev_us = MAX(1U, mdev);
+}
+
/* Returns 0 when idx contains a packet for the application. */
static int __frcti_rcv(struct frcti * frcti,
struct shm_du_buff * sdb)
@@ -280,7 +327,7 @@ static int __frcti_rcv(struct frcti * frcti,
pci = (struct frct_pci *) shm_du_buff_head_release(sdb, FRCT_PCILEN);
- clock_gettime(CLOCK_REALTIME_COARSE, &now);
+ clock_gettime(CLOCK_REALTIME, &now);
pthread_rwlock_wrlock(&frcti->lock);
@@ -300,7 +347,7 @@ static int __frcti_rcv(struct frcti * frcti,
if (seqno == rcv_cr->seqno) {
++rcv_cr->seqno;
} else { /* Out of order. */
- if ((int32_t)(seqno - rcv_cr->seqno) < 0)
+ if (before(seqno, rcv_cr->seqno))
goto drop_packet;
if (rcv_cr->cflags & FRCTFRTX) {
@@ -321,6 +368,10 @@ static int __frcti_rcv(struct frcti * frcti,
/* Check for duplicate (old) acks. */
if ((int32_t)(ackno - snd_cr->lwe) >= 0)
snd_cr->lwe = ackno;
+ if (frcti->probe && after(ackno, frcti->rttseq)) {
+ rtt_estimator(frcti, ts_diff_us(&frcti->t_probe, &now));
+ frcti->probe = false;
+ }
}
rcv_cr->act = now.tv_sec;