[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[ns] Dijkstra patch for ns
All,
For quite a while I've been playing with the code for Dijkstra in
Static/Session routing and I've noticed that the implementation is the
naive version (i.e. using a `for` loop). As such I've re-written that
code to use the heap-version of Dijkstra. For that I've made the
following changes:
- "struct route_entry" has a field for the cost of the route to that
destination (why not ;)?)
- Correspondingly route.cc has a new macro that returns the cost field
given bi-dimensional coordinates.
- "class RouteLogic" has 4 new protected members for manipulating the
heaps (creating, sift down, and printing the heap).
I haven't extensively stress-tested the implementation but even for simple
topologies I claim a relative increase in route table computation
speed.
The patch (unified diff) is included as text (for the mail archive) at
the end of this mail. As seen from the patch, the snapshot I butchered
was 20010320. If intrested I can make a patch agains the latest 2.1b8
route.{h,cc}
Questions and comments are warmly welcome
Florian
--- ns-2-snapshot-20010320/route.h Thu Feb 22 20:45:39 2001
+++ my-ns-2/route.h Tue Jun 12 16:33:48 2001
@@ -36,7 +36,7 @@
* Bertsekas' book. Written originally by S. Keshav, 7/18/88
* (his work covered by identical UC Copyright)
*
- * @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/route.h,v 1.7 2001/02/22 19:45:39 haldar Exp $
+ * @(#) $Header: /users/ce/otel/tmp/ns-unstable/ns-2/route.h,v 1.3 2001/06/12 14:33:48 otel Exp $
*
*/
@@ -66,6 +66,7 @@
struct route_entry {
public:
int next_hop;
+ double cost; // For heap Dijkstra - Yup, 20010531
void* entry;
};
@@ -121,7 +122,13 @@
int *C_; /* no. of clusters/domain */
int D_, /* total no. of domains */
Cmax_; /* max value of C_ for initialization purpose */
-
+
+ /*** Yup, 20010523 Heap helper functions (STL might not be avail) ***/
+
+ void rt_sift_down (route_entry *, int **, int *, int i);
+ void rt_make_heap (route_entry *, int **, int *);
+ void print_rt_heap (route_entry *, int **, int *);
+ int rt_min_alter_heap(route_entry *, int **, int *);
};
class RouteLogicAlgo : public RouteLogic {
--- ns-2-snapshot-20010320/route.cc Thu Feb 22 20:45:39 2001
+++ my-ns-2/route.cc Tue Jun 12 16:37:24 2001
@@ -39,7 +39,7 @@
#ifndef lint
static const char rcsid[] =
-"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/route.cc,v 1.38 2001/02/22 19:45:39 haldar Exp $ (LBL)";
+"@(#) $Header: /users/ce/otel/tmp/ns-unstable/ns-2/route.cc,v 1.7 2001/06/12 14:37:24 otel Exp $ (LBL)";
#endif
#include <stdlib.h>
@@ -409,77 +409,161 @@
adj_[INDEX(src, dst, size_)].cost = INFINITY;
}
+// ************************ Yup ****************************************
+
+
+void RouteLogic::rt_sift_down (route_entry *adjmtrx, int **heap, int *heapsz, int i)
+ { int c=i, p=-1, tind=0;
+ while (p!=c) {
+ p=c;
+ if ((2*(p+1)-1) == *heapsz -1) // Exactly half-way. One kid, one swap, one exit.
+ if (adjmtrx[(*heap)[2*(p+1)-1]].cost < adjmtrx[(*heap)[p]].cost ) {
+ // Swap
+ tind=(*heap)[p];
+ (*heap)[p]=(*heap)[2*(p+1)-1];
+ (*heap)[2*(p+1)-1]=tind;
+ return;
+ }
+// Two kids. Pick the smallest
+ if ((2*(p+1)-1) < *heapsz -1)
+ if (adjmtrx[(*heap)[2*(p+1)-1]].cost < adjmtrx[(*heap)[2*(p+1)]].cost){
+ if (adjmtrx[(*heap)[2*(p+1)-1]].cost < adjmtrx[(*heap)[p]].cost)
+ c=2*(p+1)-1;
+ }
+ else
+ if (adjmtrx[(*heap)[2*(p+1)]].cost < adjmtrx[(*heap)[p]].cost)
+ c=2*(p+1);
+// Swap
+ tind=(*heap)[p];
+ (*heap)[p]=(*heap)[c];
+ (*heap)[c]=tind;
+ }
+ }
+
+
+
+
+void RouteLogic::rt_make_heap (route_entry *adjmtrx, int **heap , int *heapsz)
+// The heap is running from 0 to (*heapsz-1)
+{ int i;
+ for (i= (int) (*heapsz/2-1) ; i>=0; i--) rt_sift_down (adjmtrx,heap,heapsz,i)
+;
+}
+
+
+void RouteLogic::print_rt_heap (route_entry *adjmtrx, int **heap, int *heapsz)
+ { int z;
+ printf ("adjmtrx\n");
+ for (z=0;z<*heapsz;z++) printf("%d ", (int) adjmtrx[(*heap)[z]].cost);
+ printf ("\nheap\n");
+ for (z=0;z<*heapsz;z++) printf("%d ", (*heap)[z]);
+ printf("\n");
+ }
+
+int RouteLogic::rt_min_alter_heap (route_entry *adjmtrx, int **heap, int *heapsz)
+{ int ret;
+ ret=(*heap)[*heapsz-1];
+ (*heap)[*heapsz-1]=(*heap)[1];
+ (*heap)[1]=ret;
+ ret=(*heap)[0];
+ (*heapsz)--;
+ (*heap)++; // XXX Pointer arithmetic
+ rt_make_heap(adjmtrx,heap,heapsz);
+ return ret;
+
+
+}
+
void RouteLogic::compute_routes()
{
int n = size_;
- int* parent = new int[n];
- double* hopcnt = new double[n];
+
#define ADJ(i, j) adj_[INDEX(i, j, size_)].cost
#define ADJ_ENTRY(i, j) adj_[INDEX(i, j, size_)].entry
#define ROUTE(i, j) route_[INDEX(i, j, size_)].next_hop
#define ROUTE_ENTRY(i, j) route_[INDEX(i, j, size_)].entry
+#define ROUTE_COST(i, j) route_[INDEX(i, j, size_)].cost
+
delete[] route_;
- route_ = new route_entry[n * n];
- memset((char *)route_, 0, n * n * sizeof(route_[0]));
+ route_ = new route_entry[n * n];
+ memset((char *)route_, 0, n * n * sizeof(route_[0]));
+
+// ************************ Yup ****************************************
+
+ int rt_heap_ [n]; // XXX Heap container. Maybe the use of heap memory instead for very large n would be wise ?
+ int * rth; // Dynamic heap head
+ int s,v,w;
+ int i,hpsz;
+
+
+// "All pairs" loop i.e. by "s", the source node
+ for (s=0;s<n;s++){
+// (Re) seat, (re)size and (re) initialize the heap
+ rth = rt_heap_;
+ hpsz=size_;
+ memset((char *) rth , 0, n * sizeof(int));
+ for (v=0;v<n;v++){ // MUST start from 0 due to above memset
+// Set the initial cost/nexthop/entry from adjacency info
+ ROUTE_COST(s,v)=ADJ(s,v);
+ if (ROUTE_COST(s,v) !=INFINITY) {
+ ROUTE(s,v)=v;
+ ROUTE_ENTRY(s,v)=ADJ_ENTRY(s,v);
+ }
+ rth[v]=v; // Initially same as the adjacency indexes
+ if (v == s){ // Iick
+ ROUTE_COST(s,s)=0;
+ ROUTE(s,s)=s;
+ ROUTE_ENTRY(s,s)=0;
+ }
+ }
+
+ if (!s) continue; // Started from node 0 (bogus) only for route_ esthetic reasons
+ rt_make_heap(route_ + s*size_,&rth,&hpsz);
+// print_rt_heap(route_ + s*size_,&rth,&hpsz); // exit (0);
+
+ rt_min_alter_heap (route_ + s*size_,&rth,&hpsz); // XXX Drop off the head (self) as the artificial 0 cost (i.e. min) screws the heap
+
+ while (hpsz > 1) {
+ v = rt_min_alter_heap (route_ + s*size_,&rth,&hpsz);
+ for (i=0;i<hpsz;i++){
+ if (!(w=rth[i])) continue; // Node 0 is bogus
+ if (ROUTE_COST(s,w) > (ROUTE_COST(s,v)+ADJ(v,w))){
+ ROUTE_COST(s,w)=ROUTE_COST(s,v)+ADJ(v,w);
+ ROUTE(s,w)=v; // new (tentative) next hop
+ ROUTE_ENTRY(s,w)=ROUTE_ENTRY(s,v);
+ }
+ }
+ }
+ }
+
+
+
+// for (i=0;i<size_*size_;i++)
+// if (route_[i].cost == (double) INFINITY) route_[i].cost=0;
+
+
+
+// --------- Cut here ------------
+//
+//
+//
+// int j;
+// for(i=0;i<n;i++){
+// for(j=0;j<n;j++)
+// printf ("%2d|%-5d ",route_[i*size_+j].next_hop,(int) route_[i*size_+j].cost);
+// printf("\n");
+// }
+// printf("\n");
+//
+//
+//
+// --------- Cut here ------------
+
+
- /* do for all the sources */
- int k;
- for (k = 1; k < n; ++k) {
- int v;
- for (v = 0; v < n; v++)
- parent[v] = v;
-
- /* set the route for all neighbours first */
- for (v = 1; v < n; ++v) {
- if (parent[v] != k) {
- hopcnt[v] = ADJ(k, v);
- if (hopcnt[v] != INFINITY) {
- ROUTE(k, v) = v;
- ROUTE_ENTRY(k, v) = ADJ_ENTRY(k, v);
- }
- }
- }
- for (v = 1; v < n; ++v) {
- /*
- * w is the node that is the nearest to the subtree
- * that has been routed
- */
- int o = 0;
- /* XXX */
- hopcnt[0] = INFINITY;
- int w;
- for (w = 1; w < n; w++)
- if (parent[w] != k && hopcnt[w] < hopcnt[o])
- o = w;
- parent[o] = k;
- /*
- * update distance counts for the nodes that are
- * adjacent to o
- */
- if (o == 0)
- continue;
- for (w = 1; w < n; w++) {
- if (parent[w] != k &&
- hopcnt[o] + ADJ(o, w) < hopcnt[w]) {
- ROUTE(k, w) = ROUTE(k, o);
- ROUTE_ENTRY(k, w) =
- ROUTE_ENTRY(k, o);
- hopcnt[w] = hopcnt[o] + ADJ(o, w);
- }
- }
- }
- }
- /*
- * The route to yourself is yourself.
- */
- for (k = 1; k < n; ++k) {
- ROUTE(k, k) = k;
- ROUTE_ENTRY(k, k) = 0; // This should not matter
- }
- delete[] hopcnt;
- delete[] parent;
}
+
/* hierarchical routing support */