Source-linked AI summary
Navigo: Interest Forwarding by Geolocations in Vehicular Named Data Networking
Giulio Grassi, Davide Pesavento, Giovanni Pau, Lixia Zhang, Serge Fdida
TL;DR
Vehicular networks have highly dynamic connectivity, challenging routing to specific moving nodes. Navigo forwards named-data Interests toward geographic regions containing potential data carriers, learning and adapting those locations. Simulations report higher success rates than GPSR, increased infrastructure offload in denser traffic, and overhead that can reach GPSR levels at higher consumer shares.
Problem
Frequent link disruptions and short link durations make routing to moving targets difficult in vehicular networks.
Method
Navigo binds data names to geographic areas and forwards Interests toward regions containing producers, mules, caches, or RSUs.
Results
Navigo satisfies more Interests than GPSR, while denser traffic increases infrastructure offload and can raise V2V channel-access overhead to GPSR levels.
Takeaways & Limitations
Fetching data from multiple carriers in geographic regions provides the basis for Navigo’s adaptive vehicular forwarding strategy.
Takeaways & Limitations
The evaluation assumes an urban setting with GPS, digital maps, capable vehicles, and roadside units, while constrained caching is left for future work.
Abstract
from arXiv · showhide
This paper proposes Navigo, a location based packet forwarding mechanism for vehicular Named Data Networking (NDN). Navigo takes a radically new approach to address the challenges of frequent connectivity disruptions and sudden network changes in a vehicle network. Instead of forwarding packets to a specific moving car, Navigo aims to fetch specific pieces of data from multiple potential carriers of the data. The design provides (1) a mechanism to bind NDN data names to the producers' geographic area(s); (2) an algorithm to guide Interests towards data producers using a specialized shortest path over the road topology; and (3) an adaptive discovery and selection mechanism that can identify the best data source across multiple geographic areas, as well as quickly react to changes in the V2X network.
I. INTRODUCTION
Vehicular networks suffer frequent connectivity disruptions and topology changes, making node-to-node routing difficult. Navigo uses geographic information to guide NDN Interests toward data locations and evaluates the design through simulations.
- Navigo maps data names to locations and forwards Interests along paths toward those locations.
- Navigo discovers and selects available data sources across multiple geographic areas and reacts to sudden vehicle-network changes.
- The design demonstrates an NDN-based approach intended to cope with ad hoc mobility and frequent connectivity disruptions in vehicular networking.
- Link duration is less than 10 seconds in 97% of cases in the Portland vehicle-mobility scenario.
- Existing position-based routing such as GPSR routes toward moving destination positions and requires location knowledge and neighborhood maintenance.
- Unlike node-targeted routing, Navigo fetches data from producers, mules, or caches in a geographic region, using broadcast communication and NDN caching.
B. Named Data Networking
NDN forwards requests for named data rather than addressing specific IP nodes, while routers track pending requests and cache returned data. V-NDN applies this model to vehicular communication, but Navigo adds directed forwarding to replace blind flooding.
- NDN consumers request named data with Interests, and routers forward those Interests while recording pending requests.
- Matching Data packets return along PIT-established paths and are cached by routers for subsequent requests.
- NDN packets do not carry IP addresses; forwarding uses names for Interests and PIT information for returning Data.
- V-NDN exploits wireless broadcast so multiple vehicles can participate, helping overcome failures at any single link.
- V-NDN lacks smart forwarding and blindly floods Interests, motivating Navigo’s effort to steer them toward data.
III. NAVIGO DESIGN OVERVIEW
Navigo couples data names with geographic locations so Interests can be forwarded without a routing protocol. It uses MGRS regions, GeoFaces, and learned bindings between prefixes and data areas.
- Navigo binds data names to locations where data resides, including producers, cached mules, or Internet access points.
- The design addresses geographic namespaces, name-to-location mapping, and compatibility with the existing NDN forwarding framework.
- A. Naming geographic areas: MGRS divides the world into labeled geographic regions derived from UTM and UPS grid systems.
- A. Naming geographic areas: The current implementation uses fixed 200x200 meter geo-areas, while MGRS supports different precision levels.
- B. Mapping names to locations: When unknown data is requested, flooding can reach a matching copy, whose returned Data supplies an MGRS area that intermediate nodes learn.
- C. Forwarding with GeoFaces: GeoFaces bind geographic areas to interfaces, allowing the FIB to map name prefixes to GeoFaces without changing its prefix-face structure.
D. Design assumptions
Navigo assumes an urban vehicular setting with GPS, digital maps, WiFi ad hoc communication, storage, computation, and roadside units. Its forwarding adapts between learned geographic paths, exploration flooding, and timeout-based removal.
- The evaluation focuses on urban scenarios and assumes every vehicle has GPS and a digital map for identifying its location and MGRS name.
- Vehicles are assumed to use WiFi ad hoc communication with sufficient storage and computational capabilities.
- Navigo assumes roadside units on some roads provide Internet connectivity and run NDN with Navigo.
- The strategy explores surrounding areas for producers, mules, or RSUs, then forwards future Interests toward the area returning the first Data packet.
- Without FIB information, Navigo floods an Interest during an exploration phase; with multiple GeoFaces it selects them round-robin.
- With one GeoFace, Navigo uses it with probability 0.95 and otherwise floods to preserve exploration opportunities.
- A GeoFace binding is removed when requested Data does not arrive before deadline T, set to 300ms in the experiments.
- The system clears deadlines for pending same-prefix Interests after one succeeds, while more sophisticated face-selection criteria remain future work.
V. FIB MANAGEMENT
Navigo manages FIB entries by associating content-name prefixes with geographic areas and corresponding GeoFaces. This binding balances FIB size against flooding overhead while supporting forwarding toward data locations.
- Prefix aggregation: NDN names may contain multiple content pieces, so Interests require a FIB entry for the prefix aggregating those pieces.Consumers and producers know the name semantics, but forwarders may not; the consumer’s LAL therefore attaches the aggregate prefix to each Interest.
- Geo-area granularity: Associating geographic areas with faces creates a trade-off between FIB size and Interest-flooding overhead.Smaller areas increase the number of faces bound to a prefix, while larger areas increase the area over which cars flood Interests.
- Geo-area granularity: With 200×200 meter areas, the number of faces bound to one prefix never exceeded 9 in the experiments.Bindings are removed when an Interest fails, limiting accumulation of faces for the same prefix.
- Navigo extension: Navigo extends LAL by binding GeoFaces to geo-areas and steering Interests along shortest paths that account for urban obstructions.The design uses destination-area knowledge rather than only the original LAL mechanisms.
A. LAL and GeoFaces
LAL maintains geographic forwarding state and uses the road topology to steer Interests toward destination areas. It combines shortest-path progress, probabilistic exploration, and local dissemination to accommodate dynamic vehicular connectivity.
- LAL and GeoFaces: LAL creates and removes GeoFaces while maintaining their geo-area mappings in the Face-to-Area table.Data packets provide geo-area information; unused GeoFaces are removed after a period on the order of tens of seconds.
- Road-topology forwarding: Navigo computes paths to destination areas with specialized Dijkstra over a graph whose edges are streets and nodes are intersections.The design substitutes the more stable road topology for VANET network topology, whose links are short-lived.
- Road-topology forwarding: Edge costs are inversely proportional to lane count, favoring roads with more lanes without requiring neighbor-position exchanges.The experiments used costs of 1 for 2-lane, 0.7 for 4-lane, and 0.25 for 6-lane roads; other weighting factors remain future work.
- Interest forwarding: A receiving node forwards an Interest only when its path to the destination area is cheaper than the previous hop’s path.Once the Interest reaches the destination area, Navigo floods it locally; cars outside that area may reply but do not continue forwarding it.
D. Forwarding based on forwarding points
Navigo prioritizes forwarding at intersections and selects relays using self-determined waiting timers based on position, distance, forwarding-point status, and packet type. Implicit acknowledgments and suppression prevent redundant transmissions.
- Forwarding points: Navigo divides each junction into FP1 at the core and FP2 at the external area, prioritizing vehicles within these forwarding points.The design uses intersections as preferred forwarding locations because they can cover larger areas with fewer hops despite urban obstructions.
- Waiting timers: Vehicles inside forwarding points wait less, with FP1 vehicles waiting less than FP2 vehicles and a random component reducing collisions.This timer policy prioritizes the more central portion of an intersection.
- Waiting timers: Among vehicles in different forwarding points, those farther from the previous hop wait less; each nearer 100-meter segment adds 4 ms for Data or 1.5 ms for Interest.Vehicles beyond 500 meters in the furthest sector use the minimum waiting timer.
- Waiting timers: At road edges, the waiting timer is inversely proportional to distance from the previous hop.This extends the distance-based prioritization used in V-NDN.
- Suppression and acknowledgment: Data packets use a shorter maximum waiting timer than the minimum Interest timer, suppressing further Interest propagation by nearby data-provider neighbors.Once one car forwards a packet, vehicles with larger waiting timers suppress their transmissions through implicit acknowledgment.
- Suppression and acknowledgment: The waiting timer is computed independently by each car from its position and distance to the previous hop, without neighbor-position knowledge.Navigo therefore avoids periodic one-hop neighbor-position exchanges.
A. Scenario
The evaluation simulates Navigo in a realistic urban Los Angeles road scenario with heterogeneous traffic, caching, wireless communication, and building-aware propagation. The setup also includes assumptions that simplify current communication behavior and fixes timer values used in experiments.
- Scenario: The simulated urban map covers 2.1×2.1 km in Los Angeles and contains 812 cars generated with SUMO traces.Traffic distribution was 48% on 6-lane roads, 37% on 4-lane roads, and 15% on 2-lane residential streets.
- Scenario: Cars enter with empty Content Stores, while each car’s store is limited to 10 GB and can retain received data for its trip.Starting empty penalizes Navigo because the design relies heavily on node caches.
- Communication model: Vehicles and RSUs share an IEEE 802.11 ad hoc interface operating at 24 Mbit/s on one fixed channel.The interface supports both vehicle-to-vehicle and vehicle-to-RSU communication.
- Experimental assumptions: The waiting-timer values remain constant for simplicity, although adapting them to car density or data traffic could improve performance.This is an explicit scope boundary of the experimental configuration.
- Experimental assumptions: The RSUs are modeled as fully functional NDN nodes without MAC-layer authentication or link setup.The paper notes that this does not reflect current WiFi practices, while emerging standards may reduce link setup requirements.
- Communication model: The experiment models urban propagation with CORNER, accounting for buildings and fast-fading effects.This propagation model is implemented in a modified ndnSIM environment.
B. Music streaming over NDN
Navigo was evaluated in a simulated music-streaming application against GPSR, varying the fraction of cars acting as consumers. It achieved higher Interest satisfaction and substantially more uninterrupted song playback, especially at lower consumer densities.
- Evaluation setup: The evaluation used a simulated music-streaming provider reachable through four RSUs, with consumers ranging from 2% to 100% of cars.Each song averaged three minutes and approximately 1,700 data chunks; requests followed a Zipf distribution.
- Evaluation setup: Navigo was compared with GPSR, supplied with an oracle locating the closest node holding the requested song chunk.The comparison therefore gave GPSR cost-free knowledge of the nearest data source location.
- Success rate: Navigo satisfied a much higher percentage of Interests than GPSR and still satisfied 10% more Interests when 70% or 100% of cars were consumers.The improvement margin narrowed as the consumer fraction increased.
- User satisfaction: Navigo substantially outperformed GPSR in the percentage of songs played without buffer-underrun interruptions, especially with 50% of consumers or fewer.The simulations used a maximum playback buffer of 30 seconds.
3) V2V channel access (protocol overhead):
Navigo reduced V2V protocol overhead and infrastructure demand relative to GPSR while making greater use of in-network caches. Its lower channel-access cost held across most scenarios, although it became slightly worse with more than 50% consumers.
- V2V channel access: GPSR required more than 30 V2V-channel packets per satisfied Interest, whereas Navigo required fewer than 20 in most cases.Navigo became slightly worse than GPSR at this measure with more than 50% of consumers.
- Load on the infrastructure: Navigo’s infrastructure load ratio never exceeded 1 and was around 0.8 in most scenarios, while GPSR’s remained around 1.2 or higher.The ratio counts requests received by the streaming server divided by satisfied Interests.
- Infrastructure offload: The infrastructure-offload metric measures the percentage of Interests satisfied by cached Data packets from a car or RSU.It is used to assess how effectively in-network caching reduces infrastructure load.
- Infrastructure offload: Navigo achieved substantially higher cache utilization than GPSR, even when only other cars were considered as potential caches.GPSR did not exceed 20% of Interests satisfied by caches in the reported comparison.
E. Simulations with higher car density
In denser traffic, Navigo remains substantially better than GPSR, while increased caching opportunities coincide with higher overhead and congestion-related efficiency limits.
- 1048 cars were simulated, with 56% on 6-lane, 30% on 4-lane, and 14% on 2-lane roads.
- Navigo substantially outperformed GPSR in success rate and user satisfaction, although both decreased relative to the previous mobility.
- Infrastructure offload increased further because denser traffic created more caching opportunities for Navigo.
- Navigo overhead increased with density and reached GPSR’s level when more than 32% of consumers were present.
- Starting at 32% of consumers, MAC transmission queues grew by two orders of magnitude in heavy traffic, explaining reduced protocol efficiency.
- Navigo’s receiver-side forwarding can create multipath, increasing overhead while improving reliability and retrieval chances.