Sequence Number Validation Bug Fixes 0/2

Sequence Number Validation Bug Fixes 0/2

[Samuel Jero]

[-- Attachment #1: Type: text/plain, Size: 2289 bytes --]

Hello All,

I have been examining DCCP for several months trying to understand
several odd behaviors that I ran across trying to utilize DCCP CCID 2
for a research project.

Over the course of that time I have become quite familiar with the DCCP
testing tree and with the DCCP protocol itself, particularly CCID 2. As
part of my examination, I wrote a tool to help graph DCCP connections.
This tool converts DCCP CCID 2 connections to TCP connections which can
then be analyzed with Tcptrace (http://tcptrace.org). (I can provide a
link to the tool if people are interested).

Examining the Graphs produced by this tool, I noticed some unusual
behaviors. The most interesting one was that at certain times the DCCP
receiver will renege on certain data segments in the Ack Vector and
renege on receiving an Ack from the sender (obvious by increasing the
length of the Ack Vector). Here is a picture:
http://jeroserver.homelinux.net/software/dccp/renege.jpg

It turns out this behavior is due to a nasty bug in the dccp sequence
number validation code (dccp_check_seqno in input.c). What happens is
that the receiver legitimately stops incrementing it's ack number
because packets from the sender are outside the valid Ack window (why
this happens is another problem I'm still working on). DCCP should send
a sync when this happens, but this sync needs to be rate-limited. If it
isn't time to send a sync, the DCCP code currently returns 0 which
indicates that the packet is good!! 

As a result, the Ack Vector is updated. Since the data in the Ack Vector
is interpreted relative to the Ack number (which wasn't updated since
the packet was out of bounds), the Ack Vector appears to shift backwards
in time, producing the strange results already described.

I have put together a patch for this bug, which follows in a separate
email.

In examining this section of code, I also noticed that the the GSR is
updated by any packet in the valid sequence number window. I believe
this represents a minor bug, because it would allow the GSR to move
backward as a result of an out of order packet that is still in the
valid window. I am also sending a patch for that as a separate email.


Samuel Jero
Internetworking Research Group
Ohio University 

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Sequence Number Validation Bug Fixes 0/2

[Gerrit Renker]

[-- Attachment #1: Type: text/plain, Size: 3270 bytes --]

Hi Samuel,

| This tool converts DCCP CCID 2 connections to TCP connections which can
| then be analyzed with Tcptrace (http://tcptrace.org). (I can provide a
| link to the tool if people are interested).
| 
Please do -- such a tool has been missing for a long time, and the idea to hook
it up with tcptrace is both original and efficient. Analysing Ack Vectors using
tcpdump/wireshark is very tedious, so anything that can help in debugging Ack
Vector traces is a great help.

| It turns out this behavior is due to a nasty bug in the dccp sequence
| number validation code (dccp_check_seqno in input.c). What happens is
| that the receiver legitimately stops incrementing it's ack number
| because packets from the sender are outside the valid Ack window (why
| this happens is another problem I'm still working on). DCCP should send
| a sync when this happens, but this sync needs to be rate-limited. If it
| isn't time to send a sync, the DCCP code currently returns 0 which
| indicates that the packet is good!! 
| 
Thanks a lot, you have found a real bug. I have edited your patch since
Evolution squeezed tabs into whitespaces, and added your Signed-off --
please check the attached result, as I would like to submit this soon.


With regard to not updating the Ack Number, I remember having seen something
related earlier. There is a relationship between the current sending rate, the
Ack Ratio, the cwnd, and the Sequence Window. The Ack window is advanced by the
GSS and depends on the local value of the Sequence Window. RFC 4340, 7.5.2
recommends 5 * max_packets_per_RTT as guideline for Sequence Window.

When I looked at this earlier I noted that the dynamic update of Ack Ratio,
cwnd, and Sequence Window (which are all inter-related, but are controlled
by different code paths) does not produce the expected interaction, therefore
Ack Ratio is currently always 1 and Sequence Window is also static and does
not change throughout the connection. 

It may be that both these shortcuts cause the behaviour you observed. The
Ack Ratio update is disabled in net/dccp/feat.c:dccp_hdlr_ack_ratio(), but
there is currently no code to predict (guess) what the sending rate will
be for the next 5 RTTs -- if such a heuristic is possible.

I am interested in suggestions to improve this.

| In examining this section of code, I also noticed that the the GSR is
| updated by any packet in the valid sequence number window. I believe
| this represents a minor bug, because it would allow the GSR to move
| backward as a result of an out of order packet that is still in the
| valid window. I am also sending a patch for that as a separate email.
|
Excellent catch, there is a second bug here. Apart from the clerical edits
(please consult Documentation/SubmittingPatches), there is a small
modification, sent in response to the other patch. Please check this also -
both are very useful bug fixes, I have already put them into the test tree at

    git://eden-feed.erg.abdn.ac.uk/dccp_exp	[subtree 'dccp']

    http://eden-feed.erg.abdn.ac.uk/cgi-bin/gitweb.cgi?p=dccp_exp.git;a=commitdiff;h=adc0984a00912f2297f8272d3756a279900f6ba9
    http://eden-feed.erg.abdn.ac.uk/cgi-bin/gitweb.cgi?p=dccp_exp.git;a=commitdiff;h=9eb39613b014cee24b0b8e390bd221df6737954c

Gerrit

[-- Attachment #2: seqno_validation-1.diff --]
[-- Type: text/x-diff, Size: 821 bytes --]

dccp: fix return value for sequence-invalid packets

Currently dccp_check_seqno returns 0 (indicating a valid packet) if the
acknowledgment number is out of bounds and the sync that RFC 4340 mandates at
this point is currently being rate-limited. This function should return -1,
indicating an invalid packet.

Signed-off-by: Samuel Jero <sj323707@ohio.edu>
Acked-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/input.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- a/net/dccp/input.c
+++ b/net/dccp/input.c
@@ -260,7 +260,7 @@ static int dccp_check_seqno(struct sock 
 		 */
 		if (time_before(now, (dp->dccps_rate_last +
 				      sysctl_dccp_sync_ratelimit)))
-			return 0;
+			return -1;
 
 		DCCP_WARN("Step 6 failed for %s packet, "
 			  "(LSWL(%llu) <= P.seqno(%llu) <= S.SWH(%llu)) and "

Re: Sequence Number Validation Bug Fixes 0/2

[Samuel Jero]

[-- Attachment #1: Type: text/plain, Size: 4709 bytes --]

Gerrit,

> | This tool converts DCCP CCID 2 connections to TCP connections which can
> | then be analyzed with Tcptrace (http://tcptrace.org). (I can provide a
> | link to the tool if people are interested).
> | 
> Please do -- such a tool has been missing for a long time, and the idea to hook
> it up with tcptrace is both original and efficient. Analysing Ack Vectors using
> tcpdump/wireshark is very tedious, so anything that can help in debugging Ack
> Vector traces is a great help.

The tool can be downloaded from here:
http://jeroserver.homelinux.net/software/dccp/files/dccp2tcp.tar.gz
or here: http://oak.cats.ohiou.edu/~sj323707/dccp2tcp.tar.gz

At the moment I'm calling it dccp2tcp and releasing it under the GNU
GPL. Right now, the tool only understands DCCP over IPv4 over Ethernet
and only compiles on Linux.

I've included a README file that explains the commandline args and what
the various parts of the Tcptrace graphs represent. The short story is
you probably want to run it like this: dccp2tcp -s dccp_file tcp_file

> 
> | It turns out this behavior is due to a nasty bug in the dccp sequence
> | number validation code (dccp_check_seqno in input.c). What happens is
> | that the receiver legitimately stops incrementing it's ack number
> | because packets from the sender are outside the valid Ack window (why
> | this happens is another problem I'm still working on). DCCP should send
> | a sync when this happens, but this sync needs to be rate-limited. If it
> | isn't time to send a sync, the DCCP code currently returns 0 which
> | indicates that the packet is good!! 
> | 
> Thanks a lot, you have found a real bug. I have edited your patch since
> Evolution squeezed tabs into whitespaces, and added your Signed-off --
> please check the attached result, as I would like to submit this soon.
>
Looks good. You have my okay to submit it.
> 
> With regard to not updating the Ack Number, I remember having seen something
> related earlier. There is a relationship between the current sending rate, the
> Ack Ratio, the cwnd, and the Sequence Window. The Ack window is advanced by the
> GSS and depends on the local value of the Sequence Window. RFC 4340, 7.5.2
> recommends 5 * max_packets_per_RTT as guideline for Sequence Window.
> 
> When I looked at this earlier I noted that the dynamic update of Ack Ratio,
> cwnd, and Sequence Window (which are all inter-related, but are controlled
> by different code paths) does not produce the expected interaction, therefore
> Ack Ratio is currently always 1 and Sequence Window is also static and does
> not change throughout the connection. 
> 
> It may be that both these shortcuts cause the behaviour you observed. The
> Ack Ratio update is disabled in net/dccp/feat.c:dccp_hdlr_ack_ratio(), but
> there is currently no code to predict (guess) what the sending rate will
> be for the next 5 RTTs -- if such a heuristic is possible.

Interesting, but I don't think that's what I'm seeing.

What I'm noticing is that the DCCP sender doesn't update it's ack
numbers very often. In examining packet captures, it is typical for DCCP
to send 20-60 packets with the same ack number (If I increase the ack
and seq validity windows to 1000, I've seen 200 packets with the same
ack number).

Since the receiver should ack every packet it gets, I would think that
we should see very few packets (1-2) sent before a new ack packet comes
and updates the GSR and hence the outgoing packet's ack numbers.

Some debugging output (printk at every send and receive) seems to
indicate that the sending and receiving are happening in large chunks
and not in small slices (we send 50 packets, then receive 20 packets,
etc).

At the moment I don't have a clue why that would happen. Thoughts/ideas
would be appreciated.

> 
> I am interested in suggestions to improve this.
> 
> | In examining this section of code, I also noticed that the the GSR is
> | updated by any packet in the valid sequence number window. I believe
> | this represents a minor bug, because it would allow the GSR to move
> | backward as a result of an out of order packet that is still in the
> | valid window. I am also sending a patch for that as a separate email.
> |
> Excellent catch, there is a second bug here. Apart from the clerical edits
> (please consult Documentation/SubmittingPatches), there is a small
> modification, sent in response to the other patch.

Thanks for the reference to Documentation/SubmittingPatches. Good
information to know.

Comments on the other patch following in a separate email.

Samuel Jero
Internetworking Research Group
Ohio University

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Sequence Number Validation Bug Fixes 0/2

[Gerrit Renker]

| > With regard to not updating the Ack Number, I remember having seen something
| > related earlier. There is a relationship between the current sending rate, the
| > Ack Ratio, the cwnd, and the Sequence Window. The Ack window is advanced by the
| > GSS and depends on the local value of the Sequence Window. RFC 4340, 7.5.2
| > recommends 5 * max_packets_per_RTT as guideline for Sequence Window.
| > 
| > When I looked at this earlier I noted that the dynamic update of Ack Ratio,
| > cwnd, and Sequence Window (which are all inter-related, but are controlled
| > by different code paths) does not produce the expected interaction, therefore
| > Ack Ratio is currently always 1 and Sequence Window is also static and does
| > not change throughout the connection. 
| > 
| > It may be that both these shortcuts cause the behaviour you observed. The
| > Ack Ratio update is disabled in net/dccp/feat.c:dccp_hdlr_ack_ratio(), but
| > there is currently no code to predict (guess) what the sending rate will
| > be for the next 5 RTTs -- if such a heuristic is possible.
| 
| Interesting, but I don't think that's what I'm seeing.
| 
| What I'm noticing is that the DCCP sender doesn't update it's ack
| numbers very often. In examining packet captures, it is typical for DCCP
| to send 20-60 packets with the same ack number (If I increase the ack
| and seq validity windows to 1000, I've seen 200 packets with the same
| ack number).
| 
Depending on the type of link (duplex or half-duplex as in WiFi) and the 
application sending rate, this might even be normal.

In 7.5.2, it is suggested to set the Sequence Window to 5 * packets/RTT where
packets/RTT is the expected maximum number of packets to be sent in one RTT. If
the Sequence Window value is very much larger than this guideline, it could be
that there are no big chances in the acknowledgment number.

But this is only a guess - I think it requires to spend some time with your
tool and/or wireshark traces to see what is going on.


| Since the receiver should ack every packet it gets, I would think that
| we should see very few packets (1-2) sent before a new ack packet comes
| and updates the GSR and hence the outgoing packet's ack numbers.
| 
I think this implicitly refers to cwnd/pipe in CCID-2 which take care of the
window flow control. There is a relationship between cwnd and Ack Ratio (there
are already some comments in ccid2_change_l_ack_ratio, which resulted from
earlier tests which showed that Ack Ratio and cwnd have a relationship.

Since cwnd and rtt determine packets/RTT, this should also allow to derive the
right value for Sequence Window. But this has not been worked out satisfactorily
yet, there is indeed room for more work here.

| Some debugging output (printk at every send and receive) seems to
| indicate that the sending and receiving are happening in large chunks
| and not in small slices (we send 50 packets, then receive 20 packets,
| etc).
| 
Nowadays multiple packets are serviced per interrupt. I have seen similar things
in CCID-3, but these things seem to depend on the link-layer and perhaps also
the network driver, comparing different configurations helps.

Re: Sequence Number Validation Bug Fixes 0/2

[Samuel Jero]

[-- Attachment #1: Type: text/plain, Size: 1309 bytes --]

> | 
> | What I'm noticing is that the DCCP sender doesn't update it's ack
> | numbers very often. In examining packet captures, it is typical for DCCP
> | to send 20-60 packets with the same ack number (If I increase the ack
> | and seq validity windows to 1000, I've seen 200 packets with the same
> | ack number).
> | 
> Depending on the type of link (duplex or half-duplex as in WiFi) and the 
> application sending rate, this might even be normal.

Good point. I hadn't thought of checking whether the network was running
duplex or half-duplex. It turns out that it was running half-duplex
because I had a dumb hub in the testbed setup. 

Once I adjusted the testbed setup to remove the hub, I was able to run
full duplex and DCCP started to work much better. I'm now seeing an
increase in the ack number with almost every packet(which is what I
would expect to see). 

Right now, I'm seeing speeds of 9.43Mbits/sec over a 10Mbit/sec link and
85Mbit/sec over a 100Mbit/sec link (TCP does 91Mbit/sec). Those speeds
seem very reasonable and are much better than anything I have seen yet
in working with DCCP. Is that about what I should expect to get out of
DCCP? Or is it typical to get better performance than that?

Samuel Jero
Internetworking Research Group
Ohio University

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Sequence Number Validation Bug Fixes 0/2

[Gerrit Renker]

| Right now, I'm seeing speeds of 9.43Mbits/sec over a 10Mbit/sec link and
| 85Mbit/sec over a 100Mbit/sec link (TCP does 91Mbit/sec). Those speeds
| seem very reasonable and are much better than anything I have seen yet
| in working with DCCP. Is that about what I should expect to get out of
| DCCP? Or is it typical to get better performance than that?
| 
These tests are very encouraging and the results look really good.

If I recall correctly on similar tests there were not higher numbers. Have you
compared this with TCP on the same link (iperf)?

What can be expected is that CCID-3 will be comparatively slower (CCID-4 has a
fixed limit of about 1.15 Mbps).