SLENDER ANKLES's 개발블로그

TCP Three-way HandShaking 이란?

클라이언트와 서버가 통신하기 전 세 번의 패킷 교환을 통해 확인하는 과정을 말합니다.

TCP Three-way HandShaking의 과정

- CLIENT에서 웹 서버로 연결을 최초시도시 먼저 SYN 패킷을 보냅니다.

- SYN 패킷을 보낸 CLIENT는 SYN-SENT 상태가 됩니다.

- SERVER에서 CLOSED는 PORT가 닫혀있는 상태를 뜻하고, 포트가 서비스 가능한 상태인 LISTEN상태로 만들어주어야 합니다.

- LISTEN상태에서 CLIENT로부터 SYN패킷을 받으면 이에 대한 응답으로 SYN + ACK 패킷을 CLIENT로 보냅니다.

- SERVER는 CLIENT IP에 대해 포트 SYN-RECEIVED 상태로 전환됩니다.

- SERVER로부터 SYN+ACK 패킷을 받으면, CLIENT는 ESTABLISHED상태로 변하게 되면서 연결을 확인합니다.

- CLIENT는 SERVER로 SYN에 대한 응답으로 ACK패킷을 보냅니다.

- SERVER는 이 ACK 패킷을 받고 해당 CLIENT IP에 대한 포트 ESTABLISHED상태로 전환됩니다.

- 이로써 SERVER와 CLIENT의 TCP 3-WAY HandShaking 과정을 마치게 됩니다.

Code Bit(TCP Header)

TCP Header에는 Code Bit라는 항목이 있습니다. 이는 6bit로 되어있으며 각각의 bit는 의미를 가지고 있습니다.

URG - ACK - PSH - RST - SYN - FIN 순서로 되어 있으며 해당 위치의 비트에 1이 들어가게 되면 이 패킷의 어떤 패킷인가를 알려주게 됩니다. 즉 000010이라고 하면 SYN 패킷이 되는 겁니다.

Sequence Number

Sequence Number과 Acknowledgemnet Number이 있는데 TCP가 패킷을 주고 받을 때 순서와 Date와 관련됩니다. 

여기서 간단하게 설명하자면, 최초 TCP 3-way HandShaking과정을 Sequence Number과 Acknowledgement Number로 나타내겠습니다.

처음 클라이언트에서 SYN패킷을 보낼 때 Sequence Number(A)에 랜덤으로 숫자를 넣어서 보냅니다. 

여기서는 1이라고 하겠습니다. 서버가 이 SYN패킷을 받게 되면 응답으로 SYN+ACK패킷을 보내게 되는데, 

서버에서 보내는 Sequence Number(B)의 경우 또 랜덤의 숫자를 보내게 됩니다. 

여기서는 편의상 70이라고 하겠습니다. Acknowledgement Number의 경우, 앞 클라이언트에서 보내온 

SYN패킷의 Sequence Number에다 +1을 하여 보내게 됩니다.(A+1). 

즉 여기서는 Sequence Number가 2가 됩니다. 마지막으로 클라이언트에서 서버로부터 오는 

SYN + ACK를 받고 응답으로 ACK 패킷을 보내게 되는데 이때 서버에서 받은 Sequence Number에다 + 1을 

하여 보냅니다.

(B+1) 즉 71이라는 숫자를 Sequence Number로 보내게 됩니다.

참조 : http://cafe.naver.com/nsis/41903

우선 쉽게 설명하겠습니다.

비동기(Asynchronous)

우선 비동기란 말 그대로 동시에 일어나지 않는다는 의미입니다. 무엇이 같이 일어나지 않는 것일까? 바로 요청과 결과가 동시에 일어나지 않을 것이라는 약속입니다. 즉 요청한 즉시 응답해주는 것이 아니라 이따가라도 줄께라는 의미입니다.

동기(Synchronous)

동기란 말 그대로 동시에 일어난다는 의미입니다. 무엇이 같이 일어나는 것인가? 바로 요청과 결과가 동시에 일어난다는 약속입니다. 즉 요청한 즉시 응답해준다는 것입니다.

쉘정렬(Shell Sort)

쉘 정렬은 삽입정렬의 단점을 보완하기 위해 만든 정렬 방법이다.

“삽입 정렬을 하기 전에 미리 정리를 해놓자!”

어떻게 정리를 한단 말인가?

삽입 정렬은 모든 원소에 대해서 검사를 하지만, 쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고, 그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다.

간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다.

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같은 수들이 있다. 간격을 5, 3, 1로 놓고 삽입 정렬을 시작할 것이다.

1) 간격이 5일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같다.

묶음 1 : 45, 44, 77 => 44, 45, 77

묶음 2 : 39, 33, 68 => 33, 39, 68

묶음 3 : 98, 28, 11 => 11, 28, 98

묶음 4 : 15, 40, 43 => 15, 40, 43

묶음 5 : 52, 38 => 38, 52

각 묶음으로 정렬을 수행 한다.

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

2) 간격이 3일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

묶음1 : 44, 15, 39, 52, 98 => 15, 39, 44, 52, 98

묶음2 : 33, 38, 28, 77, 43 => 28, 33, 38, 43, 77

묶음3 : 11, 45, 40, 68 => 11, 40, 45, 68

각 묶음으로 정렬을 수행한다.

15, 28, 11, 39, 33, 40, 44, 38, 45, 52, 43, 68, 98, 77

3) 간격이 1일 경우

보통의 삽입 정렬을 수행한다.

그렇다면 간격은 어떻게 설정하나?

간격을 어떻게 설정하는지에 따라서 성능에 중요한 영향을 끼친다. 배열의 길이를 토대로 잡는다면

첫 번째 간격을 N/2, 두 번째 간격을 N/4 ... 등으로 잡는 방법이 있다.

시간 복잡도?

삽입정렬의 O(n^2)보다는 우수하지만 가장 효율적인 정렬 알고리즘의 O(nlogn)에는 미치지 못한다.

O(n^(4/3)) 정도이다. 또한 increments sequence를 어떻게 하느냐에 따라 성능이 좌우되는데 sequence가 좋지 않는 최악의 경우 복잡도는 O(n^2)가 되어 버린다.

퀵정렬(Quick Sort)

데이터 집합 내에서 한 피벗 값(pivot value)을 고른 다음 그걸 기준으로 두 개의 부분집합으로 나눈다.

한 쪽 부분집합에는 피벗 값보다 작은 것만, 다른 부분 집합에는 큰 것만 넣는다. 더 이상 쪼갤 부분집합이 없을 때

까지 각각의부분집합에 대해 피벗/쪼개기 작업을 재귀적으로 적용한다. 그렇게 하고 나면 최종적으로 정렬된 데이

터 집합이 만들어진다.

퀵정렬의 효율

퀵정렬은 어떤 피벗 값을 고르는지에 따라 성능이 결정된다. 가장 이상적인 피벗 값 은 전체 데이터를 절반씩으로

쪼갤 수 있는 값이다. 피벗 값을 고르고 배열을 쪼갤 때마다 각 원소에 대해 상수 시간 연산을 적용해야 한다. 각 

원소마다 이 작업을  몇 번씩 할까? 최선의 경우는 재귀호출이 이뤄질 때마다 부분 리스트의 크기가 절반씩으로 

줄고, 부분 리스트의 크기가 1이 되면 재귀호출이 끝난다.즉 각 원소에 대해 상수 시간 연산을 하는 횟수 n, n을 

1이 나올 때까지 반복해서 2로 나누는 횟수, 즉 log(n)이다. n개의 원소에 대해 log(n)번씩 연산을 수행하므로 최선

의 경우 복잡도는 O(n log(n))이다. 

하지만 피벗을 잘못 고르면 어떠게 되나?

최악의 경우라면 데이터 집합의 최소값을 피벗 값으로 고를 것이고, 그러면 한쪽 부분집합은 빈 집합이고 다른 집

합에는 n-1개 (피벗 값을 제외한 나머지)가 들어간다. 그러면 재귀호출 횟수가 O(n)이고(균형 전혀 잡히지 않은 

트리는 연결 리스트와 똑같아지는 것과 마찬가지), 최악의 경우 복잡도는 O(n^2)이 된다. 이는 선택 정렬이나 삽입 정렬과 마찬가지 속도다. 

어떻게 구현하나?

삽입정렬

한 번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새 원소를 제 위치에 삽입하는 식으로 정렬된 배열을 

만든다.

삽입정렬의 효율

삽입 정렬은 최선의 경우, 즉 리스트가 이미 정렬돼 있을 때, O(n)이다.

이미 정렬된 리스트에 새 원소를 추가할 때는 삽입 정렬이 매우 효율적이다. 

그러나 평균 및 최악의 경우에는 O(n^2)이기 때문에 무작위로 정렬된 많은 데이터를 처리하기에는 좋은 알고리즘은 아니다.