solver

Documentation

Overview

Package solver contains an implementation of the Link-Guided Search algorithm to minimize the maximum utilization of a network.

Index

• type Config
• type LinkGuidedSolver
  • func NewLinkGuidedSolver(state *srte.SRTE, cfg Config) *LinkGuidedSolver
  • func (lgs *LinkGuidedSolver) ApplyMove(move srte.Move) bool
  • func (lgs *LinkGuidedSolver) MaxUtilization() float64
  • func (lgs *LinkGuidedSolver) MostUtilizedEdge() int
  • func (lgs *LinkGuidedSolver) Search(edge int, demand int, maxUtil float64) (srte.Move, bool)
  • func (lgs *LinkGuidedSolver) SelectDemand(edge int, r float64) int
  • func (lgs *LinkGuidedSolver) SelectEdge(r float64) int

Types

type Config

type Config struct {
	// Parameter alpha controls the likelihood of selecting an edge where the
	// likelihood P(e) of selecting edge e is determined by its utilization
	// raised to the power of alpha: P(e) = (util[e]^alpha) / Σ(util[ei]^alpha).
	// High values of alpha increase the probability of selecting the most
	// utilized edges. By contrast, small values of alpha flatten the
	// probability distribution. In particular, setting alpha to zero results
	// in random uniform selection.
	Alpha float64

	// Parameter beta controls the likelihood of selecting a demand where the
	// likelihood P(d|e) of selecting demand d on edge e is determined by the
	// demand's contribution to the utilization of edge e, raised to the power
	// of beta: P(d|e) = (util[e, d]^beta) / Σ(util[e, di]^alpha). High values
	// of beta increase the probability of selecting the demand with the highest
	// contribution. By contrast, small values of beta flatten the probability
	// distribution. In particular, setting alpha to zero results in random
	// uniform selection.
	Beta float64
}

type LinkGuidedSolver

type LinkGuidedSolver struct {
	State *srte.SRTE
	Cfg   Config
	// contains filtered or unexported fields
}

func NewLinkGuidedSolver

func NewLinkGuidedSolver(state *srte.SRTE, cfg Config) *LinkGuidedSolver

NewLinkGuidedSolver returns a new instance of a Link-Guided Search solver to minimize the maximum utilization of the given SRTE state.

func (*LinkGuidedSolver) ApplyMove

func (lgs *LinkGuidedSolver) ApplyMove(move srte.Move) bool

ApplyMove applies the move if possible. It returns true if the move was applied, false otherwise.

func (*LinkGuidedSolver) MaxUtilization

func (lgs *LinkGuidedSolver) MaxUtilization() float64

MaxUtilization returns the maximum edge utilization.

func (*LinkGuidedSolver) MostUtilizedEdge

func (lgs *LinkGuidedSolver) MostUtilizedEdge() int

MostUtilizedEdge returns the ID of the edge with the highest utilization. If several edges have the same highest utilization, the one with the smallest ID is returned.

func (*LinkGuidedSolver) Search

func (lgs *LinkGuidedSolver) Search(edge int, demand int, maxUtil float64) (srte.Move, bool)

Search searches for a move that reduces the load of edge by changing the demand's path. The second returned value is a bool that indicates whether a valid move was found. Moves that increase the utilization of an edge above maxUtil are not considered valid. If several moves are possible, the one that reduces the edge's load the most is returned.

func (*LinkGuidedSolver) SelectDemand

func (lgs *LinkGuidedSolver) SelectDemand(edge int, r float64) int

SelectDemand selects a demand passing through a given edge using roulette wheel selection accordingly to random number r in [0, 1). For more information about how demands are selected, refer to parameter Beta in Config.

func (*LinkGuidedSolver) SelectEdge

func (lgs *LinkGuidedSolver) SelectEdge(r float64) int

SelectEdge selects edge using roulette wheel selection accordingly to random number r in [0, 1). For more information about how edges are selected, refer to parameter Alpha in Config.