[1/4] Adds random ect generation to tfrc-sp sender side

Adds random ect generation to tfrc-sp sender side. Before sending the packet, TFRC-SP chooses randomly
one ect codepoint, returns it and register at the ect history list.

Changes:
 - Creates tfrc_sp_get_random_ect, that uses random.h to choose one ect codepoint
 - Defines tfrc_tx_li_data, that stores data parsed from options loss intervals and dropped packets, and ecn nonce history
 - Defines tfrc_ecn_echo_sum_entry, type of entries of ecn nonce history list
 - Adds memory manage routines and code to these structures

Signed-off-by: Ivo Calado <ivocalado@embedded.ufcg.edu.br>
Signed-off-by: Erivaldo Xavier <desadoc@gmail.com>
Signed-off-by: Leandro Sales <leandroal@gmail.com>


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

| Adds random ect generation to tfrc-sp sender side.

I thought about this and found several reasons why it would be better to
defer ECN Nonce sums to a later implementation.

 1) At the moment the code always sets ECT(0). Even if it would
    alternate ECT(0) and ECT(1), this would later be overwritten by ECT(0)
    in dccp_msghdr_parse(). Ok, this could be fixed, but the real problem
    is that the underlying machinery does not support ECN nonces, since

    * ECN / DiffServ information is in two separate places of the
      inet_sock (u8 `tos' field and u8 `tclass' field of ipv6_pinfo);

    * the ECN driver sits in include/net/inet_ecn.h as
      #define INET_ECN_xmit(sk) do { inet_sk(sk)->tos |= INET_ECN_ECT_0; } while (0)

    * hence this would need to be revised and the best way to make an
      acceptable suggestion would be a coded proof of concept that 
      changing the underlying implementation does have benefits.

    On the receiver side the situation is the same. The function
    tfrc_sp_check_ecn_sum(), introduced in Patch 2/4 of the TFRC-SP sender
    implementation is only referenced in Patch 2/2 of the CCID-4 set, where
    it ends, without side effect in "TODO: consider ecn sum test fail".

    That is, at the moment both the sender and receiver side of the ECN Nonce
    sum verification are placeholders which currently have no effect.


 2) As far as I can see the ECN Nonce is an optimisation, an

      "optional addition to Explicit Congestion Notification [RFC3168]
       improving its robustness against malicious or accidental
       concealment of marked packets [...]" (from the abstract)

    Hence if at all, we would only have a benefit of adding the ECN Nonce
    verification on top of an already verified implementation.

 3) Starting an implementation throws up further questions that need to
    be addressed, both the basis and the extension need to be verified.

I would like to suggest to implement the basis, that is CCID-4 with ECN
(using plain ECT(0)), test with that until it works satisfactorily, and
then continue adding measures such as the ECN Nonce verification.

Nothing is lost, once we are at this stage we can return to this set of
initial patches and revise the situation based on the insights gained 
with ECT(0) experience.

In summary, I would like to suggest to remove the ECN verification for
the moment and focus on the "basic" issues first.

Would you be ok with that?



Appendix
--------
| +int tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn)
| +{
| +	int ect;
| +	struct tfrc_ecn_echo_sum_entry *sum;
| +
| +	/* TODO: implement random ect*/
| +	ect = INET_ECN_ECT_0;
| +
| +	sum = kmem_cache_alloc(tfrc_ecn_echo_sum_slab, GFP_ATOMIC);

For a later implementation, there should be protection against NULL, e.g.
        if (sum == NULL) {
	   DCCP_CRIT("Problem here ...");
	   return 0;
	}
| +
| +	sum->previous = li_data->ecn_sums_head;
| +	sum->ecn_echo_sum = (sum->previous->ecn_echo_sum) ? !ect : ect;

(Also for later) I wonder how to do the sums, with RFC 3168
ECT(0) = 0x2 => !0x2 = 0
ECT(1) = 0x1 => !0x1 = 0

From the addition table in RFC 3540, section 2,
ECT(0) + ECT(0) = 0
ECT(0) + ECT(1) = 1
ECT(1) + ECT(1) = 0

One way could be
        sum->ecn_echo_sum ^= (ect == INET_ECN_ECT_1);
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, Oct 19, 2009 at 2:23 AM, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> | Adds random ect generation to tfrc-sp sender side.
>
> I thought about this and found several reasons why it would be better to
> defer ECN Nonce sums to a later implementation.
>
>  1) At the moment the code always sets ECT(0). Even if it would
>    alternate ECT(0) and ECT(1), this would later be overwritten by ECT(0)
>    in dccp_msghdr_parse(). Ok, this could be fixed, but the real problem
>    is that the underlying machinery does not support ECN nonces, since
>
>    * ECN / DiffServ information is in two separate places of the
>      inet_sock (u8 `tos' field and u8 `tclass' field of ipv6_pinfo);
>
>    * the ECN driver sits in include/net/inet_ecn.h as
>      #define INET_ECN_xmit(sk) do { inet_sk(sk)->tos |= INET_ECN_ECT_0; } while (0)
>
>    * hence this would need to be revised and the best way to make an
>      acceptable suggestion would be a coded proof of concept that
>      changing the underlying implementation does have benefits.
>
>    On the receiver side the situation is the same. The function
>    tfrc_sp_check_ecn_sum(), introduced in Patch 2/4 of the TFRC-SP sender
>    implementation is only referenced in Patch 2/2 of the CCID-4 set, where
>    it ends, without side effect in "TODO: consider ecn sum test fail".
>
>    That is, at the moment both the sender and receiver side of the ECN Nonce
>    sum verification are placeholders which currently have no effect.
>

Okay, then the implementation would be useless now.

>
>  2) As far as I can see the ECN Nonce is an optimisation, an
>
>      "optional addition to Explicit Congestion Notification [RFC3168]
>       improving its robustness against malicious or accidental
>       concealment of marked packets [...]" (from the abstract)
>
>    Hence if at all, we would only have a benefit of adding the ECN Nonce
>    verification on top of an already verified implementation.
>

Yes, not priority at all. And you're right, no benefit.

>  3) Starting an implementation throws up further questions that need to
>    be addressed, both the basis and the extension need to be verified.
>
> I would like to suggest to implement the basis, that is CCID-4 with ECN
> (using plain ECT(0)), test with that until it works satisfactorily, and
> then continue adding measures such as the ECN Nonce verification.
>

Okay. But, when would be good to at least include random ECT
generation? When DCCP ECN code will get fixed? Is there any work on
this?

> Nothing is lost, once we are at this stage we can return to this set of
> initial patches and revise the situation based on the insights gained
> with ECT(0) experience.
>
> In summary, I would like to suggest to remove the ECN verification for
> the moment and focus on the "basic" issues first.
>
> Would you be ok with that?
>

Yes, we'll keep the ECN verification code here at our git until the
scenario is ready.

>
>
> Appendix
> --------
> | +int tfrc_sp_get_random_ect(struct tfrc_tx_li_data *li_data, u64 seqn)
> | +{
> | +     int ect;
> | +     struct tfrc_ecn_echo_sum_entry *sum;
> | +
> | +     /* TODO: implement random ect*/
> | +     ect = INET_ECN_ECT_0;
> | +
> | +     sum = kmem_cache_alloc(tfrc_ecn_echo_sum_slab, GFP_ATOMIC);
>
> For a later implementation, there should be protection against NULL, e.g.
>        if (sum == NULL) {
>           DCCP_CRIT("Problem here ...");
>           return 0;
>        }
> | +
> | +     sum->previous = li_data->ecn_sums_head;
> | +     sum->ecn_echo_sum = (sum->previous->ecn_echo_sum) ? !ect : ect;
>

Thanks, i forgot that.

> (Also for later) I wonder how to do the sums, with RFC 3168
> ECT(0) = 0x2 => !0x2 = 0
> ECT(1) = 0x1 => !0x1 = 0
>

I don't understand. Can you try to explain it? Or cite RFC section
that address it?

> From the addition table in RFC 3540, section 2,
> ECT(0) + ECT(0) = 0
> ECT(0) + ECT(1) = 1
> ECT(1) + ECT(1) = 0
>
> One way could be
>        sum->ecn_echo_sum ^= (ect == INET_ECN_ECT_1);

Ok.

| >    That is, at the moment both the sender and receiver side of the ECN Nonce
| >    sum verification are placeholders which currently have no effect.
| >
| 
| Okay, then the implementation would be useless now.
I was not suggesting to throw away the patches, we can keep them for
later use.

They are a good starting basis once it makes sense to work with ECN.
Or how can we test ECN if we are not sure that the other parts work
as they are supposed to?

| >  3) Starting an implementation throws up further questions that need to
| >    be addressed, both the basis and the extension need to be verified.
| >
| > I would like to suggest to implement the basis, that is CCID-4 with ECN
| > (using plain ECT(0)), test with that until it works satisfactorily, and
| > then continue adding measures such as the ECN Nonce verification.
| >
| 
| Okay. But, when would be good to at least include random ECT
| generation? When DCCP ECN code will get fixed? Is there any work on
| this?
| 
I asked this on netdev earlier, there was not much enthusiasm.

The issue is that ECN belongs both to the network and the transport layer.
This network layer is in inet_ecn.h, outside of DCCP.

I believe that the changes would not be too hard to do, by changing the
macros. But it requires working with the people on netdev, in particular
to ensure it does not break something in the TCP/SCTP subsystems (both
also use ECN, and then there are also raw sockets).

I also have an interest in resolving this, due to the ugliness at the
moment for enabling ECN on IPv6.

RFC 2884, written by one of the Linux ECN developers, describes early
IPv4 ECN evaluation. It seems that initially it was planned to only 
support ECN over Ipv4, parts of the code may be still from that time.

We can pursue this in parallel to the other issues. Ideally this would be
resolved at the time the other parts of CCID-4 are ready for testing.

| > In summary, I would like to suggest to remove the ECN verification for
| > the moment and focus on the "basic" issues first.
| >
| > Would you be ok with that?
| >
| 
| Yes, we'll keep the ECN verification code here at our git until the
| scenario is ready.
| 
I was going to suggest to put them onto a webpage, such as yours, or on 
www.erg.abdn.ac.uk/users/gerrit/dccp there is also still some space.

Can you please elaborate how to keep your git tree and the one on
eden-feed synchronized? At the moment I have not made any changes other
than the ones I emailed you about. Is there a way of keeping both trees
in synch without running into versioning difficulties?

(The simplest way I can think of is to keep the patches in a separate
 set, or to spawn a subtree which contains the ECN patches on top of the
 CCID-4 tree.)


| > (Also for later) I wonder how to do the sums, with RFC 3168
| > ECT(0) = 0x2 => !0x2 = 0
| > ECT(1) = 0x1 => !0x1 = 0
| >
| 
| I don't understand. Can you try to explain it? Or cite RFC section
| that address it?
 
The values are from figure 1, page 7, the expressions evaluate both as 0:

void main(void)
{
	printf("!0x2 = %d, !0x1 = %d\n", !0x2, !0x1);
}
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, Oct 26, 2009 at 4:55 AM, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> | >    That is, at the moment both the sender and receiver side of the ECN Nonce
> | >    sum verification are placeholders which currently have no effect.
> | >
> |
> | Okay, then the implementation would be useless now.
> I was not suggesting to throw away the patches, we can keep them for
> later use.
>
> They are a good starting basis once it makes sense to work with ECN.
> Or how can we test ECN if we are not sure that the other parts work
> as they are supposed to?
>

Okay, we'll keep the patches.

> | >  3) Starting an implementation throws up further questions that need to
> | >    be addressed, both the basis and the extension need to be verified.
> | >
> | > I would like to suggest to implement the basis, that is CCID-4 with ECN
> | > (using plain ECT(0)), test with that until it works satisfactorily, and
> | > then continue adding measures such as the ECN Nonce verification.
> | >
> |
> | Okay. But, when would be good to at least include random ECT
> | generation? When DCCP ECN code will get fixed? Is there any work on
> | this?
> |
> I asked this on netdev earlier, there was not much enthusiasm.
>
> The issue is that ECN belongs both to the network and the transport layer.
> This network layer is in inet_ecn.h, outside of DCCP.
>
> I believe that the changes would not be too hard to do, by changing the
> macros. But it requires working with the people on netdev, in particular
> to ensure it does not break something in the TCP/SCTP subsystems (both
> also use ECN, and then there are also raw sockets).
>
> I also have an interest in resolving this, due to the ugliness at the
> moment for enabling ECN on IPv6.
>
> RFC 2884, written by one of the Linux ECN developers, describes early
> IPv4 ECN evaluation. It seems that initially it was planned to only
> support ECN over Ipv4, parts of the code may be still from that time.
>
> We can pursue this in parallel to the other issues. Ideally this would be
> resolved at the time the other parts of CCID-4 are ready for testing.
>

Ok.

> | > In summary, I would like to suggest to remove the ECN verification for
> | > the moment and focus on the "basic" issues first.
> | >
> | > Would you be ok with that?
> | >
> |
> | Yes, we'll keep the ECN verification code here at our git until the
> | scenario is ready.
> |
> I was going to suggest to put them onto a webpage, such as yours, or on
> www.erg.abdn.ac.uk/users/gerrit/dccp there is also still some space.
>
> Can you please elaborate how to keep your git tree and the one on
> eden-feed synchronized? At the moment I have not made any changes other
> than the ones I emailed you about. Is there a way of keeping both trees
> in synch without running into versioning difficulties?
>
> (The simplest way I can think of is to keep the patches in a separate
>  set, or to spawn a subtree which contains the ECN patches on top of the
>  CCID-4 tree.)
>

Ok, we'll put the patches at our webpage. And about the git, I can't
think a better way too.

>
> | > (Also for later) I wonder how to do the sums, with RFC 3168
> | > ECT(0) = 0x2 => !0x2 = 0
> | > ECT(1) = 0x1 => !0x1 = 0
> | >
> |
> | I don't understand. Can you try to explain it? Or cite RFC section
> | that address it?
>
> The values are from figure 1, page 7, the expressions evaluate both as 0:
>
> void main(void)
> {
>        printf("!0x2 = %d, !0x1 = %d\n", !0x2, !0x1);
> }

Thanks.