5.2 라우팅 알고리즘

라우팅 알고리즘의 목표는 송신자부터 수신자까지 좋은 경로(=최소 비용)를 결정하는 것이다.

라우팅 문제를 나타내는데에는 그래프가 매우 적합하다.

G=(N, E)로 나타낼 수 있고 N은 라우터 E는 물리 링크에 대입된다.

최단 경로를 구하는 두 가지 접근 방식이 있다.

◾ 정적 라우팅 알고리즘. 모든 경로를 미리 알고있어서 경로가 고정된다. (=link state)

◾ 동적 라우팅 알고리즘. 인접한 경로만 알고 상황에 따라 경로를 바꾼다. (=distance vector)

1) 링크 상태(link state) 라우팅 알고리즘

모든 경로를 미리 알 수 있는 이유는 노드들이 브로드캐스팅을 통해 서로 동기화가 되기 때문이다.

링크 상태 라우팅 알고리즘은 다익스트라 알고리즘 그 자체이다.

모든 경로를 미리 알고있다는것은 엣지의 가중치를 모두 알고있다는 얘기이기 때문에 다익스트라 알고리즘을 수행하면 최적의 경로가 산출된다.

목적지까지의 최소 비용을 백트래킹 하면 경로를 구할 수 있다.

하지만 현실적으로 전 세계에 존재하는 모든 라우터가 동기화 되는것은 불가능에 가깝기 때문에 브로드캐스팅의 범위는 관리주체가 동일한 하나의 네트워크 까지만이다.

2) 거리 벡터(distance vector) 라우팅 알고리즘

동적 계획법에 의해 구해지지만 모든 경로를 미리 알고있는 상태가 아니므로 인접 노드들과 메시지를 주고 받으며 자신의 거리 벡터를 갱신하여 라우팅 테이블을 작성해나간다.

인접 노드로부터 거리 벡터 메시지를 받으면 자신의 거리 벡터를 갱신하고 갱신이 이루어졌을 경우 인접 노드들에게 거리 벡터 메시지를 보낸다.

더이상 자신의 거리 벡터가 갱신되지 않으면 안정화가 되어서 거리 벡터 메시지를 보내지 않는다.

◾ 거리 벡터 알고리즘: 링크 비용 변경과 링크 고장

만약 링크의 비용이 변경되는 경우 링크와 연결된 노드들은 자신의 거리 벡터를 다시 계산하고 갱신되면 인접 노드들에게 거리 벡터 메시지를 보낸다.

링크의 비용이 기존보다 더 작아진 경우에는 금방 안정화가 이루어지지만 기존보다 더 커진경우에는 갱신 횟수가 굉장히 많아질 수 있다. (무한 계수 문제, count to infinity problem)

◾ 거리 벡터 알고리즘: 포이즌 리버스 추가

자신의 거리 벡터를 갱신할 때, 인접 노드로부터 받은 거리 벡터에 의해 갱신이 이루어지면 경유하는 경로에 해당하는 노드에게는 자신의 경로를 무한대라고 알려준다.

위의 그림에서 z-x의 경로는 초기에 7이었으나 거리 벡터 알고리즘에 의해 최종적으로 y를 경유하는 3으로 갱신된다.

이 때, y를 경유해서 갱신되었기 때문에 next hop인 y에게는 z-x의 비용을 무한대라고 알려준다.

◾ LS와 DV 알고리즘의 차이

5.3 인터넷에서의 AS 내부 라우팅: OSPF

하지만 LS, DV 알고리즘 둘 다 대규모 네트워크에 직접 적용하기에는 문제가 있다.

LS는 브로드캐스팅을 주고받느라 포워딩 테이블이 영원히 완성되지 않을것이고, DV는 라우팅 테이블의 안정화가 영원히 이뤄지지 않을 것이다.

이 문제는 라우터들을 자율 시스템(autonomous system, AS)으로 조직화 해서 해결할 수 있다.

AS는 동일한 관리 제어하에 있는 라우터의 그룹으로 구성되고 같은 AS 안에 있는 라우터들은 동일한 라우팅 알고리즘을 사용한다. (예: 대학교, 지역ISP)

AS들은 ICANN의 지역 등록 기관에 의해 AS번호가 부여되어 관리된다.

ISP간에 계층이 존재해서 서로 제공자-고객 관계가 되어 비용을 지불하는 것처럼 AS간에도 계층이 존재해서 제공자-고객 관계가 성립한다. (예: 지역ISP-대학교)

제공자-고객 관계는 암묵적으로 연결이 필요한쪽이 고객이 된다.

AS가 서로를 필요로 하는 경우는 제공자-고객 관계가 성립되기 어렵기 때문에 피어링이라는 동등한 관계로 맺어진다.

OSPF 프로토콜은 모든 라우터가 아닌 AS 내부의 라우터들만 링크 상태 알고리즘을 수행한다.

5.4 인터넷 서비스 제공업자(ISP) 간의 라우팅: BGP

동일한 AS 내부에 있는 출발지와 목적지 사이에서 패킷을 라우팅 할 때의 경로는 AS 내부 라우팅 프로토콜에 의해 결정된다. 하지만 패킷이 여러 AS를 통과하게 되는 경우 AS간의 라우팅 프로토콜이 필요하게 된다.

통신하는 AS간의 프로토콜은 동일해야 하고 일반적으로 경계 게이트웨이 프로토콜(BGP, Border Gateway Protocol)을 사용한다.

AS 가장자리에 있는 게이트웨이 라우터들 끼리 BGP가 이루어진다.

경로 정보를 인접한 AS에게 자신의 AS 번호를 담아서 브로드캐스팅 하면 AS 경로가 누적되어 계속 브로드캐스팅 된다.

이렇게 받은 경로 정보들 중 원하는 경로를 선택하는 것은 각 AS의 정책에 의해 이루어진다.

가장 짧은 경로를 선택하는것이 이상적이지만 보통은 고객 AS에게 보내는걸 우선적으로 한다. (고객 > 피어 > 제공자 순)

5.6 인터넷 제어 메시지 프로토콜(ICMP)

호스트와 라우터간에 네트워크 계층 정보를 주고받기 위해 사용되는 프로토콜이다.

주로 오류보고에 사용된다.

ICMP는 라우터가 생성하며 IP 패킷의 데이터 영역에 담겨서 전송된다.

traceroute가 ICMP로 구현되어있다. TTL을 1부터 점차 늘려나가서 경로를 추적한다.

4.1 네트워크 계층 개요

라우터는 네트워크, 링크, 물리 3개 계층만 존재한다.

라우터는 IP 패킷만 인식해서 포워딩(전달)된다.

1) 포워딩과 라우팅: 데이터 평면과 제어 평면

◾ 포워딩

입력 링크에 도달한 패킷을 올바른 방향의 출력 링크로 이동시킨다.

라우터 내부의 포워딩 테이블을 참조해서 목적지 주소에 맞는 출력 링크를 고를 수 있다.

◾ 라우팅

라우팅 알고리즘은 경로를 계산해서 포워딩 테이블을 채운다.

포워딩 테이블은 단일 주소와 출력 링크를 매핑하지 않고 주소의 범위와 출력 링크를 매핑해서 관리한다.

단일 주소-링크 매핑으로 관리한다면 테이블의 사이즈가 기하급수적으로 커지기 때문이다.

또한 범위로 관리하면 일정 비트까지 중복되는 경우가 존재하는데, 이때는 prefix 비트가 가장 많이 매칭된 링크로 이동된다.

2) 네트워크 서비스 모델

인터넷 네트워크 계층은 최선형 서비스(best-effort service)라는 것을 제공한다.

말이 최선형 서비스일 뿐이지 패킷의 대역폭, 손실, 순서, 지연을 보장하지 않는다.

4.2 라우터 내부에는 무엇이 있을까?

라우팅 프로세서가 포워딩 테이블을 만들면 각 입력 포트에 독립적으로 저장된다.

4.3 인터넷 프로토콜(IP): IPv4, 주소 지정, IPv6 등

현재 사용 중인 IP는 IPv4와 IPv6 두 가지 버전이 있다.

1) IPv4 데이터그램 형식

2) IPv4 데이터그램 단편화

패킷은 전송될 때 다수의 링크를 거쳐간다. 하지만 각 링크별로 보낼 수 있는 데이터의 최대 크기(Maximum Transmission Unit, MTU)가 다르기 때문에 패킷의 크기가 MTU보다 작다면 패킷은 단편화된다.

패킷은 단편화되면서 헤더에 정보를 기록한다.

3) IPv4 주소체계

IP 주소는 특정 호스트를 지칭하는 것이 아닌 인터페이스를 지칭한다.

그렇기 때문에 하나의 호스트가 여러개의 IP를 가질 수 있고 대표적으로 라우터가 있다.

IP 주소가 마구잡이로 할당된다면 포워딩 테이블의 규칙성은 사라지고 1:1 매핑만으로 해결할 수 있기 때문에 포워딩 테이블의 크기가 기하급수적으로 커지고 탐색 속도도 매우 느려지는 문제가 발생한다.

그래서 IP 주소는 계층화 되어 구성되고 그에 따라 할당된다.

앞 부분(network prefix)은 어떤 네트워크에 속하는지(네트워크 ID), 뒷 부분은 어떤 호스트인지(호스트 ID)를 나타낸다.

12.34.158.0/24(서브넷 마스크)는 network prefix 24비트가 네트워크 ID 라는것을 의미한다. (=12.34.158)

결과적으로 같은 네트워크 상에 속한 호스트들은 동일한 네트워크 ID를 가지기 때문에 포워딩 테이블의 구성이 단순해진다.

추가로 12.34.158.0/24 와 같은 표기방식은 사람이 읽기 편할뿐, 실제 서브넷 마스크는 기계가 이해할 수 있어야 하기 때문에 위와 같이 관리한다.

과거에는 network prefix를 고정해서 특정 기관에 따라 배분해서 사용했지만 비효율적이기 때문에 최근에는 가변적으로 운용한다.

이러한 주소 할당 방식을 CIDR(Classeless Interdomain Routing) 이라고 한다.

◾ 서브넷(subnet)

같은 네트워크 ID를 가진 호스트의 집합이다.

같은 서브넷에 속한 호스트들은 라우터를 거치지 않고도 서로 접근이 가능하다.

라우터도 마찬가지로 호스트이지만 여러개의 인터페이스를 가졌기 때문에 라우터끼리도 서브넷이 구성된다.

그렇기 때문에 라우터는 여러개의 서브넷에 걸쳐있는 호스트라고 볼 수 있다.

◾ 주소 블록 획득

서브넷에서 사용하기 위한 IP 주소 블록은 ISP에서 얻어야 하고 ISP도 마찬가지로 상위 기관에서 얻어야 한다.

이 상위기관이 ICANN이고 최상위 국제 기관이다. ICANN은 IP 주소 할당과 DNS 루트 서버를 관리한다.

◾ 호스트 주소 획득: 동적 호스트 구성 프로토콜(DHCP)

일반적으로 IP 주소를 호스트에게 고정적으로 할당해 주는것은 호스트가 항상 네트워크에 접속하고 있는것은 아니기 때문에 효율적이지 못하다.

예를 들어 호스트가 1만개 존재하지만 실제 네트워크를 이용중인 호스트가 50%라고 하더라도 존재하는 호스트에게 IP 주소를 모두 할당하기 때문에 매우 비효율적이다.

그렇기 때문에 호스트에게 요청이 들어올 때 DHCP 서버가 해당 호스트에게 IP 주소를 대여해준다.

이 때, IP 주소의 대여시간이 정해져있고 시간이 지나면 IP 주소는 회수된다.

실제 네트워크에 접속하려는 호스트들과 대여-회수가 이루어지기 때문에 더 적은수의 IP 주소로도 운영이 가능해진다.

참고로 서버-클라이언트 관계이기 때문에 DHCP는 애플리케이션 계층 프로토콜이다.

4) 네트워크 주소 변환(NAT)

IPv4는 약 43억개의 주소를 할당할 수 있는데 시간이 지남에 따라 수 많은 디바이스들이 IP를 사용되면서 IP 할당에 문제가 발생할 가능성이 생겼다. 이에 대한 해결책으로 NAT와 IPv6가 있다.

IPv6는 비용적인 문제로 현실적으로는 어렵기 때문에 NAT로 문제를 우회한다. 해결이 아닌 우회임을 알아야 한다.

NAT는 한마디로 말하자면 사설망이다. 하나의 공인 IP 주소를 여러 호스트가 사용할 수 있도록 해주는 일종의 트릭이다.

우리가 흔히 사용하는 공유기를 떠올리면 이해하기 쉽다.

게이트웨이에서 패킷이 송신될 때 NAT 변환 테이블에는 IP와 포트가 기록된다.

송신될 때 포트번호가 변환되기 때문에 서브넷의 호스트들은 동일한 포트를 사용할 수 있다.

다수의 사설 IP 주소와 하나의 공인 IP 주소가 NAT 변환 테이블에 의해 서로 변환된다.

◾ NAT 사용시 발생하는 문제점

NAT 사용시 서브넷 내부에서 서버를 운영하기 매우 어렵다는 문제가 있다.

NAT 변환 테이블에 기록되려면 패킷이 한번은 송신되어야 하는데 서버는 먼저 송신하는게 아니라 수신을 기다리기 때문에 테이블에 기록되지 않는다.

가능하게 하려면 게이트웨이의 NAT 변환 테이블을 직접 수정해야 하지만 수정 권한이 없다면 서버를 구축하기 매우 어려워진다.

또 한가지 문제로 계층구조를 침범하는 문제가 있다.

게이트웨이가 호스트를 구별하는데에 IP 주소가 아닌 포트번호를 사용할 뿐만 아니라 네트워크 계층임에도 불구하고 NAT 변환 테이블 작성을 위해 트랜스포트 계층에서 작성된 포트번호를 바꾼다.

3.5 연결지향형 트랜스포트: TCP

TCP에서 중요한 세가지를 꼽으면 신뢰성 있는 데이터 전송(reliable data transfer), 흐름 제어(flow control), 혼잡 제어(congestion control)이다.

1) TCP 연결

• TCP는 단일 송신자와 단일 수신자 한 쌍의 소켓을 위해서만 동작한다(point-to-point).
• 전송 데이터의 신뢰성이 있고 전송 순서를 지킨다.
• 파이프라인화 되어있어서 다수의 패킷을 한번에 처리한다.
• 전이중(full-duplex) 서비스를 제공한다. 하나의 TCP 소켓은 송수신이 모두 가능하다.
• 연결지향형이다. TCP 연결은 오직 종단 시스템에서만 동작한다.
• 흐름 제어가 가능하다. 네트워크나 수신자의 상태에 맞게 패킷 전송이 제어된다.

2) TCP 세그먼트 구조

◾ 순서번호(seq. no.)와 확인응답(ack. no.) 번호

순서번호는 단순히 1, 2, 3 이렇게 정해지는것이 아니라 전송된 바이트 스트림에 의해서 정해진다.

세그먼트의 첫 번째 바이트의 바이트 스트림 번호가 순서번호가 된다.

확인번호는 조금 다르다.

송신자에게 전달된 피드백에 담긴 확인번호의 의미는 "수신자가 송신자에게 받기를 기대하는 순서번호" 이다.

예를들어 위의 그림처럼 MSS가 1000인 세그먼트 데이터 스트림에서 피드백에 ACK#1000이 담겨져서 돌아왔다면 첫 번째 세그먼트는 잘 받았으니 2번째 세그먼트를 전달받기를 기대한다는 의미가 된다.

3) 왕복시간(RTT) 예측과 타임아웃

타임아웃의 시간은 RTT 시간을 측정하고 여유 시간을 조금 더해서 결정한다.

우선 샘플RTT를 측정해야 하는데, 세그먼트 전송 직후 타이머를 실행해서 피드백을 받을 때까지로 측정한다. 단, 재전송한 세그먼트는 샘플RTT에 포함되지 않는다.

샘플RTT는 큐잉 지연 등 변동성이 크기 때문에 불규칙하기 때문에 가중평균을 구한다.

샘플RTT의 평균에 여유값을 약간 더해서 타임아웃 시간을 정한다.

4) 신뢰적인 데이터 전달

송수신측의 소켓이 연결되면 각각 send/receive 2개의 버퍼와 송신측에 타이머가 생성된다.

send 버퍼는 혹시 모를 재전송을 위해, receive 버퍼는 In-order를 지키기 위해 존재한다.

중간에 패킷이 유실되어서 타임아웃이 발생하면 timer가 가리키는 세그먼트가 재전송된다.

호스트의 각 소켓별로 위와 같은 구조를 가지고있다.

◾ 빠른 재전송

패킷 손실에 의한 타임아웃이 발생해서 재전송 되는것은 신뢰성이 보장되기는 하지만 넉넉히 잡은 시간이기 때문에 타임아웃이 빈번하게 발생할수록 지연이 증가되기 때문에 타임아웃 전에 송신자에게 전달된 ACK 피드백이 일정 횟수 중복된다면 손실로 판단하고 타임아웃 전에 재전송을 한다.

일반적으로 3회 중복 수신 시, 손실로 판단한다.

5) 흐름제어

송수신자의 데이터 처리 속도 차이를 해결하기 위한 기법이다. 수신자가 송신자에게 자신의 상태를 피드백 하는것이 기본 개념이다.

receive 버퍼가 프로세스에 의해 읽혀서 비워지는 속도보다 버퍼에 세그먼트가 쌓이는게 더 빨라지면 receive 버퍼는 오버플로우가 일어나게 될 것이다.

이 때, receive 버퍼의 window size(receive window, rwnd)를 송신자에게 알려준다. 그러면 송신자가 송신여부를 판단하여 전송 흐름을 제어할 수 있다. TCP 헤더에 window size가 포함되는 이유는 이 때문이다.

send 버퍼의 window size는 매핑된 소켓 receive 버퍼의 window size에 의존적이다.

receive 버퍼의 window size만 알면 되기 때문에 흐름 제어는 매우 직관적이다.

◾ receive window(rwnd) = 0인 경우

receive 버퍼가 가득 차서 rwnd가 0이 되면 송신자는 더 이상 전송하지 않고 대기 상태가 된다.

이 때, 송신자가 다시 전송을 시작하려면 수신자는 ACK 피드백을 통해 현재 rwnd 여유가 생겼다는것을 송신자에게 알려주어야 한다. 하지만 수신자의 send 버퍼까지 비어있다면 데드락이 발생하게 된다.

해결책은 rwnd가 0이 되면 송신자의 영속(Persistence) 타이머가 주기적으로 ACK를 받기 위한 1바이트 길이의 데이터(prove packet)를 전송하여 상황을 알아본다.

참고로 UDP는 흐름제어를 제공하지 않는다.

◾ 어리석은 윈도우 신드롬 (Silly Window Syndrome)

송신측의 데이터가 저속으로 1바이트씩 발생하거나, 수신측이 저속으로 1바이트씩 처리하는 경우에 1바이트 데이터 전송을 위해 데이터보다 큰 헤더가 부가적으로 붙는 오버헤드가 발생하는 현상이다. 네트워크의 자원이 낭비된다.

이 때, 송신자는 Nagle 알고리즘, 수신자는 Clark 솔루션 또는 지연 확인을 사용하여 해결할 수 있다.

6) TCP 연결 관리

TCP는 3-way handshake 절차를 거쳐 소켓이 서로 연결된다.

3-way handshake

1. 클라이언트 TCP가 서버 TCP에게 SYN 세그먼트를 전송한다.
2. 서버 TCP가 버퍼와 변수들을 할당하고 클라이언트 TCP로 연결 승인 세그먼트(SYN ACK)를 전송한다.
3. 클라이언트 TCP도 버퍼와 변수들을 할당하고 서버로 또 다른 세그먼트(SYN ACK에 대한 ACK)를 송신한다.

 

3번의 ACK 메시지는 일반적인 ACK피드백과 같다. 1,2번은 세그먼트에 헤더만 담기지만 3번부터는 데이터도 담을 수 있다.

연결 종료는 서로 요청-응답을 주고 받으면 연결이 종료된다.

3.6 혼잡제어의 원리

◾ 혼잡

네트워크가 처리할 수 있는 양보다 더 많은 데이터가 들어왔을 때 생기는 현상. (=라우터의 버퍼가 가득 찬 경우)

1) 혼잡의 원인과 비용

세 가지 시나리오를 통해 혼잡제어의 개념을 익히도록 한다.

◾ 시나리오 1: 2개의 송신자와 무한 버퍼를 갖는 하나의 라우터

라우터의 버퍼가 무한하기 때문에 손실이 일어나지 않고 재전송도 필요가 없어진다. 또한 흐름제어나 혼잡제어도 수행하지 않는다.

이 때 패킷은 용량 R의 공유 출력 링크로 전달되고 연결당 처리량은 최대 R/2까지 증가한다.

전송률이 R/2보다 커지더라도 연결당 처리량은 R/2를 넘길 수 없다.

그리고 전송률이 R/2에 근접할수록 큐잉지연이 커진다.

◾ 시나리오 2: 2개의 송신자와 유한 버퍼를 갖는 하나의 라우터

이제 버퍼가 유한해졌으므로 패킷 손실이 발생할 수 있다. 그에 따라 재전송도 일어날 수 있다.

우선 라우터의 버퍼가 비어있는지 알아낼 수 있다고 가정을 해본다.

그러면 손실이 일어나지 않아서 마찬가지로 최대 R/2의 송신률을 가진다.

두번째로 패킷 손실을 확실히 알았을 때만 재전송을 한다고 가정을 해본다.

송신자는 재전송을 통해 패킷 손실을 처리해야하기 때문에 실제 수신된 패킷은 송신된 패킷보다 적게된다.

마지막으로 패킷 손실이 일어나지는 않았지만 타임아웃이 너무 일찍 일어난다고 가정을 해본다.

두번째와 같은 경우가 발생한다.

송신자가 데이터를 많이 보내서 혼잡이 발생했는데, 재전송으로 인해 더 많이 보내는 악순환이 일어난다.

◾ 4개의 송신자와 유한 버퍼를 갖는 라우터, 그리고 멀티홉 경로

각자의 호스트가 데이터를 전송하면 일정 수준까지는 잘 전송되다가 어느 지점에 도달하면 큐가 가득차서 손실이 일어나게된다.

패킷이 경로상에서 버려질 때, 버려지는 지점까지 패킷을 전송하는데 사용된 상위 라우터의 전송용량은 헛된 것이 된다.

결과적으로 송신자가 데이터를 많이 보내면 보낼수록 수신자의 수신률이 떨어지는 역설적인 상황이 발생하게 된다.

2) 혼잡제어에 대한 접근법

• 종단간의 혼잡제어
  네트워크 계층은 트랜스포트 계층에 혼잡제어 목적을 위한 아무런 지원도 해주지 않기 때문에 혼잡의 존재는 종단 시스템에서 추측해야만 한다.
• 네트워크 지원 혼잡제어
  네트워크 계층 구성요소가 송신자에게 직접적인 피드백을 제공한다.
  라우터가 직접 송신자에게 초크 패킷을 송신해서 알려주거나 송신중인 패킷에 혼잡 여부를 표시하면 수신자가 송신자에게 피드백으로 돌려주는 방법이 있다. 후자는 왕복 시간이 걸린다는 단점이 있다.

3.7 TCP 혼잡제어

TCP는 ACK 피드백 수신 여부에 따라 네트워크의 상태를 추측한다.

send 버퍼의 window size를 결정하는 요소는 rwnd와 더불어 congestion window(cwnd)가 존재한다.

rwnd와 cwnd 둘 중 작은값으로 send buffer의 window size가 정해진다.

rwnd는 수신자의 receive buffer window size이고 cwnd는 라우터 버퍼 여유공간의 추측 크기이다.

cwnd는 rwnd처럼 크기를 정확하게 알 수 없고 ACK 피드백 수신(손실) 여부에 따라 크기가 정해진다.

보통 초기 cwnd의 크기는 1MSS로 설정된다.

TCP의 혼잡제어는 cwnd에 의해 이루어지고 cwnd의 값을 결정하는 알고리즘들이 존재한다.

◾ 가법적 증가, 승법적 감소(additive-increase, multiplicative-decrease. AIMD)

정상적인 ACK 피드백을 받을 때마다 cwnd가 1MSS씩 증가하고 손실이 일어날 때 마다 cwnd를 1/2 감소시킨다.

◾ 슬로 스타트

정상적인 ACK 피드백을 받을 때마다 cwnd가 1MSS 증가하고 MSS크기의 세그먼트를 2개 전송한다. 손실이 일어나면 cwnd는 1MSS로 초기화된다.

초기 전송률이 매우 낮은 상태에서 시작해서 지수적으로 증가하다가 손실이 발생하면 처음부터 시작하는 것이다.

손실이 발생해서 슬로 스타트가 다시 시작될 때, 두 번째 상태 변수인 ssthresh(slow start threshold, 슬로 스타트 임계값)을 cwnd/2로 설정한다. 그이후 cwnd가 지수적으로 증가하다가 임계값에 도달하면 혼잡 회피 모드로 전환하여 cwnd를 조심스럽게 증가시킨다.

패킷 손실에 의한 재전송이 이루어지는 경우는 ACK 피드백을 받지 못해 타임아웃으로 인한 재전송이 일어나거나 중복된 ACK 피드백을 3개 받아서 빠른 재전송이 이루어졌을 때이다.

이 두가지 상황중 빠른 재전송은 타임아웃에 의한 손실 처리보다 덜 심각하다. 패킷 손실이 일어난 순간만 혼잡하고 이후 ACK 피드백을 받을 때는 네트워크 환경이 정상적이라는 의미이기 때문이다.

그래서 빠른 재전송에 의한 손실 처리가 발생할 때에는 cwnd를 1MSS로 초기화 하는게 아니라 cwnd와 ssthresh 둘 다 1/2로 줄여서 cwnd의 값을 보정해준다. (=빠른회복)

◾ TCP 처리율(=속도)의 거시적 설명

TCP의 속도는 네트워크의 상황에 따라 결정되므로 네트워크 계층에서 결정된다고 볼 수 있다.

만약 손실이 전혀 없다면 w / RTT가 성립하지만 이론적일 뿐이다.

정확한 속도는 알 수 없고 손실 이벤트가 발생하는 시점의 윈도우 크기를 W, 왕복시간을 RTT라고 했을 때,

TCP 연결의 평균 속도 = (0.75 * W) / RTT 이 성립한다.

1) 공평성

각기 다른 K개의 종단시스템이 Rbps의 전송률인 병목 링크를 지난다고 할 때 각 연결의 평균 전송률이 R/K에 가깝다면 혼잡제어 매커니즘은 공평하다고 본다. 

TCP 연결은 혼잡제어에 의해 cwnd가 계속 변하므로 대역폭을 똑같이 공유하는 공평성이 보장된다.

3.1 트랜스포트 계층 서비스 및 개요

애플리케이션 프로세스로부터 수신받은 메시지를 세그먼트로 변환한다.

세그먼트는 네트워크 계층으로 넘겨줄 때 패킷으로 변환된다.

1) 트랜스포트 계층과 네트워크 계층 사이의 관계

트랜스포트 계층 프로토콜은 애플리케이션 계층과 네트워크 계층간에 메시지를 운반할 뿐이다. 각 계층은 하위 계층에서 무슨 작업을 하는지 신경 쓸 필요가 없다.

2) 인터넷 트랜스포트 계층의 개요

트랜스포트 계층은 TCP와 UDP 두 가지의 프로토콜이 있다.

두 프로토콜의 기본적인 기능은 IP 전달 서비스를 Host-to-Host에서 Process-to-Process로 확장하는 것이다. (다중화와 역다중화)

TCP는 UDP와 다르게 신뢰적 데이터 전달과 혼잡제어를 제공한다.

3.2 다중화와 역다중화

메시지를 알맞는 목적지 프로세스에 전달해주는 작업이다.

UDP와 TCP 모두 지원하는 개념이지만 작동 원리가 조금 다르다.

• 다중화 : 세그먼트들을 네트워크 계층으로 전달하는 작업. 애플리케이션 계층에서 트랜스포트 계층으로 소켓을 통해 메시지가 전달될 때, 하나의 세그먼트로 캡슐화 하여 네트워크 계층으로 전달하는 과정이다.
• 역다중화 : 세그먼트들을 애플리케이션 계층의 올바른 소켓으로 전달하는 작업. 세그먼트의 헤더 정보를 읽어서 올바른 소켓을 판단한다.

UDP는 TCP와 다르게 소켓과 소켓이 1:1 매핑 되지 않는다. (connectionless)

그래서 헤더 정보의 목적지 포트번호만을 보고 전달된다.

TCP는 목적지 포트가 모두 80인데도 불구하고 서로 다른 소켓으로 간다.

그 이유는 "TCP 소켓은 고유의 포트번호가 아닌 고유의 ID(집합)를 가지기 때문"이다.

집합은 출발지의 IP주소/포트번호, 목적지의 IP주소/포트번호 4개 요소로 이루어진다.

4개 요소중 하나라도 다르면 다른 소켓으로 인식하기 때문에 포트번호가 같더라도 역다중화를 통해 올바른 소켓으로 전달된다.

3.3 비연결형 트랜스포트: UDP

UDP가 비연결, 비신뢰성이라고 하더라도 간단한 오류 검출 기능은 가지고 있다.

데이터가 유실될지언정 잘못된 데이터가 전달되지는 않는다.

에러가 없으면 세그먼트를 바로 목적지 포트 소켓으로 넘겨준다. 매우 단순한 구조이다.

단순한 구조인 만큼 오버헤드가 적다.

3.4 신뢰성 있는 데이터 전송의 원리

신뢰성 있는 데이터 전송은 TCP의 중요한 개념중 하나이다.

TCP는 트랜스포트 계층의 애플리케이션 계층에 대한 데이터의 신뢰성을 보장한다. 하지만 하위 계층에서는 데이터의 신뢰성을 보장할 수 없다.

1) 신뢰적인 데이터 전달 프로토콜의 구축

비신뢰적인 데이터 전달이라 함은 데이터의 에러 또는 유실 둘 중 하나가 발생할 수 있다는 의미이다.

◾ 완벽하게 신뢰적인 채널 상에서의 데이터 전송: rdt1.0 (reliable data transfer)
하위 채널이 완전히 신뢰적이라고 가정한다. 이 경우에는 각 레이어가 송수신을 바로 진행시키면 된다. 완전히 신뢰적인 채널에서는 수신 측이 송신 측에게 어떠한 피드백도 제공할 필요가 없고 '천천히' 라는것도 요청할 필요가 없다.

◾ 비트 오류가 있는 채널 상에서의 신뢰적 데이터 전송: rdt2.0
패킷 안의 비트들이 하위 채널에서 손상될 수 있지만 송신 순서대로 수신된다고 가정한다. 전화통화의 예를 생각해보면 된다.
상대방의 말을 잘 들었다면 확인 응답을 해준다(수신자 피드백, ACK). 상대방의 말이 잘 안들리면(에러 검출) 다시 말해달라고 요청하고(수신자 피드백, NAK) 상대방은 같은 말을 다시 해준다(재전송). 이 세가지가 자동 재전송 요구(ARQ) 프로토콜에 요구된다.

송신자 프로토콜은 수신자의 피드백을 받아야 다음 행동을 결정할 수 있으므로 ACK/NAK 패킷을 기다려야 한다.

단, rdt2.0은 피드백 패킷이 손상되어 송신측으로 들어오는 치명적인 문제가 발생할 수 있다.

피드백 패킷이 손상되어 송신자가 ACK/NAK를 판별하지 못할 때, 재전송을 한다면 수신자는 패킷의 중복 수신이 발생하므로 패킷에 순서번호(sequence number)를 추가해서 수신자가 중복 수신을 처리하게 한다. 순서번호는 최소 1비트면 충분하다. 이 개선사항을 rdt2.1이라고 하자. 순서번호 비트인 0, 1을 처리하기 위해 기존의 상태보다 2배 많은 상태를 가지게된다.

여기서 한발 더 나아가서 오류검출 및 중복 수신을 송신자 측에서도 같이 처리한다면 NAK 없이 ACK 처리만으로 구현이 된다. (rdt2.2: NAK-free protocol)

수신자에서 오류 검출시 NAK가 아닌 ACK와 함께 마지막으로 수신된 순서번호를 함께 송신자에게 보낸다.

송수신자의 순서번호가 다르면 재전송을 하게 된다.

◾ 비트 오류와 손실 있는 채널 상에서의 신뢰적 데이터 전송: rdt3.0
손실은 수신자에게 가는 메시지가 유실되거나 송신자에게 돌아오는 피드백이 유실되는 두 가지 경우가 존재한다.

어떤 경우간에 송신자 입장에서는 같은 현상이다. 이 때 시간 제한(timeout)을 걸어서 재전송을 하면 손실은 해결할 수 있다.

(d)는 유실이 발생하지는 않았지만 피드백이 지연이 생겨서 늦게 도착하는 바람에 타임아웃이 발생한 경우이다.

rdt3.0까지 구축하며 기능적으로 정확한 신뢰적 데이터 전송 프로토콜을 완성시켰지만 성능에는 만족하기 어렵다.

전송 후 대기 방식이기 때문에 속도가 너무나도 느리다.

2) 파이프라인된 신뢰적 데이터 전송 프로토콜

전송 후 대기 방식은 한번에 하나의 패킷만 보내기때문에 속도가 매우 느리므로 파이프라이닝화 시켜서 효율을 높인다.

3) N부터 반복(Go-Back-N, GBN)

수신자는 받은 올바른 패킷에 대해서만 ACK 피드백을 보내주고 해당되지 않는 패킷은 모두 버리기 때문에 수신측은 버퍼가 필요없다.

패킷 하나의 손실때문에 많은 패킷을 다시 재전송하는 단점이 존재한다.

4) 선택적 반복(Selective Repeat, SR)

GBN과 다르게 수신자도 버퍼를 가지고 ACK를 받지 못한 패킷마다 타이머를 계산한다.

수신자는 받은 패킷의 순서와 상관없이 받은 패킷에 대해 무조건 ACK를 피드백한다.

ACK가 손실되는 경우 송신자의 타이머가 만료되어 재전송되지만 수신자는 이미 받은 패킷이므로 별도의 저장 없이 ACK만 다시 피드백해준다.

2.1 네트워크 애플리케이션의 원리

각 호스트의 프로세스간의 통신이라고 볼 수 있다. IPC와 같은 개념이다.

1) 네트워크 애플리케이션 구조

주로 클라이언트-서버 구조 또는 P2P구조로 이루어진다.

• 클라이언트-서버 : 클라이언트와 다르게 서버는 고정 IP 주소를 가진다.
• P2P : 특정 서버를 통하지 않고 피어가 직접 통신한다.

2) 프로세스 간 통신

서로 다른 종단 시스템에서 프로세스는 네트워크를 통한 메시지 교환으로 서로 통신한다.

소켓을 통해서 네트워크로 메시지를 주고 받는다. 소켓은 애플리케이션 계층과 트랜스포트 계층 간의 인터페이스이다.

3) 애플리케이션이 이용 가능한 트랜스포트 서비스

• 신뢰적 데이터 전송 : 전송한 데이터가 유실되지 않고 온전하게 목적지까지 전달되도록 보장된 전송 서비스.
  트랜스포트 계층 프로토콜이 애플리케이션에 제공할 수 있는 한 가지 중요한 서비스이다.
• 처리량
• 시간
• 보안

4) 인터넷 전송 프로토콜이 제공하는 서비스

• TCP : 연결지향형 서비스와 신뢰적 데이터 전송 서비스를 포함한다.
• UDP : 비연결형 서비스와 비신뢰적 데이터 전송 서비스를 제공한다.

인터넷 트랜스포트 프로토콜은 시간 혹은 대역폭 보장을 제공하지는 않는다.

2.2 웹과 HTTP

1) HTTP 개요

HyperText Transfer Protocol. TCP를 전송 프로토콜로 사용한다. HTTP 서버는 클라이언트에 대한 정보를 유지하지 않으므로 비상태(stateless) 프로토콜 이라고도 한다.

2) 비지속 연결과 지속 연결

TCP 연결 상태에 따라 나뉜다.

• 비지속 연결 HTTP : 각 요구/응답별로 TCP 연결이 새로 이루어진다.
• 지속 연결 HTTP : 연결이 유지된다.

4) 사용자와 서버 간의 상호작용: 쿠키

HTTP 서버는 비상태 프로토콜이지만 쿠키를 이용해서 사용자를 추적하여 상태를 유지시킬 수 있다.

5) 웹 캐싱

웹 캐시 또는 프록시 서버는 원 출처의 웹 서버를 대신해서 HTTP 요구를 충족시켜준다.

캐시는 서버이면서 동시에 클라이언트가 된다.

클라이언트의 요구에 대한 응답시간을 줄이고 트래픽을 대폭 줄일 수 있는 장점이 있다.

2.3 인터넷 전자메일

유저 에이전트, 메일 서버, SMTP 세 가지의 주요 요소로 이루어져있다.

요즘은 HTTP 기반의 메일을 사용한다.

1) SMTP

보내고자 하는 데이터(메일)을 푸시한다.

2) HTTP와의 비교

HTTP는 풀 프로토콜이고 SMTP는 푸시 프로토콜이다.

4) 메일 접속 프로토콜

SMTP는 푸시 프로토콜이지만 최종적으로 메시지를 얻은것은 풀 동작이다.

POP3, IMAP 같은 메일 접속 프로토콜을 이용하면 목적 에이전트가 메일을 받을 수 있다.

2.4 DNSㅡ인터넷의 디렉터리 서비스

1) DNS가 제공하는 서비스

호스트 네임을 IP주소로 변환해준다. DNS는 DNS 서버들의 계층구조로 구현된 분산 데이터베이스이고 호스트가 분산 데이터베이스로 질의하도록 허락하는 애플리케이션 계층 프로토콜이다.

2) DNS 동작 원리 개요

단일 DNS 서버의 중앙 집중 데이터베이스는 확장성이 전혀 없기때문에 분산되도록 설계되었다. 웹 캐싱과 비슷한 개념이다.

• 분산 계층 데이터베이스
  루트 DNS 서버, 최상위 레벨 도메인(TLD) 서버, 책임 DNS 서버 총 3가지 유형의 DNS 서버가 존재한다.
  도메인 네임과 IP의 매핑은 책임 DNS 서버에서 이루어진다.

• DNS 캐싱
  로컬 DNS 서버에 캐시가 존재하는 경우 상위 DNS 서버까지 접근하지 않고도 빠르게 IP 주소를 반환할 수 있다. 보통 일정 시간이 지나면 캐시가 삭제된다.

3) DNS 레코드와 메시지

DNS 서버들은 호스트 네임을 IP 주소로 매핑하기 위해 자원 레코드를 저장한다.

자원 레코드는 Name, Value, Type, TTL 4가지 필드를 포함한다.

Type에 따라 Name과 Value의 의미가 달라진다.

참고로 DNS는 UDP 연결을 사용한다.

2.7 소켓 프로그래밍: 네트워크 애플리케이션 생성

소켓은 OS에서 제공해주는 API이다.

소켓을 생성할 때 TCP/UDP를 선택할 수 있다.