Subject: Re: [MMUSIC] ICE issue 1: avoiding the STUN flood

From: Magnus Westerlund <[email-masked]>
Date: Mon, 01 Aug 2005 12:17:01 +0200

Hi Jonathan,

I think the proposal looks good. I think it is a very reasonable 
approach. As you are going to perform checks in semi parallel way there 
will definitely be a need for a timer allowing for certain randomness in 
behavior. Also due to the occasional packet loss the retransmission of 
binding requests needs to be given a reasonable time to be sent and 
returned for the higher prioritized items.

Cheers

Magnus

Jonathan Rosenberg wrote:
> The algorithm in the ICE spec, as currently specified, has each endpoint 
> doing a connectivity check from each of its candidates, to each of its 
> peer candidates, completely in parallel. If you have a multi-homed host 
> with two interfaces, and you have a STUN, TURN server, and you are 
> dual-stack, you end up with 12 candidates and 144 parallel connectivity 
> checks to a similarly equipped peer.
> 
> This presents several problems:
> 
> 1. Magnus had raised this concern some time back, about the congestion 
> load on the network with the checks. This is becoming significant.
> 
> 2. There have been reports of NATs that, if the packet rates are too 
> high, revert to symmetric behaviors. They also limit the number of ports 
> that they'll allocate in some cases.
> 
> As such, we need to adjust the ICE algorithm to deal with this. I have a 
> suggested approach, and I am sure there are others.
> 
> The idea is not to do the checks in parallel, but to start with highest 
> priority pairs first. Each endpoint would basically order each candidate 
> pairing. The ordering would be such that the highest priority pairings 
> are tried first, followed by next lower, and so on. Each endpoint 
> throttles its connectivity checks at a constant rate, such that the 
> bandwidth consumed by those checks is no more than some percentage of 
> the RTP traffic rate for the largest codec in the offer/answer exchange.
> 
> Once a check has succeeded, the endpoint ceases all further checks and 
> then does a re-invite to use that successful candidate in the m/c-line. 
> Probably some random delays need to be added to avoid the glare 
> condition. I'd suggest that the answerer wait an additional 1-2 seconds, 
> and the offerer be the one to immediately try the updated offer.
> 
> This algorithm has the benefit of pacing out the stun traffic in a way 
> similar to RTCP, avoiding pointless checks by doing it for higher 
> priority candidates first, and (I think) speeding up convergence.
> 
> Suggestions, comments or improvements?
> 
> I'd need to do some work to come up with specific numbers so that this 
> works reasonably well.
> 
> Thanks,
> Jonathan R.

-- 

Magnus Westerlund

Multimedia Technologies, Ericsson Research EAB/TVA/A
----------------------------------------------------------------------
Ericsson AB                | Phone +46 8 4048287
Torshamsgatan 23           | Fax   +46 8 7575550
S-164 80 Stockholm, Sweden | mailto: [email-masked]

_______________________________________________
mmusic mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/mmusic

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 16 Aug 2005 20:19:31 -0400

We talked about this during the meeting, and in the discussion it became 
clear that this whole thing would require more consideration. There were 
two issues:

1. the actual address allocation step itself might cause the flood,
2. the algorithm below would appear to result in special treatment for 
the initial setup, different than the treatment that would occur after 
the initial exchange. This doesnt work well with offer/answer, where you 
want idempotency of o/a exchanges.

Let me address (2) first since its easier. My proposal would be that 
there is a state machine associated with each candidate pair. When an 
o/a exchange is done that results in a new candidate pair, the state 
machine is instantiated into the "pending" state. Throughout the 
lifetime of a session, an agent has a leaky bucket that emits a token 
with some period (say, every 50ms). When a token is emitted, the 
candidate pair in  pending state with the highest priority has its 
checks started. It then moves into the "trying" state, and eventually 
gets verified. Once its verified, checks are sent for it at a regular 
interval. If a later O/A exchange occurs that remove candidates while 
still in the pending state, thats fine - they are just removed. If a new 
one comes that adds candidates, thats fine, we create more pairs in the 
pending state, and checks for those eventually start when a token is 
available. This basically decouples the pacing of the connectivity 
checks from the O/A exchanges themselves.

If folks are OK with this, I'll put it in ICE-06, with sufficient 
explanation of course.

Now, (1) is the harder one. There are a few things that can be done:

1. limit the number of needless addresses that get allocated. For 
TURN-allocated addresses, its probably sufficient to allocate an address 
from a particular TURN server from just one local interface.

2. If a client has multiple interfaces of the same IP version (i..e, two 
v4 interfaces), it can perform stun connectivity checks between its own 
interfaces, and in fact use stun to determine if there is a nat between 
them. If the two are mutually reachable with no nat between, there is 
probably no point in using both to allocate addresses; it should pick 
the higher priority one and just use that. Does anyone see any concerns 
with doing this?

3. The allocations can themselves be paced out. If you want to reduce 
call setup delays, after you've obtained a few you can do the INVITE, 
and continue to allocate more. If you need more allocated addresses 
because your about to complete connectivity checks for the ones you 
allocated already and had sent in the INVITE, you do a re-invite to add 
more candidates. If you do the allocations such that you obtain the high 
priority addresses first, this has the nice effect of using just a 
single INVITE and a few allocations when the highest priority addresses 
actually work; you incur additional post-dial delays and signaling 
exchanges only as you end up scaling back to the lower priority 
addresses (including the tcp alternates). So the nice thing is in most 
cases, even if tcp alternates are supported, you'd probably never even 
allocate tcp addresses unless you were in a bad network deployment.

I'd recommend that the spec RECCOMMEND (1) in concert with (3). (2) 
might work, but I don't like it since it makes assumptions on 
reachability, and assumptions are bad. If folks like it and think it 
works, I could put it in at MAY strength I suppose...

Thanks,
Jonathan R.

Magnus Westerlund wrote:

>> The algorithm in the ICE spec, as currently specified, has each 
>> endpoint doing a connectivity check from each of its candidates, to 
>> each of its peer candidates, completely in parallel. If you have a 
>> multi-homed host with two interfaces, and you have a STUN, TURN 
>> server, and you are dual-stack, you end up with 12 candidates and 144 
>> parallel connectivity checks to a similarly equipped peer.
>>
>> high, revert to symmetric behaviors. They also limit the number of 
>> ports that they'll allocate in some cases.
>>
>> As such, we need to adjust the ICE algorithm to deal with this. I have 
>> a suggested approach, and I am sure there are others.
>>
>> The idea is not to do the checks in parallel, but to start with 
>> highest priority pairs first. Each endpoint would basically order each 
>> candidate pairing. The ordering would be such that the highest 
>> priority pairings are tried first, followed by next lower, and so on. 
>> Each endpoint throttles its connectivity checks at a constant rate, 
>> such that the bandwidth consumed by those checks is no more than some 
>> percentage of the RTP traffic rate for the largest codec in the 
>> offer/answer exchange.
>>
>> then does a re-invite to use that successful candidate in the 
>> m/c-line. Probably some random delays need to be added to avoid the 
>> glare condition. I'd suggest that the answerer wait an additional 1-2 
>> seconds, and the offerer be the one to immediately try the updated offer.
>>

-- 
Jonathan D. Rosenberg, Ph.D.                   600 Lanidex Plaza
Director, Service Provider VoIP Architecture   Parsippany, NJ 07054-2711
Cisco Systems
[email-masked]                              FAX:   (973) 952-5050
http://www.jdrosen.net                         PHONE: (973) 952-5000
http://www.cisco.com

---

From: Magnus Westerlund <[email-masked]>
Date: Mon, 22 Aug 2005 17:23:38 +0200

Hi,

I think the below proposals seems reasonable but I do have some comments 
below. I think the important is to have some mechanism that avoids a 
flood and still provides decent performance. We probably should include 
some back of an envelope calculations what this would mean in bit-rate, 
etc for a reasonably well connected peer. This to ensure that we at 
least are in the right domain with the figures. That way one can also 
have some arguments on how to scale things down even more if needed by 
the application.

> If folks are OK with this, I'll put it in ICE-06, with sufficient 

So if I understand this correct each token will start a new connectivity 
check. Each check has its own timers etc to do retransmissions and 
keep-alives. That way one limits the start of the checks so that initial 
packet transmission usage before any timers expires are paced by the 
tokens. The total bandwidth will still be dependent on the number of 
checks as each check will use a specific amount assuming if is failing. 
My question is really what happens in the interaction between the check 
starter that solves the initial problem and the retransmissions and 
keep-alives.

Hopefully it would result in a ramp function, that is most likely to be 
cut short due to high priority checks are successful.

^ Bit-rate
|            _______
|          _/
|        _/
|      _/
|-----/
|
  ------------------------> t

T0   T1    T3

T0 Checks start
T1 First Retransmission Timer expires
T3 All Retransmission Timers have expired at least once

Between T0 and T1 the bucket paces the transmission to one STUN request 
per token. After T1 if we have enough checks there will still be one 
check per token, in addition the retransmission timers expires and more 
and of them does and provide an increase in bit-rate until T3 when all 
checks have been paced out and are in retransmission phase. What is 
missing is the reduction due to that all checks has been initiated.

> from a particular TURN server from just one local interface.

Sounds good.

> the higher priority one and just use that. Does anyone see any concerns 

Agree with the potential issues that exist due to connectivity checks. 
Some interfaces may not be real interfaces and performing checks between 
them may not result in packets leaving the peer at all.

> allocate tcp addresses unless you were in a bad network deployment.

I think that one should recommend that any pre-session gathering should 
be done in a paced way also. Also keeping the number of gathered address 
to a reasonable number should be recommended.

> works, I could put it in at MAY strength I suppose...

Sound good.

-- 

Magnus Westerlund

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 24 Aug 2005 00:14:25 -0400

Thanks for the insightful comments as always, Magnus. Replies inline.

> have some arguments on how to scale things down even more if needed by 

Agree. I will work on some real figures.

Does anyone have some useful data on the kind of rates that upset NATs? 
The premise here was not just network congestion, but that nat behaviors 
changed and/or nats failed when bindings were allocated too rapidly.

>> We talked about this during the meeting, and in the discussion it 
>> became clear that this whole thing would require more consideration. 
>> There were two issues:
>>
>> the initial exchange. This doesnt work well with offer/answer, where 
>> you want idempotency of o/a exchanges.
>>
>> still in the pending state, thats fine - they are just removed. If a 
>> new one comes that adds candidates, thats fine, we create more pairs 
>> in the pending state, and checks for those eventually start when a 
>> token is available. This basically decouples the pacing of the 
>> connectivity checks from the O/A exchanges themselves.
>>
> tokens.

Right. So, the tokens pace the start of STUn transactions, rather than 
each STUn message itself. I had thought about having the tokens pace 
stun messages, but this means we need to radically change the stun 
protocol itself. We don't need precise control over bandwidth; just a 
basic pacing capability that gives us a range to work in.

> The total bandwidth will still be dependent on the number of 

Right. So, each check has minimum and maximum bandwidth. If you pace the 
checks, you end up with a range of min to max bandwidth.

> T3 All Retransmission Timers have expired at least once

Yes, it would be something like this.

The rate hits a maximum not just because you succeed and don't try more, 
but also because the bandwidth for stun retransmits itself decays 
exponentailly.

>> allocated already and had sent in the INVITE, you do a re-invite to 
>> add more candidates. If you do the allocations such that you obtain 
>> the high priority addresses first, this has the nice effect of using 
>> just a single INVITE and a few allocations when the highest priority 
>> addresses actually work; you incur additional post-dial delays and 
>> signaling exchanges only as you end up scaling back to the lower 
>> priority addresses (including the tcp alternates). So the nice thing 
>> is in most cases, even if tcp alternates are supported, you'd probably 
>> never even allocate tcp addresses unless you were in a bad network 
>> deployment.
> 
> 

Right, that is basically what I am proposing.

-Jonathan R.