[LARTC] Hashing filters

[LARTC] Hashing filters

[Matias Bjørling]

Hey

A wise man said to me that Hashing filters was my solution to rock the
world, and making my life alot easier. When applying 4000 rules, the system
had to check them all for match. But with hassing it would only require 1-2
checks.

Even though when i had read the lartc on the subject i was no less that a
question mark.

If anyone have played with it, and have a working, logic configuration and
can tell me how it works and why i would be greatly grateful.

Regards

Matias Bjørling

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] Hashing filters

[Gideon le Grange]

I have set this up using the information in
http://lartc.org/howto/lartc.adv-filter.hashing.html and it works
perfectly.How you design your rules depends on how you want to filter,
so it is a bit difficult to supply you with a better example. Do you
wish to filter per IP address? If so, I can help you:

# add htb as root queueing discipline for device. This is done once
tc qdisc add dev eth0 root handle 1: htb

# add a class with a 100Mbit rate. This is a 'transit' class, it does
# not do any shaping, you will see down below why we need it.
tc class add dev eth0 parent 1: classid 1:2 htb  rate 100MBit ceil
100MBit burst 0Kbit

# I create a hash table with 256 slots, call it 2: and attach it to 1:2 
# which is my 'transit' class above 
tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
# Classify packets matching 192.168.4.0/24 using the last byte of the 
# IP address as index into the hash
tc filter add dev eth0 protocol ip parent 1: u32 match ip src
192.168.4.0/24 hashkey mask 0x000000ff at 12 link 2:

# The bit below happens for each distinct traffic class. Multiple IP 
# addresses can map into the same end class, but you can have one class
# per IP address. In the example, 192.168.4.100 gets sent to a class 
# that shapes it down to 64Kbit. The class has it's own htb qdisc, but
# The experts may know better here

# add class for network 192.168.4.100/32
tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 64Kbit ceil
64Kbit burst 0Kbit

# Filters to allocate packets for 192.168.4.100/32
# Now this is the trickier bit. I only map one IP into class 1:3, and 
# here is where. I attach a filter to hash table 2 slot 0x64 to map to
# class 1:3. NOTE: 64 is hex, means 100 decimal which matches IP .100
tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:64: match ip src
192.168.4.100 flowid 1:3

# you can repeat the last statement 254 times for the different IPs in 
# the class C. Example: IP 1
tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:1 match ip src 
192.168.4.1 flowid 1:3 

This is not perfect, and the average number of evaluations is n/2 + 1
where n is the number of class C networks. So on 4000 addresses you are
looking at 16/2 + 1 = approx 9 evaluations vs n/2 = 2000 on your current
setup (4000 = 16 class C)

Gideon 



On Wed, 2003-05-14 at 01:17, Matias Bjørling wrote:
> Hey
> 
> A wise man said to me that Hashing filters was my solution to rock the
> world, and making my life alot easier. When applying 4000 rules, the system
> had to check them all for match. But with hassing it would only require 1-2
> checks.
> 
> Even though when i had read the lartc on the subject i was no less that a
> question mark.
> 
> If anyone have played with it, and have a working, logic configuration and
> can tell me how it works and why i would be greatly grateful.
> 
> Regards
> 
> Matias Bjørling

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] Hashing filters

[Matias Bjørling]

Hey :) I have a few questions if you have a min :)

----- Original Message ----- 
From: "Gideon le Grange" <gideon@adept.co.za>
To: "Matias Bjørling" <mb@nerdit.dk>
Cc: <lartc@mailman.ds9a.nl>
Sent: Wednesday, May 14, 2003 8:05 AM
Subject: Re: [LARTC] Hashing filters


I have set this up using the information in
http://lartc.org/howto/lartc.adv-filter.hashing.html and it works
perfectly.How you design your rules depends on how you want to filter,
so it is a bit difficult to supply you with a better example. Do you
wish to filter per IP address? If so, I can help you:

# add htb as root queueing discipline for device. This is done once
tc qdisc add dev eth0 root handle 1: htb

# add a class with a 100Mbit rate. This is a 'transit' class, it does
# not do any shaping, you will see down below why we need it.
tc class add dev eth0 parent 1: classid 1:2 htb  rate 100MBit ceil
100MBit burst 0Kbit

# I create a hash table with 256 slots, call it 2: and attach it to 1:2
# which is my 'transit' class above
tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
# Classify packets matching 192.168.4.0/24 using the last byte of the
# IP address as index into the hash
tc filter add dev eth0 protocol ip parent 1: u32 match ip src
192.168.4.0/24 hashkey mask 0x000000ff at 12 link 2:

        Do i need to specify one for every subnet im going to do?
        Like 10.0.1.0, 10.0.2.0 and so on ? :)

# The bit below happens for each distinct traffic class. Multiple IP
# addresses can map into the same end class, but you can have one class
# per IP address. In the example, 192.168.4.100 gets sent to a class
# that shapes it down to 64Kbit. The class has it's own htb qdisc, but
# The experts may know better here

# add class for network 192.168.4.100/32
tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 64Kbit ceil
64Kbit burst 0Kbit

        Do i need to add a class for every host on one of the subnets?

# Filters to allocate packets for 192.168.4.100/32
# Now this is the trickier bit. I only map one IP into class 1:3, and
# here is where. I attach a filter to hash table 2 slot 0x64 to map to
# class 1:3. NOTE: 64 is hex, means 100 decimal which matches IP .100
tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:64: match ip src
192.168.4.100 flowid 1:3

        When i have made 254 lines of thoes, then every "host" have 64kbit
each they can use until the         root bandwidth have been used?, am i
right?

        Why is it then that i only need one class of 192.168.4.100?, and not
for all the other hosts?

This is not perfect, and the average number of evaluations is n/2 + 1
where n is the number of class C networks. So on 4000 addresses you are
looking at 16/2 + 1 = approx 9 evaluations vs n/2 = 2000 on your current
setup (4000 = 16 class C)

Gideon

        Thank you for your time :)

On Wed, 2003-05-14 at 01:17, Matias Bjørling wrote:
> Hey
>
> A wise man said to me that Hashing filters was my solution to rock the
> world, and making my life alot easier. When applying 4000 rules, the
system
> had to check them all for match. But with hassing it would only require
1-2
> checks.
>
> Even though when i had read the lartc on the subject i was no less that a
> question mark.
>
> If anyone have played with it, and have a working, logic configuration and
> can tell me how it works and why i would be greatly grateful.
>
> Regards
>
> Matias Bjørling

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

[LARTC] Hashing Filters

[Matias Bjørling]

[-- Attachment #1: Type: text/plain, Size: 1882 bytes --]

Hey

Can anybody tell me what i'm doing wrong, im getting crasy of this hashing filters, and the doc at lartc is too unexplained for me. Can't get it to work

# tc qdisc del dev eth0 root > /dev/null
# tc qdisc add dev eth0 root handle 1: htb
# tc class add dev eth0 parent 1: classid 1:2 htb rate 100MBit ceil 100MBit

# tc filter add dev eth0 parent 1:2 prio 5 protocol ip u32
# tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256

// Adding a divisor 

# tc class add dev eth0 parent 1:2 classid 1:10 htb rate 512kbit ceil 512kbit burst 0k
# tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:1: match ip src 10.0.0.1 flowid 1:10

# tc class add dev eth0 parent 1:2 classid 1:11 htb rate 512kbit ceil 512kbit burst 0k
# tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:2: match ip src 10.0.0.2 flowid 1:11

# tc class add dev eth0 parent 1:2 classid 1:13 htb rate 512kbit ceil 512kbit burst 0k
# tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:4: match ip src 10.0.0.4 flowid 1:13

# tc class add dev eth0 parent 1:2 classid 1:15 htb rate 512kbit ceil 512kbit burst 0k
# tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:6: match ip src 10.0.0.6 flowid 1:15

// Making Hashing Filtering for Network 10.0.0.0/16
# tc filter add dev eth0 protocol ip parent 1:2 prio 5 u32 ht 800:: match ip src 10.0.0.0/16 hashkey mask 0x000000ff at 12 link 2:

I know i have to set 
# tc filter add dev eth1 parent 1: protocol ip prio 100 match ip src 10.0.02 classid 1:2
between the class and filter where i point to the src ip. But it wont accept the config. telling me that 

Unknown filter "match", hence option "ip" is unparsable

It's breaking my neck soon am i'm going crazy :)

If any have a working script with more than 256 hosts, i would greatly appreciate it :)

Thank You

Regards 

Matias Bjørling

[-- Attachment #2: Type: text/html, Size: 2825 bytes --]

[LARTC] hashing filters

[Valton Hashani]

[-- Attachment #1: Type: text/plain, Size: 1306 bytes --]

Hi all,
I am a newbie and I have not played a lot with tc utility. I have red maybe everything that has to do with massive filtering (maybe not everything). If you can help me on this I would appriciate that very much. I use tc utility with  iproute2-ss040831. 
I want to limit bandwidth for  the  192.168.0.0/16 subnet using this script.


tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb
tc class add dev eth0 parent 1: classid 1:2 htb  rate 100Mbit ceil 100MBit 
tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
tc filter add dev eth0 protocol ip parent 1: u32 match ip dst 192.168.0.0/16 hashkey mask 0x000000ff at 12 link 2:
tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 128Kbit ceil 128Kbit

j=0;

while [ $j -le 254 ]

do
       i=0;

        while [ $i -le 254 ]
        do
                hexi=`echo "obase=16; $i" | bc`
                tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match ip dst 192.168.$j.$i flowid 1:3
                i=$((i+1))
      done

j=$((j+1))
done
  
somewhere at 192.168.8.7/32 it appears on the screen this message 

RTNETLINK answers: File exists
We have an error talking to the kernel

Can you tell me please what am I doing wrong.

Thank you in advance 
Valton

[-- Attachment #2: Type: text/html, Size: 3114 bytes --]

Re: [LARTC] hashing filters

[Tomasz Paszkowski]

[-- Attachment #1: Type: text/plain, Size: 1708 bytes --]

On Wed, Jan 12, 2005 at 01:27:18PM +0100, Valton Hashani wrote:
> Hi all,
> I am a newbie and I have not played a lot with tc utility. I have red maybe everything that has to do with massive filtering (maybe not everything). If you can help me on this I would appriciate that very much. I use tc utility with  iproute2-ss040831. 
> I want to limit bandwidth for  the  192.168.0.0/16 subnet using this script.
> 
> 
> tc qdisc del dev eth0 root
> tc qdisc add dev eth0 root handle 1: htb
> tc class add dev eth0 parent 1: classid 1:2 htb  rate 100Mbit ceil 100MBit 
> tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
> tc filter add dev eth0 protocol ip parent 1: u32 match ip dst 192.168.0.0/16 hashkey mask 0x000000ff at 12 link 2:
change to:
tc filter add dev eth0 protocol ip parent 1: u32 match ip dst 192.168.0.0/24 hashkey mask 0x000000ff at 16 link 2:
> tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 128Kbit ceil 128Kbit
> 
> j=0;
> 
> while [ $j -le 254 ]
> 
> do
>        i=0;
> 
>         while [ $i -le 254 ]
>         do
>                 hexi=`echo "obase=16; $i" | bc`
add hiere:
		echo tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match ip dst 192.168.$j.$i flowid 1:3

and show us results.
>                 tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match ip dst 192.168.$j.$i flowid 1:3
>                 i=$((i+1))
>       done
> 
> j=$((j+1))
> done
>   
> somewhere at 192.168.8.7/32 it appears on the screen this message 
> 
> RTNETLINK answers: File exists
> We have an error talking to the kernel
> 
> Can you tell me please what am I doing wrong.

-- 
Tomasz Paszkowski

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [LARTC] hashing filters

[Valton Hashani]

Hi,

with a Tomasz suggestions I tried with the setup below but it appears at the
same place, the same error.

RTNETLINK answers: File exists
We have an error talking to the kernel

Is there any other way?

Regards,
Valton

-------------------------
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb
tc class add dev eth0 parent 1: classid 1:2 htb  rate 100Mbit ceil 100MBit
tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
#tc filter add dev eth0 protocol ip parent 1: u32 match ip dst
192.168.0.0/16 hashkey mask 0x000000ff at 12 link 2:
tc filter add dev eth0 protocol ip parent 1: u32 match ip dst 192.168.0.0/24
hashkey mask 0x000000ff at 16 link 2:
tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 128Kbit ceil 128Kbit

j=0;

while [ $j -le 254 ]

do
         i=0;

              while [ $i -le 254 ]
         do
         hexi=`echo "obase\x16; $i" | bc`
         echo tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi:
match ip dst 192.168.$j.$i flowid 1:3
         tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match
ip dst 192.168.$j.$i flowid 1:3
        i=$((i+1))
         done

j=$((j+1))
done

----- Original Message ----- 
From: "Tomasz Paszkowski" <tomasz.paszkowski@e-wro.pl>
To: "Valton Hashani" <valton@ipko.net>
Cc: <lartc@mailman.ds9a.nl>
Sent: Wednesday, January 12, 2005 2:11 PM
Subject: Re: [LARTC] hashing filters

On Wed, Jan 12, 2005 at 01:27:18PM +0100, Valton Hashani wrote:
> Hi all,
> I am a newbie and I have not played a lot with tc utility. I have red
maybe everything that has to do with massive filtering (maybe not
everything). If you can help me on this I would appriciate that very much. I
use tc utility with  iproute2-ss040831.
> I want to limit bandwidth for  the  192.168.0.0/16 subnet using this
script.
>
>
> tc qdisc del dev eth0 root
> tc qdisc add dev eth0 root handle 1: htb
> tc class add dev eth0 parent 1: classid 1:2 htb  rate 100Mbit ceil 100MBit
> tc filter add dev eth0 parent 1:2 handle 2: protocol ip u32 divisor 256
> tc filter add dev eth0 protocol ip parent 1: u32 match ip dst
192.168.0.0/16 hashkey mask 0x000000ff at 12 link 2:
change to:
tc filter add dev eth0 protocol ip parent 1: u32 match ip dst 192.168.0.0/24
hashkey mask 0x000000ff at 16 link 2:
> tc class add dev eth0 parent 1:2 classid 1:3 htb  rate 128Kbit ceil
128Kbit
>
> j=0;
>
> while [ $j -le 254 ]
>
> do
>        i=0;
>
>         while [ $i -le 254 ]
>         do
>                 hexi=`echo "obase\x16; $i" | bc`
add hiere:
  echo tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match
ip dst 192.168.$j.$i flowid 1:3

and show us results.
>                 tc filter add dev eth0 protocol ip parent 1:2 u32 ht
2:$hexi: match ip dst 192.168.$j.$i flowid 1:3
>                 i=$((i+1))
>       done
>
> j=$((j+1))
> done
>
> somewhere at 192.168.8.7/32 it appears on the screen this message
>
> RTNETLINK answers: File exists
> We have an error talking to the kernel
>
> Can you tell me please what am I doing wrong.

-- 
Tomasz Paszkowski

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] hashing filters

[Tomasz Paszkowski]

[-- Attachment #1: Type: text/plain, Size: 441 bytes --]

On Wed, Jan 12, 2005 at 07:08:03PM +0100, Valton Hashani wrote:

change te script to:
i=0;
while [ $i -le 254 ]
do
	hexi=`echo "obase=16; $i" | bc`
	tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi: match ip dst 192.168.$j.$i flowid 1:3
	i=$((i+1))
done

connected with modifications from previous mail it should work.

-- 
Tomasz Paszkowski
Administrator
Miejskie Sieci Informatyczne e-wro
http://www.e-wro.pl

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [LARTC] hashing filters

[Tomasz Paszkowski]

[-- Attachment #1: Type: text/plain, Size: 531 bytes --]

On Wed, Jan 12, 2005 at 07:08:03PM +0100, Valton Hashani wrote:
> j=0;
> 
> while [ $j -le 254 ]
> 
> do
>          i=0;
> 
>               while [ $i -le 254 ]
>          do
>          hexi=`echo "obase=16; $i" | bc`
>          echo tc filter add dev eth0 protocol ip parent 1:2 u32 ht 2:$hexi:
> match ip dst 192.168.$j.$i flowid 1:3
>          tc filter add dev eth0 protocol ip parent 1:2 u32 ht $j:$hexi match
> ip dst 192.168.$j.$i flowid 1:3
>         i=$((i+1))
>          done
> 
> j=$((j+1))
> done


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]