Hello List, I have a little non-standard problem (or so I guess). I''m getting a sponsored server on a backbone for almost nothing - which is quite nice. However there is a string attached: Since the bandwith to foreign countries is expensive, while in-land bandwith is almost free, I need to shape down access to all "foreign" IPs. Now I have a (large) list of routes/prefixes for destinations which are ok - a whitelist if you want. The question I have now is, how do I best proceed in using that list so that the kernel does not spend too much time looking it up for every single packet. Is the routing table hashed by default so access is fast and I can just pump in the ~100KBytes of ip prefixes ? Or does it traverse them linearly and I need to build a hierarchical structure so that it will be fast ? (sort of like in section 12.4 of the LARTC howto with the filters?) I''ve also toyed with the idea of doing it in netfilter since I know netfilter quite a lot better than tc and ip but it is mostly outgoing traffic that is a problem and I sort of feel that this is better done by the routing/filtering infrastructure than by the firewall. Any advice? Thanks in advance René _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
On Wed, 31 Mar 2004, Roy wrote:> 100kbytes of prefixes is not so good , hashing does not mean anything > faster when checking ip you will need to test 4 bytes in any way, since > hash is usualy 32 bit too. this can help on very complex rules only. so > if you pump 100 kbytes of prefixes this is probably 7000 addreses so on > each packet 7000 tests will be done.Incorrect. Linux route lookup is crappy, but not THAT crappy. Route-cache somewhat helps too. -alex _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
On Wed, 31 Mar 2004, Roy wrote:> I know that routes can be cached what should help, but here we are > talking about tc u32 filter, which can not be cached as I know without > hierarchy it is not posible to decrease amount of testing > > but the interesting idea is to use route for packet classification > or it can be simulated with netfilters connmark module. > then amount of test to be done will be more than half of active connections > number.Sorry - my bad, I thought that the poster *was* talking about using route (and realm) for packet classification and tc based on realm. -alex _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
100kbytes of prefixes is not so good , hashing does not mean anything faster when checking ip you will need to test 4 bytes in any way, since hash is usualy 32 bit too. this can help on very complex rules only. so if you pump 100 kbytes of prefixes this is probably 7000 addreses so on each packet 7000 tests will be done. everything mostly depends on how much trafic you need to pass. probably hierarchical structure is the best option. you can use multiple servers to mark packets and one to shape trafic ( you sould use TOS not mark) ----- Original Message ----- From: "Rene Gallati" <lartc@draxinusom.ch> To: <lartc@mailman.ds9a.nl> Sent: Wednesday, March 31, 2004 1:56 AM Subject: [LARTC] large routing table> Hello List, > > I have a little non-standard problem (or so I guess). I''m getting a > sponsored server on a backbone for almost nothing - which is quite nice. > However there is a string attached: Since the bandwith to foreign > countries is expensive, while in-land bandwith is almost free, I need to > shape down access to all ''"''foreign''"'' IPs. > > Now I have a (large) list of routes/prefixes for destinations which are > ok - a whitelist if you want. The question I have now is, how do I best > proceed in using that list so that the kernel does not spend too much > time looking it up for every single packet. > > Is the routing table hashed by default so access is fast and I can just > pump in the ~100KBytes of ip prefixes ? Or does it traverse them > linearly and I need to build a hierarchical structure so that it will be > fast ? (sort of like in section 12.4 of the LARTC howto with the filters?) > > I''ve also toyed with the idea of doing it in netfilter since I know > netfilter quite a lot better than tc and ip but it is mostly outgoing > traffic that is a problem and I sort of feel that this is better done by > the routing/filtering infrastructure than by the firewall. > > Any advice? > > Thanks in advance > > René > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
I know that routes can be cached what should help, but here we are talking about tc u32 filter, which can not be cached as I know without hierarchy it is not posible to decrease amount of testing but the interesting idea is to use route for packet classification or it can be simulated with netfilters connmark module. then amount of test to be done will be more than half of active connections number. ----- Original Message ----- From: <alex@pilosoft.com> To: "Roy" <roy@xxx.lt> Cc: <lartc@mailman.ds9a.nl> Sent: Wednesday, March 31, 2004 4:06 AM Subject: Re: [LARTC] large routing table> On Wed, 31 Mar 2004, Roy wrote: > > > 100kbytes of prefixes is not so good , hashing does not mean > anything > > faster when checking ip you will need to test 4 bytes in any > way, since > > hash is usualy 32 bit too. this can help on very complex rules > only. so > > if you pump 100 kbytes of prefixes this is probably 7000 > addreses so on > > each packet 7000 tests will be done. > Incorrect. Linux route lookup is crappy, but not THAT crappy. > Route-cache somewhat helps too. > > -alex >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hi, this is exactly why ip addresses are already grouped with respect to location. So it should be possible to optimize things, maybe use some perl with http://search.cpan.org/~nwetters/IP-Country-2.15/lib/IP/Country.pm e.g. 194.0.0.0/8 is NL And I guess you can afford to make some errors, e.g. shaping a destination which shouldn''t be shaped is not a crime if it wouldn''t happen too often, just make sure you shape foreign IP''s, how bad would it be to shape some non-foreign IP''s accidently? And, ofcourse, either "foreign IP''s" or "non foreign IP''s" is the smallest list, use the samllest list. Good luck, Jeroen. On Wed, 31 Mar 2004 00:56:52 +0200 Rene Gallati <lartc@draxinusom.ch> wrote:> Hello List, > > I have a little non-standard problem (or so I guess). I''m getting a > sponsored server on a backbone for almost nothing - which is quite nice. > However there is a string attached: Since the bandwith to foreign > countries is expensive, while in-land bandwith is almost free, I need to > shape down access to all "foreign" IPs. > > Now I have a (large) list of routes/prefixes for destinations which are > ok - a whitelist if you want. The question I have now is, how do I best > proceed in using that list so that the kernel does not spend too much > time looking it up for every single packet. > > Is the routing table hashed by default so access is fast and I can just > pump in the ~100KBytes of ip prefixes ? Or does it traverse them > linearly and I need to build a hierarchical structure so that it will be > fast ? (sort of like in section 12.4 of the LARTC howto with the filters?) > > I''ve also toyed with the idea of doing it in netfilter since I know > netfilter quite a lot better than tc and ip but it is mostly outgoing > traffic that is a problem and I sort of feel that this is better done by > the routing/filtering infrastructure than by the firewall. > > Any advice? > > Thanks in advance > > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Another idea: by default shape everything, but allow it to burst a bit (if that''s not a problem). make MARK X not shaped. MARK X some big networks which will always be Switserland. Then make a script (using the perl module I metioned previously) to check whether a new connection should be shaped or not, if it should not be shaped, and if it''s not part of the marked IP''s already, you add an entry to the MARK X list the /24 network where the IP address is in. (I think you can safely say that a /24 network is in one country). After one of these "temporary" marks is inactive for a while, remove it from the MARK X list, increase the "time to stay" for networks which are used often. So, your server apps should trigger a script (in the background) upon every new connection (maybe some tcpwrappers can do that, maybe you have to modify a tcpwrapper). make sure to update the database used by the scripts, Geo::IP has a "premium database subscription" update thingy. Good luck, you can mail me if you need some help, Jeroen. On Wed, 31 Mar 2004 00:56:52 +0200 Rene Gallati <lartc@draxinusom.ch> wrote:> Hello List, > > I have a little non-standard problem (or so I guess). I''m getting a > sponsored server on a backbone for almost nothing - which is quite nice. > However there is a string attached: Since the bandwith to foreign > countries is expensive, while in-land bandwith is almost free, I need to > shape down access to all "foreign" IPs. > > Now I have a (large) list of routes/prefixes for destinations which are > ok - a whitelist if you want. The question I have now is, how do I best > proceed in using that list so that the kernel does not spend too much > time looking it up for every single packet. > > Is the routing table hashed by default so access is fast and I can just > pump in the ~100KBytes of ip prefixes ? Or does it traverse them > linearly and I need to build a hierarchical structure so that it will be > fast ? (sort of like in section 12.4 of the LARTC howto with the filters?) > > I''ve also toyed with the idea of doing it in netfilter since I know > netfilter quite a lot better than tc and ip but it is mostly outgoing > traffic that is a problem and I sort of feel that this is better done by > the routing/filtering infrastructure than by the firewall. > > Any advice? > > Thanks in advance > > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hello, > this is exactly why ip addresses are already grouped with respect to location. > > So it should be possible to optimize things, maybe use some perl with http://search.cpan.org/~nwetters/IP-Country-2.15/lib/IP/Country.pm > e.g. 194.0.0.0/8 is NL Nope its not, I have 919 prefixes starting with 194 which are located in Switzerland. And they really are, for example picking one out randomly: nslookup 194.242.34.1 yields: Name: switch.swissix.ch Address: 194.242.34.1 whois: inetnum: 194.242.34.0 - 194.242.34.255 netname: SWISSIX descr: swissix, Swiss Internet Exchange country: CH admin-c: MC322-RIPE tech-c: MC322-RIPE status: ASSIGNED PI notify: noc@sissix.ch mnt-by: RIPE-NCC-HM-PI-MNT mnt-by: SWISSIX-MNT mnt-lower: RIPE-NCC-HM-PI-MNT To the best of my knowledge, region based IP-ranges are in IPv6 but not in IPv4. > And I guess you can afford to make some errors, e.g. shaping a destination which shouldn''t be shaped is not a crime if it wouldn''t happen too often, just make sure you shape foreign IP''s, how bad would it be to shape some non-foreign IP''s accidently? Problem is the server runs several applications and mine is but one of it. I am to make as little trouble as possible. However I do have a very good list of which IP ranges are ok and the complement are those that are not. My list comes directly from a skript that pulls it out of the core router. Some of the prefixes can be aggregated but that is a minor optimization. > And, ofcourse, either "foreign IP''s" or "non foreign IP''s" is the smallest list, use the samllest list. I have only the non-foreign list, but I am very sure that this one is smaller than the rest of the internet Its exactly 6486 prefixes atm. (without aggregating those that are possible). In any case too many to process linearly. CU René _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hello,> by default shape everything, but allow it to burst a bit (if that''s not a problem).Yeah, however my traffic won''t really be too large. I expect max bandwidth usage of about 1mbps to 2mbps max. I just need to make sure that stays in the country, because if such bandwidth usage crosses boundaries, its going to create costs that are unbearable.> make MARK X not shaped. > > MARK X some big networks which will always be Switserland. > > Then make a script (using the perl module I metioned previously) to check whether a new connection should be shaped or not, if it should not be shaped, and if it''s not part of the marked IP''s already, you add an entry to the MARK X list the /24 network where the IP address is in. (I think you can safely say that a /24 network is in one country).The problem is that the geo-skript is wrong - and I already have a "perfect" list, so I rather use this, especially because that list is provided by the people who own the machine/network, so when in doubt I can always claim that I did my best to prevent undesired leakage. As for the minimum size, I too think this is a safe assumption, though I need to check. I already wrote a skript that breaks the list up into different buckets according to the first byte. I just added a little check to see what the largest and smallest prefixes are: This is the output (number of different prefixes sorted per first byte): smallest prefix = 24, largest = 11 total 6486 15 = 7 16 = 4 32 = 15 40 = 7 44 = 1 53 = 3 57 = 1 60 = 1 62 = 312 63 = 4 64 = 5 66 = 14 69 = 5 80 = 249 81 = 221 82 = 153 83 = 49 128 = 15 129 = 16 130 = 23 131 = 27 132 = 2 134 = 11 135 = 1 136 = 5 137 = 9 138 = 16 139 = 18 140 = 4 141 = 20 143 = 9 144 = 13 145 = 23 146 = 27 147 = 19 148 = 13 149 = 21 150 = 2 151 = 5 152 = 6 153 = 13 154 = 6 155 = 24 156 = 10 157 = 6 158 = 10 159 = 23 160 = 20 161 = 9 162 = 7 163 = 9 164 = 21 166 = 1 167 = 1 168 = 7 170 = 7 171 = 5 192 = 532 193 = 1246 194 = 919 195 = 634 196 = 10 198 = 16 199 = 17 202 = 43 203 = 37 204 = 8 205 = 5 206 = 3 207 = 2 208 = 17 209 = 19 212 = 511 213 = 438 216 = 21 217 = 473 193.* is actually the one with most prefixes in it.> After one of these "temporary" marks is inactive for a while, remove it from the MARK X list, increase the "time to stay" for networks which are used often. > > So, your server apps should trigger a script (in the background) upon every new connection (maybe some tcpwrappers can do that, maybe you have to modify a tcpwrapper). > > make sure to update the database used by the scripts, Geo::IP has a "premium database subscription" update thingy.I just talked today with the owner about this and I think I''ll go another way. I might use netfilter''s connection tracker so that the lookup that decides which class to use is only done on connection setup and not per packet. Still, 6000 rules are too much so I''m going to create a hierarchical ruleset to minimize the worst case. I don''t want to have anything beyond 30 rules worst case checking or so because the server runs different applications and I should not make my presence negatively noticeable. I think that is the best approach in this situation. Thanks for all the advice! CU René _______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hello,> I know that routes can be cached what should help, but > here we are talking about tc u32 filter, which can not be cached as I know > without hierarchy it is not posible to decrease amount of testing > > but the interesting idea is to use route for packet classification > or it can be simulated with netfilters connmark module. > then amount of test to be done will be more than half of active connections > number.I think I will do exactly that. I was thinking somewhere along the lines that the routing infrastructure would be the best place to do it, but the connection tracker of netfilter is quite a bonus since it keeps state and so does minimize the times when I need to walk my classification tree to find out how to treat the connection. Also I don''t really need to route, since all the traffic goes out of the same interface anyway. Thanks for all the hints ! CU René> > ----- Original Message ----- > From: <alex@pilosoft.com> > To: "Roy" <roy@xxx.lt> > Cc: <lartc@mailman.ds9a.nl> > Sent: Wednesday, March 31, 2004 4:06 AM > Subject: Re: [LARTC] large routing table > > > >>On Wed, 31 Mar 2004, Roy wrote: >> >> >>>100kbytes of prefixes is not so good , hashing does not mean >> >>anything >> >>>faster when checking ip you will need to test 4 bytes in any >> >>way, since >> >>>hash is usualy 32 bit too. this can help on very complex rules >> >>only. so >> >>>if you pump 100 kbytes of prefixes this is probably 7000 >> >>addreses so on >> >>>each packet 7000 tests will be done. >> >>Incorrect. Linux route lookup is crappy, but not THAT crappy. >>Route-cache somewhat helps too. >> >>-alex >> > > > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hello,> 100kbytes of prefixes is not so good , hashing does not mean anything faster > when checking ip > you will need to test 4 bytes in any way, since hash is usualy 32 bit too. > this can help on very complex rules only.Yeah you''re right. Also, the hash cannot tell me if something "like" nnn.nnn.xxx.yyy is in table X because only exact matches are possible.> so if you pump 100 kbytes of prefixes this is probably 7000 addreses so on > each packet 7000 tests will be done.6486 to be exact. I don''t really want more than 30 tests or so.> everything mostly depends on how much trafic you need to pass.Not much, about 1-2mbps, maybe 4 to 5 peak. But the server does a lot of other things and I am not to use up all the ressources. Its a fast machine with lots of RAM but I still don''t pay for it and so I don''t want to create a lot of load.> probably hierarchical structure is the best option. > you can use multiple servers to mark packets and one to shape trafic ( you > sould use TOS not mark)I only have one at my disposition for this. However I think with the help of the netfilter connection tracker I''ll be able to minimize the problem to the connection setup phase. Now I just need to write a skript that generates the rules. If there is interest, I''ll copy it to the list once its working. Thanks for your hints René> > > > > ----- Original Message ----- > From: "Rene Gallati" <lartc@draxinusom.ch> > To: <lartc@mailman.ds9a.nl> > Sent: Wednesday, March 31, 2004 1:56 AM > Subject: [LARTC] large routing table > > > >>Hello List, >> >>I have a little non-standard problem (or so I guess). I''m getting a >>sponsored server on a backbone for almost nothing - which is quite nice. >>However there is a string attached: Since the bandwith to foreign >>countries is expensive, while in-land bandwith is almost free, I need to >>shape down access to all ''"''foreign''"'' IPs. >> >>Now I have a (large) list of routes/prefixes for destinations which are >>ok - a whitelist if you want. The question I have now is, how do I best >>proceed in using that list so that the kernel does not spend too much >>time looking it up for every single packet. >> >>Is the routing table hashed by default so access is fast and I can just >>pump in the ~100KBytes of ip prefixes ? Or does it traverse them >>linearly and I need to build a hierarchical structure so that it will be >>fast ? (sort of like in section 12.4 of the LARTC howto with the filters?) >> >>I''ve also toyed with the idea of doing it in netfilter since I know >>netfilter quite a lot better than tc and ip but it is mostly outgoing >>traffic that is a problem and I sort of feel that this is better done by >>the routing/filtering infrastructure than by the firewall. >> >>Any advice? >> >>Thanks in advance >> >>René >>_______________________________________________ >>LARTC mailing list / LARTC@mailman.ds9a.nl >>http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >> > > > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/ >_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Hi, You may wanna try this out (after adapting it a bit). It''s been written for the romanian iex in order to mark internal traffic. It uses BGP tables and is quite fast. If you have access to BGP routes then your task is to modify a script and add a cron job. The address is http://sourceforge.net/projects/mipclasses/. -- Adrian Vasile <adi@tettas.net> On Thu, 2004-04-01 at 00:19, Rene Gallati wrote:> Hello, > > > by default shape everything, but allow it to burst a bit (if that''s not a problem). > > Yeah, however my traffic won''t really be too large. I expect max > bandwidth usage of about 1mbps to 2mbps max. I just need to make sure > that stays in the country, because if such bandwidth usage crosses > boundaries, its going to create costs that are unbearable. > > > make MARK X not shaped. > > > > MARK X some big networks which will always be Switserland. > > > > Then make a script (using the perl module I metioned previously) to check whether a new connection should be shaped or not, if it should not be shaped, and if it''s not part of the marked IP''s already, you add an entry to the MARK X list the /24 network where the IP address is in. (I think you can safely say that a /24 network is in one country). > > The problem is that the geo-skript is wrong - and I already have a > "perfect" list, so I rather use this, especially because that list is > provided by the people who own the machine/network, so when in doubt I > can always claim that I did my best to prevent undesired leakage. > > As for the minimum size, I too think this is a safe assumption, though I > need to check. I already wrote a skript that breaks the list up into > different buckets according to the first byte. I just added a little > check to see what the largest and smallest prefixes are: > > This is the output (number of different prefixes sorted per first byte): > smallest prefix = 24, largest = 11 > total 6486 > 15 = 7 > 16 = 4 > 32 = 15 > 40 = 7 > 44 = 1 > 53 = 3 > 57 = 1 > 60 = 1 > 62 = 312 > 63 = 4 > 64 = 5 > 66 = 14 > 69 = 5 > 80 = 249 > 81 = 221 > 82 = 153 > 83 = 49 > 128 = 15 > 129 = 16 > 130 = 23 > 131 = 27 > 132 = 2 > 134 = 11 > 135 = 1 > 136 = 5 > 137 = 9 > 138 = 16 > 139 = 18 > 140 = 4 > 141 = 20 > 143 = 9 > 144 = 13 > 145 = 23 > 146 = 27 > 147 = 19 > 148 = 13 > 149 = 21 > 150 = 2 > 151 = 5 > 152 = 6 > 153 = 13 > 154 = 6 > 155 = 24 > 156 = 10 > 157 = 6 > 158 = 10 > 159 = 23 > 160 = 20 > 161 = 9 > 162 = 7 > 163 = 9 > 164 = 21 > 166 = 1 > 167 = 1 > 168 = 7 > 170 = 7 > 171 = 5 > 192 = 532 > 193 = 1246 > 194 = 919 > 195 = 634 > 196 = 10 > 198 = 16 > 199 = 17 > 202 = 43 > 203 = 37 > 204 = 8 > 205 = 5 > 206 = 3 > 207 = 2 > 208 = 17 > 209 = 19 > 212 = 511 > 213 = 438 > 216 = 21 > 217 = 473 > > 193.* is actually the one with most prefixes in it. > > > After one of these "temporary" marks is inactive for a while, remove it from the MARK X list, increase the "time to stay" for networks which are used often. > > > > So, your server apps should trigger a script (in the background) upon every new connection (maybe some tcpwrappers can do that, maybe you have to modify a tcpwrapper). > > > > make sure to update the database used by the scripts, Geo::IP has a "premium database subscription" update thingy. > > I just talked today with the owner about this and I think I''ll go > another way. I might use netfilter''s connection tracker so that the > lookup that decides which class to use is only done on connection setup > and not per packet. Still, 6000 rules are too much so I''m going to > create a hierarchical ruleset to minimize the worst case. I don''t want > to have anything beyond 30 rules worst case checking or so because the > server runs different applications and I should not make my presence > negatively noticeable. I think that is the best approach in this situation. > > Thanks for all the advice! > > CU > > René > > _______________________________________________ > LARTC mailing list / LARTC@mailman.ds9a.nl > http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/_______________________________________________ LARTC mailing list / LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/