[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Discuss-gnuradio] Packet Radio

From: dlapsley
Subject: Re: [Discuss-gnuradio] Packet Radio
Date: Tue, 4 Apr 2006 10:09:42 -0400

Hi Eric,

Thank you for the feedback. We will incorporate your comments into
a new revision of the document that we should have out soon.

Timing and scheduling seem to be the hardest issues, so we'd like
to think about them a bit more and then discuss on the list.



On Apr 1, 2006, at 2:35 PM, Eric Blossom wrote:

On Sat, Apr 01, 2006 at 11:09:18AM -0500, dlapsley wrote:
On Apr 1, 2006, at 2:42 AM, Eric Blossom wrote:
On Fri, Mar 31, 2006 at 11:42:37PM -0500, dlapsley wrote:

The document is available at


We would appreciate feedback, sent to gnuradio-discuss, or feel free
to email us privately if there's some reason gnuradio-discuss isn't


For example, Table 4.2 says that "Timestamp" carries the value of the
transmit-side "sampling-clock" at the time this message was
transmitted.  If I'm a "source m-block" generating, say a test
pattern, what do I put in the Timestamp field?  Where do I get the
value?  Consider the case where the "real" sampling-clock is across
USB or ethernet.

One option would be to have a sample counter in the source m-block
that is incremented for every data sample that is transmitted.
The value of that sample counter when you transmit a message is what
would be written into the timestamp field.

I believe this assumes a model where m-blocks have a more-or-less
uniform flow through them.  I believe this assumption is invalid.  In
fact, I thought the whole point of m-blocks was to better deal with
discontinuous flow. E.g., packets arrive at random times. The m- block
isn't running if there isn't something for it to do.  Yet, the real
world sample clock marches on...

The timing message ties wall clock time to this sample. Every block
in the flow graph would know the relationship between wall clock time
from the periodic timing messages which contain an NTP timestamp and
the equivalent RTP timestamp (i.e. sample count). Sampling frequency
can also be used to work out the time corresponding to a given sample
given a single timing/synchronization message.

I don't think this works in a world of discontinuous transmission or
reception.  We aren't streaming video ;)

If I want to tell the ultimate downstream end of the pipeline not to
transmit the first sample of the modulated packet until time t, how do
I do that?  That's essential for any kind of TDMA mechanism.

The most direct way is through the signaling interface. The MAC layer
(or other client) can send a signal enabling/disabling transmission at
the end of the pipeline at the appropriate point in time.

For this particular example, I think that the time, or a proxy for the
time (e.g., Transmit this packet in TDMA Slot N of M), should be in
the metadata attached to the high-level packet.

Perhaps we're talking past each other here.  Or we're conflating the
playout time with a desire to figure out how to schedule the m-blocks
so that the right thing occurs at the right time.

The important part is getting the timing semantics right at the
MAC/PHY boundary and at the "soft PHY / hard PHY" boundary.
Everything else is an implementation detail.

I'm not sure we've got this pinned down yet.

Another way to do it would be to have some form of "playout buffer" at
the end of the pipeline that buffers packets until it is time for
them to be sent.

Yes, and there's a (perhaps unacknowledged) requirement to minimize
latency.  The latency in this part of the system directly impacts any
MAC control loop.

In this case the timing transfer mechanism would be used to enable
each block to measure the latency from the time the packet entered
the top of the pipeline until it arrived (or left) the block.

My thought is that the latency through the blocks is going to vary all
over the place, and from packet to packet.  E.g., one packet may come
in with metadata indicating "needs to get there with
high-probability" or at a different level of abstraction "use XYZ FEC
and ABC modulation".  The next packet has a different metadata.  The
downstream flow for these two case may be completely different.

Yes, I understand that you could model this based on worst case and/or
some probability distribution.  Is that the goal?

These latencies would be exposed to the top level m-block scheduler
which could then allocate processing time to blocks based on these
latencies in order to ensure that some threshold was not
exceeded. Typically, you could imagine the processor just looking at
the end to end delay and scheduling processing to keep that below a
certain threshold. In a sense, the scheduler does coarse grain
scheduling to ensure the end to end delay does not go beyond some
tolerance, while the playout buffer does fine grained scheduling.

[The final playout buffer is in the attached hardware]

OK, I get the basic goal.
Not sure I agree with all the RTP/RTCP/NTP...  Can't the m-scheduler
just *measure* the execution time of each m-block?

In general, I'm not following this section.  I'm not sure if you're
trying to figure out the real time required through each m-block
and/or if you're trying to figure out the algorithmic delay through
each block, and/or if you're trying to figure out the NET to NET
delay between multiple nodes, ...

It's the first two.


The initial thought is just to re-use the semantics and format of
RTP/RTCP for transferring timing information between elements of a

Seems like a solution looking for a problem.

There are a couple of options. One option would be to to figure out
the wall clock delay between two blocks within a flow graph (could
imagine that typically they would be endpoints of a pipeline). This
way we can make sure the delay through a flow graph stays within
limits by scheduling blocks appropriately.

Seems reasonable.

Another option would be to measure the end to end delay between some
process in the MAC (or other controlling entity) and the bottom of a
pipeline in the PHY.  There could also be a control loop here to
ensure that the end to end delay requirements are not exceeded.


We'll work on making this section clearer and get a new revision out
next week.

Sounds good.  I suggest starting with some use cases for the MAC/PHY
interface and the soft-PHY/hard-PHY interface.

I'm particular interested in sorting out the idea of time.

I think that "priority" originates in the MAC.  It may tell us that a
particular packet has priority P.  The MAC is going to be handing us
multiple outstanding packets, right?  We're going to flow control it
somehow, but I'm assuming that it may send us a packet at time T+1
that has higher priority than one sent at time T.  When/where/how do
we handle this?

I think the soft-PHY/hard-PHY interface is pretty straight forward.
You've got to assume that the low level hardware is pretty dumb.  In
the receive direction, assume that the hardware gives you fixed length
packets of N samples with a header containing it's sample counter
value corresponding to the first sample of the packet.

In the transmit direction, it might be slightly more complicated.
Assume fixed length packets with a header that has a "do not transmit
before sample counter time T", as well as a few other bits including
things like, "this packet is the beginning of a frame", this "packet
is the middle of a frame", "this packet is the end of a frame", "this
packet has N valid samples".  The packet header probably also contains
attributes such as transmit power, but probably only in the packet
that corresponds to the first fragment of a frame.

The soft-PHY/hard-PHY packets also carry some indication of "channel"
which is a label for a particular path in the h/w from the interface
to/from an antenna. [Probably not relevant to the timing problem.]

Also, an example of how we'd map whatever you're thinking about on to
something that looked like a USRP or other h/w would be useful.

Will do.

I guess I'm missing the overall statement of intention. I.e., what do
the higher layers care about, and how does your proposal help them
realize their goals?

The main goal of section 4.5.5 is to provide mechanisms that will
bound the time it takes for a request to make it all the way to the
bottom of the PHY and to enable real-time scheduling/playout of data
at the bottom of the PHY.



General questions about metadata: Does an m-block just "copy- through"
meta-data that it doesn't understand?

Yes. Ideally, we would just be passing references/pointers so there
wouldn't need to be any copying. You could also imagine blocks
"popping" off profiles/sections of metadata specific to them.

Or in the general case, why not just make it *all* key/value pairs?
Why restrict yourself to a single distinguished "data portion"?

Sure. That's a nice way to think about it. It would also be nice to
maintain a hierarchy of metadata so that there was some structure
to it (e.g. grouping by profiles or block type).

Sounds good.

Section 4.5.8: Scheduler.

I'm not sure I follow Figure 4.8.  Perhaps once I understand the
timing stuff it'll make more sense.

We'll work on making this clearer.


With regard to signals and control processing, it seems like it would
make sense to use the same mechanism to communicate with existing
gr_blocks.  E.g., a carrier sense block implemented in the flow graph
needs to be able to send a transition signal and receive a
threshold setting.  [I'm not attached to the existing msg / msg queue
stuff, it just seemed like the simplest thing that could possible

Also, in the definitions in Table 4.1, if a "message" is the smallest
block of information that can be processed by an m-block, what do you
call the data that is associated with a "signal" or "control"?

I'm also not clear about how or when you process the scheduling of
control/signals versus data+metadata.  When does an m-block handle the
signals/control versus the data + metadata?

Do you envision a different mechanism?  If so, why?

(Can we pick different nomenclature for "signals"?  It's seriously
overloaded in the POSIX environment.)

At a higher level of abstraction, why would an m-block have different
classes of ports?  Why don't they *all* accept and/or send
"messages" containing "data + metadata".  The current design seems
like it's being prematurely narrowed and special cased, when one
simple abstraction seems to cover all the cases.  They could of course
have a ports labeled "control" and "signal", but do we really want a
different implementation?

Also, for your use cases and pictures, I'd start with m-blocks
that contain multiple input and output ports for "data + metadata",
and then handle single-in / single-out as a specialization.

It may be that this latency / scheduling problem is blown way out of
proportion.  We've got to assume we've got sufficient cycles to
execute the transmit and receive paths in the worst case, or else
we're hosed.  Buy faster hardware / fix the signal processing until
the problem goes away.

Then, you can get priority scheduling within the m-block universe by
attaching a priority to each message.  I'm assuming the "single model
of the universe where everything is a message containing
data+metadata, including the so-called signal and control ports".
Then just implement a priority queue for each port.  The priority
assigned each m-block at time t is the max(over-all-of-its-port- queues).
Then just pick the highest priority m-block and run it.  No problem.
The latency is going to be what it's going to be.  We're doing what
the MAC asked us to do in the order it asked us to do it.

Then, we're left with the high level problem of hitting the given TDMA
slot, but that gets sorted out by the tail end of the m-block pipeline
that feeds the physical h/w with the appropriate frame + timestamp.

In summary, isn't an m-block just an actor that wakes up when told and
processes events/messages in it's queue(s) and generates
events/messages that get sent someplace else?  If so, then this is a
well understood problem, with a well understood solution, and no
reentrancy problems ;)  Composing them falls out nicely too.  We also
get transparent scaling in the SMP/multi-core environment.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]