KR20060015051A - 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형라우팅 경로 설정 방법 - Google Patents

Abstract

본 발명은 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로를 설정하는 방법을 개시한다.

본 발명의 라우팅 경로 설정 방법은 임의의 송신 레이블 에지 라우터(LER)에 유입될 미래 트래픽 유입량을 산출하는 제 1 단계; 망 형상과 상기 미래 트래픽 유입량을 기준으로 상기 임의의 송신 레이블 에지 라우터와 수신 레이블 에지 라우터 간에 가능한 모든 라우팅 경로를 산출하고, 산출된 라우팅 경로에서 각 링크의 가중치를 계산하는 제 2 단계; 상기 계산된 링크의 가중치를 기반으로 홉 카운트 및 단대단 지연을 고려하여 상기 라우팅 경로 내 라우터와 링크의 오더 값을 계산하는 제 3 단계; 및 상기 오더 값을 기반으로 이용자가 요청한 대역폭 및 단대단 지연을 만족하는 라우팅 경로를 산출하는 제 4 단계를 포함하여, 현재의 망 형상에서 미래의 트래픽 수요 예측 결과와 트래픽 량을 기반으로 하여 경로를 설정함으로써 동일한 망 자원을 가지고 최대의 경로를 제공함으로써 망자원의 활용도를 극대화하고 이에 따라 동일한 망자원으로 최대의 수익을 창출할 수 있도록 해준다.

Description

멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법{Method for setting of routing path in multi protocol label switch network}

도 1은 일반적인 MPLS 망에서의 라우팅 경로 산출의 문제점을 설명하기 위한 구성도.

도 2는 본 발명에 따른 라우팅 경로 설정 방법을 설명하기 위한 순서도.

도 3은 본 발명의 실시예에 따른 멀티프로토콜 레이블 스위칭 망에서의 망 구성도.

도 4는 도 3의 망 형상에서 3개의 송신점(a, e, g)에서 서로 다른 트래픽이 유입된다는 가정하에 송/수신점 간에 가능한 모든 라우팅 경로와 이를 기반으로 계산된 각 링크 비용을 표로 나타낸 도면.

도 5는 도 4에서 유입 트랙픽 량을 고려하여 계산한 각 링크 E_ij의 가중치 w를 E_ij(w) 형태로 도식화 한 도면.

도 6은 본 발명에 따른 홉 카운트 및 단대단 지연을 고려하여 계산된 라우터 및 링크에 대한 오더 값을 표시한 도면.

도 7은 이용자의 요구사항을 만족시키는 최적의 라우팅 경로를 산출하는 과 정을 설명하기 위한 도면.

본 발명은 멀티프로토콜 레이블 스위칭(이하, MPLS:Multi Protocol Label Switching) 망에서 서비스 품질을 만족시킬 수 있는 최적의 라우팅 경로를 산출하기 위한 방법에 관한 것으로, 보다 상세하게는 임의의 송/수신점 간에 레이블 스위칭 경로를 설정시 현재의 망 형상에서 미래의 트래픽 수요 예측 결과와 트래픽 량을 기반으로 하여 경로를 설정함으로써 동일한 망자원을 가지고 최대의 LSP를 제공하여 망자원의 활용도를 극대화하고 이에 따라 동일한 망자원으로 최대의 수익을 창출할 수 있는 있도록 하는 라우팅 경로를 설정하는 방법에 관한 것이다.

MPLS는 네트워크 트래픽의 흐름 속도를 높이고 관리를 보다 쉽게 할 수 있도록 개발된 표준 기술로서, 주어진 패킷 열에 대하여 특정 경로를 설정한다. 각 패킷에는 레이블이 첨부되고, 레이블 스위치 라우터(LSR: Label Switched Router)에는 레이블에 따라 라우팅 경로를 설정할 수 있는 라우팅 정보가 저장된 FIB(Fowarded Information Base)가 구비되어, 해당 패킷에 대한 라우팅이 수행된다.

각 홉(HOP)에 해당하는 LSR은 해당 패킷에 대한 라우팅을 행할 때, 패킷의 레이블을 변경시켜 전송하므로써 해다 패킷이 수신측으로 전송될 수 있도록 한다.

한편, 복수의 LSR들을 경유하여 형성되는 레이블 스위치 경로(LSP: Label Switched Path)는 특정 성능 수준을 보장하며, 네트워크 병목을 피하고, 네트워크 기반의 가상 사설망을 위한 IP 터널을 생성하기 위하여 네트워크 운용자에 의해 구성되는데, 이러한 LSP는 특정한 레이어 2 기술에 의존하지 않는 경우를 제외하고는 ATM(asynchronous transfer mode)이나 프레임 릴레이 네트워크에서의 서킷 스위치 경로와 차이가 없다.

LSP는 ATM, 프레임 릴레이 또는 이더넷과 같이 다양한 레이어 2 전송에 대해 구성될 수 있기 때문에, MPLS는 네트워크 이중 설치나 레이어 2 전용 제어 메커니즘에 대한 필요성을 배제하면서 어떠한 전송 매체를 통해서도 특정 성능을 갖고 종단간(end-to-end) 서킷을 생성할 수 있다는 잇점을 가지고 있다.

이러한 MPLS 기술에 의하면, 데이터 서비스 제공에 기존의 인터넷 망에서 제공하지 못하였던 품질 보증형 인터넷 서비스를 제공할 수 있게 된다. 즉, 품질 보증형 인터넷 서비스 제공을 위한 MPLS 기술에서는 송신 레이블 에지 라우터(LER: Label Edge Router)와 수신 레이블 에지 라우터 간에 임의의 대역을 가지는 LSP를 미리 설정해 놓고 트래픽을 전송함으로써 품질 보장이 가능한 인터넷 서비스 제공이 가능해 진다.

MPLS 망에서는 망을 효율적으로 운용하고 망 이용자가 원하는 서비스 품질을 항상 만족시킬 수 있도록 하는 일련의 기술을 트래픽 엔지니어링 (TE: Traffic Engineering)이라 정의하고, 그 중에서 대표적인 트래픽 엔지니어링 기술은 기존의 인터넷 망에서 불가능하였던 제약기반 최단경로우선(이하, CSPF: Constraint-based Shortest Path First) 알고리즘을 사용하는 것이다.

기존의 인터넷 망에서는 최단경로우선 알고리즘을 사용하여 동일한 송/수신 MPLS 스위칭 노드 간에는 망의 상태와 무관하게 항상 최단 라우팅 경로만을 선택하여 항상 동일한 라우팅 경로 상으로 MPLS 트래픽을 전달함으로써 부하(Congestion)이 발생하였다. CSPF란 이러한 문제점을 해결하여 기존 인터넷 망의 최단경로우선 알고리즘에 대역폭, 단대단 지연 등과 같은 제약조건을 추가하여 라우팅 경로를 선정하도록 변경한 것으로 기존의 인터넷 망과는 다르게 최단 경로는 선정하되 상기와 같은 제약조건을 만족하는 라우팅 경로를 선정하여 망 부하 (Congestion) 발생이 일어나지 않도록 한다.

망은 트래픽의 폭주 또는 장애 발생 등으로 인해 안정된 데이터 전송 서비스를 제공할 수 없는 상황을 내재하고 있으며, 망 형상에 따라 임의의 송/수신점 간에 LSP를 설정하면 다른 다수의 송/수신점 간에 경로를 설정하지 못하는 상황이 발생할 가능성이 있다.

도 1은 일반적인 MPLS 망에서의 라우팅 경로 산출의 문제점을 설명하기 위한 구성도이다.

도 1에서, MPLS망은 LER들 (LER1 ∼ LER6)과 LSR들(LSR1 ∼ LSR3)로 구성되며 LER 및 LSR들이 링크로 연결되어 LSP(LSP-1 ∼ LSP-3)를 형성한다. 이때, LER은 송/수신점이 되는 라우터이며, LSR은 송수신점 라우터인 LER들 사이에서 MPLS 패킷을 전달하는 역할을 수행한다.

도 1에서 만일 모든 링크의 대역폭이 10Mbps라고 가정할 때, LER1과 LER2 사이에 대역폭 10Mbps인 LSP를 설정하려고 할 경우, 해당 LSP는 <LER1-LSR1-LSR2- LSR3-LER2> 라우터를 경유하는 LSP-1이 설정되고 이들 라우터 간의 링크 대역폭을 사용한다. 이때, LER1과 LSR1 간의 링크, LSR1과 LSR2 간의 링크, LSR2와 LSR3 간의 링크 및 LSR3와 LER2 간의 링크 대역폭 10Mbps를 LSP1을 설정하기 위해 모두 사용하게 된다.

이러한 상황하에서, LER3와 LER5 사이에 10Mbps의 대역폭을 가지는 LSP-2를 설정하려고 할 경우, 가능한 라우팅 경로는 <LER3-LSR1-LSR2-LER5>가 될 수 있으나 이미 LSR1과 LSR2 간의 링크 대역폭을 LSP-1을 설정하기 위해 사용하였기 때문에 LER3와 LER5 간에 LSP-2를 설정할 수 없게 된다. 또한, LER4와 LER6 사이에 10Mbps의 대역폭을 가지는 LSP-3를 설정하려고 하는 경우에도, 가능한 라우팅 경로는 <LER4-LSR2-LSR3-LER6>가 될 수 있으나 이미 LSR2과 LSR3 간의 링크 대역폭을 LSP-1을 설정하기 위해 사용하였기 때문에 LER4와 LER6 간에 LSP-3를 설정할 수 없게 된다.

본 발명은 이러한 문제점을 해결하기 위해 임의의 송/수신점 간에 LSP를 설정하는 경우, 망 형상을 기반으로 가능한 모든 송/수신점 간의 수요예측 데이터를 기반으로 최대의 LSP를 수용할 수 있는 라우팅 방법에 관한 것이다.

따라서, 상술된 문제를 해결하기 위한 본 발명의 목적은 MPLS 망에서 임의의 송/수신점 간에 레이블 스위칭 경로를 설정시 현재의 망 형상에서 미래의 트래픽 수요 예측 결과와 트래픽 량을 기반으로 하여 경로를 설정함으로써 동일한 망자원을 가지고 최대의 LSP를 제공하여 망자원의 활용도를 극대화하고 이에 따라 동일한 망자원으로 최대의 수익을 창출할 수 있는 있도록 하는데 있다.

위와 같은 목적을 달성하기 위한 본 발명의 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법은 임의의 송신 레이블 에지 라우터(LER)에 유입될 미래 트래픽 유입량을 산출하는 제 1 단계; 망 형상과 상기 미래 트래픽 유입량을 기준으로 상기 임의의 송신 레이블 에지 라우터와 수신 레이블 에지 라우터 간에 가능한 모든 라우팅 경로를 산출하고, 산출된 라우팅 경로에서 각 링크의 가중치를 계산하는 제 2 단계; 상기 계산된 링크의 가중치를 기반으로 홉 카운트 및 단대단 지연을 고려하여 상기 라우팅 경로 내 라우터와 링크의 오더 값을 계산하는 제 3 단계; 및 상기 오더 값을 기반으로 이용자가 요청한 대역폭 및 단대단 지연을 만족하는 라우팅 경로를 산출하는 제 4 단계를 포함한다.

이하, 첨부된 도면들을 참조하여 본 발명의 바람직한 실시예를 보다 상세하게 설명한다.

도 2는 본 발명에 따른 라우팅 경로 설정 방법을 설명하기 위한 순서도이다.

본 발명의 라우팅 경로 설정 방법을 우선 간략하게 설명하면 다음과 같다.

우선, 주어진 MPLS 망에서 임의의 송신점(송신 LER)에 대한 미래 트래픽 유입량을 산출한 후, 망 형상과 산출된 미리 트래픽 유입량을 기준으로 사용자가 요청한 송/수신점 간의 가능한 모든 라우팅 경로를 산출한다. 다음에, 산출된 라우팅 경로의 각 링크에 대한 가중치를 계산하고, 계산된 링크 가중치를 기반으로 경로상의 각 라우터와 링크의 오더 값을 산출한다. 그리고, 이렇게 산출된 오더 값 을 기준으로 최적의 라우팅 경로를 산출한다.

도 2에서의 각 라우팅 경로 설정 과정은 도 3 내지 도 7을 통하여 보다 상세하게 설명된다.

도 3은 본 발명의 실시예에 따른 멀티프로토콜 레이블 스위칭 망에서의 망 구성도이다.

우선, 도 3의 MPLS 망 형상에서 임의의 송신점(송신 LER)에서의 미래 트래픽 유입량을 산출한다(단계 210).

도 3에서, 각 송신 LER(a, e, g)에 유입될 미래 트래픽 량은 T_LOAD로 표시되었다.

본 실시예에서는 도 3과 같은 MPLS 망 환경하에서, 송신 LER(a)와 수신 LER(d) 사이에 100 Mbps의 MPLS 트래픽이 유입되고, 송신 LER(e)와 수신 LER(f) 사이에 5 Mbps의 MPLS 트래픽이 유입되며, 송신 LER(g)와 송신 LER(m) 사이에 5 Mbps의 MPLS 트래픽이 유입된다고 가정한다. 그리고, 도 3에서, E_i,j는 라우터 i와 라우터 j 간의 링크를 의미한다.

다음에, MPLS 망의 형상과 미래 트래픽 유입량을 기준으로 임의의 송/수신점 간에 가능한 모든 라우팅 경로를 산출한 후, 이를 기반으로 링크의 가중치를 계산한다(단계 220).

도 3과 같은 망 환경에서 3개의 송/수신점 간에 서로 다른 MPLS 트래픽이 유입될 수 있다는 가정하에, 임의의 송/수신점 간에 가능한 모든 라우팅 경로 산출 및 링크의 가중치 계산은 다음과 같은 방식으로 이루어진다.

도 4는 도 3의 망 형상에서 3개의 송신점(a, e, g)에서 서로 다른 트래픽이 유입된다는 가정하에 송/수신점 간에 가능한 모든 라우팅 경로와 이를 기반으로 계산된 각 링크 비용을 표로 나타낸 것이다.

이때, 링크의 가중치 산출은 링크 가중치 계산 알고리즘(이하, LWCA: Link Weight Computation Algorithm)을 이용하여 이루어진다.

도 4에서, E_ij(d)는 라우터 i와 라우터 j 간의 링크에 대한 지연(Delay)을 표시하는 것으로 단위는 ms 이며, 본 실시예에서 각각의 링크에 대한 지연은 도 4에서와 같이 정의하였다.

E_ij(ava)는 라우터 i와 라우터 j 간의 링크에서의 가용한 대역폭을 표시하는 것으로 단위는 Mbps이며, 본 실시예에서 모든 링크에 대한 가용 대역폭은 500Mbps로 정의하였다.

T_load(Si)(i=1,2,3)는 각각 세개의 송신 LER(a, e, g)에서 유입될 트래픽 량을 표시하는 것으로 단위는 Mbps이며, 본 실시예에서 송신점 S1에 유입될 트래픽 량은 100Mbps, 송신점 S2에 유입될 트래픽 량은 5Mbps, 그리고 송신점 S3에 유입될 트래픽 량은 5Mbps로 정의된다.

P_candiate(Si,Di)는 임의의 송신 LER Si와 수신 LER Di 사이의 가능한 모든 라우팅 경로를 표현하는 것으로, 라우팅 경로는 링크의 집합으로 표현된다. 예를 들어, 도 4에서, S1과 D1 간의 가능한 라우팅 경로는 1개가 존재하며 해당 라우팅 경 로는 링크 E_ab, E_bc 및 E_cd를 경유한다. 따라서, P_candiate(S1,D1) = {(E_ab,E_bc,E_cd)}이 된다. 반면, S2과 D2 간에는 링크 E_bc, E_eb 및 E_cf를 경유하는 경로와 링크 E_eh, E_hk 및 E_kl를 경유하는 경로가 존재하므로, P_candiate(S2,D2) = {(E_bc,E_eb ,E_cf),(E_eh,E_hk,E_kl)}이 된다. 동일한 방법으로, S3과 D3 간에는 링크 E_gh, E_hk, E_kl 및 E_lm 를 경유하는 경로가 존재하므로, P_candiate(S3,D3) = {(E_gh,E_hk,E_kl,E_lm )}이 된다.

E_ij(cc)는 라우터 i와 라우터 j 간의 링크가 임의의 송/수신점 간 라우팅 경로 산출시 라우팅 경로에 포함된 수를 표시한다. 예를 들어, 링크 E_bc는 P_candiate(S1,D1) 및 P_candidate(S2,D2)에 모두 포함되므로 E_bc(cc) = 2가 된다.

E_ij(load)는 임의의 송/수신점 간 라우팅 경로 산출시 포함된 라우터 i와 라우터 j 간의 링크가 해당 라우팅 경로를 모두 수용하기 위해 필요한 총 대역폭 합을 나타낸다. 예를 들어, 도 4에서 링크 E_hk는 S2와 D2 간의 라우팅 경로 및 S3와 D3 간의 라우팅 경로에 포함된다. 따라서, 링크 E_hk에서 필요한 대역폭의 량은 S2와 D2 간의 라우팅 경로를 위한 트래픽 량 5Mbps 와 S3와 D3 간의 라우팅 경로를 위한 트래픽 량 5Mbps 을 합산한 10Mbps가 된다.

E_ij(w)는 라우터 i와 라우터 j 간의 링크에 대해 LWCA 알고리즘에 의해 산출된 링크의 가중치를 나타낸다. E_ij(w)는 수학식 1과 같은 링크 비용 산출을 위한 공식에 의해 산출된다.

예를 들어, 도 3에서 링크 E_ab(w)가 정상이라는 가정하에, E_ab(w)=((100/1,024) x 1 + (2 x 1,000))=2000.098이 된다.

수학식 1에서 링크의 정상 및 비정상 판단은 링크에 장애가 발생하였거나 링크 지연이 심하여 정상적인 트래픽 전송이 불가능하거나 또는 잔여 대여폭이 더 이상 남아 있지 않은 경우에는 "비정상"으로 판정하고 그 이외의 경우에는 "정상"으로 판정한다.

위와 같이, 임의의 송신점에서의 트래픽 유입량에 따른 링크의 가중치 산출이 완료되면, 이를 기반으로 홉 카운트 및 단대단 지연을 고려한 링크 가중치인 오더 값을 계산한다(단계 230).

홉 카운트 및 단대단 지연을 고려한 링크 가중치를 계산하는 이유는 임의의 송/수신점 사이에 라우팅 경로 산출시 홉 카운트가 적은 라우팅 경로 일 수 록 사용하는 망 자원량이 적으므로, 가능하면 최소의 홉 카운트를 가지는 라우팅 경로를 산출하여 망 자원 활용도를 높이기 위함이다.

도 5는 도 4에서 유입 트랙픽 량을 고려하여 계산한 각 링크 E_ij의 가중치 w 를 E_ij(w) 형태로 도식화 한 것이다. 이러한 링크 가중치 w는 홉 카운트 및 단대단 지연을 고려한 오더 값 계산을 위한 입력 데이터로 사용된다.

도 5의 MPLS 망 형태에서 사용자가 요청하는 LSP 설정을 위한 요구사항은 다음과 같다고 가정한다.

LSP_request=P(S,D,b,d)=P(e,f,10Mbps,8ms)

이때, P는 LSP_request에 따라 산출될 라우팅 경로를 나타내며, S는 송신 LER, D는 수신 LER, b는 LSP 생성을 위한 요청 대역폭, 및 d는 LSP 생성시 단대단 지연을 각각 나타낸다.

즉, 본 실시예에서 이용자의 요구사항은 송신 LER(e)와 수신 LER(f) 간에 10Mbps 대역폭과 단대단 지연이 8ms이하인 라우팅 경로를 산출하는 것으로 정의한다.

도 6은 본 발명에 따른 홉 카운트 및 단대단 지연을 고려하여 계산된 라우터 및 링크에 대한 오더 값을 표시한 도면이다.

모든 라우터와 링크에는 오더 필드 E_ij[], N[]가 추가되어 홉 카운트를 고려한 링크 및 라우터의 오더 값을 저장할 수 있도록 한다. 도 6에서, 라우터 i와 라우터 j 간의 링크에 대한 홉 카운트를 고려한 링크 E_ij의 오더 값은 E_ij[od] 형태로 표시되며, 임의의 라우터 N의 홉 카운트를 고려한 라우터 N의 오더 값은 N[od] 형태로 표시된다. 즉, "od"가 오더 값을 나타낸다.

홉 카운트 및 단대단 지연을 기반으로 한 라우터 및 링크의 오더 값을 산출하기 위해, 본 발명에서는 수신 LER(f)부터 시작하여 송신 LER(e) 방향으로 탐색한다.

먼저, 수신 LER(f)의 오더 값은 0으로 초기화하고 나머지 모든 링크 및 라우터의 오더 값은 무한대(∞)로 초기화 한다.

임의의 라우터에 연결된 링크의 홉 카운트를 고려한 링크의 오더 값은 수학식 2에 의해 산출된다.

여기에서,

E_ij(o)는 라우터 i와 라우터 j 간의 링크에 대한 홉 카운트를 고려한 오더 값, N(o)는 임의의 라우터 N에 대한 홉 카운트를 고려한 오더 값, E_ij(w)는 라우터 i와 라우터 j 간의 링크에 대한 트래픽 유입량을 고려한 가중치 값을 나타낸다.

수신 LER(f)의 오더 값은 0 으로 초기화 되었으므로, 수신 LER(f)에 연결된 링크 E_cf 및 E_lf의 오더 값은 다음과 같이 계산된다.

본 실시예에서, 링크 E_cf의 트래픽 량을 고려한 링크 가중치는 2000.005이고, 현재 링크 E_cf에 대한 링크 오더 값은 ∞로 초기화 된 상태이다. 따라서, 기존 의 링크 E_cf에 대한 오더 값 ∞이 라우터 f의 오더 값 0에 1,000,000을 합산한 값 1,000,000보다 크므로, 현재의 링크 E_cf에 대한 홉 카운트를 고려한 오더 값 E_cf(o)은 해당 링크의 가중치 2000.005에 1,000,000을 합산한 값 1002000.005가 된다.

같은 방법으로, 링크 E_lf의 오더 값은 1001000.005가 된다.

그리고, 임의의 라우터 N과 링크로 연결된 이웃 라우터 N_neigh에 대한 오더 값 N_neigh(o)은 수학식 3에 의해 산출한다.

따라서, 수신 LER(f)과 링크 E_cf로 연결된 라우터인 LSR(c)에 대한 오더 값은, 수신 LER(f)과 연결된 링크 E_cf의 오더 값 E_ij(o)이 수학식 2에 의해 1002000.005이고 링크 E_cf와 연결된 이웃 라우터인 LSR(c)의 오더 값 N_neigh(o)이 ∞로 초기화 된 상태이므로, 링크 E_cf의 오더 값으로 변경되어 1002000.005가 된다.

같은 방법으로, 수신 LER(f)와 링크 E_lf로 연결된 라우터인 LSR(l)에 대한 오더 값은 링크 E_lf의 오더 값으로 변경되어 1001000.005가 된다.

이러한 방법으로 모든 라우터와 링크에 대한 오더 값을 계산하면, 도 6과 같이 된다.

도 6과 같이, 모드 라우터와 링크에 대한 오더 값이 산출되면, 산출된 오더 값을 기반으로 이용자가 요청한 대역폭 및 단대단 지연을 만족하는 라우팅 경로들 중 최소의 홉 카운트를 가지는 최적의 라우팅 경로를 산출한다(단계 240).

도 7은 이용자의 요구사항 (S,D,b,d) = (e,f,10Mbps,8ms)을 만족시키는 최적의 라우팅 경로를 산출하는 과정을 설명하기 위한 도면이다.

먼저, 송신 LER(e)에서 자신과 연결된 링크들 중 하나를 최적의 링크로 선택한다. 이러한 링크 선택시, 수학식 4를 이용하여 해당 링크가 이용자가 요청한 대역폭 및 단대단 지연을 만족시킬 수 있는지를 판단한다. 또한, 미래의 예측 가능한 송신 LER(e)을 통해 유입될 다양한 트래픽을 고려하여 최적의 경로를 산출하기 위하여 수학식 4를 사용한다.

송신 LER(e)은 자신과 연결된 두 개의 링크 E_eb와 E_eh에 대해 수학식 4를 적용시켜 최소의 값을 가지는 링크를 선택한다. 링크 E_eb와 E_eh에 대해 수학식 4를 적용시켜 나머지 값을 구하면, E_eh가 E_eb보다 적은 나머지 값을 가진다. 따라서 송신 LER(e)은 링크 E_eh를 선택한다.

만일, 수학식 4를 적용한 결과, 나머지 값이 동일한 두 개 이상의 링크가 존 재하는 경우에는 수학식 5를 적용하여 제일 적은 몫을 가지는 링크를 선택한다.

수학식 5를 적용하는 이유는 트래픽 유입 량을 고려하여 선택한 라우팅 경로가 두 개 이상 존재하는 경우, 최소의 홉 카운트를 가지는 라우팅 경로를 선택하여 망 자원 사용율을 최소화 하기 위함이다.

만일, 수학식 5를 적용하여 홉 카운트가 최소인 라우팅 경로가 복수개 존재하는 경우에는, 수학식 6을 적용하여 단대단 지연이 최소인 라우팅 경로를 선택한다.

상술된 과정을 거쳐 송신 LER(e)에서 링크 E_eh가 선택되면, 다음에 해당 링크 E_eh를 통해 연결되는 이웃 라우터인 LSR(h)에서도 동일한 방법으로 자신과 연결된 링크들 중 하나 E_hk를 최적의 링크로 선택한다.

이와 같은 방법으로 수신 LER(f)에 도달할 때 까지 각 라우터에서의 최적의 링크 선택을 반복 수행하면, 도 7에서 굵은 화살표와 같은 최적의 라우팅 경로가 산출된다.

위와 같은 3 단계의 필터링 과정을 거쳐, 임의의 송/수신점 사이의 트래픽 유입량을 고려하고, 홉 카운트 및 단대단 지연을 최소화 할 수 있는 라우팅 경로를 산출하기 위한 방법을 실현할 수 있다.

상술한 바와 같이, 본 발명의 라우팅 경로 설정 방법은 임의의 송/수신점 간에 레이블 스위칭 경로를 설정시 현재의 망 형상에서 미래의 트래픽 수요 예측 결과와 트래픽 량을 기반으로 하여 경로를 설정함으로써 동일한 망 자원을 가지고 최대의 LSP를 제공하여 망자원의 활용도를 극대화하고 이에 따라 동일한 망자원으로 최대의 수익을 창출할 수 있다.

Claims (7)

1. 임의의 송신 레이블 에지 라우터(LER)에 유입될 미래 트래픽 유입량을 산출하는 제 1 단계;

   망 형상과 상기 미래 트래픽 유입량을 기준으로 상기 임의의 송신 레이블 에지 라우터와 수신 레이블 에지 라우터 간에 가능한 모든 라우팅 경로를 산출하고, 산출된 라우팅 경로에서 각 링크의 가중치를 계산하는 제 2 단계;

   상기 계산된 링크의 가중치를 기반으로 홉 카운트 및 단대단 지연을 고려하여 상기 라우팅 경로 내 라우터와 링크의 오더 값을 계산하는 제 3 단계; 및

   상기 오더 값을 기반으로 이용자가 요청한 대역폭 및 단대단 지연을 만족하는 라우팅 경로를 산출하는 제 4 단계를 포함하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.
2. 제 1항에 있어서, 상기 각 링크의 가중치는

   다음식과 같은 링크 가중치 계산 알고리즘(LWCA:Link Weight Computation Algorithm)에 의해 계산되는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.

   

   여기서,

   E_ij(load)는 상기 송신 레이블 에지 라우터와 수신 레이블 에지 라우터 간 라우팅 경로 산출시 포함된 라우터 i와 라우터 j 간의 링크가 해당 라우팅 경로를 수용하기 위해 필요한 총 대역폭 합, E_ij(cc)는 라우터 i와 라우터 j 간의 링크가 임의의 송/수신점 간 라우팅 경로 산출시 라우팅 경로에 포함된 수, E_ij(d)는 라우터 i와 라우터 j 간 링크의 지연임.
3. 제 1항 또는 제 2항에 있어서, 상기 제 3 단계는

   상기 수신 레이블 에지 라우터의 오더 값을 0으로 초기화하고, 나머지 모든 링크 및 라우터의 오더 값을 무한대(∞)로 초기화 한 후,

   상기 수신 레이블 에지 라우터에서 상기 송신 레이블 에지 라우터 방향으로 상기 라우팅 경로에 포함되는 라우터와 링크의 오더 값을 계산하는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.
4. 제 3항에 있어서, 상기 수신 레이블 에지 라우터에 연결된 링크의 오더 값은

   다음식에 의해 계산되는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.

   

   여기서,

   E_ij(o)는 라우터 i와 라우터 j 간의 링크에 대한 홉 카운트를 고려한 오더 값, N(o)는 임의의 라우터 N에 대한 홉 카운트를 고려한 오더 값, E_ij(w)는 라우터 i와 라우터 j 간의 링크 가중치임.
5. 제 4항에 있어서, 상기 제 4 단계는

   상기 라우팅 경로 상의 각 라우터가 자신과 연결된 링크가 복수개인 경우 해당 링크의 오더 값을 다음식에 적용시켜 최소의 값을 가지는 링크를 선택하여 상기 라우팅 경로를 산출하는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.

   

   여기서, E_ij(o)는 라우터 i와 라우터 j 간의 링크의 오더값임.
6. 제 5항에 있어서,

   상기 최소값이 동일한 링크가 복수개 존재하는 경우, 최소의 홉 카운트를 가지는 라우팅 경로를 선택하기 위해 해당 링크의 오더 값을 다음식에 적용하여 가장 적은 몫을 가지는 링크를 선택하는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.

   
7. 제 6항에 있어서,

   홉 카운트가 최소인 라우팅 경로가 복수개 존재하는 경우, 단대단 지연이 최소인 라우팅 경로를 선택하기 위해 해당 링크의 오더 값을 다음식에 적용시켜 최소의 값을 가지는 경로를 선택하는 것을 특징으로 하는 멀티프로토콜 레이블 스위칭 망에서의 서비스 품질 보장형 라우팅 경로 설정 방법.

   

Images