네트워크(2)

윤휘영·2024년 4월 29일

4. 네트워크 계층

4.2 네트워크 계층 프로토콜

4.2.2 IPv4 주소

TCP/IP에서 각 장치가 인터넷으로의 연결을 확인하는 IP 계층에서 사용되는 식별자를 IP 주소의 인터넷 주소라고 한다. IPv4 주소는 32비트 주소로 라우터나 호스트의 인터넷 연결을 범용적이고 유일하게 만들어 준다. IP 주소는 장치가 다른 네트워크로 이동 시 변경되기 때문에 라우터나 호스트가 아닌 연결의 주소이다.

주소 공간
주소를 정의하는 IPv4와 같은 프로토콜은 주소 공간을 가진다. 주소 공간은 프로토콜에서 사용 가능한 전체 주소의 수이다. IPv4는 32비트의 주소를 사용하므로 주소 공간은 2^32(40억 이상)이 된다.

표기법
IPv4 주소를 나타내기 위해 2진수 표기법, 점 10진수 표기법, 16진수 표기법을 사용할 수 있다.

계층적 구조
32비트의 IPv4 주소는 두 부분으로 구분되는 계층적 구조이다. 주소의 첫 번째 부분은 프리픽스로 네트워크를 정의하고, 주소의 두 번째 부분은 서픽스로 노드를 정의한다. 프리픽스의 길이는 n비트이고 서픽스의 길이는 32 - n비트이다.

클래스 기반의 주소지정
인터넷이 시작될 당시 IPv4 주소는 소규모 및 대규모 네트워크를 지원하기 위해 한 가지가 아닌 세 가지의 고정된 프리픽스(8, 16, 24)로 설계되었다. 전체 주소 공간은 5개의 클래스(A, B, C, D, E)로 구성된다. 이를 클래스 기반 주소지정(classful addressing)이라 한다.

8비트 프리픽스의 처음 비트가 0이면 A 클래스이다.

16비트 프리픽스의 처음 두 비트가 10이면 B 클래스이다.

24비트 프리픽스의 처음 세 비트가 110이면 C 클래스이다.

클래스 D와 E는 프리픽스와 서픽스로 구분되지 않으며 예약된 주소이다.

1) 주소 고갈

적절히 주소가 분배되지 않아 인터넷 연결을 할 수 있는 주소가 남지 않은 현상이다.

2) 서브네팅과 수퍼네팅

주소 고갈을 완화하기 위한 기술이다. 적용되지는 않았다.

3) 클래스 기반 주소지정의 장점

주소가 주어지면 클래스의 프리픽스가 고정되어 있기 때문에 주소의 클래스를 쉽게 찾고, 프리픽스의 길이를 즉시 알 수 있는 하나의 장점이 있다.

클래스 없는 주소지정
클래스 없는 주소지정의 프리픽스는 가변적이다. 작은 프리픽스는 큰 네트워크를, 큰 프리픽스는 작은 네트워크를 의미한다.

1) 프리픽스 길이: 슬래쉬 표기법

프리픽스의 길이가 주소에 포함되어 있지 않으므로 프리픽스의 길이를 따로 주어야 한다. 이 경우 프리픽스의 길이 n은 슬래쉬로 구분하여 주소에 추가된다. 이 표기법은 CIDR(classless interdomain routing)이라 한다.

2) 특수 주소

This-host 주소: 0.0.0.0/32 블록에 있는 주소는 this-host 주소라고 한다. 이 주소는 호스트가 IP 데이터그램을 보내려고 하지만 발신지 주소인 자신의 주소를 모를 때 사용한다.
제한된 브로드캐스트 주소: 255.255.255.255/32의 주소는 호스트나 라우터가 네트워크 상의 모든 장치로 데이터그램을 보낼 때 사용한다. 그러나 네트워크 상의 라우터가 이런 패킷을 차단하기 때문에 네트워크 외부로는 패킷을 보낼 수 없다.
루프백 주소: 127.0.0.0/8 내의 주소를 가진 패킷은 호스트를 벗어나지 않고 호스트에 남게 된다.
사설 주소: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/26, 169.254.0.0/16의 네 개의 블록이 사설 주소로 지정되어 있다. 이는 NAT에서 쓰인다.

DHCP(dynamic host configuration protocol)
큰 기관이나 ISP는 ICANN으로부터 직접 주소의 블록을 할당받고 작은 기관은 ISP로부터 주소의 블록을 할당받을 수 있다. 주소의 블록이 기관에 할당되고 나면, 네트워크 관리자가 개개의 호스트나 라우터에 수동으로 주소를 할당한다. 그러나 DHCP를 사용하여 기관 내의 주소지정을 자동으로 할 수 있다. DHCP는 서버-클라이언트 패러다임을 사용하는 응용계층의 프로그램으로 실질적으로는 TCP/IP의 네트워크 계층을 보조한다.

1) DHCP 메시지 형식

DHCP에서 옵션 필드는 매우 중요한 역할을 한다. 64비트의 옵션 필드는 두 가지의 목적이 있다. 옵션 필드는 추가적인 정보나 특정 벤더의 정보를 포함할 수 있다. 서버는 IP 주소에 매직 쿠키로 불리는 99.130.83.99의 값을 사용한다. 클라이언트가 메시지를 모두 읽으면 이 매직 쿠키 값을 찾는다. 만약 이 값이 존재하면 다음 60바이트는 옵션이다. 옵션은 1바이트의 태그 필드, 1바이트의 길이 필드, 그리고 가변의 값을 가지는 필드의 세 부분으로 구성된다. 벤더가 주로 사용하는 여러 개의 태그 필드가 있다. 태그 필드가 53이면, 값을 가지는 필드는 다음 그림에 있는 8개의 메시지 유형 중 하나를 뜻하게 된다.

2) 두 개의 잘 알려진 포트

잘 알려진 포트번호와 임시 포트번호의 조합 대신 68, 67번의 알려진 포트번호를 사용한다. 서버에서 클라이언트로 전달되는 메시지자 브로드캐스트 메시지이기 때문이다.

3) 오류 제어

DHCP는 비신뢰적인 서비스인 UDP 서비스를 사용한다. DHCP의 오류 제어 방식은 두 가지이다. 1) DHCP는 UDP가 사용하는 체크섬을 필요로 한다(선택사항). 2) DHCP 클라이언트는 요청에 대한 DHCP 응답을 받지 못할 경우 타이머와 재전송 정책을 사용한다.

NAT(network address transition)
NAT은 사설 주소와 범용 주소의 매핑을 제공하고 동시에 가상 사설 네트워크를 지원하는 기술이다. 이 기술은 한 곳에서 내부 통신을 위해 사설 주소를 사용하고 다른 네트워크와의 통신에는 범용 인터넷 주소를 사용할 수 있도록 해 준다. 이 작업장의 인터넷 연결은 NAT 소프트웨어를 실행하는 NAT 기능이 있는 라우터를 통해 글로벌 인터넷으로 연결된다.

위 그림에서 보듯이 사설 네트워크는 사설 주소를 사용한다. 네트워크를 글로벌 주소로 연결하는 라우터는 하나의 사설 주소와 하나의 글로벌 주소를 사용한다. 사설 네트워크는 인터넷에서 볼 수 없고 인터넷은 200.24.5.8의 주소를 사용하는 NAT 라우터만 볼 수 있다.

1) 주소 변환

NAT 라우터를 통해 나가는 모든 패킷은 발신지 주소를 글로벌 NAT 주소로 변환한다. NAT 라우터를 통해 들어오는 모든 패킷은 목적지 주소(NAT 라우터의 글로벌 주소)를 적절한 사설 주소로 변경한다.

2) 변환 테이블

나가는 패킷의 발신지 주소를 변경하는 것은 쉽게 할 수 있다. 그러나 인터넷에서 오는 패킷의 목적지를 NAT 라우터는 어떻게 아는가? NAT 라우터의 변환 테이블로 알 수 있다.

하나의 IP 주소 사용
IP 주소의 풀 사용
IP 주소와 포트번호 사용

4.3 유니캐스트 라우팅

4.3.1 일반적인 아이디어

최소비용 라우팅
가중치 그래프로 인터넷이 모델링될 때 발신지 라우터부터 목적지 라우터까지의 최적의 경로를 표현하는 방법 중 하나는 두 라우터 사이의 최소비용을 찾는 것이다. 즉 발신지 라우터는 목적지 라우터까지의 가능한 모든 경로 중에 비용 합이 가장 적은 경로를 선택한다. 그림 4.56은 A와 E 사이의 가장 최선의 경로가 비용 6을 가지는 A-B-E임을 나타낸다. 이는 각 라우터가 패킷을 이 기준에 따라 라우팅할 수 있도록 자신과 다른 모든 라우터 사이의 최소 비용 경로를 찾아야 한다는 것을 의미한다.

최소비용 트리
만약 인터넷에 N개의 라우터들이 있다면, 각 라우터에서 다른 라우터로의 (N-1)개의 최소비용 경로가 존재한다(자신을 제외한 모든 노드들까지의 최소 비용 경로를 찾아야 하기 때문에). 이것은 전체 인터넷에 대해 N x (N - 1)개의 최소비용 경로가 필요하다는 의미이다. 예를 들어 인터넷에 10개의 라우터가 있다면 90개의 최소비용 경로가 필요하다. 이러한 모든 경로를 보기 위한 더 나은 방법은 이들을 최소 비용 트리로 결합하는 것이다. 최소비용 트리는 출발 라우터를 루트로 하여 전체 그래프를 포함하고(모든 노드를 방문), 루트와 다른 모든 노드 사이의 경로가 가장 짧은 트리이다. 이렇게 하면 각 노드에 대해 하나의 최단 경로 트리만을 가질 수 있으며, 전체 인터넷에 대해 N개의 최소비용 트리를 갖게 된다. 그림 4.57은 그림 4.56에 대한 7개의 최소비용 트리를 보여준다.

4.3.2 라우팅 알고리즘

거리 벡터 라우팅
거리 벡터 라우팅에서 제일 처음으로 각 노드가 만드는 것은 인접한 이웃들의 기초 정보를 이용하여 작성된 자신의 최소비용 트리이다. 인접한 노드들 사이의 불완전한 트리는 모든 인터넷을 나타내기 위해서 더욱 완성된 트리가 되도록 수정된다. 거리 벡터 라우팅에서 라우터는 자신의 모든 이웃들에게 자신이 가지고 있는 인터넷에 대한 정보가 불완전하더라도 자신이 알고 있는 네트워크 정보를 끊임없이 알려준다.

1) 벨만 포드 알고리즘

거리 벡터 라우팅의 핵심 아이디어이다. 이 알고리즘은 출발 노드 x와 목적지 노드 y 사이의 중간 노드들(a, b, c...)을 통해 가장 적은 비용(최단거리)을 찾기 위해 사용된다. 여기서 출발 노드와 중간 노드들 사이의 비용과 중간 노드들에서 목적지까지의 비용이 주어졌을 때, 이를 통해 경로를 계산한다. 다음은 $D_{ij}$ 가 최소 거리이고, $c_{ij}$ 가 노드 i와 j 사이의 비용으로 주어질 때의 일반적인 경우이다.

일반적으로 기존의 최소 비용을 중간 노드 z를 통한 최소 비용으로 업데이트하고자 한다. 이 경우, 후자가 더 짧다면 방정식은 아래와 같이 더 간단해진다.

그림 4.58은 두 경우를 나타낸다.

만약 벨만 포드 알고리즘을 반복적으로 사용하면, 이전에 작성한 최소비용 트리로부터 새로운 최소비용 트리를 작성할 수 있다. 즉, 거리 벡터 라우팅에서 이 알고리즘을 사용하는 것은 거리 벡터 라우팅 또한 최소비용 트리를 사용한다는 것을 의미한다.

2) 거리 벡터

최소비용 트리는 트리의 root로부터 모든 목적지까지의 최소 비용 경로를 결합한다. 최소비용 경로는 트리를 구성하기 위해 묶여 있다. 거리 벡터 라우팅은 이러한 경로들을 묶지 않고, 트리를 나타내는 일차원 배열을 이용하여 거리 벡터를 생성한다.

root로부터 거리 벡터의 이름 이 결정되고, 인덱스는 목적지를 정의하고, root로부터 목적지까지의 최소비용이 각 셀의 값을 결정한다는 것에 주목하라. 거리 벡터는 최소비용 트리에서처럼 목적지까지의 경로를 제공하지는 않는다. 거리 벡터는 단지 목적지까지의 최소비용만을 제공한다.

어떻게 네트워크의 각 노드에서 해당하는 벡터를 만들 수 있는가? 인터넷에서 각 노드는 각 노드가 부팅될 때 노드의 이웃으로부터 얻을 수 있는 최소의 정보를 사용하여 매우 기본적인 거리 벡터를 만든다. 노드는 어떤 인사 메시지를 노드의 인터페이스 밖으로 전송하여 인접 노드의 정보와 자신과 이웃 사이에 대한 정보를 검색한다. 그러고 나서 노드는 찾아낸 거리를 통해 해당하는 셀에 간단한 거리 벡터를 작성한다. 그리고 다른 셀을 채우는 작업을 무한하게 수행한다.

그림의 기초적인 벡터들은 인터넷이 효율적으로 패킷을 전송하도록 돕지 못한다. 예를 들어, 대응하는 셸이 무한대의 최소비용을 나타내고 있으므로 노드 A와 G는 연결되었다고 여기지 않는다. 이런 벡터들의 효율성을 향상시키기 위해서 네트워크에서 노드들은 다른 노드들과 정보를 교환한다. 모든 노드가 벡터를 작성한 후, 인접한 모든 노드들에게 작성된 벡터의 정보를 전송한다. 노드는 이웃으로부터 거리 벡터를 전달받은 후, 벨만 포드 알고리즘을 이용하여 자신의 거리 벡터를 업데이트한다.

3) 거리 벡터 라우팅 알고리즘

링크 상태 라우팅

1) 링크 상태 데이터베이스

링크 상태 라우팅을 사용하여 최소비용 트리를 작성하기 위해 각 노드는 각 링크의 상태를 알아야 하기 때문에 네트워크의 완전한 맵이 필요하다. 링크의 상태 집합을 링크 상태 데이터베이스(LSDB)라고 한다. 전체 인터넷에 대해 LSDB는 하나만 존재한다. 최소비용 트리를 작성하기 위해 이것의 복사본을 가지고 있어야 한다. 그림 4.63은 LSDB의 예를 나타낸다.

어떻게 각 노드가 모든 인터넷에 대한 정보가 포함된 이런 LSDB를 만들 수 있는지 알아보자. 플러딩이라 불리는 과정을 통해 가능하다. 각 노드는 서로 직접 연결된 인접한 이웃들에게 노드의 정보, 비용 정보의 두 가지 정보를 모으기 위해 인사 메시지를 전송한다. 이 두 가지 정보의 조합을 LSP이라 부른다. LSP는 각 인터페이스 밖으로 전송된다. 노드가 LSP를 인터페이스의 하나로부터 전송받을 때 LSP와 이미 가지고 있던 복사본을 비교한다. 만약 새로 도착된 LSP가 기존의 것보다 오래되었다면, 새로 받은 LSP를 차단한다. 만약 LSP가 새롭거나 처음 도착했다면, 노드는 기존의 LSP를 폐기한다. 그리고 새로 전달받은 것을 보관한다. 그런 다음 LSP의 복사본을 그 LSP를 보낸 노드를 제외하고 각 인터페이스의 외부로 전송한다. 모든 새로운 LSP들이 도착한 후에 각 노드들은 종합적인 LSDB를 작성한다. 각각의 노드는 같은 LSDB를 가지고, 인터넷의 전체 맵을 보여준다.

거리 벡터 라우팅 알고리즘에서는 각 라우터가 전체 인터넷에 대해 알고 있는 정보를 이웃 라우터에게 전달한다. 반면 링크 상태 라우팅 알고리즘에서는 각 라우터가 이웃 라우터들에 대해 알고 있는 정보를 전체 인터넷에 전달한다.

2) 최소비용 트리의 형성

세 단계를 거친다.

노드는 하나의 노드를 사용하는 트리를 작성하기 위해 자기 자신을 트리의 루트로 선택하고, LSDB의 정보를 기반으로 하여 각 노드의 전체 비용을 계산한다.
노드는 트리에 속하지 않는 모든 노드들 중에서 루트와 가장 근접한 하나의 노드를 선택하고, 이것을 트리에 추가한다. 트리에 노드를 추가한 다음에 경로가 변경되었기 때문에 트리에 속해 있지 않은 모든 트리의 비용은 갱신되어야 한다.
노드는 트리에 모든 노드가 추가될 때까지 두 번째 단계를 반복한다.

5. 데이터링크 계층: 유선 네트워크

5.1 개요

네트워크 계층의 통신은 호스트 대 호스트이다. 비록 통신이 조각화와 재조립을 통해 이뤄지더라도, 데이터그램은 세계의 어떤 곳에 있는 호스트로부터 다른 호스트까지 전송된 데이터 단위이다. 하지만 인터넷은 라우터나 스위치와 같은 접속 장치들로써 함께 구성된 네트워크의 조합이다. 만약 데이터그램이 호스트에서 다른 호스트로 전달된다면, 데이터그램은 이러한 네트워크들을 지나야 한다.

5.1.1 노드와 링크

응용, 전송, 네트워크 계층에서의 통신은 종단 대 종단(최초 송신자부터 최종 수신자까지)으로 이루어지지만, 데이터링크 계층에서의 통신은 노드 대 노드(각 네트워크 장비 사이)로 이루어진다. 인터넷의 한 지점에서 다른 지점으로 데이터 단위가 전달되기 위해서는 LAN, WAN과 같은 많은 네트워크를 지나야 한다. 일반적으로 두 종단 호스트와 라우터를 노드라고 하고, 그 사이의 네트워크를 링크라고 한다.

5.1.2 두 종류의 링크

전송 매체(케이블이나 공기 등)으로 물리적 연결된 두 노드 사이에서, 데이터링크 계층은 매체의 사용 방식을 제어한다. 데이터링크 계층은 링크의 전체 용량을 사용할 수도 있고, 링크 용량의 일부만을 사용할 수도 있다(공유). 즉, 점 대 점 링크나 브로드캐스트 링크를 사용할 수 있다. 점 대 점 링크에서 링크는 두 장치에 집중하는 반면, 브로드캐스팅 링크에서 링크는 몇 개의 장치들 사이에서 분배된다.

5.1.3 두 부계층

데이터링크 계층을 데이터링크 제어(DLC)와 매체 접근 제어(MAC)의 두 개 부계층으로 나눌 수 있다. DLC 부계층은 점 대 점 링크와 브로드캐스트 링크 모두에 공통적인 모든 문제를 다룬다. MAC 부계층은 브로드캐스트 링크에 특화된 문제를 다룬다.

DLC만으로도 브로드캐스트가 가능하지만 브로드캐스트에 특화된 제어를 하기 위해 MAC이 존재한다.

5.2 DLC

DLC는 링크가 전용인지 브로드캐스트인지 상관없는 두 인접한 노드들 사이의 통신을 다룬다. DLC 기능은 프레이밍, 흐름 및 오류 제어, 오류 검출과 수정이다.

5.2.1 프레이밍

데이터링크 계층은 비트들을 프레임 안에 만들어 넣어 각 프레임이 다른 프레임과 구분되도록 해야 한다. 데이터링크 계층의 프레이밍으로 인해 송신자와 수신자의 주소를 넣음으로써 발신지로부터 목적지의 메시지를 다른 목적지로 가야 하는 메시지와 분리한다.

전체 메시지를 한 개의 프레임에 다 끼워 넣을 수도 있지만 보통은 그러하지 않는다. 프레임이 매우 커지게 되면 흐름 제어와 오류 제어가 비효율적이 되기 때문이다.

프레임 크기
프레임은 고정 크기가 될 수도 있고 가변 크기가 될 수도 있다. 여기서는 가변 크기의 프레이밍에 대해 논하며, 이는 주로 LAN에 관련된 것이다. 가변 크기 프레이밍에서는 프레임이 끝나는 곳과 다른 프레임이 시작하는 곳을 정의해야 한다. 문자 중심과 비트 중심의 두 가지 방법이 사용된다.

1) 문자 중심 프로토콜

프레임을 다른 프레임으로부터 분리하기 위해서 8비트 플래그가 프레임의 시작점과 마지막에 추가된다. 그러나 플래그로 사용하는 패턴 그 자체도 데이터에 들어 있을 수 있으므로, 바이트 채우기를 한다. 바이트 채우기는 데이터 내부에 플래그와 동일한 패턴의 데이터가 생기면 이스케이프 캐릭터(ESC)를 추가한다. 그러나 만약 데이터 속에 한 개나 그 이상의 이스케이프 캐릭터가 있고 그 뒤에 플래그가 오게 되면 어떻게 되는가? 수신자는 이스케이프 문자는 제거하지만 데이터를 플래그라고 오인할 것이다. 이를 해결하기 위해 데이터의 일부가 되는 이스케이프 문자 자신을 다른 이스케이프 문자를 사용하여 표시한다. 즉 이스케이프 문자가 데이터의 일부인 경우에는 이스케이프 문자를 하나 더 추가하여 두 번째 탈출 문자는 데이터의 일부라는 것을 표시한다.

2) 비트 중심 프로토콜

대부분의 프로토콜들은 01111110의 8비트 패턴의 플래그를 프레임의 경계로 삼는다. 이는 문자 중심 프로토콜과 동일한 문제를 야기할 수 있다. 데이터 안에 플래그 패턴이 있을 때, 수신자로 하여금 그것이 프레임의 끝이 아니라는 것을 알게 할 필요가 있다. 이를 해결하기 위해 비트 채워 넣기를 하는데, 비트 채워 넣기는 0 뒤에 연속하는 다섯 개의 1이 있게 되면 0을 추가로 채워 넣는 과정이며, 수신자는 데이터 속의 01111110을 플래그로 오인할 수 없도록 한 것이다. 여기서에서 0 뒤에 다섯 개의 1이 연속되면 그 뒤의 비트값에 무관하게 0비트를 채워 넣는 것에 주목하라.

5.2.2 흐름 및 오류 제어

데이터링크 계층에서 DLC 부계층의 한 가지 주요 역할은 흐름 및 오류 제어이다.

흐름 제어
흐름 제어는 확인응답을 받기 전까지 보낼 데이터의 양을 조절한다. 이는 전송 계층에서의 원리와 동일하다.

오류 제어
오류 제어는 오류 검출과 정정이다. 수신자는 이로 인해 송신자에게 프레임이 전송 도중에 손상되었거나 유실된 것을 알릴 수 있으며 송신자로 하여금 해당 프레임을 재전송할 수 있도록 한다. 데이터링크 계층에서 오류 제어는 기본적으로 오류를 검출하여 프레임을 재전송하는 것을 말한다.

5.2.3 오류 검출 및 정정

개요

1) 오류의 종류

단일 비트 오류는 0이 1로 변환되거나 그 반대이다. 폭주 오류는 두 개 이상의 비트가 0에서 1로 변환되거나 그 반대이다. 폭주 오류는 단일 비트 오류보다는 일어날 가능성이 높다.

2) 중복(redundancy)

오류를 검출하거나 정정하는 것의 중심 개념으로, 데이터 이외의 추가 비트를 보낸다. 이 중복 비트들은 송신자에 의해 첨가되며 수신자가 제거한다. 중복 비트들로 인해 수신자는 오류를 찾아내거나 정정할 수 있다.

3) 검출 대 정정

오류를 정정하는 것은 검출하는 것보다 상당히 어렵다. 오류 검출에서는 생겼는지를 알아내면 된다. 오류가 몇 개인지조차 알 필요가 없는 것이다. 이는 단일 비트 오류나 폭주 오류나 마찬가지이다. 오류 정정(재전송 요구)에서는 정확하게 몇 비트가 잘못되었는지, 어디가 잘못되었는지를 알아야 한다. 오류의 개수와 메시지의 크기가 중요한 요소가 된다.

4) 코딩

중복은 여러 코딩 방법을 통해 달성된다. 송신자는 중복 비트와 실제 데이터 비트들 사이에 어떤 관련을 짓게 하는 과정을 통해 중복 비트들을 보낸다. 수신자는 이 두 종류의 비트들 사이의 관계를 파악하여 오류를 검출하거나 정정한다. 데이터 비트에 대한 중복 비트의 개수의 비율이나 처리 과정의 안정도가 코딩 기법의 주요 요소가 된다. 코딩 방법은 블록 코딩과 콘벌루션 코딩으로 나눌 수 있다.

블록 코딩
블록 코딩에서는 데이터워드라고 불리는 k비트의 블록으로 메시지를 나눈다. 각 블록에 r개의 중복 비트들을 더하여 길이 n = k + r이 되게 한다. 결과로 얻는 n비트 블록들은 코드워드라고 불린다.

1) 오류 검출

블록 코딩을 사용하여 어떻게 오류를 찾아낼 수 있는가? 다음 두 조건이 맞는다면 수신자는 원래 코드워드가 바뀐 것을 알 수 있다.

수신자는 유효 코드워드들을 찾아내거나 그 리스트를 가지고 있다.
원래의 코드워드가 무효 코드워드로 바뀌었다.

송신자는 뒤에서 논의할 부호화 규칙과 절차에 따라 데이터워드로부터 코드워드를 생성한다. 수신자에게 전송된 각 코드워드는 변형될 수 있다. 수신된 코드워드가 유효 코드워드와 같으면 용인되어 코드워드로부터 데이터를 추출한다. 수신된 코드워드가 유효하지 않으면 버려진다. 그러나 전송 도중 코드워드가 손상되었지만 수신된 코드워드가 여전히 유효 코드워드 중 하나라면 오류는 검출되지 않은 상태로 남는다. 이런 종류의 코딩은 오직 단일 비트 오류만 잡아낸다. 두 개 이상의 오류는 잡아내지 못한다.

오류 검출 코드는 찾도록 설계된 오류만을 찾아낸다. 다른 오류는 검출하지 못한다.

2) 해밍 거리

오류 제어의 중심 개념 중 하나는 해밍 거리이다. 두 같은 크기의 워드 사이의 해밍 거리는 서로 차이가 나는 해당 비트들의 개수이다. 두 워드 x와 y 사이의 해밍 거리를 d(x, y)로 표시한다. 해밍 거리는 두 워드에 XOR 연산을 행하여 얻은 값의 1의 개수를 더해 쉽게 구할 수 있다. 해밍 거리는 항상 0보다 큰 값임을 유의하라.

예제 5.2
두 워드들 사이의 해밍 거리를 알아보자.
1. d(000, 011)은 2인데 이는 000 $\oplus$ 011은 011(두 개의 1)이기 때문이다.
2. d(10101, 11110)은 3인데 이는 10101 $\oplus$ 11110은 01011(3개의 1)이기 때문이다.

두 워드 사이의 해밍 거리는 차이가 나는 해당 비트들의 개수이다.

3) 오류 탐지를 위한 최소 해밍 거리

코드워드의 집합에서 최소 해밍 거리는 가능한 모든 코드워드 쌍 조합에서 가장 작은 해밍 거리이다.

선형 블록 코드

오늘날 사용되는 대부분의 블록 코드는 선형 블록 코드이다. 비선현 블록 코드는 그 구조가 이론적으로 복잡하고 구현하기 힘들기 때문이다.

1) 패리티 확인 코드

아마 가장 익숙한 오류 검출 코드는 단순 패리티 확인 코드일 것이다. 이 코드에서는 k비트 데이터워드를 n = k + 1이 되도록 n비트 코드워드로 바꾼다. 추가된 비트는 패리티 비트라고 불리며 전체 코드워드의 1의 개수가 짝수 개가 되도록 선정된다(어떤 경우는 홀수 개로 선정). 표 5.2의 코드는 k = 5, n = 5인 경우의 패리티 확인 코드이다.

다음 그림은 가능한 인코더(송신자)와 디코더(수신자)의 그림이다.

인코더는 4비트 데이터워드(a1a2a3a4)의 사본을 받아 패리티 비트 r0을 생성한다. 데이터워드 비트와 패리티 비트는 5비트 코드워드를 만들어 낸다. 추가된 패리티 비트는 전체 코드워드의 1의 개수를 짝수 개로 만든다. 이는 보통 데이터워드의 4비트를 모듈로-2 연산으로 더해서 찾는다(비트끼리 xor). 그 결과값이 패리티 비트이다.

송신자는 전송 도중 손상된 코드워드를 보낼 수 있다. 수신자는 5비트 워드를 받는다. 수신자 쪽의 확인기는 한 가지를 제외하고 송신자 쪽의 생성기와 동일한 일을 한다. 이번에는 5비트에 대해 모듈로-2 덧셈을 하는 것이다. 그 결과를 증상(syndrome)이라고 부르는데 이는 1비트 값이다. 수신된 워드의 1의 개수가 짝수 개면 증상은 0이고 홀수 개면 1이다.

증상은 결정 논리 분석기로 보내진다. 증상이 0이면 수신된 코드에는 오류가 없는 것이고 데이터 부분이 데이터워드로서 받아들여진다. 증상이 1이면 데이터 부위를 버리게 된다. 데이터워드가 손상된 것이기 때문이다.

순환 코드(cyclic code)

순환 코드는 하나의 특별한 성질이 있는 선형 블록 코드이다. 순환 코드에서는 코드워드를 순환시키면 다른 코드워드를 얻는다. 예를 들어 1011000이 코드워드이면 한 비트를 왼쪽으로 이동시켜 얻은 코드워드 0110001도 코드워드이다.

1) 순환 중복 확인(cyclic redundancy check, CRC)

CRC는 LAN이나 WAN에서 널리 사용된다. 표 5.3은 CRC 코드의 한 예이다. 이 코드의 선형적이고 순환적인 성질을 보여준다.

다음 그림은 인코더와 디코더의 한 설계 예이다.

인코더에서 데이터워드는 k비트(여기서는 4비트)이며, 코드워드는 n비트(여기서는 7비트)이다. 데이터워드의 크기는 n - k(여기서는 3비트)개의 0을 데이터워드의 오른쪽에 더해서 키워진다. 이 n비트 결과값이 생성기로 보내진다. 생성기는 미리 정해진 크기 n - k + 1(여기서는 4비트)의 제수를 사용한다. 생성기는 확장된 데이터워드를 제수로 나누는데, 이는 모듈로-2 나눗셈이다. 나눗셈의 몫은 버려지고, 나머지(r2r1r0)를 데이터워드에 덧붙여 코드워드를 만든다.

디코더는 손상되었을지도 모르는 코드워드를 수신한다. 수신된 n비트의 사본이 확인기에 보내지는데, 이 확인기는 생성기와 동일하다. 확인기에 의해 만들어진 나머지가 n - k(여기서는 3비트)비트의 증상이 되며 이 증상이 결정 논리 분석기에 보내진다. 분석기는 간단한 기능을 한다. 증상 비트가 모두 0이면 코드워드의 왼편 4개 비트를 데이터워드로서 받아들이며 그렇지 않은 경우에는 4개 비트는 버려진다.

인코더를 자세히 들여다보자. 인코더는 데이터워드를 받아 n - k개의 0을 덧붙인다. 그 후 다음 그림처럼 확장된 데이터워드를 제수로 나눈다.

디코더를 들여다보자. 코드워드는 전송 도중 바뀔 수 있다. 디코더는 인코더와 동일한 나눗셈 연산을 수행한다. 나눗셈의 나머지는 증상이 된다. 증상이 모두 0이면 오류가 없는 것이고 데이터워드는 코드워드로부터 분리되어 채택된다. 그렇지 않으면 전체 워드를 버리게 된다. 다음 그림은 두 가지 경우를 보여주는데 왼편 그림은 증상의 값이 모두 0이며 오류가 없다. 그림의 오른편은 오류가 있는 경우의 증상 값을 보여준다.

여기서 제수 1011이 어떻게 선택되었는지 알 필요가 있다. 이는 우리가 코드로부터 얻은 예상에 따라 정해진다. 통신 분야에서 사용되는 표준 제수 중 몇 개가 표 5.4에 나타나 있다. 제수의 이름에 있는 숫자(예: CRC-32)는 제수를 표현하는 다항식의 급수를 나타낸다. 비트의 수는 항상 다항식의 급수보다 1이 높다. 예를 들면 CRC-8은 9비트를 가진다.

2) 순환 코드의 장점

순환 코드는 하드웨어나 소프트웨어로 쉽게 구현이 가능하다.

체크섬

체크섬은 어떠한 길이의 메시지에도 적용 가능한 오류 탐지 기법이다. 인터넷에서는 데이터링크 계층보다 네트워크 계층과 전송 계층에서 체크섬이 주로 사용된다.

송신측에서 메시지는 m비트 단위로 나누어진다. 그리고 체크섬으로 불리는 추가적인 m비트를 생성하여 메시지와 함께 전송한다. 수신측에서는 검사기(checker)에서 수신된 메시지와 체크섬을 사용하여 새로운 체크섬을 생성한다. 새롭게 만들어진 체크섬이 모두 0일 경우, 메시지는 정상적이지 않으므로 폐기된다.

1) 개념

수신자의 검사를 더 쉽게 하기 위해서 송신측에서는 합의 보수를 보내는데, 이를 체크섬이라고 한다.

송신측:

모든 데이터 블록의 합을 구한다. 캐리 발생 시 합에 더한다.
합의 1의 보수를 취하여 체크섬을 생성한다.
데이터 블록과 체크섬을 함께 전송한다.

수신측:

수신한 데이터 블록과 체크섬을 더한다.
모든 비트가 1인 경우(음수 0), 오류가 없는 것이고, 모든 비트가 0인 경우(양수 0), 오류가 있다고 판단한다.

5.3 MAC

다중 접근 프로토콜에 대해 알아본다. 임의 접근, 제어 접근, 채널화가 있다.

노드나 지국들이 다중 점 또는 브로드캐스트 링크라고 불리는 공유 링크를 사용할 때에는 링크에 접근하는 것을 조율하기 위한 다중 접근 프로토콜이 필요하다. 첫 번째 목표는 노드들 사이의 충돌을 방지하는 것이다. 만약 충돌이 발생하면, 두 번째 목표는 충돌을 제어하는 것이다.

5.3.1 임의 접근

임의 접근 또는 경쟁 방식에서는 어떤 지국이던 다른 지국보다 우위에 있지 않으며, 다른 지국을 제어할 권한도 부여되지 않는다. 각 순간마다 데이터를 전송할 필요가 있는 지국은 프로토콜에 정의된 절차를 사용하여 전송 여부를 결정한다. 이 결정은 매체의 상태(휴지 상태냐 사용 상태냐)에 따라 달라진다. 즉, 각 지국은 미리 정해진 절차를 따르 매체의 상태를 확인한다는 조건 하에서 원하는 때에 전송할 수 있다.

이 방식이 임의 접근이라는 이름을 갖게 된 두 가지 이유가 있다. 첫째, 지국이 전송할 수 있는 따로 정해진 시간이 없다. 지국 간의 전송은 무작위로 이루어진다. 둘째, 다음에 어떤 지국이 전송해야 하는지를 지정하는 규칙이 없다. 지국은 매체에 접근하기 위해 서로 경쟁한다.

ALOHA

가장 오래된 임의 매체 접근 방식이다. 지국들은 매체를 공유한다. 지국이 데이터를 전송할 때 동시에 다른 지국들도 같은 시도를 할 수 있다. 두 지국으로부터의 데이터는 서로 충돌하여 망가질 수 있다.

1) 순수 ALOHA

원래의 ALOHA 프로토콜이다. 각 지국은 지국이 전송할 프레임이 있으면 언제든지 전송할 수 있다는 것이 아이디어이다. 그러나 오직 하나의 채널만 있으므로 서로 다른 지국에서 전송한 프레임 간에 충돌이 있을 수 있다.

최대 전파 소요 시간 ( $T_{p}$ )
서로 가장 멀리 떨어져 있는 두 지국 사이에서 프레임을 전송하는 데 소요되는 시간

2) 틈새 ALOHA

시간을 $T_{fr}$ (지국이 고정 크기의 프레임 전송할 때의 소요 시간)의 틈새로 나누어 지국은 매 시간 틈새가 시작할 때에 전송하도록 규제한다.

CSMA(carrier sense multiple access)
반송파 감지 다중 접근은 충돌 가능성을 줄이기 위해 개발되었다. CSMA에서 각 지국은 매체의 상태를 점검한다. 이는 충돌 가능성을 줄일 수는 있지만 제거는 할 수 없다. 그 이유는 전파 지연 때문이다. 지국이 프레임을 전소할 때는 그 프레임의 첫 번째 비트가 모든 지국들에게 도착하여 각 지국들이 감지하기 전까지 (아무리 짧더라도)시간이 걸린다. 즉 지국이 매체를 감지하여 매체가 사용되지 않고 있다고 감지한다 해도 다른 지국이 전송할 프레임의 첫 번째 비트가 아직 도달 중일 수 있는 것이다.

CSMA에서 각 지국은 자신이 물리적으로 연결된 지점에서만 매체의 상태를 감지할 수 있다.

지국은 브로드캐스팅을 하고, 지국의 감지는 지국이 있는 지점에서만 이루어진다.

1) 취약 시간

CSMA의 취약 시간은 전파 시간 $T_{p}$ 이다. 이 시간은 신호가 매체의 한 끝에서 다른 끝으로 전파되는 데 소요되는 시간이며, 감지를 하지 못하고 휴지 상태라고 착각하는 시간이다.

2) 지속 방식

지국이 채널이 사용 중인 것을 감지했을 때의 세 가지 방식이다.

1-지속(1-persistant) 방식
이 방식에서는 지국이 회선이 휴지 상태인 것을 감지하게 되면 즉각 프레임을 전송한다(확률 1을 가지고). 이 방식에서는 두 개 이상의 지국이 회선의 휴지 상태를 감지할 것이고 그런 경우에 모두 즉각 프레임을 전송하기 때문에 가장 높은 충돌 위험을 유발한다.

비지속(Nonpersistant) 방식
이 방식에서는 회선의 휴지 상태를 감지하면 즉각 프레임을 보낸다. 만일 회선이 휴지 상태가 아니라면 임의의 시간을 대기하고 있다가 다시 회선을 감지한다. 비지속 방식은 두 개 이상의 지국이 같은 시간을 대기하고 있다가 동시에 전송할 확률이 낮기 때문에 충돌의 위험을 낮춘다. 그러나 이 방식은 전송할 프레임이 있는 지국이 있음에도 불구하고 회선이 휴지 상태에 있을 수 있기 때문에 회선의 효율이 낮아진다.

p-지속(p-persistant) 방식
이 방식에서는 채널이 최대 전파 지연과 같거나 그보다 큰 시간 틈새를 사용하는 경우에 채택된다. p-지속 방식은 위의 두 가지 방식의 장점을 합한 것이다. 충돌의 위험을 줄이면서 효율을 높인다. 이 방식에서는 회선이 휴지 상태에 있는 것을 감지하면 다음의 단계를 거친다.

확률 p를 가지고 프레임을 전송한다.
확률 1 - p를 가지고 지국은 다음 틈새 시작까지 기다리다가 회선을 다시 감지한다.
if(회선이 휴지 상태)
	확률 p를 가지고 프레임을 전송한다.
else
	충돌이 생긴 것으로 간주하고 대기 절차에 들어간다.

CSMA/CD(carrier sense multiple access with collision detection)

CSMA 방법은 충돌 뒤에 따라야 하는 절차에 대해 설명하고 있지 않다. 충돌 검출을 하는 CSMA, 즉 CSMA/CD는 충돌을 처리하는 절차를 더한 것이다.

이 방법에서 지국은 프레임을 전송한 뒤에 전송이 성공적인지 매체를 관찰한다(확인응답과 타임아웃). 성공적이면 지국은 소임을 다 한 것이다. 그렇지 않다면 충돌이 생긴 것이며 프레임은 다시 전송된다.

CSMA/CD를 더 잘 이해하기 위하여 충돌에 연루된 두 지국들에 의해 전송된 첫 번째 비트를 들여다보자. 비록 각 지국은 충돌을 감지할 때까지 프레임에 있는 비트들을 계속 보내겠지만 여기서는 첫 번째 비트가 충돌할 때 무슨 일이 벌어지는지를 본다.

t1에서 지국 A는 자신의 지속 절차에 따라 자신의 프레임의 비트들을 전송하기 시작한다. t2에서 지국 C는 A가 보낸 프레임의 첫 번째 비트를 아직 감지하지 못한다. 지국 C는 자신의 지속 절차를 수행하여 자신의 프레임의 비트들을 전송하는데 그 비트는 왼편과 오른편으로 전파된다. 지국 C는 t3 시점에 A가 보낸 프레임의 첫 번째 비트를 수신하게 되어 충돌을 감지한다. 지국 C는 즉각 전송하는 것을 멈춘다. 지국 A는 C의 첫 번째 프레임의 비트를 수신한 t4에서 충돌을 알게 되어 자신도 즉각 전송하던 것을 멈춘다. A는 t4 - t1동안, C는 t3 - t2동안 전송한다.

충돌 감지
지국이 프레임의 비트를 보내면, 매체에서는 신호를 전송한다. 지국은 보낸 프레임의 비트와 수신한 신호의 비트를 비교하여 서로 다르면 충돌이라고 판단한다. 프레임과 신호의 전송 속도는 같다.

1) 최소 프레임 크기

CSMA/CD가 동작하기 위해서는 프레임 크기에 제한을 두어야 한다. 프레임의 마지막 비트 보내기를 마치기 전에 송신 지국이 충돌을 감지하면 전송을 멈추어야 한다. 이는 지국이 전체 프레임을 보내고 나면 프레임의 사본을 갖고 있지 않으며 회선을 관찰하여 충돌이 생겼는지 확인하지 않기 때문이다. 그러므로 프레임 전송 시간 $T_{fr}$ 은 최소한 최대 전파 시간 $T_{p}$ 의 2배가 되어야 한다. 그 이유를 이해하기 위해 최악의 시나리오를 생각하자. 충돌에 관해서 두 지국이 서로 떨어질 수 있는 최대 거리만큼 떨어져 있다고 하자. 첫 번째 지국으로부터의 신호는 두 번째 지국에 도달하기까지 $T_{p}$ 만큼 걸리며, 충돌의 효과(매체의 신호)는 다시 $T_{p}$ 만큼 더 걸려 첫 번째 지국에 도달한다. 따라서 첫 번째 지국은 $T_{p}$ 이후에도 계속 전송을 하고 있어야만 한다. 그래야 충돌 신호를 받고 전송을 멈출 수 있다.

예제 5.15
어느 CSMA/CD 사용하는 네트워크의 대역폭이 10Mbps이다. 최대 전파 시간은 25.6마이크로초이다. 최소 프레임의 크기는?

해답
최소 프레임 전송 시간은 51.2 마이크로초이다. 프레임의 최소 크기는 10Mbps X 51.2 ms = 512비트, 즉 64바이트이다. 이는 실제로 표준 이더넷 프레임의 최소 크기이다.

마이크로초는 백만 분의 1이다.

2) 충돌 신호(jamming signal)

충돌이 생겼을 때 다른 지국이 아직 충돌을 감지하지 못했을 것을 대비하여 다른 지국에게 충돌의 발생 사실을 알리는 신호이다.

3) 에너지 준위(Energy Level)

채널의 에너지 준위는 0, 정상, 비정상의 세 가지가 있다. 0 준위에서는 채널은 휴지 상태이다. 정상 준위에서는 지국은 채널을 성공적으로 확보하여 프레임을 보낸다. 비정상 준위에서는 충돌이 생긴 것이며 에너지 준위는 정상 준위의 두 배가 된다.

CSMA/CA(carrier sense multiple access with collision avoidance)

CSMA/CA는 무선 LAN에서 사용된다.

5.3.2 제어 접근

제어 접근에서 지국들은 서로 상의하여 어느 지국이 전송할 권리를 갖는지 찾는다. 지국은 다른 지국들에 의해 권리를 인정받을 때까지는 전송할 수 없다. 예약, 폴링, 토큰 패싱의 방법이 있다.

예약
이 방식에서 지국은 데이터를 전송하기 전에 예약을 해야 한다. 시간은 구간들로 나뉘게 되며, 각 구간마다 예약 프레임이 그 구간에 전송되는 데이터 프레임의 앞에 놓인다.

폴링
폴링은 하나의 장치가 주 지국으로 지정되고 다른 장치가 부 지국으로 지정된 토폴로지에서 작동한다. 최종 목적지가 부 지국일지라도 모든 데이터는 주 지국을 통해 교환이 이루어져야 한다. 주 지국이 링크를 제어하고 부 지국은 그 지시를 따른다. 주어진 시간에 어느 지국이 채널을 사용할지 주 지국이 결정한다. 따라서 주 지국은 항상 세션의 초기화를 담당한다. 주 지국이 멈출 경우 전체 시스템이 작동할 수 없는 단점이 있다.

토큰 패싱

토큰 패싱 방식에서 네트워크 안의 지국들은 지역 고리형태로 구성된다. 즉 각 지국에는 선행자와 후행자가 있다. 토큰이라고 불리는 패킷이 고리를 따라서 돌아다닌다. 토큰을 붙잡게 되는 지국은 채널 접근 권한을 갖게 되고 데이터를 전송하게 된다. 이는 물리적 위치가 아니라 논리적 위치로 구성된다.

1) 논리적 고리

다음 그림은 한 개의 논리적인 고리를 형성하는 물리적 고리, 이중 고리, 버스 고리, 별 고리의 물리적 형상을 나타낸다.

물리적 고리 형상에서 후행자는 선상에 있는 다음 지국이다. 문제는 형상 중 하나라도 끊어지면 전체 시스템이 동작을 멈춘다.

이중 고리 형상의 이차 고리는 비상상태에서만 사용하며, 중심 고리의 링크가 망가지면 시스템은 자동으로 두 고리를 합하여 새로운 임시 고리를 형성한다.

버스 고리 형상은 버스를 사용한다. 토큰에 후행자의 주소가 있다.

별 모양 형상에서 물리적 형상은 별 모양이다. 그러나 허브가 연결 장치 역할을 한다. 허브 내부의 연결로 인해 고리 모양을 만든다. 지국은 두 개의 회선을 통해 이 고리에 연결된다. 이 형상은 네트워크가 잘 망가지지 않게 해 주는데, 링크가 망가지면 허브는 망가진 링크는 그냥 무시하고 나머지하고만 통신하기 때문이다. 지국을 더하거나 제거하는 것 또한 용이하다.

5.3.3 채널화

때떄로 채널 분할이라 불리는 채널화는 다중 접속 방법이다. 이것은 서로 다른 지국에서 사용 가능한 링크 대역폭이 동시에 주파수 또는 코드들을 사용하여 동시에 분배된다는 것을 의미한다. 일반적으로 무선 네트워크에서 이러한 방법들을 사용한다.

5.4 링크 계층 주소할당

네트워크 계층의 주소는 IP였다. 링크계층 주소는 때때로 링크 주소로 불리고, 물리 주소 그리고 MAC 주소로 불린다. 라우터 또는 게이트웨이는 2개 이상의 링크계층 주소를 사용한다.

ARP(address resolution protocol)

노드나 라우터가 다른 노드의 링크계층 주소를 모를 때 사용한다. 네트워크 계층의 프로토콜 중 하나이다. ARP 패킷에는 자신의 IP 주소 + 링크계층 주소 그리고 상대측 IP 주소를 포함한다. ARP 패킷은 브로드캐스팅으로 전체 서브넷에 전파된다.

5.5 유선 LAN: 이더넷 프로토콜

이더넷 프로토콜은 유선 LAN(Local Area Network)에서 데이터 링크 계층과 물리 계층의 표준을 정의하는 프로토콜이다. 이더넷은 NIC를 통해 각 지국이 네트워크에 연결되고, 데이터를 프레임 형태로 전송하는 방식을 사용한다. 유선 LAN은 물리적 매체(케이블)을 통해 네트워크를 구성하는 방식으로, 이더넷은 이러한 유선 LAN의 주요 구현 방식이다.

이더넷은 CSMA/CD 접근을 사용한다.

5.5.1 IEEE 프로젝트 802

1985년에 IEEE 컴퓨터분회는 다양한 제조사의 장치들 사이의 상호연결이 가능하도록 하는 표준을 만들기 위해 프로젝트 802를 시작했다. 프로젝트 802는 OSI나 TCP/IP 프로토콜의 어떠한 부분을 교체하려는 의도는 없었다. 다만, 주요 LAN 프로토콜의 물리 계층과 데이터링크 계층의 기능을 규격화하였다.

802 표준과 TCP/IP 프로토콜 사이의 관계가 다음 그림에 있다. IEEE는 데이터링크 계층을 논리적 연결 제어(LLC)와 매체 접속 제어(MAC)의 두 개 부계층으로 나누었다.

DLC는 TCP/IP 계층에서, LLC는 IEEE 802 관점에서의 데이터 링크 부계층이다.

LLC
앞에서 데이터링크 제어는 프레이밍과 흐름 제어, 오류 제어를 다룬다고 했다. IEEE 802에서는 흐름 제어, 오류 제어와 프레이밍 일부분에 대한 역할을 LLC이라는 하나의 부계층에서 처리한다. LLC는 모든 IEEE LAN을 위해 하나의 데이터 링크 제어 프로토콜을 제공한다.

MAC
IEEE 802는 각각의 LAN을 위해 특별한 접근 방식인 MAC 부계층을 만들었다. 예를 들어, 이더넷 LAN을 위한 매체 접근 방식으로 CSMA/CD를 정의했고, 토큰 링이나 토큰 버스 LAN을 위해 토큰 전달 방식을 정의했다. 프레이밍 기능의 일부도 MAC 계층에서 다루어진다.

5.5.2 표준 이더넷

10Mbps의 데이터율을 가지는 이더넷 기술을 표준 이더넷이라고 한다. 이더넷의 발전에도 불구하고 여전히 변하지 않는 표준 이더넷의 몇 가지 특징들이 있다.

주소지정
이더넷 네트워크에 있는 각 지국은 자신의 네트워크 인터페이스 카드(NIC)을 가진다. 이더넷 주소는 6바이트이며, 일반적으로 각 바이트를 콜로으로 구분한 16진법 표기법으로 쓰인다. 이더넷 MAC 주소는 아래와 같이 나타낸다.

1) 유니캐스트, 멀티캐스트, 브로드캐스트 주소

발신지 주소는 항상 유니캐스트 주소이며 이것은 프레임이 오직 하나의 지국에서부터 송신됨을 의미한다. 그러나 목적지 주소는 유니캐스트, 멀티캐스트, 브로드캐스트가 될 수 있다. 주소 바이트의 LSB가 0이면 유니캐스트 주소를, 1이면 멀티캐스트 주소를 의미하고, 6바이트 모두 1이면 브로드캐스트 주소이다.

2) 유니캐스트, 멀티캐스트, 브로드캐스트 전송 사이의 구별

서로 구별하는 방법은 프레임을 유지시키거나 폐기시키는 방법이다.

유니캐스트 전송의 경우 모든 지국은 프레임을 받은 뒤 의도된 수신자만 프레임을 유지, 관리하고 나머지 지국은 프레임을 폐기한다.

멀티캐스트 전송의 경우 모든 지국은 프레임을 받은 뒤 그룹에 속한 지국들만 프레임을 유지, 관리하고 나머지 지국은 프레임을 폐기한다.

브로드캐스트 전송의 경우 송신자를 제외한 모든 지국들은 프레임을 받은 뒤, 프레임을 유지, 관리한다.

5.5.3 고속 이더넷

프레임을 10배 빠르게 전송하려면 충돌 탐지도 10배 빠르게 이루어져야 하며, 네크워크의 최대 길이도 10배가 되어야 한다. 이 문제의 해결책은

버스 구조를 포기하고, 허브를 통한 스타 토폴로지를 사용한다.
네트워크의 최대 길이는 표준 이더넷의 2500미터 대신에 250미터여야 한다.
허브 및 노드에서 각 노드들이 전이중 연결을 한다.
실제 점-대-점 연결로 변경한다. 즉 충돌 감지가 필요 없게 만든다.

5.5.4 기가비트 이더넷

MAC 부계층을 폐기한다. 전송 매체에 전이중 접속한다. 중앙 스위치가 모든 노드에 전이중으로 접속한다. CSMA/CD를 사용하지 않는다. 따라서 충돌 감지가 필요 없다.

5.5.5 10기가비트 이더넷

LAN을 MAN처럼 사용하고 WAN과 연결한다. 충돌 없는 전이중 연결을 한다. 따라서 CSMA/CD를 폐기한다.

5.6 다른 유선 네트워크

MAN 또는 WAN 네트워크에 대해 논의한다.

5.6.1 점-대-점 네트워크

두 노드 사이를 직접 연결한다. 매체를 공유하지 않으므로 MAC이 필요 없다.

다이얼-업 접속
반이중 방식으로 동작하며, 모뎀의 속도에 의존한다.

다지털 가입자 회선(DSL)
비대칭 DSL(ADSL)은 기존의 전화선(꼬임쌍선)을 사용한다. 실제로 1.1 MHz 대역폭까지 처리할 수 있지만, 4KHz(음성 통화에 충분)으로 제한한다. 필터를 제거한다면 1.1 MHz를 데이터와 음성 통화에 사용할 수 있다. 1.104 MHz의 가용 대역폭은 업스트림 채널과 다운스트림 채널로 나뉜다.

전화 회사는 ISP의 역할을 한다.

케이블 TV 접속

하이브리드 광섬유 동축(HFC) 네트워크

광섬유 네트워크와 케이블 네트워크의 결합이다. 지역 케이블 책임국(RCH)는 일반적으로 400,000의 가입자 회선을 제공 가능하다. 분배 허브(Distribution hub)는 40,000개의 가입자 회선을 지원한다. 동축 케이블은 1,000개의 가입자 회선이 가능하다. HFC는 양방향 접속이 가능하다.

6. 무선 네트워크

6.1 무선 LAN

6.1.1 개요

구조적 비교

1) 매체

유선 LAN은 선을 사용하고 무선LAN은 공기를 사용한다. 신호는 일반적으로 브로드캐스팅이다.

2) 호스트

유선 LAN에서 호스트는 언제나 NIC과 연결된 고정된 링크 계층 주소 지점의 네트워크로 연결된다. 무선 LAN에서 호스트는 물리적으로 네트워크에 접속될 필요가 없다.

3) 고립 LAN

유선 고립 LAN은 하나의 호스트 그룹이 링크 계층 스위치(이더넷)를 통하여 연결된 것이다. 무선 고립 LAN은 에드 혹 네트워크(ad hoc network)라고 불리며 서로 자유롭게 통신하는 하나의 호스트 그룹이다.

4) 다른 네트워크로의 연결

유선 LAN은 라우터를 통해 다른 네트워크로 연결된다. 무선 LAN은 유선 기반구조 네트워크, 무선 기반구조 네트워크, 다른 무선 LAN에 접속할 수 있다. 무선 LAN이 기반구조 네트워크를 참조하게 될 때, AP를 통하여 인터넷과 같은 유선 기반구조로 연결된다. 무선 LAN에는 링크 계층 스위치의 개념이 존재하지 않는다.

5) 환경 간의 이동

유무선의 상호 이동은 NIC의 이동이 필요하다.

특성

1) 감쇠

모든 방향으로 신호가 분산되기 때문에 전자기 신호의 세기가 급격히 감소된다. 이로 인하여 신호의 일부만 수신기에 도착한다.

2) 간섭

수신기가 의도된 송신기뿐만 아니라 다른 송신기에서 같은 주파수 대역을 이용하여 보낸 신호를 같이 수신한다.

3) 다중경로 전파

전자기파는 벽, 지면, 사물과 같은 장애물에 반사될 수 있기 떄문에 동일한 송신기로부터 여러 신호를 받을 수 있다. 그 결과 수신자는 서로 다른 경로를 따라 이동하는 신호를 서로 다른 위상에서 수신하게 된다. 이는 신호를 알아보기 힘들게 만든다.

4) 오류

SNR(signal to noise ratio)이 높으면 잡음보다 신호의 세기가 센 것이다. 따라서 신호를 실제 데이터로 변환할 수 있을 것이다.

접근 제어
무선 LAN에서 가장 중요한 이슈는 호스트가 어떻게 매체(공기)를 공유하여 접근할 수 있는지에 대한 접근 제어이다. CSMA/CD는 다음과 같은 이유로 무선 LAN에서 구현할 수 없다.

충돌 검출을 위해서는 호스트가 송신과 충돌 감지를 동시에 하기 위해 전이중으로 통신해야 하는데, 무선 호스트는 반이중 통신이다.
숨겨진 지국 문제

어떤 지국은 장애물 또는 소속 범위 문제로 인하여 숨겨진 호스트가 된다. 이는 유휴 상태로 간주되거나 무선 MAC의 충돌을 야기한다.
신호 감쇠현상 떄문에 충돌을 감지할 수 없는 경우가 발생한다.
노출된 지국 문제

A 노드에서 B 노드로 데이터 전송 중 C 노드에서는 D 노드로 데이터 전송이 가능하나, C 노드에서느느 A 노드의 프레임을 감지하고 충돌을 예측해서 D 노드로 프레임을 전송하지 못하는 문제이다. 이는 RTS와 CTS로 해결할 수 없다. C 노드에서 A 노드의 RTS를 수신하면 C 노드는 D 노드에게 보낼 예정인 프레임 전송을 포기한다. 즉 C 노드가 D 노드에게 프레임을 보내는 것이 A, B 노드들에게는 문제가 없음을 인지하지 못해 생기는 문제이다.

이를 극복하기 위해 무선 LAN은 충돌 회피 반송파 감지 다중 접속(CSMA/CA)를 사용한다.

6.1.2 IEEE 802.11

IEEE가 정의한 무선 LAN에 대한 명세사항이다.

구조
표준안에는 두 가지 종류의 서비스를 정의하고 있다. 하나는 기본 서비스 세트(BSS), 다른 하나는 확장 서비스 세트(ESS)이다.

1) BSS

BSS는 고정 또는 이동하는 무선국, AP라는 중앙 기지국으로 구성되어 있다. AP가 없는 BSS는 단독 네트워크이며 다른 BSS로 데이터를 송신할 수 없다. 이것을 에드 혹 구조라고 한다. 이 구조에서 지국은 AP 없이 네트워크를 구성할 수 있다. AP를 가진 BSS는 기반구조(infrastructure) 네트워크라고 하기도 한다.

2) ESS

ESS는 AP를 가진 2개 이상의 BSS로 구성된다. 이 경우 BSS들은 유선 LAN인 분산 시스템을 통해 연결된다.

3) 지국 유형

IEEE 802.11에서는 무선 LAN에서 이동성을 기반으로 하여 무전이, BSS 전이, ESS 전이의 세 가지 유형의 지국을 정의하고 있다. 무전이 이동성을 가진 지국은 고정되어 있거나 오직 하나의 BSS 안에서만 움직이는 경우이다. BSS 전이 이동성을 가진 지국은 한 BSS에서 다른 BSS로 이동할 수 있지만, ESS 안으로 움직임이 제한된다. ESS 전이 이동성을 가진 지국은 ESS에서 다른 ESS로 이동할 수 있다. 그러나 IEEE 802.11에서는 움직이는 동안 연속적인 통신을 보장하지 않는다.

MAC 부계층
IEEE 802.11에서는 분산 조정함수(DCF, distributed coordination function)와 포인트 조정함수(PCF, point coordination function)의 두 가지 MAC 부계층을 정의한다.

1) 분산 조정함수

DCF는 매체 접속에 CSMA/CA를 사용한다.

무선 네트워크에서의 충돌은 프레임 간 공간, 경쟁 구간, 응답이라는 세 가지의 CSMA/CA 충돌 전략에 의해 회피된다.
프레임 간 공간(IFS, Interframe Space)
휴지 상태의 채널이 발견되면 지국은 IFS라고 불리는 일정 시간을 기다린다. 채널이 휴지 상태인 것처럼 보이더라도 전파 지연 으로 인해 멀리 떨어진 지국이 이미 전송을 시작했을지도 모르기 때문에, IFS 시간으로 멀리 떨어진 지국이 보낸 신호의 앞부분이 도달할 수 있도록 여유를 두는 것이다. IFS 시간동안 휴지상태이면 다시 경쟁 구간이라고 불리는 시간 동안 대기한다. IFS 시간은 우선순위에 의하여, 호스트에 따라 다르다.
경쟁 구간(contention window)
시간 틈새로 나뉜 일정 시간이다. 전송할 준비가 된 지국은 임의의 수를 선택하여 그만큼 기다리고, 틈새의 수는 지수 대기 전략에 따라 달라질 수 있다. 처음에는 한 개 틈새로 시작하다가 매번 휴지 채널을 발견하지 못할 때마다 두 배씩 틈새를 늘려간다. P-지속 방식과 유사하지만, 경쟁 구간에서는 임의의 수만큼 기다린다. 재국은 매 시간 틈새 뒤에 채널을 감지해야 한다. 그러나 채널이 사용 중인 것을 지국이 감지하면 지국은 타이머를 멈추고, 채널이 휴지 상태인 것이 감지되면 다시 타이머를 작동한다.
확인응답
위와 같이 조심하더라도 충돌 위험은 존재한다. 또한 전송 도중에 데이터가 손상될 수도 있다. 확인응답과 타임아웃을 사용하여 수신자가 프레임을 수신받았다는 것을 보장할 수 있다.

프레임 교환 시간선

프레임을 보내기 전에 발신 지국은 반송 주파수의 에너지 준위를 검사함으로써 매체를 감시

채널이 유휴상태일 때까지 백오프(일정 시간 대기) 값으로 지속성 전략 사용

채널이 사용되지 않는다는 것을 확인하면 DIFS(distribute interframe space)동안 대기, RTS(request to send)라 불리는 제어 프레임을 보냄

RTS 수신 후, SIFS(short interframe space)동안 대기, 목적 지국은 CTS(clear to send)를 발신 지국에 전송

발신 지국은 SIFS동안 대기 후 데이터 전송

SIFS 대기 후 목적 지국은 ACK 전송

비교: CSMA/CD에서는 충돌이 없으면 프레임이 목적지에 잘 도착한 것으로 간주

만약 한 지국이 접근권한을 가지고 있다면 어떻게 다른 지국은 자신이 보낼 데이터를 뒤로 미루는가?
한 지국이 RTS 프레임을 보낼 때, 프레임은 채널 점유에 필요한 시간을 포함하고 있다. 이 전송에 의해 영향을 받는 지국은 네트워크 할당 벡터(NAV)라고 불리는 타이머를 만든다. 이것은 다른 지국이 채널을 사용 중인지 확인하기 전에 얼마의 시간을 보내야 하는지를 알려준다. 매번 지국이 시스템에 접근하고 RTS를 보낼 때마다 다른 지국은 NAV를 시작한다.

핸드쉐이킹 시간은 RTS전송-CTS수신 시간이다. 이 시간동안 RTS 프레임을 송신하고 충돌하면 그 충돌을 감지할 감지 수단이 없다. 따라서 수신자로부터 CTS 프레임을 받지 못하면, 송신자는 충돌이 발생했다고 가정한다. 백오프 전략이 사용되며, 송신자는 재전송을 시도한다.

숨겨진 지국 문제의 해결은 RTS와 CTS같은 핸드쉐이크 프레임을 사용하는 것이다 .

2) 포인트 조정함수

PCF는 에드 혹 네트워크가 아닌 기반구조 네트워크에 구현되어 있는 선택적인 접근 방법이다. 이것은 DCP의 상위에 구현되어 있으며 시간에 민감한 전송에 사용된다.

7. 물리 계층과 전송 매체

7.1 디지털 전송

컴퓨터 네트워크는 네트워크 안의 한 지점으로부터 다른 지점으로 정보를 전송하기 위해 설계된 것이다. 네트워크를 설계하는 데 있어서 정보를 디지털 신호로 바꿀 것인지 아날로그 신호로 바꿀 것인지를 선택할 수 있다.

데이터가 디지털이라면, 디지털 데이터를 디지털 신호로 변환해주는 디지털 대 디지털 변환 기술과 방식을 사용해야 한다.

7.2.1 디지털-대-다지털 변환

디지털 데이터를 어떻게 디지털 신호로 나타내는지를 알아본다. 변환에는 세 가지 기술이 있다. 회선 코딩, 블록 코딩 및 뒤섞기가 그것이다. 회선 코딩은 항상 필요하다.

회선 코딩
회선 코딩은 일련의 비트인이진 데이터를 디지털 신호로 바꾸는 작업이다. 전송측에서는 디지털 데이터가 디지털 신호로 부호화되고 수신측에서는 디지털 신호를 복호화하여 디지털 데이터를 재생한다.

회선 코딩은 극형, 양극형, 다준위의 세 가지 방법으로 나뉜다.

극형

극형 부호화 방법은 양과 음의 두 가지 전압 준위를 같이 사용한다. 예를 들면, 0을 위해서는 양전압을 사용하고 1을 위해서는 음전압을 사용한다.

비영복귀(NRZ, non-return-to-zero) 부호화에서는 두 가지 준위의 신호를 사용한다. NRZ-L과 NRZ-I의 두 가지 방법이 있다. NRZ-L(level)에서는 전압 준위가 비트의 값을 결정한다. NRZ-I(Invert)에서는 전압에 변화가 있거나 없는 것으로 비트의 값을 결정한다. 전압 변화가 없으면 0이고 전압이 바뀌면 1이다.

NRZ의 주요 문제는 송신측과 수신측의 클럭이 동기화되어있지 않다는 것이다. 수신측은 한 비트가 끝나고 다음 비트가 시작되는 시점을 알지 못하는 것이다. 하나의 해결책으로 세 개의 준위값을 사용하는 RZ(return-to-zero)가 있다.

RZ에서는 신호의 변화가 비트 사이에 있는 것이 아니라 한 비트 구간 내에서 일어난다. RZ 부호화의 주요 단점은 하나의 비트를 부호화하기 위해 두 번의 신호 변화를 필요로 하여 너무 많은 대역폭을 차지한다는 것이다. RZ의 아이디어(비트 중간에서 전이)와 NRZ-L의 아이디어를 결합한 것이 맨체스터이다. 맨체스터 부호화에서 비트 구간은 두 개의 반으로 나누어진다. 전압은 첫 반의 비트 구간 동안에 유지되다가 두 번째 반 비트 구간에는 다른 수준으로 이동한다. 비트 중간에서의 전이는 동기화를 제공한다. 반면, 차분 맨체스터는 RZ와 NRZ-I의 아이디어를 결합한 것이다. 전이는 항상 비트의 중산에서 일어나나 비트의 값은 비트의 시작에 의해 결정된다. 만약 다음 비트가 0이라면 전이가 일어나고 다음 비트가 1이라면 전이는 일어나지 않는다.

추가: 라우팅 알고리즘

라우팅 알고리즘의 목표는 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것이다. 일반적으로 '좋은' 경로란 최소 비용 경로를 말한다. 네트워크 제어 평면이 라우터별 제어 방식을 선택하든 논리적 중앙 집중형 방식을 채택하든 상관없이 패킷이 전송 호스트에서 수신 호스트로 이동하기 위한 잘 정의된 일련의 라우터가 항상 존재해야 한다. 따라서 이러한 경로를 계산하는 라우팅 알고리즘은 네트워킹의 기본이다.

라우팅 문제를 나타내는 데는 그래프라 사용된다. 그래프는 G = (N, E)로 나타낸다. N과 E는 각각 노드와 에지의 집합이고, 하나의 에지는 집합 N에 속하는 한 쌍의 노드로 표시된다. 네트워크 계층 라우팅 상황에서 그래프상의 노드는 패킷 전달 결정이 이루어지는 지점인 라우터를 나타내며, 이 노드들을 연결하는 에지는 라우터들 간의 물리 링크를 나타낸다.

에지는 그 비용을 나타내는 값을 갖는다. 이 비용은 일반적으로 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영한다. 집합 E에 포함된 어떤 에지 (x, y)에 대해 c(x, y)는 노드 x와 y 간의 비용을 의미한다. 만약 노드 쌍 (x, y)가 E에 포함되어 있지 않으면 c(x, y) = INF로 둔다. 또한 모든 에지가 방향성을 갖지 않는 무방향성 그래프만을 고려한다. 그러나 우리가 살펴볼 알고리즘들은 양방향으로 서로 다른 비용을 갖는 방향성 링크의 경우로 쉽게 확장할 수 있다. 에지 (x, y)가 집합 E에 속하면, 노드 y는 노드 x의 이웃이라고 한다.

그래프의 여러 에지들에 비용이 할당되고 나면 라우팅 알고리즘은 자연적으로 출발지와 목적지 간 최소 비용 경로를 찾는 것을 목표로 하게 된다. 그래프 G(N, E)에서의 경로(path)는 노드의 연속(x1, x2, ..., xp)이고 노드 쌍은 집합 E에 속한 에지들이다. 경로 (x1, x2, ..., xp)의 비용은 경로상 모든 에지 비용의 단순 합이다. 어떤 두 노드 x, y가 주어진면 일반적으로 두 노드 간에 많은 경로가 존재하고 각 경로는 비용을 갖는다. 이 중 최소 비용 경로(least-cost path)는 하나일 수도 있고 여러 개일 수도 있다. 최소 비용 문제는 명확하다. 출발지와 목적지 간 최소 비용을 갖는 경로를 찾으면 된다. 만약 그래프의 모든 에지가 같은 비용을 갖는다면 최소 비용 경로가 최단 경로(shortest path, 출발지와 목적지 사이에서 최소 개수의 링크만을 포함하는 경로)가 된다.

중앙 집중형 라우팅 알고리즘은 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 즉 , 이 알고리즘은 모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 한다. 이러한 정보는 알고리즘의 실제 계산을 수행하기 전에 어떠한 방법을 통해서라도 얻어야 한다. 계산 자체는 한 장소에서 수행되거나 모든 라우터 각각의 라우팅 모듈로 복사될 수 있다. 그러나 핵심적인 특징은 이 알고리즘이 연결과 링크 비용에 대해 완전한 정보를 갖는다는 점이다. 전체 상태 정보를 갖는 알고리즘을 링크 상태 알고리즘이라고 하는데, 이는 이 알고리즘이 네트워크 내 각 링크의 비용을 알고 있어야 하기 때문이다.
분산 라우팅 알고리즘에서는 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지는 않다. 대신 각 노드는 자신에게 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다. 이후 반복된 계산과 이웃 노드와의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합까지의 최소 비용 경로를 계산한다. 거리 벡터 알고리즘에서는 각 노드가 네트워크 내 다른 노드까지 비용 추정값을 벡터 형태로 유지한다. 이웃한 라우터들끼지 반복적으로 메시지를 교환하는 이러한 분산형 알고리즘은 라우터들이 직접 상호작용하는 제어 평면에 좀 더 어울린다.

라우팅 알고리즘을 분류하는 또 다른 방식은 정적 알고리즘과 동적 알고리즘으로 분류하는 것이다. 정적 라우팅 알고리즘에서 경로는 아주 느리게 변하는데, 종종 사람이 개입(예: 사람이 직접 링크 비용을 수정)한 결과로 그렇게 된다. 동적 라우팅 알고리즘은 네트워크 트래픽 부하나 위상 변화에 따라 라우팅 경로를 바꾼다. 동적 알고리즘은 주기적으로, 혹은 위상이나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.

1. 링크 상태 알고리즘

링크 상태 알고리즘에서는 네트워크 토폴로지와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다는 점을 기억하라. 이것은 각 노드가 자신과 직접 연결된 링크의 식별자와 비용 정보를 담은 링크 상태 패킷을 네트워크상의 다른 모든 노드로 브로드캐스트하게 함으로써 가능하다. 실제로 이는 링크 상태 브로드캐스트 알고리즘에 의해 수행된다. 노드들의 브로드캐스트를 통해 모든 노드는 네트워크에 대한 동일하고 완벽한 관점을 갖게 된다. 각 노드는 이제 LS 알고리즘을 이용해 다른 노드와 똑같은 최소 비용 경로 집합을 계산할 수 있다.

다익스트라 알고리즘은 하나의 노드(u)에서 네트워크 내 다른 모든 노드로의 최소 비용 경로를 계산한다. 다익스트라 알고리즘은 반복적이고, 알고리즘의 k번째 반복 이후에는 k개의 목적지 노드에 대해 최소 비용 경로가 알려지며 이 k개의 경로는 모든 목적지 노드로의 최소 비용 중에서 가장 낮은 비용을 갖는 k개의 경로다.

D(x): 알고리즘의 현재 반복 시점에서 출발지 노드로부터 목적지 v까지의 최소 비용 경로의 비용
p(v): 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드
N': 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있다면, v는 N'에 포함된다.

중앙 집중형 알고리즘은 초기화 단계와 반복 부분으로 수행된다. 반복 부분의 수행 횟수는 네트워크의 노드 수와 같다. 반복 부분 수행이 종료되면 알고리즘은 출발지 노드 u에서 네트워크상의 다른 모든 노드로의 최단 경로를 산출할 수 있다.

INITIALIZATION:
N' = {u}
for all nodes v
	if v is a neigbor of u
    	then D(v) = c(u, v)
    else D(v) = INF
LOOP:
	find w not in N' such that D(w) is a minimun
    add w to N'
    update D(v) for each neigbor v of w and not in N'
    	D(v) = min(D(v), D(w) + c(w, v)
until N' = N

예를 들어, 그림 5.3의 네트워크 u로부터 모든 가능한 목적지까지의 최소 비용 경로를 계산하자. 표 5.1의 각 행은 각 반복이 끝난 후의 알고리즘의 변수값이다.

초기화 단계에서 u로부터 직접 연결된 이웃 v, x, w까지의 현재 알려진 최소 비용 경로는 각각 2, 1, 5로 초기화된다. 특히 u에서 w로 직접 연결된(1홉) 링크의 비용이 5이므로 w까지의 비용이 5로 설정되어 있음을 알아야 한다.
첫 번째 루프에서는 N' 집합에 아직 포함되지 않은 노드 중에서 이전 반복이 끝난 시점에서 최소 비용을 가진 노드를 찾는다. x를 집합 N'에 추가한다. 모든 노드 v에 대한 D(v)를 갱신한다. 그 결과는 표 5.1의 1단계에 보여진다. v로의 경로 비용은 변하지 않는다. 한편 노드 x를 통한 w로의 경로 비용(초기화 단계에서는 5였던)은 4임을 알 수 있다. 따라서 더 낮은 비용을 갖는 이 경로가 선택되고 u에서부터 w까지 최단 경로상의 w의 직전 노드는 x가 된다. 마찬가지로, y로의 (x를 통한) 비요은 2이므로 테이블이 그게 맞게 갱신된다.
두 번째 루프에서 노드 v와 y가 최소 경로 비용을 갖는다는 사실을 알게 되고 둘 중 임의로 하나를 골라 y를 N'에 넣는다. 이제 N'에는 u, x, y가 있다. N'에 없는 남은 노드들까지의 비용은 갱신되어 표 5.1의 2단계에 보인다.
계속...

링크 상태 알고리즘이 종료된 후에 우리는 각 노드에 대해 출발지 노드로부터의 최소비용 경로상의 직전 노드를 알게 된다. 각각의 직전 노드는 또 그 직전 노드를 가지며 이러한 방식으로 출발지에서 모든 목적지까지의 전체 경로를 구축할 수 있다. 한 노드, 예를 들어 노드 u의 포워딩 테이블은 각 목적지에 대해 노드 u에서 그 목적지까지의 최소비용 경로상의 다음 홉 노드 정보를 저장하여 구성한다.

이 알고리즘의 시간 복잡도는 얼마인가? 첫 번째 반복에서 최소 비용이 이미 계산된 노드의 집합 N'에 포함되지 않은 노드 w를 결정하기 위해 모든 노드 n개를 검사해야 한다. 그 다음에는 n-1개, n-2개...를 검사해야 하므로 찾아야 하는 노드의 총 수는 n(n+1)/2이다. 따라서 O(n^2)의 시간 복잡도를 갖는다.

2. 거리 벡터 알고리즘

링크 상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면에, 거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. 각 노드는 하나 이상의 직접 연결된 이웃으로부터 정보를 받고, 계산을 수행하며, 계산된 결과는 다시 그 이웃들에게 배포한다는 점에서 분산적이다. 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다는 점에서 반복적이다. 또한 톱니바퀴 돌듯이 모든 노드가 서로 정확히 맞물려 동작할 필요가 없다는 점에서 비동기적이다.

노드 x부터 y까지의 최소비용 경로의 비용을 d_x(y)라고 하자. 그러면 최소 비용은 벨만포드 식에 의해 다음처럼 나타난다.

d_x(y)=min_v{c(x,v)+d_v(y)}(식5.1)

여기서 min_v는 x의 모든 이웃들에게 적용된다. x에서 v로 이동한 후, v에서 y까지의 최소 비용 경로를 택한다면, 경로 비용은 c(x,v)+d_v(y)일 것이다. 반드시 하나의 이웃 노드 v로 가는 것부터 시작해야 하므로, x에서 y까지의 최소 비용은 모든 이웃 노드 v에 의해 계산된 c(x,v)+d_v(y) 중 최솟값이 된다.

벨만포드 식의 해답은 각 노드 포워딩 테이블의 엔트리를 제공한다. 식 5.1을 최소로 만드는 이웃 노드를 v라고 하자. 이떄 만약 노드 x가 노드 y에게 최소 비용 경로로 패킷을 보내기 원한다면, 노드 x는 패킷을 노드 v로 전달해야 한다. 그러므로 노드 x의 포워딩 테이블에는 최종 목적지 y로 가기 위한 다음 홉 라우터로 v*가 저장되어 있어야 한다. 벨만포드 식의 또 다른 역할은 DV 알고리즘에서 일어나는 이웃 간 통신을 제안한다는 것이다.

기본 아이디어는 다음과 같다. 예를 들어 출발지 노드를 x라고 가정하면, 노드 x는 자신으로부터 집합 N에 속한 다른 모드

윤휘영

이전 포스트

소프트웨어 공학(2)

다음 포스트