combinator

Documentation

Overview

Package combinator contains methods for constructing SCION forwarding paths.

Call Combine to grab all the metadata associated with the constructed paths, followed by WriteTo to obtain the wire format of a path:

for path := range Combine(src, dst, ups, cores, downs) {
  path.WriteTo(w)
}

Returned paths are sorted by weight in descending order. The weight is defined as the number of transited AS hops in the path.

Index

• type DMG
  • func NewDMG(ups, cores, downs []*seg.PathSegment) *DMG
  • func (g *DMG) AddEdge(src, dst Vertex, segment *InputSegment, edge *Edge)
  • func (g *DMG) GetPaths(src, dst Vertex) PathSolutionList
• type Edge
• type EdgeMap
• type HopField
  • func (field *HopField) String() string
• type InfoField
  • func (field *InfoField) String() string
• type InputSegment
  • func (s *InputSegment) IsDownSeg() bool
• type Path
  • func Combine(src, dst addr.IA, ups, cores, downs []*seg.PathSegment) []*Path
  • func FilterLongPaths(paths []*Path) []*Path
  • func (p *Path) ComputeExpTime() time.Time
  • func (p *Path) WriteTo(w io.Writer) (int64, error)
• type PathSolution
  • func (solution *PathSolution) GetFwdPathMetadata() *Path
• type PathSolutionList
  • func (sl PathSolutionList) Len() int
  • func (sl PathSolutionList) Less(i, j int) bool
  • func (sl PathSolutionList) Swap(i, j int)
• type Segment
  • func (segment *Segment) ComputeExpTime() time.Time
• type Vertex
  • func VertexFromIA(ia addr.IA) Vertex
  • func VertexFromPeering(upIA addr.IA, upIFID common.IFIDType, downIA addr.IA, downIFID common.IFIDType) Vertex
  • func (v Vertex) Reverse() Vertex
• type VertexInfo

Types

type DMG

type DMG struct {
	Adjacencies map[Vertex]VertexInfo
}

DMG is a Directed Multigraph.

Vertices are either ASes (identified by their ISD-AS number) or peering links (identified by the the ISD-AS numbers of the peers, and the IFIDs on the peering link).

func NewDMG

func NewDMG(ups, cores, downs []*seg.PathSegment) *DMG

NewDMG creates a new graph from sets of path segments.

The input segments are traversed to construct the graph. Each segment is traversed in reverse, from the last AS Entry to the first one. During this traversal, we save the AS number of the first traversed ASEntry (i.e., last one in ASEntries array) as pinnedIA. This will represent the source of the edges we add for Up and Core segments, and the destination for Down segments.

For each ASEntry, all hop entries are explored. If the hop entry is a “normal” hop entry (i.e., the one at index 0), we check the following: (1) If this is the last ASEntry in the segment, it means we’re routing to pinnedIA. This is not interesting so we continue to the next hop entry without changing anything in the graph. (2) Otherwise, a vertex is added (if one doesn’t exist) for the current AS. Then, an edge is added from pinnedIA to this vertex, in the case of up- and core-segments, or from this vertex to pinnedIA (in the case of down-segments). The edge is annotated with the segment that is currently being traversed, and ShortcutID is set to the position of the current ASEntry in the ASEntries array. PeerID is set to 0.

If the hop entry is a peer entry (i.e., its index is different from 0), a peering vertex is added based on (IA, Ingress, InIA, RemoteInIF) for up segments, and on (InIA, RemoteInIF, IA, Ingress) for down segments. Note that the AS number in the peering vertex is not pinnedIA, but the one participating in the peering. The edge is annotated with the segment that is currently being traversed, and ShortcutID is set to the position of the current ASEntry in the ASEntries array. The direction of the edge is from pinnedIA to the peering vertex for up-segments, and the reverse for down-segments. PeerID is set to the index of the current hop entry.

func (*DMG) AddEdge

func (g *DMG) AddEdge(src, dst Vertex, segment *InputSegment, edge *Edge)

func (*DMG) GetPaths

func (g *DMG) GetPaths(src, dst Vertex) PathSolutionList

GetPaths returns all the paths from src to dst, sorted according to weight.

type Edge

type Edge struct {
	Weight int
	// Shortcut is the ASEntry index on where the forwarding portion of this
	// segment should end (for up-segments) or start (for down-segments). An
	// additional V-only HF upstream of this ASEntry needs to be included for
	// verification.  This is also set when crossing peering links. If 0, the
	// full segment is used.
	Shortcut int
	// Peer is the index in the hop entries array for this peer entry. If 0,
	// the standard hop entry at index 0 is used (instead of a peer entry).
	Peer int
}

Edge represents an edge for the DMG.

type EdgeMap

type EdgeMap map[*InputSegment]*Edge

EdgeMap is used to keep the set of edges going from one vertex to another. The edges are keyed by path segment pointer.

type HopField

type HopField struct {
	*spath.HopField
}

func (*HopField) String

func (field *HopField) String() string

type InfoField

type InfoField struct {
	*spath.InfoField
}

func (*InfoField) String

func (field *InfoField) String() string

type InputSegment

type InputSegment struct {
	*seg.PathSegment
	Type proto.PathSegType
}

InputSegment is a local representation of a path segment that includes the segment's type.

func (*InputSegment) IsDownSeg

func (s *InputSegment) IsDownSeg() bool

IsDownSeg returns true if the segment is a DownSegment.

type Path

type Path struct {
	Segments   []*Segment
	Weight     int
	Mtu        uint16
	Interfaces []sciond.PathInterface
}

func Combine

func Combine(src, dst addr.IA, ups, cores, downs []*seg.PathSegment) []*Path

Combine constructs paths between src and dst using the supplied segments. All possible paths are first computed, and then filtered according to FilterLongPaths. The remaining paths are returned sorted according to weight (on equal weight, see pathSolutionList.Less for the tie-breaking algorithm).

If Combine cannot extract a hop field or info field from the segments, it panics.

func FilterLongPaths

func FilterLongPaths(paths []*Path) []*Path

FilterLongPaths returns a new slice containing only those paths that do not go more than twice through interfaces belonging to the same AS (thus filtering paths containing useless loops).

func (*Path) ComputeExpTime

func (p *Path) ComputeExpTime() time.Time

func (*Path) WriteTo

func (p *Path) WriteTo(w io.Writer) (int64, error)

type PathSolution

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

func (*PathSolution) GetFwdPathMetadata

func (solution *PathSolution) GetFwdPathMetadata() *Path

GetFwdPathMetadata builds the complete metadata for a forwarding path by extracting it from a path between source and destination in the DMG.

type PathSolutionList

type PathSolutionList []*PathSolution

PathSolutionList is a sort.Interface implementation for a slice of solutions.

func (PathSolutionList) Len

func (sl PathSolutionList) Len() int

func (PathSolutionList) Less

func (sl PathSolutionList) Less(i, j int) bool

Less sorts according to the following priority list:

• total path cost (number of hops)
• number of segments
• segmentIDs
• shortcut index
• peer entry index

func (PathSolutionList) Swap

func (sl PathSolutionList) Swap(i, j int)

type Segment

type Segment struct {
	InfoField  *InfoField
	HopFields  []*HopField
	Type       proto.PathSegType
	Interfaces []sciond.PathInterface
}

func (*Segment) ComputeExpTime

func (segment *Segment) ComputeExpTime() time.Time

type Vertex

type Vertex struct {
	IA       addr.IA
	UpIA     addr.IA
	UpIFID   common.IFIDType
	DownIA   addr.IA
	DownIFID common.IFIDType
}

Vertex is a union-like type for the AS vertices and Peering link vertices in a DMG that can be used as key in maps.

func VertexFromIA

func VertexFromIA(ia addr.IA) Vertex

func VertexFromPeering

func VertexFromPeering(upIA addr.IA, upIFID common.IFIDType,
	downIA addr.IA, downIFID common.IFIDType) Vertex

func (Vertex) Reverse

func (v Vertex) Reverse() Vertex

Reverse returns a new vertex that contains the peering information in reverse. AS vertices remain unchanged.

type VertexInfo

type VertexInfo map[Vertex]EdgeMap

VertexInfo maps destination vertices to the list of edges that point towards them.