---

Revision 3463 - Directory Listing
Modified Fri Oct 24 20:50:18 2008 UTC (13 months ago) by ctl

 r5008@brainchild:  ctl | 2008-10-24 16:50:07 -0400
 irrelevant old changes
 

---

Revision 3462 - Directory Listing
Modified Fri Oct 24 20:50:10 2008 UTC (13 months ago) by ctl

 r4045@brainchild:  ctl | 2008-02-03 22:34:51 -0500
 a couple of random things I forgot to check in.
 

---

Revision 3144 - Directory Listing
Modified Mon Feb 4 13:52:34 2008 UTC (21 months, 2 weeks ago) by jastr

last harness updates from submit time

---

Revision 3122 - Directory Listing
Modified Sat Feb 2 07:16:38 2008 UTC (21 months, 3 weeks ago) by ctl

 r4037@brainchild:  ctl | 2008-02-02 02:10:41 -0500
 failure graphs
 

---

Revision 3115 - Directory Listing
Modified Sat Feb 2 05:58:00 2008 UTC (21 months, 3 weeks ago) by ctl

 r4032@brainchild:  ctl | 2008-02-02 00:51:44 -0500
 some failures data
 

---

Revision 3111 - Directory Listing
Modified Sat Feb 2 05:02:39 2008 UTC (21 months, 3 weeks ago) by ctl

 r4028@brainchild:  ctl | 2008-02-01 23:56:44 -0500
 Record the number of routing attempts for each pair.
 

---

Revision 3109 - Directory Listing
Modified Sat Feb 2 04:52:42 2008 UTC (21 months, 3 weeks ago) by ctl

 r4023@brainchild:  ctl | 2008-02-01 23:46:47 -0500
 At long last, a robustness measurement I can believe in.
 "Seems to work OK."
 Simulation is super slow.
 

---

Revision 3108 - Directory Listing
Modified Sat Feb 2 04:38:26 2008 UTC (21 months, 3 weeks ago) by jastr

wasn't gossiping the non-tz entries... makes a big difference in the
routes & congestion found.  regenerating routes for the plots 
again.

---

Revision 3105 - Directory Listing
Modified Sat Feb 2 03:43:14 2008 UTC (21 months, 3 weeks ago) by ctl

 r4019@brainchild:  ctl | 2008-02-01 22:37:11 -0500
 Some very primitive link failure computation;
 cannot use full tables, only landmark tables.
 

---

Revision 3101 - Directory Listing
Modified Sat Feb 2 02:25:31 2008 UTC (21 months, 3 weeks ago) by ctl

 r4016@brainchild:  ctl | 2008-02-01 21:19:30 -0500
 Fix congestions view typo.
 In-between state for robustness measurement.
 

---

Revision 3099 - Directory Listing
Modified Sat Feb 2 02:12:46 2008 UTC (21 months, 3 weeks ago) by jastr

more updates

---

Revision 3098 - Directory Listing
Modified Sat Feb 2 01:44:58 2008 UTC (21 months, 3 weeks ago) by ctl

 r4008@brainchild:  ctl | 2008-02-01 20:36:22 -0500
 This may make the forward stage a big faster.
 

---

Revision 3097 - Directory Listing
Modified Sat Feb 2 01:44:55 2008 UTC (21 months, 3 weeks ago) by ctl

 r4007@brainchild:  ctl | 2008-02-01 19:44:26 -0500
 bump the number of iterations, print the number of iterations always
 

---

Revision 3096 - Directory Listing
Modified Sat Feb 2 00:30:45 2008 UTC (21 months, 3 weeks ago) by jastr

harness checkpoint

---

Revision 3095 - Directory Listing
Modified Sat Feb 2 00:18:13 2008 UTC (21 months, 3 weeks ago) by ctl

 r4005@brainchild:  ctl | 2008-02-01 19:12:13 -0500
 Implement TZ handshaking.  At first glance, it seems to help a little bit.
 

---

Revision 3094 - Directory Listing
Modified Fri Feb 1 23:51:28 2008 UTC (21 months, 3 weeks ago) by ctl

 r4002@brainchild:  ctl | 2008-02-01 18:45:33 -0500
 update TODO
 

---

Revision 3093 - Directory Listing
Modified Fri Feb 1 23:51:27 2008 UTC (21 months, 3 weeks ago) by ctl

 r4001@brainchild:  ctl | 2008-02-01 18:44:37 -0500
 update TODO
 

---

Revision 3092 - Directory Listing
Modified Fri Feb 1 23:48:23 2008 UTC (21 months, 3 weeks ago) by ctl

 r3999@brainchild:  ctl | 2008-02-01 18:42:28 -0500
 stylistic change, use std::advance instead of +
 

---

Revision 3091 - Directory Listing
Modified Fri Feb 1 23:44:05 2008 UTC (21 months, 3 weeks ago) by ctl

 r3997@brainchild:  ctl | 2008-02-01 18:38:12 -0500
 Here's a really rinky-dink solution to the long-stretch-1-link-path problem
 Jacob found.
 

---

Revision 3090 - Directory Listing
Modified Fri Feb 1 23:35:24 2008 UTC (21 months, 3 weeks ago) by ctl

 r3995@brainchild:  ctl | 2008-02-01 18:29:30 -0500
 Fix broken degree view
 

---

Revision 3089 - Directory Listing
Modified Fri Feb 1 23:35:12 2008 UTC (21 months, 3 weeks ago) by ctl

 r3992@brainchild:  ctl | 2008-02-01 18:25:40 -0500
 Create a view of node degrees.
 

---

Revision 3088 - Directory Listing
Modified Fri Feb 1 23:35:10 2008 UTC (21 months, 3 weeks ago) by ctl

 r3991@brainchild:  ctl | 2008-02-01 18:23:39 -0500
 The net view now contains both directions of edges, so node degree can be
 counted more easily.
 

---

Revision 3086 - Directory Listing
Modified Fri Feb 1 22:48:58 2008 UTC (21 months, 3 weeks ago) by ctl

 r3986@brainchild:  ctl | 2008-02-01 17:43:00 -0500
 Stomp a real killer of a bug --- TZ level is empty at a level is not the
 same as the distance being infinite!  This might invalidate any previous
 plain TZ results, assuming we have any...
 Though I think it only shows up in very rare circumstances with plain TZ.
 

---

Revision 3085 - Directory Listing
Modified Fri Feb 1 22:48:57 2008 UTC (21 months, 3 weeks ago) by ctl

 r3985@brainchild:  ctl | 2008-02-01 17:12:52 -0500
 script for just generating instances
 

---

Revision 3084 - Directory Listing
Modified Fri Feb 1 22:48:55 2008 UTC (21 months, 3 weeks ago) by ctl

 r3984@brainchild:  ctl | 2008-02-01 17:12:28 -0500
 allow passing in route and forward options
 

---

Revision 3083 - Directory Listing
Modified Fri Feb 1 22:13:31 2008 UTC (21 months, 3 weeks ago) by ctl

 r3981@brainchild:  ctl | 2008-02-01 17:07:20 -0500
 Turn off invariant checking (needed it for debugging the once-in-a-blue-moon problem)
 

---

Revision 3082 - Directory Listing
Modified Fri Feb 1 22:13:30 2008 UTC (21 months, 3 weeks ago) by ctl

 r3980@brainchild:  ctl | 2008-02-01 17:06:35 -0500
 Implement the code to announce tentative landmarks and pin them in the table.
 Stomped a very subtle bug (remove_if != partition) that broke everything once
 in a blue moon.
 Forwarding tables still seem broken though.
 

---

Revision 3080 - Directory Listing
Modified Fri Feb 1 20:37:53 2008 UTC (21 months, 3 weeks ago) by jastr

fix plot fonts

---

Revision 3079 - Directory Listing
Modified Fri Feb 1 20:23:03 2008 UTC (21 months, 3 weeks ago) by ctl

 r3974@brainchild:  ctl | 2008-02-01 15:16:52 -0500
 1. a lot of infrastructure for "pinned" and "tentative" tables.
    it all compiles and works,
    BUT currently never announces any non-TZ landmarks.
    That's next step.
 2. Bryan's requested num-levels option.
 

---

Revision 3077 - Directory Listing
Modified Fri Feb 1 18:56:59 2008 UTC (21 months, 3 weeks ago) by jastr

save pre-route copies of all

---

Revision 3075 - Directory Listing
Modified Fri Feb 1 18:21:51 2008 UTC (21 months, 3 weeks ago) by jastr

max relative congestion.  plain TZ is pretty awful...

separate out the plotting from the data.

---

Revision 3074 - Directory Listing
Modified Fri Feb 1 18:20:45 2008 UTC (21 months, 3 weeks ago) by ctl

 r3961@brainchild:  ctl | 2008-02-01 13:14:50 -0500
 Kludge the hell out of the cache to avoid broken paths:
 add a never-evict option to turn off cache eviction.
 Eviction is a total rathole.  But it's going to be necessary in some form
 to deal with dynamicity.
 

---

Revision 3070 - Directory Listing
Modified Fri Feb 1 17:04:58 2008 UTC (21 months, 3 weeks ago) by jastr

cache sql summarizations,
plot average values (currently only two samples up to
16k)

---

Revision 3068 - Directory Listing
Modified Fri Feb 1 06:59:50 2008 UTC (21 months, 3 weeks ago) by ctl

 r3957@brainchild:  ctl | 2008-02-01 01:54:00 -0500
 Filling out routing table cache levels works as advertised, but be warned,
 forwarding will fail due to broken trees.  The broken trees are caused
 by cache evictions, much as you'd expect.  In a real system the solution
 would be to just run another search in parallel, but that's weak
 here.  Still trying to come up with the right solution.
 

---

Revision 3067 - Directory Listing
Modified Fri Feb 1 06:22:50 2008 UTC (21 months, 3 weeks ago) by jastr

create a stretch view in forward.cpp

first plots for avg and max stretch for single runs in the
range of really small to 3200 nodes

---

Revision 3065 - Directory Listing
Modified Fri Feb 1 05:23:27 2008 UTC (21 months, 3 weeks ago) by ctl

 r3955@brainchild:  ctl | 2008-02-01 00:17:31 -0500
 Finally, have caching seemingly working.
 

---

Revision 3064 - Directory Listing
Modified Fri Feb 1 03:39:02 2008 UTC (21 months, 3 weeks ago) by jastr

bump up table_levels to 25

---

Revision 3063 - Directory Listing
Modified Fri Feb 1 03:08:19 2008 UTC (21 months, 3 weeks ago) by jastr

generate (small numbers of small) datasets

---

Revision 3062 - Directory Listing
Modified Fri Feb 1 02:28:43 2008 UTC (21 months, 3 weeks ago) by jastr

the prune code if ever needed again

---

Revision 3060 - Directory Listing
Modified Fri Feb 1 00:46:58 2008 UTC (21 months, 3 weeks ago) by ctl

 r3948@brainchild:  ctl | 2008-01-31 19:41:02 -0500
 Implement pragmas to turn off synchronous writing and turn up the sqlite cache size.
 See --synchronous and --cache-size options.
 

---

Revision 3059 - Directory Listing
Modified Thu Jan 31 23:23:31 2008 UTC (21 months, 3 weeks ago) by ctl

 r3946@brainchild:  ctl | 2008-01-31 18:17:39 -0500
 Implemented mesh generation.
 

---

Revision 3058 - Directory Listing
Modified Thu Jan 31 20:53:59 2008 UTC (21 months, 3 weeks ago) by ctl

 r3943@brainchild:  ctl | 2008-01-31 15:48:06 -0500
 Split graph.hpp random generators off into random_graph.hpp to mitigate
 crushingly slow compile times.  Yay templates.
 

---

Revision 3057 - Directory Listing
Modified Thu Jan 31 20:53:56 2008 UTC (21 months, 3 weeks ago) by ctl

 r3942@brainchild:  ctl | 2008-01-31 15:18:50 -0500
 reorder classes without changing content
 

---

Revision 3056 - Directory Listing
Modified Thu Jan 31 20:19:43 2008 UTC (21 months, 3 weeks ago) by ctl

 r3934@brainchild:  ctl | 2008-01-31 15:13:50 -0500
 Generate scale-free graphs.  Seemed to work first time it compiled.
 

---

Revision 3054 - Directory Listing
Modified Thu Jan 31 18:12:41 2008 UTC (21 months, 3 weeks ago) by jastr

attempt to use the DIMES city-edges anyway.  Not sure if this
will work yet, but we'll see.

The 1e4 pair on the skitter router graph finished:

probably 1e5 won't finish in a useful amount of time, but I'll
start another 1e4 set and see whether the results look the same.

================================
../compact generate-pairs --pairs 10000 --progress --network-input skitter-rtr.db -o skitter-rtr.db
Loading network from skitter-rtr.db ...
Generating random node pairs...
Storing random node pairs to skitter-rtr.db ...
sample-id 3328034125031986140
../compact shortest-paths --progress --unbias-pred --network-input skitter-rtr.db -o skitter-rtr.db
Loading network from skitter-rtr.db ...
Loading pairs from skitter-rtr.db ...
Computing shortest paths for all pairs...  done.
Failed pairs: 135/10000
Storing sample distances to skitter-rtr.db ...
distances-id 8044582011608803502
Storing congestion data to skitter-rtr.db ...
congestions-dv-id  1324815252155934972
congestions-opt-id 299744725222829449
Computing summary statistics...
sample distances:  min  2.00 max 16.00 med  7.00 avg  7.00 +/-  1.73 count    9865
congestion DV:     min     0 max    70 med     0 avg  0.06 +/-  0.32 count 1218132
congestion OPT:    min     0 max    70 med     0 avg  0.06 +/-  0.32 count 1218132
../compact route --progress --network-input skitter-rtr.db -o skitter-rtr.db
Loading network from skitter-rtr.db ...
Constructing initial routing tables...
Gossiping to compute routing tables... round    19
Storing node data to skitter-rtr.db ...
routing-table-id 6339645757909746051
Storing landmark tables to skitter-rtr.db ...
Computing summary statistics...
TZ table sizes:    min     0 max    29 med     8 avg  8.72 +/-  2.36 count  192245
Announcements sent:min     0 max  1085 med    22 avg 24.13 +/- 14.99 count  192245
../compact forward --progress --routing-table-input skitter-rtr.db -o skitter-rtr.db
Loading routing tables from skitter-rtr.db ...
Loading pairs from skitter-rtr.db ...
Routing sample pairs...  done.
Failed pairs: 135/10000
Storing route data to skitter-rtr.db ...
routes-id 3666254583353997693
Storing congestion data to skitter-rtr.db ...
congestions-id 1789872676116050562
Computing summary statistics...
TZ route length:   min     3 max    22 med    11 avg 10.93 +/-  2.67 count    9865
TZ congestion:     min     0 max  2716 med     0 avg  0.09 +/-  5.00 count 1218132
==============================================

---

Revision 3053 - Directory Listing
Modified Thu Jan 31 17:43:18 2008 UTC (21 months, 3 weeks ago) by jastr

Load the AS-edge equivalent files from DIMES
(it found significantly more edges... 50k, so does take
 take longer to run than the skitter data)

The DIMES version of the all-routers graph isn't
really usable... it's giant, and the only coalescence
they've done is to city-edges (POPs?) but they don't
appear to be uniquely identified in the datasets.
They do give the individual traceroute hops, but I don't
have time to use those.

---

Revision 3051 - Directory Listing
Modified Thu Jan 31 15:54:23 2008 UTC (21 months, 3 weeks ago) by jastr

process the HOT topology data.

plain 'make' will do all of these -- they're small & fast (<1min total)

'make test-as-edges' will do the skitter AS adjacency graphs (a few mintes to run)

'make test-router-edges' will do the full-graph router adjacency.  
I have a data file for only 1e3 pairs, 300+M resulting file, 
and am running a 1e4 pairs set now -- should take only a few more hours.

---

Revision 3050 - Directory Listing
Modified Thu Jan 31 13:58:29 2008 UTC (21 months, 3 weeks ago) by jastr

graphs load fast now.  1000 shortest paths on the full-network link looks like it'll take under an hour to run

---

Revision 3049 - Directory Listing
Modified Thu Jan 31 07:19:23 2008 UTC (21 months, 3 weeks ago) by ctl

 r3931@brainchild:  ctl | 2008-01-31 02:13:27 -0500
 implement random regular graph generation
 

---

Revision 3047 - Directory Listing
Modified Thu Jan 31 00:43:08 2008 UTC (21 months, 3 weeks ago) by ctl

 r3929@brainchild:  ctl | 2008-01-30 19:37:23 -0500
 Fill out the todo list more thoroughly
 

---

Revision 3046 - Directory Listing
Modified Thu Jan 31 00:33:19 2008 UTC (21 months, 3 weeks ago) by ctl

 r3927@brainchild:  ctl | 2008-01-30 19:27:35 -0500
 Count the number of announcements at each node and record it to the database.
 

---

Revision 3045 - Directory Listing
Modified Thu Jan 31 00:13:46 2008 UTC (21 months, 3 weeks ago) by ctl

 r3925@brainchild:  ctl | 2008-01-30 19:07:59 -0500
 Now with even less total incorrectness!
 (Fix predecessor computation for the case of non-unitary edge lengths)
 

---

Revision 3044 - Directory Listing
Modified Wed Jan 30 22:42:43 2008 UTC (21 months, 3 weeks ago) by ctl

 r3920@brainchild:  ctl | 2008-01-30 17:36:50 -0500
 Fix forwarding to go *down* from a landmark to a node instead of up both ways.
 Stomped a particularly pernicious off-by-one bug.
 

---

Revision 3043 - Directory Listing
Modified Wed Jan 30 22:34:02 2008 UTC (21 months, 3 weeks ago) by jastr

start of router-edge loading.   It's running 
now at least... we'll see how long it runs for.

---

Revision 3041 - Directory Listing
Modified Wed Jan 30 21:38:28 2008 UTC (21 months, 3 weeks ago) by jastr

skitter graph runs now

---

Revision 3040 - Directory Listing
Modified Wed Jan 30 19:03:00 2008 UTC (21 months, 3 weeks ago) by ctl

 r3916@brainchild:  ctl | 2008-01-30 13:57:11 -0500
 One-liner change to make shortest-paths measure
 congestion on a directed graph, so it's comparable to forward.
 Template libraries are the bomb.
 

---

Revision 3039 - Directory Listing
Modified Wed Jan 30 19:02:57 2008 UTC (21 months, 3 weeks ago) by ctl

 r3915@brainchild:  ctl | 2008-01-30 13:47:55 -0500
 Bring shortest-paths into this brave new world of save_graph
 so that everything is consistent.
 Create a bunch of views and indices for queries.
 

---

Revision 3038 - Directory Listing
Modified Wed Jan 30 18:12:25 2008 UTC (21 months, 3 weeks ago) by jastr

skitter graph loads, generates pairs, shortest paths, and routes.
still need to fix forwarding

---

Revision 3037 - Directory Listing
Modified Wed Jan 30 06:03:40 2008 UTC (21 months, 3 weeks ago) by ctl

 r3913@brainchild:  ctl | 2008-01-30 00:57:55 -0500
 - add current sql statement to error messages
 - create a bunch of indices and views to help queries go fast
 

---

Revision 3036 - Directory Listing
Modified Wed Jan 30 04:50:25 2008 UTC (21 months, 3 weeks ago) by ctl

 r3911@brainchild:  ctl | 2008-01-29 23:44:39 -0500
 Kill another TODO: correctly filter out failed routes before writing to database.
 (When the routing protocol is correct, which I think it currently is, there
 shouldn't ever be any failed routes on a connected network.  But the network
 can be disconnected if --keep-disconnected is used when generating.
 And the routing protocol may become buggy when changed.)
 

---

Revision 3035 - Directory Listing
Modified Wed Jan 30 04:18:12 2008 UTC (21 months, 3 weeks ago) by ctl

 r3909@brainchild:  ctl | 2008-01-29 23:12:29 -0500
 Use randomization to balance which predecessor is used to get to a landmark.
 

---

Revision 3034 - Directory Listing
Modified Wed Jan 30 01:55:21 2008 UTC (21 months, 3 weeks ago) by ctl

 r3907@brainchild:  ctl | 2008-01-29 20:49:38 -0500
 Awesome, routing to/from the very top level landmark no longer fails.
 I declare the forward subcommand working.
 

---

Revision 3033 - Directory Listing
Modified Wed Jan 30 01:37:28 2008 UTC (21 months, 3 weeks ago) by ctl

 r3904@brainchild:  ctl | 2008-01-29 20:31:45 -0500
 Finally kill subtle bug --- the problem was that landmarks were accepting
 records for themselves at distance 2 (to their neighbors and back).
 There remains a small bug with failed routes, which I think I can fix.
 

---

Revision 3032 - Directory Listing
Modified Wed Jan 30 01:27:57 2008 UTC (21 months, 3 weeks ago) by jastr

skitter loading skeleton

---

Revision 3031 - Directory Listing
Modified Wed Jan 30 00:31:00 2008 UTC (21 months, 3 weeks ago) by ctl

 r3900@brainchild:  ctl | 2008-01-29 19:25:15 -0500
 save landmark id on found path.
 the hope is to figure out this elusive path bug...
 

---

Revision 3016 - Directory Listing
Modified Tue Jan 29 03:48:30 2008 UTC (21 months, 3 weeks ago) by ctl

 r3878@brainchild:  ctl | 2008-01-28 22:42:43 -0500
 Computing congestions and routing paths with summary
 statistics seems to mostly work.
 Except it SEGVs when compiled with -g...
 And avg congestion is mysteriously slightly below avg path length...
 

---

Revision 3015 - Directory Listing
Modified Mon Jan 28 23:00:33 2008 UTC (21 months, 3 weeks ago) by ctl

 r3876@brainchild:  ctl | 2008-01-28 17:54:52 -0500
 Correctly computes TZ path lengths.
 

---

Revision 3014 - Directory Listing
Modified Mon Jan 28 21:23:39 2008 UTC (21 months, 3 weeks ago) by ctl

 r3873@brainchild:  ctl | 2008-01-28 16:17:53 -0500
 Change templates to concrete structures in route.cpp and forward.cpp
 and consequently move around code to make the compiler happy.
 Convert "graph" to "network" everywhere to be more clear.
 Use save_graph/load_graph to save/load sample pairs.
 Fill out metadata tables more completely.
 Can now run whole pipeline on a single database.
 

---

Revision 3013 - Directory Listing
Modified Mon Jan 28 21:23:35 2008 UTC (21 months, 3 weeks ago) by ctl

 r3872@brainchild:  ctl | 2008-01-28 14:22:53 -0500
 Load routing tables into memory.
 

---

Revision 3012 - Directory Listing
Modified Mon Jan 28 18:14:48 2008 UTC (21 months, 3 weeks ago) by ctl

 r3870@brainchild:  ctl | 2008-01-28 13:09:03 -0500
 Table size statistics.
 

---

Revision 3011 - Directory Listing
Modified Mon Jan 28 07:06:31 2008 UTC (21 months, 4 weeks ago) by ctl

 r3867@brainchild:  ctl | 2008-01-28 02:00:50 -0500
 Skeleton of forward.cpp builds, but doesn't do anything.
 

---

Revision 3010 - Directory Listing
Modified Mon Jan 28 07:06:29 2008 UTC (21 months, 4 weeks ago) by ctl

 r3866@brainchild:  ctl | 2008-01-28 01:36:59 -0500
 copy route.cpp as a skeleton for forward command
 

---

Revision 3009 - Directory Listing
Modified Mon Jan 28 06:40:32 2008 UTC (21 months, 4 weeks ago) by ctl

 r3863@brainchild:  ctl | 2008-01-28 01:32:55 -0500
 Stomp a bunch of subtle bugs with gossip().
 Finally a version which seems to produce valid minimal TZ tables.
 

---

Revision 3008 - Directory Listing
Modified Mon Jan 28 06:40:30 2008 UTC (21 months, 4 weeks ago) by ctl

 r3862@brainchild:  ctl | 2008-01-27 23:39:12 -0500
 First compiling version which actually does TZ routing.
 

---

Revision 3007 - Directory Listing
Modified Mon Jan 28 00:32:30 2008 UTC (21 months, 4 weeks ago) by ctl

 r3860@brainchild:  ctl | 2008-01-27 19:26:51 -0500
 Now storing landmark table to database
 

---

Revision 3006 - Directory Listing
Modified Sun Jan 27 23:41:36 2008 UTC (21 months, 4 weeks ago) by ctl

 r3858@brainchild:  ctl | 2008-01-27 18:35:50 -0500
 ignore precompiled headers and core file
 

---

Revision 3005 - Directory Listing
Modified Sun Jan 27 23:40:31 2008 UTC (21 months, 4 weeks ago) by ctl

 r3856@brainchild:  ctl | 2008-01-27 18:34:51 -0500
 Vertex and edge properties work
 

---

Revision 3004 - Directory Listing
Modified Sun Jan 27 08:34:59 2008 UTC (21 months, 4 weeks ago) by ctl

 r3854@brainchild:  ctl | 2008-01-27 03:26:32 -0500
 saving node properties to database
 

---

Revision 3003 - Directory Listing
Modified Sun Jan 27 00:51:18 2008 UTC (21 months, 4 weeks ago) by ctl

 r3852@brainchild:  ctl | 2008-01-26 19:45:42 -0500
 trim away disconnected nodes when generating the graph.
 

---

Revision 3002 - Directory Listing
Modified Sat Jan 26 23:29:02 2008 UTC (21 months, 4 weeks ago) by ctl

 r3850@brainchild:  ctl | 2008-01-26 18:18:08 -0500
 - improve options description
 - fix bug of looking at predecessor map for infinite-distance nodes
 

---

Revision 3001 - Directory Listing
Modified Sat Jan 26 22:32:08 2008 UTC (21 months, 4 weeks ago) by ctl

 r3848@brainchild:  ctl | 2008-01-26 17:26:24 -0500
 Compute basic landmark table.
 

---

Revision 3000 - Directory Listing
Modified Sat Jan 26 09:33:45 2008 UTC (21 months, 4 weeks ago) by ctl

 r3837@brainchild:  ctl | 2008-01-26 04:28:06 -0500
 Define routing tables and levels.
 

---

Revision 2999 - Directory Listing
Modified Sat Jan 26 09:33:42 2008 UTC (21 months, 4 weeks ago) by ctl

 r3836@brainchild:  ctl | 2008-01-24 23:58:49 -0500
 - load undirected graph as directed
 - allocate routing tables
 

---

Revision 2990 - Directory Listing
Modified Fri Jan 25 03:32:10 2008 UTC (22 months ago) by ctl

 r3830@brainchild:  ctl | 2008-01-24 22:26:36 -0500
 - compute both OPT and distance-vector shortest-paths congestions
 - print progress report
 

---

Revision 2985 - Directory Listing
Modified Thu Jan 24 16:29:14 2008 UTC (22 months ago) by ctl

 r3828@brainchild:  ctl | 2008-01-24 11:23:42 -0500
 A number of minor fixes and reorgs,
 and a skeleton of route.cpp
 

---

Revision 2984 - Directory Listing
Modified Thu Jan 24 11:58:58 2008 UTC (22 months ago) by ctl

 r3824@brainchild:  ctl | 2008-01-24 06:51:37 -0500
 Computes and stores summary statistics about output.
 Uses a fair bit of memory and time overhead though.
 

---

Revision 2983 - Directory Listing
Modified Thu Jan 24 11:58:56 2008 UTC (22 months ago) by ctl

 r3823@brainchild:  ctl | 2008-01-24 04:57:51 -0500
 Make load_graph more sane in semantics.
 

---

Revision 2982 - Directory Listing
Modified Thu Jan 24 11:58:53 2008 UTC (22 months ago) by ctl

 r3822@brainchild:  ctl | 2008-01-24 04:11:37 -0500
 - Initialize unbiased variable
 - change program name to "compact"
 

---

Revision 2981 - Directory Listing
Modified Thu Jan 24 09:13:22 2008 UTC (22 months ago) by ctl

 r3814@brainchild:  ctl | 2008-01-24 04:07:20 -0500
 Use Dijkstra's algorithm and randomization to avoid bias in shortest path selection
 towards lower-indexed edges, which causes more extreme congestion distributions.
 Both add time cost.  Dijkstra's algorithm by itself eliminates most bias, but
 randomization still helps.
 

---

Revision 2980 - Directory Listing
Modified Thu Jan 24 09:13:19 2008 UTC (22 months ago) by ctl

 r3813@brainchild:  ctl | 2008-01-24 02:33:42 -0500
 Move options structure to top.
 

---

Revision 2979 - Directory Listing
Modified Thu Jan 24 09:13:15 2008 UTC (22 months ago) by ctl

 r3812@brainchild:  ctl | 2008-01-24 02:32:31 -0500
 Correctly computes congestion values using a new BFS visitor.
 

---

Revision 2978 - Directory Listing
Modified Thu Jan 24 09:13:11 2008 UTC (22 months ago) by ctl

 r3811@brainchild:  ctl | 2008-01-23 23:01:58 -0500
 Avoid uninitialized value warnings;
 add explicit parameters to BFS search for shortest pathsl
 

---

Revision 2974 - Directory Listing
Modified Wed Jan 23 11:07:51 2008 UTC (22 months ago) by ctl

 r3792@brainchild:  ctl | 2008-01-23 06:02:09 -0500
 Seems to successfully compute shortest paths.
 Could use some optimization to avoid excessive memory allocation/deallocation.
 Spurious uninitialized variable warnings have to go.
 

---

Revision 2973 - Directory Listing
Modified Wed Jan 23 11:07:43 2008 UTC (22 months ago) by ctl

 r3791@brainchild:  ctl | 2008-01-23 02:57:32 -0500
 - pairs generation works
 - improve sqlite iterator interface
 

---

Revision 2957 - Directory Listing
Modified Thu Jan 17 21:59:37 2008 UTC (22 months, 1 week ago) by ctl

 r3789@brainchild:  ctl | 2008-01-17 16:54:21 -0500
 add skeleton of generate-pairs command
 

---

Revision 2956 - Directory Listing
Modified Thu Jan 17 21:47:44 2008 UTC (22 months, 1 week ago) by ctl

 r3780@brainchild:  ctl | 2008-01-17 04:57:44 -0500
 save/load graphs working
 

---

Revision 2955 - Directory Listing
Modified Thu Jan 17 21:47:40 2008 UTC (22 months, 1 week ago) by ctl

 r3779@brainchild:  ctl | 2008-01-17 04:56:25 -0500
 save/load graphs working

---

Revision 2954 - Directory Listing
Modified Thu Jan 17 21:47:37 2008 UTC (22 months, 1 week ago) by ctl

 r3778@brainchild:  ctl | 2008-01-15 03:48:46 -0500
 generates erdos-renyi graphs correctly.
 

---

Revision 2953 - Directory Listing
Modified Thu Jan 17 21:47:35 2008 UTC (22 months, 1 week ago) by ctl

 r3777@brainchild:  ctl | 2008-01-15 00:52:31 -0500
 fix virtual methods
 

---

Revision 2952 - Directory Listing
Modified Thu Jan 17 21:47:34 2008 UTC (22 months, 1 week ago) by ctl

 r3776@brainchild:  ctl | 2008-01-14 20:15:49 -0500
 subcommand_options class created and works.
 makefile generates .d dependency files.
 

---

Revision 2951 - Directory Listing
Modified Thu Jan 17 21:47:32 2008 UTC (22 months, 1 week ago) by ctl

 r3775@brainchild:  ctl | 2008-01-11 17:41:37 -0500
 ignore executable file
 

---

Revision 2950 - Directory Listing
Modified Thu Jan 17 21:47:30 2008 UTC (22 months, 1 week ago) by ctl

 r3774@brainchild:  ctl | 2008-01-11 17:38:49 -0500
 reorganize as subcommands of a single executable
 

---

Revision 2949 - Directory Listing
Modified Thu Jan 17 21:47:28 2008 UTC (22 months, 1 week ago) by ctl

 r3773@brainchild:  ctl | 2008-01-11 16:10:16 -0500
 (checkpoint to copy)

---

Revision 2895 - Directory Listing
Modified Tue Dec 11 01:05:29 2007 UTC (23 months, 2 weeks ago) by ctl

 r3663@brainchild:  ctl | 2007-12-10 20:00:14 -0500
 implement dynamically-typed arguments to enable dynamically generic manipulators.
 

---

Revision 2894 - Directory Listing
Modified Tue Dec 11 01:05:19 2007 UTC (23 months, 2 weeks ago) by ctl

 r3662@brainchild:  ctl | 2007-12-10 05:37:41 -0500
 implement rows()
 

---

Revision 2893 - Directory Listing
Modified Tue Dec 11 01:05:13 2007 UTC (23 months, 2 weeks ago) by ctl

 r3661@brainchild:  ctl | 2007-12-10 05:27:17 -0500
 Implement a STL iterator interface on stmt.
 

---

Revision 2892 - Directory Listing
Modified Tue Dec 11 01:05:07 2007 UTC (23 months, 2 weeks ago) by ctl

 r3660@brainchild:  ctl | 2007-12-10 03:35:41 -0500
 Fix mixed exec/row bugs by adding explicit state variable to stmt class.
 

---

Revision 2891 - Directory Listing
Modified Tue Dec 11 01:04:54 2007 UTC (23 months, 2 weeks ago) by ctl

 r3659@brainchild:  ctl | 2007-12-10 02:41:35 -0500
 add $Id$
 

---

Revision 2890 - Directory Listing
Modified Tue Dec 11 01:04:50 2007 UTC (23 months, 2 weeks ago) by ctl

 r3658@brainchild:  ctl | 2007-12-10 02:39:22 -0500
 Rename .C/.H to .cpp/.hpp at advice of -c sipb.
 

---

Revision 2889 - Directory Listing
Modified Tue Dec 11 01:04:39 2007 UTC (23 months, 2 weeks ago) by ctl

 r3657@brainchild:  ctl | 2007-12-10 02:37:29 -0500
 Implement all argument binding and row retrieval functions.
 Fix bugs.
 Some known bugs remain.
 

---

Revision 2888 - Directory Listing
Modified Tue Dec 11 01:04:35 2007 UTC (23 months, 2 weeks ago) by ctl

 r3656@brainchild:  ctl | 2007-12-08 03:59:30 -0500
 checkpoint much old code before air flight
 

---

Revision 2887 - Directory Listing
Modified Tue Dec 11 01:04:28 2007 UTC (23 months, 2 weeks ago) by ctl

 r3655@brainchild:  ctl | 2007-12-08 03:58:23 -0500
 checkpoint old changes before air flight

---

Revision 2704 - Directory Listing
Modified Sat Aug 4 06:35:38 2007 UTC (2 years, 3 months ago) by ctl

 r3361@brainchild:  ctl | 2007-08-04 02:37:33 -0400
 Do the same for max-stretch.
 

---

Revision 2701 - Directory Listing
Modified Sat Aug 4 06:29:24 2007 UTC (2 years, 3 months ago) by ctl

 r3358@brainchild:  ctl | 2007-08-04 02:31:17 -0400
 Combine congestion graph.
 

---

Revision 2699 - Directory Listing
Modified Sat Aug 4 06:17:02 2007 UTC (2 years, 3 months ago) by ctl

 r3356@brainchild:  ctl | 2007-08-04 02:18:55 -0400
 address bryan's nitpicks
 

---

Revision 2698 - Directory Listing
Modified Sat Aug 4 05:58:43 2007 UTC (2 years, 3 months ago) by ctl

 r3352@brainchild:  ctl | 2007-08-04 02:00:38 -0400
 table size plots
 

---

Revision 2697 - Directory Listing
Modified Sat Aug 4 05:53:44 2007 UTC (2 years, 3 months ago) by jastr

pile of skitter & dimes resuls

---

Revision 2695 - Directory Listing
Modified Sat Aug 4 05:40:30 2007 UTC (2 years, 3 months ago) by ctl

 r3347@brainchild:  ctl | 2007-08-04 01:41:47 -0400
 Add some -vs-budget graphs, update source.
 

---

Revision 2694 - Directory Listing
Modified Sat Aug 4 05:40:27 2007 UTC (2 years, 3 months ago) by ctl

 r3346@brainchild:  ctl | 2007-08-04 01:30:38 -0400
 A bunch of not-so-hot charts.
 

---

Revision 2693 - Directory Listing
Modified Sat Aug 4 05:39:59 2007 UTC (2 years, 3 months ago) by ctl

 r3345@brainchild:  ctl | 2007-08-04 01:21:20 -0400
 Check in a big pile of data.
 

---

Revision 2691 - Directory Listing
Modified Sat Aug 4 04:03:11 2007 UTC (2 years, 3 months ago) by ctl

 r3339@brainchild:  ctl | 2007-08-04 00:05:01 -0400
 Fix a bunch of dumb bugs with optimized statistics computations.
 

---

Revision 2690 - Directory Listing
Modified Sat Aug 4 04:03:08 2007 UTC (2 years, 3 months ago) by ctl

 r3338@brainchild:  ctl | 2007-08-03 22:17:32 -0400
 Read in data files.
 

---

Revision 2686 - Directory Listing
Modified Sat Aug 4 00:19:21 2007 UTC (2 years, 3 months ago) by ctl

 r3336@brainchild:  ctl | 2007-08-03 20:21:00 -0400
 Add terrible harnesses.
 

---

Revision 2685 - Directory Listing
Modified Sat Aug 4 00:09:10 2007 UTC (2 years, 3 months ago) by ctl

 r3331@brainchild:  ctl | 2007-08-03 20:10:16 -0400
 Fix bizarre graph loading bug.
 

---

Revision 2684 - Directory Listing
Modified Fri Aug 3 22:40:53 2007 UTC (2 years, 3 months ago) by jastr

generate dimes and skiter again

---

Revision 2682 - Directory Listing
Modified Fri Aug 3 22:13:28 2007 UTC (2 years, 3 months ago) by ctl

 r3325@brainchild:  ctl | 2007-08-03 18:15:00 -0400
 Rename outputs of LSL.
 

---

Revision 2677 - Directory Listing
Modified Fri Aug 3 19:41:58 2007 UTC (2 years, 3 months ago) by ctl

 r3319@brainchild:  ctl | 2007-08-03 15:42:56 -0400
 Other half of separation of workload generation and simulation: load the workload and simulate it.
 

---

Revision 2676 - Directory Listing
Modified Fri Aug 3 19:41:08 2007 UTC (2 years, 3 months ago) by ctl

 r3318@brainchild:  ctl | 2007-08-03 14:36:28 -0400
 Generate separate congestion and statistics.
 

---

Revision 2672 - Directory Listing
Modified Fri Aug 3 17:53:01 2007 UTC (2 years, 3 months ago) by ctl

 r3311@brainchild:  ctl | 2007-08-03 13:27:15 -0400
 Use much less memory to generate sample pairs.
 

---

Revision 2671 - Directory Listing
Modified Fri Aug 3 17:50:00 2007 UTC (2 years, 3 months ago) by ctl

 r3310@brainchild:  ctl | 2007-08-03 12:30:58 -0400
 Support gzip files properly.
 

---

Revision 2666 - Directory Listing
Modified Fri Aug 3 08:09:11 2007 UTC (2 years, 3 months ago) by ctl

 r3307@brainchild:  ctl | 2007-08-03 04:10:56 -0400
 Separate out graph, sampling, and shortest-paths generation into a separate program.
 

---

Revision 2665 - Directory Listing
Modified Fri Aug 3 08:09:07 2007 UTC (2 years, 3 months ago) by ctl

 r3306@brainchild:  ctl | 2007-08-03 03:34:33 -0400
 Move old data out of the way.
 

---

Revision 2664 - Directory Listing
Modified Fri Aug 3 03:58:37 2007 UTC (2 years, 3 months ago) by ctl

 r3304@brainchild:  ctl | 2007-08-03 00:00:29 -0400
 Generate scale-free graphs by the preferential attachment method.
 

---

Revision 2663 - Directory Listing
Modified Fri Aug 3 03:28:32 2007 UTC (2 years, 3 months ago) by ctl

 r3302@brainchild:  ctl | 2007-08-02 23:30:23 -0400
 Per-node congestion ratio is a useless statistic, and it causes divide-by-zero errors.
 

---

Revision 2662 - Directory Listing
Modified Fri Aug 3 03:10:10 2007 UTC (2 years, 3 months ago) by ctl

 r3299@brainchild:  ctl | 2007-08-02 23:11:16 -0400
 1. Implement measurement of "optimal" congestion.  (Not actually optimal, but
 measured based on congestion of shortest-paths routes, so good baseline.)
 2. Fix bugs with non-shortcutting version.
 

---

Revision 2661 - Directory Listing
Modified Fri Aug 3 03:09:28 2007 UTC (2 years, 3 months ago) by ctl

---

Revision 2659 - Directory Listing
Modified Thu Aug 2 23:13:39 2007 UTC (2 years, 3 months ago) by jastr

include the internet topology generator

---

Revision 2658 - Directory Listing
Modified Thu Aug 2 20:51:42 2007 UTC (2 years, 3 months ago) by jastr

dimes graph

---

Revision 2657 - Directory Listing
Modified Thu Aug 2 19:05:08 2007 UTC (2 years, 3 months ago) by ctl

 r3289@brainchild:  ctl | 2007-08-02 15:06:39 -0400
 Implemented bandwidth budget limited routing table growth.
 

---

Revision 2656 - Directory Listing
Modified Thu Aug 2 19:05:06 2007 UTC (2 years, 3 months ago) by ctl

 r3288@brainchild:  ctl | 2007-08-02 14:27:52 -0400
 Improve the statistical reporting format more.
 

---

Revision 2655 - Directory Listing
Modified Thu Aug 2 19:05:03 2007 UTC (2 years, 3 months ago) by ctl

 r3287@brainchild:  ctl | 2007-08-02 14:16:42 -0400
 Improve the statistical reporting format a bit.
 

---

Revision 2654 - Directory Listing
Modified Thu Aug 2 18:34:30 2007 UTC (2 years, 3 months ago) by jastr

skitter graph construction

---

Revision 2653 - Directory Listing
Modified Thu Aug 2 17:59:35 2007 UTC (2 years, 3 months ago) by ctl

 r3283@brainchild:  ctl | 2007-08-02 14:01:28 -0400
 Implement explicit message passing between nodes instead of having
 nodes inspect each others' tables directly.  This is the first big
 step towards bandwidth-budget-based tables.
 

---

Revision 2649 - Directory Listing
Modified Wed Aug 1 22:20:04 2007 UTC (2 years, 3 months ago) by ctl

 r3280@brainchild:  ctl | 2007-08-01 18:21:56 -0400
 Boilerplate for bandwidth budget code.
 

---

Revision 2648 - Directory Listing
Modified Wed Aug 1 20:29:24 2007 UTC (2 years, 3 months ago) by ctl

 r3277@brainchild:  ctl | 2007-08-01 16:31:19 -0400
 Apply shortcut optimization.
 

---

Revision 2645 - Directory Listing
Modified Tue Jul 31 23:36:38 2007 UTC (2 years, 3 months ago) by ctl

 r3274@brainchild:  ctl | 2007-07-31 19:38:35 -0400
 Implement mesh graph generator.
 

---

Revision 2644 - Directory Listing
Modified Tue Jul 31 21:26:25 2007 UTC (2 years, 3 months ago) by ctl

 r3272@brainchild:  ctl | 2007-07-31 17:28:22 -0400
 Update the minimal self-documentation
 

---

Revision 2643 - Directory Listing
Modified Tue Jul 31 21:21:45 2007 UTC (2 years, 3 months ago) by ctl

 r3269@brainchild:  ctl | 2007-07-31 17:23:13 -0400
 Measure and report congestion.
 

---

Revision 2641 - Directory Listing
Modified Tue Jul 31 20:54:13 2007 UTC (2 years, 3 months ago) by ctl

 r3267@brainchild:  ctl | 2007-07-31 16:56:09 -0400
 Finally correctly finds paths using landmarks.
 

---

Revision 2640 - Directory Listing
Modified Tue Jul 31 04:22:54 2007 UTC (2 years, 3 months ago) by ctl

 r3265@brainchild:  ctl | 2007-07-31 00:24:45 -0400
 Implement fast C inner loop for shortest paths.
 

---

Revision 2638 - Directory Listing
Modified Tue Jul 31 03:05:00 2007 UTC (2 years, 3 months ago) by ctl

 r3245@brainchild (orig r2624):  ctl | 2007-07-30 19:02:57 -0400
  r3243@brainchild:  ctl | 2007-07-30 19:04:40 -0400
  Boilerplate for C optimization.
  
 

---

Revision 2637 - Directory Listing
Modified Tue Jul 31 03:04:55 2007 UTC (2 years, 3 months ago) by ctl

 r3244@brainchild (orig r2623):  ctl | 2007-07-30 19:02:54 -0400
  r3242@brainchild:  ctl | 2007-07-30 18:51:31 -0400
  Fairly fast implementation of single-source shortest paths, but needs improvement.
  
 

---

Revision 2636 - Directory Listing
Modified Tue Jul 31 03:04:50 2007 UTC (2 years, 3 months ago) by ctl

 r3241@brainchild (orig r2622):  ctl | 2007-07-27 13:05:18 -0400
  r3238@brainchild:  ctl | 2007-07-27 00:02:07 -0400
  Basic implementation of a thorup-zuick-like protocol.
  
 

---

Revision 2635 - Directory Listing
Modified Tue Jul 31 03:04:46 2007 UTC (2 years, 3 months ago) by ctl

 r3240@brainchild (orig r2621):  ctl | 2007-07-27 13:05:14 -0400
  r3237@brainchild:  ctl | 2007-07-26 22:15:01 -0400
  checkpoint earlier changes.
  
 

---

Revision 2634 - Directory Listing
Modified Tue Jul 31 03:04:39 2007 UTC (2 years, 3 months ago) by ctl

 r2957@brainchild (orig r2605):  ctl | 2007-06-27 15:18:00 -0400
  r2949@brainchild:  ctl | 2007-06-26 14:51:50 -0400
  boilerplate works again --- no routing yet.
  
 

---

Revision 2633 - Directory Listing
Modified Tue Jul 31 03:04:35 2007 UTC (2 years, 3 months ago) by ctl

 r2956@brainchild (orig r2604):  ctl | 2007-06-27 15:17:55 -0400
  r2948@brainchild:  ctl | 2007-06-26 14:05:12 -0400
  copy and delete all irrelevant stuff.
  
 

---

Revision 2632 - Directory Listing
Modified Tue Jul 31 03:04:30 2007 UTC (2 years, 3 months ago) by ctl

 r2955@brainchild (orig r2603):  ctl | 2007-06-27 15:17:49 -0400
  r2947@brainchild:  ctl | 2007-06-26 09:50:41 -0400
  random graph generation supported, all-pairs distances faster.
  
 

---

Revision 2631 - Directory Listing
Modified Tue Jul 31 03:04:26 2007 UTC (2 years, 3 months ago) by ctl

 r2954@brainchild (orig r2602):  ctl | 2007-06-27 15:17:44 -0400
  r2946@brainchild:  ctl | 2007-06-17 17:50:14 -0400
  All-pairs distances, summary statistics
  
 

---

Revision 2630 - Directory Listing
Modified Tue Jul 31 03:04:22 2007 UTC (2 years, 3 months ago) by ctl

 r2953@brainchild (orig r2601):  ctl | 2007-06-27 15:17:28 -0400
  r2945@brainchild:  ctl | 2007-06-16 18:59:03 -0400
  Cut copied source down to the relevant graph generation parts.
  
 

---

Revision 2494 - Directory Listing
Modified Thu May 24 22:04:44 2007 UTC (2 years, 6 months ago) by ctl

Merge in all changes from trunk, including merge hell in naming/named (not tested)

---

Revision 2359 - Directory Listing
Modified Tue May 1 00:05:52 2007 UTC (2 years, 6 months ago) by ctl

Data for small-world graph (2D plane, average degree 5).
Simulation only makes it up to 100k nodes before running out
of memory.  Most plausible fitting line for average stretch is
~0.6 N^0.24.
Why 0.24?  I have no idea.
.

---

Revision 2355 - Directory Listing
Modified Mon Apr 30 00:55:19 2007 UTC (2 years, 6 months ago) by ctl

Implement new fast algorithm to generate a close approximation of a random small-world graph.

---

Revision 2354 - Directory Listing
Modified Sun Apr 29 22:12:27 2007 UTC (2 years, 6 months ago) by ctl

Implement (slow) random small world graph generator.

---

Revision 2353 - Directory Listing
Modified Sun Apr 29 18:58:06 2007 UTC (2 years, 6 months ago) by ctl

Fill out data with low-N test runs.
Average stretch is (curiously) very well fitted by 0.5 * N^0.28.
Why 0.5 and 0.28?  I have no idea.

---

Revision 2352 - Directory Listing
Modified Sun Apr 29 18:37:51 2007 UTC (2 years, 6 months ago) by ctl

Data from runs of the simulator on degree-5 regular graphs.

---

Revision 2351 - Directory Listing
Added Sun Apr 29 06:30:19 2007 UTC (2 years, 6 months ago) by ctl

UIP simulator.