Packet dropping

Given a per-connection queue that could potentially become full (or in 
case of RED, hits dropping threshold), an incoming packet arrives and 
finds the queue full. What would be the best policy:

1) admit the new packet and drop one at the queue front
2) drop the newly arriving packet.

For real-time connections, it is intuitive that dropping at queue front 
would tend to result in better delay responses (this was already shown 
in an early paper by Yin and Hluchyj in IEEE Trans. Comm, June 1993). 
What about data/non-real time connections? Assume an FTP or HTTP session 
subject to above situation, would TCP behave better if packet is dropped 
from front or  the new packet is dropped?

I have no evidence but I tend to feel that if the congestion is 
persistent for some reasonable time, it would make more sense to deliver 
whatever is in the queue right now and drop the new ones at the expense 
of increasing overall avg. packet delay. If the congestion duration is 
small, it would not make a lot of difference (I guess).

Any thoughts?

Khaled

Re: Packet dropping

For non-real time, the answer I believe is drop the new packet.

Dropping the earlier packet (assuming the earlier packet has a lower
sequence number) is more likely to slow effective delivery of data
to the recipient and require a more complex set of retransmissions to
recover from.

Craig

In message <463857A4.1020205 <at> gmail.com>, Khaled Elsayed writes:

>Given a per-connection queue that could potentially become full (or in 
>case of RED, hits dropping threshold), an incoming packet arrives and 
>finds the queue full. What would be the best policy:
>
>1) admit the new packet and drop one at the queue front
>2) drop the newly arriving packet.
>
>For real-time connections, it is intuitive that dropping at queue front 
>would tend to result in better delay responses (this was already shown 
>in an early paper by Yin and Hluchyj in IEEE Trans. Comm, June 1993). 
>What about data/non-real time connections? Assume an FTP or HTTP session 
>subject to above situation, would TCP behave better if packet is dropped 
>from front or  the new packet is dropped?
>
>I have no evidence but I tend to feel that if the congestion is 
>persistent for some reasonable time, it would make more sense to deliver 
>whatever is in the queue right now and drop the new ones at the expense 
>of increasing overall avg. packet delay. If the congestion duration is 

Re: Collaboration on Future Internet Architectures

virtualization could be a very good thing for solving one past and one future
problem.

1/ some people have claimed that one can build many-to-many multihop radio
systems that offer more capacity as the number of nodes join. If this is true,
this can operate within quite a narrow band (e.g. ISM) and should be sufficient
for a very long time. If we can show its true in that band, other bands can
follow - within regions we still need to multipelx spectrum in some hard non
liquid (dave reed) way just til some of the technology is better  the identifiers
and management of this could be done through Virtual Private Wireless Channel
Idenfiers which might use some name space we have seen before

2/ some people claim that IPv6 will never deploy in the core, and that we have to
live with IPv4 core networks even thugh practically all significant end systems
are IPv6 capable. on the other hand other people have looked at the net and
decided that one of the big problems is that receivers can be sent data from just
about anywhere even though their kinship groups are relalyl quite limited. what
we need is a virtual private IPv4 internet per kinship group, and the VPII
(Virtual Private Internet Identifier, yes it does sound like a VPI in ATM speak:)
would be the IPv6 provider number (yes this isn't new, but i thought i'd spell it
out)

of course, with plutarch, all this would be easy, but its taking us longer to
code than we expected

 >>A vital part of this effort concerns fostering collaboration and
 >>consensus-building among researchers working on future global network
 >>architectures. To this end, NSF has created a FIND Planning Committee
 >>that works with NSF to organize a series of meetings among FIND grant
 >>recipients structured around activities to identify and refine

Re: Packet dropping

Re: Packet dropping

In message <62857.93128.qm <at> web25415.mail.ukl.yahoo.com>, Saqib Ilyas writes:

>I would expect for non-real-time protocols such as FTP that if the packet at t
 >he head of the queue is dropped, there'd be several duplicate acks which coul
 >d trigger congestion control. 
>  Regards

I understand that point.

My reasoning may be flawed, but just to dig myself deeper.  The
question was what's the best way for the queue to drain?

So let's consider ten packets 0-9 in flight at sender, router and receiver

In the scenario, the router is about to receive buffer 9

    Sender's buffer		Router Buffer		Receiver Buffer

    012345679			012345679

If it drops 9, then in one RTT we'll have

    Sender's buffer		Router Buffer		Receiver Buffer

    9abcdefghi			<some packets>

If it drops 0, then in one RTT with fast retransmit we'll have

    Sender's buffer		Router Buffer		Receiver Buffer
    012345679			0			123456789

In either case the router queue looks similar -- the issue is which wins
going forward.  And it wasn't immediately clear to me that fast retransmit
was better.  If we drop 0, we're in fast retransmit and about to enter
slow start on packet a.  If we drop 9, we're about to fire off dupe acks
on a-i, and will enter fast retransmit on packet b.

Craig

Re: Packet dropping

Hi Khaled,

I did some research on the impact of dropping packets from the front of a queue 
that might be of interest for you. It was related to the approximative longest 
queue drop algorithm and shows how packet drops from the front of a queue can 
help TCP to maintain a certain bandwidth share in presence of a non-responsive 
source. Have a look at section 3 in the report:

http://ecwww.eurecom.fr/~pletka/publications/report-pletka-99.pdf

Best regards,
Roman

Khaled Elsayed wrote:
> Given a per-connection queue that could potentially become full (or in 
> case of RED, hits dropping threshold), an incoming packet arrives and 
> finds the queue full. What would be the best policy:
> 
> 1) admit the new packet and drop one at the queue front
> 2) drop the newly arriving packet.
> 
> For real-time connections, it is intuitive that dropping at queue front 
> would tend to result in better delay responses (this was already shown 
> in an early paper by Yin and Hluchyj in IEEE Trans. Comm, June 1993). 
> What about data/non-real time connections? Assume an FTP or HTTP session 
> subject to above situation, would TCP behave better if packet is dropped 
> from front or  the new packet is dropped?
> 
> I have no evidence but I tend to feel that if the congestion is 
> persistent for some reasonable time, it would make more sense to deliver 
> whatever is in the queue right now and drop the new ones at the expense 
> of increasing overall avg. packet delay. If the congestion duration is 
> small, it would not make a lot of difference (I guess).
> 
> Any thoughts?
> 
> Khaled
> 
> 

--

-- 
---------------------------------------------------------------------------
Dr. Roman Pletka                                            roman <at> pletka.ch
Meilibachweg 11                                    Private: +41 43 244 6654
CH-8810 Horgen                                      Mobile: +41 79 293 6948
---------------------------------------------------------------------------

Re: Packet dropping (Khaled Elsayed)

My belief is as Craig said, for real-time packets - dropping the oldest
packet would be the best solution - so it would be better to drop from the
front of the queue, as most of the real-time packets (VoIP,
videoconferencing) would be carried on UDP or DCCP - which do not require
transport layer retransmissions. We need to note dropping real-time packets
such as VoIP packets (carried by UDP or DCCP) would be more of a concern to
the application layer rather than the transport layer.

But for non-real time applications running over TCP - then I would prefer to
see the new packet being dropped rather the oldest packet - as it would be a
burden to the transport layer - since the transport layer has to buffer up
all the out of order packets!

Arjuna

------------------------------

Message: 2
Date: Wed, 02 May 2007 06:33:08 -0400
From: Craig Partridge <craig <at> aland.bbn.com>
Subject: Re: [e2e] Packet dropping
To: Khaled Elsayed <kelsayed <at> gmail.com>
Cc: end2end-interest <at> postel.org
Message-ID: <20070502103308.0E521123842 <at> aland.bbn.com>

For non-real time, the answer I believe is drop the new packet.

Dropping the earlier packet (assuming the earlier packet has a lower
sequence number) is more likely to slow effective delivery of data
to the recipient and require a more complex set of retransmissions to
recover from.

Craig
***************************************

Re: Packet dropping

Dropping the new packet slows the current TCP congestion control 
algorithm's response, leading to slower and slower clogged Stevens' 
pipes, and a long time to recover.

Making the control loop for congestion faster end-to-end is a real-time 
problem embedded in non-real-time data transfers, and it affects overall 
performance.

Craig Partridge wrote:
> For non-real time, the answer I believe is drop the new packet.
>
> Dropping the earlier packet (assuming the earlier packet has a lower
> sequence number) is more likely to slow effective delivery of data
> to the recipient and require a more complex set of retransmissions to
> recover from.
>
> Craig
>
>
> In message <463857A4.1020205 <at> gmail.com>, Khaled Elsayed writes:
>
>   
>> Given a per-connection queue that could potentially become full (or in 
>> case of RED, hits dropping threshold), an incoming packet arrives and 
>> finds the queue full. What would be the best policy:
>>
>> 1) admit the new packet and drop one at the queue front
>> 2) drop the newly arriving packet.
>>
>> For real-time connections, it is intuitive that dropping at queue front 
>> would tend to result in better delay responses (this was already shown 
>> in an early paper by Yin and Hluchyj in IEEE Trans. Comm, June 1993). 
>> What about data/non-real time connections? Assume an FTP or HTTP session 
>> subject to above situation, would TCP behave better if packet is dropped 
>>     
> >from front or  the new packet is dropped?
>   
>> I have no evidence but I tend to feel that if the congestion is 
>> persistent for some reasonable time, it would make more sense to deliver 
>> whatever is in the queue right now and drop the new ones at the expense 
>> of increasing overall avg. packet delay. If the congestion duration is 
>> small, it would not make a lot of difference (I guess).
>>
>> Any thoughts?
>>
>> Khaled
>>     
>
>   

Re: Packet dropping (Khaled Elsayed)

Actually, TCP typically retransmits all the "out of order" packets you 
refer to Arjuna, because the sender won't know the receiver has received 
them unless SACK is working, an option that is not necessarily there.   
So the receiver can just drop all the out of order packets after a loss 
due to congestion without affecting throughput.

If you had a channel that could carry acknowledgements faster than the 
speed of light (a so-called ESP channel), of course you could invent a 
more interesting protocol than TCP.

But then you'd have to require that of every technology supported by 
TCP, and it's important to remember that TCP is a protocol for interop 
among heterogeneous technologies as its number one goal.   Super hyper 
optimized multihop subnets of uniform technology are best deployed as an 
underlay under TCP, and viewed as a link.

Arjuna Sathiaseelan wrote:
> My belief is as Craig said, for real-time packets - dropping the oldest
> packet would be the best solution - so it would be better to drop from the
> front of the queue, as most of the real-time packets (VoIP,
> videoconferencing) would be carried on UDP or DCCP - which do not require
> transport layer retransmissions. We need to note dropping real-time packets
> such as VoIP packets (carried by UDP or DCCP) would be more of a concern to
> the application layer rather than the transport layer.
>
> But for non-real time applications running over TCP - then I would prefer to
> see the new packet being dropped rather the oldest packet - as it would be a
> burden to the transport layer - since the transport layer has to buffer up
> all the out of order packets!
>
>
> Arjuna
>
> ------------------------------
>
> Message: 2
> Date: Wed, 02 May 2007 06:33:08 -0400
> From: Craig Partridge <craig <at> aland.bbn.com>
> Subject: Re: [e2e] Packet dropping
> To: Khaled Elsayed <kelsayed <at> gmail.com>
> Cc: end2end-interest <at> postel.org
> Message-ID: <20070502103308.0E521123842 <at> aland.bbn.com>
>
>
> For non-real time, the answer I believe is drop the new packet.
>
> Dropping the earlier packet (assuming the earlier packet has a lower
> sequence number) is more likely to slow effective delivery of data
> to the recipient and require a more complex set of retransmissions to
> recover from.
>
> Craig
> ***************************************
>
>
>   

Re: Packet dropping

On May 2, 2007, at 10:36 AM, Craig Partridge wrote:
> My reasoning may be flawed, but just to dig myself deeper.  The
> question was what's the best way for the queue to drain?
>
> So let's consider ten packets 0-9 in flight at sender, router and 
> receiver
>
> In the scenario, the router is about to receive buffer 9
>
>     Sender's buffer		Router Buffer		Receiver Buffer
>
>     012345679			012345679
>
> If it drops 9, then in one RTT we'll have
>
>     Sender's buffer		Router Buffer		Receiver Buffer
>
>     9abcdefghi			<some packets>
>
> If it drops 0, then in one RTT with fast retransmit we'll have
>
>     Sender's buffer		Router Buffer		Receiver Buffer
>     012345679			0			123456789
>
>
> In either case the router queue looks similar -- the issue is which 
> wins
> going forward.  And it wasn't immediately clear to me that fast 
> retransmit
> was better.  If we drop 0, we're in fast retransmit and about to enter
> slow start on packet a.  If we drop 9, we're about to fire off dupe 
> acks
> on a-i, and will enter fast retransmit on packet b.

At the risk of ignoring previously stated context I think it is prudent 
to _not_ assume there will be segments abcdfeghi, in which case, 
dropping 0 gives us the best chance at having fast retransmit in the 
first place rather than a retransmission timeout.

rick jones
there is no rest for the wicked, yet the virtuous have no pillows