Skip to contentSkip to conversation

Filter huge number of hosts

LARTC Peter Nelson 2 participants 4 messages Nov 11, 2003

lore
Share & tools
lore
#0 lore raw

Ok, I'm pretty new at this and am probably in a bit over my head, but I was looking for some pointers. I want to classify and then prioritize traffic based on if it is to an Internet2 host, a host on campus or the general internet. I got a dump from one of our campus's routers that classifies everything as either I2 or local, only problem is that it is ~8000 entries. Now a lot of those entries can probably be combined down (for example a couple of sequential /24's). My first question is does anyone have any script that you give it multiple netmasks and it combines it down to the simplest netmasks? Now my second question is would using hashtables, maybe even nested ones be practical for this? This is how I'm thinking of hashing so far:

Mask hashes children to check

0xFF000000:   100           most 50-500
0xFFFF0000:   3000         most <20, some 50-200
0xFFFFFF00:   8000         all < 10

Obviously hashing based on 0xFF helps, but it still has to go through up to 500 checks for somes hosts. Once I hash based on 0xFFFF the worst case gets a lot better, and of course hashing on 0xFFFFFF makes almost perfect hashes. Only thing is does a hash table lose it's point once you start indexing everything? I was thinking maybe hashing based on the 0xFF and then from there making hashes based on 0x00FF (and then maybe an other layer of 0x0000FF). I admit I really don't know all that much about the hashing algorighm and it's complexity so I don't know how to approach this.

Thanks for any information,
Peter Nelson
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#1 lore raw

Ok, I'm pretty new at this and am probably in a bit over my head, but I was looking for some pointers. I want to classify and then prioritize traffic based on if it is to an Internet2 host, a host on campus or the general internet. I got a dump from one of our campus's routers that classifies everything as either I2 or local, only problem is that it is ~8000 entries. Now a lot of those entries can probably be combined down (for example a couple of sequential /24's). My first question is does anyone have any script that you give it multiple netmasks and it combines it down to the simplest netmasks? Now my second question is would using hashtables, maybe even nested ones be practical for this? This is how I'm thinking of hashing so far:

Mask hashes children to check

0xFF000000:   100           most 50-500
0xFFFF0000:   3000         most <20, some 50-200
0xFFFFFF00:   8000         all < 10

Obviously hashing based on 0xFF helps, but it still has to go through up to 500 checks for somes hosts. Once I hash based on 0xFFFF the worst case gets a lot better, and of course hashing on 0xFFFFFF makes almost perfect hashes. Only thing is does a hash table lose it's point once you start indexing everything? I was thinking maybe hashing based on the 0xFF and then from there making hashes based on 0x00FF (and then maybe an other layer of 0x0000FF). I admit I really don't know all that much about the hashing algorighm and it's complexity so I don't know how to approach this.

Thanks for any information,
Peter Nelson
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#2 lore raw
In reply to Peter Nelson

Ok, I'm pretty new at this and am probably in a bit over my head, but I was looking for some pointers. I want to classify and then prioritize traffic based on if it is to an Internet2 host, a host on campus or the general internet. I got a dump from one of our campus's routers that classifies everything as either I2 or local, only problem is that it is ~8000 entries. Now a lot of those entries can probably be combined down (for example a couple of sequential /24's). My first question is does anyone have any script that you give it multiple netmasks and it combines it down to the simplest netmasks? Now my second question is would using hashtables, maybe even nested ones be practical for this? This is how I'm thinking of hashing so far:

Mask hashes children to check

0xFF000000:   100           most 50-500
0xFFFF0000:   3000         most <20, some 50-200
0xFFFFFF00:   8000         all < 10

Obviously hashing based on 0xFF helps, but it still has to go through up to 500 checks for somes hosts. Once I hash based on 0xFFFF the worst case gets a lot better, and of course hashing on 0xFFFFFF makes almost perfect hashes. Only thing is does a hash table lose it's point once you start indexing everything? I was thinking maybe hashing based on the 0xFF and then from there making hashes based on 0x00FF (and then maybe an other layer of 0x0000FF). I admit I really don't know all that much about the hashing algorighm and it's complexity so I don't know how to approach this.

Thanks for any information,
Peter Nelson
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#3 lore raw
In reply to Peter Nelson
Quoted 12 lines · Peter Nelson

Ok, I'm pretty new at this and am probably in a bit over my head, but I was looking for some pointers. I want to classify and then prioritize traffic based on if it is to an Internet2 host, a host on campus or the general internet. I got a dump from one of our campus's routers that classifies everything as either I2 or local, only problem is that it is ~8000 entries. Now a lot of those entries can probably be combined down (for example a couple of sequential /24's). My first question is does anyone have any script that you give it multiple netmasks and it combines it down to the simplest netmasks? Now my second question is would using hashtables, maybe even nested ones be practical for this? This is how I'm thinking of hashing so far:

Quoted 5 lines

Mask hashes children to check

0xFF000000:   100           most 50-500
0xFFFF0000:   3000         most <20, some 50-200
0xFFFFFF00:   8000         all < 10

You can link hashes to do what you want:
hash (made from first byte of the ip):

	01 -> another_hash_1
	10 -> another_hash_2

another_hash_1 entries (hash made from second byte):

	01 -> another_hash_on_level_2
	10 -> another_hash_on_level_2

and so on.

Quoted 10 lines

Obviously hashing based on 0xFF helps, but it still has to go through up to 500 checks for somes hosts. Once I hash based on 0xFFFF the worst case gets a lot better, and of course hashing on 0xFFFFFF makes almost perfect hashes. Only thing is does a hash table lose it's point once you start indexing everything? I was thinking maybe hashing based on the 0xFF and then from there making hashes based on 0x00FF (and then maybe an other layer of 0x0000FF). I admit I really don't know all that much about the hashing algorighm and it's complexity so I don't know how to approach this.

Quoted 6 lines

Thanks for any information,
Peter Nelson
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

---
Catalin(ux) BOIE
[email protected]
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/