[xcp] Paper on XCP for shared-access links

[Filipe Abrantes]

Hello Yuri,

Yuri Pradkin wrote:
> Hi, Filipe, 
> 
> thanks for the link, the paper is very interesting.  A few of comments:
> 
thanks for taking the time to read it

> 1. It was not very clear from the paper how the upper bound on \chi, 
> 1/(5-\alpha-\beta) was derived to guarantee that the queue never 
> overflows.  I got the impression that it was from a fluid-model 
> simulation of a single flow shown in fig 4.  My concern is that this 
> bound will not hold in case d != rtt, as might be when the traffic is 
> a mix of flows with different RTTs.
> 
Yes, the bound is derived from analysing the step by step system 
variables in the worst case scenario (Fig. 4). It assumes that the flows 
receiving the feedback have an rtt = d. If the flows have heterogeneous 
rtt's, then we expect d = avg_rtt and we should observe some 
compensatory behaviour from different flows (flows with rtt < d reacting 
quick to compensate late behaviour of flows with rtt > d), but we 
haven't really analysed that situation. In the simulations we have done, 
with flows with mixed rtt's [40-370]ms (those in the comparison with TCP 
section 4.3), if I remember correctly, queue overflow never occurred.

I should add that this is the worst case scenario which is not too 
common, and that the queue peak decreases exponentially with the initial 
over-estimation. Initial over-estimation in the worst-case is \chi*q_max/d.

> 2. I thought it might be desirable to preserve continuity in the 
> feedback function F in order to avoid oscillations and perhaps make 
> analysis more tractable.  Have you considered having F increase 
> gradually with time from 0 to something if q=0 && dq/dt=0?  I guess 
> Your "Late reaction" idea comes close to that.
> 

Oscillations between the two modes is one of the weakest points in xcp-b 
in my opinion, as the equilibrium point (full utilization) is too thin. 
   We may have too many oscillations when arrival of flows is more 
dynamic.  What you propose may be a good idea. I had thought of 
exponentially adapting F to F_max (\chi*Q_max/d) after under utilization 
has been detected. For example F_max/8, F_max/4, F_max/2, F_max in the 
subsequent intervals, but I haven't yet tried it. I expect this to 
produce lower queue peaks in scenarios of more dynamic arrival of flows.


> 3. Re your queue frequency response analysis (fig3), there's been a 
> more rigorous analysis of XCP stability in "Stability Analysis of 
> Explicit Congestion Control Protocols" by Hamsa Balakrishnan.
> 

I will look into it. Thanks for the reference.
(is some text missing above in "3.Re your..."?)


> 4. After we switched to "X" in packet headers in place of throughput 
> (and X can be thought of as inter-packet time), I've been on and off 
> thinking about recasting the whole XCP calculations in the time 
> domain.  Presumably the queue controller will have to use MAC idle 
> time instead of (C - input_bw).  I've never got around to finishing 
> this line of thought, but it just seems it might be related to the 
> whole capacity estimation problem.
>

Yep, measuring MAC idle time and assigning it a bandwidth value based 
the average bandwidth of the MAC busy time would be another option. I 
think it becomes trickier when you think of mesh or ad-hoc scenarios, as 
you may have to track the number of active stations and maybe other 
stuff. It sort of becomes technology dependent too. I liked this 
approach of not caring too much in the details of the underlying 
technology, other than assuming it provides a fair random access.


Filipe


>   -Yuri
> 
> On Monday 10 July 2006 11:52, Filipe Abrantes wrote:
> 
>>Hi,
>>
>>I've been working on an approach to the problem of using XCP in
>>links where the capacity is unknown (e.g. 802.11), and , eventually,
>>I have put it into paper which is now available to the community in:
>>
>>http://portal.acm.org/affiliated/citation.cfm?id=1140086.1140091&col
>>l=ACM&dl=ACM&idx=1140086&part=periodical&WantType=periodical&title=AC
>>M%20SIGCOMM%20Computer%20Communication%20Review&CFID=15151515&CFTOKEN
>>=6184618
>>
>>(pdf direct link)
>>http://www.acm.org/sigs/sigcomm/ccr/archive/2006/july/p29-v36n3f-abr
>>antes.pdf or
>>http://pong.inescn.pt/~fabrantes/xcpb.pdf
>>
>>I would be happy if this paper would help trigger the discussion on
>>this topic, so any comments you may have are most welcome.
>>
>>Filipe
> 
> 

-- 
Filipe Lameiro Abrantes
INESC Porto
fla at inescporto.pt

Certificate Auth
https://ra.inescporto.pt/pub/cacert/cacert.crt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 4475 bytes
Desc: S/MIME Cryptographic Signature
Url : http://mailman.isi.edu/pipermail/xcp/attachments/20060714/11927675/smime.bin