23.08.01

2023. 08. 01 화요일

 

- 최소 신장 트리란? 관련 두 알고리즘 설명, 구현?

: MST(Minimum Spanning Tree).

그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법. 크루스칼과 프림 알고리즘이 있다.

 

크루스칼 알고리즘은 간선을 기준으로 최소 그래프를 연결하는 방법.

간선이 작은 순서대로 연결하며, 사이클이 생길 시에 취소하고 다음 최소 간선을 택한다.

간선이 적을 때 사용된다.

최소 신장 트리의 성격상 사이클을 만들 필요가 없으므로(사이클이 생겼다면 이미 이전에서 최솟값들로 이루어진 간선을 택하는 것이 유리) 사이클을 포기하는 것이다.

 

사이클 확인의 구현 방법은 Union-find라는 배열을 사용한다. 배열은 특정 인덱스 노드의 부모 노드를 탐색하기 위한 기능으로, 두 노드가 연결될 시 두 노드 중 작은 인덱스의 값으로 해당 배열을 초기화한다. (2, 3 노드가 연결되면 2 인덱스에는 ‘2’값이, 3 인덱스에는 3과 2 중 작은 값인 ‘2’로 초기화한다) 해당 방식의 초기화는 직접적인 연관이 없을 때도 특정 두 노드가 연결될 때마다 지속적으로 초기화해주어야 한다. (2-3이 연결되고, 1-2가 연결됐다면 인덱스 2에는 1값이, 인덱스 3 역시 1값으로 바꾸어준다)

 

이를 코드로 구현하는 방법은 두 인덱스를 비교하여 두 인덱스의 부모 인덱스가 같지 않으면 둘의 부모를 같게 하고 가중치를 answer에 더해주는 함수를 구현한다. 이때, 부모를 찾는 과정에서 지속적으로 최고 부모의 인덱스를 갱신하도록 한다.

find(int idx) {

if(parents[idx] == idx) return idx; else return parents[idx] = find(parents[idx]); }

 

프림 알고리즘은 노드(가중치)를 기준으로 최소 그래프를 연결하는 방법.

최초 연결된 노드들 중에 가장 작은 가중치를 택하며 진행한다.

visited 배열로 방문한 배열을 체크하며 진행하며, 특정 노드에서 시작하여 간택된 노드는 true, 이후 연결된 노드들에서 가장 적은 가중치를 택하며 진행한다. visited 배열로 인해 사이클이 생기지 않는다.

 

코드적 구현 방법은 bfs와 동일하게 진행되며, visited 배열을 두어 visited[Node.to]이라면 continue;, 이후 list.get(Node.to)를 돌며 !visited[Node.to] 라면 que.add(Node);

 

 

- 송신 제어를 위한 윈도우 2개? 설명? 최종 단위?

: 송신 제어를 위해 두 가지 윈도우가 존재하며, 두 값 중 작은 값으로 송신측 최종 window 크기를 정한다.

Receiver Window(RWND) - 흐름제어(sliding window)

Congestion Window(CWND) – 네트워크 혼잡 제어

 

최종 단위는 MSS라고 하며, MTU(Maximom Transmission Unit)에서 IP 헤더 길이(20)와 TCP 헤더 길이(20)을 제외한 값이 최종 MSS가 된다.

 

 

- 혼잡 제어란? 알고리즘?

Congestion Window. 네트워크 트래픽을 해결하기 위한 알고리즘.

 

혼잡 제어의 가장 기본이 되는 알고리즘은 AIMD가 있다.

AIMD(Additive Increase/Multicative Decrease)

AIMD는 첫 CWND를 1로 설정하고 송신 후 ACK가 도착하면 1씩 늘려서 보내며 ACK가 도착하지 않을 때까지 송신해본다.

만약 ACK가 도착하지 않는다면 네트워크가 혼잡한 상태이므로, 최고 CWND 값의 1/2만큼 송신하고 다시 거기서부터 1씩 늘려가며 송신한다.

이를 설명이 용이하도록 앞으로는 ACK ? CWND+=1 : CWND/=2 로 표기하겠다.

 

이때 1부터 시작하여 늘려가는 시간이 너무 천천히 진행되기 때문에 이를 해결하기 위해 고안된 방법이 느린 시작과 혼잡 회피 방법이다.

느린 시작(slow start)은 ACK ? CWND*=2 : CWND=1의 방식이고,

CWND를 1로 급작스럽게 떨어트리는 문제를 해결하고자 나온 방법이

혼잡 회피(Congestion Avoidance)이며, 해당 방식은 limit을 정해 limit이 넘어갈 시 AIMD 방식으로 바꾸도록 동작한다. 즉, limit을 넘기 전엔 느린 시작, 넘은 후엔 CWND를 1씩 증가하며 ACK가 도착하지 않으면 1/2로 줄인다.

 

 

- UDP 프로토콜이란? 특징?

: User Datagram Protocol(사용자 데이터그램 프로토콜).

데이터를 보내는 것에 중점이 맞춰져 있으므로, TCP의 연결 설정(3-way handshake), 연결 해제(4-way handshake), 혼잡 제어(sliding window, slow start), 데이터 신뢰성(ACK) 모두 없다. 따라서 효율적이고, 스트리밍 서비스 등에서 사용된다. (데이터 일부 유실 상관없음)

 

UDP는 특성 때문에 브로드캐스팅을 지원한다. 브로드캐스팅이란 동일 네트워크에 연결된 모든 컴퓨터에 데이터 송신을 가능하게 해주는 기능으로, 예를 들어 동일 허브에 연결된 모든 사용자에게 동일하게 데이터를 쏴줄 수 있다.