Optimal or Shortest Path Routing | 4G Networks

In terms of route choices, the traditional routing may be classified as Optimal or Shortest Path routing. An algorithm is said to present optimal routing, only when it has a convex function f _routing. (X): X → D, where D is always the best routing for all X, the convex set of parameters for this function. Although seemingly highly desirable, it suffers from some design limitations. It is difficult to build an optimized routing function that accurately captures all the performance measures and balances all data flows in a network. This task could lead to the use of routing parameters with incorrect or insufficient information, generating a probable unbalanced environment.

In general, many works define a function f (x) which expresses how to measure the network performance using metrics such as delay, latency, packet loss, link throughput and so on. Next, f(x) is minimized over variable x by applying one or more derivatives and defining the inequality of the form g_i(x) ≤ α and/or equality of the form h_i(x) = ω asconstraints, where g_i is a convex function and h_i is an affine function (i.e. one that consists of a linear transformation then a translation). As a result, an optimal routing algorithm controls the traffic and load balancing according to constraints of the minimum global value. The formula (4) could be a generic optimal function defined to choose the best route r_i(one with minimal load among neighbors of node k expressed by N_k) in terms of network load (expressed using constraints over the total mean and variance flow over the network).

Although not strictly a routing protocol, acting between the link and network layers, the IETF multiprotocol label switching (MPLS) may be seen as one that falls into the optimal routing class. MPLS has emerged as a very promising traffic engineering tool used in the control of traffic within current broadband core networks.

The routing protocols, classified as Shortest Path Routing (SPF), are characterized as those where each network node k selects routes following a formula such as the one in (5): here node k chooses the neighbor that can route its message with the shortest metric between source (node k) and destination. The number of hops is the usually used metric, but others also may used in addition to the attribution of weight for each metric such delay, throughput and others. In this case, the shortest path is the route with lowest weight instead to be the one with smallest number of hops. Consequently, we could classify SPF as an optimal routing when the network traffic is always stable, where, for example, the user's network maintains   and σ² ≤ ω.

However, this scenario is not a common one. Given that each node leads with estimated costs of link and does not worry whether its choices will unbalance the network traffic, SPF nodes tend to generate points of congestion on the network on a shortest path, along which most traffic is directed. Consequently, this class of algorithms is not an interesting one when dealing with highly dynamic network and disconnections. Dynamicity may turn the environment unstable with some nodes underutilized and others overloaded.