transport layer

end to end 통신, 양 종단 간에 있는 신뢰성 있는 전달로 보내는 것이 transport layer이다.

network layer

network 계층은 각각 라우터에서 모두 참조한다. 각 라우터에서 network layer의 header를 까보는 것이다. 이 때 읽은 정보를 토대로 routing하는 등 이런 부분을 처리한다.

datagram

transport layer에서는 segment였던 것이 network layer에서는 datagram이라고 부른다. 그래서 보내는 쪽이 segment를 datagram으로 encaptulation하고, 받는 쪽에서 segment로 바꾸어줘서 transport layer로 전달한다.

network layer의 두가지 기능

1. Forwarding

복수개의 output이 연결되어 있는 router의 input에 패킷이 들어왔을 때, 어느 port로 보내줘야 할 것인가를 결정해서 보내는 것을 말한다.

2. Routing

Forwarding하기 전에 어디로 보낼 것인가 결정하는 것을 말한다.(이는 routing 알고리즘에 의해 실행된다)

data plane, control plane

1. data plane

local 라우터마다 있는 기능이다. 어떤 datagram이 라우터의 input으로 들어왔을 때 어떻게 forwarding해줄 것인가(forwarding function) 이런 것을 data plane이라고 보면 된다. 즉 header에 있는 값(data)이 들어와서, 이 data마다 라우터에서 forwarding해주는 것이 data plane이다.

2. control plane

network-wide logic이다. 모든 라우터가 공통으로 돌릴 수 있는 부분들이다. 예를 들어 routing protocol같이 어떤 라우터든 공통으로 돌아갈 수 있는 것이 control plane이다. 그래서 datagram을 보낼 path를 결정하는 routing에 대한 것이 control plane이다.

1) Per-router control plane

각각의 router에 있는 control plane들의 서로와 상호작용하여 독립적인 routiong algorithm을 통해 나와 붙어있는 라우터들에 대한 정보를 알아낸다.(내 이웃 라우터를 알아야 다음 일을 진행할 수 있으며 각각의 라우터에 의해 path가 결정된다.)

2) Logically centealized control plane

각각의 라우터에 있는 controller들이 local cotrol agent(CA)이다. 중앙에 있는 Remote Controller와 interaction(상호작용)하는 것이다. 중앙집중되어 있는 알고리즘이다.

Network service model

sender에서 receiver까지 datagram을 transporting하는 "channel"에 대한 어떤 service model을 network service model이라고 한다.

< individual datagrams(각각의 데이터그램)에 대항 예 >

1. guaranteed delivery : 전달을 보장하는 것

2. guaranteed delivery with less than 40 msec delay : 40 msec 이내로 무조건 전달을 보장하는 것

<각각의 datagram마다가 아니라 datagram의 연속적인 각 flow에 대한 예>

1. in-order. 순서가 맞는 datagram을 전달해 주는 것

2. 이 flow에 대해서 최소한의 bandwidth를 보장해 주는 것.

3. 패킷들 간에 spacing에 대해 restriction(제한)을 주는 것.

ATM

network service model을 고려한 ATM이라고 하는 2000년대 초기의 network 스위치 장비가 있다. (Bandwidth, Loss, Order, Timing을 보장해줄 수 있다.) CBR (Constant Bit Rate) : 일정한 전송률을 갖는 서비스에 대해서 전부 게런티 보장해 줄 수 있다. VBR (Variable Bit Rate) : 가변적인 전송률에서도 게런티 보장해 줄 수 있다 ABR: Bandwidth와 order정도만 service하는 모델. UBR: order정도만 service해주는 모델.

< ATM vs Router >

ATM과 Router는 network layer에서 경쟁하던 관계였는데 지금은 ATM은 사라지고 Router만 사용한다. Bandwidth, loss, order, timing의 게런티를 보장해 줄 수 있는 것은 ATM이고, Router는 아무것도 게런티를 보장해 주지 못하는데 왜 ATM은 사라지고 Router를 사용할까? 그 이유는 가격이다.(ATM은 고가이고 Router는 저렴했기 때문이다)

Email system은 크게 3가지로 구성되어 있다.

1. user agent ( email을 주고받는 쪽. email을 사용하는 PC)
2. mail server
3. SMTP (simple mail transfer protocol)

위의 그림은 email system을 간단하게 나타낸 것이다. 이 그림을 바탕으로 email system을 알아보자.

User Agent

mail reader라고도 한다. 메일을 작성하거나 읽는 것을 수행한다.

Mail server

email msg를 가지고 있는 server이다. email을 갖고 온다고 하면, server에 저장되어 있는 메시지를 가지고 온다 생각하면 된다. 위 그림의 mailbox는 유저에게 들어온 email들을 가지고 있다. message queue는 나갈 email들을 가지고 있다.

SMTP(Simple Mail Transfer Protocol)

Mail server들 간에 주고받을 때 사용하는 protocol이다. mail을 보내는 쪽 서버가 client. 받는 쪽 서버가 server가 된다. 만약 daum.net에서 gmail.com으로 메일을 보냈다하면, daum.net server와 google mail server가 통신하게 되는데, 여기서 사용되는게 SMTP이다. SMTP는 TCP를 사용한다. port number는 25번 사용한다. 보내는 쪽과 받는 쪽이 같은 port number를 사용해야 한다. 메일을 보내는 과정은 3개의 과정으로 구성된다.

1. handshking: TCP connection open
2. transfer: 전송
3. closure: 위 과정이 끝나면 TCP connection close

Mail을 보내는 과정

Alice가 Bob에게 메시지를 보내는 과정

1. Alice가 someschool.edu 도메인으로 메일을 보냄(5번 서버에 해당하는 도메인이다.)
2. Alice의 user agent가 자신의 서버에 메시지를 보내고, queue에 저장. (queue에 저장하는 이유는 여러 사용자가 있기 때문에 쌓았다가 보내려고 저장하는 것이다.)
3. Bob의 메일 서버로 TCP connection을 연다.
4. SMTP는 Alice의 메시지를 TCP connection을 통해 보낸다.
5. Bob의 메일 서버가 Bob의 mailbox에 집어넣는다.
6. Bob이 자신의 user agent를 통해서 읽게되면 메시지(mail sever)를 가져와서 읽는다. (읽지 않으면 mail server queue에 저장되어 있음) 즉, Bob이 메일을 열변 mail server queue에 저장된 메일을 Bob의 user agent로 메일을 전송한다.

<요약>

1. Alice가 메일을 보낸다.
2. 3번 mail server에서 Alice의 메일을 받는다.(Alice의 mail server)
3. 5번 mail server로 Alice의 메일을 전송한다.(Bob의 mail server로)
4. Bob이 메일을 열면 Bob의 user agent로 메일 전송.(mail server -> user agent)

SMTP 예시

Handshcking을 하고, DATA 전까지 email을 주고받는데 필요한 과정을 주고받고, Do you like ketchup? How about pickles?(실제 메세지)를 전달하고 끝낸다.

HTTP와 SMTP비교

SMTP는 persistent connection을 이용한다.(email은 한번가면 연달아 가기 때문에 persistent connection을 이용한다.) HTTP는 server에 있는 내용 가져오는 것이고, SMTP는 server에다가 내용을 보내는 것이다. (HTTP : pull, SMTP : push) HTTP는 각각 오브젝트들은 각 메시지 내에서 encapsulated 되어 있는 형태이고, SMTP는 여러 개의 오브젝트들이 한번에 보내지는 형태이다. HTTP와 SMTP는 동일하게 ASCII코드이고, command/response 구조를 가진다.

Mail message는 header와 body 부분이 있다. header에는 To, From, Subject 가 있다.

To, From : 실제 이메일 내에 들어가는 보내는 사람, 받는 사람 정보 메시지.

Subject : 제목 정보

body 부분: 이메일 내용.(ASCII 형태로 되어있다)

(※주의) SMTP의 명령어 To, From과는 다르다. SMTP는 서버들 간에 주고받는 것이고, 이것은 실제 정보이다.

Mail access protocols

Mail access protocol이란 user agent가 Mail server로부터 가지고 오는 protocol이다.

(※주의) SMTP는 Mail server들 간에 메시지를 교환하는 protocol이다.

Mail access protocol에는 PEP3, IMAP, HTTP 등이 있다.

POP3(Post Office Protocol 3)

Post Office Protocol 3 또는 POP3는 인터넷을 통해 이메일을 수신하는 가장 일반적으로 사용되는 프로토콜이다. 대부분의 이메일 서버와 클라이언트가 지원하는 이 표준 프로토콜은 원격 서버(email server)에서 이메일을 수신하고 로컬 클라이언트(user agent)로 보내는 데 사용됩니다. POP3는 이메일을 수신하고 이메일 서버에 보관하는 단방향 클라이언트-서버 프로토콜이고 "3"은 원래 POP 프로토콜의 세 번째 버전을 나타낸다. 수신자 또는 이메일 클라이언트는 POP3를 사용하여 서버에서 주기적으로 메일을 다운로드할 수 있고 수신자가 오프라인으로 이메일을 볼 수 있도록 서버에서 클라이언트로 이메일을 다운로드하는 수단을 제공한다. POP3는 "저장 후 전달하는" 서비스로 생각할 수 있습니다. 이메일이 클라이언트에 있으면 POP3는 서버에서 이메일을 삭제한다. 그러나 일부 구현에서 사용자 또는 관리자는 메일이 일정 시간 동안 저장되도록 지정할 수 있어 사용자가 지정된 기간 내에 원하는 만큼 이메일을 다운로드할 수도 있다.

POP3 포트 POP3는 기본적으로 다음 두 포트에서 작동한다.

• 포트 110: 기본, 암호화되지 않은 포트
• 포트 995: 사용자가 POP3를 사용하여 안전하게 연결해야 할 때 사용해야하는 포트

authorization phase : user id와 password를 입력해서 맞으면 OK.(사용자 인증 과정이 있다)

transaction phase : 나한테 받은 email들의 list를 보여준다. (retr: msg를 가져온다, dele: 삭제)

<POP3와 IMAP 특징>

< POP3 >

• 다운로드와 삭제가 가능하다.(삭제하면 돌려놓는 건 불가능하다)
• download-and kepp 형태(email을 받아와서 PC에 email을 저장하는 형태)
• stateless하다.(요청에 대한 응답만 처리한다.)

< IMAP >

• 모든 메세지들이 내 PC말고 서버에 저장된다. 단지 서버에 있는 것을 읽는 것이다.
• user들이 폴더를 만들어서 메세지를 분류하는 기능이 있다.
• user의 state를 기록한다. 폴더의 이름, 매핑, 이메일의 폴더 위치

IMAP

저장된 메시지들에 의해 manipulation(조작)할 수 있다. 예로 폴더를 지정해서 폴더별로 관리할 수 있다.

HTTP

최근에는 그냥 웹으로 접속해서 메일을 본다.

Web caches

Web Caching은 client가 멀리 있는 origin server까지 가지 않고 가까운 proxy server의 web caches 파일에 접근하여 원하는 파일을 받아오는 기술이다. 그림을 통해 과정을 알아보자.

1. client가 proxy server에 접근해 caches file이 있는지 본다. 2-1.caches가 있으면 proxy server에서 데이터를 받아온다. 2-2. caches가 있으면 proxy server는 origin server로부터 데이터를 요청하여 받아온다. 받은 데이터는 proxy server에 저장된다. 그리고 client에게 데이터를 전달해준다. 그래서 최초의 client를 제외한 clients는 proxy server에서 정보를 받아올 수 있게 된다.(데이터를 찾을 때 RAM에서 찾아본 뒤 없으면 하드디스크에 가서 찾듯이 클라이언트가 proxy server에 먼저 접근해 Web caches는 굳이 멀리 있는 origin server로 가지 않고, 가까이 있는 proxy server로 가서 정보를 가져오기 때문에 요청-응답 시간을 줄일 수 있다.서 caches file이 있는지 보고 없으면 proxy server가 origin server에게 데이터를 요청하여 이를 받아서 proxy server에 저장한다. 이후 찾는 caches file은 proxy server에 있기 때문에 proxy server에서 데이터를 받아온다.) cache는 ISP가 운연한다고 한다.(하나의 네트워크를 운영하는 대락교, 회사 등등)

   Web caches의 장점

   1. response time을 줄일 수 있다.

   Web caches는 굳이 멀리 있는 origin server로 가지 않고, 가까이 있는 proxy server로 가서 정보를 가져오기 때문에 요청-응답 시간을 줄일 수 있다.

   

위의 그림으로 알아보자. 클라이언트가 origin server까지 가려면 acces link(1.54 Mbps)와 public Internet을 지나야 한다. 그러나 가까운 곳에 proxy server를 두면 1Gbps의 LAN link만 지나면 되기 때문에 훨씬 향상된 response time을 제공받을 수 있다.

2. server의 traffic을 줄일 수 있다.

Web caches를 사용하면 client의 request가 모두 server로 가는 것이 아닌, proxy server로 분산되기 때문에, 그만큼 request에 대한 traffic을 아낄 수 있다. 만약 40%가 hit되어 origin server로 오지 않는다면, 40%만큼 traffic을 아낄 수 있는 것이다.

Cacing 예시

1. Web cache를 이용하지 않는 경우

(가정) avg object size : 100K bits avg request rate (client -> origin server) : 15/sec RTT (institutional router -> origin server) : 2 sec access link rate : 1.54 Mbps client에서 origin server까지 15개의 object를 request한다면 object size가 100K bits 이기 때문에 avg data rate는 15 * 100K bits = 1500K bits = 1.5Mbits 이다. access link에서는 1.54Mbps가 주어져 있는데, 1.5Mbps를 보내고 있으니, bandwidth에 거의 꽉차게 보내고 있다. 이것은 queueing delay에서 배웠던 L*a/R (1 에 가까울수록 delay시간은 엄청나게 늘어난다는 사실을 보면, 1.5Mbps/1.54Mbps = 0.97... (1에 가깝다) 엄청난 delay가 발생할 것이다.)

위처럼 web caches를 사용하지 않는다면, total delay = Internet delay(RTT) (2sec) + access delay(엄청난 delay(1.5Mbps/1.54Mbps)) + LAN delay (1.5Mbps / 1Gbps)가 된다.

2. Web caches를 사용하는 경우

(가정)

avg object size : 100K bits avg request rate (client -> origin server) : 15/sec RTT (institutional router -> origin server) : 2 sec access link rate : 1.54 Mbps avg data rate : 1.5Mbps(100K * 10) hit rate (request 데이터가 web cache(proxy server)에 있다면 hit이라고 한다) : 0.4

hit이 40%라면, access link를 통과하는 데이터는 원래 지나던 데이터의 60%만 지나면 된다. 그러므로 access delay는 1.5Mbps * (0.6) / 1.54Mbps = 0.9Mbps / 1.54Mbps = 0.52... 이 되므로 delay가 훨씬 감소한다. Web caches를 사용한다면 total delay = internet delay(2s) * 0.6 + access delay(약 0.52s) + LAN delay(0.9Mbps/1Gbps)가 된다.(web caches를 사용하면 훨씬 적은 delay를 가져올 수 있다.)

Web page는 objects로 구성되어 있다. objects는 HTML file, JPEG, Java applet, audio file 등등으로 이루어져 있다. web page는 기본 objects가 포함된 기본 HTML file로 구성되어 있다.

각 오브젝트는 URL로 adderssable되어 있다.

HTTP는 웹에서 사용되는 web application layer protocol이다. web application은 HTTP외에는 protocol 없다고 생각하면 된다. client는 서버로부터 정보를 받아서 display한다. 서버는 URL 정보를 가지고 있고, 해당하는 응답을 보내준다. application layer에 있는 HTTP는 아래 transport layer에서 사용한 TCP를 사용한다. 웹은 신회성이 중요하기 때문에 신뢰성 없는 UDP보다 TCP를 사용하는 것이다. HTTP는 stateless하다(상태가 없다). (TCP는 stateful하다. TCP는 connection이 열려있는지 state가 있다.) HTTP 입장에서는 이 Client의 request에 대한 정보에 관심있다. 그냥 무언가가 오면, 상응하는 답을 보낼 뿐이다. stateless하기 때문에 가벼워서 서버가 부담없이 돌릴 수 있다.

HTTP

1. 비연결성(Connectionless)

비연결성은 클라이언트와 서버가 한 번 연결을 맻은 후, 클라이언트 요청에 대해 서버가 응답을 마치면 맺었던 연결을 끊어 버리는 성질을 말한다.

<HTTP 프로토콜이 한 번 맺은 연결을 끊어버리는 이유>

HTTP는 인터넷 상에서 불특정 다수의 통신 환경을 기반으로 설계되었다. 만약 서버에서 다수의 클라이언트와 연결을 계속 유지해야 한다면, 이에 따른 많은 리소스가 발생하게 된다.그래서 연결을 유지하기 위한 리소스를 줄이면 더 많은 연결을 할 수 있으므로 비연결적인 특징을 갖는 것이다. 즉, 한 번 맺은 연결을 끊어버리는 이유는 더 많은 호클라이언트와 연결을 하기 위해서이다.

이에 따른 단점도 있는데 서버는 클라이언트를 기억하고 있지 않으므로 동일한 클라이언트의 모든 요청에 대해, 매번 새로운 연결을 시도/해제의 과정을 거쳐야하므로 연결/해제에 대한 오버헤드가 발생한다는 단점이 있다.

오버헤드(overhead): 어떤 처리를 하기 위해 들어가는 간접적인 처리시간, 메모리 등을 말한다.

KeepAlive

오버헤드를 줄이기 위해 HTTP의 keepAlive 속성을 사용할 수 있습니다. KeepAlive는 지정된 시간동안 서버와 클라이언트 사이에서 패킷 교환이 없을 경우, 상대방의 안부를 묻기위해 패킷을 주기적으로 보내는것을 말하며 패킷에 대한 반응이 없으면 접속을 끊게 된다. 이 방법은 주기적으로 클라이언트의 상태를 체크해야 하므로 KeepAlive 역시 완벽한 해결책은 아니다. 왜냐하면 KeepAlive 속성이 On 상태라해도, 서버가 바쁜 환경에서는 프로세스 수가 기하급수적으로 늘어나기 때문에 KeepAlive로 상태를 유지하기 위한 메모리를 많이 사용하게 되기 때문이다.

2. 무상태(Stateless)

Connectionless(비연결성)로 인해 서버는 클라이언트를 식별할 수가 없는데, 이를 Stateless(무상태)라고 한다. 클라이언트의 상태를 모른다는 것을 예시를 통해 봐보자.

1. 쇼핑몰에 접속
2. 로그인
3. 상품 클릭 -> 특정 상품화면으로 이동
4. 로그인
5. 주문
6. 로그인
7. .....

매번 새로운 인증을 해야하는 번거로움이 발생하게 된다.

그렇다면 클라이언트의 상태를 기억하는 방법은 없을까? 한번 알아보자.

클라이언트의 상태를 기억하는 방법

클라언트의 상태를 기억하는 이유는 클라이언트의 인증을 유지하기 위해서이다. 서버는 클라이언트가 요청을 하기위해 로그인(인증)을 해도 다음 요청을 할 때 이를 기억하지 못한다. (쇼핑몰에서 페이지를 이동할 때 마다 로그인을 해야 된다....) 이는 사용자의 접근성이 매우 떨어지는 요인이 된다.

쿠키(Cookie)

쿠키란 클라이언트 측(브라우저)에서 관리되는 작은 기록 정보 파일을 의미한다. 쿠키에는 사용자 인증이 유효한 시간을 명시할 수 있고, 한 번 유효 시간이 정해지면 브라우저를 끄더라도 인증이 유지된다는 특징이 있다. HTTP는 state를 가지고 있지 않아, user의 id나 정보를 읽을 수 없다. 그래서 콘텐츠 제공, 차단 등과 같은 서비스를 제공하지 못한다. 이러한 단점 때문에 HTTP는 state를 가지고 있는 Cookie를 사용한다. Cookie는 state가 있어 사용자 정보를 읽어와 사용자 식별, 콘텐츠 제공 등을 수행할 수 있게 된다.

Cookie의 종류

1. HTTP response message의 header line에 Cookie
2. HTTP request message의 header line에 Cookie
3. user의 host, user의 browser에 의해 관리되는 Cookie
4. 웹사이트 백엔드 데이터베이스 상에 있는 Cookie

위 그림을 보몀 Cookie의 state가 어떻게 유지되는지에 대해 주목해보자.

1. client가 Amazon server로 request msg를 보냄
2. Amazon server에서 user ID(1678)를 생성하고, 데이터베이스에 기입하고 response 데이터에 담아서 보냄. (response Cookie(1))
3. client는 자체 웹에서 amazon 1678이라는 Cookie 파일 생성 (user brower Cookie(3))
4. 다시 접속할때 Cookie가 있으므로 request에 Cookie 파일을 담아서 보냄. (request Cookie(2))
5. server는 Cookie가 있다는 신호를 받고, 데이터베이스에서 Client의 정보를 꺼내 보내줌. (back end database Cookie(4))
6. client는 지난번에 했던 행동들을 다시 확인 및 수행

요약하자면Client에 Cookie 파일이 없으면 server에서 user ID 만들고 response msg에 Cookie 파일에 담아 보내준다. 그리고 이 user ID는 백엔드 데이터베이스에 기입한다. Client에 Cookie 파일이 있으면 request msg에 Cookie 파일을 함께 보내고, server의 백엔드 데이터베이스에서 user의 state에 해당하는 response msg를 보내준다. 여기서 알아야 할 것은, HTTP가 Cookie(state)를 전달해준다고 해서 HTTP가 state를 가지고 있는 것은 아니다. state를 가지고 있는 것은 Cookie이고, HTTP는 양쪽의 end points에서 상호보관하고 있는 Cookie(state)를 전달만 해준다는 것을 기억해야 한다.

<쿠키 구성 요소>

• 이름 각각의 쿠키를 구별하는 데 사용되는 이름
• 값 쿠키가 갖고 있는 값
• 유효시간 쿠키의 유지시간
• 도메인 쿠키를 전송할 도메인 (도메인(domain) 주소: 온라인상 위치를 나타내는 인터넷 프로토콜(IP)에 접근하기 위한 주소)
• 경로 쿠키를 전송할 요청 경로

<쿠키 동작 방식>

1. 클라이언트가 요청을 보냄
2. 서버에서 쿠키를 생성
3. HTTP 헤더에 쿠키를 포함시켜 응답
4. 브라우저가 종료되어도 쿠키 만료 기간이 있다면 클라이언트에서 보관하고 있음
5. 쿠키가 존재하면 요청을 할 경우 HTTP 헤더에 쿠키를 함께 보내서 요청한다.
6. 서버에서 쿠키를 읽어 이전 상태 정보를 변경할 필요가 있는 경우, 쿠키를 업데이트 하여 변경된 쿠리를 HTTP 헤더에 포함시켜 응답한다.

<쿠키 사용 예시>

• 방문 사이트에서 로그인 시 "아이디와 비밀번호를 저장하시겠습니까?"
• 쇼핑몰의 장바구니 기능

세션

세션은 쿠키를 기반으로 하고 있지만, 사용자 정보 파일을 브라우저에 저장하는 쿠키와 달리 세션은 서버 측에서 관리한다. 서버에서는 클라이언트를 구분하기 위해 세션 ID를 부여하며 웹 브라우저가 서버에 접속해서 브라우저를 종료할 때까지 인증상태를 유지한다. 물론 접속 시간에 제한을 두어 일정 시간 응답이 없다면 세션을 끊도록 설정이 가능 하다. 사용자에 대한 정보를 서버에 저장하기 때문에 쿠키보다 보안에 좋지만, 사용자가 많아질수록 서버 메모리를 많이 차지하게 된다. 즉, 동접자 수가 많은 웹 사이트인 경우 서버에 과부하를 주게 되므로 성능 저하의 요인이 된다.

※ 쿠키와 세션의 차이

쿠키와 세션은 비슷한 역할을 하며, 동작원리도 비슷하다.그 이유는 세션도 결국 쿠키를 사용하기 때문이다. 가장 큰 차이점은 사용자의 기록 정보가 저장되는 위치이다. 쿠키는 서버의 자원을 전혀 사용하지 않으며, 세션은 서버의 자원을 사용을 한다. 보안 면에서는 세션이 더 우수하며, 요청 속도는 쿠키가 세션보다 더 빠른데, 그 이유는 세션의 경우 서버에서의 처리가 필요하기 때문이다.

<세션의 흐름>

1. 클라이언트가 첫번째 최초 요청을 했을 때 서버는 목록에다가 카드를 하나만들어 두고(이는 위조 방지를 위해 만드는 거임) 그 카드를 html을 던져줄 때 header 부분에다가 담아서 웹브라우저(클라이언트)에 보낸다. 웹브라우저는 내부에 받았던 카드를 지니고 있다가(자동으로 저장이 됨, http프로토콜이기 때문에)
2. 두번째로 요청을 할 때 웹브라우저에 저장하고 있던 카드를 들고 간다. 서버는 그 카드가 목록에 있는지를 확인한다.(없으면 새로운 카드를 만든다.) 카으가 있으면 "너 이전에 온 적이 있구나."라고 서버가 인지하게 됨.(이 카드가 세션 id이다.) 이후 3번째, 4번쨰 요청때마다 계속 웹브라우저에 저정된 세션 id를 가져간다.

<세션 id가 사라지는 상황>

1. 서버에서 세션의 값을 날렸을 때(제거) -> 목록에서 해당 세션 id를 강제로 제거
2. 사용자가 브라우저를 다 종료시켰을 때(브라우저를 다 종료시키면 웹브라우저가 들고 있던 세션 id값이 날라가게 됨) ㄴ> 그러면 브라우저에서는 세션 id가 날라가서 없어졌지만 서버에는 남아있게 된다. (브라우저를 다 종료하고(닫고) 다시 요청을 보내면 서버는새로운 세션 id값을 만들어준다.)(그래서 서버가 특정 시간(보통 30분)동안 해당 세션 id로 요청이 없으면 알아서 세션 id값을 날려버린다.)
3. 특정 시간(보통 30분)이 지나면 서버쪽의 세션 id값이 사라지게 된다.

<세션 동작 방식(로그인 할 떄)>

1. 클라이언트가 최초로 리퀘스트를 한다.
2. 요청을 받은 서버는 세션이라는 저장소에 세션 id를 하나 만든다. 그러면 세션 id를 들고있는 조그만 저장소가 하나 생긴다.(세션의 전체 저장공간은 매우 크다.) - 다른 사용자의 요청도 받아야되기 때문
3. 이후 다시 웹브라우저에 응답을 해줄 때 헤더에 세션 id를 넣어서 돌려준다.
4. 그러면 클라이언트 쪽 웹브라우저에 세션 id가 저장이 된다.
5. (가정)이후 클라이언트 쪽에서 서버로 로그인 요청을 보낸다고 가정(아이디와 비번을 보냄(클라이언트 쪽에서))
6. 그러면 서버는 데이터베이스에서 클라이언트에서 보낸 아이디와 비번이 있는지 확인한다.
7. (만약 정상적으로 DB에 저장되어 있는 값이 들어왔다면) 세션 쪽에 세션 id 밑에 만들어놓은 조그만 저장소에 지금 클라이언트 쪽에서 로그인 요청을 한 유저의 정보를 저장을 한다.(이 정보는 DB에 있는 로그인 요청을 한 유저의 유저정보이다.) (이후 로그인이 성공을 하면 메인페이지로 리턴을 해준다.(html파일))
8. (가정) 이후 클라이언트 쪽에서 유저 정보를 요청을 했다면 서버는 이 사람이 지금 유저 정보에 접근을 하는거니까 세션id가 있는지 확인하고 해당 세션id가 세션에 있는지 확인하고 유저정보 요청을 했으므로 밑의 저장소(7번에서 만들어진 저장소)에 유저의 정보가 있는지도 확인한다.
9. 만약 유저정보까지 정상적으로 확인했다면 DB에서 사용자가 요청한 데이터를 응답 받는다.
10. 응답을 받은 뒤 이를 서버가 다시 웹브라우저로 돌려준다. (이거 반복)

세선의 단점

서버를 여러개 만들어 놨을 때 클라이언트가 접근 할 때 로드 밸런싱이 일어난다면 서버의 세션의 정보는 각가 다르기 때문에 클라이언트 입장에서는 로그인을 여러번 해야하는 상황이 생길 수가 있다. 그럼 이 단점을 해결할 방법은 없을까?

<이를 해결하는 방법>

1. Sticky 서버를 만들어서 해결 (클라이언트가 최초의 요청을 할 때 동작했던 서버로만 요청을 계속하도록 만드는 방법)
2. 각 서버의 세션을 복제를 시킴(새로운 데이터가 만들어 질 때 마다 복제) (1,2번 둘 다 귀찮은 짓이고 효율적이지 않다.)
3. 각 서버들이 세션에다가 정보를 저장하는 것이 아니라 이 서버들이 데이터베이스에 세션 값을 넣고 이를 공유해서 쓰는 방법 (단점: 세션이라는 거는 원래 서버가 들고 있는건데 이 방법은 메모리에 접근해서 데이터를 들고 오는 방식이라 엄청나게 빠른데 이 세션 값을 데이터베이스에 넣는다면 IO가 일어나서 데이터를 하드디스크에서 찾아야한다. 그러면 엄청나게 느려진다.) 원래 CPU가 어떤 데이터가 필요할 때 RAM으로 먼저가서(하드디스크에서 찾으면 너무 오래걸리기 때문에) 데이터가 있는지 확인을 하고 없으면 하드디스크로 가서 찾고자 하는 데이터를 찾는다. 만약 RAM에서 못 찾은 데이터를 하드디스크에서 찾았다면 하드디스크에서 찾은 데이터를 RAM에다가 넣고 CPU한테 줘서 데이터를 처리함. 이후 만약 똑같은 데이터를 요청한다면 이때는 하드디스크에서 찾는게 아니라 RAM에서 찾아서 CPU에서 데이터를 줘서 처리를 하게 된다. 이를 캐싱이라고 한다. (그래서 첫번째 요청은 IO가 일어나서 하드디스크까지 데이터를 찾으러 갔다가 와서 시간이 오래걸리지만 두번째 요청은 RAM에서 데이터를 찾아 CPU로 주기 때문에 엄청 빠르다. 그리고 두번째 요청 때는 IO가 일어나지 않는다.) (하드디스크에 접근했다는 건 IO가 일어났다는 것이고 IO가 일어나는 순간 속도가 100만배정도가 느려진다.) (RAM에 접근하면 전기적 신호로 데이터에 접근하는 것이기 때문에 랜덤 Access가 발생하지 않는다. 원하는 위치로 다이렉트하게 접근이 가능하다. 하지만 하드디스크에 접근할 때는 하드디스크에 있는 데이터에는 다이렉트하게 접근이 불가는하다. 왜냐하면 하드디스크에서 데이터를 찾을 떄 하드디스크는 원판모양으로 생겼는데 액츄에이터라는 침과 디스크 원판이 돌면서 데이터를 일일히 찾는(정확한건 찾아보기) 그래서 대부분 하드디스크에 있는 데이터는 풀스캔을 하게 된다. 그래서 IO가 일어나면 굉장히 느려진다.) 3번은 데이터베이스에 데이터를 넣으면 IO가 일어나기 때문에 데이터를 찾는데 굉장히 오랜 시간이 걸리게 된다.

(※ 1,2,3번 모두 해결할 수는 있는 방법들이지만 효율적이지는 않다.) 4. 그래서 보통 메모리 서버를 쓴다. (왜냐면 메모리(공유)서버를 쓰면 IO가 일어나지 않으므로) (메모리 서버는 RAM만 존재, 하드디스크 존재 X) (전기적 신호로 접근하여 다이렉트하게 데이터를 찾아옴) 이 방법으로는 서버들이 메모리 서버에 세션 값을 저장해놓고 같이 공유해서 사용하면 된다. 그러면 위의 문제들이 발생하지 않는다. (대표적인 예: Redis서버)

토큰을 사용하는 OAuth, JWT

쿠키와 세션의 문제점들을 보완하기 위해 토큰(Token)기반의 인증 방식이 도입되었다. 토큰 기반의 인증 방식의 핵심은 보호할 데이터를 토큰으로 치환하여 원본 데이터 대신 토큰을 사용하는 것이다. 그래서 중간에 공격자로부터 토큰이 탈취당하더라도 데이터에 대한 정보를 알 수 없으므로, 보안성을 높은 기술이다. 대표적으로는 OAuth와 JWT이 있습니다. 나중에 더 자세히 다뤄보겠다.

HTTP Method

클라이언트가 서버로 요청을 할 때, 어떠한 목적을 갖는 행위인지 HTTP 메서드에 명시해야한다.(GET, HEAD, PUT, POST, DELETE, TRACE, OPTIONS) GET 서버에게 리소스를 달라는 요청 (조회)

HEAD HTTP HEAD 메서드는 특정 리소스를 GET 메서드로 요청했을 때 돌아올 헤더를 요청한다. HEAD 메서드에 대한 응답은 본문을 가져선 안되며, 본문이 존재하더라도 무시해야한다. 그러나, Content-Length처럼 본문 콘텐츠를 설명하는 개체 헤더는 포함할 수 있는데 이 때 개체 헤더는 비어있어야 하는 HEAD의 본문과는 관련이 없고 GET 메서드로 동일한 리소스를 요청했을 때의 본문을 설명한다.

PUT 서버가 요청의 본문을 갖고 요청 URI의 이름대로 새 문서를 만들거나, 이미 URI가 존재한다면 요청 본문을 변경할 때 사용한다.(수정)

POST 서버에 입력데이터를 전송하며 요청 엔티티 본문에 데이터를 넣어 서버에 전송한다.(삽입)

DELETE 서버에서 요청 URI 리소스를 삭제하도록 요청합니다.(삭제) 클라이언트는 항상 삭제된다고 생각하지만, 서버에서는 이 요청을 무시할 수도 있다.

TRACE 클라이언트와 목적지 서버 사이에 있는 모든 HTTP 애플리케이션의 요청/응답 연쇄를 따라가면서 자신이 보낸 메시지의 이상 유무를 파악한다. 서버는 응답 메시지의 본문에 자신이 받은 요청메시지를 넣어 응답하며, 주로 진단을 위해 사용한다.

OPTIONS 서버에게 특정 리소스가 어떤 메소드를 지원하는지 물어볼 수 있다.

HTTP connections

HTTP connection은 두가지가 있다.

1. non-persistent HTTP TCP connection에 한 오브젝트만 보내고 connection을 닫아버린다. web 브라우저 띄울 때마다 connection을 열고 닫고 하는것이다.

2. persistent HTTP

TCP connection을 하나 열고, 복수개의 objects가 전달하고, 전달이 끝나면 connection을 닫는다.

Non-persistent HTTP

위의 사진 순서를 보면 위와 같은 URL을 들어간다고 가정해보자.

1a. HTTP client가 HTTP server한테(process) TCP connection을 요청한다(www.comeSchool.edu로 port 번호 80으로).

1b. HTTP 서버는 www.someSchool.edu(port 번호 80으로)로 TCP connection을 요청한 HTTP 클라이언트에게 요청을 잘 받았다고 메세지를 통해 알려준다.

2. HTTP 클라이언트는 HTTP request 메시지(URL을 포함하여)를 TCP 연결 소켓으로 보냅니다. 이 요청 메세지는 HTTP 클라이언트가 웹 페이지 클릭에 해당하는 주소(someDepartment/home.index(path name))이라는 object를 원한다는 것을 알려준다.

3. HTTP 서버는 HTTP 클라이언트가 보낸 요청 메세지를 수신하고 요청받은 object(someDepartment/home.index(path name))를 포함하는 response 메세지를 만들어서 소켓으로 보낸다.(해당하는 데이터 or 에러 메시지)

4. 하나 주고 받았으니 HTTP server는 TCP connection 닫음

5. HTTP 클라이언트는 response 메세지를 포함하는 html 파일을 받고 클릭에 해당하는 html 웹 페이지가 보여지게 된다. html 파일을 파싱하면서 10개의 referenced된 jpeg object 보게 된다. (HTTP client는 닫았다는 소식 받고, 클릭에 해당하는 것을 display)

6. 1~5번 과정 반복

RTT (Round Trip Time) : 메시지가 갔다가 온데까지 시간. 하나의 TCP connection을 만드는데 하나의 RTT를 소요한다. HTTP 보내고 response 받는데 걸리는 시간으로 또 RTT 하나 소요한다. 위의 굵은 선은 transmission time이다. 결론은, 2RTT + transmission time이 걸린다.

Persistent HTTP

Non-persistent HTTP에서는 하나의 데이터를 주고 받으려면 2RTT + transmission delay만큼의 delay가 생긴다. 두배 정도 오래걸리는 것이다. 이 문제를 해결하기 위해 Persistent HTTP가 등장했다. Persistent HTTP는 server가 하나의 response를 보내도, connection을 열어놓는다. 그리고 일정시간동안 데이터가 오지 않으면 connection을 닫는다. 이렇게 처음 데이터에 대해서 connection을 열고, 바로 닫지 않기 때문에 여러 개의 데이터를 받아도 delay time이 Non-persistent HTTP보다 짧아지는 것이다.

예시) 만약 10개의 objects를 주고 받는다하면 delay time은 1RTT(connection) + 10RTT(objects) + 10 transmission time이 될 것이다.

HTTP request, response

requset

• header : body를 전달하는데 필요한 값. 버전이 뭐고, URL이 뭐고 등등
• body : 진짜 전달하는 내용물

<클라이언트가 request를 보내는 방법>

1. POST 방식

web 페이지 자체가 input을 가지고 있다. input이 body 내에 들어와서 보내진다. 내가 무언가를 request할 때, 구체적인 내용이 body부분으로 들어가는 방식이다.

2. URL 방식

GET Method 사용. input이 request line 안에 URL field에 찍혀있다.

response

HTTP response status codes

200 OK : 성공했다. 301 Moved Permanently : 요청된 오브젝트가 서버의 로케이션에서 사라졌다(옮겨졌다). 400 Bad Request : 서버가 이해할 수 없는 request가 왔다. 404 Not Found : 서버에 request에 해당하는 것이 없다. 505 HTTP Version Not Supported : HTTP의 버전이 안 맞다. (오래된 프로토콜을 전부 지원해주므로 보기 힘들 것이다.)

Process는 호스트 내에서 돌아가는 프로그램이다.(application layer에 존재) 같은 호스트 내에서 복수개의 processes가 돌아갈 수 있다. 두 개의 processes가 내부적으로 communication할 수 있다. 다른 호스트들에 있는 processes과는 messages 교환을 통해 communication한다.

Client-Server 구조에서는, server가 데이터를 제공하기 위한 process와 client는 데이터를 받기 위한 process가 다르다.

P2P 구조는 client processes와 server processes가 존재한다.

Socket

양쪽의 application process가 서로 메세지를 주고 받으려고 할 때 일종의 문 역할을 하는 것을 Socket이라고 한다. socket은 메세지를 transport layer로 전달한다. 즉, application layer의 process가 메세지를 던지면 socket을 통해 메세지가 transport layer로 간다.

Addressing processes

메시지를 받기 위해 process는 id가 필요하다. 이것이 port number이다. port nunmber와 ip address를 예시로 설명해보자면 한 집에 4식구가 산다고 가정했을 때 집주소는 IP주소이고, 그 집의 각 사람들에게 붙힌 이름은 port number라고 생각하면 된다. 많이 사용하는 port number는 정해놓는다.(HTTP는 80, mail은 25) IP주소가 128.119.245.12 인 호스트에서 HTTP 메시지를 보낸다하면, port number는 80으로 보내는 것이다. 상대방은 IP주소를 보고 호스트를 구별하고, port number를 보고 processes를 구별하는 것이다. IP주소가 128.119.245.12 인 호스트에서 HTTP 메시지를 보낸다하면, port number는 80으로 보내는 것이다. 상대방은 IP주소를 보고 호스트를 구별하고, port number를 보고 processes를 구별하는 것이다.

Application architectures는 두가지가 있다.

1. client-server

2. peer-to-peer(P2P)

Client-Server

Client-server 구조는 client와 server간에 데이터를 주고받는 형태이며 client는 데이터를 요청해서 받는 쪽이고, server는 데이터를 보내는 쪽이다.

Server

• client가 언제 데이터를 요청할 지 모르기 때문에 server는 항상 ON상태읻.
• client가 같은 IP주소로 정보를 요청하므로 server의 IP주소는 고정되어 있다.
• data center(cloud 기반)를 통해서 서버가 운용되는 경우도 있다.

Client

• 시간 간격을 두고 일어나는 방식(간헐적)으로 연결된다.
• 일반적으로 동적 IP주소를 가진다.(IP주소가 충분하지 않기 때문에)
• Clients끼리 직접적으로 communication을 못한다. 반드시 server를 통해서 데이터를 주고받는다.

Peer-to-Peer(P2P)

P2P방식은 서로 동등한 Peers(end systems)끼리 직접적으로 communication을 해서 정보를 주고 받는 방식이다. 새로운 peers가 나타나면 스스로 규모가 늘어나며 P2P link가 많아진다. 이것을 self scalability(자기 확장성)라고 한다.

<특징>

• server같이 항상 ON되어 있는 것이 없다.
• peers는 IP주소를 변경할 수 있다. 새로운 IP주소가 부여 된 상태여도 여전히 P2P link를 유지하고 있다.
• 제약조건: 사용자의 IP주소가 동적으로 바뀌면 P2P 네트워크를 뚫고 들어가지 못하는 경우가 있다. 그래서 네트워크 환경에 따라 P2P가 될수도 안될수도 있다.

네트워크는 매우 복잡하다. 매우 많은 "pieces"가 존재한다.(hosts, routers, links of various media, applications, protocols, hardware, software 등) 네트워크는 이런 복잡한 구조를 layer 별로 구분하여 각 층마다 다른 기능을 수행해낸다. 네트워크에서 layer를 나눈다는 것은 소프트웨어에선 Component를 나눈다는 표현과 같다. 이렇게 층을 나누면 장점이 뭘까? 컴퓨터를 예시로 생각해보자. 컴퓨터는 일체형 컴퓨터, 분리형 컴퓨터가 있다. 일체형 컴퓨터에 하나라도 고장이 나면 전부 가져가서 고쳐야한다. 하지만 분리형 컴퓨터는 고장나면 고장난 것만 가져가서 고치면 된다. 즉, 각 모듈별로 관리해주면 되기 때문에 유지보수가 편하다. 그리고 1개의 layer가 바뀌어도 나머지 layer에 영향을 주지 않는다.

네트워크는 전세계적으로 이용하기 때문에 전세계적으로 공통으로 만들어져야 한다. 그래서 reference moodel이 나오게 되었고 reference model에 들어가는 protocol도 공통되어야 한다. 이 reference model은 국제표준기구 ISO에서 만들었다.

프로토콜 스택이란 데이터 통신에 활용되는 프로토콜의 구조에 관한 개념으로, 계층화된 구조(스택 구조)로 모여있는 프로토콜의 집합을 의미한다. 프로토콜 슈트(Protocol Suite) 또는 프로토콜 패밀리(Protocol Family)라고 불리며 프로토콜 스택이라는 이름이 붙여진 까닭은 자료구조의 스택과 유사한 모습의 구현체이기 때문이다.

application

• 실제 네트워크를 활용하는 application이 어떤 소프트웨어인가.
• 쓰이는 protocol : FTP, SMTP, HTTP

transport

• data 전송에 대한 process. 주로 하는 건 신뢰성 있는 전달.
• protocol : TCP, UDP

network

• 경로를 가르쳐주는 Routing. 데이터가 어디로 가야할지 알려준다.
• protocol : IP, routing protocols

link

• 매체가 무엇이냐에 따라 그 매체에 적합하게 데이터를 보낼 수 있게 하는 길.
• Ethernet, 802.11(WiFi), PPP

physical

• 실제 물리적인 매체

OSI 7계층(OSI 모형)

OSI 모형(Open Systems Interconnection Reference Model)은 국제표준화기구(ISO)에서 개발한 모델로, 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 것이다. 이를 일반적으로 OSI 7계층이라고 한다.

최초의 표준 reference model이다. Internet에서는 application, presentation, session을 묶어서 application layer이다.

• presentation : 보안, 데이터 압축, 기계 특화

• session : 동기화, 체크포인트, 데이터 교환할 때 recovery

source에서 destination까지 데이터를 보내는 과정은 다음과 같다.

• 각 계층을 거치면 그 계층의 정보(헤더)가 붙는다.

• switch에서 어느 경로로 갈지 결정 (router와 다르게 link계층까지만 헤더를 읽는다.)

• router도 어느 경로로 갈지 결정 (network 계층까지만 헤더를 읽음)

• destination에서 다 일고 데이터를 받는다.

Packet sniffing, Ip snoofing

Packet sniffing

sniffing은 해킹 기법으로서 네트워크 상에서 자신이 아닌 다른 상대방들의 패킷 교환을 엿듣는 것을 의미한다. Packet sniffing은 공유된 Ethernet, wireless 같은 곳에서 일어난다. 네트워크는 정보를 확인할 때 모든 곳에 뿌리고 그 사람이 맞는지 체크하는 방식이다. 이런 점을 이용한 것이 packet sniffing이다. 위의 그림으로 예시를 보며 이해해보자.

B가 A하네 정보를 보내려고 하는데 이 정보는 A한테 뿐만 아니라 이 네트워크에 물려있는 모든 host에 간다. 그래서 C한테도 가는데 이 때 C가 A인척을 해서 정보를 받는 것이 packet sniffing이다.

IP spoofing

스푸핑(spoofing)이란 직접적으로 시스템에 침입을 시도하지 않고 피해자가 공격자의 악의적인 시도에 의한 잘못된 정보, 혹은 연결을 신뢰하게끔 만드는 일련의 기법들을 의미한다. 한마디로 속임수 혹은 사기이다. 위의 그림으로 예시를 보며 이해해보자.

네트워크에서는 반드시 IP주소를 포함하여 패킷을 보내야한다. C가 A한테 정보를 보내느데, source 정보를 B의 IP 주소로 해서 보내서 A는 A가 받은 패킷이 B가 보낸 패킷이라고 알고 받게 되는 것을 IP spoofing이라고 한다.

Host는 데이터를 전송할 수 있는데 전송하려는 데이터를 잘라서 보낸다. 이것을 Packet이라고 하며 쉽게 말해 전송하는 데이터를 일정한 크기의 데이터로 자르는 것을 Packet이라고 한다. 서버에서 주고받는 데이터는 모두 Packet이라고 생각해도 되며 실제 전송되는 데이터 단위이다.

패킷 전송 지연과 손실과 처리율(Packet transmission delay and loss and Throughput)

각 패킷의 길이가 L일 때 어떤 host에서 데이터를 보내는데 link에서 보낼 수 있는 전송률, 즉 link transmission rate를 R이라고 한다면 L bit짜리 데이터를 R이라는 link transmission rate를 가지고 있는 링크를 통해 전송할 때 전송 delay는 어떻게 될까?

패킷 전송 지연 = L비트의 패킷을 링크로 전송하는데 필요한 시간 = L(bits)/R(bits/sec)

• link: 링크는 노드 사이의 패킷을 전달하기 위한 물리적인 통신경로를 말한다.
• R은 capacity, link bandwidth라고 말할 수 있다.

즉, 패킷의 길이 L을 link의 전송률 R로 나누면 된다.

단위시간 동안 도착하는 패킷으이 수가 output link의 capacity를 넘어설 때 라우터의 queeu에 패킷잉 대기상태로 쌓이게 되어, delay가 발생하게 된다. 이것을 queueing delay라고 한다. 만약 queue가 가득 차서 더 이상 패킷을 받을 공간이 없다면 이 패킷은 버려지게 된다(packet loss).

위의 그림처럼 delay에는 총 4가지가 있다.

• nodal processing

• queueing delay
• transmission delay
• propagation delay

1. nodal processing delay(노드 처리 지연)

Nodal processing은 라우터(노드)에서 작업을 할 때 걸리는 시간을 의미한다. 참고로 Nodal delay는 Nodal processing과 다르고, Nodal processing은 Node processing과 같다. 라우터에서 하는 작업에는 패킷의 bit error를 측정하고, 목적지로 보낼 패킷의 헤더를 조사하고 어느 출력 링크(output link)로 보낼지 나갈 통로를 결정하는 작업(routing algorithm이 돌아가는 시간)을 한다.

2. queueing delay(큐잉 지연)

queue에서 패킷이 대기상태로 쌓여 나갈떄까지 기다리는 시간을 말한다.

3. transmission delay(전송 지연)

패킷의 모든 비트들을 링크로 전송하는데(밀어내는데) 필요한 시간을 말한다. 저장 후에는 전파 지연(propagation delay) 데이터가 전송되는데 걸리는 시간을 말한다.(L/R) L: 패킷의 길이(bits) R: 링크 전송률(link bandwidth, bps)

4. propagation delay(전파 지연)

출력 링크에서 다음 라우터까지 전파하는데 필요한 시간이며 전파 속도는 링크의 물리 매체(광섬유, 꼬임쌍선 등)에 좌우된다.

전파 지연 = d(두 라우터 간의 거리(length of physical link)) / s(매체의 전파 속도) (210^8 m/sec ~ 310^8 m/sec)

5. 전체 노드 지연(nodal delay)

nodal delay = dproc + dqueue + dtrans + dprop

• transmission delay : 이미 결정되어 있는 프로토콜. 어떤 식으로 신호를 변환할지 결정되어 있다. 패킷의 길이에 따라 달라지겠지만 IP에 따라 패킷의 크기가 고정되어 있기에 값이 크게 달라지지 않는다.

• propagation delay : 라우터들의 물리적인 거리를 바꾸지 않는 이상 바뀌지 않음. 거리 대비 커진다. 클 수도 있지만 고정된 값이기 때문에 예측하기 쉽다.

• nodal processing : nodal processing은 CPU 노드에 따라 달라지지만 워낙 작은 값이라 크게 신경 안써도 된다.

• queueing delay는 혼자 데이터를 보내는 것이 아니라 수많은 end systems이 언제 어디로 보낼지 예측 불가능하다. 가장 가변적이다.(4가지 delay 중 가장 가변적인 것은 queueing delay이다.)

6. 트래픽 강도(traffic intensity)

큐잉 지연의 정도를 측정, 큐가 아주 커서 무한대 비트를 저장한다고 가정 La / R(능력이 R인데 단위시간마다 La만큼 데이터를 처리해달라고 요청)

L: 패킷 길이(bits) a: 패킷이 큐에 도착하는 평균율(packets/sec) R: 링크 전송률로 비트가 큐에서 나가는 비율(bits/sec) (0에 가까우면 평균 큐잉 지연이 작은거고 1에 가까우면 큐잉 지연은 매우 큰거다. 1보다 커지면 서비스 용량을 초과하여 평균 지연이 무한대로 커진다.)

※ 엄청나게 delay가 늘어나는 것보단 버리는 게 낫다.

7. 패킷 손실(packet loss)

Packet loss는 위와 같이 라우터의 buffer가 가득차서 packet이 들어갈 공간이 없을 때 버려지는 현상이다. 잃어버린 패킷은 이전 노드나 출발지 노드에서 재전송 될 수 있다.

8. 처리율(throughput)

단위시간 동안 sender와 receiver가 교환된 데이터의 양을 말한다. 정확히 말하자면 데이터를 보내는 source가 목적지를 향해서 데이터를 보냈고, source가 받은 데이터의 양을 말한다. throughput은 link의 bandwidth가 고정되었다 하더라고, 망상태에 따라(사용자가 얼마나 몰렸느냐) 달라지기도 한다. 처리율은 한마디로 성능이라고 할 수 있다.

<순간적인 처리율(instantaneous throughput)>

주어진 순간에 전송 비율을 말한다. (파일 수신 시 파일을 수신하는 비율)

<평균 처리율(average throughput)>

주어진 시간 동안의 전송 비율 (파일의 크기가 F이고 모두 수신하는데 T초가 걸리면 F/T(비트/초)가 평균 처리율이다.)

bottleneck link(병목현상)

위 그림처럼 네트워크의 각 link의 capacity가 다를 수 있다. 이런 상황에서 자기가 가지고 있는 capacity를 낭비하거나 패킷이 버려지는 경우가 생길 수 있다. 이를 어떻게 하면 해결할 수 있을까? 가장 좁은 길을 파악해서 그 좁은 길의 용량을 기준으로 그 용량만큼 보내면 된다. 가장 좁은 길(성능이 가장 낮은 길(link))을 bottleneck(병목)이라고 한다. 결국 전체적인 네트워크의 link의 성능은 이 bottleneck link가 좌지우지한다.

※ 데이터를 보내는 입장에서는 데이터를 보낼 때 bottleneck이 어딘지 모른다. 이런 문제를 해결하기 위해 TCP가 있다. 데이터를 보낼 때마다 망상태를 보고 보낼 데이터를 결절한다.

네트워크는 여러사람과 공유하여 사용한다. 네트워크가 안되는 원인을 알아보자.(성능 저하)

• link capacity가 작아서

• core network 상에 있는 어떤 라우터가 라우터의 link를 여러 사용자들에게 공유하는데, 내 지분이 너무 작아서

그렇다면 end system과 ens system 사이의 성능은 누가 결정할까? 서버의 네트워크, source의 네트워크 destination의 네트워크 또는 공유하는 네트워크에 대한 내 지분의 최소값에 따라 좌지우지하게 된다. 보통 core는 좋은 걸 쓰기 때문에 나머지 부분에서 결정된다. 그래서 Rc나 Rs가 대부분 bottleneck이 된다.(link capacity에 의해 좌지우지됨.)

우리가 항상 사용하는 스마트폰과 PC는 네트워크와 연결되어 있어 다양한 일들을 할 수 있다. 네트워크는 크게 3가지로 구성되어 있다.

1. 네트워크 엣지(Network edge)
2. 엑세스 네트워크(Access network)
3. 네트워크 코어(Network core)

각각의 네트워크 구성요소들을 알아보자.

네트워크 엣지(Network edge)

네트워크의 가장 가장자리이며 여기에는 수많은 end system들이 존재한다. end system이란 host라고 생각하면 되는데 host는 클라이언트나 서버를 뜻한다. 네트워크 엣지란 네트워크의 가장 말단에 존재하는 여러 구성요소라고 생각하면 된다.

엑세스 네트워크(Access network)

end system과 end system이 통신을 할 떄 Network core로 들어가기 위한 라우터들이 존재하는데 통신을 하고자 하는 end system에서 경로상에 있는 첫번째 라우터(edge router)에 연결하는 네트워크를 access network라고 한다(edge router와 system을 연결시켜주는 network). 즉, end system이 네트워크에 연결되기 위해 제공되는 네트워크가 access network라고 보면 된다. 예를 들어 스마트폰에서 와이파이에 접속하거나 PC에 랜선을 꼽는 것 모두 엑세스 네트워크에 접속하는 것이라고 할 수 있다. 대부분 KT나 SKT같은 ISP(Internet Service Provider)가 엑세스 네트워크를 제공해준다.

access network를 연결시켜주는 다리 연결을 해주는 라우터들의 집합을 Core Network라고 하며 Core Network에는 라우터들만 존재한다.

< edge router에 어떻게 end systems가 연결될까? >

• 집은 residential access networks를 설치하면 된다.
• 학교, 회사 기관은 institutional access networks를 설치하면 된다.
• 기지국 같은 곳은 mobile access network를 설치하면 된다.

DSL(Digital Subscriber Line)

Accee network의 예시로 DSL이 있다. 통신사에 연결된 link가 집 안에서 전화기, 인터넷으로 나눠지며 모두 같은 네트워크에 물리게 된다. 그런데 전화는 dedicate, 인터넷은 share이다. 그림을 보면서 이해해보자.

• 가정의 DSL modem: 컴퓨터의 디지털신호를 아날로그 신호로 변환해준다.
• 가정의 splitter: DSL modem을 거쳐 온 컴퓨터의 데이터와 전화의 음성을 서로 다른 주파수로 central office의 DSLAM에 보낸다. 그리고 central office의 DSLAM으로부터 받은 데이터를 음성과 데이터로 분리하여 보낸다(가정으로 보낸다).

먼저 가정은 telco(유선 로컬 전화 서비스를 제공)로 부터 DSL 인터넷 접속 서비스를 받는다. 가정의 DSL모뎀은 PC의 digital data를 받아서 telco의 CO(Central Office)로 전송하기 위해 디지털 데이터를 아날로그 신호로 바꿔주는 역할을 한다. 또한 CO에 위치한 DSLAM과 데이터 교환을 하기 위해 existing telephone line(기존 전화 회선)인 twisted pair(TP,꼬임쌍선)을 사용한다. PC와 전화기에서부터 온 분리된 data들은 DSL phone line을 통해 동시에 전달되며, 서로 다른 주파수로 전달된다. DSL 접속은 downstream의 대역폭(bandwidth)은 크게, upstream의 대역폭은 좁게하여 전송된다. 그 이유는 downstream(CO -> 가정)로 데이터가 전달 되는 것이 upstream(가정 -> CO)보다 많기 때문이다. 그래서 upstream과 downstream의 데이터 전송 속도도 다르다. 즉, 접속이 비대칭하다. 이를 접속이 asymmetric하다고 한다. (대역폭이 크면 전송속도가 빠르다.) 이를 ADSL(Asymmetric Digital Subscriber Line, 비대칭 디지털 가입자 회선)이라고 한다. 하나의 DSL phone line은 data가 동시에 전송되는 것이 가능하다.(PC와 전화기에서 부터 온 분리된 데이터들을 동시에 전달 가능하므로) 이렇게 동시에 전송이 가능한 특징을 가지고 있는 링크는 dedicated link이라고 한다. 전화는 dedicated link이고 인터넷은 shared link이다. telephone network와 ISP에서 downstream된 data와 음성 신호가 CO의 DSLAM을 만나 다시 모아지고 dedicated line을 통해 비교적 빠른 속도로 전송된 data들은 splitter를 만나 splitter에 의해 들어온 데이터와 음성 신호를 분리하고 데이터를 PC로 보내준다.

< upstream > (사용자에서 보내는 데이터) PC의 digital data는 DSL modem을 통해서 디지털 신호에서 아날로그 신호로 바뀌고 이후 음성신호와 같이 DSL phone line을 통해 동시에 전달이 된다. spliiter에서 음성 신호와 데이터를 서로 다른 주파수로 central office의 DSLAM으로 보낸다.

< downstream > (사용자가 받는 데이터) telephone network와 ISP에서 downstreame된 data와 음성 신호가 CO의 DSLAM을 만나 다시 모아지고 dedicated line을 통해 비교적 빠른 속도로 전송된 data는 스플리터를 만나서 이 때 들어오는 데이터와 음성 신호를 분리하고 데이터를 PC로 보내준다.

보통 사람들이 업로드보단 다운로드를 많이해서 downstream의 전송률이 높도록 설계되어있다. upstream과 downstream의 전송률이 달라 asymmetric이다.

dedicated link는 데이터의 동시 전송이 가능한 형태이며, 데이터가 동시에 전송되어도 서로 충돌하지 않는다. 가성에서 사용하는 DSL line은 dedicated link를 사용한다. 하지만 shared link는 동시에 데이터를 보내면 서로 충돌이 발생하기 떄문에 전송할 수 없다. 오직 하나의 data packet만을 link를 통해 전송할 수 있다. cable network인 HFC access link에서 shared link를 사용한다.

cable network

Cable network는 DSL과는 다르게 음성이 아니라 TV 데이터가 보내진다. 비트들은 파형의 형태로 날라가고 높은 주파수와 낮은 주파수를 섞어 보내서 수신하는 쪽에서 분리가 가능하다. 이것을 frequency division multiplexing(주파수 분할 다중화)이라고 한다. 그래서 텔레비전, 인터넷, 전화 등의 신호들을 섞어서 보낼 수 있는 것이다. 위 그림에서 Channel은 텔레비전의 채널과 같다고 생각하면 된다. 각각의 채널은 주파수가 다 다르며 위의 그림처럼 1번 ~ 9번 까지 비디오, 데이터 등 다른 주파수들을 섞어서 보내는 것을 볼 수 있다.

Hybrid Fiber Coax(HFC)

각 집들은 cable headend로 가는 access network를 공유한다. DSL과는 다르게 dedicated access가 아니고 shared access를 한다. 그리고 cable은 fiber cable과 coaxial cable이 있다. fiber는 bandwidth가 높아 수백개의 가정집을 연결할 경우에 사용하고 fiber에서 각 가정집으로 연결되는 케이블은 bandwidth가 비교적 낮은 coaxial cable을 사용한다. downstream의 전송률은 30Mbps까지, upstream은 2Mbps까지이며 upstream과 downstream의 전송률이 달라 asymmetric하다고 한다.

이 방식에서 가정은 동네 케이블 회사로 부터 인터넷 접속 서비스를 받는다. 수백 가구로부터 흘러오는 데이터를 교환시키는 link는 shared link이며, 물리적으로는 coaxial cable(동축 케이블)이 데이터를 동네에서부터 개별 가정까지 연결해주는 역할을 한다. cable headend의 CMTS는 가정의 케이블 모델에서부터 온 아날로그 신호를 다시 디지털 포맷으로 변환하는 역할을 하며, 이것은 DSL 네트워크의 DSLAM과 유사한 기능을 제공하는 셈이다. 가정의 케이블 모뎀은 HFC 네트워크를 다운스트림과 업스트림, 2개의 채널로 나누는 역할을 한다. HFC는 2가지 성격을 띈다.

1) HFC란 hybria fiber coax를 의미하는 데, 여기서 fiber(광)은 가정에서 동네까지를 연결하는 physical media이고, coax는 동네에서 집까지를 연결하는, downstream에 이용되는 physical media이다. 동네란 CMTS가 위치한, 동네 케이블 회사를 말한다. 2) 이 네트워크도 asymmetric, 비대칭 접속을 채택한다. downstream 전송속도를 더 빠르게, upstream 전송속도를 더 느리게 두어 bandwidth에 차이를 준다.

<주파수 대역> upstream: 5MHz ~ 42MHz downstream: 54 MHz ~ 750 MHz  - 54 MHz ~ 500 MHz : 아날로그(케이블TV) 방송  - 500 MHz ~ 552 MHz : 인터넷 대역  - 552 MHz ~ 750 MHz : 디지털TV 등 부가서비스 대역

home network

과거에는 DSL이었지만 현재는 cable이다. firewall(방화벽): 보안에 관련된 기능, 비정상적인 것을 걸러냄 NAT: IP주소를 할당받아 사용하게 됨. 현재 IP주소가 부족해서 집 안에서는 임의의 IP주소를 할당해 안에서만 쓰게 한다.(무선의 최대 전송률은 54Mbps, 유선은 최대 1Gbps이다.)

Enterprise access networks(Ethernet)

이더넷은 컴퓨터 네트워크 기술의 하나로, 일반적으로 LAN, MAN 및 WAN에서 가장 많이 활용되는 기술 규격이다. 예시로 학교 PC를 보면 유선으로 꼽혀져 있는데 이것이 이더넷 케이블이다. 학교 내에 Ethernet switch로 다 연결되어 있는 것이다. 초창기엔 10Mbps에서 시작했으나 10Gbps까지 성장했다. 원래는 Enterprise(기업)에서만 쓰였으나 지금은 속도가 잘나와서 국가기관망을 이더넷으로 바꾸었다.

Wireless access networks

< Wireless LANs > 무선 랜은 쉽게 말해서 Wifi이다. 비교적 근거리에서 사용가능하다.

< wide-area wireless access > 기지국을 통해서 서비스하는 cellular(무선 전화) 네트워크이다. 과거에는 음성 중심이었지만 지금은 스마트폰의 증가로 인터넷 영역으로 편입되었다. 비교적 먼거리에서 사용이 가능하다.

네트워크 코어(Network core)

네트워크 코어는 전체 네트워크 시스템의 중앙에 위치하여 데이터를 전송하는 핵심적인 역할을 한다. 우리가 통신을 할 때 end system과 end system이 연결되어야 하는데 이 연결을 제공해 주는 것이 Network core이다. 네트워크 코어의 구조는 수많은 라우터들이 그물처럼 얽혀있는 구조(Mesh of interconnected routers)라고 보면 된다. 네트워크 코어에서 패킷을 교환하는 것을 Packet switching이라고 한다. 네트워크 코어에서는 라우터들은 상호 연결되어 있어서 end system간의 데이터 교환을 돕는다. internet protocol stack의 application layer에서 생성되는 message는 호스트들에 의해 여러 개의 패킷으로 쪼개진다. (참고로, 데이터들이 방문하는 네트워크상의 모든 장치들은 각각의 internet protocol stack을 가지고 있다.) 호스트에 의해 쪼개진 패킷들은 network core에 위치한 router들을 거쳐 receiver(end system)으로 전송된다.

네트워크 코어의 라우터의 역할

• Forwarding
• Routing

Routing

데이터를 송신하는 호스트는 패킷을 라우터로 보낼 때, 각 패킷마다 헤더(header)에 목적지 end system의 정보를 포함시킨다. 따라서 헤더를 가진 packet을 통해, 라우터는 source - destination 루트(이 패킷이 어느 경로로 가야하는지)를 결정한다.

Forwarding

패킷이 어느 경로로 가야하는지를 알아내면 link를 통해서 패킷을 그 곳으로 보내주는 역할을 한다. packet header로 이동할 라우터를 찾으면, 그 라우터에 들어온 data이 output link를 결정하는 테이블이 있는 것이다. 이 table이 패킷의 다음 링크를 결정한다. 이 때 각 패킷은 링크의 최대 전송률 속도로 전송된다. 패킷이 어디로 갈지 판단하는 과정. forwarding table을 만드는 과정이며 routing 알고리즘으로 판단한다. 즉, 패킷은 링크의 최대 전송속도와 같은 속도로 전송된다는 의미이다.

link와 router에서 데이터가 이동하는 방식에는 두가지가 있다. packet switching과 circuit switching이다.

Packet switching(패킷 교환 방식 (store-and-forward))

switching이란 어디로 갈 지 길을 바꿔주는 역할을 하는 것을 말하고 packet switching은 store-and-forward(저장 후 전달)방식을 사용한다. 저장 후 전달하는 방식은 패킷의 첫 비트가 라우터로 도착하고 next link로 전송되기 전에, 한 패킷의 모든(entire) 비트가 라우터에 도착해야한다는 개념이다. 그림으로 이해해보자 패킷 교환 방식으로 source에서 destination까지 패킷이 전달된다고 가정해보자. 각 링크는 초당 R bps의 속도로 패킷을 전송하고, 각 패킷은 L bit이다. 한 패킷의 모든 bit가 라우터에 다 도착할 때 까지, 이미 도착해 있는 packet 1 의 일부 비트들은 다음 링크로 출발하지 못하고 기다려 주어야 한다. 그러므로 packet 1 이 라우터에 다 도착하여 저장이 완료되면(store), 그 시간은 1L/R초이다. 1L/R 초에서 2L/R 초가 될 동안, 첫번째 패킷은 destination으로 연결된 링크를 타고 전송되고, 소스에서는 두번째 패킷이 라우터를 향해 출발한다. 그렇다면 2L/R 초가 흐르면, packet 1은 destination(end system)에 있고 packet 2는 라우터에 저장이 완료(모든 비트들이 도착)된다. 첫번째 패킷이 destionation에 도착하면 end-end delay가 2L/R (전파 지연은 0이라고 가정) 초가 된다는 뜻인데, 만약 store-and-forward 방식이 아니였더라면, 지연은 발생하지 않으므로 end-end delay는 1L/R초가 된다는 것도 알아두면 좋다. (즉, store-and-forward 방식을 사용해서 지연시간이 1L/R초가 된거다.) 그림처럼 라우터를 사이에 둔 두 링크가 모두 같은 속도라면 좋겠지만, 대부분은 그렇지 않다. 만약, 출력링크로 패킷을 내보내는 속도가 패킷이 라우터로 들어오는 속도보다 느리다면 라우터에는 queue가 생기며, 시간이 흘러 이 큐는 패킷을 받아들일 저장공간이 부족하여 넘치게 될 것이다.

queueing delay : 각 패킷 스위치(라우터)는 여러 개의 link를 가진다. 이 link에 대해, 도착하는 패킷이 전송되어야 할 링크(next link)가 이미 다른 패킷을 전송하는 중이라면 도착하는 패킷들이 대기해야 할 공간인 buffer가 존재한다. 이렇게 도착하는 패킷이 버퍼에서 대기하는 상황을, queueing delay라고 한다. packet loss(drop) : 버퍼의 용량은 한정적이므로, 이 버퍼가 넘치면 방금 도착한 패킷이나 이미 저장되어 있는 패킷은 버려진다.

위의 그림에서 라우터는 데이터릐 목적지 주소를 보고 어디로 보내야 할지를 판단해야한다. 판단해서 보내는 기능을 Forwarding이라고 한다. 근데 라우터는 뭘 보고 어디로 보내야 할지를 판단할까?? 바로 local forwarding table을 보고 판단을 한다. 이 local forwarding table은 라우터끼리 만들어야한다. 데이터가 발생하기 전에 라우터들끼리 미리 정보를 주고받는다. 그래서 라우터들끼리 누가 존재하고 누가 연결되어 있고 어디로 보내는게 가장 합리적인지를 미리 결정(routing algorithm)한다. 그리고 이것을 forwarding table로 만든다. 이후 패킷이 들어오면 forwarding table에 근거하여 내보내는(Forwarding) 일을 진행할 수 있다.

<정리>

1. 라우터에 들어오는 패킷의 header에는 목적지 주소가 있다.
2. 이 주소에 대한 경로 정보를 미리 정하는 routing algorithm에 의해 각 라우터에 local forwarding table이 만들어진다.
3. 이후 라우터에 패킷이 왔을 때, 패킷의 목적지 주소와 table의 header value를 보고 해당하는 output link로 보낸다.

Forwarding : 패킷이 왔을 때 실제 전달하는 기능 Routing : 경로를 만들기 위해서 라우터들끼리 협력하는 것

Circuit switching (회선 교환 방식)

Circuit switching은 전화를 위해 개발되었다. Circuit switching은 end system간의 통신을 위해 경로 상 필요한 자원인 link를 독점적으로 예약(reserve)해놓고 사용한다. 이 방식은 리소스를 할당해놓는다는 개념으로(dedicated resources) 데이터를 언제든지 보낼 수 있다는 의미이며 보장(guaranteed)된 일정 전송률로 데이터를 보내는 것이 가능하다는 뜻이다. 하지만 예약한 링크로 데이터를 보내지 않고 있을 때 다른 데이터가 이 링크를 사용할 수 없다는 단점이 있다. packet switching은 circuit switching과 다르게 on-damand방식을 사용한다. 다른 데이터가 링크를 사용하고 싶다면 요청 후 사용이 가능하다. on-demand방식은 링크를 공유한다고 볼 수 있으므로 효율적이지만 delay가 가능하다는 단점을 수반한다.

on-demand방식: 사용자가 있는 곳 까지 찾아가서 무언가를 수행하는 것, 사용자의 요구에 따라 무언가 제공되는 것 (다른 데이터가 링크를 사용하고 싶을 때 "나 링크 쓸래"라고 요청을 하고 사용 가능하다면 사용하도록 하는 방식이다. )

source와 destination 사이의 경로를 정해버리면 queueing delay가 완화되고 중간에서의 손실도 줄어든다. 하지만 사용을 하지 않으면 그냥 낭비가 되기 때문에 전화 통화처럼 계속 데이터를 주고 받을 때 적합하다. 예를 들어 친구랑 통화를 한다면 내 목소리와 친구 목소리가 흘러가는 경로가 미리 준비가 되어있는 것이다.

< circuit-switching의 특징 >

1. 공유하지 않아 독립적이다.
2. 경로를 미리 지정한다.
3. delay와 loss가 완화된다.(라우터에 도착하는 패킷은 미리 지정된 경로로 빠르게 전송이 되기 때문이다.)
4. Bandwidth를 고정하면 사용자의 수가 정해져있어서 resource가 없으면 연결이 안된다.

위의 그림에서 한 링크가 4개의 회선(channel)으로 구성되어 있다. 따라서 각 회선은 (링크의 전송 속도)/4의 속도로 데이터를 전송하며, 이 데이터 전송 속도는 destination까지의 링크가 몇 개 이고, 라우터가 몇 개 있는지와는 상관이 없다. 위의 그림처럼 여러 개의 channel이 존재할 수 있는 데, 링크 내에서 channel을 나누는 기준은 2가지가 있다.

< 1. FDM >

식은 channel을 주파수 대역 별로 나누는 방식이다. 즉, 링크의 주파수 스펙트럼을 공유하는 형태이며, 여기서 제공되는 주파수 대역(색깔 별)은 고정 제공된다. 이 주파수 대역 각각의 대역 폭을 bandwidth라고 하며 이는 전송 속도와 크게 관련이 있다.

**< 2. TDM > ** channel을 시간대별로 나누는 방식이다. 그림 속에 있는 그래프를 색깔 별로 구분지어 보자. 4가지의 색이 시간(time)이 지남에 따라 반복되어 나타나고 있다. 이렇게 각각의 색으로 나눠놓은 구간은 모두 1개의 slot(슬롯)이라고 한다. 그렇다면, 이 그래프는 4가지 슬롯이 시간이 지남에 따라 반복되고 있다는 뜻인데, 여기서 언급되는 이 4개의 슬롯을 합한 구간을 frame(프레임)이라고 한다. 즉, 한 프레임은 4개의 슬롯으로 구성되어 있는 것이다. 이 그래프는 위의 circuit switching을 설명할 때 사용한 그림과 상응하는데, 그림 속 link가 4개의 channel로 이루어져 있기 때문에 여기서 한 프레임이 4개의 슬롯으로 구성된 모습을 띄는 것이다. 하나의 시간 slot은 reserve가 끝날 때 까지 고정된다. 또, 하나의 링크 설정 시 모든 프레임마다 하나의 slot이 할당되는 개념인데, 한 패킷은 할당된 슬롯(1개)만 사용할 수 있고 다른 slot에 패킷을 보낼 수 있는 시간대가 생긴다 하더라도 새로 생성된 시간대에 패킷을 보낼 수 없다.

※ 전화 통화를 할 때 Circuit-switching 방식을 사용하는데 이를 사용할 떄 왼쪽처럼 나 또는 상대방이 계속 이야기를 한다면 Circuit-switching을 좋게 활용하는 것이지만 오른쪽처럼 내가 이야기하고 쫌 있다가 상대방이 이야기하는 식으로 쓴다면 자원이 낭비되는 것이다.(회색부분이 낭비되는 자원)

(정리) Packet-switching vs Circuit-switching

< Circuit-switching의 장정 >

Circuit-switching는 경로를 지정하여 일정한 전송률을 보장받는다. 그래서 전화통화 같은 품질보장이 되어야 하고 계속해서 데이터를 주고받아야 하는 서비스에선, 가변적인 Packet-switching보다 일정한 Circuit-switching를 이용하는 것이 좋다.

1. queueing delay가 완화된다.

   Packet-switching의 queueing delay는 예측하기 어렵고 매우 가변적이기 때문에 다른 delay보다 대비하기 어렵다. 심지어 queue가 넘치게 되면 loss도 발생한다. 그러나 source와 destination의 경로를 정해버리면 바로바로 보낼 수 있기에 queueing delay가 상당히 완화된다. 품질도 보장될 뿐만 아니라 빠르게 데이터를 주고 받을 수 있다.

2. 장시간 긴 데이터를 보낼 때 더 낫다.

   Packet-switching는 여러 sources에서 데이터가 패킷으로 쪼개져 날라가기 때문에, 장시간 긴 데이터를 보낸다면 많은 패킷을 보내므로, 데이터 전송이 지연되거나 전송을 완전히 보장받을 수 없다(loss가 발생할 수도 있음). Circuit-switch는 자원을 독점하여 사용하기 때문에 패킷보다 신뢰있는 전송을 보장받을 수 있다.

3. 제한된 시간에 빠르게 보낼 때 더 낫다.

   패킷같은 일정한 전송을 보장받지 못하는 상황에서, 시간을 제한한다면 신뢰있는 전송을 보장받지 못한다.

   4. 독립적이다.

   Circuit-switch는 다른 사용자와 공유하지 않아 독립적이다. (이것이 곧 Circuit-switch의 장점이자 단점이다.)

< Packet-switching의 장정 >

Circuit-switching는 계속해서 데이터를 주고받아야 하는데, 데이터를 주고받지 못하는 경우가 생긴다면 이것은 낭비이다. Packet-switching는 이러한 낭비를 줄여준다. Packet-switchind은 주고받는 데이터를 패킷단위로 자르고 그 패킷들을 섞어서 보냄으로써 데이터가 전달되는 효율적인 길을 찾아 전송하는 방식이다.

1. link의 낭비가 줄어든다.

   보낼 패킷을 다른 사용자들의 데이터들과 섞여서 공유하고 있는 link를 통해 전송되기 때문에 계속해서 link를 계속해서 활용할 수 있어서, link가 사용되지 않는 경우를 줄일 수 있다.

   2. 더 많은 사용자가 사용 가능하다.

   link의 사용자가 정해져서 그 사용자만 사용하는 것이 아니며 link를 공유해서 사용하므로 Circuit-switching보다 더 많은 사용자가 사용을 할 수 있는 방식이다.

Network of networks

end system은 access network가 필요하고, 이 때 ISP가 access network를 제공한다. 이 ISP끼리도 서로 상호 연결되어 있는데, 이를 Network of network 형태라고 말한다. 세계 각국의 ISP 끼리 모두 직접 연결되어있으면 가장 명확하지만, 거리문제도 있고 비효율적이기 때문에 가운데 global ISP를 두고 각국의 ISP가 global ISP에 연결하는 형태로 많이 활용된다. ISP들도 규모에 따라 티어가 나뉘어져 있으며, 구글같은 대규모 회사의 경우 자체망을 가지고 있는 경우도 존재한다.

ISP structure (network of networks)

end system은 access ISPs에 연결되어 있다. ISP구조에 대해 알아보자.

access ISPs는 수백만 개이다. 이런 access ISP를 어떤 방식으로 연결을 해줄까?

이처럼 직접 연결을 해주면 너무 많은 연결이 생긴다.

그렇다면 global한 하나의 ISP에 연결한다면? 수많은 access ISPs를 global ISP혼자서 처리하기 힘들다.

그러면 이런식으로 ISP를 여러개로 나눈다면? access isp들이 특정 지역의 ISP에 몰리면 그 ISP가 처리하기 힘들다.

그러면 ISP들 끼리 연결 시켜주자.(ISPs) IXP: Internet exchange point. ISP와 ISP 사이의 연결을 담당하는 라우터이다. peering link: 서로 네트워크(ISP)를 연결하여 트래픽을 교환하는 link를 말함

경우에 따라서 regional network(reginal net)를 만드는 경우도 있다.

구글 같은 곳은 자체적으로 유튜크 같은컨텐츠들을 제공해주는 네트워크, Content provider network를 구축했다.

< ISP의 구조 >

ISP의 구조는 위의 그림과 같다. Tier 1ㅇㄴ 국가기관망 또는 대형 통신사(KT,STK 등)이다. (Google은 전세계 네트워크의 상당부분을 차지하고 있디.)

네트워크 구성요소

예시) <사용자가 스마트폰으로 네이버에 접속할 때> -> 스마트폰(네트워크 엣지)으로 와이파이(엑세스 네트워크)를 통해 접속하여 네트워크 코어의 기능을 통해 네이버 서버까지 패킷이 전송되고, 받을 수 있는 것이다.

+ Physical Media

하나의 end system에서 다른 하나의 end system으로 bit 전송(propagation)시 물리 매체(physical media) 상에 전기 신호를 전달하는 방식으로 비트를 전송시킨다. 이 때 비트를 보내는 end system을 transmmitter(송신기), 받는 end system을 receiver(수신기)라고 한다.

** < physical media의 종류 > **

1. guided media (유선 매체)

유선 매체에는 twisted pair(TP), coaxial cable, fiber cable이 있다.

**<twisted pair(꼬임쌍선)> **

1) twisted insult copper wire : 2개의 절연 동선(insult copper wire)이 규칙적인 형태로 배열되어 있는 모양이다. 선들이 꼬여 있으므로 이웃하는 쌍들 간의 전기 간섭이 줄어든다. 2) undirection(한방향) : 전기 신호를 보내는 데 쓰는 선과 받는 데에 쓰는 선이 다르다.기서 언급하는 copper wire는 인터넷 연결에 쓰이는 physical media이다. 3) baseband 통신을 한다. 4) 다른 주파수를 쓰기 위한 주파수 변조를 하지 않는다

** <coaxial cable(동축케이블)> **

1) HFC나 FTTH 에 사용된다. 2) 양방향통신(bidirectional)을 한다. 하나의 케이블로 전기 신호를 주고 받으며, 여러 end system들을 케이블에 직접 연결되어 있는 형태이다. 3) broadband 통신 (multiple channels): 다른 주파수를 쓰기 위해 서로 다른 주파수 대역들 사이에서 변조를 하는 방식이다.

<fiber optic cable(광섬유)>

1) 주로 해저 케이블에 사용된다. 2) 초당 전송할 수 있는 비트(비트율)가 엄청나며 error rate가 낮아, 효율이 좋다. 참고로, 전화선은 error rate가 높다. 3) repeater들이 서로 떨어져 있기 때문에 electromagnetic noise(전자기성 간섭) 에 영향을 받지 않으며 신호 감쇠 현상이 매우 적다.

2. unguided media (무선 매체)

unguided media는 주변 환경 영향을 많이 받으며, 신호 전송에 있어서 감쇄 현상(distortion)이 발생할 수 있다. 이 때에는 디지털에서 신호를 멀리 보내기 위한 도구인 repeater(중계기)를 사용하여 신호를 증폭시켜 멀리 보낸다. 무선 매체의 예로는 radio가 있다.

** < radio >**

1) physical 'wire'가 필요 없다. 무선 매체이기 때문에 물리적인 ' 선 ' 자체는 필요없지만, 주변 환경의 영향을 많이 받는다 2) 여기서 말하는 주변 환경은 전기 신호 bit들의 경로 손실, 섀도 페이딩, 간섭 등을 결정한다. 섀도 페이딩: 신호가 먼 거리를 지나가거나 방해되는 물질을 통과하면서 신호 강도가 약해지는 현상이다. 간섭: 다른 라디오 채널이나 전자기 신호 때문에 발생하는 현상이다. 3) bidirectional, 양방향 통신을 한다.

Computer Architecture

• 컴퓨터 구조 기초
• 컴퓨터의 구성
• CPU 작동원리
• 캐시 메모리

Computer Architecture

컴퓨터 구조 기초

컴퓨터는 입력, 연산, 제어, 기억, 출력 5가지 기능을 구현하기 위해 여러부품으로 구성되어 있다. 위의 사진은 컴퓨터의 추상 계층을 나타내는 사진이다.

하드웨어

컴퓨터 하드웨어는 케이스 중앙 처리 장치(CPU), 모니터, 자판, 컴퓨터 기억 장치, 그래픽 카드, 사운드 카드, 메인보드와 같은 컴퓨터의 물리적 부품을 의미한다.

중앙 처리 장치(CPU(Central Processing Unit))

CPU는 컴퓨터 시스템을 통제하고 프로그램의 연산을 실행 및 처리하는 가장 핵심적인 컴퓨터의 제어 장치를 말하거나 그 기능을 하는 칩을 말한다. CPU는 외부에서 정보를 입력받고 그 정보를 기억하고 컴퓨터 프로그램의 명령어를 해석하여 연산하고, 외부로 출력하는 역할을 한다. 즉 CPU는 컴퓨터 부품과 정보를 교환하면서 컴퓨터 시스템 전체를 제어한다. 모든 컴퓨터의 작동과정이 CPU의 제어를 받아서 컴퓨터의 두뇌라고 부른다.

기억 장치

기억 장치는 전자회로에서 데이터나 상태 명령어 등을 기록하는 장치를 말하며, 흔히 메모리라고 한다. 컴퓨터에서 널리 사용되며, CPU가 계산을 담당하고 메모리가 기억을 담당한다. 쉽게 설명하면 CPU는 일꾼이고 메모리는 작업장이며 보조기억장치는 창고라고 할 수 있다.

CPU에 가까운 순서대로 레지스터(CPU) -캐시 메모리 - 주기억 장치 - 캐시 메모리 - 보조 기억장치로 나눌 수 있다. 일반적으로 용량이 작을수록 동작속도가 빠르며, 용량이 클수록 동작속도가 느리다.

펌웨어(firnware)

펌웨어는 툭정 하드웨어 장치에 포함된 소프트웨어로 소프트웨어를 읽어 실행하거나, 수정하는 것도 가능한 장치를 뜻한다. 하드웨어의 제어(low-level control)와 구동을 담당하는 일종의 운영체제이다. 펌웨어는 ROM이나 PROM에 저장되며, 하드웨어보다는 교환하기가 쉽지만, 소프트웨어보다는 어렵다.

소프트웨어(software)

소프트웨어는 컴퓨터에게 동작 방법을 지시하는 명령어 집합의 모임이다. 프로그램 소프트웨어는 컴퓨터 하드웨어에 직접 명령어를 주거나 다른 소프트웨어에 입력을 제공함으로써, 명령어의 기능을 수행한다.

컴퓨터의 구성

하드웨어

• 중앙처리장치(CPU)
• 기억장치: RAM, HDD
• 입출력 장치: 마우스, 프린터

소프트웨어

• 시스템 소프트웨어: 운영체제, 컴파일러
• 응용 소프트웨어: 워드프로세서, 스프레드시트

시스템 버스

하드웨어 구성 요소를 물리적으로 연결하는 선

각 구성요소가 다른 구성요소로 데이터를 보낼 수 있도록 통로가 되어줌

용도에 따라 데이터 버스, 주소 버스, 제어 버스로 나누어짐

데이터 버스

중앙처리장치와 기타 장치 사이에서 데이터를 전달하는 통로

기억장치와 입출력장치의 명령어와 데이터를 중앙처리장치로 보내거나, 중앙처리장치의 연산 결과를 기억장치와 입출력장치로 보내는 '양방향' 버스임

주소 버스

데이터를 정확히 실어나르기 위해서는 기억장치 '주소'를 정해주어야 함.

주소버스는 중앙처리장치가 주기억장치나 입출력장치로 기억장치 주소를 전달하는 통로이기 때문에 '단방향' 버스임

제어 버스

주소 버스와 데이터 버스는 모든 장치에 공유되기 때문에 이를 제어할 수단이 필요함

제어 버스는 중앙처리장치가 기억장치나 입출력장치에 제어 신호를 전달하는 통로임

제어 신호 종류 : 기억장치 읽기 및 쓰기, 버스 요청 및 승인, 인터럽트 요청 및 승인, 클락, 리셋 등

제어 버스는 읽기 동작과 쓰기 동작을 모두 수행하기 때문에 '양방향' 버스임

컴퓨터는 기본적으로 읽고 처리한 뒤 저장하는 과정으로 이루어짐

(READ → PROCESS → WRITE)

이 과정을 진행하면서 끊임없이 주기억장치(RAM)과 소통한다. 이때 운영체제가 64bit라면, CPU는 RAM으로부터 데이터를 한번에 64비트씩 읽어온다.

CPU 작동원리

CPU는 컴퓨터에서 가장 핵심적인 역할을 수행하는 부분. '인간의 두뇌'에 해당

크게 연산장치, 제어장치, 레지스터 3가지로 구성됨

연산 장치

산술연산과 논리연산 수행 (따라서 산술논리연산장치라고도 불림)

연산에 필요한 데이터를 레지스터에서 가져오고, 연산 결과를 다시 레지스터로 보냄

제어 장치

명령어를 순서대로 실행할 수 있도록 제어하는 장치

주기억장치에서 프로그램 명령어를 꺼내 해독하고, 그 결과에 따라 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력장치로 보냄

또한 이들 장치가 보낸 신호를 받아, 다음에 수행할 동작을 결정함

레지스터

고속 기억장치임

명령어 주소, 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장

용도에 따라 범용 레지스터와 특수목적 레지스터로 구분됨

중앙처리장치 종류에 따라 사용할 수 있는 레지스터 개수와 크기가 다름

범용 레지스터 : 연산에 필요한 데이터나 연산 결과를 임시로 저장 특수목적 레지스터 : 특별한 용도로 사용하는 레지스터

CPU의 동작 과정

1. 주기억장치는 입력장치에서 입력받은 데이터 또는 보조기억장치에 저장된 프로그램 읽어옴
2. CPU는 프로그램을 실행하기 위해 주기억장치에 저장된 프로그램 명령어와 데이터를 읽어와 처리하고 결과를 다시 주기억장치에 저장
3. 주기억장치는 처리 결과를 보조기억장치에 저장하거나 출력장치로 보냄
4. 제어장치는 1~3 과정에서 명령어가 순서대로 실행되도록 각 장치를 제어

캐시 메모리

속도가 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리를 말한다.

CPU가 주기억장치에서 저장된 데이터를 읽어올 때, 자주 사용하는 데이터를 캐시 메모리에 저장한 뒤, 다음에 이용할 때 주기억장치가 아닌 캐시 메모리에서 먼저 가져오면서 속도를 향상시킨다.

속도라는 장점을 얻지만, 용량이 적기도 하고 비용이 비싼 점이 있다.

CPU에는 이러한 캐시 메모리가 2~3개 정도 사용된다. (L1, L2, L3 캐시 메모리라고 부른다)

속도와 크기에 따라 분류한 것으로, 일반적으로 L1 캐시부터 먼저 사용된다. (CPU에서 가장 빠르게 접근하고, 여기서 데이터를 찾지 못하면 L2로 감)

듀얼 코어 프로세서의 캐시 메모리 : 각 코어마다 독립된 L1 캐시 메모리를 가지고, 두 코어가 공유하는 L2 캐시 메모리가 내장됨

만약 L1 캐시가 128kb면, 64/64로 나누어 64kb에 명령어를 처리하기 직전의 명령어를 임시 저장하고, 나머지 64kb에는 실행 후 명령어를 임시저장한다. (명령어 세트로 구성, I-Cache - D-Cache)

L1 : CPU 내부에 존재 L2 : CPU와 RAM 사이에 존재 L3 : 보통 메인보드에 존재한다고 함

캐시 메모리 작동 원리

시간 지역성

for나 while 같은 반복문에 사용하는 조건 변수처럼 한번 참조된 데이터는 잠시후 또 참조될 가능성이 높음

공간 지역성

A[0], A[1]과 같은 연속 접근 시, 참조된 데이터 근처에 있는 데이터가 잠시후 또 사용될 가능성이 높음

이처럼 참조 지역성의 원리가 존재한다.

캐시에 데이터를 저장할 때는, 이러한 참조 지역성(공간)을 최대한 활용하기 위해 해당 데이터뿐만 아니라, 옆 주소의 데이터도 같이 가져와 미래에 쓰일 것을 대비한다.

CPU가 요청한 데이터가 캐시에 있으면 'Cache Hit', 없어서 DRAM에서 가져오면 'Cache Miss'

캐시 미스 경우 3가지

Cold miss

해당 메모리 주소를 처음 불러서 나는 미스

Conflict miss

캐시 메모리에 A와 B 데이터를 저장해야 하는데, A와 B가 같은 캐시 메모리 주소에 할당되어 있어서 나는 미스 (direct mapped cache에서 많이 발생)

항상 핸드폰과 열쇠를 오른쪽 주머니에 넣고 다니는데, 잠깐 친구가 준 물건을 받느라 손에 들고 있던 핸드폰을 가방에 넣었음. 그 이후 핸드폰을 찾으려 오른쪽 주머니에서 찾는데 없는 상황

Capacity miss

캐시 메모리의 공간이 부족해서 나는 미스 (Conflict는 주소 할당 문제, Capacity는 공간 문제)

캐시 크기를 키워서 문제를 해결하려하면, 캐시 접근속도가 느려지고 파워를 많이 먹는 단점이 생김

Java

• 컴파일 과정
• Java Virtual Machine
• Call By Value / Call By Reference
• Thread
• Casting
• Auto Boxing / Auto Unboxing

JAVA

컴파일 과정

컴파일

인간이 이해하기 쉬운 언어를 기계어로 변역하는 과정

컴파일러

컴파일을 하는 프로그램

바이트 코드

컴퓨터가 이해할 수 있는 0과 1로 이루어진 코드

프로그래밍 언어 ---------- (컴파일러) ---------- 바이트 코드

이 바이트 코드는 운영체제마다 다르기 때문에 컴파일러를 통해 만들어진 바이트 코드를 윈도우, 맥, 리눅스에서 실행시켰을 때 다른 결과가 나올 수 있게 된다.

예를 들어 C언어는 윈도우 C언어 컴파일러, 맥 C언어 컴파일러, 리눅스 C언어 컴파일러가 각각 있어서 이 컴파일러마다 다른 0과 1을 만들어내게 되고 해당 운영체제에 서로 다르게 만들어진 바이트 코드를 전달해 주면 C언어 프로그래밍 언어로 만든 같은 내용이 출력이 되는 식이다.

하지만 자바는 자바 컴파일러 하나가 있고 자바 컴파일러 하나로부터 생성된 0과 1의 바이트 코드가 하나있으며 이 바이트 코드가 윈도우, 맥, 리눅스에 바로 가는 것이 아니라 윈도우의 JVM, 맥의 JVM, 리눅스의 JVM에 가는 것이다.

JVM은 바이트코드와 운영체제 사이에서 둘을 호환시켜주는 역할을 한다. JVM은 운영체제마다 각각있으며 JAVA를 설치하면 한 번에 같이 설치가 되는 식이다.

정리하면 C언어는 컴파일러가 여러 개 있고 컴파일 된 결과물(바이트코드)이 여러개지만 자바는 컴파일러가 하나고 컴파일된 결과물(버이트코드)이 동일하며 이 결과물을 JVM이 각각의 운영체제에게 번역을 해주는 것이다.

그래서 자바는 한 번만 결과물을 만들어 놓으면 어떤 운영체제에서든지 똑같은 결과가 나온다는 장점이있다.

JDK > JRE > JVM JDK에는 JRE가 포함되어 있고 JRE에는 JVM이 포함되어 있는 관계이다. 즉, JDK를 설치하면 JRE도 설치되고, JVM도 설치가 되는 것이다.

Java Virtual Machine

JVM

JVM (Java Virtual Machine)

OS 별로 존재한다. 바이너리 코드를 읽고 검증하고 실행한다. 컴파일 한 결과물을 실행시켜주는 역할

JRE

JRE (Java Runtime Environment, 자바 실행 환경)

JRE = JVM + 자바 프로그램 실행에 필요한 라이브러리 파일들 JVM의 실행환경을 구현

JDK

JDK (Java Develrpment Kit, 자바 개발 도구)

JDK = JRE + 개발을 위한 도구 컴파일러, 디버그 도구 등이 포함 자바의 버전 = JDK의 버전 (JDK는 여러 종류가 있으며 기능 자체는 모두 동일하나 성능과 비용에 약간의 차이가 있을 수 있다.) 자바의 버전 중에는 LTS(Long Time Support)라는 버전이 있는데 이 버전은 오래 지원하는 버전을 뜻한다.

Call By Value / Call By Reference

Call By Value(값에 의한 호출)

함수가 호출될 때, 메모리 공간 안에서는 함수를 위한 별도의 임시 공간이 생성된다. (c++의 경우 stack frame) 함수가 종료되면 해당 공간은 사라진다. 스택 프레임(Stack Frame) : 함수 호출시 할당되는 메모리 블록(지역변수의 선언으로 인해 할당되는 메모리 블록) call-by-value 값에 의한 호출방식은 함수 호출시 전달되는 변수의 값을 복사하여 함수의 인자로 전달한다. 복사된 인자는 함수 안에서 지역적으로 사용되는 local value의 특성을 가진다. 따라서 함수 안에서 인자의 값이 변경되어도, 외부의 변수의 값은 변경되지 않는다. Java의 경우 함수에 전달되는 인자의 데이터 타입에 따라서 (원시자료형 / 참조자료형) 함수 호출 방식이 달라진다. 원시 자료형 (primitive type) : call-by-value 로 동작 (int, short, long, float, double, char, boolean ) 참조 자료형 (reference type): call-by-reference 로 동작 (Array, Class Instance)

Call By Reference(참조에 의한 호출)

함수가 호출될 때, 메모리 공간 안에서는 함수를 위한 별도의 임시 공간이 생성된다. (예: stack frame) 함수가 종료되면 해당 공간은 사라진다. call-by-reference 참조에 의한 호출방식은 함수 호출시 인자로 전달되는 변수의 레퍼런스를 전달한다. (해당 변수를 가르킨다.) 따라서 함수 안에서 인자의 값이 변경되면, 아규먼트로 전달된 객체의 값도 함께 변경된다.

Thread

• 프로세스 내에서 실제 작업을 수행하는 것을 쓰레드라고 한다.
• 모든 프로세스는 최소한 하나의 쓰레드를 가지고 있다.

프로세스

실행 중인 프로그램, 자원(메모리, CPU 등)과 쓰레드로 구성됨

프로세스 : 쓰레드 = 공장 : 일꾼

싱글 쓰레드 프로세스(일꾼이 한명) = 자원 + 쓰레드 멀티 쓰레드 프로세스(일꾼이 여러명) = 자원 + 쓰레드 + 쓰레드 + 쓰레드 + ..... + 쓰레드

<멀티 쓰레드로 프로그램을 작성하면 좋은 점>

• 한 프로세스안에서 일꾼이 여러명이기 때문에 여러 작업을 나누어서 처리할 수 있어 작업을 보다 효율적으로 처리할 수 있다. (자바는 멀티 쓰레드를 지원한다.)
• 사용자에 대한 응답성이 향상된다.(파일을 보내면서 채팅을 칠 수가 있다.)
• 작업이 분리되어 코드가 간결해진다.

<멀티 쓰레드로 프로그램을 작성하면 안 좋은 점>

• 동기화(synchronization)에 주의해야 한다.
• 교착상태(dead-lock)가 발생하지 않도록 주의해야 한다. (교착상태: 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 완료되지 못하는 상태를 말함)
• 각 쓰레드가 효율적으로 고르게 실행될 수 있게 해야한다. (쓰레드가 여러개가 있어서 어떤 쓰레드는 실행할 기회를 갖지 못해서 작업이 진행이 안될 수가 있다. 이를 기아라고 하며 프로그램을 잘못 짜면 특정 쓰레드는 작업을 실행할 기회를 얻지 못할 수 있어 각 쓰레드가 효율적으로 고르게 실행될 수 있게 작성해야 한다.)

  하나의 새로운 프로세스를 생성하는 것보다 하나의 새로운 쓰레드를 생성하는 것이 더 적은 비용이 든다. 2개의 싱글 쓰레드 프로세스의 비용 > 멀티 쓰레드 프로세스(쓰레드 2개) 1개의 비용

Casting(형변환)

다형성- 하나의 객체가 여러가지 타입을 가질 수 있는 것을 의미한다.

캐스팅은 OOP(객체지향프로그래밍) 에서 매우 중요하다. 왜냐하면 캐스팅은 OOP의 다형성과 관련이 있기 때문이다. 캐스팅의 목적은 데이터를 바꾸는 것이 주목적이 아닌, 코드를 적는 프로그래머가 이미 데이터 정보에 대해 이해한 가정하에, OOP의 다형성 측면에서 사용한다.기본 데이터형에서의 캐스팅은 원칙적으로 데이터손실을 막고자 한다.

자료형이 정해진 변수에 값을 넣을때는 변수가 원하는 정보를 하나도 빠짐 없이 다 넣어줘야 성립한다. (즉 변수의 데이터 타입 >= 실제 데이터의 타입)

예시를 통해 알아보자.

int a = 1.0 // 불가능 (변수의 데이터 타입은 int지만 1.0은 double이므로) int a = (int) 1.0 // 가능 (실제 데이터 앞에 (데이터 자료형)을 붙여줘 캐스팅이 되어 1.0대신 1이 들어가서 int a = 1과 동일한 코드가 된다.) double b = 1 // 가능 (변수의 데이터 타입이 더 크므로)

<업캐스팅>

Parent와 Child 클래스가 있으며 Child클래스가 Parent 클래스를 상속 받는다고 가정해보자.

Parent parent = new Parent(); // 문제 없음 Child child = new Child(); // 문제 없음

Parent parent = new Child(); // Child클래스는 부모 클래스를 상속 받기 때문에 Parent 자료형 데이터를 모두 가지고 있다. (Parent <= Child) 이를 업캐스팅이라고 한다.

<다운캐스팅>

다운캐스팅을 알아보기 전에 다음 코드가 에러인 이유를 살펴보고 가자.

Child child = (Child) new Parent();

위의 코드는 컴파일에러가 아닌 런타임에러이다. 컴파일러에게 프로그래머가 현변환을 함으로써, 일단 데이터를 맞게 넣어준 것처럼 보여줘서 컴파일러가 문법이 맞다고 생각하게 만들어 컴파일에러가 나지 않는 것이다. 하지만 프로그램이 실제로 작동할 때 Parent의 데이터 타입을 Child로 바꾸지 못한다는 것을 깨닫고 런타임에러가 나며 프로그램이 종료된다. 데이터 타입을 바꾸지 못하는 이유는 Child는 참조형 데이터 타입으로 프로그래머가 작성하는 부분이다. 이 말은 프로그래머마다 다른 Child클래스가 만들어 질 것이다. 이를 JVM은 추리하지 못함로 런타임에러가 나오는 것이다.

int a = (int) 1.0;

위의 코드는 기본형 데이터 타입이므로 기본형 데이터 타입끼리는 추리가 가능하기 때문에 알아서 알맞은 데이터 크개로 변환하여 넣어줄 수 있다. 하지만 참조형 데이터 타입은 그렇지 못해 위의(Child child = (Child) new Parent();)는 런타임에러가 발생하게 된다.

다운 캐스팅은 일반적으로 성립하지 않지만 성립되는 경우가 존재한다. 예시를 통해 알아보자.

Parent parent = new Child(); // 업캐스팅 (Child 데이터 타입이 Parent 데이터 타입보다 크다.) Child child = (Child) parent; // 가능

위의 Child child = (Child) parent가 가능한 이유는 parent는 Parent클래스 형태의 변수지만 Child 객체를 생성하여 그 주소값을 가지고 있는 변수이다. 그래서 다음과 같은 코드가 가능한 것이다.

Auto Boxing / Auto Unboxing

기본 타입 : boolean, char, byte, short, int, long, flaot, double Wrapper 클래스 : Integer, Long, Float, Double, Boolean...

Wrapper클래스를 사용하는 이유는?

1. 기본 데이터 타입을 Object로 변환할 수 있다.

2. java.util패키지의 클래스는 객체만 처리하므로 Wrapper class는 이경우에도 도움이 된다.

3. ArrayList등과 같은 Collection Framework의 데이터 구조는 기본 타입이 아닌 객체만 저장하게 되고, Wrpper class를 사용하여 오토 방식/ 언박싱이 일어난다.

4. 멀티스레딩에서 동기화를 지원하려면 객체가 필요하다.

박싱이란?

기본 타입 데이터를 대응하는 Wrapper클래스로 만드는 동작(int -> Integer)

언박싱이란?

Wrapper 클래스에서 기본 타입으로 변환(Integer -> int)

<주위할 점> 편의성을 위해 오토 박싱과 언박싱이 제공되지만, 내부적으로 추가 연산 작업이 발생하여, 성능이 떨어지게 된다. 따라서 오토 박싱과 언박싱이 일어나지 않도록 동일한 타입 연산이 이루어지도록 구현해야 한다.

//박싱
int a = 10;
Integer b = new Integer(a);

//오토 박싱
int i =10;
Integer num = i;

//언박싱
Integer b = new Integer(10);
int a = b.intValue();

//오토 언박싱
Integer num = new Integer(10);
int i = num;

https://www.acmicpc.net/problem/2864

풀이

이 문제는 입력을 한줄로 받으면서 5를 6으로 바꿔 최댓값을 만들거나 6을 5로 만들어서 최솟값을 만드는 문제인다. String의 replace()메서드를 이용하여 6을 5로 바꿔서 입력을 한 번 받고 5를 6으로 바꿔서 입력을 받아 이 문제를 해결하였다.

코드

package Category.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_2864 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String input = br.readLine();

        input = input.replace("6", "5");

        StringTokenizer st = new StringTokenizer(input);

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        sb.append(a + b).append(" ");

        input = input.replace("5", "6");

        st = new StringTokenizer(input);

        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        sb.append(a + b);
        System.out.print(sb);
    }
}

https://www.acmicpc.net/problem/1213

풀이

이 문제는 가운데를 기준으로 양옆이 같도록 출력하는 문제이다. 규칙을 찾아보면 홀수가 2개 이상나오는 순간 좌우가 대칭이 될수 없다는 것을 알수 있다. 대문자로 입력 받으므로 배열을 효율적으로 사용하기 위해 'A'를 빼줘서 0 ~ 25까지의 배열을 선언하여 사용하지 않는 배열이 없도록 작성하였다. 그리고 담긴 배열을 보면 홀수가 2개이면 대칭이 될 수 없으므로 최대 1값만 홀수이고 나머지는 짝수일 것이다. 그래서 인덱스에 담긴 값을 반으로 나누어서 해당 문자를 StringBuilder를 생성하여 문자를 넣는다.

(ex) A라는 문자가 2번 들어왔다. -> 이를 2로 나누면 1이니 한 번만 StringBuilder를 사용하여 A를 넣는다.(sb.append(A)))

StringBuilder에는 reverse()라는 메서드가 있다. 이를 이용하면 가운데를 기준으로 오른쪽 값을 찾기 위한 코드를 작성할 필요가 없어진다.

StringBuilder sb = new StringBuilder();
sb.append('AB');
System.out.println(sb); // AB
sb.reverse();
System.out.println(sb); // BA

만약 홀수가 존재한다면 입력받은 문자열은 홀수개의 문자로 구성되어 있을 것이다. 그러면 가운데 값이 존재하므로 위의 코드들로는 구현할 수 없게된다. 위의 코드들은 짝수만 커버하는 코드이다.

if (odd == 1) {
            st += (char) (num + 'A');
        }

        st += sb.reverse().toString(); // StringBuilder sb를 문자열로 바꾸려면 toString 메서드를 사용해야한다.
        System.out.println(st);

그래서 미리 왼쪽 문자를 담고 이를 String 변수(st)에 저장한 후에 odd가 1이면 홀수의 인덱스(num)에 'A'를 더하고 char로 형변환을 해줘 원래 입력값으로 받았던 가운데 문자를 추가해준다. 이후 reverse메서드를 문자열 st에 추가해주어 대칭이되는 문자열을 만들고 출력해준다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class q_1213 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();
        int[] arr = new int[26];
        for (int i = 0; i < str.length(); i++) {

            int index = str.charAt(i) - 'A';
            arr[index]++;
        }
        int odd = 0;
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 != 0) {
                odd++;
                num = i;
            }
            if (odd >= 2) {
                System.out.println("I'm Sorry Hansoo");
                return;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i] / 2; j++) {
                sb.append((char)(i+'A'));
            }
        }
        String st = sb.toString();
        if (odd == 1) {
            st += (char) (num + 'A');
        }

        st += sb.reverse().toString();
        System.out.println(st);


    }
}

https://www.acmicpc.net/problem/1049

풀이

이 문제는 M개의 브랜드 줄 중 어느것이 6개 짜리 줄의 가격(all)과 한 줄의 가격(one)이 최소값인지 구하고 가장 최소값인 6개 짜리 줄 가격(all[0])과 가장 최소값의 한개 짜리 줄(one[0]) * 6의 각격 중 어느 것이 저렴한지 구해서 N개의 줄을 사는 최소값을 구하는 그리디 알고리즘 문제이다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class q_1049 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] all = new int[M]; 
        int[] one = new int[M];

        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine(), " ");

            all[i] = Integer.parseInt(st.nextToken());
            one[i] = Integer.parseInt(st.nextToken());
        }

        // 최소값을 구하기 위해서 정렬
        Arrays.sort(all);  
        Arrays.sort(one);

        if (all[0] < one[0] * 6) {
            System.out.println(all[0] * (N / 6) + Math.min(all[0], one[0] * (N % 6)));
        }
        else {
            System.out.println(one[0] * N);
        }
    }
}

https://www.acmicpc.net/problem/2477

풀이

문제에서 육각형의 방향과 길이를 입력받는다. 이 문제를 입력받은 방향을 이용하지 않고 문제를 풀었다. 이용하지 않고 풀 수 있는 이유는 다음과 같다. 6각형이 위의 그림처럼 생겼다고 가정하자. 그림에서 길이가 가장 긴 변은 160이다. 이 변의 양옆으로 50과 20의 길이를 가진 변이 있다. 문제에서 시계 반대 방향으로 값을 입력받는다고 하였으므로 가장 긴 변의 바로 전과 바로 다음으로 입력받는 값은 160이 가로라고 가정해 보면 세로일 것이고 160의 변의 길이를 가지는 값의 앞 변과 뒤 변 중 하나는 세로에서 가장 긴 변일 것이다. 그림에서 세로 변 중 30은 실제 면적을 구하는 데 사용되지 않는다. 이렇게 가장 큰 변을 구하고 그 앞뒤의 변만 확인한다면 30과 같은 실제 면적을 구하는 데 사용되지 않는 변을 고려하지 않아도 된다.

<입력 값을 받은 후에>

1. 가장 큰 변의 길이를 구하고 그 입력 값의 인덱스를 저장해둔다.(maximumNum, 변의 길이는 maximum)
2. 가장 큰 변의 앞 뒤 인덱스 값에 담긴 값을 비교하여 큰 값과 작은 값을 각각 변수에 담는다. (max, min)
3. 값을 담을 때 maximumNum+1번째 인덱스가 큰지 maximumNum-1번째 인덱스가 큰지 확인하여 큰 값이 나온 인덱스를 maxNum 변수에 저장한다.
4. maxNum 기준으로 앞 뒤 값을 비교하여 작은 값을 minimum 변수에 저장한다.(이 때 큰 값은 maximum이다.) 정리: 가장 큰 변의 길이: maximum(가로라고 가정) 가장 큰 변의 길이: max(세로) - maximumNum으로 찾은 값 가장 작은 변의 길이: min(세로) - maximumNum으로 찾은 값 가장 작은 변의 길이: minimum(가로) - maxNum으로 찾은 값

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_2477 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] arr = new int[6];
        int maximum = 0;
        int maximumNum = 0;
        for (int i = 0; i < 6; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int direct = Integer.parseInt(st.nextToken());
            arr[i] = Integer.parseInt(st.nextToken());;

            if (maximum < arr[i]) {

                maximum = arr[i];
                maximumNum = i;
            }
        }
        int maxNum, max, min;
        if (arr[(maximumNum - 1 + 6) % 6] < arr[(maximumNum + 1) % 6]) {
            maxNum = maximumNum + 1;
            max = arr[(maximumNum + 1) % 6];
            min = arr[(maximumNum - 1 + 6) % 6];
        } else {
            maxNum = maximumNum - 1;
            max = arr[(maximumNum - 1 + 6) % 6];
            min = arr[(maximumNum + 1) % 6];
        }
        int minimum = Math.min(arr[(maxNum - 1 + 6) % 6], arr[(maxNum + 1) % 6]);
        System.out.println((max * maximum - (max - min) * (maximum - minimum)) * T);
    }
}

https://www.acmicpc.net/problem/1005

풀이

이 문제는 방향은 있으며 사이클이 없는 그래프 문제이다.(DAG 알고리즘 문제) 그래서 위상 정렬을 사용하여 문제를 해결하였다. 간선이 0인 번호의 빌딩은 먼저 지어져야 하는 빌딩이 없다는 것을 의미하므로 해당 빌딩까지 걸리는 시간은 그 빌딩이 걸리는 시간과 같다.

time[간선이 0인 빌딩의 인덱스] == timeSum[간선이 0인 빌딩의 인덱스]

위상 정렬을 수행하는 알고리즘은 크게 두 가지 스택(Stack)과 큐(Queue) 두 가지가 존재한다. 이 문제는 큐를 이용하여 풀었으며 입력 값으로 주어지는 건물의 순서를 받을 때 아래와 같이 list[x]에 y값을 추가시키고 count배열의 y번째 값을 증가시켜 y번째 빌딩의 간선의 수를 증가시킨다. count배열은 간선의 수를 체크하려고 만들었다. 만약 x번째 빌딩이 간선이 존재하지 않고 list[x].size()도 0이 아니라면 x번째 빌딩이 어떤 빌딩을 지을 때 먼저 지어야 하는 빌딩이라는 것을 의미한다.

for (int p = 0; p < K; p++) {

    st = new StringTokenizer(br.readLine(), " ");
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());

        list[x].add(y);
        count[y]++;
    }

그리고 topologySort()메서드를 만들어서 메서드 안에 큐를 생성하여 간선이 0인 빌딩(인덱스)를 큐에 넣는다.

만약 간선의 수가 0인 빌딩이 없다면 사이클이 있다는 뜻이고 위상 정렬은 시작점이 존재해야 사이클이 생기는 그래프에서는 시작점을 찾을 수 없어 위상 정렬을 사용할 수 없다.

while문으로 큐가 비었는지 확인한 후 비어있지 않으면 큐에서 poll()메서드로 큐에 저장된 첫번째 값을 반환하고 제거한다. poll메서드로 반환한 값을 currentTime에 넣으면 currentTime에는 간선이 0인 빌딩의 인덱스 값이 담기게 된다. 해당 인덱스 빌딩(currentTime)을 먼저 지어야하는 빌딩으로 하는 빌딩의 인덱스들이 list[currentTime]안에 저장되어 있다. nextTime에는 list[currentTime]안에 저장된 값들을 담긴 순으로 받아서 timeSum[currentTime] + time[nextTime]와 timeSum[nextTime] 중 큰 값으로 timeSum[nextTime]값을 바꿔준다. timeSum[nextTime]를 비교하는 이유는 현재 nextTime 값의 간선의 수(count[nextTime])이 1보다 크다면 timeSum[nextTime]값은 처음에는 timeSum[currentTime] + time[nextTime]로 값을 가지겠지만 count[nextTime]--;되어도 count는 0이 안되므로 다시 한번 값이 바뀌게 되므로 count가 1보다 클 경우를 생각하여 다음처럼 비교하도록 코드를 작성하였다.

 for (int i = 0; i < list[currentTime].size(); i++) {
    int nextTime = list[currentTime].get(i);
    timeSum[nextTime] = Math.max(timeSum[currentTime] + time[nextTime], timeSum[nextTime]);
    count[nextTime]--;
    if (count[nextTime] == 0) {
            q.offer(nextTime);
    }

그리고 Math.max로 하는 이유는 문제 예시로도 알 수 있지만 1번 건물을 완성하고 2,3번 건물을 동시에 짓기 시작해도 2,3번의 최대시간(Max)이 끝나기 전까지는 4번 건물을 지을 수 없기 때문에 max로 코드를 작성한 것이다.

이렇게 코드를 작성하면 주어진 건물순서 규칙을 모두 계산하여 각 건물을 짓는 최소 시간을 구할 수 있게 된다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q_1005 {

    static int[] time;
    static int[] timeSum;
    static ArrayList<Integer>[] list;
    static int[] count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());


        for (int i = 0; i < T; i++) {

            st = new StringTokenizer(br.readLine(), " ");

            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            time = new int[N + 1];
            list = new ArrayList[N + 1];
            st = new StringTokenizer(br.readLine(), " ");

            for (int j = 1; j <= N; j++) {
                time[j] = Integer.parseInt(st.nextToken());
                list[j] = new ArrayList<>();
            }

            count = new int[N + 1];

            for (int p = 0; p < K; p++) {

                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                list[x].add(y);
                count[y]++;
            }

            int W = Integer.parseInt(br.readLine());

            timeSum = new int[N + 1];
            topologySort();
            sb.append(timeSum[W]).append("\n");
        }
        System.out.println(sb);


    }


    static void topologySort() {

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < count.length; i++) {

            if (count[i] == 0) {

                timeSum[i] = time[i];
                q.offer(i); // 값을 추가
            }
        }

        while (!q.isEmpty()) {
            int currentTime = q.poll(); 
            for (int i = 0; i < list[currentTime].size(); i++) {

                int nextTime = list[currentTime].get(i);
                timeSum[nextTime] = Math.max(timeSum[currentTime] + time[nextTime], timeSum[nextTime]);
                count[nextTime]--;
                if (count[nextTime] == 0) {
                    q.offer(nextTime);
                }
            }
        }
    }
}

https://www.acmicpc.net/problem/1189

풀이

이 문제는 DFS 방법으로 풀어야한다. 출발 지점이 왼쪽 하단이고 도착 지점이 오른쪽 상단이므로 입력값으로 받는 R, C로 시작점을 (R-1, 0) 도착점을 (0, C-1)로 하여 문제를 풀었다. 모든 배열의 값은 시작점을 제외하고 0으로 시작하고 시작점은 1로 시작하게 하고 해당 위치를 지나가면 그 배열의 인덱스 값을 1로 바꿔준다. DFS를 사용하므로 한 쪽 방향으로 시작하여 입력값으로 T를 받는 배열의 위치를 제외하고 모든 값이 채워질 때까지 재귀적으로 호출한다. 재귀 호출이 끝나면 마지막으로 채워진 배열 위치의 인덱스 값을 0으로 바꿔준다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_1189 {

    static int R, C, K;
    static int[][] map;
    static int[][] visit;

    static int[] Rmove = {1, -1, 0, 0}; // 아래, 위, 오른쪽, 왼쪽 순으로 진행
    static int[] Cmove = {0, 0, 1, -1};
    static int count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int [R][C];
        visit = new int[R][C];

        for (int i = 0; i < R; i++) {

            String s = br.readLine();
            for (int j = 0; j < C; j++) {

                map[i][j] = s.charAt(j);
            }
        }

        visit[R - 1][0] = 1; // 시작지점을 1로 초기화시킴
        moving(R - 1, 0, 1);
        System.out.println(count);

    }

    static void moving(int r, int c, int k) {

        if (k == K) {
            if (r == 0 && c == C - 1) {
                count++;
            }
            return;
        }

        for (int i = 0; i < 4; i++) {

            int Rlocate = r + Rmove[i];
            int Clocate = c + Cmove[i];
            if (Rlocate < 0 || Rlocate >= R || Clocate < 0 || Clocate >= C) {
                continue;
            }
            if (visit[Rlocate][Clocate] == 1 || map[Rlocate][Clocate] == 'T') {
                continue;
            }
            visit[Rlocate][Clocate] = 1;
            moving(Rlocate, Clocate,k+1);
            visit[Rlocate][Clocate] = 0; // 모든 인덱스의 값이 1이 되었거나, k값이 K와 같으면 이 코드가 실행됨
        }
    }
}

응용

문제가 최소거리를 구하는 거라면 Rmove와 Cmove에서 아래와 왼쪽은 사용하지 않아도 됨.

Tree에서 데이터를 가져오는 방법인 Incorder, Preorder, Postorder 구현

코드

package Category;


class Node { // 이진트리의 노드는 data와 왼쪽 오른쪽 2개의 자식노드로 구성

    int data;
    Node left;
    Node right;
}
class Tree { 

    public Node root; 

    public void setRoot(Node node) {
        root = node;
    }

    public Node getRoot() {
        return root;
    }

    public Node makeNode(Node left, int data, Node right) { // 새로운 노드 추가하는 메서드
        Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }

    public void inorder(Node node) {

        if (node != null) { // 새로운 노드를 만들 때 Node타입으로 객체를 생성하고 그 객체의 주소를 참조변수 node에 넣는다. 그러므로 node가 null이라는 것은 만든 노드가 없다는 거를 의미한다. 
                            // 즉 이 코드에서 n1, n2, n3, n4, n5의 참조변수가 inorder의 매개변수로 오지 않으면 다 null이다. 
            inorder(node.left);
            System.out.println(node.data);
            inorder(node.right);
        }
    }

    public void preorder(Node node) {

        if (node != null) {
            System.out.println(node.data);
            preorder(node.left);
            preorder(node.right);
        }
    }

    public void postorder(Node node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.right);
            System.out.println(node.data);
        }
    }
}
public class Test {

    public static void main(String[] args) {

        Tree t = new Tree();
        Node n4 = t.makeNode(null, 4, null);
        Node n5 = t.makeNode(null, 5, null);
        Node n2 = t.makeNode(n4, 2, n5);
        Node n3 = t.makeNode(null, 3, null);
        Node n1 = t.makeNode(n2, 1, n3);
        t.setRoot(n1);
        System.out.println("inorder 결과");
        t.inorder(t.getRoot());
        System.out.println("preorder 결과");
        t.preorder(t.getRoot());
        System.out.println("postorder 결과");
        t.postorder(t.getRoot());
    }
}

밑에 결과가 맞는지 보다 편하게 확인하기 위해 코드에서 생성한 트리를 그림으로 그려보았다.

결과

inorder 결과
5
6
13
10
11
preorder 결과
10
6
5
13
11
postorder 결과
5
13
6
11
10

Tree는 Array, LinkedList, Stack, Queue처럼 일직선 구조가 아니라 부모 자식 관계를 가지는 구조이다. 그래서 Tree는 계층이 있고 그룹이 있다.(계층과 그룹이 있는 이유는 각 노드가 하나 이상의 자식노드를 가지기 때문이다.) 더이상 자식이 없는 마지막 노드를 leaf라고 부른다.

Binary Tree(이진트리)

노드가 하나이상의 자식 노드를 가지면 트리라고 하는데 그 중에 자식노드가 최대 2개까지만 붙는 트리를 이진트리라고 한다. (최대 3개씩 붙는 트리는 Ternary Tree라고 한다.)

Binary Search Tree(이진 검색트리)

다른 조건 없이 노드의 자식노드가 최대 2개씩만 붙어있는 것이 Binary Tree이고 Binary Search Tree는 트리안의 데이터가 root노드 기준으로 왼쪽은 root노드보다 작은 값 오른쪽은 큰 값으로 정렬되어 있는 트리이다. 이진 검색트리는 모든 값들이 노드들을 기준으로 나누어져 있어서 값을 찾을 때 root노드를 기준으로 범위를 줄여가며 찾을 수 있다.

Complete Binary Tree(완전 이진트리)

완전 이진트리는 모든 노드들이 레벨별로 왼쪽부터 채워져 있는 것을 말한다. 트리를 만들면 노드들의 자식노드들이 생기는데 그 자식노드들이 만들어 질 때 왼쪽부터 채워지는 트리를 말한다.

Full Binary Tree

Full Binary Tree는 노드가 자식노드를 하나도 안가지거나 가진다면 2개를 가지는 트리이다.

Perfect Binary Tree

Perfect Binart Tree는 노드들이 각 레벨별로 구성될 수 있는 최대의 노드 수로 이루어진 트리를 말한다.(모든 노드들이 자식노드를 2개가지는 트리) Perfect Binary Tree는 레벨의 수가 N일 때 노드의 개수가 2^N-1개이다.

Tree의 데이터를 가져오는 방법(Binary Tree Traversals)

Tree의 node들을 지정된 순서대로 방문하는 것

• Inorder(Left, Root, Right)
• Preorder(Root, Left, Right)
• Postorder(Left, Right, Root)

각 방법에 대해서 아래의 노드를 예시로 하여 데이터를 가져오는 방법을 알아보자

Inoeder(Left, Root, Right)

Root노드를 시작으로 먼저 왼쪽 leaf노드의 데이터를 가져오고 그 다름 leaf의 부모 노드의 데이터를 가져오고 그 다음 오른쪽 노드를 가져오는 방식으로 데이터를 가져온다. (5 -> 6 -> 13 -> 10 -> 11)

• 트리에 Root노드는 하나이다.

Preorder (Root, Left, Right)

Root노드의 데이터를 먼저 가져오고 그 다음 왼쪽, 오른쪽 순으로 데이터를 가져온다. (10 -> 6 -> 5 -> 13 -> 11)

Postorder(Left, Right, Root)

왼쪽, 오른쪽의 데이터를 먼저 가져오고 다 가져왔으면 Root노드의 데이터를 가져오는 방식 (5 -> 13 -> 6 -> 11 -> 10)

Binary Heaps

heap

heap은 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조이다.

최소 Heap

작은 값이 항상 위에 노드에 있도록 만들어 트리의 root노드에 가장 작은 값이 오도록 하는 트리구조

최대 Heap

큰 값이 항상 위에 노드에 있도록 만들어 트리의 root노드에 가장 큰 값이 오도록 하는 트리구조

최소 힙에 노드 삽입하기

1.새로운 노드를 마지막 레벨에 완전 이진트리를 유지하며 생성한다.(왼쪽부터 노드생성) 2. 부모 노드와 비교를 해서 부모 노드보다 값이 작다면 값을 바꾼다.
3. 2번 과정을 반복한다. 더 이상 비교를 안한다면 새로 추가한 값이 root 노드에 도달하였거나 부모 노드가 새로 추가한 노드값보다 작은 것이다. 시간 복잡도: 최대 O(log n) (한번 비교할 때마다 노드의 수가 절반씩 줄기 때문에)

최소 힙에서 노드 꺼내오기

주로 최소값을 찾을 때 최소 힙을 이용한다. 최소 값을 꺼내오는 것은 root노드를 가져오면 된다. 그런데 root노드를 꺼내온 뒤 root노드에 값을 채워야 하는데 이때는 완전 이진트리의 마지막 레벨의 마지막 노드를 가져와서 root노드에 채운 후에 자식 노드(왼쪽, 오른쪽)들과 비교하여 가장 작은 노드가 위의 노드로 가도록 만들어 최소 힙을 만든다. 이 과정은 자식 노드들이 부모 노드보가 크거나 leaf노드에 도달했을 때 멈춤다. 시간복잡도: 최대 O(log n)

• 객체지향 개념(규칙)들이 추가된 이유

1. 코드의 재사용성을 높이기 위해(코드를 한 번 만들면 이를 다른대서 쉽게 사용할 수 있도록 하기 위해서 사용)
2. 유지보수가 용이해서 소프트웨어가 변경이 되도 적은 노력으로 그 변경에 대응할 수 있어서
3. 코드의 중복을 제거하기 위해

객체지향언어의 핵심적인 특징

• 캡슐화
• 상속
• 추상화
• 다형성

클래스와 객체

클래스의 정의

• 설계도
• 데이터 + 함수
• 사용자 정의 타입(원하는 타입을 직접 만들 수 있다. )

클래스의 용도

• 클래스는 객체를 생성하는데 사용한다.

객체의 정의

• 실제로 존재하는것. 사물 또는 개념

객체의 용도

• 객체가 가지고 있는 기능과 속성에 따라 다르다.

클래스는 설계도이고 객체는 제품이다.

우리 일상생활에서 하드웨어로 구성되어 있는 것(tv, 오디오 등)을 소프트웨어(프로그램)으로 바꾸려고 하드웨어를 분석하고 관찰해보니 "속성"과 "기능"으로 표현이 가능하였다. 그래서 한 사물(객체)는 속성과 기능으로 구현이 가능하며 속성은 변수, 기능은 메서드로 정의하여 한 사물(객체)의 클래스를 만들 수 있다.

객체와 인스턴스

인스턴스 ≒ 객체

객체: 모든 인스턴스를 대표하는 일반적 용어 인스턴스: 특정 클래스로부터 생성된 객체

클래스로 객체(인스턴스)를 만드는 것을 인스턴스화라고 한다. 클래스(설계도)만 만든다고 제품을 사용할 수 없음.(제품을 의미하는 객체를 생성해야만 사용가능)

하나의 소스파일에 클래스 작성

• public 클래스의 이름은 무조건 소스파일의 이름과 같아야한다. 소스파일: A.java , public 클래스: public class A{}

  하나의 소스파일에는 하나의 public 클래스만 존재해야한다. 소스파일과 같은 이름의 클래스안에 main메서드가 존재해야 한다.

<클래스가 여러개일 때> (public 클래스가 없을 때)

• 존재하는 클래스중 main메서드를 가지고 있는 클래스와 소스파일이름이 같으면 문제 없음(클래스 이름과 같은 소스파일이 하나도 없어도 에러는 나지 않지만 실행이 안됨 IDE가 main메서드가 어디있는지 알아야 자동으로 실행이 되는데 소스파일이름을 가지고 판단을 하기 때문에 main메서드를 가지고 있는 클래스 이름이 소스파일이름과 같아야한다.) (소스파일과 같은 이름의 클래스안에 main메서드가 존재해야 한다!)
• 자바는 대소문자를 구별하므로 (소스파일: Hello.java 클래스: class hello{}는 다른거다.)

(public 클래스가 있을 때)

• public 클래스는 무조건 1개만 존재해야하고 public 클래스 이름이 소스파일의 이름과 같기만 하면 문제 없음(public 클래스 내부에 main메서드 존재)

<클래스가 한개일 때>

(public 클래스가 있을 때, 없을 때)

• 클래스 이름이 소스파일과 같아야한다.(클래스 안에 main메서드 존재)

객체의 생성과 사용

객체의 생성

1. 참조변수를 선언
2. 객체를 생성
3. 대입연산자로 참조변수와 객체를 연결

클래스명 변수명;           // 클래스의 객체를 참조하기 위한 참조변수 선언
변수명 = new 클래스명();   //클래스의 객체를 생성한 후(new 클래스명()), 객체의 주소를 참조변수에 저장

(2줄을 1줄로)
클래스명 변수명 = new 클래스명(); (Tv tv = new Tv();)

• 참조변수는 객체를 다루기 위해서 필요하다. 참조변수가 없으면 객체를 다룰 방법이 없다. (ex) 클래스: tv 설계도, 객체: tv, 참조변수: 리모컨 )

객체의 사용

tv.channel =7; // 변수(속성)를 사용하는 방법
tv.channelDown(); // 메서드(기능)을 사용하는 방법 (메서드 호출이라고도 함)

객체를 사용한다는 말은 객체가 가진 멤버를 사용한다는 말이며 멤버는 변수하고 메서드이다.

new 연산자

new 연산자는 객체를 만들고 그 객체의 주소값을 반환한다. (new 연산자로 만들어지는 객체의 주소값은 같을 수 없다. 사용되고 있는 메모리를 피헤서 빈 자리에 객체를 만들기 때문) ex) Tv tv = new Tv(); // (new 연산자가 반환한 주소값이 0x100이라고 가정)tv에는 0x100이 저장이 된다.(대입연산자에 의해) 즉, 참조변수에 생성된 객체의 주소값이 저장된다.(대입연산자로 참조변수와 객체를 연결). 참조변수의 타입과 생성하려는 객체의 타입이 같아야한다.(tv(제품)에 맞는 리모컨(참조변수)를 생성)

Tv tv1 = new Tv(); 
Tv tv2 = new Tv();  
tv1.channel = 7;

tv1가 tv2에는 다른 주소 값이 저장된다. 그러므로 tv1.channel = 7로는 tv1이 가지고 있는 주소값에 해당하는 객체만 값이 변한다.

Tv tv1 = new Tv(); 
Tv tv2 = new Tv();  
tv2 = tv1; // (tv2의 값이 0x200이고 tv1의 값이 0x100이라고 가정하면 이 코드로 인해 tv2의 값이 0x100으로 바뀌게 된다.
그러면 tv2와 연결된 객체(객체주소: 0x200)은 tv2리모컨과 연결이 끊어지게 되고 tv1과 연결된 객체(객체 주소: 0x100)는 리모컨이 2개가 된다.(tv1, tv2)) 
tv2와 연결됬었던 객체(객체주소: 0x200인 객체)는 존재는 하지만 사용할 수 없게 된다.(참조변수(리모컨)가 없기 때문에) 
tv1.channel = 7;  // tv1.channel값도 7이고 tv2.channel값도 7이된다.

<자바는 Garbage Collector가 존재한다.> 사용할 수 없는 메모리는 Garbage Collector가 메모리를 주기적으로 확인하고 있다가 사용할 수 없는 객체를 찾으면 메모리에서 제거시켜 불필요하게 메모리가 낭비되지 않도록한다.

변수는 하나의 값만 저장가능해서 한 객체에 참조변수가 여러개일순 있지만 참조변수 하나가 여러개의 주소를 가질 수는 없다.(참조변수는 하나의 객체와만 연결 가능)

객체 배열

객체 배열 == 참조변수 배열 (참조변수 배열이지만 참조변수들 안에 객체의 주소가 저장됨, 참조변수 여러개를 묶어서 하나의 배열로 만든 것)

 Tv tv1, tv2, tv3  -> Tv[] tvArr = new Tv[3];  // Tv타입의 참조변수 3개 생성, 초기화는 tvArr[0], tvArr[1], tvArr[2]모두 null로 된다. 
 그리고 tvArr의 값은 new 연산자로 Tv타입의 참조변수를 3개 생성했을 때의 첫번 째 tvArr[0]의 주소 값을 가지게 된다.

 tvArr[0] = new Tv(); // Tv객체를 생성하여 참조변수(tvArr[0])와 연결시켜줌 
 tvArr[1] = new Tv(); // Tv객체를 생성하여 참조변수(tvArr[2])와 연결시켜줌
 tvArr[2] = new Tv(); // Tv객체를 생성하여 참조변수(tvArr[1])와 연결시켜줌
 (tvArr[0], tvArr[1], tvArr[2]이 가지고 있는 주소값은 모두 다름)


(위의 코드를 줄여서)
Tv[] tvArr = {new Tv(), new Tv(), new Tv()};

https://www.acmicpc.net/problem/1149

풀이

1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다

처음에는 그리디 알고리즘으로 문제를 풀어보았지만 오답이었다. 매순간 가장 최선의 선택을 하는 것으로는 최솟값을 구할 수 없다.

위의 그림은 그리디 알고리즘으로 풀이하는 방법이고 아래 그림은 동적계획법으로 풀이하는 방법이다.(위의 그립처럼 풀면 최솟값을 구할 수 없음)

Cost와 Dp 2차원 배열을 선언한다. Dp는 누적 최솟값을 구하기 위해서 사용, Cost는 입력값을 받기 위해서 사용한다. Cost배열로 집의 수만큼의 RGB값(N*3)을 받고 Cost[0][0],Cost[0][1], Cost[0][2])를 Dp[0][0], Dp[0][1],Dp[0][2]에 넣어 Dp의 초기값을 설정해준 후에 Dp[N][Red],Dp[N][Green],Dp[N][Blue] 중 가장 작은 값을 구하면 된다. 가장 작은 값을 구하는 과정은

Dp[N][Red] = Math.Min(Dp[N-1][Green], Dp[N-1][Blue]) + Dp[N][Red] Dp[N][Green] = Math.Min(Dp[N-1][Red], Dp[N-1][Blue]) + Dp[N][Green] Dp[N][Red] = Math.Min(Dp[N-1][Red], Dp[N-1][Green]) + Dp[N][Blue]

다음과 같이 재귀함수를 구성하여 이 문제를 해결할 수 있다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_1149 {

    static final int Red = 0;
    static final int Green = 1;
    static final int Blue = 2;
    static int[][] Cost;
    static int[][] Dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        Cost = new int[T][3];
        Dp = new int[T][3];


        for (int i = 0; i < T; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            Cost[i][Red] = Integer.parseInt(st.nextToken());
            Cost[i][Green] = Integer.parseInt(st.nextToken());
            Cost[i][Blue] = Integer.parseInt(st.nextToken());
        }
        // Dp 2차원 배열 초기값 설정
        Dp[0][Red] = Cost[0][Red];
        Dp[0][Green] = Cost[0][Green];
        Dp[0][Blue] = Cost[0][Blue];

        System.out.println(Math.min(costMin(T - 1, Red), Math.min(costMin(T - 1, Green), costMin(T - 1, Blue))));
    }


    static int costMin(int N, int color) {

        if (Dp[N][color] == 0) {

            if (color == Red) {
                Dp[N][Red] = Math.min(costMin(N - 1, Green), costMin(N - 1, Blue)) + Cost[N][Red];
            } else if (color == Green) {
                Dp[N][Green] = Math.min(costMin(N - 1, Red), costMin(N - 1, Blue)) + Cost[N][Green];
            } else {
                Dp[N][Blue] = Math.min(costMin(N - 1, Red), costMin(N - 1, Green)) + Cost[N][Blue];
            }
        }
        return Dp[N][color];
    }
}