A link contact duration-based routing protocol in delay-tolerant networks

Delay Tolerant Networks (DTNs) provide message delivery services to users via intermittently connected nodes. In DTNs, routing is one of the most challenging issues since end-to-end connectivity between nodes may not be available most of the time. Although many routing protocols for DTNs have been proposed, they do not achieve satisfactory performance, since they exploit only some of the network characteristics. In this paper, we present a new DTN routing protocol, called the Link Contact Duration-based Routing Protocol (LCD). Like existing protocols, LCD uses the disconnect duration of a link between two nodes to find the routing path with the shortest end-to-end delay. In addition, LCD uses the contact duration of a link and the number of buffered messages to deliver as many messages as possible in a short time. Our simulation results show that LCD has better performance than existing DTN routing protocols.     

Socially-aware routing for publish-subscribe in delay-tolerant mobile ad hoc networks

Applications involving the dissemination of information directly relevant to humans (e.g., service advertising, news spreading, environmental alerts) often rely on publish-subscribe, in which the network delivers a published message only to the nodes whose subscribed interests match it. In principle, publish- subscribe is particularly useful in mobile environments, since it minimizes the coupling among communication parties. However, to the best of our knowledge, none of the (few) works that tackled publish-subscribe in mobile environments has yet addressed intermittently-connected human networks. Socially-related people tend to be co-located quite regularly. This characteristic can be exploited to drive forwarding decisions in the interest-based routing layer supporting the publish-subscribe network, yielding not only improved performance but also the ability to overcome high rates of mobility and long-lasting disconnections. In this paper we propose SocialCast, a routing framework for publish-subscribe that exploits predictions based on metrics of social interaction (e.g., patterns of movements among communities) to identify the best information carriers. We highlight the principles underlying our protocol, illustrate its operation, and evaluate its performance using a mobility model based on a social network validated with real human mobility traces. The evaluation shows that prediction of colocation and node mobility allow for maintaining a very high and steady event delivery with low overhead and latency, despite the variation in density, number of replicas per message or speed.     

A simple model of contact patterns in delay-tolerant networks

Delay-tolerant networks, consisting of a number of intermittently connected wireless devices, are emerging as a promising application field, able to complement in some situations infrastructure-based service delivery. In this work, we propose a marked point process model for characterizing the pattern of contacts among nodes in such systems. The model can be used for deriving analytical results on various performance indexes. Validation of the model is performed through comparison with experimental traces obtained from real-world DTN deployments.     

Optimal base station selection for anycast routing in wireless sensor networks

Energy constraints have a significant impact on the design and operation of wireless sensor networks. This paper investigates the base station (BS) selection (or anycast) problem in wireless sensor networks. A wireless sensor network having multiple BSs (data sink nodes) is considered. Each source node must send all its locally generated data to only one of the BSs. To maximize network lifetime, it is essential to optimally match each source node to a particular BS and find an optimal routing solution. A polynomial time heuristic is proposed for optimal BS selection and anycast via a sequential fixing procedure. Through extensive simulation results, it is shown that this algorithm has excellent performance behavior and provides a near-optimal solution.     

Opportunistic media access control and routing for delay-tolerant mobile ad hoc networks

In delay-tolerant mobile ad hoc networks, motion of network nodes, network sparsity and sporadic density can cause a lack of guaranteed connectivity. These networks experience significant link delay and their routing protocols must take a store-and-forward approach. In this paper, an opportunistic routing protocol is proposed, along with its compatible media access control, for non-real-time services in delay-tolerant networks. The scheme is mobility-aware such that each network node needs to know its own position and velocity. The media access control employs a four-fold handshake procedure to probe the wireless channel and cooperatively prioritize candidate nodes for packet replication. It exploits the broadcast characteristic of the wireless medium to utilize long-range but unreliable links. The routing process seizes opportunities of node contacts for data delivery. It takes a multiple-copy approach that is adaptive with node movements. Numerical results in mobile ad hoc networks and vehicular ad hoc networks show superior performance of the proposed protocol compared with other routing protocols. The mobility-aware media access control and routing scheme exhibits relatively small packet delivery delay and requires a modest amount of total packet replications/transmissions.     

Actor-oriented directional anycast routing in wireless sensor and actor networks with smart antennas

Current routing protocols in wireless sensor and actor networks (WSANs) shows a lack of unification for different traffic patterns because the communication for sensor to actor and that for actor to actor are designed separately. Such a design poses a challenge for interoperability between sensors and actors. With the presence of rich-resource actor nodes, we argue that to improve network lifetime, the problem transforms from reducing overall network energy consumption to reducing energy consumption of constrained sensor nodes. To reduce energy consumption of sensor nodes, especially in challenging environments with coverage holes/obstacles, we propose that actor nodes should share forwarding tasks with sensor nodes. To enable such a feature, efficient interoperability between sensors and actors is required, and thus a unified routing protocol for both sensors and actors is needed. This paper explores capabilities of directional transmission with smart antennas and rich-resource actors to design a novel unified actor-oriented directional anycast routing protocol (ADA) which supports arbitrary traffic in WSANs. The proposed routing protocol exploits actors as main routing anchors as much as possible because they have better energy and computing power compared to constraint sensor nodes. In addition, a directional anycast routing approach is also proposed to further reduce total delay and energy consumption of overall network. Through extensive experiments, we show that ADA outperforms state-of-the-art protocols in terms of packet delivery latency, network lifetime, and packet reliability. In addition, by offer fault tolerant features, ADA also performs well in challenging environments where coverage holes and obstacles are of concerns.     

QoS routing for anycast communications: motivation and anarchitecture for DiffServ networks

Much research in QoS routing has focused on the unicast communication paradigm. However, another communication paradigm - anycasting - has grown in importance. In the anycast paradigm, one endpoint is specified and the other is selected from a set of "equivalent" endpoints. An anycast service in a QoS-based network requires selection of both an endpoint and a path that satisfies a QoS constraint. This article provides background material on anycasting in both best-effort networks and QoS-based networks. We then focus on the differentiated services QoS model, and present the design of a QoS-based anycasting architecture consistent with that model. Via simulations, we explore the design options implied by the architecture, including signaling protocols, server selection/sorting algorithms, and resource reservation granularity. We conclude by highlighting open problems in the emerging area of QoS-based anycasting     

An energy-aware deadline-constrained message delivery in delay-tolerant networks

In order to understand the message dissemination performance in delay-tolerant networks, much analysis work has been proposed in literature. However, existing work shares a common simplification that the pairwise inter-meeting time between any two mobile nodes is exponentially distributed. Not mention the fact that such assumption is only an approximation, it cannot be applied by network planners to directly control the mobile nodes for any network optimization, e.g., energy efficiency. It is quite significant to study the relationship between the network performance with the parameters that can be adjusted directly to tackle the limitations of current exponential distribution assumption based analysis. Therefore, in this paper, we are motivated to jointly consider the transmission range and messages residence time to stochastically analyze deadline-constrained message delivery ratio utilizing a controlled epidemic routing. The message propagation is considered as an age-structure process and described by a susceptible–infectious–recovered model, which is then analyzed using delay differential equations. Since both the transmission range and the message residence time are related to the mobile nodes’ energy consumption, we further apply our analysis framework to investigate the tradeoff between the energy consumption and the achievable message delivery ratio. The correctness and accuracy of our analysis are validated by extensive simulations.     

A survey of anycast in IPv6 networks

Anycast is a new "one-to-one-of-many" communication method in IPv6 networks. With this technology, the problem of finding the best server to respond to a request becomes a virtual noop. Hindered by unresolved issues and the slow deployment of IPv6, network-layer anycast is still not a reality. However, an increase in interest and research surrounding anycast recently warrants a look at the state and direction of the ideas in this area. This article describes some of the major problems with network-layer anycast and their possible solutions, as well as some optimizations and applications that have been developed recently.     

Node localization using mobile robots in delay-tolerant sensor networks

We present a novel scheme for node localization in a delay-tolerant sensor network (DTN). In a DTN, sensor devices are often organized in network clusters that may be mutually disconnected. Some mobile robots may be used to collect data from the network clusters. The key idea in our scheme is to use this robot to perform location estimation for the sensor nodes it passes based on the signal strength of the radio messages received from them. Thus, we eliminate the processing constraints of static sensor nodes and the need for static reference beacons. Our mathematical contribution is the use of a robust extended Kalman filter (REKF)-based state estimator to solve the localization. Compared to the standard extended Kalman filter, REKF is computationally efficient and also more robust. Finally, we have implemented our localization scheme on a hybrid sensor network test bed and show that it can achieve node localization accuracy within 1 m in a large indoor setting.     

基于智能天线的定向传播路由协议在WSAN中的应用

在无线传感器及执行器网络(WSAN)中,节点的协作需要通过路由协议进行大量的信息转发。传统使用全方向天线的节点存在能耗高、传输延迟高、数据包传递率低的问题。文中基于智能天线,将定向传播路由协议(ADA)应用于WSAN网络中,通过定向的转发信息减小节点能耗,降低传输延迟,提高数据包传递率。最后,通过Matlab对ADA协议和其他使用全方向天线的节点通信协议的性能进行仿真对比。实验结果表明,在节点能耗、数据包传送延迟和数据包传递率方面,基于智能天线的ADA协议优于其他使用全方向天线的节点通信协议。     

Eco-sustainable routing in optical networks

It is quite easy to foresee that in the next years, the future generation ultra-high speed network infrastructures and equipments will be no longer constrained only by their pure transport capacity, but also by their energy consumption costs and environmental effects. In particular, large network infrastructures are now widely recognized to play a fundamental role in the emission of greenhouse gases in the atmosphere, significantly affecting the environmental sustainability of new evolutions in network architectures as well as technological developments in communication devices. In this paper, a novel eco-sustainable routing and wavelength assignment algorithm, based on shortest path routing with an adaptive link weighting function relying on an extension of the OSPF-TE protocol to convey carbon footprint information, has been proposed to decrease the network ecological impact while balancing the traffic load and maintaining acceptable connection-blocking rate. The trade-off between load balancing and carbon footprint is also analyzed to evaluate the effectiveness of the proposed strategy within the context of a real world network.     

Dynamic routing in multiparented networks

The authors investigate some of the consequences for dynamic routing schemes of dual- and multiparented networks, in which a call can enter (or leave) the network at two or more points. In particular, they compare bounds on the performance of optimal dynamic routing strategies which respectively ignore and utilize the multiparented structure, and show that simple schemes, easily implemented and analyzed, are able to achieve most of the additional advantages allowed to dynamic routing schemes by multiparenting. The robust behavior of these schemes under traffic mismatches as well as multiple link or node failure events is illustrated     

Deflection routing in hypercube networks

An approximate analysis of the transient and steady state behavior of deflection routing in hypercube networks is presented, under a uniform traffic model. In deflection routing congestion causes packets admitted to the network to be temporarily misrouted rather than buffered or dropped. The approximations show that deflection routing performs remarkably well in hypercube networks, for small as well as large networks and for the whole range from light to heavy load. Simulations suggest that the approximations are quite accurate     

Non-Euclidian geographic routing in wireless networks

Greedy geographic routing is attractive for large multi-hop wireless networks because of its simple and distributed operation. However, it may easily result in dead ends or hotspots when routing in a network with obstacles (regions without sufficient connectivity to forward messages). In this paper, we propose a distributed routing algorithm that combines greedy geographic routing with two non-Euclidian distance metrics, chosen so as to provide load balanced routing around obstacles and hotspots. The first metric, Local Shortest Path, is used to achieve high probability of progress, while the second metric, Weighted Distance Gain, is used to select a desirable node among those that provide progress. The proposed Load Balanced Local Shortest Path (LBLSP) routing algorithm provides loop freedom, guarantees delivery when a path exists, is able to efficiently route around obstacles, and provides good load balancing.     

Diverse routing in optical mesh networks

We study the diverse routing problem in optical mesh networks. We use a general framework based on shared risk link groups to model the problem. We prove that the diverse routing problem is indeed NP-complete, a result that has been conjectured by several researchers previously. In fact, we show that even the fiber-span-disjoint paths problem, a special case of the diverse routing problem, is also NP-complete. We then develop an integer linear programming formulation and show through numerical results that it is a very viable method to solve the diverse routing problem for most optical networks found in many applications which typically have no more than a few hundred nodes and fiber spans.     

Position-based routing in ad hoc networks

The availability of small, inexpensive low-power GPS receivers and techniques for finding relative coordinates based on signal strengths, and the need for the design of power-efficient and scalable networks provided justification for applying position-based routing methods in ad hoc networks. A number of such algorithms were developed previously. This tutorial will concentrate on schemes that are loop-free, localized, and follow a single-path strategy, which are desirable characteristics for scalable routing protocols. Routing protocols have two modes: greedy mode (when the forwarding node is able to advance the message toward the destination) and recovery mode (applied until return to greedy mode is possible). We discuss them separately. Methods also differ in metrics used (hop count, power, cost, congestion, etc.), and in past traffic memorization at nodes (memoryless or memorizing past traffic). Salient properties to be emphasized in this review are guaranteed delivery, scalability, and robustness     

BGP routing policies in ISP networks

The Internet has quickly evolved into a vast global network owned and operated by thousands of different administrative entities. During this time, it became apparent that vanilla shortest path routing would be insufficient to handle the myriad operational, economic, and political factors involved in routing. ISPs began to modify routing configurations to support routing policies - goals held by the router's owner that controlled which routes were chosen and which routes were propagated to neighbors. BGP, originally a simple path vector protocol, was incrementally modified over time with a number of mechanisms to support policies, adding substantially to the complexity. Much of the mystery in BGP comes not only from the protocol complexity, but also from a lack of understanding of the underlying policies and the problems ISPs face that are addressed by these policies. In this article we shed light on goals operators have and their resulting routing policies, why BGP evolved the way it did, and how common policies are implemented using BGP. We also discuss recent and current work in the field that aims to address problems that arise in applying and supporting routing policies.