Source-Tree Adaptive Routing Protocol

from Wikipedia, the free encyclopedia

The Source-Tree Adaptive Routing Protocol ( STAR ) was the first proactive routing protocol to work with link-state information. It also implemented the LORA principle (Least Overhead Routing Approach; found paths are retained for as long as possible to avoid control messages) for the first time. STAR does not use the shortest possible paths so that unnecessary control messages can be avoided. All nodes are assigned fixed addresses, which has the advantage that the information does not have to be constantly updated . These consist of at least one LSU (Link State Update).

When the network is initialized, source trees are created which represent the connections between a node and its neighbor. The next step (= update) consists in sending your own source tree to all neighboring nodes, which update your own source tree with it. In this way, each node can build a topology graph that contains the complete network with its own and the obtained source tree .

Update information

Update information is broadcast and numbered. The counter is only increased by the transmitter. An LSU is valid if the number is higher than the last stored number for the same connection, which has the advantage that LSUs do not have to be updated periodically.

Update information will be sent if

  • a recipient can no longer be reached,
  • a new recipient has been found,
  • it appears that loops have been formed
  • the metric of the connections exceeds the maximum value, which can be determined by comparing the received with the own source tree.

Prevent loops

To prevent loops, the following rules for sending update information must apply to a Router [R]. It sends updates if

  1. a path seems to end in a loop
  2. a new selected successor of the router [R] has a higher address,
  3. the distance to the recipient via a selected successor is greater than to the old successor.

Examples

  1. If a router [R] receives an update from neighbor X, its source tree is updated. The next step is to test for which receiver neighbor X must go via router [R] and whether router [R] has to go via neighbor [N] in order to reach the same receiver.
  2. Every router has a fixed address and when a router [R] has to look for a new successor, it always takes the one with a higher address than its own. An update will then be sent.
  3. See pictures.

STAR counterexample.jpg

Illustration (II) - (IV) show the source trees of the yellow marked nodes or routers. If connection (c, d) fails, the source tree of c in Figure V. No update is necessary here, since the successor has a lower number than router c. In this case it is not possible to apply rule 2 because there is no router with a higher number. Now connection (b, e) fails. The source tree of b is shown in Figure VI and again no update is necessary because the successor has a lower number. To reach router d, it tries to send via a and c. At the same time, router c only knows the route to d via b. This is how a loop was created.

STAR-Example.jpg

An update is sent immediately if connection (c, d) fails because the metric has been increased to f (Figure II). Router a corrects its source tree in Figure III. If connection (b, e) fails again, b sends an update with the metric (b, e) = infinite, as it knows that (c, d) has also failed and therefore d, e and f can no longer be reached .

Web links