---

Revision 3672 - Directory Listing
Modified Wed Jan 21 14:30:25 2009 UTC (10 months ago) by baford

Add LGPL copyright notices, update licensing info/explanation in README

---

Revision 2880 - Directory Listing
Modified Fri Nov 23 22:04:25 2007 UTC (2 years ago) by baford

Incorporated patch from Cyrus Hall for install target and shared libs,
slightly modified to preserve POST_TARGETDEPS dependency on libsst.

---

Revision 2728 - Directory Listing
Modified Tue Aug 7 15:30:00 2007 UTC (2 years, 3 months ago) by baford

Added API hooks for listen modes and receive buffer control

---

Revision 2599 - Directory Listing
Modified Tue Jun 19 10:36:47 2007 UTC (2 years, 5 months ago) by baford

Propagate process exit status/signals correctly.

---

Revision 2360 - Directory Listing
Modified Tue May 1 09:55:34 2007 UTC (2 years, 6 months ago) by baford

Implemented the routing table building algorithm in my recent E-mail.
Indeed, it appears to work reliably regardless of graph topology
(no subsequent routing failures), and the stretch results are sometimes
substantially better than with the old announcement flooding algorithm.
Comparing the old results for different values of 'r' against the new:


2D mesh:

Network size 100:
r=1: 494/1000 failures (49.4%), stretch avg 1.5379
r=2: 0 failures, stretch avg 1.4819
r=3: 0 failures, stretch avg 1.4848
r=4: 0 failures, stretch avg 1.5063
new: stretch: min 1 max 3.13122 med 1.25529 avg 1.32887 +/- 0.313466

Network size 300:
r=1: 605/1000 failures (60.5%), stretch avg 1.8984
r=2: 0 failures, stretch avg 1.6867
r=3: 0 failures, stretch avg 1.6882
r=4: 0 failures, stretch avg 1.6417
new: stretch: min 1 max 3.57915 med 1.37983 avg 1.48458 +/- 0.395171

Network size 1000:
new: stretch: min 1 max 4.89052 med 1.52345 avg 1.60581 +/- 0.418589


High-dimension graphs w/ median degree 3:

Network size 100:
r=1: 316/1000 failures (31.6%), stretch avg 1.8079
r=2: 4/1000 failures (0.4%), stretch avg 1.5657
r=3: 3/1000 failures (0.3%), stretch avg 1.5718
r=4: 0 failures, stretch avg 1.6229
new: stretch: min 1 max 5 med 1.33333 avg 1.52003 +/- 0.583348

Network size 300:
r=1: 449/1000 failures (44.9%), stretch avg 2.095
r=2: 4/1000 failures (0.4%), stretch avg 1.790
r=3: 0 failures, stretch avg 1.7845
r=4: 0 failures, stretch avg 1.8302
new: stretch: min 1 max 6 med 1.66667 avg 1.78197 +/- 0.754117 count 1000

Network size 1000:
new: stretch: min 1 max 8 med 2 avg 2.20762 +/- 0.894658 count 1000


High-dimension graphs w/ median degree 5:

Network size 100:
r=1: 260/1000 failures (26.0%), stretch avg 1.8833
r=2: 6/1000 failures (0.6%), stretch avg 1.6754
r=3: 0 failures, stretch avg 1.6432
r=4: 0 failures, stretch avg 1.6025
new: stretch: min 1 max 5 med 1.5 avg 1.6875 +/- 0.692101 count 1000

Network size 300:
r=1: 270/1000 failures (27.0%), stretch avg 2.1526
r=2: 12/1000 failures (1.2%), stretch avg 1.8712
r=3: 0 failures, stretch avg 1.8149
r=4: 0 failures, stretch avg 1.8158
new: stretch: min 1 max 6 med 1.66667 avg 1.83503 +/- 0.750267 count 1000

Network size 1000:
new: stretch: min 1 max 10 med 2 avg 2.2809 +/- 0.92863 count 1000


High-dimension graphs w/ median degree 8:

Network size 100:
r=1: 199/1000 failures (19.9%), stretch avg 1.7482
r=2: 11/1000 failures (1.1%), stretch avg 1.5615
r=3: 0 failures, stretch avg 1.5477
r=4: 0 failures, stretch avg 1.5052
new: stretch: min 1 max 6 med 1.5 avg 1.66833 +/- 0.751188 count 1000


The disadvantage of the new "fully reliable" algorithm
is that on some graphs the degree tends to explode on intermediate levels.
For example, on a 300-node random graph:

affinity 0 degrees: min 1 max 23 med 6 avg 7.27333 +/- 4.50614 count 300
affinity 1 degrees: min 1 max 59 med 8 avg 10.8733 +/- 9.1926 count 300
affinity 2 degrees: min 1 max 50 med 12 avg 14.4033 +/- 10.5613 count 300
affinity 3 degrees: min 1 max 39 med 14 avg 14.1633 +/- 8.35604 count 300
affinity 4 degrees: min 1 max 24 med 11 avg 10.58 +/- 4.87069 count 300
affinity 5 degrees: min 1 max 16 med 6 avg 6.63667 +/- 2.81389 count 300
affinity 6 degrees: min 0 max 9 med 4 avg 3.81 +/- 1.94608 count 300
affinity 7 degrees: min 0 max 7 med 2 avg 2.24 +/- 1.47955 count 300
affinity 8 degrees: min 0 max 5 med 1 avg 1.14667 +/- 1.04809 count 300
affinity 9 degrees: min 0 max 3 med 0 avg 0.593333 +/- 0.753628 count 300
affinity 10 degrees: min 0 max 2 med 0 avg 0.34 +/- 0.6146 count 300
affinity 11 degrees: min 0 max 2 med 0 avg 0.153333 +/- 0.395587 count 300
affinity 12 degrees: min 0 max 1 med 0 avg 0.08 +/- 0.271293 count 300
affinity 13 degrees: min 0 max 1 med 0 avg 0.0533333 +/- 0.224697 count 300
affinity 14 degrees: min 0 max 1 med 0 avg 0.0333333 +/- 0.179505 count 300
affinity 15 degrees: min 0 max 1 med 0 avg 0.0133333 +/- 0.114698 count 300
affinity 16 degrees: min 0 max 1 med 0 avg 0.0133333 +/- 0.114698 count 300
affinity 17 degrees: min 0 max 1 med 0 avg 0.00666667 +/- 0.081377 count 300
affinity 18 degrees: min 0 max 0 med 0 avg 0 +/- 0 count 300
stretch: min 1 max 6 med 1.66667 avg 1.78197 +/- 0.754117 count 1000

Unsurprisingly, degree explosion isn't nearly so bad on a 2D mesh graph;
in fact degree seems to taper off with level:

affinity 0 degrees: min 3 max 22 med 12 avg 12.48 +/- 4.20114 count 300
affinity 1 degrees: min 2 max 14 med 8 avg 8.24 +/- 2.8453 count 300
affinity 2 degrees: min 2 max 12 med 6 avg 5.92 +/- 2.12766 count 300
affinity 3 degrees: min 1 max 11 med 5 avg 4.82 +/- 1.80581 count 300
affinity 4 degrees: min 1 max 9 med 4 avg 4.07333 +/- 1.59832 count 300
affinity 5 degrees: min 1 max 7 med 3 avg 3.36667 +/- 1.32372 count 300
affinity 6 degrees: min 0 max 5 med 2 avg 2.58 +/- 1.07561 count 300
affinity 7 degrees: min 0 max 4 med 2 avg 1.64667 +/- 0.963581 count 300
affinity 8 degrees: min 0 max 4 med 1 avg 0.94 +/- 0.862013 count 300
affinity 9 degrees: min 0 max 3 med 0 avg 0.513333 +/- 0.695094 count 300
affinity 10 degrees: min 0 max 2 med 0 avg 0.293333 +/- 0.517 count 300
affinity 11 degrees: min 0 max 2 med 0 avg 0.146667 +/- 0.380993 count 300
affinity 12 degrees: min 0 max 1 med 0 avg 0.08 +/- 0.271293 count 300
affinity 13 degrees: min 0 max 1 med 0 avg 0.0466667 +/- 0.210924 count 300
affinity 14 degrees: min 0 max 1 med 0 avg 0.0266667 +/- 0.161107 count 300
affinity 15 degrees: min 0 max 1 med 0 avg 0.0133333 +/- 0.114698 count 300
affinity 16 degrees: min 0 max 1 med 0 avg 0.0133333 +/- 0.114698 count 300
affinity 17 degrees: min 0 max 1 med 0 avg 0.00666667 +/- 0.081377 count 300
affinity 18 degrees: min 0 max 0 med 0 avg 0 +/- 0 count 300
stretch: min 1 max 3.57915 med 1.37983 avg 1.48458 +/- 0.395171 count 1000


On the other hand, the high-conductance graphs on which degree explosion
is likely to occur are probably exactly the graphs on which artificially
capping degree somehow to a fixed redundancy limit is least likely to
cause the graph to become disconnected and cause routing failures.
So the best algorithm is probably a hybrid of the new and old schemes.

---

Revision 2043 - Directory Listing
Modified Thu Apr 26 02:26:47 2007 UTC (2 years, 7 months ago) by baford

Recover from recursive path optimization failures;
got some failure results for various maximum bucket sizes and networks.

---

Revision 2042 - Directory Listing
Modified Wed Apr 25 16:39:19 2007 UTC (2 years, 7 months ago) by baford

Added simple high-dimensional random graph generator.
Some preliminary results on 300-node networks
with different exponential node degree distributions:

graph degree: min 0 max 8 med 1 avg 1.75667 +/- 1.11839 count 300
stretch: min 1 max 6.66667 med 1.86607 avg 2.05983 +/- 0.913994 count 1000

graph degree: min 0 max 21 med 3 avg 3.63667 +/- 2.97848 count 300
stretch: min 1 max 5 med 1.66667 avg 1.85468 +/- 0.777779 count 1000

graph degree: min 0 max 35 med 5 avg 6.65667 +/- 5.63727 count 300
stretch: min 1 max 6 med 1.66667 avg 1.80578 +/- 0.739338 count 1000

---

Revision 2038 - Directory Listing
Modified Tue Apr 24 15:56:54 2007 UTC (2 years, 7 months ago) by baford

Exploring more routing algorithm variants,
but no substantial improvements this time.

---

Revision 2032 - Directory Listing
Modified Sun Apr 22 18:03:17 2007 UTC (2 years, 7 months ago) by baford

Added statistics computation module, random path evaluation,
improved path optimization based on pre-recursion.
Results are already starting to look fairly usable:

small, 100-node network:
stretch: min 1 max 4.58289 med 1.56416 avg 1.70738 +/- 0.597866 count 1000 

larger 1000-node network:
stretch: min 1 max 7.48593 med 2.20895 avg 2.311 +/- 0.739895 count 1000 

(These are with 2 levels of pre-recursion and no post-recursion optimization.)

---

Revision 2031 - Directory Listing
Modified Sat Apr 21 18:21:27 2007 UTC (2 years, 7 months ago) by baford

Added shortest path computation, for stretch comparison

---

Revision 2030 - Directory Listing
Modified Fri Apr 20 23:10:34 2007 UTC (2 years, 7 months ago) by baford

First cut at an initial (still pretty simplistic)
route optimization algorithm.

---

Revision 2023 - Directory Listing
Modified Fri Apr 20 16:09:26 2007 UTC (2 years, 7 months ago) by baford

Separated router stuff out of main module

---

Revision 2022 - Directory Listing
Modified Thu Apr 19 20:46:42 2007 UTC (2 years, 7 months ago) by baford

First cut at building routing tables working -
but without route optimization or time-based simulation yet.

---

Revision 2021 - Directory Listing
Modified Thu Apr 19 17:53:40 2007 UTC (2 years, 7 months ago) by baford

first bits of neighbor table maintenance for routing algorithm

---

Revision 2020 - Directory Listing
Added Wed Apr 18 21:41:55 2007 UTC (2 years, 7 months ago) by baford

Beginnings of a rewrite of the old UIP routing protocol
under the new SST simulation framework.