diff options
Diffstat (limited to 'doc/developer/link-state.rst')
| -rw-r--r-- | doc/developer/link-state.rst | 499 |
1 files changed, 499 insertions, 0 deletions
diff --git a/doc/developer/link-state.rst b/doc/developer/link-state.rst new file mode 100644 index 0000000..aaa253d --- /dev/null +++ b/doc/developer/link-state.rst @@ -0,0 +1,499 @@ +Link State API Documentation +============================ + +Introduction +------------ + +The Link State (LS) API aims to provide a set of structures and functions to +build and manage a Traffic Engineering Database for the various FRR daemons. +This API has been designed for several use cases: + +- BGP Link State (BGP-LS): where BGP protocol need to collect the link state + information from the routing daemons (IS-IS and/or OSPF) to implement RFC7752 +- Path Computation Element (PCE): where path computation algorithms are based + on Traffic Engineering Database +- ReSerVation Protocol (RSVP): where signaling need to know the Traffic + Engineering topology of the network in order to determine the path of + RSVP tunnels + +Architecture +------------ + +The main requirements from the various uses cases are as follow: + +- Provides a set of data model and function to ease Link State information + manipulation (storage, serialize, parse ...) +- Ease and normalize Link State information exchange between FRR daemons +- Provides database structure for Traffic Engineering Database (TED) + +To ease Link State understanding, FRR daemons have been classified into two +categories: + +- **Consumer**: Daemons that consume Link State information e.g. BGPd +- **Producer**: Daemons that are able to collect Link State information and + send them to consumer daemons e.g. OSPFd IS-ISd + +Zebra daemon, and more precisely, the ZAPI message is used to convey the Link +State information between *producer* and *consumer*, but, Zebra acts as a +simple pass through and does not store any Link State information. A new ZAPI +**Opaque** message has been design for that purpose. + +Each consumer and producer daemons are free to store or not Link State data and +organise the information following the Traffic Engineering Database model +provided by the API or any other data structure e.g. Hash, RB-tree ... + +Link State API +-------------- + +This is the low level API that allows any daemons manipulate the Link State +elements that are stored in the Link State Database. + +Data structures +^^^^^^^^^^^^^^^ + +3 types of Link State structure have been defined: + +.. c:struct:: ls_node + + that groups all information related to a node + +.. c:struct:: ls_attributes + + that groups all information related to a link + +.. c:struct:: ls_prefix + + that groups all information related to a prefix + +These 3 types of structures are those handled by BGP-LS (see RFC7752) and +suitable to describe a Traffic Engineering topology. + +Each structure, in addition to the specific parameters, embed the node +identifier which advertises the Link State and a bit mask as flags to +indicates which parameters are valid i.e. for which the value is valid and +corresponds to a Link State information conveyed by the routing protocol. + +.. c:struct:: ls_node_id + + defines the Node identifier as router ID IPv4 address plus the area ID for + OSPF or the ISO System ID plus the IS-IS level for IS-IS. + +Functions +^^^^^^^^^ + +A set of functions is provided to create, delete and compare Link State +Node, Atribute and Prefix: + +.. c:function:: struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr router_id, struct in6_addr router6_id) +.. 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) +.. c:function:: struct ls_prefix *ls_prefix_new(struct ls_node_id adv, struct prefix p) + + Create respectively a new Link State Node, Attribute or Prefix. + Structure is dynamically allocated. Link State Node ID (adv) is mandatory + and: + + - at least one of IPv4 or IPv6 must be provided for the router ID + (router_id or router6_id) for Node + - at least one of local, local6 or local_id must be provided for Attribute + - prefix is mandatory for Link State Prefix. + +.. c:function:: void ls_node_del(struct ls_node *node) +.. c:function:: void ls_attributes_del(struct ls_attributes *attr) +.. c:function:: void ls_prefix_del(struct ls_prefix *pref) + + Remove, respectively Link State Node, Attributes or Prefix. + Data structure is freed. + +.. c:function:: void ls_attributes_srlg_del(struct ls_attributes *attr) + + Remove SRLGs attribute if defined. Data structure is freed. + +.. c:function:: int ls_node_same(struct ls_node *n1, struct ls_node *n2) +.. c:function:: int ls_attributes_same(struct ls_attributes *a1, struct ls_attributes *a2) +.. c:function:: int ls_prefix_same(struct ls_prefix *p1, struct ls_prefix*p2) + + Check, respectively if two Link State Nodes, Attributes or Prefix are equal. + Note that these routines have the same return value sense as '==' (which is + different from a comparison). + + +Link State TED +-------------- + +This is the high level API that provides functions to create, update, delete a +Link State Database to build a Traffic Engineering Database (TED). + +Data Structures +^^^^^^^^^^^^^^^ + +The Traffic Engineering is modeled as a Graph in order to ease Path Computation +algorithm implementation. Denoted **G(V, E)**, a graph is composed by a list of +**Vertices (V)** which represents the network Node and a list of **Edges (E)** +which represents Link. An additional list of **prefixes (P)** is also added and +also attached to the *Vertex (V)* which advertise it. + +*Vertex (V)* contains the list of outgoing *Edges (E)* that connect this Vertex +with its direct neighbors and the list of incoming *Edges (E)* that connect +the direct neighbors to this Vertex. Indeed, the *Edge (E)* is unidirectional, +thus, it is necessary to add 2 Edges to model a bidirectional relation between +2 Vertices. Finally, the *Vertex (V)* contains a pointer to the corresponding +Link State Node. + +*Edge (E)* contains the source and destination Vertex that this Edge +is connecting and a pointer to the corresponding Link State Attributes. + +A unique Key is used to identify both Vertices and Edges within the Graph. + + +:: + + -------------- --------------------------- -------------- + | Connected |---->| Connected Edge Va to Vb |--->| Connected | + --->| Vertex | --------------------------- | Vertex |----> + | | | | + | - Key (Va) | | - Key (Vb) | + <---| - Vertex | --------------------------- | - Vertex |<---- + | |<----| Connected Edge Vb to Va |<---| | + -------------- --------------------------- -------------- + + +4 data structures have been defined to implement the Graph model: + +.. c:struct:: ls_vertex +.. c:struct:: ls_edge +.. c:struct:: ls_ted + + - :c:struct:`ls_prefix` + +TED stores Vertex, Edge and Subnet elements with a RB Tree structure. +The Vertex key corresponds to the Router ID for OSPF and ISO System ID for +IS-IS. The Edge key corresponds to the IPv4 address, the lowest 64 bits of +the IPv6 address or the combination of the local & remote ID of the interface. +The Subnet key corresponds to the Prefix address (v4 or v6). + +An additional status for Vertex, Edge and Subnet allows to determine the state +of the element in the TED: UNSET, NEW, UPDATE, DELETE, SYNC, ORPHAN. Normal +state is SYNC. NEW, UPDATE and DELETE are temporary state when element is +processed. UNSET is normally never used and ORPHAN serves to identify elements +that must be remove when TED is cleaning. + +Vertex, Edges and Subnets management functions +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +.. c:function:: struct ls_vertex *ls_vertex_add(struct ls_ted *ted, struct ls_node *node) +.. c:function:: struct ls_edge *ls_edge_add(struct ls_ted *ted, struct ls_attributes *attributes) +.. c:function:: struct ls_subnet *ls_subnet_add(struct ls_ted *ted, struct ls_prefix *pref) + + Add, respectively new Vertex, Edge or Subnet to the Link State Datebase. + Vertex, Edge or Subnet are created from, respectively the Link State Node, + Attribute or Prefix structure. Data structure are dynamically allocated. + +.. c:function:: struct ls_vertex *ls_vertex_update(struct ls_ted *ted, struct ls_node *node) +.. c:function:: struct ls_edge *ls_edge_update(struct ls_ted *ted, struct ls_attributes *attributes) +.. c:function:: struct ls_subnet *ls_subnet_update(struct ls_ted *ted, struct ls_prefix *pref) + + Update, respectively Vertex, Edge or Subnet with, respectively the Link + State Node, Attribute or Prefix. A new data structure is created if no one + corresponds to the Link State Node, Attribute or Prefix. If element already + exists in the TED, its associated Link State information is replaced by the + new one if there are different and the old associated Link State information + is deleted and memory freed. + +.. c:function:: void ls_vertex_del(struct ls_ted *ted, struct ls_vertex *vertex) +.. c:function:: void ls_vertex_del_all(struct ls_ted *ted, struct ls_vertex *vertex) +.. c:function:: void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge) +.. c:function:: void ls_edge_del_all(struct ls_ted *ted, struct ls_edge *edge) +.. c:function:: void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet) +.. c:function:: void ls_subnet_del_all(struct ls_ted *ted, struct ls_subnet *subnet) + + Delete, respectively Link State Vertex, Edge or Subnet. Data structure are + freed but not the associated Link State information with the simple `_del()` + form of the function while the `_del_all()` version freed also associated + Link State information. TED is not modified if Vertex, Edge or Subnet is + NULL or not found in the Data Base. Note that references between Vertices, + Edges and Subnets are removed first. + +.. c:function:: struct ls_vertex *ls_find_vertex_by_key(struct ls_ted *ted, const uint64_t key) +.. c:function:: struct ls_vertex *ls_find_vertex_by_id(struct ls_ted *ted, struct ls_node_id id) + + Find Vertex in the TED by its unique key or its Link State Node ID. + Return Vertex if found, NULL otherwise. + +.. c:function:: struct ls_edge *ls_find_edge_by_key(struct ls_ted *ted, const uint64_t key) +.. c:function:: struct ls_edge *ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes); +.. c:function:: struct ls_edge *ls_find_edge_by_destination(struct ls_ted *ted, struct ls_attributes *attributes); + + Find Edge in the Link State Data Base by its key, source or distination + (local IPv4 or IPv6 address or local ID) informations of the Link State + Attributes. Return Edge if found, NULL otherwise. + +.. c:function:: struct ls_subnet *ls_find_subnet(struct ls_ted *ted, const struct prefix prefix) + + Find Subnet in the Link State Data Base by its key, i.e. the associated + prefix. Return Subnet if found, NULL otherwise. + +.. c:function:: int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2) +.. c:function:: int ls_edge_same(struct ls_edge *e1, struct ls_edge *e2) +.. c:function:: int ls_subnet_same(struct ls_subnet *s1, struct ls_subnet *s2) + + Check, respectively if two Vertices, Edges or Subnets are equal. + Note that these routines has the same return value sense as '==' + (which is different from a comparison). + + +TED management functions +^^^^^^^^^^^^^^^^^^^^^^^^ + +Some helpers functions have been also provided to ease TED management: + +.. c:function:: struct ls_ted *ls_ted_new(const uint32_t key, char *name, uint32_t asn) + + Create a new Link State Data Base. Key must be different from 0. + Name could be NULL and AS number equal to 0 if unknown. + +.. c:function:: void ls_ted_del(struct ls_ted *ted) +.. c:function:: void ls_ted_del_all(struct ls_ted *ted) + + Delete existing Link State Data Base. Vertices, Edges, and Subnets are not + removed with ls_ted_del() function while they are with ls_ted_del_all(). + +.. c:function:: void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst, struct ls_edge *edge) + + Connect Source and Destination Vertices by given Edge. Only non NULL source + and destination vertices are connected. + +.. c:function:: void ls_connect(struct ls_vertex *vertex, struct ls_edge *edge, bool source) +.. c:function:: void ls_disconnect(struct ls_vertex *vertex, struct ls_edge *edge, bool source) + + Connect / Disconnect Link State Edge to the Link State Vertex which could be + a Source (source = true) or a Destination (source = false) Vertex. + +.. c:function:: void ls_disconnect_edge(struct ls_edge *edge) + + Disconnect Link State Edge from both Source and Destination Vertex. + Note that Edge is not removed but its status is marked as ORPHAN. + +.. c:function:: void ls_vertex_clean(struct ls_ted *ted, struct ls_vertex *vertex, struct zclient *zclient) + + Clean Vertex structure by removing all Edges and Subnets marked as ORPHAN + from this vertex. Corresponding Link State Update message is sent if zclient + parameter is not NULL. Note that associated Link State Attribute and Prefix + are also removed and memory freed. + +.. c:function:: void ls_ted_clean(struct ls_ted *ted) + + Clean Link State Data Base by removing all Vertices, Edges and SubNets + marked as ORPHAN. Note that associated Link State Node, Attributes and + Prefix are removed too. + +.. c:function:: void ls_show_vertex(struct ls_vertex *vertex, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_edge(struct ls_edeg *edge, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_subnet(struct ls_subnet *subnet, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_vertices(struct ls_ted *ted, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_edges(struct ls_ted *ted, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_subnets(struct ls_ted *ted, struct vty *vty, struct json_object *json, bool verbose) +.. c:function:: void ls_show_ted(struct ls_ted *ted, struct vty *vty, struct json_object *json, bool verbose) + + Respectively, show Vertex, Edge, Subnet provided as parameter, all Vertices, + all Edges, all Subnets and the whole TED if not specified. Output could be + more detailed with verbose parameter for VTY output. If both JSON and VTY + output are specified, JSON takes precedence over VTY. + +.. c:function:: void ls_dump_ted(struct ls_ted *ted) + + Dump TED information to the current logging output. + +Link State Messages +------------------- + +This part of the API provides functions and data structure to ease the +communication between the *Producer* and *Consumer* daemons. + +Communications principles +^^^^^^^^^^^^^^^^^^^^^^^^^ + +Recent ZAPI Opaque Message is used to exchange Link State data between daemons. +For that purpose, Link State API provides new functions to serialize and parse +Link State information through the ZAPI Opaque message. A dedicated flag, +named ZAPI_OPAQUE_FLAG_UNICAST, allows daemons to send a unicast or a multicast +Opaque message and is used as follow for the Link State exchange: + +- Multicast: To send data update to all daemons that have subscribed to the + Link State Update message +- Unicast: To send initial Link State information from a particular daemon. All + data are send only to the daemon that request Link State Synchronisatio + +Figure 1 below, illustrates the ZAPI Opaque message exchange between a +*Producer* (an IGP like OSPF or IS-IS) and a *Consumer* (e.g. BGP). The +message sequences are as follows: + +- First, both *Producer* and *Consumer* must register to their respective ZAPI + Opaque Message: **Link State Sync** for the *Producer* in order to receive + Database synchronisation request from a *Consumer*, **Link State Update** for + the *Consumer* in order to received any Link State update from a *Producer*. + These register messages are stored by Zebra to determine to which daemon it + should redistribute the ZAPI messages it receives. +- Then, the *Consumer* sends a **Link State Synchronistation** request with the + Multicast method in order to receive the complete Link State Database from a + *Producer*. ZEBRA daemon forwards this message to any *Producer* daemons that + previously registered to this message. If no *Producer* has yet registered, + the request is lost. Thus, if the *Consumer* receives no response whithin a + given timer, it means that no *Producer* are available right now. So, the + *Consumer* must send the same request until it receives a Link State Database + Synchronistation message. This behaviour is necessary as we can't control in + which order daemons are started. It is up to the *Consumer* daemon to fix the + timeout and the number of retry. +- When a *Producer* receives a **Link State Synchronisation** request, it + starts sending all elements of its own Link State Database through the + **Link State Database Synchronisation** message. These messages are send with + the Unicast method to avoid flooding other daemons with these elements. ZEBRA + layer ensures to forward the message to the right daemon. +- When a *Producer* update its Link State Database, it automatically sends a + **Link State Update** message with the Multicast method. In turn, ZEBRA + daemon forwards the message to all *Consumer* daemons that previously + registered to this message. if no daemon is registered, the message is lost. +- A daemon could unregister from the ZAPI Opaque message registry at any time. + In this case, the ZEBRA daemon stops to forward any messages it receives to + this daemon, even if it was previously converns. + +:: + + IGP ZEBRA Consumer + (OSPF/IS-IS) (ZAPI Opaque Thread) (e.g. BGP) + | | | \ + | | Register LS Update | | + | |<----------------------------| Register Phase + | | | | + | | Request LS Sync | | + | |<----------------------------| | + : : : A | + | Register LS Sync | | | | + |----------------------------->| | | / + : : : |TimeOut + : : : | + | | | | + | | Request LS Sync | v \ + | Request LS Sync |<----------------------------| | + |<-----------------------------| | Synchronistation + | LS DB Update | | Phase + |----------------------------->| LS DB Update | | + | |---------------------------->| | + | LS DB Update (cont'd) | | | + |----------------------------->| LS DB Update (cont'd) | | + | . |---------------------------->| | + | . | . | | + | . | . | | + | LS DB Update (end) | . | | + |----------------------------->| LS DB Update (end) | | + | |---------------------------->| | + | | | / + : : : + : : : + | LS DB Update | | \ + |----------------------------->| LS DB Update | | + | |---------------------------->| Update Phase + | | | | + : : : / + : : : + | | | \ + | | Unregister LS Update | | + | |<----------------------------| Deregister Phase + | | | | + | LS DB Update | | | + |----------------------------->| | | + | | | / + | | | + + Figure 1: Link State messages exchange + + +Data Structures +^^^^^^^^^^^^^^^ + +The Link State Message is defined to convey Link State parameters from +the routing protocol (OSPF or IS-IS) to other daemons e.g. BGP. + +.. c:struct:: ls_message + +The structure is composed of: + +- Event of the message: + + - Sync: Send the whole LS DB following a request + - Add: Send the a new Link State element + - Update: Send an update of an existing Link State element + - Delete: Indicate that the given Link State element is removed + +- Type of Link State element: Node, Attribute or Prefix +- Remote node id when known +- Data: Node, Attributes or Prefix + +A Link State Message can carry only one Link State Element (Node, Attributes +of Prefix) at once, and only one Link State Message is sent through ZAPI +Opaque Link State type at once. + +Functions +^^^^^^^^^ + +.. c:function:: int ls_register(struct zclient *zclient, bool server) +.. c:function:: int ls_unregister(struct zclient *zclient, bool server) + + Register / Unregister daemon to received ZAPI Link State Opaque messages. + Server must be set to true for *Producer* and to false for *Consumer*. + +.. c:function:: int ls_request_sync(struct zclient *zclient) + + Request initial Synchronisation to collect the whole Link State Database. + +.. c:function:: struct ls_message *ls_parse_msg(struct stream *s) + + Parse Link State Message from stream. Used this function once receiving a + new ZAPI Opaque message of type Link State. + +.. c:function:: void ls_delete_msg(struct ls_message *msg) + + Delete existing message. Data structure is freed. + +.. c:function:: int ls_send_msg(struct zclient *zclient, struct ls_message *msg, struct zapi_opaque_reg_info *dst) + + Send Link State Message as new ZAPI Opaque message of type Link State. + If destination is not NULL, message is sent as Unicast otherwise it is + broadcast to all registered daemon. + +.. c:function:: struct ls_message *ls_vertex2msg(struct ls_message *msg, struct ls_vertex *vertex) +.. c:function:: struct ls_message *ls_edge2msg(struct ls_message *msg, struct ls_edge *edge) +.. c:function:: struct ls_message *ls_subnet2msg(struct ls_message *msg, struct ls_subnet *subnet) + + Create respectively a new Link State Message from a Link State Vertex, Edge + or Subnet. If Link State Message is NULL, a new data structure is + dynamically allocated. Note that the Vertex, Edge and Subnet status is used + to determine the corresponding Link State Message event: ADD, UPDATE, + DELETE, SYNC. + +.. c:function:: int ls_msg2vertex(struct ls_ted *ted, struct ls_message *msg) +.. c:function:: int ls_msg2edge(struct ls_ted *ted, struct ls_message *msg) +.. c:function:: int ls_msg2subnet(struct ls_ted *ted, struct ls_message *msg) + + Convert Link State Message respectively in Vertex, Edge or Subnet and + update the Link State Database accordingly to the message event: SYNC, ADD, + UPDATE or DELETE. + +.. c:function:: struct ls_element *ls_msg2ted(struct ls_ted *ted, struct ls_message *msg, bool delete) +.. c:function:: struct ls_element *ls_stream2ted(struct ls_ted *ted, struct ls_message *msg, bool delete) + + Convert Link State Message or Stream Buffer in a Link State element (Vertex, + Edge or Subnet) and update the Link State Database accordingly to the + message event: SYNC, ADD, UPDATE or DELETE. The function return the generic + structure ls_element that point to the Vertex, Edge or Subnet which has been + added, updated or synchronous in the database. Note that the delete boolean + parameter governs the action for the DELETE action: true, Link State Element + is removed from the database and NULL is return. If set to false, database + is not updated and the function sets the Link State Element status to + Delete and return the element for futur deletion by the calling function. + +.. c:function:: int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient, struct zapi_opaque_reg_info *dst) + + Send all the content of the Link State Data Base to the given destination. + Link State content is sent is this order: Vertices, Edges then Subnet. + This function must be used when a daemon request a Link State Data Base + Synchronization. |