Skip to contentSkip to conversation

DCCP: Fix up t_nom - FOLLOW-UP

PATCH Gerrit Renker 3 participants 15 messages Jan 10, 2007 – Feb 8, 2007

lore
Share & tools
lore
#0 lore raw
		Packet scheduling tardiness problem
		-----------------------------------

I would like to continue discussion on your patch; I hope you are not dismayed about the response: this concerned only the code changes as such. I think that there is a valid point which you were trying to resolve.

I have therefore consulted with colleagues and tried to find out why successive packets might be too late. This resulted in the following.

(A) The granularity of the rate-based packet scheduling is too coarse

We are resolving t_ipi with microsecond granularity but the timing for the delay between packets uses millisecond granularity (schedule_timeout). This means we can only generate inter-packet delays in the range of 1 millisecond up to 15.625 milliseconds (the largest possible inter-packet interval which corresponds to 1 byte per each 64 seconds).

As a result, our range of speeds that can be influenced is:

1/64 byte per second .... 1000 bytes per second

In all other cases, the delay will be 0 (due to integer division) and hence their packet spacing solely depends on how fast the hardware can cope.

In essence, this is like a car whose accelerator works really well in the range 1 meter/hour up to 2 miles per hour, and for everything else it tries to use top speed of 120 mph.

Therefore I wonder if there is some kind of `micro/nanosleep' which we can use? Did some grepping and inevitably landed in kernel/hrtimers.c - any advice on how to best deploy these?

On healthy links the inter-packet times are often in the range of multiples of 10 microseconds (60 microseconds is frequent).

(B) Fixing send time for packets which are too late

You were mentioning bursts of packets which appear to be too late. I consulted with a colleague of how to fix this: the solution seems much more complicated than the current infrastructure supports.
Suppose the TX queue length is n and the packet at the head of the queue is too late. Then one would need to recompute the sending times for each packet in the TX queue by taking into account the tardiness (it would not be sufficient to simply drain the queue). It seems that we would need to implement a type of credit-based system (e.g. like a Token Bucket Filter); in effect a kind of Qdisc on layer 4.

When using only a single t_nom for the next-packet-to-send as we are doing at the moment, resetting t_nom to t_now when packets are late seems the most sensible thing to do.

So what I think we should do is fix the packet scheduling algorithm to use finer-grained delay. Since in practice no one really is interested in speeds of 1kbyte/sec and below, it in effect means that we are not controlling packet spacing at all.

#1 lore raw

Gerrit,

Thank you for this summary. I think that this discussion shows the fundamental difference in our patches and therefore the fundamental issue we need to resolve. It would be helpful if Eddie or others throws in their 2 cents worth.

Quoted 7 lines · Gerrit Renker

Packet scheduling tardiness problem
-----------------------------------

I would like to continue discussion on your patch; I hope you are not dismayed about the response: this concerned only the code changes as such. I think that there is a valid point which you were trying to resolve.

I'm not dismayed at all by the response. These issues sometimes take a lot of discussion before they go into the kernel. Look at hrtimers, kevents, netchannels, reiser4 etc and you will see that we are a in low number of revisions! It is far better to discuss so that we all understand what is happening and can get the best possible solution.

Quoted 13 lines

I have therefore consulted with colleagues and tried to find out why successive packets might be too late. This resulted in the following.

(A) The granularity of the rate-based packet scheduling is too coarse

We are resolving t_ipi with microsecond granularity but the timing for the delay between packets uses millisecond granularity (schedule_timeout). This means we can only generate inter-packet delays in the range of 1 millisecond up to 15.625 milliseconds (the largest possible inter-packet interval which corresponds to 1 byte per each 64 seconds).

As a result, our range of speeds that can be influenced is:

Quoted 9 lines

1/64 byte per second .... 1000 bytes per second

In all other cases, the delay will be 0 (due to integer division) and hence their packet spacing solely depends on how fast the hardware can cope.

In essence, this is like a car whose accelerator works really well in the range 1 meter/hour up to 2 miles per hour, and for everything else it tries to use top speed of 120 mph.

This is correct provided you are working on the assumption of part B. I think that this is the whole crux of the problem and why we haven't got an agreed patch between us yet.

Rather than espouse my views directly I'll try and comment on the RFC which is the canonical definition of what we should be doing. I've put in the whole 4.6 section of RFC 3448 and commented inline.

4.6. Scheduling of Packet Transmissions

As TFRC is rate-based, and as operating systems typically cannot schedule events precisely, it is necessary to be opportunistic about sending data packets so that the correct average rate is maintained despite the course-grain or irregular scheduling of the operating system.

Note here that the requirement is not to maintain precise timing. The requirement is to maintain the correct average rate. This was the light that went on in my head when I was reviewing both of our previous iterations. I believe we were coming from the wrong starting point - we were trying to improve scheduling, not maintain the correct rate.

Thus a typical sending loop will calculate the correct inter-packet interval, t_ipi, as follows:

        t_ipi = s/X_inst;

Note here that we must calculate t_ipi by this definition. It doesn't say whether it MUST be in sending loop (capitals deliberate as these have special meaning) so my approach of doing in sending loop is fine as is yours provided we pick up both changes in s and X_inst. From memory you detect changes in X_inst and recalculate t_ipi but not for s (although it could be other way around).

When a sender first starts sending at time t_0, it calculates t_ipi, and calculates a nominal send time t_1 = t_0 + t_ipi for packet 1. When the application becomes idle, it checks the current time, t_now, and then requests re-scheduling after (t_ipi - (t_now - t_0)) seconds. When the application is re-scheduled, it checks the current time, t_now, again. If (t_now > t_1 - delta) then packet 1 is sent.

Note that initially we set t_ipi to 1 second. This could be set to a better value based on connection setup as per Eddie and your discussion earlier but I haven't implemented this yet. In this way my code is a hack that I remove the 1 second and add the initial RTT once we obtain it. I see this ugliness can be removed when we make the code base conform to the RFC intent (it is not in RFC yet but Eddie said he would propose for revision)

Now a new t_ipi may be calculated, and used to calculate a nominal send time t_2 for packet 2: t2 = t_1 + t_ipi. The process then repeats, with each successive packet's send time being calculated from the nominal send time of the previous packet.

In some cases, when the nominal send time, t_i, of the next packet is calculated, it may already be the case that t_now > t_i - delta. In such a case the packet should be sent immediately. Thus if the operating system has coarse timer granularity and the transmit rate is high, then TFRC may send short bursts of several packets separated by intervals of the OS timer granularity.

Note a couple of phrases here "the packet should be sent immediately", "TFRC may send short bursts of several packets separated by intervals of the OS timer granularity". This is why I don't think we should ever reset t_nom to the current time. Doing this stops us achieving the average rate required. With reseting t_nom what we are doing is setting X as the maximum instantaneous rate rather than the average rate we are trying to achieve.

The parameter delta is to allow a degree of flexibility in the send time of a packet. If the operating system has a scheduling timer granularity of t_gran seconds, then delta would typically be set to:

        delta = min(t_ipi/2, t_gran/2);

t_gran is 10ms on many Unix systems. If t_gran is not known, a value of 10ms can be safely assumed.

We do this properly.

Quoted 7 lines

Therefore I wonder if there is some kind of `micro/nanosleep' which we can use? Did some grepping and inevitably landed in kernel/hrtimers.c - any advice on how to best deploy these?

On healthy links the inter-packet times are often in the range of multiples of 10 microseconds (60 microseconds is frequent).

I don't believe we need to do this from a practical point of view as the RFC says we aim for average packet rate rather than precise timing. It is interesting from a research point of view whether we achieve better results from smoother packet flow given precise timing, and I have seen published literature on this effect. It is not necessary for RFC compliance though.

However if you want to implement for research that is fine provided that we satisfy a couple of criteria:
- negligible performance impact. I would have thought that hrtimer would add to overhead a reasonable amount. Is the point of hrtimers to achieve a large number of timers per second with low overhead or does it allow you to precisely schedule an event at a time you precisely require? By my calculations using CCID3 on a 1 GBits/sec link using 1 hrtimer per packet would mean around 90,000 timer fires per second vs a maximum of 1000 timeslices if we are using standard setup and HZ of 1000. Interrupting other operations 90,000 times per second is surely not good??
- cross platform support. I'm not sure if platforms like ARM support hrtimers. I want to see CCID3 used across many platforms and small embedded devices based on ARM would be a key market (your cellphone for video calls for example).

Based on this I think hrtimer support is not needed but if it is done then it should be an option not a requirement.

Quoted 13 lines

(B) Fixing send time for packets which are too late

You were mentioning bursts of packets which appear to be too late. I consulted with a colleague of how to fix this: the solution seems much more complicated than the current infrastructure supports.
Suppose the TX queue length is n and the packet at the head of the queue is too late. Then one would need to recompute the sending times for each packet in the TX queue by taking into account the tardiness (it would not be sufficient to simply drain the queue). It seems that we would need to implement a type of credit-based system (e.g. like a Token Bucket Filter); in effect a kind of Qdisc on layer 4.

Quoted 7 lines

When using only a single t_nom for the next-packet-to-send as we are doing at the moment, resetting t_nom to t_now when packets are late seems the most sensible thing to do.

So what I think we should do is fix the packet scheduling algorithm to use finer-grained delay. Since in practice no one really is interested in speeds of 1kbyte/sec and below, it in effect means that we are not controlling packet spacing at all.

See above.

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group
#2 lore raw
In reply to Gerrit Renker
|  Summary: I agree with Ian that hrtimer support is not required, and that 
|  bursts are OK.  They are explicitly allowed by the RFC.

I don't have much disagreement with your points. However, the `bursts' issue can really not be dismissed as unproblematic. Please see other reply.

|  
|  >   When a sender first starts sending at time t_0, it calculates t_ipi,
|  >   and calculates a nominal send time t_1 = t_0 + t_ipi for packet 1.
|  >   When the application becomes idle, it checks the current time, t_now,
|  >   and then requests re-scheduling after (t_ipi - (t_now - t_0))
|  >   seconds.  When the application is re-scheduled, it checks the current
|  >   time, t_now, again.  If (t_now > t_1 - delta) then packet 1 is sent.
|  > 
|  > Note that initially we set t_ipi to 1 second. This could be set to a
|  > better value based on connection setup as per Eddie and your
|  > discussion earlier but I haven't implemented this yet. In this way my
|  > code is a hack that I remove the 1 second and add the initial RTT once
|  > we obtain it. I see this ugliness can be removed when we make the code
|  > base conform to the RFC intent (it is not in RFC yet but Eddie said he
|  > would propose for revision)
|  
|  For what it's worth, it's as close to in the RFC as it can get without a 
|  revision.  The authors of the RFC agree that we meant the initial 
|  Request-Response RTT to be usable as an initial RTT estimate; the 
|  working group agreed; errata has been sent.

So we are RFC-compliant for the moment. One point which remains unresolved is, the above is about RTTs, but what about the initial sending rate of 1 packet per second, which implies an initial t_ipi of 1 second?

#3 lore raw
In reply to Gerrit Renker

Quoting Eddie Kohler:

|  > The problem I see is that
|  >  * scheduling granularity is at best 1ms
|  >  * hence t_gran/2 is at best 500usec
|  >  * and so when t_ipi < 1ms, packets will always be sent in bursts
|  > 
|  > So we have a `critical point' after which the average sending rate is dominated by the
|  > hardware and no longer under the rate-based control of t_ipi.
|  
|  I think there might be a confusion about what "average sending rate" 
|  actually means.  You appear to assume that precise timing control is 
|  needed to obtain a smooth average.  I.e., if there are bursts, then 
|  there is no smooth average.  But this isn't what the RFC means by 
|  average.  The average rate is suppsoed to be smooth *from one RTT to the 
|  next*.  Sub-RTT burstiness is *explicitly allowed*, although 
|  implementations should try to avoid it when it's easy to do so.

Sorry, I don't think you got my point. The problem is NOT in occasional bursts, but rather that there is a critical speed X_crit after which the system essentially gets completely out of control.

If bursts would occur occasionally then it would be like a car which is speeding up for a moment, but then slows down again (and thus keeps the average speed) - agree that this would not be a problem. Here however we have that, once X_crit is reached, the system will _oscillate_ between the top available speed (and this could be hundreds of Mbits per second) and whatever it gets in terms of feedback from the receiver. After slowing down, it would again climb in slow-start up to X_crit, then jump to top speed. Thus it is like a car which will abruptly switch to top speed of e.g. 160 mph when trying to accelerate past 2 mph.

I have a snapshot which illustrates this state:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png

The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the desirable state is the following:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png

These snapshots were originally taken to compare the performance with and without serializing access to TX history. I didn't submit the patch since, at times, I would get the same chaotic behaviour with TX locking.

Other people on this list have reported that iperf performance is unpredictable with CCID 3.

The point is that, without putting in some kind of control, we have a system which gets into a state of chaos as soon as the maximum controllable speed X_crit is reached. When it is past that point, there is no longer a notion of predictable performance or correct average rate: what happens is then outside the control of the CCID 3 module, performance is then a matter of coincidence.

I don't think that a kernel maintainer will gladly support a module which is liable to reaching such a chaotic state.

|  > I have done a back-of-the-envelope calculation below for different sizes of s; 9kbyte
|  > I think is the maximum size of an Ethernet jumbo frame.
|  > 
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  >             s | 32      | 100     | 250     | 500     | 1000  | 1500    | 9000  |
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  >     X_critical| 32kbps  | 100kbps | 250kbps | 500kbps | 1mbps | 1.5mbps | 9mbps |
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+ 
|  > 
|  > That means we can only expect predictable performance up to 9mbps ?????
|  
|  Same comment.  I imagine performance will be predictable at speeds FAR 
|  ABOVE 9mbps, DESPITE the sub-RTT bursts.  Predictable performance means 
|  about the same average rate from one RTT to the next.

I think that, without finer timer resolution, we need to put in some kind of throttle to avoid entering the region where speed can no longer be controlled.

|  > I am dumbstruck - it means that the whole endeavour to try and use Gigabit cards (or
|  > even 100 Mbit ethernet cards) is futile and we should be using the old 10 Mbit cards???
|  
|  Remember that TCP is ENTIRELY based on bursts!!!!!  No rate control at 
|  all.  And it still gets predictable performance at high rates.
|  

Yes, but ..... it uses an entirely different mechanism and is not rate-based.

#4 lore raw
In reply to Gerrit Renker
Quoted 7 lines
|  For what it's worth, it's as close to in the RFC as it can get without a 
|  revision.  The authors of the RFC agree that we meant the initial 
|  Request-Response RTT to be usable as an initial RTT estimate; the 
|  working group agreed; errata has been sent.

So we are RFC-compliant for the moment. One point which remains unresolved is, the above is about RTTs, but what about the initial sending rate of 1 packet per second, which implies an initial t_ipi of 1 second?

"Therefore, in contrast to [RFC3448], the initial CCID 3 sending rate is allowed to be at least two packets per RTT, and at most four packets per RTT, depending on the packet size. ..." [RFC4342, Sec 5]

Since CCID3 always has an estimate of the round trip time when it sends packets, there is no such thing as an initial sending rate of 1 packet per second. The initial sending rate, after the Response arrives (thus providing an initial estimate of the round trip time), is 2-4 packets per RTT, depending on s.

Eddie

#5 lore raw
In reply to Gerrit Renker

The first figure certainly demonstrates a problem. However, that problem is not inherent in CCID3, it is not inherent in rate-based solutions, and high-rate timers probably wouldn't solve it. CCID3 has been tested -- in simulation mind you -- at high rates. The problem is a bug in the Linux implementation. Ian seems to think he can solve the problem with bursts and I am inclined to agree.

Your comments about X_crit are based on your observations, not analysis, yes? If you can provide some reason why CCID3 inherently has an X_crit, I'd like to hear it. "Oscillat[ing] between the top available speed ... and whatever it gets in terms of feedback" is not TFRC. Sounds like a bug.

I agree that kernel maintainers don't want bugs in the kernel.

Anyway, if you can go deeper into the code and determine why you're observing this behavior (I assume in the absence of loss, which is even weirder), then that might be useful.

Eddie

Quoted 76 lines · Gerrit Renker

Quoting Eddie Kohler:

|  > The problem I see is that
|  >  * scheduling granularity is at best 1ms
|  >  * hence t_gran/2 is at best 500usec
|  >  * and so when t_ipi < 1ms, packets will always be sent in bursts
|  > 
|  > So we have a `critical point' after which the average sending rate is dominated by the
|  > hardware and no longer under the rate-based control of t_ipi.
|  
|  I think there might be a confusion about what "average sending rate" 
|  actually means.  You appear to assume that precise timing control is 
|  needed to obtain a smooth average.  I.e., if there are bursts, then 
|  there is no smooth average.  But this isn't what the RFC means by 
|  average.  The average rate is suppsoed to be smooth *from one RTT to the 
|  next*.  Sub-RTT burstiness is *explicitly allowed*, although 
|  implementations should try to avoid it when it's easy to do so.

Sorry, I don't think you got my point. The problem is NOT in occasional bursts, but rather that there is a critical speed X_crit after which the system essentially gets completely out of control.

If bursts would occur occasionally then it would be like a car which is speeding up for a moment, but then slows down again (and thus keeps the average speed) - agree that this would not be a problem. Here however we have that, once X_crit is reached, the system will _oscillate_ between the top available speed (and this could be hundreds of Mbits per second) and whatever it gets in terms of feedback from the receiver. After slowing down, it would again climb in slow-start up to X_crit, then jump to top speed. Thus it is like a car which will abruptly switch to top speed of e.g. 160 mph when trying to accelerate past 2 mph.

I have a snapshot which illustrates this state:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png

The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the desirable state is the following:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png

These snapshots were originally taken to compare the performance with and without serializing access to TX history. I didn't submit the patch since, at times, I would get the same chaotic behaviour with TX locking.

Other people on this list have reported that iperf performance is unpredictable with CCID 3.

The point is that, without putting in some kind of control, we have a system which gets into a state of chaos as soon as the maximum controllable speed X_crit is reached. When it is past that point, there is no longer a notion of predictable performance or correct average rate: what happens is then outside the control of the CCID 3 module, performance is then a matter of coincidence.

I don't think that a kernel maintainer will gladly support a module which is liable to reaching such a chaotic state.

|  > I have done a back-of-the-envelope calculation below for different sizes of s; 9kbyte
|  > I think is the maximum size of an Ethernet jumbo frame.
|  > 
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  >             s | 32      | 100     | 250     | 500     | 1000  | 1500    | 9000  |
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  >     X_critical| 32kbps  | 100kbps | 250kbps | 500kbps | 1mbps | 1.5mbps | 9mbps |
|  >    -----------+---------+---------+---------+---------+-------+---------+-------+ 
|  > 
|  > That means we can only expect predictable performance up to 9mbps ?????
|  
|  Same comment.  I imagine performance will be predictable at speeds FAR 
|  ABOVE 9mbps, DESPITE the sub-RTT bursts.  Predictable performance means 
|  about the same average rate from one RTT to the next.

I think that, without finer timer resolution, we need to put in some kind of throttle to avoid entering the region where speed can no longer be controlled.

|  > I am dumbstruck - it means that the whole endeavour to try and use Gigabit cards (or
|  > even 100 Mbit ethernet cards) is futile and we should be using the old 10 Mbit cards???
|  
|  Remember that TCP is ENTIRELY based on bursts!!!!!  No rate control at 
|  all.  And it still gets predictable performance at high rates.
|  

Yes, but ..... it uses an entirely different mechanism and is not rate-based.

#6 lore raw
In reply to Gerrit Renker
|  > |  For what it's worth, it's as close to in the RFC as it can get without a 
|  > |  revision.  The authors of the RFC agree that we meant the initial 
|  > |  Request-Response RTT to be usable as an initial RTT estimate; the 
|  > |  working group agreed; errata has been sent.
|  > So we are RFC-compliant for the moment. One point which remains unresolved is,
|  > the above is about RTTs, but what about the initial sending rate of 1 packet
|  > per second, which implies an initial t_ipi of 1 second?
|  
|  "Therefore, in contrast to [RFC3448], the initial CCID 3 sending rate is 
|  allowed to be at least two packets per RTT, and at most four packets per 
|  RTT, depending on the packet size. ..." [RFC4342, Sec 5]
|  
|  Since CCID3 always has an estimate of the round trip time when it sends 
|  packets, there is no such thing as an initial sending rate of 1 packet 
|  per second.  The initial sending rate, after the Response arrives (thus 
|  providing an initial estimate of the round trip time), is 2-4 packets 
|  per RTT, depending on s.

Thanks for the clarification. Using the initial RTT estimate for the first packets has not been ignored, but will require some API changes, since CCIDs operate all in connected state and hence have no access to handshake-RTT information. But before changing the API, there are many bugs which need to be fixed.

#7 lore raw
In reply to Gerrit Renker
Quoted 9 lines · Gerrit Renker

I have a snapshot which illustrates this state:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png

The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the desirable state is the following:

http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png

Questions on the graphs:
- are these direct connect nodes?
- why is Xcalc 0?
- why on the stable one is Xrecv different from X. Is X the rate that it is allowed to send at but doesn't so only achieves Xrecv?

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group
#8 lore raw
In reply to Gerrit Renker
|  > I have a snapshot which illustrates this state:
|  >
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png
|  >
|  > The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the
|  > desirable state is the following:
|  >
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png
|  >
|  
|  Questions on the graphs:
|  - are these direct connect nodes?

The nodes are on the same Ethernet LAN, connected via 100Mbps / 1GBps interfaces. There is no other traffic on that LAN.
| - why is Xcalc 0?
Since no losses occurred (p is always 0 on these tests).

|  - why on the stable one is Xrecv different from X. Is X the rate that
|  it is allowed to send at but doesn't so only achieves Xrecv?

When there is no loss, X = max(min(2*X, 2*X_recv), s/R) - the graph agrees with this, since X is about 2*X_recv.

#9 lore raw
In reply to Gerrit Renker

Quoting Eddie Kohler:

|  The first figure certainly demonstrates a problem.  However, that 
|  problem is not inherent in CCID3, it is not inherent in rate-based 
|  solutions, and high-rate timers probably wouldn't solve it.  CCID3 has 
|  been tested -- in simulation mind you -- at high rates.  The problem is 
|  a bug in the Linux implementation.  Ian seems to think he can solve the 
|  problem with bursts and I am inclined to agree.
|  
|  Your comments about X_crit are based on your observations, not analysis, 
|  yes?  If you can provide some reason why CCID3 inherently has an X_crit, 
|  I'd like to hear it.  "Oscillat[ing] between the top available speed ... 
|  and whatever it gets in terms of feedback" is not TFRC.  Sounds like a bug.
|  
|  I agree that kernel maintainers don't want bugs in the kernel.
|  
|  Anyway, if you can go deeper into the code and determine why you're 
|  observing this behavior (I assume in the absence of loss, which is even 
|  weirder), then that might be useful.
|  

First off - I think we all agree that the RFCs are all sound and thus virtually everything here deals with implementation problems (if there are additional observations or discussions, we can copy to dccp@ietf).

I think to find why the CCID 3 performance is so chaotic, unpredictable and abysmally poor we should try to combine the various strenghts of people on this list.

Apart from writing standards documents, you have designed the core of the click modular router system, so many issues arising here you can probably evaluate from a practical perspective as well as from a standards-based perspective.

Ian has been the maintainer of the CCID 3 module for so long and knows all the background from the original Lulea code, through the WAND research code and the various stages it went through. So it more or less entirely depends on the communication on this list how good this code can be made.

Below I throw in my 2 cents of why I think there is a critical speed X_crit. Maybe you can help me dispel it or point out other possibilities which we can - step-by-step - eliminate, until the cause becomes fully clear.

Firstly, all packet scheduling is based on schedule_timeout().

The return code rc of ccid_hc_tx_send_packet (wrapper around ccid3_hc_tx_send_packet) is used to decide whether to

(a) send the packet immediately or
(b) sleep with HZ granularity before retrying

I am assuming that there is no loss on the link and no backlog of packets which couldn't be scheduled so far (i.e. if t_nom < t_now then t_now - t_nom < t_ipi). I assume further that there is a constant stream of packets, fed into the TX queue by continuously calling dccp_sendmsg. This is also the background of the experiments/graphs.

Here is the analysis, starting with ccid3_hc_tx_send_packet:

1) dccp_sendmsg calls dccp_write_xmit(sk, 0)

2) dccp_write_xmit calls ccid_hc_tx_send_packet, a wrapper around ccid3_hc_tx_send_packet

3) ccid3_hc_tx_send_packet gets the current time in usecs and computes delay = t_nom - t_now

(a) if delay >= delta = min(t_ipi/2, t_gran/2) then it returns delay/1000
(b) otherwise it returns 0

4) back in dccp_write_xmit,
* if rc=0 then the packet is sent immediately; otherwise (since block=0),
* dccps_xmit_timer is reset to expire in t_now + rc milliseconds (sk_reset_timer) -- in this case dccp_write_xmit exits now and
-- when the write timer expires, dccp_write_xmit_timer is called, which again
calls dccp_write_xmit(sk, 0)
-- this means going back to (3), now delay < delta, the function returns 0
and the packet is sent immediately

To find where the problematic case is, assume that the sender is in slow start and doubles X each RTT. As X increases, t_ipi decreases so that there is a point where t_ipi < 1000 usec.

-> all differences delay = t_nom - t_now which are less than 1000 result in
delay / 1000 = 0 due to integer division
-> hence all packets which are late up to 1 millisecond are sent immediately -> assume that t_ipi is less than 1 millisecond, then in effect all packets are
sent immediately; hence we have a _continuous_ burst of packets
-> schedule_timeout() really only has a granularity of HZ:
* if HZ00, msecs_to_jiffies(m) returns m
* if HZ < 1000, msecs_to_jiffies(m) returns (m * HZ + 999)/1000
=> hence m=1 millisecond will give a result of 1 jiffie
=> but the granularity of jiffies is in HZ < 1000 so that the
timer will expire with a granularity of HZ
=> that means if X is higher than X_crit, t_ipi will always be such that
the timer expires at a time which is too late, so that packets are all sent in immediate bursts or in scheduled bursts, but there is no longer any real scheduling

The other points which I am not entirely sure about yet are
* compression of packet spacing due to using TX output queues
* interactions with the traffic control subsystem
* times when the main socket is locked

- Gerrit

|  > I have a snapshot which illustrates this state: 
|  > 
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png
|  >   
|  > The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the
|  > desirable state is the following:
|  > 
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png
|  > 
|  > These snapshots were originally taken to compare the performance with and without serializing access to
|  > TX history. I didn't submit the patch since, at times, I would get the same chaotic behaviour with TX locking.
|  > 
|  > Other people on this list have reported that iperf performance is unpredictable with CCID 3. 
|  > 
|  > The point is that, without putting in some kind of control, we have a system which gets into a state of
|  > chaos as soon as the maximum controllable speed X_crit is reached. When it is past that point, there is
|  > no longer a notion of predictable performance or correct average rate: what happens is then outside the
|  > control of the CCID 3 module, performance is then a matter of coincidence.
|  > 
|  > I don't think that a kernel maintainer will gladly support a module which is liable to reaching such a
|  > chaotic state.
|  >  
|  >   
|  > |  > I have done a back-of-the-envelope calculation below for different sizes of s; 9kbyte
|  > |  > I think is the maximum size of an Ethernet jumbo frame.
|  > |  > 
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  > |  >             s | 32      | 100     | 250     | 500     | 1000  | 1500    | 9000  |
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  > |  >     X_critical| 32kbps  | 100kbps | 250kbps | 500kbps | 1mbps | 1.5mbps | 9mbps |
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+ 
|  > |  > 
|  > |  > That means we can only expect predictable performance up to 9mbps ?????
|  > |  
|  > |  Same comment.  I imagine performance will be predictable at speeds FAR 
|  > |  ABOVE 9mbps, DESPITE the sub-RTT bursts.  Predictable performance means 
|  > |  about the same average rate from one RTT to the next.
|  > I think that, without finer timer resolution, we need to put in some kind of throttle to avoid
|  > entering the region where speed can no longer be controlled.
|  > 
|  >   
|  > |  > I am dumbstruck - it means that the whole endeavour to try and use Gigabit cards (or
|  > |  > even 100 Mbit ethernet cards) is futile and we should be using the old 10 Mbit cards???
|  > |  
|  > |  Remember that TCP is ENTIRELY based on bursts!!!!!  No rate control at 
|  > |  all.  And it still gets predictable performance at high rates.
|  > |  
|  > Yes, but ..... it uses an entirely different mechanism and is not rate-based.
|  
|  
#10 lore raw
In reply to Gerrit Renker

I have some minor thoughts relating to this.

- In what units are t_nom kept? I would hope microseconds at least, not milliseconds. You say "dccps_xmit_timer is reset to expire in t_now + rc milliseconds"; I assume you mean that the value t_now + rc is cast to milliseconds. Clearly high rates will require that t_nom be kept in microseconds at least.

I wonder because you say:

Quoted 2 lines

-> assume that t_ipi is less than 1 millisecond, then in effect all packets are
sent immediately; hence we have a _continuous_ burst of packets

but this does not follow. If t_ipi<1ms, but is non-zero, then at most 1ms worth of packets can be sent in a burst -- not continuous (assuming it takes way less than 1ms to send a packet).

- ccid3_hc_tx_send_packet should return a value that is measured in MICROSECONDS not milliseconds. It also sounds like there is a rounding error in step 3a); it should probably return (delay + 500)/1000 at least.

- What if the delay till the next packet is >0 but <HZ? It sounds like that case is causing the problem. One answer: Do not schedule a TIMER; instead, leave a kernel thread or bottom half scheduled, so that the next time the kernel runs, it will poll DCCP, even if that is before 1HZ from now.

Make sense?
Eddie

Quoted 114 lines

Below I throw in my 2 cents of why I think there is a critical speed X_crit. Maybe you can help me dispel it or point out other possibilities which we can - step-by-step - eliminate, until the cause becomes fully clear.

Firstly, all packet scheduling is based on schedule_timeout().

The return code rc of ccid_hc_tx_send_packet (wrapper around ccid3_hc_tx_send_packet) is used to decide whether to

(a) send the packet immediately or
(b) sleep with HZ granularity before retrying

I am assuming that there is no loss on the link and no backlog of packets which couldn't be scheduled so far (i.e. if t_nom < t_now then t_now - t_nom < t_ipi). I assume further that there is a constant stream of packets, fed into the TX queue by continuously calling dccp_sendmsg. This is also the background of the experiments/graphs.

Here is the analysis, starting with ccid3_hc_tx_send_packet:

1) dccp_sendmsg calls dccp_write_xmit(sk, 0)

2) dccp_write_xmit calls ccid_hc_tx_send_packet, a wrapper around ccid3_hc_tx_send_packet

3) ccid3_hc_tx_send_packet gets the current time in usecs and computes delay = t_nom - t_now

(a) if delay >= delta = min(t_ipi/2, t_gran/2) then it returns delay/1000
(b) otherwise it returns 0

4) back in dccp_write_xmit,
* if rc=0 then the packet is sent immediately; otherwise (since block=0),
* dccps_xmit_timer is reset to expire in t_now + rc milliseconds (sk_reset_timer) -- in this case dccp_write_xmit exits now and
-- when the write timer expires, dccp_write_xmit_timer is called, which again
calls dccp_write_xmit(sk, 0)
-- this means going back to (3), now delay < delta, the function returns 0
and the packet is sent immediately

To find where the problematic case is, assume that the sender is in slow start and doubles X each RTT. As X increases, t_ipi decreases so that there is a point where t_ipi < 1000 usec.

-> all differences delay = t_nom - t_now which are less than 1000 result in
delay / 1000 = 0 due to integer division
-> hence all packets which are late up to 1 millisecond are sent immediately -> assume that t_ipi is less than 1 millisecond, then in effect all packets are
sent immediately; hence we have a _continuous_ burst of packets
-> schedule_timeout() really only has a granularity of HZ:
* if HZ00, msecs_to_jiffies(m) returns m
* if HZ < 1000, msecs_to_jiffies(m) returns (m * HZ + 999)/1000
=> hence m=1 millisecond will give a result of 1 jiffie
=> but the granularity of jiffies is in HZ < 1000 so that the
timer will expire with a granularity of HZ
=> that means if X is higher than X_crit, t_ipi will always be such that
the timer expires at a time which is too late, so that packets are all sent in immediate bursts or in scheduled bursts, but there is no longer any real scheduling

The other points which I am not entirely sure about yet are
* compression of packet spacing due to using TX output queues
* interactions with the traffic control subsystem
* times when the main socket is locked

- Gerrit

|  > I have a snapshot which illustrates this state: 
|  > 
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/no_tx_locking/transmit_rate.png
|  >   
|  > The oscillating behaviour is well visible. In contrast, I am sure that you would agree that the
|  > desirable state is the following:
|  > 
|  >  http://www.erg.abdn.ac.uk/users/gerrit/dccp/dccp_probe/examples/with_tx_locking/transmit_rate.png
|  > 
|  > These snapshots were originally taken to compare the performance with and without serializing access to
|  > TX history. I didn't submit the patch since, at times, I would get the same chaotic behaviour with TX locking.
|  > 
|  > Other people on this list have reported that iperf performance is unpredictable with CCID 3. 
|  > 
|  > The point is that, without putting in some kind of control, we have a system which gets into a state of
|  > chaos as soon as the maximum controllable speed X_crit is reached. When it is past that point, there is
|  > no longer a notion of predictable performance or correct average rate: what happens is then outside the
|  > control of the CCID 3 module, performance is then a matter of coincidence.
|  > 
|  > I don't think that a kernel maintainer will gladly support a module which is liable to reaching such a
|  > chaotic state.
|  >  
|  >   
|  > |  > I have done a back-of-the-envelope calculation below for different sizes of s; 9kbyte
|  > |  > I think is the maximum size of an Ethernet jumbo frame.
|  > |  > 
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  > |  >             s | 32      | 100     | 250     | 500     | 1000  | 1500    | 9000  |
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+
|  > |  >     X_critical| 32kbps  | 100kbps | 250kbps | 500kbps | 1mbps | 1.5mbps | 9mbps |
|  > |  >    -----------+---------+---------+---------+---------+-------+---------+-------+ 
|  > |  > 
|  > |  > That means we can only expect predictable performance up to 9mbps ?????
|  > |  
|  > |  Same comment.  I imagine performance will be predictable at speeds FAR 
|  > |  ABOVE 9mbps, DESPITE the sub-RTT bursts.  Predictable performance means 
|  > |  about the same average rate from one RTT to the next.
|  > I think that, without finer timer resolution, we need to put in some kind of throttle to avoid
|  > entering the region where speed can no longer be controlled.
|  > 
|  >   
|  > |  > I am dumbstruck - it means that the whole endeavour to try and use Gigabit cards (or
|  > |  > even 100 Mbit ethernet cards) is futile and we should be using the old 10 Mbit cards???
|  > |  
|  > |  Remember that TCP is ENTIRELY based on bursts!!!!!  No rate control at 
|  > |  all.  And it still gets predictable performance at high rates.
|  > |  
|  > Yes, but ..... it uses an entirely different mechanism and is not rate-based.
|  
|  
#11 lore raw
In reply to Gerrit Renker
Quoted 7 lines · Eddie Kohler

I have some minor thoughts relating to this.

- In what units are t_nom kept? I would hope microseconds at least, not milliseconds. You say "dccps_xmit_timer is reset to expire in t_now + rc milliseconds"; I assume you mean that the value t_now + rc is cast to milliseconds. Clearly high rates will require that t_nom be kept in microseconds at least.

It's definitely microseconds. Nearly all critical stuff such as t_nom, t_ipi, rtt are calculated in usecs. Early on some code was attempted to be run as msecs and it was a disaster.

But t_nom wouldn't matter if it was msecs in this case as you send packets up to t_nom and then set a timer. If there was a backlog they'd get sent next time and as you say takes way less than 1ms to send a packet.

Quoted 6 lines

I wonder because you say:

Quoted 2 lines

-> assume that t_ipi is less than 1 millisecond, then in effect all packets are
sent immediately; hence we have a _continuous_ burst of packets

Quoted 8 lines

but this does not follow. If t_ipi<1ms, but is non-zero, then at most 1ms worth of packets can be sent in a burst -- not continuous (assuming it takes way less than 1ms to send a packet).

- ccid3_hc_tx_send_packet should return a value that is measured in MICROSECONDS not milliseconds. It also sounds like there is a rounding error in step 3a); it should probably return (delay + 500)/1000 at least.

This is used to set a timer to know when to wake up again which is valid to be in msecs. We don't want to be firing interrupts in usec intervals as too intensive and that's why you have t_gran there.

Quoted 5 lines

- What if the delay till the next packet is >0 but <HZ? It sounds like that case is causing the problem. One answer: Do not schedule a TIMER; instead, leave a kernel thread or bottom half scheduled, so that the next time the kernel runs, it will poll DCCP, even if that is before 1HZ from now.

Might have a look at that but it's not affecting me right now - more Gerrit's area.

Quoted 4 lines

Make sense?
Eddie

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group
#12 lore raw
In reply to Gerrit Renker
Quoted 8 lines
Quoted 5 lines

- ccid3_hc_tx_send_packet should return a value that is measured in MICROSECONDS not milliseconds. It also sounds like there is a rounding error
in step 3a); it should probably return (delay + 500)/1000 at least.

This is used to set a timer to know when to wake up again which is valid to be in msecs. We don't want to be firing interrupts in usec intervals as too intensive and that's why you have t_gran there.

You want it to return microseconds precisely so you can distinguish between cases that require a timer and cases that require something lighterweight, like a simple rescheduling. If you pre-truncate the information to millisecond granularity there's no way to distinguish between "send NOW" and "send pretty soon but not now". Just divide by 1000 when you actually schedule the timer.

E

Quoted 15 lines
Quoted 8 lines

- What if the delay till the next packet is >0 but <HZ? It sounds like that
case is causing the problem. One answer: Do not schedule a TIMER; instead,
leave a kernel thread or bottom half scheduled, so that the next time the kernel runs, it will poll DCCP, even if that is before 1HZ from now.

Might have a look at that but it's not affecting me right now - more Gerrit's area.

Quoted 4 lines

Make sense?
Eddie

#13 lore raw
In reply to Gerrit Renker
Quoted 9 lines · Eddie Kohler
Quoted 8 lines
Quoted 5 lines

- ccid3_hc_tx_send_packet should return a value that is measured in MICROSECONDS not milliseconds. It also sounds like there is a rounding error
in step 3a); it should probably return (delay + 500)/1000 at least.

This is used to set a timer to know when to wake up again which is valid to be in msecs. We don't want to be firing interrupts in usec intervals as too intensive and that's why you have t_gran there.

Quoted 7 lines

You want it to return microseconds precisely so you can distinguish between cases that require a timer and cases that require something lighterweight, like a simple rescheduling. If you pre-truncate the information to millisecond granularity there's no way to distinguish between "send NOW" and "send pretty soon but not now". Just divide by 1000 when you actually schedule the timer.

I'm not sure about this. If you reschedule you've got no guarantee when you get your next timeslice. I also think that timers probably aren't that heavy in Linux as it probably weights the scheduler. If you ask for something 5 msecs in future you are guaranteed it won't go off before then but sometime after..

Probably one to test some time but I can't see this affecting things too much and bigger bugs to fry at present probably. But certainly worth checking at some point.

Ian

Signature · 3 lines
Web: http://wand.net.nz/~iam4
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group
#14 lore raw
In reply to Gerrit Renker
Quoted 10 lines
Quoted 10 lines

You want it to return microseconds precisely so you can distinguish between
cases that require a timer and cases that require something lighterweight,
like a simple rescheduling. If you pre-truncate the information to millisecond granularity there's no way to distinguish between "send NOW" and
"send pretty soon but not now". Just divide by 1000 when you actually schedule the timer.

Quoted 2 lines

I'm not sure about this. If you reschedule you've got no guarantee when you get your next timeslice.

You've got no GUARANTEE of when you get your next timeslice, but in most cases it will be soon. As opposed to scheduling a timer 1ms in the future, where you KNOW you won't run for 1ms, as you say.

Gerrit's problem is burstiness at the level of milliseconds. The only way to solve this is to run at sub-millisecond granularity. Use hi-res timers, or easier, use existing mechanisms for running code frequently:
i.e., leaving the code runnable.

Eddie

Quoted 10 lines

I also think that timers probably
aren't that heavy in Linux as it probably weights the scheduler. If you ask for something 5 msecs in future you are guaranteed it won't go off before then but sometime after..

Probably one to test some time but I can't see this affecting things too much and bigger bugs to fry at present probably. But certainly worth checking at some point.

Ian