Search

Network-on-Chip (NoC) has been made the communication infrastructure for many-core architecture. NoC are subject to congestion, which is claimed to be avoided by many researchers. However, there is no completely understanding of congestion in literature, which hinders its solution. Toward this direction, we firstly carry out study on congestion in this paper. We find that congestion usually occurs at a portion of nodes in a local network region. Moreover, local congestion will significantly decrease system performance and mostly impact some particular communication pairs. Then we attempt to solve local congestion by addressing different local region size, based on Divide-Conquer approach and routing pressure. It avoids congestion in every local region by keeping routing pressure of every local region minimum. Using different local region size will create different routings. Our study shows that the local region size is closely related with the routing performance. When local region size is 5 × 5 the optimal routing performance of large size network could be achieved. [ABSTRACT FROM AUTHOR]

Lifetime optimization and security are two conflicting design issues for multi-hop wireless sensor networks (WSNs) with non-replenishable energy resources. In this paper, we first propose a novel secure and efficient Cost-Aware SEcure Routing (CASER) protocol to address these two conflicting issues through two adjustable parameters: energy balance control (EBC) and probabilistic-based random walking. We then discover that the energy consumption is severely disproportional to the uniform energy deployment for the given network topology, which greatly reduces the lifetime of the sensor networks. To solve this problem, we propose an efficient non-uniform energy deployment strategy to optimize the lifetime and message delivery ratio under the same energy resource and security requirement. We also provide a quantitative security analysis on the proposed routing protocol. Our theoretical analysis and OPNET simulation results demonstrate that the proposed CASER protocol can provide an excellent tradeoff between routing efficiency and energy balance, and can significantly extend the lifetime of the sensor networks in all scenarios. For the non-uniform energy deployment, our analysis shows that we can increase the lifetime and the total number of messages that can be delivered by more than four times under the same assumption. We also demonstrate that the proposed CASER protocol can achieve a high message delivery ratio while preventing routing traceback attacks. [ABSTRACT FROM AUTHOR]

In this paper, we propose E-STAR for establishing stable and reliable routes in heterogeneous multihop wireless networks. E-STAR combines payment and trust systems with a trust-based and energy-aware routing protocol. The payment system rewards the nodes that relay others’ packets and charges those that send packets. The trust system evaluates the nodes’ competence and reliability in relaying packets in terms of multi-dimensional trust values. The trust values are attached to the nodes’ public-key certificates to be used in making routing decisions. We develop two routing protocols to direct traffic through those highly-trusted nodes having sufficient energy to minimize the probability of breaking the route. By this way, E-STAR can stimulate the nodes not only to relay packets, but also to maintain route stability and report correct battery energy capability. This is because any loss of trust will result in loss of future earnings. Moreover, for the efficient implementation of the trust system, the trust values are computed by processing the payment receipts. Analytical results demonstrate that E-STAR can secure the payment and trust calculation without false accusations. Simulation results demonstrate that our routing protocols can improve the packet delivery ratio and route stability. [ABSTRACT FROM AUTHOR]

Existing social-aware routing protocols for pocket switched networks make use of the information about the social structure of the network deduced by state information of nodes (e.g., history of past encounters) to optimize routing. Although these approaches are shown to have superior performance to social-oblivious, stateless routing protocols (BinarySW, Epidemic), the improvement comes at the cost of considerable storage overhead required on the nodes. In this paper we present SANE, the first routing mechanism that combines the advantages of both social-aware and stateless approaches. SANE is based on the observation—that we validate on a real-world trace—that individuals with similar interests tend to meet more often. In SANE, individuals (network members) are characterized by their interest profile, a compact representation of their interests. By implementing a simple routing rule based on interest profile similarity, SANE is free of network state information, thus overcoming the storage capacity problem with existing social-aware approaches. Through thorough experiments, we show the superiority of SANE over existing approaches, both stateful, social-aware and stateless, social-oblivious. We discuss the statelessness of our approach in the supplementary file, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TPDS.2014.2307857, of this manuscript. Our interest-based approach easily enables innovative networking services, such as interest-casting. An interest-casting protocol is also introduced in this paper, and evaluated through experiments based on both real-world and synthetic mobility traces. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel semi-directional flooding (SDF) algorithm for on-demand routing in IEEE 802.15.4-based low-rate wireless mesh networks (LRWMNs). The novelty of our work is that the proposed routing algorithm enables route discovery request (RREQ) packets to be semi-directionally flooded, with respect to a source-destination pair, in a fully distributed manner without either physical or virtual location information. The idea behind this is to exploit the hierarchical addressing structure that allows each router node to compute logical tree distances between source-destination pairs, which approximately mirrors relative hop distance between the pairs, without message exchanges. By exploiting tree distances with a given target address, the SDF algorithm enables RREQ packets to be flooded over a small area, directed towards the destination. We also apply SDF to a lightweight on-demand routing algorithm like AODVjr, and propose two techniques of adaptive timers and route repair that reduces path setup delays and overheads during route rediscovery, respectively. We carry out extensive simulations and quantitatively show that SDF significantly reduces flooding overhead of network-wide flooding (NWF). We compare SDF-based AODVjr with both NWF-based AODVjr and enhanced hierarchical routing protocol (EHRP) for on demand routing and demonstrate that SDF-based AODVjr drastically reduces route discovery overhead by up to about 95 percent while still providing comparable or better performance than NWF-based AODVjr and EHRP. [ABSTRACT FROM AUTHOR]

The ZigBee tree routing is widely used in many resource-limited devices and applications, since it does not require any routing table and route discovery overhead to send a packet to the destination. However, the ZigBee tree routing has the fundamental limitation that a packet follows the tree topology; thus, it cannot provide the optimal routing path. In this paper, we propose the shortcut tree routing (STR) protocol that provides the near optimal routing path as well as maintains the advantages of the ZigBee tree routing such as no route discovery overhead and low memory consumption. The main idea of the shortcut tree routing is to calculate remaining hops from an arbitrary source to the destination using the hierarchical addressing scheme in ZigBee, and each source or intermediate node forwards a packet to the neighbor node with the smallest remaining hops in its neighbor table. The shortcut tree routing is fully distributed and compatible with ZigBee standard in that it only utilizes addressing scheme and neighbor table without any changes of the specification. The mathematical analysis proves that the 1-hop neighbor information improves overall network performances by providing an efficient routing path and distributing the traffic load concentrated on the tree links. In the performance evaluation, we show that the shortcut tree routing achieves the comparable performance to AODV with limited overhead of neighbor table maintenance as well as overwhelms the ZigBee tree routing in all the network conditions such as network density, network configurations, traffic type, and the network traffic. [ABSTRACT FROM AUTHOR]

This paper presents ALBA-R, a protocol for convergecasting in wireless sensor networks. ALBA-R features the cross-layer integration of geographic routing with contention-based MAC for relay selection and load balancing (ALBA), as well as a mechanism to detect and route around connectivity holes (Rainbow). ALBA and Rainbow (ALBA-R) together solve the problem of routing around a dead end without overhead-intensive techniques such as graph planarization and face routing. The protocol is localized and distributed, and adapts efficiently to varying traffic and node deployments. Through extensive ns2-based simulations, we show that ALBA-R significantly outperforms other convergecasting protocols and solutions for dealing with connectivity holes, especially in critical traffic conditions and low-density networks. The performance of ALBA-R is also evaluated through experiments in an outdoor testbed of TinyOS motes. Our results show that ALBA-R is an energy-efficient protocol that achieves remarkable performance in terms of packet delivery ratio and end-to-end latency in different scenarios, thus being suitable for real network deployments. [ABSTRACT FROM AUTHOR]

Malicious and selfish behaviors represent a serious threat against routing in delay/disruption tolerant networks (DTNs). Due to the unique network characteristics, designing a misbehavior detection scheme in DTN is regarded as a great challenge. In this paper, we propose iTrust, a probabilistic misbehavior detection scheme, for secure DTN routing toward efficient trust establishment. The basic idea of iTrust is introducing a periodically available Trusted Authority (TA) to judge the node's behavior based on the collected routing evidences and probabilistically checking. We model iTrust as the inspection game and use game theoretical analysis to demonstrate that, by setting an appropriate investigation probability, TA could ensure the security of DTN routing at a reduced cost. To further improve the efficiency of the proposed scheme, we correlate detection probability with a node's reputation, which allows a dynamic detection probability determined by the trust of the users. The extensive analysis and simulation results demonstrate the effectiveness and efficiency of the proposed scheme. [ABSTRACT FROM AUTHOR]

IP multimedia subsystem (IMS) and IMS-based services are increasingly providing interoperable session control and mobility for next-generation all-IP networks. However, clear design guidelines and techniques for the support of scalable IMS-based deployment, especially for data-intensive services such as mobility management, presence, and instant messaging, are still missing. That could block or at least relevantly slow down IMS acceptance by network operators and application providers. To address these challenges, this paper thoroughly analyzes IMS scalability with special attention to intradomain deployment issues. Then, it proposes a novel solution with three core original contributions toward intradomain scalability: 1) data-centric dissemination of session state with limited overhead; 2) service-aware routing for fast intradomain load balancing; 3) service-aware load monitoring and component de-/activation for long-term intradomain load partitioning at both service and infrastructure levels. The reported experimental results point out that our solution can significantly increase intradomain scalability with very limited costs. [ABSTRACT FROM PUBLISHER]

Delay tolerant networks (DTN) are characterized by a lack of continuous end-to-end connections due to node mobility, constrained power sources, and limited data storage space of some or all of its nodes. To overcome the frequent disconnections, DTN nodes are required to store data packets for long periods of time until they come near other nodes. Moreover, to increase the delivery probability, they spread multiple copies of the same packet on the network so that one of them reaches the destination. Given the limited storage and energy resources of many DTN nodes, there is a tradeoff between maximizing delivery and minimizing storage and energy consumption. In this paper, we study the routing problem in DTN with limited resources. We formulate a mathematical model for optimal routing, assuming the presence of a global observer that can collect information about all the nodes in the network. Next, we propose a new protocol based on social grouping among the nodes to maximize data delivery while minimizing network overhead by efficiently spreading the packet copies in the network. We compare the new protocol with the optimal results and the existing well-known routing protocols using real life simulations. Results show that the proposed protocol achieves higher delivery ratio and less average delay compared to other protocols with significant reduction in network overhead. [ABSTRACT FROM PUBLISHER]

To cope with challenging problems faced by traditional multicast routing protocols, many branching-router (BR)-based multicast routing schemes with desirable features have been proposed. However, the current BR-based methods still lack efficient multicast management and suffer from a long join latency, leading to a disappointing mobility performance. In this paper, we propose a novel BR-based multicast architecture with a corresponding multicast routing protocol supporting multicast receiver mobility. In the proposed multicast architecture, a new management entity called multicast controller (MC) is used to handle most of the multicast management-related tasks, while other routers in the network construct a multicast tree according to the proposed Branching-Router-based Multicast routing protocol with Mobility support (BRMM). Besides, the fast handover of multicast service can be supported by BRMM through the pre-establishment of temporary multicast paths. Through extensive simulation and analysis, we show that BRMM outperforms existing protocols and has many other attractive features. [ABSTRACT FROM AUTHOR]

Social behavior plays a more and more important role in delay tolerant networks (DTNs). In this paper, we present an analytical model for a hypercube-based social feature multipath routing protocol in DTNs. In this routing protocol, we use the internal social features of each node (individual) in the network for routing guidance. This approach is motivated from several real social contact networks, which show that people contact each other more when they have more social features in common. This routing scheme converts a routing problem in a highly mobile and unstructured contact space (M-space) to a static and structured feature space (F-space). The multipath routing process is a hypercube-based feature matching process where the social feature differences are resolved step-by-step. A feature matching shortcut algorithm for fast searching is presented where more than one feature difference is resolved at one time. The multiple paths for the routing process are node-disjoint. We formally analyze the delivery rate and latency by using hypercube-based routing. The solutions for the expected values of latency and delivery rate are given under different path conditions: single-/multipath and feature difference resolutions with/without shortcuts. Extensive simulations on both real and synthetic traces are conducted in comparison to several existing state-of-the-art DTN routing protocols. [ABSTRACT FROM AUTHOR]

We propose a pervasive usage of the sensor network infrastructure as a cyber-physical system for navigating internal users in locations of potential danger. Our proposed application differs from previous work in that they typically treat the sensor network as a media of data acquisition while in our navigation application, in-situ interactions between users and sensors become ubiquitous. In addition, human safety and time factors are critical to the success of our objective. Without any preknowledge of user and sensor locations, the design of an effective and efficient navigation protocol faces nontrivial challenges. We propose to embed a road map system in the sensor network without location information so as to provide users navigating routes with guaranteed safety. We accordingly design efficient road map updating mechanisms to rebuild the road map in the event of changes in dangerous areas. In this navigation system, each user only issues local queries to obtain their navigation route. The system is highly scalable for supporting multiple users simultaneously. We implement a prototype system with 36 TelosB motes to validate the effectiveness of this design. We further conduct comprehensive and large-scale simulations to examine the efficiency and scalability of the proposed approach under various environmental dynamics. [ABSTRACT FROM AUTHOR]

This paper introduces a novel multicopy routing protocol, called Self-Adaptive Utility-based Routing Protocol (SAURP), for Delay Tolerant Networks (DTNs) that are possibly composed of a vast number of devices in miniature such as smart phones of heterogeneous capacities in terms of energy resources and buffer spaces. SAURP is characterized by the ability of identifying potential opportunities for forwarding messages to their destinations via a novel utility function-based mechanism, in which a suite of environment parameters, such as wireless channel condition, nodal buffer occupancy, and encounter statistics, are jointly considered. Thus, SAURP can reroute messages around nodes experiencing high-buffer occupancy, wireless interference, and/or congestion, while taking a considerably small number of transmissions. The developed utility function in SAURP is proved to be able to achieve optimal performance, which is further analyzed via a stochastic modeling approach. Extensive simulations are conducted to verify the developed analytical model and compare the proposed SAURP with a number of recently reported encounter-based routing approaches in terms of delivery ratio, delivery delay, and the number of transmissions required for each message delivery. The simulation results show that SAURP outperforms all the counterpart multicopy encounter-based routing protocols considered in the study. [ABSTRACT FROM AUTHOR]

To efficiently archive and query data in wireless sensor networks (WSNs), distributed storage systems, and multisink schemes have been proposed recently. However, such distributed access cannot be fully supported and exploited by existing routing protocols in a large-scale WSN. In this paper, we will address this challenging issue and propose a distributed geographic $(K)$-anycast routing (GKAR) protocol for WSNs, which can efficiently route data from a source sensor to any $(K)$ destinations (e.g., storage nodes or sinks). To guarantee $(K)$-delivery, an iterative approach is adopted in GKAR where in each round, GKAR will determine not only the next hops at each node, but also a set of potential destinations for every next hop node to reach. Efficient algorithms are designed to determine the selection of the next hops and destination set division at each intermediate node. We analyze the complexity of GKAR in each round and we also theoretically analyze the expected number of rounds required to guarantee $(K)$-delivery. Simulation results demonstrate the superiority of the GKAP scheme in reducing the total duration and the communication overhead for finding $(K)$ destinations, by comparing with the existing schemes, e.g., $(K 1)$-anycast [10]. [ABSTRACT FROM AUTHOR]

Routing in delay tolerant networks is a challenging problem due to the intermittent connectivity between nodes resulting in the frequent absence of end-to-end path for any source-destination pair at any given time. Recently, this problem has attracted a great deal of interest and several approaches have been proposed. Since Mobile Social Networks (MSNs) are increasingly popular type of Delay Tolerant Networks (DTNs), making accurate analysis of social network properties of these networks is essential for designing efficient routing protocols. In this paper, we introduce a new metric that detects the quality of friendships between nodes accurately. Utilizing this metric, we define the community of each node as the set of nodes having close friendship relations with this node either directly or indirectly. We also present Friendship-Based Routing in which periodically differentiated friendship relations are used in forwarding of messages. Extensive simulations on both real and synthetic traces show that the introduced algorithm is more efficient than the existing algorithms. [ABSTRACT FROM PUBLISHER]

The nonexistence of an end-to-end path poses a challenge in adapting traditional routing algorithms to delay-tolerant networks (DTNs). Previous works have covered centralized routing approaches based on deterministic mobility, ferry-based routing with deterministic or semideterministic mobility, flooding-based approaches for networks with general mobility, and probability-based routing for semideterministic mobility models. Unfortunately, none of these methods can guarantee both scalability and delivery. In this paper, we extend the investigation of scalable deterministic routing in DTNs with repetitive mobility based on our previous works. Instead of routing with global contact knowledge, we propose a routing algorithm that routes on contact information compressed by three combined methods. We address the challenge of efficient information aggregation and compression in the time-space domain while maintaining critical information for efficient routing. Then, we extend it to handle a moderate level of uncertainty in contact prediction. Analytical studies and simulation results show that the performance of our proposed routing algorithm, DTN Hierarchical Routing (DHR), is comparable to that of the optimal time-space Dijkstra algorithm in terms of delay and hop count. At the same time, the per-node storage overhead is substantially reduced and becomes scalable. [ABSTRACT FROM AUTHOR]

Due to limitations on transmission power of wireless devices, areas with sparse nodes are decisive to some extreme properties of network topology. In this paper, we assume wireless ad hoc and sensor networks are represented by uniform point processes or Poisson point processes. Asymptotic analyses based on minimum scan statistics are given for some crucial network properties, including coverage of wireless sensor networks, connectivity of wireless ad hoc networks, the largest edge length of geometric structures, and local-minimum-free geographic routing protocols. We derive explicit formulas of minimum scan statistics. By taking the transmission radius as a major parameter, our results are applied to various network problems. This work offers a unified approach to solve various problems and reveals the evolution of network topology. In addition, boundary effects are thoroughly handled. [ABSTRACT FROM AUTHOR]

This article presents an efficient and scalable mechanism to overcome the limitations of collective communication in switched interconnection networks in the presence of faults. Considering that current trends in supercomputing are moving toward massively parallel computers, with many thousands of components, reliability becomes a challenge. In such scenario, fat-tree networks that provide hardware support for collective communication suffer from serious performance degradation due to the presence of, even, a single faulty node. This paper describes a new mechanism to provide high-performance collective communication in such situations. The feasibility of the proposed technique is formally demonstrated. We present the design of a new hardware-based routing algorithm for multicast, that is at the base of our proposal. The proposed mechanism is implemented and experimentally evaluated. Our experimental results show that hardware-based multicast trees provide an efficient and scalable solution for collective communication in fat-tree networks, significantly outperforming traditional solutions. [ABSTRACT FROM AUTHOR]

The topological explorations of on-chip networks are important for efficiently using their enormous wire resources for low- latency and high-throughput communications using a modest silicon budget. In this paper, we propose a novel tree-based interconnection network called Fat H-Tree that meets these requirements. A Fat H-Tree provides a torus structure by combining two folded H-Tree networks and is an attractive alternative to tree-based networks such as the Fat Trees in a micro architecture domain. We introduce its chip layout schemes based on a folding technique for 2D and 3D lCs. Three deadlock-free routing schemes are proposed for Fat H-Tree. We evaluate the performance of Fat H-Tree and other tree-based networks using real application traces. In addition, the network logic area, wire resource, and energy consumption of Fat H-Tree are compared with other topologies, based on a typical implementation of on-chip routers synthesized with a 90-nm standard cell library. The results show that 1) a Fat H-Tree outperforms a Fat Tree with two upward and four downward connections in terms of the throughput and average hop count, 2) a Fat H-Tree requires 19.8 percent-27.8 percent smaller network logic area than the Fat Tree, 3) a Fat H-Tree consumes slightly less energy than the Fat Tree does, and 4) a Fat H-Tree uses slightly more wire resources than the Fat Tree, but the current process technology can provide sufficient wire resources for implementing Fat-H-Tree-based on-chip networks. [ABSTRACT FROM AUTHOR]

Routing is the foremost issue in mobile ad hoc networks (MANETs). To guarantee delivery and improve performance, most position-based routing protocols, e.g., greedy-face-greedy (GFG), forward a message in greedy routing mode until the message is forwarded to a local minimum where greedy forwarding is impossible. They then switch to a less efficient mode known as taco routing, Face routing requires the underlying network to be a planar graph which makes geometric routing only theoretically feasible. To remove this constraint, this paper tackles Ike local minimum problem with two new methods. First, we construct a virtual small-world network by adding virtual long links to the network to reduce the number of local minima. Second, we use the virtual force method to recover from local minima without relying on face routing. Combining these two methods, we propose a purely greedy routing protocol, the small-world iterative navigation greedy (SWING+) routing protocol. Simulations are conducted to evaluate SWING+ against existing geometric routing protocols. Simulation results show that SWING+ guarantees delivery, and that its performance is comparable to that of the state-of-the-an greedy other adaptive face routing (GOAFR+) routing protocol. [ABSTRACT FROM AUTHOR]

Abstract-We study efficient interference-aware joint routing and TDMA link scheduling for a multihop wireless network to maximize its throughput. Efficient link scheduling can greatly reduce the interference effect of close-by transmissions. Unlike the previous studies that often assume a unit disk graph (UDG) model, we assume that different terminals could have different transmission ranges and different interference ranges. In our model, it is also possible that a communication link may not exist due to barriers or is not used by a predetermined routing protocol, while the transmission of a node always result interference to all nonintended receivers within its interference range. Using a mathematical formulation, we develop interference-aware joint routing and synchronized TDMA link schedulings that optimize the networking throughput subject to various constraints. Our linear programming formulation will find a flow routing whose achieved throughput is at least a constant fraction of the optimum, and the achieved fairness is also a constant fraction of the requirement. Then, by assuming known link capacities and link traffic loads, we study link scheduling under the request-to-send and clear-to-send (RTS/CTS) interference model and the protocol interference model (PrIM) with fixed transmission power. For both models, we present both efficient centralized and distributed algorithms that use timeslots within a constant factor of the optimum. We also present efficient distributed algorithms whose performances are still comparable with optimum, but with much less communications. We prove that the timeslots needed by our faster distributed algorithms are only at most O(iniii(logn, Iog ψ)) for RTS/ CTS interference model and PrIM. Our theoretical results are corroborated by extensive simulation studies. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of destination anonymity for applications in mobile ad hoc networks where geographic information is ready for use in both ad hoc routing and Internet services. Geographic forwarding becomes a lightweight routing protocol in favor of the scenarios. Traditionally, the anonymity of an entity of interest can be achieved by hiding it among a group of other entities with similar characteristics, i.e., an anonymity set. In mobile ad hoc networks, generating and maintaining an anonymity set for any ad hoc node is challenging because of the node mobility and, consequently, the dynamic network topology. We propose protocols that use the destination position to generate a geographic area called an anonymity zone (AZ). A packet for a destination is delivered to all the nodes in the AZ, which make up the anonymity set. The size of the anonymity set may decrease, because nodes are mobile, yet the corresponding anonymity set management is simple. We design techniques to further improve node anonymity and reduce communication overhead. We use analysis and extensive simulation to study the node anonymity and routing performance and to determine the parameters that most impact the anonymity level that can be achieved by our protocol. [ABSTRACT FROM AUTHOR]

In this paper, we present a new multicast architecture and the corresponding multicast routing protocol for providing efficient and flexible multicast services over the Internet. Traditional multicast protocols construct and update the multicast tree in a distributed manner, which may cause two problems: first, since each node has only local or partial information on the network topology and group membership, it is difficult to build an efficient multicast tree and, second, due to the lack of complete information, broadcast is often used for sending control packets and data packets, which consumes a great deal of network bandwidth. In the newly proposed multicast architecture, a few powerful routers, called m-routers, collect multicast-related information and process multicast requests based on the information collected. The m-routers handle most of the multicast-related tasks, whereas other routers in the network only need to perform minimum functions for routing. The m-routers are designed to be able to handle simultaneous many-to-many communications efficiently. The new multicast routing protocol, called the Service-Centric Multicast Protocol (SCMP), builds a shared multicast tree rooted at the m-router for each group. The multicast tree is computed in the m-router by employing the Delay-Constrained Dynamic Multicast (DCDM) algorithm, which dynamically builds a delay-constrained multicast tree and minimizes the tree cost as well. The physical construction of the multicast tree over the Internet is performed by a special type of self-routing packets in order to minimize the protocol overhead. Our simulation results on ns-2 demonstrate that the new SCMP protocol outperforms other existing protocols and is a promising alternative for providing efficient and flexible multicast services over the Internet. [ABSTRACT FROM AUTHOR]

The bandwidth-constrained routing problem (BCRP) asks for a route that has sufficient bandwidth for data transmission. When BCRP is defined for wired networks, it can be solved in polynomial time. On the other hand, when it is defined for wireless ad hoc networks, it is NP-complete if the underlying MAC protocol is TDMA-based or CDMA-over-TDMA-based. In this paper, we show that BCRP is still NP-complete, even if CSMA-based or contention-based CDMA MAC protocols are used. Besides, we show that BCRP is polynomial-time solvable if the channel model is collision-free and the scheduling policy is FIFO. In wireless ad hoc networks, no MAC protocol was designed before, which would lead to a polynomial-time solution to BCIRP. The results of this paper suggest a design principle for MAC protocols that can support QoS routing well. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of balancing the network traffic load when the data generated in a wireless sensor network is stored on the sensor node themselves, and accessed through querying a geographic hash table. Existing approaches allow balancing network load by changing the georouting protocol used to forward queries in the geographic hash table. However, this comes at the expense of considerably complicating the routing process, which no longer occurs along (near) straight-line trajectories, but requires computing complex geometric transformations. In this paper, we demonstrate that it is possible to balance network traffic load in a geographic hash table without changing the underlying georouting protocol. Instead of changing the (near) straight-line georouting protocol used to send a query from the node issuing the query (the source) to the node managing the queried key (the destination), we propose to “reverse engineer” the hash function used to store data in the network, implementing a sort of “load-aware” assignment of key ranges to wireless sensor nodes. This innovative methodology is instantiated into two specific approaches: an analytical one, in which the destination density function yielding quasiperfect load balancing is analytically characterized under uniformity assumptions for what concerns location of nodes and query sources; and an iterative, heuristic approach that can be used whenever these uniformity assumptions are not fulfilled. In order to prove practicality of our load balancing methodology, we have performed extensive simulations resembling realistic wireless sensor network deployments showing the effectiveness of the two proposed approaches in considerably improving load balancing and extending network lifetime. Simulation results also show that our proposed technique achieves better load balancing than an existing approach based on modifying georouting. [ABSTRACT FROM AUTHOR]

Delay Tolerant Networks (DTNs) are characterized by nondeterministic mobility and connectivity. Message routing in DTNs usually employs a multicopy forwarding scheme. To avoid the cost associated with flooding, much effort has been focused on opportunistic forwarding, which aims to reduce the cost of forwarding while retaining high routing performance by forwarding messages only to nodes that have high delivery probabilities. This paper presents two multicopy forwarding protocols, called optimal opportunistic forwarding (OOF) and OOF-, which maximize the expected delivery rate and minimize the expected delay, respectively, while requiring that the number of forwardings per message does not exceed a certain threshold. Our contributions in this paper are summarized as follows: We apply the optimal stopping rule in the multicopy opportunistic forwarding protocol. Specifically, we propose two optimal opportunistic forwarding metrics to maximize delivery probability and minimize delay, respectively, with a fixed number of copies and within a given time-to-live. We implement and evaluate OOF and OOF- as well as several other representative forwarding protocols, i.e., Epidemic, Spray-and-wait, MaxProp^\ast, and Delegation. We perform trace-driven simulations using both real and synthetic traces. Simulation results show that, in the traces where nodes have regular intermeeting times, the delivery rates of OOF and OOF- can be 30 percent greater than the compared routing protocols. [ABSTRACT FROM PUBLISHER]

Energy awareness for computation and protocol management is becoming a crucial factor in the design of protocols and algorithms. On the other hand, in order to support node mobility, scalable routing strategies have been designed and these protocols try to consider the path duration in order to respect some QoS constraints and to reduce the route discovery procedures. Often energy saving and path duration and stability can be two contrasting efforts and trying to satisfy both of them can be very difficult. In this paper, a novel routing strategy is proposed. This proposed approach tries to account for link stability and for minimum drain rate energy consumption. In order to verify the correctness of the proposed solution a biobjective optimization formulation has been designed and a novel routing protocol called Link-stAbility and Energy aware Routing protocols (LAER) is proposed. This novel routing scheme has been compared with other three protocols: PERRA, GPSR, and E-GPSR. The protocol performance has been evaluated in terms of Data Packet Delivery Ratio, Normalized Control Overhead, Link duration, Nodes lifetime, and Average energy consumption. [ABSTRACT FROM AUTHOR]

Greedy forwarding is a simple yet efficient technique employed by many routing protocols. It is ideal to realize point-to-point routing in wireless sensor networks because packets can be delivered by only maintaining a small set of neighbors' information regardless of network size. It has been successfully employed by geographic routing, which assumes that a packet can be moved closer to the destination in the network topology if it is forwarded geographically closer to the destination in the physical space. This assumption, however, may lead packets to the local minimum where no neighbors of the sender are closer to the destination or low-quality routes that comprise long distance hops of low packet reception ratio. To address the local minimum problem, we propose a topology aware routing (TAR) protocol that efficiently encodes a network topology into a low-dimensional virtual coordinate space where hop distances between pairwise nodes are preserved. Based on precise hop distance comparison, TAR can assist greedy forwarding to find the right neighbor that is one hop closer to the destination and achieve high success ratio of packet delivery without location information. Further, we improve the routing quality by embedding a network topology based on the metric of expected transmission count (ETX). ETX embedding accurately encodes both a network's topological structure and channel quality to nodes' small size virtual coordinates, which helps greedy forwarding to guide a packet along the optimal path that has the fewest number of transmissions. We evaluate our approaches through both simulations and experiments, showing that routing performance are improved in terms of routing success ratio and routing cost. [ABSTRACT FROM AUTHOR]

Routing is one of the most challenging, open problems in disruption-tolerant networks (DTNs) because of the short-lived wireless connectivity environment. To deal with this issue, researchers have investigated routing based on the prediction of future contacts, taking advantage of nodes' mobility history. However, most of the previous work focused on the prediction of whether two nodes would have a contact, without considering the time of the contact. This paper proposes predict and relay (PER), an efficient routing algorithm for DTNs, where nodes determine the probability distribution of future contact times and choose a proper next-hop in order to improve the end-to-end delivery probability. The algorithm is based on two observations: one is that nodes usually move around a set of well-visited landmark points instead of moving randomly; the other is that node mobility behavior is semi-deterministic and could be predicted once there is sufficient mobility history information. Specifically, our approach employs a time-homogeneous semi-Markov process model that describes node mobility as transitions between landmarks. Then, we extend it to handle the scenario where we consider the transition time between two landmarks. A simulation study shows that this approach improves the delivery ratio and also reduces the delivery latency compared to traditional DTN routing schemes. [ABSTRACT FROM AUTHOR]

In this paper, we present a framework for analyzing routing performance in delay tolerant networks (DTNs). Differently from previous work, our framework is aimed at characterizing the exact distribution of relevant performance metrics, which is a substantial improvement over existing studies characterizing either the expected value of the metric, or an asymptotic approximation of the actual distribution. In particular, the considered performance metrics are packet delivery delay, and communication cost, expressed as number of copies of a packet circulating in the network at the time of delivery. Our proposed framework is based on a characterization of the routing process as a stochastic coloring process and can be applied to model performance of most stateless delay tolerant routing protocols, such as epidemic, two-hops, and spray and wait. After introducing the framework, we present examples of its application to derive the packet delivery delay and communication cost distribution of two such protocols, namely epidemic and two-hops routing. Characterizing packet delivery delay and communication cost distribution is important to investigate fundamental properties of delay tolerant networks. As an example, we show how packet delivery delay distribution can be used to estimate how epidemic routing performance changes in presence of different degrees of node cooperation within the network. More specifically, we consider fully cooperative, noncooperative, and probabilistic cooperative scenarios, and derive nearly exact expressions of the packet delivery rate (PDR) under these scenarios based on our proposed framework. The comparison of the obtained packet delivery rate estimation in the various cooperation scenarios suggests that even a modest level of node cooperation (probabilistic cooperation with a low probability of cooperation) is sufficient to achieve 2-fold performance improvement with respect to the most pessimistic scenario in which all potential forwarders drop packets. [ABSTRACT FROM AUTHOR]

Reliable communications are essential for most applications in wireless sensor networks (WSNs). In traditional approaches, the per-hop and end-to-end (E2E) recovery schemes are widely used. These schemes, however, suffer from low E2E success rate and poor energy efficiency in large-scale real environments. Through empirical studies, in this paper we identify three major problems that hinder the efficient and reliable communications. To address these problems, we propose a novel in-middle recovery scheme and realize it by designing and implementing a proliferation routing. Proliferation routing integrates three core technologies, namely, capability-based path finder, a randomized dispersity, and reproduction. Proliferation routing offers great flexibilities for transmissions. It cannot only be applied with any Medium Access Control (MAC) protocols and routing metrics, but also obtains a desired service quality (i.e., transmission success rate, energy cost, etc.) by controlling the system parameters. To demonstrate the effectiveness of proliferation routing, we thoroughly analyze its performance. We also conduct performance evaluations through implementation experiments as well as simulations. In a specific experimental setup, proliferation routing can increase the E2E transmission success rate up to 80 percent compared with the well-known hop-based routing and flooding. [ABSTRACT FROM PUBLISHER]

Energy is an extremely critical resource for battery-powered wireless sensor networks (WSN), thus making energy-efficient protocol design a key challenging problem. Most of the existing energy-efficient routing protocols always forward packets along the minimum energy path to the sink to merely minimize energy consumption, which causes an unbalanced distribution of residual energy among sensor nodes, and eventually results in a network partition. In this paper, with the help of the concept of potential in physics, we design an Energy-Balanced Routing Protocol (EBRP) by constructing a mixed virtual potential field in terms of depth, energy density, and residual energy. The goal of this basic approach is to force packets to move toward the sink through the dense energy area so as to protect the nodes with relatively low residual energy. To address the routing loop problem emerging in this basic algorithm, enhanced mechanisms are proposed to detect and eliminate loops. The basic algorithm and loop elimination mechanism are first validated through extensive simulation experiments. Finally, the integrated performance of the full potential-based energy-balanced routing algorithm is evaluated through numerous simulations in a random deployed network running event-driven applications, the impact of the parameters on the performance is examined and guidelines for parameter settings are summarized. Our experimental results show that there are significant improvements in energy balance, network lifetime, coverage ratio, and throughput as compared to the commonly used energy-efficient routing algorithm. [ABSTRACT FROM PUBLISHER]

Wormhole switching is a popular switching technique in interconnection networks. This technique is also prone to deadlocks. Adaptive routing algorithms provide alternative paths that can be used to escape congested areas and prevent some deadlocks to occur. If not designed carefully, these new paths may as well introduce deadlocks. A successful solution to deadlock prevention is to constrain the routing function such that it does not introduce any deadlock. Many necessary and sufficient conditions for deadlock-free routing have been proposed. The definition and the proof of these conditions are complex and error-prone. These conditions are often counterintuitive and difficult to understand. Moreover, they are not static, as they all require the analysis of configurations, i.e., the network state. The contribution of this paper is twofold. We present the first static necessary and sufficient condition for deadlock-free routing in wormhole networks. Our condition is much simpler and requires less assumptions than all previous ones. It is formally proven correct using an automated proof assistant. In particular, our condition applies to incoherent routing functions which was considered an open problem. Second, we prove the deadlock decision problem co-NP-complete for wormhole networks. [ABSTRACT FROM PUBLISHER]

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol that connects autonomous systems (ASes). Despite its importance for the Internet infrastructure, BGP is vulnerable to a variety of attacks due to lack of security mechanisms in place. Many BGP security mechanisms have been proposed. However, none of them has been deployed because of either high cost or high complexity. The right trade-off between efficiency and security has been ever challenging. In this paper, we attempt to trade-off between efficiency and security by giving a little dose of trust to BGP routers. We present a new flexible threat model that assumes for any path of length h, at least one BGP router is trustworthy, where h is a parameter that can be tuned according to security requirements. Based on this threat model, we present two new symmetric key approaches to securing BGP: the centralized key distribution approach and the distributed key distribution approach. Comparing our approaches to the previous SBGP scheme, our centralized approach has a 98 percent improvement in signature verification. Our distributed approach has equivalent signature generation cost as in SBGP and an improvement of 98 percent in ]signature verification. Comparing our approaches to the previous SPV scheme, our centralized approach has a 42 percent improvement in signature generation and a 96 percent improvement in signature verification. Our distributed approach has a 90 percent improvement on signature generation cost and a 95 percent improvement in signature verification cost. We also describe practical techniques for increasing the long-term security and collusion resistance of our key distribution protocols without increasing the signature generation and verification costs. By combining our approaches with previous public key approaches, it is possible to simultaneously provide an increased level of security and reduced computation cost. [ABSTRACT FROM PUBLISHER]

Although anonymizing Peer-to-Peer (P2P) systems often incurs extra traffic costs, many systems try to mask the identities of their users for privacy considerations. Existing anonymity approaches are mainly path-based: peers have to pre-construct an anonymous path before transmission. The overhead of maintaining and updating such paths is significantly high. We propose Rumor Riding (RR), a lightweight and non-path-based mutual anonymity protocol for decentralized P2P systems. Employing a random walk mechanism, RR takes advantage of lower overhead by mainly using the symmetric cryptographic algorithm. We conduct comprehensive trace-driven simulations to evaluate the effectiveness and efficiency of this design, and compare it with previous approaches. We also introduce some early experiences on RR implementations. [ABSTRACT FROM AUTHOR]