Abstract
Cyclic-Reservation Multiple-Access (CRMA) is an access scheme for high-speed local and metropolitan area networks based on a dual-bus configuration. CRMA provides high throughput efficiency and fairness independent of the network speed or distance. In CRMA, the headend generates the reserve commands periodically. Each station reserves a number of slots in each reserve command if necessary. The headend will generate a sequence of cycles each of which is used to service the reservations on the corresponding reserve command. The length of each cycle is equal to the total number of slots reserve by the stations in the corresponding reserve command. Generally, a longer cycle length will conduct a longer access delay and a lower slots utilization. It is desirable to have a scheme to make the cycle length as short as possible. In this paper, we prove that the problem of finding a shortest cycle for a CRMA reservation (called as cycle compression problem) is NP-complete by showing that it is equivalent to the internal coloring problem. We also propose an O(n 2 ) approximation algorithm to solve this problem; where n is the number of stations in the network.