최단경로 브리징에서의 확장된 동일비용트리 = Extended Equal Cost Trees in Shortest Path Bridging

국문 초록 (Abstract)

Shortest Path Bridging(SPB)[1]은 이더넷 백본망에서 사용하기 위하여 IEEE802.1aq에서 표준화가 진행중인 2계층 라우팅 프로토콜이다. SPB는 최단경로 스패닝 트리를 생성하여 트리를 따라서 메시지를 전송한다. SPB는 의도적으로 많은 최단경로를 생성한 후에 동일 비용트리 선택규칙(Equal Cost Tree 규칙, 이하 ECT 혹은 선택규칙)을 반복적으로 적용하여 여러 최단경로를 선택하고 이들을 통해서 병렬적으로 트래픽을 적절히 분산하며 전송한다. ECT는 고유노드id 대신에 인코딩된 노드id를 기준으로 다양한 트리를 생성한다. 이 방식은 고유노드id가 어떤 값을 갖느냐에 따라서 일부 최단경로를 선택하지 못하거나 불공평하게 최단경로를 선택하는 약점이 있다.
이러한 문제점을 개선하기 위해서 이 논문은 ECT를 변형한 ECTc를 제안한다. 분석을 통해서 ECTc가 ECT보다 개선된 선택방식이며, ECT와 ECTc를 함께 사용하면 최상의 선택방식이 될 수 있음을 밝혔다. 그 근거로서 경로선택이 잘못될 확률을 계산하였고, 한 개의 경로선택공식만을 사용할 때와 두 개의 경로선택공식을 함께 사용할 때에 네트워크 자원을 얼마나 균등하게 사용하는가를 수치로 제시하였다.

다국어 초록 (Multilingual Abstract)

Shortest Path Bridging (SPB) is a very recent layer-2 routing protocol under discussion in IEEE802.1aq to be used in Ethernet backbone networks. SPB builds up the shortest path trees to send messages. SPB intentionally generates many shortest paths, and the special tie-break rule, called Equal Cost Tree (ECT), picks up a final one. As a featured encoding scheme in SPB, ECT can generate many different shortest paths by repeated using itself, through which traffic are delivered while balancing the load. This nice scheme, unfortunately, used to fail choosing some paths or choose paths in an unfair way depending what the node identifiers are.
This paper proposes the complementary ECT, briefly ECTc. The analysis shows our proposed ECTc is better than ECT and the combined use of ECT and ECTc is the best. As evidences, we calculated the probability of wrong path selection and observed how uniformly network resources are used with the single path selection and as well as the double path selection.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 소개
• 2. SPB 브리징
• 3. ECTc에 의한 개선
• 4. 결론
• 참고문헌

참고문헌 (Reference)

1 이문호, "퍼지 집합 이론을 활용한 무선인지 주파수 할당 알고리즘" 한국통신학회 33 (33): 745-750, 2008

2 S. L. Cecilio, "Using regular topologies for wimax backbone : A case study" 466-473, 2009

3 Juan A. Carral, "TRE+: Extended Tree-Based Routing Ethernet" 한국전자통신연구원 32 (32): 157-159, 2010

4 M. Huynh, "Spanning tree elevation protocol: Enhancing metro ethernet performance and QoS" 32 (32): 750-765, 2009

5 D. Allan, "Shortest Path Bridging : Efficient Control of Large Ethernet Networks" IEEE 48 (48): 128-135, 2010

6 János Farkas, "Performance Analysis of Shortest Path Bridging Control Protocols" 2009

7 David Allan, "Method and Apparatus for Selecting Between Multiple Equal Cost Paths, 특허출원번호 20110060844"

8 Shin-woong Jung, "Layer-2 Routing Analytic Model by Linear Programming" 2008

9 A. de Sousa, "Improving load balance of ethernet carrier networks using ieee 802.1s mstp with multiple regions" 3976 : 1252-1260, 2006

10 A. F. De Sousa, "Improving load balance and resilience of ethernet carrier networks with ieee 802.1s multiple spanning tree protocol" IEEE Computer Society 1 : 95-102, 2006

11 "I. T. G. of IEEE 802.1, Spanning Tree Protocol, IEEE 802.1D Std"

12 "I. T. G. of IEEE 802.1, Shortest Path Bridging, IEEE 802.1aq Std"

13 "I. T. G. of IEEE 802.1, Multiple Spanning Trees, IEEE 802.1s Std"

14 G. Ibáñez, "Evaluation of tree-based routing ethernet" 13 (13): 444-446, 2009

15 A. Kasim, "Delivering Carrier Ethernet Extending Ethernet Beyond the LAN" McGraw-Hill 2008