-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 With evanbd's guidance I've run more simulations, this time comparing an ideal network to one more closely conforming to the actual network as measured. Specifically, in addition to matching degree distribution it also matches link length distribution. The impact is drastic: it appears to result in routing 2 to 3 times worse than the ideal.
These findings are encouraging: they suggest - as was suspected - that link length distribution distortion is a significant problem. If we can fix the link length distribution routing could improve dramatically. The next step is attempting to reproduce in simulation the link length distribution distortion from scratch. This could take the form of simulating opennet with node churn and varying uptime. I've been continuing work on the probes, focusing now on concurrency and design refinement, for which zab_'s insight and assistance have been invaluable. toad_, too, has contributed very thorough and helpful review. If anyone would like to review the patches they are available here. [1] If any of this is unclear or calls for additional explanation, please don't hesitate to ask. Now the simulation details: changes are ~2x or more due to variance expected on the scale of logarithmic changes. The degrees are different from what was intended due to the behavior of the ideal graph generation. My hope is that though the degrees are off, they are enough to confirm the basic principle that link length distortion on the order seen in the actual network severely impacts routing. For size: - -Small: 6000 - -Normal: 18000 (approximate measured network size) - -Large: 36000 For mean degree: - -Low: 16 - -Normal: 26 (measured mean degree is closer to 17) - -Large: 86 Hops values are for 90th percentile. If degree is low, normal, or large, the link length distribution is ideal. If the degree conforms to measurement, (conf) so does the link length distribution. - ---------------------------------------------------------------------- network size | smal | smal | norm | norm | norm | norm | larg | larg | degree | norm | conf | high | norm | low | conf | norm | conf | data found | 5 | 15 | 3 | 6 | 11 | 20 | 6 | 22 | not found | 16 | 22 | 14 | 13 | 18 | 25 | 14 | 28 | - ---------------------------------------------------------------------- The simulator is also available, [2] and I've attached the output of the simulations summarized in the table above. Thanks, operhiem1 [1] https://github.com/freenet/fred-staging/pull/94 [2] https://github.com/Thynix/routing-simulator/tree/linkConformance -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQIcBAEBAgAGBQJP66mCAAoJECLJP19KqmFuh+IQALrBUsRhMPUxTZ4173hkCdul IFLGuyNSQs86wDz9/U/VgfgFEB/15RAljGbYP7PGF82dv/sVZ2XoIhqDbIEdK2LC W5sTql/eMTZ8TpYADDqHUXNuckynD3ZfiMoqqujx6atgDj61TO6H06KzCjYGpATH Z5jgm1xnEafUbLy1R/KWxiWpQxnnhx4ZM6clPnV56XtdfTFvVK9NvrHjjn6j/K62 +sZAam0Ui1LmqG8sAu3awJHOJbTf205LHZClsu8hQxx2d4zYoFIIU6PtPvEAX8zG tZ3LT5+049/gOSGf5Kh9+nWH06qGMHM86r7s0qDtV1TodL5cUZ/jQFSY/4UIn0CF AItyWgbm37pSjz8CYDxGzT/oHB1v0CZTyoh7scCJ41PBpV7ppl4pA9HHRhD9FD0o lnUDo4hwaYYYPzNaZcsCan87ibRBmFe5VfyJBqBs4ffULYCdRZBwdgKu48zjyux6 SP4AVQREwu4pCDtqAN/c42vSq8tdIvuSsONl/kTWeXi8sQw2w/VdKVixIkU9caka c78ON/b+XhGzThch1IHvUVrm0JiXVTw5bjwqjy1/WmgWvE7B0OrRr33ghiZbOo1n Axwn0F0tP2lFv+T9pMU57LFhNVpkqkPsfHJqFjzk7/JJPrj2jxRA0D9f6Lq4MNoq AE5czu00GNcjL4AOKphr =DkwA -----END PGP SIGNATURE----- -------------- next part -------------- A non-text attachment was scrubbed... Name: routing_simulator_results.zip Type: application/zip Size: 7614 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20120627/5cb921b0/attachment.zip> -------------- next part -------------- A non-text attachment was scrubbed... Name: routing_simulator_results.zip.sig Type: application/pgp-signature Size: 543 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20120627/5cb921b0/attachment.pgp>
