라우팅 및 파장 할당

Routing and Wavelength Assignment(RWA; 라우팅 및 파장 할당) 문제는 광접속 수를 최대화하는 것을 목적으로 하는 광네트워크 문제입니다.

정의.

RWA 문제의 일반적인 목적은 확립된 접속 수를 최대화하는 것입니다.각 접속 요구에는 루트와 파장을 지정해야 합니다.파장 변환기의 사용이 상정되지 않는 한, 파장은 패스 전체에 대해 일정해야 합니다.다른 파장을 사용하고 있는 경우, 2개의 접속 요구가 같은 광링크를 공유할 수 있습니다.

RWA 문제는 Integer Linear Program(ILP; 정수선형 프로그램)에서 정식으로 정의할 수 있습니다.여기에 제시된 ILP 공식은 에서 ^[1]추출한 것입니다.

최대화:

${\displaystyle C_{0}(\rho,q)=\sum _{i=1}^{N_{sd}}m_{i}}$

의 영향을 받는.

${\displaystyle m_{i}\geq 0, 정수, i=1,2,...,N_{sd}}$

${\displaystyle c_{ij}\in {0,1},i=1,2,P,j=1,2,...W}$

${\displaystyle C^{T}B\leq l_{W\times L}}$

${\displaystyle m\leq 1_{W}C^{T}A}$

${\displaystyle m_{i}\leq q_{i}\rho,i=1,2,...,N_{sd}$

${\displaystyle N_{}}$ s$$ \ $display style$ N _ { $sd$} $n$ 、 ${\displaystyle {mi}_{}}$ $\$ $displaystyle$ m$_$ { $i}$ n$$ 、 각 송신원/수신처 쌍에 확립된 접속의 수입니다.$(\displaystyle$ L$)$은 링크 $수이고{\displaystyle }$W(\$displaystyle$ W$)$는 파장 수입니다.$\displaystyle$P는 접속을$$ 라우팅하기 위한 경로 세트입니다.$display style$$$$P\times$ N_${sd}$ 는$$, 액티브한 송신원과 행선지의 페어를 나타내는 매트릭스입니다${\displaystyle .}B{\displaystyle }$ :${\displaystyle P}$ ×$$ \ $displaystyle$B :$P\times$L은$$ 액티브한 링크를 나타내는 매트릭스입니다${\displaystyle .C}$ :${\displaystyle }$P ×$$ \ $displaystyle$C :$P\times$ W$}$는 경로 및 파장 할당 매트릭스입니다.

위의 공식은 트래픽 요구가 사전에 알려져 있는 것을 전제로 하고 있습니다.이런 유형의 문제는 Static Lightpath Establishment(SLE)라고 불립니다.위의 공식에서도 신호의 품질은 고려되지 않습니다.

SLE RWA 문제는 NP-complete ^[2]in으로 판명되었습니다.$이$ 증거에는 $그래프$$$색채성 문제가 포함됩니다$.$즉, SLE RWA 문제를 해결하는 것은 일반 그래프의 색수를 찾는 것만큼 복잡합니다.다이내믹 RWA는 스태틱 RWA보다 복잡하기 때문에 다이내믹 RWA도 NP-complete여야 합니다.

또 다른 NP-완전증명이 제시된다.^[3]이 증명에는 멀티커뮤니티 플로우 문제의 경감이 포함됩니다.

RWA 문제는 신호의 품질을 고려해야 하기 때문에 더욱 복잡해집니다.광학적 장애의 대부분은 비선형이기 때문에 네트워크의 정확한 상태를 알고 있어도 표준 최단 경로 알고리즘을 사용하여 최적으로 해결할 수 없습니다.이는 일반적으로 안전한 가정이 아니기 때문에 한정된 네트워크 정보만을 사용하여 솔루션을 효율적으로 사용할 필요가 있습니다.

방법론

RWA가 복잡하기 때문에 문제 해결에는 다음 두 가지 일반적인 방법이 있습니다.

• 첫 번째 방법은 라우팅 부분을 먼저 해결하고 다음으로 파장을 할당하는 것입니다.루트 선택에는 고정 경로라우팅, 고정 대체 라우팅 및 적응형 라우팅의 3가지 유형이 있습니다.
• 두 번째 접근법은 루트 선택과 파장 할당을 모두 함께 고려하는 것입니다.

첫 번째 라우팅 후 파장 할당

라우팅 알고리즘

고정 경로 라우팅

고정 경로 라우팅은 광경로를 찾는 가장 간단한 방법입니다.특정의 송신원과 행선지 쌍에 대해서, 항상 같은 고정 루트가 사용됩니다.일반적으로 이 경로는 Dijkstra의 알고리즘과 같은 최단 경로 알고리즘을 사용하여 미리 계산됩니다.이 접근방식은 매우 간단하지만 퍼포먼스는 보통 충분하지 않습니다.고정 경로를 따라 리소스가 사용 중인 경우 다른 경로가 있더라도 이후 연결 요청은 차단됩니다.

SP-1(최단 패스, 1 프로브) 알고리즘은 고정 패스라우팅 솔루션의 예입니다.이 알고리즘은 비용 함수로서 광라우터의 수를 사용하여 최단 경로를 계산합니다.최단 경로를 사용하여 연결을 확립하기 위해 단일 프로브가 사용됩니다.실행시간은 Dijkstra 알고리즘의 비용입니다${\displaystyle .}O{\displaystyle }$ (${\displaystyle m}$ + ${\displaystyle n}$ ${\displaystyle \log n}$n$$) { $display style$O ($m$ +$n$ \ $log$n )$$。$여기$서$$m { $display$ style m$$}은$$ 엣지 수,$n{\displaystyle }$ { $display style$ n$}$은 라우터의 수입니다.실행 시간은 미리 정해진 경로를 사용하는 경우 상수입니다.

이 SP-1의 정의에서는 비용 함수로서 홉카운트를 사용합니다.SP-1 알고리즘은 EDFA의 수 등 다른 비용 함수를 사용하도록 확장할 수 있습니다.

고정 대체 라우팅

고정 대체 라우팅은 고정 경로 라우팅의 확장입니다.특정의 송신원 및 행선지 쌍에 대해서, 1개의 고정 루트만을 가지는 것이 아니라, 복수의 루트가 보존됩니다.프로브는 시리얼 또는 병렬로 송신할 수 있습니다.각 접속 요구에 대해서, 송신원노드는 각 패스상의 접속을 검출하려고 합니다.모든 경로에 장애가 발생하면 연결이 차단됩니다.여러 경로를 사용할 수 있는 경우 그 중 하나만 사용됩니다.

${\displaystyle }$\ $displaystyle$p （ $Shortest$ $Path{\displaystyle }$ $$, p \ $displaystyle$ p$$} Probes$$ , > \ $displaystyle$p $1$) 알고리즘은 고정 대체 라우팅의 예입니다.$이{\displaystyle }$ 알고리즘은 광라우터의 수를 비용함수로 사용하여 p$\displaystyle$p의$$ 최단 경로를 계산합니다.Yen 알고리즘을^[4] 사용한 $실행시간$은 O${\displaystyle }$( ${\displaystyle p}$n (${\displaystyle m}$ + ${\displaystyle n}$ ${\displaystyle \log \mathrm{nn}}$)$${ $displaystyle$O ( $pn ( m$ +$n$ \ $log$n ) } 。$m$ { $displaystyle$ m$$}는$$ 엣지 수,$n{\displaystyle }$ { $displaystyle$ n$}$은 라우터 수, $p{\displaystyle }${ $displaystyle$ p$}$는 경로 수입니다.경로가 미리 계산되어 있는 경우 실행 시간은 일정한 요소가 됩니다.

적응형 라우팅

고정 패스 라우팅과 고정 대체 라우팅의 주요 문제는 어느 알고리즘도 네트워크의 현재 상태를 고려하지 않는다는 것입니다.미리 정해진 경로를 사용할 수 없는 경우 다른 경로가 존재하더라도 연결 요청은 차단됩니다.고정 패스 라우팅과 고정 대체 라우팅은 모두 품질에 대응하고 있지 않습니다.이러한 이유로, RWA의 대부분의 연구는 현재 적응형 알고리즘에서 이루어지고 있습니다.적응형 라우팅의 5가지 예로는 LORA, PABR, IA-BF, IA-FF 및 AQoS가 있습니다.

적응형 알고리즘은 기존 알고리즘과 물리적 인식 알고리즘의 두 가지 범주로 나뉩니다.기존의 적응형 알고리즘에서는 신호 품질을 고려하지 않지만 물리 인식 적응형 알고리즘에서는 고려합니다.

기존의 적응형 RWA

Lexicographic Routing Algorithm(LORA; 사전 라우팅 알고리즘) 알고리즘은 에서 ^[5]제안되었습니다.LORA의 주된 발상은 접속 요구를 네트워크의 폭주 영역에서 멀리 라우팅하여 접속 요구가 받아들여질 가능성을 높이는 것입니다.이것은 각 링크의 비용을 ${\displaystyle c}$ ${\displaystyle o}$ s${\displaystyle }$t (${\displaystyle l}$ ) ${\displaystyle =}$ ${\displaystyle {\beta }^{}}$ ${\displaystyle u^{}}$ ${\displaystyle s^{}}$ a ${\displaystyle g^{}}$e ($l$) （ \ $display style$ cost ( l ) = \ $display$^ { $l$$$） } 로 $설정함$으로써 실현됩니다.$\beta {\displaystyle }$ { $\$ $displaystyle$$$$}$는 트래픽 부하에 따라 동적으로 조정 가능한 $파라미터$이며 ${\displaystyle u}$ ${\displaystyle s\mathrm{ge}}$ (${\displaystyle }$l$$)는 파장 단위입니다.링크$$l\$displaystyle$ l$.$ 표준 최단 경로 알고리즘을 사용하여 경로를 찾을 수 있습니다.이를 위해서는 각 옵티컬스위치가 최신 사용정보를 정기적으로 브로드캐스트해야 합니다.LORA 에서는 물리적인 장애는 고려되지 않습니다.

β$(\displaystyle\beta)$가 1일 $경우{\displaystyle }$ LORA 알고리즘은 SP 알고리즘과 동일합니다.β$(\displaystyle\beta)$ $값$을 높이면 덜 사용되는 루트에 대한 편중이 증가합니다.β$(\displaystyle\beta)$의 최적값은 잘 알려진 힐 클라이밍 알고리즘을 사용하여 계산할 수 있습니다.제안서에서$$β$(\displaystyle$\beta$)$의 최적값은 1.1에서 1.2 사이였다.

물리 인식 적응형 RWA

Physical-Aware Backward Reservation Algorithm(PABR; 물리 인식 역방향 예약 알고리즘)은 LORA의 확장입니다.PABR은 물리적인 장애를 고려하는 것과 파장 선택의 개선이라는2가지 방법으로 퍼포먼스를 향상시킬 수 있습니다.PABR이 광패스를 검색할 때 선형 장애로 인해 허용되지 않는 신호 품질을 가진 경로가 플루닝됩니다.즉, PABR은 추가 품질 제약이 있는 LORA입니다.

PABR에서는 선형 장애만 고려됩니다.한편, 비선형 장애는 글로벌 트래픽 지식이 필요하기 때문에 분산 환경에서는 추정할 수 없습니다.

PABR은 파장 선택 시 신호 품질도 고려합니다.이를 위해서는 허용되지 않는 신호 품질 수준을 가진 모든 파장을 고려 대상에서 제외합니다.이 접근방식은 Quality First Fit이라고 불리며 다음 섹션에서 설명합니다.

LORA와 PABR은 모두 싱글프로빙 또는 멀티프로빙 중 하나로 구현할 수 있습니다.$p$의 최대수(\displaystyle p)는$$$또는$ PABR-p(\$displaystyle$$$p$)$로 표시됩니다.싱글 프로빙에서는 루트 선택에 의해 선택되는 패스는 1개뿐입니다.멀티프로빙에서는 복수의 패스가 병렬로 시행되어 접속 성공 가능성이 높아집니다.

기타 라우팅 어프로치

IA-BF - Information Aware Best Fit(IA-BF) 알고리즘이 제안되었습니다.^[6]이 알고리즘은 글로벌 정보를 사용하여 항상 사용 가능한 최단 경로와 파장을 선택하기 위해 대량의 통신에 의존하는 분산 접근법입니다.이것은 시리얼 멀티프로빙을 사용하여 실현됩니다.사용 가능한 최단 경로 및 파장이 먼저 시도되고 장애 발생 시 사용 가능한 두 번째 경로 및 파장이 시도됩니다.이 과정은 경로와 파장이 정상적으로 발견되거나 모든 파장이 시도될 때까지 계속됩니다.

멀티프로빙 어프로치를 사용하면 IA-BF가 PABR-1과 LORA-1을 모두 능가할 수 있습니다.그러나 프로브 수가 증가함에 따라 알고리즘의 성능은 비슷해집니다.

IA-FF - IA-FF는 IA-BF의 단순한 확장입니다.파장은 최소 비용 측면에서 선택하는 것이 아니라 지수에 따라 순서대로 선택한다.IA-BF는 대부분의 시나리오에서 IA-FF를 능가하는 경향이 있습니다.

AQoS - Adaptive Quality of Service(^[7]AQoS)가 에서 제안되었습니다.이 알고리즘은 몇 가지 점에서 독특합니다.첫 번째로 각 노드는 2개의 카운터를 $유지$합니다.${\displaystyle N_{}}$ ${\displaystyle B_{}}$ E R$$\ $display style$N _ { $B$ ）$ER}$ $및$ N ${\displaystyle w_{}}$ a ${\displaystyle v_{}}$ { $display style$ N _ { $wave$ 。각 카운터의 목적은 경로와 파장의 가용성 또는 품질 요건 중 어떤 문제가 블로킹의 더 큰 요인인지를 판별하는 것입니다.알고리즘은 큰 문제에 따라 루트를 다르게 선택합니다.

분류하는 또 다른 그 AQoS는 링크를 비용으로 그 전기를 사용하기 때문이다.i하루에 500파운드 h{\displaystyle i_{월}}고리의 비용으로, 이 공식에 의해 D나는 갈∑ j=1N나는 10통나무 ⁡[Q나는, j(s)/Q 나는, j(d)]N나는{\displaystyle D_{나는}={\frac{\sum_{j=1}^{N_{나는}}10\log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]}계산한다.{N_{나는}}}}이 N나는{\displaystyle N_{나는}}은 j 바래{\displaystyle j_{월}의 나는 하루에 500파운드 h{\displaystyle i_{월}}링크, Q나는, j({\displaystyle Q_{i,j}^{(s)}}와 Q나는, j({\displaystyle Q_{i,j}^{(d)}}에 lightpaths의 수는 품질 계수 측정은}lightpat.Hi하루에 500파운드 h{\displaystyle i_{월}}링크, 각각 소스와 목적지 노드에서.이러한 반복되는 품질 계수 평가 computationally은 매우 비싸다.

이 알고리즘은 단일 프로빙 접근법입니다.종이에서 ALT-AQoS(대체 AQoS)라고 명명하는 멀티프로빙 접근법은 동일한 기본 아이디어에 대한 단순한 확장입니다.

파장 할당

가장 일반적인 파장 할당 방법 중 두 가지는 First Fit과 Random Fit입니다.First Fit(퍼스트 핏)은 지수가 가장 낮은 사용 가능한 파장을 선택합니다.랜덤 핏은 사용 가능한 파장을 결정하고 그 중에서 랜덤으로 선택합니다.두 알고리즘의 복잡도는 O${\displaystyle }$(${\displaystyle w}$ $)\displaystyle$ O$(w)$입니다$.$$여기$서 w$\displaystyle$w는$$ 파장의 수입니다.첫 번째 적합은 랜덤 적합보다 성능이 우수합니다.

에서는 신호 품질을 고려하기 위해 First Fit 및 Random Fit으로의 확장이 제안되었습니다.Quality First Fit 및 Quality Random Fit은 허용할 수 없는 신호 품질을 가진 파장을 고려 대상에서 제거합니다.단, Q 계수를 추정하기 위해서는 $최대$ w$\displaystyle$w 호출이$$ 필요하기 때문에 이들 알고리즘의 복잡도는 더 높아집니다.

기타 파장 할당 알고리즘에는 최소 사용, 최소 사용, 최소 제품, 최소 부하, 최대 ^[8]합계 및 상대 용량 ^[9]손실이 있습니다.대부분의 사용 빈도가 최소 사용 빈도를 크게 웃돌고 첫 번째 적합치보다 약간 더 높습니다.Min Product, Lest Loaded, Max Sum 및 Relative Capacity Loss는 모두 향후 요구가 차단될 가능성을 최소화하는 파장을 선택하려고 합니다.

이러한 알고리즘의 큰 단점은 대량의 통신 오버헤드가 필요하기 때문에 일원화된 네트워크 구조를 가지고 있지 않으면 실장할 수 없다는 것입니다.

공동 라우팅 및 파장 할당

루트와 파장을 개별적으로 선택하는 대체 접근법은 이들을 함께 고려하는 것입니다.이러한 접근방식은 이론적인 경향이 있으며 실용적이지 않습니다.이것은 NP-완전한 문제이기 때문에 정확한 해결책은 불가능할 수 있습니다.근사 기법도 일반적으로는 중앙 집중식 제어와 사전 정의된 트래픽 요구가 필요하기 때문에 그다지 유용하지 않습니다.두 가지 공동 접근 방식은 ILP 제제와 아일랜드 호핑입니다.

위의 ILP 공식은 기존의 ILP 솔버를 사용하여 해결할 수 있습니다.이는 일반적으로 정수 제약을 일시적으로 완화하여 문제를 최적으로 해결한 후 실제 솔루션을 정수 솔루션으로 변환함으로써 이루어집니다.브랜치 및 바운드 접근방식을 사용하여 제약조건을 추가하고 프로세스를 무한정 반복할 수 있습니다.

저자는 제약된 RWA 문제를 효율적이고 최적으로 해결하기 위해 사용할 수 있는 알고리즘에 대해 보고한다.저자들은 한 슬라이스를 요청함으로써 제한된 RWA 문제로 축소될 수 있는 RSA(Restricted Routing and Spectrum Assignment) 문제를 연구한다.제약에 의해 경로 길이가 제한됩니다.

저자는 범용 Dijkstra 알고리즘에 대해 보고합니다.이 알고리즘은 패스 길이에 제한을 두지 않고 RWA, RSA 및 라우팅, 변조, 스펙트럼 할당(RMSA) 문제를 효율적이고 최적으로 해결하기 위해 사용할 수 있습니다.

레퍼런스