Statistics on semi-reliable UDP and improvements
Raphael Manfredi <[email protected]> Wed, 24 Oct 2012 14:02:30 +0200
| Newsgroups | gmane.network.gnutella.devel |
|---|---|
| Organization | Home, Grenoble, France |
| Message-ID | <[email protected]> |
--AtqiTLHV5laqNu-nXd--JIDxqWhaZZhJO7HhxQs
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Now that I have deployed the semi-reliable UDP layer in gtk-gnutella, I have
been able to collect some interesting statistics.
One figure is striking: about 10% of the fragments need to be retransmitted,
meaning that there is a drop rate of about 10% of UDP messages. This shows
why the semi-reliable UDP layer is worth using when transmitting query hits
over UDP!
When IP drops a fragment, it is usually not resent, so 10% fragment dropping
may equal to perhaps 15% or 20% of the multi-fragment messages that are
lost because they are incompletely received. I'm extrapolating my 10% user-
level fragment drop rate with IP's drop rate, which I believe is OK because
the fragments sent by my layer are about 512 bytes (at the IP level).
Secondly, in order to improve the semi-reliable layer and avoid costly
retransmissions when the remote end is not answering, I have introduced
EARs (Extra Acknolwedgment Requests). Here are the specifications:
------------------------------------------------------------------------
2.10 Extra Acknowledgment Requests
An Extra Acknowledgment Request (EAR) is a special message that can be sent
by the transmission side (TX side, for short) to request an acknowledgment
(ACK) from the receiving side (RX side) for everything that was successfully
received so far for a particular sequence ID.
After sending all the fragments initially, and before resending a fragment
upon not getting any ACK back, the TX side can send an EAR, which will be
hopefully answered to by the RX side. This serves two purposes:
1. It cheaply requests that another ACK be sent by the RX side, in case the
previous one was lost on its way back.
2. It avoid resending fragments uselessly if there is nobody listening on the
other end.
An EAR is kind of an ACK message, albeit it has nPart = 0 and nCount = 0.
Moreover, the 0x02 bit in nFlags is set (ACK requested) to indicate that this
message must somehow be replied to. The 0x01 bit MUST be cleared as well: its
payload is never deflated (there is none).
It is easy to recognize the EAR for what it is because no valid ACK will have
a nPart field set to zero.
When the RX side gets an EAR, it looks at its nSequence field:
- If it knows the sequence ID, it has already started to receive fragments
for this message. In that case, it immediately acknowledges the EAR
by sending back an ACK for the sequence ID, describing what has been
received so far. It can be a cumulative or an extended ACK.
- If it does not know the sequence ID, it means no fragments were received
so far. In that case, it immediately negatively acknowledges the EAR
by sending back another EAR but with the 0x02 bit in nFlags cleared!
This indicates to the TX side receiving the EAR that it is actually an
ACK for the EAR it sent, not an EAR that it must respond to.
The TX side then either gets an ACK or an EAR back, and it knows that the
remote host is up, as well as how many fragments it has received so far.
It can then proceed with re-transmission.
If the TX side gets nothing back after sending an EAR and waiting 5 seconds,
it resends another EAR, waiting for 7.5 seconds before sending a final EAR
and waiting 11 seconds for a reply (same parameters as for a regular fragment).
After 3 EARs sent and no reply received, the TX side can assume the other end
is not listening and it can drop the message. Fragments will only have been
sent once.
------------------------------------------------------------------------
Cheers,
Raphael
--AtqiTLHV5laqNu-nXd--JIDxqWhaZZhJO7HhxQs
Content-Type: text/html; charset=US-ASCII
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
</head>
<body style="background-color: #fff;">
<span style="display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id="ygrp-mlmsg" style="position:relative;">
<div id="ygrp-msg" style="z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id="ygrp-text" >
<p>Now that I have deployed the semi-reliable UDP layer in gtk-gnutella, I have<br>
been able to collect some interesting statistics.<br>
<br>
One figure is striking: about 10% of the fragments need to be retransmitted,<br>
meaning that there is a drop rate of about 10% of UDP messages. This shows<br>
why the semi-reliable UDP layer is worth using when transmitting query hits<br>
over UDP!<br>
<br>
When IP drops a fragment, it is usually not resent, so 10% fragment dropping<br>
may equal to perhaps 15% or 20% of the multi-fragment messages that are<br>
lost because they are incompletely received. I'm extrapolating my 10% user-<br>
level fragment drop rate with IP's drop rate, which I believe is OK because<br>
the fragments sent by my layer are about 512 bytes (at the IP level).<br>
<br>
Secondly, in order to improve the semi-reliable layer and avoid costly<br>
retransmissions when the remote end is not answering, I have introduced<br>
EARs (Extra Acknolwedgment Requests). Here are the specifications:<br>
<br>
----------------------------------------------------------<br>
2.10 Extra Acknowledgment Requests<br>
<br>
An Extra Acknowledgment Request (EAR) is a special message that can be sent<br>
by the transmission side (TX side, for short) to request an acknowledgment<br>
(ACK) from the receiving side (RX side) for everything that was successfully<br>
received so far for a particular sequence ID.<br>
<br>
After sending all the fragments initially, and before resending a fragment<br>
upon not getting any ACK back, the TX side can send an EAR, which will be<br>
hopefully answered to by the RX side. This serves two purposes:<br>
<br>
1. It cheaply requests that another ACK be sent by the RX side, in case the<br>
previous one was lost on its way back.<br>
<br>
2. It avoid resending fragments uselessly if there is nobody listening on the<br>
other end.<br>
<br>
An EAR is kind of an ACK message, albeit it has nPart = 0 and nCount = 0.<br>
Moreover, the 0x02 bit in nFlags is set (ACK requested) to indicate that this<br>
message must somehow be replied to. The 0x01 bit MUST be cleared as well: its<br>
payload is never deflated (there is none).<br>
<br>
It is easy to recognize the EAR for what it is because no valid ACK will have<br>
a nPart field set to zero.<br>
<br>
When the RX side gets an EAR, it looks at its nSequence field:<br>
<br>
- If it knows the sequence ID, it has already started to receive fragments<br>
for this message. In that case, it immediately acknowledges the EAR<br>
by sending back an ACK for the sequence ID, describing what has been<br>
received so far. It can be a cumulative or an extended ACK.<br>
<br>
- If it does not know the sequence ID, it means no fragments were received<br>
so far. In that case, it immediately negatively acknowledges the EAR<br>
by sending back another EAR but with the 0x02 bit in nFlags cleared!<br>
This indicates to the TX side receiving the EAR that it is actually an<br>
ACK for the EAR it sent, not an EAR that it must respond to.<br>
<br>
The TX side then either gets an ACK or an EAR back, and it knows that the<br>
remote host is up, as well as how many fragments it has received so far.<br>
It can then proceed with re-transmission.<br>
<br>
If the TX side gets nothing back after sending an EAR and waiting 5 seconds,<br>
it resends another EAR, waiting for 7.5 seconds before sending a final EAR<br>
and waiting 11 seconds for a reply (same parameters as for a regular fragment).<br>
<br>
After 3 EARs sent and no reply received, the TX side can assume the other end<br>
is not listening and it can drop the message. Fragments will only have been<br>
sent once.<br>
----------------------------------------------------------<br>
<br>
Cheers,<br>
Raphael<br>
</p>
</div>
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style="color: #fff; height: 0;">__._,_.___</div>
<table cellspacing=4px style="margin-top: 20px; margin-bottom: 10px;">
<tbody>
<tr>
<td style="font-size: 12px; font-family: arial; font-weight: bold; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA " >
<a style="text-decoration: none; color: #2D50FD" href="http://groups.yahoo.com/group/the_gdf/post;_ylc=X3oDMTJxZmxnc2N2BF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBG1zZ0lkAzIzODA3BHNlYwNmdHIEc2xrA3JwbHkEc3RpbWUDMTM1MTA4MDE1OQ--?act=reply&messageNum=23807">Reply via web post</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="mailto:[email protected]?subject=Re%3A%20Statistics%20on%20semi-reliable%20UDP%20and%20improvements" style="text-decoration: none; color: #2D50FD;">
Reply to sender </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; ">
<a href="mailto:[email protected]?subject=Re%3A%20Statistics%20on%20semi-reliable%20UDP%20and%20improvements" style="text-decoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/the_gdf/post;_ylc=X3oDMTJla2U0bDZxBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM1MTA4MDE1OQ--" style="text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td style="font-size: 12px; font-family: arial; padding: 7px 5px 5px; color: #2D50FD; background-color: #F2F2F2; border: 1px solid #EAEAEA; " >
<a href="http://groups.yahoo.com/group/the_gdf/message/23807;_ylc=X3oDMTM2dGFxZDJzBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBG1zZ0lkAzIzODA3BHNlYwNmdHIEc2xrA3Z0cGMEc3RpbWUDMTM1MTA4MDE1OQR0cGNJZAMyMzgwNw--" style="text-decoration: none; color: #2D50FD;">Messages in this topic</a>
(1)
</td>
</tr>
</tbody>
</table>
<!------- Start Nav Bar ------>
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-vital" style="background-color: #f2f2f2; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span>
<ul style="list-style-type: none; margin: 0; padding: 0; display: inline;">
<li style="border-right: 1px solid #000; font-weight: 700; display: inline; padding: 0 5px; margin-left: 0;">
<span class="cat"><a href="http://groups.yahoo.com/group/the_gdf/links;_ylc=X3oDMTJnZzlwNmxsBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwN2dGwEc2xrA3ZsaW5rcwRzdGltZQMxMzUxMDgwMTU5" style="text-decoration: none;">New Links</a></span>
<span class="ct" style="color: #ff7900;">1</span>
</li>
</ul>
<div style="clear: both; padding-top: 2px; color: #1e66ae;">
<a href="http://groups.yahoo.com/group/the_gdf;_ylc=X3oDMTJlYzRiYmdpBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM1MTA4MDE1OQ--" style="text-decoration: none;">Visit Your Group</a>
</div>
</div>
<div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;">
<a href="http://groups.yahoo.com/;_ylc=X3oDMTJkNWk3ODZkBF9TAzk3MzU5NzE0BGdycElkAzI2ODQyNTMEZ3Jwc3BJZAMxNzA1MDE2MDYxBHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzUxMDgwMTU5" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a>
<div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a> • <a href="mailto:[email protected]?subject=Feedback on the redesigned individual mail v1" style="text-decoration: none;">Send us Feedback </a></div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id="ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style="clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src="http://geo.yahoo.com/serv?s=97359714/grpId=2684253/grpspId=1705016061/msgId=23807/stime=1351080159/nc1=5741393/nc2=5898818/nc3=5522132" width="1" height="1"> <br>
<div style="color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type="text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.file-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;
}
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--AtqiTLHV5laqNu-nXd--JIDxqWhaZZhJO7HhxQs--