Spanning tree
1. 스패닝 트리 개요
스패닝 트리란 n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리로 사이클이 없다. 즉, G안에 있는 모든 정점을 다 포함하면서 최소의 간선을 이용하여 연결한 그래프이다.
스패닝 트리는 다음과 같은 성질을 가진다.
① 그래프 내에 원래 있던 간선들만을 포함 한다
② 정점의 수가 n일때 n-1개의 간선만을 포함 한다
③ 순환 (cycle)이 있어서는 안된다
2. 스패닝 트리 알고리즘
스패닝 트리 알고리즘(Spanning Tree Algorithm)이란 스위치나 브리지에서 발생할 수 있는 루핑을 미리 막기 위해 두 개 이상의 경로가 발생하면 하나를 제외하고 나머지 경로들을 자동으로 막아두었다가 만약 기존 경로에 문제가 생기면 막아놓은 경로를 풀어서 데이터를 전송하는 알고리즘이다.
(그림 1)은 스패닝트리 알고리즘을 적용한 네트워크의 예를 보여주고 있다.
1. 네트워크당 하나의 Root Bridge를 갖는다.
2. 루트 브리지가 아닌 나머지 브리지(Non Root Bridge)는 무조건 하나씩의 Root Port를 갖는다.
3. Segment당 하나씩의 Designated Port를 갖는다.
<Root Port와 Designated Port 순서 정하는 공식>
1단계 : 누가 더 작은 Root BID를 가졌는가?
2단계 : 루트브리지까지의 Path Cost 값은 누가 더 작은가?
3단계 : 누구의 BID (sender BID)가 더 작은가?
4단계 : 누구의 Port ID가 더 낮은가?
1) 루트 브리지(Root Bridge)
네트워크당 하나의 루트 브리지를 갖는다. 스패닝 트리 프로토콜 수행시 기준이 되는 브리지로서 가장 작은 값을 가진 스위치가 Root Bridge가 된다.
2) 루트가 아닌 브리지(Non Root Bridge)
Root Bridge를 제외한 모든 브리지를 말하는 것으로 무조건 하나씩의 루트포트를 갖고 있어야 한다. 루트포트란 루트가 아닌 브리지에서 루트 브리지까지 가장 빨리 갈 수 있는 포트(가장 가까운 포트)를 말한다.
3) 지정 포트 (Designated port)
사용자 입장에서 Root Bridge로 갈 수 있는 최저 경로 포트를 의미한다. 즉 브리지 또는 스위치 간에 연결된 링크에서 한 포트는 지정포트로 설정을 해야 된다. (=Segment당 하나씩의 Designated Port를 갖는다.)
4) Non Designated port
Blocking 상태로서 데이터 전송이 이루어지지 않게 된다. (링크가 끊어짐)
- TCP/IP Protocol Suite(3rd).
- 후니의 쉽게 쓴 시스코 네트워킹.
Try to look on the bright side.
천공
댓글을 달아 주세요