TWiki > DNA > DNASolution1 > DNASoln1Issue014	TWiki webs: Main | TWiki | Know | Sandbox
	DNA . { History of Changes | DNA Documents | Search | Go }

TBF vs RDA

I think we should flag the issue of RDA v.s. TBF as an issue and leave it
there.

Some of the mods that Erik and Sathya have suggested to TBF over the last
couple days seem like they would help, but I think it makes more sense to
let the WG decide.

Discussion

Sathya

I apologize for all this confusion. Hopefully the following clarifies my thoughts:
1) I think the router should not just continue responding to RS messages with unicast RA following the token bucket becoming empty because it makes it possible for an attacker to keep sending one RS every UnicastRAInterval and continue using up the tokens. Hence moving into multicast mode for a period after the bucket becoming empty is good. 
2) But instead of moving to ONLY multicast responses mode abruptly, I think RDA allows for the transistion to be smooth and allows for some unicast responses probabilistically while allowing the token bucket to be replenished. For an attacker to continue using up the token, he will have flood the link with a lot of RS messages, because the probability of dropping increases with the increased RS rate. This way we have changed the token bucket attack into a flooding attack.

Erik

> I apologize for all this confusion. Hopefully the following clarifies my thoughts:
> 1) I think the router should not just continue responding to RS messages with unicast RA following the token bucket becoming empty because it makes it possible for an attacker to keep sending one RS every UnicastRAInterval and continue using up the tokens. Hence moving into multicast mode for a period after the bucket becoming empty is good. 


Does this concern of yours only apply to TBF? To me it seems as much an issue for RDA, because an attacker can just send at the Max rate and force RDA to do only multicast.

> 2) But instead of moving to ONLY multicast responses mode abruptly, I think RDA allows for the transistion to be smooth and allows for some unicast responses probabilistically while allowing the token bucket to be replenished. For an attacker to continue using up the token, he will have flood the link with a lot of RS messages, because the probability of dropping increases with the increased RS rate. This way we have changed the token bucket attack into a flooding attack.


Are you assuming that the max RDA rate is orders of magnitudes larger than the Min RDA rate?
If you don't, then your argument doesn't make sense to me.
If you do, then it seems like you are allowing an RS rate which is significantly larger than the min rate, thus I don't understand what limit you are trying to apply.

Thus if max = 2*min, then the sustained rate of RSs is limited to about 1.5*min, but the attacker can just send 2*min rate of RAs and force multicast mode.

If max = 100*min, then you can argue that the attacker needs to do a lot more work to exceed max, but the counterargument is that now you have an RS rate limit of 51*min.

>> And in the mail titled "Random Drop Algorithm" that you sent just after this one, you explained how random drop does send some unicast RAs after the token bucket has become empty. So which behavior do you want?
>
>
>
> I want some unicast RAs to be sent - but not determinsitically, because it makes it easy to be attacked.


Please look at the above and state what your assumption is about
 - the ratio between the max and min parameters in RDA
 - what average unicast RA rate you want to constrain the router to send

I think what you are trying to do amounts to keeping the cake and eating it too.

Something which is quite similar to RDA as you describe it can be accomplished by a TBF scheme which still adds tokens as a fixed average rate, but not at fixed, predictable time intervals (i.e., instead of adding a token say every 50 ms, a token is added using a random process whose average is 50 ms).

Do you see how such a scheme would satisfy your request form non-determinism?

FWIW, I don't think that this non-determinism makes a bit of a difference for the attacker. It is the capping of the rates and the amplification (#routers on the link, and ratio of size of RA vs RS) that matters for the attacker.

But perhaps we should agree that we disagree on this point.

   Erik 

Jim

>>I apologize for all this confusion. Hopefully the following clarifies my
>>> > thoughts:
>>> > 1) I think the router should not just continue responding to RS messages
>>> > with unicast RA following the token bucket becoming empty because it
>>> > makes it possible for an attacker to keep sending one RS every
>>> > UnicastRAInterval and continue using up the tokens. Hence moving into
>>> > multicast mode for a period after the bucket becoming empty is good.
>
>>
>> Does this concern of yours only apply to TBF? To me it seems as much an
>> issue for RDA, because an attacker can just send at the Max rate and
>> force RDA to do only multicast.
>>


One issue for TBF is that after multicasting, the bucket gets filled again,
and so the router starts unicasting. So under sustained attack, the router
doesn't switch into multicast-only mode. The bucket will get quickly
depleted of course, but it still adds to congestion on the link. I can't see
any way to do this with TBF because it is not measuring the arrival/response
rate, so it has no way to determine whether the router is under attack or
not. The only way to do it is to use some kind of measurement, like RDA
does. So it is true that an attacker can force RDA to do multicast only, but
I actually see that as an advantage. It reduces traffic volume on the link,
until someone has an opportunity to find the attacker and shut them down.


>>> > 2) But instead of moving to ONLY multicast responses mode abruptly, I
>>> > think RDA allows for the transistion to be smooth and allows for some
>>> > unicast responses probabilistically while allowing the token bucket to
>>> > be replenished. For an attacker to continue using up the token, he will
>>> > have flood the link with a lot of RS messages, because the probability
>>> > of dropping increases with the increased RS rate. This way we have
>>> > changed the token bucket attack into a flooding attack.
>
>>
>> Are you assuming that the max RDA rate is orders of magnitudes larger
>> than the Min RDA rate?
>> If you don't, then your argument doesn't make sense to me.
>> If you do, then it seems like you are allowing an RS rate which is
>> significantly larger than the min rate, thus I don't understand what
>> limit you are trying to apply.
>>
>> Thus if max = 2*min, then the sustained rate of RSs is limited to about
>> 1.5*min, but the attacker can just send 2*min rate of RAs and force
>> multicast mode.
>>
>> If max = 100*min, then you can argue that the attacker needs to do a lot
>> more work to exceed max, but the counterargument is that now you have an
>> RS rate limit of 51*min.
>>
>
>>>> >> And in the mail titled "Random Drop Algorithm" that you sent just
>>>> >> after this one, you explained how random drop does send some unicast
>>>> >> RAs after the token bucket has become empty. So which behavior do you
>>>> >> want?
>>
>>> >
>>> >
>>> > I want some unicast RAs to be sent - but not determinsitically, because
>>> > it makes it easy to be attacked.
>
>>
>> Please look at the above and state what your assumption is about
>>   - the ratio between the max and min parameters in RDA
>>   - what average unicast RA rate you want to constrain the router to send
>>
>> I think what you are trying to do amounts to keeping the cake and eating
>> it too.
>>
>> Something which is quite similar to RDA as you describe it can be
>> accomplished by a TBF scheme which still adds tokens as a fixed average
>> rate, but not at fixed, predictable time intervals (i.e., instead of
>> adding a token say every 50 ms, a token is added using a random process
>> whose average is 50 ms).
>>
>> Do you see how such a scheme would satisfy your request form
>> non-determinism?
>>


Yes, this would be acceptable. And I agree that it would be simpler than the
moving average calculation I sent out to estimate the rate. We could also
scale the probability as D = (MIN_DELAY_BETWEEN_RAS - t), where t is the
number of msec from deterministic unicast bucket exhaustion. The probability
is easy to generate, just calculate F = D / MIN_DELAY_BETWEEN_RAS, then
generate a random number X between [0,1]. If X > D, then generate a token,
otherwise drop the packet. No need for a complex Poisson calculation.

But it would not fix the problem of the bucket getting filled again after
the multicast.


>> FWIW, I don't think that this non-determinism makes a bit of a
>> difference for the attacker. It is the capping of the rates and the
>> amplification (#routers on the link, and ratio of size of RA vs RS) that
>> matters for the attacker.
>>
>> But perhaps we should agree that we disagree on this point.
>>


I believe it makes a difference for congestion and for ensuring that an
average number of nodes get service on the link in nonattack but overload
situations, particularly when coupled with random backoff from the host
side. But to actually prove this would take constructing a simulation of
both cases and trying them out, something I'd love to do but simply don't
have the time to do right now.

So, yes, we will have to agree to disagree on this point.

            jak

-- Main.SathyaNarayanan - 29 Apr 2005

Back to DNA Issue Tracker Base Page