체육공대생

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$..

전 글에서는 Stop and Wait ARQ에 대해서 배웠다.이번 글에서는 Go Back N ARQ에 대해 알아볼 것이다.Go Back N ARQ먼저 Go Back N ARQ 에서 송신자와 수신자가 어떻게 작동하는지 알아보자.대기열의 맨 앞에 패킷이 있고, 전송할 준비가 되었다면 해당 패킷을 전송한다.ACK timer를 시작하고 대기열의 후속 패킷을 전송한다. 전송되었지만 아직 확인되지 않은 패킷 수가 N을 초과하지 않는 한 계속 전송이 가능하다.타임 아웃 기간 내에 ACK를 수신했는지 확인한다. 수신했다면, 대기열의 맨 앞에 있는 패킷을 제거하고, 새로운 대기열의 맨 앞 패킷에 대한 ACK 타이머를 갱신한다. 이때도 역시 대기열의 후속 패킷을 전송하되, 전송되었지만 아직 확인되지 않은 패킷 수가 N을 ..

수신자가 받은 패킷이 송신자가 보낸 패킷과 다를 때, 해당 패킷에서 오류가 발생했다고 얘기한다.이러한 오류는 잡음과 간섭에 의해 발생할 수 있다. 오류의 주요 원인들로는,전자들의 무작위 운동자연 현상: 번개, 태양 흑점 등인간 활동: 전기 점화 시스템, 모터 및 스위칭 시스템 등기호 간 간섭(Inter-symbol interference): 인접한 신호가 서로 영향을 미치는 현상혼선(Crosstalk): 신호 간의 전자기적 결합에 의해 발생하는 현상에코: 부적절하게 끝난 회로에서 먼 쪽으로부터 전자기 에너지가 반사되는 현상등이 존재한다. 오류를 제어하는 방식은 두 가지로 분류된다.closed-loop error control scheme(폐쇄 루프 오류 제어 방식): automatic repeat req..

이전 글에서는 데이터 중심의 일관성 모델에 대해서 알아봤다.이번엔 클라이언트 중심 일관성 모델에 대해서 알아보자. Client-centric Consistency Models: 클라이언트 중심 일관성 모델데이터 중심 일관성 모델은 데이터 저장소에 대해 시스템 전체의 일관성 보장을 목표로 한다.하지만 클라이언트 중심 일관성 모델은 주로 동시 업데이트가 거의 없는 애플리케이션에 사용되기 때문에, 대부분의 연산은 데이터를 읽는데 중점을 둔다.따라서 매우 약한 일관성이 특징이다. 시스템 전반의 일관성을 유지하기 보다는, 특정 클라이언트의 요구에 집중함으로써 시스템 전체의 일관성을 피할 수 있는 방법을 보여준다. 대부분의 대규모 분산 시스템은 확장성을 위해 복제를 적용하지만, 약한 일관성만 지원한다.예들 들어, ..

그래프 알고리즘을 배우기에 앞서, 그래프란 무엇일까? 그래프는 $G = (V, E)$는 정점 집합 V와 간선 집합 E로 이루어져 있으며, 방향성이 있을 수도 있고 없을 수도 있다.알고리즘에서 사용하는 그래프 표현 방법에는 두가지가 존재한다.인접 리스트(Adjacency list): 각 정점에 연결된 이웃 정점들을 리스트 형태로 저장한다.인접 행렬(Adgacency matrix): 정점 간의 연결을 행렬 형태로 표현하여, 특정 정점 쌍 간의 연결 여부를 나타낸다.알고리즘의 실행 시간은 보통 정점의 수 |V|와 간선의 수 |E|로 표현된다.점근 표기법을 사용할 때는, 집합의 크기를 나타내는 기호는 생략할 수 있다. $O(V + E)$로 간단히 표현할 수 있다는 의미이다.인접 리스트: Adjacency lis..

Replication: 복제복제의 목적은 가용성(availability), 신뢰성(dependability), 또는 성능(performance)을 향상시키는 것이다.이때 복제 가시성(replica visibility)에 대한 정보가 없어도 이러한 목적을 달성할 수 있어야한다. 분산 시스템인만큼, 시스템 내에서 상태의 복제를 숨겨서 사용자나 애플리케이션이 복제를 인식하지 못하도록 하는 복제 투명성(replication transparency)이 중요하다.활성 복제(Active replication)는 여러 복제본이 동시에 활성 상태로 작동하여 요청을 처리한다.기본/대기 복제(Primary/Stand-by replication)는 하나의 기본 복제본이 활성 상태로 작동하고, 대기 복제본은 기본 복제본이 장애..