docs/graph/graph-user-guide-graph-model.rst

   1 .. _graph-user-guide-graph-model:
   2
   3 Graph Model Overview
   4 ====================
   5 This section provides a high-level overview of the Graph Model.
   6
   7 .. contents:: Contents
   8    :depth: 2
   9    :local:
  10
  11 Graph Theory and Path Computation
  12 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  13
  14 The primary goal of Graph and Algorithms features, is to be able to compute
  15 constrainted path among a given IP/MPLS network. Such path could be used to
  16 enforce connectivity by means of RSVP-TE or Segment Routing TE through PCEP
  17 protocol or simply provide a solution to answer a path request (coming from
  18 RESTCONF API or a PcRequest message).
  19
  20 In IP/MPLS networks, these path computation algorithms need to access to a
  21 representation of the network topology which is, in general, denoted as
  22 *Traffic Engineering Database (TED)* in reference to information convey by
  23 the IGP Traffic Engineering routing protocols such as OSPF-TE or IS-IS-TE.
  24 There is many way to store this TED and the IETF is in the process of
  25 defining the corresponding yang model (draft-ietf-teas-yang-te-topo-22.txt).
  26 But, most of these path computation algorithms have been designed with a
  27 particular representation of network model for perfomrance efficiency: a Graph.
  28 This latter is denoted in literature as *G(V, E)* where V, the Vertices,
  29 represent the nodes (e.g. routers) and E, the Edges, represent the link between
  30 nodes. There is numerous graph type, but for path computation, a Directed and
  31 Connected Graph is recommended, again for performance efficiency.
  32
  33 A Connected Graph is a particular graph type where each pair of vertices forms
  34 the endpoints of a path. It is used because path computation algorithms need to
  35 progress smoothly in the graph without searching for the next hops in the whole
  36 graph (mostly for performance issue) and also because some algorithms need to
  37 mark Vertices as visited once processed to avoid loop. Connected Graph is a
  38 particular graph type where each pair of vertices forms the endpoints of a
  39 path.
  40
  41 In general, for modern networks (i.e. with optical links), links are considered
  42 as full-duplex. Thus, from a resources (mostly bandwidth) point of view, going
  43 from node *A to B* will consumes resources (mostly bandwidth) on the link from
  44 A to B while keeping intact resources on the link from B to A. So, the graph
  45 model needs to reflect this behaviour. The graph that represents the network
  46 will used Directed Edges for that purposes. So, the recommended graph is a
  47 Directed Graph (sometimes also named Oriented Graph). As a consequence, it is
  48 necessary to create 2 edges between 2 vertices: *A to B* and *B to A*.
  49
  50 For more information, reader could refer to Graph Theory
  51 e.g. https://en.wikipedia.org/wiki/Graph_theory and Path Computation algorithms
  52 e.g. Shortest Path First (SPF) https://en.wikipedia.org/wiki/Shortest_path_problem
  53 and Constrainted Shortest Path First (CSPF) https://en.wikipedia.org/wiki/Constrained_Shortest_Path_First.
  54
  55 Yang Model for Graph
  56 ^^^^^^^^^^^^^^^^^^^^
  57
  58 In order to manipulate the Graph within the OpenDaylight Data Store, the given
  59 yang model has been provided. It defines Edges and Vertices. Edges are enhanced
  60 by Edges Attributes which are define all link attributes we could collect from
  61 real network (e.g. through BGP Link State). Vertices are enhanced by Prefixes
  62 in order to find quickly where End Points of a path are attached in the Graph.
  63 It also serves to store Segment Routing information when computing path for
  64 Segment Routing TE setup.
  65
  66 A new yang model is provided as an alternative to the IETF yang-te-topo model
  67 and IETF RFC8345 for several reasons:
  68
  69  * Some link and node parameters (e.g. Segment Routing, TE Metric extensions)
  70    which are available in IP/MPLS networks, through the IGP-TE or BGP-LS
  71    protocols (see Linkstate Routes in BGP RIB) are not present in the IETF
  72    ted model
  73  * Node and link identifier are represented as string in the IETF ted model
  74    which it is not efficient when looking into a HashMap() to find node or
  75    link by its identifier
  76  * Even if LinkstateTopologyBuilder() provided mechanism to fulfil IETF ted
  77    model in the datastore, the NodeHolder an TpHolder classes have been
  78    defined as private, and thus could not be used outside the
  79    LinkstateTopologyBuilder() class
  80
  81 Graph and Algorithm have been also designed to be used by other projects
  82 (e.g. openflow) which not control IP/MPLS network. Thus, even if the graph
  83 model addresses in first case the IP/MPLS network, its genericity allows
  84 it to be suitable for other network types.
  85
  86 The yand model for the Graph is as follow:
  87
  88 .. code-block:: console
  89
  90         module: graph
  91         +--rw graph-topology
  92             +--rw graph* [name]
  93                 +--rw name            string
  94                 +--rw domain-scope?   enumeration
  95                 +--rw asn?            uint32
  96                 +--rw vertex* [vertex-id]
  97                 |  +--rw vertex-id      uint64
  98                 |  +--rw name?          string
  99                 |  +--rw router-id?     inet:ip-address
 100                 |  +--rw vertex-type?   enumeration
 101                 |  +--rw srgb
 102                 |  |  +--rw lower-bound?   uint32
 103                 |  |  +--rw range-size?    uint32
 104                 |  +--rw asn?           uint32
 105                 +--rw edge* [edge-id]
 106                 |  +--rw edge-id             uint64
 107                 |  +--rw local-vertex-id?    uint64
 108                 |  +--rw remote-vertex-id?   uint64
 109                 |  +--rw name?               string
 110                 |  +--rw edge-attributes
 111                 |     +--rw metric?                    uint32
 112                 |     +--rw te-metric?                 uint32
 113                 |     +--rw admin-group?               uint32
 114                 |     +--rw local-address?             inet:ip-address
 115                 |     +--rw remote-address?            inet:ip-address
 116                 |     +--rw local-identifier?          uint32
 117                 |     +--rw remote-identifier?         uint32
 118                 |     +--rw max-link-bandwidth?        decimal-bandwidth
 119                 |     +--rw max-resv-link-bandwidth?   decimal-bandwidth
 120                 |     +--rw unreserved-bandwidth* [class-type]
 121                 |     |  +--rw class-type    uint8
 122                 |     |  +--rw bandwidth?    decimal-bandwidth
 123                 |     +--rw delay?                     delay
 124                 |     +--rw min-max-delay
 125                 |     |  +--rw min-delay?   delay
 126                 |     |  +--rw max-delay?   delay
 127                 |     +--rw jitter?                    delay
 128                 |     +--rw loss?                      loss
 129                 |     +--rw residual-bandwidth?        decimal-bandwidth
 130                 |     +--rw available-bandwidth?       decimal-bandwidth
 131                 |     +--rw utilized-bandwidth?        decimal-bandwidth
 132                 |     +--rw adj-sid?                   uint32
 133                 |     +--rw backup-adj-sid?            uint32
 134                 |     +--rw srlgs*                     uint32
 135                 +--rw prefix* [prefix]
 136                 +--rw prefix        inet:ip-prefix
 137                 +--rw prefix-sid?   uint32
 138                 +--rw node-sid?     boolean
 139                 +--rw vertex-id?    uint64
 140
 141 Java Class for Connected Graph
 142 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 143
 144 Yang model represents data as a Flat Tree hierarchy. However, this particular
 145 graph representation (without a specific storage engine capabilities) is not
 146 very useful for Path Computation due to lower performance compared to other
 147 Graph types. Of course path computation algorithms could play with a such
 148 Graph, but at the cost of performance issue as algorithms need to search the
 149 neighbours of a vertices at each step when progressing in the graph. This will
 150 decrease the performance by a factor of *N* to *N²* depending of the
 151 algorithms. For large scale network, say 1000+ nodes, it is too high.
 152
 153 Yang syntax authorizes reference to other grouping or leaf with 'leafref'.
 154 This could allows from a Vertex to access to Edges. However, it is not possible
 155 to achieve a cross reference between Vertex and Edge. In Connected Graph,
 156 both Vertex and Edge must reference each together: from Vertex it is needed to
 157 access directly at the list of Edges connected to this Vertex, and from Edge,
 158 it is need to access directly at the source and destination Vertex.
 159
 160 So, to overcome this limitation, the implemented Graph is composed of two
 161 pieces:
 162
 163  * A standard Graph modeled in yang and stored in the Data Store
 164  * A Connected Graph version based on the yang model but stored in memory only
 165
 166
 167 The connected version of Vertex is composed of:
 168
 169 .. code-block:: java
 170
 171     /* Reference to input and output Connected Edge within the Connected Graph */
 172     private ArrayList<ConnectedEdgeImpl> input = new ArrayList<>();
 173     private ArrayList<ConnectedEdgeImpl> output = new ArrayList<>();
 174
 175     /* List of Prefixes announced by this Vertex */
 176     private ArrayList<Prefix> prefixes = new ArrayList<>();
 177
 178     /* Reference to the Vertex of the standard Graph associated to the Connected Graph */
 179     private Vertex vertex = null;
 180
 181 Where distinction is made between input and output Edges in order to respect the Directed Graph
 182 behviour.
 183
 184 The connected version of Edges is composed of:
 185
 186 .. code-block:: java
 187
 188     /* Reference to Source and Destination Connected Vertex within the Connected Graph */
 189     private ConnectedVertexImpl source;
 190     private ConnectedVertexImpl destination;
 191
 192     /* Reference to the Edge within the Graph associated to the Connected Graph */
 193     private Edge edge;
 194
 195 Where source and destination Vertices also ease to implement the Directed Graph.
 196
 197 And finally, the connected version of Graph is composed of:
 198
 199 .. code-block:: java
 200
 201     /* List of Connected Vertics that composed this Connected Graph */
 202     private final HashMap<Long, ConnectedVertexImpl> vertices = new HashMap<>();
 203
 204     /* List of Connected Edges that composed this Connected Graph */
 205     private final HashMap<Long, ConnectedEdgeImpl> edges = new HashMap<>();
 206
 207     /* List of IP prefix attached to Vertices */
 208     private final HashMap<IpPrefix, Prefix> prefixes = new HashMap<>();
 209
 210     /* Reference to the non connected Graph stored in DataStore */
 211     private Graph graph;
 212
 213 Where Vertices, Edges and Prefixes are stored in *HashMap* to speed up the
 214 access of a given element of the Graph.
 215
 216 Note that the Unique Key identifier for Connected Edge and Connected Vertex
 217 must not be equal to zero (and as a consequence the Edge and Vertex key).
 218 This restriction is due to some algorithms that used the value 0 as a
 219 special indication during the path computation.
 220