[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [ns] Dijkstra patch for ns
Xuan, John, all,
After a bit of holiday I've got some extra stamina (and time) to
fix the problems w/ my previous patch for using heap Dijkstra for
Static/Session routing. As I suspected initially (see below the
original mail exchange) it was indeed a routing logic error. Now I
fixed it and all regression tests pass successfully.
As always, the patch is against an ancient ns snapshot (20010320) but
I guess forward porting to the current bleeding edge isn't such a
major PITA.
Regards and all the best,
Florian
P.S. IIRC there were some others asking questions about it so I Cc:
ns-users too ;)
>> Hi, Florian:
>> We (saman group at ISI) have put your patch into the ns cvs. However,
>> serveral tests failed after that, could you please have a look into
>> that. Thanks so much for contributing your new implementation.
>> Cheers,
>> -chen xuan
> ACK that. Test fail here too. Sorry for that, but ATM I don't have
> the time to dig into it to see exactly what's broken, moved to other
> stuff (MNS....). Good to remember next time to validate a patch
> before submitting it ;).
> Thanks for your notice, sorry for introducing the bug.
> Florian
> P.S. From the error message it looks like a routing logic error. I'll try to
> have a look at it but cannot promise any timeline.
--- 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 Mon Jul 23 17:06:16 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/my-ns-2/route.cc,v 1.7 2001/06/12 14:37:24 otel Exp otel $ (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]));
- /* 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
- }
+// ************************ Yup ****************************************
- delete[] hopcnt;
- delete[] parent;
+ 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)=ROUTE(s,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 ------------
+
+
+
+
}
+
/* hierarchical routing support */