Title :
A cycle compression algorithm for CRMA high-speed networks
Author :
Huang, Nen-Fu ; Chang, Chiu-Sen ; Ma, Gin-Kou
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Abstract :
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(n2) approximation algorithm is proposed to solve this problem, where n is the number of stations in the network
Keywords :
approximation theory; computational complexity; cyclic reservation multiple access; graph colouring; local area networks; metropolitan area networks; polynomials; trees (mathematics); CRMA high-speed networks; approximation algorithm; cycle compression problem; cyclic reservation multiple access; dual-bus configuration; interval coloring; local area networks; metropolitan area networks; Approximation algorithms; Compression algorithms; Computer science; Delay; High-speed networks; Local area networks; Metropolitan area networks; Mice;
Conference_Titel :
Communications, 1993. ICC '93 Geneva. Technical Program, Conference Record, IEEE International Conference on
Conference_Location :
Geneva
Print_ISBN :
0-7803-0950-2
DOI :
10.1109/ICC.1993.397511
