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:
-
struct ls_node
that groups all information related to a node
-
struct ls_attributes
that groups all information related to a link
-
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.
-
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:
-
struct ls_node *ls_node_new(struct ls_node_id adv, struct in_addr router_id, struct in6_addr router6_id)
-
struct ls_attributes *ls_attributes_new(struct ls_node_id adv, struct in_addr local, struct in6_addr local6, uint32_t local_id)
-
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.
-
void ls_attributes_del(struct ls_attributes *attr)
-
void ls_prefix_del(struct ls_prefix *pref)
Remove, respectively Link State Node, Attributes or Prefix. Data structure is freed.
-
void ls_attributes_srlg_del(struct ls_attributes *attr)
Remove SRLGs attribute if defined. Data structure is freed.
-
int ls_attributes_same(struct ls_attributes *a1, struct ls_attributes *a2)
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:
-
struct ls_vertex
-
struct ls_edge
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
-
struct ls_edge *ls_edge_add(struct ls_ted *ted, struct ls_attributes *attributes)
-
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.
-
struct ls_edge *ls_edge_update(struct ls_ted *ted, struct ls_attributes *attributes)
-
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.
-
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.
-
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.
-
struct ls_edge *ls_find_edge_by_source(struct ls_ted *ted, struct ls_attributes *attributes);
-
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.
-
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.
-
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:
-
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.
-
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().
-
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.
-
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.
-
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.
-
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.
-
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.
-
void ls_show_vertex(struct ls_vertex *vertex, struct vty *vty, struct json_object *json, bool verbose)
-
void ls_show_subnet(struct ls_subnet *subnet, struct vty *vty, struct json_object *json, bool verbose)
-
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.
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.
-
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
-
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.
-
int ls_request_sync(struct zclient *zclient)
Request initial Synchronisation to collect the whole Link State Database.
-
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.
-
void ls_delete_msg(struct ls_message *msg)
Delete existing message. Data structure is freed.
-
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.
-
struct ls_message *ls_vertex2msg(struct ls_message *msg, struct ls_vertex *vertex)
-
struct ls_message *ls_edge2msg(struct ls_message *msg, struct ls_edge *edge)
-
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.
-
int ls_msg2vertex(struct ls_ted *ted, struct ls_message *msg)
-
int ls_msg2edge(struct ls_ted *ted, struct ls_message *msg)
-
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.
-
struct ls_element *ls_msg2ted(struct ls_ted *ted, struct ls_message *msg, bool delete)
-
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.
-
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.