Subject: [dtn-interest] Minimum Expected Delay routing on DTN2

From: kevin prima <[email-masked]>
Date: Mon, 19 Oct 2015 14:46:28 +0700

Hello all,

I try to implement Minimum Expected Delay (MED) routing algorithm on DTN2.
Basically, it was based on Dijkstra's algorithm. The cost of node is the
sum of average waiting time plus delay transmission and delay propagation.
My idea is modifying flood routing default on DTN2 by computing the cost of
neighbor node first, so the packet will be forwarded to only one node with
lower cost and not all neighbor nodes will get copy of packet from source
node. In your opinion, which part of flood routing script that should be
modified ? Or maybe there is another idea to implement MED on DTN2 ?

Thanks,
Kevin

---

From: Vint Cerf <[email-masked]>
Date: Mon, 19 Oct 2015 05:13:27 -0400

this is tricky in a DTN environment since the delays are much less certain
than in a dedicated, wired system.

v

On Mon, Oct 19, 2015 at 3:46 AM, kevin prima <[email-masked]>
wrote:

> _______________________________________________
> dtn-interest mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/dtn-interest
>
>

---

From: "Scott, Keith L." <[email-masked]>
Date: Mon, 19 Oct 2015 11:48:14 +0000

IF you know the connectivity schedule, then what you’re describing sounds like the Contact Graph Routing that the ION BP implementation uses.  Implementing something like that in DTN2 would be a useful thing, IMHO.

I’m not sure if the flood router would be the place to start if this is what you want to do.  I would start (I think) with tablebasedrouter and add the ability to deal with schedules.  Then you have to run Dijkstra’s taking into account the link schedules and constraints.

THEN, if you don’t want to do the calculations for every packet, you have to do something to abstract out the actual packet size and transmission times (which might be small compared to the waiting times in the schedule) and cache the route calculation results between (scheduled) topology changes.

Again, the ION CGR mechanism does this, but it would be interesting to have a second implementation, especially if you do it from scratch without trying to emulate exactly what ION CGR does.

===

If you DON’T assume that you know the connectivity schedule, then I think you need to do something like the above while trying to build a heuristic about the schedule.  PRoPHET seems like the place to start there, but frankly (and admittedly without any real data) I suspect that this would only work well in situations where the connectivity was pretty predictable.

V/r,

—keith

From:r,  dtn-interest <[email-masked]<mailto:[email-masked]>> on behalf of Vint Cerf <[email-masked]<mailto:[email-masked]>>
Date: Monday, October 19, 2015 at 5:13 AM
To: kevin prima <[email-masked]<mailto:[email-masked]>>
Cc: dtn-interest <[email-masked]<mailto:[email-masked]>>
Subject: Re: [dtn-interest] Minimum Expected Delay routing on DTN2

this is tricky in a DTN environment since the delays are much less certain than in a dedicated, wired system.

v

On Mon, Oct 19, 2015 at 3:46 AM, kevin prima <[email-masked]<mailto:[email-masked]>> wrote:
Hello all,

I try to implement Minimum Expected Delay (MED) routing algorithm on DTN2. Basically, it was based on Dijkstra's algorithm. The cost of node is the sum of average waiting time plus delay transmission and delay propagation. My idea is modifying flood routing default on DTN2 by computing the cost of neighbor node first, so the packet will be forwarded to only one node with lower cost and not all neighbor nodes will get copy of packet from source node. In your opinion, which part of flood routing script that should be modified ? Or maybe there is another idea to implement MED on DTN2 ?

Thanks,
Kevin

_______________________________________________
dtn-interest mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/dtn-interest

---

From: "Burleigh, Scott C (312B)" <[email-masked]>
Date: Mon, 19 Oct 2015 13:59:40 +0000

It sounds like what Kevin is looking at is using a delay metric to back off from flooding by transmitting only to the lowest-cost neighbor(s).  This is kind of doable in opportunistic DTN because you don’t need to know the topology of the network between the source and the destination, you’re just working off local information that might be provided by neighbor discovery.  To move from that to something CGR-like would require connectivity schedule information not only for the local node but also for all other nodes in the network, a serious leap.

Scott

From: dtn-interest [mailto:[email-masked]] On Behalf Of Scott, Keith L.
Sent: Monday, October 19, 2015 4:48 AM
To: Vint Cerf <[email-masked]>; kevin prima <[email-masked]>
Cc: dtn-interest <[email-masked]>
Subject: Re: [dtn-interest] Minimum Expected Delay routing on DTN2

===

V/r,

—keith

v