Re: [tcpm] poll for adoption of long connectivity disruptions draft

[Alexander Zimmermann <[e-mail]>]

Hi Joe,

first of all, thank you very much for your valuable comments! Since  
I'm not sure
I understand you correctly, I break down our problem to a concrete  
example with
we can play with.

* If I understand you correctly in this threat as well in the threat  
"WG Last
Call for ICMP Attacks", the "possibility" and the "impact" of a false  
positive
is something different and both should be included in our I-D. Till  
now only the
"possibility" is included. I will fix that.

* Every time I had the problem "RTO-based loss recovery AND router can  
delay to
send/generate ICMPs AND sequence space can wrap" in mind, I mean problem
"B.4.2". However, I have the feeling you mean problem "2.4.2". Right?

Alex

---

Situation:

S (Source) ---------------- R (Router) ---------------- D (Destination)

- At time t0, a steady state TCP flow with packets p1,...,pn in flight  
between a
   source S and a destination D. Packets are routed by an intermediate  
router R.

- At time t1 a connectivity disruption occurs at router R.

- At time t2, S starts to send RTO based retransmissions r1,...,rm and  
backs off
   and undoes according the algorithm.

- At time t3, the connection is re-established

- At time t4, the sequence space wraps

- At time t5, the connection is in RTO-based loss recovery again


The following scenarios are possible, when ICMP DUs for the packets  
p1,...,pn
are delayed for a longer time (or are not generated at all):

1. R does not generate ICMP DUs for p1,...,pn (congestion)
    => Backoff according to RFC 2988, no undo by design.

2. R generates ICMP DUs for p1,...,pn
   2.1 S receives ICMP DUs BEFORE t2 (standard)
       => Impact: None. ICMP DUs are ignored by design.

   2.2 S receives ICMP DUs AFTER t2, but BEFORE t3
       => Impact: Retransmission ambiguity. To be considered as not  
harmful.
       (described in I-D section 4.3, para 5)

   2.3 S receives ICMP DUs AFTER t3, but BEFORE t5
       => Impact: None. ICMP DUs are ignored by design.

   2.4 S receives ICMP DUs AFTER t5
     2.4.1 RTO due to connectivity disruption
       => Impact: No false positives since we count backoffs.

     2.4.2 RTO due to congestion
       => Impact: one false positive possible
       => Possibility: at most n/2^32
       (not described in I-D yet!!!)


The following scenarios are possible, when ICMP DUs for the  
retransmissions
r1,...,rm are delayed for a longer time (or are not generated at all):

A. R does not generate ICMP DUs for r1,...,rm (congestion)
    => Backoff according to RFC 2988, no undo by design.

B. R generates ICMP DUs FOR ALL r1,...,rm
   B.1 S receives ICMP DUs BEFORE t3
       => ICMP DUs are exploited by design. => Undo

   B.2 S receives ICMP DUs AFTER t3, but BEFORE t5
       => Impact: None. ICMP DUs are ignored by design.

   B.3 S receives ICMP DUs AFTER t5
     B.4.1 RTO due to connectivity disruption
       => Impact: No false positive since we count backoffs.

     B.4.2 RTO due to congestion
       => Impact: at most m false positives
       => Possibility: at most 1/2^32
       (described (not completely correct) in I-D section 4.3, para 6)


B.1) A steady state TCP flow between a sender S and a destination D is  
disrupted
at some router R. The first few RTO retransmissions trigger ICMP DUs  
at R, but
are delayed by it. Then, while S is still in the same loss recovery  
phase, the
accumulated ICMPs are emitted by R and received by S, triggering  
multiple
reversions. This is safe, as the result would be the same, when ICMPs  
were
emitted instantly.

B.2) A steady state TCP flow between a sender S and a destination D is  
disrupted
at some router R. The first few RTO retransmission trigger ICMP DUs at  
R, but
are delayed by it. Then, connectivity is re-established by a successful
retransmission and S leaves the loss state. If the delayed ICMPs are  
emitted by
R now, they will have no effect on S.

2.4.2) A steady state TCP flow between a sender S and a destination D is
disrupted at some router R. Each packet p[i], which is in flight from  
S to T
passes R and may (ICMP rate limiting) trigger a DU message, which is  
delayed
at R. Afterwards, when the link outage is over, the connection is
re-established, and S slow-starts the connection. When the sender's TCP
performs a sequence number wrap and approaches the sequence numbers of  
p[i],
an RTO occurs and S enters RTO-based loss recovery. Now, R emits the  
delayed
ICMPs for the p[i] of the last sequence number cycle, which may  
trigger one
false reversion. In case of congestion, this leads to one false
retransmission, while in the case of another link outage, the additional
reversion is harmless. However, it is at most one false reversion, as  
long
as we assume only one sequence number cycle of delayed ICMPs. The  
probability of
this to happen depends on the number of packets which are in flight  
towards R.

B.4.2) A steady state TCP flow between a sender S and a destination T is
disrupted at some router R. The sender performs multiple consecutive RTO
retransmissions, but the corresponding ICMPs are delayed by R. Then,  
after
several more retransmissions, connectivity is re-established and S  
leaves
loss state. A sequence space wrap later, the path is disrupted again,  
exactly
at the time at which the current SND.UNA matches the SND.UNA form the  
previous
cycle. If the router R emits the delayed ICMPs now, but is currently  
congested,
S will undo the multiple backoffs falsely. The probability of this  
should be at
most 1 to 4 billion.
Given sufficiently many RTO retransmissions in the first loss phase, the
corresponding ICMPs can pull the RTO in the second loss phase from  
MAX_RTO
to the initial RTO. However, once the ICMPs are depleted, standard  
exponential
backoff will be performed. Roughly speaking, the standard congestion
response will be delayed by a few false retransmissions, and after
log2(MAX_RTO/MIN_RTO) of those retransmissions, MAX_RTO is reached  
again.

//
// Dipl.-Inform. Alexander Zimmermann
// Department of Computer Science, Informatik 4
// RWTH Aachen University
// Ahornstr. 55, 52056 Aachen, Germany
// phone: [phone], fax: [phone]
// email: [e-mail]
// web: http://www.umic-mesh.net
//