doc/developer/link-state.rst

   1 Link State API Documentation
   2 ============================
   3
   4 Introduction
   5 ------------
   6
   7 The Link State (LS) API aims to provide a set of structures and functions to
   8 build and manage a Traffic Engineering Database for the various FRR daemons.
   9 This API has been designed for several use cases:
  10
  11 - BGP Link State (BGP-LS): where BGP protocol need to collect the link state
  12   information from the routing daemons (IS-IS and/or OSPF) to implement RFC7572
  13 - Path Computation Element (PCE): where path computation algorithms are based
  14   on Traffic Engineering Database
  15 - ReSerVation Protocol (RSVP): where signaling need to know the Traffic
  16   Engineering topology of the network in order to determine the path of
  17   RSVP tunnels
  18
  19 Architecture
  20 ------------
  21
  22 The main requirements from the various uses cases are as follow:
  23
  24 - Provides a set of data model and function to ease Link State information
  25   manipulation (storage, serialize, parse ...)
  26 - Ease and normalize Link State information exchange between FRR daemons
  27 - Provides database structure for Traffic Engineering Database (TED)
  28
  29 To ease Link State understanding, FRR daemons have been classified into two
  30 categories:
  31
  32 - **Consumer**: Daemons that consume Link State information e.g. BGPd
  33 - **Producer**: Daemons that are able to collect Link State information and
  34   send them to consumer daemons e.g. OSPFd IS-ISd
  35
  36 Zebra daemon, and more precisely, the ZAPI message is used to convey the Link
  37 State information between *producer* and *consumer*, but, Zebra acts as a
  38 simple pass through and does not store any Link State information. A new ZAPI
  39 **Opaque** message has been design for that purpose.
  40
  41 Each consumer and producer daemons are free to store or not Link State data and
  42 organise the information following the Traffic Engineering Database model
  43 provided by the API or any other data structure e.g. Hash, RB-tree ...
  44
  45 Link State API
  46 --------------
  47
  48 This is the low level API that allows any daemons manipulate the Link State
  49 elements that are stored in the Link State Database.
  50
  51 Data structures
  52 ^^^^^^^^^^^^^^^
  53
  54 3 types of Link State structure have been defined:
  55
  56 .. c:type:: struct ls_node
  57
  58    that groups all information related to a node
  59
  60 .. c:type:: struct ls_attributes
  61
  62    that groups all information related to a link
  63
  64 .. c:type:: struct ls_prefix
  65
  66    that groups all information related to a prefix
  67
  68 These 3 types of structures are those handled by BGP-LS (see RFC7752) and
  69 suitable to describe a Traffic Engineering topology.
  70
  71 Each structure, in addition to the specific parameters, embed the node
  72 identifier which advertises the Link State and a bit mask as flags to
  73 indicates which parameters are valid i.e. for which the value is valid and
  74 corresponds to a Link State information conveyed by the routing protocol.
  75
  76 .. c:type:: struct ls_node_id
  77
  78    defines the Node identifier as router ID IPv4 address plus the area ID for
  79    OSPF or the ISO System ID plus the IS-IS level for IS-IS.
  80
  81 Functions
  82 ^^^^^^^^^
  83
  84 A set of functions is provided to create, delete and compare Link State Node:
  85
  86 .. c:function:: struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr router_id, struct in6_addr router6_id)
  87 .. c:function:: voidls_node_del(struct ls_node *node)
  88 .. c:function:: int ls_node_same(struct ls_node *n1, struct ls_node *n2)
  89
  90 and Link State Attributes:
  91
  92 .. c:function:: struct ls_attributes *ls_attributes_new(struct ls_node_id adv, struct in_addr local, struct in6_addr local6, uint32_t local_id)
  93 .. c:function:: void ls_attributes_del(struct ls_attributes *attr)
  94 .. c:function:: int ls_attributes_same(struct ls_attributes *a1, struct ls_attributes *a2)
  95
  96 The low level API doesn't provide any particular functions for the Link State
  97 Prefix structure as this latter is simpler to manipulate.
  98
  99 Link State TED
 100 --------------
 101
 102 This is the high level API that provides functions to create, update, delete a
 103 Link State Database to from a Traffic Engineering Database (TED).
 104
 105 Data Structures
 106 ^^^^^^^^^^^^^^^
 107
 108 The Traffic Engineering is modeled as a Graph in order to ease Path Computation
 109 algorithm implementation. Denoted **G(V, E)**, a graph is composed by a list of
 110 **Vertices (V)** which represents the network Node and a list of **Edges (E)**
 111 which represents Link. An additional list of **prefixes (P)** is also added and
 112 also attached to the *Vertex (V)* which advertise it.
 113
 114 *Vertex (V)* contains the list of outgoing *Edges (E)* that connect this Vertex
 115 with its direct neighbors and the list of incoming *Edges (E)* that connect
 116 the direct neighbors to this Vertex. Indeed, the *Edge (E)* is unidirectional,
 117 thus, it is necessary to add 2 Edges to model a bidirectional relation between
 118 2 Vertices. Finally, the *Vertex (V)* contains a pointer to the corresponding
 119 Link State Node.
 120
 121 *Edge (E)* contains the source and destination Vertex that this Edge
 122 is connecting and a pointer to the corresponding Link State Attributes.
 123
 124 A unique Key is used to identify both Vertices and Edges within the Graph.
 125
 126
 127 ::
 128
 129           --------------     ---------------------------    --------------
 130           | Connected  |---->| Connected Edge Va to Vb |--->| Connected  |
 131       --->|  Vertex    |     ---------------------------    |  Vertex    |---->
 132           |            |                                    |            |
 133           | - Key (Va) |                                    | - Key (Vb) |
 134       <---| - Vertex   |     ---------------------------    | - Vertex   |<----
 135           |            |<----| Connected Edge Vb to Va |<---|            |
 136           --------------     ---------------------------    --------------
 137
 138
 139 4 data structures have been defined to implement the Graph model:
 140
 141 .. c:type:: struct ls_vertex
 142 .. c:type:: struct ls_edge
 143 .. c:type:: struct ls_prefix
 144 .. c:type:: struct ls_ted
 145
 146
 147 Functions
 148 ^^^^^^^^^
 149
 150 .. c:function:: struct ls_vertex *ls_vertex_add(struct ls_ted *ted, struct ls_node *node)
 151 .. c:function:: struct ls_vertex *ls_vertex_update(struct ls_ted *ted, struct ls_node *node)
 152 .. c:function:: void ls_vertex_del(struct ls_ted *ted, struct ls_vertex *vertex)
 153 .. c:function:: struct ls_vertex *ls_find_vertex_by_key(struct ls_ted *ted, const uint64_t key)
 154 .. c:function:: struct ls_vertex *ls_find_vertex_by_id(struct ls_ted *ted, struct ls_node_id id)
 155 .. c:function:: int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2)
 156
 157 .. c:function:: struct ls_edge *ls_edge_add(struct ls_ted *ted, struct ls_attributes *attributes)
 158 .. c:function:: struct ls_edge *ls_edge_update(struct ls_ted *ted, struct ls_attributes *attributes)
 159 .. c:function:: void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge)
 160 .. c:function:: struct ls_edge *ls_find_edge_by_key(struct ls_ted *ted, const uint64_t key)
 161 .. c:function:: struct ls_edge *ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes);
 162 .. c:function:: struct ls_edge *ls_find_edge_by_destination(struct ls_ted *ted, struct ls_attributes *attributes);
 163
 164 .. c:function:: struct ls_subnet *ls_subnet_add(struct ls_ted *ted, struct ls_prefix *pref)
 165 .. c:function:: void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet)
 166 .. c:function:: struct ls_subnet *ls_find_subnet(struct ls_ted *ted, const struct prefix prefix)
 167
 168 .. c:function:: struct ls_ted *ls_ted_new(const uint32_t key, char *name, uint32_t asn)
 169 .. c:function:: void ls_ted_del(struct ls_ted *ted)
 170 .. c:function:: void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst, struct ls_edge *edge)
 171 .. c:function:: void ls_connect(struct ls_vertex *vertex, struct ls_edge *edge, bool source)
 172 .. c:function:: void ls_disconnect(struct ls_vertex *vertex, struct ls_edge *edge, bool source)
 173 .. c:function:: void ls_disconnect_edge(struct ls_edge *edge)
 174
 175
 176 Link State Messages
 177 -------------------
 178
 179 This part of the API provides functions and data structure to ease the
 180 communication between the *Producer* and *Consumer* daemons.
 181
 182 Communications principles
 183 ^^^^^^^^^^^^^^^^^^^^^^^^^
 184
 185 Recent ZAPI Opaque Message is used to exchange Link State data between daemons.
 186 For that purpose, Link State API provides new functions to serialize and parse
 187 Link State information through the ZAPI Opaque message. A dedicated flag,
 188 named ZAPI_OPAQUE_FLAG_UNICAST, allows daemons to send a unicast or a multicast
 189 Opaque message and is used as follow for the Link State exchange:
 190
 191 - Multicast: To send data update to all daemons that have subscribed to the
 192   Link State Update message
 193 - Unicast: To send initial Link State information from a particular daemon. All
 194   data are send only to the daemon that request Link State Synchronisatio
 195
 196 Figure 1 below, illustrates the ZAPI Opaque message exchange between a
 197 *Producer* (an IGP like OSPF or IS-IS) and a *Consumer* (e.g. BGP). The
 198 message sequences are as follows:
 199
 200 - First, both *Producer* and *Consumer* must register to their respective ZAPI
 201   Opaque Message. **Link State Sync** for the *Producer* in order to receive
 202   Database synchronisation request from a *Consumer*. **Link State Update** for
 203   the *Consumer* in order to received any Link State update from a *Producer*.
 204   These register messages are stored by Zebra to determine to which daemon it
 205   should redistribute the ZAPI messages it receives.
 206 - Then, the *Consumer* sends a **Link State Synchronistation** request with the
 207   Multicast method in order to receive the complete Link State Database from a
 208   *Producer*. ZEBRA daemon forwards this message to any *Producer* daemons that
 209   previously registered to this message. If no *Producer* has yet registered,
 210   the request is lost. Thus, if the *Consumer* receives no response whithin a
 211   given timer, it means that no *Producer* are available right now. So, the
 212   *Consumer* must send the same request until it receives a Link State Database
 213   Synchronistation message. This behaviour is necessary as we can't control in
 214   which order daemons are started. It is up to the *Consumer* daemon to fix the
 215   timeout and the number of retry.
 216 - When a *Producer* receives a **Link State Synchronisation** request, it
 217   starts sending all elements of its own Link State Database through the
 218   **Link State Database Synchronisation** message. These messages are send with
 219   the Unicast method to avoid flooding other daemons with these elements. ZEBRA
 220   layer ensures to forward the message to the right daemon.
 221 - When a *Producer* update its Link State Database, it automatically sends a
 222   **Link State Update** message with the Multicast method. In turn, ZEBRA
 223   daemon forwards the message to all *Consumer* daemons that previously
 224   registered to this message. if no daemon is registered, the message is lost.
 225 - A daemon could unregister from the ZAPI Opaque message registry at any time.
 226   In this case, the ZEBRA daemon stops to forward any messages it receives to
 227   this daemon, even if it was previously converns.
 228
 229 ::
 230
 231        IGP                           ZEBRA                        Consumer
 232     (OSPF/IS-IS)               (ZAPI Opaque Thread)              (e.g. BGP)
 233         |                              |                             |           \
 234         |                              |      Register LS Update     |            |
 235         |                              |<----------------------------|   Register Phase
 236         |                              |                             |            |
 237         |                              |      Request LS Sync        |            |
 238         |                              |<----------------------------|            |
 239         :                              :                             :  A         |
 240         |    Register LS Sync          |                             |  |         |
 241         |----------------------------->|                             |  |        /
 242         :                              :                             :  |TimeOut
 243         :                              :                             :  |
 244         |                              |                             |  |
 245         |                              |      Request LS Sync        |  v        \
 246         |    Request LS Sync           |<----------------------------|            |
 247         |<-----------------------------|                             |   Synchronistation
 248         |    LS DB Sync                |                             |           Phase
 249         |----------------------------->|      LS DB Sync             |            |
 250         |                              |---------------------------->|            |
 251         |    LS DB Sync (cont'd)       |                             |            |
 252         |----------------------------->|      LS DB Sync (cont'd)    |            |
 253         |            .                 |---------------------------->|            |
 254         |            .                 |             .               |            |
 255         |            .                 |             .               |            |
 256         |    LS DB Sync (end)          |             .               |            |
 257         |----------------------------->|      LS DB Sync (end)       |            |
 258         |                              |---------------------------->|            |
 259         |                              |                             |           /
 260         :                              :                             :
 261         :                              :                             :
 262         |    LS Update                 |                             |           \
 263         |----------------------------->|      LS Update              |            |
 264         |                              |---------------------------->|      Update Phase
 265         |                              |                             |            |
 266         :                              :                             :           /
 267         :                              :                             :
 268         |                              |                             |           \
 269         |                              |      Unregister LS Update   |            |
 270         |                              |<----------------------------|      Deregister Phase
 271         |                              |                             |            |
 272         |    LS Update                 |                             |            |
 273         |----------------------------->|                             |            |
 274         |                              |                             |           /
 275         |                              |                             |
 276
 277         Figure 1: Link State messages exchange
 278
 279
 280 Data Structures
 281 ^^^^^^^^^^^^^^^
 282
 283 The Link State Message is defined to convey Link State parameters from
 284 the routing protocol (OSPF or IS-IS) to other daemons e.g. BGP.
 285
 286 .. c:type:: struct ls_message
 287
 288 The structure is composed of:
 289
 290 - Event of the message:
 291
 292   - Sync: Send the whole LS DB following a request
 293   - Add: Send the a new Link State element
 294   - Update: Send an update of an existing Link State element
 295   - Delete: Indicate that the given Link State element is removed
 296
 297 - Type of Link State element: Node, Attribute or Prefix
 298 - Remote node id when known
 299 - Data: Node, Attributes or Prefix
 300
 301 A Link State Message can carry only one Link State Element (Node, Attributes
 302 of Prefix) at once, and only one Link State Message is sent through ZAPI
 303 Opaque Link State type at once.
 304
 305 Functions
 306 ^^^^^^^^^
 307
 308 .. c:function:: struct ls_message *ls_parse_msg(struct stream *s)
 309 .. c:function:: int ls_send_msg(struct zclient *zclient, struct ls_message *msg, struct zapi_opaque_reg_info *dst)
 310 .. c:function:: struct ls_message *ls_vertex2msg(struct ls_message *msg, struct ls_vertex *vertex)
 311 .. c:function:: struct ls_message *ls_edge2msg(struct ls_message *msg, struct ls_edge *edge)
 312 .. c:function:: struct ls_message *ls_subnet2msg(struct ls_message *msg, struct ls_subnet *subnet)
 313 .. c:function:: int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient, struct zapi_opaque_reg_info *dst)
 314