Note: Goby version 1 (shown here) is now considered obsolete. Please use version 2 for new projects, and consider upgrading old projects.

Goby Underwater Autonomy Project  Series: 1.1, revision: 163, released on 2013-02-06 14:23:27 -0500
goby-acomms: libqueue (Message Priority Queuing)

Table of Contents for libqueue:

Return to goby-acomms: Overview of Acoustic Communications Libraries.

Understanding dynamic priority queuing

Each queue has a base value ( $V_{base}$) and a time-to-live ( $ttl$) that create the priority ( $P(t)$) at any given time ( $t$):

\[ P(t) = V_{base} \frac{(t-t_{last})}{ttl} \]

where $t_{last}$ is the time of the last send from this queue.

This means for every queue, the user has control over two variables ( $V_{base}$ and $ttl$). $V_{base}$ is intended to capture how important the message type is in general. Higher base values mean the message is of higher importance. The $ttl$ governs the number of seconds the message lives from creation until it is destroyed by libqueue. The $ttl$ also factors into the priority calculation since all things being equal (same $V_{base}$), it is preferable to send more time sensitive messages first. So in these two parameters, the user can capture both overall value (i.e. $V_{base}$) and latency tolerance ( $ttl$) of the message queue.

The following graph illustrates the priority growth over time of three queues with different $ttl$ and $V_{base}$. A message is sent every 100 seconds and the queue that is chosen is marked on the graph.

priority_graph.png

Queuing tag structure

This section gives a brief outline of the tag structure of an XML file for defining the queuing for a DCCL message. The tags fit in the same file used for DCCL encoding and decoding; see DCCL tag structure for more information.

Interacting with the QueueManager

Instantiate and configure

The goby::acomms::QueueManager is configured similarly to the goby::acomms::DCCLCodec. You need to add queues to the goby::acomms::protobuf::QueueManagerConfig which is done by feeding it either XML files or goby::acomms::protobuf::QueueConfig objects. You also need to set a unique identification number in the range 1-31 for this platform (the "modem_id"). This is analogous to a MAC address.

goby::acomms::QueueManager q_manager(&std::clog);
goby::acomms::protobuf::QueueManagerConfig cfg;
cfg.add_message_file()->set_path("path/to/file.xml");
cfg.set_modem_id(1); // unique id 1-31 for each platform
q_manager.set_cfg(cfg);

Signals and (application layer) slots

Then, you need to do a few more initialization chores:

Operation

At this point the goby::acomms::QueueManager is ready to use. At the application layer, new messages are pushed to the queues for sending using goby::acomms::QueueManager::push_message. Each queue is identified by a unique goby::acomms::protobuf::QueueKey , which is simply the identification number of the queue (<id> for DCCL queues or the decimal representation of the first byte of a CCL message) and the queue type (goby::acomms::protobuf::QUEUE_DCCL or goby::acomms::protobuf::QUEUE_CCL ).

At the driver layer, messages are requested using goby::acomms::QueueManager::handle_modem_data_request, incoming messages are published using goby::acomms::QueueManager::handle_modem_receive, and acknowledgements are given using goby::acomms::QueueManager::handle_modem_ack. If using the goby-acomms drivers (i.e. some class derived from goby::acomms::ModemDriverBase), simply call goby::acomms::bind (ModemDriverBase&, QueueManager&) and these methods (slots) will be invoked automatically from the proper driver signals.

You must run goby::acomms::QueueManager::do_work() regularly (faster than 1 Hz; 10 Hertz is good) to process expired messages (goby::acomms::QueueManager::signal_expire). All other signals are emitted in response to a driver level signal (and thus are called during a call to goby::acomms::ModemDriverBase::do_work()).

Queuing XML Tags Reference

<ack>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ...
      <ack>true</ack>
    </queuing>    
  </message>
</message_set>

Description: boolean flag (1=true, 0=false) whether to request an acoustic acknowledgment on all sent messages from this field. If omitted, default of 1 (true, request ack) is used. Note that if a message has a destination of 0 (broadcast), an ack will never be requested regardless of the value set here.

<blackout_time>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ...
      <blackout_time>0</blackout_time>
    </queuing>    
  </message>
</message_set>

Description: time in seconds after sending a message from this queue for which no more messages will be sent. Use this field to stop an always full queue from hogging the channel. If omitted, default of 0 (no blackout) is used.

<max_queue>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ...
      <max_queue>1</max_queue>
    </queuing>    
  </message>
</message_set>

Description: number of messages allowed in the queue before discarding messages. If <newest_first> is set to true, the oldest message in the queue is discarded to make room for the new message. Otherwise, any new messages are discarded until the space in the queue opens up.

<newest_first>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ...
      <newest_first>true</newest_first>
    </queuing>    
  </message>
</message_set>

Description: boolean flag (1=true=FILO, 0=false=FIFO) whether to send newest messages in the queue first (FILO) or not (FIFO).

<value_base>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ... 
      <value_base>10</value_base>
    </queuing>    
  </message>
</message_set>

Description: base priority value for this message queue. priorities are calculated on a request for data by the modem (to send a message). The queue with the highest priority (and isn't in blackout) is chosen. The actual priority ( $P$) is calculated by P(t) = $V_{base} \frac{(t-t_{last})}{ttl}$ where $V_{base}$ is the value set here, $t$ is the current time (in seconds), $t_{last}$ is the time of the last send from this queue, and $ttl$ is the <ttl>. Essentially, a message with low <ttl> will become effective quickly again after a sent message (the priority line grows faster). See Understanding dynamic priority queuing for further discussion.

<ttl>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      ... 
      <ttl>120</ttl>
    </queuing>    
  </message>
</message_set>

Description: the time in seconds a message lives after its creation before being discarded. This time-to-live also factors into the growth in priority of a queue. see <value_base> for the main discussion on this. 0 is a special value indicating infinite life (i.e. <ttl>0</ttl> is effectively the same as <ttl> $\infty$</ttl>).

<queuing>

Syntax: 

<?xml version="1.0" encoding="UTF-8"?>
<message_set>
  <message>
    <queuing>
      <ack></ack>
      <blackout_time></blackout_time>
      <max_queue></max_queue>
      <newest_first></newest_first>
      <priority_base></priority_base>
      <priority_time_const></priority_time_const>
    </queuing>    
  </message>
</message_set>

Description: Represents the XML embodiment of the goby::acomms::protobuf::QueueConfig .

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends
Generated on Wed Feb 6 2013 19:25:22 for Goby Underwater Autonomy Project by   doxygen 1.7.6.1