A * search algorithm in networking

Question

I'm not entirely sure if this question has been asked before, so apologies if it has.

I'm studying computer science at university and I've had two modules: Data Communication and Networking; Artificial Intelligence.

In networking we've been learning about routing and connecting routers together in order to transfer data (mainly discussing different types of protocols).

In AI, we used the A* Search as a path finding algorithm from a start node to a goal node in a graph with walls and traps.

My main question is: Is it possible for A* Search to be used in routing?

I understand that you would need to identify a form of cost between network nodes and find a suitable heuristic to do so. I'm more interested to know if something like that could work, and if not, then how?

Thanks!

Answer 1

A * is an extension of the Dijkstra algorithm that used by some routing protocols, e.g. OSPF and IS-IS.

It is certainly possible to create a new routing protocol that uses A *, but it would really need to add something new to find any acceptance.

---

Edit:

In networking, routing is handled by routers. A node will know if the destination node is on a different network. If it is, then the node sends the traffic to its configured gateway (router).

A router has a routing table where it looks up the destination address to find the next interface to which the traffic should be sent. The routing table may be implemented as a memory structure (lookup table, tree, trie, etc.) or in hardware (CAM, TCAM, etc.).

The interesting part is how a routing table is populated. Routers learn about routes three ways:

1. Directly connected networks
2. Statically configured routes
3. Routing protocols

A routing protocol is where the algorithms are used.

It really is not in the best interest of the network for a node to determine which path its traffic should take.