aboutsummaryrefslogtreecommitdiffstats
path: root/src
AgeCommit message (Collapse)AuthorFilesLines
2015-07-21alloc: Optionally enforce first common TS in find_multi_slots (TODO)jerlbeck/wip/pdch-allocJacob Erlbeck1-2/+20
TODO: - This isn't probably triggered at all currently, so this commit can possibly be dropped
2015-07-21bssgp: Use measured leak rate for flow control (EXPERIMENTAL)Jacob Erlbeck5-6/+87
THIS IS EXPERIMENTAL, DO NOT USE IN PRODUCTION The leak rate sent to the SGSN does not reflect the current CS level, lost frames, and control message overhead. Use the ratio between sent blocks and successfully received bytes to derive the net leak rate. TODO: - The values are not stable, possibly resulting from interference with the sampling rate or from the interval between send and receive if they fall into different sampling intervals. - Perhaps the rate can be computed from sent data bytes / sent data frames or from the average packet size and the global nack rate.
2015-07-21bssgp: Fix leak rate computation CS valueJacob Erlbeck1-5/+21
Currently the initial_cs_dl value is used to compute the maximum leak rate. This can be too low if adaptive CS selection is used. This commit changes gprs_bssgp_tx_fc_bvc to derive the max CS level from the configuration. Sponsored-by: On-Waves ehf
2015-07-21pcu: Enable LLC CoDel by defaultJacob Erlbeck1-0/+2
Currently CoDel is disabled by default. This commit enables CoDel on start up with the default interval time, equivalent to the 'queue codel' VTY command. To disable CoDel, use the 'no queue codel' command. Sponsored-by: On-Waves ehf
2015-07-21llc: Use CoDel to drop packages from the LLC queueJacob Erlbeck5-1/+91
Currently packets are only dropped if they have reached their maximum life time. This leads to LLC queues being constantly filled under load, increasing the latency up to the maximum life time. This kind of bufferbloat hinders TCP's congestion avoidance algorithms. To keep the queues short, the CoDel active queue management algorithm can be used. This commit changes to llc_dequeue method to apply the CoDel algorithm to selectively drop LLC frames before they passed to the TBF layer to be encoded in BSNs. This feature is currently disabled by default. The CoDel state is managed per MS since the LLC queues are also kept in the MS objects. Note that there is still some buffering in the TBF objects, in the worst case (CS4) 3.5kByte + LLC-MTU octets are stored there. The resulting additional packet delay is not (yet) taken into account for CoDel. Also note that configuration changes are applied to new MS objects only. The following VTY commands are added to the 'pcu' node: - queue codel activates CoDel, the interval is selected by the implementation - queue codel interval <1-1000> activates CoDel with a fixed interval given in centiseconds (10ms-10s) - no queue codel deactivates CoDel Which interval value to use is still an open issue. For high speed links (e.g. Ethernet), CoDel suggests 100ms. For slower links, the expected RTT is recommended. The current implementation uses a default value of 2000ms. Measurements: Note that the following measurements depend on several other factors, most notably the interaction with the SGSN's flow control. They are just examples to give an idea how CoDel might influence some parameters. The measurements have been done with a single E71, first with a running ping only (Idle), then with an additional TCP download of a 360k file (Busy). The CoDel interval was set to 1s. - Idle : ping ~400ms, avg queue delay 0ms, dropped 0 - Busy, No CoDel: ping ~6s, avg queue delay 4-6s, dropped 0, scheduled 948, duration 54s - Busy, CoDel: ping 500-1500ms, avg queue delay ~600ms, dropped 77, scheduled 1040, duration 60s More measurements with two MS downloading in parallel (two independant measurements per case). - Busy, No CoDel: dropped 0, scheduled 1883, duration 121s dropped 19, scheduled 2003, duration 133s - Busy, CoDel: dropped 22, scheduled 1926, duration 116s dropped 22, scheduled 1955, duration 108s Sponsored-by: On-Waves ehf
2015-07-21llc: Add CoDel AQM implementationJacob Erlbeck3-2/+291
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
2015-07-17bssgp: Adapt flowcontrol MS default to current alloc algorithmJacob Erlbeck3-2/+29
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 Erlbeck2-3/+45
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-16pcu: Use alloc_algorithm_dynamic by defaultJacob Erlbeck1-1/+1
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
2015-07-16alloc: Add counters for successful algo A/B allocationsJacob Erlbeck3-0/+11
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 Erlbeck3-3/+38
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-16ms: Add is_idle() method to GprsMs::GuardJacob Erlbeck2-0/+10
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
2015-07-16tbf: Put the TFI->TBF mapping into the PDCH objectsJacob Erlbeck4-74/+85
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 Erlbeck7-60/+71
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-16pdch: Manage TFIs per directionJacob Erlbeck2-8/+9
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
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-15sba: Fix loop exit in SBAController::alloc (Coverity)Jacob Erlbeck1-1/+1
The commit 506f156f7a4aebb52dace00a760f86b2b4f5e19a 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
2015-07-14llc: Fix comparison warningJacob Erlbeck1-1/+1
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
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-07sba: Reverse TS search orderJacob Erlbeck1-2/+2
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
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-07tbf: Keep a set of used TFI and USF per PDCHJacob Erlbeck2-4/+39
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
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-07tbf: Add Poll Timeout countersJacob Erlbeck3-0/+20
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
2015-07-03Revert "tbf: Add GprsMs* argument to update() and use it in reuse_tbf"Jacob Erlbeck2-10/+4
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
2015-07-03tbf: Remove call to update() in reuse_tbfJacob Erlbeck1-2/+0
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
2015-07-03tbf: Set ms in call to tbf_alloc_dl_tbfJacob Erlbeck1-3/+1
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
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-03ms: Get the set of slots currently activeJacob Erlbeck4-0/+66
This commits adds methods to GprsMs and gprs_rlcmac_tbf to retrieve the slots that are actively used. Sponsored-by: On-Waves ehf
2015-07-03ms: Add support for slot reservationJacob Erlbeck4-3/+102
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
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: Add GprsMs* argument to update() and use it in reuse_tbfJacob Erlbeck3-5/+11
Since set_ms() is caled on the new DL TBF, the old DL TBF loses the reference to the MS object. This will lead to a segfault, when update() is called in reuse_tbf(). This commit adds an optional GprsMs* parameter to update() and uses it for the slot allocation. This fixes a TbfTest crash that would otherwise occur after applying the next commit. Sponsored-by: On-Waves ehf
2015-07-03ms: Add tbf() method to get the TBF based on the directionJacob Erlbeck3-0/+16
To avoid the need for a switch or conditional statement when needing a TBF from an MS object in direction independant code, this method contains that case distinction. For additional flexibility, a reverse() function is added to get the opposite direction. Sponsored-by: On-Waves ehf
2015-07-03ms: Add first_common_ts method to GprsMsJacob Erlbeck2-0/+13
This method gets the index (0 based) of first common time slot used by the TBFs attach to it. It expects that all of them have the same notion of this. If no TBF is attached, -1 will be returned. Sponsored-by: On-Waves ehf
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 04:15:44 +0000