앞서 Data Link Control의 기능을 알아보았다. 이 기능들은 프로토콜로 구현되는데, 이 프로토콜들에 대해 알아볼 것이다. 이 책에서는 HDLC와 Point-to-Point에 대해 소개하고 있다. High Level Data-link Control HDLC는 bit oriented 프로토콜이고 point-to-point 통신과 multipoint links 통신도 가능하다. 이는 두 가지 전송 모드를 갖는데, NRM(normal response mode)와 ABM(Asynchronous Balanced mode)이다. NRM : primary에서 명령을 보내고 secondary에서 응답하는 방식, Point-to-Point, Multipoint link 둘다 가능 ABM : Point-to-Po..
분류 전체보기
데이터 링크 계층 데이터 링크 계층이 하는 일은 "node-to-node" 통신이다. 패킷의 최종 목적지엔 크게 관심이 없고, 당장 다음 노드로 잘 보내기만 하면 된다. 유선, 무선으로 연결해 1대1 연결도 가능하고 broadcast도 가능하다. 데이터 링크 계층에서 제공하는 서비스를 이해하기 위해서는 데이터 링크 계층의 sublayer를 이해해야 한다. 데이터 링크 계층의 오류를 제어하는 등의 역할을 하는 Data-link-control(DLC) Sublayer와 데이터 전송의 타이밍을 결정하는 Media-Access-control(MAC) Sublayer가 있다. MAC은 broadcast 할 때만 사용되는데, 그 이유는 여러 명에게 송신할 때 충돌이 발생할 수 있기 때문에 어떻게 보낼지 결정하는 M..
Peer-to-Peer Architecture 서버가 항상 있는 구조가 아니라, end system이 직접적으로 서로 통신하는 방법이다. peer가 다른 peer에게 서비스를 요청하면, 요청을 받은 peer는 서비스를 제공한다. 이러한 예시로는 BitTorrent, KanKan, VoIP 등이 있다. File Distribution 지난 번에 Client-server Paradigm과 Peer-to-Peer Paradigm에 대해 언급한 적이 있다. 이번에는 파일 공유 관점에서 더욱 자세히 분석해보자. 하나의 서버에서 N개의 peer에게 파일을 공유하는데 시간이 얼마나 소요될까? 클라이언트-서버 모델은 클라이언트가 서버에 연결하고 데이터를 조금씩 받아가는데 시간이 소요된다. 그러나 P2P는 파일을 sha..
E-mail 이메일은 아래 3가지 구성요소를 가진다. user agent : "mail reader"로 메일을 작성하고 수정하며 전송할 수 있다. Outlook, iPhone mail client가 이에 속한다. mail server mailbox : 들어온 메일이 저장되는 곳이다. Message queue : 내보낸 메일이 저장되는 곳이다. SMTP Protocol : 메일 서버 간, user agent와 메일 서버 사이의 이메일 전송 프로토콜이다. SMTP(Simple Mail Transfer Protocol) TCP를 사용하며 2번 포트를 사용한다. 전송할 때는 Handshaking, Transfers of messages, closure 과정을 겪는다. 보통 ASCII 코드로 전송된다. SMTP ..
Web과 HTTP 웹 페이지는 동영상, 이미지, 문서와 같은 많은 object로 구성되어 있다. 이것들은 서로 다른 웹 서버에 저장될 수 있다. 웹 페이지는 기본 HTML 파일과 여러 참조 객체로 구성된다. 예를 들어, 웹 페이지가 HTML 텍스트와 5개의 JPEG 이미지로 구성되어 있으면, 이 웹 페이지는 6개의 object를 갖는다. HTTP HTTP는 Hyper Transfer Protocol의 약자로, 웹의 애플리케이션 계층 프로토콜이다. 클라이언트/서버 모델로 동작하며 클라이언트(브라우저)가 HTTP 프로토콜로 object를 요청하면, 서버(웹 서버)가 요청을 받아 object를 보낸다. HTTP와 TCP HTTP는 TCP를 사용하는데, 동작 과정은 다음과 같다. 클라이언트가 TCP 연결을 설정..
Principles of network applications 네트워크 앱 생성 end system에서 동작할 수 있게 프로그램을 구성하고 네트워크를 넘어 서로 소통한다. 예를 들면, 웹 서버 소프트웨어가 브라우저 소프트웨어와 통신하는 것과 같다. end system에서 동작하도록 프로그램을 구성하면, 네트워크 코어에서는 동작할까? 정답은 그렇다. 네트워크 코어에서는 사용자 애플리케이션으로 동작하지 않기 때문에 프로그램을 짜지 않아도 된다. Client-Server paradigm 서버 클라이언트 항상 켜져 있고 고정된 IP 주소를 갖는다. 대부분 데이터 센터에 구축되어 있다. 서버와 통신하며 항상 연결된 상태가 아니라서 통신할 때 켜줘야 한다. 따라서 IP 주소는 항상 바뀌고 클라이언트들과 직접적인 통..
Optimal Binary Search Trees 이진 탐색 트리에서 평균 탐색 비용을 최적화하는 알고리즘이다. 이진 탐색 트리에 대한 내용은 [자료구조] Tree(트리) - 이진 트리를 참고하면 된다. 간단하게 이진 탐색 트리의 성질은 다음과 같다. 각 노드는 하나의 유일한 key를 가진다. 모든 노드의 key는 그 노드의 왼쪽 서브 트리의 key보다 항상 크다. 모든 노드의 key는 그 노드의 오른쪽 서브 트리의 key보다 항상 작다. 문제 접근 n개의 key들이 배열 K에 정렬되어 있고, 각 key의 탐색 확률인 pi가 주어진다. 각 key의 비교 횟수는 ci이다. 이러한 조건에서 각 key의 평균 탐색 비용는 pi * ci이다. 먼저, Brute Force로 접근해보자. 모든 경우에 대해 최적의 ..
Chained Matrix Multiplication 연쇄 행렬 곱셈은 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬에서 곱셈은 결합 법칙이 성립하기 때문에 곱셉 순서는 상관 없지만, 연산의 양이 달라진다. 예를 들어, 2 * 3 행렬 A와 3 * 5 행렬 B, 5 * 7 행렬 C가 있다고 하자. 이 행렬들의 곱 ABC를 구하는 경우는 2가지가 있다. (A * B) * C 연산 횟수 : 2 * 3 * 5 + 2 * 5 * 7 = 100 A * (B * C) 연산 횟수 : 3 * 5 * 7 + 2 * 3 * 7 = 147 결과는 같지만 연산의 횟수가 달라진다는 것을 알 수 있다. 먼저 Brute Force로 접근해보자. 모든 경우의 수를 계산해야 하기 때문에 exponenti..
플로이드 알고리즘 플로이드 알고리즘은 최단 경로를 구하는 유명한 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘인 반면, 플로이드 알고리즘은 모든 노드 간의 최단 경로를 구하는 방법이다. 2차원 인접 행렬을 구성해서 경로마다 더 짧은 길이를 선택해 줄이는 과정을 반복한다. 플로이드와 다익스트라에 대한 자세한 내용은 [자료구조] Graph(그래프) - 최단 경로 알고리즘을 참고하면 된다. 플로이드 알고리즘은 모든 경로를 확인해야 하기 때문에 Brute Force 방법으로 접근할 수 있다. 그러나, 시간복잡도가 O(n!)이므로 효율적인 다른 방법을 사용해야 한다. Dynamic Programming을 사용하면, n!인 시간복잡도를 조금 더 줄일 수 있다...
이항계수 이항계수는 주어진 집합에서 원하는 개수만큼 순서에 상관없이 뽑는 조합의 개수를 의미한다. 이항계수는 위와 같은 수식으로 표현해 풀 수 있다. 알고리즘적으로 조금 더 쉽게 풀어보면 아래 수식과 같다. 이항계수를 계산하는 방법은 2가지가 있다. Divide-and-Conquer과 Dynamic Programming으로 푸는 방법이다. Divide-and-Conquer k 가 0이거나 n이 k일 때는 1을 리턴하고, 그게 아니라면 재귀를 반복한다. 아래와 같이 코드를 짤 수 있다. typedef unsigned long long LongInteger; LongInteger bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n - ..
