A cycle compression algorithm for CRMA high-speed networks
Nen-Fu Huang, C.-S. Chang, Guangsheng Ma · 2002
Cyclic-reservation multiple-access (CRMA) is an access scheme for high-speed local and metropolitan area networks based on a dual-bus configuration. In CRMA, the headend generates the reserve commands periodically. It is proved that the problem of finding a shortest cycle for a CRMA reservation (called a cycle compression problem) is NP-complete by showing that it is equivalent to the interval coloring problem. An O(n/sup 2/) approximation algorithm is proposed to solve this problem, where n is the number of stations in the network.>