KR100194608B1

KR100194608B1 - Atm 통신망에서의 멀티캐스트 경로 할당방법

Info

Publication number: KR100194608B1
Application number: KR1019960055702A
Authority: KR
Inventors: 양선희; 김봉태; 고병도
Original assignee: 이계철; 한국전기통신공사; 정선종; 한국전자통신연구원
Priority date: 1996-11-20
Filing date: 1996-11-20
Publication date: 1999-06-15
Also published as: KR19980037020A; US6088333A

Abstract

본 발명은 ATM 통신망에 적용할 수 있는 멀티캐스트 경로 할당방법으로서, 종래에는 통신망 상의 소스노드와 목적노드들간을 연결하는 최소 비용 연결 경로를 구하되 계산량을 줄이기 위해 먼저 해당 소스노드와 목적노드들만으로 망을 단순화 한 후 모든 목적노드들이 연결될때까지 가장 비용이 싼 링크부터 하나씩 추가해 나감으로서 최소 비용 연결 경로를 찾아낸다.

따라서 전체망을 대상으로 연결 경로를 찾아내는데 비해서 계산량을 줄일수 있으나, 소스노드와 목적노드들 사이에 존재하는 셀복사노드에 대한 정보가 무시되므로 전체 멀티캐스트 경로 상에서의 경로중첩 효과가 반영되지 않아 링크 대역폭의 낭비를 가져온다.

본 발명에서는 멀티캐스트 경로상의 여러 목적노드들간에 경로가 중첩되도록 하기 위해 두 개 이상의 목적노드들이 연결되어 있는 경유 노드로서 셀 복사 기능을 가지며 각각의 목적노드들로 별도 경로를 할당하는 것보다 이 경유노드에서 셀을 복사하여 전달하는 것이 더 경제적인 가상목적노드를 사용하여 멀티캐스트 경로를 구한다.

이를 위해 망을 모델링할 때 소스노드와 목적노드들간의 관계만을 보는 것이 아니라 중간의 가상목적노드들과의 관계도 고려함으로서 목적노드 그룹들간의 경로 중첩 효과가 반영된 경로가 구해진다.

Description

ATM 통신망에서의 멀티캐스트 경로 할당방법

본 발명은 ATM 통신망에 적용할 수 있는 멀티캐스트 경로 할당방법으로서, 멀티캐스트 경로 설정에 대한 종래의 방법들은 주로 대역폭을 최적으로 사용하기 위한 방법으로 컴퓨터 네트워크에서의 비실시간 서비스에 대한 경로 할당을 한다.

일반적으로 통신망을 구성하는 각 링크에 대해 경로 설정 기준을 고려한 비용함수를 정의하고, 소스노드와 목적노드들간을 연결하는 총 비용이 최소가 되는 경로를 찾는다.

따라서 종래 방법에서는 통신망 상의 소스노드와 목적노드들간을 연결하는 최소 비용 연결 경로를 구하되 계산량을 줄이기 위해서, 먼저 해당 소스노드와 목적노드들만으로 망을 단순화 한후, 모든 목적노드들이 연결될때까지 가장 비용이 싼 링크부터 하나씩 추가해 나감으로써 최소 비용 연결 경로를 찾아낸다.

이에 따라 전체 망을 대상으로 연결 경로를 찾는데 비해서 계산량을 줄일수는 있으나, 소스노드와 목적노드들 사이에 존재하는 셀복사가 일어나는 경유 노드인 셀복사 노드에 대한 정보가 무시되게 된다.

따라서 전체 멀티캐스트 경로 상에서의 경로 중첩 효과가 반영되지 않게 되어 링크 대역폭의 낭비 요인이 된다.

본 발명에서는 멀티캐스터 경로 할당시 다중의 목적노드들간에 경유 경로를 공유할 수 있도록 경로를 할당함으로써 링크 사용 효율을 개선시킨다.

제1도(a),(b),(c)는 본 발명이 적용되는 ATM 망 구성도.

제2도는 본 발명에 따른 멀티캐스트 경로를 구하는 절차도.

제3도는 본 발명에 따른 멀티캐스트 경로 할당을 위한 기능블럭도.

제4도는 본 발명의 가상목적 검색 절차도.

제5도는 본 발명의 멀티캐스트 클러스터 구성도.

제6도(a)에서 제6도(e)는 본 발명을 적용한 실시예의 구성도.

* 도면의 주요부분에 대한 부호의 설명

1001 : 소스노드 1002, 1003, 1004 : 목적노드

1005 : 경유노드 1101 - 1106 : 물리 링크

본 발명은 ATM 망에서 멀티캐스트 경로를 구할 때 다중의 목적노드들간에 경로가 중첩되도록 하기 위해 가상목적노드를 검색하는 방법 및 이를 이용한 경로 할당방법에 관한 것으로서, 이하 첨부된 도면을 참조하여 본 발명을 상세히 설명하면 다음과 같다.

제1도(a),(b),(c)는 본 발명이 적용되는 ATM 망 구성도이다.

먼저 상기 제1도(a)는 ATM 물리망을 나타낸 도면이다.

상기 망은 다섯 개의 가상경로/가상채널(VP/VC) 교환노드와 그들 간을 연결하는 링크로 구성된다.

상기 A 노드(1001)SMS 소스노드이고, B 노드(1002)와 D 노드(1003)와, E 노드(1004)가 목적노드들이다.

또한, C 노드(1005)는 경유노드로서 셀 복사 기능을 갖지 않으며 가입자들이 연결되지 않는다.

상기 노드들간을 연결하는 링크들(1101-1106)은 할당 가능 대역폭과 고유의 지연 특성을 갖는 물리 링크들이다.

제1도(b)는 상기 제1도(a)의 ATM 물리망을 가상경로(Virtual Path) 레벨에서 재구성한 멀티캐스트 망 모델이다.

상기 각 연결노드는 셀 복사 기능을 갖는 가상경로/가상채널(VP/VC) 교환기이며, 연결 링크(1201-1207)SMS 가상경로(VP) 링크로서 하나 이상의 물리링크로 구성될 수 있다.

예를 들어 A 노드(1001)와 F 노드(1006)를 연결하는 링크(1207)는 A(1001) - B(1002) - D(1003) - E(1004) - F(1005) 혹은 A(1001) - B(1002) - C(1005) - E(1004) - F(1006)의 4개물리 링크를 경유하는 가상경로(VP) 링크가 된다.

상기 C 노드(1005)는 전자에 언급했듯이 셀 복사 기능을 갖지 않으며 가입자들이 연결되지 않으므로 멀티캐스트 망 모델에서는 나타나지 않는다.

상기 각 가상경로 링크(1201-1207)에 대해 비용함수 Ce(A, B)(1211)와 지연함수 De(A, B)(1212)가 주어진다.

상기 비용함수(1211)는 링크 사용에 대한 비용으로서 대역폭 요구량과, 가상경로(VP) 링크가 경유하는 물리 링크의 개수 등 여러 가지 비용 발생 요소를 고려하여 정의할 수 있다.

또한, 상기 지연함수(1212)는 가상경로(VP)링크의 지연 특성을 나타낸 값으로서 가상경로 링크의 총 길이와, 단위 트래픽이 겪게 되는 교환 지연 및 전달 지연 등을 고려하여 정의할 수 있다.

상기 제1도(c)는 상기 제1도(b)의 멀티캐스트 망모델 상에서 소스노드 A(1001)로부터 목적노드 그룹 B(1002)와, D(1003), E(1004)를 연결하는 멀티캐스트 경로 모델 T(A,{B, D, E})를 구성한 도면이다.

상기 멀티캐스트 경로 모델은 방향성을 갖는 점 대 다중점 데이터 흐름을 표현하기 위한 모델로서 소스를 루트(root)로 목적노드를 잎(leaf)들로 하는 트리 T(s, {M})로 표현된다.

제2도는 본 발명에 따른 멀티캐스트 경로를 구하는 절차도이다.

망이 초기화 될 때 노드 개수와, 노드별 연결 링크와, 링크별 가용 대역 및 비용과 지연 특성, 노드별 셀 복사 기능 유무와 가입자 접속 여부의 물리망 구성에 대한 초기화 데이터가 다운로드된다(201).

상기 과정은 물리망 구성에 대한 초기화 데이터가 망 자원관리자(Net_Rsc_Manger)(306)로부터 망 모델링 관리 프로세스(Network_Model_Proc)(304)로 다운로드되는 과정이다.

상기 망 모델링 관리 프로세스(Network_Model_Proc)(304)는 다운로드 받은 물리망 구성 데이터를 이용하여 물리망 구성 테이블(Tbl_Phy_Net)(316)을 작성한다(202).

물리망 구성 테이블이 작성되면 이로부터 가상경로(Virtual Path, VP) 레벨의 멀티캐스트 가상망 모델 테이블(Tbl_VM_Net)(317)을 구성한다(203).

상기 멀티캐스트 가상망은 물리망 상에 멀티캐스트 용 가상경로(VP)를 할당하여 마치 멀티캐스트 전용의 가상 망이 있는 것처럼 구성된 가상경로(VP) 레벨의 망이다.

상기 가상망 모델 테이블(317)의 구성은 망 운용자의 개입 하에 이루어지거나 자동적으로 구성될 수 있는데 본 발명에서는 자동 생성되도록 구현하였다.

먼저 상기 가상망 모델 테이블이 구성되면 각 노드 사이에 할당된 가상경로(VP) 연결의 지연 및 비용에 대한 계산이 이루어져 기록된다(204).

상기 가상 경로의 비용 및 지연 데이터는 가상경로(VP) 연결 경로를 구성하는 각 물리 링크의 비용 및 지연 정보를 갖고 있는 상기 물리망 구성 테이블(Tbl_Phy_Net)로부터 가져와서 계산된다.

상기 멀티캐스트 가상망이 구성되면 초기화가 끝나고 가입자로부터의 멀티캐스트 요구를 대기하게 된다.

가입자로부터 멀티캐스트 요구가 발생하면(205), 노드에 존재하는 경로 처리 프로세스(Node_Proc)는 가입자가 요구한 소스노드 s와, 목적노드그룹{M}과, 서비스 유형 및 경로 할당 제한 사항들을 입력 받아 유효성을 검사한다(206).

검사 후 상기 가입자의 요구가 유효한 경우 경로 할당 절차가 시작된다.

상기 노드의 경로 처리 프로세서(Node_Proc)(302)는 경로 할당 요구를 망관리 프로세스(Network_Manager_Proc)(303)를 거쳐 경로 할당 프로세스(Multi_Router_Proc)(305)로 보낸다.

상기 경로 할당 프로세스(305)는 멀티캐스트 가상망(Tbl_VM_Net)과 소스노드 s와, 목적노드 그룹 {M}등의 정보를 이용하여 가상목적노드 그룹{VD}를 구성한다(207).

가상목적노드는 두 개 이상의 목적노드가 연결되어 있는 경유노드로서 각각 별도의 경로를 통해 셀을 전달하는 것보다 이 가상목적노드에서 셀이 복사되어 전달되는 것이 총 링크 사용을 줄일 수 있는 노드이다.

상기 가상목적노드 그룹이 구해지면 각 가상목적노드에 대해 경로중첩 효율을 계산한다(208).

경로중첩효율은 그 가상목적노드로부터 셀 복사되어 연결될 수 있는 목적노드의 개수이다.

망을 단순화하기 위해 필요한 상기 소스노드 s와, 목적노드 그룹 {M}과, 가상목적노드 그룹{VD}가 구해졌으므로 이들을 연결하는 완전 연결 망을 구성한다(209).

상기 완전 연결망은 s와, {M}과, {VD}의 각 노드간에 최소 비용 연결 경로를 통해 Full-Mesh로 연결된 망 모델로서, 계산량을 줄이면서 멀티캐스트 경로를 찾기 위해서 망을 단순화하는 과정이다.

상기에 따라 두 노드 A와, B간에 최소 비용 연결 경로를 찾는 과정은 멀티캐스트 가상망 모델상에서 A 노드로부터 B 노드가 연결될때까지 가장 가까운 즉 비용이 가장 적게 들면서 연결될 수 있는 노드가 C 노드이면 일단 A-C 간을 선택한다.

그 다음 A-C 전체를 마치 하나의 노드처럼 간주하고 그 다음 가까운 노드를 찾는다.

예를 들어 C-D 연결 경로가 가장 가까운 경우 연결 경로(A-C-D)가 찾아간다.

상기 과정을 A-B 노드가 연결될때까지 반복한다.

상기 s와, {M}과, {VD}간이 완전히 연결된 망 모델 테이블(Tbl_Clos_Net)이 구성되면 다시 각 노드간을 연결하는 가상경로(VP)의 비용 및 지연값을 계산하여 기록한다(210).

상기 완전 연결망 모델을 구성하는 가상경로(VP) 연결 경로는 멀티캐스트 가상망의 하나 이상의 가상경로 연결이 직 연결될 수 있으며, 따라서 지연 및 비용 값은 각각의 가상경로의 값을 누적한 값이 된다.

이때 상기 s와 각 가상목적노드를 연결하는 경로의 비용은 상기(208)과정에서 구한 경로중첩 효율로 나누어 준다.

이렇게 함으로써 경로중첩 효율이 큰 경로가 상대적 비용이 싸지게 되므로 다른 링크에 비해 우선적으로 선택되게 된다.

따라서 나중에 멀티캐스트 경로를 구할 때 우선적으로 선택되어지게 되어 경로 중첩 효과가 반영되게 된다.

상기 s와, {M}과, {VD}가 Full-Mesh 형태로 연결된 완전 망이 구성되었으므로 이로부터 최소 비용 멀티캐스트 경로를 할당한다(211).

상기 최소 비용 멀티캐스트 경로를 구하는 과정은 상기 (209)과정과 유사하나, 이 과정을 모든 목적노드 그룹이 다 연결될때까지 반복해야 한다.

상기 목적노드들을 하나씩 연결해 나가는 과정에서 가상목적노드가 포함되어지는 경우에는 그 가상목적노드를 통해 전달되는 목적노드들은 연결이 된 것으로 간주한다.

상기와 같이 해서 최소 비용 멀티캐스트 연결 경로가 구해지면 그 결과를 노드들에게 통보하고(212), 결과는 멀티캐스트 가상망 모델 테이블에 반영한다(213).

경로 할당이 끝났으므로 다시 멀티캐스트 대기 상태로 복귀한다(214).

제3도는 본 발명에 따른 멀티캐스트 경로 할당을 위한 기능블럭도이다.

멀티캐스트 경로 할당을 위한 기능은 크게 관리 프로세스(Manager-Proc)(301)와 노드 프로세스(Node_Proc)(302)로 구성된다.

상기 관리 프로세스(301)은 멀티캐스트 경로 할당을 위한 망 자원관리와, 망 모델링 관리와, 경로 할당 및 경로 관리 기능 등으로 구성된다.

그리고 Network_Manager_Proc(303)은 망 구성 및 상태 데이터의 초기화 및 관리와, 경로 할당 관리를 수행하는데, Net_Rsc_Manager과, Net_Status_Manager과, Route_Manager로 구성된다.

또한, Net_Rsc_Manager(306)은 물리망 구성에 대한 정보와 링크 비용이나 지연 특성에 대한 관리 기능으로서 망 모델링 관리 프로세스(Network_Model_Proc)(304)에게 망 구성 및 자원의 특성 데이터를 넘겨주어 망을 모델링 할 수 있도록 한다.

다음 Net_Status_Managers(307)는 망 구성 요소 시스템인 노드나 링크의 상태 데이터를 노드들로부터 보고 받아 이를 처리하고, 상태의 변화를 망 모델 테이블에 갱신(Update)하도록 하는 기능이다.

그리고 Route_Manager(308)는 노드나 운용자로부터 멀티캐스트 경로 할당에 대한 요구를 접수하여 요구 내용을 검증하고, 관련 경로 할당 기능에게 이의 수행을 요구하는 기능이다.

Network_Model_Proc(304)는 상기 Network_Manager_Proc(303)으로부터 넘겨 받은 망 구성 및 자원 특성 데이터와 망 상태 데이터를 이용하여 멀티캐스트 경로 할당을 위한 망 모델을 구성하는 프로세스이다.

상기 Network_Model_Proc(304)안의 Creat_Phy_Net(309) 기능은 물리망을 구성하는 노드와 링크에 대한 정보를 기록하는 물리망 모델 테이블(Tbl_Phy_Net)을 작성한다.

또한, Make_VM_Net(310) 기능은 Tbl_Phy_Net 테이블로부터 가상경로 레벨의 멀티캐스트 경로용 가상 망 모델을 구성하여 멀티캐스트 가상망 모델 테이블(Tbl_VM_Net)을 작성한다.

그리고 Compute_LK_Cost(312) 기능은 멀티캐스트용으로 할당된 각 가상경로에 대한 비용과 지연값을 계산하는 기능으로서 비용과 지연값은 물리적 구성 데이터로부터 자동 생성되거나 혹은 운용자가 정의한 함수를 적용할 수도 있다.

다음 Update_Net_Mdl(311) 기능은 망 상태가 바뀌거나 운용자의 요구가 있을 때 물리망 및 멀티캐스트 가상망 테이블을 변경하는 기능이다.

Multi_Router_Proc(305)는 사용자의 멀티캐스트 요구가 오면 경로를 할당해 주는 기능블럭이다.

상기 블록은 크게 Find_VD_Node(313)과, Make_Closure_Net(314)와, Make_Shortest_Route(315)의 세 기능으로 구성된다.

상기 Find_VD_Node(313)는 사용자가 요구한 소스노드 s와, 목적노드그룹{M}과 Tbl_VM_Net에 대한 정보를 이용하여 가상목적노드를 찾아내고, 각 가성목적노드에 연결되는 목적노드 및 경로중첩효율을 계산하는 기능이다.

그리고 Make_Closure_Net(314)는 Tbl_VM_Net 구성 데이터로부터 s와, {M}과, {VD} 노드간을 가장 비용이 적게되는 경로를 통해 Full_Mesh 형태로 연결한 단순화된 망을 구성하고, 각 노드들을 연결하는 가상경로 연결(Virtual Path Connection)의 비용 및 지연값을 계산하여 Tbl_Clos_Net(318)에 기록하는 기능이다.

상기 Make_Shortest_Route(315)는 상기 Make_Closure_Net(314)가 만든 단순화된 연결망에서 소스노드 s와 목적노드 {M}을 연결하는 최소 비용 경로를 찾아내는 기능이다.

상기 Node_IF_Proc(305)는 상기 Node_Proc(302)와 Manager_Proc(301) 간의 인터페이스 메시지 교환(316)을 처리하는 기능이다.

제4도는 본 발명의 가상목적 검색 절차도이다.

상기 절차에 따라 Route_Manager(308)은 멀티캐스트 경로 할당 요구가 발생하면 Find_VD_Node(313) 기능에게 가상목적노드 검색을 요구한다(401).

상기 검색 요구가 발생하면 멀티캐스트 가상망(Tbl_VM_Net)과 목적노드 그룹 {M}에 대한 정보를 이용하여 각 목적노드들이 연결되어 있는 인집 경유 노드들을 검색한다(402).

상기 검색된 모든 인접 노드들에 대해 두 개 이상의 목적노드가 동시에 연결된 셀 복사 대상 노드 B(i)들을 찾아낸다(403).

상기 각 셀 복사 노드 B(i)에 대해 목적노드들에 대한 멀티캐스터 클러스터를 구성한다(404).

상기 멀티캐스터 클러스터는 제5도에 나타낸 것처럼 소스노드와 셀 복사 대상 노드 B(i)와, B(i)를 통해 연결되는 목적노드들에 대한 가장 짧은 경로를 나타낸 경로도로서 찾아진 B(i)가 가상목적노드에 포함될 수 있는지를 조사하기 위한 것이다.

상기 멀티캐스터 클러스터가 구성되면 각 클러스터에 대해 경로 제한 조건을 검사한다(405).

먼저 비용 제한 조건을 조사하는데(406) 비용제한 조건은 s로부터 클러스터의 각 목적노드를 별도 경로를 통해 접속하는 경우와 s로부터 B(i)까지 공통 경로를 통해 한 연결로 전달되고 B(i)에서 각 목적노드로 브랜칭되어 연결되는 경우의 비용을 계산하여 비교함으로써 어느 경로가 더 경제적인지를 판단하는 과정이다.

만약 별도 경로를 통해 연결되는 것이 망자원 사용 효율이 좋은 경우에는 B(i)는 가상목적노드에서 배제된다(407).

상기 B(i)가 비용제한 조건을 만족시키는 경우 지연 제한 사항을 조사하는데(408) B(i)를 통해 접속되는 경우 그 클러스터에 속하는 각 목적노드의 종단간 지연이 서비스 품질 요구사항을 만족시킬 수 있는지를 검사하는 과정이다.

만약 B(i)를 통해 경로가 중첩되도록 연결하는 경우 지연 제한 사항을 만족시키지 못하면 B(i)는 가상목적노드가 될 수 없다(409).

반면에 비용 제한 및 지연을 다 만족시키는 경우 B(i)는 가상목적노드 그룹{VD}에 포함된다(410).

상기 제한조건 검사는 모든 멀티캐스터 클러스터에 대해 이루어져야 한다(411).

상기 {VD}검사가 끝나면 각 가상목적노드에 대해 경로중첩효율 및 해당 클러스터에 포함되는 목적노드에 대한 정보를 기록한다(412).

제5도는 본 발명의 멀티캐스터 클러스터 구성도이다.

상기 구성을 보면 목적노드 m1(503)과, m2(504)와, m3(505)가 셀 복사노드 B(502)에 연결되어 소스노드 s(501)와 함께 하나의 멀티캐스터 클러스터를 구성한다.

상기 각 목적노드 m(i)는 s로부터 별도의 경로를 통해 연결되는 경로(507, 508, 509)를 가지며, B를 통해 경로 중첩되어 연결되는 경우에는 s로부터 B까지 상기 (509)경로로 연결되고, B에서 브랜칭되는 510과, 511과, 512 연결 경로로 접속될 수 있다.

각 노드들을 연결하는 경로들은 비용 C(a,b) 및 지연 D(a,b)를 갖는다.

예를 들어 상기 (509) 링크의 경우 C(s, B)와, D(s,B) 값이 정의되며, 경로중첩효율이 3이 된다.

이에 따라 제5도에서 경로의 비용 제한 조건은 중첩 경로인 (509)와, (510)과, (511)과, (512) 링크의 총 비용이 별도 링크인 (506)과, (507)과, (508)의 합보다 작아야 된다.

그리고 지연 제한 조건은 중첩 경로를 통해 전달되는 각 목적노드들의 종단간 지연이 최대 허용 지연을 초과하지 않아야 되는 것이다.

즉, m1 노드의 경우 중첩 경로인 (509)와, (510) 링크를 통해 접속될 때의 통 지연이 최대 허용 지연보다 작아야 한다.

상기 조건은 m2와, m3 노드에 대해서도 만족되어야만 B 노드가 가상목적노드가 될 수 있다.

제6도(a)에서 제6도(e)는 본 발명을 적용한 실시예의 구성도이다.

상기 구성도의 (a) 와 같은 멀티캐스터 가상망이 구성된 예에서 s(601)로부터 모든 V_i노드들에게 데이터를 멀티캐스팅하고자 하는 경우 중간의 V 노드(602)를 경유하는 경우와 그렇지 않고 s로부터 직접 모든 목적노드들에게 경로를 할당하는 경우가 가능하다.

본 발명에서 기술한 가상목적노드 방식을 적용하는 경우 (b)의 가상목적노드를 먼저 구하게 된다.

즉, V 노드(611)가 가상목적노드가 되고, V 노드에 연결된 목적노드가 k개이므로 (612) 링크의 경로중첩효율은 k가 된다.

따라서 (c)와 같은 완전연결망이 구해진다.

상기 (c)의 완전연결망 상에서 최소 비용 경로를 구하면 먼저 s 노드와 V 노드 연결 경로(621)가 찾아진다.

왜냐하면 상기 연결 경로(621) 링크의 경우 경로중첩 효율이 k 이므로 비용이 1/k가 되므로 가장 비용이 작은 링크가 되기 때문이다.

일단 상기 V 노드가 찾아지면 가상목적노드 정의에 의해 상기 V에 연결된 모든 목적노드들이 자동 연결되므로 멀티캐스트 경로 할당이 끝나게 되어 (d)의 경로가 구해진다.

상기 경우 총 비용은 (1+k)가 된다.

그러나 종래의 방식에서는 상기 (a)의 망에서 최소비용 경로를 찾으면 s로부터 V_i로 직접 연결되는 경로가 찾아지므로 (e)의 경로가 구해진다.

따라서 총 비용이 1k가 된다.

상기에 따라 본 발명에서 기술한 방법을 이용하는 경우 망자원 사용 효율이 (1+k)/1k로 개선됨을 알 수 있다.

본 발명은 멀티캐스터 경로 할당시 다중의 목적노드들간에 경유 경로를 공유할 수 있도록 할당함으로써 링크 사용 효율을 개선시킬 수 있다.

특히 망의 노드 개수가 많은 대규모 망과 목적노드 그룹들이 집중화되어 있을수록 기존의 방법에 비해 링크 사용 효율이 개선될 수 있다.

따라서 본 발명에서 제안한 방법은 사설 및 공중 ATM 망의 멀티캐스팅 경로 할당방법으로 적용될 수 있다.

ATM 통신망은 VOD나 다자간 영상회의와 같은 멀티캐스트 서비스를 지원해야 한다.

점대 다중점 연결 형상을 요구하는 경우에는 임의의 소스노드로부터 다중의 목적노드로의 데이터 전달이 이루어져야 하므로 유니캐스트 서비스에 비해 총 사용 대역폭이 절대적으로 많아진다.

따라서 망 사용 효율을 높이기 위해서는 망 자원을 효율적으로 사용할 수 있는 멀티캐스트 경로 설정 방식이 요구된다.

본 발명의 목적은 ATM 통신망에 적용할 수 있는 멀티캐스트 경로 설정 방식으로서 가급적 목적노드 가까이서 셀 복사가 일어나도록 함으로써 목적노드들간의 경유 경로를 최대한 공유하게 하여 총 링크 사용을 줄이도록 한다.

Claims

ATM망에서 멀티캐스트 경로를 할당할 때 경로가 중첩되도록 하기 위해 가상목적노드를 검색하는 제1과정과; 상기 가상목적노드를 이용하여 멀티캐스트 경로를 할당하는 제2과정을 포함하여 이루어지는 것을 특징으로 하는 ATM 통신망에서의 멀티캐스트 경로 할당방법.
제1항에 있어서, 상기 제1과정은 Route_Manager(308)로부터 멀티캐스트 경로할당요구가 발생하면 Find_VD_Node(313) 기능이 가상목적노드를 검색하는(401) 제1단계와, 상기 검색후 멀티캐스트 가상망(Tbl_VM_Net)과 목적노드 그룹{M}에 대한 정보를 이용하여 각 목적노드들이 연결되어 있는 인접 경유 노드들을 검색하는(402) 제2단계와, 상기 검색된 모든 인접 노드들에 대해 두 개 이상의 목적노드가 동시에 연결된 셀 복사 대상 노드 B(i)들을 찾아내고(403) 상기 각 셀 복사 노드 B(i)에 대해 목적노드들에 대한 멀티캐스터 클러스터를 구성하는(404) 제3단계와, 상기 멀티캐스터 클러스터가 구성되면 각 클러스터에 대해 경로 제한 조건에 대해 먼저 비용 제한 조건을 조사하는데(406) 비용 제한 조건은 s로부터 클러스터의 각 목적노드를 별도 경로를 통해 접속하는 경우와 s로부터 B(i)까지 공통 경로를 통해 한 연결로 전달되고 B(i)에서 각 목적노드로 브랜칭되어 연결되는 경우의 비용을 계산함으로서 어느 경로가 더 경제적인지를 판단하는 제4단계와, 상기 {VD}검사가 끝나면 각 가상목적노드에 대해 경로중첩효율 및 해당 클러스터에 포함되는 목적노드에 대한 정보를 기록하는(412) 제5단계를 포함하여 이루어지는 것을 특징으로 하는 ATM 통신망에서의 멀티캐스트 경로 할당방법.
제1항에 있어서, 상기 제2과정은 망이 초기화 될 때 노드 개수와, 노드별 연결 링크와, 링크별 가용 대역 및 비용과 지연 특성과, 노드별 셀 복사 기능 유무와 가입자 접속 여부의 물리망 구성에 대한 초기화 데이터가 다운로드하는(201) 제1단계와, 상기 망 모델링 관리 프로세스(Network_Model_Proc)(304)는 다운로드 받은 물리망 구성 데이터를 이용하여 물리망 구성 테이블(Tbl_Phy_Net)(316)을 작성하는(202) 제2단계와, 상기 물리망 구성 테이블이 작성되면 이로부터 가상경로(Virtual Path, VP)레벨의 멀티캐스트 가상망 모델 테이블(Tbl_VM_Net)(317)을 구성하는(203) 제3단계와, 상기 가상망 모델 테이블이 구성 후 각 노드 사이에 할당된 가상경로(VP) 연결의 지연 및 비용에 대한 계산이 이루어져 기록하는(204) 제4단계와, 상기 멀티캐스트 가상망이 구성되면 초기화가 끝나고 가입자로부터의 멀티캐스트 요구를 대기하는 제5단계와, 상기 가입자로부터 멀티캐스트 요구가 발생하면(205), 노드에 존재하는 경로처리 프로세스(Node_Proc)는 가입자가 요구한 소스노드 s와, 목적노드그룹 {M}과, 서비스 유형 및 경로 할당 제한 사항들을 입력 받아 유효성을 검사하는(206) 제6단계와, 검사 후 상기 노드의 경로 처리 프로세서(Node_Proc)(302)는 경로 할당 요구를 망관리 프로세스(Multi_Router_Proc)(303)를 거쳐 경로 할당 프로세스(Multi_Router_Proc)(305)로 보내는 제7단계와, 상기 경로 할당 프로세스(305)는 멀티캐스트 가상망(Tbl-VM-Net)과 소스노드 s와, 목적노드 그룹 {M} 등의 정보를 이용하여 가상목적노드 그룹{VD}를 구성하는(207) 제8단계와, 상기 가상목적노드 그룹이 구해지면 각 가상목적노드에 대해 경로중첩 효율을 계산하는(208) 제9단계와, 망을 단순화하기 위해 필요한 상기 소스노드 s와, 목적노드 그룹{M}과, 가상목적노드 그룹 {VD}가 구해졌으므로 이들을 연결하는 완전 연결 망을 구성(209) 제10단계와, 상기 s와, {M}과, {VD}간이 완전히 연결된 망 모델 테이블(Tbl_Clos_Net)이 구성되면 다시 각 노드간을 연결하는 가상경로(VP)의 비용 및 지연값을 계산하여 기록하는(210) 제11단계와, 상기s와, {M}과, {VD}가 Full-Mesh 형태로 연결된 완전 망이 구성되었으므로 이루부터 최소 비용 멀티캐스트 경로를 할당하는(211) 제12단계와, 상기 각 단계를 통해 최소 비용 멀티캐스트 연결 경로가 구해지면 그 결과를 노드들에게 통보하고(213), 결과를 멀티캐스트 가상망 모델 테이블에 반영하는(214) 제13단계를 포함하여 이루어지는 것을 특징으로 하는 ATM 통신망에서의 멀티캐스트 경로 할당방법.