A fast optimal slot reuse scheme for CRMA high speed networks

Cyclic-reservation multiple-access (CRMA) is an access scheme for high-speed local and metropolitan area networks based on folded-bus or dual-bus configurations. CRMA provides high throughput and fairness independent of the network speed or distance. In CRMA, the headend generates reserve commands periodically. Each station may reserve a number of empty slots in each reserve command if necessary. Corresponding to every reserve command, the headend generates a cycle of length equal to the total number of empty slots reserved. Every cycle is used to serve the reservations made on its corresponding reserve command. Generally, a longer cycle length means a longer access delay and a lower throughput. Therefore, it is desirable to develop a scheme such that the cycle length is the shortest. The authors study the problem of reducing the total number of empty slots generated within every cycle. However, it has been shown that the problem is NP-complete under the constraint that all the empty slots used by a station in a cycle are required to be consecutive. They release the slot-contiguity constraint and propose a fast optimal slot reuse scheme with low time complexity O(M²), where M is the number of stations. To evaluate the effectiveness of the slot reuse scheme, a large number of computer simulations are performed. They compare the slot reuse scheme with the original CRMA in terms of the following three important performance measurements: average cycle length, average throughput, and average MAC delay