Route realms and policy propagation, rtacct

On routers using OSPF ASE or, especially, the BGP protocol, routing tables may be huge. If we want to classify or to account for the packets per route, we will have to keep lots of information. Even worse, if we want to distinguish the packets not only by their destination, but also by their source, the task gets quadratic complexity and its solution is physically impossible.

One approach to propagating the policy from routing protocols to the forwarding engine has been proposed in [8]. Essentially, Cisco Policy Propagation via BGP is based on the fact that dedicated routers all have the RIB (Routing Information Base) close to the forwarding engine, so policy routing rules can check all the route attributes, including ASPATH information and community strings.

The Linux architecture, splitting the RIB (maintained by a user level daemon) and the kernel based FIB (Forwarding Information Base), does not allow such a simple approach.

It is to our fortune because there is another solution which allows even more flexible policy and richer semantics.

Namely, routes can be clustered together in user space, based on their attributes. F.e. a BGP router knows route ASPATH, its community; an OSPF router knows the route tag or its area. The administrator, when adding routes manually, also knows their nature. Providing that the number of such aggregates (we call them realms) is low, the task of full classification both by source and destination becomes quite manageable.

So each route may be assigned to a realm. It is assumed that this identification is made by a routing daemon, but static routes can also be handled manually with ip route (see sec.7, p.). 1cm NB. There is a patch to gated, allowing classification of routes to realms with all the set of policy rules implemented in gated: by prefix, by ASPATH, by origin, by tag etc.

To facilitate the construction (f.e. in case the routing daemon is not aware of realms), missing realms may be completed with routing policy rules, see sec. 8, p..

For each packet the kernel calculates a tuple of realms: source realm and destination realm, using the following algorithm:

1. If the route has a realm, the destination realm of the packet is set to it.
2. If the rule has a source realm, the source realm of the packet is set to it. If the destination realm was not inherited from the route and the rule has a destination realm, it is also set.
3. If at least one of the realms is still unknown, the kernel finds the reversed route to the source of the packet.
4. If the source realm is still unknown, get it from the reversed route.
5. If one of the realms is still unknown, swap the realms of reversed routes and apply step 2 again.

After this procedure is completed we know what realm the packet arrived from and the realm where it is going to propagate to. If some of the realms are unknown, they are initialized to zero (or realm unknown).

The main application of realms is the TC route classifier [7], where they are used to help assign packets to traffic classes, to account, police and schedule them according to this classification.

A much simpler but still very useful application is incoming packet accounting by realms. The kernel gathers a packet statistics summary which can be viewed with the rtacct utility.

kuznet@amber:~ $ rtacct russia
Realm      BytesTo    PktsTo     BytesFrom  PktsFrom   
russia     20576778   169176     47080168   153805     
kuznet@amber:~ $

This shows that this router received 153805 packets from the realm russia and forwarded 169176 packets to russia. The realm russia consists of routes with ASPATHs not leaving Russia.

Note that locally originating packets are not accounted here, rtacct shows incoming packets only. Using the route classifier (see [7]) you can get even more detailed accounting information about outgoing packets, optionally summarizing traffic not only by source or destination, but by any pair of source and destination realms.