신장 트리 프로토콜

신장 트리 프로토콜(영어: spanning tree protocol, STP)은 래디아 펄먼(Radia Perlman)이 고안한 알고리즘에 기반한 OSI 2계층 프로토콜로 브리지 랜에서 루프 발생을 방지하기 위해 사용된다. 신장 트리 프로토콜은 IEEE 802.1D에서 정의되었으며 이름에서 알 수 있듯이 2계층 브리지(이더넷 스위치)를 통해 연결된 매시 네트워크내에서 신장 트리를 생성한다. 두 노드 사이에 활성된 경로가 두 개 이상 존재할 경우 브리지 루프가 발생할 수 있으며 브리지 루프는 몇 가지 문제를 야기시킨다. 첫째, 동일 MAC 주소(즉, 동일 호스트)가 여러 포트에서 보여 브리지에서 사용하는 MAC 주소 테이블(스위칭 포워딩 테이블)이 실패할 수 있다. 둘째, 브로드캐스트 스톰(broadcast storm)이 발생하여 브로드캐스트 패킷들이 스위치 사이를 무한히 돌게 된다. 브로드캐스트 스톰은 CPU 리소스와 대역폭을 극심히 소모시킨다. 신장 트리는 자동 백업을 지원하는 여분의 링크를 제공하면서 브리지 루프를 방지해 준다.

프로토콜의 동작

LAN 내 브리지들의 집합은 하나의 그래프로 표현할 수 있으며 이때 브리지를 그래프의 정점이 된다. 브리지들은 신장 트리를 만들어 모든 LAN 세그먼트간의 연결성을 유지하면서 루프를 방지한다. 신장 트리가 꼭 최소 신장 트리 필요는 없다. 망 관리자는 필요에 따라 설정 파라미터를 제거함으로써 신장 트리의 루트(root) 선출에 영향을 줄 수 있다.

루트 브리지의 선출. 신장 트리의 루트 브리지는 가장 낮은 브리지 ID를 갖는 브리지로 한다. 각각의 브리지는 유일한 ID와 설정가능한 우선순위 번호를 갖는다. 브리지 ID는 이 두 가지를 모두 포함한다. 두 브리지 ID를 비교할 때, 우선 순위를 먼저 비교한다. 이 값이 같을 경우 MAC 주소를 비교한다. 망 관리자는 우선 순위 값을 설정하여 특정 브리지를 루트로 삼을 수 있다.

루트 브리지로의 최소 비용 경로 결정. 신장 트리가 계산되면 망내 장비는 최소 비용으로 루트로의 메시지 전송이 가능해진다. 경로의 비용은 경로 상의 네트워크 세그먼트의 비용의 합이며 네트워크 세그먼트의 비용은 각기 다르게 설정될 수 있다. 다음의 두 규칙을 통해 메시지는 항상 최소 비용으로 루트까지 전달된다.

• 각 브리지에서의 최소 비용 경로: 루트 브리지가 선출된 다음, 각각의 브리지는 루트에서 자신으로 연결되는 각각의 경로에 대한 비용을 결정하고 그 중 최소 비용의 경로를 선택한다. 선택된 경로로 연결된 포트를 이 브리지의 루트포트(root port)라 한다.

• 각 네트워크 세그먼트에서의 최소 비용 경로: 네트워크 세그먼트 상의 브리지들은 해당 네트워크 세그먼트에서 루트로의 최소 비용 경로를 갖는 브리지를 결정하고 이 브리지와 해당 네트워크 세그먼트를 연결한 포트를 해당 세그먼트의 지명 포트(designated port)라 한다.

나머지 경로들의 삭제. 루트 포트 혹은 지명 포트를 제외한 모든 포트를 막아놓는다.

묶음 상태에 대한 수정(Modifications in case of ties). 위의 규칙들은 네트워크 상태를 지나치게 간략히 표현한 것이다. 간혹 하나의 브리지에 둘 이상의 포트가 최소 비용 경로에 연결되어 있거나 동일 네트워크 세그먼트내 둘 이상의 브리지가 같은 비용의 경로를 가질 수 있다. 이와 같은 상황은 다음과 같이 없앨 수 있다:

• 루트 포트에 대한 묶음 제거(Breaking ties for root ports): 하나의 브리지에서 최소 비용 경로가 여러 개 존재할 경우, 각각의 경로에 대해 이웃 브리지의 브리지 ID값을 확인하고 이 값이 가장 작은 경로를 선택한다. 그리하여 가장 낮은 브리지 ID의 브리지와 연결된 포트를 이 브리지의 루트 포트로 정한다.

• 지명 포트에 대한 묶음 제거(Breaking ties for designated ports): 세그먼트내 하나 이상의 브리지가 최소 비용 경로를 가질 때, 더 낮은 브리지 ID를 갖는 브리지가 메시지 전송을 위해 사용되며 해당 네트워크 세그먼트로 브리지하는 데에 사용되는 포트가 해당 세그먼트에 대한 지명 포트(designated port)가 된다.

• 최종 묶음 제거자(The final tie-breaker): 몇 가지 경우에 있어서 두 개의 브리지가 여러 라인으로 연결되어 여전히 묶음이 존재할 수 있다. 이처럼 하나의 브리지에 여러 개의 루트 포트 또는 지명 포트가 있을 경우 가장 낮은 포트 번호를 갖는 포트를 사용한다.

대역폭과 STP 경로 비용

아래 표는 대역폭에 따른 인터페이스의 기본 비용을 나타낸 것이다.

대역너비	STP 비용
4 Mbit/초	250
10 Mbit/초	100
16 Mbit/초	62
45 Mbit/초	39
100 Mbit/초	19
155 Mbit/초	14
200 Mbit/초	12
622 Mbit/초	6
1 Gbit/초	4
2 Gbit/초	3
10 Gbit/초	2

BPDUs(Bridge Protocol Data Units)

위의 규칙에 따라 신장 트리를 만들기 위해서는 전체 네트워크에 대한 정보를 알아야 한다. 브리지들은 루트 브리지를 결정하고 포트의 역할(루트, 지명, 비사용)을 결정하는 데에 오직 자신이 가지고 있는 정보만을 사용해야 한다. 각각의 브리지가 충분한 정보를 가질 수 있도록 하기 위해 브리지들은 BPDU라 불리는 특별한 데이터 프레임을 사용하여 브리지 ID와 루트 경로 비용에 대한 정보를 교환한다. 브리지는 포트의 발신지 주소로 포트의 MAC 주소를 사용하며 목적지 주소로는 STP 멀티캐스트 주소 01:80:C2:00:00:00를 사용한다. BPDU는 크게 세 가지 형태가 있다

• Configuration BPDU(CBPDU), 신장 트리 계산에 사용
• Topology Change Notification(TCN) BPDU, 망 토폴로지 변경을 알리기 위해 사용
• Topology Change Notification Acknowledgement(TCA)

BPDU는 정기적으로(기본적으로 2초마다) 교환되어 망 변화 감지 및 포트의 포워딩 동작을 제어한다. 어느 장비가 스위치 포트에 최초 연결되면 이 장비는 바로 데이터를 전송하지 않는다. 대신 BPDU가 처리되고 망 토폴로지가 결정될때까지 많은 수의 상태를 넘나든다. 컴퓨터, 프린터 또는 서버와 같은 호스트는 비록 상태 정보를 알기까지 30초의 지연이 있지만 항상 포워딩 상태로 간다. 상태 정보를 듣고 알기까지의 시간은 포워드 지연(기본적으로 루트 브리지에서 15초로 설정)에 의해 결정된다. 하지만 만일 또다른 스위치가 연결되고 이로 인해 망내에 루프가 발생할 경우 이 포트는 막힌다. Topology Change Notification(TCN) BPDU는 포트의 변화를 알리기 위해 사용된다. TCN은 루트 스위치 이외의 스위치에 의해 망에 퍼지며 루트로 전달된다. TCN을 수신하면 루트 스위치는 일반 BPDU내에 Topology Change 플래그를 설정한다. 이 플래그는 다른 모든 스위치로 빠르게 전달되어 다른 스위치의 포워딩 테이블 엔트리를 오래된 것으로 만든다.

STP 스위치 포트 상태

• Disable - STP에 의한 것이 아닌, 망 관리자에 의해서 특정 포트는 사용을 금지당할 수 있다.
• Blocking - 스위치 루프를 일으키는 포트로 어떠한 사용자 데이터를 송수신할 수 없다. 단, 다른 링크가 사용불가가 되고 신장 트리 알고리즘에 의해 포워딩 상태가 되면 동작한다. BPDU 데이터는 blocking 상태에서도 여전히 받을 수 있다.
• Listening - 해당 스위치는 BPDU를 처리하고 blocking 상태로 전환케 할 수 있는 정보에 대해 수신을 기다린다.
• Learning - 해당 포트가 프레임을 전달할 수 없는 동안 프레임들의 발신자 주소를 얻어 필터링 DB(스위칭 DB)에 저장한다.
• Forwarding - 해당 포트에서 필터링 DB에 저장된 발신자 주소를 기반으로 프레임을 전달하는 상태.

BPDU 필드

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

같이 보기

• IEEE 802.1w - 2004 Rapid Spanning Tree Protocol (RSTP)
• IEEE 802.1s - 2005 Multiple Spanning Tree Protocol (MSTP)
• IEEE 802.1aq - 2012 Shortest path bridging (SPB)

• 최소 트리 프로토콜 (Minimum Spanning Tree)
• 분산 최소 신장 트리(distributed minimum spanning tree)
• IEEE 802.1D
• VLAN
• 이더넷 자동 보호 시스템(Ethernet Automatic Protection System)
• UDLD
• 네트워크 브리지
• 이더채널

외부 링크

• Cisco's Introduction to Spanning-Tree
• Radia Perlman at Sun Labs
• ANSI/IEEE 802.1D-2004 standard
• ProCurve Spanning Tree implementation Training
• RFCs
  • RFC 2674-1999, proposed standard, Definitions of Managed Objects for Bridges with Traffic Classes, Multicast Filtering and Virtual LAN Extensions
  • RFC 1525-1993, - SBRIDGEMIB, proposed standard, Definitions of Managed Objects for Source Routing Bridges
  • RFC 1493-1993 - BRIDGEMIB, draft standard, Definitions of Managed Objects for Bridges