I want to implement a small routing table for my learning. I know it is implemented using radix/patricia tree in routers

Question

I want to implement a small routing table for my learning? I know it is implemented using radix/patricia tree in routers?

Can someone give me an idea on how to go about implementing the same?

The major issue i feel is storing IP ADDRESS. For example : 10.1.1.0 network next hop 20.1.1.1 10.1.0.0 network next hop 40.1.1.1

Can someone give me a declaration of the struct from which can I have an idea?

Answer 1

This doesn't use a radix, but it is simple to implement.

Your look-up keys aren't going to be absolute. Partial matches are possible, which would signify that you have located a network matching rule rather than a host matching rule.

I suggest you use a list of containers (sub-tables). The first list will be ordered by subnet mask from the most restrictive (host route rules with mask 255.255.255.255 ) to least restrictive (default gateway with mask 0.0.0.0 ).

Under each entry in the list will be an easily searchable structure (tree, hash table, or just a list) which is keyed on the masked portion of the address you are attempting to look up.

For each address you attempt to look up you should search for it in each net-mask's sub-table in turn and choose the first match you come across as your route to use. It will have the most restrictive net-mask possible as they are ordered from most restrictive to least, and if no match is found by the time you reach the end of the net-mask list you will find the default gateway net-mask entry in the list if you have one. This entry will be a little bit different from the others because if you have more than one entry in its sub-table they would all have the same network address. If you only want to have one default gateway then you can opt to not have the 0.0.0.0 entry and just treat that as a special case.

You may also want to have a metric (cost, speed, ...) as a sub-key for each entry (or have each network match be a list of entries with the same network/destination address ordered by their metric). This would allow you to have more than one 192.168.1.0 route (one by WiFi and one by wired Etherent) without making things difficult.

When a net-mask entry becomes empty you will probably want to remove it.

struct route4_table_subnet {
    uint32_t mask;
    struct route_table_network_container sub_table;
    struct route_table_subnet * next;
};

struct route4_table_network_container_entry {
    // The route_table_network_container contains nodes of this type, but
    // however you want to implement this container is up to you
    uint32_t network; // this is the key
    uint32_t metric;

    // route info

    struct route4_table_network_container_entry * next;
};

The route info is tricky. You could simply list an IP address here and recognize when you got an IP address that was on a local network and stop looking up stuff. This would require that you recognized when you were about to look up an address that was in a local network. This would make it difficult to set up routing rules to send packets that were to an address that looked local to a router instead, which is often useful.

You could instead do what Linux does and allow for the use of interface routes in addition to address routes.

You would probably implement this by having a flag that told what type of route it was and having a union type that contained the data for that type of route. This makes interfaces like PPP where it really doesn't matter that you know the IP address of the machine on the other side of the modem is work very cleanly. It also allows you to not have an oddball case for the locally attached network. You just look them up like any other address in the table and they say "use Ethernet interface 0".

In this case when you had a packet to route you would pass the destination IP address to your route lookup function which would return the best match. If the best match was an IP address entry then you would turn around and look that IP address up in the routing table and it would return that address's best match. You would continue this until you got to an interface match (so interface match routes would be required).

You would probably want to hold on to the IP address whose lookup resulted in the interface route entry. In the case of an Ethernet route you would need to supply this address to the ARP lookup. This last matched IP could be the same as the destination address or it could be a router that is on the same network as one of your network interfaces.

Each time you found an interface match you could test that the interface is still present before returning from the route_lookup routine. In the case that an interface is no longer present you could remove it then and then continue looking for a best match. You would not have to restart the search in the net-mask list but would need to ensure that you did not miss an entry in the current network list that had a more costly metric than the interface that you just noticed had been removed. Say you have WiFi and wired Ethernet to your local home network, but you just unplugged your Ethernet which costs less than the WiFi to use (Ethernet is faster and uses less power, so you gave it a more favorable metric) -- you would now want for this packet you are trying to route to get sent to the WiFi.

I don't know how this would compare to a radix tree implementation. I suspect that it would be compeditive to it on a 32 bit machine for IPv4 (depending on how you chose your route_table_network_container) but possibly less favorably in IPv6 where address sizes are larger and subnet masks aren't used (are they? I'm not overly familiar with IPv6, sadly)

I completely ignored threading in this. I am assuming that only one thread would access the routing table at any one time. If this is not the case then adding and removing of nodes would require you to include some type of locks, which would depend on whatever platform you are planning on implementing this on.