srte

Documentation

Index

• func SplitLoad(load int64, ratio float64) int64
• type Demand
• type Edge
• type EdgeRatio
• type FGraphs
  • func NewFGraphs(g *Topology) (*FGraphs, error)
  • func (fgs *FGraphs) EdgeRatios(s int, t int) []EdgeRatio
• type LoadChange
• type Move
• type MoveType
• type NetworkState
  • func NewNetworkState(nEdges int) *NetworkState
  • func (s *NetworkState) AddLoad(edge int, load int64)
  • func (s *NetworkState) Changes() []LoadChange
  • func (s *NetworkState) Load(edge int) int64
  • func (s *NetworkState) PersistChanges()
  • func (s *NetworkState) RemoveLoad(edge int, load int64)
  • func (s *NetworkState) UndoChanges()
• type SRTE
  • func NewSRTE(instance *SRTEInstance) (*SRTE, error)
  • func (srte *SRTE) ApplyMove(m Move, persist bool) bool
  • func (srte *SRTE) Changes() []LoadChange
  • func (srte *SRTE) Clear(demand int) bool
  • func (srte *SRTE) Insert(demand int, pos int, node int) bool
  • func (srte *SRTE) Load(edge int) int64
  • func (srte *SRTE) PersistChanges()
  • func (srte *SRTE) Remove(demand int, pos int) bool
  • func (srte *SRTE) Search(edge int, demand int, maxUtil float64) (Move, bool)
  • func (srte *SRTE) SearchClear(edge int, demand int, maxUtil float64) (Move, bool)
  • func (srte *SRTE) SearchInsert(edge int, demand int, maxUtil float64) (Move, bool)
  • func (srte *SRTE) SearchRemove(edge int, demand int, maxUtil float64) (Move, bool)
  • func (srte *SRTE) SearchUpdate(edge int, demand int, maxUtil float64) (Move, bool)
  • func (srte *SRTE) Update(demand int, pos int, newNode int) bool
  • func (srte *SRTE) Utilization(edge int) float64
• type SRTEInstance
• type Topology
  • func NewTopology(edges []Edge, nNodes int) *Topology

Functions

func SplitLoad

func SplitLoad(load int64, ratio float64) int64

SplitLoad calculates the portion of the load based on the given ratio and converts it to an integer to guarantee numerical stability. SplitLoad is used for all splitting operations in this package.

Types

type Demand

type Demand struct {
	From      int
	To        int
	Bandwidth int64
}

type Edge

type Edge struct {
	From int
	To   int
	Cost int
}

Edge represents an edge between two nodes in a directed graph.

type EdgeRatio

type EdgeRatio struct {
	Edge  int
	Ratio float64
}

EdgeRatio represent an edge in a forwarding graph and the ratio of load sent on that edge. For example, EdgeRatio{5, 0.5} means that 50% of the load sent on the forwarding graph traverses edge 5.

type FGraphs

type FGraphs struct {
	// contains filtered or unexported fields
}

func NewFGraphs

func NewFGraphs(g *Topology) (*FGraphs, error)

func (*FGraphs) EdgeRatios

func (fgs *FGraphs) EdgeRatios(s int, t int) []EdgeRatio

EdgeRatios returns the list of EdgeRatio pairs on the forwarding graph from node s to node t.

type LoadChange

type LoadChange struct {
	Edge         int
	PreviousLoad int64
}

LoadChange is a pair made of an edge and its load before any change was applied to the current state.

type Move

type Move struct {
	MoveType MoveType
	Position int
	Node     int
	Demand   int
}

type MoveType

type MoveType int8

const (
	MoveUnknown MoveType = iota
	MoveClear
	MoveRemove
	MoveUpdate
	MoveInsert
)

type NetworkState

type NetworkState struct {
	// contains filtered or unexported fields
}

NetworkState is a reversible structure which represents the state of the network's load. This structure keeps track of changes applied to its edges and can efficiently undo them.

func NewNetworkState

func NewNetworkState(nEdges int) *NetworkState

NewNetworkState initializes and returns a new NetworkState.

func (*NetworkState) AddLoad

func (s *NetworkState) AddLoad(edge int, load int64)

AddLoad adds the load from the edge. The change is registered so that it can be undone if needed.

func (*NetworkState) Changes

func (s *NetworkState) Changes() []LoadChange

Changes returns the edges that have been changed since the last time changes were persisted.

Important: the slice is a view on one of the state's internal structure and should only be used in read-only operations. Modifying the slice will most likely results in incorrect behavior.

func (*NetworkState) Load

func (s *NetworkState) Load(edge int) int64

Load returns the current load on the edge.

func (*NetworkState) PersistChanges

func (s *NetworkState) PersistChanges()

PersistChanges persists all the changes as the "new" state. New changes can be accumulated (and undone) from this point.

func (*NetworkState) RemoveLoad

func (s *NetworkState) RemoveLoad(edge int, load int64)

RemoveLoad removes the load from the edge. The change is registered so that it can be undone if needed.

func (*NetworkState) UndoChanges

func (s *NetworkState) UndoChanges()

UndoChanges undoes all the changes since the last time PersistChanges was called. This operation is done in O(C) where C is the number of edges that have been changed.

type SRTE

type SRTE struct {
	FGraphs  *FGraphs
	PathVar  []*paths.PathVar
	Instance *SRTEInstance
	// contains filtered or unexported fields
}

func NewSRTE

func NewSRTE(instance *SRTEInstance) (*SRTE, error)

func (*SRTE) ApplyMove

func (srte *SRTE) ApplyMove(m Move, persist bool) bool

ApplyMove applies the given move to the network's state. The function returns true if the move could be applied, it returns false otherwize (e.g. if the move is invalid).

func (*SRTE) Changes

func (srte *SRTE) Changes() []LoadChange

Changes returns the list of changes applied to the network since the last time the state was persisted.

func (*SRTE) Clear

func (srte *SRTE) Clear(demand int) bool

Clear removes all the intermediate nodes in the demand's path and updates the load of the impacted edge accordingly.

The function returns true if (i) the operation is valid, and (ii) it changed the demand's path. Otherwise, it returns false and does not change the state of the network.

func (*SRTE) Insert

func (srte *SRTE) Insert(demand int, pos int, node int) bool

Insert inserts a new intermediate node at position pos in the demand's path and updates the load of the impacted edge accordingly.

The function returns true if (i) the operation is valid, and (ii) it changed the demand's path. Otherwise, it returns false and does not change the state of the network.

func (*SRTE) Load

func (srte *SRTE) Load(edge int) int64

Load returns the edge's load.

func (*SRTE) PersistChanges

func (srte *SRTE) PersistChanges()

PersistChanges persists the changes applied since the last time the state of the network was persisted. New changes can be accumulated (and undone) from this point.

func (*SRTE) Remove

func (srte *SRTE) Remove(demand int, pos int) bool

Remove removes the intermediate node at position pos in the demand's path and updates the load of the impacted edge accordingly.

The function returns true if (i) the operation is valid, and (ii) it changed the demand's path. Otherwise, it returns false and does not change the state of the network.

func (*SRTE) Search

func (srte *SRTE) Search(edge int, demand int, maxUtil float64) (Move, bool)

Search searches for a move that reduces the load of the selected edge and keeps the maximum utilization of the network below maxUtil. It returns an empty move and false if it could not find an improving move.

func (*SRTE) SearchClear

func (srte *SRTE) SearchClear(edge int, demand int, maxUtil float64) (Move, bool)

SearchClear searches for a "clear" move that reduces the load of the selected edge and keeps the maximum utilization of the network below maxUtil. It returns an empty move and false if it could not find an improving move.

func (*SRTE) SearchInsert

func (srte *SRTE) SearchInsert(edge int, demand int, maxUtil float64) (Move, bool)

SearchInsert searches for a "insert" move that reduces the load of the selected edge and keeps the maximum utilization of the network below maxUtil. It returns an empty move and false if it could not find an improving move.

func (*SRTE) SearchRemove

func (srte *SRTE) SearchRemove(edge int, demand int, maxUtil float64) (Move, bool)

SearchRemove searches for a "remove" move that reduces the load of the selected edge and keeps the maximum utilization of the network below maxUtil. It returns an empty move and false if it could not find an improving move.

func (*SRTE) SearchUpdate

func (srte *SRTE) SearchUpdate(edge int, demand int, maxUtil float64) (Move, bool)

SearchUpdate searches for a "update" move that reduces the load of the selected edge and keeps the maximum utilization of the network below maxUtil. It returns an empty move and false if it could not find an improving move.

func (*SRTE) Update

func (srte *SRTE) Update(demand int, pos int, newNode int) bool

Update replaces the intermediate node at position pos in the demand's path with newNode and updates the load of the impacted edge accordingly.

The function returns true if (i) the operation is valid, and (ii) it changed the demand's path. Otherwise, it returns false and does not change the state of the network.

func (*SRTE) Utilization

func (srte *SRTE) Utilization(edge int) float64

Utilization returns the edge's utilization.

type SRTEInstance

type SRTEInstance struct {
	Graph          *Topology
	FGraphs        *FGraphs
	MaxPathNodes   int
	Demands        []Demand
	LinkCapacities []int64
}

type Topology

type Topology struct {
	Nexts [][]int
	Edges []Edge
}

Topology represents the topology of a network as a directed graph.

func NewTopology

func NewTopology(edges []Edge, nNodes int) *Topology

NewTopology creates a new topology with the specified edges and number of nodes. It is important to ensure that edges are only between nodes within the range [0, nNodes); otherwise, the function will panic.