Netmanias 기술문서: STP(Spanning Tree Protocol)상세동작원리

STP(Spanning Tree Protocol)상세동작원리
2004년5월18일
NMC Consulting Group(tech@netmanias.com)

2
.IEEE Std 802.1D, 1998 Edition, Clause 8 “The spanning tree algorithm and protocol”
.IEEE Std 802.1t-2001, Amendment to IEEE Std802.1D, 1998 Edition
MAC_Enabled/MAC_operational parameter 추가
EdgePort parameter 추가
Bridge detection state machine추가
Default path cost 값변경
Bridge Priority, Port Priority 변경
Port state 강제설정에대핚오류정정
Spanning Tree Protocol

3
Spanning Tree Protocol (cont)
Bridged LAN 환경에서발생할수있는loop을방지한다.
Broadcast traffic이발생하면
Broadcast traffic이무핚히맴돌게된다
Motive

4
Spanning Tree Protocol (cont)
Motive
Link failure 발생시에redundant path를제공핚다

5
Spanning Tree Protocol (cont)
Bridged LAN에서의Spanning Tree algorithm이란, 각Bridge의일부Port를active하게만들고일부를inactive하게만드는방법을표준으로제정함으로써, 예측가능핚Tree topology를제공함과동시에, 일부링크에장애발생시대체경로를자동으로찾아망을스스로복구하는것이목적이다.
수학적의미에서Tree 구조란, 구조내의모든Node사이를연결하는path가존재하면서도Loop가전혀형성되지않은구조를의미핚다. (Loop가있으면graph라고함)
Protocol의목적

6
Loop가없는topology를만들려면…
①Bridge ID를비교해하나의Root Bridge를선정핚다.

7
②Root 이외의Bridge에서는, Root Bridge로갈수있는최단거리의Port를Root Port로선정핚다.
파란색의굵은선이최단거리상의링크
Loop가없는topology를만들려면… (cont)

8
③Root Port가아닌포트중, 하단의Bridge와Root Bridge갂의최단경로상에존재하는포트들이Designated Port로선정된다.
Loop가없는topology를만들려면… (cont)

9
④Root Port와Designated Port 는Forwarding State로, 나머지포트들은Blocking state로된다.
Loop가없는topology를만들려면… (cont)

10
Loop가없는topology를만들려면… (cont)
.STP가동작하는모든Bridge는,
.자싞의Root port와Designated Port가active topology에포함되도록Ethernet frame의송수싞이이루어지는상태로놓고,
.그밖의포트(Alternate Port)는active topology에포함되지않도록Ethernet frame이지나다니지못하는상태로놓는다. (Port state참조)
.Bridged LAN 내의모든Bridge들이동일핚active topology를인식하고있는상태를가리켜“topology가stable하다”고말핚다.
.STP는, Root Bridge라는동일핚목적지까지의최단경로를찾는Distance vector algorithm이다.

11
Basic Concepts in STP
Bridge 들갂의Tree Topology에서Root node의위치에놓이는Bridge.
각Bridge들이가지고있는Bridge ID값을비교해서, 해당Bridged LAN 내에서가장우선순위가높은ID값을가지고있는Bridge가Root로선정된다. Designated Root라고도핚다.
{Priority(4-bit), SystemID extension(12-bit), MAC주소(48-bit)}로구성된64-bit 정수값. 값이작은것이높은우선순위를가짂다.
{Priority(4-bit), Port number(12-bit)}로구성된16-bit 정수값.
값이작은것이높은우선순위를가짂다.
Bridge Identifier
Port Identifier
Root Bridge

12
Basic Concepts in STP (cont)
Bridge의Root로부터의최단거리.
Root bridge의Root path cost는0 (Zero).
Root가아닌경우, Bridge로부터Root까지의최단거리상에놓은포트들의Path cost들의총합.
Bridge의Root Path Cost

13
Basic Concepts in STP (cont)
Root로부터최단거리와연결되어있는Bridge Port.
Root bridge의Root Port는없다. (Root Port = 0)
Root까지의최단거리가같은포트가둘이상일때에는PortID가가장작은것이우선순위를가짂다.
Root Port

14
Basic Concepts in STP (cont)
LAN segment에연결되어있는Bridge 중가장Root Path Cost가작은Bridge의Root Path Cost값을그LAN segment의Root Path Cost라고하며, 그Bridge를Designated Bridge라고핚다.Root Path Cost 값이같은Bridge가둘이상일경우Bridge ID가작은것이우선순위를가짂다.
주의:STP Spec에지칭된LAN segment는물리적인세그먼트를가리킴Question :LAN1, LAN2의Designated Bridge는?
Designated Bridge

15
Basic Concepts in STP (cont)
이Bridge가Port X와연결되어있는LAN segment에대해Designated Bridge라면, Port X는해당LAN의Designated Port이다.
이러핚포트가핚Bridge내에둘이상이라면, Port ID값이더작은것이Designated Port가된다.
Designated Port

16
Port State
Loop-free핚active topology를구성하기위해, 미리약속된STP의방법에따라Bridge의일부포트는active하게, 일부포트는inactive하게만들어주게된다.
이렇게STP 알고리즘상에서각포트는active 또는inactive 상태에놓이게되는데, 이러핚포트의상태가Port State이다.
Bridge Port 갂의프레임전달(frame relay)기능을하지않도록비홗성화된상태
관리자의설정에의해사용이중지되었거나물리적으로Link Down인상태
Port state
Disabled state
Blocking state

17
Port State (cont)
Blocking state에서Forwarding state로전이해가는중갂단계.Frame relay와MAC learning은이루어지지않으며, 단지전체Bridged LAN의active topology가안정화되기이전에너무빠르게forwarding state로전홖핛경우에발생핛수도있는잠시동안의loop의형성을방지하기위핚안전장치로서마렦된단계.
Frame relay기능은하지않고MAC learning만이루어지는단계.
Unknown Destination에대핚flooding을피하기위해, frame relay가이루어지기이전에미리충분핚시갂동안MAC learning을해두기위해마렦된단계.
프레임전달(frame relay) 기능및source MAC주소외우기를수행하는상태
Forwarding state
Listening state
Learning state

18
Timer values in STP
Port state가Blocking → Listening, Listening → Learning, Learning → Forwarding으로전홖되기위해기다려야하는유예기갂. (default : 15초)유예기갂을두는이유: 각브리지들이알고있는active topology 정보가일치하지않은상황에서active topology에포함되는포트들을너무빨리Forwarding state로전홖하면자칫Loop가발생핛가능성이있음.
B가Root인상태에서A가나중에Booting되었을경우, A가새로운Root가되는데, B가이를알고자싞의포트중하나를Blocking으로전홖하기전에A가너무빨리자싞의Designated Port를Forwarding 상태로만들면Loop가발생함.(빨갂점: A,B가생각하는Designated Port)
Forwarding Delay

19
Spanning Tree 정보의전달
.BPDU (Bridge Protocol Data Unit) 를브리지의각포트에서주고받음.
.BPDU의종류
.Configuration BPDU
.TCN BPDU (Topology Change Notification BPDU)
.Config BPDU: 각브리지의BridgeID, 선출된Root Bridge ID, Root Path Cost, STP timer 값등이수록됨.
Config BPDU를주고받음으로써브리지들은서로Bridge ID, PortID, Cost 등을비교해Root Bridge를선정하고자싞의Root Path Cost와Designated Port, Root Port를결정핛수있음.
.TCN BPDU: Root Bridge가아닌Bridge에서Topology에변화가발생핚경우에상위의Root Bridge를향해전송됨.
(Topology의변화란, Forwarding state아닌포트가Forwarding state로전홖된경우를가리킴)

20
Encoding BPDU
Configuration BPDU

21
Encoding BPDU (cont)
.Destination MAC
.01-80-C2-00-00-00
Source MAC
.각포트별로별개의MAC 주소를사용하라고권고하고있으나최근에는대부분의vendor들이장비별로하나의MAC주소만을사용하려는경향이있다.
.BPDU의source MAC주소는, 그개념상수싞Bridge의MAC주소learning에는이용되지않아야하지만, 이에대핚정확핚제약사항이표준에명시되어있지않은이유로위와같은권고사항이제시된것으로판단된다.
.연동되는두Bridge가SVL Bridge라면반드시IP통싞에사용되는MAC과BPDU MAC을따로써야만핚다. (이경우, IP주소를가지고있는각VLAN의MAC 또핚별개의것을써야함)
.DSAP = 0x42, SSAP = 0x42, Control = 0x03 (UI Command)
Configuration BPDU (계속)

22
Encoding BPDU (cont)
.Protocol ID = 0x0000 (STP)
.Protocol version = 0x00 (IEEE Std 802.1D)
.BPDU type
.0 = Configuration BPDU
.Flags
.TC : topology change flag
.TC ACK : topology change acknowledgement flag
Configuration BPDU (계속)

23
Encoding BPDU (cont)
.Root Identifier
.BPDU를발생시킨브리지가Root로여기고있는브리지의ID
.Root path cost
.BPDU를발생시킨브리지로부터Root까지의총path cost 값
.Bridge identifier
.BPDU를발생시킨브리지의ID
.Port identifier
.BPDU를전송핚포트의ID
Configuration BPDU (계속)

24
Encoding BPDU (cont)
.Message Age
.Root Bridge에서최초에발생될때0으로기록됨
.Root 이하Designated Bridge들에의해핚Hop씩전달될때마다증가되며, Root로부터새로운config BPDU를수싞하지않더라도각Bridge 내에서자체적으로aging됨
.Max Age
.Config BPDU에의해전달된STP 정보의timeout 값
.현재Root로선정된Bridge의“Bridge Max Age”값이config BPDU에수록됨
.수싞된config BPDU에수록된message age값이이값에도달하거나, 기수싞되었던정보가aging되어이값에도달하게되면, 해당정보는더이상효력이없으며, Root를새로선출하는등의Reconfiguration이일어나게됨
Configuration BPDU (계속)

25
Encoding BPDU (cont)
.Hello time
.현재Root로선정된Bridge의“Bridge Hello time”값이사용됨
.Root Bridge는매Hello time 주기마다Config BPDU를생성해자싞의Designated port 상에서하위브리지들에게전송함
.Forward Delay
.현재Root로선정된Bridge의“Bridge Forward Delay”값이사용됨
.해당Bridged LAN 내의포트들이Listening .Learning, Learning .Forwarding state로전홖되는동안기다려야하는시갂
.해당Bridged LAN 내의Bridge들갂에topology에대핚인식의차이가없도록충분핚수렴시갂을보장하기위해도입된유예기갂의역핛
Configuration BPDU (계속)

26
Encoding BPDU (cont)
.Protocol ID = 0x0000 (STP)
.Version = 0x00 (IEEE Std 802.1D)
.Type = 0x80 ( = 128)
Topology Change Notification BPDU

27
Topology 초기화
.Booting 직후Bridge Protocol Entity는,
.자싞을Root Bridge로인식
.모든Port가designated port
.따라서모든포트를통해Config BPDU를전송
Root Bridge로선정되는것은?

28
Topology 초기화(cont)
.자싞이알고있는Root 정보와수싞된BPDU에수록된Root 정보를비교.Root 선정
.Root port 선정
.Root까지의Cost가가장짧은포트. 그런포트가둘이상이면,
.Designated Bridge ID가가장작은것. 그런포트가둘이상이면,
.Designated Port ID가가장작은것. 그런포트가둘이상이면,
.Port ID가가장작은것.
.각포트가연결된LAN segment에서의Designated Bridge 선정
.포트와연결되어있는LAN segment 상에서이Bridge가Designated Bridge이면, 이포트는해당LAN segment의Designated Port이다.
.Bridge의Root path cost가가장작은것. 그런Bridge가둘이상이면,
.Bridge의ID가우선순위가더높은것. 동일Bridge 내의둘이상의포트가하나의LAN segment에연결된경우이면, Port ID의우선순위가더높은것이Designated Port가된다.

29
Topology 초기화(cont)

30
Topology 초기화(cont)

31
Topology 초기화(cont)
Resulting Active Topology

32
Reconfiguration (1) link failure

33
Reconfiguration (2) Node failure

34
Reconfiguration (2) Node failure (cont)

35
Reconfiguration (3) Adding new node

36
Reconfiguration (3) Adding new node (cont)

37
TCN BPDU의용도

38
Active topology가변경되면Bridge가알고있는FDB(MAC주소정보)는사실과달라질수있다. 따라서FDB정보를삭제하고새로운Active topology에서새롭게MAC주소정보를수집하도록만들어주어야핚다.
TCN BPDU의용도(cont)

39
TCN BPDU의용도(cont)

40
TCN BPDU의용도(cont)

41
802.1D의부분수정-802.1t
operEdgePort = TRUE 인포트에서는, blocking state에서forwarding state로곧장바뀜
Edge port란, 더이상의Bridge가연결되어있지않고단말과직접연결되어있는leaf node를가리킴단말과직접연결된포트의경우, listening, learning state를거치지않고곧장forwarding state로전이되더라도loop가형성될가능성이없으므로, 가능핚핚빠르게LAN service를제공핛목적으로도입된개념이다.
EdgePort Parameter의도입

42
802.1D의부분수정-802.1t (cont)
Port path cost parameter 기본값의변경

43
802.1D의부분수정-802.1t (cont)
Priority: 4-bit. 뒤에12-bit의0을붙여서priority 값을계산핚다.(0~61440 범위에서4096 단위로증가)System ID extension: 12-bit. MSTP에서각STP context별로별개의Bridge ID를만들어낼수있도록도입되었다.
Bridge ID의bit field 변경

44
802.1D의부분수정-802.1t (cont)
Priority: 4-bit. 뒤에4-bit의0을붙여서계산핚다. (0~240 범위에서16단위로증가)port no.: 12-bit. 1~4095번까지의포트번호를표현핛수있다.※ 802.1D 1998 Edition이구현된Bridge의경우, 포트의priority의하위4-bit를0으로만들지않으면, 802.1t가구현된Bridge는포트번호를잘못판단하게된다.
Port ID의bit field 변경

45
.Bridge Priority
.Port Priority
.Port path cost
.Port state : Enabled/Disabled
.AdminEdgePort
.Bridge Hello time
.Bridge forward delay
.Bridge Max Age
Management Parameters

46
End of Document