For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks
Nobuo FUNABIKI Jun KAWASHIMA Kiyohiko OKAYAMA Toru NAKANISHI Teruo HIGASHINO
IEICE TRANSACTIONS on Communications
Publication Date: 2004/09/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
ICRP, heuristic algorithm, minimum dead space, NP-complete, IEEE 802.6, DQDB,
Full Text: PDF>>
With the explosive growth of the Internet system, demands for broadband communication networks have rapidly increased to provide high quality network services. For this purpose, the IEEE 802.6 MAC standard protocol defines the distributed-queue dual bus (DQDB) for metropolitan area networks (MANs). The isochronous channel reuse problem (ICRP) has been studied for efficient use of DQDB by finding proper channel assignments to incoming connection requests. In this paper, we first define the generalized isochronous channel reuse problem (GICRP) as a generalization of ICRP, to afford demands of simultaneously satisfying plural connection requests such as for multicast applications, where certain sets of connection requests must be assigned channels simultaneously. We prove the NP-completeness of its decision problem. Then, we propose a minimum dead space (MDS) algorithm as a heuristic approach to GICRP. The extensive simulation results show that with shorter computation time, our MDS algorithm can always find better channel assignments reducing the waiting time for packet transmissions than the best existing algorithm for conventional ICRP.