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

논문 상세정보

구간 추정 기반의 지연시간을 고려한 저비용 유니캐스트 라우팅 방식
Low Cost and Acceptable Delay Unicast Routing Algorithm Based on Interval Estimation

김문성   (성균관대학교 대학원 정보통신공학부UU0000759  ); 방영철   (한국산업기술대학교UU0001397  ); 추현승   (성균관대학교 정보통신공학부UU0000759  );
  • 초록

    멀티미디어 응용 서비스에서는 특정 시간 내에 데이터 전송이 이루어져야 하는 시간 의존성이 있다. 이러한 실시간 특성은 네트웍의 QoS 보장을 위한 중요한 요소이다. 네트웍 사용자의 증가와 응용 프로그램의 데이터 전송율의 증가로 네트웍 자원을 효율적으로 사용하기 위한 연구는 계속 진행되고 있다. 종단간(End-to-End) 지연시간 제한 조건을 만족하면서 최소 비용을 갖는(Delay Constrained Least Cost, DCLC) 경로를 찾는 문제는 이미 NP-hard 문제로 알려져 있다. 최소 지연시간 경로의 비용은 최소 비용 경로의 비용보다 상대적으로 높은 경로 비용을 갖으며, 역으로 최소 비용 경로의 지연시간은 최소 지연시간 경로의 지연 시간보다 상대적으로 높은 지연시간을 갖는다. 본 논문에서는 이러한 단점을 극복하여 DCLC문제에 접근하기 위해 링크비용과 지연시간을 확률적으로 조합한 인자를 사용한 새로운 알고리즘을 연구하였다. 최근 Salama에 의해 제안된 DCUR 알고리즘은 최적에 가까운 알고리즘이나, 제안한 알고리즘은 DCUR 알고리즘과 비교하여 종합적인 컴퓨터 시뮬레이션 결과에 의하면 노드 수 200에서 38% 이상의 효과를 보았다. 본 알고리즘의 특징은 선택의 요소로서 새로운 인자를 만들었고, 링크를 순차적으로 선택하지 않고 동적으로 선택하는 방법을 구현하였다는 것이다.


    The end-to-end characteristic Is an important factor for QoS support. Since network users and required bandwidths for applications increase, the efficient usage of networks has been intensively investigated for the better utilization of network resources. The distributed adaptive routing is the typical routing algorithm that is used in the current Internet. The DCLC(Delay Constrained 1.east Cost) path problem has been shown to be NP-hard problem. The path cost of LD path is relatively more expensive than that of LC path, and the path delay of LC path is relatively higher than that of LD path in DCLC problem. In this paper, we investigate the performance of heuristic algorithm for the DCLC problem with new factor which is probabilistic combination of cost and delay. Recently Dr. Salama proposed a polynomial time algorithm called DCUR. The algorithm always computes a path, where the cost of the path is always within 10% from the optimal CBF. Our evaluation showed that heuristic we propose is more than 38% better than DCUR with cost when number of nodes is more than 200. The new factor takes in account both cost and delay at the same time.


  • 주제어

    DCLC 문제 .   DCUR 알고리즘 .   구간추정.  

  • 참고문헌 (9)

    1. A. S. Rodionov and H. Choo, 'On Generationg Random Network Structures : Connected Graphs,' Information Networking, Proc. ICOIN-18, pp.1145-1152, February, 2004 
    2. V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, 'Multicast routing for multimedia communication,' IEEE/ACM Transaction on Networkg, Vol.1, No.3, pp.286-292, June, 1993 
    3. A. S. Rodionov and H. Choo, 'On Generationg Random Networks Stuctures : Trees,' Springer-Verlang Lecuure Notes in Computer Science, Vol.2658, pp.879-887, June, 2003 
    4. D. S. Reeves and H. F. Salama, 'A distributed algorithm for delay-constrained unicast routing,' IEEE/ACM Transaction on Networking, Vol.8, pp.239-250, April, 2000 
    5. R. Widyono, 'The Design and Evaluation of Routing Algorithms for Real-Time Channels,' International Computer Science Institure, Univ. of California at Berkely, Tech. Rep, ICSI TR-94-024 
    6. D. Bertsekas and R. Gallager, 'Data Networks', 2nd Ed., Englewood Cliffs, NJ : Prentice-Hall, 1992 
    7. M. Garey and D. Johnson, 'Computers and intractability : A Guide to the Theory of NP-completencess,' New York : Freeman, 1979 
    8. C. Hedrick, 'Routing information protocol,' http://www.ietf.org/rfc/rfc1058.txt, June, 1988 
    9. J. Moy, 'OSPF Version 2,' http://www.ietf.org/rfc/rfc1583.txt, March, 1994 

 저자의 다른 논문

  • 방영철 (6)

    1. 2003 "기가비트 라우터 시스템에서의 내부 데이터 처리를 위한 소프트웨어 구조" 정보처리학회논문지. The KIPS transactions. Part C Part C c10 (1): 71~76    
    2. 2004 "차세대 인터넷 구조 진화" 電子工學會誌 = The journal of Korea Institute of Electronics Engineers 31 (4): 91~98    
    3. 2004 "EDP들의 참조 테이블을 이용한 실용적 인 경로 설정 및 파장 할당 알고리즘" 정보과학회논문지. Journal of KIISE. 정보통신 31 (2): 123~130    
    4. 2006 "이종 라우팅 메커니즘을 위한 quickest path 기반 통합 라우팅 알고리즘" 인터넷정보학회논문지 = Journal of Korean Society for Internet Information 7 (1): 143~150    
    5. 2010 "무선 센서 네트워크에서 에너지 잔량과 신호세기를 이용한 데이터 전송 프로토콜" 인터넷정보학회논문지 = Journal of Korean Society for Internet Information 11 (4): 33~39    
    6. 2011 "자기장 통신을 위한 매체 접근 제어 프로토콜의 성능분석" 한국통신학회논문지. The journal of Korea Information and Communications Society. 무선통신 36 (a5): 464~472    
  • Choo, Hyun-Seung (33)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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