An official website of the United States government
This paper considers the single source shortest path (SSSP) problem, which is the key for many applications such as navigation, mapping, routing, and social networking. Existing SSSP algorithms are designed mostly for shared-memory systems. Nevertheless, with the prevalence of diverse smart devices like drones, there is a growing interest in deploying SSSP algorithms over distributed computing systems so that they can run efficiently onboard of smart devices via Mobile Ad Hoc Computing or at the network edges via Mobile Edge Computing. In this paper, we introduce a communication-efficient ∆-stepping algorithm for distributed computing systems. The proposed algorithm is featured by 1) a message coordination architecture for reducing message exchanges between workers, 2) a pruning technique for reducing redundant computations, and 3) an aggregation technique for further reducing message exchanges when communication delay is significant. Theoretical analyses and experimental studies on real-world graph datasets demonstrate the promising performance of proposed algorithm.
more »
« less
Predictive routing for wireless networks: Robotics-based test and evaluation platform
Emerging Internet of Things (IoT) provides connectivity to a wide range of mobile nodes including indoor wireless users, pedestrian, ground robotics, vehicles, and flying objects. Such decentralized network require rethinking user-centric communication protocols which accommodate extremely dynamic environments of autonomous nodes. The authors recently proposed a predictive routing algorithm, which enables a delay-optimal communication through incorporating network topology prediction into the Dijkstra's shortest path algorithm. In this work, we extend the proposed solution to jointly optimize the end-to-end latency and total transmission power. Further, we develop a ground robotics platform in order to study the utility of the proposed algorithm in real-world applications. The simulation results which verified by the test platform, confirm the superiority of the proposed algorithm compared to the conventional shortest path algorithms by improving the delay and power consumption by a factor of 10% to 15%.
more »
« less
- Award ID(s):
- 1755984
- PAR ID:
- 10133287
- Date Published:
- Journal Name:
- IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC)
- Page Range / eLocation ID:
- 993 to 999
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Dynamic processes on networks, be it information transfer in the Internet, contagious spreading in a social network, or neural signaling, take place along shortest or nearly shortest paths. Computing shortest paths is a straightforward task when the network of interest is fully known, and there are a plethora of computational algorithms for this purpose. Unfortunately, our maps of most large networks are substantially incomplete due to either the highly dynamic nature of networks, or high cost of network measurements, or both, rendering traditional path finding methods inefficient. We find that shortest paths in large real networks, such as the network of protein-protein interactions and the Internet at the autonomous system level, are not random but are organized according to latent-geometric rules. If nodes of these networks are mapped to points in latent hyperbolic spaces, shortest paths in them align along geodesic curves connecting endpoint nodes. We find that this alignment is sufficiently strong to allow for the identification of shortest path nodes even in the case of substantially incomplete networks, where numbers of missing links exceed those of observable links. We demonstrate the utility of latent-geometric path finding in problems of cellular pathway reconstruction and communication security.more » « less
-
Many spatial applications benefit from the fast answering to a seemingly simple spatial query: “Is a point of interest (POI) ‘in-path’ to the shortest path between a source and a destination?” In this context, an in-path POI is one that is either on the shortest path or can be reached within a bounded yet small detour from the shortest path. The fast answering of the in-path queries is contingent on being able to determine without having to actually compute the shortest paths during runtime. Thus, this requires a precomputation solution. The key contribution of the paper is the development of an in-path oracle that is based on precomputation of which pairs of sources and destinations are in-path with respect to the given POI. For a given road network with n nodes and m POIs, an O(m×n)-sized oracle is envisioned based on the reduction of the well-separated pairs (WSP) decomposition of the road network. Furthermore, an oracle can be indexed in a database using a B-tree that can answer queries at very high throughput. Experimental results on the real road network POI dataset illustrate the superiority of this technique compared to a baseline algorithm. The proposed approach can answer ≈ 1.5 million in-path queries per second compared to a few hundred per second using a suitable baseline approach.more » « less
-
Although social media and contents are being generated and shared with an unprecedented scale and speed, rural and underdeveloped areas throughout the world have only limited access due to the lack of high-speed Internet. Connecting rural communities to the digital world and providing them with right contents will provide the much-needed bridge between urban and rural areas. In this paper, we propose a communication and information framework that utilizes simple Internet of Things (IoT) in a rural community to assist delay-tolerant content distribution. Specifically, a hybrid fog-cloud content distribution network is constructed by deploying low-end simple fog nodes and utilizing the movement of community vehicles. Moreover, drones are used to distribute content on demand as a compliment of the delay tolerant network for better delivery rate and lower delay time. A novel drone scheduling algorithm is proposed to plan drones’ tours optimally. Extensive simulation experiments have been performed to evaluate the performance of the proposed framework.more » « less
-
Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs) (i.e., firewalls and load balancers), is an effective service provision technique in modern data center networks. By requiring cloud user traffic to traverse the VNFs in order, SFC im- proves the security and performance of the cloud user applications. In this paper, we study how to place an SFC inside a data center to mini- mize the network traffic of the virtual machine (VM) communication. We take a cooperative multi-agent reinforcement learning approach, wherein multiple agents collaboratively figure out the traffic-efficient route for the VM communication. Underlying the SFC placement is a fundamental graph-theoretical prob- lem called the k-stroll problem. Given a weighted graph G(V, E), two nodes s, t ∈ V , and an integer k, the k-stroll problem is to find the shortest path from s to t that visits at least k other nodes in the graph. Our work is the first to take a multi-agent learning approach to solve k- stroll problem. We compare our learning algorithm with an optimal and exhaustive algorithm and an existing dynamic programming(DP)-based heuristic algorithm. We show that our learning algorithm, although lack- ing the complete knowledge of the network assumed by existing research, delivers comparable or even better VM communication time while taking two orders of magnitude of less execution time.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CCWC.2018.8301751
