RFC: replace packets already in queue

(I've send this email already in the lartc mailing list. Short after this I found the list seems dead (http://dir.gmane.org/gmane.linux.network.routing). I hope this is the correct place to ask. If not - please give me a note, where I can ask this.)

----------

Hello.

I'm writing a kernel module (net/sched) which replaces packets in the queue. I'm glad hearing your option.

Background:
In very low bandwidth network (<=9.6Kbps, shared, etc.) its hard (rather: impossible) to get all packets sent.
But some of the packets contain information, which gets obsolete over time. E.g. (GPS) positions, which will be sent periodically. If the application sends a new packet while an old position packet is still in the queue, the old packet is obsolete. This can be dropped. But just dropping the old packet and queuing the new packet will result in never sending a packet of this type.

So I'm writing a tc-qdisc scheduler module, which replaces packets in the queue on enqueuing, when this properties are given:
- UDPv4
- not fragmented
- (TOS & bitmask) = givenCompare; (bitmask and compare are adjustable)
- same source IP
- same destination IP
- same destination port
- same TOS
So, the packet got sent over the time - but with the actual information.

What do you think? Is this module worth to get released to kernel.org? Have you any other comments?

Greetings
Ralph Erdt

You might want to try the recent "codel" additions to the stack.  They 
seek to keep the size of queues more manageable while still allowing the 
occasional burst.

rick jones

Hello Rick Jones,

You might want to try the recent "codel" additions to the stack.  They
seek to keep the size of queues more manageable while still allowing
the occasional burst.

Thank you for your hint. This is surly a needful solution in normal network, but this didn't help us:
We are working with very heterogeneous networks:
Internal: 100MBit and more.
Extern: 9,6*K*Bit and LESS(*), and shared, and...
A few other information: wireless (higher packet loss rate), medium access time > 100ms, RTT (standard ping) with IDLE network: 1,5 *seconds*, RTT with network load: minutes(!), and so on. Just very shocking..

TCP isn't usable over such a link. So we are only sending UDP. The codel didn't help us, as codel addresses the flow speed. It's dropping "randomly" (I know it's not random in the lower level, but it's random from the application's perspective) packets. 

I'm addressing the amount of information: Trying to reduce it intelligently by REPLACING old packets with new ones.. Surely - the application must handle this. But in such a network a administrator have to configure the queues and he knows the applications.
In one private mail someone guesses that we are making VoIP. No - we just want to send status information (e.g. sensor information) which will get deprecated, when a new information is available.

I know, this is a very special problem, which didn't occur in normal or even abnormal situations. But I'm sure there are some other people having the this problem, too. So I'm glad to share my solution.

(*you remember the good ol' times with modems over telephone lines? When the internet was called BBS? And how it suddenly feels, when the BBS starts using ANSI? This was comfortable compared to our problem..)

Greetings
Ralph Erdt

On Fri, 2012-06-29 at 08:46 +0000, Erdt, Ralph wrote:

Hello Rick Jones,

quoted

You might want to try the recent "codel" additions to the stack.  They
seek to keep the size of queues more manageable while still allowing
the occasional burst.

Thank you for your hint. This is surly a needful solution in normal network, but this didn't help us:
We are working with very heterogeneous networks:
Internal: 100MBit and more.
Extern: 9,6*K*Bit and LESS(*), and shared, and...
A few other information: wireless (higher packet loss rate), medium access time > 100ms, RTT (standard ping) with IDLE network: 1,5 *seconds*, RTT with network load: minutes(!), and so on. Just very shocking..

TCP isn't usable over such a link. So we are only sending UDP. The codel didn't help us, as codel addresses the flow speed. It's dropping "randomly" (I know it's not random in the lower level, but it's random from the application's perspective) packets. 

I'm addressing the amount of information: Trying to reduce it intelligently by REPLACING old packets with new ones.. Surely - the application must handle this. But in such a network a administrator have to configure the queues and he knows the applications.
In one private mail someone guesses that we are making VoIP. No - we just want to send status information (e.g. sensor information) which will get deprecated, when a new information is available.

I know, this is a very special problem, which didn't occur in normal or even abnormal situations. But I'm sure there are some other people having the this problem, too. So I'm glad to share my solution.

(*you remember the good ol' times with modems over telephone lines? When the internet was called BBS? And how it suddenly feels, when the BBS starts using ANSI? This was comfortable compared to our problem..)

Problem is : with wireless, chances are high that the old packet is not
waiting in qdisc, but in wireless queues.

Anyway, adding a maxdelay to codel / fq_codel is really easy : This
would drop packet if its sejourn time is above a given limit.

You could use codel with @target being greater than @maxdelay to remove
all probabilistic drops, and only keep the @maxdelay behavior.

If you want I can cook this patch.

Hello Eric Dumazet,

sorry for the late answer, but sometimes it's not easy here...

Problem is : with wireless, chances are high that the old packet is not
waiting in qdisc, but in wireless queues.

Even if the wireless queue is a problem (because of our setup, this is not a problem), the network stack queue (*) is the biggest queue, and a good point to optimize. And its impossible doing things 100%. We are happy to get 99%. This is a great improvement compared to the previous situation.

(* When I'm getting the picture in http://lartc.org/howto/lartc.qdisc.terminology.html correct, the qdisc is the outgoing queue and the last queue of the kernel. After this queue, there are only the hardware queues.)

Anyway, adding a maxdelay to codel / fq_codel is really easy : This
would drop packet if its sejourn time is above a given limit.

Just dropping when to old is not our goal. In fact we are avoiding blind dropping! With our replace we make sure that a packet of one class will go over the air when this packet is in line. But the information was replaced during the stay in the queue, so that the newest information got sent.

If you want I can cook this patch.

Thank for you offer/support. But as described above, this is not a solution for us (we discussed this again in our group).  

Greetings
Ralph Erdt

On Mon, 2012-07-02 at 07:02 +0000, Erdt, Ralph wrote:

Even if the wireless queue is a problem (because of our setup, this is
not a problem), the network stack queue (*) is the biggest queue, and
a good point to optimize. 

Hmm, I am not convinced you have no queues on wireless.

Please describe how you managed this.

In fact this is the biggest problem with wireless : mac82011 framework
aggressively pull packets from Linux packet qdisc in order to perform
packet aggregation.

Most packets don't stay in qdisc but are sitting in wireless driver,
unless you really flood it. If it happens, you already are in trouble.

So code your qdisc thing, but I am not sure you'll get much improvement.
You would need to implement it in wireless code instead.

quoted

Even if the wireless queue is a problem (because of our setup, this

is

quoted

not a problem), the network stack queue (*) is the biggest queue, and
a good point to optimize.

Hmm, I am not convinced you have no queues on wireless.

Please describe how you managed this.

In fact this is the biggest problem with wireless : mac82011 framework
aggressively pull packets from Linux packet qdisc in order to perform
packet aggregation.

I did not talking about W-LAN (802.11). I'm talking about an property technology which is able to send over KILOMETERs (WLAN < 100m) but with VERY low bandwidth: 9600 bit (no Mega, Giga or Kilo!) (W-LAN: slowest: 1Mbit).
The devices is loosely connected to our boxes: No linux driver but a program which create an virtual network device. This just sends one packet to the devices and then waits for the acknowledgement that the packet was sent. THEN the next packet will be send. There is no further queue, because the wireless is so lame, that there is no need for that!
(BTW: the qdisc and the connector are distinct problems/programs. There is no dependency.)

Most packets don't stay in qdisc but are sitting in wireless driver,
unless you really flood it. If it happens, you already are in trouble.

We ARE in trouble... :-/

So code your qdisc thing, but I am not sure you'll get much
improvement.

It's implemented already (it's just a little source file), and it worked in the simulation. But I cannot test them on real devices ATM.

My question is: Should I do the work to create and release a kernel patch and make it perfect over the time, or is this just our internal code, which I can leave at the current state? I know our module won't be used widely (too special), but I'm sure, there are a few people out there, which would be thankful for this.

On 07/02/2012 01:38 AM, Erdt, Ralph wrote:

I did not talking about W-LAN (802.11). I'm talking about an
property technology which is able to send over KILOMETERs (WLAN <
100m) but with VERY low bandwidth: 9600 bit (no Mega, Giga or Kilo!)
(W-LAN: slowest: 1Mbit). The devices is loosely connected to our
boxes: No linux driver but a program which create an virtual network
device. This just sends one packet to the devices and then waits for
the acknowledgement that the packet was sent. THEN the next packet
will be send. There is no further queue, because the wireless is so
lame, that there is no need for that! (BTW: the qdisc and the
connector are distinct problems/programs. There is no dependency.)

quoted

Most packets don't stay in qdisc but are sitting in wireless
driver, unless you really flood it. If it happens, you already are
in trouble.

We ARE in trouble... :-/

While you may need to tweak some of the constants based on your bitrate
and MTU size (which if the former is 9600 bits per second I trust the
latter is rather smaller than 1500 bytes since that would be well over a
second to transmit... and so the RTT there will be large), it sounds 
like codel will do good things for you.  It won't replace the packet, 
but its use of drop on dequeue will I believe accomplish substantially 
the same effect.

rick jones

Le 02/07/2012 10:38, Erdt, Ralph a écrit :

quoted

quoted

Even if the wireless queue is a problem (because of our setup, this

is

quoted

not a problem), the network stack queue (*) is the biggest queue, and
a good point to optimize.

Hmm, I am not convinced you have no queues on wireless.

Please describe how you managed this.

In fact this is the biggest problem with wireless : mac82011 framework
aggressively pull packets from Linux packet qdisc in order to perform
packet aggregation.

I did not talking about W-LAN (802.11). I'm talking about an property technology which is able to
send over KILOMETERs (WLAN<  100m) but with VERY low bandwidth: 9600 bit (no Mega, Giga or Kilo!)
(W-LAN: slowest: 1Mbit). The devices is loosely connected to our boxes: No linux driver but a
program which create an virtual network device. This just sends one packet to the devices and
then waits for the acknowledgement that the packet was sent. THEN the next packet will be send.
There is no further queue, because the wireless is so lame, that there is no need for that! (BTW:
the qdisc and the connector are distinct problems/programs. There is no dependency.)

If I were you, I would use a tun/tap interface and manage a private packet queue in userspace. This 
way, you wouldn't have to manage the overhead of porting your kernel code to every new kernel versions.

	Nicolas.

On Mon, 2012-07-02 at 22:32 +0200, Nicolas de Pesloüan wrote:

Le 02/07/2012 10:38, Erdt, Ralph a écrit :

quoted

quoted

quoted

Even if the wireless queue is a problem (because of our setup, this

is

quoted

not a problem), the network stack queue (*) is the biggest queue, and
a good point to optimize.

Hmm, I am not convinced you have no queues on wireless.

Please describe how you managed this.

In fact this is the biggest problem with wireless : mac82011 framework
aggressively pull packets from Linux packet qdisc in order to perform
packet aggregation.

I did not talking about W-LAN (802.11). I'm talking about an property technology which is able to
send over KILOMETERs (WLAN<  100m) but with VERY low bandwidth: 9600 bit (no Mega, Giga or Kilo!)
(W-LAN: slowest: 1Mbit). The devices is loosely connected to our boxes: No linux driver but a
program which create an virtual network device. This just sends one packet to the devices and
then waits for the acknowledgement that the packet was sent. THEN the next packet will be send.
There is no further queue, because the wireless is so lame, that there is no need for that! (BTW:
the qdisc and the connector are distinct problems/programs. There is no dependency.)

If I were you, I would use a tun/tap interface and manage a private packet queue in userspace. This 
way, you wouldn't have to manage the overhead of porting your kernel code to every new kernel versions.

This seems a good idea.

Then you can do other coalescing stuff, like TCP ACK that could be
aggregated to single ACK as well.

quoted

If I were you, I would use a tun/tap interface and manage a private
packet queue in userspace. This way, you wouldn't have to manage the

overhead of porting your kernel code to every new kernel versions.

quoted

This seems a good idea.

Then you can do other coalescing stuff, like TCP ACK that could be
aggregated to single ACK as well.

Thanks for the idea. But this is option when just doing the replace thing.
But the charm of the qdisc solution is the complete integration to TC. It's complete compatible to the other options, so that you can create a bigger TC rule set. And creating the rules is a standard operation for the administrators - they know TC.

In terms of the other coalescing stuff (we didn't use TCP, because it's not possible) - it's already done in the device "driver" I mentioned. Yes, we can extend the "driver", but the qdisc solution has the benefit that there is a clear separation.

Nevertheless we will discuss the idea internally. Maybe the group got another idea based on this.

Hello,

I found, that my eMail program send the eMail as UTF-8 / Base64. I'm sorry for the circumstances. I hope it's OK for you, that I'm repeating the content, so that everyone can follow it. But I will compress the whole discussion (Thanks to Eric Dumazet, Rick Jones and Nicolas de Peslouan):

-

I'm writing a kernel module (net/sched) which replaces packets in the queue. I'm glad hearing your option.

Background:
We are working with a property wireless network (no 802.11). The specifications: 
 Range: Kilometers.
 Speed: <=9,600 bps (no Megs, Gigs or Kilo!) (*).
 RTT (standard ping): idle-network: 1,5 *seconds*; network with load: minutes
 Other: shared.
 Connection: loosely to a Linux box, but without Linux driver. 
 Driver: a user-space program, which opens a virtual network device and sends 
         the packet from the virtual network device to the device.
 Queue: The device has no queue nor the user-space program. The program waits 
         for the ACK from the device before sending the next packet. This is 
         possible, because the wireless is so lame...

(*you remember the good ol' times with modems over telephone lines? When the 
internet was called BBS? And how it suddenly feels, when the BBS starts using
ANSI? This was comfortable compared to our problem..)

With such a very low bandwidth network its hard (rather: impossible) to get all 
packets sent. (TCP isn't possible, so we are sending everything as UDP.)
Some of the packets contain information, which gets obsolete over time. E.g. 
(GPS) positions, which will be sent periodically. If the application sends a new 
packet while an old position packet is still in the queue, the old packet is 
obsolete. This can be dropped. But just dropping the old packet and queuing the 
new packet will result in never sending a packet of this type.

So I've written a tc-qdisc scheduler module, which replaces packets in the queue 
on enqueuing, when this properties are given:
- UDPv4
- not fragmented
- (TOS & bitmask) = givenCompare; (bitmask and compare are adjustable)
- same source IP
- same destination IP
- same destination port
- same TOS
So, the packet got sent over the time - but with the actual information.
 (The code is tiny - just a file (and Kconfig, etc.))

Why not using "codel"? Because codel will drop "randomly" ("random" not for the 
protocol, but for the application) packets. It's made to reduce the flow speed.
But we haven't a flow, only periodic sensor data.
My qdisc won't drop random packets. It will reduce the traffic by intelligently 
replacing packets in the queue. Surely - the application must handle this. But 
in such a network a administrator have to configure the queues and he knows the 
applications.

Why not adding a tun/tap interface and do everything in the user space? 
As mentioned, the device "driver" is a user space program, which creates a tun/tap
interface. We CAN mix the code there in, but separating the work has a few benefits:
- separating the work with clear interfaces is always a good idea.
- having a qdisc will allow complex TC rules using this qdisc - it's fully compatible.
  (In fact - we have guidelines given. We can handle all of the guidelines with the 
   given TC classes - except the replace thing.)
- administrators knowing TC can work with this qdisc without any problems

My question is: Should I do the work to create and release a kernel patch and make 
it perfect over the time, or is this just our internal code, which I can leave at 
the current state? I know our module won't be used widely (too special), but I'm 
sure, there are a few people out there, which would be thankful for this.

Have you any other comments?

Greetings
Ralph Erdt 

Le 03/07/2012 12:02, Erdt, Ralph a écrit :

My question is: Should I do the work to create and release a kernel patch and make
it perfect over the time, or is this just our internal code, which I can leave at
the current state? I know our module won't be used widely (too special), but I'm
sure, there are a few people out there, which would be thankful for this.

I suggest you try and send a properly formated patch with your code, so that people here can have a 
look at it and evaluate the interest of integrating it into main line kernel.

That being said, I really think you should try to manage a userspace queue, in particular if you 
already have most of the job done in userspace using a tun/tap. I don't know the details of the 
special device you work with, but if you manage both side of the link, you can add many nice 
features into userspace to enhance the speed/quality :

- Compression (including very clever one if you know the meaning of the data you are transmitting).
- Packet numbering, to allow the remote side to ACK packet, the same way TCP does.
- Early ACK on TCP, if you get an ACK from the other side of your link and you assure that this link 
is the worst part of the path. This may help TCP to work on this low speed/high RTT link.

And I really see your packet replacement system as one of those nice features and cannot imagine a 
good reason not to put it in userspace.

	Nicolas.

Hello.

I'm sorry for the very late answer. But I had top-priority family issues.

I suggest you try and send a properly formated patch with your code, so
that people here can have a look at it and evaluate the interest of
integrating it into main line kernel.

Attached at the button of the eMail.

That being said, I really think you should try to manage a userspace
queue, [..] you can
add many nice features into userspace to enhance the speed/quality 
[..]
And I really see your packet replacement system as one of those nice
features and cannot imagine a good reason not to put it in userspace.

All this features are done already. E.g. we are using RoHC.
But we also want to use the TC stuff - its already there - why reprogramming?

Here the patch. But I didn't find which git tree I should use. This patch is against Linux-2.6. I'm sorry. Can you tell me, which tree I've to use?
-------------

From 52f27fa2b0867de821af38c731c2ebc763afb1f1 Mon Sep 17 00:00:00 2001

From: Ralph Erdt <redacted>
Date: Wed, 18 Jul 2012 16:43:44 +0200
Subject: [PATCH] RFC: TC qdisc "replace packet in queue"

This adds a new TC qdisc, which replaces packets in the queue. It
compares every incoming packet with all of the packets in the queue.
If the incoming and the compared packet meet all these conditions:
 - UDPv4
 - not fragmented
 - TOS like the given value(s)
 - same TOS
 - same source IP
 - same destination IP
 - same destination port
the packet in the queue will be replaced with the incoming packet.

The variable "overlimit" is the counter of replaced packets

Background:
In very low bandwidth networks (<=9.6Kbps, shared, etc.) it's hard
(rather: impossible) to get all packets sent.
But some of the packets contain information, which gets obsolete over
time. E.g. (GPS) positions, which will be sent periodically. If the
application sends a new packet while an old position packet is still in
the queue, the old packet is obsolete. This can be dropped. But just
dropping the old packet and queuing the new packet will result in never
sending a packet of this type. So this qdisc replace the old packet with
the new one. The information gets the chance to get sent - with the
newest available information.

Code-Status:
RFC for discussing.
The configuration by "debug-fs" is ... not optimal. But following the
"litte step" rules this is a first option. A configuration with tc will
be done later (if this patch got offical).

Signed-off-by: Ralph Erdt <redacted>
---
 net/sched/Kconfig  |   16 +++
 net/sched/Makefile |    1 +
 net/sched/sch_pr.c |  264 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 281 insertions(+), 0 deletions(-)
 create mode 100644 net/sched/sch_pr.c

diff --git a/net/sched/Kconfig b/net/sched/Kconfig
index e7a8976..e29ad48 100644
--- a/net/sched/Kconfig
+++ b/net/sched/Kconfig

@@ -308,6 +308,22 @@ config NET_SCH_PLUG
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_plug.
 
+config NET_SCH_PR
+	tristate "Packet Replace"
+	help
+	  Say Y here if you want to use the "Packet Replace"
+	  packet scheduling algorithm.
+
+	  This qdisc will replace packets in the queue, if this is a packet
+	  from the same UDP stream (IP/Port).
+
+	  See the top of <file:net/sched/sch_pr.c> for more details.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_pr.
+
+	  If unsure, say N.
+
 comment "Classification"
 
 config NET_CLS

diff --git a/net/sched/Makefile b/net/sched/Makefile
index 5940a19..ef669ff 100644
--- a/net/sched/Makefile
+++ b/net/sched/Makefile

@@ -39,6 +39,7 @@ obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
 obj-$(CONFIG_NET_SCH_QFQ)	+= sch_qfq.o
 obj-$(CONFIG_NET_SCH_CODEL)	+= sch_codel.o
 obj-$(CONFIG_NET_SCH_FQ_CODEL)	+= sch_fq_codel.o
+obj-$(CONFIG_NET_SCH_PR)	+= sch_pr.o
 
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o

diff --git a/net/sched/sch_pr.c b/net/sched/sch_pr.c
new file mode 100644
index 0000000..5cbf8d8
--- /dev/null
+++ b/net/sched/sch_pr.c

@@ -0,0 +1,264 @@
+/*
+ * net/sched/sch_pr.c	"packet replace"
+ *
+ * Copyrigth (c) 2012 Fraunhofer FKIE, all rigths reserved.
+ *
+ *		This program is free software; you can redistribute it and/or
+ *		modify it under the terms of the GNU General Public License
+ *		as published by the Free Software Foundation; either version
+ *		2 of the License, or (at your option) any later version.
+ *
+ * Authors:	Ralph Erdt (Fraunhofer FKIE),
+ *                                 <ralph.robert.erdt@fkie.fraunhofer.de>
+ */
+
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/errno.h>
+#include <linux/skbuff.h>
+#include <net/pkt_sched.h>
+
+#include <linux/ip.h>
+#include <net/ip.h>
+#include <linux/debugfs.h>
+
+/*
+ * replace packet in queue
+ * ==========================
+ * This is a modified fifo queue (fifo by Alexey Kuznetsov).
+ *
+ * This packet compares every incoming packet with all of the packets in the
+ * queue.
+ * If the incoming and the compared packet meet all these conditions:
+ *  - UDPv4
+ *  - not fragmented
+ *  - TOS like the given value(s)
+ *  - same TOS
+ *  - same source IP
+ *  - same destination IP
+ *  - same destination port
+ * the packet in the queue will be replaced with the incoming packet.
+ *
+ * The variable "overlimit" is the counter of replaced packets
+ *
+ * Background:
+ * In very low bandwidth networks (<=9.6Kbps, shared, etc.) it's hard
+ * (rather: impossible) to get all packets sent.
+ * But some of the packets contain information, which gets obsolete over time.
+ * E.g. (GPS) positions, which will be sent periodically. If the application
+ * sends a new packet while an old position packet is still in the queue, the
+ * old packet is obsolete. This can be dropped. But just dropping the old
+ * packet and queuing the new packet will result in never sending a packet
+ * of this type.
+ * So this qdisc replace the old packet with the new one. The information gets
+ * the chance to get sent - with the newest available information.
+ *
+ * DRAWBACKS:
+ * Its not very CPU cycle saving. But on very low bandwith networks the
+ * application have to be careful with sending packets. And with a propper
+ * configuration, this will be OK.
+ */
+
+struct dentry *dgdir, *dgfile;
+
+#define TOSBITMASK 0
+#define TOSCOMPARE 1
+/* tos Flag. 1.: BitMask. 2.: Compare with */
+static u8 tos[] = {0xFF, 0xFF};
+
+bool pr_packet_to_work_with(struct sk_buff *pkt)
+{
+	struct iphdr *hdr;
+
+	if (unlikely(pkt->protocol != htons(ETH_P_IP)))
+		return false;
+
+	/* Only compare UDP - Layer 4 must be there */
+	if (unlikely(pkt->network_header == NULL))
+		return false;
+
+	hdr = ip_hdr(pkt);
+
+	/* Check for UDPv4 */
+	if (unlikely(hdr->protocol != IPPROTO_UDP))
+		return false;
+
+	/* no fragmented packets */
+	if (unlikely(ip_is_fragment(hdr)))
+		return false;
+
+	/* Correct TOS ? */
+	if ((hdr->tos & tos[TOSBITMASK]) != tos[TOSCOMPARE])
+		return false;
+
+	return true;
+}
+
+bool comp(struct sk_buff *a, struct sk_buff *b)
+{
+	struct iphdr *ah = NULL;
+	struct iphdr *bh = NULL;
+	u32 ipA, ipB;
+	u16 portsA, portsB;
+	int poff;
+	/* The packet has a header
+	 *  - the existence was already checked by "pr_packet_to_work_with" */
+	ah = ip_hdr(a);
+	bh = ip_hdr(b);
+
+	/* TOS must be the same */
+	if (ah->tos != bh->tos)
+		return false;
+
+	/* IP and Port must be the same */
+	ipA = (__force u32)ah->daddr;
+	ipB = (__force u32)bh->daddr;
+	if ((ipA != ipB))
+		return false;
+	ipA = (__force u32)ah->saddr;
+	ipB = (__force u32)bh->saddr;
+	if ((ipA != ipB))
+		return false;
+
+	poff = proto_ports_offset(IPPROTO_UDP);
+	if (unlikely(poff < 0))
+		/* This should be impossible.. */
+		return false;
+
+	/* Src Ports are always different - just compare destination ports */
+	portsA = *(u16 *)((void *)ah + bh->ihl * 4 + poff + 2);
+	portsB = *(u16 *)((void *)bh + ah->ihl * 4 + poff + 2);
+	if ((portsA != portsB))
+		return false;
+
+	return true;
+}
+
+static int pr_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+	struct sk_buff *replace = NULL;
+
+	/* Search, if there is a packet with same IDs */
+	/* Only search, if this packet is worth it */
+	if (pr_packet_to_work_with(skb)) {
+		struct sk_buff *it;
+		skb_queue_walk((&(sch->q)), it) {
+			/* If the other packet is worth it? */
+			if (pr_packet_to_work_with(it)) {
+				if (comp(skb, it)) {
+					replace = it;
+					break;
+				}
+			}
+		}
+	}
+
+	if (replace == NULL) {
+		/* a new kind of packet. Just enqueue */
+		if (likely(skb_queue_len(&sch->q) < sch->limit))
+			return qdisc_enqueue_tail(skb, sch);
+		return qdisc_reshape_fail(skb, sch);
+	} else {
+		/* replace the packet */
+		sch->qstats.overlimits++;
+		/* There is no drop nor replace. So do the replace myself */
+		skb->next = replace->next;
+		skb->prev = replace->prev;
+		if (replace->next != NULL)
+			replace->next->prev = skb;
+		if (replace->prev != NULL)
+			replace->prev->next = skb;
+		kfree_skb(replace);
+		return NET_XMIT_SUCCESS;
+	}
+}
+
+static int pr_init(struct Qdisc *sch, struct nlattr *opt)
+{
+	sch->flags |= TCQ_F_CAN_BYPASS; /* sounds good, but what? */
+	sch->limit = qdisc_dev(sch)->tx_queue_len ? : 1;
+	return 0;
+}
+
+static int pr_dump(struct Qdisc *sch, struct sk_buff *skb)
+{
+	struct tc_fifo_qopt opt = { .limit = sch->limit };
+
+	if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt))
+		goto nla_put_failure;
+
+	return skb->len;
+
+nla_put_failure:
+	return -1;
+}
+
+struct Qdisc_ops pr_qdisc_ops __read_mostly = {
+	.id		=	"pr",
+	.priv_size	=	0,
+	.enqueue	=	pr_enqueue,
+	.dequeue	=	qdisc_dequeue_head,
+	.peek		=	qdisc_peek_head,
+	.drop		=	qdisc_queue_drop,
+	.init		=	pr_init,
+	.reset		=	qdisc_reset_queue,
+	.change		=	pr_init,
+	.dump		=	pr_dump,
+	.owner		=	THIS_MODULE,
+};
+EXPORT_SYMBOL(pr_qdisc_ops);
+
+/* DebugFS interface as first shot configuration */
+static ssize_t dg_read_file(struct file *file, char __user *userbuf,
+					size_t count, loff_t *ppos)
+{
+	return simple_read_from_buffer(userbuf, count, ppos, tos, 2);
+}
+
+static ssize_t dg_write_file(struct file *file, const char __user *buf,
+					size_t count, loff_t *ppos)
+{
+	u8 tmp[] = {0xFF, 0xFF};
+	int res;
+	if (count != 2)
+		return -EINVAL;
+
+	res = copy_from_user(tmp, buf, count);
+	if (res != 0)
+		return -EINVAL;
+
+	/* Two bytes to copy.. for this a memcpy with errorhandling?!? */
+	tos[0] = tmp[0];
+	tos[1] = tmp[1];
+
+	return count;
+}
+
+static const struct file_operations dgfops = {
+	.read = dg_read_file,
+	.write = dg_write_file,
+};
+
+static int __init pr_module_init(void)
+{
+	bool ret = register_qdisc(&pr_qdisc_ops);
+	if (!ret) {
+		/* open Communication channel */
+		dgdir = debugfs_create_dir("sch_pr", NULL);
+		dgfile = debugfs_create_file("tos", 0644, dgdir, tos, &dgfops);
+	}
+	return ret;
+}
+
+static void __exit pr_module_exit(void)
+{
+	debugfs_remove(dgfile);
+	debugfs_remove(dgdir);
+	unregister_qdisc(&pr_qdisc_ops);
+}
+
+module_init(pr_module_init);
+module_exit(pr_module_exit);
+MODULE_LICENSE("GPL");

-- 
1.7.7