Re: [Discuss-gnuradio] Proposed enhancements for data networking

[Michael Dickens]

Note to the discuss-gnuradio list: This is an ongoing discussion  
about BBN's proposed enhancements for dealing with packets.  While  
not all the previous discussion is here, the most relevant parts are.  
- MLD

A brief background:

I view data as coming in 2 types: "explicit" and "implicit" packets.

The former are the actual structured packets (e.g. a TCP/IP packet).   
The BBN proposal is to create a hierarchal scheduler which processed  
these packets, with a means for incorporating the current gr-graph  
inside a proposed m-block.

The latter are data streams, segmented arbitrarily (hence "implicit")  
into chunks (hence "packets") of data.  From this viewpoint, there  
are similarities between the data types, and it would not be  
difficult to create a "queue" which handles both types.  By handling  
both data types, I come up with a hybrid scheduler, one which has a  
primary routine to handle prioritization, pausing / stopping / (re) 
starting, and calling the different data types' "sub"-schedulers -  
which handle just that one packet and then return.

On Tuesday, June 6, 2006, at 03:18 PM, Eric Blossom wrote:
> On Tue, Jun 06, 2006 at 02:34:23PM -0400, Michael Dickens wrote:
> > Avoiding copying whenever possible is a good thing.  Copying takes
> > time, even using DMA, and time is latency which is a parameter that
> > needs to be kept minimized when doing SDR-oriented stuff.
> >
> > Ah ... so when doing "packet to stream" a const reference of the
> > packet's data is sent as the stream's output ... I had already
> > envisioned something like that ... anyplace else where it would be
> > used?  I was somehow imagining that the same packet would be passed
> > through an m-graph (not copying it, but rather a reference to the
> > packet's "class" or "structure"), and data added and changed in it
> > "in place" - much different that the current gr_block's method of
> > "always copy".  Is this also part of "zero copy" or is it really
> > limited to the "packet to stream" issue?
>
> We may not want to modify data in place, because other pieces of code
> may be hold references to it.  Also, the input and output sizes may be
> different.  That said, there's nothing in the plan that would prohibit
> you from modifying data in place.

Am I understanding correctly that the m-scheduler will basically do  
the same thing that the gr-scheduler does: it'll provide both an  
input and output packet reference to the called m-block, which will  
do processing, filling up the output packet as it goes?  Or is there  
something else which will be done?

> > > > Is there some reason why to create the whole new codes and not try
> > > > to integrate into what's already there?
> > >
> > > First off, we *really* want hiearchical scheduling.  That is, an
> > > m-block can fire off and run a flowgraph from beginning to end.   
> > > This
> > > gives us the ability to "wrap" for example a classic GR
> > > modulator, while controlling the input and harvesting the output.
> > > This allows the m-block to impose the "packetization" in such a way
> > > that the existing GR code doesn't notice.
> > >
> > > Second, the two abstractions really have different scheduling needs.
> > > The m-block is priority based (based on message priority), and
> > > theres's no need to check for anything like "Do I have enough  
> > > input" /
> > > "do I have room for the expected output".  I've considered this
> > > option, but didn't see a way to combine them that wasn't an extreme
> > > kludge.  Also, keeping them separate will allow m-blocks to be  
> > > reused
> > > outside of gnuradio.
> >
> > I can accept the argument that you want to keep the programming as
> > separate as possible so-as to be able to re-use m-blocks outside of
> > GR.  I think it is wise to keep the current stream-scheduler code
> > away from the new packet-scheduler code as much as possible since
> > they're different beasts.  But ...
> >
> > Why hierarchical and not "hybrid"?  I assume by the former you mean
> > that "doing packets" is the default, and "doing streams" is a sub-
> > method - which might involve a slight penalty w/r.t. how many
> > function calls it takes to execute a gr_block graph.
>
> I seriously doubt that it will be visible above the noise.

That's probably true for the means proposed for executing a gr-graph,  
so long as it doesn't happen too often.  More below in the comments  
and replies.

> > From your description above, you'll need 4 "schedulers" in one form
> > or another: "packet to packet", "stream to stream", "packet to
> > stream", and "stream to packet".
>
> There are only two schedulers.  The classic one
> (gr_single_threaded_scheduler), and the to be written m-block  
> scheduler.

[Yes, OK ... better understanding after reading your next reply below]

> > In a hierarchical scheduler, I'm
> > guessing that "p2p" would be the default method, "s2s" would be the
> > current scheduler operating as a subroutine of "p2p" which could be
> > #define'd in or out (or some similar way that might look nicer), and
> > the others would be glue to "make things work" between packets and
> > streams - maybe some very specific sinks or sources which "know" how
> > to deal with the various I/O necessities of "p2s" and "s2p".
>
> In the case of an m-block which contains an embedded flow graph (I
> suspect that this will be a small minority of all m-blocks), the
> handle_message callback of the m-block will pass any relevant data
> to the source that talks to the flow graph and then will invoke
> gr_single_threaded_scheduler (or something that calls it).
> When gr_single_threaded_scheduler returns, the callback will finish up
> whatever processing is required (if any) and will return (to the
> m-block scheduler which invoked the callback.)

Ah ... so the m-block itself invokes a gr-scheduler.  My initial  
reaction is to question why this needs to be the case: why not keep  
data processing in the blocks and leave scheduling to the scheduler?   
True, part of handling a message might be to invoke some other  
routine to work on the data .. and that routine could be in FFTW or  
the gr-scheduler.  Either way, it's interesting.  I'll think about  
this one a bit, as it wasn't obvious up front (to me).

As a related comment: I presume I could run a gr-graph alone inside  
the m-block ... there would be no need to "zero-copy" data from the m- 
block to the gr-graph since the sink and source would be in the gr- 
graph.  Am I correct here, or will some other method be used to run a  
gr-graph alone (without the need for the m-stuff)?

> > Why not have a main scheduler loop which checks the next block in the
> > queue for its type, then calls a subroutine to handle the execution
> > (memory management and such) for that block -this 1 time-.  Upon
> > return (with whatever information is appropriate to return from that
> > block's execution), the super-scheduler would do whatever it needs to
> > do re: prioritization and timing, then call the sub-scheduler for the
> > highest priority block in the queue.  In this manner, all blocks in a
> > graph would be executed over, no matter their type or priority.
>
> I'm not following this.

Think of it (roughly) as moving the gr-scheduler execution from the m- 
block - as in BBN's proposal - to the a sub-scheduler of the super- 
scheduler ("super" in the sense of a scheduler that calls the other  
ones) ... processing one "data block" at a time (whichever is the  
highest priority data block - either an explicit packet or a  
"implicit packet" stream).  If the highest priority data in the queue  
is a explicit packet (which requires packet-only processing), then  
the super-scheduler calls the "p2p" scheduler to deal with this  
packet.  If the highest priority data in the queue is an implicit  
packet (which requires stream-only processing) then the super- 
scheduler calls the "s2s" scheduler to deal with this stream data.   
Upon return (with whatever appropriate arguments are returned), then  
the super-scheduler re-prioritizes the data to be processed.  Repeat  
until either all data is processed or the process is killed.

> If I've got high priority m-blocks, I want to
> run *only* them before taking a look at anything else.

This could be done by setting the priority correctly.  The super- 
scheduler takes care of that.  As -any- type of sub-scheduler returns  
after processing a given block type, the super-scheduler reorders the  
current data "to process" list such that the highest priority data is  
next in the queue ... the actual implementation would probably be  
inserting the returned block into the queue at the correct priority  
location.  Either way, very-high-priority data (of any type) could be  
run through processing quickly, while ignoring all other data  
temporarily.

> > There isn't a need to "wrap" m-blocks around gr_blocks ... data in
> > the form of packets or streams would be moved appropriately by the
> > sub-scheduler for its given block type.  m-blocks and gr_blocks could
> > live "side-by-side" in the same graph.  The code could be easily
> > tweaked (#def'd or whatever) to be m-block specific, and thus could
> > be made to work outside GR.
>
> [#ifdef considered harmful...]

No smiley ... hmmm.  So how else would m-block and gr-stuff be kept  
separate if an m-block method is calling gr-scheduler?  I'm going  
back to the desire to keep the programming separate so that m-blocks  
could be used independent of GR.  Ah ... a special block type which  
"knows" how to execute the gr-scheduler, and does nothing else, yes?   
If not using GR, then that file just isn't compiled.  That would be  
clever, and indeed much better separation of programming than the  
hybrid model I'm proposing.

> The whole point of this exercise is to allow m-blocks to execute GR
> flow graphs as "subroutines".

Why require m-blocks be the place where gr-graphs are called from?   
Why not incorporate both types of graphs together into one graph?   
It's easier to check on "connect()" (if you choose to use a static  
graph, or even if dynamic changes are allowed ... even allows for  
dynamic changes to the gr-graph blocks) ... speaking of which, how  
are the gr-graphs checked?  I suppose they're connected first (which  
does the checking), then the source and sink are passed into the m- 
block in which they will be processed?  Thus a special type of m- 
block which knows how to handle gr-graphs?  [See above for the  
"lightbulb" ;-]  And a special type of gr-block "source" and "sink"  
would need to be made to handle "p2s" and "s2p" zero-copy, yes?

> This behavior allows us to associate
> metadata with incoming and outgoing messages.

There is no reason meta-data couldn't be passed to a stream block ...  
it would by default just be ignored (not written to or read from,  
except for timing of block execution and anything else a generic  
block type would want).  Of course, new gr-blocks could be written to  
use the meta-data if they wished.

A difference between the hierarchal and hybrid designs is that the  
latter augments current gr-blocks with the basic properties of m- 
blocks ... latency timing, meta-data availability, whatever would be  
common between both block types.  While I like the current gr-blocks,  
I would like them even more if they "knew" something about time and  
the data they were processing.  I see no reason why to not allow meta- 
data for streams ... could be useful (e.g. "this is a MP3 data VBR  
192 kpbs, joint stereo" ... and the receiver could dynamically [re] 
configure a graph to deal with that particular set of meta-data).

> If they weren't nested,
> how would the m-block know when the graph had completed generating the
> data?

In the hierarchal design as proposed, there would be no way to know  
when the graph had completed.  Hence that design requires that the m- 
block call the gr-scheduler.

In the hybrid design, the m-block would have no knowledge of  
completion ... if wouldn't need that knowledge, just as gr-blocks  
don't.  That knowledge would reside in the scheduler, as it currently  
does - just an upgraded scheduler to handle all block types ... a  
more integrated scheduler than that in the current proposal, which  
has both benefits and drawbacks.

> Also note that the m-block handle_message callback must "run to
> completion".  That is, it is not allowed to block in the callback
> waiting for something in the outside world.
>
> > I haven't actually implemented such a hybrid scheduler, but I've
> > thought about it enough to believe it can be done without too much  
> > to-
> > do.  While it does involve re-writing a bit of GR's scheduler code, I
> > think the add-on benefits would be worth the effort.  For example, in
> > what I envision, the current gr_block's would be augmented with the
> > basics needed to deal with time-based processing: min/max/avg latency
> > computation, min/max/avg throughput computations, and/or anything
> > else which would be generically required for any type of block no
> > matter the data I and O types.
>
> > I can certainly write more about this, and might even possibly do
> > some quick programming to see if/how well it would work.  Thoughts?
> > Are these really the same thing, or am I just dreaming about mine?  
> > - MLD
>
> I'm not sure that I'm following what you are saying...
> But I'm interested in hearing more ;)

Ah, the smiley!  I like this discussion - though it does take time to  
read and digest - since I think it's the future of GR in many ways,  
no matter which scheduler type gets implemented.  I definitely am  
getting a better understanding of the proposed enhancements than from  
just reading the chapter.  Hence I will re-read it & see if there are  
points which could be clarified ... tomorrow.

> How do you propose that m-blocks and gr-blocks interact?

They interact in the same was gr-blocks do in a gr-graph right now.   
One could create a graph which links p_source -> p2p -> p2s -> s2s ->  
s_sink.  There could be multiple p2p's linked together, or multiple  
s2s's ... just one p2s between them.  It's possible to use the "zero- 
copy" as mentioned in the proposal for the p2s part (and s2p part)  
instead of an actual block, which might be the default, but it could  
also be possible to create a specific block type which handles the  
initial and eventual conversion to/from packets and streams.

> Here's a mini use case:
>
> A frame (packet) is passed to us from the MAC layer.  The metadata
> associated with it specifies a set of attributes including power level
> to use, modulation, priority,... and the time that it is to sent on  
> the
> air.
>
> A few ticks later, the MAC sends us a higher priority frame.  The new
> frame should be modulated and queued prior to the previous packet if
> possible.
>
> We're thinking about "pre-modulating" the frames into samples, and
> then handling the ultimate scheduling for the transmission of the
> resulting samples in yet another m-block that would handle the
> prioritization, QoS, and precise timing requirements...
>
> The ultimate timing control will be in the USRP or other attached
> hardware.  We plan on using inband signaling on the USB to indicate
> when the samples that correspond to a particular frame are to be
> transmitted.  This means we'll have a queue of modulated frames
> (variable length groups of samples that are associated with a given
> high-level frame) in the USRP, not just a FIFO of samples.

i believe that all of this would remain the same, no matter the  
scheduler type.