Campus Coder

목차 Bellman-Ford equation Example Distance vector algorithm Distance vector algorithm 문제점 1. Bellman-Ford equation 데스티네이션까지의 최적 cost에 대해, 소스 노드가 계산한 값과 이웃 노드가 계산한 값을 비교하여 최적 cost를 찾아내는 알고리즘 d_x(y): x에서 y로 가는 최적 경로의 cost d_x(y) = min_v{c(x,v) + d_v(y)} 2. Example d_u(z) = min{c(u,v) + d_v(z), c(u,x) + d_x(z), c(u,w) + d_w(z)} u에서 z로 가는 최적 경로의 cost는 u→v의 cost + v→z의 cost u→x의 cost + x→z의 cost u→w의 ..

목차 Dijkstra's algorithm (다익스트라 알고리즘) Example Oscillation problem (진동 문제) 1. Dijkstra’s algorithm 인접한 노드들 중 최적 경로인 노드를 계속 선택하여 최적 경로 Tree를 만드는 알고리즘 Link status algorithm은 Dijkstra’s algorithm을 기반으로 만들어짐 특징 모든 노드에 대한 비용을 알고 있을 때 사용 가능 각 라우터들이 link state broadcast 하기 때문에 사용 가능 모든 노드가 동일한 정보를 가짐 하나의 노드(source)에서 모든 노드로의 최소 비용 경로 계산 해당 노드에 대한 포워딩 테이블 주어짐 반복적인 작업을 수행한 후 최소 비용 경로를 파악 2. Example c(x,y):..

목차 라우팅 프로토콜 Link status algorithm vs. Distance vector algorithm 1. 라우팅 프로토콜 라우팅 프로토콜 목표: 라우터 네트워크를 통해 송신 호스트에서 수신 호스토로의 최적의 경로를 결정 네트워크의 그래프 추상화 그래프: G = (N,E) N = 라우터 집합 -> {u, v, w, x, y, z } E = 링크 집합 -> { (u,v), (u,x), (v,x), (v,w), (x,y), (w,y), (w,z), (y,z) } c(x,x') = 링크 비용(x,x') -> 예를 들어, c(w,z) = 5 -> 비용은 대역폭, u 또는 혼잡과 역으로 관련될 수 있음 경로 비용(x1, x2, x3,..., xp) -> c(x1,x2) + c(x2,x3) + ... ..

목차 IP(Internet Protocol) Datatgram format Fragmentation IPv4 addressing Network address translation (NAT) IPv6 1. IP (Internet Protocol) 2. Datagram format 3. Fragmentation 네트워크 링크에 MTU(max.transfer size)가 존재 하나의 데이터그램이 여러 개의 데이터그램으로 쪼개짐 최종 목적지에서 재조립 데이터그램 조각을 식별, 순서를 지정하는 IP헤더가 있음 4. IPv4 addressing Introduction IP 주소: 호스트, 라우터 인터페이스의 32비트 식별자 interface: 호스트/라우터와 물리적 링크 간의 연결 라우터는 일반적으로 여러 인터페이..

목차 라우터 구조 Input port Switch fabric Output port 스케줄링 메커니즘 First-in-First-out (FIFO) Priority Round Robin (RR) Weighted Fair Queueing 1. 라우터 구조 Routing control plane - Routing processor 라우팅 알고리즘이 돌아가 포워딩 테이블을 생성 -> 소프트웨어 구현 Forwarding data plane - input port, switch fabric, output port -> 하드웨어 구현 Switch fabric input 포트와 outport의 연결이 얽힌 구조 1-1. Input port input port는 크게 3가지로 이루어져 있음 line terminatio..

목차 Overview of Network layer Data plane Control plane 1. Overview of Network layer 네트워크 계층 전송 계층에서 다른 지역의 호스트까지 데이터를 전송하는 역할 세그먼트를 송신 호스트에서 수신 호스트로 전송 세그먼트를 패킷으로 캡슐화 세그먼트를 전송 계층으로 전달 네트워크 계층은 모든 호스트와 라우터에 구현되어 있음 네트워크 계층의 두 가지 기능 Forwarding: 다수의 input 포트와 output 포트가 있을 때 들어온 패킷를 적절한 output 포트로 보냄 Routing: 소스에서 대상으로 패킷이 이동하는 경로 결정 네트워크 서비스 모델 네트워크 서비스 모델은 송신 호스트와 수신 호스트 간 패킷의 종단 간 전달 특성을 정의 배송 보장..

목차 Congestion Causes & cost of congestion TCP 혼잡 제어 TCP 혼잡 제어 알고리즘 1. Congestion 네트워크에 트래픽(사용량)이 많이 몰리는 상황 혼잡 징후 - lost packets(라우터의 버퍼 오버플로우) - long delays(라우터 버퍼 큐잉 딜레이) flow control vs. congestion control - flow control: 상대방이 데이터를 받을 수 있을 때, 그 범위 내로 데이터를 보내는 것 - congest control: 네트워크 관점에서 데이터가 많아지면 제어하는 것 2. Causes & cost of congestion scenario 1 조건 송신기 2개, 수신기 2개 라우터 1개, 버퍼 크기 무한 링크 출력 성능 R ..

목차 Overview TCP 세그먼트 구조 TCP 시퀀스 번호, ACK RTT(rount trip time), timeout TCP 신뢰성 있는 데이터 전송 TCP fast retransmit TCP flow control TCP Connection Management Syn Flood Attack 1. Overview 2. TCP segment structure 3. TCP 시퀀스 번호, ACK 데이터 스트림의 첫 번째 바이트는 0 TCP가 데이터 스트림에서 500개의 세그먼트 구성 첫 번째 세그먼트에는 시퀀스 번호 0이 할당 두 번째 세그먼트에는 시퀀스 번호 1000이 할당 MMS, MTU: MSS: Maximum Segment Size MTU: Maximum Transmission Unit 시퀀스 ..

목차 신뢰성 있는 데이터 전송 원칙 RDT에 대한 유한 상태 머신(오토마톤) 표현 파이프라인 방식의 고신뢰도 전송 프로토콜 1. 신뢰성 있는 데이터 전송 원칙 a. Provided service 수신자가 메시지를 만들어 세그먼트 단위로 쪼갬 신뢰성 있는 채널로 데이터를 전송 TCP 서비스가 Reliable 한 서비스를 만들어 줌 하지만 현실은 다름, 호스트가 떨어진 원격지에 있기 때문에 전송 계층을 통해 바로 데이터를 전송할 수 없음→ 네트워크 계층을 거처야 함 네트워크 계층은 신뢰할 수 없음 무수히 많은 라우터에 오류가 있을 수도 있고 해커들도 존재 현실적으로 TCP의 신뢰성 있는 서비스는 b와 같은 형태로 이루어짐 b. Service Implementation 애플리케이션은 전송 계층의 TCP 서비스..

목차 UDP (User Datagram Protocol) 전송 계층에 체크섬이 있는 이유 1. UDP (User Datagram Protocol) UDP 특징 UDP 세그먼트 - 손실 가능 UDP 용도 - 멀티미디어 앱 스트리밍(손실 허용, 속도 민감) - DNS(Domain Name Service) - SNMP(Simple Network Management Protocol) UDP를 통한 신뢰성 있는 전송 - 응용 계층에 신뢰성 추가 - 애플리케이션별 오류 복구 필요 정체 제어 없음 - 전송되는 데이터, 시기에 대한 애플리케이션 수준의 세밀한 제어 연결 설정 없음(지연 감소) 단순: 발신자, 수신자에 연결 상태 없음 작은 헤더 크기 UDP 세그먼트 구조 데이터 필드: 애플리케이션 데이터 Length 필..