Linux strategic routing application

Strategic routing

Strategicity means that the routing of IP packets is mainly based on some policies set by the network administrator as needed. For example, we can have a strategy like this: "All packages from direct network A, select X path; other packages select Y path", or "All packages with TOS select path F; other selector path K".

Cisco's Network Operating System (Cisco IOS) has adopted a new strategic routing mechanism since 11.0. Linux began to adopt a strategic routing mechanism in kernel 2.1. Compared with traditional routing algorithms, the strategic routing mechanism mainly introduces the concept of multi-routing tables and rules.

Multiple Routing Tables

Traditional routing algorithms use only one routing table. But in some cases, we need to use multi-routing tables. For example, a subnet is connected to the outside world through a router, and the router is connected to the outside world with two lines, one of which is faster and the other is slower. For most users in the subnet, there are no special requirements for speed, so they can use slower routes; however, some special users in the subnet have strict requirements on speed, so they need to use faster routes. The above requirements cannot be achieved if you use a routing table, but if you use different routing tables for different users based on the source address or other parameters, the performance of the router can be greatly improved.

Rule

Rules are a new concept of strategic criticality. We can describe rules in natural language like this, for example, our system can specify such rules:

Rule 1: "All IP packets from 192.16.152.24, use routing table 10, the priority level of this rule is 1500."

Rule 2: "For all packages, use routing table 253, the priority level of this rule is 32767"

We can see that the rule contains 3 elements:

What kind of package will be used (the so-called SELECTOR may be more reflective of its role);

What actions will a package that complies with this rule take to it (ACTION), such as using which table;

Priority levels of this rule. The higher the priority, the more the rules match first (the smaller the value, the higher the priority).

Configuration method for strategic routing

The traditional tool for configuring routing in Linux is route, while the tool for implementing strategic routing configuration is iproute2 toolkit. This package was developed by Alexey Kuznetsov.
Here we briefly introduce the configuration method of strategic routing so that we can better understand the content of the second part. For detailed usage methods, please refer to the ip-cfref document written by Alexey Kuznetsov. The configuration of strategic routing mainly includes the configuration of interface address, routing configuration, and rule configuration.

Configuration of interface address IP Addr

For interface configuration, you can use the following command:

Usage: ip addr [ add | del ] IFADDR dev STRING

For example:

router># ip addr add 192.168.0.1/24 broadcast 192.168.0.255 label eth0 dev eth0

The above indicates that the address 192.168.0.1 is assigned to interface eth0. The mask is 255.255.255.0 (24 represents the number of 1 in the mask), and the broadcast address is 192.168.0.255.

Route configuration IP Route

Linux can support up to 255 routing tables, of which 3 are built-in:

Table 255 Local table Local interface address, broadcast address, and NAT address are all placed in this table. The routing table is automatically maintained by the system and cannot be modified directly by the administrator.

Table 254 Main table If the table to which the route belongs is not specified, all routes are placed in this table by default. Generally speaking, routes added by old routing tools (such as route) will be added to this table. Generally it is a normal route.

Table 253 Default routing table Generally speaking, the default routes are placed in this table, but if specified, all gateway routes can be placed.

Table 0 Reserved

The format of the routing configuration command is as follows:
Usage: ip route list SELECTOR
ip route { change | del | add | append | replace | monitor } ROUTE

If you want to view the contents of the routing table, you can use the command:

ip route list table table_number

The operations for routing include change, del, add, append, replace, and monitor. For example, adding a route can be used:

router># ip route add 0/0 via 192.168.0.4 table main
router># ip route add 192.168.3.0/24 via 192.168.0.3 table 1

The first command is to add a route to the main routing table (main table), i.e. table 254, and the content of the route is to set 192.168.0.4 to become the gateway.

The second command represents adding a route to routing table 1, and the gateway for subnet 192.168.3.0 (subnet mask is 255.255.255.0) is 192.168.0.3.

In the multi-routing table routing system, all route operations, such as adding routes to the network routing table, or looking for specific routes in the routing table, need to specify the routing table to operate. All route tables are not specified, and the default operation is to operate on the main route table (Table 254). In a single table system, the routing operation does not need to specify the routing table.

Rules configuration IP Rule

In Linux, there can be a total of rules that define priority levels. There can only be one rule for a priority level, that is, there can be a total of rules in theory. Three of the rules are default. The command usage is as follows:

First we can take a look at all the default rules of the routing table:

0: from all lookup local
32766: from all lookup main
32767: from all lookup default

Rule 0, it is the rule with the highest priority. The rule stipulates that all packages must be routed first using the local table (254). These rules cannot be changed or deleted.

Rule 32766 stipulates that all packets are routed using table main. These rules may be changed and deleted.

Rule 32767 stipulates all packets and uses table default for routing. These rules may be changed and deleted.

When routing by default, first, the route will be found in the local routing table according to rule 0. If the destination address is the network or broadcast address, the appropriate route can be found here; if the route fails, the next non-empty rule will be matched, there is only 32766 rule, and the route will be found in the main routing table; if it fails, the 32767 rule will be matched, that is, the default routing table will be found. If it fails, the routing will fail. It can be seen here that strategic routing is forward compatible.

You can also add rules:

router># ip rule add [from 0/0] table 1 pref 32800
router >#ip rule add from 192.168.3.112/32 [tos 0x10] table ２ pref 1500 prohibit

The first command will add a rule to the rule chain. The object matching the rule is all packets. The action is to select the route in routing table 1. The priority of this rule is 32800.

The second command will add a rule to the rule chain. The object matching the rule is a packet with IP of 192.168.3.112, tos equals 0x10. Use routing table 2. The priority of this rule is 1500, and the action is. After adding, we can see the changes in system rules.

router># ip rule
0: from all lookup local
1500 from 192.168.3.112/32 [tos 0x10] lookup 2
32766: from all lookup main
32767: from all lookup default
32800: from all lookup 1

The above rules are based on the source address as the keyword as the basis for whether to match. In addition to the source address, the following information can also be used:

From -- Source address

To -- Destination address (this is used when selecting rules, and is also used when searching for routing tables)

Tos -- TOS (type of service) domain of IP Baotou

Dev -- Physical Interface

Fwmark -- Firewall parameters

In addition to specifying the table, the actions taken can also specify the following actions:

Table Specifies the table used

Nat Transparent Gateway

Action prohibit discards the packet and sends ICMP information

Reject simply discard the package

Unreachable discards the packet and sends ICMP information of NET UNREACHABLE

Application of strategic routing

Source-Sensitive Routing

If one network connects to the Internet through two lines, one is the faster ADSL and the other is the slower ordinary modem. In this way, network administrators can provide indiscriminate routing services, or make some specific addresses use faster lines according to different source addresses, while ordinary users use slower lines, that is, route selection based on source addresses.

Select the route according to the service level (Quality of Service)

Network administrators can route datagrams with different requirements for transmission rate, throughput and reliability according to the service level domain of the IP header, and for different service requirements.

Cost-saving applications

Network administrators can use some larger paroxysmal communications with higher bandwidth but more expensive paths for a short period of time according to the communication situation, and then allow basic communications to continue to use the cheaper basic lines. For example, administrators know that a certain host communicates with a specific address usually accompanied by a large number of paroxysmal communications, so the network administrator can arrange some policies to make these hosts use special routes, which are dialed on demand and have relatively high bandwidth lines, and will be stopped after the communication is completed, while ordinary communication will not be affected. This not only improves network performance but also saves costs.

Load Sharing

According to the characteristics of network traffic, network administrators can allocate load between different paths to achieve load balancing.

Implementation of strategic routing under Linux--RPDB (Routing Policy DataBase)

Under Linux, policy routing is implemented by RPDB. Understanding the internal mechanism of RPDB can deepen the understanding of the use of strategic routing. Here are the details of the RPDB implementation of Linux 2.4.18. The main implementation files include:

fib_hash.c
fib_rules.c
fib_sematic
fib_frontend.c

RDPB is mainly composed of multiple routing tables and rules. The routing table, its operations and its external interfaces are the core parts of the entire RPDB. The routing table is mainly composed of main data structures such as table, zone, and node. Operations on routing tables mainly include physical operations and semantic operations. In addition to providing the IP layer with the interface to find the route, the routing table must also provide interfaces with several elements: the interface to the user (i.e., changing the route), the interface to the proc, the IP layer control interface, and the interface to the hardware (changes of network interfaces will cause changes in the content of the routing table). Rules at the center of RDPB, the table is selected by the rules. The IP layer does not directly use the routing table, but passes through a routing adaptation layer, which provides high-performance routing services for the IP layer.

Routing table (Fib Table)

Data structure:

In the entire strategic routing framework, routing tables are the most important data structures. We have clearly explained the concept and structure of routing tables above and above. Linux is implemented through the following main data structures.

Main data structures Function location
struct fib_table routing table ip_fib.h 116
struct fn_hash hash data of the routing table fib_hash.c 104
struct fn_zone zone domain fib_hash.c 85
struct fib_node routing node fib_hash.c 68
struct fib_info routing information ip_fib.h 57
struct fib_result routing result ip_fib.h 86

The main relationships between data structures are as follows. The routing table consists of the routing table number, the operation function pointer of the routing table and the table data. It should be noted here that the router table structure does not directly define the zone domain, but points to fn_hash through a data pointer. Only when there is data in the zone will it be connected to fn_zone_list.

All routing tables of the system are maintained by the array variable *fib_tables[RT_TABLE_MAX+1], where the system defines RT_TABLE_MAX to 254, which means that the largest routing table in the system is 255, and all routing table operations are performed on this array. . At the same time, the system also defines the three-length routing table *local_table; *main_table.

Operation of routing table:

The main part of Linux policy routing code is the operation of routing tables. For routing table operations, physical operations are intuitive and easy to understand. Operations on tables are nothing more than adding, deleting, updating, etc. There is another operation, which is the so-called semantic operation. Semantic operation mainly refers to such as calculating the address of the next item, converting the node into a routing item, and finding the route of specified information.

1. Physical operation:

The physical operations of the routing table mainly include the following functions:

Routing flag operation Implement function location
Create a new routing table
Delete the routing table
Search route fn_hash_lookup fib_hash.c 269
Insert routing to routing table fn_hash_insert fib_hash.c 341
Delete the route of the routing table fn_hash_delete
fn_hash_dump
fib_hash.c 433
fib_hash.c 614
Update routes to route table fn_hash_flush fib_hash.c 729
Display routing information of the routing table fn_hash_get_info fib_hash.c 750
Select the default route fn_hash_select_default fib_hash.c 842

2. Semantic operation:

Semantic operations do not involve the understanding of the overall framework of routing tables, and the function name is self-explanatory, so please refer to fib_semantics.c.

3. Interface (front end)

The key to understanding the routing table interface is to understand where there is

The first is the interface that routes the IP layer. In the current Linux sense, the most important thing is routing at the IP layer, so the interface with the IP layer is the most important interface. The connection with the IP layer is mainly to provide the IP layer with interfaces to find routing, route control, and search for specified IP.

Fil_lookup
ip_rt_ioctl fib_frontend.c 286;" f
ip_dev_find 145

　Inet

The routing table must also provide a configuration interface, i.e. the interface that the user operates the route directly, such as adding and deleting a route. Of course, in strategic routing, there are also rules addition and deletion.

inet_rtm_delroute 351
inet_rtm_newroute 366
inet_check_attr 335

　proc

Display routing information in /proc/net/route.
　fib_get_procinfo

4. Network equipment (net dev event)

Routing is associated with hardware. When a network device is started or shut down, the route table management program must be notified to update the route table information.

fib_disable_ip 567
fib_inetaddr_event 575
fib_netdev_event

5. Internal maintenance (magic)

As we mentioned above, the maintenance of local routing tables is automatically performed by the system. That is to say, when the user sets an IP address, etc. for the hardware, the system automatically adds the local interface address and broadcast address to the local routing table.

fib_magic 417
fib_add_ifaddr 459
fib_del_ifaddr 498

Rule

1. Data structure

The rule is defined as struct fib_rule in line 52 of fib_rules.c. All routes in RPDB are stored in the variable fib_rules on line 101. Note that this variable is very important. It controls all rules, and the addition and deletion of rules are performed on this variable.

2. System definition rules:

fib_rules is defined and is assigned three default rules: default rules, local rules and main rules.

u Local rule local_rule
94 static struct fib_rule local_rule = {
r_next: &main_rule, /*The next rule is the main rule*/
r_clntref: ATOMIC_INIT(2),
r_table: RT_TABLE_LOCAL, /*Point to local routing table*/
r_action: RTN_UNICAST, /* action is to return route*/
};

u main_rule
86 static struct fib_rule main_rule = {
r_next: &default_rule,/*The next rule is the default rule*/
r_clntref: ATOMIC_INIT(2),
r_preference: 0x7FFE, /*Priority of default rule 32766*/
r_table: RT_TABLE_MAIN, /*Point to the main routing table*/
r_action: RTN_UNICAST, /* action is to return route*/
};
u default rule
79 static struct fib_rule default_rule = {
r_clntref: ATOMIC_INIT(2),
r_preference: 0x7FFF,/*Priority of default rule 32767*/
r_table: RT_TABLE_DEFAULT,/* refers to the default routing table*/
r_action: RTN_UNICAST,/* action is to return route*/
};

The header of the rule chain points to the local rule.

RPDB's central function fib_lookup

Now it's time to discuss the central function fib_lookup of the implementation of RPDB. RPDB provides the interface function fib_lookup as the entry point for finding routes. It is necessary to discuss this function in detail here. The following is the source code:

310 int fib_lookup(const struct rt_key *key, struct fib_result *res)
311 {
312 int err;
313 struct fib_rule *r, *policy;
314 struct fib_table *tb;
315
316 u32 daddr = key->dst;
317 u32 saddr = key->src;
318
321 read_lock(&fib_rules_lock);
322 for (r = fib_rules; r; r=r->r_next) {/*Scan every rule in the rule chain fib_rules until it matches*/
323 if (((saddr^r->r_src) & r->r_srcmask) ||
324 ((daddr^r->r_dst) & r->r_dstmask) ||
325 #ifdef CONFIG_IP_ROUTE_TOS
326 (r->r_tos && r->r_tos != key->tos) ||
327 #endif
328 #ifdef CONFIG_IP_ROUTE_FWMARK
329 (r->r_fwmark && r->r_fwmark != key->fwmark) ||
330 #endif
331 (r->r_ifindex && r->r_ifindex != key->iif))
332 continue;/*The above is to determine whether the rules match. If they do not match, scan the next rule, otherwise continue*/

335 switch (r->r_action) {/*Okay, start processing the action*/
336 case RTN_UNICAST:/*No action is set*/
337 case RTN_NAT: /*action nat ADDRESS*/
338 policy = r;
339 break;
340 case RTN_UNREACHABLE: /*action unreachable*/
341 read_unlock(&fib_rules_lock);
342 return -ENETUNREACH;
343 default:
344 case RTN_BLACKHOLE:/* Action reject */
345 read_unlock(&fib_rules_lock);
346 return -EINVAL;
347 case RTN_PROHIBIT:/* Action prohibit */
348 read_unlock(&fib_rules_lock);
349 return -EACCES;
350 }
351 /*Select routing table*/
352 if ((tb = fib_get_table(r->r_table)) == NULL)
353 continue;
/*Search for specified routes in the routing table*/
354 err = tb->tb_lookup(tb, key, res);
355 if (err == 0) {/*Hit the target*/
356 res->r = policy;
357 if (policy)
358 atomic_inc(&policy->r_clntref);
359 read_unlock(&fib_rules_lock);
360 return 0;
361 }
362 if (err < 0 && err != -EAGAIN) {/*Routing failed*/
363 read_unlock(&fib_rules_lock);
364 return err;
365 }
366 }
368 read_unlock(&fib_rules_lock);
369 return -ENETUNREACH;
370 }

The idea of the above code is very clear. First, the program scans all rules from high priority to low, and if the rules match, handles the actions of the rules. If it is a normal route addressing or a nat address conversion, first get the routing table from the rules and then operate on the routing table. In this way, RPDB finally appeared clearly.

IP layer routing adaptation (IP route)

A system composed of routing tables and rules can complete route management and search, but in order to make the IP layer routing work more efficient, the Linux routing system completes the adaptation work of most IP layers and RPDB, as well as the routing cache function.

Calling the interface

The routing interfaces of the IP layer are divided into sending routing interfaces and receiving routing interfaces:

Send routing interface

When the IP layer needs to route data, it will call the ip_route_out function. After this function completes some simple conversion of key values, it will call the ip_route_output_key function. This function first looks for a route in the cache. If it fails, it will call ip_route_output_slow. In ip_route_output_slow, fib_lookup is called in the routing table to find the route. If it hits, first add the route in the cache and then return the result.

ip_route_out
ip_route_output_key 1984;
ip_route_output_slow 1690;"

Receive routing interface

After the IP layer receives a packet, if it needs to be routed, it calls the function ip_route_input. ip_route_input is now searched in the cache. If it fails, ip_route_inpu calls ip_route_input_slow, ip_route_input_slow calls fib_lookup in ip_route_input_slow to find the route in the routing table. If it hits, first add this route in the cache and then return the result.

ip_route_input_slow 1312;" f
ip_route_input 1622;" f

cache

The routing cache saves the most recently used routes. After the IP is routed in the routing table, if it hits, the route will be added to the routing cache. At the same time, the system will regularly check whether the items in the routing cache are invalid, and if they are invalid, they will be cleared.