[CUWiN-Dev] routeviz patch
Bill Comisky
bcomisky at pobox.com
Fri Aug 5 17:29:58 CDT 2005
[Note: my ISPs mailserver has decided it doesn't like to send mail to this
list anymore, so I'm using SMTP from my local box. There may be
some dupes stuck in the queue, ignore them if they show up.]
Attached is a patch to the routeviz code in src/viz. Dave, I mostly followed
your algorithm with a few changes:
- the cache file is only read at startup
- the generation is incremented only when the HSLS vizlinks file is read
The routeviz.conf file has two new variables:
new_metric_weight=.2
node_max_age=360
Where link metrics are updated like:
metric = new_metric*new_metric_weight + old_metric*(1-new_metric_weight)
And nodes are "retired" when:
vnet->generation - vnode->generation > node_max_age
So node_max_age has units of generations rather than seconds, which made it
easier to test, but it could easily be switched if desired. The idle time
between generations is compiled in, currently 10 secs.
Other significant changes:
- Instead of assigning forward & reverse links simultaneously to the most
recently read value, they are assigned individually when read. A new
combined_link_metric() function is called to return the metric for a
link pair. Right now it averages the metrics (will halve any
unidirectional link metrics). I actually tried drawing both forward &
reverse links side by side, but a lot of time it looked messy.. it
couldn't offset the parallel lines the right amount due to the screen
resolution most of the time.
- I made the remove_node() function remove all links from other nodes to
the removed node. I added some nfree()'s where I thought they were
needed, and it did make a difference in the nmalloc_pool_report_all()
output.
It seems to work the way I expect it to. Let me know if there are any problems.
Someone with more C experience should probably give it a once over (& check the
nfree()s in remove_node()).
I still often get layouts that are difficult to read: all nodes in a line
and/or too close together. I've tweaked my routeviz.conf file for our testbed
to increase the lengths, which helps.
One last thing, I tested things by manually editing the vizlinks file to remove
nodes/links. I noticed that in practice a node will stay in the vizlinks file
after I power it down. How long does HSLS keep the linkstate for nodes from
which it receives no data?
Bill
--
Bill Comisky
bcomisky at pobox.com
On Tue, 26 Jul 2005, David Young wrote:
> On Mon, Jul 25, 2005 at 01:54:33PM -0500, Bill Comisky wrote:
> >
> > I had noticed before that I had to delete the
> > /var/db/routeviz_layout.cache file in order for it to update properly
> > from
> > /var/db/vizlinks. After looking in the code, it appears that the
> > rv_layout_net() function is called to read and write the cache file after
> > the parse_hsls_log() function is called. The rv_read_cache_file()
> > function parses and configures link metrics in addition to node
> > positions,
> > so it writes over the data from the parse_hsls_log() call. So once a
> > link makes it into the cache file, it's metric is static unless the
> > cache file is deleted.
> >
> > Also, I don't see how node/link info would ever get removed from the vnet
> > data structure if nodes/links dissappear from the vizlinks file.
> >
> > Correct me if I missed something..
>
> That sounds to me like a serious bug. I don't think it will be very
> hard to fix. I believe this is the correct algorithm:
>
> Initialize:
>
> initialize a global "generation" number, N <- 0
>
> Repeat every W seconds:
>
> 1 if the cache exists, read the cache, first; store the cached
> metric in the vlinks; read the generation number from the cache
>
> 2 increase the global generation number, N <- N + 1
>
> 3 if and only if the "vizlinks" file exists and it is newer
> than the cache:
>
> 3b read the vizlinks file
>
> 3b1 label all of the linkstates read from vizlinks
> with the generation number
>
> 3b2 do not overwrite the cached metric, but
> "scoot" it toward the vizlinks metric---i.e.,
> metric <- .9 * metric(cache) + .1 *
> metric(vizlinks)
>
> I believe this will help avoid injecting
> new energy into the "springs" system that
> will keep the system from converging [1]
>
> 4 delete vlinks / vnodes that are labeled with a generation-number
> that is very far in the past, i.e., W * (N - N(vlink)) > 1 hour.
>
> 5 label as "down" all vlinks / vnodes that remain, if their
> generation-number label is not equal to N.
>
> 6 re-run the springs simulation for "a while" (I don't remember
> how this works---does it stop when no/low motion is reached?)
>
> 7 re-draw
>
> 8 write all of the links & nodes back to the cache file; write
> the generation number to the cache file
>
> Dave
>
> [1] This is one of three recommendations for improving routeviz,
> especially the convergence/stability, that my friend Dave Healy and
> I came up with in a brainstorming session. I will remind myself of
> the other two, which I have written down, and send them to the list.
>
> --
> David Young OJC Technologies
> dyoung at ojctech.com Urbana, IL * (217) 278-3933
> _______________________________________________
> CU-Wireless-Dev mailing list
> CU-Wireless-Dev at lists.cuwireless.net
> http://lists.chambana.net/cgi-bin/listinfo/cu-wireless-dev
>
-------------- next part --------------
=== conf/parse.y
==================================================================
--- conf/parse.y (/cuw/trunk/src/viz) (revision 3016)
+++ conf/parse.y (/cuw/branches/cnt/src/viz) (local)
@@ -74,9 +74,9 @@
%token CONTROLFGC_TOK DEBUG_TICKS ELECTRON_CONSTANT EQ_TOK FONTSIZE_TOK
%token HSLS_TOK LABELC_TOK LABELF_TOK LABELOLC_TOK LAYOUT_TICKS
%token LAYOUT_TIMESTEP LINKW_TOK LONGEST_NATURAL_SPRING MAX_ZOOM_TOK
-%token MODE_TOK NODEB_TOK NODEC_TOK NODEICC_TOK NODEOLC_TOK
-%token NODESC_TOK NODES_TOK NO_DRAG NO_EDGE NO_ELECTRONS NO_SPRINGS
-%token PANAMOUNT_TOK RESAMPLE_TOK SHORTEST_NATURAL_SPRING
+%token MODE_TOK NODEB_TOK NODEC_TOK NODEICC_TOK NODEOLC_TOK NODEMAXAGE_TOK
+%token NEWMETRICWEIGHT_TOK NODESC_TOK NODES_TOK NO_DRAG NO_EDGE NO_ELECTRONS
+%token NO_SPRINGS PANAMOUNT_TOK RESAMPLE_TOK SHORTEST_NATURAL_SPRING
%token SPRING_CONSTANT STANDARD_MASS TOO_CLOSE TOPOFILE_TOK
%token ULLRLATLONG_TOK VIEWPORTSIZE_TOK ZOOMAMOUNT_TOK
@@ -110,6 +110,8 @@
| labelcolor
| labelolcolor
| max_zoom
+| new_metric_weight
+| node_max_age
| nodeborder
| nodecolor
| nodeselfcolor
@@ -242,6 +244,20 @@
vnet->max_zoom = $3;
}
+new_metric_weight:
+ NEWMETRICWEIGHT_TOK EQ_TOK REAL
+ {
+ vnet->new_metric_weight = $3;
+ }
+ ;
+
+node_max_age:
+ NODEMAXAGE_TOK EQ_TOK INTEGER
+ {
+ vnet->node_max_age = $3;
+ }
+ ;
+
nodecolor:
NODEC_TOK EQ_TOK INTEGER INTEGER INTEGER
{
=== conf/scan.l
==================================================================
--- conf/scan.l (/cuw/trunk/src/viz) (revision 3016)
+++ conf/scan.l (/cuw/branches/cnt/src/viz) (local)
@@ -87,6 +87,8 @@
node_iccolor return NODEICC_TOK;
node_olcolor return NODEOLC_TOK;
node_size return NODES_TOK;
+node_max_age return NODEMAXAGE_TOK;
+new_metric_weight return NEWMETRICWEIGHT_TOK;
pan_amount return PANAMOUNT_TOK;
parsermode return MODE_TOK;
resample return RESAMPLE_TOK;
=== daemon/routevizd.c
==================================================================
--- daemon/routevizd.c (/cuw/trunk/src/viz) (revision 3016)
+++ daemon/routevizd.c (/cuw/branches/cnt/src/viz) (local)
@@ -57,6 +57,7 @@
#include "parser/defs.h"
LOGLIB_SINK_DECL(rv_daemon);
+LOGLIB_SINK_SHORT_DEFN(rv_daemon, all);
#define RV_CACHE_UMASK 0777
#define RV_DELAY 10 /* in seconds, idle time between iterations */
@@ -188,26 +189,23 @@
rv_node_t *vnode;
rv_link_t *vlink;
rv_alias_t *alias;
- FILE *f;
-
- if ((f = fopen("/var/tmp/viz.debug", "w")) == NULL) {
- loglib_warn("%s: fopen", __func__);
- return;
- }
+ LOGLIB_LOG(&log_rv_daemon, "Generation = %u", vnet->generation);
SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
- fprintf(f, "Node: %s\n", vnode->label);
- fprintf(f, "\tAliases: ");
+
+ LOGLIB_LOG(&log_rv_daemon, "Node: %s @ generation %u", vnode->label,
+ vnode->generation);
+ LOGLIB_LOG(&log_rv_daemon, "Aliases:");
SLIST_FOREACH(alias, &vnode->aliases, aliases)
- fprintf(f, "%s ", alias->label);
- fprintf(f, "\n");
- fprintf(f, "\tLinks: ");
+ LOGLIB_LOG(&log_rv_daemon, "%s", alias->label);
+ LOGLIB_LOG(&log_rv_daemon, "Links:");
SLIST_FOREACH(vlink, &vnode->links, links)
- fprintf(f, "%s ", vlink->dest->label);
- fprintf(f, "\n");
+ LOGLIB_LOG(&log_rv_daemon, "%s @ %u\t%f", vlink->dest->label,
+ vlink->generation, vlink->metric);
}
- fclose(f);
+ nmalloc_pool_report_all(log_printer, NULL);
+
#endif
}
@@ -215,13 +213,22 @@
main_loop(rv_net_t *vnet, struct opts *o)
{
struct stat st;
- time_t last_seen = 0;
+ time_t last_seen;
u_int wait;
int first_pass = 1;
+ if (stat(vnet->cachefile, &st) != 0) {
+ last_seen = 0;
+ } else {
+ last_seen = st.st_mtime;
+ LOGLIB_LOG(&log_rv_daemon, "Reading cache file");
+ rv_layout_read_cache(vnet);
+ debug_dump(vnet);
+ }
+
LOGLIB_LOG(&log_rv_daemon, "Entering main loop");
+ for (;;) {
- for (;;) {
if (stat(vnet->topofile, &st) != 0) {
switch (errno) {
case ENOENT:
@@ -242,12 +249,16 @@
}
last_seen = st.st_mtime;
+ vnet->generation += 1;
+ LOGLIB_LOG(&log_rv_daemon, "Parsing HSLS log.");
vnet = parse_hsls_log(vnet);
+ retire_nodes(vnet);
+
LOGLIB_LOG(&log_rv_daemon, "Doing net layout.");
vnet = rv_layout_net(vnet);
-
+
if ((o->o_flags & OPT_F_LAYOUT) == 0) {
LOGLIB_LOG(&log_rv_daemon, "Populating background.");
populate_background(vnet);
@@ -260,13 +271,12 @@
first_pass = 0;
}
+ debug_dump(vnet);
+
bottom:
if ((o->o_flags & OPT_F_ONE_SHOT) != 0)
return;
- nmalloc_pool_report_all(log_printer, NULL);
-
- debug_dump(vnet);
LOGLIB_LOG(&log_rv_daemon, "Sleeping for %i seconds.", RV_DELAY);
for (wait = RV_DELAY; wait > 0; wait = sleep(wait));
@@ -324,6 +334,7 @@
errx(EXIT_FAILURE, "%s: could not start logging", __func__);
vnet = config_net_from_file(o.o_config_file, 1);
+ vnet->generation = 0;
nfree(o.o_config_file);
create_dirs(vnet->cache_path, vnet->max_zoom);
=== parser/parse.y
==================================================================
--- parser/parse.y (/cuw/trunk/src/viz) (revision 3016)
+++ parser/parse.y (/cuw/branches/cnt/src/viz) (local)
@@ -149,7 +149,7 @@
"parsed metric %d on %s %s (etx %f, temperature %f)",
metric, n1, n2, etx, temperature);
- config_link(vnet, n1, n2, temperature, type);
+ config_link(vnet, n1, n2, temperature, type, vnet->generation);
}
%}
=== routeviz.conf
==================================================================
--- routeviz.conf (/cuw/trunk/src/viz) (revision 3016)
+++ routeviz.conf (/cuw/branches/cnt/src/viz) (local)
@@ -58,3 +58,5 @@
cached_mass=10000.0
electron_constant=0.000000001
coeff_drag=500.0
+new_metric_weight=0.2
+node_max_age=360
=== routeviz.sh
==================================================================
--- routeviz.sh (/cuw/trunk/src/viz) (revision 3016)
+++ routeviz.sh (/cuw/branches/cnt/src/viz) (local)
@@ -329,6 +329,9 @@
cat << EOHTML
Content-type: text/html
+Cache-Control: no-cache
+Pragma: no-cache
+Expires: 0
<html>
<head>
=== rv/layout.c
==================================================================
--- rv/layout.c (/cuw/trunk/src/viz) (revision 3016)
+++ rv/layout.c (/cuw/branches/cnt/src/viz) (local)
@@ -94,7 +94,9 @@
if (vlink->metric <= 0) {
return vnet->longest_natural_spring;
} else {
- double ret = vnet->shortest_natural_spring / vlink->metric;
+ double ret;
+
+ ret = vnet->shortest_natural_spring / combined_link_metric(vlink);
if (ret > vnet->longest_natural_spring)
return vnet->longest_natural_spring;
else
@@ -383,10 +385,12 @@
kinetic_energy + potential_energy);
}
-#define RV_CACHE_NODE_WRITE_FMT "node\t%31s\t%f\t%f\t%u\t%u\n"
-#define RV_CACHE_NODE_READ_FMT "%31s\t%lf\t%lf\t%u\t%u\n"
-#define RV_CACHE_LINK_WRITE_FMT "link\t%u\t%31s\t%31s\t%lf\n"
-#define RV_CACHE_LINK_READ_FMT "%u\t%31s\t%31s\t%lf\n"
+#define RV_CACHE_NET_WRITE_FMT "net\t%u\n"
+#define RV_CACHE_NET_READ_FMT "%u\n"
+#define RV_CACHE_NODE_WRITE_FMT "node\t%31s\t%f\t%f\t%u\t%u\t%u\n"
+#define RV_CACHE_NODE_READ_FMT "%31s\t%lf\t%lf\t%u\t%u\t%u\n"
+#define RV_CACHE_LINK_WRITE_FMT "link\t%u\t%u\t%31s\t%31s\t%lf\n"
+#define RV_CACHE_LINK_READ_FMT "%u\t%u\t%31s\t%31s\t%lf\n"
void
rv_layout_read_cache(rv_net_t *vnet)
@@ -398,6 +402,7 @@
char token[5];
double lat, lon;
uint flags;
+ uint32_t generation;
uint type;
rv_node_t *vnode;
double metric;
@@ -419,30 +424,34 @@
loglib_warn("%s: locking cache", __func__);
while ((rc = fscanf(fp, "%s\t", token)) != EOF) {
- if (strcmp(token, "node") == 0) {
+ if (strcmp(token, "net") == 0) {
+ rc = fscanf(fp, RV_CACHE_NET_READ_FMT, &generation);
+ vnet->generation = generation;
+ } else if (strcmp(token, "node") == 0) {
rc = fscanf(fp, RV_CACHE_NODE_READ_FMT, label, &lat, &lon,
- &flags, &type);
- if (rc != 5) {
+ &flags, &type, &generation);
+ if (rc != 6) {
loglib_warnx("%s: read short node record (%d), aborting"
, __func__, rc);
break;
}
vnode = find_or_add_node(vnet, label, flags, type);
vnode->flags = flags;
+ vnode->generation = generation;
update_position_by_latlon(vnode->pos, vnet->mapdata, lat, lon);
/* make the cached node heavier to dampen it's movement. */
vnode->mass = vnet->cached_mass;
} else if (strcmp(token, "link") == 0) {
- rc = fscanf(fp, RV_CACHE_LINK_READ_FMT, &type, label,
- label0, &metric);
- if (rc != 4) {
+ rc = fscanf(fp, RV_CACHE_LINK_READ_FMT, &type, &generation,
+ label, label0, &metric);
+ if (rc != 5) {
loglib_warnx("%s: read short link record (%d), aborting"
, __func__, rc);
break;
}
- config_link(vnet, label, label0, metric, type);
+ config_link(vnet, label, label0, metric, type, generation);
} else
- loglib_warn("%s: unexpexted token %s", __func__, token);
+ loglib_warn("%s: unexpected token %s", __func__, token);
}
fl.l_type = F_UNLCK;
@@ -474,17 +483,20 @@
if (fcntl(fileno(fp), F_SETLKW, &fl) == -1)
loglib_warn("%s: locking cache", __func__);
+ if (fprintf(fp, RV_CACHE_NET_WRITE_FMT, vnet->generation) == -1)
+ loglib_warnx("%s: wrote short net record", __func__);
+
SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
if (fprintf(fp, RV_CACHE_NODE_WRITE_FMT,
vnode->label, vnode->pos->lat, vnode->pos->lon,
- vnode->flags, vnode->type) == -1)
+ vnode->flags, vnode->type, vnode->generation) == -1)
loglib_warnx("%s: wrote short node record", __func__);
}
SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
SLIST_FOREACH(vlink, &vnode->links, links) {
if (fprintf(fp, RV_CACHE_LINK_WRITE_FMT, vnode->type,
- vnode->label, vlink->dest->label, vlink->metric)
- == -1)
+ vlink->generation, vnode->label, vlink->dest->label,
+ vlink->metric) == -1)
loglib_warnx("%s: wrote short link record",
__func__);
}
@@ -500,11 +512,16 @@
rv_net_t *
rv_layout_net(rv_net_t * vnet)
{
+ rv_node_t *vnode;
int tick;
- rv_layout_read_cache(vnet);
for (tick = 0; tick < vnet->layout_ticks; tick++)
rv_layout_move_nodes(vnet);
+
+ // set node mass to cached_mass
+ SLIST_FOREACH(vnode, &vnet->nodes, nodes)
+ vnode->mass = vnet->cached_mass;
+
rv_layout_write_cache(vnet);
return vnet;
=== rv/output.c
==================================================================
--- rv/output.c (/cuw/trunk/src/viz) (revision 3016)
+++ rv/output.c (/cuw/branches/cnt/src/viz) (local)
@@ -195,11 +195,13 @@
fn = get_rv_font(vnet);
- /* draw links */
+ /* draw links for current generation */
LOGLIB_LOG(&log_rv_output, " drawing links");
SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
- if (vnet->show != vnode->type)
+ if (vnet->show != vnode->type ||
+ vnet->generation > vnode->generation)
continue;
+
SLIST_FOREACH(vlink, &vnode->links, links) {
/* This is kind of clever: a link's pointer
* identifies it. The pointers are strictly
@@ -208,15 +210,16 @@
* always choose the link with the smaller
* pointer.
*/
- if (vlink->reverse != NULL && vlink->reverse < vlink)
+ if ((vlink->reverse != NULL && vlink->reverse < vlink) ||
+ (vlink->generation < vnet->generation))
continue;
LOGLIB_LOG(&log_rv_output, " link %s %s",
- vnode->label, vlink->dest->label);
+ vnode->label, vlink->dest->label);
draw_link(vnet->bg, vnet, vnode->pos->x, vnode->pos->y,
- vlink->dest->pos->x, vlink->dest->pos->y,
- vlink->metric);
+ vlink->dest->pos->x, vlink->dest->pos->y,
+ combined_link_metric(vlink));
}
}
@@ -547,9 +550,10 @@
tile_real_w = vnet->mapdata->x_width / (1 << z);
tile_real_h = vnet->mapdata->y_height / (1 << z);
- /* draw links */
+ /* draw links for current generation */
SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
- if (vnet->show != vnode->type)
+ if (vnet->show != vnode->type ||
+ vnet->generation > vnode->generation)
continue;
tile_x = (z * vnode->pos->view_x) -
@@ -565,7 +569,8 @@
* always choose the link with the smaller
* pointer.
*/
- if (vlink->reverse != NULL && vlink->reverse < vlink)
+ if ((vlink->reverse != NULL && vlink->reverse < vlink) ||
+ (vlink->generation < vnet->generation))
continue;
tile_x0 = (z * vlink->dest->pos->view_x) -
@@ -574,7 +579,7 @@
(y * vnet->mapdata->view_y_height / 2);
draw_link(tile, vnet, tile_x, tile_y, tile_x0,
- tile_y0, vlink->metric);
+ tile_y0, combined_link_metric(vlink));
}
}
=== rv/routeviznet.c
==================================================================
--- rv/routeviznet.c (/cuw/trunk/src/viz) (revision 3016)
+++ rv/routeviznet.c (/cuw/branches/cnt/src/viz) (local)
@@ -225,6 +225,7 @@
vnode->label = nstrdup(snp, label);
vnode->flags = flags;
vnode->type = type;
+ vnode->generation = vnet->generation;
vnode->mass = vnet->standard_mass;
vnode->pos = new_position();
init_node_position(vnet, vnode, 0.0, 0.0);
@@ -299,25 +300,43 @@
}
static void
-remove_node(rv_net_t *vnet, rv_node_t *vnode) {
+remove_node(rv_net_t *vnet, rv_node_t *remove_node) {
- while (SLIST_EMPTY(&vnode->links) == 0)
- SLIST_REMOVE_HEAD(&vnode->links, links);
+ rv_link_t *vlink;
+ rv_node_t *vnode;
+ rv_alias_t *alias;
- while (SLIST_EMPTY(&vnode->aliases) == 0) {
- nfree(SLIST_FIRST(&vnode->aliases)->label);
- SLIST_REMOVE_HEAD(&vnode->aliases, aliases);
+ LOGLIB_LOG(&log_warn, "freeing vnode %s", remove_node->label);
+
+ // remove all links from other nodes to this node
+ SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
+ SLIST_FOREACH(vlink, &vnode->links, links) {
+ if (vlink->dest == remove_node) {
+ SLIST_REMOVE(&vnode->links, vlink, rv_link, links);
+ nfree(vlink);
+ }
+ }
}
-
- nfree(vnode->label);
- nfree(vnode->pos);
- nfree(vnode->layout_data);
+ while (SLIST_EMPTY(&remove_node->links) == 0) {
+ vlink = SLIST_FIRST(&remove_node->links);
+ SLIST_REMOVE_HEAD(&remove_node->links, links);
+ nfree(vlink);
+ }
- SLIST_REMOVE(&vnet->nodes, vnode, rv_node, nodes);
+ while (SLIST_EMPTY(&remove_node->aliases) == 0) {
+ alias = SLIST_FIRST(&remove_node->aliases);
+ SLIST_REMOVE_HEAD(&remove_node->aliases, aliases);
+ nfree(alias->label);
+ nfree(alias);
+ }
- LOGLIB_LOG(&log_warn, "freeing vnode");
- nfree(vnode);
+ nfree(remove_node->label);
+ nfree(remove_node->pos);
+ nfree(remove_node->layout_data);
+
+ SLIST_REMOVE(&vnet->nodes, remove_node, rv_node, nodes);
+ nfree(remove_node);
}
void
@@ -346,7 +365,7 @@
SLIST_FOREACH(vlink, &discard_node->links, links) {
config_link(vnet, real_node->label, vlink->dest->label,
- vlink->metric, real_node->type);
+ vlink->metric, real_node->type, vlink->generation);
vlink->reverse->dest = real_node;
}
@@ -402,11 +421,11 @@
void
config_link(rv_net_t *vnet, const char *label1, const char *label2,
- rv_metric_t metric, uint type)
+ rv_metric_t metric, uint type, uint32_t generation)
{
rv_link_t *vlink;
rv_node_t *vnode1, *vnode2;
- int updated_links;
+ int updated_link;
vnode1 = find_or_add_node(vnet, label1, 0, type);
vnode2 = find_or_add_node(vnet, label2, 0, type);
@@ -417,34 +436,31 @@
return;
}
- updated_links = 0;
+ vnode1->generation = vnode2->generation = generation;
+
+ updated_link = 0;
SLIST_FOREACH(vlink, &vnode1->links, links) {
if (strcmp(vlink->dest->label, vnode2->label) != 0)
continue;
- vlink->metric = metric;
- updated_links++;
+ // could raise weight to a power,
+ // i.e. 1/(vnet->generation - vlink->generation)
+ // to give current metric more emphasis for stale links
+ vlink->metric += vnet->new_metric_weight * (metric - vlink->metric);
+ vlink->generation = generation;
+ updated_link++;
+ break;
}
- SLIST_FOREACH(vlink, &vnode2->links, links) {
- if (strcmp(vlink->dest->label, vnode1->label) != 0)
- continue;
- vlink->metric = metric;
- updated_links++;
- }
- if (updated_links == 1)
- LOGLIB_LOG(&log_warn,
- "%s: unexpected unidirectional node link", __func__);
- if (updated_links > 2)
- LOGLIB_LOG(&log_warn,
- "%s: unexpected links, duplicated node entry?", __func__);
- if (updated_links == 0) {
+
+ if (updated_link == 0) {
add_link(vnode1, vnode2, metric);
}
+
}
void
add_link(rv_node_t *vnode1, rv_node_t *vnode2, rv_metric_t metric)
{
- rv_link_t *vlink;
+ rv_link_t *vlink1, *vlink2;
static struct nmalloc_pool *pool;
if (pool == NULL &&
@@ -464,37 +480,58 @@
return;
}
- SLIST_FOREACH(vlink, &vnode1->links, links)
- if (strcmp(vlink->dest->label, vnode2->label) == 0) {
+ SLIST_FOREACH(vlink1, &vnode1->links, links)
+ if (strcmp(vlink1->dest->label, vnode2->label) == 0) {
LOGLIB_LOG(&log_err, "%s: link already exists",
__func__);
return;
}
- SLIST_FOREACH(vlink, &vnode2->links, links)
- if (strcmp(vlink->dest->label, vnode1->label) == 0) {
- LOGLIB_LOG(&log_err, "%s: link already exists",
- __func__);
- return;
- }
-
- if ((vlink = nzmalloc(pool, 2 * sizeof(*vlink))) == NULL)
+ if ((vlink1 = nzmalloc(pool, sizeof(*vlink1))) == NULL)
LOGLIB_LOG(&log_mem, "%s: failed to allocate memory for link",
__func__);
- vlink[0].dest = vnode1;
- vlink[1].dest = vnode2;
+ vlink1->dest = vnode2;
+ vlink1->metric = metric;
+ vlink1->generation = vnode1->generation;
- vlink[0].reverse = &vlink[1];
- vlink[1].reverse = &vlink[0];
+ // assign reverse link pointer if found
+ SLIST_FOREACH(vlink2, &vnode2->links, links)
+ if (strcmp(vlink2->dest->label, vnode1->label) == 0) {
+ vlink1->reverse = vlink2;
+ vlink2->reverse = vlink1;
+ }
- vlink[0].metric = vlink[1].metric = metric;
+ SLIST_INSERT_HEAD(&vnode1->links, vlink1, links);
+}
- /* note well: this is NOT backwards. */
- SLIST_INSERT_HEAD(&vnode2->links, &vlink[0], links);
- SLIST_INSERT_HEAD(&vnode1->links, &vlink[1], links);
+double
+combined_link_metric(rv_link_t *vlink)
+{
+ double metric;
+
+ // Average of forward and reverse link metrics;
+ // if link is uni-directional it will be halved.
+ metric = vlink->metric;
+ if (vlink->reverse != NULL)
+ metric += vlink->reverse->metric;
+ metric /= 2;
+
+ return metric;
}
+void
+retire_nodes(rv_net_t *vnet)
+{
+ rv_node_t *vnode;
+
+ SLIST_FOREACH(vnode, &vnet->nodes, nodes) {
+ if (vnet->generation - vnode->generation > vnet->node_max_age) {
+ remove_node(vnet, vnode);
+ }
+ }
+}
+
rv_net_t *
init_viznet(int load_bgimage)
{
@@ -600,5 +637,3 @@
return 0;
}
-
-
=== rv/routeviznet.h
==================================================================
--- rv/routeviznet.h (/cuw/trunk/src/viz) (revision 3016)
+++ rv/routeviznet.h (/cuw/branches/cnt/src/viz) (local)
@@ -73,6 +73,7 @@
struct rv_link {
rv_node_t *dest; /* src is the owner of the link */
rv_metric_t metric; /* between 0 and 1 inclusive */
+ uint32_t generation;
struct rv_link *reverse; /* the backwards link */
SLIST_ENTRY(rv_link) links;
};
@@ -88,6 +89,7 @@
rv_position_t *pos; /* see latlon.h */
node_layout_data_t *layout_data; /* see layout.h */
double mass; /* layout mass */
+ uint32_t generation;
uint flags;
#define NODE_LOCATION_MASK 0x01
#define NODE_LOCATION_UNKNOWN 0x00
@@ -98,6 +100,7 @@
struct rv_net {
struct rv_nodes nodes; /* SLIST of nodes */
+ uint32_t generation;
gdImagePtr bg; /* background */
char *bgfn; /* filename of background */
char *fmt; /* image format */
@@ -125,6 +128,8 @@
int node_size;
int node_border;
int link_width;
+ int node_max_age;
+ double new_metric_weight;
/* The rest are all parameters for layout.c */
double coeff_drag;
int layout_ticks;
@@ -161,7 +166,10 @@
int is_alias(rv_net_t *, const char *);
rv_node_t *find_node(rv_net_t *, const char *);
rv_node_t *find_or_add_node(rv_net_t *, const char *, uint, uint);
-void config_link(rv_net_t *, const char *, const char *, rv_metric_t, uint);
+void config_link(rv_net_t *, const char *, const char *, rv_metric_t, uint,
+ uint32_t);
+double combined_link_metric(rv_link_t *);
+void retire_nodes(rv_net_t *);
void add_link(rv_node_t *, rv_node_t *, rv_metric_t);
rv_net_t *init_viznet(int);
int is_node_pinned(rv_node_t *);
More information about the CU-Wireless-Dev
mailing list