A deadlock model for a multi-service medium access protocol employing multi-slot N-ary stack algorithm (msSTART)

Many modern multi-service medium access protocols (MACs) use a collision based capacity request signaling channel as part of a hybrid TDMA frame structure. Multi-slot Stack Random Access Algorithm (msSTART) is proposed for use in IEEE 802.14 hybrid fiber/coaxial network and will be highly relevant for the S-MAC development of evolving WATM MAC specifications. This paper studies the performance of msSTART as an example of a Q-ary tree contention resolution algorithm (CRA) in the wireless environment using the novel Basic Deadlock model. We contrast approximate results for msSTART performance obtained by simulation under extreme inter-station correlation with analytical results for the more popular p-persistence CRA used in several testbed WATM implementations. Using three signaling channel schemes designed to provide support for increased system stability, to implement priority in the wireless MAC, and maximise efficiency, we provide comparative results for evaluation of msSTART and p-persistence ALOHA under what the IEEE 802.14 working group has termed the 'disaster scenario'. We find that of the three schemes evaluated the full Contention Mini-Slot (CMS) sharing scheme employing multiple CMSs per data region extends the protocol's useable load region the furthest. We conclude that Q-ary tree contention resolution algorithms (in particular msSTART) are best adapted to the wireless environment, providing less case sensitive performance.