This commit adds an implementation of the CoDel algorithm based on
the reference pseudocode presented in
http://queue.acm.org/appendices/codel.html. Instead of abstracting
the queue itself, the implementation provides a time stamp based
automaton which is invoked after a package has been dequeued.
Note that the modifications of the algorithm shown in
https://tools.ietf.org/html/draft-ietf-aqm-codel-01 are not yet
applied.
Sponsored-by: On-Waves ehf
Currently the values Bmax/R default MS are computed under the
assumption than min(4, N_PDCH) DL slots are allocated for an MS, even
if multislot assignment is not enabled.
This commit changes the computation to assume 1 DL slot if algorithm
A is selected or the dynamic algorithm is used and has disabled
multislot assigment due to high load.
Sponsored-by: On-Waves ehf
Currently there is no persistent state being used in
alloc_algorithm_dynamic. So algorithm B is even used in persistent
high usage scenarios. If there are many active TBFs, multislot
assigments are not fair, because MS of a "higher" multislot class get
higher troughputs. On the other hand, as long as all PDCH are busy no
bandwidth will be wasted even if all MS use algorithm A.
This commit modifies alloc_algorithm_dynamic to disable algorithm B
when that call fails. It then keeps it disabled until there is a
single PDCH which is idle (it is considered idle, if there is at most
one active DL TBF assigned to it).
Sponsored-by: On-Waves ehf
Currently the value of trx_no2 is used in the assertion, even if the
call to tfi_find_free has failed.
This commit fixes the asserted expression to only compare the trx_no
values if the function call has succeeded.
Sponsored-by: On-Waves ehf
Currently if both an uplink and a downlink TBF are to be allocated by
alloc_tbfs() and the second allocation fails, the first TBF is not
freed.
This commit changes the recursive function to free the TBF if the ms
variable has been changed to NULL.
Sponsored-by: On-Waves ehf
Indicate those slots with lower case letters that do not have a spare
TFI for the other direction if such a TBF has not been attached to
the MS object yet.
Sponsored-by: On-Waves ehf
Currently algorithm A can select an TBF even when there is no free
TBF in the reverse direction. While this does not necessarily lead to
an allocation failure, the probabily is higher. In addition, the
current slot reservations are not taken into account.
This commit changes the selection algorithm to prefer slots where TFI
are available in both directions and which are less reserved.
Sponsored-by: On-Waves ehf
Currently each tx_window combination is checked only once by using a
set containing the sets of TX slots that have been checked already.
This approach does not ensure, that num_tx and ul_ts really match the
tx_window being tested. This does not make a difference with the
current test cases probably because num_tx starts with 1 and is
increased each iteration. Since the bitmap optimization is equivalent
to a cache optimization strategy that only uses tx_window as key. On
the other hand, ul_ts, num_tx, and rx_mask cannot be derived from
tx_window, but these values are also refered to after the call to
test_and_set_bit(). This makes it difficult to prove that correctness
of the caching. While this will not lead to a defect, the results
might be less optimal.
This commit changes the optimization strategy to skip all tx_window
where ul_ts and ul_ts+num_tx-1 are not both contained. This provides
a similar degree of optimization like the set approach (only the
iteration with num_ts == 8 is not optimized, which only applies to to
ms class 18 and 29 MS) but ensures that the values of the related
variables have a clear relationship.
Note that the bitset based optimization for rx_window does not suffer
from a possible cache inconsistency, since only tx_window and
rx_window (tx_slot_count and rx_slot_count can be derived from the
windows and thus are covered by the cache key) are used after the call
to test_and_set_bit(). tx_window is constant over the whole lifetime
of the cache.
Sponsored-by: On-Waves ehf
The dynamic algorithm behaves like B until there are no TFI left.
This commit changes the default algorithm to to former.
Ticket: #1934
Sponsored-by: On-Waves ehf
The idea behind this meta algorithm is to automatically select one of
the other algorithms based on the system state. Basically algorithm B
will be selected if the PDCH usage is low to improve throughput and
latency. Algorithm A will be selected to support more concurrent MS.
This commit adds a first simple state-less version of this algorithm
that always tries B first and only if that fails A is tried
afterwards.
The following VTY command is added to the 'pcu' node:
- alloc-algorithm dynamic
Ticket: #1934
Sponsored-by: On-Waves ehf
This part of algorithm_b has already been disabled. Further work may
depend on this, but it is going out of sync. So this commit removes
it completely.
Sponsored-by: On-Waves ehf
Currently these algorithms modify other objects (MS, TBF, PDCH) even
if the allocation will fail later on. To implement an algorithm that
dynamically tries another algorithm on failure (e.g. A after B), the
first (failing) algorithm should not change or damage anything.
This commit refactors algorithm A and B to delay the actual allocation
until it is known that the allocation will not fail.
Ticket: #1934
Sponsored-by: On-Waves ehf
Currently this code path is only used, if an allocation has been
taken place in a former call to an allocation algorithm function.
If this was for an DL TBF, the first common TS was selected,
otherwise the least used common TS was selected for an UL TBF.
The shrinking of the UL set (to 1<<first_common_ts) is done in the
latter case.
This commit removes an additional code path that aligns the UL set to
first_common_ts, because it has no more influence on the set of
common TS after both UL and DL TBF have been allocated.
Sponsored-by: On-Waves ehf
MS iniated TCP connections generally result in a sequence
of short time UL and longer lasting DL TBFs, being interleaved
between several MS. This scenario is not covered by the existing
tests.
This commit adds a test, that allocates as man as possible TBFs
several times with different test modes without clearing the BTS (and
thus the TBF list) in between. The number of allocated DL TBFs in
each round is expected to be constant.
Sponsored-by: On-Waves ehf
Currently all TBFs are deleted after the allocation loop finishes.
This make it difficult to interleave the TBF allocation like it
happens with real MS.
This commit refactors the allocation loop into alloc_many_tbfs and
adds support for TLLIs, which are derived from the counter value and
used to retrieve an old MS object if alloc_many_tbfs is called a
second time.
Note that this does not make a difference for the existing tests.
Sponsored-by: On-Waves ehf
Currently there is no simple way to determine, whether the MS object
protected by a guard will continue to exist after the guard object is
destroyed.
This patch adds a is_idle() method that will return true if the MS
object is just kept by the guard from being idle. In that case, the
MS object would either be deleted or return true for
GprsMs::is_idle() after the guard's destruction, provided that no
TBF attachment took place in between.
Sponsored-by: On-Waves ehf
Currently the TBFs are registered in a TFI indexed array within the TRX
objects. TBFs can be searched globally by TFI and TRX number. This
conflicts with the use of the same TFI for different TBF on different
PDCH. This use case requires the specification of the PDCH as
additional search dimension.
This commit moves the TFI index TBF arrays into the PDCH objects. The
related methods are updated accordingly.
Ticket: #1793
Sponsored-by: On-Waves ehf
Currently the TFI are managed per TRX, thus only a maximum of 32 TBF
per direction and per TRX are possible simultaneously.
This commit modifies algorithm_a() to allow the sharing of TFI
between different PDCH. Since algorithm A only assigns a single slot
to each TBF, the TFI of each PDCH can be assigned independently.
This increases the maximum to 32 TBF per direction and per PDCH
concerning the TFI allocation.
Ticket: #1793
Sponsored-by: On-Waves ehf
Currently the TFI and the TRX have to be determined before the actual TBF
allocation function is called, passing TFI and TRX number as
parameters. This does fit to TFI reuse for different slots, since
this were tightly coupled with the slot selection.
This commit just moves the TFI selection into the alloc_algorithm
functions. The tfi parameter is removed from the the TFI alloc
functions. The trx parameter is changed into use_trx to optionally
limit the trx selection (same semantics like in tfi_find_free).
Sponsored-by: On-Waves ehf
Currently a single bit set is used to maintain a set of used TFI
without distinguishing between uplink and downlink. Since the
namespaces of UL and DL TFI are separate, this implementation is
not correct.
This commit changes gprs_rlcmac_pdch to use a separate bit set for
each direction. It also replace the corresponding conditional fprintf
statement in check_tfi_usage (AllocTest.cpp) by an equivalent
OSMO_ASSERT.
Sponsored-by: On-Waves ehf
This commit adds the check_tfi_usage function that checks the TFI
usage. It iterates through all TBFs, records on which PDCH it uses
which TFI and check for conflicts. It also checks the bits returned
by pdch->assigned_tfi(). The latter suffers from an bug in that
method (no separation of uplink and downlink), so a conditional
fprintf is used instead of an assertion. The method tfi_find_free
is checked for conflicts after allocations.
Sponsored-by: On-Waves ehf
Currently the handling of MS_B and MS_C is not compliant with TS
45.002, annex B.1. These values may only interpreted as 0, if
frequency hopping is not enabled and if there is no change from Rx to
Tx or vice-versa.
This commit sets Ttb/Trb to 1 if the table entry is MS_B/MS_C, since
only combined down/up access modes are supported.
Sponsored-by: On-Waves ehf
Currently the masks are computed equally for each class type. This
does not make much sense for class type 2 MS, since those are capable
to work in full duplex mode.
This commit sets the masks to 0xff for class type 2 MS.
Sponsored-by: On-Waves ehf
According to TS 45.002, 6.4.2.2 the choice whether Tta or Tra has to
be applied, depends on the medium access mode (currently always
dynamic) and the number of UL/DL slots. Currently either value can be
used which might result in combinations not covered by the spec.
This commit changes find_multi_slots() to skip non-compliant
combinations.
Note that this code will have to be extended, if other medium
access modes are implemented.
Sponsored-by: On-Waves ehf
The local enums MASK_TT and MASK_TR replace the hard coded indices.
The variable m_idx is renamed to mask_sel for more clarity.
Sponsored-by: On-Waves ehf
Both functions only differ in the computation of the value for
num_tbfs.
This commit merge both functions and adds a parameter containing a
function for that compuation.
Sponsored-by: On-Waves ehf
The commit 506f156f7a has reverted the
TS search order. The outer loop exit condition was not updated
accordingly. This bug would would only lead to an error if there were
multiple TRX where the first TRX has not got any PDCH assigned.
This commit corrects the break condition.
Fixes: Coverity CID 1311776
Sponsored-by: On-Waves ehf
Fixes: Jenkins build #609 warning
Addresses:
llc.cpp:56, GNU C Compiler 3 (gcc), Priority: Normal
comparison between signed and unsigned integer expressions
Sponsored-by: On-Waves ehf
Currently the slot selection of algorithm A is based on the current
slot usage by active TBF. Especially in the Dl after UL case which
reflects the commen use case "MS initiates TCP connection", the
resulting distribution is not optimal with respect to PDCH usage.
This commit changes the implementation to use the slot reservation
information instead.
Sponsored-by: On-Waves ehf
Currently when using the test modes TEST_MODE_DL_AFTER_UL or
TEST_MODE_UL_AFTER_DL, the first TBF is deleted before the second is
allocated. The far more interesting case were to keep the first TBF a
little bit longer until the second TBF has been created and delete
then. This comes closer the the situation observed with real MS,
where the first TBF takes some time (timeout or waiting for Ack)
before it gets deleted and thus detached from the MS object.
This commit delays the call to tbf_free accordingly.
The effect can be observed in the results of the algo A tests, where
the uniform distribution of the allocated PDCH is lost.
Sponsored-by: On-Waves ehf
Currently the search for an enabled PDCH slot for SBA start with the
first TS. If there are more than 2 PDCH slots enabled, this slot will
conflict with an existing multislot reservation for most multislot
classes. This were less likely if the search were reversed and
started with the last slot due to the 3 slot shift between Tx and Rx.
When multislot allocation is enabled and several MS are connected,
and increased rate of poll timeouts can be observed.
This commit tries to reduce the number of poll timeouts by reverting
the slot search order for SBA allocation.
Sponsored-by: On-Waves ehf
The current logging statements within the inner loop of
find_multi_slots drain quite a lot of CPU resources even if
LOGL_DEBUG is not enabled. This might cause issues on the target
hardware.
This commit disables these LOGP calls unless the
ENABLE_TS_ALLOC_DEBUG macro has been set explicitly. This results in
a reduction in the CPU usage reported by callgrind for
find_multi_slots from 42% to 25% when executing AllocTest.
Sponsored-by: On-Waves ehf
According to callgrind, this function consumes 33% CPU when running
the AllocTest program.
This commit uses the assigned_usf() method to get the USFs allocated
by a PDCH instead of traversing the TBFs.
Sponsored-by: On-Waves ehf
Currently is is rather expensive to get TFI and USF usage per PDCH,
because the TBFs need to be scanned to get that information.
This commit adds corresponding bit sets which get updated by the
attach_tbf/detach_tbf methods of the gprs_rlcmac_pdch class.
Sponsored-by: On-Waves ehf
Currently the search of the "best" slot combination is done
separately from the UL slot selection, which can lead to an
allocation failure due to USF exhaustion even if another combination
had been possible.
This commit reduces the probability for this event by skipping UL
slots without free USF while calculation the capacity.
Note that the implementation is rather inefficient which will be
fixed by the following commits.
Sponsored-by: On-Waves ehf
Since currently the algorithm B will only allocate a single UL slot
and will have to stick to it (first common TS), the other possible UL
slots will not be allocated while the reservation is kept.
This commit adds code to update the reserved set of UL slots to only
reserve the single common TS when the UL TBF is allocated.
Interestingly this leads to fewer allocated TBF in some cases due to
USF exhaustion. This will be improved by the following commit "alloc:
Skip common TS without free USF".
Sponsored-by: On-Waves ehf
Currently the capacity of a PDCH slot is calculated as 32 - N_reserved
for each direction. This can result in a capacity of 0 and even
negative values.
This commit forces the capacity of an usable slot to be at least zero
under the assumption, that an overly reserved PDCH is still better
than none.
Sponsored-by: On-Waves ehf
Currently al possible UL slots are included in the capacity
calculation which is the base of the slot selection. Nevertheless
UL-only slots will never be used, since only one uplink slot (which
must be a common slot) will be used.
This patch changes the code to only include common slots in the
capacity sum.
Note that this might not be optimal if algorithm B supported
multiple uplink slots.
Sponsored-by: On-Waves ehf
The current implementation always starts the downlink slot allocation
with the first possible slot, depending on which channels are enabled
and which multislot class is offered by the MS. So in configurations
with many (>4) PDCH, some PDCH are not really used.
The new implementation introduced by this commit differs as follows:
- The reservation mechanism provided by GprsMs is used to avoid
incompatibilities is used in the same way like algo A does. This
basically means, that the allocation is done once when the first
TBF is requested and then used until all TBF have been released.
- All combinations of Rx and Tx slots are checked for compatibility
with the multiscot class. Basically the combination with the most
usable PDCH and the least number of reservations is used.
- Only one UL slots is provided.
- Tta and Tra are checked.
Sponsored-by: On-Waves ehf
This commits adds three poll timeout counters
- RLC Assign Timeout
- RLC Ack Timeout
- RLC Release Timeout
to help diagnosing to cause for these events. There seems to be an
increased rate of these when a PDCH is shared by multiple TBFs.
Sponsored-by: On-Waves ehf
This reverts commit 2272a83a13b57ea7e99fe96ac76e4ad892e19e90.
The modification is no longer needed, since the call to update has
been removed from reuse_tbf().
Conflicts:
src/tbf_dl.cpp
Sponsored-by: On-Waves ehf
Since both TBF are based on the same reservation which means that
they should be compatible with respect to the slot usage, and since
the new TBF has not been forced to single slot usage, an update of
the allocation is not necessary now.
This commit removes the call to update() from within reuse_tbf().
Sponsored-by: On-Waves ehf
The call to tbf_alloc_dl_tbf misses the pointer to the GprsMs object
which is already known in that case (tbf_reuse). This leads to a full
reallocation of the PDCH slots, which is possibly incompatible with
the old set of slots. This can result in hanging TCP connections and
TCP connection failures.
This commit replaces the old NULL value by the actual GprsMs object.
Since the set_ms() is also done within the tbf_alloc_dl_tbf method,
that call is removed.
Sponsored-by: On-Waves ehf
Currently algorithm A bases its time slots selection on the number of
TBF actively using the PDCHs. This statistically prefers the first
time slots, especially with short living TBFs. So when the first TBF
is triggered by an uplink transfer (which generally results in a
short-lived TBF) the potentially longer living DL TBF will be bound
to the same slot. When another MS then requests an uplink TBF, it
will get the same slot (no UL TBF currently active).
This commit changes the algorithm to base its selection on reserved
slots instead.
Sponsored-by: On-Waves ehf
According to TS 45.002, 6.4.2 the training sequence (TSC) must be the
same for all slots in a multi-slot set.
This commit updates find_possible_pdchs() to only consider slots with
the same TSC if more that 1 slot shall be assigned.
Note that the first PDCH's TSC will be used as reference, so if two
or more groups with a common TSC are configured, only the first will
be used. This restriction does not apply to algorithm A, since it
will not assign more than one slot and therefore sets the max_slots
parameter to 1.
Sponsored-by: On-Waves ehf
In contrast to the slots currently used by existing TBFs, the
reserved slots refer to the time slots that can be used for newly
allocated TBFs without causing conflicts (given that the first common
TS does not change). They correspond to the potential use of the
PDCHs and can be used to achieve a more uniform slot allocation.
This commit adds bit set based methods to GprsMs and gprs_rlcmac_trx
and a counter to gprs_rlcmac_pdch. The current TRX will also be
stored in the MS object.
Sponsored-by: On-Waves ehf
Currently only the first enabled PDCH will be used. Beside the
throughput this will also limit the number of TBFs:
- number of UL TBFs <= 7
- number of DL TBFs <= 32
This commit changes the allocation algorithm to use the PDCH with the
least number of attached TBFs. This will improve the troughput in
both directions and the UL limits:
- number of UL TBFs <= min(32, N_PDCH * 7) UL TBFs
Ticket: #1794
Sponsored-by: On-Waves ehf
Jacob Erlbeck