DTN Neighbor Discovery - ION IPND Implementation Assembly Part 1

Register
Submit a solution
The challenge is finished.

Challenge Overview

1.0. Project Overview

Welcome to the NASA Disruption Tolerant Networking (DTN) project. DTN is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity.

Note that some literature may use the term Delay Tolerant Network which is also abbreviated as DTN - the two terms are used interchangeably.

DTN is designed to provide reliable end-to-end delivery of information between nodes, and to do so in an environment that experiences frequent connectivity disruptions and topology changes. Such a capability will directly support human and robotic space exploration, as well as have wide applicability to land-mobile and airborne terrestrial communications.

Learn more about DTN

 

Project Objectives

The goal of this project is very simple – and that is to update DTN ION so that it includes IP Neighbor Discovery (IPND).  

IPND is a method for otherwise oblivious nodes to learn of the existence, availability, and addresses of other DTN participants. IPND both sends and listens for small IP UDP announcement beacons that are addressed to an IP unicast, multicast, or broadcast address to discover specified remote neighbors, or unspecified local neighbors in the network topology.

Other DTN implementations, such as DTN2 and IBR, already support IPND. We now need to updated DTN ION to enable neighbor discovery capabilities as well. Neighbor discovery is also needed to enable future dynamic routing capability for the ION DTN implementation.

- See more at: http://www.topcoder.com/dtn/neighbor-discovery/#sthash.Mdb2QG1w.dpuf

2.0. Project Objectives

The goal of this project is fairly straightforward, to update an open source DTN implementation called DTN Interplanetary Overlay Network (DTN ION) so that it includes IP Neighbor Discovery (IPND) functionality. 

IPND is a method for otherwise oblivious nodes to learn of the existence, availability, and addresses of other DTN participants. IPND both sends and listens for small IP UDP announcement beacons that are addressed to an IP unicast, multicast, or broadcast address to discover specified remote neighbors, or unspecified local neighbors in the network topology.

Other DTN implementations, such as DTN2 and IBR, already support IPND. This project will design and implement updates to the DTN ION code written in C to add neighbor discovery capabilities.

Neighbor discovery is also needed to enable future dynamic routing capability for the ION DTN implementation.

 

Project Objectives

The goal of this project is very simple – and that is to update DTN ION so that it includes IP Neighbor Discovery (IPND).  

IPND is a method for otherwise oblivious nodes to learn of the existence, availability, and addresses of other DTN participants. IPND both sends and listens for small IP UDP announcement beacons that are addressed to an IP unicast, multicast, or broadcast address to discover specified remote neighbors, or unspecified local neighbors in the network topology.

Other DTN implementations, such as DTN2 and IBR, already support IPND. We now need to updated DTN ION to enable neighbor discovery capabilities as well. Neighbor discovery is also needed to enable future dynamic routing capability for the ION DTN implementation.

- See more at: http://www.topcoder.com/dtn/neighbor-discovery/#sthash.Mdb2QG1w.dpuf

3.0. Challenge Details

          

3.1. Challenge Documents

Document Description
IPND Internet Draft PDF version. The actual IPND spec is just 19 pages (page 3 - 21).
ION-DTN Please download it from SourceForge directly. You must use ION version 3.3.0.
Python IPND (PyIPND) Please download it from the forum after you register for the challenge.
ION Style Guide ION-DTN C coding conventions. Available from the forum after you register for the challenge.

 

We want to port our proof of concept IPND implementation -- PyIPND written in Python to C. Similar to our approach for PyIPND, the implementation of IPND in ION-DTN will be split in two challenges: Parts 1 and 2. The Part 1 assembly challenge will implement all mandatory and some optional aspects of the IPND protocol while Part 2 will implement the remaining optional aspects of IPND in ION-DTN.

 

3.2. Challenge Requirements

The table below summarizes the aspects of the IPND protocol that are to be implemented in ION-DTN. All sections labelled "Part 1" are in scope of this assembly challenge.

IPND Section

Challenge

2.1. Beacon Period . . . . . . . . . . . . . . . . . . . . . . 5

2.2. Unknown Neighbors . . . . . . . . . . . . . . . . . . . . 6

2.3. Enumerated Neighbors . . . . . . . . . . . . . . . . . . . 6

2.4. Allowing Data to Substitute for Beacons . . . . . . . . . 6

2.5. Discovering Bidirectional Links . . . . . . . . . . . . . 7

2.6. Beacon Message Format . . . . . . . . . . . . . . . . . . 7

2.6.1. Service Block . . . . . . . . . . . . . . . . . . . . 9

2.6.2. IPND Service Definition TLV Encoding . . . . . . . . . 10

2.6.3. Services . . . . . . . . . . . . . . . . . . . . . . . 13

2.6.4. Neighborhood Bloom Filter . . . . . . . . . . . . . . 14

2.7. IPND and CLAs . . . . . . . . . . . . . . . . . . . . . . 16

2.8. Disconnection . . . . . . . . . . . . . . . . . . . . . . 16

Appendix B. Fictional Private Service Example . . . . . . . . . . 25

Part 1.

Part 1.

Part 1.

Part 1.

Part 2.

Part 1.

Part 2.

Part 2.

Part 2.

Part 2.

Part 1.

Part 1.

Part 2.

3.3. Challenge Task: Implementation

1. The ION-DTN code base is fairly large, so you are encouraged to familiarize yourself with its architecture by reviewing the document ION.pdf in the ion-open-source folder after extracting ION v3.3.0 locally. You should review sections: 1.1, 1.2, 1.3, 1.4, 1.5 and 1.6.1 that document salient aspects of the design and operation of ION-DTN.

2. ION-DTN was designed to run on flight environments, which are typically based on Real Time Operating Systems (RTOS). Many RTOS improve processing determinism by omitting the support for protected memory models that is provided by Unix-like operating systems: all tasks have direct access to all regions of system memory. ION-DTN therefore had to be designed with no expectation of memory protection.

Competitors must be cautious with respect to the memory management in ION-DTN because it is different from traditional C memory management, therefore, malloc can NOT be used. ION-DTN provides its own mechanisms for memory management / data sharing via Personal Space Management (PSM), Spacecraft Data Recorder (SDR), Memmgr etc. Competitors are advised to read section 1.5 of ION.pdf to get familiar with these memory/resource management modules.

3. Wherever possible, please adhere to the C coding guidelines in the ION Style Guide.

4. The ION IPND code should reside in a new ion-open-source/bp/ipnd directory, along the same lines as the ipn directory. Please split the IPND daemon up into multiple source files and put all the common definitions in an ipndP.h file in that directory.

5. PyIPND spawns 3 threads on start up making it multithreaded. Please use an existing multithreaded ION program such as stcpcli as a model for writing multithreaded code in ION.

6. PyIPND does not provide any Convergence Layer Adapters (CLA) to be able to fulfill the requirements of the IPND protocol with respect to notifying dependent CLAs of the discovery of a new node, or loss of contact to a previously discovered node, as described in section 2.7. IPND and CLAs, because it is a prototype and not a proper DTN distribution like ION.

Your ION IPND port from PyIPND must implement this requirement by notifying dependent CLAs via the eureka interface (ion-open-source/bp/include/eureka.h).

 

3.3.1. Technologies

  • Linux (Ubuntu 14.04.2 LTS recommended)
  • C
  • GCC (version 4.8.1 is recommended)
  • Make (version 3.82 is recommended)
  • Python 2.7.9
  • ION-DTN 3.3.0
  • Docker 1.5.0

 

3.3.2. ION-DTN Setup

PyIPND includes several Docker files that demonstrate how to install ION-DTN (and other DTN distributions) on Ubuntu Linux which you'll find in docker/templates/. You should be able to adapt the instructions in the Docker file for ION-DTN (docker/templates/ion.dockerfile) to suit your development environment.

You can refer to the assembly tutorial for additional information on challenge deliverables if you are new to competing on Assembly challenges.

 

3.4. Challenge Task: Tests

Your system tests should demonstrate the use of the IPND protocol between multiple nodes running different IPND implementations. Please test your implementation can interoperate with DTN2 and PyIPND.

For instance, if node 1 is running DTN2, node 2 is running PyIPND and node 3 is running ION-DTN and they constitute a 3-node local network, each node should be able to learn of the existence the other 2 nodes via the IPND protocol.

 

4.0. Challenge Deliverables

Please submit, in a compressed archive:

  • Deployment Guide (DG): describing how to deploy and test your Python IPND implementation;
  • Updated ION-DTN code: implementing the requirements;
  • Updated Docker files and Python scripts: that exercise your implementation using system tests.

Please download the template on which to base your deployment guide on from here.



Final Submission Guidelines

1. Third Party Code/Libraries - All third party code/libraries must be open source and you must include the license in your submission. The license must allow us to modify/re-package the code as necessary. If you have any questions regarding this, please post in the forums. Submissions that include third party code without the proper license information will be disqualified if the third party code is found to be non-usable due to license restrictions.

2. Attribution/References - You must properly attribute and or reference any sentences, paragraphs or quotes that you cite in your text-based submission. If your submission is found to include text that has been copied and pasted from an online source without properly attributing the source, you will receive a not-so-nice email from the topcoder competition manager.

3. Spell Check - We understand that not all submitters will be native English speakers and that there will be spelling/grammatical mistakes. We request that you first run your submission through a grammar/spell checker before submission so as to fix simple mistakes.

ELIGIBLE EVENTS:

2015 topcoder Open

Review style

Final Review

Community Review Board

Approval

User Sign-Off

ID: 30048846