KR100757893B1 - 광 전송망에서의 자원 분산 공유 방법 - Google Patents

Abstract

본 발명은 광 전송망에서 단일 장애 보호 패스 설정을 위하여 자원을 분산 공유하는 방법에 관한 것이다.

본 발명에 따른 광 전송망에서 자원을 분산 공유하는 방법은, 광 전송망에서 현재 연결 개수에 대한 정보를 유지하는 제1 단계; 현재까지 추출된 워킹 패스들의 링크 리스트를 유지하는 제2 단계; 상기 광 전송망에서 전체 망 토폴러지를 복수의 서브 도메인으로 구분하고, 백업 패스를 위한 서브 도메인을 추출하는 제3 단계; 하위 SRLG의 백업 패스 설정 알고리즘을 적용하여 백업 패스를 추출하는 제4 단계; 및 상기 적용 결과, 적용에 성공한 경우, 링크들의 타당성을 검증하는 제5 단계를 포함하는 것을 특징으로 한다.

광 전송망, 장애, 분산, 교환, 서브 도메인, 워킹 패스, SRLG

Description

광 전송망에서의 자원 분산 공유 방법{METHOD FOR BALANCED RESOURCE SHARE IN THE OPTICAL TRANSMISSION NETWORK}

도 1은 본 발명에 따라 서브 도메인으로 구분한 망 토폴러지를 나타내는 도면.

도 2는 본 발명의 실시 예에 따른 두 레벨로 구성된 망 토폴러지를 나타내는 도면.

도 3은 본 발명의 실시 예에 따른 링크에서의 자원 분배를 나타내는 도면.

도 4는 본 발명의 실시 예에 따라 우선적으로 처리되어야 할 절차를 나타내는 흐름도.

도 5는 본 발명의 실시 예에 따라 상위 SRLG를 적용한 백업 패스 설정 절차를 나타내는 흐름도.

도 6은 본 발명의 실시 예에 따라 하위 SRLG를 적용한 백업 패스 설정 절차를 나타내는 흐름도.

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

101 내지 108: 서브 도메인 200: 상위 SRLG

201 내지 206, 304: 워킹 패스 301, 302, 303: 백업 패스

본 발명은 광 전송망에서 자원을 분산 공유하는 시스템에 관한 것으로, 보다 상세하게는 광 전송망에서 단일 장애 보호 패스 설정을 위하여 자원을 분산 공유하는 방법에 관한 것이다.

광 전송 망에서 파이버(fiber)의 장애는 상기 파이버를 경유하는 모든 광 연결(lightpaths)의 장애를 의미하며, 상기 각각의 광 연결은 10Gbps에 해당된다. 한편, 광 통신 망에서 각각의 연결은 기존 패킷 망(예컨대, MPLS(Multi Protocol Label Switching))에서보다 그 전송 단위(granularity)가 훨씬 높으므로(coarser), 상기 장애에 의한 자원 손실은 보다 더 크게 된다. 따라서, 전송 망 내에서 연결 자원의 유용성(utilization)은 기존의 망에서보다　더욱 중요하다고 볼 수 있다.

한편, 광 교환 장치(OXC; Optical Cross Connector)로 구성된 광 전송 망은 50ms정도의 빠른 복구 시간을 갖는 SONET/SDH(Synchronous Optical NETwork/Synchronous Digital Hierarchy)망보다 느리므로, 그로 인한 트래픽 손실은 매우 크다. 따라서, 결과적으로 광 전송 망의 생존성을 위한 메커니즘이 요구되며, 이러한 메커니즘은 망의 자원을 효율적으로 사용하도록 해야 한다.

최근에는 WDM(Wavelength Division Multiplexing) 기술의 발달로 높은 자원을 제공하는 광 전송 망 기술이 개발되어 왔다. 이러한 광 전송 망은 상기 다수의 OXC(Optical Cross Connector)들로 구성되며, 전송 단위는 기존 망에서보다 훨씬 크므로 상술한 바와 같이 한 개의 파이버(fiber) 장애는 장애가 된 파이버를 지나는 모든 광 연결(lightpaths)의 장애를 의미하며 1.6Tb/s에 해당되는 자원의 손실을 가져온다. 이러한 장애는 실제 망에서 빈번히 발생할 수 있으며 이로 인해 광 전송 망에서 연결 자원의 생존성(Survivability)은 중요한 요소로 대두 된다.

한편, 상기 생존성을 보장하기 위해서는 보호와 복구 메커니즘이 있는데 서로 상반된 장단점을 가진다. 상기 보호, 복구 메커니즘은 대부분 링크나 노드와 같은 하나의 요소를 고려한 단일 장애(Single Failure)를 위한 메커니즘이며, 이는 생존성을 제공하기 위한 전형적인 방법으로 사용되고 있다. 그러나 이를 위한 많은 연구에도 불구하고, 아직까지 자원을 효율적으로 사용하기 위한 메커니즘이 절실히 요구되고 있는 실정이다.

또한, 상기 종래의 단일 장애를 위한 보호 메커니즘은 빠른 복구를 수행할 수 있는 반면에 미리 설정된 백업 패스로 인하여 자원의 낭비가 초래된다. 이러한 종래의 보호 메커니즘들은 워킹 패스(working path)의 SRLG(Shared Risk Link Group)만으로 다른 백업 패스를 선택함으로써 장애에 대한 신속한 복구를 수행한다. 그러나 이러한 메커니즘들은 백업 패스들 간의 자원 공유 방법 미흡으로 자원을 효율적으로 사용하지 못한다는 문제가 있다.

이러한 점을 보완하기 위해 S. Kini et al ., "Shared backup Label Switched Path Restoration,"(Internet Draft, draft-kini-restoration-shared-backup-00.txt, November 2000) 및 S. Datta et al ., "Efficient Channel Reservation for Backup Paths in Optical Mesh Networks,"(in Proc . GLOBCOM'01) 등에서 상기 백업 패스들(Backup Paths) 간의 자원 공유에 대한 메커니즘을 제안했다.

그러나 비록 상기 메커니즘들이 자원 사용의 효율성을 개선할지라도 백업 패스들 간의 불균형한(unbalanced) 자원 공유를 고려하지는 못했다. 즉, 상기 백업 패스들이란 어느 한 곳에 집중될 수 있고 그 결과, 유휴한(idle) 자원을 사용하지 못하게 되는 결과를 초래할 수 있다.　따라서, 결과적으로 이러한 유휴한 자원을 효율적으로 사용하지 못함으로써 전체 자원의 효율성을 감소시키게 된다.

이하, 한 순간에 하나의 장애를 가정한 종래의 보호 복구 메커니즘들의 문제점들을 상세히 설명한다.

먼저, 지역 복구(local restoration) 방법은 백업 패스가 지역적으로 설정되고 장애 정보는 소스에 전달되지 않으며 이로 인해 장애 처리 시간을 감소시킬 수 있다. 상기 지역 복구 메커니즘의 대표적인 예로서 빠른 재전송(fast re-route)이 있다. 상기 빠른 재전송은 장애 시점에서 어떠한 시그널을 수행하지 않고서도 장애가 난 지점에서 MPLS 데이터가 우회(detour) 패스를 이용하여 우회할 수 있도록 하는 메커니즘이다. 그러나 상기 지역 복구 메커니즘은 복구 시간을 단축시키는 장점이 있는 반면, 각 노드의 장애를 고려한 우회 패스를 설정해야 하므로 자원 효용성이 매우 낮다는 단점이 있다.

다음으로, "Somdip"에 의한 방법은 기존의 워킹 패스별로 백업 패스에 대한 자원을 예약하는 방법들에서 자원의 낭비가 심한 것을 보완하기 위하여, 백업 패스들끼리도 자원을 공유하기 위한 풀 예약(pool-reserved) 백업 패스 자원 공유 방법을 제안하였다. 그러나 상기 "Somdip"에 의한 방법은 기존의 "SRLG-diversity"의 제한 조건에서 탈피하여 장애가 발생했을 때 백업 패스 선정 시 우선적으로 풀(pool) 내에서 가용한 자원을 찾고 복구를 위하여 그들을 사용하게 된다. 그러나 이러한 방법은 연결 제어에 대한 방법이 서술되지 않았으며, 백업 패스들이 편중된 경우 자원 공유가 어렵다는 문제점이 있다.

또한, "Xu's"의 메커니즘은 효율적인 SRLG 보호를 위해 다중 세그먼트(segments)를 이용한 보호 메커니즘이다. 상기 메커니즘은 소스에서 목적지까지 "SRLG-disjoint"한 쌍을 찾지 못하는 경우 전체 패스를 엑티브(active) 세그먼트와 백업(backup) 세그먼트로 분류하여 세그먼트 단위로 패스를 설정하도록 한다. 한편, 상기 메커니즘은 이러한 세그먼트들로 인하여 많은 자원을 낭비하게 된다.

상기와 같은 문제점을 해소하기 위한 본 발명의 목적은 편중된(unbalanced) 백업 패스 요구 자원을 분산 시켜 자원 사용의 효율을 높이는 광 전송망에서 자원을 분산 공유하는 방법을 제공함에 있다.

또한, 본 발명의 다른 목적은, 공유된 백업 패스의 수가 최대가 되도록 하며, 두 레벨의 SRLG를 통해 백업 패스 공유를 분산시킴으로써 유휴한 자원을 효율 적으로 사용할 수 있도록 하는 광 전송망에서 자원을 분산 공유하는 방법을 제공함에 있다.

상기 목적을 달성하기 위한 본 발명에 따른 광 전송망에서 자원을 분산 공유하는 방법은, 광 전송망에서 현재 연결 개수에 대한 정보를 유지하는 제1 단계; 현재까지 추출된 워킹 패스들의 링크 리스트를 유지하는 제2 단계; 상기 광 전송망에서 전체 망 토폴러지를 복수의 서브 도메인으로 구분하고, 백업 패스를 위한 서브 도메인을 추출하는 제3 단계; 하위 SRLG의 백업 패스 설정 알고리즘을 적용하여 백업 패스를 추출하는 제4 단계; 및 상기 적용 결과, 적용에 성공한 경우, 링크들의 타당성을 검증하는 제5 단계를 포함하는 것을 특징으로 한다.

본 발명에서는 불균형한(unbalanced) 자원 공유의 문제를 해결함으로써 자원 공유의 효율성을 증가시키기 위한 방법을 제안한다. 보다 구체적으로 설명하면, 제안된 메커니즘은 공유된 백업 패스의 수가 최대가 되도록 하며, 두 레벨(two-level)의 SRLG를 통해 백업 패스 공유를 분산시킴으로써 유휴한 자원을 효율적으로 사용할 수 있도록 한다. 또한, 제안된 메커니즘은 SRLG를 상위 SRLG 및 하위 SRLG의 두 레벨로 구성한다. 이때, 상기 두 레벨 중 하위 SRLG는 백업 패스를 워킹 패스와 다른(disjoint) 길의 패스를 추출하기 위한 것이고, 상위 SRLG는 워킹 패스의 서브 도메인(sub-domain) 정보를 이용하여 분산된 백업 패스 설정의 효과를 갖기 위한 것이다. 이에 따라, 본 발명은 자원 공유의 효율성을 증가시키며, 최대 링크 부하를 분산 시킴으로써 링크의 효율성을 개선 시키도록 하는 효과를 얻을 수가 있게 된다.

즉, 백업 패스 설정 시 그에 대응되는 워킹 패스와는 서로 SRLG가 다른 패스를 선택하도록 하며, 그 중에서도 워킹 패스의 서브 도메인 내에 있는 패스를 최종 백업 패스로 선택하게 한다. 따라서, 백업 패스 설정시에는 워킹 패스의 SRLG들 및 서브 도메인들을 파악하는 것이 바람직하다. 이렇게 함으로써, 각 백업 패스는 각 워킹 패스의 서브 도메인 내에 존재하므로 편중된 공유 백업 패스들을 분산시키는 효과를 가질 수가 있게 된다.

한편, 본 발명에서는 제안된 메커니즘을 위하여 다음과 같은 사항을 가정한다. 먼저, 광 전송 망에서의 자원인 파장(wavelength)은 광 패스를 따라 각 노드에서 변환되며 각 링크는 고정된 수의 파장을 갖는다. 또한, 제안된 메커니즘은 패스 기반(path-based) 보호를 수용하며, 두 레벨의 SRLG를 포함하는 라우팅 정보는 망 내에 플러딩(flooding) 된다. 아울러, 워킹 패스는 최적의 알고리즘에 의해 이미 설정되어 있다고 가정하며, 한 순간에 하나의 장애를 가정하여 백업 패스 설정 알고리즘을 정한다.

이하 본 발명의 바람직한 실시 예의 상세한 설명이 첨부된 도면들을 참조하여 설명될 것이다. 도면들 중 참조번호 및 동일한 구성요소들에 대해서는 비록 다른 도면상에 표시되더라도 가능한 한 동일한 참조번호들 및 부호들로 나타내고 있 음에 유의해야 한다. 하기에서 본 발명을 설명함에 있어, 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다.

도 1은 본 발명에 따라 서브 도메인으로 구분한 망 토폴러지를 나타내는 도면이다.

도 1을 참조하면, 본 발명에 따라 전체 망 토폴러지(topology)를 복수의 서브 도메인들(101 내지 108)로 구분하게 된다. 상기 구분된 복수의 서브 도메인들(101 내지 108)은 상술한 상위 SRLG에 따른 백업 패스 설정 방법을 수행하기 위해 사용된다. 즉, 본 발명에서는 각 워킹 패스에 대해 설정되는 백업 패스가 상기 각 워킹 패스의 해당 서브 도메인 내에 존재하도록 설정함으로써 공유 백업 패스들을 분산시키는 효과를 가져오게 된다.

한편, 본 발명의 실시 예에 따라 분산된 백업 패스 선택을 위해 하위 SRLG는 백업 패스를 워킹 패스와 다른(disjoint) 길의 패스를 추출하고, 상위 SRLG는 워킹 패스의 서브 도메인(sub-domain) 정보를 이용하여 백업 패스 설정을 하게 된다. 상기 도 1에서는 상기와 같은 백업 패스 설정을 위하여 두 레벨 SRLG로 구성된 망 토폴러지를 나타내고 있다.

즉, 상기 도 1에 도시된 망 토폴러지는 39개의 노드로 구성이 되어 있고, 8개의 서브 도메인과 69개의 링크로 구성이 되어 있다. 예컨대, 전체 망 토폴러지는 A 내지 H의 8개의 서브 도메인들(101 내지 108)로 구분되며, 각 서브 도메인들(101 내지 108)은 복수의 노드들 및 링크들로 구성된다. 이때, 상기 A 서브 도메인(101)은 1, 2, 3, 5 및 6의 5개의 노드들과 a1 내지 a7의 7개의 링크들로 구성된다.

도 2는 본 발명의 실시 예에 따른 두 레벨로 구성된 망 토폴러지를 나타내는 도면이다.

도 2를 참조하면, 본 발명의 실시 예에 따른 망 토폴러지는 상위 SRLG(200) 및 하위 SRLG로 구성될 수 있다. 따라서, 각 링크의 SRLG는 a 내지 q의 하위 SRLG 및 s의 상위 SRLG로 나타낼 수 있다. 이때, 워킹 패스(working path)는 W1 내지 W6(201 내지 206)으로서 트래픽 요구에 따라 최단 경로의 패스를 할당하게 된다. 여기서, 상기 최단 경로로 할당하는 것이 그렇지 않은 경우보다 자원의 효율성이 더 좋다는 것이 실험 결과로 밝혀졌다.

한편, 본 발명의 실시 예에 따라 백업 패스(backup path)는 해당 워킹 패스와 다른(SRLG-disjoint) 한 패스를 추출하며, 특정 링크에 편중된 백업 패스가 되지 않고 분산 설정되도록 상기 해당 워킹 패스가 속한 서브 도메인 내에 존재하는 것을 두 번째 제한 조건으로 한다.

도 3은 본 발명의 실시 예에 따른 링크에서의 자원 분배를 나타내는 도면이다.

도 3을 참조하면, 본 발명의 실시 예에 따라 링크 ij 에는 λ₁ 내지 λ₃의 세 개의 λ가 있다. 상기　λ₁ 에는 상기 도 3의 3개의 워킹 패스(즉, W1(201), W3(203), W6(206))에 대응되는 세 개의 백업 패스(즉, B1(301), B3(302), B6(303))가 공유되도록 설정될 수 있다.

또한, 상기 λ₂ 는 또 다른 워킹 패스 P4(304)를 설정하고, 나머지 λ₃은 유휴한 자원으로 남게 된다. 이때, 물론 B1(301), B3(302), B6(303)는 본 발명의 실시 예에 따라 각각의 워킹 패스와 다른(disjoint) 패스를 선택하며, 상기 각 워킹 패스와 동일한 서브 도메인 내에서 백업 패스를 설정하게 된다.

이하, 상기 본 발명의 실시 예에 따라 사용되는 자원을 최소화하기 위해 선택되는 패스에 대한 최적의 해를 산출하는 방법을 설명하기로 한다.

하기 <수학식 1>은 사용되는 자원을 최소화하기 위하여 최적의 해를 수식화한 목적 함수(Object Function)로서, 상기 목적 함수는 전체 파장의 수를 최소화하기 위한 식으로 나타낼 수 있다.

한편, 상기 <수학식 1>에 사용된 상수 및 변수들은 다음과 같이 정의된다.

<상 수>

w : 각 링크(link) 상의 파장(wavelength) 수, 1≤w≤W.

C_ij : 링크 (i, j)에서 총 용량(capacity, total wavelengths).

: 링크 (u, v) 상에 파장(wavelength) w를 갖는 워킹 패스.

s_p, t_p : 워킹 패스 p의 시작 s, 끝 t 노드.

<변 수>

: 만약 워킹 패스 (s, d)의 백업 패스가 링크 (i, j)에서 파장(wavelength) w를 사용한다면 1, 그 외에는 0.

β^w : 파장(wavelength) w, (1≤w≤W)를 공유하는 백업 패스 수의 역수.

(만약, 3 개의 백업 패스가 파장(wavelength) λ¹을 공유한다면, β^w 는 1/3)

S_ij : 링크 (i, j)에서 여유 용량.

s_b, t_b : 백업 패스 b의 시작, 끝 노드.

또한, 상기 <수학식 1>의 목적 함수를 만족하기 위한 조건들은 하기 <수학식 2> 내지 <수학식 7>과 같다.

상기 <수학식 2>는 목적 함수를 위한 제한 조건으로서, 워킹 패스의 수와 백업 패스의 수가 동일하다는 것을 의미한다. 즉, 패스의 길이에 관계없이 해당 망 내에서 상기 해당 패스에 대한 시작과 끝이 존재한다는 것을 의미한다.

상기 <수학식 3>은 링크 ij에서의 총 파장 수는 링크 ij에서 백업 패스로 사용된 파장의 총 수보다 많다는 것을 의미한다.

상기 <수학식 4> 내지 <수학식 6>은 백업 패스가 해당 패스를 따라 각 링크에 보존(conserve)되어 있는 것을 의미한다.

상기 <수학식 7>은 링크 ij에서 유휴 자원은 링크 ij의 총 자원에서 현재 워킹 패스로 사용중인 자원을 제외한 자원보다 적음을 의미한다.

이하, 도 4 내지 도 6을 참조하여 본 발명의 실시 예에 따라 백업 패스를 설정하는 절차를 상세히 설명한다. 먼저, 도 4를 참조하여 우선적으로 처리되어야 할 절차를 설명하며, 다음으로 도 5 및 도 6을 참조하여 본 발명의 실시 예에 따라 상위 SRLG에 따른 설정 절차 및 하위 SRLG에 따른 설정 절차를 차례로 설명한다.

도 4는 본 발명의 실시 예에 따라 우선적으로 처리되어야 할 절차를 나타내는 흐름도이다.

도 4를 참조하면, 본 발명의 실시 예에 따른 백업 설정 절차를 수행하기 위하여 다음과 같은 우선 처리 절차를 수행하게 된다. 즉, 상기 도 4는 본 발명의 실시 예에 따라 광 전송 망에서 단일 장애(single failure) 보호 패스(Backup Path) 설정을 위한 분산 자원 공유(Balanced Resource Share) 메커니즘을 적용하기 위하여 우선적으로 가정되어야 할 워킹 패스의 추출과 두 레벨의 SRLG 할당에 관한 도면이다.

먼저, 본 발명의 실시 예에 따라 두 레벨의 SRLG(즉, 상위 SRLG 및 하위 SRLG)를 이용한 백업 패스 추출을 위하여 운용자 망 정책에 따라 서브 도메인을 나타내는 상위 SRLG를 할당(단계 401)하고 입력한다. 또한, 실제 물리 링크의 배선 상황에 따른 하위 SRLG의 번호를 할당(단계 402)한다.

한편, 본 발명에서 제안된 알고리즘을 통하여 획득한 정보는 GMPLS(Generalized MPLS) 라우팅에 의하여 자원 및 루트 정보가 제공되고 상기 GMPLS 시그널링에 의해서 연결이 설정된다. 이와 같이, 할당된 각각의 정보는 라우팅 프로토콜의 주기적인 정보 플러딩(flooding) 시 링크 정보에 이러한 정보를 추가(단계 403)하게 된다. 그런 다음, 상기 라우팅 정보의 플러딩을 위하여 상기 해당 링크 정보들은 인코딩(encoding)(단계 404)되고, 상기 인코딩된 정보는 망 내의 각 노드들에게 전달(단계 405)된다. 마지막으로, 워킹 패스들이 후술할 백업 패스 설정 전에 모두 할당(단계 406)된다.

이하, 도 5를 참조하여 상위 SRLG를 적용한 백업 패스 설정 절차를 설명하고, 도 6을 참조하여 하위 SRLG를 적용한 백업 패스 설정 절차를 설명한다.

도 5는 본 발명의 실시 예에 따라 상위 SRLG를 적용한 백업 패스 설정 절차를 나타내는 흐름도이다.

도 5를 참조하면, 먼저, 현재 연결 개수에 대한 정보를 유지(단계 501)하게 되며, 이는 차후 연결들을 설정하기 위한 참조 자료로 쓰이게 된다. 또한, 현재까지 추출된 워킹 패스들의 링크 리스트를 유지(단계 502)한다.

그런 다음, 상기 상위 SRLG에서는 하위 SRLG와는 달리 백업 패스를 위한 서브 도메인을 추출(단계 503)하게 되며, 나머지 링크들은 블록 시킨다. 이때, 추출된 상기 서브 도메인에 백업 패스가 없을 경우를 대비하여 나머지 서브 도메인들을 추출하여 저장(단계 504)한다. 그런 다음, 상위 SRLG의 백업 패스를 추출하기 위하여 우선 하위 SRLG의 백업 패스 설정 알고리즘을 적용(단계 505)하게 된다. 상기 하위 SRLG의 백업 패스 설정 알고리즘은 도 6의 설명에서 후술하기로 한다.

상기 적용 결과, 적용 실패한 경우(단계 506)에는 계속적으로 적용 시도를 하게 되며, 적용에 성공한 경우에는 링크들의 타당성을 검증(단계 507)한다. 그런 다음, 방금 추출된 백업 패스가 해당 링크에서 다른 백업 패스와 자원을 공유하는 지를 검색(단계 508)하게 된다. 상기 검색 결과, 자원을 공유하는 경우에는 사용 자원 값을 증가시키지 않고, 공유하지 않은 경우에는 자원을 증가(단계 509)시키게 된다.

한편, 상술한 상위 SRLG를 기반으로 한 백업 패스 설정 알고리즘은 다음과 같은 프로그램 언어로 구현할 수가 있다.

______________________________________________

cur_connection : current connections

WP_list : the link list of the selected working paths

accept_region = find_region()

//find the whole sub-domains on the working path

//find the rest sub-domains

not_accept_link_list = find_not_accept_region

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 (accept_region)

// disable the links on the rest of the working paths

set_link_disable(not_accept_link_list)

result = find_Low_backup()

//applies the Low-SRLG algorithm

if result == fail

　　 then set_link_enable(not_accept_link_list)

　　 //discharges the sub-domains

　　　　　　　　 find_Low_backup()

end if

set_link_enable(){

for bk_link // for all backup links

　　 if　 (backup Path == share)

　　 // check the backup path with the others

　　　　　 then increase band-width of backup links

　　 else not increase band-width of backup links

end for }

____________________________________________

도 6은 본 발명의 실시 예에 따라 하위 SRLG를 적용한 백업 패스 설정 절차를 나타내는 흐름도이다.

도 6을 참조하면, 상기 도 5에 따라 상위 SRLG를 적용하여 백업 패스 설정을 수행하는 과정에서 후술하는 하위 SRLG를 적용한 백업 패스 설정 절차를 수행하게 된다. 즉, 상기 도 6은 백업 패스를 추출하기 위한 휴리스틱(Heuristic) 알고리즘으로서 하위 SRLG를 적용한 백업 패스 설정 알고리즘이다. 상기 수학식들에서 언급한 ILP(Integer Linear Programming) 해를 얻기 위해서는 많은 시간이 소요되며, 정수 해를 요한다. 또한, 문제의 크기가 증가함에 따라 문제의 해를 얻는 데에는 어려움이 있다. 따라서, 본 발명에서는 제안된 자원 공유 메커니즘을 풀기 위하여 상기 휴리스틱 알고리즘을 적용하여 정의하게 된다.

먼저, 상기 상위 SRLG에서와 같이 현재 연결 개수에 대한 정보를 유지(단계 601) 하게 되며, 이는 차후 연결들을 설정하기 위한 참조 자료로 쓰이게 된다. 또한, 현재까지 추출된 워킹 패스들의 링크 리스트를 유지(단계 602)한다.

한편, 상기 하위 SRLG에서는 상위 SRLG와는 달리 백업 패스를 추출하기 위해 가용한 링크로 설정해야 하므로, 현재까지 설정된 워킹 패스들의 링크들을 차단(disable)(단계 603) 시키게 된다. 이때, 요구된 백업 패스를 위해 최단 거리 백업 패스를 추출(단계 604)한다.

그런 다음, 상기 추출된 백업 패스에 걸쳐 있는 링크들의 유효성을 검증(단계 605) 한 후, 실제 유휴한 자원이 있는지를 검색(단계 606)하게 된다. 상기 검색 결과, 만약 유휴한 자원이 없는 경우(단계 607)에는 지속적으로 검색을 시도하며, 유휴한 자원이 있는 경우에는 링크들의 타당성을 검증(단계 608)하게 된다.

마지막으로, 방금 추출된 백업 패스가 해당 링크에서 다른 백업 패스와 자원을 공유하는지를 검색(단계 609)하고, 상기 검색 결과 자원을 공유하는 경우에는 사용 자원 값을 증가시키지 않게 되며, 반면 자원을 공유하지 않는 경우에는 자원을 증가(단계 610)시키게 된다.

한편, 상술한 하위 SRLG를 기반으로 한 백업 패스 설정 알고리즘은 다음과 같은 프로그램 언어로 구현할 수가 있다.

__________________________________________

cur_connection : current connections

WP_list : the link list of the selected working paths

while

　　 set_link_disable(WP_list)

　　 //disable the links on the working paths

　　 bk_link = find_shortest_path()

　　 // find the shortest path based on hops

　　 no_resource_link = validate_link(bk_link)

　　 // checks usable resource

　　　　　　　 if no_resource_link == NULL

　　　　　　　　then break　　　　　　　　　//path selected

　　　　　　　 else set_link_disable(no_resource_link)

　　　　　　　　continue;

end while

validate_link (){

for bk_link // for all backup links

　　　 if　 (backup Path == share)

　　　 // check the backup path with the others

　　　　　　　　then increase band-width of backup links

　　　 else not increase band-width of backup links

end for }

__________________________________________

상술한 본 발명에 따른 광 전송망에서 자원을 분산 공유하는 방법은 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현할 수 있다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피 디스크, 광데이터 저장장치 등이 있으며, 또한 인터넷을 통한 전송과 같이 커리어 웨이브의 형태로 구현되는 것도 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수도 있다.

한편, 본 발명의 상세한 설명에서는 구체적인 실시 예에 관해 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한도 내에서 여러 가지로 변형할 수 있음은 물론이다. 그러므로 본 발명의 범위는 설명된 실시 예에 국한되어 정해져서는 안되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.

상술한 바와 같이 본 발명에 따르면 종래의 자원 공유 메커니즘들의 단점인 편중된 자원 공유를 분산 시킴으로써, 자원 공유의 효율성을 증가시키며, 최대 링크 부하를 분산시킴으로써 링크의 효율성을 개선하는 이점이 있다.

Claims (6)

1. 광 전송망에서 현재 연결 개수에 대한 정보를 유지하는 제1 단계;

   현재까지 추출된 워킹 패스들의 링크 리스트를 유지하는 제2 단계;

   상기 광 전송망에서 전체 망 토폴러지를 복수의 서브 도메인으로 구분하고, 백업 패스를 위한 서브 도메인을 추출하는 제3 단계;

   하위 SRLG의 백업 패스 설정 알고리즘을 적용하여 백업 패스를 추출하는 제4 단계; 및

   상기 적용 결과, 적용에 성공한 경우, 링크들의 타당성을 검증하는 제5 단계를 포함하는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.
2. 제1항에 있어서, 상기 제5 단계 이후에,

   상기 추출된 백업 패스가 해당 링크에서 다른 백업 패스와 자원을 공유하는 지를 검색하는 단계; 및

   상기 검색 결과, 자원을 공유하지 않은 경우, 자원을 증가시키는 단계;를 더 포함하는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.
3. 제1항에 있어서, 상기 제4 단계는,

   현재까지 설정된 워킹 패스들의 링크들을 차단시키는 단계;

   요구된 백업 패스를 위해 최단 거리 백업 패스를 추출하는 단계;

   상기 추출된 백업 패스에 걸쳐 있는 링크들의 유효성을 검증하는 단계;

   상기 추출된 백업 패스에 실제 유휴한 자원이 있는지를 검색하는 단계; 및

   상기 검색 결과, 유휴한 자원이 있는 경우에는 링크들의 타당성을 검증하는 단계를 더 포함하는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.
4. 제1항에 있어서, 상기 제1 단계 수행 이전에,

   상기 서브 도메인을 나타내는 상위 SRLG를 할당하고 입력하는 단계;

   실제 물리 링크의 배선 상황에 따른 하위 SRLG의 번호를 할당하는 단계;

   라우팅 프로토콜의 링크 정보에 상기 SRLG의 정보를 추가하는 단계;

   링크 정보를 인코딩하여 망 내 각 노드들에게 전달하는 단계; 및

   워킹 패스들을 할당하는 단계를 더 포함하는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.
5. 제1항에 있어서, 상기 제4 단계의 상기 백업 패스 추출은 자원의 사용을 최소화하기 위하여 하기 수학식에 의해 산출되는 목적 함수에 의해 선택하는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.

   

   이때, 상기 수학식에 사용된 상수 및 변수들은 다음과 같다.

   <상 수>

   w : 각 링크(link) 상의 파장(wavelength) 수, 1≤w≤W.

   C_ij : 링크 (i, j)에서 총 용량(capacity, total wavelengths).

   

   : 링크 (u, v) 상에 파장(wavelength) w를 갖는 워킹 패스.

   s_p, t_p : 워킹 패스 p의 시작 s, 끝 t 노드.

   <변 수>

   

   : 만약 워킹 패스 (s, d)의 백업 패스가 링크 (i, j)에서 파장(wavelength) w를 사용한다면 1, 그 외에는 0.

   β^w : 파장(wavelength) w, (1≤w≤W)를 공유하는 백업 패스 수의 역수.

   (만약, 3 개의 백업 패스가 파장(wavelength) λ¹을 공유한다면, β^w 는 1/3)

   S_ij : 링크 (i, j)에서 여유 용량.

   s_b, t_b : 백업 패스 b의 시작, 끝 노드.
6. 제5항에 있어서, 상기 목적 함수를 만족하기 위한 제한 조건은 하기 수학식과 같이 산출되는 것을 특징으로 하는 광 전송망에서 자원을 분산 공유하는 방법.

   

Images