aboutsummaryrefslogtreecommitdiffstats
path: root/src/gprs_rlcmac_ts_alloc.cpp
AgeCommit message (Collapse)AuthorFilesLines
2018-02-27Simplify TS alloc: internalize TRX checkMax1-11/+10
Move TRX check inside local tfi_find_free() wrapper to make main algorithm easier to follow. Change-Id: I02da2b8ba8c9c8815dae0e39e1fed277ca0df171 Related: OS#2282
2018-02-27Simplify TS alloc: adjust function signaturesMax1-47/+58
* document used parameters and return values * use consistent formatting * constify function parameters where appropriate (adjusting parameter types if necessary) Change-Id: I211b10b4da59c73d509b719346774515c761886a Related: OS#2282
2018-02-27Simplify TS alloc: use defines for constantsMax1-4/+4
* define and use constant for occupied TFI instead copying the same magic number all over the place * use libosmocore's define for bit pretty-printer Change-Id: I2699ceebf0cbec01652a02fa68ccc9e9419d0293 Related: OS#2282
2018-02-27Simplify TS alloc: avoid TS reassignmentMax1-5/+5
Assign reserved_*_slots only when multislot masks are found to avoid reassignment and make code easier to follow. Change-Id: I9b0482f4ea75ead9855cd78e33c8e70d0ccf4484 Related: OS#2282
2018-02-27Simplify TS alloc: adjust allocator signaturesMax1-16/+30
* drop unused parameters (from both functions and structs) * document used parameters and return values * tighten types used for parameters * use consistent formatting Tests are adjusted accordingly but test results are left untouched to avoid regressions. Change-Id: I39d81ab64ff790b9c4c2d0312a574485cd83e755 Related: OS#2282
2018-02-27Add multislot classes from latest specMax1-2/+6
The table B.1 is copy-pasted from 3GPP TS 45.002 and reformatted via Emacs macros into C struct to avoid typos. The test output expanded accordingly. The allocation test expectations and output are adjusted accordingly. Note: classes 35-45 which need TA offset are not properly supported yet. This can be extended once we have such devices available for tests. Change-Id: I1ef2eb99c517f25e7d1e71b985a3e0eb3879eb2c Related: OS#2282
2018-02-27Add tests for find_multi_slots()Max1-1/+1
* make function public * add tests Change-Id: I4174703808335c19341cd5b5f4422496d958967f
2017-11-21Move multislot table to separate fileMax1-109/+29
To facilitate testing and addition of support for new multislot classes, hide multislot class struct internals: * introduce mslot_class_get_*() functions * use those functions instead of direct access to array of structs * use ms_class as a parameter to find_multi_slot() instead of entire object Change-Id: Id796bcff1322b1e273a0e3236c66c23b9da8fac6
2017-11-21Remove unused parameterMax1-3/+2
Change-Id: Ifd6e04a29e27b1862cf9e98dec7481d3e0efcd48
2017-10-10cosmetic: reformat multislot classes tableMax1-31/+32
Add header similar to the one used in the standard, reformat to facilitate further extention. Change-Id: I786df6b154c0668d2cefa0ea84d7dea336b0da1d Related: OS#2282
2016-02-08utils: Add pcu_bitcount and pcu_lsbJacob Erlbeck1-21/+8
These functions are currently defined in src/gprs_rlcmac_ts_alloc.cpp but will be needed elsewhere. Turn them into template functions to support different types and move them to pcu_utils.h. Sponsored-by: On-Waves ehf
2016-02-01tbf: Replace static casts by calls to as_ul_tbf/as_dl_tbfJacob Erlbeck1-8/+4
Currently casts from gprs_rlcmac_tbf to gprs_rlcmac_ul_tbf and gprs_rlcmac_dl_tbf are done by using static_cast. This doesn't provide protection against converting a gprs_rlcmac_ul_tbf pointer to a gprs_rlcmac_dl_tbf pointer and vice versa. This commit provides two functions as_ul_tbf and as_dl_tbf, that behave similar like dynamic_cast but use the direction field instead of RTTI. Sponsored-by: On-Waves ehf
2015-07-17bssgp: Adapt flowcontrol MS default to current alloc algorithmJacob Erlbeck1-0/+21
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
2015-07-16alloc: Make alloc_algorithm_dynamic statefulJacob Erlbeck1-3/+43
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
2015-07-16alloc: Use a separate usage computation for algo AJacob Erlbeck1-1/+17
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
2015-07-16alloc: Change tx_window optimization strategyJacob Erlbeck1-5/+4
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
2015-07-16alloc: Add counters for successful algo A/B allocationsJacob Erlbeck1-0/+3
This adds counters for algorithm A and B with count successful allocation combined for UL and DL. Ticket: #1934 Sponsored-by: On-Waves ehf
2015-07-16alloc: Add 'dynamic' allocation algorithmJacob Erlbeck1-0/+23
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
2015-07-16alloc: Remove disabled code fragment for multi-UL allocationJacob Erlbeck1-21/+0
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
2015-07-16alloc: Refactor alloc algorithms to only apply changes on successJacob Erlbeck1-84/+150
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
2015-07-16alloc: Remove redundant first_common_ts handlingJacob Erlbeck1-17/+0
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
2015-07-16tbf: Put the TFI->TBF mapping into the PDCH objectsJacob Erlbeck1-2/+0
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
2015-07-16alloc: Allocate TFI per slot (algorithm A)Jacob Erlbeck1-20/+95
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
2015-07-16tbf: Move TFI selection into alloc_algorithmJacob Erlbeck1-3/+40
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
2015-07-16alloc: Fix MS_B/MS_C interpretationJacob Erlbeck1-4/+12
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
2015-07-16alloc: Do not use masking for multislot class type 2 MSJacob Erlbeck1-4/+12
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
2015-07-16alloc: Select applicable Tta/TraJacob Erlbeck1-9/+44
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
2015-07-16alloc: Use an enum instead of numbers to select the maskJacob Erlbeck1-10/+12
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
2015-07-16alloc: Merge find_least_busy_pdch and find_least_reserved_pdchJacob Erlbeck1-59/+19
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
2015-07-07alloc: Use least reserved PDCH for algo AJacob Erlbeck1-1/+60
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
2015-07-07alloc: Disable inner loop debugging by defaultJacob Erlbeck1-9/+15
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
2015-07-07alloc: Optimize find_free_usfJacob Erlbeck1-9/+4
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
2015-07-07alloc: Skip common TS without free USF when ratingJacob Erlbeck1-3/+5
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
2015-07-07alloc: Only reserve 1 UL slot with algorithm BJacob Erlbeck1-0/+5
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
2015-07-07alloc: Set minimum slot capacity to 1Jacob Erlbeck1-0/+2
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
2015-07-07alloc: Only use common UL slots when calculating the capacityJacob Erlbeck1-1/+2
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
2015-07-07alloc: Replace Algorithm B implementationJacob Erlbeck1-418/+374
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
2015-07-03alloc: Base algo A on reserved PDCHsJacob Erlbeck1-9/+11
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
2015-07-03alloc: Ignore slots with differing TSC if multiple slots are requestedJacob Erlbeck1-1/+18
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
2015-07-03alloc: Load balancing for algo AJacob Erlbeck1-13/+107
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
2015-07-03tbf: Maintain the number of TBF per PDCHJacob Erlbeck1-2/+12
Currently the PDCH object do not know anything about the TBFs using them. To make the slot allocation load dependant, at least some numbers are required. This commit adds TBF counters (one per direction) and the related methods attach_tbf, detach_tbf, and num_tbfs to gprs_rlcmac_pdch. Sponsored-by: On-Waves ehf
2015-06-29tbf: Pass the MS object around instead of old_tbfJacob Erlbeck1-7/+13
Currently the old TBF (either uplink or downlink) is passed around at TBF allocation mainly to get information about the MS. To implement more complex allocation algorithms, the MS object itself will be needed anyway. This commit replaces the old_tbf arguments by MS object arguments. Sponsored-by: On-Waves ehf
2015-06-08tbf: Store MS class in GprsMs objectsJacob Erlbeck1-7/+7
The ms_class value is a property of the MS and thus belongs to the GprsMs class. Nevertheless the MS object is created after the TLLI gets known, so the value still has to be stored in the TBF initially. This commit add the ms_class value to the GprsMs class and introduces TBF accessor functions which either access that object or, if that is not available, the value stored locally. Ticket: #1674 Sponsored-by: On-Waves ehf
2014-08-07tbf, ...: Make the fields in the dl/ul struct member variablesDaniel Willmann1-2/+2
There is no need for the union/struct anymore. Make the variable members of the UL/DL class. As a result gprs_rlc_dl_window gets a reset() method because memset(&dir.dl, 0, sizeof(dir.dl)) doesn't work anymore in reuse_tbf(). Ticket: SYS#389 Sponsored by: On-Waves ehf
2014-08-07gprs_rlcmac_ts_alloc: Be explicit about which TBF is usedDaniel Willmann1-9/+13
Use UL/DL TBFs instead of the base class wherever it is clear that the code only deals with one kind of TBF. Ticket: SYS#389 Sponsored by: On-Waves ehf
2014-06-04gprs_rlcmac_pdch: Get rid of ul/dl_tbfDaniel Willmann1-3/+1
The current code keeps a reference to all tbfs in the bts and another reference in the pdch. This allows for the possibility of both lists to go out of sync. This patch removes the pdch-specific list of ul and dl tbfs and uses the lists in the bts to lookup tbfs everywhere. Performance for going through the global list is not an issue yet. We can optimize this later and in a better way. Sponsored-by: On-Waves ehf
2014-05-30tbf: Re-send dl assignment if we can upgrade to multislotDaniel Willmann1-0/+9
The current code would only ever assign one PDCH for the initial assignment (from CCCH). Only if reuse_tbf is called the algorithm would actually use multiple DL PDCHs if possible. This patch introduced a tbf attribute upgrade_to_multislot that is set if we have multiple PDCH configured, and support multislot assignment, but can only assign a single PDCH (alloc_algorithm_b, parameter single is set). In this case after the assignment completes (and the MS is listening on a PDCH) we resend a DL assignment though the PACCH and this time we can assign multiple timeslots.
2014-05-30Fixed calculation of colliding UL/DL slots in TS allocation algorithm BAndreas Eversberg1-1/+1
Counter j must be wrapped to prevent beeing negative, when it is initialized. This wrapping happens, if TS 0 is used for PDCH in combination with regular GPRS phones (MS class 12 or similar).
2014-01-15alloc_algorithm_b: Remove obsolete 'i' incrementation from for-loopAndreas Eversberg1-1/+1
2014-01-15alloc_algorithm_b: Add seperate function to shrink rx window when TS are removedAndreas Eversberg1-6/+12
After reduce_rx_window() and update_rx_win_max() was called, one or more TS might be removed. tx_win_min and tx_win_max must be adjusted to the new range of allocated slots.
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 11:42:59 +0000