[Tinyos-devel] retransmissions in networking protocols

[Omprakash Gnawali]

> Om -- we have some detailed MLQI traces, right? Did we log duplicate  
> suppression in them? Or, at the very least, we can definitely measure  
> the duplicate delivery rate at the root, right? It would be good to  
> know how bad the problem is.
> 
> Phil

This is data from Mirage, the sixth column tells you the number of
duplicate packets received from that origin and the sevent column
tells you what fraction of the total pkts received from the origin
were duplicates:

#node total_sent uniq_rcv success_rate   total_rcv repeated_rcv (frac), minseq, maxseq
3 369 369 1.000 370 1 0.003, 1, 369
4 373 373 1.000 375 2 0.005, 1, 373
5 368 367 0.997 381 14 0.037, 2, 369
6 374 374 1.000 374 0 0.000, 1, 374
9 368 368 1.000 369 1 0.003, 1, 368
10 364 364 1.000 366 2 0.005, 1, 364
13 366 366 1.000 367 1 0.003, 1, 366
16 365 365 1.000 365 0 0.000, 2, 366
17 372 372 1.000 372 0 0.000, 1, 372
18 369 369 1.000 370 1 0.003, 2, 370
19 352 232 0.659 233 1 0.004, 3, 354
20 372 372 1.000 372 0 0.000, 2, 373
21 372 294 0.790 296 2 0.007, 1, 372
22 369 369 1.000 370 1 0.003, 1, 369
24 367 358 0.975 364 6 0.016, 1, 367
26 372 371 0.997 372 1 0.003, 1, 372
27 362 342 0.945 344 2 0.006, 1, 362
28 362 351 0.970 352 1 0.003, 1, 362
30 369 369 1.000 369 0 0.000, 1, 369
32 368 366 0.995 367 1 0.003, 1, 368
33 375 375 1.000 375 0 0.000, 2, 376
36 364 364 1.000 365 1 0.003, 2, 365
37 360 360 1.000 360 0 0.000, 2, 361
39 357 357 1.000 357 0 0.000, 2, 358
40 358 358 1.000 359 1 0.003, 1, 358
41 368 336 0.913 339 3 0.009, 2, 369
43 371 371 1.000 375 4 0.011, 2, 372
44 372 371 0.997 374 3 0.008, 1, 372
47 365 362 0.992 362 0 0.000, 2, 366
48 359 359 1.000 361 2 0.006, 2, 360
49 373 263 0.705 266 3 0.011, 2, 374
50 371 370 0.997 371 1 0.003, 2, 372
52 365 356 0.975 357 1 0.003, 3, 367
53 357 282 0.790 282 0 0.000, 2, 358
55 359 359 1.000 360 1 0.003, 2, 360
56 358 229 0.640 230 1 0.004, 3, 360
57 367 367 1.000 368 1 0.003, 2, 368
58 364 364 1.000 365 1 0.003, 2, 365
59 364 349 0.959 351 2 0.006, 3, 366
60 366 366 1.000 367 1 0.003, 2, 367
61 362 362 1.000 385 23 0.060, 1, 362
62 369 369 1.000 369 0 0.000, 1, 369
66 360 360 1.000 364 4 0.011, 1, 360
68 370 370 1.000 371 1 0.003, 1, 370
69 367 367 1.000 368 1 0.003, 2, 368
70 370 370 1.000 373 3 0.008, 2, 371
71 365 364 0.997 365 1 0.003, 1, 365
77 364 363 0.997 368 5 0.014, 1, 364
78 365 365 1.000 366 1 0.003, 2, 366
82 365 259 0.710 262 3 0.011, 3, 367
85 367 352 0.959 353 1 0.003, 3, 369
86 373 361 0.968 362 1 0.003, 2, 374
89 370 370 1.000 371 1 0.003, 2, 371
92 362 362 1.000 365 3 0.008, 3, 364
95 379 379 1.000 381 2 0.005, 2, 380
96 365 365 1.000 366 1 0.003, 3, 367
100 367 367 1.000 368 1 0.003, 2, 368
102 368 368 1.000 371 3 0.008, 1, 368
104 375 375 1.000 379 4 0.011, 1, 375
105 372 372 1.000 373 1 0.003, 2, 373
107 363 357 0.983 359 2 0.006, 2, 364
109 371 370 0.997 371 1 0.003, 2, 372
112 368 366 0.995 367 1 0.003, 2, 369
115 371 370 0.997 375 5 0.013, 2, 372
116 369 368 0.997 372 4 0.011, 2, 370
117 372 369 0.992 369 0 0.000, 2, 373
119 360 352 0.978 352 0 0.000, 3, 362
120 375 374 0.997 376 2 0.005, 2, 376
122 368 352 0.957 353 1 0.003, 2, 369
123 355 355 1.000 357 2 0.006, 2, 356
124 368 368 1.000 372 4 0.011, 2, 369
125 360 360 1.000 362 2 0.006, 2, 361
130 371 371 1.000 373 2 0.005, 2, 372
131 367 255 0.695 255 0 0.000, 2, 368
132 364 339 0.931 339 0 0.000, 3, 366
133 360 343 0.953 343 0 0.000, 3, 362
137 378 370 0.979 371 1 0.003, 2, 379
138 373 351 0.941 352 1 0.003, 2, 374
140 366 348 0.951 351 3 0.009, 3, 368
141 363 350 0.964 352 2 0.006, 2, 364
142 377 313 0.830 314 1 0.003, 2, 378
143 373 347 0.930 349 2 0.006, 2, 374
145 376 346 0.920 347 1 0.003, 2, 377
146 364 243 0.668 244 1 0.004, 2, 365
148 369 344 0.932 344 0 0.000, 2, 370
#delivery 0.959233382475482
#throughtput 8.35853449121161
#time 3600.033

There were a total of 161 duplicate packets received by the root out
of total 30091 pkts received.

Looking at the duplicates in the network, lqi detected and suppressed
1943 duplicates out of total 76606 message receptions in the network
(includes root). So, it seems about 2.5% packets are duplicates. Here
are the number of duplicate events logged by the nodes:

node id #duplicates dropped
68 806
78 314
6 240
18 185
26 147
89 45
112 43
71 23
102 23
22 21
37 19
130 10
50 9
123 8
120 7
33 6
125 5
104 5
96 3
48 3
133 3
95 2
5 2
39 2
115 2
107 2
70 1
61 1
57 1
36 1
3 1
24 1
16 1
10 1


Then the question is if any node missed some duplicates due to cache
size limitation. I wrote a script that checked to see if the same
<origin, seq> were transmitted (FW_FWD_MSG) by a node within a 100-pkt
window, and there was not a single instance of missed duplicate due to
cache size limitation.

- om_p