Proactive or Reactive Routing

Proactive and Reactive are ways to classify a routing mechanism in terms of when an algorithm announces the routing route selection information. The routing mechanism mayanticipate having this information or select a route on-demand due to the high dynamicity and unpredictability of a network environment.

The proactive routing announces periodically network information generating a predictability amount of messages. In a worst case, the time to select the correct path t_s = t_period(period used to update paths). For example, formula (8) presents a possible generic function that may be adopted to calculate the number of messages generated by each node k when using proactive algorithms, where T is a set of announcement periods t independently of node or network faults. Hence, if there is large interval between path announcements, the number of messages will be small, nonetheless leading to a routing scenario practically lacking reactivity to possible network failures. Examples of pro-active routing include: DSDV (Destination-Sequenced Distance Vector) and WRP (Wireless Routing Protocol).

On the other hand, the algorithms classified as reactive do not issue their route announcement messages following any periodicity. They rely on observed failures or user demand to update routes. Consequently the number of messages announced could be much lower than that of proactive algorithms. Given that they do not need to wait a whole period to update their routing information, they may have offer better performance in unpredicted environment. They may also however suffer from low select the correct path may be given as the sum of t_s = t_fault (time needed to identify a failure)+t_request(to search for a correct path) + t_response (someone response the node with the correct path). For example, formula (9) presents a possible generic function to calculate the number of messages generated by each node k using a reactive algorithm, where F is a set of independent failures. So, one cannot know the number of message without knowing the number of failures. When some fault occurs, node k is notified, next it announces a request to find the route and others nodes announce or send back their responses. Examples that fall into this routing category are AODV (Ad-Hoc On-Demand Distance Vector), DSR (Dynamic Source Routing) and LMR (Lightweight Mobile Routing).

Distance Vector or Link-State Routing

Many routing strategies rely on mechanisms for sharing and announcing their routes among routing nodes. Traditional routing algorithms may be classified as Distance Vector and Link State under this angle.

Distance Vector algorithms are characterized by the fact that each network node announces the content of its routing table, known as a vector in this context, to "only" its neighbors. Although such limited scope announcement saves networking resources, it is also the root for some known route convergence latency related problems suffered by large networks. Each vector entry contains local information on some node k and how this may be reached in terms of number of hops and delay for example. Each neighbor for node k receives its advertisement (routing vector or information from node k) to build a routing database with size m.m_etric′, where m is the number of routers known by node k and m_etricis a number of metrics announced about each node. So, the traffic size generated by each node is given by formula (6) in order for a network node to get to know the network's topology. Once, a node acquires this knowledge through these advertisements, each node locally calculates the importance of each other node in the network according to its own vector and those received vector from the neighbors. Hence there is a combination of both local and external information to perform shortest paths selection. The result of such regular calculus updates the routing table based on algorithms such as Bellman-Ford and Ford-Fulkerson.

Given that the advertisement is relayed from neighbor to neighbor until all network nodes acquire network topology and path information, the protocols classified as Distance Vector suffer from slow convergence. The following protocols are example of Distance Vector: the Routing Internet Protocol (RIP) executed in intra-domain, Border Gateway Protocol (BGP) executed in inter-domain, DVMRP (Distance Vector Multicast Routing Protocol) for multicast applications, AODV (Ad-hoc On-demand Distance Vector) for mobile ad hoc networks (MANETs) and DSDV (Destination-Sequence Distance-Vector) also for MANETs.

link-state algorithms are different from distance vector ones in terms of the scope of their announcements. Unlike the former one where each node notifies the neighbors only about its vector, link-state routing floods such announcement to all the network nodes. Further, link-state updates are conveyed over small messages to all nodes. Each message contains the link-state of its neighbor's node such as occupied bandwidth, throughput, delay and so forth. A network node then builds a routing database with size m.n.m_etric where m is the number of neighbor nodes, n is the number of routers in the network and m _etric the number of metrics announced for each node. As a result, the traffic size generated by each node is given by formula (7) in order for network node to build its database and get to know the current topology. With this knowledge at hand, each node locally then calculates the importance of each neighbor to forward messages over the shortest paths determined for each destination. This may be achieved usually using Dijkstra's algorithm, although there are others as described in. The most common and widespread link state protocols used are the OSPF (Open Shortest Path Frist) and IS-IS. Similarly, Multicast OSPF (MOSPF)  has been developed to lead with multicast transmission. Other link state protocols include SPF 

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.

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.