본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

IP 멀티캐스팅을 위한 센트로이드 기반의 백본코아트리 생성 알고리즘
(A Centroid-based Backbone Core Tree Generation Algorithm for IP Multicasting)

서현곤   (대구대학교 정보통신공학부 BK21UU0000355  ); 김기형   (영남대학교 컴퓨터공학과UU0000951  );
  • 초록

    본 논문에서는 공유 트리에 기반에서 IP 멀티캐스팅을 위한 센트로이드 기반 백본코아트리 (Centroid-based Backbone Core Tree: CBCT) 생성 알고리즘을 제안한다 코아기반트리(Core Based Tree: CBT)는 공유 트리를 이용하여 멀티캐스트 자료를 전달하는 것으로 소스 기반 트리에 비하여 각 라우터가 유지해야 하는 상태 정보의 양이 적고, 적용하기 간단한 장점을 가지고 있지만, 코아 라우터(Core router) 선택이 어렵고, 멀티캐스트 트래픽이 코아로 집중되는 문제점을 가지고 있다. 백본코아트리(Backbone Core Tree: BCT)는 CBT의 단점을 보완하기 위해 제안되었다. BCT는 각 멀티캐스트 그룹마다 특정한 코아 라우터를 선정하지 않는 대신 코아라우터 후보들을 백본코아트리(BCT)로 연결하고, 이 트리를 통하여 코아라우터 후보들이 서로 협동하므로써 위의 두 가지 문제점을 해결한다. 이때 BCT를 어떻게 구성하는가에 따라 멀티캐스트 성능이 크게 변하게 된다. 본 논문에서는 백본코아라우터 후보들 및 이들을 연결하는 BCT를 생성하기 위해 네트워크의 최소 신장 트리와 센트로이드를 이용하는 효율적인 알고리즘 CBCT를 제시한다. 제안된 알고리즘의 성능평가를 위해서 CBT와 CBCT 프로토콜의 성능비교 결과를 보인다.


    In this paper, we propose the Centroid-based Backbone Core Tree(CBCT) generation algorithm for the shared tree-based IP multicasting. The proposed algorithm is based on the Core Based Tree(CBT) protocol. Despite the advantages over the source-based trees in terms of scalability, the CBT protocol still has the following limitations; first, the optimal core router selection is very difficult, and second, the multicast traffic is concentrated near a core router. The Backbone Core Tree(BCT) protocol, as an extension of the CBT protocol has been proposed to overcome these limitations of the CBT Instead of selecting a specific core router for each multicast group, the BCT protocol forms a backbone network of candidate core routers which cooperate with one another to make multicast trees. However, the BCT protocol has not mentioned the way of selecting candidate core routers and how to connect them. The proposed CBCT generation algorithm employs the concepts of the minimum spanning tree and the centroid. For the performance evaluation of the proposed algorithm, we showed the performance comparison results for both of the CBT and CBCT protocols.


  • 주제어

    멀티캐스트 라우팅 .   공유기반트리 .   백본코아트리 .   센트로이드 .   최소신장트리.  

  • 참고문헌 (20)

    1. D. Knuth, 'The Art of Programming : Fundarmental Algorithms,' Addison-Wesley, Vol.1, pp. 386-388, 1969 
    2. Frank Harary, 'Graph Theory(2nd edition),' Addison-Wesley, pp. 35-36, 1971 
    3. Robert Sedgewick, 'Algorithms(2nd edition),' Addison-Wesley, pp. 456-464, 1988 
    4. Ellen W. Zegura, Kenneth Calvert and M. Jeff Donahoo, 'A Quantitative Comparison of Graph-based Models for Internet Topology,' IEEE/ACM Transactions on Networking, Dec. 1997 
    5. Kenneth L. Cavert, Ellen W. Zegura and Michael J. Donahoo, 'Core Selection Methods for Multicast Routing,' Techinal Report GA3332-0280, http://www.cc.gatech.edu/tech_reports, College of Computing, Georgia Tech 
    6. Seok-Joo Koh, Shin-Gak Kang and Ki Sjik Park, 'Enhanced Cores Based Tree for Many-to-many IP Multicasting,' Telecommunications Review Vol.11, N0.3, pp. 485-493, May-June 2001 
    7. Seok-Joo Koh, Shin Gak Kang, 'Engancement of the CBT Multicast Routing Protocol,' ICPADS2001(Published by IEEE Computer Society), 26-29 June, Kyungju, Korea 2001 
    8. A. Shaikh, et al., 'Destination Driven Routing for Low Cost Multicast,' IEEE JSAC Vol. 15, No. 3, Apr. 1997 
    9. L, Guo, et al., 'QDMR: an Efficient Qos Dependent Multicast Routing Algorithm,' Proceeding of 5th IEEE Real-time Technology and Application Symposium(RTAS '99), Vancouver, Canada, June 1999 
    10. Seok J. Koh, Myung K. Shin, Jong H. Yi, Jin H. Hahm and Chee H. Park, 'Non-Core based Shared Tree Architecture for IP Multicasting,' Electronic Letters, Vol.35, No.11, pp. 872-873, May 1999 
    11. M. Faloutsis, A. Banerjea and R. Pankaj, 'QoSMIC : Quality of Service Sensitive Multicast Internet protocol,' ACM SIGCOMM'98,, Sept. 1998 
    12. A.J. Ballardie, 'Core Based Tree Multicast Routing Architecture,' RFC2201, Sept. 1997 
    13. A.J. Ballardie, 'Core Based Trees (CBT version 2) Multicast Routing-Protocol Spectification,' RFC2189, Sept. 1997 
    14. R. Perlman, C. Lee, A. Ballardie, J. Crowcroft, Z. Wang and T. Maufer, 'Simple Multicast : A Design fro Simple, Low-Overhead Multicast,' Internet-Draft:draft-peliman-simple-nulticast-01.txt, Nov. 1998 
    15. D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma and L. Wei, 'Protocol Independent Multicast-Sparse Mode(PIM-SM): Protocol Speckfication,' RFC2362, June 1998 
    16. H. Holbrook and B. Cain, 'Source-Specific Multicast for IP,' Intermet-Draft: draft-holbrook-ssm-00.txt, Mar. 2000 
    17. D. Waitzman, S. Deering and C. Partridge, 'Distance Vector Multicast Routing Protocol,' RFC 1075, Nov. 1988 
    18. S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, D. Meyer and L. Wei, 'Protocol Independent Multicast Dense Mode Specifications,' Internaet-Draft:draft-ietf-pim-v2-dm-01.txt, Nov. 1998 
    19. J. Moy, 'Multicast Extension to OSPF,' RFC 1584, Mar. 1994 
    20. Protocol Independent Multicast-Sparse Mode(PIM-SM): Protocol Speckfication , D.Estrin;D.Farinacci;A.Helmy;D.Thaler;S.Deering;M.Handley;V.Jacobson;C.Liu;P.Sharma;L.Wei , RFC2362 / v.,pp.,

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기