스패닝 트리 알고리즘 spanning tree algorithm

스패닝 트리 알고리즘(spanning tree algorithm)
스위치나 브리지에서 발생할 수 있는 루핑(looping)을 미리 막기 위해 두 개 이상의 경로가 발생하면 하나를 제외하고 나머지 경로들을 자동으로 막아두었다가 만약 기존 경로에 문제가 생기면 막아놓은 경로를 풀어서 데이터를 전송하는 알고리즘, 혹은 스패닝트리프로토콜(STP)

스위치 루핑 Looping은 구축된 네트워크에서 Frame 이 무한대로 뺑뺑이처럼 돌기 때문에 이더넷 특성상 pc들이 전송한 데이터가 없어질 때까지 기다리기만 할 뿐, 데이터 전송은 불가능해지는 상태를 의미합니다. 보통 이중화 등을 위해 네트워크 장비를 서로 연결해 놓은 경우 이 네트워크 장비들 간의 전송상에서 발생합니다. 

 

* SPA 동작과정 

* 동작과정에 있어 설명하기 앞서 bridge Id, path cost의 개념을 이해해야만 합니다.

 

1) bridge ID란? (스위치도 이 ID를 사용하지만 스위치ID라 부르지않고 다 브리지ID라 부른다.) 

브리지나 스위치가 서로를 인식할 수 있는 ID

16bit의  Bridge priorty 브리지우선순위번호와

48bit의  MAC 어드레스로 구성되어있어 총 64bit = 8Byte이다.  

 

2) path cost(STP cost)란?

STP를 이용할때 네트워크에서 전송되는 링크의 코스트를 의미한다.

예전에는 1000이라는 정수값 / x(Mbps)의 값이었으나

네트워크 전송속도가 빨라져 IEEE에서 속도마다 전송값으로 따로 정의하였다.

3) 3가지 기본약속과 용어

 

*STP 세가지 약속

a. 네트워크 당 하나의 루트 브리지(Root bridge)를 갖는다.

b. 루트 브리지가 아닌 나머지 모든 브리지(Non root bridge)는 무조건 하나씩의 루트포트를 갖는다.

c. 세그먼트(segment)당 하나씩의 Designated port를 갖는다.

 

여기서 네트워크는 하나의 스위치, 브리지 혹은 허브로만 연결된 라우터 하위의 하나의 LAN을 의미한다.

즉 하나의 브로드캐스트 공간을 의미하며 스위치 혹은 브리지의 개수의 따라 N+1개의 콜리전 도메인을 갖는 상태이다.

 

루트브리지는 하나의 네트워크에서 STP를 수행할 때 기준이 되는 브리지(스위치)이다.

 

논루트브리지들은 하나의 Root port를 갖는데 root port란 루트브리지로 가장 빠르게 갈 수 있는 포트를 말한다.

 

세그먼트(segment)는 네트워크에서 브리지 또는 스위치 간의 연결된 링크인데 이 링크의 양 포트중 하나를 designated port로 선정한다.

 

         

 

 

4) 알고리즘 순서! (암기필수)

1. 누가 더 작은 Root BID를 가졌는가?

2. 루트 브리지까지의 Path Cost는 누가 더 작은가?

3. 누구의 BID(sender bid)가 더 낮은가? 

4. 누구의 포트ID가 더 작은가?

 

** BPDU( Bridge protocol data unit)이란?

브리지(스위치)들은 특수한 프레임을 서로주고받는데 이를 BPDU라 부른다.

브리지는 부팅되면 각각의 포트로 BPDU를 2초마다 보내면서 정보를 주고받는다. 그리고 BPDU의 통신을 통해 어떤 포트가 RP가 될지 DP가 될지를 결정한다.

BPDU 포맷 -> 브리지 ID 또는 BID가 BPDU 패킷의 하나의 필드로 들어가며 8바이트이다. 최초 2바이트는 브리지 우선순위이며 0-65535의 비부호 정수(unsigned integer)이다. 뒤의 6바이트는 스위치에서 제공한 MAC 주소이다. MAC 주소 축약(MAC Address Reduction)이 사용될 경우 앞의 2바이트 다르게 사용된다. 앞의 4비트는 우선순위로 사용되고 뒤의 12비트는 VLAN ID나 MSTP 인스턴스 번호의 전달에 사용된다.

           

 

5) 스패닝 트리 프로토콜의 5가지 상태변화

1. disabled : 포트가 고장나거나 네트워크관리자가 포트를 일부러 shutdown시켰을 때

데이터전송 X / learnMac X / BPDU통신 X

 

2. blocking : 막 부팅시켰을때 상황, STP를 위한 정보를 배우는 중

데이터전송 X / learnMac X / BPDU통신 O 

 

3. listening : BPDU통신을 통해 RP와 DP로 포트선정이 완료되면 이 상태가 된다.

데이터전송 X / learnMac X / BPDU통신 O 

 

4. learning : 리스닝상태의 포트가 포워딩 딜레이 디폴트 시간인 15초를 유지하면 리스닝에서 러닝으로 바뀐다.

데이터전송 X / learnMac O / BPDU통신 O 

 

5. forwarding : 러닝 상태에서 또 포워딩 딜레이 디폴트 시간 15초를 넘겼기에 러닝으로 바꾼다.

데이터전송 O / learnMac O / BPDU통신 O