TCP connection managementTCP를 이용해서 데이터를 주고 받으려면, 그 전에 먼저 sender와 receiver 사이에 'handshake'가 필요하다.연결 설정하는 것에 서로 동의하고, 어떤 seq 넘버를 시작점으로해서 데이터를 주고 받을 지 서로에게 알리는 과정을 거치는 것이다. UDP는 이 과정이 필요없다. 내가 보내고 싶으면 상대방이 준비되어 있는지 확인하지 않고 그냥 보내면 된다.하지만 TCP는 신뢰성을 보장해야 하기 때문에 연결을 설정하는 과정을 사전에 거쳐야 한다. 사전에 협의하는 내용은 구체적으로 아래와 같다. 1. 서로의 IP, port 번호, TCP 소켓 여부를 확인한다.2. 데이터를 보낼 때 시작할 initial Seq Number (항상 0으로 시작하는게 아니라 ..
Flow Control세그먼트의 흐름을 제어하는 것1:1 상황에서 자신의 윈도우가 넘치지 않을 정도로만 세그먼트를 보내도록 리시버가 남은 버퍼의 크기를 센더에게 알려주는 것을 '흐름 제어' 라고 한다.센더는 리시버로부터 여유 공간에 맞게 추가 데이터를 보냄으로써 리시버의 버퍼가 넘치지 않도록한다. 위 그림은 리시버의 프로토콜 스택을 보여준다.sender가 보낸 데이터는 IP 헤더 (녹색) 이 붙은 채로 3계층 (네트워크 계층) 을 지나고,3계층에서 TCP로 payload를 넘겨줄 것이다. 이 payload 데이터는 TCP 소켓의 receiver buffer에 담겨있다가, 어플리케이션이 데이터를 읽어가면 그때 버퍼에서 데이터를 삭제한다. 그런데 만약 어플리케이션이 다른 로직을 수행하느라 바빠서 데이터를..
TCP 개요TCP 는 RFC 793 에서 처음 제시된 프로토콜로, 아래와 같은 특징을 가진다. 1. point - to - point 프로토콜TCP는 하나의 sender 와 하나의 receiver 사이에 일어나는 통신에 대한 프로토콜이다.(참고로 1:1 이 아닌 통신으로는 브로드캐스트(1:N, 모두가 수신하도록 전송하는 방법)와 멀티캐스트(특정 그룹만 수신하도록 전송하는 방법)가 있다.) 2. 신뢰성 제공, 정해진 순서에 따른 byte stream 제공byte stream을 제공한다는 의미는 어플리케이션이 보낸 메세지 단위로 데이터를 전송하지 않는다는 의미이다.여러 메세지에 대해서 메세지 단위로 구분해서 데이터를 보내주지 않고, 정해진 byte 단위로 구분해서 전송하므로, 어플리케이션이 생성한 메세지의 ..
Pipelined Protocolrdt 3.0 프로토콜은 stop and wait 방식의 프로토콜이라 performance 가 매우 좋지 않았다.이를 해결하기 위해 pipeline 기법을 이용하여 한번에 여러개 패킷을 전송하는 아이디어가 제시되었다.이와 관련된 아이디어는 크게 Go-Back-N (GBN) 과 Selective Repeat (SR) 프로토콜이 있다.이 프로토콜들은 pipelined protocol 로 분류한다.먼저 Go-Back-N 프로토콜에 대해 정리하자. Go-Back-Nsender먼저 Go-Back-N 프로토콜을 사용하는 sender 입장을 살펴보자.sender는 다수의 pipelined packet을 보내야 하기 때문에 '윈도우' 를 사용한다.'윈도우'라는 이름은 슬라이딩 윈도우 기..
테스트 파일아래 테스트 케이스를 일일히 입력으로 넣고 빼는 게 불편해서 테스트 케이스 파일과 스크립트를 작성했다.https://github.com/kckc0608/Programming-Language-HW/tree/main/HW2 Programming-Language-HW/HW2 at main · kckc0608/Programming-Language-HW프로그래밍 언어론 과제 레포. Contribute to kckc0608/Programming-Language-HW development by creating an account on GitHub.github.com위 레포지토리에 테스트 케이스 파일들을 저장하였다.A. Function함수 정의, 함수 사용 (내장 함수 포함) 횟수 카운팅함수가 전방 선언되고..
hw3.l: In function ‘yylex’:hw3.l:14:9: error: ‘AUTO’ undeclared (first use in this function) 14 | "auto" {return(AUTO);} | ^~~~hw3.l:14:9: note: each undeclared identifier is reported only once for each function it appears in lex 에서 반환한 토큰 AUTO 가 yacc 파일에서 %token 으로 정의되지 않을 때 발생하는 에러이다. hw3.l: In function ‘yylex’:hw3.l:51:9: warning: returning ‘char *’ from a function with return..
rdt 3.0rdt 2.2 까지는 data corruption 이 발생했을 때, 이를 대처하는 방법을 기술한 프로토콜이었다.rdt 3.0 에서는 여기에 더해 underline 채널에서 데이터가 유실되어 목적지에 데이터가 전송되지 않았을 때 대처하는 방법을 추가적으로 기술한 프로토콜이다.(즉, loss 에 대한 대처 방법이다.) rdt 3.0에서는 데이터 loss가 발생했을 때도 데이터를 다시 전송하는 방법으로 해결하려고 한다.그래서 데이터를 전송한 뒤 기다리는 시간(타이머)을 정해놓고, 타이머의 시간이 다 지나도 ACK가 오지 않으면 재전송한다. 타이머의 시간은 transmission delay + propagation delay + queueing delay 를 모두 고려해서 최소한 1RTT..
허프만 코드와 데이터 압축 컴퓨터는 문자를 그대로 이해하지 못한다. 따라서 문자를 컴퓨터가 이해할 수 있도록 숫자로 바꾸어주어야 한다. 문자를 숫자로 변환하는 것을 '인코딩' 숫자에서 다시 문자로 변환하는 것을 '디코딩' 이라고 한다. 예를 들어 아래와 같은 규칙의 코드 표가 있다면 a,b,c,d 4개 문자로 구성된 아래 문자열을 그 아래처럼 인코딩할 수 있다. 13자리 문자열이 26자리 bit 리스트로 인코딩되었다. Prefix-Free code 문자열을 인코딩할 때 사용하는 코드 표는 다른 규칙의 코드표를 사용해도 된다. 이런 코드 표를 사용하더라도 문제없이 인코딩과 디코딩이 가능하다. 이때, 각각의 bit 가 선택됨에 따라 어떤 문자를 가리키게 되는지를 이진트리로 나타낼 수 있는데 위와 같이 나타난..
동적 계획법은 어떤 값을 구할 때 반복적으로 이미 구했던 값을 사용하는 경우, 이 값을 미리 기록해두었다가 활용하는 방법의 알고리즘이다.동적 계획법은 대체로 재귀 형태의 점화식을 가지는 문제를 해결하는데 유용하게 사용할 수 있다. 이항 계수이항계수는 nCk 조합의 경우의 수를 구하는데 사용된다. 이항 계수의 값은 위와 같이 계산한다.이때 이항 계수 nCk 를 각각의 값에 따라 쭉 표를 그리듯 그리면 아래와 같이 그려진다. 이 삼각형을 가리켜 '파스칼 삼각형' 이라고 한다.파스칼의 삼각형에 따르면 이항 계수는 아래와 같은 성질을 지닌다. 이항계수의 값이 다른 이항계수의 값을 이용해 재귀적으로 표현됨을 알 수 있다.이 공식을 그대로 함수로 옮기면def binom(n,k): i..
분할 정복은 말 그대로 주어진 문제를 분할하고, 분할한 조각을 정복(해결) 하는 방식으로 해결한다. 그리고 이 과정은 재귀적으로 발생한다. 지난 글에서 정리한 피보나치 수열도 그 값을 구할 때 '재귀'를 주요 아이디어로 활용하였듯, 분할 정복도 다른 관점에서 재귀를 활용하는 알고리즘이다. 이제부터 다양한 분할 정복 알고리즘과 그들의 시간복잡도를 구해본다. 카라츠바 곱셈 계산 (Karatsuba Method) 일반적인 곱셈 계산 곱셈은 덧셈의 반복이므로, 먼저 덧셈을 하는 과정을 생각해보자. 1234와 5678을 더한다면 일반적으로 아래와 같은 과정으로 진행된다. 두 피연산자는 정렬되어있어 i번째 자릿수는 같은 열에 위치한다. 각 자리수를 더해 만약 올림(carry)이 발생한다면, 다음 자리수에 넘겨 함께..
