[네트워크] Bridge and Bridging

28 Oct 2018

Reading time ~9 minutes

들어가기 전에

세상에는 많은 상호 연결(inter-connection)을 위한 장비가 많습니다. 잠시 앞에서 한 내용을 짚고 넘어가도록 하면 리피터(Repeater)는 물리 영역인 레이어 1의 영역에 있는 것으로 하나의 포트에서 받은 내용을 다른 포트로 복사하도록 합니다. 그리고 이 복사 시에는 비트 단위로 진행하게 됩니다. 그리고 오늘 배우는 브리지(Bridge)는 데이터 링크 레이어로 레이어 2의 영역에 해당합니다. 이는 하나의 포트에서 받은 내용은 다른 쪽으로 넘겨주나 데이터를 비트 단위가 아닌 프레임 단위로 보내게 됩니다. 따라서 반드시 프레임을 위한 버퍼가 있어야 합니다. 그다음으로 IP(Network) 레이어를 위한 라우터가 있습니다.

브리지

브리지(Bridge)는 아래 그림과 같이 생겼고 이를 보고 허브(HUB), 스위치(switch) 등의 이름으로 부릅니다.

bridge

이러한 브리지는 플러그 앤드 플레이(Plug & Play, self-configuration)를 지원하는 장치입니다. 여기서 플러그 앤드 플레이는 그냥 선을 꽂으면 바로 사용할 수 있음을 의미합니다. 그리고 위에서 언급한 허브, 브리지를 좀 더 자세히 설명하면 허브와 브리지는 같은 다중 포트 리피터로 하나의 포트로 데이터가 오게 되면 다른 모든 포트로 보내주는 역할을 합니다. 하지만 여기서 허브의 경우에는 갈 곳을 특정하지 않고 바로 보내도록 하지만 브리지의 경우는 좀 더 지능적으로 데이터를 보내도록 합니다. 어떻게 지능적인지 이제 보도록 하겠습니다.

이를 제대로 이해하기 위해서는 리피터에 관해서 제대로 알아야 합니다. 먼저 증폭기(amplifier)와 리피터는 어떤 차이가 있을까요? 증폭기는 아날로그 값을 증폭하며 원래의 데이터 내용을 신경을 쓰지 않습니다. 이러한 특징으로 잡음도 같이 증폭되는 특징이 있습니다. 하지만 리피터는 디지털 값을 증폭하며 원래의 데이터 내용을 신경을 씁니다. 이러한 특징으로 원래의 신호를 재생성을 할 수 있는 특징이 있습니다.

리피터하고 증폭기

그리고 이러한 리피터에는 다중 포트 리피터가 있습니다. 이러한 리피터는 어느 포트에서 받은 신호를 다른 모든 포트로 신호를 재생성해서 보내는 특징이 있습니다. 또한, 이러한 리피터를 이해하기 위해서는 네트워크의 형상(Topology)을 잘 이해해야 합니다. 이러한 네트워크의 형상으로는 아래와 같은 것들이 있습니다.

네트워크 형

허브

허브는 다중 포트 리피터의 일종으로 레이어 1 장치에 해당합니다. 이는 별 모양 형상(Star Topology)을 가지고 있습니다. LAN(Local Area Network)을 구축하는 데 사용합니다.

허브 구성

위 사진이 일반적인 허브를 통한 네트워크 구축 모습입니다. 위와 같은 허브 네트워크에서 A가 데이터를 보내면 M도 받을 수 있습니다. 이러면 허브만 사용해서 네트워크를 구축하면 될 것 아니냐고 할 수도 있지만 이러한 허브의 치명적인 문제가 있는 데 만약 A가 데이터를 M에게 보내는 동시에 C가 어느 다른 누군가에게 보내게 되면 충돌이 일어나게 됩니다. 즉, 같은 허브 네트워크에 속한 장치들이 같은 시간에 전송을 수행하면 충돌을 겪을 수 있다는 것입니다. 결과적으로 허브는 능동적인 트래픽 제어가 없다고 할 수 있습니다. 따라서 이러한 허브는 큰 네트워크에서 사용하기는 어렵고 작은 네트워크 환경에서의 사용에 좋습니다.

스위치

스위치는 또한 다중 포트 리피터입니다. 하지만 허브와 달리 어떠한 지능을 가진 능동 장치라고 할 수 있습니다. 지능을 가졌기 때문에 네트워크를 보조하는 소프트웨어가 있으며 이러한 소프트웨어는 불필요한 전송을 줄여주고 트래픽의 충돌을 막아주도록 합니다. 즉, 능동적인 트래픽 제어가 있다고 할 수 있습니다. 이러한 스위치는 동시에 다중 연결을 지원하고 필요로 하는 위치로만 데이터를 보내도록 합니다.

스위치

브리지/LAN 스위치는 2개 또는 그 이상 LAN의 상호 연결을 해주거나 이러한 네트워크들 사이에 패킷을 보내는 장치입니다. 이러한 브리지/LAN 스위치는 데이터 링크 계층(레이어 2)에서 동작하도록 합니다. 2개의 LAN을 연결할 때 브리지 같은 경우에는 플러그 앤드 플레이로 그냥 연결만 하면 끝이지만 라우터는 서브넷 설정 등의 네트워크 설정을 필요로 합니다.

브리지의 구현

이러한 브리지의 최종 설계 목표는 완벽한 투명성(transparency), 플러그 앤드 플레이를 지원하고자 합니다. 그리고 이러한 지원은 소프트웨어에 의해 구현이 됩니다.

일반적으로 네트워크 사이에는 포워딩이 필요로 합니다. 라우터에도 포워딩 테이블이 있듯이 브리지에도 이러한 포워딩이 있어야 합니다. 이를 바탕으로 소프트웨어적인 구현의 접근 방법으로 3가지가 있습니다.

고정 라우팅(Fixed Routing) : 수동적으로 목적지를 하나씩 적어주도록 합니다.
소스 라우팅(Source Routing) : 소스(Source)가 갈 곳을 지정해주는 방식입니다. 이를테면, B1, B3, B5를 지나서 갈 때는 B1 B3 B5 DATA 형식의 데이터 양식으로 보내주면 되는 방법입니다.
신장 트리 라우팅(Spanning Tree Routing) : 이는 IEEE 802.1d로 표준화된 방법입니다.

일반적으로 브리지는 이 중에서 신장 트리 알고리즘을 통해서 투명한 브리지를 구현됩니다. 우리는 이것에 관해서만 알아보도록 하겠습니다.

먼저 각각의 브리지는 MAC 포워딩 테이블이 존재합니다. 이러한 포워딩 테이블은 아이피 라우터의 포워딩 테이블과 같은 역할을 합니다. 이러한 테이블에는 MAC 주소, 포트, 나이가 들어갑니다. 여기서 각각을 알아보도록 하겠습니다.

MAC 주소 : 호스트 이름 또는 그룹 주소가 들어갑니다.
포트 : 브리지의 포트 번호가 들어갑니다.
나이 : 테이블에 엔트리(Entry)가 들어온 이후 지난 시간을 의미합니다.

여기서 나이가 많은 엔트리 같은 경우에는 지워지게 됩니다. 일반적으로 삭제는 15초 정도 사용이 없으면 삭제가 되게 됩니다. 아래와 같은 구성을 가진 브리지에서 어떤 포트 x로 MAC 프레임이 들어왔다고 가정해보겠습니다.

브리이잇지

포트 x로 프레임이 들어오게 되면 포트 A, B, C 중에서 포워딩 테이블에 목적지의 MAC 주소가 적힌 테이블을 찾도록 합니다. 만약 찾으면 적합한 포트로 프레임을 보내주도록 합니다. 만약 찾지 못한 경우에는 전체 포트로 프레임을 보내주도록 합니다. 이를 홍수(Flood)라고 합니다.

이러한 포워딩 테이블을 작성하는 방식은 절대로 수동적으로 작동이 일어나지는 않습니다. 그 방식을 이야기하자면 위 그림에서 포트 x에 있는 호스트 X가 포트 B에 있는 호스트 B에게 프레임을 보낸다고 하겠습니다. 그 경우 아래와 같은 일이 벌어집니다.

프레임의 소스를 통해서 위 그림의 브리지는 호스트 X를 알 수 있게 됩니다.
만약 호스트 B의 위치를 브리지가 모른다고 할 때는 입력된 포트를 제외하고 아까 이야기한 홍수를 일으키게 됩니다.
홍수에 의해서 호스트 B가 프레임을 받고 호스트 X에게 응답하는 프레임을 받게 됩니다.
브리지는 해당 프레임의 소스를 통해서 호스트 B도 알 수 있게 됩니다.

이렇게 브리지는 포워딩 테이블을 구성한 이후로는 브리지는 호스트 X가 다시 호스트 B에게 보내면 바로 보내줄 수 있게 됩니다. 하지만 이는 브리지가 하나만 있는 경우입니다. 만약 2개 이상이 있는 경우에는 루프가 발생이 할 수가 있습니다. 아래의 그림을 보겠습니다.

이 경우 다음과 같은 일이 벌어질 수 있습니다.

호스트 A가 B에게 프레임을 보냅니다.
브리지 A는 호스트 A의 엔트리를 포워딩 테이블에 넣고 프레임을 호스트 B로 보냅니다. 동시에 브리지 B도 같은 행동을 하게 됩니다.
브리지 A에 의해서 받아진 프레임은 호스트 B의 위치를 모르기에 홍수가 벌어집니다. 이와 동시에 B도 같은 행위를 하게 됩니다.
브리지 A에서 보내어진 프레임을 브리지 B가 받아서 호스트 A가 호스트 B 위치에 있다고 테이블을 갱신하게 됩니다. 그리고 브리지 A도 브리지 B에서 보내어진 프레임으로 같은 갱신을 하게 됩니다.

이러면 호스트 B의 응답이 오고도 호스트 A의 위치는 잘못된 위치를 가리키기 때문에 브리지는 루프(loop)에 빠지는 문제가 발생하게 됩니다. 이를 해결하는 방법으로 첫 번째는 물리적으로 브리지의 구성을 루프가 없도록 만들도록 합니다. 두 번째는 루프가 논리적으로 발생하지 않도록 포워딩 테이블을 만들도록 합니다. 첫 번째 방법은 사실상 불가능한 방법이니 저희는 두 번째 방법을 사용하도록 하겠습니다.

이런 두 번째 방법을 위해서 우리는 논리적으로 사이클(cycle)이 없는 트리(tree)를 만들어야 하고 이 트리를 신장 트리라고 합니다. 이 신장 트리를 만드는 방법에 관해서 자세히 알고 싶으시면 Horowitz, Sahni, Anderson-Freed가 작성한 Fundamentals of Data Structures in C를 참고해주시길 바랍니다.

이러한 신장 트리는 아래와 같이 정의됩니다.

임의의 서브 그래프 \(T\)가 그래프 \(G = (V, E)\)의 신장 트리가 되려면 \(T\)는 트리이고, \(V(T)=V(G)\)를 만족한다.

여기서 \(V, E\)는 각각 정점과 간선을 의미합니다. 이런 신장 트리를 만드는 탐색 방법으로는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Bread-First Search)이 있습니다.

Minimal-Cost Spanning Tree

그리고 이러한 실세계의 간선에는 어느 일정한 비용(e.g. 거리)이 존재합니다. 따라서 비용을 최소화하려면 최소 비용 신장 트리(Minimal-Cost Spanning Tree)를 만들어야 합니다. 이것은 아래와 같이 정의됩니다.

임의의 그래프 \(G\)가 가중치 그래프에 대해 \(T\)가 최소 비용 신장 트리가 되려면 그래프 \(G\)에 의한 다른 신장 트리에 \(T^{\prime}\)에 \(C(T)\)< \(C(T^{\prime})\)을 만족해야 한다.

이러한 최소 비용 신장 트리를 만들기 위해서 그리디 알고리즘(Greedy Algorithm)의 일종인 크루스칼 알고리즘(Kruskal’s Algorithm)과 프림 알고리즘(Prim Algorithm)이 사용됩니다. 전자는 전체 그래프에서 가장 비용이 작은 간선부터 순서대로 루프가 발생하지 않게 잡아가는 과정입니다. 전자를 의사 코드(Psuedo Code)로 작성하면 아래와 같이 작성 가능합니다.

T = 공집합;
E = 간선의 집합;
n = 정점의 개수;
while(T가 n-1개 미만의 간선 포함 && E가 비어있지 않음){
    E에서 최저 비용 간선 (v, w) 선택;
    E에서 (v, w)를 삭제;
    if((v, w)가 T에서 사이클을 형성하지 않음)
        (v, w)를 T에 추가;
    else
        (v, w)는 무시;
}
if(T가 n-1개 보다 적은 간선을 포함)
    printf("스패닝 트리가 없습니다.\n");

후자를 의사 코드로 작성하면 아래와 같이 작성 가능합니다.

T = 공집합;
TV = {0}; // 시작 정점 번호 설정(0)
n = 정점의 개수;
while(T의 간선수가 n-1보다 적음){
    u가 TV의 부분 집합, v가 TV의 부분 집합이 아닌 최저 비용 간선 (u, v) 선택;
    if(간선을 선택하지 못함) break;
    v를 TV의 부분 집합에 추가;
    (u, v)를 T에 추가;
}
if(T의 간선 수가 n-1보다 적음)
    printf("스패닝 트리가 없습니다.\n");

Spanning Tree in Bridging

이렇게 신장 트리를 만들게 되면 모든 LAN 사이에서 루프가 없이 경로를 만들 수 있습니다. 그리고 이러한 브리지는 각각의 루트 브리지를 찾고 루트 포트를 구축하기 위해 BPDU(Bridge Protocol Data Unit)라고 IEEE 802.1D로 표준화된 특별한 설정 메시지를 사용해서 만들도록 합니다.

간략하게 어떻게 돌아가는지 알려드리면

루트(root) 브리지를 선택합니다.
브리지의 신장 트리를 계산해서 루트 포트를 찾습니다.
LAN 구획(segment)에서의 신장 트리를 계산해서 지정 포트(Designated Ports)를 찾습니다.

이런 방식을 통해서 진행되게 됩니다. 좀 더 용어를 파고들어 보면

루트 브리지 : 브리지들의 신장 트리의 루트가 됩니다.
루트 포트 : 각각의 브리지는 하나의 루트 포트만 가지고 포트는 루트에서 가장 적합한, 가까운, 짧은 포트를 찾습니다.
지정 브리지 : 각각의 LAN 구획이 가지는 것으로 가장 루트에 가까운 브리지를 의미합니다.
지정 포트 : 지정 포트는 지정 브리지의 LAN 구획에서 루트로 가는 포트를 의미합니다. 이러한 브리지는 여러 개의 LAN 구획을 가진다면 각각의 지정 브리지에 의해서 여러 개를 가질 수 있습니다. 유의 사항으로 루트 포트는 지정 포트가 될 수 없습니다.

그리고 이 경우에 브리지 간의 신장 트리만을 보는 것이 아니라 LAN 간의 신장 트리도 살펴봐야 합니다. 이러한 신장 트리를 구성할 때 가장 ID 값이 적은 것을 루트로 하도록 합니다.

BPDU

BPDU는 IEEE 802.1D로 표준화되어 있습니다. 이러한 BPDU의 프레임을 살펴보면 목적지 MAC 주소, 소스 MAC 주소, 설정 메시지로 구성되어 있습니다. 여기서 중요한 내용은 설정 메시지의 루트 ID, 비용, 브리지 ID, 포트 ID가 됩니다. 여기서 루트 ID는 송신 브리지가 생각하는 루트 브리지 ID를 의미하고, 비용은 송신 브리지에서 루트까지의 거리 비용을 의미합니다. 브리지 ID는 보내는 브리지의 ID를 의미하며, 포트 ID는 송신 브리지에서 수신 브리지로 보내는 포트의 ID를 의미합니다.

예를 들어, Bridge 1-Bridge 2-Bridge 3과 같이 브리지가 구성된 경우를 생각해보도록 하겠습니다. Bridge 1은 Bridge 2에 BPDU로 17, 0, 17, 1을 보내도록 합니다. 이를 받음과 동시에 Bridge 2는 Bridge 1과 Bridge 3롤 13, 0, 13, 0, 13, 0, 13, 1을 보내도록 합니다. 이렇게 하면 Bridge 1은 본인의 ID가 더 적으므로 Bridge 2를 루트로 바꾸도록 합니다. 그렇게 되면 이제 Bridge 2에 BPDU를 보내면 13, 1, 13, 1로 보내도록 합니다.

이를 통해서, 신장 트리를 빠르게 구축해나갈 수 있습니다. 그리고 여기서 알 수 있듯이 브리지의 ID는 우선순위라고 할 수 있습니다. 여기서 브리지의 ID는 2바이트의 데이터입니다. 이에 반해, 브리지의 MAC은 6바이트의 데이터입니다.

여기서 알 수 있는 사실은 최소 비용 신장 트리를 통해서 신장 트리를 구축하는 것은 사실상 불가능함을 알 수 있습니다. 왜냐하면, 전체 네트워크의 비용을 알아야만 하므로 사실상 이는 실세계에서 불가능한 일이기 때문입니다. 그래서 실제로 신장 트리를 구축할 때에는 최단 거리 신장 트리를 구축하여 해결하도록 합니다. 이를 위해서 분산 벨만 포드 알고리즘(Distributed Bellman-Ford algorithm)를 사용합니다. 이러한 분산 벨만 포드 알고리즘은 아래와 같이 동작하게 됩니다.

추측 : 유일한 정점 노트 s가 있다고 합니다.
각각의 정점은 주기적으로 s로부터의 거리를 주변에 알리도록 합니다. 만약 루트이면 \(dist_s = 0\)으로 보냅니다.
루트를 제외한 정점은 \(dist_v = min\{dist_u + cost_uv \mid u\ is\ neighbor\ to\ v\}\)로 보냅니다.
이웃 중에 가장 짧은 거리를 가진 정점을 부모로 저장합니다.

여기서 3, 4를 하면서 각 정점은 정점까지의 거리와 부모의 포인터를 가지게 됩니다. 아래가 분산 벨만 포드의 동작 예입니다. 해당 예에서 모든 비용은 1이라 가정하겠습니다.