Computer Network - Application Layer 정리(91-108p) 15.09.24

Q. HTTP가 Stateless Protocol인 이유 -91p
HTTP는 요청이 들어왔을 때 응답을 주는 On-Demand 방식을 이용해 동작하는데,
요청된 웹페이지의 객체들을 되돌려 주는 식으로 구현된다.
여기서 말하는 객체는 HTML,자바 애플릿, JPEG, GIF와 같은 것들을 모두 포함하는 개념이다.

- 서버는 클라이언트에 대한 어떠한 정보도 저장하지 않는다.
- 특정 클라이언트가 몇초후에 같은 객체를 요청하더라도 클라이언트에 대한 정보를 저장 하지 않기에 다시 보내야 한다.
- 이러한 방식이 수천개의 TCP연걸이 가능하게 한다.

Q. 비지속연결, 지속연결이란? -91p
비지속 연걸(non-persistent connection) : 각 요구/응답쌍이 분리된 TCP연결을 통해 보내진다.
지속 연결(persistent connection) : 모든 요구와 해당하는 응답들과 같은 TCP연결상으로 보내진다.

Q. 비지속연결의 단점 -92p
1. 각 요청 객체에 대한 새로운 연결이 설정되고 유지되어야 한다.
  객체 별로 TCP연결을 생성해 버퍼를 할당해야 하므로 이게 서버에 과부하를 줄 수 있다.

2. 각 객체는 2RTT를 필요로 한다. (TCP 연결을 요청하는 RTT + 파일을 요청하는RTT)

Q. RTT(Round Trip Time) -93p
- 작은 패킷이 클라이언트로 부터 서버까지 가고, 다시 클라이언트로 되돌아가는 시간을 의미한다.

Q. HTTP 방식 필드(Method Field)의 종류- 95p
- Get : 서버에 어떠한 객체를 요청할 때 사용하며, HTTP에서 가장 많이 사용하는 방식이다.
- Post : 검색엔진에 검색단어를 넣는 것 처럼 사용자가 폼을 채워 넣을 때 사용하는 방식이다.
- Head : 서버가 요청을 받으면, 메시지로 응답하고 요청한 객체는 보내지 않는다. 디버깅을 할 때 많이 사용하는 방식이다.
- Put : 웹서버에 업로드를 할 때 사용

Q. 쿠키의 필요이유 -98p
쿠키는 비상태 HTTP위에서도 사용자 세션 계층을 생성하기 위해 이용된다.
- 서버가 접속을 제한하거나, 사용자에 따라 다른 콘텐츠를 제공하고 싶을 때 사용한다.
- 사용자가 서버에 쿠키 식별번호를 같이 전송해서, 그에 따라 다른 서비스를 제공받게 된다.

Q. 웹캐시의 기능 -101p
웹캐시(프록시 서버)는 기점 웹서버를 대신하여 HTTP의 요구를 충족시키는 개체이다.
자체의 저장 디스크를 가지고 있어서 최근 호출된 객체의 사본을 저장 및 보존한다.
Client - Proxy server - Origin Server 의 순으로 구성되게 된다.

일단 브라우저가 설정되면, 객체에 대한 각각의 브라우저 요청은 웹 캐시에 가장 먼저 보낸다.
웹캐시의 가장 가장 중요한 목적은 트래픽을 지역화 시켜서 Origin Server에 많은 부하가 걸리는 것을 막는 것이다.

Q. 조건부GET(Conditional get)이란?-105p
웹캐시에서 현재 가지고 있는 캐시가 최신의 것인지를 확인하기 위해 Origin Server로 보내서 최신의 것이 아니면
응답 메시지로 객체를 수신하게 된다.
최신의 것 이라면, 헤더만을 가진 빈 패킷이 도착해 최신의 것임을 확인할 수 있다.

Dijkstra Algorithm

Dijkstra Algorithm

1. 집합 S를 정의하여 공집합으로 초기화한다. 

2. 그래프의 각 정점 u에 대해 d(u)가 정의되어, u=s인 경우 0으로, 나머지 경우 ∞​으로 초기화한다.
  즉, d(s) := 0, d(v) := ∞​ (v≠​​s)​3. S에 속해있지 않은 V의 원소에서 d(u)의 값이 최소가 되는 정점 u를 선택하여 S에 추가한다.  

4. u와 연결된 모든 정점을 v1, ..., vk라 두자. 
  기존의 d(vi)​ (i=1, 2, ... , k)​ 값보다​ d(u)+w(u, vi)​ 의 값이 더 작다면, d(vi)​​의 값을 d(u)+w(u, vi)로 수정해준다.
  즉, ​d(vi)​ := ​min{d(vi), ​d(u)+w(u, vi)} ​(i=1, 2, ... , k) 

5. S와 V가 일치할 때까지 3번과 4번을​ 반복해준다.
  최종적으로 얻어지는 d(u)의 값이 s에서 임의의 정점 u까지의 최단 경로의 길이이다.

Uk는 k번째 단계에서 선택된 정점
Sk는 k번째 단계에서 집합S
Dk(v)는k번째 단계에서의 d(v)로 정의된다.
D(v,v')은 v에서 v'을 잇는 최단경로이다.

Reference)
http://m.blog.naver.com/sehoon95/220115473322

Greedy Algorithm의 정의와 증명 방법

Greedy Algorithm

​

한국말로는 탐욕 알고리즘이라고도 하고, 욕심쟁이 알고리즘이라고도 한다.

Greedy 알고리즘이란 문제를 풀기 위해 선택을 내려야 할 매 순간마다 '최고'의 선택을 내리는 알고리즘이다. 

 

다음 문제를 보자. 

서로 다른 수 n개 a1, a2, a3, ..., an가 주어졌다. 이 중 k개(물론 k는 n보다 작거나 같은 수이다)의 숫자를 뽑아 이들의 합을 가장 크게 만들어주려면 어떻게 해야할까?

답은 간단하다. 바로 '가장 큰 숫자 k개를 뽑는 것'이다. 즉, '숫자를 뽑는 선택'을 내리는 매 순간마다 남아있는 숫자 중 '가장 큰' 숫자를 뽑는 것, 이것이 바로 Greedy Algorithm의 한 예라고 볼 수 있겠다. 

그러면 Greedy Algorithm으로 얻은 답은 항상 옳을까? 이는 증명해 보아야 할 문제이다. 어떤 문제를 풀던 간에 Greedy Algorithm으로 접근하여 답을 얻었다면 이 답이 옳은지를 증명하여야한다.  

위의 문제 역시 자명해 보이지만, 엄밀하게는 증명이 필요하며 증명은 다음과 같다.

증명

​

Greedy Algorithm으로 얻은 k개의 숫자의 집합을 G={g_1, g_2, ..., g_k} (g_1>g_2>...>g_k),

그리고 최적해의 집합을 O={o_1, o2_, ..., o_k} (o_1>o_2>...>o_k}라고 하자.

그리고, O와 G가 다르다고 가정하자. (귀류법)

​

그렇다면, o_m와 g_m의 값이 달라지는 최소의 자연수 m이 존재한다.

이때, g_m는 Greedy Agorithm에 의해 선택된 m번쨰로 큰 숫자이기 때문에 g_m는 o_m보다 크게 된다.​

​

새로운 집합 S를 다음과 같이 정의하자.

​S = {o_1, ..., o_(m-1), g_m, o_(m+1), ..., o_k}

이때 S의 원소의 합은 O의 원소의​ 합보다 크게 되며, O가 최적해의 집함임에 모순된다.

​

이와 같은 방법으로 증명하는 방법을 "​Exchange Argument" 라고 부르며, Greedy Algorithm과 최적 해가 동일함을 증명할 때 자주 사용되는 증명 방법이다. 

Reference)
http://sehoon95.blog.me/220115473322

[출처] [알고리즘] Greedy Algorithm : Greedy Algorithm이란?|작성자 몽환

P,NP,NP-Hard,NP-Complete에 대한 간략한 정리

P 
  : Deterministic Polynomial Time 의 약자이다.
  : Polynomial time 이내에 해결, 곧 답을 찾을 수 있는 문제들을 의미한다.
  : 즉 알고리즘의 복잡도가 O(n^x)로 표현되는 모든 문제들을 말한다.

NP
  : Non Deterministic Polynomial Time의 약자이다.
  : Polynomial time에 답의 존재 유무를 확인할 수 있는 문제를 말한다.
  : 답을 줬을 때 그 답이 맞는지를 Polynomial한 시간 이내에 찾을 수 있는 문제들을 의미한다.
  : 답이 Polynomial Time 안에 해결 가능한지, 불가능한지는 모르지만 답의 유무는 확인
    가능한 문제들의 집합이다.

NP-Hard
  : at least hard as the hardest problem in NP
  : 답을 줘도 답이 맞는지 P-time이내에 확인할 길이 없고, 답을 구할 수도 없는 문제를 의미한다.


NP-Complete 
  : 모든 NP문제들을 P-Time 이내에 Reduction(변환)할 수 있는 문제를 NP-Complete라고한다.
  : 결국 NP-Complete문제를 해결한다면 모든 NP문제를 풀 수 있다는 결론이 나온다.
  : NP-Complete 문제를 해결한다면 P=NP라는 가설이 해결된다는 의미이지 않을까 싶다.

Basic of Dedicated Short Range Communication(DSRC)

*Why are Dedicated Short-Range Communication(DSRC) being used in active safety system research?

  Communication-based active safety application은 V2V나 V2I에서 운전자가 보지 못하는 잠재적인 위협을 감지하기 위해 사용된다.
ConnectedVehicle은 잠재적 비용감소와 자동 센서 기반의 기능들을 가능케한다.
  Communication based sensor system은 위험감지를 통해 모든 종류의 vehicles에서 절감 할 수 있지만, Vehicle과 Infrastructure간에 상호운용가능한 통신이 필요하다.

Reference) http://www.its.dot.gov/DSRC/dsrc_faq.htm
http://web.archive.org/web/20130216162616/http://www.standards.its.dot.gov/Documents/advisories/dsrc_advisory.htm

추가조사내용)

  *  DSRC는 Roadside와 Vehicles, Vehicles과 Vehicles 사이의 통신을 하며, 제한거리는 1000m이다.

  *  지금은 전자요금 징수나, 전자 자격 심사에 사용된다. 915MHz에서 동작하며 현재는 주로 독자적인 기술로 이용되나, 표준에 호환되는 장치들도 개발되고 있다.

  * 99년 이후로, 5.9GHz 대역폭을 할당받았으며, 이러한 새로운 대역폭은 더 높은 데이터 전송률을 가지며, 스펙트럼이 더 넓다. 기존에 사용되던 915MHz는 다른 허가되지 않은 기기들과 같은 대역폭을 사용해야 하지만 5.9GHz는 군사용레이더나 인공위성 통신 시스템과 같이 사용하게 된다.