[컴퓨터네트워크] 스패이닝트리(spanning tree)

목차

1. 스패닝트리
1.1 스패닝트리와 브릿지
1.1.1알고리즘
1.1.2루트 포트 찾기
1.1.3지정 브릿지 선택
1.1.4스패닝트리구성
1.2스패닝트리와 멀티캐스트라우팅

본문내용

스패닝 트리(spanning tree) 알고리즘은 그래프로부터 트리를 만드는 데이터 구조에 사용된다. 트리는 모든 교점(노드)을 포함하고 있으며 이러한 교점은 최소의 에지(edge,라인)로 연결되어 있다. 모든 교점은 스패닝 트리의 루트(root)로 사용될 수 있다. 하나의 특정 루트를 선택한후 루트와 각 교점을 연결하는 선택된 가지(banch)의 집합을 기반으로 하는 여러 가지 스패닝 트리를 만들 수 있다. 그러나 루트를 선택한 후에, 일반적으로는 루트에서 각 교점과 최소의 경로를 가지는 하나의 특별한 스패닝 트리만을 다룬다. 최소 경로는ㄴ 어떤한 교점에서 루트까지 가중치의 함으로 결정된다. 만약 그래프에서 가중치가 없다면
각 에지에는 1의 가중치가 할당된다.

1.1 스패닝 트리와 브릿지

브릿지가 동작하지 않은 경우를 대비하기 위해 LAN 세그먼트는 일반적으로 하나 이상의 브릿지와 연결되어 있다. 그러나 하나의 브릿지로 패킷이나 여러 패킷의 복사본이 이동되는 과정에서 대체경로의 생겅이 무한히 반복될 수 있다. 간단한 예를 들어보자. 그림 1,2에서 2개의 LAN 세그먼트는 2개의 브릿지(Br1,Br2)로 연걸되어 있다.

참고자료

· 없음