Quagga routing table
By the nature of my work, I am engaged in designing networks and setting up network equipment. At some point in time, I wanted to find out how network devices are arranged, which black boxes have always represented for me, magically implementing network protocols. Since devices from vendors like Cisco or Juniper are closed and not available for any study, I chose Quagga, an open source router that is widely used in real life and quite successfully copes with OSPF and BGP protocols. Armed with the Quagga source code, I began research. In this article I want to tell how the routing table in Quagga is arranged, what structures and algorithms are used to implement it.
First, a few words about the overall architecture of Quagga. Quagga consists of several separate programs, or demons, each of which performs a specific function. For example, the ospfd daemon implements the OSPF protocol, and bgpd implements the BGP protocol. The central role in Quagga is played by the zebra daemon. One of its main roles is to get routing information from demons that implement specific protocols and select the best routes obtained from various sources. After that, the best routes are transferred to the Linux kernel, which actually transmits user traffic (we assume that Quagga is installed on Linux). This is how the classic “intelligence” of the router (Control Plane) and the transfer of user traffic (Data Plane) is realized. In our case, Quagga is the Control Plane, and the Linux kernel is the Data Plane. The Quagga routing table is located inside the zebra daemon.
Each individual route in the routing table can be represented as a prefix (usually denoted as the ip-address and prefix length, for example, 192.168.0.0/24) with which various route information is associated: next-hop, administrative distance, metric, protocol that reported the route etc. The routing table is simply a set of such prefixes with additional information associated with them. The zebra daemon stores all routes that were passed to it or configured in the zebra itself. For example, if a static route 192.168.0.0/24 was configured with next-hop 1.1.1.1, and a route was received with the same prefix from the ospfd daemon and with next-hop 2.2.2.2, then zebra will store both of these routes and show them in the show ip route command output. Storing all routes allows you to quickly select a new best route, if for any reason the current best route has ceased to exist. For example, in our example, after removing the static route, zebra will immediately select OSPF as the best route without any reference to the ospfd daemon. Routes for a specific prefix are stored as a linked list, as shown in the figure (in this case, for the prefix 192.168.0.0/24). Green is the best route.
')
When receiving the next route, its route information is added to the beginning of the linked list, after which the procedure of sequential viewing of all routes for a given prefix and selection of the best one is started. The best route (assuming next-hop is valid) is the route with the smallest administrative distance. Since, by default, routes from different protocols have different administrative distances (for example, OSPF has 110, and static routes have 1), it is administrative distance that is the decisive criterion for choosing the best route. If the settings are such that different routes have the same administrative distance, then the route with the lowest metric is best. If the routes have the same administrative distance and metric, then the route closer to the end of the list, i.e. the one that was added before.
When deleting a route, this route is removed from the list of routes for a given prefix, and the procedure for choosing the best route is also launched. For example, after removing a static route, the picture will look like this:
After choosing the best route, information about it is transmitted to the Linux kernel.
As a rule, there are not many routes for one prefix and it doesn’t take much to look at them all to choose the best one. A much more difficult task is to find the prefix itself when adding or removing a route. There can be a lot of different prefixes in the routing table - thousands and tens of thousands, and a simple sequential enumeration of all the prefixes to find the right one will be extremely inefficient. For faster and more efficient searching, all prefixes in the routing table are stored in a structure called compact trie or compressed binary prefix tree.
In the future, prefixes will be more convenient to represent in binary form, indicating only the first bits, in an amount equal to the prefix length. The remaining bits of the prefix are 0 and are not important for the search. For example, the prefix 10.0.0.0/8 in binary form will look like 00001010, the prefix 128.0.0.0/1 will look like 1, 128.0.0.0/2 as 10, etc.
What is a trie or prefix tree and how it works can be read, for example, here . For our purposes, the easiest way to understand it is by example. For example, we have prefixes 1, 111, 010, 0110000. These prefixes will be organized as the following prefix tree:
White nodes correspond to the prefixes of interest. Yellow nodes are intermediate and serve to properly organize the structure of the tree. The top node is the root of the tree and corresponds to the prefix 0.0.0.0/0. Search for the desired prefix as follows. The search begins with the root of the tree. Then the first bit of the desired prefix is ​​checked. If the first bit is 0, then go down to the left child element. If the first bit is 1, then to the right child element. Then we repeat this procedure for the second bit of the desired prefix, then for the third, and so on. until we reach the desired prefix or make sure that it is not there. In the absence of the desired prefix, it is added to the tree in the appropriate place. It can be seen that the number of accesses to the tree is equal to the length of the desired prefix and for the longest prefix IPv4 is 32. Strictly speaking, in each node of the tree it is not necessary to store the prefix itself, since it is uniquely determined by the location of the node, but I indicated it for clarity. In addition, in the real Quagga structure, the prefix is ​​indeed stored in each node of the tree.
A compressed prefix tree is different from the usual one in that it optimizes long chains without branches. For our example, a compressed prefix tree will look like this:
Now, when searching for a prefix in the current node, we check whether the first n bits of the desired prefix match the prefix bits in the node, where n is the prefix length in the node. If the bits match, then we look in the desired prefix n + 1'y bits and, depending on whether it is 0 or 1, we go down to the left or right child element.
For example, the search for the prefix 011000 will be performed as follows. We start as usual with the root of the tree. The root in our case contains a prefix of length 0, so we check the first bit of the desired prefix. Since it is equal to 0, we go down to the left child element and get to the node with the prefix 01. Here we check the desired prefix with the prefix in the current node, i.e. whether the first 2 bits of the prefix 011000 coincide with the prefix 01. Since the bits match, we move on and check the 3rd bit of the desired prefix. The third bit is 1, so we go down to the right child element and get into the prefix 011000 we need. To find the prefix, we needed three calls to the tree instead of seven in the case of an uncompressed tree. If at some stage it turned out that the first n bits of the prefix in the node do not coincide with the bits of the desired prefix, this means that the desired prefix does not exist and it is added to the tree.
In Quagga, the prefix is ​​stored as an ip address and prefix length. In this case, only the first n-bits, where the n-length of the prefix has the value, and the rest are 0 and do not participate in the search for the desired prefix. For example, the prefix 192.168.1.0/24 looks like:
For clarity, I will display it as follows:
Here, at the top, I indicate the usual type of the prefix in decimal form, and at the bottom - its binary representation, with the red number of bits equal to the prefix length. In such designations, the routing table consisting of the prefixes 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24 will look like this:
For example, when searching for the prefix 192.168.1.0/24, its 1st, 2nd, 23rd, and 24th bits are sequentially checked to find its location in the tree. Each of our prefixes also points out the corresponding route information. The prefixes highlighted in yellow are intermediate and there is no route information for them.
In conclusion, I would like to tell you how the routes are displayed when typing the show ip route command. To display routes, you need to sort through all the prefixes in the tree in any way. This procedure is called tree traversal and can be implemented in various ways. Quagga uses a pre-ordered bypass method and which is easiest to define recursively:
To bypass subtrees, the same rules are used. For the routing table we built above, the prefix bypass will look like this. First we take the top of the tree, i.e. prefix 0.0.0.0/0. Then we go around the left subtree. It consists of the only prefix 10.0.0.0/8. Then we go around the right subtree, which we will display in the picture:
To circumvent it, we apply the same rules: first we take its root, i.e. prefix 128.0.0.0/1, then we go around its left subtree, i.e. prefix 172.16.0.0/16, then the right subtree shown in the picture:
Next, take the top of this subtree, i.e. prefix 192.168.0.0/22, go around its left subtree, getting the prefixes 192.168.0.0/23, 192.168.0.0/24 and 192.168.1.0/24, and its right subtree, consisting of the prefix 192.168.2.0/24.
Thus, we will get the prefixes in the following order: 0.0.0.0/0, 10.0.0.0/8, 128.0.0.0/1, 172.16.0.0/16, 192.168.0.0/22, 192.168.0.0/23, 192.168.0.0/ 24, 192.168.1.0/24, 192.168.2.0/24. The prefixes 128.0.0.0/1, 192.168.0.0/22 ​​and 192.168.0.0/23 are proprietary and are not shown when displaying the routing table. The remaining prefixes will be displayed in the order: 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24.
In conclusion, I provide a list of Quagga source files where the structures and algorithms described above are implemented:
Quagga sources can be downloaded from here: download.savannah.gnu.org/releases/quagga . I took version 0.99.24.
Structures and functions for working with prefixes are in the file lib / prefix.c.
Structures and functions for working with the prefix tree are in the file lib / table.c
Structures and functions for working with route information are located in the zebra / zebra_rib.c file.
Quagga architecture
First, a few words about the overall architecture of Quagga. Quagga consists of several separate programs, or demons, each of which performs a specific function. For example, the ospfd daemon implements the OSPF protocol, and bgpd implements the BGP protocol. The central role in Quagga is played by the zebra daemon. One of its main roles is to get routing information from demons that implement specific protocols and select the best routes obtained from various sources. After that, the best routes are transferred to the Linux kernel, which actually transmits user traffic (we assume that Quagga is installed on Linux). This is how the classic “intelligence” of the router (Control Plane) and the transfer of user traffic (Data Plane) is realized. In our case, Quagga is the Control Plane, and the Linux kernel is the Data Plane. The Quagga routing table is located inside the zebra daemon.
Storing routing information
Each individual route in the routing table can be represented as a prefix (usually denoted as the ip-address and prefix length, for example, 192.168.0.0/24) with which various route information is associated: next-hop, administrative distance, metric, protocol that reported the route etc. The routing table is simply a set of such prefixes with additional information associated with them. The zebra daemon stores all routes that were passed to it or configured in the zebra itself. For example, if a static route 192.168.0.0/24 was configured with next-hop 1.1.1.1, and a route was received with the same prefix from the ospfd daemon and with next-hop 2.2.2.2, then zebra will store both of these routes and show them in the show ip route command output. Storing all routes allows you to quickly select a new best route, if for any reason the current best route has ceased to exist. For example, in our example, after removing the static route, zebra will immediately select OSPF as the best route without any reference to the ospfd daemon. Routes for a specific prefix are stored as a linked list, as shown in the figure (in this case, for the prefix 192.168.0.0/24). Green is the best route.
')
When receiving the next route, its route information is added to the beginning of the linked list, after which the procedure of sequential viewing of all routes for a given prefix and selection of the best one is started. The best route (assuming next-hop is valid) is the route with the smallest administrative distance. Since, by default, routes from different protocols have different administrative distances (for example, OSPF has 110, and static routes have 1), it is administrative distance that is the decisive criterion for choosing the best route. If the settings are such that different routes have the same administrative distance, then the route with the lowest metric is best. If the routes have the same administrative distance and metric, then the route closer to the end of the list, i.e. the one that was added before.
When deleting a route, this route is removed from the list of routes for a given prefix, and the procedure for choosing the best route is also launched. For example, after removing a static route, the picture will look like this:
After choosing the best route, information about it is transmitted to the Linux kernel.
Prefix storage
As a rule, there are not many routes for one prefix and it doesn’t take much to look at them all to choose the best one. A much more difficult task is to find the prefix itself when adding or removing a route. There can be a lot of different prefixes in the routing table - thousands and tens of thousands, and a simple sequential enumeration of all the prefixes to find the right one will be extremely inefficient. For faster and more efficient searching, all prefixes in the routing table are stored in a structure called compact trie or compressed binary prefix tree.
In the future, prefixes will be more convenient to represent in binary form, indicating only the first bits, in an amount equal to the prefix length. The remaining bits of the prefix are 0 and are not important for the search. For example, the prefix 10.0.0.0/8 in binary form will look like 00001010, the prefix 128.0.0.0/1 will look like 1, 128.0.0.0/2 as 10, etc.
What is a trie or prefix tree and how it works can be read, for example, here . For our purposes, the easiest way to understand it is by example. For example, we have prefixes 1, 111, 010, 0110000. These prefixes will be organized as the following prefix tree:
White nodes correspond to the prefixes of interest. Yellow nodes are intermediate and serve to properly organize the structure of the tree. The top node is the root of the tree and corresponds to the prefix 0.0.0.0/0. Search for the desired prefix as follows. The search begins with the root of the tree. Then the first bit of the desired prefix is ​​checked. If the first bit is 0, then go down to the left child element. If the first bit is 1, then to the right child element. Then we repeat this procedure for the second bit of the desired prefix, then for the third, and so on. until we reach the desired prefix or make sure that it is not there. In the absence of the desired prefix, it is added to the tree in the appropriate place. It can be seen that the number of accesses to the tree is equal to the length of the desired prefix and for the longest prefix IPv4 is 32. Strictly speaking, in each node of the tree it is not necessary to store the prefix itself, since it is uniquely determined by the location of the node, but I indicated it for clarity. In addition, in the real Quagga structure, the prefix is ​​indeed stored in each node of the tree.
A compressed prefix tree is different from the usual one in that it optimizes long chains without branches. For our example, a compressed prefix tree will look like this:
Now, when searching for a prefix in the current node, we check whether the first n bits of the desired prefix match the prefix bits in the node, where n is the prefix length in the node. If the bits match, then we look in the desired prefix n + 1'y bits and, depending on whether it is 0 or 1, we go down to the left or right child element.
For example, the search for the prefix 011000 will be performed as follows. We start as usual with the root of the tree. The root in our case contains a prefix of length 0, so we check the first bit of the desired prefix. Since it is equal to 0, we go down to the left child element and get to the node with the prefix 01. Here we check the desired prefix with the prefix in the current node, i.e. whether the first 2 bits of the prefix 011000 coincide with the prefix 01. Since the bits match, we move on and check the 3rd bit of the desired prefix. The third bit is 1, so we go down to the right child element and get into the prefix 011000 we need. To find the prefix, we needed three calls to the tree instead of seven in the case of an uncompressed tree. If at some stage it turned out that the first n bits of the prefix in the node do not coincide with the bits of the desired prefix, this means that the desired prefix does not exist and it is added to the tree.
In Quagga, the prefix is ​​stored as an ip address and prefix length. In this case, only the first n-bits, where the n-length of the prefix has the value, and the rest are 0 and do not participate in the search for the desired prefix. For example, the prefix 192.168.1.0/24 looks like:
For clarity, I will display it as follows:
Here, at the top, I indicate the usual type of the prefix in decimal form, and at the bottom - its binary representation, with the red number of bits equal to the prefix length. In such designations, the routing table consisting of the prefixes 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24 will look like this:
For example, when searching for the prefix 192.168.1.0/24, its 1st, 2nd, 23rd, and 24th bits are sequentially checked to find its location in the tree. Each of our prefixes also points out the corresponding route information. The prefixes highlighted in yellow are intermediate and there is no route information for them.
Prefix Tree Traversal
In conclusion, I would like to tell you how the routes are displayed when typing the show ip route command. To display routes, you need to sort through all the prefixes in the tree in any way. This procedure is called tree traversal and can be implemented in various ways. Quagga uses a pre-ordered bypass method and which is easiest to define recursively:
- First we take the top of the tree.
- Then we go around the left subtree.
- Then we go around the right subtree.
To bypass subtrees, the same rules are used. For the routing table we built above, the prefix bypass will look like this. First we take the top of the tree, i.e. prefix 0.0.0.0/0. Then we go around the left subtree. It consists of the only prefix 10.0.0.0/8. Then we go around the right subtree, which we will display in the picture:
To circumvent it, we apply the same rules: first we take its root, i.e. prefix 128.0.0.0/1, then we go around its left subtree, i.e. prefix 172.16.0.0/16, then the right subtree shown in the picture:
Next, take the top of this subtree, i.e. prefix 192.168.0.0/22, go around its left subtree, getting the prefixes 192.168.0.0/23, 192.168.0.0/24 and 192.168.1.0/24, and its right subtree, consisting of the prefix 192.168.2.0/24.
Thus, we will get the prefixes in the following order: 0.0.0.0/0, 10.0.0.0/8, 128.0.0.0/1, 172.16.0.0/16, 192.168.0.0/22, 192.168.0.0/23, 192.168.0.0/ 24, 192.168.1.0/24, 192.168.2.0/24. The prefixes 128.0.0.0/1, 192.168.0.0/22 ​​and 192.168.0.0/23 are proprietary and are not shown when displaying the routing table. The remaining prefixes will be displayed in the order: 0.0.0.0/0, 10.0.0.0/8, 172.16.0.0/16, 192.168.0.0/24, 192.168.1.0/24, 192.168.2.0/24.
Conclusion
In conclusion, I provide a list of Quagga source files where the structures and algorithms described above are implemented:
Quagga sources can be downloaded from here: download.savannah.gnu.org/releases/quagga . I took version 0.99.24.
Structures and functions for working with prefixes are in the file lib / prefix.c.
Structures and functions for working with the prefix tree are in the file lib / table.c
Structures and functions for working with route information are located in the zebra / zebra_rib.c file.
Source: https://habr.com/ru/post/306084/
All Articles