Routing

Optimal route calculation for vehicles between a point of origin and a target point based on cartography of the OpenStreetMap project.

The routing or routing is the function of searching for a path among all the possible ones in a packet network whose topologies have a great connectivity. Since it is about finding the best possible route, the first thing to do is to define what is meant by "best route" and consequently what is the "metric" that should be used to measure it.

Strict sense routing refers to IP routing and is opposed to bridging. Routing assumes that network addresses are structured and that similar addresses imply proximity within the network. Structured addresses allow a single routing table entry to represent the route to a group of devices. In large networks, structured addressing (routing in the strict sense) outperforms unstructured addressing (bridging). Routing has become the dominant form of addressing on the Internet. Bridging is still widely used in local area networks.

Network Parameters

Network metrics

It can be, for example, the number of hops needed to go from one point to another. Although this is not an optimal metric since it assumes “1” for all links, it is simple and usually gives good results.

Best route

Best route is understood to be the one that meets the following conditions:

• Get to keep the delay between pairs of network nodes.
• Gets to offer effective high cadences regardless of the average transit delay.
• Allows to offer the lowest cost.

The simplest criterion is to choose the shortest path, that is, the route that passes through the fewest number of nodes. A generalization of this criterion is that of “minimum cost”. In general, the concept of distance or cost of a channel is a measure of the quality of the link based on the metric that has been defined. In practice several metrics are used simultaneously.

Routing in virtual circuit and datagram networks

When the packet-switched network operates in virtual circuit mode, the routing function generally establishes a route that does not change during the lifetime of that virtual circuit. In this case the routing is decided per session.

A network that works in datagram mode does not have the commitment to guarantee the orderly delivery of the packets, so the nodes can change the routing criteria for each packet that has to be sent. Any change in the network topology is easy to solve in terms of routing, once the corresponding algorithm has discovered the new optimal path.

Classification of routing methods

The routing algorithms can be grouped into:

Deterministic or static

They do not take into account the state of the subnet when making routing decisions. The routing tables of the nodes are configured manually and remain unchanged until they are not acted upon again. Therefore, the adaptation in real time to changes in network conditions is nil.

The calculation of the optimal route is also off-line (off-line) so neither the complexity of the algorithm nor the time required for its convergence does not matter. Ex: Dijkstra's algorithm.

These algorithms are rigid, fast and simple in design, yet they make the worst decisions overall...

Adaptive or dynamic

They can make them more tolerant of changes in the subnet such as variations in traffic, increased delay, or topology failures. Dynamic or adaptive routing can be classified in turn into three categories, depending on where the decisions are made and the origin of the information exchanged:

• Centralized adaptation: all network nodes are equal except a central node that collects control information and data from the other nodes to calculate with them the lacing table. This method has the inconvenience that it consumes abundant resources from the network itself.
• Distributed adaptation: This type of lacing is characterized because the corresponding algorithm is executed equally on all nodes of the subnet. Each node continuously recalculates the lacing table from that information and that it contains in its own database. To this type belong two of the most used on the Internet that are the algorithms by vector of distances and the state of liaison.

• Insulated adaptive: they are characterized by the simplicity of the method they use to adapt to the changing state of the network. Your response to traffic or topology changes is obtained from the local and own information of each node. A typical case is the “inundation” roaming, whose mechanism is to forward each package received for other nodes, for all the links except for which it arrived.