RFC - bandwidth optimization idea
Quoted 5 lines
From: Andreas Klauer <[email protected]>
Doesn't every QDisc work that way? When the kernel wants to send a packet, it calls the appropriatedequeue()function in the QDisc. I'm not a kernel developer so this guess might be wrong.
That's correct, but this operation takes a packet from an OS queue and the only control the application has over that queue is to put something into it. One way to view the idea is that I want to make it convenient for the application to decide what to put into the queue at the latest possible time without losing any of its available bandwidth. Think in terms of an OS callback to the application saying "I'm ready to send your data now, what should I send?"
Quoted 3 lines
But still, I don't think that the queueing is the main problem with your idea... the main problem is, how do you decide what's important and what not, and what's obsolete?
This is up to the application of course. See below.
Quoted 2 lines
From: [email protected] (Paul Hampson)
I believe the general solution to this is to use UDP, and make sure
The scheme I describe wouldn't make a lot of sense for tcp, which after all specifies congestion control, retransmission, etc. But UDP still goes through the queuing that I want to optimize.
Quoted 3 lines
your source machine doesn't queue up packets locally (eg. ethernet network contention) and let the best-effort nature of UDP deal with dropping stuff that gets delayed.
The problem is that the OS is not helpful in avoiding queuing up packets locally. That's part of what I'm trying to fix. For instance, a relatively cheap approximation would be to give the application a way to see how many packets it has in the queue. Then it could at least delay its decision about what to put into the queue until the queue was short. Even better would be to see an estimate of how long it will be before the next packet it enqueues will be sent - like "your call will be answered in approximately 4 minutes".
Quoted 4 lines
I'm not sure there's any way to have an 'I changed my mind about sending that' interface into your network stack... And generally it wouldn't be useful, data spends longer in transit than it does in your queues.
That depends on the rate at which the queue is emptied.
If your queue has a rate limit of 10bps then your packets can spend a long time in the queue.
- There are slow links
(For instance, I recall hearing that submarines have very low rates.)
- The application might be allocated a small part of the bandwidth shared with other applications.
It occurs to me that an example where this would be helpful is transmitting voice data over a low bandwidth link (like a cell phone). Suppose you know that the actual transit time is .1 sec and you want the listener to always hear what the speaker was saying .2 sec ago at the best possible quality.
Suppose the available bandwidth is shared with other applications. The voice application doesn't know when they will want to send or how urgent their data might be. Someone else decides that. It just wants to send the best possible data in the bandwidth allocated to it. I imagine is continually sampling the input and revising what it considers to be the most valuable unsent data for the last .1 sec. Whenever the OS decides it's time to send the next voice packet I want it to send the latest idea of what's most valuable. I don't want to have to put data into the queue to wait for times that might depend on what urgent communication might be required by other applications.
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 23 lines · Don Cohen
Quoted 2 lines
From: [email protected] (Paul Hampson)
I believe the general solution to this is to use UDP, and make sureThe scheme I describe wouldn't make a lot of sense for tcp, which after all specifies congestion control, retransmission, etc. But UDP still goes through the queuing that I want to optimize.
Quoted 3 lines
your source machine doesn't queue up packets locally (eg. ethernet network contention) and let the best-effort nature of UDP deal with dropping stuff that gets delayed.
The problem is that the OS is not helpful in avoiding queuing up packets locally. That's part of what I'm trying to fix. For instance, a relatively cheap approximation would be to give the application a way to see how many packets it has in the queue. Then it could at least delay its decision about what to put into the queue until the queue was short. Even better would be to see an estimate of how long it will be before the next packet it enqueues will be sent - like "your call will be answered in approximately 4 minutes".
Quoted 4 lines
I'm not sure there's any way to have an 'I changed my mind about sending that' interface into your network stack... And generally it wouldn't be useful, data spends longer in transit than it does in your queues.
Quoted 7 lines
That depends on the rate at which the queue is emptied.
If your queue has a rate limit of 10bps then your packets can spend a long time in the queue.
- There are slow links
(For instance, I recall hearing that submarines have very low rates.)
- The application might be allocated a small part of the bandwidth shared with other applications.
Wait, you're trying to send more data than the link can take? Then send UDP, throttle it at the local end with a drop-oldest qdisc. Then you get the effect of 'most recent data is best'. Anything more compilcated in terms of priority either needs a custom qdisc, or your application needs to not try and send more than the link can take.
Quoted 6 lines
It occurs to me that an example where this would be helpful is transmitting voice data over a low bandwidth link (like a cell phone). Suppose you know that the actual transit time is .1 sec and you want the listener to always hear what the speaker was saying .2 sec ago at the best possible quality.
Quoted 10 lines
Suppose the available bandwidth is shared with other applications. The voice application doesn't know when they will want to send or how urgent their data might be. Someone else decides that. It just wants to send the best possible data in the bandwidth allocated to it. I imagine is continually sampling the input and revising what it considers to be the most valuable unsent data for the last .1 sec. Whenever the OS decides it's time to send the next voice packet I want it to send the latest idea of what's most valuable. I don't want to have to put data into the queue to wait for times that might depend on what urgent communication might be required by other applications.
You gotta prioritise your data, using TOS or diffserv or something. Set your voice to real-time, so it always gets sent, and the your other applications can use unused packet-times. Use a dropping qdisc for traffic where 'most-recent' is more important than 'all, in order' as described above, and you're set.
I have a vauge recollection that this sort of thing is discussed in Tannenbaum's Computer Networks textbook, to do with positional data of satellites or something. (eg. if the positional data is delayed, we write it off, we don't want to delay the data about where we are _now_ in order to know where we were _then_)
Signature · 5 lines
Paul "TBBle" Hampson, on an alternate email client. _______________________________________________ LARTC mailing list [email protected] http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 8 lines
Wait, you're trying to send more data than the link can take? Then send UDP, throttle it at the local end with a drop-oldest qdisc. Then you get the effect of 'most recent data is best'. Anything more compilcated in terms of priority either needs a custom qdisc, or your application needs to not try and send more than the link can take.
The situation described is real and complex. For example I run an email service which caters for people using satellite phones (1,200 baud on a good day), but the whole point is that they don't need to change any settings when they jump on a 10Mbit leased line connection...
This is a total pain to optimise. Ideally I would like an API to be able to limit the congestion window on the local machine for a particular connection (which I don't think exists on either windows or linux?). This way the OS will report that the queue is full quickly to the local program without buffering up a ton of data.
The issue in my case is that you have two simultaneous streams in transit for email, one to receive new mail and one to send mail out. In the case of the sat phone it's possible to have net buffers which are 20 secs or so long and so when you send out a status message to say "email received successfully, send me the next one", it can end up queued behind a bunch of lower priority data for a VERY long time. Often these buffers are on the remote ISP end where you have very little control. This is a serious slowdown on a link which is costing you $1.50/min.
My main focus has been adjusting the protocol to be less interactive, but it would be nice to have more operating system support for these fringe cases
Ed W
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 10 lines · Ed W
Quoted 5 lines
Wait, you're trying to send more data than the link can take? Then send UDP, throttle it at the local end with a drop-oldest qdisc. Then you get the effect of 'most recent data is best'. Anything more compilcated in terms of priority either needs a custom qdisc, or your application needs to not try and send more than the link can take.
The situation described is real and complex. For example I run an email service which caters for people using satellite phones (1,200 baud on a good day), but the whole point is that they don't need to change any settings when they jump on a 10Mbit leased line connection...
Ah, I was picturing voice over a low-latency, low-speed link. Now I can understand what you're trying to acheieve.
Is that 1200 baud each way? Or do you have to alternate up and down somehow?
Quoted 5 lines
This is a total pain to optimise. Ideally I would like an API to be able to limit the congestion window on the local machine for a particular connection (which I don't think exists on either windows or linux?). This way the OS will report that the queue is full quickly to the local program without buffering up a ton of data.
Indeed. For TCP, you could use setsockopt with SO_SNDBUF maybe? However, I'm not sure this is what you want.
Quoted 8 lines
The issue in my case is that you have two simultaneous streams in transit for email, one to receive new mail and one to send mail out. In the case of the sat phone it's possible to have net buffers which are 20 secs or so long and so when you send out a status message to say "email received successfully, send me the next one", it can end up queued behind a bunch of lower priority data for a VERY long time. Often these buffers are on the remote ISP end where you have very little control. This is a serious slowdown on a link which is costing you $1.50/min.
Assuming you can send both ways simultaneously, or at least guarantee some traffic time outbound no matter how busy the inbound traffic, you would surely have to pipeline your commands in order to get any kind of efficient use out of a high-latency link like a satellite link. Otherwise you lose 2x round-trip-time of incoming data stream while you request the next item.
In this situation, you would want the OS buffers to be as full as possible so the minimal time possible is spent receiving, but using a traffic-shaping solution so that the most important stuff (acks and commands) goes out in preference to whatever else you're sending.
eg. If you're doing POP3 and SMTP, you make sure any to-tcp-110 or tcp-ack-only packet is dequeued before any from-tcp-25 packets.
You'd also need to jack the receive window right up, or wait for TCP to figure that out for itself.
Quoted 3 lines
My main focus has been adjusting the protocol to be less interactive, but it would be nice to have more operating system support for these fringe cases
This is actually a common case, and often cited as a great big hole in TCP/IP's traffic algorithms. I know, it was a question on the exam. ^_^
Signature · 5 lines
Paul "TBBle" Hampson, on an alternate email client. _______________________________________________ LARTC mailing list [email protected] http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 5 lines · Ed W
This is a total pain to optimise. Ideally I would like an API to be able to limit the congestion window on the local machine for a particular connection (which I don't think exists on either windows or linux?).
It looks like you could do it per route in the past - don't know about now.
http://www.linux-ip.net/gl/ip-cref/node77.html
Andy.
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 2 lines
From: [email protected] (Paul Hampson)
Wait, you're trying to send more data than the link can take? Then
No, of course I don't expect to send more than the limit.
Quoted 2 lines
send UDP, throttle it at the local end with a drop-oldest qdisc. Then you get the effect of 'most recent data is best'. Anything more
Yes, that gives me "most recent is best" but that does not do what I want except in a few weird cases. If every packet is independent, perhaps it would suffice to always send the newest, e.g., if I were trying to tell the other side what's the latest clock time. (In that case I'd also limit the queue length to one.)
Quoted 3 lines
You gotta prioritise your data, using TOS or diffserv or something. Set your voice to real-time, so it always gets sent, and the your other applications can use unused packet-times. Use a dropping qdisc
This may be the best I can do in the current world where the facility I described does not exist. It does not solve the problem I described. TOS/diffserv etc is more for use by the intervening infrastructure and this problem applies even in the case where there is no congestion or delay at all in that infrastructure, but only in the link from the sending machine. Using "real time" is just a matter of giving one application priority over others. First, the link itself may have varying bandwidth, and second the other applications might also have urgent data to send. Dropping packets can be disastrous if they happen to contain critical data that is not duplicated in other packets. At very least I have to be able to find out which ones were dropped. But better than all of that is the ability to decide what to send at the last moment.
Quoted 5 lines
I have a vauge recollection that this sort of thing is discussed in Tannenbaum's Computer Networks textbook, to do with positional data of satellites or something. (eg. if the positional data is delayed, we write it off, we don't want to delay the data about where we are _now_ in order to know where we were _then_)
If the goal is to listen to the sound from .2 sec ago and it takes .1 sec to get there then clearly it's a waste of time to send data that's older than .1 sec. But the packet in the queue might have some data that's older and some that's newer. I can't drop part of it. Instead I'd like to know that the packet is about to be sent now, and respond by finding the best data to send now.
Quoted 7 lines
From: Ed W <[email protected]>
This is a total pain to optimise. Ideally I would like an API to be able to limit the congestion window on the local machine for a particular connection (which I don't think exists on either windows or linux?). This way the OS will report that the queue is full quickly to the local program without buffering up a ton of data.
Quoted 8 lines
The issue in my case is that you have two simultaneous streams in transit for email, one to receive new mail and one to send mail out. In the case of the sat phone it's possible to have net buffers which are 20 secs or so long and so when you send out a status message to say "email received successfully, send me the next one", it can end up queued behind a bunch of lower priority data for a VERY long time. Often these buffers are on the remote ISP end where you have very little control. This is a serious slowdown on a link which is costing you $1.50/min.
I'm not sure I follow the problem, but if you're saying that one stream should have priority over the other, it seems you could do that with two different queues, one with priority over the other. Or something like sfq could at least prevent one connection from waiting for the other to send a lot of data.
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 8 lines
Assuming you can send both ways simultaneously, or at least guarantee some traffic time outbound no matter how busy the inbound traffic, you would surely have to pipeline your commands in order to get any kind of efficient use out of a high-latency link like a satellite link. Otherwise you lose 2x round-trip-time of incoming data stream while you request the next item.
Quoted 6 lines
In this situation, you would want the OS buffers to be as full as possible so the minimal time possible is spent receiving, but using a traffic-shaping solution so that the most important stuff (acks and commands) goes out in preference to whatever else you're sending.
Yes you do want to pipeline, but you still don't want the OS buffers full as possible. Consider that you might want to know a message was sent successfully before sending the next message, but at the same time you have the pipe full with downloading new messages. The OK which says the message was sent OK can be behind 15-20 seconds worth of downloads - hence you have to wait a long time before you can start sending the next message!
Also you can't use any kind of QOS here because the hypothetical 15-20 second buffer is at the remote ISP end. (Who are not cooperative)
It's a tricky situation all you can do is figure out how to keep changing your protocol so that you don't ever need to hear a reply before you continue sending.
Anyone wants to buy it then drop me a line!
:-)
Ed W
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
Quoted 8 lines
I'm not sure I follow the problem, but if you're saying that one stream should have priority over the other, it seems you could do that with two different queues, one with priority over the other. Or something like sfq could at least prevent one connection from waiting for the other to send a lot of data.
You could if you have control over the queues. But they are on the remote ISP end... So the problem is similar to the one you describe - once the data is inflight you lose control but you want to limit how much data is inflight so that you have as much control as possible...
Ed W
_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc