Date: Sat, 23 May 1998 03:53:53 +0200 From: Eivind Eklund <eivind@yes.no> To: dg@root.com Cc: freebsd-net@FreeBSD.ORG Subject: Re: hash calculation for IP fast forwarding Message-ID: <19980523035353.44901@follo.net> In-Reply-To: <199805230021.RAA06112@implode.root.com>; from David Greenman on Fri, May 22, 1998 at 05:21:55PM -0700 References: <19980522172718.26605@follo.net> <199805230021.RAA06112@implode.root.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, May 22, 1998 at 05:21:55PM -0700, David Greenman wrote: > >On Fri, May 22, 1998 at 05:27:16AM -0700, David Greenman wrote: > >> As I mentioned recently in freebsd-net, the hash function that the fast > >> IP forwarding code uses is expensive (16 adds, 12 shifts, 6 subtracts, and > >> 6 compares). I think the following will provide a hash with similar quality, > >> but I might be missing something. This assumes that the table is 256 buckets > >> large, but it should work for larger tables as well. Opinions? > > > >I think this will tend to be overly much influenced by the tendency of > >IP-addresses to be loaded in the lower end of each octet. For a good > >hash, you'll want to mix bits on a non-octet level. However, to > >really find out if this is significant you'd have to do measurements. > > That might cause a small statistical shift, but I don't think it will be > significant since that it really only true for the LSB and all of the > octets are xored together. Well, labelling the address as A.B.C.D, it seems (from some examination of the net) A is clearly biased towards the range 192 (128) to 210 (223) B is not biased (or not much, anyway; it might look like a slight bias towards high values, which would be natural) C is biased towards small values D is biased towards small values I'm don't think the influence is too significant for a backbone router. However, I'm slightly less certain when it comes to small networks, where you often have a significant slide towards the lower address-ranges (e.g, splitting 10.x.x.x into a lot of /24-nets). One possible solution to find out how well it works is a verifier that tests how well the buckets are utilized every now and then, and printf()s a request for the admin to contact questions@FreeBSD.ORG if the utilization suck :) Here are smaple hash values for a sample from the large-scale net (based on a web-log I had lying around): Reviewed 1015317 entires : A B C D H 000: 0 2690 4657 27 3351 001: 0 3388 15182 14690 2299 002: 0 2917 9579 27290 5299 003: 0 4541 7282 13655 3422 004: 0 8293 6480 8204 4271 005: 0 2561 4744 15687 3880 006: 0 3057 3644 13031 2913 007: 0 2500 3648 10676 3274 008: 0 3355 5281 8927 4512 009: 0 1680 4762 7399 4850 010: 0 4039 5900 15201 5048 011: 0 2883 4183 9538 2655 012: 17040 3231 2930 5813 3492 013: 0 2222 5492 5123 3764 014: 0 1882 3946 5063 4374 015: 52 1958 3960 5173 5511 016: 0 4059 4796 3809 3207 017: 4 2517 4936 6031 2867 018: 0 3005 4567 6215 4705 019: 0 2559 4016 6326 2834 020: 22 1700 3873 6568 4719 021: 0 4638 3568 7293 4497 022: 0 3462 3613 5873 4840 023: 0 2069 3593 5417 5629 024: 8363 3380 2978 4275 4799 025: 0 4113 4143 7130 6798 026: 0 4456 3723 5734 3778 027: 0 4734 3586 5377 2925 028: 0 3018 5139 3176 2752 029: 0 4041 3770 4235 2573 030: 0 5991 3996 3900 6269 031: 0 3715 2732 4772 2420 032: 2477 2182 3748 5213 3433 033: 9 2737 4317 7752 4238 034: 0 8701 4206 7669 4798 035: 178 8921 31467 11534 5698 036: 6 4962 5838 6916 2500 037: 0 7366 4180 7396 4036 038: 4493 2081 3076 7485 4898 039: 0 3184 3547 6333 4404 040: 230 2498 2803 6690 5321 041: 0 2102 4581 5252 3565 042: 0 2937 1901 6660 3177 043: 0 1268 4260 3982 3794 044: 0 1952 4129 4335 5991 045: 0 1925 2270 4445 5996 046: 0 1461 3060 3712 3884 047: 0 2922 2053 2138 7349 048: 0 4194 3467 4341 3410 049: 0 3230 3555 6871 3429 050: 0 2674 5630 4995 3009 051: 0 3532 2688 3838 2365 052: 0 1936 2808 3702 3696 053: 112 2156 2050 2616 5150 054: 0 4148 4324 2586 1875 055: 262 3980 3234 4132 5309 056: 0 1695 3432 3028 3052 057: 37 1841 4652 4036 3389 058: 0 2202 4626 4617 2785 059: 0 1922 3384 3252 2676 060: 0 2954 4147 2383 3281 061: 0 1898 2362 2727 3994 062: 381 1345 3852 2483 3645 063: 0 4354 2898 1768 3286 064: 0 5718 7601 2460 3946 065: 0 4745 3249 5444 3792 066: 0 3008 6284 8787 3482 067: 0 6985 2321 4398 2718 068: 0 4547 4868 3850 4110 069: 0 2398 3243 3366 4701 070: 0 2783 4509 4038 4001 071: 0 4821 3044 3785 3895 072: 0 5263 4130 4187 4286 073: 0 1897 2805 3321 4452 074: 0 2467 2567 2421 4211 075: 0 1622 2999 3894 2855 076: 0 2126 2673 2870 5377 077: 0 3785 3511 2923 3290 078: 0 2032 2111 3279 4638 079: 0 27470 3143 3028 3848 080: 0 2915 4631 4468 2504 081: 0 2446 2296 2331 2746 082: 0 2853 1704 3710 3191 083: 0 5389 5048 3901 2747 084: 0 2730 3731 2520 3912 085: 0 830 2728 2644 2731 086: 0 4188 2722 2856 2923 087: 0 1388 2333 7252 2815 088: 0 3450 2672 6826 3595 089: 0 1317 3489 6066 2387 090: 0 1707 7574 2260 2446 091: 0 2375 3264 3898 2281 092: 0 3030 3363 2754 3007 093: 0 1391 2159 2327 3572 094: 0 3779 3055 2591 4731 095: 0 1565 1871 2425 2172 096: 0 6135 4278 1414 3536 097: 0 3179 4651 3142 3026 098: 0 869 1647 3990 4314 099: 0 2320 3094 2453 2819 100: 0 5585 3887 6546 2439 101: 0 4158 3279 6703 6529 102: 0 3657 3713 4924 2997 103: 0 4759 2885 4840 2628 104: 0 2043 4630 4756 3569 105: 0 1405 3895 5364 2948 106: 0 2146 3986 5303 4722 107: 0 2167 4651 3696 6289 108: 0 2351 2982 3398 5116 109: 0 3281 2322 3136 3567 110: 0 989 2813 3725 3412 111: 0 2578 2293 3818 2790 112: 0 4033 2407 4334 5659 113: 0 2722 3386 5365 3466 114: 0 1808 4740 4699 2332 115: 0 7763 2237 4848 3163 116: 0 3902 3482 3666 2845 117: 0 2625 3111 3056 4915 118: 0 1054 4955 2146 4337 119: 0 1441 3366 2033 4883 120: 0 6701 2534 3071 6407 121: 0 2104 2620 2788 4417 122: 0 1212 2020 3207 4026 123: 0 2581 4547 2542 5000 124: 0 1282 3061 3806 4890 125: 0 2444 5277 2636 5749 126: 0 2097 2431 2158 6269 127: 0 4222 2936 1634 4613 128: 10595 5206 4961 2185 2977 129: 12702 2404 3423 3816 4971 130: 9222 4308 7851 5770 5008 131: 4717 2900 12590 3476 4189 132: 3589 2992 3563 3569 3577 133: 13 5695 4571 4059 4451 134: 5450 5010 2622 2688 2843 135: 0 3060 4001 6835 3403 136: 2845 2998 2794 6705 3668 137: 5856 3205 2763 7462 4303 138: 994 3055 2354 6994 3611 139: 2908 3967 3623 6827 2906 140: 3167 3419 3707 8717 3830 141: 1603 2612 2093 3948 4023 142: 11392 12327 3096 2255 2842 143: 1138 3405 2758 2533 2598 144: 1535 3384 3142 2331 2843 145: 571 915 3327 3411 3733 146: 3058 2782 4164 2912 3484 147: 3110 3673 2495 1949 1948 148: 1882 3600 3480 2539 2057 149: 1779 4146 2397 2182 3058 150: 2297 3045 2999 2348 4320 151: 3313 3615 3094 3204 3744 152: 132700 6814 3166 3699 3582 153: 13014 4775 2478 3590 2370 154: 113 3398 1928 1774 5282 155: 3517 4923 2768 3955 3959 156: 3674 3345 3196 2468 6679 157: 1861 2117 2241 2468 6955 158: 3009 2472 3254 2973 7301 159: 2793 2545 2291 2382 8260 160: 1773 3632 3260 1343 4681 161: 4076 4507 4034 1863 5383 162: 3665 4409 2352 3200 4902 163: 2890 128061 3265 2283 3730 164: 6651 3503 2893 2624 3210 165: 6041 7906 1707 2591 4149 166: 8974 3360 2766 3149 2302 167: 3397 2592 3451 2297 3710 168: 8162 2888 2274 2596 2524 169: 2568 1204 2740 2346 2591 170: 3784 6192 2561 3014 3295 171: 493 2536 2166 3016 3058 172: 0 12311 2583 2214 4529 173: 0 4116 2600 3280 4190 174: 0 4972 4005 1927 5469 175: 0 4572 2719 1217 7494 176: 0 4231 1719 1284 3676 177: 0 8279 2348 2319 2466 178: 0 1995 2152 2161 3110 179: 0 2457 1912 2009 3290 180: 0 2341 1797 2720 3167 181: 0 2680 1414 2506 4167 182: 0 1077 1963 2219 3391 183: 0 3968 3534 2718 3988 184: 0 3886 3094 2862 2818 185: 0 2499 2727 1179 2229 186: 0 3480 2247 2670 3768 187: 0 1389 4267 2571 2660 188: 0 16570 2277 1521 3920 189: 0 3938 2115 1164 2316 190: 0 3308 2082 1841 3342 191: 0 1705 3601 2153 3913 192: 23883 1548 2816 949 2916 193: 15099 4266 3618 2152 4138 194: 33808 5753 7890 3161 3447 195: 21309 1562 18733 2161 3491 196: 10369 4690 2648 2705 3203 197: 0 1919 16132 3651 2846 198: 30691 5067 3900 1306 2488 199: 28058 1864 2299 2192 3848 200: 2902 3337 2595 3564 4934 201: 0 3118 18514 2239 4024 202: 13802 2031 2722 2634 4369 203: 27279 3188 2781 1596 2871 204: 54243 4403 17751 1927 3746 205: 46194 4201 15483 2223 3963 206: 80883 2800 16128 3059 3206 207: 135804 4171 13543 2496 2845 208: 71091 2179 4250 2126 4006 209: 77330 2567 2490 2399 6038 210: 1766 3168 2868 1864 5164 211: 0 1850 2930 1724 4817 212: 249 5610 2772 1598 2736 213: 0 2104 18159 1802 4359 214: 0 8997 2487 1443 4941 215: 0 1740 2156 2593 3590 216: 0 7027 3637 1926 5960 217: 0 4504 2443 9879 4305 218: 0 1969 2007 8178 4660 219: 0 2432 2535 9692 6009 220: 0 1683 2841 1646 4542 221: 0 1134 2044 1531 4567 222: 0 3866 2357 2792 3922 223: 0 1627 1889 1095 3317 224: 0 2812 5237 1843 3925 225: 0 4596 2232 2527 3796 226: 0 1569 2648 3272 4368 227: 0 4269 2920 3783 4119 228: 0 5341 3834 2231 3212 229: 0 3477 4055 2813 3322 230: 0 2797 3051 2478 2816 231: 0 2715 1472 2593 4566 232: 0 3740 7231 1587 2833 233: 0 2841 2810 2362 2779 234: 0 2477 3009 1865 3779 235: 0 2668 2095 3740 5235 236: 0 2808 2255 3654 4944 237: 0 3596 2958 3799 2897 238: 0 5706 2675 1917 3065 239: 0 3027 2451 1578 4443 240: 0 2712 3834 3823 4891 241: 0 2763 3331 5396 5406 242: 0 2061 2486 6679 4855 243: 0 3402 2352 2096 2081 244: 0 3202 1870 1260 6230 245: 0 1919 3348 1763 7276 246: 0 1209 2747 1383 4334 247: 0 2469 1941 2812 6067 248: 0 2171 3964 1948 5967 249: 0 768 1956 1978 2092 250: 0 3125 1611 2766 7104 251: 0 2361 1418 1906 5753 252: 0 2907 2206 1958 3178 253: 0 3407 3867 2136 4544 254: 0 5023 3497 3534 4166 255: 0 3781 3665 61 4799 Doesn't look so bad, especially considering that this is from a single site, so the IP-addresses of the admins can cause some 'spikes'. Oh, and A 152 and B 163 is AOL :-) Eivind To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19980523035353.44901>