POLICIES FOR UNTRADITIONAL ROUTING

The untraditional routing algorithms, deal with different quality metrics associated with nodes, location or other information used to choose a suitable relay node. On the other hand, most traditional routing policies deal with only address and interface metrics, where the objective is the management of network traffic in order to decrease its latency, cost, congestion and other metrics. For example, policies for BGP, the current inter-domain routing protocol in the Internet, may be used to update routing tables and consequently to control the traffic forwarding, taking into account path lengths, local preference values, traffic origin among others factors. In terms of software, the IP Filter, iproute2 and net filter are utilities commonly used to create and apply network policies in order to control the routing in local area networks.

However, these approaches are based on the origin-destination pair of IP addresses and interfaces and are not suitable for 4G networks where routing involves often multi-homed end-hosts, intermittent connection, unpredicted mobility and other dynamic characteristics. We need new policies and mechanisms to deal with buffer, message replication and scheduling schemes.

In untraditional routing algorithms, information forwarding can be based on replication (usually broadcast) or on the basis of the pair: source and destination nodes. When using replication, one needs to evaluate and establish the necessary number of replicas according to the underlying environment being used (network size, mobility model, etc.). This is important to avoid network congestion and unnecessary overhead and resource usage. Note that a replication level or value must be carefully set as a small number of replicas may very well become insufficient for the dissemination of information and discovering all nodes and paths. Changes to the number of neighbors over a short period of time indicate a high mobility scenario and consequent frequent topology updates including the network size. This information is a very determinant factor in setting the replication policy and its parameters.

One may choose to apply a policy over the forwarding mechanism based on source and destination information, whereby a node is not required to send all messages. Forwarding may be subject to priority in order to give preferential treatment to some messages for example or offer differentiated traffic. Work in (Lindgren & Phanse, 2006) evaluated four such strategies: GRTR, GR-TRSort, GRTRMax and COIN. GRTR defines a mechanism that allows forwarding to a neighbor if the encountered node has higher delivery predictability to the message destination. When a node A uses GRTR Sort with its neighboring node B, node A subtracts both delivery predictability values for this message destination and then forwards the message for node B using the highest subtraction result it could find. The GRTR Max strategy is also a little similar to GRTR and the difference between these lies in the ordering executed by GRTRMax which is before comparing the delivery predictability. The last policy example is given by COIN which generates a random value for each message. Depending on whether this is higher than 0.5, then the node forwards the message which is similar to tossing a coin and taking a decision according to the outcome.

Independently of whether the message forwarding policy is based on broadcast, replication use, or according to source and destination, the buffer (where messages are stored before being forwarded) is obviously not an infinite resource. Therefore, one needs to have one or more policies in place to determine what to do with the messages. Common per hop behavior or queue management techniques such as FIFO (First In First Out), MOFO (Most Forwarded first) – messages, MOPR (Most favorably forwarded first), SHLI (Shortest Life Time First) or LEPR (Least Probable First) may apply.

Policies may also determine for how long a message could be stored. For example, the Data Mule project considers that a mobile node must store information until finding or coming into contact with a destination (in this case, a base station within a sensor network). Moreover, Data Mule chooses the next hop according to the mobile's behavior, all the way from the fixed nodes, by forwarding the data to intermediary mobile nodes that collect and store the information until the base station is reached.

Another routing work involving policies. In this social overlay shaped by groups, a node needs to decide which query could be dropped, when the buffer is full or simply choose randomly queries to swap. However the authors suggest that the nodes should firstly exchange meta-information, before deleting and adding queries (buffer management). Although it uses a simple decision mechanism, it follows the policy approach to choose what queries must be dropped from the buffer and exchanged with its neighbors. Instead of using such a simple policy model, it could adopt a social policy that gives higher priority to messages forwarded from friends or partners over strangers or unknown senders.

In summary, this section presented how important it is to work towards reducing costs and the requirement for policy changes according to behavior modification in order to provide more flexibility for routing mechanisms. Moreover, it has shown that policies may be applied to control several device features (i.e. buffer, message replication and message scheduling schemes) to determine, configure and improve 4G routing.

SOCIAL OVERLAY NETWORKS

The overlay network approach allows the creation of several virtual networks over physical ones. Here one hop in a virtual network may correspond to several hops from one or more physical networks (underlays). In turn, a virtual network may even be built over other virtual networks. However the overlay routing does not have direct control over how the underlay forwarding of packets is actually performed. As a result one may not classify solutions such as Buble and SimBet as mechanisms to build overlay networks, since their nodes have routing control over the physical layer. Other routing algorithms found in widely spread Peer-to-Peer (P2P) social networks such as Gnutella, Chord and Tapestry are examples of peer-to-peer protocols that can be used to create overlay networks. In order to improve these overlay networks, and other works applied social mechanisms and consequently we named these proposals as social overlay networks. They deal with security and optimization using social ideas extracted from the underlays.

DSL (Davis Social Links) is an example of a proposal that applied social approaches to deal with security. It has a social overlay mechanism that creates trust relationships of social networks based on the small-world phenomenon in order to control, trace and separate address and identity information. The idea is to allow communication between nodes with a direct link or a social path linking them. Messages in the DSL social network contain a set of keywords describing node properties. The social path is created by the exchange of keywords between nodes connected by direct links. The nodes can accept or drop messages from some social path or modify these along another one. There is consequently a recipient controllability being exerted. For example, nodes A and B have "red" and "yellow" as part of their keyword sets respectively. These strings are cryptographically exchanged prior to the exchange of data. A Node can propagate the keywords in order to increase routability.

Work is a bit similar to social routing while not applied at the physical layer however. SOLAR, seen earlier, imports a user's profile information to forward data. In SOLAR, the profile is defined by a node itself and describes node mobility and its likely locations. Differently from SOLAR, acts at the application layer where the profile manipulates the dissemination and routing of messages. An even greater difference is to do with the fact that the profile in  may be updated and created by friends and acquaintances of a given node instead of being the sole responsibility of the node as in SOLAR. When a node creates a link, the user must attribute one or more keywords to describe the new friend. This one, the friend, needs then to agree with such description to allow for the effective link creation. As described by an application in, it is important to find a best person to answer some questions about some given keywords. This idea for creating profiles by friends could be implemented at the network level in terms of performance and made available to view by other nodes. Consequently, a profile that describes the options and possibilities for other nodes could be an interesting mechanism to help the node decide if another encountered node is a good relay to forward its messages.

PeopleNet is another social mechanism that propagates information using overlay networks. It has only three types of messages: request propagation, request and response. The request and response messages are always forwarded over long range connectivity such as over a cellular infrastructure; the propagation messages are always broadcasted with shorter range connections until some node matches the request propagation with some response. Whenever a propagation message matching occurs, the user who placed the request message receives the response message via long range connectivity. Moreover, the users can pre-determine the type of queries to handle in some specific geographic context, called Bazaar. So, any person close or distant to a Bazaar can send requests through the cellular infrastructureto other users in a specific geographic (Bazaar). Information is spread around to users in a specific geographic location, but it does not benefit from the number of meetings among nodes in a specific geographic area as in SOLAR.

PeopleNet differs from the proposal defined in as it does not concern itself with any mobility pattern, similarity of mobility and the ability of nodes to learn about their own mobility. PeopleNet relies on the innovative idea of using the widely deployed cellular infrastructure and Bluetooth devices to propagate information search. A second peculiar contribution involves the overlay routing according to the meta-information (i.e. Bazzar and message type) to choose what connection must be used to forward the messages. So, one could extract the importance from high level information that could be used in routing.

SPROUT presents a social mechanism to route messages in overlay networks such as Distributed Hash Tables (DHT). It is based on the use of the knowledge of a trust relationship among social nodes to choose what node must receive a message and to associate message priority. SPROUT presents possible trust function according to the number of hops in a social overlay (the distance d_ij between social nodes n₁ and n_j). The relation in (46) is one of its trust functions used to choose the next hop, where f is a static probability for two nodes to be trusted friends. The reader may note that the probability of two nodes being friends is limited by the value r. For example, if f = 0.95 and r = 0.6, then the trust function assumes that the friends with high proximity of node n i are best friends (reflecting a high trust relationship) and consequently very likely to correctly route a message and when d_ij >8 the trust will be maintained as 0.6. The objective of this work is to reduce the number of several network attack types that may drop the packets or forward the data to any different node other than the correct destination. For instance, in a DHT structure, a malicious node may exchange messages in order to disseminate unwanted information. SPROUT locates the trustiest friend of a given node that has a closer identifier, but not greater than, a key value until finding the destination node for that given key. Should this fail, then the source node executes the traditional DHT process. Although this work has been implemented in overlays, it could also be applied at the network layer. A node should evaluate the trust relationship of its neighbor instead of choosing the shortest path, which may be an unsafe path in terms of optimization and integrity. Further, trust identification remains a hard undertaking.

On the other hand, the trust relationship is not immune to attacks completely. Malicious nodes may convince a small number of honest ones trough the creation of several and false identities to increase their influence and credibility in the network. Looking at this problem SybilGuard and Syb-ilLimit map users and nodes, separating the network in two groups: a honest region with nodes with only one identity and a Sybil region populated by malicious nodes with more than a single identity. They also established that the number of links between these regions (called attack edges) is independent of the number of malicious identities. Moreover, if a trust route contains only nodes into the honest region then all the routes that cross the same node or edge will converge. Therefore, one may observe that there are several works applying social approaches in order to improve information propagation in overlay networks, security and optimization.

Propagation in social overlay and underlay is very similar, but there is a little difference. Both the optimization and security are interlaced in the context of social networks. This may be the case when messages are dropped or wrongly forwarded. A number of security enhancements have been suggested in to improve underlay security. User's devices are used to route data in DTN scenarios, increasing the likelihood to disseminate worms and viruses, as their users are often inexperienced with regard to such security threats. Moreover, networks with high-degree nodes tend to connect to other high-degree node networks (the famous often move in the same circles) and are therefore more likely to be subject to epidemics. Indeed a single infected high degree node will quickly infect other high-degree ones. On the other hand, networks where high-degree nodes tend to connect to low-degree nodes show the opposite behavior; a single infected high-degree node will not spread an epidemic very far.

Challenges for Future 4G Networks

We have established that 4G convergence is expected to deal with several environments, including short range networks, which, in general, involve devices with capabilities subject to CPU, memory and disk limitations. Thus, with regard to routing, the next generation network should consider strategies that conserve battery power not only from a device survival point of view but more importantly in an attempt to use greener environment friendly solutions. These are also known as power-aware routing. For example, these devices should avoid the use of highly demanding table updates.

Routing mechanisms using location information have been proposed in order to improve energy consumption and data delivery. Note that the excessive use of location information from devices such as GPS for routing decisions can lead to a considerable increase in energy consumption when compared to location agnostic solutions. Moreover, vehicular networks are also expected to maintain location servers for vehicles to help in information routing.

In existing 2G and 3G networks, there is the horizontal cell connectivity handoff, one that involves cell changes by a terminal within the same type of network. 4G introduces also the vertical handoff. Here devices are expected to change networks they attach to. Hence, the challenge is to design routing protocols that are capable of handling vertical handoffs between pairs of different types of networks, while maintaining QoS requirements and optimizing common radio resources availability.

Under 4G networks, security is also seen as a paramount concern. Traditional attacks on existing IP networks will certainly migrate to 4G networks encouraged by both the heterogeneity and the open air interfaces of such networks. Routing information may be targeted in such attacks on system security, there is a need to design secure routing approaches to ensure the integrity of routing in 4G systems. This is not however the object of this chapter.

In summary, among the many routing-related challenges this work has identified, we mentioned QoS, security, energy and location information. The following section will present the details of new routing algorithms, with new network metrics and routing mechanisms, which motivate the extension of traditional classification to include epidemic, biological and social class of routing ideas, one expects to see in 4G networks.

WHY DO WE NEED NEW ROUTING MECHANISMS?

If anything is certain, the fact that 4G system will be completely IP-based is one. Although homogeneous at the higher levels of the architecture. 4G most likely will integrate several nestled networks with heterogeneous offered services, features, applications and service providers represented by mobile operators, companies or even individual users and content providers. The role of 4G systems in the wireless arena will be parallel to that of the Internet for fixed networks. It will be a common place to find the same service being offered by different sub-networks though maybe under varying security, bandwidth, delay, availability and pricing features.

While the prices for multi-radio and multi-interface devices are continuing to drop, new network topologies are also emerging including ad-hoc, mesh, hybrid and multi-dimensional ones. The latter are networks where a node may take part into different technology dependent networks at the same time, leading hence to a multi-layer view of the new topology. For this reason, new routing algorithms are designed to lead with new topologies and network challenges.

New Network Topologies

One expects that existing traditional network topologies such as those based on fixed infrastructure, ad hoc networks and others, to blend into 4G networks in a highly dynamic cooperating environment. 4G is also embracing highly dynamic networks such as delay tolerant or disruptive networks in addition to opportunistic communications which may be exploited in disaster recovery scenarios and military applications. The emergence of vehicular networks also presents new challenges to the design of 4G edge capacity and mobility support. VANs are expected to have bit rates close to those of fixed networks. New VAN topologies depict dynamic multi-hop short range vehicle-to-vehicle and vehicle-with-infrastructure communications.

Similarly to fixed networks, overlay topologies can run over 4G to offer virtual high level structures among individuals across 4G networks. Examples of such overlays are emerging new social networks, where topology information is primordial to improving data forwarding, privacy and security as seen in (Bernardos, Casar & Tarrio, 2006). Unlike current networks, a 4G one should open up further possibilities for individuals and groups to work, discuss and play together often by self-structuring driven by common interests, needs and incentives, instead of mere connectivity. The success of future 4G systems may depend to a great extent on their capacity to accommodate these new data services using social, biological and other nature inspired.