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 ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DAMG ¶
type DAMG struct {
Adjacencies map[Vertex]VertexInfo
}
DAMG is a Directed Acyclic 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 NewDAMG ¶
func NewDAMG(ups, cores, downs []*seg.PathSegment) *DAMG
NewDAMG 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 (*DAMG) GetPaths ¶
func (g *DAMG) 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 DAMG.
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 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
ExpTime time.Time
}
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 ¶
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).
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 DAMG.
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
ExpTime uint32
}
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 DAMG that can be used as key in maps.
func VertexFromIA ¶
func VertexFromPeering ¶
type VertexInfo ¶
VertexInfo maps destination vertices to the list of edges that point towards them.
Source Files