Depth first traversal algorithm for the back-off tree of distributed queuing

Abstract

An analytic model was provided for the conventional distributed queueing (DQ) and its back-off tree operations, followed by a design of improving algorithm based on depth first traversal.Combing the specific analysis of complete binary tree with generalized extension by random tree reconstruction, the performance of proposed algorithm was evaluated on the throughput in both theory and simulation experiment.A theoretic optimal solution of contention slots of DQ frame and a brief description of simulation extension based on the open source NS-3 were presented.The simulation results show that the maximum stationary throughput by the proposed algorithm reaches 70% of the physical capacity of channel.

Keywords

• random multiple access;distributed queuing;exponential back-off tree;depth first searching;performance evaluation