Subject: [dtn-users] Improving performance in DTN2

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Thu, 5 Jul 2012 11:16:22 -0500

I've broken out the input related event processing and methods of the BundleDaemon to a new BundleDaemonInput thread.

I included the BPQ processing in the Input thread since the processing happens during the handle_bundle_received event processing
	1. It does not look like it checks to make sure that the bundle is destined for the local node before it processes it
	2. Could this be implemented as a registration?
	3. Haven't read the draft so I could be way off base...
 
Multiple threads updating the BundleStore resulted in the following errors around the 2 million bundles mark and then a panic abort:
	[1341373296.657839 /dtn/storage/deadlock_timer warning] deadlock detection found 1 aborted transactions
	[1341373296.657890 /dtn/storage/bundles error] DB internal error: DB_LOCK_DEADLOCK: Locker killed to resolve a deadlock
 
I believe that the database access at the table level for BerkeleyDB needs to be single threaded or serialized so I added a lock to the BundleStore to serialize access. If I find it still happens, I'll raise the lock to the database level and retest.

Results of the 30 minute disconnect test at this stage:
Running connected for 1 hour with continuous 167 bundles/second flow using custody and Aggregate Custody Signals (ACS)
Memory usage according to top:
VIRT     RES     SHR     %MEM  
52924  5448  3968        0.1	    2012.07.05  07:30     no bundles sent yet
198m    62m  4128        1.6	    2012.07.04  08:00     30 minutes
198m    63m  4136        1.6	    2012.07.04  08:30     1 hour
* CPU utilization is roughly 30% with spikes to 70% every 30 seconds when it processes the ACS (dual core system)
* Using regular custody signals should smooth out the spikes which happens when it removes custody on 5000 bundles in a single pop
* 602000 bundles received and transmitted in 1 hour

At this point, I Stopped the receiving DTN node at this point for 30 minutes while continuing the 167 bundles/sec input.
CPU usage early in the 30 minute disconnect:  14 - 24%
CPU usage late in the 30 minute disconnect:  14 - 24%
Memory usage at the end of the 30 minute disconnect (319000+ bundles pending):
VIRT      RES     SHR     %MEM  
1876m  1.7g   4212       44.8	    2012.07.04  09:00     30 minutes accumulated bundles
* No problem storing 167 bundles/sec for 30 minutes

I then restarted the receiving DTN node while continuing to try to pump 167 b/s into the input node.
* 319000+ bundles pending
* Input stopped and transmit started in the 111 b/s range and quickly jumped to 125 b/s, CPU at 100%

Quickly started getting this error message which continued throughout this phase of processing:
        BundleList::contains is waiting for spin lock held by TableBasedRouter::check_next_hop

				dtnd
Time after        Input Rate       Transmit      % CPU          Bundles
  Restart               (b/s)             Rate (b/s)      Usage    Transmitted
-------------    --------------     -------------    --------    ---------------
      15m		0		 112                100            121000
      20m		0		 125                100            134500
      25m		0		 128                100            182000
      30m		0		 127                100            214500
      35m		0		 125                100            252000
      40m		0		 112                100            290000
      45m		0		 240                100            335000
      46m		0		 300                100            359000
      51m		4		     4                 200            361900
      55m		6		     6                 200            363400
      60m		8		     8                 198            365000
      65m		39		   39                192            3??000
      66m		320		 320                119            3??000
      67m		350		 350                  96            410000
      68m		167		 167                  24            565900
- 100% CPU usage was usually in the 101-103% range and idle was showing 0% so I thought the 2 CPUs were maxed out. I was surprised to see the 200% CPU at minute 55 so I guess I wasn't seeing the complete picture while looking at the top stats.
- single input bundles snuck in at roughly 1 bundle per 10 minutes during the thrashing

* So, the separate input thread by itself does not allow new bundles to be processed in and actually extended the thrashing period compared to the previous test
* One of the bottlenecks is contention by the TableBasedRouter and another thread over the TableBasedRouter's deferred list 
* Wouldn't be surprised if there are 3 or 4 bottlenecks at play here
* This was a probably a pretty good test of the BundleStore issue but I'll continue with a long duration test for added assurance

I think that I'll continue on with my planned patches for now and re-run the test after each. I suspect that this scenario will require some overhauling of a few areas after the planned patching is done to get it to run smoothly.
DZ

David Zoller
COLSA Corporation
Marshall Space Flight Center

---

From: Jacob Green <[email-masked]>
Date: Thu, 5 Jul 2012 12:38:39 -0400

I am very interested in finding ways to increase DTN2 performance, and to finding out where the bottlenecks are.

However, I would also give a word of caution here regarding multi-threading it.  The BPA is designed around a single event queue.  This is a very important design feature, and I think it important that this be maintained.  So while we can have additional threads to do I/O (network and disk), all results of that I/O still needs to be handled through the main event Q.

Events that fire from the main event Q are processed by various different plug-able subsystems, and depend on the single threaded and FIFO nature of this design.  For example, immediate delivery of bundles to local clients in a client I/O thread, prior to being processed by main event Q will not work.  Some routers need to know about the existence of the local bundles even if they don't need to immediately route them, especially for many-to-many EID destinations.  In cases where a router adds meta-blocks, those blocks need to be added prior to delivery to local clients.  

Jacob

-------------------------------------------------------------------------------
Jacob Green
[email-masked]
Spread Concepts LLC.  
-------------------------------------------------------------------------------

On Jul 5, 2012, at 12:16 PM, Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT] wrote:

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

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Thu, 5 Jul 2012 12:17:35 -0500

Jacob,
I suspected and mentioned in previous messages that some of these modifications may break nuances of the spec and may not be suitable for the reference implementation. I'll be happy if this exercise results in 1 or 2 innovations that can be incorporated into the ref imp or can be used by others in their work.
Thanks for the caution and interest,
DZ

David Zoller
COLSA Corporation

From: Jacob Green [mailto:[email-masked]]
Sent: Thursday, July 05, 2012 11:39 AM
To: Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]
Cc: [email-masked]
Subject: Re: [dtn-users] Improving performance in DTN2

Jacob

-------------------------------------------------------------------------------
Jacob Green
[email-masked]<mailto:[email-masked]>
Spread Concepts LLC.
-------------------------------------------------------------------------------

                                                dtnd

David Zoller
COLSA Corporation

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

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Fri, 6 Jul 2012 07:21:45 -0500

Yet another change in plans...

Jacob's insights have me contemplating some changes to my current structuring that I want to pursue after I finish with the planned multi-threading which would push things back a bit. So, I now think it best to go ahead and generate patch files for the ACS and BundleList mods so that Lee can get the paperwork and legal review started early next week. I feel pretty confident that those two mods do not impact the main  event queue processing and would make the reference implementation capable of decent sustained input under the right scenarios. I'll try to break the patch files  up into smaller non-overlapping units when I can to make it easier to select which pieces to include or easier to back out if there is an issue.

After that, I'll get back to what is turning into my public quest to conquer the 30 minute disconnect test or my public humiliation as the case may be :)

Cheers,
DZ

David Zoller
COLSA Corporation

Jacob

---

From: "Ivancic, William D. (GRC-RHN0)" <[email-masked]>
Date: Fri, 6 Jul 2012 07:28:45 -0500

I feel pretty confident that those two mods do not impact the main  event queue processing and would make the reference implementation capable of decent sustained input under the right scenarios.

David, What does this statement mean "Under the right scenarios"?  Does that imply this will only work for very specific traffic patterns or bundle sizes or something else?  What are the "right scenarios"?

- Will

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Fri, 6 Jul 2012 09:40:26 -0500

The one time that I know of that it cannot sustain input is when there is a large number of bundles pending for a destination and then the link becomes available. At that point the BundleDaemon processing is completely dominated by moving those pending bundles to the Link's queue and their transmission. I have not done the debugging yet to track down the exact bottleneck yet so that description is my gut feel.

It can sustain input if bundles are arriving and being transmitted continuously and also if there is no transmission and the bundles are just accumulating in the database.

David Zoller
COLSA Corporation

From: Ivancic, William D. (GRC-RHN0)
Sent: Friday, July 06, 2012 7:29 AM
To: Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]
Cc: [email-masked]
Subject: Re: [dtn-users] Improving performance in DTN2

- Will

---

From: "Ivancic, William D. (GRC-RHN0)" <[email-masked]>
Date: Fri, 6 Jul 2012 09:55:21 -0500

I don't know if this matters, but is the configuration a single Interface or two interfaces, One for input and one for output (i.e two ethernet cards)?

- Will

On Jul 6, 2012, at 10:40 AM, Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT] wrote:

The one time that I know of that it cannot sustain input is when there is a large number of bundles pending for a destination and then the link becomes available. At that point the BundleDaemon processing is completely dominated by moving those pending bundles to the Link’s queue and their transmission. I have not done the debugging yet to track down the exact bottleneck yet so that description is my gut feel.

David Zoller
COLSA Corporation

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Fri, 6 Jul 2012 10:00:09 -0500

It is a single interface but I don't think that it is network related at this time. The transmit rate during the impacted period is much lower than is seen during a continuous flow.

David Zoller
COLSA Corporation

From: Ivancic, William D. (GRC-RHN0)
Sent: Friday, July 06, 2012 9:55 AM
To: Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]
Cc: [email-masked]
Subject: Re: [dtn-users] Improving performance in DTN2

- Will

David Zoller
COLSA Corporation

---

From: Elwyn Davies <[email-masked]>
Date: Fri, 06 Jul 2012 17:15:50 +0100

Hi, David

On Fri, 2012-07-06 at 09:40 -0500, Zoller, David A. (MSFC-EO60)[HOSC
SERVICES CONTRACT] wrote:
> The one time that I know of that it cannot sustain input is when there
> is a large number of bundles pending for a destination and then the
> link becomes available. At that point the BundleDaemon processing is
> completely dominated by moving those pending bundles to the Link’s
> queue and their transmission. I have not done the debugging yet to
> track down the exact bottleneck yet so that description is my gut
> feel.

At least for table-based routers (i.e., most of the insternally defined
routers), the problem a.s. lies in TableBasedRouter::check_next_hop.

If the system knows about a link but it is not currently available, the
bundles will be queued up on the link's deferred_queue.  When the link
opens, the system iterates through the deferred queue, irrespective of
how large it is, creating the transmit blocks for all these bundles (or
at least until the sending queue fills up).  This blocks everything
probably for quite a time since transmit block building is a complex
process, especially if the bundles have multiple blocks.

Thinking about it, a relatively trivial fix for this would be to limit
the number of bundles that are transferred from the deferred queue to
the send queue on each call of check_next_hop.  It should probably be
greater than one to keep the link transmission busy, but limiting the
size of the send queue (in bundles) is probably quite efficient if the
link tends to go up and down, because then when it does go down there
are less xmit blocks to clear up.

This would automatically phase the transfer from deferred to send
because check_next_hop is called every time a bundle_transmitted event
is processed, so the send queue is replenished from the deferred queue
while bundles remain deferred. 

Actually *thinking more about this*, no code changes are needed here!
The queues already have configurable parameters to limit their sizes in
bundles and in octets.  Setting the qlimit bundles low water mark to 2
and the high water mark to (say) 4 would probably solve the problem.
Leave the octet high water mark limit as large as possible so that large
bundles can be handled.

The only other change this might need in order to work properly is in
TableBasedRouter::fwd_to_nexthop
where the test to see if the send queue is full should be augmented by
testing to see if there is anything in the deferred queue as well.  If
there is anything in the deferred queue already then any new bundles to
be sent should be added to the end of the deferred queue and not the
send queue whether or not there is space in order to ensure that the
sending order isn't screwed up.

This has got me wondering whether there is a lurking bug here - it is
conceivably possible that there is a race condition here where a bundle
send gets in between the bundle being removed from the send queue (to go
on in_flight) and the bundle_transmitted event being processed which
moves more deferred bundles on to the send queue.  The only symptom
would be that the sending order was very occasionally wrong.  The test
for bundles already on the deferred queue should probably go in in any
case. 

AFAIK, this one fix combined with setting the parameters correctly would
relieve the problem for all the internal routers except possibly PRoPHET
(that needs separate attention) but external routers would have to
consider how they handle the same issue.

Regards,
Elwyn

> 
>  
> 
> It can sustain input if bundles are arriving and being transmitted
> continuously and also if there is no transmission and the bundles are
> just accumulating in the database.
> 
>  
> 
> David Zoller
> 
> COLSA Corporation
> 
>          I feel pretty confident that those two mods do not impact the
>         main  event queue processing and would make the reference
>         implementation capable of decent sustained input under the
>         right scenarios. 
>         
>         
> 
>  
> 
> 
> David, What does this statement mean "Under the right scenarios"?
>  Does that imply this will only work for very specific traffic
> patterns or bundle sizes or something else?  What are the "right
> scenarios"?
> 
> 
>  
> 
> 
> - Will
> 
> 
>  
> 
>

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Sat, 7 Jul 2012 14:41:41 -0500

HI Elwyn,
I was not planning on looking at this until after I completed the patches for upload and the BD multi-threading, but after you dumped all of this excellent analysis on me, I had to put the debugging hat on and dig in :) You are definitely on the right track for part of it.

I ended up starting at the bottom of your post and working my way up after looking at the TableBasedRouter...

> This has got me wondering whether there is a lurking bug here - it is conceivably possible that 
> there is a race condition here where a bundle send gets in between the bundle being removed 
> from the send queue (to go on in_flight) and the bundle_transmitted event being processed 
> which moves more deferred bundles on to the send queue.  The only symptom would be that 
> the sending order was very occasionally wrong.  The test for bundles already on the deferred 
> queue should probably go in in any case.

Correct, I have seen this in my testing. I monitor a sequence counter in the payload on the receiving end and I sometimes see what I've been calling a jump and backfill. I modified the fwd_to_nexthop to add an initial test for the deferred list size being greater than zero and was surprised to find that the intake of bundles while disconnected could no longer keep up. The size() call locks the deferred list resulting in thread access competition. It looked like check_next_hop was called from pretty much everywhere so I tried simplifying fwd_to_nexthop to always add to the deferred list without checking size or queue space and let the check_next_hop calls take care of moving it to the queue. This seems to work just fine in all of the scenarios I've been able to generate.

It turns out that your first thought was necessary after all. Changing the default Link high and low water marks from 10 and 5 to 4 and 2 was not sufficient. Even with the marks that low, the check_next_hop was stuck processing the entire deferred queue. I suspect that the locking allows the Link to remove a bundle from its queue between each deferred bundle so check_next_hop always finds space available and continues. 
"suspect" = my usual half-xxxxx debugging as I stop after I learn enough to make progress until I find that I need to dig deeper.

I added your simple fix of limiting the number of bundles that can be moved to the Link queue during any one call. I chose the Link's high water mark as the max. That does at least let the loop exit and the event to be cleared.

The DTN server with just the bundle list patch and no multi-threading of the BundleDaemon:
After the 30 minutes accumulating 300000+ bundles, the receiving node was brought on line.
Input dropped to zero and transmit was in the 125 bundles/sec range.
About 15 or 20 seconds later, there were a couple of seconds of an input burst (500+ per sec) and then dropped back to zero.
For the next 10 minutes, input remained at 0 and transmit in the 125 range so I decided to hit it with the debugger.
The BundleDaemon had around 60,000 events queued and the ones I checked were BundleTransmitted events in the bundle id 36,500 range after 100,000 bundles had been transmitted.

The DTN server with the bundle list patch and a broken out BundleDaemon Input thread:
After the 30 minutes accumulating 300000+ bundles, the receiving node was brought on line.
Input dropped to 4 and transmit was in the 125 bundles/sec range.
It is not a complete halt!  Progress!!!

I guess, I'll get back to working on the patches for upload and return to this later.

Would you like to generate a patch for the TableBasedRouter or should I include it as one in my batch?
You could probably get it out there faster and it is based on your analysis.

Do all of you other US gov contactors/employees have to go through a legal review before you can submit a patch? Or maybe I shouldn't ask :)

Thanks for the help!
DZ

David Zoller
COLSA Corporation

-----Original Message-----
From: Elwyn Davies [mailto:[email-masked]] 
Sent: Friday, July 06, 2012 11:16 AM
To: Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]
Cc: Ivancic, William D. (GRC-RHN0); [email-masked]
Subject: Re: [dtn-users] Improving performance in DTN2

Hi, David

> track down the exact bottleneck yet so that description is my gut 

At least for table-based routers (i.e., most of the insternally defined routers), the problem a.s. lies in TableBasedRouter::check_next_hop.

If the system knows about a link but it is not currently available, the bundles will be queued up on the link's deferred_queue.  When the link opens, the system iterates through the deferred queue, irrespective of how large it is, creating the transmit blocks for all these bundles (or at least until the sending queue fills up).  This blocks everything probably for quite a time since transmit block building is a complex process, especially if the bundles have multiple blocks.

Thinking about it, a relatively trivial fix for this would be to limit the number of bundles that are transferred from the deferred queue to the send queue on each call of check_next_hop.  It should probably be greater than one to keep the link transmission busy, but limiting the size of the send queue (in bundles) is probably quite efficient if the link tends to go up and down, because then when it does go down there are less xmit blocks to clear up.

This would automatically phase the transfer from deferred to send because check_next_hop is called every time a bundle_transmitted event is processed, so the send queue is replenished from the deferred queue while bundles remain deferred. 

Actually *thinking more about this*, no code changes are needed here!
The queues already have configurable parameters to limit their sizes in bundles and in octets.  Setting the qlimit bundles low water mark to 2 and the high water mark to (say) 4 would probably solve the problem.
Leave the octet high water mark limit as large as possible so that large bundles can be handled.

The only other change this might need in order to work properly is in TableBasedRouter::fwd_to_nexthop where the test to see if the send queue is full should be augmented by testing to see if there is anything in the deferred queue as well.  If there is anything in the deferred queue already then any new bundles to be sent should be added to the end of the deferred queue and not the send queue whether or not there is space in order to ensure that the sending order isn't screwed up.

This has got me wondering whether there is a lurking bug here - it is conceivably possible that there is a race condition here where a bundle send gets in between the bundle being removed from the send queue (to go on in_flight) and the bundle_transmitted event being processed which moves more deferred bundles on to the send queue.  The only symptom would be that the sending order was very occasionally wrong.  The test for bundles already on the deferred queue should probably go in in any case. 

AFAIK, this one fix combined with setting the parameters correctly would relieve the problem for all the internal routers except possibly PRoPHET (that needs separate attention) but external routers would have to consider how they handle the same issue.

Regards,
Elwyn

---

From: Brenton Walker <[email-masked]>
Date: Wed, 25 Jul 2012 11:19:27 -0400

HI,
     Like Angela Hennessy wrote, we were looking at DTN2 performance a 
couple weeks ago too.  I just put up a summary of what we did with 
bundle processing throughput here:
https://wiki.umiacs.umd.edu/VirtualMeshTest/index.php/Space_Robots_CL
https://wiki.umiacs.umd.edu/VirtualMeshTest/images/8/85/SpaceRobotCL-wiki.pdf

It's probably stuff that people familiar with DTN2 already know, but 
maybe interesting to others.  It's not thorough or cleaned up, we 
haven't done much follow-up, and the tests were only for relatively 
small numbers of bundles (500-50,000).  This doesn't include the 
experiments Angela and others did with replacing lists with hashes.

Here's some highlights:
- we built a dummy convergence layer to isolate bundle processing and 
generation
- the bottleneck is disk access
- memorydb is a lie.  The payloads still get written to disk.
- optimizing payload storage for short bursts seems feasible
- optimizing event processing and database storage gets into oasys and 
is more confusing

Thanks,
Brenton

On 07/05/2012 12:16 PM, Zoller, David A. (MSFC-EO60)[HOSC SERVICES

---

From: "Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]" <[email-masked]>
Date: Thu, 26 Jul 2012 08:58:13 -0500

Hi Brenton,
Thanks for sharing your results and analyses. Creative use of a convergence layer!
> Dell optiplex 990 with 8GB RAM     - let me know when you want to trade development systems 

I've only worked with the "BundlePayload=DISK berkeleydb" option and your results looked low so I ran a couple of tests for comparison using the Sourceforge changeset 3550  version. I pushed in 5000 bundles (1316 bytes as opposed to your 1024 bytes) as fast as I could through the API and tracked how many per second it could handle. I also compared a solid state drive (SSD) with a regular hard drive (HD).

Sec	HD	SSD
1	461	908
2	379	715
3	326	555
4	324	419
5	311	402
6	265	372
7	231	317
8	260	326
9	229	310
10	213	294
11	247	282
12	204	100
13	203	
14	231	
15	177	
16	204	
17	169	
18	191	
19	171	
20	182	
21	22	

With the regular hard drive, 500 bundles were allocated and processed in well under 2 seconds and possibly 1 second since I don't have the resolution to indicate when in the first second it started. This compares to 22 seconds for 500 bundles in your results.

Were you starting with a clean database for each individual test? It does slow down the more bundles there are in the database.
What else might be impacting performance?

Looking forward to future results and the "easier-said-than-done" implementations :)
DZ

David Zoller
COLSA Corporation

-----Original Message-----
From: Brenton Walker [mailto:[email-masked]] 
Sent: Wednesday, July 25, 2012 10:19 AM
To: Zoller, David A. (MSFC-EO60)[HOSC SERVICES CONTRACT]
Cc: [email-masked]
Subject: Re: [dtn-users] Improving performance in DTN2

HI,

Here's some highlights:

Thanks,
Brenton