/* ospf_rte_table.ex.c: Support procedures for building an OSPF routing table. */ #include /* Header file for Dijkstra's algorithm */ #include "djk.h" /* IP specific header files */ #include "ip3_addr.h" #include "ip3_rte.h" /* OMS specific header files */ #include "oms_pr.h" /* OSPF specific header files */ #include "ospf_const.h" #include "ospf_defs.h" #include "ospf_rte_table.h" #include "ospf_lsa.h" #include "ospf_area.h" /***** Globals *****/ extern IpT_Address IpI_Broadcast_Addr; extern double OspfI_Converge_Time; /***** Procedures *****/ /***** Interface to Dijkstra Package *****/ void ospf_rte_table_calc (OspfT_Router *router_ptr) { OspfT_Rte_Table * rte_table_ptr; OspfT_Area * area_ptr; int area_index, num_areas; List * area_list_ptr; List * djk_node_list_ptr; DjkT_Node * root_node_ptr; char area_id_str [IPC_ADDR_STR_LEN]; char router_id_str [IPC_ADDR_STR_LEN]; char trace_msg [128]; /** Calculate a routing table for a particular router. Modifies router DS. **/ FIN (ospf_rte_table_calc (router_ptr)); /* Create a reference to the routing table. */ rte_table_ptr = router_ptr->rte_table_ptr; /* If no calculation is necessary, exit. */ if (!rte_table_ptr->dirty_flag) FOUT; /* Update the time calculated, and convergence time. */ rte_table_ptr->last_calc_time = op_sim_time (); OspfI_Converge_Time = op_sim_time (); /* Clear the entries of the routing table. */ ospf_rte_table_entries_clear (rte_table_ptr); /* Deactivate the area address ranges. */ ospf_rte_table_areas_deactivate (router_ptr); /* Loop through the areas the router is connected to and run Dijkstra for each. */ area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); for (area_index = 0; area_index < num_areas; area_index++) { area_ptr = op_prg_list_access (area_list_ptr, area_index); /* Issue trace statement. */ if (op_prg_odb_ltrace_active ("ospf_rte_table")) { ip_address_print (area_id_str, area_ptr->area_id); ip_address_print (router_id_str, router_ptr->router_id); sprintf (trace_msg, "Performing SPF calculation for router %s, area %s", router_id_str, area_id_str); op_prg_odb_print_minor (trace_msg, OPC_NIL); } /* Build a list of Dijkstra nodes to pass to the Djk package based on the LSAs in the area. */ djk_node_list_ptr = ospf_rte_table_djk_nodes_build (area_ptr); /* Get the root node. This corresponds to the router running Dijkstra. */ root_node_ptr = ospf_lsa_djk_node_lookup (djk_node_list_ptr, router_ptr->router_id, OspfC_Lsa_Router_Links); /* And run Dijkstra. */ djk_shortest_paths_calc (djk_node_list_ptr, root_node_ptr, 0); /* Then add the node entries to the routing table. */ ospf_rte_table_node_entries_add (root_node_ptr, rte_table_ptr, djk_node_list_ptr, area_ptr->area_id); } /* Tag the configured address ranges if we have routing table entries for them. */ ospf_rte_table_areas_activate (router_ptr); /* Examine the summary links LSAs, and add inter-area routes based on these LSAs. */ ospf_rte_table_inter_area_rtes_add (router_ptr, OPC_NIL, OPC_NIL); /* Reset the dirty flag after finishing. */ rte_table_ptr->dirty_flag = OPC_FALSE; /* Flush out summary advertisements whose destinations are no longer reachable. */ ospf_rte_table_summary_lsa_flush (router_ptr); /* For area border routers, generate a set of summary links LSAs. */ if (ospf_area_border_router_check (router_ptr)) ospf_rte_table_summary_lsa_generate (router_ptr); FOUT; } List * ospf_rte_table_djk_nodes_build (OspfT_Area *area_ptr) { List * djk_node_list_ptr; int lsa_index, num_lsa; OspfT_Lsa * lsa_ptr; DjkT_Node * djk_node_ptr; /** Build a set of Djk nodes based on the LSAs within the area LS database. **/ FIN (ospf_rte_table_djk_nodes_build (area_ptr)); /* Create initial list. */ djk_node_list_ptr = ospf_lsa_djk_node_list_create (area_ptr); /* Loop through router links and network links LSAs in */ /* area database, and create Dijkstra nodes for each. */ num_lsa = op_prg_list_size (area_ptr->router_lsa_list_ptr); for (lsa_index = 0; lsa_index < num_lsa; lsa_index++) { lsa_ptr = op_prg_list_access (area_ptr->router_lsa_list_ptr, lsa_index); /* Translate LSA into a Djk node(s). The nodes created by the LSA */ /* will be added to the node list. */ ospf_lsa_djk_nodes_add (lsa_ptr, djk_node_list_ptr); } num_lsa = op_prg_list_size (area_ptr->network_lsa_list_ptr); for (lsa_index = 0; lsa_index < num_lsa; lsa_index++) { lsa_ptr = op_prg_list_access (area_ptr->network_lsa_list_ptr, lsa_index); /* Translate LSA into a Djk node(s). The nodes created by the LSA */ /* will be added to the node list. */ ospf_lsa_djk_nodes_add (lsa_ptr, djk_node_list_ptr); } FRET (djk_node_list_ptr); } void ospf_rte_table_node_entries_add (DjkT_Node *root_node_ptr, OspfT_Rte_Table *rte_table_ptr, List *djk_node_list_ptr, OspfT_Area_Id area_id) { OspfT_Lsa * lsa_ptr; DjkT_Node * node_ptr; IpT_Address subnet_mask; int num_nodes, node_index; DjkT_Node * next_hop_ptr; IpT_Address dest_network_addr; IpT_Address next_hop_addr; /** Loop through the list of Djk nodes, and add a routing table entry for each node. **/ FIN (ospf_rte_table_node_entries_add (rte_table_ptr, djk_node_list_ptr, area_id)); num_nodes = op_prg_list_size (djk_node_list_ptr); lsa_ptr = OPC_NIL; subnet_mask = OPC_NIL; for (node_index = 0; node_index < num_nodes; node_index++) { node_ptr = op_prg_list_access (djk_node_list_ptr, node_index); lsa_ptr = (OspfT_Lsa *) node_ptr->node_state_ptr; /* Only construct destinations to networks and area border routers. */ if ((lsa_ptr->lsa_header_ptr->type != OspfC_Lsa_Network_Links) && (lsa_ptr->lsa_header_ptr->type != OspfC_Lsa_Router_Links)) continue; if ((lsa_ptr->lsa_header_ptr->type == OspfC_Lsa_Router_Links) && (!lsa_ptr->lsa_data.lsa_router_links_ptr->is_abr)) continue; /* Get the next hop. */ next_hop_addr = ospf_rte_table_node_next_hop_get (node_ptr->path_list_ptr); if (next_hop_addr == OPC_NIL) continue; if (lsa_ptr->lsa_header_ptr->type == OspfC_Lsa_Network_Links) { /* Destination is network */ dest_network_addr = ip_address_mask (lsa_ptr->lsa_header_ptr->link_state_id, lsa_ptr->lsa_data.lsa_network_links_ptr->network_mask); ospf_rte_table_entry_add (rte_table_ptr, OspfC_Rte_Dest_Network, dest_network_addr, lsa_ptr->lsa_data.lsa_network_links_ptr->network_mask, area_id, next_hop_addr, OspfC_Rte_Path_Intra_Area, node_ptr->root_distance, lsa_ptr->lsa_header_ptr->router_id); } else { /* Destination is area border router */ ospf_rte_table_entry_add (rte_table_ptr, OspfC_Rte_Dest_ABR, lsa_ptr->lsa_header_ptr->router_id, IpI_Broadcast_Addr, area_id, next_hop_addr, OspfC_Rte_Path_Intra_Area, node_ptr->root_distance, lsa_ptr->lsa_header_ptr->router_id); } } FOUT; } void ospf_rte_table_entry_add (OspfT_Rte_Table *rte_table_ptr, OspfT_Rte_Dest_Type route_dest_type, IpT_Address dest_id, IpT_Address subnet_mask, OspfT_Area_Id area_id, IpT_Address next_hop, OspfT_Rte_Path_Type path_type, int cost, OspfT_Router_Id adv_router_id) { OspfT_Rte_Path * path_ptr; OspfT_Rte_Entry * entry_ptr; /** Add a routing table entry specified by the above parameters. **/ FIN (ospf_rte_table_entry_add (rte_table_ptr, route_dest_type, dest_id, subnet_mask, area_id, next_hop, path_type, cost, adv_router_id)); /* Create a path to the destination. */ path_ptr = ospf_rte_table_path_create (); path_ptr->next_hop = ip_address_copy (next_hop); path_ptr->adv_router = ip_address_copy (adv_router_id); /* Create a routing table entry. */ entry_ptr = ospf_rte_table_entry_create (); entry_ptr->path_type = path_type; entry_ptr->cost = cost; entry_ptr->route_dest_type = route_dest_type; entry_ptr->dest_id = ip_address_copy (dest_id); entry_ptr->subnet_mask = ip_address_copy (subnet_mask); entry_ptr->area_id = ip_address_copy (area_id); op_prg_list_insert (entry_ptr->path_list_ptr, path_ptr, OPC_LISTPOS_TAIL); /* Add entry to routing table. */ op_prg_list_insert (rte_table_ptr->entry_list_ptr, entry_ptr, OPC_LISTPOS_TAIL); FOUT; } IpT_Address ospf_rte_table_node_next_hop_get (List *node_list_ptr) { IpT_Address next_hop_addr = OPC_NIL; OspfT_Lsa_Router_Links_Info * router_links_info_ptr; DjkT_Connection * connect_ptr; DjkT_Node * node_ptr; DjkT_Node * root_node_ptr; DjkT_Node * next_node_ptr; OspfT_Lsa * lsa_ptr; /** Extract the next hop address for a particular path of nodes. */ FIN (ospf_rte_table_node_next_hop_get (node_list_ptr)); /* If this is a one element path list, then there is no next hop. */ if (op_prg_list_size (node_list_ptr) < 2) FRET (OPC_NIL); /* Create a reference to the root node, which is always the */ /* first element of the path list. */ root_node_ptr = op_prg_list_access (node_list_ptr, OPC_LISTPOS_HEAD); /* Create a reference to the next node in the path list. */ node_ptr = op_prg_list_access (node_list_ptr, 1); lsa_ptr = (OspfT_Lsa *) node_ptr->node_state_ptr; /* Look for the connection to the next router in the path. */ if (lsa_ptr->lsa_header_ptr->type == OspfC_Lsa_Network_Links) { if (op_prg_list_size (node_list_ptr) < 3) { /* This is a path to a local network. Add it to the routing table, since */ /* we need to generate a summary links LSA for it. */ next_hop_addr = lsa_ptr->lsa_header_ptr->link_state_id; FRET (next_hop_addr); } /* Look for the router that connects to this network. */ next_node_ptr = op_prg_list_access (node_list_ptr, 2); connect_ptr = djk_connect_lookup (next_node_ptr->connection_list_ptr, node_ptr); } else connect_ptr = djk_connect_lookup (node_ptr->connection_list_ptr, root_node_ptr); /* The connection contains information about the router interface. */ router_links_info_ptr = (OspfT_Lsa_Router_Links_Info *) connect_ptr->connect_state_ptr; /* The link data field contains the router's interface to whatever it's connected to. */ /* Type 3 router links should not return this field, since it represents the subnet */ /* mask. In this case, the next hop is not yet available. */ if (router_links_info_ptr->link_type != OspfC_Lsa_Router_Link_Stub_Net) next_hop_addr = router_links_info_ptr->link_data; FRET (next_hop_addr); } void ospf_rte_table_inter_area_rtes_add (OspfT_Router *router_ptr, IpT_Address dest_id, OspfT_Area *rcvd_area_ptr) { OspfT_Area * area_ptr; List * area_list_ptr; List * summary_lsa_list_ptr; int num_lsa, lsa_index; OspfT_Lsa * lsa_ptr; OspfT_Area * check_area_ptr; int num_areas, area_index; OspfT_Area_Range * range_ptr; int num_ranges, range_index; Boolean range_found; int inter_area_cost; OspfT_Rte_Entry * abr_entry_ptr; OspfT_Rte_Entry * network_entry_ptr; OspfT_Rte_Entry * new_entry_ptr; OspfT_Rte_Path * abr_path_ptr; OspfT_Rte_Path * network_path_ptr; Boolean entry_change = OPC_FALSE; OspfT_Lsa_Header * new_lsa_header_ptr; OspfT_Lsa * new_lsa_ptr; /** Examine the summary links advertisements found on the router and construct **/ /** inter-area routes based on these advertisements. If the router is an **/ /** area border router, examine the summary LSAs found in the backbone area. **/ /** If the router is attached to a single area, then only examine the summary **/ /** LSAs for that area. This procedure corresponds to section 16.2 in RFC 1583. **/ /** This procedure can also be used upon reception of a summary links LSA. **/ /** Under section 16.5 in RFC 1583, the routing table may be calculated **/ /** incrementally (if at all) upon reception of a summary links LSA. If dest_id **/ /** is non-NIL, then this procedure will only consider entries and LSAs **/ /** pertaining to the dest_id. If dest_id is OPC_NIL, then all entries and **/ /** summary LSAs will be considered. **/ FIN (ospf_rte_table_inter_area_rtes_add (router_ptr, dest_id, rcvd_area_ptr)); area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); /* Get the area whose advertisements we need to look at. */ if (ospf_area_border_router_check (router_ptr)) area_ptr = ospf_area_backbone_get (router_ptr); else area_ptr = op_prg_list_access (area_list_ptr, OPC_LISTPOS_HEAD); /* If the received area was specified, it must match the area we examine. */ /* If not, then this procedure should not be performed. */ if ((rcvd_area_ptr != OPC_NIL) && (!ip_address_equal (area_ptr->area_id, rcvd_area_ptr->area_id))) FOUT; /* Loop through the summary advertisements in the area, and */ /* calculate inter-area routes based on these areas. */ summary_lsa_list_ptr = area_ptr->summary_lsa_list_ptr; num_lsa = op_prg_list_size (summary_lsa_list_ptr); for (lsa_index = 0; lsa_index < num_lsa; lsa_index++) { entry_change = OPC_FALSE; lsa_ptr = op_prg_list_access (summary_lsa_list_ptr, lsa_index); /* Only consider this LSA if it matches the destination specified by the client. */ if ((dest_id != OPC_NIL) && (!ip_address_equal (dest_id, lsa_ptr->lsa_header_ptr->link_state_id))) continue; /* If the advertisement was originated by the router itself, go on to the next one. */ if (ip_address_equal (lsa_ptr->lsa_header_ptr->router_id, router_ptr->router_id)) continue; /* Does the advertisement refer to a network within one of the router's */ /* configured and active address ranges? If so, then we can assume that */ /* the network described by this advertisement is either reachable via */ /* an intra-area route, or not reachable through any means. In this */ /* case, continue on to the next advertisement. */ for (area_index = 0; area_index < num_areas; area_index++) { check_area_ptr = op_prg_list_access (area_list_ptr, area_index); range_found = OPC_FALSE; num_ranges = op_prg_list_size (check_area_ptr->address_list_ptr); for (range_index = 0; range_index < num_ranges; range_index++) { range_ptr = op_prg_list_access (check_area_ptr->address_list_ptr, range_index); /* Does the LSA destination fall within this range? */ if (range_ptr->active && (ip_address_range_check (lsa_ptr->lsa_header_ptr->link_state_id, range_ptr->addr_range_ptr))) { range_found = OPC_TRUE; break; } } if (range_found) break; } /* If this LSA falls within one of the routers area ranges, continue on. */ if (range_found) continue; /* Next, look for the area border router that originated this LSA. If that */ /* router is unreachable for the area we're considering (i.e., no entry */ /* to that router exists for that area), then move on to the next LSA. */ /* If that router is reachable, calculate the cost to the network described */ /* by the LSA by adding the cost to the area border router to the cost */ /* advertised by the LSA. */ abr_entry_ptr = ospf_rte_table_entry_find (router_ptr->rte_table_ptr, lsa_ptr->lsa_header_ptr->router_id); if (abr_entry_ptr == OPC_NIL) continue; /* Is the ABR associated with the area we're interested in? */ if (!ip_address_equal (abr_entry_ptr->area_id, area_ptr->area_id)) continue; /* Find the inter-area cost to the destination network. */ inter_area_cost = abr_entry_ptr->cost + lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost; /* Does there already exist an entry for the network advertised by the LSA? */ network_entry_ptr = ospf_rte_table_entry_find (router_ptr->rte_table_ptr, lsa_ptr->lsa_header_ptr->link_state_id); abr_path_ptr = op_prg_list_access (abr_entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); if (network_entry_ptr == OPC_NIL) { /* If not, then add a new entry. */ ospf_rte_table_entry_add (router_ptr->rte_table_ptr, OspfC_Rte_Dest_Network, lsa_ptr->lsa_header_ptr->link_state_id, lsa_ptr->lsa_data.lsa_summary_links_ptr->network_mask, area_ptr->area_id, abr_path_ptr->next_hop, OspfC_Rte_Path_Inter_Area, inter_area_cost, lsa_ptr->lsa_header_ptr->router_id); entry_change = OPC_TRUE; } else { /* If this is an intra-area path, continue, since intra-area paths are always */ /* preferred to inter-area paths to the same destination. */ if (network_entry_ptr->path_type == OspfC_Rte_Path_Intra_Area) continue; /* Does this entry describe a lower cost than what we just calculated? */ /* If so, then continue, since lower cost paths are preferred. */ if (network_entry_ptr->cost <= inter_area_cost) continue; /* Modify the current entry to include the updated cost and next hop. */ network_entry_ptr->cost = inter_area_cost; network_path_ptr = op_prg_list_access (network_entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); ip_address_destroy (network_path_ptr->next_hop); network_path_ptr->next_hop = ip_address_copy (abr_path_ptr->next_hop); entry_change = OPC_TRUE; } /* If an entry changed, and this is an incremental calculation, then flood */ /* a new LSA to represent the new route to all areas except the one that */ /* received the original LSA in the first place. */ if ((dest_id != OPC_NIL) && entry_change) { for (area_index = 0; area_index < num_areas; area_index++) { check_area_ptr = op_prg_list_access (area_list_ptr, area_index); if (ip_address_equal (check_area_ptr->area_id, rcvd_area_ptr->area_id)) continue; /* Find the newly created or changed entry. */ new_entry_ptr = ospf_rte_table_entry_find (router_ptr->rte_table_ptr, dest_id); /* Create an LSA header whose link state ID is the destination network. */ new_lsa_header_ptr = ospf_lsa_header_create (OspfC_Lsa_Summary_Links, router_ptr->router_id, new_entry_ptr->dest_id); new_lsa_ptr = ospf_lsa_create (new_lsa_header_ptr); new_lsa_ptr->lsa_data.lsa_summary_links_ptr->network_mask = ip_address_copy (new_entry_ptr->subnet_mask); new_lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost = new_entry_ptr->cost; /* Install the LSA and flood. */ ospf_area_lsa_install (check_area_ptr, new_lsa_ptr); ospf_area_flood (check_area_ptr, new_lsa_ptr, OPC_NIL, OPC_TRUE); } } } FOUT; } void ospf_rte_table_areas_activate (OspfT_Router *router_ptr) { List * area_list_ptr; OspfT_Area * area_ptr; int num_areas, area_index; OspfT_Area_Range * area_range_ptr; int num_ranges, range_index; List * entry_list_ptr; OspfT_Rte_Entry * entry_ptr; int num_entries, entry_index; /** Loop through the entries in the routing table, and activate area address **/ /** ranges if a routing table entry exists in that address range. **/ FIN (ospf_rte_table_areas_activate (router_ptr)); /* Create a reference to the area list. */ area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); /* Loop through the entries in the routing table. If an entry falls */ /* within the range of an advertised area address range, mark that */ /* address range as active. This will be used later on by the */ /* inter-area route calculation procedure. */ entry_list_ptr = router_ptr->rte_table_ptr->entry_list_ptr; num_entries = op_prg_list_size (entry_list_ptr); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (entry_list_ptr, entry_index); /* Now loop through the address ranges for each area. */ for (area_index = 0; area_index < num_areas; area_index++) { area_ptr = op_prg_list_access (area_list_ptr, area_index); num_ranges = op_prg_list_size (area_ptr->address_list_ptr); for (range_index = 0; range_index < num_ranges; range_index++) { area_range_ptr = op_prg_list_access (area_ptr->address_list_ptr, range_index); if (!area_range_ptr->active && ip_address_range_check (entry_ptr->dest_id, area_range_ptr->addr_range_ptr)) area_range_ptr->active = OPC_TRUE; } } } FOUT; } void ospf_rte_table_areas_deactivate (OspfT_Router *router_ptr) { List * area_list_ptr; OspfT_Area * area_ptr; int num_areas, area_index; OspfT_Area_Range * area_range_ptr; int num_ranges, range_index; /** Loop through all area address ranges, and set them to be inactive. **/ FIN (ospf_rte_table_areas_deactivate (router_ptr)); /* Create a reference to the area list. */ area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); /* Now loop through the address ranges for each area. */ for (area_index = 0; area_index < num_areas; area_index++) { area_ptr = op_prg_list_access (area_list_ptr, area_index); num_ranges = op_prg_list_size (area_ptr->address_list_ptr); for (range_index = 0; range_index < num_ranges; range_index++) { area_range_ptr = op_prg_list_access (area_ptr->address_list_ptr, range_index); area_range_ptr->active = OPC_FALSE; } } FOUT; } /***** Constructors *****/ OspfT_Rte_Table * ospf_rte_table_create (void) { OspfT_Rte_Table * rte_table_ptr; /** Create a routing table, and return a pointer to that routing table. **/ FIN (ospf_rte_table_create (void)); rte_table_ptr = (OspfT_Rte_Table *) op_prg_mem_alloc (sizeof (OspfT_Rte_Table)); /* Initialize components of routing table. */ rte_table_ptr->entry_list_ptr = op_prg_list_create (); rte_table_ptr->dirty_flag = OPC_FALSE; rte_table_ptr->last_calc_time = 0.0; FRET (rte_table_ptr); } OspfT_Rte_Entry * ospf_rte_table_entry_create (void) { OspfT_Rte_Entry * entry_ptr; /** Create a routing table entry, and return a pointer to that entry. **/ FIN (ospf_rte_table_entry_create (void)); entry_ptr = (OspfT_Rte_Entry *) op_prg_mem_alloc (sizeof (OspfT_Rte_Entry)); /* Initialize components of the entry. */ entry_ptr->route_dest_type = OspfC_Rte_Dest_Network; entry_ptr->dest_id = OPC_NIL; entry_ptr->subnet_mask = OPC_NIL; entry_ptr->area_id = OPC_NIL; entry_ptr->path_type = OspfC_Rte_Path_Intra_Area; entry_ptr->cost = 0; entry_ptr->path_list_ptr = op_prg_list_create (); FRET (entry_ptr); } OspfT_Rte_Path * ospf_rte_table_path_create (void) { OspfT_Rte_Path * path_ptr; /** Create a routing table path, and return a pointer to that path. **/ FIN (ospf_rte_table_path_create (void)); path_ptr = (OspfT_Rte_Path *) op_prg_mem_alloc (sizeof (OspfT_Rte_Path)); /* Initialize components of path. */ path_ptr->next_hop = OPC_NIL; path_ptr->adv_router = OPC_NIL; FRET (path_ptr); } /***** Destructors *****/ void ospf_rte_table_destroy (OspfT_Rte_Table *rte_table_ptr) { /** Deallocate routing table and all its elements. **/ FIN (ospf_rte_table_destroy (rte_table_ptr)); /* Clear entries from routing table. */ ospf_rte_table_entries_clear (rte_table_ptr); /* Free the list. */ op_prg_list_free (rte_table_ptr->entry_list_ptr); /* Then free the table. */ op_prg_mem_free (rte_table_ptr); FOUT; } void ospf_rte_table_entries_clear (OspfT_Rte_Table *rte_table_ptr) { OspfT_Rte_Entry * entry_ptr; /** Remove and deallocate entries from routing table. **/ FIN (ospf_rte_table_entries_clear (rte_table_ptr)); while (op_prg_list_size (rte_table_ptr->entry_list_ptr) > 0) { entry_ptr = op_prg_list_remove (rte_table_ptr->entry_list_ptr, OPC_LISTPOS_HEAD); ospf_rte_table_entry_destroy (entry_ptr); } FOUT; } void ospf_rte_table_entry_destroy (OspfT_Rte_Entry *entry_ptr) { OspfT_Rte_Path * path_ptr; /** Deallocate a routing table entry. **/ FIN (ospf_rte_table_entry_destroy (entry_ptr)); /* Destroy the IP address elements. */ ip_address_destroy (entry_ptr->dest_id); ip_address_destroy (entry_ptr->area_id); /* Loop through the paths, and destroy each one individually. */ while (op_prg_list_size (entry_ptr->path_list_ptr) > 0) { path_ptr = op_prg_list_remove (entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); ospf_rte_table_path_destroy (path_ptr); } /* Free the path list. */ op_prg_list_free (entry_ptr->path_list_ptr); /* Free the data structure. */ op_prg_mem_free (entry_ptr); FOUT; } void ospf_rte_table_path_destroy (OspfT_Rte_Path *path_ptr) { /** Deallocate a routing table path. **/ FIN (ospf_rte_table_path_destroy (path_ptr)); /* Deallocate the components with IP addresses. */ ip_address_destroy (path_ptr->next_hop); ip_address_destroy (path_ptr->adv_router); /* Free the data structure. */ op_prg_mem_free (path_ptr); FOUT; } /***** Print Procedures *****/ void ospf_rte_table_print (OspfT_Rte_Table *rte_table_ptr) { int entry_index, num_entries; OspfT_Rte_Entry * entry_ptr; OspfT_Rte_Path * path_ptr; char entry_str [128]; char dest_str [IPC_ADDR_STR_LEN]; char net_mask_str [IPC_ADDR_STR_LEN]; char next_hop_str [IPC_ADDR_STR_LEN]; /** Print out contents of routing table. **/ FIN (ospf_rte_table_print (rte_table_ptr)); /* Print header. */ op_prg_odb_print_minor ("OSPF Routing Table","------------------", OPC_NIL); num_entries = op_prg_list_size (rte_table_ptr->entry_list_ptr); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (rte_table_ptr->entry_list_ptr, entry_index); /* Don't print out ABR destinations. */ if (entry_ptr->route_dest_type == OspfC_Rte_Dest_ABR) continue; path_ptr = op_prg_list_access (entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); ip_address_print (dest_str, entry_ptr->dest_id); ip_address_print (net_mask_str, entry_ptr->subnet_mask); ip_address_print (next_hop_str, path_ptr->next_hop); sprintf (entry_str, "Destination: %s\tSubnet Mask: %s\tNext Hop: %s\tCost: %d", dest_str, net_mask_str, next_hop_str, entry_ptr->cost); op_prg_odb_print_minor (entry_str, OPC_NIL); } FOUT; } /****** IP Routing API Procedures *****/ Compcode ospf_rte_table_lookup (int fast_address, IpT_Rte_Table_Handle rte_table_ptr, IpT_Address dest_addr, IpT_Address *next_addr_ptr) { OspfT_Rte_Entry * best_entry_ptr = OPC_NIL; OspfT_Rte_Entry * entry_ptr; int num_entries, entry_index; OspfT_Rte_Table * ospf_rte_table_ptr; IpT_Address dest_entry_addr; IpT_Address dest_net_addr; OspfT_Rte_Path * path_ptr; /** Lookup function that is called by IP to get next hop. Note that **/ /** this function currently ignores its fast address input. **/ FIN (ospf_rte_table_lookup (fast_address, rte_table_ptr, dest_addr, next_addr_ptr)); /* For DEBUG Xin Wang */ if (ip_address_equal (dest_addr, ip_address_create ("128.3.2.0")) && fast_address == 1000) printf ("inside lookup ~~~~\n"); /* Cast the incoming handle to the proper type. */ ospf_rte_table_ptr = (OspfT_Rte_Table *) rte_table_ptr; /* Loop through all the entries and find the best match. */ num_entries = op_prg_list_size (ospf_rte_table_ptr->entry_list_ptr); /* For DEBUG Xin Wang */ if (ip_address_equal (dest_addr, ip_address_create ("128.3.2.0")) && fast_address == 1000) printf ("entry_num = %d ~~~~\n", num_entries); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (ospf_rte_table_ptr->entry_list_ptr, entry_index); /* Does this entry match? */ dest_entry_addr = ip_address_mask (entry_ptr->dest_id, entry_ptr->subnet_mask); dest_net_addr = ip_address_mask (dest_addr, entry_ptr->subnet_mask); if (ip_address_equal (dest_entry_addr, dest_net_addr)) { if (best_entry_ptr == OPC_NIL) best_entry_ptr = entry_ptr; else { /* Which subnet mask is more specific? */ if (ip_address_to_int (entry_ptr->subnet_mask) > ip_address_to_int (best_entry_ptr->subnet_mask)) best_entry_ptr = entry_ptr; } } /* Destroy addresses after comparision. */ ip_address_destroy (dest_entry_addr); ip_address_destroy (dest_net_addr); } if (best_entry_ptr != OPC_NIL) { /* Get the first available path. */ path_ptr = op_prg_list_access (best_entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); *next_addr_ptr = ip_address_copy (path_ptr->next_hop); FRET (OPC_COMPCODE_SUCCESS); } else { FRET (OPC_COMPCODE_FAILURE); } } /* Added by XIn Wang */ /****** IP Routing API Procedures *****/ Compcode ospf_rte_table_cost_lookup (int fast_address, IpT_Rte_Table_Handle rte_table_ptr, IpT_Address dest_addr, int *cost) { OspfT_Rte_Entry * best_entry_ptr = OPC_NIL; OspfT_Rte_Entry * entry_ptr; int num_entries, entry_index; OspfT_Rte_Table * ospf_rte_table_ptr; IpT_Address dest_entry_addr; IpT_Address dest_net_addr; OspfT_Rte_Path * path_ptr; /** Lookup function that is called by IP to get next hop. Note that **/ /** this function currently ignores its fast address input. **/ FIN (ospf_rte_table_lookup (fast_address, rte_table_ptr, dest_addr, cost)); /* For DEBUG Xin Wang */ if (ip_address_equal (dest_addr, ip_address_create ("128.3.2.0")) && fast_address == 1000) printf ("inside lookup ~~~~\n"); /* Cast the incoming handle to the proper type. */ ospf_rte_table_ptr = (OspfT_Rte_Table *) rte_table_ptr; /* Loop through all the entries and find the best match. */ num_entries = op_prg_list_size (ospf_rte_table_ptr->entry_list_ptr); /* For DEBUG Xin Wang */ if (ip_address_equal (dest_addr, ip_address_create ("128.3.2.0")) && fast_address == 1000) printf ("entry_num = %d ~~~~\n", num_entries); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (ospf_rte_table_ptr->entry_list_ptr, entry_index); /* Does this entry match? */ dest_entry_addr = ip_address_mask (entry_ptr->dest_id, entry_ptr->subnet_mask); dest_net_addr = ip_address_mask (dest_addr, entry_ptr->subnet_mask); if (ip_address_equal (dest_entry_addr, dest_net_addr)) { if (best_entry_ptr == OPC_NIL) best_entry_ptr = entry_ptr; else { /* Which subnet mask is more specific? */ if (ip_address_to_int (entry_ptr->subnet_mask) > ip_address_to_int (best_entry_ptr->subnet_mask)) best_entry_ptr = entry_ptr; } } /* Destroy addresses after comparision. */ ip_address_destroy (dest_entry_addr); ip_address_destroy (dest_net_addr); } if (best_entry_ptr != OPC_NIL) { /* Get the first available path. */ *cost = best_entry_ptr->cost; path_ptr = op_prg_list_access (best_entry_ptr->path_list_ptr, OPC_LISTPOS_HEAD); /**next_addr_ptr = ip_address_copy (path_ptr->next_hop); */ FRET (OPC_COMPCODE_SUCCESS); } else { FRET (OPC_COMPCODE_FAILURE); } } int ospf_rte_table_fast_addr_get (IpT_Rte_Table_Handle rte_table_ptr, IpT_Address dest_addr) { /** Function to get fast address for a particular destination. Currently **/ /** not supported by OSPF, so just return an invalid fast address. **/ FIN (ospf_rte_table_fast_addr_get (rte_table_ptr, dest_addr)); FRET (IPC_FAST_ADDR_INVALID); } /***** General utilities *****/ OspfT_Rte_Entry * ospf_rte_table_entry_find (OspfT_Rte_Table *rte_table_ptr, IpT_Address entry_addr) { int num_entries, entry_index; OspfT_Rte_Entry * entry_ptr; /** Retrieve an entry whose destination is equal to the address provided. **/ /** Returns OPC_NIL if no matching entry is found. **/ FIN (ospf_rte_table_entry_find (rte_table_ptr, entry_addr)); num_entries = op_prg_list_size (rte_table_ptr->entry_list_ptr); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (rte_table_ptr->entry_list_ptr, entry_index); if (ip_address_equal (entry_ptr->dest_id, entry_addr)) FRET (entry_ptr); } FRET (OPC_NIL); } void ospf_rte_table_summary_lsa_flush (OspfT_Router *router_ptr) { OspfT_Rte_Table * rte_table_ptr; List * entry_list_ptr; OspfT_Rte_Entry * entry_ptr; List * area_list_ptr; OspfT_Area * area_ptr; int num_areas, area_index; int num_lsa, lsa_index; int num_entries, entry_index; OspfT_Lsa * lsa_ptr; IpT_Address_Range * lsa_addr_range_ptr; Boolean entry_found; /** Search through the summary LSAs and flush those whose destinations are no **/ /** longer reachable (i.e. have no entries in the routing table). **/ FIN (ospf_rte_table_summary_lsa_flush (router_ptr)); /* Create a reference to the routing table. */ rte_table_ptr = router_ptr->rte_table_ptr; entry_list_ptr = rte_table_ptr->entry_list_ptr; num_entries = op_prg_list_size (entry_list_ptr); area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); for (area_index = 0; area_index < num_areas; area_index++) { area_ptr = op_prg_list_access (area_list_ptr, area_index); num_lsa = op_prg_list_size (area_ptr->summary_lsa_list_ptr); for (lsa_index = 0; lsa_index < num_lsa; lsa_index++) { entry_found = OPC_FALSE; lsa_ptr = op_prg_list_access (area_ptr->summary_lsa_list_ptr, lsa_index); /* Only consider this advertisement for flushing if this router originated it. */ if (!ip_address_equal (lsa_ptr->lsa_header_ptr->router_id, router_ptr->router_id)) continue; lsa_addr_range_ptr = ip_address_range_create (lsa_ptr->lsa_header_ptr->link_state_id, lsa_ptr->lsa_data.lsa_summary_links_ptr->network_mask); /* Loop through the entries in the routing table to see if */ /* any part of the LSA is covered by a routing table entry. */ for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (entry_list_ptr, entry_index); if (ip_address_range_check (entry_ptr->dest_id, lsa_addr_range_ptr)) { /* Found an entry, so finish this loop. */ entry_found = OPC_TRUE; break; } } if (!entry_found) { /* If no entry was found, then flush the advertisement that */ /* we were checking. */ ospf_lsa_flush (lsa_ptr, area_ptr); } } } FOUT; } void ospf_rte_table_summary_lsa_generate (OspfT_Router *router_ptr) { OspfT_Rte_Table * rte_table_ptr; int num_areas, area_index; OspfT_Area * area_ptr; OspfT_Rte_Entry * entry_ptr; int num_entries, entry_index; OspfT_Lsa_Header * lsa_header_ptr; OspfT_Lsa * lsa_ptr; List * area_list_ptr; int num_ranges, range_index; IpT_Address_Range * addr_range_ptr; IpT_Address dest_net_addr; List * area_lsa_list_ptr; int num_lsa, lsa_index; Boolean network_found; OspfT_Area_Range * area_range_ptr; OspfT_Area * check_area_ptr; IpT_Address range_addr; /** Generate a new set of summary LSAs based on the routing table in this **/ /** router. This function also will initiate the flooding of these **/ /** advertisements throughout the rest of the AS. This corresponds to **/ /** section 12.4.3 of RFC 1583. **/ FIN (ospf_rte_table_summary_lsa_generate (router_ptr)); /* Create a reference to the routing table. */ rte_table_ptr = router_ptr->rte_table_ptr; /* Loop through the areas, and flood the appropriate advertisements throughout the area. */ area_list_ptr = ospf_area_list_get (router_ptr); num_areas = op_prg_list_size (area_list_ptr); for (area_index = 0; area_index < num_areas; area_index++) { area_ptr = op_prg_list_access (area_list_ptr, area_index); /* Generate a list of summary LSAs to flood to this area. */ area_lsa_list_ptr = ospf_area_summary_lsa_generate (area_list_ptr, area_ptr->area_id, router_ptr->router_id); /* Loop through the routing table entries. If any are appropriate */ /* to send as a summary advertisement, generate the advertisement, */ /* install it in the link state database, and flood it to the area. */ num_entries = op_prg_list_size (rte_table_ptr->entry_list_ptr); for (entry_index = 0; entry_index < num_entries; entry_index++) { entry_ptr = op_prg_list_access (rte_table_ptr->entry_list_ptr, entry_index); /* Generate a summary LSA if: */ /* 1) The destination is a network */ /* 2) The path is not for an external route */ /* 3) The associated area for the entry is not */ /* the same as the area we're looking at. */ /* Reason 2 will not apply for this model. */ /* Under the above conditions, inter-area routes are always generated. Intra-area */ /* routes will be summarized according to the list of addresses ranges configured */ /* for this area. */ if ((entry_ptr->route_dest_type == OspfC_Rte_Dest_Network) && (!ip_address_equal (area_ptr->area_id, entry_ptr->area_id))) { if (entry_ptr->path_type == OspfC_Rte_Path_Inter_Area) { /* Create an LSA header whose link state ID is the destination network. */ lsa_header_ptr = ospf_lsa_header_create (OspfC_Lsa_Summary_Links, router_ptr->router_id, entry_ptr->dest_id); lsa_ptr = ospf_lsa_create (lsa_header_ptr); lsa_ptr->lsa_data.lsa_summary_links_ptr->network_mask = ip_address_copy (entry_ptr->subnet_mask); lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost = entry_ptr->cost; /* Install the LSA and flood. */ ospf_area_lsa_install (area_ptr, lsa_ptr); ospf_area_flood (area_ptr, lsa_ptr, OPC_NIL, OPC_TRUE); } else { /* Intra-area paths must be checked against the address lists that */ /* define the area. If the network is to be advertised, merely */ /* update the cost of the address range the network is a component */ /* of. If the network is a component of a hidden address range, */ /* do not generate an advertisement for this network. If the */ /* network appears in neither address range lists, then generate */ /* an advertisement just for that network. */ /* Find the area associated with the routing table entry. */ check_area_ptr = ospf_area_lookup (area_list_ptr, entry_ptr->area_id); network_found = OPC_FALSE; /* First check the ranges to be hidden. */ num_ranges = op_prg_list_size (check_area_ptr->hidden_addr_list_ptr); for (range_index = 0; range_index < num_ranges; range_index++) { area_range_ptr = op_prg_list_access (check_area_ptr->hidden_addr_list_ptr, range_index); addr_range_ptr = area_range_ptr->addr_range_ptr; if (ip_address_range_check (entry_ptr->dest_id, addr_range_ptr)) { network_found = OPC_TRUE; break; } } if (network_found) continue; /* Then check the ranges to be advertised. */ num_ranges = op_prg_list_size (check_area_ptr->address_list_ptr); for (range_index = 0; range_index < num_ranges; range_index++) { area_range_ptr = op_prg_list_access (check_area_ptr->address_list_ptr, range_index); addr_range_ptr = area_range_ptr->addr_range_ptr; if (ip_address_range_check (entry_ptr->dest_id, addr_range_ptr)) { /* Check the corresponding LSA, and update the cost if necessary. */ range_addr = ip_address_mask (addr_range_ptr->address, addr_range_ptr->subnet_mask); lsa_ptr = ospf_lsa_lookup (area_lsa_list_ptr, range_addr, router_ptr->router_id, OspfC_Lsa_Summary_Links); ip_address_destroy (range_addr); network_found = OPC_TRUE; if ((entry_ptr->cost < lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost) || (lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost == 0)) { lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost = entry_ptr->cost; break; } } } if (network_found) continue; /* Destination is not a component of the defined area address ranges. */ /* Generate a summary links LSA for this destination. */ /* Create an LSA header whose link state ID is the destination network. */ lsa_header_ptr = ospf_lsa_header_create (OspfC_Lsa_Summary_Links, router_ptr->router_id, entry_ptr->dest_id); lsa_ptr = ospf_lsa_create (lsa_header_ptr); lsa_ptr->lsa_data.lsa_summary_links_ptr->network_mask = ip_address_copy (entry_ptr->subnet_mask); lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost = entry_ptr->cost; /* Install the LSA and flood. */ ospf_area_lsa_install (area_ptr, lsa_ptr); ospf_area_flood (area_ptr, lsa_ptr, OPC_NIL, OPC_TRUE); } } } /* Now send out the summarized link state advertisements for this */ /* area. Only send the advertisements if their cost is non-zero, */ /* indicating that the routing table contains a component of the */ /* range denoted by the advertisement. */ num_lsa = op_prg_list_size (area_lsa_list_ptr); for (lsa_index = 0; lsa_index < num_lsa; lsa_index++) { lsa_ptr = op_prg_list_access (area_lsa_list_ptr, lsa_index); if (lsa_ptr->lsa_data.lsa_summary_links_ptr->network_cost > 0) { ospf_area_lsa_install (area_ptr, lsa_ptr); ospf_area_flood (area_ptr, lsa_ptr, OPC_NIL, OPC_TRUE); } } } FOUT; }