KR20130109132A

KR20130109132A - 타이-브레이킹 메커니즘으로의 피드백으로서 링크 사용률을 갖는 멀티-프로토콜 레이블 스위칭(ｍｐｌｓ)을 위한 자동화된 트래픽 엔지니어링

Info

Publication number: KR20130109132A
Application number: KR1020137008858A
Authority: KR
Inventors: 데이비드 이안 앨런; 스콧 앤드류 맨스필드
Original assignee: 텔레호낙티에볼라게트 엘엠 에릭슨(피유비엘)
Priority date: 2010-09-08
Filing date: 2011-08-04
Publication date: 2013-10-07
Also published as: AU2011300438A1; JP5985483B2; US20120057466A1; JP2013539646A; TWI521924B; EP2614618A1; TW201215063A; US8553562B2; WO2012032426A1; BR112013003488A2; AU2011300438B2; EP2614618B1; CN103081416A

Abstract

향상된 부하 분산을 위한 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크의 노드에서 구현되는 방법으로서, 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제1 집합을 결정하는 단계, 일반 알고리즘 타이-브레이킹 프로세스를 적용하여 적어도 제1 최단 경로를 선택하는 단계, MPLS 네트워크의 각 링크에 대한 링크 사용률 값을 계산하는 단계, 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제2 집합을 결정하는 단계, 각 최단 경로에 대응하는 링크 사용률 값들에 기초하여 최단 경로들의 제2 집합 내의 각 최단 경로들에 대한 경로 사용률 값을 생성하는 단계, 및 상기 경로 사용률 값을 기초로 하여 최단 경로들의 제2 집합으로부터 제2 최단 경로를 선택하는 단계를 포함하며, 이에 의해서 상기 경로 사용률 값을 고려한 제2 서브셋의 선택은 MPLS 네트워크 전체에 걸친 부하 분산의 표준 편차를 최소화한다.

Description

타이-브레이킹 메커니즘으로의 피드백으로서 링크 사용률을 갖는 멀티-프로토콜 레이블 스위칭(ＭＰＬＳ)을 위한 자동화된 트래픽 엔지니어링{AUTOMATED TRAFFIC ENGINEERING FOR MULTI-PROTOCOL LABEL SWITCHING(MPLS) WITH LINK UTILIZATION AS FEEDBACK INTO THE TIE-BREAKING MECHANISM}

<관련 출원에 대한 상호 참조>

본 출원과 동일한 날짜에 출원되고 공동으로 소유된 "AUTOMATED TRAFFIC ENGINEERING FOR 802.1AQ BASED UPON THE USE OF LINK UTILIZATION AS FEEDBACK INTO THE TIE BREAKING MECHANISM"에 대하여 David Ian Allen과 Scott Andrew Mansfield가 공동출원한 특허 출원에 대하여 상호 참조가 이루어졌다. 상호 참조된 출원은 참조에 의하여 본 명세서에 원용된다.

<기술분야>

본 발명의 실시예들은 네트워크 내의 부하 분산을 향상시키기 위한 방법 및 장치에 관한 것이다. 특히, 본 발명의 실시예들은 네트워크 내의 노드들 간에 복수의 동일 비용 경로들을 갖는 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크 내의 부하 확산(load spreading) 위한 방법에 관한 것이다.

부하 분산 또는 부하 확산은 네트워크 내에서 대역폭이 더욱 효율적으로 활용되고 전체의 성능이 개선되게 하는 방법이다. 오늘날 사용되는 대부분의 자동화된 부하 분산 기술 및 부하 확산 기술들은 매우 국소적 관점으로만 동작하며, 이 부하 분산 기술 및 부하 확산 기술들은 주어진 목적지까지의 경로들의 수 또는 다음 홉(hop)만을 고려하고 네트워크 내의 트래픽의 전체 분산을 고려하지 않는다.

동일 비용 다중 경로(Equal cost multi-path; ECMP)는, 주어진 목적지로 어떻게 패킷을 포워딩하는가에 관한 결정이, 데이터베이스 계산들을 실행할 때 최단 경로가 되는 것에 대하여 타이(tie)인 복수의 "동일 비용" 경로들 중 임의의 것으로 귀착할 수 있는 경우에 이용되는, 라우팅 네트워크 내의 유니캐스트 트래픽의 부하 확산을 위한 일반적인 전략이다. ECMP는 대부분의 유니캐스트 라우팅 프로토콜 및 필요한 지원 데이터 플레인 하드웨어가 장착된 노드들과 함께 이용될 수 있는데, 이는 단일 라우터에 국소적이며 중간 노드마다의 잡다한 수신 및 완전한 포워딩 테이블을 가정하는 홉마다의 결정에 의존하기 때문이다. 네트워크 내의 주어진 임의의 노드에서 ECMP를 이용하여, 부하는 동일 비용의 다음 홉들의 집합에 걸쳐 의사 균등하게(pseudo-evenly) 분할된다. 이 프로세스는 주어진 목적지로의 둘 이상의 경로가 존재하는 네트워크의 각각의 홉마다 독립적으로 구현된다.

많은 구현들에서, 복수의 동일 비용의 다음 홉들의 존재를 접하는 경우, 각각의 패킷은 인터넷 프로토콜(IP) 헤더와 같은 엔트로피의 소스에 대하여 검사되고, 경로 수의 헤더 정보의 해시 모듈로가 특정 패킷에 대한 다음 홉을 선택하기 위하여 이용된다. 고도로 축적된 트래픽에 대하여, 이 방법은 규칙적인 토폴로지에서(즉, 대칭적인 토폴로지에서) 평균적으로 균등하게 부하를 분배하고, 덜 규칙적인 토폴로지에서 일부 개선을 제공한다.

멀티프로토콜 레이블 스위칭(MPLS)은 네트워크를 통해 트래픽을 포워딩하기 위해 이용되는 데이터 플레인 기술 및 컨트롤 플레인 기술의 조합이다. MPLS는 레이블 룩업 및 변환("스와핑(swapping)"이라고 함)을 이용하여 네트워크에 걸쳐 트래픽을 포워딩하기 위해 트래픽의 스트림에 할당된 홉 단위 레이블들(per hop labels)을 이용한다. 네트워크의 각 노드는 네트워크를 통해 수신된 인입 트래픽을 검토하고 그 트래픽을 그것의 레이블에 기초하여 포워딩함으로써 MPLS를 지원하며, 여기에서의 레이블은 일반적으로 각 홉에서 변환되거나 "스와핑"된다.

MPLS 네트워크는 동일 비용 경로들에 걸쳐 부하를 분산시키거나 확산하기 위해 홉 단위 ECMP를 이용하여 네트워크 내의 라우팅된 트래픽의 분산을 향상시킬 수 있다. MPLS 네트워크에서, 네트워크 내의 모든 노드에 의해서 각 동일 비용 경로에 대한 다음 홉 각각에 레이블 스위치 경로(LSP)가 설정된다. 네트워크 내의 주어진 목적지에 대한 포워딩 경로는, 네트워크 내의 각 노드에서 최단 경로 우선(SPF: shortest path first) 알고리즘을 이용하여 계산되고, 노드 내의 로컬 레이블 바인딩에 매핑되고(mapped), 그 결과에 따른 접속성이 다중점-대-다중점 메시(mesh)로서 나타난다. 복수의 동일 비용 경로로 향하는 트래픽이 주어졌을 때의 각 노드들은, 경로들의 집합에 걸친 플로우 분산의 균등성을 최대화하기 위해서 경로 선택의 메커니즘의 일부분으로서 페이로드 정보를 이용한다. 다중점-대-다중점 LSP의 설정은 자동화된다.

레이블 분배 프로토콜(LDP) 또는 유사한 프로토콜은 네트워크 내의 가능한 모든 포워딩 동치 클래스들(forwarding equivalence classes)에 대한 레이블 바인딩의 완전한 집합을 오버프로비전(overprovision)하기 위하여 이용되고, 그러면 각 레이블 스위치 라우터(LSR)는 각 포워딩 동치 클래스에 대한 다음 홉들의 집합을 독립적으로 계산하고, 임의의 특정 순간에 어떠한 레이블 바인딩을 실제로 이용할 것인지 선택한다.

향상된 부하 분산을 위해 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크의 노드 내에서 구현되는 방법으로서, 노드는 최소 비용 최단 경로 트리들을 만들어내기 위하여 일반 알고리즘 타이-브레이킹 프로세스(common algorithm tie-breaking process)를 각각 구현하는 MPLS 네트워크 내의 복수의 노드들 중 하나이고, 노드는 MPLS 네트워크의 토폴로지를 저장하는 토폴로지 데이터베이스를 포함하고, MPLS 네트워크의 토폴로지는 복수의 노드들 및 노드들 간의 링크를 포함하며, 방법은: 토폴로지 데이터베이스에 저장된 MPLS 네트워크의 토폴로지 상에서 최단 경로 탐색 알고리즘을 실행함으로써 MPLS 네트워크 내의 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제1 집합을 결정하는 단계; 일반 알고리즘 타이-브레이킹 프로세스를 적용하여 각 MPLS 노드 쌍에 대한 최단 경로들의 제1 집합으로부터 적어도 제1 최단 경로를 선택하는 단계; 각 링크를 통과하는 선택된 최단 경로들의 카운트에 기초하여 MPLS 네트워크의 각 링크에 대한 링크 사용률 값을 계산하는 단계; 토폴로지 데이터베이스에 저장된 MPLS 네트워크의 토폴로지 상에서 최단 경로 탐색 알고리즘을 실행함으로써 MPLS 네트워크 내의 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제2 집합을 결정하는 단계; 각 최단 경로에 대응하는 링크 사용률 값에 기초하여 하나 이상의 최단 경로의 제2 집합 내의 각 최단 경로에 대한 경로 사용률 값을 생성하는 단계; 상기 경로 사용률 값에 기초하여 하나 이상의 최단 경로의 제2 집합으로부터 제2 최단 경로를 선택하는 단계 - 선택하는 단계는 하나 이상의 최단 경로들의 집합에 동일 경로 사용률 값을 갖는 복수의 최단 경로가 있는 경우 일반 알고리즘 타이-브레이킹 프로세스를 이용함 -; 및 레이블 정보 데이터베이스 내에, 각 MPLS 노드 쌍에 대하여 적어도 제1 최단 경로 및 제2 최단 경로를 저장하는 단계 - 레이블 정보 데이터베이스는 MPLS 노드로 들어오는 트래픽을 어디로 포워딩할지를 나타냄 - 를 포함하며, 이에 의해서 경로 사용률을 고려한 제2 서브셋의 선택은 MPLS 네트워크 전체에 걸친 부하 분산의 표준 편차를 최소화한다.

자신을 포함하는 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크 내의 향상된 부하 분산을 위한 네트워크 구성요소로서, 네트워크 구성요소는 MPLS 네트워크 내의 복수의 노드들 중 하나이고, MPLS 네트워크의 토폴로지는 복수의 노드들 및 노드들 간의 링크를 포함하고, 네트워크 구성요소는: MPLS 네트워크 내의 각 링크에 대한 링크 정보를 저장하는 토폴로지 데이터베이스; 네트워크 구성요소의 각 포트에 대한 레이블 정보를 저장하는 레이블 정보 데이터베이스 - 레이블 정보 데이터베이스는 네트워크 구성요소로 들어오는 각 포워딩 동치 클래스(FEC)를 어디로 포워딩할지를 나타냄 -; 토폴로지 데이터베이스와 레이블 정보 데이터베이스에 연결된 컨트롤 프로세서를 포함하고, 네트워크 프로세서는 데이터 트래픽을 프로세싱하도록 구성되고, 네트워크 프로세서는: 레이블 스위치 경로(LSP)들을 통하여 데이터 트래픽을 포워딩하도록 구성된 MPLS 관리 모듈; MPLS 네트워크에 LSP를 설정하도록 구성된 레이블 분배 프로토콜(LDP) 모듈; 토폴로지 데이터베이스 상에서 최단 경로 탐색 알고리즘을 실행함으로써 MPLS 네트워크 내의 각 MPLS 노드 쌍 간의 적어도 하나의 최단 경로를 결정하도록 구성된 최단 경로 탐색 모듈 - 최단 경로 탐색 모듈은, 복수의 동일 비용 최단 경로를 갖는 각 MPLS 노드 쌍들을 위하여 동일 비용 최단 경로들을 부하 분산 모듈로 송신하도록 구성됨 -; 복수의 동일 비용 최단 경로들 내의 각 경로와 관련된 링크 사용률 값들로부터 도출된 경로 사용률 값에 기초하여, 복수의 동일 비용 최단 경로 각각을 순위화하도록 구성된 정렬 모듈; 및 수신된 복수의 동일 비용 최단 경로로부터, MPLS 노드 쌍 간에 데이터 트래픽 부하를 공유하기 위하여 이용되는, 그 MPLS 노드 쌍을 위한 복수의 동일 비용 최단 경로의 제1 서브셋을 선택하고, 경로 사용률 값에 기초하여 이더넷 브리지 쌍에 대한 제1 서브셋과 데이터 트래픽 부하를 공유하기 위하여 이용되는, 그 MPLS 노드 쌍을 위한 복수의 동일 비용 최단 경로로부터의 제2 서브셋을 선택하도록 구성된 부하 분산 모듈을 포함하며, 이에 의해서 경로 사용률 값을 고려한 제2 서브셋의 선택은 MPLS 네트워크 전체에 걸친 부하 분산의 표준 편차를 최소화한다.

본 발명은 동일한 참조 부호들이 유사한 요소들을 가리키는 첨부 도면들 내에서 제한의 방법이 아닌 예시로서 도시되었다. 본 명세서의 "하나의" 또는 "일" 실시예에 대한 상이한 참조들은 반드시 동일한 실시예에 대한 것은 아니며, 이러한 참조들은 적어도 하나를 의미한다. 또한, 특정한 특징, 구조 또는 특성이 실시예와 관련하여 설명된 경우, 명시적으로 설명되었는지 여부와 상관없이 이러한 특징, 구조 또는 특성을 다른 실시예들과 관련하여 실시하는 것은 당업자의 지식 내에 있다.
도 1은 네트워크 토폴로지의 예의 도면이다.
도 2는 멀티-프로토콜 레이블 스위칭 네트워크(MPLS)에 대한 자동화 트래픽 엔지니어링을 구현하는 네트워크 구성요소의 일 실시예의 도면이다.
도 3은 타이-브레이킹 메커니즘으로의 피드백으로서 링크 사용률의 이용을 통합한 자동화된 트래픽 엔지니어링을 포함하는 부하 분산 프로세스의 일 실시예의 흐름도이다.
도 4는 레이블 분배 프로토콜의 일부로서 레이블 매핑 메시지를 생성하기 위한 프로세스의 일 실시예의 순서도이다.
도 5는 다중점-대-다중점 네트워크 토폴로지의 예의 도면이다.
도 6은 다중점-대-다중점 네트워크 토폴로지의 다른 예의 도면이다.
도 7은 MPLS 네트워크 내의 운용, 관리 및 유지보수(OAM)를 지원하기 위하여 의사 와이어(pseudo wire)들의 집합을 기저의 패킷 스위치 네트워크에 매핑하는 일 실시예의 도면이다.

이하의 설명에서, 다수의 특정한 상세들이 명시되었다. 그러나, 본 발명의 실시예들은 이러한 특정한 상세들이 없이 실시될 수 있을 것으로 이해된다. 경우에 따라, 잘 알려진 회로, 구조 및 기술들은 본 명세서의 이해를 불명료하게 하지 않도록 상세히 나타내지 않았다. 그러나, 당업자는 본 발명이 이러한 특정한 상세들 없이도 실시될 수 있음을 알 것이다. 당업계에서 통상의 지식을 가진 자는, 포함된 설명으로 과도한 실험 없이 적당한 기능을 구현할 수 있을 것이다.

실시예들은, 프로세스가 언제나 단일 경로로 귀착하고, 계산의 순서 또는 방향에 독립적이고, 전체 경로를 고려할 필요없이 고려된 경로의 임의 부분에 대한 타이가 해결될 수 있도록 국소성 속성을 갖는다는 속성들을 포함하는 특정 속성들을 갖는 기본 타이-브레이킹 프로세스를 포함한다.

흐름도의 동작이 도 2의 예시적인 실시예를 참조하여 설명될 것이다. 그러나, 흐름도의 동작들은 도 2를 참조하여 논의된 것들 이외의 본 발명의 실시예에 의하여 수행될 수 있으며, 도 2를 참조하여 논의된 실시예는 도 3 및 도 4의 흐름도를 참조하여 논의된 동작과 다른 동작들을 수행할 수 있음을 이해해야 한다. 도 1, 도 5-도 7은 도 2, 도 3 및 도 4의 원리와 구조의 구현을 보여주는 예시적인 토폴로지 및 시나리오들을 제공한다.

도면에 나타난 기술들은 하나 이상의 전자 디바이스(예컨대, 엔드 스테이션, 네트워크 구성요소 등) 상에서 저장되고 실행되는 코드 및 데이터를 이용하여 구현될 수 있다. 이러한 전자 디바이스들은, 비-일시적인(non-transitory) 기계 판독가능한 저장 매체 또는 컴퓨터 판독가능한 저장 매체(예컨대, 자기 디스크; 광 디스크; 랜덤 액세스 메모리; 읽기 전용 메모리; 플래시 메모리 디바이스; 및 상 변화 메모리)와 같은 비-일시적인 기계 판독가능한 매체 또는 컴퓨터 판독가능한 매체를 이용하여 코드 및 데이터를 저장하고 통신한다(내부적으로 및/또는 네트워크를 통해 다른 전자 디바이스들로). 또한, 이러한 전자 디바이스들은 일반적으로, 하나 이상의 저장 디바이스와 같은 하나 이상의 다른 구성요소에 연결된 하나 이상의 프로세서들의 집합, 사용자 입력/출력 디바이스(예컨대, 키보드, 터치 스크린, 및/또는 디스플레이), 및 네트워크 연결부를 포함한다. 프로세서 집합 및 다른 구성요소들을 연결하는 것은 일반적으로 하나 이상의 버스 및 브리지(버스 컨트롤러라고도 칭함)를 통한다. 저장 디바이스들은 하나 이상의 비-일시적인 기계 판독가능한 저장 매체 또는 컴퓨터 판독가능한 저장 매체, 및 비-일시적인 기계 판독가능한 통신 매체 또는 컴퓨터 판독가능한 통신 매체를 나타낸다. 따라서, 주어진 전자 디바이스의 저장 디바이스는 일반적으로 그 전자 디바이스의 하나 이상의 프로세서들의 집합 상에서의 실행을 위해 코드 및/또는 데이터를 저장한다. 물론, 본 발명의 실시예의 하나 이상의 부분은 소프트웨어, 펌웨어 및/또는 하드웨어의 서로 다른 조합들을 이용하여 구현될 수 있다.

본 명세서에서 이용될 때, 네트워크 구성요소(예컨대, 라우터, 스위치, 브리지 등)는, 하드웨어 및 소프트웨어를 포함하며 네트워크 상의 다른 장비(예컨대, 다른 네트워크 구성요소들, 엔드 스테이션 등)를 통신으로 상호 접속하는 네트워킹 장비의 일부분이다. 일부 네트워크 구성요소들은 다수의 네트워크 기능들(예컨대, 라우팅, 브리징, 스위칭, 레이어 2 집적, 세션 보더 컨트롤(session border control), 멀티캐스팅, 및/또는 가입자 관리)을 위한 지원을 제공하고, 및/또는 다수의 애플리케이션 서비스들(예컨대, 데이터, 음성, 및 비디오)을 위한 지원을 제공하는 "다중 서비스 네트워크 구성요소" 이다. 가입자 엔드 스테이션(예컨대, 서버, 워크스테이션, 랩탑, 팜 탑, 이동 전화, 스마트폰, 멀티미디어 폰, VOIP(Voice Over Internet Protocol) 폰, 휴대용 미디어 플레이어, GPS 유닛, 게이밍 시스템, 셋톱 박스(STB) 등)들은, 인터넷을 통해 제공되는 컨텐츠/서비스들 및/또는 인터넷 상에 오버레이된 가상 사설망(VPN) 상에 제공되는 컨텐츠/서비스들에 액세스한다. 컨텐츠 및/또는 서비스들은 일반적으로 서비스 또는 컨텐츠 제공자에 속하는 하나 이상의 엔드 스테이션(예컨대, 서버 엔드 스테이션), 또는 피어-투-피어 서비스에 참여하는 엔드 스테이션들에 의하여 제공되며, 공개 웹 페이지(무료 컨텐츠, 인터넷 상점, 검색 서비스 등), 사적인 웹 페이지(예컨대, 이메일 서비스를 제공하는, 사용자명/암호로 액세스되는 웹 페이지 등), VPN을 통한 회사 네트워크, IPTV 등을 포함할 수 있다. 일반적으로, 가입자 엔드 스테이션들은 에지 네트워크 구성요소들에 연결되는데(예컨대, (유선 또는 무선으로) 액세스 네트워크에 연결된 가입자 구내 장비를 통하여), 이 에지 네트워크 구성요소들은 다른 엔드 스테이션들(예컨대, 서버 엔드 스테이션들)에 연결된다(예컨대, 하나 이상의 코어 네트워크 구성요소를 통하여 다른 에지 네트워크 구성요소들로).

본 발명의 실시예들은 종래 기술의 단점들을 피하기 위한 시스템, 네트워크 및 방법을 제공하는데, 이 단점들은 비대칭 토폴로지 내의 낮은 성능, 운용, 관리 및 유지보수(OAM) 프로토콜의 지원 결핍, 패킷 단위 검사를 위한 높은 리소스의 요구, 적당한 네트워크 활용을 달성하기 위한 높은 수준의 확장, 다수의 메트릭 집합의 생성 및 유지, 및 상태에 있어서 작은 변화를 일으키는 데 필요한 상당한 리소스를 포함한다.

본 발명의 실시예들은 네트워크에 대한 토폴로지 데이터베이스의 횡단(traversal)의 수를 최소화하면서 동적 트래픽 엔지니어링을 가능하게 함으로써 이러한 단점들을 극복한다. 부하 분산 방법은 동적 트래픽 엔지니어링을 통합하고 포워딩 플레인 내의 복수의 동일 비용 경로들의 집합의 인스턴스화를 이용하는데, 이는 동일 비용 트리들의 집합들로 집적될 수 있으며, 이에 의해서 경로 생성 프로세스의 이전의 모든 반복으로부터 나온 경로 내의 각 링크를 통과하는 누적된 수의 최단 경로들은 경로들의 다음 집합의 생성을 위해 타이-브레이킹을 요인으로 포함한다. 노드가 타이-브레이킹 프로세스를 이용하여 최초 경로 선택을 수행하고 토폴로지 데이터베이스 내의 모든 노드 쌍들을 프로세싱하고 나면, 각 링크를 통과하는 최단 경로의 수가 결정되고 이를 링크 사용률 값이라고 칭한다. 추가 경로 집합을 생성하기 위한 이후의 데이터베이스 패스들 각각에 대하여, 임의의 두 개의 노드 쌍 간의 최단 경로들의 집합은, 고려 중인 각 경로 내의 각 링크에 대한 링크 사용률 값들의 사전적 순서로 분류된 리스트(lexicographically sorted list)를 순위화함으로써 정리된다(prune). 순위화된 리스트가 유일한 최저 활용 경로를 갖는다면, 그 경로가 선택된다. 순위화된 리스트가 유일한 최저 활용 경로를 갖지 않는다면, 최저 링크 사용률에 대하여 타이인 최단 경로들의 서브셋에 기본 타이-브레이킹 프로세스가 적용된다.

부하 분산 방법 및 시스템에서, 네트워크 내의 링크들의 부하를 균등하게 나누기 위해서 이전 반복들의 타이-브레이킹을 고려하여 경로 생성의 각 반복에서 네트워크 부하의 모델이 계산된다. 향상된 알고리즘은 제1 반복 이후의 각 반복들에 있어서 더 적은 부하의 링크의 선택을 본질적으로 선호한다.

부하 분산 프로세스는 임의의 두 지점 간의 경로에 대하여, 그 경로의 임의의 서브셋의 계산 방향, 계산 또는 검사 순서에 무관하게 단일의 대칭 경로로 귀착하도록 하는(즉, "최단 경로의 임의의 부분 역시 최단 경로이다"라고 기술되는 속성) 뚜렷한 속성들을 갖는 타이-브레이킹 프로세스를 이용한다. 또는 다르게 말하면, 최단 경로의 임의의 일부분을 따라 타이가 발생한 곳에서, 이러한 노드들은 동일한 선택으로 경로의 서브셋에 대한 타이를 해결할 것이며, 결과는 최소 비용 최단 경로 트리가 된다. 이것은 본 명세서에서 "일반 알고리즘 타이-브레이킹" 프로세스로 칭한다.

부하 분산 프로세스에서, 일반 알고리즘 타이-브레이킹 프로세스를 이용한 토폴로지 데이터베이스의 최초 패스(pass)는 트리의 제1 집합을 생성하게 한다. 이는 어떠한 링크에도 부하가 기록되어 있지 않기 때문이며, 따라서 동일 비용의 정의가 최저 메트릭과 최소 수의 홉인 경우에서 모든 동일 비용 경로들은 사용률에 대하여 타이가 될 것이다. 최초 단계는 네트워크 내의 각각의 MPLS 노드 쌍들 간의 최단 경로의 결정을 필요로 하고, 임의의 두 개의 MPLS 노드들 간에 둘 이상의 최단 경로가 발견된 경우 네트워크 내의 각각의 MPLS 노드 쌍들 간의 유일한 경로 선택을 생성하고, "ECT 집합"으로 지칭되는 동일 비용 포워딩 트리의 하나 이상의 집합의 생성하기 위해, 타이-브레이킹을 위하여 일반 알고리즘 타이-브레이킹 프로세스(common algorithm tie-breaking process)가 이용된다.

부하 분산 프로세스는 동일 비용 경로들을 순위화할 수 있고 낮은 순위의 경로와 높은 순위의 경로, 또는 '북엔드(bookend)' 경로를 결정할 수 있는데, 이 두 경로들은 필수 속성들의 집합을 나타낸다. 이에 의해서, 이러한 부하 분산 프로세스는 데이터베이스의 단일 "모든 쌍" 패스(single "all pairs" pass)로부터 둘 이상의 경로를 선택할 수 있다. 부하 분산 프로세스는 이전의 타이 브레이킹 절차에 의하여 실제로 선택된 경로들을 기초로 하여 각각의 링크를 횡단하는 최단 경로의 수도 계산한다. 이 값을 "링크 사용률" 값이라고 하며, 이것은 이후의 계산에서 이용될 수 있다. 링크 사용률 값은 링크를 통과(transit)하는 최단 경로들을 갖는 MPLS 노드 쌍들의 카운트일 수 있다. 다른 실시예들에서, 토폴로지 데이터베이스 내에서 추가적인 정보를 고려하여 링크 사용률 대신에 이용될 더욱 정교한 가능성들이 존재한다.

추가의 경로들 또는 트리들의 집합들을 생성하기 위한 후속의 데이터베이스 패스에서, 임의의 두 MPLS 노드 간의 최단 경로들의 집합은, 각 경로에 대하여 사전적 순서로 정렬된 링크 사용률 값 또는 단순하게는 경로 내의 각 링크들의 사용률의 총합을 포함할 수 있는 경로 사용률 값을 생성한 다음, 경로 사용률 값에 기초하여 결과 경로들을 순위화함으로써 먼저 순위화된다. 동일 비용 경로들 또는 트리들의 집합을 생성할 때 둘 이상의 경로를 선택하는 경우에는 동일한 경로가 선택되는 횟수를 최소화하는 것이 유리하기 때문에, 두 가지 이상의 순위화 방식들도 이용될 수 있다. 다양성을 보여주는 다수의 링크 순위화를 이용하면 다수의 경로들을 선택하는 데 필요한 반복 횟수를 최소화할 수 있다. 순위화 프로세스가 최소 활용된 하나의 경로를 생성할 때에는, 그 경로가 추가 프로세싱 없이 선택될 수 있다. 둘 이상의 순위(예컨대, 최저 순위 및 최고 순위)가 고려될 때, 최소 활용된 경로가 최저 순위 경로 및 최고 순위 경로로서 선택된다. 둘 이상의 동일한 최소 활용된 경로가 있을 때, 선택을 위해, 최소 활용된 경로들의 집합에 일반 알고리즘 타이-브레이킹 프로세스가 적용된다. 일 실시예에서, 이 단계로부터 둘 이상의 순위가 선택될 수 있다. 둘 이상의 부하 순위화 메커니즘이 이용되는 경우(예컨대, 부하의 총합 및 부하의 사전적 순서 정렬이 순위로서 이용되는 경우), 타이가 발생했을 때 각각으로부터 다수의 순위를 추출하는 것이 더욱 가능하다.

토폴로지 데이터베이스를 통한 추가적인 패스 또는 반복들이 수행될 수 있으며, 각 반복에서 경로 내의 각 링크에 할당된 링크 사용률 값은, 토폴로지 데이터베이스를 통한 이전의 모든 패스 동안 선택된 링크를 통과하는 최단 경로들의 누적 측정 또는 표시이다.

도 1은 예시적인 네트워크 토폴로지의 일 실시예의 도면이다. 예시적인 네트워크 토폴로지는 대응하는 노드 식별자 1 내지 6을 갖는 여섯 개의 노드를 포함한다. 네트워크 토폴로지에 대한 경로 쌍들은 아무 것도 결정되지 않았다. 노드 식별자들을 이용하여 경로를 사전적 순서로 순위화하는 예시적인 일반 알고리즘 타이-브레이킹 프로세스가 이용된다. 노드 1과 노드 4 간의 동일 비용의 경로들의 집합을 검사하면, 이하의 순위화된 경로 식별자들의 집합이 생성될 것이다(노드 식별자들이 통과 리스트로서 나타나지 않도록 경로 식별자들은 사전적 순서로 정렬되었음을 유념한다):

1-2-3-4

1-2-4-6

1-3-4-5

1-4-5-6

이러한 타이-브레이킹 프로세스의 최초 적용은 1-2-3-4와 1-4-5-6을 이 노드들 간의 낮은 순위 경로 및 높은 순위 경로로서 선택할 것이다. 본 예에서 간단히 하기 위해, 네트워크에 대한 경로 카운트를 결정하는 데에 있어서 여섯 개 노드 모두로부터의 최단 경로 트리가 아니라, 노드 1과 노드 4의 쌍만이 고려된다. 이 예에서, 선택된 링크 경로 내의 링크들은 각각 경로 쌍 카운트 1을 할당받는다. 부하 분산 프로세스는 토폴로지 데이터베이스를 통한 다음 패스를 위하여, 이하와 같이 각 경로 ID와 관련된 링크 부하의 사전적 순서 정렬을 산출할 것이다.

경로 1-2-4-6에 대한 부하 0,1,1

경로 1-3-4-5에 대한 부하 0,1,1

경로 1-2-3-4에 대한 부하 1,1,1

경로 1-4-5-6에 대한 부하 1,1,1

링크 부하들의 사전적 순서 정렬은 경로 1-2-4-6과 경로 1-3-4-5가 각각 0-1-1로써 타이로 되게 할 것이다. 유사하게 링크 부하들의 총합이 산출될 것이다:

경로 1-2-4-6에 대한 부하 2

경로 1-3-4-5에 대한 부하 2

경로 1-2-3-4에 대한 부하 3

경로 1-4-5-6에 대한 부하 3

양쪽 모두의 순위화 방식에 대한 결과로서, 사전적 순서로 정렬된 경로 ID들의 이차적인 타이브레이커(secondary tiebreaker)가 이용된다. 양쪽 모두의 경우에서 이 이차적인 타이브레이커로부터 낮은 경로(1-2-4-6)가 선택된다. 유사하게 최저 부하 경로들의 집합의 높은 순위 경로 ID로서 1-3-4-5가 선택될 수 있다. 일 실시예에서, 낮음-높음 선택이 이용되는 경우, 두 개의 경로들이 선택된다. 이 경로들은 동일하거나 상당한 오버랩을 가질 수 있다. 예를 들면, 경로 1-3-4-5가 상기의 순위화된 리스트에 존재하지 않는다면, 경로 1-2-4-6이 최저 비용의 낮은 순위 경로 및 높은 순위 경로 양쪽 모두로서의 자격을 얻을 것이다. 다른 실시예들에서, 낮은 경로 선택으로의 최초 입력은 부하들의 사전적 순서 분류에 기초한 순위로부터 온 것일 수 있으며, 높은 경로 선택으로의 최초 입력은 부하들의 총합에 기초한 순위로부터 온 것일 수 있다.

본 예가 단지 하나의 경로 쌍을 검사하는 것으로부터 링크 사용률을 고려하는 반면에, 당업자는 데이터베이스의 단일 패스 이후에 잠재적인 트래픽 분산의 포괄적인 조망이 존재한다는 것과, 이후의 패스들의 타이-브레이킹은 본질적으로 최대(maxima)를 피하므로 부하가 네트워크에 걸쳐 더욱 균등하게 분산된다는 것을 이해할 것이다. 부하 분산의 수정의 정도는 효과가 누적될 것으로 생각되는 각각의 새로운 경로들의 집합에 비례하여 감소한다.

프로세스의 반복마다 선택되는 경로들의 수 및 네트워크가 활용하도록 구성된 경로들의 누적 수는 요구되는 처리 능력 분석에 대한 선험적(priori) 포워딩 상태의 함수일 수 있다. 최저 비용의 최저 순위 경로와 최고 순위 경로 모두를 선택하면 링크 사용률의 표준 편차의 주어진 개선을 위해 필요한 계산 능력의 양이 최소화될 것이지만, 반복마다 두 세트의 동일 비용 트리가 생성되기 때문에 결과적으로 더 많은 포워딩 상태가 필요할 것이다. 각각의 반복으로부터 단일 경로 순열을 선택하면 처리 능력이 더욱 필요할 것이지만, 하나의 최저 사용률 후보로부터 두 개의 경로가 선택되어야 하는 횟수가 최소화되기 때문에, 사용률의 표준 편차의 주어진 감소를 위해 필요한 포워딩 데이터베이스 상태의 양이 감소될 것이다. 생성되는 경로들의 전체 수는, 네트워크 구성요소의 상태, 및 네트워크 효율성에 대하여 균형이 맞추어지는 처리 능력 고려 사항들 양쪽 모두의 조합에 기초하여 결정된다. 경로 부하의 순위화를 위한 다수의 방식들의 활용은 주어진 수의 경로 선택에 대하여 동일한 경로가 두 번 이상 선택되는 확률을 감소시키므로, 데이터베이스의 주어진 패스로부터 더 많은 경로들이 선택되는 것을 허용한다. 상기 예들에서, 네트워크에 걸쳐 적용되는 일관성 있는 결과들을 생성할 두 가지의 경로 부하 순위화 방법이 설명되었다. 다른 실시예들에서, 추가의 또는 대안적인 순위화 방법이 이용될 수 있다. 예를 들면, 국소성(locality) 속성(일반 알고리즘 타이-브레이킹 프로세스와 결합된 때 최저 부하 경로의 임의의 일부분도 최저 부하 경로임)도 갖는 다른 부하 순위화 메커니즘들 및 이러한 순위화의 조합들이 활용될 수 있다.

또한, 상기의 예에서, 링크 사용률은 링크를 통과하는 최단 경로들의 카운트로서 나타내어진다. 더 상세하고 정확도가 증가한 링크 사용률을 나타내기 위하여 많은 변화들을 이용할 수 있다. 레이블 정보 및 토폴로지 데이터베이스 내에는, 네트워크 내의 각 노드가 특정한 최단 경로를 이용하는 서비스 인스턴스들의 수를 결정할 수 있도록 하는 충분한 정보가 있다. 링크 사용률 값은 대응하는 링크에 적절하게 가중치를 부여하기 위해서 이 사용률에 기초하여 결정될 수 있다. 레이블 정보 또는 토폴로지 데이터베이스에 의하여 저장되는 데이터를 증가시킴으로써, 서비스마다의 추가 대역폭 프로파일링 정보가 부하 분산 계산에서 이용가능하게 된다. 다른 실시예에서, 경로 내의 링크들의 집합의 최소 링크 메트릭들만이 그 노드들의 쌍 간에 제공될 수 있는 최대 부하의 대표로서 활용된다. 다른 실시예들에서, 유사한 메트릭들 또는 더욱 상세한 메트릭들이 활용될 수 있다.

일 실시예에서, 토폴로지 데이터베이스의 마지막 패스를 제외한 모든 패스들은 네트워크 내의 모든 노드 쌍들 간의 최단 경로들의 "모든 쌍" 계산을 포함한다. 이는 복잡성으로 인하여 계산적으로 비용이 많이 들 수 있다. 그러나, 부하 분산 프로세스는 눈에 띄는 이득을 산출하기 위하여 토폴로지 데이터베이스를 통하는 많은 수의 패스를 필요로 하지 않으며, 그 결과로 부하 분산 프로세스는 네트워크 리소스 할당에 있어서 이 "모든 쌍" 계산을 정당화하는 가치있는 전체적인 개선을 제공한다.

랜덤 그래프 생성을 이용하는 실험 예에서, 최초 ECT 집합을 설정한 후에 데이터베이스를 통하는 단일 패스들은, 네트워크 내의 각각의 링크를 통과하는 최단 경로들의 카운트로서 측정되는 링크 부하의 변화의 계수에 있어서 대략 평균 45%의 감소를 가져온다. 토폴로지 데이터베이스를 통하는 추가적인 3회의 패스는 평균 75% 감소된 지점까지 변화의 계수를 계속해서 감소시키지만, 이득의 대부분은 베이스라인을 설정한 이후의 제1 패스에서 일어난다. 따라서, 부하 분산에 있어서 이득의 대부분은 데이터베이스의 처음 2회의 패스에서 발생한다. 제2 집합이 제1 집합의 부하를 피하기 위하여 명시적으로 배치되었을 때, 네트워크를 통한 경로들의 수는 두 배가 된다. 그러나, 변동성의 계수의 개선의 비율은 누적 경로 카운트가 피상적으로 제안할 수 있는 1/2, 1/3, 1/4의 비율보다 더욱 빠르게 패스마다 줄어든다. 따라서, 부하 분산 프로세스를 계산 및 포워딩 상태 둘 다의 관점에서 다루기 쉽게 유지하면서 의미 있는 결과가 달성될 수 있다.

방법이 효과적으로 접속 지향적이고 최소 부하 링크들을 찾기 때문에, 실패에 의해서 발생하는 트래픽 매트릭스의 모든 섭동은 사실상 고립되거나 국소적인 경향이 있다. 부하 분산 프로세스는 일단 네트워크 내의 수축(constriction)을 우회하고 나면, 데이터 트래픽을 원래의 분산으로 돌아가게 조종하는 경향이 있을 것이다. 방법은 운용, 관리 및 유지보수(OAM: operation, administration and management) 프로토콜이 변경되지 않고 활용될 수 있도록, 최근 만들어진 MPLS-TP 기술 기반으로도 작동하며, 그 기법은 MPLS 네트워크의 아키텍처 및 서비스 보증을 보존한다.

또한 부하 분산 프로세스 및 시스템은, 관리자가 소정의 부하를 특정 링크로부터 멀어지게 이동시키는 효과를 가질 부하 인자로 링크를 "프리-바이어스(pre-bias)"할 수 있게 한다. 이는 라우팅 거동을 조작하는 데에 있어서의 단순 메트릭 변경보다 더 미묘한 그라데이션, 및 멀티 토폴로지 라우팅보다 더 단순한 관리를 허용하며, 선험적 부하 균등화 시스템에서 행해지는, 메시 밀도(mesh density)를 인위적으로 조종하기 위한 링크 가상화(예를 들어, RFC 4206에 따른 MPLS "포워딩 인접")를 불필요하게 한다. 2단계의 정렬을 위하여, 링크 바이어스가 적용되는 타이밍이 문제된다. 이는 일반적으로 제2 반복 및 그 이후의 반복들을 위하여만 고려된다. 제1 반복에서 모든 동일 비용 경로들이 활용률에 관하여 타이가 되는(제로) 구현에서, 바이어스 인자를 즉시 적용하는 것은 모든 부하를 바이어스를 갖는 그 링크들로부터 멀어지게, 제1 반복으로부터 기인한 다른 경로들을 향해 이동시키는 경향이 있다.

도 2는 타이-브레이킹 메커니즘으로의 피드백으로서 링크 사용률을 이용하는 부하 균등화 방법을 구현하는 네트워크 구성요소의 일 실시예의 도면이다. 네트워크 구성요소(200)는 레이블 정보 데이터베이스(215), 토폴로지 데이터베이스(217), 진입 모듈(203), 출구 모듈(205), 및 컨트롤 프로세서(207)를 포함할 수 있다. 진입 모듈(203)은 물리 링크 레벨 및 데이터 링크 레벨에서 네트워크 구성요소(200)에 의하여 수신되는 데이터 패킷의 프로세싱을 다룰 수 있다. 출구 모듈(205)은 물리 링크 레벨 및 데이터 링크 레벨에서 네트워크 구성요소(200)에 의하여 송신되는 데이터 패킷의 프로세싱을 다룬다. 컨트롤 프로세서(207)는 데이터 트래픽의 라우팅, 포워딩 및 더 높은 레벨의 프로세싱을 다룬다. 컨트롤 프로세서(207)는 최단 경로 탐색 모듈(209), 부하 분산 모듈(215), 레이블 분배 프로토콜(LDP) 모듈(213), MPLS 관리 모듈(217) 및 정렬 모듈(211)을 실행하거나 포함할 수 있다.

레이블 정보 데이터베이스(215)는 데이터 패킷이 포워딩될 방식을 정의한 레이블 포워딩 엔트리들을 갖는 테이블을 포함한다. 레이블 포워딩 엔트리는 레이블 및 기저 FEC 및 가상 토폴로지를 네트워크 구성요소(200)의 네트워크 인터페이스에 결부시킨다. 이 정보는 데이터 패킷이 어떻게 다루어질 것인지, 즉 데이터 패킷이 어느 네트워크 인터페이스에 포워딩되어야 하는지를 결정하기 위하여 컨트롤 프로세서(207)에 의해서 이용될 수 있다. 부하 분산 방법 및 시스템은 본 명세서에서 이하에 설명된 바와 같은 부하 분산을 구현하는 부하 분산 프로토콜(LDP)을 통해 레이블 포워딩 엔트리를 생성한다.

토폴로지 데이터베이스(217)는 네트워크 구성요소(200)가 접속된 네트워크의 토폴로지의 네트워크 모델 또는 유사한 표현을 저장한다. 일 실시예에서, 네트워크 내의 노드들은 각각의 레이블 스위치 라우터(LSR)들이고, LSR들 간의 링크들은 다수의 기저 프로토콜 및 기술을 이용할 수 있다. 노드들은 노드 루프백 주소와 같은 고유한 노드 식별자에 의하여 식별될 수 있으며, 링크들은 노드-식별자 쌍들에 의하여 식별될 수 있다. 당업자는, 이 네트워크 모델 표현이 예시로서 제공된 것이며, 네트워크 토폴로지의 다른 표현들이 부하 분산 방법 및 시스템과 함께 이용될 수 있음을 이해할 수 있을 것이다.

최단 경로 탐색 모듈(209)은 컨트롤 프로세서(207)의 구성요소이거나 컨트롤 프로세서(207)에 의해서 실행되는 모듈이다. 최단 경로 탐색 모듈(209)은 네트워크 토폴로지 내의 임의의 두 노드들 간의 최단 경로를 결정하기 위하여 토폴로지 데이터베이스를 횡단한다. 만약 네트워크 내의 두 노드들 간에 동일 거리 또는 동일 비용을 갖는 복수의 경로들이 있고 이 복수의 경로들이 모두 최단 경로라면, 이 복수의 동일 비용 경로들은 어느 것을 이용할지를 결정하기 위하여 정렬 모듈(211) 및 부하 분산 모듈(215)로 제공될 수 있다. 최단 경로 탐색 모듈(209)은 네트워크 토폴로지 내의 모든 노드들 간의 최단 경로를 결정할 수 있으며, 이는 본 명세서에서 "모든 쌍" 계산으로 칭한다.

최단 경로 탐색 모듈(209)은 각각의 노드 쌍에 대한 최단 경로들의 집합을 제공하고, 부하 분산 모듈(215)은 최단 경로들의 서브셋을 선택하고, 네트워크 요소(200)를 횡단하는 각각의 최단 경로들의 서브셋을 구현하는 엔트리를 포함하도록 레이블 정보 데이터베이스를 업데이트한다.

제1 패스 이후에, 최단 경로 탐색 모듈(209)은 토폴로지 데이터베이스를 통하는 제1 패스로부터 기인한 네트워크 토폴로지 내의 각각의 링크의 링크 사용률 값을 계산한다. 링크 사용률 값은 주어진 링크를 횡단하는 선택된 최단 경로들의 수의 카운트이다. 각 링크에 대하여 별도의 링크 사용률이 계산되고 기록된다. 이 링크 사용률 값들은 경로 사용률 값을 생성하기 위하여 이용되고, 그것은 결국 토폴로지 데이터베이스를 통하는 이후의 패스들에 대한 경로들의 순위를 바이어스하기 위하여 이용되는데, 여기에서 최초의 타이브레이커는 사전적 순서로 정렬된 링크 사용률 값들의 순위화된 리스트 또는 링크 사용률 값들의 총합(즉, 경로 사용률 값의 형태)이며, 이것이 타이가 되면 일반 알고리즘 타이-브레이킹 프로세스가 이후의 타이 브레이커로서 이용된다.

정렬 모듈(211)은 컨트롤 프로세서(207)의 구성요소이거나 컨트롤 프로세서(207)에 의하여 실행되는 모듈이다. 정렬 모듈(211)은 제2 패스 및 이후의 패스들의 경로 사용률 값에 기초한 동일 비용 트리들의 부하 집합의 최초 순위화를 수행함으로써 부하 분산 모듈(215)을 지원한다.

복수의 동일 비용 경로들을 갖는 각 노드 쌍들을 위하여, 정렬 모듈(211)은 경로 사용률 값들에 기초하여 이 동일 비용 경로들 각각의 순위를 생성하고, 부하 분산 모듈(215)은 이 순위로부터 적어도 하나의 경로를 선택한다. 다른 실시예들에서, 대응되는 노드 쌍들 간의 부하를 나누기 위하여 최고 순위 경로 및 최저 순위 경로가 선택될 수 있다. 부하 분산 모듈(215)은 컨트롤 프로세서(207)의 구성요소이거나 컨트롤 프로세서(207)에 의해서 실행되는 모듈이다.

이 프로세스는 링크 사용률 값이 그것을 통과하는 최단 경로들의 집합의 누적 표시가 되도록 업데이트되는 임의의 수의 패스 또는 반복을 통하여 반복될 수 있다. 경로 사용률 값들은 링크 사용률에 대한 변경과 함께 업데이트될 수도 있다. 경로 내의 변화의 표준 편차는 일반적으로 각각의 반복에 따라 감소되지만, 경로 집합들의 수가 커지면서 각각의 추가 집합의 전체적인 영향은 비례하여 감소되며, 이는 둘 또는 셋을 초과하는 패스 또는 반복의 이용은 생성을 위한 계산적 노력 또는 인스턴스화(instantiate)하는 포워딩 상태 모두에 가치가 없다는 것을 나타낸다. 패스 또는 반복의 수는 관리자에 의해서 지정되며 네트워크 전체로 구성된다.

MPLS 관리 모듈(217)은 컨트롤 프로세서(207)의 구성요소이거나 네트워크 프로세서(207)에 의해서 실행되는 모듈이다. MPLS 관리 모듈(217)은 인입 패킷을 검사하고, 관련된 레이블을 결정하고, 패킷을 포워딩할 때 통할 네트워크 인터페이스를 결정하기 위하여 레이블 정보 데이터베이스(219) 내에서 패킷에 대한 룩업(look-up)을 수행한다. MPLS 관리 모듈(217)은 각 데이터 패킷에 대한 LSP의 적절한 횡단에 영향을 주기 위해서 필요한 임의의 레이블 스와핑, 레이블 추가 또는 레이블 제거도 수행한다.

LDP 모듈(213)은 컨트롤 프로세서(207)의 구성요소이거나 컨트롤 프로세서(207)에 의해서 실행되는 모듈이다. LDP 모듈(213)은, 네트워크의 부하를 분산하도록 활용되는 LSP들을 생성하기 위하여 이용되는 네트워크 내의 레이블 바인딩에 포워딩 동치 클래스(FEC) 및 가상 토폴로지를 설정하는 데 필요한 메시지를 생성한다. LDP 모듈(213)은 가상 토폴로지 타입-길이-값(TLV) 필드 뿐만 아니라 FEC TLV 필드, 레이블 TLV 필드를 포함하는 레이블 매핑 메시지를 생성한다. 토폴로지 TLV 필드는, 레이블 및 FEC가 부하 분산 프로세스의 어느 반복과 연관되는지를 표시하는 토폴로지 인덱스를 포함한다. LDP 모듈(213)은 레이블 분배를 구현하기 위한 기존의 다른 기능들도 수행한다.

도 3은 동일 비용 경로들을 위한 타이-브레이킹 메커니즘으로의 피드백으로서의 링크 사용률의 이용에 기초한 멀티-프로토콜 레이블 스위칭에 대한 자동화된 트래픽 엔지니어링을 지원하는 부하 분산을 위한 프로세스의 일 실시예의 순서도이다. 일 실시예에서, 프로세스는 링크 스위치 라우터와 같은 네트워크 구성요소의 개시 시에, 정의된 간격으로 또는 유사한 이벤트 또는 시간에서 브리지에 접속되는 네트워크에 토폴로지 변화를 통지할 때 실행될 수 있다. 토폴로지 데이터베이스는 네트워크 내의 각각의 네트워크 구성요소에서 부하 분산 프로세스로부터 개별적인 프로세스로서 유지되며, 네트워크의 진정한 토폴로지의 현재의 표현인 것으로 추정된다.

일 실시예에서, 부하 분산 프로세스는 네트워크 내의 네트워크 구성요소 또는 MPLS 노드(예를 들어, SLR)와 네트워크 내의 다른 네트워크 구성요소 또는 MPLS 노드 간의 최단 경로들의 집합을 결정함으로써 시작한다(블록 301). 최단 경로들의 집합은 개별적 경로들 또는 각각의 네트워크 구성요소를 각각의 개별 트리의 루트로서 갖는 트리들의 집합으로 이해된다. 복수의 최단 경로들이 있는지, 즉, MPLS 노드들 간에 최단 경로에 대하여 타이가 있는지 여부를 결정하기 위하여 확인이 이루어진다(블록 303). MPLS 노드 쌍이 그들 간에 단일 최단 경로를 갖는다면, 레이블 정보 데이터베이스는 그 최단 경로를 반영하기 위하여 업데이트된다(블록 306). 일 실시예에서, 레이블 정보 데이터베이스는 그것을 유지하는 네트워크 구성요소를 횡단하는 각각의 경로들을 반영하기 위하여 업데이트된다. 네트워크 내의 각 네트워크 구성요소가 이 동일한 계산을 수행한다. 부하 분산 프로세스는 결정론적이며 따라서 각 네트워크 구성요소는 동일한 결과를 계산할 것이다. 단일 최단 경로를 갖는 MPLS 노드 쌍들에 대한 추가의 프로세싱은 토폴로지의 변화가 있지 않는 한 불필요하다.

MPLS 노드 쌍이, 일반적으로 최소 수의 홉 및 최저 비용으로서 측정되는 유일한 최단 경로를 갖지 않는다면, 유일한 최단 경로 또는 최단 경로들의 집합이 선택되는 것이 허용되도록 일반 알고리즘 타이-브레이킹 프로세스가 이용된다(블록 305). 일 실시예에서, 제1 순위 경로 및 마지막 순위 경로를 선택하는 것이 가능하다. 경로들이 선택된 후에, 모든 MPLS 노드 쌍들이 선택된 쌍들 간에 적어도 하나의 경로를 갖도록, 경로들은 레이블 정보 데이터베이스에 저장되거나 레이블 정보 데이터베이스를 업데이트하기 위하여 이용된다.

최단 경로가 선택된 후에, 모든 MPLS 노드 쌍들이 선택된 경로를 가졌는지 여부를 결정하기 위하여 확인이 이루어진다(블록 307). 추가 MPLS 노드 쌍들이 선택된 경로 또는 경로들의 집합을 갖지 않는다면, 프로세스는 프로세싱할 다음 MPLS 노드 쌍을 선택함으로써 계속된다(블록 309). 모든 MPLS 노드 쌍들이 선택된 최단 경로를 가졌다면 프로세스는 제2 패스 또는 제2 반복으로 계속된다.

각 링크에 대한 링크 사용률 값은 모든 MPLS 노드 쌍들에 대한 포워딩 데이터베이스의 업데이트의 결과로서 계산되거나, 모든 이더넷 브리지 쌍들에 대한 포워딩 데이터베이스의 업데이트가 완료된 후에 계산된다(블록 310). 링크 사용률 값은 네트워크의 토폴로지 내의 대응하는 각 링크를 횡단하는 경로들의 수의 카운트이다. 링크 사용률 값은 네트워크 내의 각 링크에 대하여 계산된다. 링크 사용률 값은 이용 레벨, 및 추가 경로들이 형성되면 방지되어야 하는 네트워크 내의 잠재적인 병목현상의 표시를 제공한다.

이후의 최단 경로들의 생성을 위하여, 사전적 순서로 정렬된 리스트(경로 사용률 값들이 링크 사용률 값들을 포함함)로서의 경로 사용률 값, 또는 링크 사용률 값들의 총합으로서의 경로 사용률 값을 생성함으로써 타이-브레이킹이 처음으로 수행된다. 모든 노드 프로세스는 MPLS 노드 쌍을 선택하고 MPLS 노드 쌍 간의 최단 경로들의 집합을 결정함으로써 다시 시작한다(블록 311). 이 프로세스는 각 경로에 대응하는 링크 사용률 값에 기초한 경로 사용률 값을 포함한다(블록 313). 경로 사용률 값들은, 링크 사용률 값들의 총합과 같은 각 경로의 전체 부하를 표시할 수 있거나, 각 경로의 최대 부하 링크 또는 최소 부하 링크를 강조한 링크 사용률 값들의 사전적 순서로 정렬된 배열, 또는 유사한 배열 및 표현일 수 있다. 최단 경로들은 그들의 경로 사용률 값에 의하여 순위화된다(블록 315). 동일한 경로 사용률 값을 갖는 주어진 MPLS 노드 쌍에 대하여 둘 이상의 최단 경로가 있는지 여부를 결정하기 위하여 확인이 이루어진다(블록 317).

유일한 최저 부하 경로가 존재할 경우 그것은 모든 경로 순위에 대하여 추가 프로세싱 없이 선택될 수 있다(예컨대, 최저 및 최고). 동일한 부하의 최단 경로가 둘 이상 있는 경우(즉, 동일한 경로 사용률 값), 최단 경로들의 최저 부하 집합의 이 서브셋 내에서 경로 선택을 수행하기 위하여 일반 알고리즘 타이-브레이킹 프로세스가 이용된다(블록 321). 순위화는 최저 또는 최소 사용 링크들을 갖는 경로들이 선택될 가능성이 높도록 링크 사용률 값을 고려하는데, 이것은 네트워크 내의 다음 홉뿐만 아니라 네트워크의 전체 부하를 고려하고, 결과적으로 네트워크 전체의 라우팅이 더욱 균등화된다. 그러면 레이블 정보 데이터베이스는 선택된 경로들을 반영하도록 업데이트된다(블록 318).

다음으로, 모든 MPLS 노드 쌍들이 선택된 최단 경로 또는 최단 경로들의 집합을 갖는지 여부를 결정하기 위하여 확인이 이루어진다(블록 319). 그렇지 않다면, 프로세싱할 다음 MPLS 노드 쌍을 선택함으로써 프로세스는 계속된다(블록 323). 모든 MPLS 노드 쌍들이 계산되면, 추가 경로가 필요한지 여부를 결정하기 위하여 확인이 이루어진다(블록 325). 추가 경로가 필요하지 않은 경우(이것은 네트워크 관리자에 의해 설정되거나 유사하게 결정된 파라미터일 수 있음), 부하 분산 프로세스는 종료된다. 추가 경로가 필요한 경우, 프로세스는 제2 패스 또는 제2 반복과 유사하지만 이전 반복들에서 결정된 링크 사용률을 기반으로 하는 제3 패스 또는 제3 반복으로 계속된다. 이 프로세스는 임의의 수의 반복을 가질 수 있다.

도 4는 레이블 분배 프로토콜의 일부로서 레이블 매핑 메시지를 생성하기 위한 프로세스의 일 실시예의 순서도이다. 일 실시예에서, 토폴로지 내의 변경 또는 네트워크에 대한 레이블 정보 데이터베이스에 대한 변경에 대응하여 프로세스가 개시된다. 다른 실시예에서, MPLS 네트워크의 상태를 유지하기 위해서 프로세스가 주기적으로 개시된다. 프로세스는 각각의 노드가 그것의 피어들 중 하나로 보내질 레이블 매핑 메시지를 생성하는 것에 의해서 개시된다(블록 401).

레이블 매핑 메시지는 다수의 타입-길이-값(TLV) 필드를 포함한다. 개별 레이블 매핑 메시지는 호스트 노드의 레이블 정보 베이스에 표현된 대로 각 포워딩 동치 클래스(FEC) 및 네트워크의 토폴로지 내의 각 토폴로지 경로 또는 트리에 대하여 생성된다. 각 레이블 매핑 메시지에 대하여, 대응하는 필드 동치 클래스가 레이블 매핑 메시지의 FEC TLV 필드에 정의된다(블록 403).

경로 내의 각 인터페이스에 대한 LSP에 할당된 레이블에 따라 각 레이블 매핑 메시지의 레이블 TLV 필드도 정의된다(블록 405). 레이블 매핑 메시지에 토폴로지 인덱스도 정의된다(블록 407). 토폴로지 인덱스는 레이블 매핑 메시지에 의해서 정의된 LSP의 선택 프로세스의 반복을 표시한다. 예를 들어, 레이블 매핑 메시지가 선택된 제1 트리 또는 경로와 대응하는 경우, 0 또는 1의 토폴로지 인덱스가 선택될 수 있고 레이블 매핑 메시지에 삽입될 수 있다. 마찬가지로, 제2 경로 또는 트리가 메시지와 대응하는 경우 값으로서 1 또는 2가 지정될 수 있다. 각 레이블 매핑 메시지가 정의되고 그것의 각 값들이 지정되고 나면, 레이블 매핑 메시지는 각 레이블 분배 프로토콜 피어들로 송신될 수 있다(블록 409). 일 실시예에서, 토폴로지 인덱스는 레이블 매핑 메시지의 기존의 TLV에 포함된다. 다른 실시예에서, 레이블 매핑 메시지를 위하여 토폴로지 TLV가 정의된다.

도 5는 레이블 스위치 라우터(LSR) 1-18의 집합을 포함하는 다중점-대-다중점 네트워크의 일 실시예의 도면이다. 도면은 주어진 예에 대하여 상기 정의된 프로세스의 제1 반복에 의하여 정의된 경로들의 집합 또는 트리들의 집합을 나타낸다. 도면은 이 네트워크로의 진입은 노드 1 내지 노드 4로 분배될 수 있고 마찬가지로 노드 13 내지 노드 18로 분배될 수 있음을 가정하며, 즉 이 LSR들은 네트워크의 에지에 있지만 동일한 외부 인터페이스를 갖는다. 이 예에서, 제1 패스에서 프로세스는 이 유일한 경로들의 집합으로부터, 1-13 내지 4-18로부터의 모든 노드 쌍들(예컨대, 1-5, 5-9, 9-13 및 4-8, 8-12, 12-18)에 대해 사전적 순서로 정렬된 유일한 경로들의 집합을 생성할 수 있으며, 본 예는 이 유일한 경로 식별자들의 순위화로부터 낮은 경로 및 높은 경로가 선택되며, 그들은 트리(501) 및 트리(503)에 대응한다고 가정한다.

도 6은 상기 본 명세서에 설명된 부하 분산 방법의 제2 반복에서 선택된 경로들 또는 트리들을 나타낸다. 이 예에서, 부하 분산 방법은, 각 경로와 관련된 사전적 순서의 링크 부하가 두 경로들 간에 타이를 만들어내는 두 경로들을 찾으며, 경로 식별자로서의 노드 ID들의 예시적인 사전적 순서는 타이를 강압적으로 해결하기 위하여 호출된다. 제2 반복으로부터의 최저 순위 트리(605) 및 최고 순위 트리(607)는 노드 1 내지 노드 4와 노드 13 내지 노드 18 간의 트래픽을 더 분산시키고, 도 5에 도시된 제1 반복으로부터의 최저 랭크 트리(601) 및 최고 랭크 트리(603)를 보충한다. 사전적 정렬로 링크 사용 값을 통합함으로써, 제2 반복은 최소 활용된 링크들을 갖는 동일 비용 경로들을 선택하고, 이에 의해서 대역폭의 활용 및 선택된 "모든 쌍" 경로들의 토폴로지의 다양성이 증가한다.

도 7은 MPLS 네트워크 내의 운용, 관리 및 유지보수(OAM)를 지원하기 위하여 의사 와이어(pseudo wire)들의 집합을 기저 패킷 스위치 네트워크에 매핑하는 일 실시예의 도면이다. 성능 모니터링이 유지될 수 있으며, 의사 와이어들의 집합과 등가인 엔드 포인트들 간에 피어 투 피어 LSP들의 풀 메시(full mesh)를 놓음으로써 트래픽 엔지니어링 시스템과 호환성이 유지될 수 있다. 패킷 스위치 네트워크는 순서(N)를 스케일링하며 그에 따라 장애 관리가 스케일링 수 있지만, 오버레이는 성능 모니터링에 필요한 피어-투-피어 속성을 갖는다. 의사 와이어들의 FEC들은 의사 와이어 FEC를 PSN 가상 토폴로지 인덱스에 바인딩하기 위하여 수정된다. PSN 토폴로지가 의사 엔드 포인트들 간에서 논리적으로 피어-투-피어이기 때문에, 의사 와이어 레이블은 OAM 카운터에 대한 소스 명확화의 수단을 제공한다.

따라서, 링크 사용을 고려한 MPLS 네트워크 내의 부하 분산을 위한 방법, 시스템 및 장치가 설명되었다. 상기 설명은 예시를 위한 것이고 한정을 위한 것이 아님을 이해해야 한다. 상기 설명을 읽고 이해하면 당업자들에게 다른 많은 실시예들이 명백할 것이다. 따라서, 발명의 범위는 첨부된 청구항 및 이러한 청구항에 부여되는 동등한 모든 범위를 함께 참조하여 결정되어야 한다.

Claims

향상된 부하 분산을 위해 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크의 노드에서 구현되는 방법으로서,
상기 노드는 최소 비용 최단 경로 트리들을 만들어내도록 일반 알고리즘 타이-브레이킹 프로세스(common algorithm tie-breaking process)를 각각 구현하는 상기 MPLS 네트워크 내의 복수의 노드 중 하나이고, 상기 노드는 상기 MPLS 네트워크의 토폴로지를 저장하기 위한 토폴로지 데이터베이스를 포함하고, 상기 MPLS 네트워크의 토폴로지는 복수의 노드들 및 상기 노드들 간의 링크들을 포함하며, 상기 방법은,
상기 토폴로지 데이터베이스에 저장된 상기 MPLS 네트워크의 토폴로지 상에서 최단 경로 탐색 알고리즘을 실행함으로써 상기 MPLS 네트워크 내의 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제1 집합을 결정하는 단계;
상기 일반 알고리즘 타이-브레이킹 프로세스를 적용함으로써 각 MPLS 노드 쌍에 대한 상기 최단 경로들의 제1 집합으로부터 적어도 제1 최단 경로를 선택하는 단계;
각 링크를 통과하는 선택된 최단 경로들의 카운트에 기초하여 상기 MPLS 네트워크의 각 링크에 대한 링크 사용률 값(link utilization value)을 계산하는 단계;
상기 토폴로지 데이터베이스에 저장된 상기 MPLS 네트워크의 토폴로지 상에서 최단 경로 탐색 알고리즘을 실행함으로써 상기 MPLS 네트워크 내의 각 MPLS 노드 쌍 간의 하나 이상의 최단 경로의 제2 집합을 결정하는 단계;
각 최단 경로에 대응하는 링크 사용률 값들에 기초하여 상기 하나 이상의 최단 경로의 제2 집합 내의 각 최단 경로에 대한 경로 사용률 값을 생성하는 단계;
상기 경로 사용률 값을 기초로 하여 상기 하나 이상의 최단 경로의 제2 집합으로부터 제2 최단 경로를 선택하는 단계 - 상기 선택하는 단계는 동일한 경로 사용률 값들을 갖는 복수의 최단 경로가 상기 하나 이상의 최단 경로의 집합에 존재할 때 상기 일반 알고리즘 타이-브레이킹 프로세스를 활용함 -; 및
레이블 정보 데이터베이스 내에서, 각 MPLS 노드 쌍에 대해 적어도 상기 제1 최단 경로 및 상기 제2 최단 경로를 저장하는 단계 - 상기 레이블 정보 데이터베이스는 상기 MPLS 노드로 들어오는 트래픽을 어디로 포워딩할 것인지 표시함 -
를 포함하며, 이에 의해서 경로 사용률을 고려한 제2 서브셋들의 선택은 상기 MPLS 네트워크 전체에 걸친 부하 분산의 표준 편차를 최소화하는 방법.
제1항에 있어서, 상기 경로 사용률 값을 생성하는 단계는,
각 경로에 대응하는 링크 사용률 값들을 총합하는 단계, 또는
각 경로에 대응하는 상기 링크 사용률 값들을 사전적 순서로 정렬하는 단계
를 포함하는 방법.
제2항에 있어서,
관리자로부터 링크 수정 인자(link modification factor)를 수신하는 단계; 및
상기 링크들 및 경로들 중 대응하는 것에 가중치를 부여하여, 최저 부하 경로의 집합의 순위화에 영향을 미쳐 선택의 가능성을 감소시킴으로써 그 링크의 이용을 감소시키도록, 상기 링크 수정 인자를 상기 링크 사용률 값과 결합하는 단계
를 더 포함하는 방법.
제2항에 있어서,
대응하는 경로 사용률 값들에 기초하여, 상기 최단 경로들의 제2 집합 내의 각 최단 경로를 순위화하는 단계를 더 포함하며,
적어도 상기 제2 최단 경로를 선택하는 단계는, 상기 순위화로부터 최고 순위 최단 경로 및 최저 순위 최단 경로를 선택하는 단계를 더 포함하는 방법.
제2항에 있어서,
이더넷 네트워크를 위한 전체적인 향상에 대한 네트워크 운영자들의 희망을 반영하는 관리된 경로들의 수가 만족될 때까지 상기 제1 최단 경로 및 제2 최단 경로와 부하 분산을 공유하도록 추가 최단 경로들을 반복적으로 선택하는 단계를 더 포함하는 방법.
제1항에 있어서, MPLS 노드 쌍들 간의 최단 경로들의 집합들은 상기 MPLS 네트워크 내의 레이블 스위치 경로들(label switched paths)로서 구현되는 방법.
제1항에 있어서,
레이블 매핑 메시지를 생성하는 단계;
상기 레이블 매핑 메시지 내에 FEC 타입-길이-값(TLV) 필드를 정의하는 단계;
상기 레이블 매핑 메시지 내에 레이블 TLV 필드를 정의하는 단계;
상기 레이블 매핑 메시지에 대한 토폴로지 인덱스를 정의하는 단계 - 상기 토폴로지 인덱스는 제1 서브셋 및 제2 서브셋을 선택하는 단계에 있어서의 반복을 표시함 - ; 및
상기 MPLS 네트워크 내의 각 레이블 분배 프로토콜 피어에 상기 레이블 매핑 메시지를 송신하는 단계
를 더 포함하는 방법.
제7항에 있어서, 상기 레이블 매핑 메시지들은 토폴로지-인덱스 값들 및 FEC의 각 조합에 대해 각 LDP 피어로 송신되는 방법.
자신을 포함하는 멀티-프로토콜 레이블 스위칭(MPLS) 네트워크 내의 향상된 부하 분산을 위한 네트워크 구성요소로서,
상기 네트워크 구성요소는 상기 MPLS 네트워크 내의 복수의 노드 중 하나이고, 상기 MPLS 네트워크의 토폴로지는 복수의 노드들 및 상기 노드들 간의 링크들을 포함하고, 상기 네트워크 구성요소는,
상기 MPLS 네트워크 내의 각 링크에 대한 링크 정보를 저장하는 토폴로지 데이터베이스;
상기 네트워크 구성요소의 각 포트에 대한 레이블 정보를 저장하는 레이블 정보 데이터베이스 - 상기 레이블 정보 데이터베이스는 상기 네트워크 구성요소로 들어오는 각 포워딩 동치 클래스(FEC: forwarding equivalency class)를 어디로 포워딩할지를 나타냄 - ; 및
상기 토폴로지 데이터베이스 및 상기 레이블 정보 데이터베이스에 연결된 컨트롤 프로세서 - 네트워크 프로세서는 데이터 트래픽을 프로세싱하도록 구성됨 -
를 포함하며, 상기 네트워크 프로세서는,
레이블 스위치 경로(LSP)들을 통해서 데이터 트래픽을 포워딩하도록 구성된MPLS 관리 모듈;
상기 MPLS 네트워크에 LSP들을 설정하도록 구성된 레이블 분배 프로토콜(LDP) 모듈;
상기 토폴로지 데이터베이스 상에서 최단 경로 탐색 알고리즘을 실행함으로써 상기 MPLS 네트워크 내의 각각의 MPLS 노드 쌍 간에 적어도 하나의 최단 경로를 결정하도록 구성된 최단 경로 탐색 모듈 - 상기 최단 경로 탐색 모듈은, 복수의 동일 비용 최단 경로를 갖는 각각의 MPLS 노드 쌍들에 대하여 상기 동일 비용 최단 경로들을 부하 분산 모듈로 송신하도록 구성됨 - ;
상기 복수의 동일 비용 최단 경로 내의 각각의 경로와 관련된 링크 사용률 값들로부터 도출된 경로 사용률 값에 기초하여 상기 복수의 동일 비용 최단 경로 각각을 순위화하도록 구성된 정렬 모듈; 및
수신된 상기 복수의 동일 비용 최단 경로로부터, MPLS 노드 쌍 간에 데이터 트래픽 부하를 공유하기 위하여 이용되는, 그 MPLS 노드 쌍을 위한 상기 복수의 동일 비용 최단 경로의 제1 서브셋을 선택하고, 상기 경로 사용률 값에 기초하여 이더넷 브리지 쌍을 위한 제1 서브셋과 데이터 트래픽 부하를 공유하기 위하여 이용되는, 그 MPLS 노드 쌍을 위한 상기 복수의 동일 비용 최단 경로로부터의 제2 서브셋을 선택하도록 구성된 부하 분산 모듈
을 포함하며,
이에 의해서 상기 경로 사용률 값을 고려한 상기 제2 서브셋의 선택은 상기 MPLS 네트워크 전체에 걸친 부하 분산의 표준 편차를 최소화하는 네트워크 구성요소.
제9항에 있어서, 상기 정렬 모듈은 또한 상기 복수의 동일 비용 최단 경로의 순위화를 생성하기 위하여 상기 링크 사용률 값들을 사전적 순서로 정렬하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 최단 경로 탐색 모듈은 또한 상기 토폴로지 내의 각 링크에 대하여 상기 링크 사용률 값을 계산하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 컨트롤 프로세서는 또한 상기 MPLS 네트워크 내의 노드 쌍들 간의 각각의 선택된 최단 경로들을 구현하기 위해 레이블 스위치 경로(LSP)들을 생성하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 부하 분산 모듈은 또한, 관리자로부터 링크 수정 인자를 수신하고; 경로 내의 대응하는 링크에 가중치를 부여하여, 그 경로의 사전적 순서 정렬에 영향을 미쳐 선택의 가능성을 감소시킴으로써 상기 링크의 이용을 감소시키도록, 상기 링크 수정 인자를 링크 사용 값과 결합하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 부하 분산 모듈은 또한, 상기 동일 비용 최단 경로들의 제1 순위화에서 최고 및 최저 아이템을 선택함으로써 상기 복수의 동일 비용 최단 경로 각각으로부터 상기 제1 서브셋을 선택하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 부하 분산 모듈은 또한, 최저 부하를 갖는 동일 비용 최단 경로들에 일반 알고리즘 타이-브레이킹 프로세스를 적용하여 최고 및 최저 아이템을 선택함으로써 상기 복수의 동일 비용 최단 경로 각각으로부터 상기 제2 서브셋을 선택하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 정렬 모듈 및 부하 분산 모듈은 또한 상기 제1 서브셋 및 제2 서브셋과 부하 분산을 공유하기 위하여 추가 서브셋들을 반복적으로 선택하도록 구성된 네트워크 구성요소.
제9항에 있어서, 상기 LDP 모듈은 또한, 레이블 매핑 메시지 내의 FEC 타입-길이-값(TLV) 필드, 상기 레이블 매핑 메시지 내의 레이블 TLV 필드, 및 상기 레이블 매핑 메시지에 대한 토폴로지 인덱스를 포함하는 상기 레이블 매핑 메시지를 생성하도록 구성되고, 상기 토폴로지 인덱스는 상기 제1 서브셋 및 제2 서브셋을 선택하는 단계에 있어서의 반복을 표시하고, 또한 상기 MPLS 네트워크 내의 각 레이블 분배 프로토콜 피어에 상기 레이블 매핑 메시지를 송신하도록 구성된 네트워크 구성요소.
제17항에 있어서, 상기 LDP 모듈은 또한, 토폴로지 인덱스 및 FEC의 각 조합에 대하여 레이블 매핑 메시지들을 각 LDP 피어로 송신하도록 구성된 네트워크 구성요소.