PaperlayerView exact revision on arXiv

Source-linked AI summary

Relieving the Wireless Infrastructure: When Opportunistic Networks Meet Guaranteed Delays

John Whitbeck, Yoann Lopez, Jérémie Leguay, Vania Conan, Marcelo Dias de Amorim

arXiv:1007.5459v3cs.NI

TL;DR

Wireless infrastructure faces growing mobile-data demand, while opportunistic ad hoc communication offers another way to distribute content. Push-and-Track uses acknowledgments to track dissemination and reinject copies when needed, achieving over 90% lower infrastructure load with 100% on-time delivery in the reported Bologna evaluation.

  • Problem

    The paper asks how to relieve wireless infrastructure while guaranteeing 100% delivery under tight delays as mobile data demand grows.

    Source: §I · p. 1

  • Method

    Push-and-Track combines wide-area and ad hoc radios, tracking content spread through acknowledgments and reinjecting infrastructure copies when needed.

    Source: §I · p. 1, §II · p. 2

  • Results

    Over 90% infrastructure-load reduction was achieved while maintaining 100% on-time delivery for periodic content in Bologna peak-hour traffic.

    Source: §I · p. 2

  • Takeaways & Limitations

    Random recipient selection works well as a simple strategy for pushing content to nodes that have not acknowledged reception.

    Source: §I · p. 2

Abstract

from arXiv · show

Major wireless operators are nowadays facing network capacity issues in striving to meet the growing demands of mobile users. At the same time, 3G-enabled devices increasingly benefit from ad hoc radio connectivity (e.g., Wi-Fi). In this context of hybrid connectivity, we propose Push-and-track, a content dissemination framework that harnesses ad hoc communication opportunities to minimize the load on the wireless infrastructure while guaranteeing tight delivery delays. It achieves this through a control loop that collects user-sent acknowledgements to determine if new copies need to be reinjected into the network through the 3G interface. Push-and-Track includes multiple strategies to determine how many copies of the content should be injected, when, and to whom. The short delay-tolerance of common content, such as news or road traffic updates, make them suitable for such a system. Based on a realistic large-scale vehicular dataset from the city of Bologna composed of more than 10,000 vehicles, we demonstrate that Push-and-Track consistently meets its delivery objectives while reducing the use of the 3G network by over 90%.

I. INTRODUCTION

The paper asks how opportunistic networking can reduce infrastructure load while guaranteeing full delivery within tight delays. Push-and-Track uses acknowledgments to track dissemination and reinject copies when needed; its Bologna evaluation reports over 90% lower infrastructure load with 100% on-time delivery.

I. INTRODUCTION

  • The central challenge is reducing infrastructure load while distributing content to many subscribers within a short time and guaranteeing 100% delivery.The motivating setting includes shared content such as newspapers or traffic updates.Source: §I · p. 1
  • Push-and-Track combines wide-area and local-area radios, using acknowledgments to track delivery and reinject copies when ad hoc spread may miss the target delay.The closed control loop supervises infrastructure reinjection; opportunistic ad hoc communication is preferred where possible.Source: §I · p. 1, Figure 1 · p. 1
  • The proposed strategies choose how many copies to inject, when to inject them, and which recipients to target.When-strategies set infection objectives, while whom-strategies include randomized, sojourn-time, location-based, and connectivity-based choices.Source: §I · p. 2
  • Over 90% lower infrastructure load with 100% on-time delivery was achieved for periodic content during Bologna peak-hour traffic.The evaluation used a large-scale vehicular simulation based on traffic measurements from more than 10,000 vehicles.Source: §I · p. 2
  • Random recipient selection is reported as straightforward and efficient, while reinjection decisions have greater impact early in a message’s lifetime.Both findings are reported among the paper’s introduction-level results.Source: §I · p. 2

II. MASSIVE DISSEMINATION OF MOBILE CONTENT WITH PUSH-AND-TRACK

Push-and-Track targets content for mobile subscribers with broadband infrastructure access and ad hoc connectivity. It tracks epidemic dissemination through acknowledgments and uses feedback to decide whether to push more copies, without relying on restricted contact-statistics assumptions.

II. MASSIVE DISSEMINATION OF MOBILE CONTENT WITH PUSH-AND-TRACK

  • The setting assumes a significant subscriber base, with devices able to use both 3G and ad hoc communication; forwarding content to uninterested users is left open.Content may serve interest-based subscriptions or geographical needs such as local traffic information.Source: §II · p. 2
  • The approach targets delay-tolerant content whose usefulness or validity has an expiration date; jitter-sensitive services such as VoIP remain infrastructure-only.The expiration date sets the delay-tolerance limit the dissemination scheme should respect.Source: §II · p. 2
  • Push-and-Track does not require restricted contact-statistics hypotheses or a learning phase before users can access content.The paper argues that contact statistics can be less relevant in urban vehicular settings where nodes may meet only once.Source: §II · p. 2
  • The system pushes content to selected nodes, tracks epidemic dissemination through infrastructure acknowledgments, and uses a closed-loop controller to decide whom to push to at each time step.The feedback is designed to be much smaller than the content itself.Source: §II · p. 2

III. REDUCING INFRASTRUCTURE LOAD: STRATEGIES

The framework divides reinjection into deciding whether and how many copies to send, then choosing recipients. Its reference strategies bound performance against infrastructure-only delivery and a centralized dominating-set target.

III. REDUCING INFRASTRUCTURE LOAD: STRATEGIES

  • Each reinjection strategy first decides how many copies to send, if any, and then selects recipients for those copies.The objective is to guarantee 100% delivery while minimizing infrastructure load.Source: §III · p. 2

A. Assumptions

  • The model issues content at time ti for delivery to all target nodes within T seconds, dividing that period into ∆t feedback steps.Nodes entering during a period should receive the message before it expires.Source: A. Assumptions · p. 2

B. Reference strategies

  • Infrastructure-only delivery pushes all content through the infrastructure and serves as the baseline cost of present-day massive distribution.No ad hoc communication is allowed in this reference strategy.Source: B. Reference strategies · pp. 2–3
  • The Dominating Set Oracle pushes to a precomputed dominating set in a directed space-time reachability graph, providing a performance target.A greedy algorithm yields a set at most log K times larger than optimal, where K is the graph’s maximum node degree.Source: B. Reference strategies · p. 3

C. When to push

When-strategies set a target infection ratio over a message’s lifetime and reinject copies when acknowledgments show dissemination below that target. They range from slow-start and fast-start curves to steady linear spread, with a panic zone near the deadline.

C. When to push

  • When-strategies define a target infection ratio over elapsed message lifetime and reinject the minimum additional copies needed when measured infection falls below target.The measured ratio comes from acknowledgments and can decline if nodes unsubscribe.Source: C. When to push · p. 3
  • In the panic zone, reached when remaining time equals the direct infrastructure push time, the system sends content to every node not yet reached.This is the deadline-protection behavior described for the objective strategies.Source: C. When to push · p. 3
  • Slow-start strategies inject few initial copies or follow slowly rising objectives, while fast-start strategies use rapidly rising objectives; Linear maintains infection proportional to elapsed time.Single Copy and Ten Copies push once and wait until the panic zone; Quadratic and Square Root are the very slow- and very fast-start objectives.Source: C. When to push · p. 3

D. To whom

The paper tests several ways to choose recipients for reinjected copies, using acknowledgments to track delivery. Its control loop supports subscriptions, departures, and receipt reporting; the Bologna dataset was selected for its large, changing user population and limited social ties.

D. To whom

  • Recipient strategies also include random selection, entry-time heuristics, and GPS-based density or potential choices.Entry-time choices target nodes near an area’s edge or middle; GPS strategies use density or potential to spread copies.Source: D. To whom · p. 3
  • Connectivity-based selection uses neighbor reports to target a node in the largest uninfected connected component, or the component with most uninfected nodes.The strategy aims to push one copy per component and approach the optimal number of copies.Source: D. To whom · p. 4

E. Control loop operation

  • Vehicles send ENTER on entry, LEAVE on exit, and ACK after receiving the content, reporting subscription, departure, and receipt to the control system.Source: E. Control loop operation · p. 4

IV. BOLOGNA VEHICULAR DATASET

  • The Bologna dataset was chosen for realistic scale, user turnover, and minimal social dynamics, unlike contact traces with roughly 100 fixed participants.Source: §IV · p. 4

A. Dataset construction

The study reconstructs individual vehicle movement for a weekday peak-hour area of Bologna, then analyzes traffic and ad hoc connectivity. The simulated network is large but remains partitioned, making mobility over time important for connectivity.

A. Dataset construction

  • The Bologna study area covers 20.6 km2 and 191 km of roads, with a ring-shaped main road and routes into the historic center.Source: A. Dataset construction · p. 4
  • Lane width encodes average incoming vehicle flow on a logarithmic scale, while color encodes average vehicle speed.Source: Figure 3 · p. 4
  • Traffic demand comes from induction-loop measurements and commute surveys, using weekday 8–9 a.m. flows while excluding Monday and Friday mornings.Source: A. Dataset construction · p. 4
  • Individual vehicle movements are inferred from macroscopic demand and route assignments using SUMO on the supplied detailed road network.The network representation includes traffic lights, lane changes, and junction right-of-way rules.Source: A. Dataset construction · p. 4

B. Dataset analysis

  • The one-hour simulation contains 10,333 vehicles; vehicles remain in the area an average of 13.2 minutes, though some trips exceed 50 minutes.Half of trips are shorter than 10 minutes.Source: B. Dataset analysis · p. 4
  • Traffic is heavier on the ring road than on the mostly single-lane capillary network, with jams on the ring and at crossroads.Source: B. Dataset analysis · p. 5
  • Contacts require vehicles within 100 m; half last under 25 seconds, while a few persist for up to 50 minutes.The contact-duration distribution is approximated by a power law up to five minutes, then an exponential decay.Source: B. Dataset analysis · p. 5
  • Despite connected components of up to 1,200 vehicles, the network remains highly partitioned, so exploiting mobility is crucial to connectivity over time.Source: B. Dataset analysis · p. 5

V. SIMULATION RESULTS

The authors built a simulator for evaluating Push-and-Track strategies at the scale of the Bologna vehicle dataset. It models contact-based ad hoc communication alongside infrastructure links and message-transfer failures.

A. Simulator

  • Existing simulators had scalability problems and were not adapted to evaluate Push-and-Track, so the authors built a simulator inspired by ONE.Source: A. Simulator · p. 5
  • The simulator retains ONE’s contact-based ad hoc model and single-neighbor communication constraint, while adding broadcast routing, message classes, and infrastructure and ad hoc media.Source: A. Simulator · p. 5
  • Transfers can fail when vehicles move out of range or leave the area before transfer completion; duplicate reception is canceled when the first transfer finishes.Transferred data before cancellation still counts toward network load.Source: A. Simulator · p. 5

B. Experimental setup

The evaluation tests message lifetimes of one and ten minutes and averages results across repeated runs. Push-and-Track shifts most message load to ad hoc communication, with its infrastructure-load advantage over the oracle depending on the deadline.

B. Experimental setup

  • With infrastructure downlink at 100 Kbytes/s and ad hoc links at 1 Mbytes/s, each 1 Mbyte content message takes 10 seconds over infrastructure and 1 second over ad hoc.Source: B. Experimental setup · p. 5
  • The evaluation tests 1-minute and 10-minute message lifetimes, with only one message active at a time.Source: B. Experimental setup · p. 6
  • Global and dynamic results are averages over 10 runs, with 95% confidence intervals calculated for each measurement.Global runs shift the first message’s send time by T/10 to smooth effects from the starting network topology.Source: B. Experimental setup · p. 6

C. Relieving the infrastructure

  • Push-and-Track shifts 97% of load to ad hoc communication with a 10-minute delay and 92% with a 1-minute delay.With a tighter deadline, epidemic dissemination has less time to spread, so more copies must be reinjected.Source: C. Relieving the infrastructure · p. 6
  • With a 10-minute delay, Push-and-Track’s infrastructure load exceeds the oracle’s by 28%.With more time, epidemic propagation can explore space-time paths, making a good initial dominating set difficult to beat.Source: C. Relieving the infrastructure · p. 6
  • With a 1-minute constraint, Push-and-Track outperforms the Dominating Set Oracle by 13.5%.Source: C. Relieving the infrastructure · p. 6
  • A feedback loop that tracks epidemic progress and reinjects copies when needed is essential to guaranteeing delivery delays in the hybrid network.Source: C. Relieving the infrastructure · p. 6

D. Beating random

Random reinjection performs better than most more sophisticated recipient-selection strategies, especially under the one-minute deadline. Connected Components is the main exception, while its control-message overhead can be substantial.

D. Beating random

  • With best reinjection (Slow linear at 10-minute delay), average infrastructure load per message, including control load, is roughly 3 Mbytes, rising to 15 Mbytes for GPS-based and Connected Components strategies.With Quadratic reinjection at a 1-minute delay, those loads are 1 Mbyte and 2 Mbytes, respectively.Source: D. Beating random · p. 7
  • At a 10-minute delay, only Connected Components significantly outperforms Random, and its extra control messages are worth the effort.Given enough time, even pushing a single copy to any node in the area is sufficient.Source: D. Beating random · p. 7
  • With a 1-minute delay, nearly every whom-strategy performs significantly worse than Random, and Connected Components is the only strategy that beats it.Random combines a high chance of reaching large connected components with uniform spreading across the area.Source: D. Beating random · p. 7
  • Random remains a practical choice when operators wish to avoid the complexity of a more sophisticated control channel and localization or proximity privacy concerns.The authors describe Random as consistently performing very well.Source: D. Beating random · p. 7

E. Fast or slow start?

The when-strategy determines how quickly infection spreads and how much infrastructure reinjection is needed. Small initial pushes can limit load, but freezing the feedback loop changes which strategy performs best.

E. Fast or slow start?

  • With a 1-minute delay, quick-start strategies approach an infection ratio of 1 after 20 seconds, while Quadratic reaches near-complete coverage after about 40 seconds.Single Copy and Ten Copies fail to achieve complete coverage before the panic zone and must reinject many copies near the deadline.Source: E. Fast or slow start? · p. 7, Figure 7 · p. 8
  • Freezing slows infection across strategies, but Quadratic initially sends one copy and then overreacts when its spread cannot catch up to the objective.Each reinjection freezes the message for twice its transmission time; new messages are initially frozen for 1 second.Source: E. Fast or slow start? · pp. 7–8, Figure 8 · p. 8
  • Quadratic without freezing and Fast Linear with freezing have the lowest infrastructure load; their infection rates nearly overlap.The comparison is for Random reinjection with a 1-minute maximum delay.Source: E. Fast or slow start? · p. 8, Figure 9 · p. 8
  • The crucial reinjection decisions occur early: copies sent during the epidemic phase-transition are nearly useless, while late additions may be deferred until the panic zone.The aim is to seed enough copies early to trigger the transition without overburdening infrastructure.Source: E. Fast or slow start? · p. 8

VI. RELATED WORK

Prior work explores opportunistic offloading and hybrid infrastructure–ad hoc networks, but uncertain delivery and delay remain concerns for opportunistic approaches. Push-and-Track is related to hybrid dissemination methods that differ in their feedback and network-knowledge assumptions.

VI. RELATED WORK

  • Opportunistic offloading has been studied for delay-tolerant email and file transfers and for overnight podcast delivery, but uncertain delays and probabilistic delivery ratios limit its suitability for many applications.Source: §VI · p. 8
  • Prior hybrid-network work found that opportunistic capabilities can improve delivery even with dense infrastructure access points, while SMS was proposed as a low-cost control channel for opportunistic networks.Source: §VI · p. 8
  • Related content-dissemination studies optimize freshness through rate allocation or choose users to maximize end-of-lifetime infection and reduce infrastructure load.Source: §VI · pp. 8–9
  • Unlike those two close approaches, Push-and-Track uses a feedback loop to react to network changes and new nodes without assuming prior pairwise contact probabilities.Source: §VI · p. 9

VII. CONCLUSIONS

Push-and-Track combines opportunistic dissemination with acknowledgments and infrastructure reinjection to reduce infrastructure load while meeting delivery deadlines. The evaluation reports over 90% lower infrastructure load with 100% delivery, while several deployment and content-demand settings remain for future study.

VII. CONCLUSIONS

  • On the Bologna vehicular dataset, Push-and-Track reduces infrastructure load by over 90% while achieving 100% delivery.The framework tracks ad hoc spread through acknowledgments and reinjects copies when needed.Source: §VII · p. 9
  • Pushing to random nodes works well because it can reach large connectivity clusters with high probability while spreading pushes uniformly around the city.Source: §VII · p. 9
  • The study assumes all users want the same content; partial participation, intermittent infrastructure connectivity, and concurrent requests for different content remain future directions.Source: §VII · p. 9
Loading 1007.5459v3…