summaryrefslogtreecommitdiffstats
path: root/src/vnet/lldp
diff options
context:
space:
mode:
authorAndrew Yourtchenko <ayourtch@gmail.com>2017-12-09 14:55:52 +0100
committerFlorin Coras <florin.coras@gmail.com>2017-12-11 19:05:23 +0000
commitd78349109fdb98fa0ba5f5aff779be700ff78357 (patch)
treef704a36483ac448ea8946949e90d556510f952be /src/vnet/lldp
parentabbc04c564b4120a3ee753cdd133a7a151dc5c8e (diff)
acl-plugin: unapply/reapply the classifier-based inacls when performing macip_acl_add_replace on an existing MACIP ACL
The classifier tables layout might (and most always will) change during the MACIP ACL modification. Furthermore, vnet_set_input_acl_intfc() is quite a picky creature - it quietly does nothing if there is an existing inacl applied, even if the number is different, so a simple "reapply" does not work. So, cleanly remove inacl, then reapply when the new tables are ready. Also, fix the testcase which was supposed to test this exact behavior. Thanks to Jon Loeliger for spotting this issue. Change-Id: I7e4bd8023d9de7e914448bb4466c1b0ef6940f58 Signed-off-by: Andrew Yourtchenko <ayourtch@gmail.com>
Diffstat (limited to 'src/vnet/lldp')
0 files changed, 0 insertions, 0 deletions
' href='#n151'>151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 
/*
  Copyright (c) 2011 Cisco and/or its affiliates.

  * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
*/

#include <vppinfra/anneal.h>

/*
 * Optimize an objective function by simulated annealing
 *
 * Here are a couple of short, easily-understood
 * descriptions of simulated annealing:
 *
 * http://www.cs.sandia.gov/opt/survey/sa.html
 * Numerical Recipes in C, 2nd ed., 444ff
 *
 * The description in the Wikipedia is not helpful.
 *
 * The algorithm tries to produce a decent answer to combinatorially
 * explosive optimization problems by analogy to slow cooling
 * of hot metal, aka annealing.
 *
 * There are (at least) three problem-dependent annealing parameters
 * to consider:
 *
 * t0, the initial "temperature. Should be set so that the probability
 * of accepting a transition to a higher cost configuration is
 * initially about 0.8.
 *
 * ntemps, the number of temperatures to use. Each successive temperature
 * is some fraction of the previous temperature.
 *
 * nmoves_per_temp, the number of configurations to try at each temperature
 *
 * It is a black art to set ntemps, nmoves_per_temp, and the rate
 * at which the temperature drops. Go too fast with too few iterations,
 * and the computation falls into a local minimum instead of the
 * (desired) global minimum.
 */

void
clib_anneal (clib_anneal_param_t * p)
{
  f64 t;
  f64 cost, prev_cost, delta_cost, initial_cost, best_cost;
  f64 random_accept, delta_cost_over_t;
  f64 total_increase = 0.0, average_increase;
  u32 i, j;
  u32 number_of_increases = 0;
  u32 accepted_this_temperature;
  u32 best_saves_this_temperature;
  int accept;

  t = p->initial_temperature;
  best_cost = initial_cost = prev_cost = p->anneal_metric (p->opaque);
  p->anneal_save_best_configuration (p->opaque);

  if (p->flags & CLIB_ANNEAL_VERBOSE)
    fformat (stdout, "Initial cost %.2f\n", initial_cost);

  for (i = 0; i < p->number_of_temperatures; i++)
    {
      accepted_this_temperature = 0;
      best_saves_this_temperature = 0;

      p->anneal_restore_best_configuration (p->opaque);
      cost = best_cost;

      for (j = 0; j < p->number_of_configurations_per_temperature; j++)
	{
	  p->anneal_new_configuration (p->opaque);
	  cost = p->anneal_metric (p->opaque);

	  delta_cost = cost - prev_cost;

	  /* cost function looks better, accept this move */
	  if (p->flags & CLIB_ANNEAL_MINIMIZE)
	    accept = delta_cost < 0.0;
	  else
	    accept = delta_cost > 0.0;

	  if (accept)
	    {
	      if (p->flags & CLIB_ANNEAL_MINIMIZE)
		if (cost < best_cost)
		  {
		    if (p->flags & CLIB_ANNEAL_VERBOSE)
		      fformat (stdout, "New best cost %.2f\n", cost);
		    best_cost = cost;
		    p->anneal_save_best_configuration (p->opaque);
		    best_saves_this_temperature++;
		  }

	      accepted_this_temperature++;
	      prev_cost = cost;
	      continue;
	    }

	  /* cost function worse, keep stats to suggest t0 */
	  total_increase += (p->flags & CLIB_ANNEAL_MINIMIZE) ?
	    delta_cost : -delta_cost;

	  number_of_increases++;

	  /*
	   * Accept a higher cost with Pr { e^(-(delta_cost / T)) },
	   * equivalent to rnd[0,1] < e^(-(delta_cost / T))
	   *
	   * AKA, the Boltzmann factor.
	   */
	  random_accept = random_f64 (&p->random_seed);

	  delta_cost_over_t = delta_cost / t;

	  if (random_accept < exp (-delta_cost_over_t))
	    {
	      accepted_this_temperature++;
	      prev_cost = cost;
	      continue;
	    }
	  p->anneal_restore_previous_configuration (p->opaque);
	}

      if (p->flags & CLIB_ANNEAL_VERBOSE)
	{
	  fformat (stdout, "Temp %.2f, cost %.2f, accepted %d, bests %d\n", t,
		   prev_cost, accepted_this_temperature,
		   best_saves_this_temperature);
	  fformat (stdout, "Improvement %.2f\n", initial_cost - prev_cost);
	  fformat (stdout, "-------------\n");
	}

      t = t * p->temperature_step;
    }

  /*
   * Empirically, one wants the probability of accepting a move
   * at the initial temperature to be about 0.8.
   */
  average_increase = total_increase / (f64) number_of_increases;
  p->suggested_initial_temperature = average_increase / 0.22;	/* 0.22 = -ln (0.8) */

  p->final_temperature = t;
  p->final_metric = p->anneal_metric (p->opaque);

  if (p->flags & CLIB_ANNEAL_VERBOSE)
    {
      fformat (stdout, "Average cost increase from a bad move: %.2f\n",
	       average_increase);
      fformat (stdout, "Suggested t0 = %.2f\n",
	       p->suggested_initial_temperature);
    }
}

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */