A minimum dead space algorithm for generalized isochronous channel reuse problems m DQDB networks

Nobuo Funabiki, Jun Kawashima, Kiyohiko Okayama, Toru Nakanishi, Teruo Higashino

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)2692-2698
Number of pages7
JournalIEICE Transactions on Communications
Issue number9
Publication statusPublished - Sept 2004


  • DQDB
  • Heuristic algorithm
  • ICRP
  • IEEE 802.6
  • Minimum dead space
  • NP-complete

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'A minimum dead space algorithm for generalized isochronous channel reuse problems m DQDB networks'. Together they form a unique fingerprint.

Cite this