summaryrefslogtreecommitdiff
path: root/mac
diff options
context:
space:
mode:
authorschodet2007-03-23 17:18:53 +0000
committerschodet2007-03-23 17:18:53 +0000
commita2c17d2b7b09a1401eb9bdd7d41ebade6e69cb31 (patch)
tree8d41a49fc1a991bcdee72c528ac8e18bd73551dd /mac
parent66aca88d7494c2e3c0453339dd324a3139b0e47f (diff)
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
Diffstat (limited to 'mac')
-rw-r--r--mac/ca/Module1
-rw-r--r--mac/ca/ca.h115
-rw-r--r--mac/ca/inc/backoff.h55
-rw-r--r--mac/ca/inc/context.h49
-rw-r--r--mac/ca/src/backoff.c36
-rw-r--r--mac/ca/test/backoff/Makefile7
-rw-r--r--mac/ca/test/backoff/src/test_backoff.c89
-rw-r--r--mac/common/mfs.h20
8 files changed, 372 insertions, 0 deletions
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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file test_backoff.c
+ * \brief Test backoff code.
+ * \ingroup test
+ */
+#include "common/std.h"
+
+#include "mac/ca/inc/context.h"
+
+#include <stdio.h>
+
+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
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file mfs.h
+ * \brief « brief description »
+ * \ingroup « module »
+ *
+ * « long description »
+ */
+
+typedef struct mfs_t mfs_t;
+
+#endif /* mfs_h */