CDN은 웹 콘텐츠 로드/배포 시 지연을 최소화하기 위해 사용하는 분산된 서버의 그룹이다. 프록시 서버에 웹 페이지, 이미지 등과 같은 콘텐츠를 복사해 캐싱해 놓고 사용자의 요청 시 해당 사용자에게 물리적으로 가까운 서버에서 콘텐츠를 제공하는 형태로 운영된다. 웹 상 다양한 미디어 콘텐츠가 공유되면서 CDN의 중요성이 대두되기 시작했다.

작동 메커니즘

CDN은 ATM과도 같은 개념으로 생각할 수 있다. 출금을 원할 때마다 사용자들이 은행을 방문하는 수고를 덜어주기 위해 은행은 도시 곳곳에 ATM을 설치한다. 이제 사용자들은 자신의 집에서 먼 은행 대신 바로 길 건너 모퉁이의 ATM기만 찾아가면 언제든지 이번에는 실제 사례로 CDN의 작동 방식을 이해해보자. 부산의 사용자가 영국에 서버를 둔 웹사이트를 방문했다고 가정하자. 해당 웹사이트에서 비디오와 같은 콘텐츠를 로드하기 위해서는 먼저 요청을 전송하고 응답을 받아야 하는데, 이러한 소통은 말 그대로 바다를 건너서 이루어지는 것이라 속도가 느릴 수밖에 없다. 만약 웹사이트 측에서 영국 서버의 콘텐츠들을 전세계 곳곳의 서버에 캐싱해놓았다면 사용자는 영국보다 훨씬 가까운 곳에서 콘텐츠를 받을 수 있고, 따라서 콘텐츠에 훨씬 빠르게 접근할 수 있다. 이렇게 서버들을 분산해서 위치시킨 곳들을 PoP(Points of Presence)라고 부른다.

CDN을 사용하지 않을 때는 서버와의 물리적 거리가 늘어날 수록 시간 지연이 증가하는 모습을 보인다.

CDN을 사용할 경우 사용자의 요청은 글로벌 서버 로드 밸런서라는 글로벌 레벨의 DNS 서비스가 CDN의 DNS 서버 중 하나로 전달된다. 글로벌 서버 로드 밸런서는 최고 성능을 낼 수 있는 CDN 프록시 서버, 즉, 엣지(Edge) 주소를 선택하여 요청을 전달한다.

이후 사용자는 해당 엣지에 HTTP 요청을 하고, 엣지 서버는 사용자가 원하는 콘텐츠가 자신이 이미 가지고 있는지 확인한다. 만약 캐싱된 콘텐츠가 있다면 사용자에게 바로 넘겨주고, 그렇지 않다면 먼저 같은 region 그룹의 엣지 서버에 해당 콘텐츠가 있는지 묻는 메세지를 전송한다. 이때도 콘텐츠를 전달 받지 못한다면 원본 서버(Origin Server)에 요청을 전송하여 사용자에게 콘텐츠를 전달해준다. 주의할 점은 CDN은 주로 정적 콘텐츠 전달에 특화되어 있다는 것이다. 정적 콘텐츠는 누가 언제 요청을 하든 내용이 변하지 않는 콘텐츠를 일컫는다. 이미지, CSS 파일, 자바스크립트 라이브러리, 비디오, 정적 HTML 페이지 등이 대표적인 예이다. 동적 콘텐츠의 경우 엣지 서버는

그런데 엣지 서버에 캐싱된 웹 콘텐츠가 콘텐츠의 가장 최신 버전과 일치함을 어떻게 보증할까? 이 문제를 해결하기 위하여 CDN은 TTL(Time-to-Live) 개념을 도입하였다. TTL값은 캐싱된 콘텐츠가 얼마나 오랫동안 서버에 머물 수 있는지를 결정한다. 다만 TTL값은 캐싱된 콘텐츠가 최신 버전과 같다고 항상 보장하지는 않는다. TTL값은 캐싱된 콘텐츠를 최신 버전이라고 상정할 기간을 임의로 지정한 값이기 때문이다. 또한, TTL값이 지나지 않아도 콘텐츠에 대한 요청 불충분 등의 이유로 콘텐츠가 캐시에서 탈락하는 경우도 있다.
해당 화면은 레딧 웹 어플리케이션 화면으로, 화면의 에러 메세지는 레딧의 CDN 서버가 모종의 이유로 원본 서버에 접근하지 못하여 콘텐츠를 로드하지 못한 상황을 보여준다.

탄생 배경

웹 페이지, 이미지 등 콘텐츠에 대한 웹 사용자들의 수요가 폭발적으로 증가하여 CDN의 필요성이 대두하였다. 이후 Netflix 등 주문형 비디오 서비스의 성장으로 CDN에 대한 관심이 더욱 증가하게 되었다. 현재 비디오 스트리밍 사이트, 전자 상거래 플랫폼 등 다양한 호스트들이 CDN을 이용하여 사용자들에게 자사의 콘텐츠를 전달하고 있다.

현재 AWS, GCP 등 클라우드 서비스들은 자신들이 이미 보유한 글로벌 네트워크 인프라를 활용하여 클라우드 CDN를 제공하고 있다. 유명한 서비스로는 AWS의 CloudFront, 구글의 Google Cloud CDN 등이 있다.

장단점

장점

• 웹사이트 페이지 로드 시간 개선
• 원본 서버에 대한 요청을 줄여 웹사이트 소유자의 호스팅 비용 절감
• 분산 서버 구조 덕분에 원본 서버보다 더 많은 웹 트래픽을 처리 및 하드웨어 오류 견디기 가능
• 글로벌 서버 로드 밸런서와 엣지 서버의 사용으로 네트워크 전체 용량에 걸쳐 균등하게 로드를 분산함으로써 DDos 공격 가능성 완화
• 엣지 서버 단위로 더욱 세밀한 액세스 관리 가능

단점

• 트래픽 볼륨 등 요소에 따라 과도한 비용 발생 가능
• 관리해야 될 서버가 많으므로 서비스 관리 복잡도 증가
• 캐싱 에러,
• CDN 관리를 서드 파티 서비스 주체에 위임하면 내 서비스에 대한 제어권 감소
• 원본 서버가 잘 작동해도 엣지 서버들이 다운되면 서비스 제공 장애 발생 가능
• TTL값이 잘 설정되지 않으면 최신 버전 이전의 콘텐츠 제공이 가능한 문제
  ### 함께 알면 좋은 키워드

proxy server, global server load balancer, edge server, caching
참고 사이트

https://www.cdnetworks.com/ko/what-is https://www.cloudflare.com/ko-kr/learning/cdn/how-cdns-reduce-bandwidth-cost/https://www.akamai.com/glossary/what-is https://www.reddit.com/r/explainlikeimfive/comments/2jdzdw https://www.reddit.com/r/webdev/comments/qk39tv/ https://stackoverflow.com/questions/42865428/do-akamai-edge-servers-share-cached-content-or-go-to- https://www.cloudflare.com/ko-kr/learning/cdn/glossary/time-to-live-ttl/ https://www.linkedin.com/advice/1/what-benefits-drawbacks-using-cdn-web-performance-skills-web-design#:~:text=Drawbacks of a CDN&text=A CDN can be expensive,overage fees%2C and minimum commitments.

CORS는 브라우저가 현재 도메인 밖의 다른 도메인에 속한 자원과 상호작용하기 위해 사용하는 HTTP 헤더 기반의 메커니즘이다. 출처가 다른 어플리케이션 간 상호작용은 CSRF 등의 보안 문제에 취약하기 때문에, 웹은 같은 출처에서만 자원을 공유케 하는 Same-Origin Policy를 수립하였다. 그러나 웹 어플리케이션에서 다른 출처의 자원(서드 파티 api, 라이브러리 등)을 가져와 로드하는 일이 매우 빈번하기 때문에 SOP에 예외 조항을 두었고, 이에 따라 CORS 정책에 부합한다면 현재 도메인 밖의 출처로 자원을 요청할 수 있게 되었다. CORS 정책 부합 여부는 서버가 아닌 브라우저가 판단한다.

같은 출처 구분 기준

출처(Origin)는 위 그림의 Protocol, Host 그리고 생략된 포트 번호를 합친 것으로, 서버의 위치를 찾아갈 때 필수적인 정보의 합을 일컫는다. 따라서 같은 출처라 함은 Protocol/Scheme, Host, Port Number 값이 동일한 출처를 말한다.

CORS 작동 메커니즘

Simple Request

GET, POST 메서드 사용 시에만 사용 가능한 방식이다. 또한, 해당 방식과 사용 가능한 헤더의 종류에도 제한이 있고, Content-Type을 사용하는 경우 multipart/form-data, text/plain 등만 한정적으로 허용한다. 따라서 사용 빈도가 높은 text/xml 또는 application/json 컨텐츠 타입에 대해서는 사용이 불가하다.

해당 방식 사용 시 예비 요청(Preflight request) 없이 바로 서버에게 본 요청을 보내고, 서버가 응답 헤더에 Access-Control-Allow-Origin 값을 보내주면 이를 바탕으로 브라우저가 CORS 정책 위반 여부를 검사한다. 위의 이미지에서 보면 Access-Control-Allow-Origin의 값이 *인데, 이는 어떠한 출처에서든 해당 자원을 액세스할 수 있음을 의미한다.

Preflight Request

일반적인 웹 어플리케이션에서 대부분 사용하는 방식이다. 자원 요청 시 브라우저가 서버에 예비 요청을 먼저 전송하고, 서버의 응답에 따라 같은 서버로 본 요청을 보낸다.

**OPTIONS /doc HTTP/1.1**
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:71.0) Gecko/20100101 Firefox/71.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Connection: keep-alive
**Origin: https://foo.example**
**Access-Control-Request-Method: POST
Access-Control-Request-Headers: X-PINGOTHER, Content-Type**

예비 요청은 OPTIONS라는 HTTP/1.1 메서드를 사용하여 이루어진다. Origin 헤더에는 자신의 도메인을, Access-Control-Request-Headers에는 본 요청에서 사용할 헤더 정보들을 넣어 예비 요청을 전송한다.

HTTP/1.1 204 No Content
Date: Mon, 01 Dec 2008 01:15:39 GMT
Server: Apache/2
**Access-Control-Allow-Origin: https://foo.example
Access-Control-Allow-Methods: POST, GET, OPTIONS
Access-Control-Allow-Headers: X-PINGOTHER, Content-Type**
Access-Control-Max-Age: 86400
Vary: Accept-Encoding, Origin
Keep-Alive: timeout=2, max=100
Connection: Keep-Alive

예비 요청을 받은 서버는 자원 액세스 가능 여부를 판단하여 브라우저에 응답을 전송한다. 응답 헤더들을 살펴보면 어떠한 출처에서 자원을 액세스 할 수 있는지 뿐만 아니라 어떠한 HTTP 메서드로 자원에 접근 가능한지, 예비 요청에서 브라우저가 보낸 Access-Control-Request-Headers의 헤더들을 본 요청에서 사용 가능한지 여부 등을 명시하고 있다. 한편, 예비 요청은 서버의 응답에 명시된 시간만큼 캐싱될 수 있다.

POST /doc HTTP/1.1
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:71.0) Gecko/20100101 Firefox/71.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Connection: keep-alive
X-PINGOTHER: pingpong
Content-Type: text/xml; charset=UTF-8
Referer: https://foo.example/examples/preflightInvocation.html
Content-Length: 55
Origin: https://foo.example
Pragma: no-cache
Cache-Control: no-cache

예비 요청에서 자원 액세스가 가능하다는 응답을 받았기 때문에 브라우저는 서버로 본 요청을 전송한다. 본 요청의 내용은 Simple Request와 동일하다.

CORS 정책 위반 방지법

CORS 정책 위반 시에도 보안 상의 이유로 에러의 상세 내용은 확인할 수 없으므로 처음부터 에러가 발생하지 않도록 방지하는 것이 중요하다. CORS 정책 위반 여부는 브라우저에서 검사하지만 방지 조치는 주로 서버단에서 수행한다.

커스텀 필터를 생성하거나 WebMvcConfigurer를 이용해서 처리할 수도 있지만 내가 사용한 방법은 컨트롤러에서 @CrossOrigin 어노테이션을 추가해주는 것이었다. 서드 파티 api를 사용한 부분에서 계속 CORS 에러가 났는데 해당 api를 호출하는 컨트롤러 메서드에 해당 어노테이션을 추가해주니 에러가 해결되었다. @CrossOrigin은 컨트롤러 레벨이나 메서드 레벨 중 선택해서 추가하거나 둘 다 해주어도 된다.

@Controller
@CrossOrigin(origins = "https://foo.example") // 컨트롤러에서 설정
public class AdminController{

    @GetMapping
    @CrossOrigin(origins = "https://foo.example") // 메서드에서 설정
    public String memberList(){
        }
}

* 해당 글은 다음의 글들을 참고하여 작성하였습니다: https://developer.mozilla.org/en-US/docs/Web/HTTP/CORS https://evan-moon.github.io/2020/05/21/about-cors/ https://aws.amazon.com/ko/what-is/cross-origin-resource-sharing/ https://wonit.tistory.com/572

원래 자바스크립트 라이브러리나 파일을 다른 파일에서 사용 시 직접 다운받아서 스크립트 태그 형식으로 직접 포함시켜야 했다. 하지만 이 방식은 라이브러리 버전 관리도 힘들고, 다른 사용자와의 파일 공유시 다른 사용자들도 각자 사용된 라이브러리 및 스크립트를 다운로드해야한다는 단점이 있었다. 이를 개선하고자 등장한 것이 패키지 매니저 프로그램들이다.

npm은 package.json 파일을 생성해 해당 프로젝트 관련 정보를 관리한다. npm install을 통해 원하는 패키지를 설치하면 해당 패키지가 package.json 파일의 프로젝트 dependency 목록에 추가된다. 따라서 프로젝트를 공유할 때 패키지가 설치된 폴더 대신 package.json 파일만 공유하면 다른 사용자들이 자동으로 필요한 패키지를 설치할 수 있다는 장점이 있다.

번들링(Bundling)

하지만 npm으로 다운받은 파일은 스크립트 태그 형식으로 직접 추가해 주어야하는 불편사항을 여전히 있었다. 자바스크립트는 브라우저에서만 실행하기위해 만들어진 언어였으므로 애초에 클라이언트의 파일 시스템에 액세스할 수 없기 때문이다. 이러한 불편사항을 극복하기 위하여 번들러 프로그램들이 출시되었다. Webpack을 비롯한 번들러 프로그램들은 dependency들이 import되는 지점을 찾아 이를 import되는 파일에서 실제 필요한 내용으로 변환하고, 최종적으로 프로젝트를 하나의 자바스크립트 파일로 묶어준다. 번들러는 사용자가 지정한 entry point를 시작으로 프로젝트의 모든 파일을 살펴서 entry point 당 하나의 결과 파일, 즉, 하나의 컴파일된 output을 생성한다.

ES6 모듈(Modules)

번들러 프로그램은 ES6 모듈을 사용하는 프로젝트의 경우 특히 중요하다. 프로젝트가 여러 모듈 파일로 구성되어 있을 경우 브라우저가 각 파일에 대해 별도의 HTTP request를 날려야 할 수도 있기 때문에 프로젝트 크기나 복잡도에 따라 속도나 비용 면에서 큰 손실이 발생할 수도 있기 때문이다.

한편, 모듈은 코드 재사용성의 증가라는 큰 장점을 가지고 있다. import 선언을 통해 자바스크립트 파일을 현재 페이지에서 바로 사용할 수 있고, 반대로 export 선언을 통해 다른 페이지에서 사용하고 싶은 값, 함수, 클래스, 생성자 등을 내보낼 수 있는 덕분이다.

export

export는 named export와 default export 두 종류가 있다. 모듈 당 named export는 여러 개, default export는 단 한 개만 허용된다. export 선언의 이름은 겹쳐서는 안되며, 중복시 syntaxError가 발생한다.

1. named export

    export { myFunction2, myVariable2 };
    export let myVariable = Math.sqrt(2);
    export function myFunction() {}

   • 여러 개의 값을 export 할 때 유용
   • import한 파일은 넘어온 값들을 export된 명으로 칭해야 함

2. default export

    export default 1 + 1;
    export default function foo() {
      console.log("Hi");
    }
    export default function () {
      console.log("Hi");
    }

   • export 키워드 뒤에 어떠한 표현(expression)도 허용
   • 함수와 클래스를 익명으로 export 가능
   • import시 어떠한 이름으로도 칭할 수 있음

import

import { foo, bar } from "/modules/my-module.js";
import * as myModule from "/modules/my-module.js";

• export한 모듈의 변화에 따라 import한 값이 업데이트되지만, 반대로 현재 파일에서의 변화가 export한 모듈에 적용되지 않는 live binding 방식
• import 선언은 모듈의 최상위 레벨에서 이루어져야함
• expression대신 스트링 리터럴 식별자만 사용 가능
• 위와 같이 엄격한 구문 문법 적용덕분에 모듈의 dependency들을 runtime 이전에 정적으로 분석 가능
  ### Single Page Application 개발에서의 활용 Vue.js는 컴포넌트 사용에 있어 ES6 모듈 방식을 적극 활용한다. Vue.js의 공식 문서에도 언급되어 있듯이 Vue.js는 컴포넌트 기반 구조와 클라이언트 단의 라우터 등의 다양한 툴을 제공하여 Single Page Application 개발에 적합한 프레임워크이다. 번들러 프로그램은 Vue.js의 컴포넌트 등의 자원들을 묶어서 브라우저에서 보다 효율적으로 동작하도록 도울 수 있다.
  
  
• 해당 글은 다음의 글들을 참고하여 작성하였다:
• https://peterxjang.com/blog/modern-javascript-explained-for-dinosaurs.html
• https://www.theodinproject.com/lessons/node-path-javascript-es6-modules
• https://ljs0705.medium.com/spa-single-page-app-에서-webpack을-사용하는-이유-ce7d3f82fe9
• https://vuejs.org/guide/extras/ways-of-using-vue.html#single-page-application-spa
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/import
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/export

EC2 서버로 배포한 서비스가 갑자기 연결이 안된다. 배포 주소로 들어가면 연결을 거부했다는 메세지만 계속 출력되는 것이다. 며칠 전만 해도 잘 작동하는 걸 직접 확인했는데 너무 당황스러웠다. 일단 인스턴스에 문제가 생겼는지 확인하기 위해서 다음의 사항들을 확인해보았다:

1. 인스턴스 상태가 running인지 확인
2. 보안 그룹 인바운드/아웃바운드 규칙 확인
3. IP 주소 변경 여부 확인
4. 인스턴스 시스템 로그 확인

오류의 이유

확인 결과 인스턴스는 문제 없이 구동 중이었다. 오류의 이유도 모른 채 ‘EC2 연결 오류’로 구글링만 하염 없이 해도 대부분은 인스턴스 문제에 관한 팁이어서 별 도움이 되지 않았다. 그러다 번뜩 떠오른 것이 AWS 웹사이트에서 확인 가능한 인스턴스 콘솔 스크린샷이었다. 인스턴스 콘솔 스크린샷을 보니 그제야 오류의 원인을 파악할 수 있었다:

메모리가 부족해서 서비스를 강제로 종료한 것이었다. AWS 공식 홈페이지에 따르면 out of memory 발생 시 Linux Out Of Memory(OOM) 매니저가 호출되고, 이 매니저가 프로세스들을 강제 종료시킨다고 한다.$\tt{^{1}}$ 나는 다행히 해당 인스턴스에서 swiftER 서비스만 구동 중이었기에 서비스가 강제 종료되는 선에서 끝났지만 여러 서비스를 배포/구동 중이었다면 연쇄적으로 피해가 발생할 수도 있는 상황이었다. EC2 인스턴스는 기본적으로 스왑 공간을 할당받지 않아서 직접 스왑 파일을 생성해야 한다. 공식 홈페이지에서 설명하는 스왑 파일 생성 방법은 다음과 같다:

스왑 파일 생성 방법

1.   dd 명령을 사용하여 루트 파일 시스템에 스왑 파일을 생성합니다.

$ sudo dd if=/dev/zero of=/swapfile bs=128M count=32

2.    스왑 파일의 읽기 및 쓰기 권한을 업데이트합니다.

$ sudo chmod 600 /swapfile

3.    Linux 스왑 영역을 설정합니다.

$ sudo mkswap /swapfile

4.    스왑 공간에 스왑 파일을 추가하여 스왑 파일을 즉시 사용할 수 있도록 합니다.

$ sudo swapon /swapfile

5.    프로시저가 성공적인지 확인합니다.

$ sudo swapon -s

6.    /etc/fstab 파일을 편집하여 부팅 시 스왑 파일을 시작합니다. 먼저, 편집기에서 파일을 엽니다.

$ sudo vi /etc/fstab

파일 끝에 다음 줄을 새로 추가하고 파일을 저장한 다음 종료합니다.

해결

위의 방식대로 하니 서비스가 다시 정상적으로 구동하기 시작했다.

1) https://repost.aws/knowledge-center/ec2-linux-prevent-over-utilization

Threads

Each thread can represent one chunk of code and is a unit of concurrency provided by the OS. In other words, the OS can handle multiple things at once with threads.

A thread is in one of the three states: running, ready and blocked. If a thread is waiting for an I/O to finish, the OS marks it as blocked. Once the I/O operation finishes, the OS marks it as ready. Once a process starts, it issues system calls to create new threads. The calls are usually made by OS library or language runtime so system calls are hidden below programming interface. For example, $\tt{pthread_create()}$ in C library issues a system call with some special assembly code and then the kernel creates a new thread and return the values and the program runs in user mode again.

Main thread creates, or, forks subthreads and after its subthreads are done, it joins with them, collecting their results. While content of memory and I/O state are shared by all threads in one process, information in TCB, CPU registers(including program counter) and execution stack are kept private to each thread. Execution stack stores parameters and temporary variables. A thread’s stack can touch that of another thread but since the focus of protection is on process itself, not individual threads, procedures to prevent this aren’t essential.

Scheduler can run threads in any order and can switch threads at any time. This can be problematic in race conditions where threads might depend on the result of other threads. To prevent race conditions, synchronization is needed. A lock is an object only one thread can hold at a time, ensuring only one thread does a particular thing at a time. Before a thread executes, it will claim to acquire a lock and after execution it will release the lock so one of the other threads can acquire it.

Processes

Processes are always created by other processes and the first process is initiated by the kernel. The OS library calls main thread (i.e. public static void main(String[] args) in java) and when main returns, the library calls exit on the process.

Thread

A thread is a single unique execution context that has a program counter, registers, execution flags, stack and memory state. Out of many threads, only one at a time gets executed on a processor when it is resident in the processor registers. Being resident means that the registers hold the root state of that thread including PC register pointing at the next instruction of the instructions in memory, intermediate values/pointers for ongoing computations and stack pointer holding the address of the top of stack. On the contrary, a thread is suspended, or, not executing when its state is not loaded into the processor registers. The last values from the execution are stored in memory during this period.

With a single processor, you can multiplex the hardware in time to achieve the illusion of multiple processors, running a part of each thread for a certain amount of time, alternating between threads. These threads are virtual cores. Switching from one thread to another is called context switching. During context switching, OS saves the current thread’s PC, SP, etc. information in its thread control block in memory and load that of the other thread.

While the illusion of multiple processors is achievable, the aforementioned way is not safe in that the threads share the same memory and thus can overwrite each other, even OS. A simple protection approach is base and bound where the start and end of the execution boundary of a thread are written in base register and bound register respectively. Whenever a program executes, hardware will check if the address program counter inputs is within that range. When a thread is loaded into memory, it is relocated according to the base register and the program counter will store addresses within the range. Instead, if you add an adder by which the program counter will store addresses as is and the adder will add the value of the base register when they are loaded to memory.

One significant problem this method has is when the currently running program needs more memory space, the current memory space’s contents have to be copied into somewhere bigger. After use, it can cause fragmentation errors. An alternative is translation where instructions operate on virtual addresses and the hardware translates them into physical addresses with a page table.

Address Space

An address space is a set of memory addresses accessible to program for read/write. It includes program counter, static data, stack, heap and so on.

Process

A process is an execution environment with restricted rights. In other words, it is a protected (by base and bound or translation mentioned in the thread section) address space with one or more threads. Application programs usually execute as a process. While it is easy for threads within the same process to communicate as they share memory, it is harder for processes to communicate with one another for protection. Bugs can only overwrite memory of process they are in and malicious process cannot read/write other process’ data.

Dual Mode Operation

Hardware provides at least two modes: kernel mode and user mode. Some operations are prohibited in user mode. Processes execute in user mode while kernel executes in kernel mode. A program can issue a system call to transition into kernel mode.

Binary Search Tree (Set Binary Tree)

Finding a certain item can be done with binary search if the nodes are ordered so that the keys the nodes represent are in an increasing order

• subtree_find(node, k):

  if node is not to be found, return. If k < node.item.key, recurse on node.left. If equal, return the node as this is the node we intended to look for. If k > node.item.key, recurse on node.right. As you can see, it is the same as binary search

Sequence Binary Tree

Its traversal order is the sequence order. The challenge is to find the ith node in the subtree. Knowing the size of the subtree is crucial and the size of a node means the number of nodes in the subtree, including the node itself

• subtree_at(node, i):

  Set an arbitrary variable NL to the size of node.left(the subtree on the left in the picture above). Suppose we know the value of the size somehow. So the index* of the root node is NL. If i < NL then recurse on node.left. If i = NL, return the current node. Lastly, if i > NL then do subtree_at(node.right, i-NL-1) recursively. We readjust the NL’s value to i-NL-1 because we don’t need node.left(NL) and the root node(1) so we subtract them. This operations takes O(height)

  * when dealing with set binary trees, keys were used; here, indices are used with sequence objects

Subtree Augmentation

Each node can store O(1) extra fields/properties. Subtree property can be computed from properties of its left or right children in O(1) time. Size of a sequence binary tree is a property as node.size = node.left.size + node.right.size + 1(itself). If every node has its size as its property, we can get a size of a particular node in constant time. Common properties include sum, min, max of some feature of every node in subtree.

However, you cannot store the index or depth of each node as once a new node is added, every node’s index changes and a node’s index doesn’t necessarily depend on the subtree it belongs to. For example, the index of the first node in node.right right below the root is solely reliant on the number of nodes in node.left and root.

When a new leaf is added or removed, the newly created subtree(which is the new leaf itself) and the subtrees that contain its ancestors should be updated. The number of subtrees to be updated is the same as the height of the tree. To update the subtrees, you need to update each ancestor’s size value bottom up. To update one subtree takes a constant time because its children have correct information either because they were unaffected by the change or they already have been updated before we’ve moved on to the subtree at focus. Thus, the whole operation as a whole takes O(height).

AVL Tree

When the height equals log n, the tree is considered balanced. To rebalance an unbalanced tree, you need the rotation trick. Rebalancing means reorganize the tree without modifying its original traversing order.

An AVL tree is a tree that maintains height balance, so that height(node.right) - height(node.left), or skew(node) is always either -1, 0 or 1. Suppose we have a tree whose node.left is shorter than node.right by 1 in terms of height. The number of nodes in an AVL tree of height H($N_h$) is $N_{h-1}$ + $N_{h-2}$ + 1(root).

💡 $N_h$ > $N_{h-2}$ + $N_{h-2}$ = 2 x $N_{h-2}$ This(2 x $N_{h-2}$) is powers of two thus this is exponential. This implies the height, h, is equal to or smaller than 2 log n.

Height is a subtree property in that node.height = max{node.left.height, node.right.height} + 1. When adding or deleting a node to an AVL tree, the height of a subtree might change, which in turn might make the skew value go out of range of -1, 0 and 1 (the new value is either -2 or 2). To rebalance the tree, you have to rotate it. When skew(y) is either 0 or 1(like in the picture below), you only need to rotate the tree so that y is now the root.

On the contrary, if skew(y) is -1, the rotation gets complicated but still doable.

위의 물음은 사용자가 마이 페이지에서 자신의 회원 정보를 조회하는 기능을 만들다가 문득 떠올랐다. 대부분의 웹서비스에서 사용자가 자신의 아이디를 변경할 수 없는 것이 관례이지만 우리 서비스에서도 역시 아이디 변경 불가 원칙을 고수할 것인지 먼저 고민해보고 싶었다. 사용자는 자신의 아이디를 변경하지 못하더라도 관리자도 사용자들의 아이디를 변경하지 못하게 해야 할까? 스택 오버플로우같은 사이트들을 찾아보기도 하고 팀원들과 머리를 맞대고 고민한 결과, 관리자와 사용자 모두 아이디를 변경하지 못하는 방향으로 결론을 내렸다. 변경 불허의 근거는 다음과 같다:
네이버, 페이스북 등의 서비스는 데이터 무결성을 이유로 대부분의 경우 아이디 변경을 불허한다. 데이터 관련 이슈의 경우, 아이디를 다른 테이블에서 외래키로 참조하고 있다면 아이디가 변경되었을 때 해당 테이블에서도 값을 변경해주어야한다. heidiSQL 기준 외래키 설정에서 on update 항목의 값을 cascade로 설정하면 아이디 변경 시 해당 아이디를 참조하는 테이블의 아이디 값도 자동으로 바뀌기는 하지만 아이디를 참조하는 테이블이 많고, 아이디 변경이 많이 일어난다면 유지보수가 힘들 것이다. 같은 논리로, 만약 사용자의 아이디 변경을 허가하더라도 다른 유저의 변경 전 아이디를 사용하지 못하게 해야 할 것이다.

아이디 변경을 보통 불허하는 또 다른 이유로는 아이디 값이 hard code되는 부분이 있다는 것이다. 예를 들어 사용자가 자신의 개인 페이지에 다른 사람들이 방문할 수 있도록 링크를 공유하는데, 그 링크에 아이디값이 파라미터로 들어있다면 이미 공유된 링크에 대해서는 아이디가 변경되어도 아이디 파라미터값을 바꿀 수 없다.

보안 문제도 생각해보아야 한다. 조원의 개인적인 경험에 따르면, 조원의 스팀 계정이 해킹당하였는데 해커가 이메일 등 모든 정보를 바꾸었지만 스팀 정책 상 아이디는 바꿀 수 없었고, 그 덕분에 기존 아이디로 계정을 복구할 수 있었다고 한다. 만약 해커가 아이디까지 바꾸었다면 기존 계정에 접근할 방법이 없었을 것이다.
새로 아이디를 만드는 대신 이메일을 로그인 식별 정보로 사용하는 방법도 고민해보았다. 어차피 회원가입할 때 이메일을 입력하고 인증까지 거쳐야 하기때문에 이메일을 사용하는 일 자체는 문제가 되지 않을 것이라 생각한다. 그러나 가입 당시 등록한 이메일을 나중에 사용자가 삭제할 경우 등 나름의 문제가 있기 때문에 이메일을 사용하는 방법은 보류하였다. 로그인 식별 정보로서의 아이디, 그리고 아이디 변경 가능 여부는 추후 우리 서비스를 사용하는 사용자들이 생긴다면 다시 깊게 고민해보아야 할 것이다.

Binary Tree

A node in a binary tree typically has an item and three pointers: parent pointer, left pointer(child) and right pointer(child). A root is a node that does not have a parent pointer. Unlike singly or doubly linked list, you can get to a node within less than a linear time, and possibly within a logarithmic time. In a singly linked list, the item at the end has a high depth value, meaning you have to follow many pointers to get there. In a doubly linked list, you can get to the end easily but again, it takes a linear time to get to the middle of the list.

Traversal Order of a Binary Tree

A binary tree decomposes into subtrees; a subtree of x consisting of x (root of the subtree) and its descendants. It also has leaves, nodes with no children. The depth of a node is the number of its ancestors or the number of edges (an edge is a line that connects two nodes) in path from x up to the root. The height of a node is the number of edges in the longest downward path from x or the maximum depth in x’s subtree. All leaves have height of 0 and the height of the root is the same as the height of the tree.

When traversing a tree, you should determine the traversal order of nodes. Suppose for every node x, nodes in x.left come before x while nodes in x.right come after x. With this particular traversal order, we can define some traversal operations:

• subtree_first(node)

  This operation decides which node in the subtree should come first during traversal. Here, it should go to the bottom left first(node = node.left) and return the node.

• successor(node)

  This operation finds the next after node in traversal. If node.right exists, meaning if the node has a right child, it should return subtree_first(node.right). Else, walk up the tree (node=node.parent) until you go up to a left branch(node = node.parent.left) and return the node. You hitting the left branch is when the traversal direction becomes reverse.

The operations above will be O(height)

• subtree_insert_after(node.new)

  This operation inserts a new node so that it comes after a particular node during traversal. If there’s no node.right, put the new node there. Else, put the new node as successor(node).left. Since the successor(node) operation goes down left as much as possible, the successor(node) is guaranteed to have no left child. This operation is O(height).

• subtree_delete(node)

  This operation deletes a node. If the node is a leaf, you just detach it from its parent. If the node is not a leaf, there are two cases: node.left(the target node has a left child) and node.right. In case of node.left, swap the node’s item with predecessor(node)’s item and subtree_delete(predecessor). In case of node.right, you do the same but with successor(node). This operation is O(height).

For a sequence, make the traversal order equal to the sequence order. For a set, make the traversal order equal to ordered by increasing item key. In a Binary Search Tree, you store integer key values in order. In the example order defined above, all the keys smaller than the root will be the root’s left children and those bigger will be its right children. Thus, find(k), find_previous and find_next operations are made easy.

Direct Access Array Sort

Suppose u is small and all the keys are unique. Make a direct access array(O(u)), store each key in their respective indices(n * O(1)) and walk down the array and return the keys seen in order(O(u)). The whole process will take O(n+u), which is a linear time algorithm

What if u gets bigger, say, u is smaller than n squared. Decompose each item into two smaller numbers. For example, with k, you can get two smaller numbers a and b, a being k/n and b being k mod n. You can retrieve the k value later because you know k=an+b. For example, when you have a set of keys that go: [17, 3, 24, 22, 12], after the decomposition, you get a tuple of [(3,2), (0,3), (4,4), (4,2), (2,2)], or, [32, 03, 44, 42, 22]

Tuple Sort

When there are many factors you can base the sorting on, you first have to rearrange the factors in order of importance. In the example above, you would say a is more important than b in that a change in the value of a leads to a greater change the value of k.

Most significant first

First sort the tuple by a:

[03 22 32 44 42]

Then, sort it again by b:

[22 32 42 03 44] X

Least significant first

First sort the tuple by b:

[32 42 22 03 44]

Then, sort it again by a:

[03 22 32 42 44] O

As you can see, the tuple should be sorted by the least significant first. Also note that you should use stable sorting algorithm, meaning the outcome of the first sorting should remain intact unless effected by the sortings to follow. That is why the final outcome on the right is 03 22 32 42 44, not 03 22 32 44 42. You cannot use direct access array sort with the outcome because of possible duplicates(42 and 44 in this case)

Counting Sort

At each key K in the direct access array, we store a pointer to a chain. The chain should remain the same order in which the elements were put. Thus, the chain should be a sequence data structure

To guarantee all the elements in every chain are sorted, you can combine tuple sort and counting sort, using counting sort as an auxiliary stable sorting algorithm. This also takes O(n+u) when k is equal to or less than n squared because u is n in this specific example and the maximum amount of a is n(when k=n squared). When k is increase to n cubed, you simply divide k into three digits(when you divide k with n, you will be left with n squared and this can again be divided into the combination of a and b)

Radix Sort

Break up integers(max size u) into a base-n tuple. The number of digits is log n of u. It is the same as tuple sort on digits using counting sort from least to most significant. It takes O(n + n log n U) as long as u is smaller than n to the power of c, c being any constant, making it a linear time algorithm

Comparison Model

A comparison model or comparison tree consists of internal nodes, each of which represents comparison operation, and leaves, each of which represents the final result of the operations, or, an item selected from the n items stored in a data structure. This is essentially a binary tree in that after an operation, based on whether the result is true or false, it decides whether to branch to this next node or the other one. Thus, each model should have n + 1 leaves because the model should be able to present any item off the n items and a situation where the value user is looking for doesn’t exist in the n items. The height of the tree means the number of operations that need to be done to get to the final result. The minimal height of a comparison tree is θ(log n)

Is there any way to make the height shorter than θ(log n)?

Direct Access Array/Hash Table in RAM

Suppose you have an array and an item with a key whose value is 10. You just store the item at the 10th index of the array. The find and insertion time will be constant but the length of an array can get exponentially big if the values of the keys are huge. Adding to that, if items are stored non-continuously, finding the next element will take extra time.

Hashing

Instead of having an array with the height as same as the size of the largest key, you cram the u amount of keys into an array whose length is m or θ(log n), n being a smaller number than u. Storing more than two items at a same index is inevitable, thus, the question regarding efficiency in searching is how to evenly distribute keys over the array. A hash function is a function which compresses the universe of keys from 0 to u-1 to that of 0 to m-1.

One way to handle a collision where more than two keys need to be put in the same place is open addressing, which simply put, is to store the other key in a place yet to be occupied. This is possible when m is larger than n. Another way is to have a pointer to some other data structure where you can store different keys that could have been stored at the same index. To find a key on the array, first you have to go to that index and loop up the data structure the index is pointing at. This method is called chaining and each data structure that stores keys, or, chains should be kept to a small size so that searching for a key won’t take too much time. If we add more keys to the array, meaning we grow n and a once fixed m in return, m will stop being linear in n. Then, all you need to do is to rebuild the entire hash table with a new m.

Division hash function, h(k) = k mod m, mingled with some other extra steps, is used by Python and other languages for hashing. To guarantee all the keys get stored in one place given that the size of the universe of keys is huge, you can also choose which hash function to use after the user picks input. Universal Hash functions are non-deterministic or not fixed hash functions that can provide a family of hash functions to choose from. This notion adds randomness to the whole process.

Sets

A set interface is a container that stores a sequence of iterable entities. A stored item can be retrieved with its key as every item is associated with a unique key

It can be implemented into an unordered array but it will be very inefficient as you’ll have to iterate the whole array to find an item till you run across the item. With an sorted array, the keys of each item being sorted in this case, finding items with keys is faster but it generally takes more time to sort the keys than to build an unordered array

Sorting

In goes an array of n numbers/keys and out comes a sorted array in sorting

Permutation Sort

Enumerate all the permutations of the input array(Ω(n!)) and check which permutation is in order(O(n)). Thus, this algorithm takes at least Ω(n! x n) time

Selection Sort

At each step, find the biggest item in the array and swap it out with the last item in the array. Repeat till the array is ordered. The amount of time this algorithm takes is T(n) and it is the same as T(n-1) + θ(n) as each step takes O(n) and the algorithm is recursive in that you get to sort one less element than the prior step. So sorting will take O(n²) time

Merge Sort

First, you see every element as an array of size 1, which is naturally sorted. Then, merge the array with the one right next to it and sort the elements in order. Repeat till you have one big list whose elements are in order. The merging process per each step takes θ(n) as you have to go through every element to sort them in order. The whole algorithm takes

Interface, or API, is the specification of what you want to do, or in other words, what data you can store and data structure is the representation of how you do it. Algorithms are needed to support data structure operations. In short, interface is a problem set and algorithms are the solution to the problem

Interfaces

A static sequence interface has a fixed number of items it can store. The solution to the static sequence interface is a static array/list. Memory is an array of w-bit words and array is a consecutive chunk of memory. Thus, to access the array[i] is to access (the address of the array in memory + i), making the array access is constant time of O(1)

A dynamic sequence interface’s main focus is to insert at or delete from the middle of an array. On top of that, ways to insert/delete at before the beginning and/or after the end should be devised

Data Structures

The two main data structure approaches/tools are arrays and pointers

Linked List

Inserting/deleting is easy as you only need to add/remove a node and change where the pointer of the node right before it points to, hence O(1) time. However, get_at/set_at(ith element) or inserting/deleting the ith element can be anywhere from θ(i) to θ(n) as you have to follow the pointers till you find the element. If you make your linked list store a tail, or a pointer to the last node, deleting the last element will also take a linear time. Whenever a change is made to the linked list, the tail should also be updated

Static Array

Inserting/deleting can’t be achieved by shifting all the elements that will come after the newly inserted/deleted element as the size of a static array is fixed. This is because when a static array is created, it is allocated a certain size of array in memory and by adding an element and thus increasing the size of the array, it can touch other neighboring arrays in memory that it shouldn’t have met. Thus, the only way to achieve this is to create a new array of size n + 1 and copy the elements from the original array into the new array and this will take a linear time

Dynamic Array (Python lists)

It has the size of roughly n, meaning it is θ(n) and is bigger or equal to n, which means it can be n, 2n, 10n, etc. As its size is not strictly n, there will be items to store a sequence and also, some blank ones in the end. The array will keep track of the length to tell where the blank ones start and the size of the array, occupied and blank ones put together. Thus, insert_last(x) takes a linear time and is possible unless n (interface size) = size (representation size). When n = size, you have to allocate a new bigger array and copy the elements into it just like with static arrays but much less often

Algorithms

An algorithm is a fixed size solution or a function to general problems with arbitrarily sized inputs. The goal of learning algorithms is to solve computational problems in a correct and effective way. The efficiency units that signify the performance of an algorithm are O(upper bound), Ω(lower bound) and θ(when upper and lower bounds are the same)

Overview

3-1 Transport Layer

• definitions
  • transport layer: logical communication b/ processes
  • network layer: logical communication b/ hosts(can have many diff processes)
• process
  1. application layer passes a message through socket
  2. transport layer determines segment header fields values and creates segment
  3. transport layer passes down the segment to the network layer, to the IP protocol
  4. network layer sends the segment to the receiving host
  5. receiving host checks the header values, extracts application layer message and demultiplexes messages up to application via socket
• two principal internet transport protocols
  • TCP
  • UDP(connectionless)

Transport Layer Multiplexing and Demultiplexing

3-2 Transport Layer Multiplexing and Demultiplexing

• demultiplexing
  • process by which the payloads of a datagram(received from the sender host) are directed to the designated applications
  • host uses IP addresses and port numbers specified in the transport layer segment of the datagram it received to direct segment to appropriate socket
  • all the UDP datagrams with same destination port # will be directed to the same socket
  • TCP socket is identified by both source and destination IP address and port number whereas UDP socket only requires those of destination. This means each TCP socket will be associated with a different connecting client as they all have different source IP addresses
• multiplexing
  • many applications sending down messages through respective sockets to TCP and it is TCP’s job to funnel down the messages to the IP protocol

Connectionless Transport - UDP

3-3 Connectionless Transport UDP

• features
  • User Datagram Protocol, or UDP for short, provides “best effort” service, thus segments can be lost or delivered out of order
  • UDP is connectionless, meaning sender and receiver does not share handshakes or states. Since there is no connection, there is no connection establishment
  • As UDP provides relatively simple service, the header size is also relatively small
  • UDP provides no congestion control so it can function on a congested network, unlike TCP
  • All of the characteristics above make UDP suitable for applications such as streaming services, DNS, SNMP and so on
• UDP segment header
  • Header includes source port #, destination port #, length of the payload(application data) and checksum field
  • Pseudo header containing source and destination addresses is prefixed to the UDP header
• checksum
  • Its goal is to detect errors in transmitted segment
  • Sender turns the contents of UDP segment(including header fields and IP addresses) into a sequence of 16-bit integers. Add all the integers and the complement sum of the addition is the checksum value
  • Receiver compute the checksum of the received segment to see if it matches the checksum field
  • Checksum is not foolproof however, as the two values turning out to be equal does not necessarily mean the received segment has not been corrupted
  • HTTP3 sets security measures in application layer on top of UDP to supplement UDP’s weak protection

Principles of Reliable Data Transfer

3-4 Principles of Reliable Data Transfer Part1

• abstraction and implementation
  • While the process of sending data from one point to another is abstracted away as a uni-directional, reliable service, it really is a bi-directional message changing(NOT data transfer) process through reliable data transfer protocol, then over an unreliable channel in the network layer
  • Complexity of reliable data transfer protocol will rely on the characteristics of unreliable channel
  • Sender and receiver do not know the state of each other or what’s happening at the channel unless they are communicating via messages
• Reliable Data Transfer Protocol
  • Finite State Machines are used to specify the state of sender and receiver
  • If the underlying channel is perfectly reliable, the FSMs on each end only need to send/read data from the channel. For example, on the sending side, rdt will send data to the transport layer. The transport layer’s actions then, are to turn data into a series of packets and send them through the underlying channel
  • If the underlying channel has impairments, rdt2.0 is used to recover from errors. Rdt 2.0 uses acknowledgements(ACKs) or negative acknowledgements(NAKs) whereby receiver explicitly tells sender that a packet is received okay or not. Sender retransmits the packet on receipt of NAK. Acknowledgement happens after every one packet
• Rdt 2.0
  • Sender goes from one state to another: waiting for call from above for another rdt send, to waiting for ACK/NAK. If it gets an ACK, it falls back to the initial state whereas a NAK response will call for a retransmit of the packet till it gets an ACK back
  • Receiver will be waiting for the arrival of the packet and send out an ACK or NAK accordingly. If the data is found out to be not corrupt, it gets extracted and delivered up to the application layer and then the receiver sends an ACK back to the sender
  • ACK/NAK can be corrupted during communication. In such a case, sender will retransmit the current packet and add a sequence # to each packet so that the receiver can detect and discard duplicate packets
• Rdt 2.1
  • Sender is in one of the four possible states: the two of which are the same as those of rdt 2.0 but with the sequence # of 0; and the remaining two, with the sequence # of 1. The initial state is waiting for call 0 from above and on receiving an ACK, it transitions to waiting for call 1 from above. Upon receiving an ACK, it goes back to the initial state and the cycle repeats
  • Receiver has two possible states: waiting for 0 from below and waiting for 1 from below. When it receives a packet of 0 in the state of waiting for 1, it will still send an ACK since when it transitions to the other state, it will receive a packet of 1 anyways
  • TCP uses only ACK along with checksum

• Rdt 3.0

  • The underlying channel can both get corrupt or lose packets
  • Sender starts timer and waits some amount of time for ACK and retransmits the packet if it did not receive an ACK(timeout). When it receives a response, the timer stops. Corrupt packets are treated the same as lost packets that will be recovered by a later timeout retransmit. ACK with a wrong sequence number or any ACK received while waiting for call from above is ignored. When an ACK is lost or delayed, the sender will resend the packet again at timeout

• Pipeline Protocols

  • Stop-and-wait behavior of the protocol limits the performance of underlying channel. A more efficient alternative is pipelined protocol. Sender sends multiple yet-to-be-acknowledged packets. The range of sequence number should be increase in this case

  • In Go-Back-N protocol, sender can transmit N amounts of unacknowledged packets in a row. Sender has a window of size up to N that shows the state(whether it’s been sent/ack’ed). When a timeout occurs, sender retransmit the current packet and all the packes with higher sequence # in the window. Upon receiving a packet, Receiver sends an ack for the correctly received packet so far with the highest in-order sequence #

    

- In Selective Repeat protocol, receiver can individually acknowledge all correctly received packets and it can buffer an out-of-order packet  and later deliver it to the above. Sender maintains timer for each unACKed packet

    ![](https://velog.velcdn.com/images/sour_aguacate/post/16651afc-868c-443e-8e7f-4e6f7dafb953/image.png)

TCP Reliability, Flow Control and Connection Management

3-5 TCP Reliability, Flow Control and Connection Management part1

• TCP segment structure

  • Sequence #s in the header is the byte stream # of the first byte in segment’s data

  • ACKs are sequence # of next byte expected from the sender. It’s cumulative in that the number shows all the byte stream before that # has been received. This means even though the receiver gets a segment and has ACK pending, it will send only one cumulative ACK

    

• TCP round trip time, timeout
  • Timeout interval will be the average value of recent measured times from segment transmission until ACK receipt + safety margin
  • usually implemented so that timer checks for the oldest unACKed segment
• TCP fast retransmit
  • If sender receives 3 ACKS for same data, it will resend unACKed segment with the smallest sequence # in the current payload instead of waiting for timeout

3-5 TCP Reliability, Flow Control and Connection Management part2

• TCP flow control

  • How the transport layer receives a segment is first, when the segment is brought up to the transport layer the payload is removed from the segment and is written into the socket buffers. Then an application program will perform a socket read and that’s when the data is removed from the socket buffers. Flow control allows the receiver to control the sender so that the sender won’t overflow the receiver’s buffer by transmitting too much, too fast

    

- Receiver will notify the sender how much free space there is in the buffers so that the sender will know the limit of the amount of data it can send. It is specified in `rwnd` field in TCP header

• TCP Connection Management
  • TCP is connection oriented in that the sender and the receiver have a lot of shared state and they need to build them before establishing a connection
  • A handshake is done by the client reaching out the server(request) and the server answering back(accept) to establish a connection. This 2-way handshake doesn’t always work in network settings because of variable delays, message loss and other issues
  • TCP uses 3-way handshake. Both the client and server create a TCP socket and enter the LISTEN state. Then, the client connects to the server by sending a SYN message and a sequence number. Upon receiving it, the server enters the SYN RECEIVED state(not yet established). The server sends a SYN and ACK message back and the client finally sends an ACK message to the server. When the server receives the ACK, it enters the ESTABLISH state and that’s when the connection is established
• One side sends a FIN message, the other side sends a FIN and ACK message, after which it times out and closes

Principles of Congestion Control

• A congestions is when too many sources sending too much data too fast for network to handle. Long delays and packet loss can happen during congestion. It differs from flow control, which is about one sender sending data too fast for one receiver
• End-end congestion control mainly and network layer assisted congestion control tactics are used by TCP for congestion control

HTTP

• client(request)-server(response)
  • Client initiates TCP connection, or, creates a socket to server on port 80
  • Server accepts TCP connection from the client
  • HTTP messages are exchanged between browser and server(HTTP connection); in the process, at most one object is sent over TCP connection
• statelessness, meaning the server does not store the state of the client; so a transaction at hand theoretically does not have info on the prior transactions
• web cache to reduce load on server and reduce response time
• conditional GET to reduce load on server and reduce response time
• cookies to store the state of the client, or the user info

이후 내용은 추가할 예정