summaryrefslogtreecommitdiff
path: root/src/ipcpd/unicast/pol
Commit message (Collapse)AuthorAgeFilesLines
* ipcpd: Fix slow start in multi-bit (F)ECN policyDimitri Staessens2020-12-071-8/+11
| | | | | | | | | | | There is a check not to rapidly double the window to astronomical sizes when there is no congestion experienced for long periods of time, but the if-else logic was botched and it still grew to astronomical sizes (albeit linear instead of exponential). I also lowered the ECN threshold a bit. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix off-by-one in Multi-bit (F)ECN policyDimitri Staessens2020-12-051-2/+1
| | | | | | | | Noticed an off-by-one in the packet counter because it was incremented before and the byte counter after the flow update. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Add RIB statistics for flow allocatorDimitri Staessens2020-12-053-2/+46
| | | | | | | | | | The RIB will now show some stats for the flow allocator, including congestion avoidance statistics. This is needed before decoupling the data transfer component and the flow allocator as some current stats show in DT will move to FA. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Simplify multi-bit (F)ECN policyDimitri Staessens2020-12-021-54/+69
| | | | | | | | | | | | The mb-ecn policy has a couple of divisions in the math, which I wanted to avoid. Now it measures the number of bytes sent in a window, and updates the next window with AIMD logic. If the number of bytes in the window is reached, the call blocks. To avoid long packet bursts, the window size continually scales to contain between CA_MINPS (8) and CA_MAXPS (64) packets. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Add congestion avoidance policiesDimitri Staessens2020-12-025-1/+414
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds congestion avoidance policies to the unicast IPCP. The default policy is a multi-bit explicit congestion avoidance algorithm based on data-center TCP congestion avoidance (DCTCP) to relay information about the maximum queue depth that packets experienced to the receiver. There's also a "nop" policy to disable congestion avoidance for testing and benchmarking purposes. The (initial) API for congestion avoidance policies is: void * (* ctx_create)(void); void (* ctx_destroy)(void * ctx); These calls create / and or destroy a context for congestion control for a specific flow. Thread-safety of the context is the responsability of the flow allocator (operations on the ctx should be performed under a lock). ca_wnd_t (* ctx_update_snd)(void * ctx, size_t len); This is the sender call to update the context, and should be called for every packet that is sent on the flow. The len parameter in this API is the packet length, which allows calculating the bandwidth. It returns an opaque union type that is used for the call to check/wait if the congestion window is open or closed (and allowing to release locks before waiting). bool (* ctx_update_rcv)(void * ctx, size_t len, uint8_t ecn, uint16_t * ece); This is the call to update the flow congestion context on the receiver side. It should be called for every received packet. It gets the ecn value from the packet and its length, and returns the ECE (explicit congestion experienced) value to be sent to the sender in case of congestion. The boolean returned signals whether or not a congestion update needs to be sent. void (* ctx_update_ece)(void * ctx, uint16_t ece); This is the call for the sending side top update the context when it receives an ECE update from the receiver. void (* wnd_wait)(ca_wnd_t wnd); This is a (blocking) call that waits for the congestion window to clear. It should be stateless (to avoid waiting under locks). This may change later on if passing the context is needed for different algorithms. uint8_t (* calc_ecn)(int fd, size_t len); This is the call that intermediate IPCPs(routers) should use to update the ECN field on passing packets. The multi-bit ECN policy bases the value for the ECN field on the depth of the rbuff queue packets will be sent on. I created another call to grab the queue depth as fccntl is write-locking the application. We can further optimize this to avoid most locking on the rbuff. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* build: Add support for GCC 100.17.5Dimitri Staessens2020-05-235-5/+5
| | | | | | | | | GCC 10 defaults to -fno-common, so some variables that were defined in the headers needed to be declared "extern". The GCC 10 static analyzer can now be invoked using the DebugAnalyzer build option. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix locking in link_state policyDimitri Staessens2020-03-141-7/+6
| | | | | | | | There were updates under rdlock instead of wrlock, causing data races and trouble. Also speeds up shutdown a bit. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Add unit tests for LFA and ECMP algorithmsDimitri Staessens2020-02-231-49/+100
| | | | | | | This adds tests for LFA and ECMP to the graph_test routine. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix infinite recursion in LFADimitri Staessens2020-02-231-2/+2
| | | | | | | | | There were bugs introduced in the LFA algorithm refactor causing infinite recursion and SEGV. The infinite recursion check was added as an explicit compiler flag to the build. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix double free, memleak and malloc checkDimitri Staessens2020-02-162-6/+7
| | | | | | | | Some fixes in the multipath implementation related to memory management that showed up with the static analyzer. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* Add equal-cost multipath routing policyDimitri Staessens2020-02-168-13/+389
| | | | | | | | | | This adds an equal-cost multipath routing policy to Ouroboros, based on Nick Aerts' code. When selected, flows will send packets over all paths with equal cost (hop count). Path selection is round-robin. It does not yet take into account flows that are down. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix uninitialized variable in graphDimitri Staessens2020-02-161-1/+1
| | | | | | | During refactor a variable initialization was removed. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Rename hashtable to pftDimitri Staessens2020-02-167-351/+346
| | | | | | | | | This makes the hashtable more tailored to a packet forwarding table (PFT). In the end not much of a change was needed, but now it's clear the pft maps a destination address to a list of (outgoing) fds. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Fix minor things in graph and link_stateDimitri Staessens2020-02-162-23/+74
| | | | | | | | | | The vertex was used before definition in the graph implementation. Fixed potential data race in link_state algorithm. Added missing asserts. Removed initialization of variables where not needed to let compiler warn about uninitialized uses. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* lib: Move hashtable from lib to unicastDimitri Staessens2020-02-166-2/+409
| | | | | | | | | | The hashtable is only used for forwarding tables in the unicast IPCP. This moves the generic hashtable out of the library into the unicast IPCP to prepare a more tailored implementation specific to routing tables containing address lists. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* ipcpd: Refactor graph to self-contain LFADimitri Staessens2020-02-161-72/+86
| | | | | | | | | | The LFA algorithm modifies the output of the simple routing algorithm, but the output was mixed in the general call. This moves the LFA subroutine to be self-contained. This makes for a cleaner entry point when adding more routing algorithms. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* build: Update copyright to 20200.16.0Dimitri Staessens2020-01-0211-11/+11
| | | | | Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>
* build: Refactor normal to unicastDimitri Staessens2019-07-2912-0/+2991
This completes the renaming of the normal IPCP to the unicast IPCP in the sources, to get everything consistent with the documentation. Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks> Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>