체육공대생

Flow란 무엇일까?플로우는 송신자로부터 수신자로 향하는 패킷들의 흐름을 의미한다. 여러 플로우가 동시에 동일한 수신자로 전달될 수 있다. 플로우를 제어함으로써 네트워크와 사용자가 과부하 상태가 되는 것을 방지하여 처리량과 응답시간의 저하를 막고, 자원을 보호할 수 있다. 또한 deadlock 상황을 피할 수 있으며, 사용자간 자원을 공정하게 분배할 수 있으며, 네트워크와 사용자의 속도를 일치시킬 수 있다.Sliding Window Control Scheme슬라이딩 윈도우 제어 방식에서 사용되는 윈도우 크기 W는 송신 노드(source node)와 수신 노드(destination node)의 협의하에 결정된다.송신 노드는 수신 노드로부터 승인(authorization)을 받지 않고도 최대 W개의 세그먼트..

Fault Tolerance 이어서Consensus: 합의하나 이상의 시스템이 값을 제안할 때, 시스템들이 어떻게 합의하여 하나의 값을 결정할까?전제 조건(Prerequisite)이 있는데, 결함 허용 프로세스 그룹에서는 모든 비결함 프로세스가 다른 비결함 프로세스와 동일한 명령을 동일한 순서로 실행해야된다는 것이다. 이 말은, 비결함 그룹 구성원들은 다음에 실행할 명령에 대해 합의해야된다는 것이다.Flooding-based Consensus 시스템에는 프로세스 그룹 P = {$P_1, ... P_n$}이 있고, Fail-stop 실패 의미론(신뢰할 수 있는 실패 감지 기능)을 가정한다. 클라이언트가  특정 프로세스 $P_i$에 접촉하여 명령 실행을 요청하면, 모든 $P_i$는 제안된 명령 목록을 유지한..

주어진 마을에 여러 집과 이를 연결하는 도로가 있다. 각 도로는 두 개의 집을 연결하며, 도로를 수리하는데 비용 w(u, v)이 소요된다. 목표는 최소 비용으로 필요한 도로만 수리하여 모든 집이 서로 연결되도록 하는 것이다. 이 문제는 MST를 구하는 알고리즘으로 해결할 수 있다.수리할 도로 집합 T⊆E를 찾으며, 이때 T는 모든 정점을 연결하면서 최소 비용을 만족하는 스패닝 트리가 되어야한다. 최소 비용 스패닝 트리(Minimum Spainning Tree)란, 주어진 그래프의 모든 정점을 연결하는 모든 스패닝 트리 중에서 가중치의 합이 최소가 되는 트리를 의미한다. 위 그림에서 두껍게 칠해진 선들의 집합을 MST라고 한다. 모든 노드들을 연결하고 있으며, 도합 37이라는 최소 비용을 가지고 있다.간선..

Performance of FEC Channel Model채널의 모델에는 다양한 종류가 존재한다. Performance anaylsis of (3, 1) Repetition Code 성능 분석을 위한 환경 가정을 먼저 해보겠다.각 전송된 기호는 독립적으로 0 또는 1일 가능성이 같고, 기호 오류 확률은 $\epsilon \in [0, 1/2]$이다.  코드 되지 않은 경우의 검출 실패 확률코드 되지 않은 경우는 데이터가 전송될 때 오류 검출 및 수정 코드 없이 전송되는 것이다.기호 오류 확률 $\epsilon$이 주어졌을 때, 전체 오류가 발생할 확률(전송된 기호가 수신될 때 원래의 값과 달라지는 경우)은 다음과 같다. P(A) = 0 (정상적인 경우)와 P(B) = $\epsilon$(오류가 발생한 경..

FEC 이어서(7, 4) Hamming CodeEncoding인코더로의 input word는 $U = (U_1, U_2, U_3, U_4)$이며, 모든 $i \in \left\{1,2,3,4\right\}$에 대해 $U_i \in \left\{0,1\right\}$이다.인코더에서 생성된 output word는 $X = (X_1, ..., X_7)$이며, 모든 $j \in \left\{1,2,...,7\right\}$에 대해 $X_j \in \left\{0,1\right\}$이다. 인코딩 규칙과 그에 따른 코드워드는 아래와 같다. Encoding: 생성행렬(7, 4) 해밍코드의 생성 행렬(Generator matrix) G는 4×7 행렬로 표현된다. 생성행렬을 통한 인코딩은 $X = UG$로 생성된다. 첫..

Fault ToleranceDependability: 신뢰성컴포넌트는 클라이언트에게 서비스를 제공한다. 그리고 서비스를 제공하기 위해 그 컴포넌트는 다른 컴포넌트의 서비스를 필요로 할 수 있다. 즉, 컴포넌트는 다른 컴포넌트에 의존할 수 있다는 것이다.다음은 신뢰성과 관련된 요구사항들이다.Availability(가용성): 사용 가능Reliability(신뢰성): 서비스의 연속적 제공Safety(안전성):  아주 낮은 재앙(catastrophes) 가능성Maintainability(유지보수성): 수리하기 용이컴포넌트 C가 시간 T = 0에서 정상적으로 작동한 상태에서 [0, t) 동안 정상적으로 작동할 확률을 Reliability R(t) 라고한다.Mean Time To Failure, MTTF (평균 고..

과제의 내용은 ARQ 심층 우주 통신 중 갈릴레오 우주선의 목성 탐사 임무에 대한 내용이였다.목성을 탐사한 시스템이 지구로 사진을 보내기 위해 Stop and Wait ARQ를 사용했을 때의 성능을 분석하는 것이다. 1. Let $N_P$ denote the length of the packet(the number of binary digits that comprise a packet), calculate $N_P$. 먼저 사진 한 장의 bit를 계산해 보면, 100(lines)×100(pixels)×10(bits) = 100000 bits 이다.여기서 한 장의 사진은 100개의 패킷들로 이루어져 있으므로, 100000bits / 100packets = 1000 bits가 된다.$N_P$ = 1000 b..

Forward  Error Correction, FEC (전진 오류 수정)FEC는 송신자가 패킷에 특수 기능을 추가하여 수신자가 수신된 패킷의 오류를 수정할 수 있도록 한다. 송신기의 인코딩송신기가 수신기로 전송할 이진 기호 스트림이 있다고 가정한다. 이진 기호 스트림은 길이 k인 기호 블록으로 분할된다. 이러한 기호 블록은 인코더에 입력하는 input word라고 하며, $U = (U_1, ..., U_k)$로 표시된다. 여기서 모든 $i \in \left\{1, ..., k\right\}$에 대해 $U_i \in \left\{1, 0\right\}$ 이다. input word는 $\left\{0, 1\right\}^k$ 집합에서 $2^k$개의 값 중 하나를 가질 수 있다. 인코더는 길이 k인 inpu..

Selective Repeat ARQ큐에 패킷이 있고 전송할 준비가 되었다면, 맨 앞에 있는 패킷을 전송한다. 그리고 이 패킷에 대한 ACK timer를 시작한다.큐에서 아직 전송된 적이 없는 후속 패킷들도 전송하는데, 각 패킷에 대한 ACK timer를 시작한다.타임아웃 기간 내에 ACK을 수신했는지 확인한다. ACK을 수신한 경우, 인증된 패킷을 큐에서 제거하고, 후속 패킷들을 전송하며 ACK 타이머 또한 작동시킨다. 만약 ACK을 수신하지 못한 경우, 큐에서 ACK을 받지 못한 패킷을 재전송하며 이 패킷에 대한 ACK timer를 다시 시작한다. 이후에 후속 패킷들을 전송하며 ACK 타이머 또한 작동시킨다. Stop and Wait ARQ나, Go and Back ARQ 같은 경우에는 타이머를 하나..

Strongly Connected Components: 강한 연결 성분, SCC주어진 방향 그래프 G = (V, E)에서, SCC는 그래프 G의 최대 정점 집합 C⊆⊆V로, 모든 정점 u, v ∈ C에 대해 u에서 v로의 경로와 v에서 u로의 경로가 모두 존재하는 집합이다. 말이 좀 어렵게 느껴질 수 있는데 그림으로 설명해보자면,정점들을 묶어놓은 것이 부분 집합 C이고, 이 C내의 모든 정점들은 역방향이든 정방향이든 경로가 모두 존재한다는 것이다.타임스탬프 14를 가진 정점과 13을 가진 정점을 보자. 14에서 13으로 향하는 경로도 존재하고, 13에서 14로 향하는 경로도 존재하는 것을 볼 수 있다.경로가 존재하는 정점이 따로 없다면, 타임스탬프 10을 가진 정점처럼 혼자 묶인다. 알고리즘은 $G^T$..