summaryrefslogtreecommitdiff
path: root/doc/developer/link-state.rst
diff options
context:
space:
mode:
Diffstat (limited to 'doc/developer/link-state.rst')
-rw-r--r--doc/developer/link-state.rst314
1 files changed, 314 insertions, 0 deletions
diff --git a/doc/developer/link-state.rst b/doc/developer/link-state.rst
new file mode 100644
index 0000000000..f1fc52966b
--- /dev/null
+++ b/doc/developer/link-state.rst
@@ -0,0 +1,314 @@
+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 RFC7572
+- 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:type:: struct ls_node
+
+ that groups all information related to a node
+
+.. c:type:: struct ls_attributes
+
+ that groups all information related to a link
+
+.. c:type:: 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:type:: 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:
+
+.. 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:: voidls_node_del(struct ls_node *node)
+.. c:function:: int ls_node_same(struct ls_node *n1, struct ls_node *n2)
+
+and Link State Attributes:
+
+.. 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:: void ls_attributes_del(struct ls_attributes *attr)
+.. c:function:: int ls_attributes_same(struct ls_attributes *a1, struct ls_attributes *a2)
+
+The low level API doesn't provide any particular functions for the Link State
+Prefix structure as this latter is simpler to manipulate.
+
+Link State TED
+--------------
+
+This is the high level API that provides functions to create, update, delete a
+Link State Database to from 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:type:: struct ls_vertex
+.. c:type:: struct ls_edge
+.. c:type:: struct ls_prefix
+.. c:type:: struct ls_ted
+
+
+Functions
+^^^^^^^^^
+
+.. c:function:: struct ls_vertex *ls_vertex_add(struct ls_ted *ted, struct ls_node *node)
+.. c:function:: struct ls_vertex *ls_vertex_update(struct ls_ted *ted, struct ls_node *node)
+.. c:function:: void ls_vertex_del(struct ls_ted *ted, struct ls_vertex *vertex)
+.. 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)
+.. c:function:: int ls_vertex_same(struct ls_vertex *v1, struct ls_vertex *v2)
+
+.. c:function:: struct ls_edge *ls_edge_add(struct ls_ted *ted, struct ls_attributes *attributes)
+.. c:function:: struct ls_edge *ls_edge_update(struct ls_ted *ted, struct ls_attributes *attributes)
+.. c:function:: void ls_edge_del(struct ls_ted *ted, struct ls_edge *edge)
+.. 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);
+
+.. c:function:: struct ls_subnet *ls_subnet_add(struct ls_ted *ted, struct ls_prefix *pref)
+.. c:function:: void ls_subnet_del(struct ls_ted *ted, struct ls_subnet *subnet)
+.. c:function:: struct ls_subnet *ls_find_subnet(struct ls_ted *ted, const struct prefix prefix)
+
+.. c:function:: struct ls_ted *ls_ted_new(const uint32_t key, char *name, uint32_t asn)
+.. c:function:: void ls_ted_del(struct ls_ted *ted)
+.. c:function:: void ls_connect_vertices(struct ls_vertex *src, struct ls_vertex *dst, struct ls_edge *edge)
+.. 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)
+.. c:function:: void ls_disconnect_edge(struct ls_edge *edge)
+
+
+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 Sync | | Phase
+ |----------------------------->| LS DB Sync | |
+ | |---------------------------->| |
+ | LS DB Sync (cont'd) | | |
+ |----------------------------->| LS DB Sync (cont'd) | |
+ | . |---------------------------->| |
+ | . | . | |
+ | . | . | |
+ | LS DB Sync (end) | . | |
+ |----------------------------->| LS DB Sync (end) | |
+ | |---------------------------->| |
+ | | | /
+ : : :
+ : : :
+ | LS Update | | \
+ |----------------------------->| LS Update | |
+ | |---------------------------->| Update Phase
+ | | | |
+ : : : /
+ : : :
+ | | | \
+ | | Unregister LS Update | |
+ | |<----------------------------| Deregister Phase
+ | | | |
+ | LS 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:type:: 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:: struct ls_message *ls_parse_msg(struct stream *s)
+.. c:function:: int ls_send_msg(struct zclient *zclient, struct ls_message *msg, struct zapi_opaque_reg_info *dst)
+.. 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)
+.. c:function:: int ls_sync_ted(struct ls_ted *ted, struct zclient *zclient, struct zapi_opaque_reg_info *dst)
+