체육공대생

전 글에서는 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)는 하나의 기본 복제본이 활성 상태로 작동하고, 대기 복제본은 기본 복제본이 장애..

Coordination전 글에 이어서 coordination에 대해 더 알아보겠다. 분산 시스템에서 여러 프로세스가 특정 자원에 대한 독점적 접근을 원할 때, 각 프로세스는 다른 프로세스와 동시에 해당 자원에 접근하지 못하도록 상호 배제(Mutual exclusion)이 필요하다.허가 기반 해결 방법(Permission-based solution): 프로세스가 자신의 임계 영역에 들어가거나 자원에 접근하기를 원할 때, 다른 프로세스들로부터 허가를 받는 방식이다.토큰 기반 해결 방법(Token-based sloution): 공유 자원에 접근할 수 있는 권한을 나타내는 토큰을 소유한 프로세스만 자원에 접근 가능한 방식이다. 토큰을 가진 프로세스만 접근 권한을 가지므로 상호 배제가 보장된다.Permission..

정렬 알고리즘에는 여러가지 타입이 존재한다.정렬에는 요소들이 순차적으로 증가하게끔 만드는 오퍼레이션만 사용되며, 이는 요소의 쌍을 비교하면서 이루어진다. Exchange Sorting - Bubble Sort, Quick SortInsertion Sort Selection Sorting - Selection Sort, Heap SortMerge SortDistribution Sort - Bucket Sort, Radix Sort 정렬의 하한(lower bound)하한은 주어진 입력을 정렬하기 위해 필요한 최소 계산 작업을 의미한다. 비교 기반 정렬 알고리즘의 경우, 이 최소 비교 횟수는 보통 $\Omega(n\lg n)$이다. 여기서 어떤 비교 기반 정렬이 수행하는 비교 과정을 추상화한 것을 결정 트리 ..