Re: CUD and FBD

[marcelo bagnulo braun <marcelo@it.uc3m.es>]

Hi Erik,

sorry for the delay...

El 14/09/2005, a las 19:54, Erik Nordmark escribió:

> marcelo bagnulo braun wrote:
>
> > In CUD, each node waits for a given time Tu for ULP feedback. If no 
> > feedback is received during Tu seconds, then it probes reachability 
> > by sending probes. This means that it will send a probe and wait for 
> > To for the answer to come back. It will probably send several probes, 
> > e.g. m probes. The node will wait for w seconds between each probe.
> > So the time required in FBD would be: n*t seconds
> > And the time required in CUD would be Tu + To + (m-1)w
>
> Presumably To=w,

right, but i think we discussed once the possibility that w being much 
smaller than To (i.e. pessimistic approach) in order to have a faster 
detection/reaction. In any case i agree that for the purpose of the 
comparison assuming To similar to w makes sense.

>  but to avoid causing congestion, presumably CUD needs to do binary 
> exponential backoff.

i would like to understand a bit more if this is really needed...
First of all, the gaol of these set of probes is to determine that a 
failure occurred so that an alternative path is used (i note this, as 
opposed to other cases, where exponential backoff is used, where the 
sender just give up sending)
In this case, including an exponential backoff would result in an 
exponential increased delay/response time, since in every case that an 
outage has really occurred, all the exponential backoff process needs 
to finnish, right?
So using exponential backoff here would result in a worse performance 
of the shim (additional delay/interruption in the communication)
OTOH, i think that the number m considered will be somehow low (in 
order of 3 or 4 perhaps?) so, i am not sure that these would result in 
much additional congestion (while the exponetial increasing time with 4 
iterations may be somehow high, i guess)

>  (NUD doesn't do this, since it assumes that the local link isn't 
> likely to suffer congestive collapse from only the NUD probes, but for 
> the end-to-end path I don't think this assumption holds.)
>
> This raises the question whether the packets generated by FBD needs to 
> be concerned about congestion control.
> If we have a simple model of the network where the paths are symmetric 
> and traffic volume is symmetric, then one can definitely argue that 
> FBD does no need this, because at most it sends one packet for every 
> received packet. (Only if a packet has been received in the last t 
> seconds and the ULPs haven't sent anything back, will FBD send a 
> keepalive.)
>
> But the limit on FBD (of at most sending one packet in response to one 
> received packet) means that it exhibits the same behavior as TCP SYNs 
> and DNS queries; in those cases the protocols do not apply any 
> congestion control to the "responder" but does assume that the 
> "requestor" handles congestion avoidance (by retransmitting using 
> binary exponential backoff.)
>
> So my take is that FBD doesn't need binary exponential backoff, which 
> would be a great benefit.

yes that would be my understanding also, BTW i am not sure i understand 
how FBD could implement an exponential backoff, since the other end is 
expecting a given frequency of incoming packets... implemeting an 
exponential backoff would imply that packets are generated more and 
more spaced in time, so the other end would not receive a fixed 
frequency of incoming packets, right?



> > Now i think that for the comparaison, and if the expected resiliency 
> > is to be similar, we could assume that n = m (the number of probes is 
> > the same).
> > Also, that Tu will be smaller or similar to t, since Tu is the 
> > timeout of the application, and t is the default timeout of the shim.
>
> I NUD Tu isn't related to the application/ULP timeout; instead it is a 
> protocol constant (which is picked so that with high probability if 
> there will be ULP positive advice it will arrive in less than Tu 
> seconds). Basically you want it to be at least Rtt + ack delay (to 
> handle protocols like TCP that implements delayed acks).

right, that is why i assumed that Tu is smaller than t (Tu is the 
timeout of the app, which should know better than the shim, which has a 
generic (by default) tiemout t)

> Another thing to look at is whether the timers can be dynamic, or keep 
> them static as in NUD. Since shim6 is end-to-end I think it makes 
> sense to make them dynamic.
> In CUD, when the probes are not supressed, then the probe+response can 
> be used by the host to determine the roundtrip time, hence it can be 
> the basis for the "w" timeout.

agree

> In FBD it is not clear to me what techniques can be used to make "t" 
> be a function of the Rtt. Any ideas?

interesting question...

i guess that t is not directly affected by the value of the RTT but t 
is affected by the variations of the RTT.
I mean, if the RTT remains constant, then it doesn't matter if it is 1 
ms or 500 ms, because t is the time between probes, so it is only 
related to the rate at which the sender generates probes. the RTT would 
impact the time that it takes the first packet to arrive but not to the 
time between packets, right?

However, it the RTT changes during the communication, then the 
variation in the RTT would be added to the t.

I mean, suppose that the sender is generating probes each t seconds.
Until now, the RTT was fixed.
this means that the receiver is receiving probes each t seconds.

Now, the RTT increases in dRTT, so that it results in RTT+dRTT.
this means that the next packet won't be received in t seconds but in 
(t+dRTT/2)seconds, right?

So, in order to make the t adaptive, we would need to measure the 
variations in the RTT... this could be done if the receiver of the 
probes can feedback the sender of the probes about the variations in 
the times between received probes... but i am getting the feeling that 
this may be too much complexity and i am not sure if it is worthy...

> > - Overhead
> > In CUD, each time there is an idle period, 2 packets are generated, 
> > one in each direction.
>
> I don't think that is necessary (assuming ULP advice).
>
> A sends packet to B, and B sends a packet back shortly there after. 
> Then things go idle.
> This means that the reachability state will move from REACHABLE to 
> UNKNOWN (RFC 2461 uses a slightly different description).
> If A then goes to send a packet, we can use the DELAY state idea from 
> RFC 2461 to avoid sending an immediate probe. As long as B responds 
> and the ULP on A passes down positive advice, any probe from A to B 
> can be supressed. Whether B ends up probing A is more difficult to 
> tell; if B receives packets from A (need multiple packets) that 
> indicate to the ULP on B that A has received it's ack, then the ULP on 
> B can provide positive advice.

right, but i was comparing the worse scenario (which for the overhead 
implies that no ULP feedback is provided, so periodic keepalive tests 
are required)

> But if there is no positive advice from the ULP, the overhead would be 
> 4 packets when the flow restarts (a probe from each direction, which 
> each of them being acknowledged). This could be minimized to 3 but 
> can't do any better to verify that both directions are working.

right. However, i we consider the possibility of using packet flow as 
an indication that the things are working, then this case that you are 
presenting would not generate any additional packet since the data 
packets would serve as an indication that things are working. In this 
case, the worse case is an ULP that doesn't provides feedback to the 
shim and that it generates unidirectional flow, in which case the 
sender has to generate periodic keepalives tests, adding two extra 
packets.
(but i guess that what we need to discuss first is about the usage of 
data packets as an indicator that things are working, which i will 
address below)

> > In FBD, each time there is an idle period, i packet is generated
>
> "i" or "1"??

1 (sorry for the typo)

> I think this can actually be zero extra packets, depending on details 
> of  the time period FBD uses to "measure" received and transmitted 
> packets.
>
> A sends a packet to B, and B responds in time period 0. No need to 
> send extra packets.
> The communication is silent in time period 1,2,3, and 4.
> In time period 5, A sends a packet to B, and B responds. Both ends 
> have sent and received in time period 5, hence no need to send a 
> keepalive.
>
> Only if the packet arrives at B at the very end of time period 5 so 
> that the ULP response is sent by B in time period 6, would FBD cause 
> an extra packet. Presumably one can avoid that by having FBD, after an 
> idle period, start the new time period when the first packet is 
> received.

i was considering again an unidirectional flow. In this case the 
receiver would need to generate periodic packets (since it does not 
generates data packets) right?

> > FBD imposes half of the overhead than CUD
> > [Note: As currently defined in the draft, if there is no ULP 
> > feedback, CUD will periodically generate probes, which would greatly 
> > increment the overhead imposed by CUD when the ULP does not provides 
> > feedback (e.g. UDP) resulting in an overhead much greater than the 
> > double of the one of FBD . However, i think that not only ULP 
> > feedback can be used as an indicator of communication progress, but 
> > also the reception of packets could be assumed as an indication of 
> > progress. In this case, the overhead of CUD would be the double of 
> > the one in FBD]
>
> FWIW I don't think reception of packets can be an indication in CUD 
> that the bidirectional path is working.
> If A is transmitting packets to B, and B is acking, but the acks don't 
> make it to A, then B will continue to receive (ULP retransmitted) 
> packets from A for a few minunutes, even though the path from B to A 
> is broken.

right, but A won't receive any packets and would start path exploration 
procedure.
I mean, in this case, the node detects outages in its incoming path, 
i.e. A is the one that will detect the outage.

In other words, a necessary condition for a failure is that at least 
one of the communicating nodes is not receiving packets. this is not a 
sufficient condition for a failure, since traffic can be unidirectional 
(in which case, the above condition is meet but no outage has occurred)
In the case of unidirectional communications, explicit reachability 
tests are required in CUD

So, the point is to use use the absence of incoming packets as an 
indicator that an explicit reachability test is required (in order to 
differentiate a failure from an unidirectional flow)

In this extended CUD scheme there are three elements in the failure 
detection:
- ULP feedback
- incoming traffic
- explicit reachability tests

Regards, marcelo



>    Erik