[Click] Problem with Queue element

Sun Apr 2 14:40:30 EDT 2006

Hi,

I have created my own version of the SimpleQueue element. Instead of
dropping the incoming packet when the queue is full I would like my queue
to drop a packet depending on its "Type of Service" value which is
specified in the IP Header. I have created an element that sets this header
field with a value between 0-255. Basically my queue element when full
should compare the TOS value of all the packets in the queue to find the
one with the lowest value. If this is lower than the incoming packet it
should drop this packet if not drop the incoming packet. I am using a
circular queue so when a packet is dropped that is in the queue I need to
shift the queue packet pointer foward for all the postions behind the
dropped packet in the queue so the original ordering of the queue is
maintained and so the next incoming packet is the tail of the queue. Below
is the configuration I am using to test this element.

require(sample);

q1 :: TOSQueue(6)

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(255)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(60)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(128)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(10)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(92)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(150)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(192)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(200)
        ->q1

InfiniteSource(DATA \<00 00 c0 ae 67 ef  00 00 00 00 00
00  08 00 45 00 00 28  00 00 00 00  40 11 77 c3  01 00 00 01
02 00 00 02  13 69 13 69  00 14 d6 41  55 44 50 20
70 61 63 6b  65 74 21 0a>, LIMIT 1, STOP true)
        ->Strip(14)
        ->CheckIPHeader()
        ->SetTOS(100)
        ->q1

q1->IanPrint->Discard;

However when I run this using my own adaption of the print element I get the
following results. The 3 packets with the lowest TOS are correctly dropped.
However when moving the packets along to fill in the gap in the queue it
does this correctly until the point where it moves the tail forward to the
position infront, after this it seems to make duplicate copies of the
packet with TOS value 150. It seems the tail always becomes a duplicate of
the packet in the postion in front.

q1 :: TOSQueue: overflow

Source Address = 16777217
Destination Address = 33554434
Type of Service = 255
Source Address = 16777217
Destination Address = 33554434
Type of Service = 128
Source Address = 16777217
Destination Address = 33554434
Type of Service = 150
Source Address = 16777217
Destination Address = 33554434
Type of Service = 150
Source Address = 16777217
Destination Address = 33554434
Type of Service = 150
Source Address = 16777217
Destination Address = 33554434
Type of Service = 150

I cannot understand why this is happening. Please find below the push part
of the queue element I am using.

void
TOSQueue::push(int, Packet *p)
{
    const click_ip *ip = p->ip_header();
    int tos_min = 256;
    int packet_drop = -1;
    int tos_val = 0;

    if (next != _head) {
        _q[_tail] = p;
        _tail = next;

        int s = size();
        if (s > _highwater_length)
            _highwater_length = s;

    } else {
        if (_drops == 0)
            click_chatter("%{element}: overflow", this);
            _drops++;

            for (int i = _head; i != _tail; i = next_i(i)){
                const click_ip *iph = _q[i]->ip_header();
                tos_val = (int)iph->ip_tos;
                        if (tos_val <= tos_min){
                                tos_min = (int)iph->ip_tos;
                                 packet_drop = i;
                          }
                 }
             if ((int)ip->ip_tos <= tos_min){
                p->kill();
                 }
             else {
                _q[packet_drop]->kill();
                for (int i = packet_drop; next_i(i) != _tail; i =
next_i(i)){
                        _q[i] = _q[next_i(i)];
                }
                _q[_tail] = p;
             }
    }
}

Can anyone see why this problem is occuring????

Any help or advice would be greatly appreciated.

Thanks