A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks


IEICE TRANSACTIONS on Communications   Vol.E87-B   No.9   pp.2692-2698
Publication Date: 2004/09/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
ICRP,  heuristic algorithm,  minimum dead space,  NP-complete,  IEEE 802.6,  DQDB,  

Full Text: PDF(271KB)>>
Buy this Article

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.