TCP: Transmission Control Protocol 7. Flow Control Flow Control 생산자가 데이터를 생성하는 속도와 소비자가 데이터를 사용할 수 있는 속도의 균형을 유지. sliding window Send window in TCP Sender는 Receiver가 Ack을 보내면서 알려준 rwnd 값을 통해 상대방 버퍼의 빈 공간을 파악하고, 그 빈 공간만큼을 Send window 사이즈로 정한다. window 사이즈는 Receiver가 한번에 받을 수 있는 데이터의 양이다. 데이터 전송 후, 보낸 데이터는 데이터 전송 오류를 대비하여 여전히 Sending Buffer에 남겨둔다. 상대방이 Ack을 보내 해당 데이터를 잘 받았다는 표시를 하면 해당 데이터를 Sending ..

1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Let's Divide-and-Conquer 개선된 알고리즘 → 분할과 정복 Problem and Strategy D K를 먼저 배열의 가운데에 있는 entry와 비교 한 번의 연산으로 절반의 entry를 제거할 수 있다. 동일한 전략을 재귀적으로 수행한다. Algorithm D: Binary Search (반드시 정렬된 array 여야 함) Input: E, first, last, and K→ first, …, last까지 정렬된 array E, K 는 찾아야 할 key 값, input 모두 정수 Output: firs..

TCP: Transmission Control Protocol 6. Windows in TCP stop & wait 방식 데이터 전송할 때마다 잘 받았는지 확인 신뢰성 보장 위한 가장 쉬운 접근 방식 데이터 전송을 화물 트럭으로 비유해 보자. 화물트럭 5대는 서울에서 출발해 부산에 화물을 운반 후 다시 서울로 돌아와 화물이 안전하게 도착했음을 보고해야 한다. stop & wait는 하나의 트럭이 서울-부산을 왕복해서 돌아온 후에 다음 번 트럭이 운행을 시작하는 방식이다. 서울에서 부산까지 왕복으로 10시간이 걸리기 때문에, 트럭 5대가 부산에 화물을 모두 운반하기까지는 50시간이 걸린다. 이는 매우 비효율적이다. 이러한 비효율성을 해결하기 위해 한꺼번에 트럭을 여러 대 보낼 수는 없을까?트럭을 여러 대 ..

TCP: Transmission Control Protocol 3. State transition diagram TCP 연결요청 / 수락 과정 State transition diagram Client / Server 동작 및 상태 설명 (왼: 클라이언트 / 오: 서버) Passive open 수동으로 서버를 열어놓음 [LISTEN] 연결요청 대기, 클라이언트로부터 SYN이 오기를 기다리는 상태 Active open / SYN Active open하기 위해 SYN을 서버에게 전송 [SYN-SENT] SYN을 전송한 뒤 서버로부터 SYN+ACK이 오기를 대기중인 상태 SYN / SYN + ACK 클라이언트로부터 SYN이 오면 클라이언트에게 SYN + ACK을 전송 [SYN-RCVD] 클라이언트로부터 SYN을..

1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Problem and Strategy A Problem: array search 배열 탐색 n개의 entry가 담긴 배열 E와 value K가 주어졌을 때, 배열에서 K=E[index]를 찾는다면 인덱스 값을, K를 찾지 못한다면 -1을 결과로 리턴한다. Strategy A input data와 자료구조: 정렬되지 않은 배열 sequential search(index 0부터 차례로 비교) Algorithm A int seqSearch(int []E, int n, int K) Analysis A W(n) = n //wors..

chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.2 Set Operations Union 합집합 표기: A ∪ B Example: What is {1,2,3} ∪ {3, 4, 5}? Solution: {1,2,3,4,5} Intersection 교집합 표기: A ∪ B 만약 교집합이 존재하지 않는다면, A와 B는 disjoint되었다고 말한다. Example: What is {1,2,3} ∩ {3,4,5} ? Solution: {3} Example: What is {1,2,3} ∩ {4,5,6} ? Solution: ∅ Complement 여집합 U - A (전체집합에서 A를 제외한 나머지) Ā(or Ac) = {..

chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1 Sets 집합 Sets 집합은 순서가 없는(unordered) object들의 모임이다. ex. 반의 학생들 / 방의 의자들 집합의 object들을 elements(원소), 또는 집합의 members(멤버)라 칭한다. 집합은 이러한 element들을 포함(contain)하고 있다. a ∈ A : a는 집합 A의 element이다. a ∉ A : a는 집합 A의 element가 아니다. Describing a Set: 원소나열법 S = {a,b,c,d} 순서는 중요하지 않다. ☞ S = {a,b,c,d} = {b,c,a,d} 중복 멤버는 허용하지 않는다. ☞ S =..

chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Equivalences in Predicate Logic predicates(술어)와 quantifiers(한정자)가 포함된 문장은 동일한 진리 값을 갖는 경우에만 논리적으로 동일하다. - 이 statements(진술)로 대체되는 모든 predicate에 대하여 - 표현식의 변수에 사용되는 담론의 모든 domain에 대해 표기법 S ≡ T: S와 T가 논리적으로 동일하다. Example: ∀x¬¬S(x) ≡ ∀xS(x) Thinking about Quantifiers as Conjunctions and Disjunctions Conjunctions: ∧ Disjuncti..

chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Quantifiers quantifiers(한정자): all과 some를 포함한 영어 단어의 의미를 표현하기 위해 필요하다. - “All men are Mortal.” - “Some cats do not have fur.” 가장 중요한 두 가지 한정자는 다음과 같다. - 전체 한정자(Universal Quantifier), “For all,” symbol: ∀ - 존재 한정자(Existential Quantifier), “There exists,” symbol: ∃ ∀xP(x) (☞모든 x에 대해 P(x)) 와 ∃xP(x) (☞P(x)인 x가 존재) 와 같이 사용한다. ..