Title: oroute_table / oroute_hash_table
"Ouput routing" is routing that is done for outgoing packets. As an example, suppose that there are two ethernet ports with corresponding ip devices of "/dev/ip0" (220.127.116.11/255.255.255.0) and "/dev/ip1" (18.104.22.168/255.255.255.0). If the following add_route command is issued:
add_route -g 22.214.171.124 -d 126.96.36.199 -m 2 -n 255.255.255.0 -I /dev/ip0
then outgoing ip packets (that did not, however, arrive on another interface) are sent out the ethernet port that corresponds to /dev/ip0 to the gateway with ip address of 188.8.131.52.
Output routes are stored in two different arrays, oroute_table and oroute_hash_table. oroute_table is the main table and oroute_hash_table is the cache, where routes can be quickly looked up. oroute_table has 32 elements and each element is of type oroute_t:
typedef struct oroute
int ort_port: The port number (e.g., ip0 is 0).
struct oroute *ort_nextnw;
struct oroute *ort_nextgw;
struct oroute *ort_nextdist;
ipaddr_t ort_dest: The network address of the routing entry (e.g., 184.108.40.206).
ipaddr_t ort_subnetmask: The subnet mask of the routing entry (e.g., 255.255.255.0).
int ort_dist: The distance to the route. Routes with low distances are chosen over routes with high distances.
i32_t ort_pref: The preference of the route. Routes with high preferences are chosen over routes with low preferences. The distance of a route is of higher importance. In other words, the relative preference of two routes is only significant if and only if these two routes are tied for the lowest distance.
ipaddr_t ort_gateway: The ip address of the gateway. Packets that are not destined to systems on the local network are sent to the gateway.
time_t ort_exp_tim: The expiration time for the entry. Note that when using add_route, this value will always 0. The entries, therefore, do not expire.
time_t ort_timestamp: The time at which the entry is added to oroute_table.
#define ORTF_EMPTY 0
#define ORTF_INUSE 1
#define ORTF_STATIC 2
Only OROUTE_STATIC_NR (#define'd as 16) static routes are allowed in the output routing table. Static and dynamic routes cannot replace static routes, even if 2 routes are to the same network.
struct oroute *ort_nextnw:
struct oroute *ort_nextgw:
struct oroute *ort_nextdist:
ort_nextnw, ort_nextgw, and ort_nextdist can best be described using a figure. The figure below represents the main output routing table, oroute_table:
The ort_nextnw field (red) is the linked list of routes to specific networks/subnet mask pairs. A, B, C, D, and E all are routes to different network/subnet mask pairs. For example, A could be the route to 220.127.116.11/255.255.255.0 and B could be the route to 18.104.22.168/255.255.255.0.
The ort_nextgw field (blue) links the linked lists of routes with the same network/subnet mask pairs but different gateways. D, F, and G are all routes to the same network/subnet mask pairs but all have different gateways. ort_nextdist connec
The ort_nextdist field (green) links the linked lists of routes with the same network/subnet mask pairs and the same gateway but with possibly different distances/preferences. F, H, I, and J are all routes to the same network/subnet mask pairs and the same gateway but have possibly different distances/preferences.
The oroute_hash_table is a 2-dimensional array of dimensions 32x4 whose entries are of type oroute_hash_t:
typedef struct oroute_hash
ipaddr_t irh_addr: The ip address (not the network address) of a system.
iroute_t *irh_route: The best route for the ip address above.
If an entry for a system does not exist in oroute_hash_table, the best route for the system is determined from the entries in oroute_table. The ip address of this system and the best route to the system (which together form an oroute_hash_t struct) is then placed in oroute_hash_table. The first dimension corresponds to the hash of the ip address, as determined by the #define hash_iroute. The second dimension will be 0. The entry with the same hash that was formerly in the 0th slot will be pushed to the 1st slot, the entry that was formerly in the 1st slot will be pushed to the 2nd slot, and then entry that was formerly in the 2nd slot will be pushed to the 3rd slot. The entry that was formerly in the 3rd slot will be pushed out of oroute_hash_table.
The best route for the ip address can later be quickly retrieved from oroute_hash_table (if it hasn't since been pushed out).