Ring optimal assignment of slot reservations for Cyclic TDMA Protocols

Abstract

We present two algorithms to assign time slots to nodes in a TDMA network that minimize the jitter in time slot assignments or minimize the channel access latency for flows with a known arrival time. The algorithms are designed for TDMA MAC layers where a node has the potential to reserve some number of time slots out of a larger selection of available time slots, and one wishes to choose the time slots that optimize performance. Because in TDMA protocols time slots are typically arrange in a repeating sequence, the algorithms operate on a ring. The first algorithm solves the Minimum Variance Placement problem for time slots around the ring, which may be useful for variable or unpredictable traffic. The second algorithm finds the set of time slots that minimize the switching latency between known inflows and time slots used for outflows, and approximates a solution to the Capacitated K-Median Problem with Splittable Loads.