ospf_shortest_path_calculation.c

vxworks下ospf协议栈

	USHORT advertisement_length;
	ULONG link_id;
	enum TEST test_return_type;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_check_if_link_exists\r\n");

	OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer, vertex);

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Checking if link exists back to vertex = %s\n", print_buffer);

	if (vertex == ospf.router_id)
		{
		return (PASS);
		}
	else if (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_ROUTER)
		{
		test_return_type = ospf_check_if_link_exists_for_ls_header_type_of_ls_router (sptr_advertisement, vertex, sptr_area);

		return (test_return_type);
		}
	else if (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_NETWORK)
		{

		sptr_network_link = &sptr_advertisement->sptr_network->attached_router;

		advertisement_length = sptr_advertisement->sptr_network->ls_header.length;
		advertisement_length = net_to_host_short (advertisement_length);
		advertisement_length = (USHORT) (advertisement_length - OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER_SIZE);

		for (; advertisement_length > 0x0000; advertisement_length = (USHORT) (advertisement_length - OSPF_NETWORK_LINK_PIECE_SIZE))
			{
			link_id = sptr_network_link->link_id;
			link_id = net_to_host_long (link_id);

			if (link_id == vertex)
				{
				return (PASS);
				}

			++sptr_network_link;

			}

		return (FAIL);
		}
	else
		{
		return (FAIL);
		}
}
/***********************************************************************************************//* section 16.1.1 (page 155-156) */
OSPF_NEXT_HOP_BLOCK *ospf_calculate_the_set_of_next_hops (OSPF_SHORTEST_PATH_NODE *sptr_destination,OSPF_SHORTEST_PATH_NODE *sptr_parent,
	OSPF_ROUTER_LINK_PIECE *sptr_link, OSPF_AREA_ENTRY *sptr_area)
{
	OSPF_NEXT_HOP_BLOCK *sptr_next_hop;

	sptr_next_hop = NULL;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_calculate_the_set_of_next_hops\r\n");

	if (sptr_destination->intervening_router != 0x00000000L)
		{
		sptr_next_hop = ospf_set_next_hop_when_intervening_router_is_present (sptr_destination, sptr_parent, sptr_area, sptr_link);
		}
	else if (sptr_parent->vertex == ospf.router_id)						/* the parent vertex is the root */
		{
		sptr_next_hop = ospf_set_next_hop_when_parent_vertex_is_this_router (sptr_destination, sptr_link, sptr_area);
		}
	else if (sptr_link != NULL)
		{
		if (sptr_parent->vertex == sptr_link->link_id)		/* link points back to the parent network */
			{
			sptr_next_hop = ospf_create_next_hop_block ();

			if (sptr_next_hop != NULL)
				{
				sptr_next_hop->next_hop_router = sptr_link->link_data;
				sptr_next_hop->next_hop_router = net_to_host_long (sptr_next_hop->next_hop_router);

				sptr_next_hop->outgoing_router_interface = sptr_next_hop->next_hop_router;
				}
			else
				{
				return NULL;
				}
			}
		}

	if (sptr_next_hop != NULL)
		{
		if ( (sptr_next_hop->next_hop_router == 0x00000000L) && (sptr_next_hop->outgoing_router_interface == 0x00000000L) )
			{
			table_free (sptr_next_hop);
			sptr_next_hop = NULL;

			return (NULL);
			}
		}
	return (sptr_next_hop);
}
/**********************************************************************************************************************************/
static OSPF_NEXT_HOP_BLOCK *ospf_create_next_hop_block (void)
{
	OSPF_NEXT_HOP_BLOCK *sptr_next_hop;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_create_next_hop_block\r\n");

	sptr_next_hop = (OSPF_NEXT_HOP_BLOCK *) table_malloc (1, sizeof (OSPF_NEXT_HOP_BLOCK));

	if (sptr_next_hop == NULL)
		{
		ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *) NULL, "OSPF_NEXT_HOP_BLOCK");
		}
	else
		{
		memset (sptr_next_hop, 0x00, sizeof (OSPF_NEXT_HOP_BLOCK));
		}

	return (sptr_next_hop);
}
/**********************************************************************************************************************************/
static ULONG ospf_find_outgoing_interface_for_router (ULONG router, ULONG interface_address, ULONG *next_hop_router)
{
	OSPF_AREA_ENTRY *sptr_area = NULL;
	OSPF_AREA_ENTRY *sptr_next_area = NULL;
	OSPF_INTERFACE *sptr_interface = NULL;
	OSPF_INTERFACE *sptr_next_interface = NULL;
	OSPF_NEIGHBOR *sptr_neighbor = NULL;
	OSPF_NEIGHBOR *sptr_next_neighbor = NULL;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_find_outgoing_interface_for_router\r\n");

	for (sptr_area = ospf.sptr_area_list; sptr_area != NULL; sptr_area = sptr_next_area)
		{
		sptr_next_area = sptr_area->sptr_forward_link;
		for (sptr_interface = sptr_area->sptr_interfaces; sptr_interface != NULL; sptr_interface = sptr_next_interface)
			{
			sptr_next_interface = sptr_interface->sptr_forward_link;
			if (sptr_interface->area_id == sptr_area->area_id)
				{
			 	for (sptr_neighbor = sptr_interface->sptr_neighbor; sptr_neighbor != NULL; sptr_neighbor = sptr_next_neighbor)
			 		{
					sptr_next_neighbor = sptr_neighbor->sptr_forward_link;
			 		if ((sptr_neighbor->id == router) && ((interface_address == sptr_interface->address) || (interface_address == 0x00000000)))
			 			{
#if defined (__UNNUMBERED_LINK__)
			 			if (sptr_interface->address == 0x00000000L)
			 				{
        	                 *next_hop_router = sptr_neighbor->address;
			 				return (sptr_interface->port_number);
			 				}
			 			else
			 				{
	                       	*next_hop_router = sptr_neighbor->address;
			 				return (sptr_interface->address);
			 				}
#else /* __UNNUMBERED_LINK__ */
                    	*next_hop_router = sptr_neighbor->address;
						return (sptr_interface->address);
#endif /* __UNNUMBERED_LINK__ */
						}
					}
		   		}
			}
		}

	return (00000000L);
}
/**********************************************************************************************************************************/
OSPF_NEXT_HOP_BLOCK *ospf_inherit_the_set_of_next_hops_from_node_X (OSPF_NEXT_HOP_BLOCK *sptr_node_X_next_hops)
{
	OSPF_NEXT_HOP_BLOCK *sptr_first_new_next_hop;
	OSPF_NEXT_HOP_BLOCK *sptr_next_hop;
	OSPF_NEXT_HOP_BLOCK *sptr_next_hop_of_node_X;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_inherit_the_set_of_next_hops_from_node_X\r\n");

	sptr_first_new_next_hop = NULL;

	for (sptr_next_hop_of_node_X = sptr_node_X_next_hops; sptr_next_hop_of_node_X != NULL;
		sptr_next_hop_of_node_X = sptr_next_hop_of_node_X->sptr_forward_link)
		{
		sptr_next_hop = (OSPF_NEXT_HOP_BLOCK *) table_malloc (1, sizeof (OSPF_NEXT_HOP_BLOCK));

		if (sptr_next_hop == NULL)
			{
			ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *) NULL, "OSPF_NEXT_HOP_BLOCK");

			return (NULL);
			}

		memset (sptr_next_hop, 0x00, sizeof (OSPF_NEXT_HOP_BLOCK));

		sptr_next_hop->outgoing_router_interface = sptr_next_hop_of_node_X->outgoing_router_interface;
		sptr_next_hop->next_hop_router = sptr_next_hop_of_node_X->next_hop_router;

		if (sptr_first_new_next_hop == NULL)
			{
			sptr_first_new_next_hop = sptr_next_hop;
			}
		else
			{
			ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_next_hop, (OSPF_GENERIC_NODE *) sptr_first_new_next_hop);
			}
		}

	return (sptr_first_new_next_hop);
}
/**********************************************************************************************************************************/
void ospf_schedule_shortest_path_first_job (OSPF_AREA_ENTRY *sptr_area)
{
	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_schedule_shortest_path_first_job\r\n");

	if (sptr_area->run_shortest_path_calculation == FALSE)
		{
		sptr_area->run_shortest_path_calculation = TRUE;
		sptr_area->shortest_path_calculation_time_counter = 0x00000000L;
		}

	return;
}
/**********************************************************************************************************************************/
static OSPF_NEXT_HOP_BLOCK *ospf_set_next_hop_when_intervening_router_is_present (OSPF_SHORTEST_PATH_NODE  *sptr_destination, OSPF_SHORTEST_PATH_NODE  *sptr_parent, OSPF_AREA_ENTRY *sptr_area, OSPF_ROUTER_LINK_PIECE *sptr_link)
{
 	OSPF_NEXT_HOP_BLOCK *sptr_next_hop = NULL;
	OSPF_INTERFACE *sptr_interface = NULL;
	OSPF_INTERFACE *sptr_next_interface = NULL;
	OSPF_NEIGHBOR *sptr_neighbor = NULL;
	OSPF_NEIGHBOR *sptr_next_neighbor = NULL;
	ULONG best_cost = 0x00000000;
	bool first_pass = TRUE;
	OSPF_NEIGHBOR *best_neighbor = NULL;
	USHORT tos0_metric;
	ULONG link_id = 0x00000000;

	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_set_next_hop_when_intervening_router_is_present\r\n");

	if (sptr_link == NULL)
		{
		tos0_metric = 0x0000;
		}
	else
		{
		tos0_metric = sptr_link->tos0_metric;
		tos0_metric = net_to_host_short (tos0_metric);
		link_id = sptr_link->link_id;
		link_id = net_to_host_long(link_id);
		}

	sptr_next_hop = NULL;


	for (sptr_interface = ospf.sptr_interface_list; sptr_interface != NULL; sptr_interface = sptr_next_interface)
        {
		sptr_next_interface = sptr_interface->sptr_forward_link;
		/* SPR 71227 */
		if (sptr_interface->area_id == sptr_area->area_id)
			{
			OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "OSPF: ----->>>>> ospf_set_next_hop_when_intervening_router_is_present: interface address: %lx\r\n", sptr_interface->address);
			for (sptr_neighbor = sptr_interface->sptr_neighbor; sptr_neighbor != NULL; sptr_neighbor = sptr_next_neighbor)
				{
				sptr_next_neighbor = sptr_neighbor->sptr_forward_link;
				OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "OSPF: ----->>>>> ospf_set_next_hop_when_intervening_router_is_present: neighbor address: %lx\r\n", sptr_interface->sptr_neighbor->address);
				if ((sptr_neighbor->id == sptr_destination->intervening_router) || (sptr_neighbor->address == sptr_destination->intervening_router))
					{
                    /* SPR# 85573 fix start 
                     * Checking only the neighbor state is not sufficient especially when there are multiple
                     * interfaces to the same neighbor. Interface state needs to considered as
                     * well before considering the interface as operational. Only those interfaces that have 
                     * state equal to or higher than point-to-point are considered operational - RFC 2328 Sec 9.1.
                     * Interfaces whose state is lower than point-to-point are just ignored while determining the
                     * best outgoing interface.
                     */
                    if ((sptr_neighbor->state != OSPF_NEIGHBOR_FULL) || 
                        (sptr_neighbor->sptr_interface->state < OSPF_INTERFACE_POINT_TO_POINT) )
                    /* SPR# 85573 fix end */
						{
						continue;
						}
					
                    
                    if (first_pass)
						{
						first_pass = FALSE;
						best_cost = sptr_neighbor->sptr_interface->cost;
						best_neighbor = sptr_neighbor;
						}
					else
						{
						if (best_cost > sptr_neighbor->sptr_interface->cost)
							{
							best_neighbor = sptr_neighbor;
							best_cost = sptr_neighbor->sptr_interface->cost;
							}
						}
					}
 				}
			}
		}
    if (best_neighbor != NULL)