(@ #define INFINITY  (1e100) @)


// compute the proximity of each virtual node to its destination in
// the corresponding DAG in the routing table. There is a choice of
// 3 algorithms, the greedy, EP and MP algorithms.

*operation* void compute_proximities(RoutingTable* rtable, Ring* ring)
*traverse*
  *from* ProxAlg
  *to* {Greedy, EP, MP}
*wrapper* Greedy
  (@
     rtable->compute_greedy_proximities(ring);
   @)
*wrapper* EP
  (@
     rtable->compute_ep_proximities(ring);
   @)
*wrapper* MP
  (@
     rtable->compute_mp_proximities(ring);
   @)


// compute the proximities for the greedy algorithm. The closer a vnode
// to the destination of the DAG, the higher its proximity.

*operation* void compute_greedy_proximities(Ring* ring)
*traverse*
  *from* RoutingTable
  *through* -> *, dag, *
  *to* DagAdjacency
*carry* *in* VNode* dest_vnode = (@ get_dest() @)
*along*
  *from* DagDest
  *through* -> *, dag, *
  *to* DagAdjacency
*wrapper* DagAdjacency
  (@
     int dist = ring->distance(get_source(), dest_vnode);
     double prox;
     if (dist == 0)
       prox = INFINITY;
     else
       prox = 1.0/(double)dist;
     this->get_proximity()->set_val(prox);
   @)


// compute the proximities for the EP algorithm.

*operation* void compute_ep_proximities(Ring* ring)
*traverse*
  *from* RoutingTable
  *through* -> *, dag, *
  *to* DagAdjacency
*carry* *in* Dag* dag = (@ this @)
*along*
  *from* Dag
  *to* DagAdjacency
*carry* *in* VNode* dest_vnode = (@ get_dest() @)
*along*
  *from* DagDest
  *through* -> *, dag, *
  *to* DagAdjacency
*wrapper* DagAdjacency
  (@
     if (get_source() != dest_vnode) {
       double ep = 0;
       expected_proximity(dest_vnode, dag, ring, 1, 0, ep);
       get_proximity()->set_val(ep);
     }
   @)

// compute the proximities for the MP algorithm.

*operation* void compute_mp_proximities(Ring* ring)
*traverse*
  *from* RoutingTable
  *through* -> *, dag, *
  *to* DagAdjacency
*carry* *in* VNode* dest_vnode = (@ get_dest() @)
*along*
  *from* DagDest
  *through* -> *, dag, *
  *to* DagAdjacency
*carry* *in* Dag* dag = (@ this @)
*along*
  *from* Dag
  *to* DagAdjacency
*wrapper* DagAdjacency
  (@
     if (get_source() != dest_vnode) {
       double mp = 0;
       maximum_proximity(dest_vnode, dag, ring, 1, 0, mp);
       get_proximity()->set_val(mp);
   }
   @)


// find the utilization on the link (vnode1, vnode2) on the ring.

*operation* double get_utilization(VNode* vnode1, VNode* vnode2)
*init* (@ 0.0 @)
*traverse*
  *from* Ring
  *to* VirtualNeighbor
*carry* *in* Ring* ring = (@ this @)
*along*
  *from* Ring
  *to* VirtualAdjacency
*wrapper* VirtualAdjacency
  (@
     if (get_source() != vnode1)
       return;
     if (ring->get_nextdefault(this)->get_source() == vnode2) {
       return_val = get_next_util()->get_val();
       return;
     }
   @)
*wrapper* VirtualNeighbor
  (@
     if (get_neighbor() == vnode2)
       return_val = get_util()->get_val();
   @)


// find the DagAdjacency of "vnode" in the corresponding DAG.

*operation* DagAdjacency* find(VNode* vnode)
*init* (@ NULL @)
*traverse*
  *from* Dag
  *to* DagAdjacency
*wrapper* DagAdjacency
  (@
     if (this->get_source() == vnode)
       return_val = this;
   @)


// compute the expected proximity (EP) of the current dag adjacency
// with respect to the destination "dest_vnode" in the DAG.

*operation* void expected_proximity(VNode* dest_vnode, Dag* dag, Ring* ring,
				    double product, int length, double& sum)
*traverse*
  *from* DagAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode
*carry* *in* VNode* source_vnode = (@ get_source() @)
*along*
  *from* DagAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode
*wrapper* VNode
  (@
     product *= (1 - ring->get_utilization(source_vnode, this));
     length++;
     if (this == dest_vnode)
       sum += (product/length);
     else {
       DagAdjacency* dag_adj = dag->find(this);
       dag_adj->expected_proximity(dest_vnode, dag, ring, product, length, sum);
     }
   @)


// compute the maximum proximity (MP) of the current dag adjacency 
// with respect to the destination "dest_vnode" of the DAG.

*operation* void maximum_proximity(VNode* dest_vnode, Dag* dag, Ring* ring,
				   double product, int length, double& max)
*traverse*
  *from* DagAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode
*carry* *in* VNode* source_vnode = (@ get_source() @)
*along*
  *from* DagAdjacency
  *through* -> *, neighbor, *
  *to-stop* VNode
*wrapper* VNode
  (@
     product *= (1 - ring->get_utilization(source_vnode, this));
     length++;
     if (this == dest_vnode) {
       double val = product/length;
       if (val > max)
	 max = val;
     }
     else {
       DagAdjacency* dag_adj = dag->find(this);
       dag_adj->maximum_proximity(dest_vnode, dag, ring, product, length, max);
     }
   @)