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

func (*SRTE) Changes

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

func (*SRTE) Clear

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

func (*SRTE) Insert

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

func (*SRTE) Load

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

func (*SRTE) PersistChanges

func (srte *SRTE) PersistChanges()

func (*SRTE) Remove

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

func (*SRTE) Search

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

func (*SRTE) SearchClear

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

func (*SRTE) SearchInsert

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

func (*SRTE) SearchRemove

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

func (*SRTE) SearchUpdate

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

func (*SRTE) Update

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

func (*SRTE) Utilization

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

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.