ospf_dijkstra.c

vxworks下ospf协议栈

	OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V)
{
	USHORT length_of_advertisement =0;
	USHORT number_of_links =0;
	OSPF_NETWORK_LINK_PIECE *sptr_link= NULL;
	ULONG link_id =0;
	OSPF_LS_DATABASE_ENTRY *sptr_database_entry_for_vertex_W =NULL;
	USHORT age =0;
	enum TEST test_return_type;
	ULONG cost_D =0;
	USHORT tos0_metric =0;
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_W =NULL;
	OSPF_NEXT_HOP_BLOCK *sptr_next_hop =NULL;
	ULONG vertex =0;
	char print_buffer[PRINT_BUFFER_SIZE];
	char print_buffer_1[PRINT_BUFFER_SIZE];

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

	tos0_metric = 0x00000000L;

	PARAMETER_NOT_USED (tos0_metric);

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_examine_network_link_advertisement_for_vertex_V\r\n");

	length_of_advertisement = sptr_network_link_advertisement->ls_header.length;
	length_of_advertisement = net_to_host_short (length_of_advertisement);

	number_of_links = (USHORT) ((length_of_advertisement - OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER_SIZE) / OSPF_NETWORK_LINK_PIECE_SIZE);

	for (sptr_link = &sptr_network_link_advertisement->attached_router; number_of_links > 0x0000; --number_of_links,
		sptr_link = (OSPF_NETWORK_LINK_PIECE *) ((ULONG) sptr_link + OSPF_NETWORK_LINK_PIECE_SIZE))
		{

		link_id = sptr_link->link_id;
		link_id = net_to_host_long (link_id);

		/* SPR#76812 -- Begin */
		sptr_database_entry_for_vertex_W = ospf_find_LSA (sptr_area,link_id, 0x00000000L, OSPF_LS_ROUTER);
		/* SPR#76812 -- End */

 		if (sptr_database_entry_for_vertex_W == NULL)
 			{
			continue;													/* section 16.1, item (2)(b) page (152) */
			}

		age = sptr_database_entry_for_vertex_W->advertisement.sptr_router->ls_header.age;
		age = net_to_host_short (age);

		if (age == OSPF_MAXIMUM_AGE)
			{
			continue;													/* section 16.1, item (2)(b) page (152) */
			}

		vertex = sptr_network_link_advertisement->ls_header.advertising_router;
		vertex = net_to_host_long (vertex);

		test_return_type = ospf_check_if_link_exists (&sptr_database_entry_for_vertex_W->advertisement, vertex, sptr_area);

		if (test_return_type == FAIL)
			{

			OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer, link_id);
			OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer_1, vertex);

			OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Link does not exist from %s back to %s (network link's advertising router)\r\n", print_buffer, print_buffer_1);

			continue;													/* section 16.1, item (2)(b) page (152) */
			}

        /* SPR 87386 - Begin */
        /*
           Check if a link exists to a transit network in the router LSA of the attached router. 
           If no link found skip this attached router.   
        */
		test_return_type = ospf_check_if_net_link_exists (sptr_network_link_advertisement, 
                                                          (sptr_database_entry_for_vertex_W->advertisement.sptr_router));

		if (test_return_type == FAIL)
			{

			OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer, link_id);
			OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer_1, vertex);

			OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Link does not exist from %s back to %s (network link's advertising router)\r\n", print_buffer, print_buffer_1);

			continue;													
			}
        /* SPR 87386 - End */
		
        test_return_type = ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree (sptr_area, link_id, OSPF_LS_ROUTER /*#$-NOTE:note31-$#*/);

		if (test_return_type == PASS)
			{
			continue;													/* section 16.1, item (2)(c) page (152) */
			}


		cost_D = sptr_vertex_V->cost;

		sptr_vertex_W = ospf_find_vertex_W_on_candidate_list (sptr_area->sptr_candidate, link_id, OSPF_LS_ROUTER );

		if (sptr_vertex_W == NULL)									/* section 16.1, item (2)(d), third bullet item, page (152) */
			{
			sptr_vertex_W = (OSPF_SHORTEST_PATH_NODE *) table_malloc (1, sizeof (OSPF_SHORTEST_PATH_NODE));

			if (sptr_vertex_W == NULL)
				{
				ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *) NULL, "OSPF_SHORTEST_PATH_NODE");

				continue;
				}

			memset (sptr_vertex_W, 0x00, sizeof (OSPF_SHORTEST_PATH_NODE));

			sptr_vertex_W->vertex = sptr_link->link_id;

			sptr_vertex_W->vertex = net_to_host_long (sptr_vertex_W->vertex);

			sptr_vertex_W->vertex_type = OSPF_LS_ROUTER;

			sptr_vertex_W->sptr_database_entry = sptr_database_entry_for_vertex_W;

			sptr_vertex_W->cost = cost_D;

			OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "IN EXAMINE NETWORK LINK ADVERTISEMENTS: PARENT vertex_V:%lx type:%x cost:%d vertex_W:%lx type:%x cost:%d \r\n",
				sptr_vertex_V->vertex, sptr_vertex_V->vertex_type, sptr_vertex_V->cost, sptr_vertex_W->vertex, sptr_vertex_W->vertex_type, sptr_vertex_W->cost);

			ospf_set_intervening_router (sptr_vertex_V, sptr_vertex_W, sptr_area, NULL);

            sptr_vertex_W->sptr_next_hop = ospf_calculate_the_set_of_next_hops (sptr_vertex_W, sptr_vertex_V, NULL, sptr_area);

			if (sptr_area->sptr_candidate == NULL)
				{
				sptr_area->sptr_candidate = sptr_vertex_W;
				}
			else
				{
				ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_vertex_W, (OSPF_GENERIC_NODE *) sptr_area->sptr_candidate);
				}
			}
		else if (cost_D > sptr_vertex_W->cost)				/* section 16.1, item (2)(d), first bullet item, page (152) */
			{
			continue;
			}
		else if (cost_D == sptr_vertex_W->cost)			/* section 16.1, item (2)(d), second bullet item, page (152) */
			{
			ospf_set_intervening_router (sptr_vertex_V, sptr_vertex_W, sptr_area, NULL);

            sptr_next_hop = ospf_calculate_the_set_of_next_hops (sptr_vertex_W, sptr_vertex_V, NULL, sptr_area);

			if (sptr_vertex_W->sptr_next_hop == NULL)
				{
				sptr_vertex_W->sptr_next_hop = sptr_next_hop;
				}
			else if (sptr_next_hop != NULL)
				{
				ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_next_hop, (OSPF_GENERIC_NODE *) sptr_vertex_W->sptr_next_hop);
				}
			}
		else															/* section 16.1, item (2)(d), third bullet item, page (152) */
			{
			sptr_vertex_W->sptr_database_entry = sptr_database_entry_for_vertex_W;

			sptr_vertex_W->cost = cost_D;

			ospf_set_intervening_router (sptr_vertex_V, sptr_vertex_W, sptr_area, NULL);

            sptr_vertex_W->sptr_next_hop = ospf_calculate_the_set_of_next_hops (sptr_vertex_W, sptr_vertex_V, NULL, sptr_area);
			}
		}

	return;
}

/**************************************************************************************
*
* ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree - checks if node is already on shortest path tree
*
* This routine will check if a node associated with the vertex is already on the shortest
* path tree before adding the node to the shortest path tree.
*
* <sptr_area> OSPF area
*
* <vertex_W> Shortest path node for vertex on router OSPF is examining
*
* <ls_type> Link state advertisement type
*
* RETURNS: PASS or FAIL
*
* ERRNO: N/A
*
* NOMANUAL
*/
static enum TEST ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	ls_type )
{
	OSPF_SHORTEST_PATH_NODE *sptr_shortest_path_node =NULL;
	OSPF_INTERFACE *sptr_interface = NULL;
	OSPF_INTERFACE *sptr_next_interface = NULL;
	enum BOOLEAN need_further_checking;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree\r\n");

	if ( (sptr_area->shortest_path_first_tree.vertex == vertex_W) && (sptr_area->shortest_path_first_tree.vertex_type == ls_type ) ) /* If RID is also one of the Interface address#$-NOTE:note1-$#*/
		{
		need_further_checking = FALSE;

		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)
			{
				if ((sptr_interface->designated_router.address == vertex_W) && (ls_type == OSPF_LS_NETWORK) ) 	/* #$-NOTE:note12-$#*/
					{
					need_further_checking = TRUE;
					}
				}
			}

		if (need_further_checking != TRUE)
			{
			return (PASS);
			}
		}

	if (sptr_area->shortest_path_first_tree.sptr_forward_link != NULL)
		{
		for (sptr_shortest_path_node = sptr_area->shortest_path_first_tree.sptr_forward_link; sptr_shortest_path_node != NULL;
			sptr_shortest_path_node = sptr_shortest_path_node->sptr_forward_link)
			{
			if ( (sptr_shortest_path_node->vertex == vertex_W) && (sptr_shortest_path_node->vertex_type == ls_type) )
				{
				return (PASS);
				}
			}
		}

	return (FAIL);
}

/**************************************************************************************
*
* ospf_find_vertex_W_on_candidate_list - finds associated shortest path node on candidate list
*
* This routine will try to find an associated shortest path node to the vertex OSPF is
* examining on the candidate list.
*
* <sptr_candidate> Shortest path node candidate list
*
* <vertex_W> Vertex OSPF is examining
*
* <link_type> Link state advertisement type
*
* RETURNS: OSPF_SHORTEST_PATH_NODE * or NULL
*
* ERRNO: N/A
*
* NOMANUAL
*/
static OSPF_SHORTEST_PATH_NODE *ospf_find_vertex_W_on_candidate_list (OSPF_SHORTEST_PATH_NODE *sptr_candidate,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	link_type)
{
	OSPF_SHORTEST_PATH_NODE *sptr_node =NULL;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_find_vertex_W_on_candidate_list\r\n");

	for (sptr_node = sptr_candidate; sptr_node != NULL; sptr_node = sptr_node->sptr_forward_link)
		{
		if ((sptr_node->vertex == vertex_W) && (sptr_node->vertex_type == link_type) )
			{
			return (sptr_node);
			}
		}

	return (NULL);
}

/**************************************************************************************
*
* ospf_choose_closest_vertex_to_root - traverses through the candidate list to find the closest node to root
*
* This routine will traverse through the shortest path node candidate list to find
* the closest vertex to the root.  This is done by comparing the costs between each
* candidate in the list and returning the smallest cost shortest path node.
*
* <sptr_candidate> Shortest path node candidate list
*
* RETURNS: OSPF_SHORTEST_PATH_NODE * or NULL
*
* ERRNO: N/A
*
* NOMANUAL
*/
static OSPF_SHORTEST_PATH_NODE *ospf_choose_closest_vertex_to_root (OSPF_SHORTEST_PATH_NODE *sptr_candidate)
{
	OSPF_SHORTEST_PATH_NODE *sptr_node =NULL;
	OSPF_SHORTEST_PATH_NODE *sptr_closest_vertex =NULL;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_choose_closest_vertex_to_root\r\n");

	sptr_closest_vertex = sptr_candidate;

	for (sptr_node = sptr_candidate; sptr_node != NULL; sptr_node = sptr_node->sptr_forward_link)
		{

		if (sptr_node->cost < sptr_closest_vertex->cost)
			{
			sptr_closest_vertex = sptr_node;
			}
		else if (sptr_node->cost > sptr_closest_vertex->cost)
			{
			continue;
			}
		else if ((sptr_node->sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_NETWORK) &&
			(sptr_closest_vertex->sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_ROUTER))
			{
			sptr_closest_vertex = sptr_node;
			}
		}

	return (sptr_closest_vertex);
}

/**************************************************************************************
*
* ospf_add_closest_vertex_to_shortest_path_tree - adds the candidate to the shortest path tree
*
* This routine will add the candidate to the shortest path tree and remove the node from
* the candidate list.
*
* <sptr_vertex_to_add> Shortest path node candidate
*
* <sptr_area> OSPF area
*
* RETURNS: N/A
*
* ERRNO: N/A
*
* NOMANUAL
*/
static void ospf_add_closest_vertex_to_shortest_path_tree (OSPF_SHORTEST_PATH_NODE *sptr_vertex_to_add,OSPF_AREA_ENTRY *sptr_area)
{
	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_add_closest_vertex_to_shortest_path_tree\r\n");