1. 스패닝 트리 개요
  스패닝 트리란 n개의 정점으로 이루어진 무방향 그래프 G에서 n개의 모든 정점과 n-1개의 간선으로 만들어진 트리로 사이클이 없다. 즉, G안에 있는 모든 정점을 다 포함하면서 최소의 간선을 이용하여 연결한 그래프이다.

스패닝 트리는 다음과 같은 성질을 가진다.
① 그래프 내에 원래 있던 간선들만을 포함 한다
② 정점의 수가 n일때 n-1개의 간선만을 포함 한다
③ 순환 (cycle)이 있어서는 안된다



2. 스패닝 트리 알고리즘
  스패닝 트리 알고리즘(Spanning Tree Algorithm)이란 스위치나 브리지에서 발생할 수 있는 루핑을 미리 막기 위해 두 개 이상의 경로가 발생하면 하나를 제외하고 나머지 경로들을 자동으로 막아두었다가 만약 기존 경로에 문제가 생기면 막아놓은 경로를 풀어서 데이터를 전송하는 알고리즘이다.

  그림 1에서는 스패닝트리 알고리즘을 적용한 네트워크의 예를 보여주고 있다.

3) 지정 포트 (Designated port)
  사용자 입장에서 Root Bridge로 갈 수 있는 최저 경로 포트를 의미한다. 즉 브리지 또는 스위치 간에 연결된 링크에서 한 포트는 지정포트로 설정을 해야 된다. (=Segment당 하나씩의 Designated Port를 갖는다.)

4) Non Designated port
  Blocking 상태로서 데이터 전송이 이루어지지 않게 된다. (링크가 끊어짐)
 

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

  해밍코드(Hamming code)는 오류를 검출한 후 교정까지 할 수 있는 코드이다.
  해밍코드 조건식은 2^p ≥ m + p + 1 이다. 예를 들어 7개의 정보 비트가 있을때, p=3 이라고 가정해보자. 그러면 8 ≥ 7 + 3 + 1 은 성립하지 않는 식이 된다. p=4 라 가정하면 16 ≥ 7 + 4 +1 은 조건을 만족하는 식이 된다.
  따라서 정보비트의 수는 7, 패리티 비트 수는 4가 되는 것이다.

-P1 : 1,3,5,7,9,11
-P2 : 2,3,6,7,10,11
-P3 : 4,5,6,7
-P4 : 8,9,10,11

  짝수 패리티의 경우 P1,P2,P3,P4 각각의 비트 번호에 해당되는 정보비트를 읽어서 1이 짝수이면 0이 패리티, 1이 홀수이면 1이 패리티 비트가 된다. <표1>처럼  패리티 비트와 정보 비트를 순서대로 나열하면 해밍코드가 되는 것이다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.