Fault Tolerance provided by Capillary Routing

 

Rounded Rectangle: Home   Rounded Rectangle: Examples   Rounded Rectangle: Code   Rounded Rectangle: Download   Rounded Rectangle: Speedup   Rounded Rectangle: Upgrades   Rounded Rectangle: Links

 

Description of the AMPL code

 

Rounded Rectangle: model  Rounded Rectangle: diagram  Rounded Rectangle: config  Rounded Rectangle: cleancore  Rounded Rectangle: randomwalk  Rounded Rectangle: solve  Rounded Rectangle: slideshow  Rounded Rectangle: ACAE

 

Construction of the capillary routing

 

..\a21download\ab46-model.txt

Script

Comments

reset;

commands config.txt;

option randseed (randseed);

option presolve 1;

set NODES = 1..N;

param source_node in NODES, =1;

param sink_node in NODES, != source_node, =int(N/2)+1;

◄defining the set of nodes, the source and the sink nodes of the communication flow

param flow_out{1..T,NODES} default 0;

param flow_out_incr{1..T,NODES} default 0;

param flow_out_bottl{1..T,NODES} default 0;

◄parameter flow_out specifies the net flow out or net flow in at each node, the two other parameters are used for construction of the problem of the next layer

set LINKS{1..T} dimen 2 within NODES cross NODES;

set INITLINKS{1..T} dimen 2;

◄set of links evolving over the construction and the initial set of links

set FRAMES within 1..T default 1..T;

set FRAMES_quit;

set FRAMES_true;

◄set of active frames of the problem

var F{1..T}>=0;

◄flow increase factor

set Core{1..T} dimen 2;

set Core_clean{1..T} dimen 2;

◄set of links whose load to be minimized, Core_clean is used in cleancore for identifying the end of the discovery of the bottleneck links

param eps = 1e-10;

◄if below eps, the load of a link or the value of the node’s flow out is considered as zero

minimize Cost;

◄objective for minimizing the load of Core links

node Node{t in FRAMES, i in NODES}: net_out = F[t]*flow_out[t,i];

◄node constraints

arc Link{t in FRAMES, (i,j) in LINKS[t]} >=0, <=1,

  from Node[t,i], to Node[t,j],

  obj Cost if (i,j) in Core[t] then 1;

◄link variables with lower and upper bounds

maximize Flow:

  sum{t in FRAMES} F[t];

◄objective for maximizing the overall flow

param xxx;

param yyy;

param xx{NODES};

param yy{NODES};

param x{1..T,NODES};

param y{1..T,NODES};

param a{NODES} default Uniform(0,2*PI);

commands randomwalk.txt;

◄random walk coordinates of nodes, used and generated by randomwalk script

for{t in 1..T} let INITLINKS[t] := LINKS[t];

◄saving links in INITLINKS

param layers{1..T} default 0;

◄stores the number of layers for each timeframe

param flow_outs{t in 1..T,0..layers[t],NODES} default 0;

◄flow out values at nodes after discovery of the present layer of the capillary routing (input conditions of the problem of the next layer)

param pump{t in 1..T, 1..layers[t]};

◄flow increase factor of the layer

set PATH_mincost{1..T} dimen 2;

param load_mincost{t in 1..T, (i,j) in INITLINKS[t]} >=0;

◄first min cost path solution of the max flow

set BOTTLENECKS{t in 1..T, 1..layers[t]} dimen 2;

◄bottleneck links identified at the given layer

set PATH{t in 1..T, 1..layers[t]} dimen 2;

param load{t in 1..T, l in 1..layers[t], (i,j) in PATH[t,l]} >=0;

◄copy of the first min cost path solution for each layer

param maxload;

◄used in cleancore

param counter;

◄used for logging the preparation of the LP problem of the next layer

for{t in 1..T, i in NODES: (if i==source_node then 1)+(if i==sink_node then -1) != 0}

{

  let flow_out[t,i] := (if i==source_node then 1) + (if i==sink_node then -1);

  let flow_outs[t,0,i] := flow_out[t,i];

}

◄computing initial values of the flow_out and saving a copy into flow_outs at index 0; since both flow_out and flow_outs are declared to have a default value 0, no need to initialize the zero entries

printf "\nlayering:\n" > (log);

for{l in 1..200}

{

  printf "\n  layer %d:\n",l > (log);

  printf "    %-8s %d\n","frames",card(FRAMES) > (log);

◄starting the layering loop; logging the layer number and the number of frames in the current problem

  for{t in FRAMES} unfix F[t];

◄unfixing the flow increase factors of active frames

  for{t in FRAMES} let Core[t] := {};

◄emptying the Core sets (used for the load minimizing objective)

  objective Flow;

  commands solve.txt;

◄setting the flow increase maximizing objective and solving the LP problem

  printf "    %-8s %f\n","max-flow",Flow > (log);

◄logging the obtained aggregate max flow value

  for{t in FRAMES} fix F[t];

◄fixing the flow increase factors at their optimal values

  for{t in FRAMES} let layers[t]:=layers[t]+1;

◄increasing the layer number of all active frames

  display setof {t in FRAMES} (t,round(F[t],5));

◄displaying the obtained flow increase factors for all timeframes

  for{t in FRAMES} let pump[t,layers[t]] := F[t];

◄storing flow increase factors in pump

  let FRAMES_quit := {t in FRAMES: not F[t]};

◄frames for which the flow increase factor is zero, i.e. there is no communication between the end nodes, are marked for removal from the set of active frames of the problem

  # Emptying all parameters for frames with no flow

  if FRAMES_quit not within {}

    then

    {

      print "Frames with no flow:";

      display FRAMES_quit;

      printf "Emptying all parameters for these frames ... ";

      for{t in FRAMES_quit}

      {

        let PATH[t,layers[t]] := {};

        let BOTTLENECKS[t,layers[t]] := {};

        for{i in NODES: flow_out[t,i]!=0}

        {

          let flow_out[t,i] := 0;

          let flow_outs[t,layers[t],i] := flow_out[t,i];

        }

      }

      printf "Ok\n";

    }

◄for frames with no flow, zeroing flow_out and flow_outs at all nodes, emptying the path set and the bottlenecks

  let FRAMES := FRAMES diff FRAMES_quit;

◄removing frames with no flow from the set of active frames of the problem

  if FRAMES within {}

    then

    {

      print "no frame has flow";

      break;

    }

◄breaking the layering loop if no frame left in the problem

  printf "Setting the cost objective for all links ... ";

  for{t in FRAMES} let Core[t] := LINKS[t];

  objective Cost;

  printf "Ok\n\n";

◄for the problems with the flow increase factors fixed on their optimal values, setting a new objective of the min cost, which is initially applicable to all links of the network

  printf "    hunting bottlenecks:\n" > (log);

  let FRAMES_true := FRAMES;

  for{hunt in 1..1000}

  {

◄starting the bottleneck hunting loop; saving the active frames of the problem in FRAMES_true – frames for which the capillary routing is still being searched

    printf "      hunt %d:\n",hunt > (log);

    printf "        %-8s %d\n","frames",card(FRAMES) > (log);

    printf "        %-8s %d\n","core",sum{t in FRAMES} card(Core[t]) > (log);

◄logging the hunt number, number of active frames in the current hunting problem and the current number of candidates for the bottleneck links

    commands solve.txt;

◄solving min cost for the links of Core sets; if a link is a bottleneck it will not delegate its load to a link out of the Core set, if a link reduced its load under the cost objective, then it cannot be a bottleneck

    printf "        %-8s %f\n","min-cost",Cost > (log);

◄logging the obtained min cost

    if hunt==1 then

    {

      # min-cost solution for all FRAMES of the present layer

      for{t in FRAMES} let PATH_mincost[t] := {(i,j) in LINKS[t]: Link[t,i,j]>eps};

      for{t in FRAMES} for{(i,j) in PATH_mincost[t]} let load_mincost[t,i,j] := Link[t,i,j];

 

      for{t in FRAMES} let PATH[t,layers[t]] := PATH_mincost[t];

      for{t in FRAMES} for{(i,j) in PATH_mincost[t]} let load[t,layers[t],i,j] := load_mincost[t,i,j];

    }

◄if it is the first hunt, the min cost flow is stored in PATH_mincost and load_mincost; the min cost flow is also saved in PATH and load under the index of the current layer; only links carrying a non-negligible flow are considered as a part of the min cost flow solution

    let FRAMES_quit := {}; #will be computed in cleancore

    commands cleancore.txt;

◄calling cleancore script, which will clean from the core set the obviously non-bottleneck links; the script will also assign to FRAMES_quit the timeslots for which no further reduction of the Core set is observed, i.e. for which the definitive set of bottleneck links is discovered

    display setof{t in FRAMES} (t,card(Core[t]));

◄displaying the number of candidates for each active frame (for which the bottleneck discovery is still in progress)

    let FRAMES := FRAMES diff FRAMES_quit;

◄quitting from the hunting problem the frames (computed by cleancore) with discovered bottlenecks

    display FRAMES_quit,FRAMES;

    if FRAMES within {}

      then

        break;

◄display the quit and the remaining frames; break the hunting loop if no frames with undiscovered bottlenecks is left

  };

  let FRAMES := FRAMES_true;

◄end of the hunting loop; setting active frames back to frames for which the capillary routing discovery is still in the progress

  let benchmark_start := _ampl_time;

  printf "    preparing the next layer:\n" > (log);

  printf "Preparing the next layer (5 steps):\n";

◄once the true bottlenecks of the current layer are discovered, starting the preparation of the problem for the next layer of the capillary routing; benchmarking the AMPL time and logging

  printf "  (1) Increase of non-zero flow outs ... ";

  reset data flow_out_incr;

  for{t in FRAMES, i in NODES: abs(flow_out[t,i])>0}

  {

    let flow_out_incr[t,i] := if abs(flow_out[t,i]) <= eps then 0 else

      flow_out[t,i]*F[t];

  }

  printf "Ok\n";

◄increasing the flow out values at each node according to the flow increase factor; for every node where there was a non zero net flow, if the flow amount is not negligible, the flow_out_incr is initialized with the flow_out value increased by the flow increase factor; flow_out_incr is previously reset so non initialized values remain zero

  printf "      increased flow outs  %d\n",

    card({t in FRAMES, i in NODES: abs(flow_out_incr[t,i])>0}) > (log);

◄logging the total number of nodes with non-negligible net flows, undergoing the flow increase

  printf "  (2) Removal of bottleneck links ... ";

  reset data flow_out_bottl;

  for{t in FRAMES}

  {

    for{(i,j) in Core[t]}

    {

      let LINKS[t] := LINKS[t] diff {(i,j)};

    }

    for{i in NODES}

    {

      let flow_out_bottl[t,i] :=

        sum{(j,i) in Core[t]} 1 - sum{(i,j) in Core[t]} 1;

    }

  }

◄computing total increment or decrement at nodes due to removal of bottleneck links: resetting to zero the flow_out_bottl parameter; for each frame removing from the problem the bottleneck links with their inverse counterpart links; for each node computing the total positive and negative contribution resulting from the removal of all bottleneck links

  reset data flow_out;

  for{t in FRAMES, i in NODES} let flow_out[t,i] :=

    flow_out_incr[t,i] + flow_out_bottl[t,i];

  printf "Ok\n";

◄resetting the flow_out to zero and initializing it at each node by a sum of increased flow with the total increment or a decrement implied by the removal of bottlenecks

  printf "      removed bottlenecks  %d\n",

    card({t in FRAMES, Core[t]}) > (log);

◄logging the number of removed bottlenecks

  printf "  (3) Zeroing negligible flow: ";

  let counter:=0;

  for{t in FRAMES, i in NODES: 0<abs(flow_out[t,i])<=eps}

  {

    let flow_out[t,i] := 0;

    printf ".";

    let counter:=counter+1;

  }

  printf " Ok\n";

  printf "      zeroed flow outs     %d\n",counter > (log);

◄net flow outs obtained from the flow increase and from the removal of bottlenecks, which are not zeroes but are very close to zero, are reset to zero; logging the number of such resets

  # Calibration

  printf "  (4) Calibration ... ";

  for{t in FRAMES} let PATH_mincost[t] := PATH_mincost[t] diff Core[t];

◄starting calibration of flow_out values at nodes according to the flow traversing the adjacent links; first removing from the PATH_mincost the bottleneck links

  reset data flow_out_incr;

  let counter:=0;

  for{t in FRAMES, i in NODES: abs(flow_out[t,i])>0}

  {

    let flow_out_incr[t,i] :=

      sum{(i,j) in PATH_mincost[t]} load_mincost[t,i,j] -

      sum{(j,i) in PATH_mincost[t]} load_mincost[t,j,i];

    let counter:=counter+1;

  }

◄for all nodes having a preliminarily computed non-zero flow out values, flow_out_incr is computed to be the flow carried by outgoing links minus the flow carried by incoming links; flow on the links is taken from the first min cost solution of the layer, in fact any other valid flow can be used for the calibration

  reset data flow_out;

  for{t in FRAMES, i in NODES: abs(flow_out_incr[t,i])>0}

    let flow_out[t,i] := flow_out_incr[t,i];

  printf "Ok\n";

  printf "      calibrated flow outs %d\n",counter > (log);

◄initializing flow_out by non-zero values of calibrated flow_out_incr;

  printf "  (5) Zeroing negligible flow: ";

  let counter:=0;

  for{t in FRAMES, i in NODES: 0<abs(flow_out[t,i])<=eps}

  {

    let flow_out[t,i] := 0;

    printf ".";

    let counter:=counter+1;

  }

  printf " Ok\n";

  printf "      zeroed flow outs     %d\n",counter > (log);

◄ if after calibration new nodes are obtained with very close to zero flow-out values, do zero the flow outs at these nodes

  for{t in FRAMES, i in NODES: flow_out[t,i] != 0}

    let flow_outs[t,layers[t],i] := flow_out[t,i];

◄save flow_out parameter in flow_outs at the index of the current layer

  for{t in FRAMES} let BOTTLENECKS[t,layers[t]] := Core[t];

◄save the set of bottlenecks

  let benchmark_stop := _ampl_time;

  printf "Done in %f seconds\n\n",benchmark_stop - benchmark_start;

  printf "      all done in (sec)    %f\n",benchmark_stop - benchmark_start > (log);

◄benchmarking and logging the duration of the preparation of the next layer

  display setof{t in FRAMES} (t,card(BOTTLENECKS[t,layers[t]]));

◄displaying the number of bottlenecks in each frame of the current layer

  let FRAMES_quit := {t in FRAMES: {i in NODES: abs(flow_out[t,i])>eps} within {}};

◄capillary routing is completely discovered for frames whose networks contain no node with a non-zero (positive or negative) flow out

  for{t in FRAMES_quit}

  {

    fix F[t] := 0;

    let Core[t] := {};

  }

◄for frames with discovered capillary routing the flow increase factors are fixed to 0 and the Core sets are emptied (flow increase factors for these frames will not be released in the next layer, since these frames will be removed from the processing)

  let FRAMES := FRAMES diff FRAMES_quit;

◄removing from active frames the frames with discovered capillary routing

  if FRAMES within {}

    then

    {

      print "all explored";

      break;

    }

◄quit the layering loop once the capillary routing is discovered for all timeframes

}

printf "\nlayering completed.\n" > (log);

close (log);

◄end of the capillary routing layering loop

set All_solve_results := setof{i in 1..solve_n} solve_results[i];

display _ampl_time, _total_solve_time;

display solve_n;

display All_solve_results;

display N,T;

display max{t in 1..T} layers[t];

◄displaying total AMPL and CPLEX times, number of solves and all solve results (collected by solve script), number of nodes, timeframes and maximal number of discovered layers

let file := "speedup.csv";

if num(sub(ctime(),"^.* [0-9]+:[0-9]+:([0-9]+) .*$","\1")) mod 5 == 0 then

  print "time,ampl_time,total_solve_time," &

         "solve_n,solved,N,T,max layers,randseed" >> (file);

printf "%s,%.5f,%.5f,%d,%s,%d,%d,%d,%d\n", sub(ctime(),"^[^ ]* ",""),

  _ampl_time, _total_solve_time,

  solve_n,if All_solve_results symdiff {"solved"} within {} then "ok" else "error",

  N, T, max{t in 1..T} layers[t], randseed >> (file);

close (file);

◄the same data with the accomplishment time and randseed value is recorded in speedup.csv file; at about every 5 records adding a header in speedup.csv file

shell "rmdir /s /q dump";

shell "mkdir dump";

shell "del /q dump\*";

shell "copy config.txt dump";

shell "copy solvelog.csv dump";

shell "copy model.log dump";

◄create an empty dump directory and copy there the configuration, solvelog.csv (created by solve script) and model.log files

let file := "dump/flow.txt";

display layers > (file);

display pump > (file);

display BOTTLENECKS > (file);

display flow_outs > (file);

close (file);

◄store in the flow.txt file of the dump folder the capillary flow information; layers, pump, bottleneck links of each layer, flow out values before and after each layer; information stored in the flow.txt is unique for any given network, whichever is the method for discovery of the capillary routing this information will be identical in any solution (due to a strong property of the uniqueness of the capillary routing)

let file := "dump/path.txt";

printf "param T = %d;\n\n",T > (file);

printf "param N = %d;\n\n",N > (file);

print "param" > (file);

display layers > (file);

print "param" > (file);

display pump > (file);

display BOTTLENECKS > (file);

display PATH > (file);

display INITLINKS > (file);

print "param" > (file);

display load > (file);

close (file);

◄store in the path.txt file of the dump folder the path information for computing ACAE of each layer; data is stored in a format for being read by an AMPL data statement; since the path file contains the shortest path solutions for each layer, its content is not obligatorily unique and for an identical input may vary from one solver to another

#end;

print "Drawing...";

param ps symbolic = "diagram/out.ps";

param layer;

param diagram_pos;

commands linkviews_load.txt;

commands diagram.txt;

commands slideshow.txt;

◄preparing the diagram drawing

 

 

*    *    *