CS

6.1 링크 계층 소개노드: 링크 계층 프로토콜을 실행하는 장치링크: 통신 경로상의 인접한 노드들을 연결하는 통신 채널데이터 그램을 종단간 경로의 개별 링크로 이동시켜야 전달 가능(송신호스트-WIFI 접속점 사이의 WIFI 링크 - 접속점과 링크 계층 스위치 사이의 이더넷 링크 - 링크 계층 스위치와 라우터 사이의 링크 - 라우터 사이의 링크 - 라우터와 링크 계층 스위치 사이의 이더넷 링크 - 스위치와 서버 간의 이더넷 링크) 한 링크에서 각 노드는 데이터그램을 링크 계층 프레임으로 캡슐화해서 링크로 전송 링크 계층 프로토콜 서비스프레임화: 네트워크 계층 데이터그램을 링크 계층 프레임에 캡슐화.프레임= 데이터그램이 들어있는 데이터필드 + 여러개의 헤더 필드. 링크 계층 프로토콜이 프레임 구조를 명시.링..

5.1 개요제어평면: 네트워크 전체를 아우르는 구성요소, 데이터그램이 송신 호스트~목적지까지 경로상의 라우터들 간에어떻게 전달돼야 하는지 뿐만 아니라 네트워크 계층 구성요소들과 서비스들을 어떻게 설정하고 관리할지 제어.(데이터 평면: 입력링크에서 출력 링크로 데이터 그램 전달) 최소 비용경로 - 라우팅 알고리즘 OSPF(단일 네트워크) BGP(모든 네트워크)원격 컨트롤러 서비스(라우터의 전달기능 요소와 분리된)에서 제어평면 기능을 구현.IP 네트워크 관리의 기본 요소 - ICMP SNMP등등을 다룬다. 목적지 기반 포워딩일 때 포워딩 테이블, 일반화된 포워딩일 때 플로우 테이블을 사용하여데이터 평면과 제어 평면을 연결하였다는 것을 4장에서 다뤘다. 라우터별 제어: 라우팅 알고리즘이 각각의 라우터에서 동작..

4.1 네트워크 계층 개요데이터 평면: 입력 링크 -> 출력 링크 데이터 그램 전달제어 평면: 데이터 그램이 송신호스트에서 목적지 호스트까지 잘 전달되게끔 로컬, 퍼 라우터 포워딩 조절#라우터에선 전송계층, 어플계층을 지원x, 프로토콜 스택에서 네트워크 계층이 최상위 계층 포워딩: 패킷이 라우터의 입력 링크에서 출력링크까지 전달. 라우터에서 나갈 때 막힐 수도,복제되어 여러 링크로 전송될 수도.. 매우 짧은 시간 - 하드웨어 실행라우팅: 송신자-수신자 패킷 전송 시 패킷 경로를 설정. 종단 간 경로이기 때문에 더 긴 시간 - 소프트웨어 실행포워딩 테이블: 라우터가 도착하는 패킷 헤더의 필드값을 조사하여 라우터가 가진 포워딩 테이블의내부 색인으로 사용. 헤더의 값은 해당 패킷이 전달될 라우터의 외부링크 인..

*본문에서 트랜스포트 = 전송 혼동해서 사용*chapter 1,2를 하고보니 너무 많은 볼륨을 다루는 것 같아서 앞으론 핵심적인 내용을 더 간추려 정리할 예정3.1 트랜스포트 계층 서비스 및 개요전송 계층 프로토콜: 어플 프로세스 간의 논리적 통신 제공. 네트워크 라우터가 아닌 종단 시스템에서 구현됨.송신측 전송계층은 송신 어플 프로세스부터 수신한 메시지를 전송 계층 세그먼트인 전송 계층 패킷으로 변환.메시지들을 세그먼트로 만들기 위해 작은 조각으로 분할하여 각 조각에 전송 계층 헤더를 추가함.송신 종단 네트워크 계층으로 세그먼트를 전달하고, 거기서 세그먼트가 네트워크 계층패킷(데이터그램)안에캡슐화되어 목적지로 전달됨.라우터는 데이터그램의 필드에 대해 동작하기 때문에 캡슐화된 전송 계층 세그먼트 필드는 ..

*본문에서 어플리케이션 = 애플리케이션= 어플2.1 네트워크 애플리케이션의 원리여러 종단 시스템에서 실행되는 소프트웨어는 C, JAVA 등으로 작성되는데, 라우터나 링크 계층 스위치와 같이네트워크 코어 장비에서 실행되는 소프트웨어는 작성할 필요가 없다. 어플리케이션 구조: 어플 개발자에 의해 설계되고 어플이 종단 시스템에서 어떻게 조직되어야 하는지를 지시- 네트워크 어플리케이션에 클라이언트/서버구조 혹은 P2P구조를 사용클라이언트-서버 구조: 서버는 항상 켜짐. 클라이언트라는 호스트의 요청을 받음.클라이언트끼린 서로 직접적 통신x, 서버는 고정 IP주소라는 잘 알려진 주소를 가짐.웹, 파일전송, 원격 로그인, 전자메일 등의 어플리케이션들이 있음.하나의 서버로 호스트의 요청을 못 버티는 경우 때문에 많은 ..

1.1  인터넷이란 무엇인가호스트 = 종단시스템종단 시스템은 통신 링크와 패킷 스위치의 네트워크로 연결(ISP)각 링크는 동출 케이블, 구리선 등의 물리 매체로 구성.다양한 전송률(링크 대역폭)을 이용하여 데이터를 전송하고 bps단위를 이용.호스트가 다른 호스트로 데이터 보낼 때 데이터를 세그먼트로 나누고패킷 (= 각 세그먼트에 헤더를 붙인 정보 패키지)을 보내는데 이를 목적지 호스트에서 받아서 원래의 데이터로 조립 패킷 스위치 = 입력 통신 링크로 도착하는 패킷 받아서 출력 통신 링크로 보냄라우터(네트워크 코어)랑 링크계층 스위치(액세스 네트워크)가 있음.패킷이 송~수신 종단 시스템에 도착할 때까지 거쳐 온 통신 링크+ 패킷 스위치들 = 경로 ISP = 종단 시스템이 인터넷에 접속하는 도구. 각  IS..

14.5 개방 주소법 ● 충돌과 오버플로우 충돌: 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상 오버플로우: 충돌이 발생했을 때 해당 해시 주소에 더 이상 빈 버킷이 남아있지 않아 항목을 저장할 수 없는 현상 오버플로우 해결하는 2가지 해결책 1. 개방주소법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장 2, 체이닝: 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조 변경 14.5절에서는 개방 주소법에 대해 다루고 14.6절에서 체이닝을 다룬다. ● 선형 조사법 조사(probing): 해시테이블에서 비어있는 공간 찾기 선형조사법: ht[k]에서 충돌이 발생했다면 ht[k+1]이 비어있는지 확인 후 비어있다면 삽입, 비어있지 않다면 ht[k+2] 확인 조..

14.1 해싱이란? ● 해싱: key에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 직접 접근하는 탐색 - 해시 테이블: 키에 대한 연산에 의해 직접 접근이 가능한 구조 - 컴바일러가 사용하는 심볼 테이블, 철자 검사기, 데이터베이스 등에서 활용 - O(1)의 시간안에 탐색을 마칠 수 있음 14.2 추상 자료형 사전 ● 사전: (키, 값)의 쌍으로, 키와 관련된 값을 동시에 저장하는 자료구조. map이나 table로도 불림 키(key): 사전의 단어처럼 항목과 항목을 구별시켜주는 것 값(value): 단어의 설명에 해당 - 항목들의 위치는 상관없으며 키만 알고 있으면 항목에 접근하고 삭제할 수 있다. - 리스트는 위치에 의해 관리되는 자료구조인 반면, 사전은 오직 키에 ..

01 (3) 02 05(a) 03 (2) 04 100,00,000 경사트리일 경우, 최악의 경우는 O(n) 05(b) 06 07 생략 08 이진 탐색 트리는 정렬되어있지않은 배열을 못받기 때문에 AVL tree를 활용해 정렬시킨 후 해당 트리를 중위순회하며 arr[] 배열에 담아서 정렬한 숫자를 출력하였다. // 위는 AVL Tree code int arr[6]; int k=0; void inorder(AVLNode *root){ if(root !=NULL){ inorder(root->left); arr[k++] = root->key; inorder(root->right); } } int main(){ AVLNode *root = NULL; root = insert(root,30); root = inse..

13.4 이진 탐색 트리 이진 탐색은 자료들이 배열에 저장되어 있어 삽입과 삭제가 힘들다는 단점 존재 이진 탐색 트리는 삽입, 삭제가 빈번한 상황에서 사용 - 이진 탐색 트리는 트리가 균형 트리 일 때 O(log2n)의 시간 복잡도를, 균형 트리가 아닐 때는 최악의 경우 O(n)의 시간복잡도를 가짐 알고리즘 최악 평균 탐색 삽입 탐색 삽입 순차 탐색(정렬x) N N N/2 N 이진 탐색(정렬o) logN N logN N/2 이진 탐색 트리 N N logN logN 모든 항목이 균일하게 탐색된다는 가정 하에 평균 비교 횟수를 비교 좌측 트리와 같은 편향된 경사 트리는 (1+2+3+4+5+6+7)/7 = 4 우측 트리와 같은 균형트리는 (1+2+2+3+3+3+3)/7 = 2.4 따라서 이진 탐색 트리에서는 ..