graph

Documentation

Overview

Package graph implements a multigraph model of a SCION network for use in tests. The default Mock SCIOND implementation uses the graph to simulate path lookups.

Note that the graph always returns the shortest paths, regardless whether they are valid SCION paths (e.g., the path might cross multiple peering links).

Index

• Variables
• func MustParseIA(ia string) addr.IA
• type AS
  • func (as *AS) Delete(ifid common.IFIDType)
• type Description
• type EdgeDesc
• type Graph
  • func New() *Graph
  • func NewDefaultGraph() *Graph
  • func NewFromDescription(desc *Description) *Graph
  • func (g *Graph) Add(ia string)
  • func (g *Graph) AddLink(xIA string, xIFID common.IFIDType, yIA string, yIFID common.IFIDType, ...)
  • func (g *Graph) Beacon(ifids []common.IFIDType) *seg.PathSegment
  • func (g *Graph) DeleteInterface(ifid common.IFIDType)
  • func (g *Graph) GetParent(ifid common.IFIDType) addr.IA
  • func (g *Graph) GetPaths(xIA string, yIA string) [][]common.IFIDType
  • func (g *Graph) RemoveLink(ifid common.IFIDType)

Variables

var DefaultGraphDescription = &Description{
	Nodes: []string{
		"1-ff00:0:110",
		"1-ff00:0:111",
		"1-ff00:0:112",
		"1-ff00:0:120",
		"1-ff00:0:121",
		"1-ff00:0:122",
		"1-ff00:0:130",
		"1-ff00:0:131",
		"1-ff00:0:132",
		"1-ff00:0:133",
		"2-ff00:0:210",
		"2-ff00:0:211",
		"2-ff00:0:212",
		"2-ff00:0:220",
		"2-ff00:0:221",
		"2-ff00:0:222",
	},
	Edges: []EdgeDesc{
		{"1-ff00:0:110", 1112, "1-ff00:0:120", 1211, false},
		{"1-ff00:0:110", 1113, "1-ff00:0:130", 1311, false},
		{"1-ff00:0:110", 1121, "2-ff00:0:210", 2111, false},
		{"1-ff00:0:110", 1114, "1-ff00:0:111", 1411, false},
		{"1-ff00:0:120", 1213, "1-ff00:0:130", 1312, false},
		{"1-ff00:0:120", 1222, "2-ff00:0:220", 2212, false},
		{"1-ff00:0:120", 1215, "1-ff00:0:121", 1512, false},
		{"1-ff00:0:130", 1316, "1-ff00:0:131", 1613, false},
		{"1-ff00:0:111", 1415, "1-ff00:0:121", 1514, true},
		{"1-ff00:0:111", 1423, "2-ff00:0:211", 2314, true},
		{"1-ff00:0:111", 1417, "1-ff00:0:112", 1714, false},
		{"1-ff00:0:121", 1516, "1-ff00:0:131", 1615, true},
		{"1-ff00:0:121", 1518, "1-ff00:0:122", 1815, false},
		{"1-ff00:0:131", 1619, "1-ff00:0:132", 1916, false},
		{"1-ff00:0:132", 1910, "1-ff00:0:133", 1019, false},
		{"2-ff00:0:210", 2122, "2-ff00:0:220", 2221, false},
		{"2-ff00:0:210", 2123, "2-ff00:0:211", 2321, false},
		{"2-ff00:0:220", 2224, "2-ff00:0:221", 2422, false},
		{"2-ff00:0:211", 2324, "2-ff00:0:221", 2423, true},
		{"2-ff00:0:211", 2325, "2-ff00:0:212", 2523, false},
		{"2-ff00:0:211", 2326, "2-ff00:0:222", 2623, false},
		{"2-ff00:0:221", 2426, "2-ff00:0:222", 2624, false},
	},
}

Graph description of the topology in doc/fig/default-topo.pdf. Comments mention root name for IFIDs.

Functions

func MustParseIA

func MustParseIA(ia string) addr.IA

Types

type AS

type AS struct {
	IFIDs map[common.IFIDType]struct{}
}

AS contains a list of all the IFIDs in an AS.

func (*AS) Delete

func (as *AS) Delete(ifid common.IFIDType)

Delete removes ifid from as.

type Description

type Description struct {
	Nodes []string
	Edges []EdgeDesc
}

Description contains the entire specification of a graph. It is useful for one shot initilizations.

type EdgeDesc

type EdgeDesc struct {
	Xia   string
	Xifid common.IFIDType
	Yia   string
	Yifid common.IFIDType
	Peer  bool
}

EdgeDesc is used in Descriptions to describe the links between ASes.

type Graph

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

Graph implements a graph of ASes and IFIDs for testing purposes. IFIDs must be globally unique.

Nodes are represented by ASes.

Edges are represented by pairs of IFIDs.

func New

func New() *Graph

New allocates a new empty graph.

func NewDefaultGraph

func NewDefaultGraph() *Graph

func NewFromDescription

func NewFromDescription(desc *Description) *Graph

NewFromDescription initializes a new graph from description desc.

func (*Graph) Add

func (g *Graph) Add(ia string)

Add adds a new node to the graph. If ia is not a valid string representation of an ISD-AS, Add panics.

func (*Graph) AddLink

func (g *Graph) AddLink(xIA string, xIFID common.IFIDType,
	yIA string, yIFID common.IFIDType, peer bool)

AddLink adds a new edge between the ASes described by xIA and yIA, with xIFID in xIA and yIFID in yIA. If xIA or yIA are not valid string representations of an ISD-AS, AddLink panics.

func (*Graph) Beacon

func (g *Graph) Beacon(ifids []common.IFIDType) *seg.PathSegment

Beacon constructs path segments across a series of egress ifids. The parent AS of the first IFID is the origin of the beacon, and the beacon propagates down to the parent AS of the remote counterpart of the last IFID. The constructed segment includes peering links. The hop fields in the returned segment do not contain valid MACs.

func (*Graph) DeleteInterface

func (g *Graph) DeleteInterface(ifid common.IFIDType)

DeleteInterface removes ifid from the graph without deleting its remote counterpart. This is useful for testing IFID misconfigurations.

func (*Graph) GetParent

func (g *Graph) GetParent(ifid common.IFIDType) addr.IA

GetParent returns the parent AS of ifid.

func (*Graph) GetPaths

func (g *Graph) GetPaths(xIA string, yIA string) [][]common.IFIDType

GetPaths returns all the minimum-length paths. If xIA = yIA, a 1-length slice containing an empty path is returned. If no path exists between xIA and yIA, a 0-length slice is returned.

Note that this always returns shortest length paths, even if they might not be valid SCION paths.

func (*Graph) RemoveLink

func (g *Graph) RemoveLink(ifid common.IFIDType)

RemoveLink deletes the edge containing ifid from the graph.