From a2c17d2b7b09a1401eb9bdd7d41ebade6e69cb31 Mon Sep 17 00:00:00 2001 From: schodet Date: Fri, 23 Mar 2007 17:18:53 +0000 Subject: Added ca. Added backoff unit test (but no backoff yet). Added common. git-svn-id: svn+ssh://pessac/svn/cesar/trunk@19 017c9cb6-072f-447c-8318-d5b54f68fe89 --- mac/ca/Module | 1 + mac/ca/ca.h | 115 +++++++++++++++++++++++++++++++++ mac/ca/inc/backoff.h | 55 ++++++++++++++++ mac/ca/inc/context.h | 49 ++++++++++++++ mac/ca/src/backoff.c | 36 +++++++++++ mac/ca/test/backoff/Makefile | 7 ++ mac/ca/test/backoff/src/test_backoff.c | 89 +++++++++++++++++++++++++ mac/common/mfs.h | 20 ++++++ 8 files changed, 372 insertions(+) create mode 100644 mac/ca/Module create mode 100644 mac/ca/ca.h create mode 100644 mac/ca/inc/backoff.h create mode 100644 mac/ca/inc/context.h create mode 100644 mac/ca/src/backoff.c create mode 100644 mac/ca/test/backoff/Makefile create mode 100644 mac/ca/test/backoff/src/test_backoff.c create mode 100644 mac/common/mfs.h (limited to 'mac') diff --git a/mac/ca/Module b/mac/ca/Module new file mode 100644 index 0000000000..6f402ca462 --- /dev/null +++ b/mac/ca/Module @@ -0,0 +1 @@ +SOURCES := backoff.c diff --git a/mac/ca/ca.h b/mac/ca/ca.h new file mode 100644 index 0000000000..f28f4d8c06 --- /dev/null +++ b/mac/ca/ca.h @@ -0,0 +1,115 @@ +#ifndef mac_ca_ca_h +#define mac_ca_ca_h +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file mac/ca/ca.h + * \brief Channel Access public interface. + * \ingroup mac_ca + */ +#include "mac/common/mfs.h" + +/* Forward declarations. */ +typedef struct ca_t ca_t; + +/** Channel Access schedule entry. */ +struct ca_schedule_t +{ + /** Allocation end date. */ + u32 end_date_tck; + /** GLID of this allocation. */ + u8 glid; +}; +typedef struct ca_schedule_t ca_schedule_t; + +/** + * Restart VCS. + * \param ctx ca context + * \param date current date + * \param length_fl VCS length + * \param anticipation_tck ACCESS event anticipation + * + * Restart the Virtual Carrier Sense timer for a given length. The ca layer + * will use its schedule to find the next transmit opportunity after the VCS + * expiration. The hardware will programmed with an anticipation in order to + * take extra computation depending on the current state into account. + */ +void +ca_vcs_restart (ca_t *ctx, u32 date, uint length_fl, uint anticipation_tck); + +/** + * Program hardware ACCESS timer. + * \param ctx ca context + * \param date current date + * \param length_fl timer length + * \param anticipation_tck ACCESS event anticipation + * + * Program the hardware ACCESS timer, ignoring VCS. This can be used for + * responses or bursts where we know we have the medium access. + */ +void +ca_vcs_access (ca_t *ctx, u32 date, uint length_fl, uint anticipation_tck); + +/** + * Update Channel Access after a MFS update. + * \param ctx ca context + * \param date current date + * \param mfs the updated MFS + * + * When a MFS is updated, this can change its priority. The Channel Access + * layer must update its priority queue and may change the MFS which was + * chosen for the next transmission. + */ +void +ca_mfs_update (ca_t *ctx, u32 date, mfs_t *mfs); + +/** + * Update the Channel Access schedule. + * \param ctx ca context + * \param date current date + * \param schedule schedule elements table + * \param schedule_length number of schedule elements + * + * This is called after the beacon reception, or after expected beacon + * reception by an upper layer at least before end of CSMA region (first CSMA + * region is at least 1.5ms). The schedule is stored as a circular buffer and + * searched using dichotomy using absolute date in ticks. + */ +void +ca_schedule_update (ca_t *ctx, u32 date, + ca_schedule_t *schedule, uint schedule_length); + +/** + * Update backoff after a deferral. + * \param ctx ca context + * \param slot_counter hardware slot counter value at the time of deferral + * + * If a FC is received after an ACCESS in CSMA, we did not get the medium. + * This is a backoff deferral. If we lost the PRP, this is not counted as a + * backoff deferral because backoff procedure is not entered. + * + * If a collision is inferred (no acknowledgement), this is also a backoff + * deferral. + * + * This function can be called in advance after an ACCESS event and cancelled + * with a ca_backoff_success later. + */ +void +ca_backoff_deferred (ca_t *ctx, uint slot_counter); + +/** + * Update backoff after a success. + * \param ctx ca context + * + * Will reset the backoff procedure for the next transmission. This is called + * when the MPDU has been sent and no collision is inferred. + */ +void +ca_backoff_success (ca_t *ctx); + +#endif /* mac_ca_ca_h */ diff --git a/mac/ca/inc/backoff.h b/mac/ca/inc/backoff.h new file mode 100644 index 0000000000..c0357af6d5 --- /dev/null +++ b/mac/ca/inc/backoff.h @@ -0,0 +1,55 @@ +#ifndef mac_ca_inc_backoff_h +#define mac_ca_inc_backoff_h +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file mac/ca/inc/backoff.h + * \brief Backoff handling private header. + * \ingroup mac_ca + */ +#include "mac/ca/ca.h" + +#include "lib/rnd.h" + +/** Channel Access backoff context. */ +struct ca_backoff_t +{ + /** Current backoff procedure counter. */ + uint bpc; + /** Current contention window size. */ + uint cw; + /** Current backoff counter value. */ + uint bc; + /** Current deferral counter. */ + uint dc; + /** Random number generator context. */ + lib_rnd_t rnd_context; +}; +typedef struct ca_backoff_t ca_backoff_t; + +/** + * Initialise the backoff structure to a known state. + * \param ctx ca context + */ +void +ca_backoff_init (ca_t *ctx); + +/** + * Initialise the backoff procedure for a new transmission. + * \param ctx ca context + * \param cap channel access priority + * + * Called when a new transmission is planned to start in a CSMA allocation. + */ +void +ca_backoff_new (ca_t *ctx, uint cap); + +/* ca_backoff_deferred is public */ +/* ca_backoff_success is public */ + +#endif /* mac_ca_inc_backoff_h */ diff --git a/mac/ca/inc/context.h b/mac/ca/inc/context.h new file mode 100644 index 0000000000..1c6fc5efe5 --- /dev/null +++ b/mac/ca/inc/context.h @@ -0,0 +1,49 @@ +#ifndef mac_ca_inc_context_h +#define mac_ca_inc_context_h +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file mac/ca/inc/context.h + * \brief Channel Access private context. + * \ingroup mac_ca + */ + +#include "mac/ca/ca.h" +#include "mac/common/mfs.h" + +#include "mac/ca/inc/backoff.h" + +/** Schedule circular buffer size. \todo TBD */ +#define CA_SCHEDULE_BUFFER_SIZE 32 + +/** Channel Access context. */ +struct ca_t +{ + /** \todo document context. */ + /** Scheduled MFS for next access. */ + mfs_t *access_mfs; + /** End date of the current VCS. */ + u32 vcs_end_date; + /** Programmed end date. It may be farther than vcs_end_date when + * it lands in a unusable region or sooner when we have a exclusive + * access to the medium for a response or a burst. Does not include + * anticipation. */ + u32 programmed_end_date; + /** Programmed anticipation, may be needed if the timer must be + * reprogrammed. */ + u32 anticipation_tck; + /** Backoff context. */ + ca_backoff_t backoff; + /** Schedule circular buffer head and tail. */ + uint schedule_head, schedule_tail; + /** Schedule circular buffer. */ + ca_schedule_t schedule[CA_SCHEDULE_BUFFER_SIZE]; +}; +/* Forward declaration in ca.h. */ + +#endif /* mac_ca_inc_context_h */ diff --git a/mac/ca/src/backoff.c b/mac/ca/src/backoff.c new file mode 100644 index 0000000000..75b47119a9 --- /dev/null +++ b/mac/ca/src/backoff.c @@ -0,0 +1,36 @@ +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file mac/ca/src/backoff.c + * \brief Backoff handling. + * \ingroup mac_ca + */ +#include "common/std.h" + +#include "mac/ca/inc/backoff.h" + +void +ca_backoff_init (ca_t *ctx) +{ +} + +void +ca_backoff_new (ca_t *ctx, uint cap) +{ +} + +void +ca_backoff_deferred (ca_t *ctx, uint slot_counter) +{ +} + +void +ca_backoff_success (ca_t *ctx) +{ +} + diff --git a/mac/ca/test/backoff/Makefile b/mac/ca/test/backoff/Makefile new file mode 100644 index 0000000000..85dd429477 --- /dev/null +++ b/mac/ca/test/backoff/Makefile @@ -0,0 +1,7 @@ +BASE = ../../../.. + +HOST_PROGRAMS = test_backoff +test_backoff_SOURCES = test_backoff.c +test_backoff_MODULES = lib mac/ca + +include $(BASE)/common/make/top.mk diff --git a/mac/ca/test/backoff/src/test_backoff.c b/mac/ca/test/backoff/src/test_backoff.c new file mode 100644 index 0000000000..f95851c649 --- /dev/null +++ b/mac/ca/test/backoff/src/test_backoff.c @@ -0,0 +1,89 @@ +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file test_backoff.c + * \brief Test backoff code. + * \ingroup test + */ +#include "common/std.h" + +#include "mac/ca/inc/context.h" + +#include + +int +main (void) +{ + uint i; + uint cap = 0, slot_count = 0, bpcm; + lib_rnd_t rnd; + ca_t ca; + uint iter = 1000; + u32 success_ratio = LIB_RND_RATIO (0.5), + same_cap_ratio = LIB_RND_RATIO (0.6); + bool last_success = true; + uint last_cap = 0, + last_bpc = 0, + last_cw = 0, + last_bc = 0, + last_dc = 0; + const uint dc_table[4] = { 0, 1, 3, 15 }; + const uint cw_table[4][4] = { + { 7, 15, 31, 63 }, + { 7, 15, 31, 63 }, + { 7, 15, 15, 31 }, + { 7, 15, 15, 31 }, + }; + /* Initialise. */ + ca_backoff_init (&ca); + lib_rnd_init (&rnd, 1234); + /* Use backoff. */ + for (i = 0; i < iter; i++) + { + /* New frame. */ + if (lib_rnd32 (&rnd) >= same_cap_ratio) + { + cap = lib_rnd32 (&rnd) % 4; + } + ca_backoff_new (&ca, cap); + /* Check backoff. Throw some general rules... */ + printf ("cap = %d, bpc = %d, cw = %d, bc = %d, dc = %d\n", + cap, ca.backoff.bpc, ca.backoff.cw, ca.backoff.bc, + ca.backoff.dc); + bpcm = MIN (3u, ca.backoff.bpc); + dbg_assert (ca.backoff.cw == cw_table[cap][bpcm]); + dbg_assert (ca.backoff.bc <= ca.backoff.cw); + dbg_assert ((last_success && ca.backoff.bpc == 0) || !last_success); + dbg_assert (last_success + || (ca.backoff.bpc > last_bpc + && (last_bpc == 0 || last_bc - slot_count == 0 + || last_dc == 0)) + || (ca.backoff.bpc == last_bpc + && (last_bpc != 0 && last_bc - slot_count != 0 + && last_dc != 0))); + dbg_assert (((last_success || ca.backoff.bpc > last_bpc) + && ca.backoff.dc == dc_table[bpcm]) + || ca.backoff.dc < last_dc); + + /* Defer or success? */ + slot_count = lib_rnd_uniform (&rnd, ca.backoff.bc + 1); + ca_backoff_deferred (&ca, slot_count); + last_success = lib_rnd32 (&rnd) < success_ratio; + if (last_success) + { + ca_backoff_success (&ca); + } + /* Save last state. */ + last_cap = cap; + last_bpc = ca.backoff.bpc; + last_cw = ca.backoff.cw; + last_bc = ca.backoff.bc; + last_dc = ca.backoff.dc; + } + return 0; +} diff --git a/mac/common/mfs.h b/mac/common/mfs.h new file mode 100644 index 0000000000..345475bcf5 --- /dev/null +++ b/mac/common/mfs.h @@ -0,0 +1,20 @@ +#ifndef mfs_h +#define mfs_h +/* Maria project {{{ + * + * Copyright (C) 2007 Spidcom + * + * <<>> + * + * }}} */ +/** + * \file mfs.h + * \brief « brief description » + * \ingroup « module » + * + * « long description » + */ + +typedef struct mfs_t mfs_t; + +#endif /* mfs_h */ -- cgit v1.2.3