RAINBOW-LAB

오일러 경로(Eulerian trail) 란 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때 시작점과 도착점이 같으면 오일러 회로(Circuit) 가 됩니다. 가장 대표적으로 별 모양 그래프가 있는데 어느 점에서 시작하더라도 모두 출발점으로 되돌아 올 수 있습니다. 즉, 위 그래프는 오일러 회로가 존재합니다. 위 그래프를 다시 보면 모든 정점의 차수가 2(짝수)인데 시작점과 끝점을 제외하고서는 들어오는 간선이 있다면 반드시 나가는 간선이 하나 더 마련되어 있어야 하기 때문입니다. 그렇기에 항상 차수가 2의 배수꼴로 붙게 됩니다. 오일러 경로의 존재여부를 판단하는 방법은, 무향 그래프(non-directed graph)일 경우 Degree가 홀수 인 정점(Vertex)가..

어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이 동적계획법(Dynamic Programming) 이다. Divide-and-conquer 와 비슷해 보이지만 DC는 문제를 큰 부분에서 작은 부분으로 나누는 Top-Down approach인데 반해, DP는 작은 문제부터 큰 문제로 풀어가는 Bottom-Up approach이다. 또한 DC는 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만 DP는 이전 단계의 답에 의존적이다. 그래서 한 번 푼적 있는 문제는 다시 풀지 않도록 테이블에 저장해둔다. 정리하면, 1. 문제를 작은 부분 문제로 나눈다. 2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다. (Mem..

1. P 문제 현실적으로 쓸만한 알고리즘이라면, 그 비용이 견딜만큼 현실적인 알고리즘이라는 것이다. 알고리즘의 Time complexity가 입력 크기 n에 대해 상수 k승을 가진다면 '현실적' 이라고 본다. 예를 들어 $$O(n^2)$$ 혹은 $$O(n^3)$$등이 있다. 입력 크기가 커지면 다항으로 증가하는 비용(Polynomial Complexity)이다. 즉, 현실적인 비용으로 풀 수 있는 문제들, 다항(Polynomial) 알고리즘이 있는 문제들을 'P 클래스 문제' 라고 한다. 2. NP 문제 어려운 문제의 경계에 가까이 있는 문제들의 집합을 'NP클래스 문제' 라고 한다. 운에 기대면 현실적인 비용으로 해결할 수 있는(Non-Deterministic polynomimal) 문제들이다. 운에 ..

Network 에서 패킷의 오류를 검출하기 위해 CheckSum이라는 헤더의 Field를 사용한다. CheckSum방법은 상대적으로 패킷 오버헤드가 적은데, 예를 들어 TCP와 UDP는 16bit만 사용한다. (TCP의 헤더크기는 20byte, UDP는 8byte) Checksum은 보안 관점에서 사용되는 Hash Function보다는 취약한 무결성 검증 방법이다. Transport 계층은 일반적으로 호스트의 OS의 일부로서 Software로 구현된다. 즉, Transport계층의 오류 검출이 Software로 구현되므로 CheckSum처럼 간단하고 빠른 오류 검출 기법이 필요하다. 반면에 Data Integrity를 위한 보안 관점의 Hash는 예로, 대표적인 Hash 알고리즘인 MD5는 길이로만 봐도..

◎ 신뢰적인 데이터 전달 프로토콜의 구축 완전히 신뢰적인 데이터 전송 프로토콜에 도달하기 위해 조금씩 복잡해지는 일련의 프로토콜을 소개한다. 1. 완벽하게 신뢰적인 채널 상에서의 신뢰적인 데이터 전송 : rdt 1.0 먼저, 하위 채널이 완전히 신뢰적인 가장 간단한 경우를 고려한다. 프로토콜 자체는 단순하며, rdt(reliable data transfer) 1.0이라 부르겠다. rdt 1.0은 송신자와 수신자에 대한 유한상태 머신(Finite-State Machine, FSM) 이다. 위의 Figure 3.9(a) 는 송신자의 동작을 정의하고, 3.9(b) 는 수신자의 동작을 정의한다. 송신자에 대해 그리고 수신자에 대해 분리된 FSM이 있다는 것에 유의해야한다. 변화를 일으키는 Event에 대해서는 ..

프로토콜 rdt3.0 은 기능적으로 정확한 프로토콜이다. 오늘날의 고속 네트워크에서 누구나 이것의 성능에 만족하지는 않는다. rdt 3.0 의 핵심적인 성능 문제는 stop-and-wait방식이라는 것이다. 이러한 특별한 성능 문제에 대한 간단한 해결책으로, Stop-and-Wait 동작하는것 대신에 송신자에게 확인 응답을 기다리지 않고 여러패킷을 전송하도록 허용하는 것이다. 이러한 신뢰적 데이터 전송 프로토콜 기술을 "파이프라이닝(Pipelining)" 이라고 한다. 파이프라이닝 방식은 데이터 전송 프로토콜에서 다음과 같은 중요성을 가지고 있다. 1) 순서번호의 범위는 증가되어야 한다. 각각의 전송중인 패킷은 유일한 순서번호를 가져야하고, 거기에 전송 중이고 확인 응답이 안 된 여러 패킷이 있을지도 모..

Context Switching이란 멀티 프로세서 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때 기존 프로세스의 상태 또는 레지스터 값을 저장하고, CPU가 다음 프로세스를 실행하도록 새로운 프로세스의 상태 또는 레지스터 값을 교체하는 작업입니다. 다시 말해서, CPU는 하나의 프로세스를 수행할 수 있는데 다른 작업으로 전환하여 수행하기 위한 상태 정보가 필요합니다. 이때 다른 프로세스의 상태 정보를 가져와 작업을 갱신하는 과정이 Context Switching 입니다. (간혹 Context Switching을 문맥 교환이라고 한글로 번역해놓았던데.. 전 개인적으로 이러한 표현이 상당히 거부감이 들었습니다.. 문맥?? ..

1. Thrashing 이란? 일반적으로 하나의 프로세스는 실행을 위해 몇 개의 페이지 프레임(Page Frame)을 할당 받는다. 물론 이때 할당받는 프레임의 수는 주기억장치의 크기와 페이지 프레임의 크기에 따라 결정되는 종속적인 문제이기는 하지만 대부분의 경우에는 각 작업에 필요한 충분한 페이지 프레임을 항상 할당 받을 수 있다. 프로세스에 할당된 프레임의 수가 효율적인 실행을 위해 시스템에 의해 요구되는 최소한의 수보다 적으면 적을수록 페이지 부재율(Page missing fault)는 증가하며, 프로세스의 실행은 늦어지게 된다. 이와 같이 만일 하나의 프로세스가 어느 정도의 충분한 프레임을 갖고 있지 않다면 페이지 부재가 발생하여 프레임 안에 있는 사용중인 어떤 페이지를 교체해야 하는데, 이러한 ..

TCP는 통신을 위해 사전에 3-way handshaking을 사용하여 연결을 설정해놓고 Flow control, Sequence number, ack message, timer를 활용하여 송신하는 프로세스로부터 수신하는 프로세스에게 데이터가 순서대로 정확하게 전달하게 한다. 또한 TCP는 congestion control을 통해 TCP연결이 과도하게 몰리는 현상을 방지하기도 한다. TCP는 혼잡한 네트워크 링크에서 각 연결이 링크의 Bandwidth를 공평하게 공유하여 통과하도록 한다. UDP는 [RFC 786]에 정의된 내용에 따르면 트랜스포트 계층이 할 수 있는 최소 기능으로 동작한다. Multiplexing, DeMultiplexing 및 간단한 오류 검사를 제외하면 IP에 아무것도 추가하지 않는..

TCP(Transmission Control Protocol) 은 연결 지향형 프로토콜로서 3-way handshaking 과정에 의해 연결을 설정한 후 데이터를 전송한다. TCP는 Transfer 과정에서 reliable하다는 것은, 전송 및 수신 상태를 보장해주기 때문이다. 하지만 이러한 TCP의 reliable하다는 것은 전송에 있어 신뢰성을 증가시켜줄 수 있지만 반대로 전송 과정에 문제가 생긴다면 처리 과정에 latency가 생기게 된다. 예를 들면, 음식을 주문하고 대기표를 받고 기다리던 손님이 있었다. 손님 차례가 되어 주문한 음식이 나와 직원이 주문 대기표를 확인하는데 손님이 대기표를 잃어버린것이 아닌가? 이러한 상황에서 TCP라는 직원은 대기표를 명확하게 확인할 때 까지 그 손님에게 음식을..