Table Of Contents
Table Of Contents

Queueing Model

Overview

The INET queueing model provides reusable modules for various application areas. These modules can be used to build application traffic generators, queueing models for MAC protocols, traffic conditioning models for quality of service implementations, and so on.

Usage

The queueing modules can be used in two very different ways. For one, they can be connected to other INET modules using gates. In this case, the modules send and receive packets asynchronously as many other INET modules do. For example, application packet source and packet sink modules are used this way. The other way to use them is to directly call their C++ methods through one of the C++ interfaces of the contract package. In this case, the queueing modules are not connected to other INET modules at all. For example, MAC protocol modules use packet queues as submodules through C++ method calls.

Model

Most queueing model elements provide simple behaviors, so they are implemented as simple modules. But queueing elements can also be composed to form more complex behaviors. For example, priority queues, request-response based traffic generators, traffic shapers are usually implemented as compound modules. In fact, some of the queueing model elements provided by INET are actually realized as compound modules using composition.

The queueing model can be found in the inet.queueing NED package. All queueing model elements implement one or more NED module interfaces and also the corresponding C++ interfaces from the contract folder. As a minimum, they all implement the IPacketQueueingElement interface.

Operation

Internally, connected queueing model elements most often communicate with each other using synchronous C++ method calls without utilizing handleMessage(). The only exception is when an operation takes a non-zero simulation time, such as when the processing of a packet is delayed. The connections between the model elements are simply used to designate the caller and the callee. Other modules can still send and receive messages through the gates of queueing model elements, but only Packet instances are allowed.

There are two new important operations on queueing model elements defined in IPassivePacketSource and IPassivePacketSink. Packets can be pushed into gates and packets can be pulled from gates. Both of these operations are synchronous, they either finish successfully or throw an exception. The main difference between pushing and pulling is the subject of the activity. In the former case, when a packet is pushed, the activity is initiated by the source of the packet. In contrast, when a packet is pulled, the activity is initiated by the sink of the packet. In both cases, the passive elements can be asked via separate methods to tell if they can be pushed or pulled on a specific gate in their current state either with respect to a specific packet or any packet thereof.

Queueing model elements can be divided into two categories with respect to the operation on a given gate: passive and active. The passive model elements are pushed into and pulled from by other connected modules. In contrast, the active model elements push into and pull from other connected modules as they see fit. They implement the interfaces IActivePacketSource and IActivePacketSink.

The active queueing elements take into consideration the state of the connected passive elements. That is, they push or pull packets only when the passive end is able to consume or provide, respectively. The queueing model elements also validate the assembled structure during module initialization with respect to the active and passive behavior of the connected gates. That is, active output gates must be connected to passive input gates, and active input gates must be connected to passive output gates.

The mechanism that allows passive modules to prevent a push or pull operation of an active module is called backpressure. For example, a queue that is full, and which doesn’t have a configured packet dropping mechanism generates backpressure towards the connected active packet source. This backpressure prevents the source from pushing more packets into the queue. Similarly an empty queue generates backpressure towards the connected active server component. The backpressure prevents the server from pulling more packets from the queue. In general, backpressure can be generated by modules on their own any time they want, it can be transferred from one gate to another, or it can be simply absorbed by a module. For example, a scheduler transfers the backpressure from its input gates towards its output gate, and similarly a classifier transfers backpressure from its output gates towards its input gate. Finally, modules can choose if they consider or ignore the backpressure from the connected modules. In the latter case, the push and pull operations may cause a runtime error.

Pushing a packet into a gate (and similarly pulling a packet from a gate) can have far reaching consequences by triggering a chain of operations potentially by passing through multiple connected elements. For example, pushing a packet into a classifier will immediately push the packet into one of the connected queueing elements, and will also potentially lead to additional operations on further connected elements. Similarly, pulling a packet from a scheduler will immediately pull a packet from one of the connected queueing elements, and will also potentially lead to additional operations on further connected elements.

In general, the following equation about the number of packets holds true for all queueing model elements:

#created + #pushed - #pulled - #removed - #dropped = #available + #delayed

Sources

These modules act as sources of packets. An active packet source pushes packets to its output. A passive packet source returns a packet when it is pulled by other queueing model elements.

Sinks

These modules act as sinks of packets. An active packet sink pulls packets from its input. A passive packet sink is pushed with packets by other queueing model elements.

  • ActivePacketSink: generic sink that collects packets periodically

  • PassivePacketSink: generic sink that consumes packets as they arrive

  • RequestConsumer: processes incoming requests in order and initiates response traffic

  • PcapFilePacketConsumer: writes packets to a PCAP file

  • FullPacketSink: doesn’t pull packets and doesn’t allow packets to be pushed

Queues

These modules store packets and maintain an ordering among them. Queues do not delay packets, so if a queue is not empty, then a packet is always available. When a packet is pushed into the input of a queue, then the packet is either stored, or if the queue is overloaded, it is dropped. When a packet is pulled from the output of a queue, then one of the stored packets is returned.

The following simpler equation about the number of packets always holds true for queues:

#pushed - #pulled - #dropped - #removed = #queueLength = #available

  • PacketQueue: generic queue that provides ordering and selective dropping

    parameterizable with an IPacketComparatorFunction and an IPacketDropperFunction

  • DropHeadQueue: drops packets at the head of the queue

  • DropTailQueue: drops packets at the tail of the queue, the most commonly used queue

  • PriorityQueue: contains several subqueues that share a buffer

  • RedDropperQueue: combines random early detection with a queue

  • CompoundPacketQueueBase: allows building complex queues by pure NED composition

Buffers

These modules deal with memory allocation of packets without considering the ordering among them. A packet buffer generally doesn’t have gates, and packets are not pushed into or pulled from it.

  • PacketBuffer: generic buffer that provides shared storage between several queues

    parameterizable with an IPacketDropperFunction

  • PriorityBuffer: drops packets based on the queue priority

Filters

These modules filter for specific packets while dropping the rest. When a packet is pushed into the input of a packet filter, then the filter either pushes the packet to its output or it simply drops the packet. In contrast, when a packet is pulled from the output of a packet filter, then it continuously pulls and drops packets from its input until it finds one that matches the filter criteria.

Classifiers

These modules classify packets to one of their outputs. When a packet is pushed into the input of a packet classifier, then it immediately pushes the packet to one of its outputs.

Schedulers

These modules schedule packets from one of their inputs. When a packet is pulled from the output of a packet scheduler, then it immediately pulls a packet from one of its inputs and returns that packet.

Servers

These modules process packets in order one by one. A packet server actively pulls packets from its input when it sees fit, and it also actively pushes packets into its output.

  • PacketServer: serves packets according to the processing time based on packet length

  • TokenBasedServer: serves packets when the required number of tokens are available (token generators are described later)

Markers

These modules attach some information to packets on an individual basis. Packets can be both pushed into the input and pulled from the output of packet markers.

  • PacketLabeler: generic marker which attaches labels to matching packets

    parameterizable with an IPacketFilterFunction

  • ContentBasedLabeler: attaches labels to packets based on the data they contain

  • PacketTagger: attaches tags such as outgoing interface, hopLimit, VLAN, user priority to matching packets

    parameterizable with an IPacketFilterFunction

  • ContentBasedTagger: attaches tags to packets based on the data they contain

Meters

These modules measure some property of a stream of packets. Packets can be both pushed into the input and pulled from the output of packet meters.

  • ExponentialRateMeter: Measures the packetrate and datarate of the packet stream. Takes older packets into account with an exponentially decreasing weight

  • SlidingWindowRateMeter: Measures the packetrate and datarate of the packet stream. Takes packets into account only in the given time window

Token generators

These modules generate tokens for other modules. A token generator generally doesn’t have gates and packets are not pushed into or pulled from it.

Conditioners

These modules actively shape traffic by changing the order of packets, dropping packets, delaying packets, etc. Note that the capabilities of conditioners also includes delaying, which queues are not capable of. Traffic conditioners are generally built by composition using other queueing model elements.

  • LeakyBucket: generic shaper with overflow and configurable output rate

  • TokenBucket: generic shaper with overflow and configurable burstiness and output rate

Other queueing elements

There are also some other generic queueing model elements which don’t fit well into any of the above categories.

  • PacketGate: allows or prevents packets to pass through, either pushed or pulled

  • PacketMultiplexer: passively connects multiple inputs to a single output, packets are pushed into the inputs

  • PacketDemultiplexer: passively connects a single input to multiple outputs, packets are pulled from the outputs

  • PacketDelayer: sends received packets to the output with some delay independently

  • PacketCloner: sends one copy of each received packet to all outputs

  • PacketHistory: keeps track of the last N packets which can be inspected in Qtenv

  • PacketDuplicator: sends copies of each received packet to the only output

  • OrdinalBasedDuplicator: duplicates received packets based on their ordinal number