Routing algorithms 4G Networks

Routing algorithms are mechanisms to build paths and forwarding messages by selecting one or more intermediary nodes between source and destination of data messages. At the early days of the Internet, theses algorithms were designed to often lead with a single routing metric: the number of hops between routers. This was primarily due to the homogenous nature of the early IP backbone of the ARPANET. A general rule of thumb was adopted: the fewer hops a packet goes through, the less time it stays in the network and the fewer resources it uses. With time, the Internet evolved to a heterogeneous melting pot where such simple hop routing could no longer be sufficient. Let us consider that a network, expressed by N, is constituted by a set of heterogeneous routers (n nodes), then N = {n_1′ n_2′…n_n-1, n_n}, where each node n_i can have a distinct total network capacity c_i and a set of known routes {r_1′ r_2′…r_n-1, r_n} that consumes the node's resources. Given that each router can have different capacities and routes known to it, its available capacity to forward messages can be represented by formula (1). Consequently, the network is constituted by a set of available capacities of nodes X= {x_1′ x_2′… x_n-1′x_n }, where the network balance can be measured by the average and variance according to formulas (2) and (3) respectively.

However, performance measurements itself generate overhead that should be known and controlled. Node and network measurement, as well as, the routing algorithms also consume resources. Overhead control may be subject to what is being evaluated, the operating capacities of each node, its dynamicity, mobility, constraints on the resources and the underlying network switching, transmission capabilities among other factors. As a result, several routing algorithms have emerged, where each one is better when executed in specific environment(s) according to some pre-established. On the other hand, there are some common characteristics among them, allowing their grouping and classification. The traditional classification of routing algorithms looks for similarity in terms of three routing aspects: the process of route selection, whether it concerns itself or not with network balancing and process of route building, when routes are announced, including also what is announced and to whom.