This does not use radix, but its simple to implement.
Your search keys will not be absolute. Partial matches are possible, which means that you found a network matching rule, not a host matching rule.
I suggest you use a list of containers (sub-tables). The first list will be sorted by subnet mask from the most restrictive (host route rules with mask 255.255.255.255) to the least restrictive (default gateway with mask 0.0.0.0).
Under each entry in the list there will be an easily visible structure (tree, hash table or just a list) that is entered into the masked part of the address you are trying to find.
For each address that you are trying to find, you must alternately look for it in each net-mask subcategory and select the first match that you encounter as the route you are using. It will have the most restrictive network mask, since they are ordered with the least restriction, and if a match is not found by the time you get to the end of the net-mask list, you will see the default gateway network mask entry in the list, if you have it there is. This entry will be slightly different from the others, because if there is more than one entry in its subcategory, they all have the same network address. If you want to have only one default gateway, you can opt out of writing 0.0.0.0 and just treat this as a special case.
You can also have a metric (cost, speed, etc.) as a sub-key for each record (or each of them corresponds to a list of records with the same network address / destination, ordered by their metric). This will allow you to have more than one route 192.168.1.0 (one over WiFi and one over wired Etherent), without complicating the work.
When the entry in the netmask becomes empty, you probably want to delete 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 {
Route information is complicated. You can simply list the IP address here and find out when you have an IP address that was on the local network and stop looking for things. This will require that you find out when you look for an address that was on the local network. This makes it difficult to configure routing rules to send packets that were addressed to addresses that looked local to the router, which is often useful.
Instead, you can do what Linux does and allow the use of interface routes in addition to address routes.
You will probably take advantage of this by indicating a flag that tells what type of route it has, and having a union type containing data for this type of route. This is done by interfaces such as PPP, where it really doesn’t matter that you know that the IP address of the machine on the other side of the modem works very cleanly. It also allows you not to have a random case for the local network. You just look at them, like any other address in the table, and say that "use Ethernet interface 0".
In this case, when you had the package for the route, you must pass the destination IP address to the route search function, which will return the best match. If the best match was to record the IP address, you would turn around and look at that IP address in the routing table, and it would return that address in the best way. You continue this until you get an interface match (so interface routes are required).
You will probably want to keep the IP address, the search for which led to the input of the interface. In the case of an Ethernet route, you will need to provide this address to search for ARP. This last mapped IP address may be the same as the destination address, or it may be a router that is on the same network as one of your network interfaces.
Each time you find an interface match, you can verify that the interface is still present before returning from the route_lookup procedure. In case the interface is no longer present, you can remove it and then continue to search for the best match. You would not have to restart the search in the net-mask list, but you would need to make sure that you did not miss an entry in the current list of networks that had a more expensive metric than the one you just noticed was deleted. Say you have WiFi and wired Ethernet on your local LAN, but you just turned off Ethernet, which costs less than Wi-Fi (Ethernet is faster and consumes less power, so you gave it a better rate). want for this packet that you are trying to route to send it to wifi.
I do not know how this will be compared with the implementation of the base tree. I suspect that it would be compatible with it on a 32-bit machine for IPv4 (depending on how you chose route_table_network_container ), but perhaps in a less favorable way in IPv6, where the address sizes are larger and the subnet masks are not used ( are they? I "I'm not too familiar with IPv6, unfortunately)
In this, I completely ignored the threads. I assume that only one thread will access the routing table at any given time. If this is not the case, then adding and removing nodes will require the inclusion of some types of locks, which will depend on any platform that you plan to implement at the same time.