---

암호기술

암호학적 해쉬 함수

• Cryptographic hash functions

• one-way function: 한방향으로만 입출력(출력값을가지고 입력값을 구하기 어려움)

• 해쉬 함수 특징

  • 1차 역상 저항성(Preimage resistance): output을 가지고 input을 유추하기 어려움

• Avalanche effect

  • 입력값이 1비트 값만 변하더라도 결과값은 전혀 다른값이 됨
  • 암호학적 해쉬 함수 종류
    • MD5, SHA1, SHA256…

• 사용 예: 파일 이미지 확인, 패스워드 생성기

대칭키 암호

• 평문 (Planetext): 암호화 되기 전 메시지

• 암호문 (Ciphertext): 암호화된 메시지

• 구성요소

  • 암호알고리즘: E()
  • 암호화 키: K
  • 암호화(Encryption): EK(P) = C
  • 복호화(Decryption): DK(C) = P

• 대칭키 암호 (Symmetric key encryption)

  • 스트림 암호 (Stream Cipher): RC4, OTP, …
  • 블록 암호 (Block cipher): DES, AES, SEED, …

블록 암호 (Block Cipher)

• 실생활에서 주로 사용되는 대칭키 암호 시스템
• 평문을 고정된 길이의 블록으로 나눈 후, 암호화 과정 진행
  • 암호문 길이 = 평문 길이

대칭키 암호 (DES)

• 1977년에 표준으로 제정
• 2007년에 6.4일만에 해독됨

대칭키 암호 (AES)

• 1997년 NIST가 차세대 암호 표쥰(AES: Advanced encryption standard) 공모
• 벨기에 암호학자들이 제안한 블록 암호 시스템 선정

메시지 인증 코드 (MAC)

• MAC(Message authentication code)

• MAC 구성요소

  • MAC 알고리즘: MAC()
  • MAC Key: K

• MAC을 만드는 방법

  • 블록암호 기반 MAC 알고리즘
  • 암호학적 해쉬 기반 MAC 알고리즘 (일반적)

공개키 암호 시스템

• 공개키 암호(Public key system or Asymmetric key system)

  • 공개키 암호는 한쌍의 키를 가지고 있음

  • 공개키: 외부로 공개하는 키 값

  • 개인키: 자신만 가지고 있는 키 값

  • 수학적 난제를 통해 키를 생성

  • 전자서명 시스템에 자주 사용

네트워크와 암호

Backgrounds

• Link encryption

  • 암호화가 모든 링크에서 독립적으로 수행
  • 모든 링크간의 사전에 공유된 암호화 키 필요

• End-to-End encryption

  • 암호화가 시작점과 도착점에서 수행

End-to-End 암호화

• 헤더부분(e.g., IP address)은 암호화 되지 않음

  • 헤더정보를 통해 인터넷 패킷들을 라우팅
  • 헤더정보가 암호화되지 않으므로 traffic 흐름 노출
    • End-to-End에서는 A와 B가 통신하고 있다는 사실 노출

• 그래서 End-to-End와 Link 암호화 동시에 사용되기도 함

  • End-to-End 암호화: 데이터 보호
  • Link 암호화: traffic 흐름 숨김

• 둘다 대부분 대칭키 암호 사용 (e.g., AES)

  • 비대칭키 암호(공개키 암호)는 주로 암호화 키 교환(혹은 인증)에 사용

SSL/TLS 프로토콜 구조

• SSL/TLS 프로토콜은 클라이언트와 서버의 통신에 메시지 인증, 기밀성, 가용성 제공

• 암호화 되지 않은 패킷 (e.g., HTTP)는 SSL패킷으로 인코딩 되면서 암호화 진행 (HTTP SSL)

구조

• Handshake protocol

  • 암호화/인증 통신을 위해 사용할 알고리즘의 종류 그리고 암호화/인증 키에 대해 협의

• ChangeCipherSpec protocol

  • Handshake 프로토콜을 통해 교환된 정보들을(e.g., 암호 알고리즘 종류, 암호화 키) 확인

• Alert protocol

  • TLS 괒어 중에 발생하는 에러 혹은 비정상적인 상황을 리포트

• Record portocol

  • TLS에서 전송되는 상위 레이어의 메시지 처리

IPsec

• IPSec(Internet Protocol Security): SSL과 달리 네트워크 계층에서 보안을 제공하기 위해 IETF(Internet Engineering Task Force)에 의해 표준화된 프로토콜

• 왜사용?

  • 어플리케이션 레이어에서 보호 안될수도
  • UDP 사용할수도

Transport mode vs. tunnel mode

전송모드 (Transport 모드)

• IPSec의 기본 모드, end-to-end 보안 제공
• IPSec에서 전송모드가 사용되면 IP데이터영역만 보안 처리함으로써 IP데이터 영역을 보호
• IP헤더는 보호X

터널모드 (Tunnel 모드)

• IP패킷 전체를 보호
• 헤더영역도 보호함
• 트래픽 흐름 보호 가능

TLS vs. IPSec

• SSL/TLS

  • transport layer에서 제공
  • 일반 보안통신에 주로 사용

• IPSec

  • network layer에서 제공
  • 특수 보안통신(e.g., VPN)에서 주로 샤용

VPN(Virtual Private Network)

Tor (The Onion Router)

• Onion Routing 기반

---

네트워크 트래픽 분석과 악성코드

• 악성코드를 분석하는데 네트워크 트래픽 분석이 왜 필요할까?
  • 악성코드는 네트워크 기술이 발달함에 따라 배포 및 명령 전달이 용이해짐
  • 86년도부터 급격히 증가한 배경은 인터넷 기술의 발전
  • 출현개수와 새로운 종의 출현은 인터넷 보급속도와 유사하게 증가

인터넷을 통한 악성코드 감염 경로

• 인터넷 브라우저
• 불법 크랙 프로그램
• 피싱/파밍
• 외부 문서의 매크로

파악

• 네트워크 트래픽 분석을 통해 악성코드의 정확한 행위를 파악 가능

  • 대부분 악성코드는 네트워크 사용
  • DDoS 공격을 위한 좀비 PC를 모으거나, 특정사용자 파일 감시, 악의적인 파일 암호화등의 악성행위는 네트워크가 필요한 경우가 많음

• 네트워크 트래픽을 통한 악성코드 통신 차단 기능

  • 방화벽을 통한 의심 ip, 포트 차단
  • Intrusion Detection System(IDS)를 통한 네트워크 공격 탐지 및 Intrusion Prevention System (IPS)를 통한 네트워크 트래픽 차단

보안 관점에서 바라본 OSI 7계층

• L2: MAC
• L3: IP
• L4: 프로토콜(TCP/UDP)
• L7: 페이로드

L2 계층

• 데이터 링크 계층으로 MAC과 가장 관련이 깊음
• Source MAC주소와 Destination MAC 주소를 보고 Switch에서 차단 가능

L2 방화벽

• L2와 가장 관계가 깊은 보안 시스템은 방화벽

• 일반적으로 방화벽의 경우 최소 2개 이상의 NIC 필요

• 장점

  • L2 방화벽을 설치 할 때 일반적으로 네트워크 디자인을 바꾸지 않아도 됨

• 단점

  • 동일한 네트워크 안에서만 가능, 다양한 네트워크 환경에는 적용 불가능

L3 계층

• 네트워크 계층으로 IP 주소와 연관 있음

• 하나의 네트워크 장비(e.g., 방화벽)를 통해 여러개의 네트워크 망을 구성

  • NAT와 VLAN기술 필요

L3 방화벽

• 장점

  • L2 방화벽에선 하지 못했던 좀 더 다양한 접근 제어 가능
  • NAT과 VLAN 활용

• 단점

  • L3 방화벽을 설치할 때 일반적으로 네트워크 디자인을 바꿔야 할 수도 있음

L4 계층

• 전송계층
• 패킷을 포트수준까지 확인

L7 계층

• L5는 세션계층, L6는 표현계층, L7은 응용계층
  • 요즘에는 L5,6,7을 통틀어 L7이라 부르기도 함
• L7 방화벽에서는 패킷 페이로드를 활용하여 운용 가능

방화벽

• 하드웨어 기반 방화벽: 여러대의 PC와 서버를 커버함
• 소프트웨어 기반 방화벽: 설치된 host PC만 보호

방화벽: 1세대 방화벽

• 패킷 필터링 기반의 1세대 방화벽

  src IP	dst IP	src Port	dst Port	Control
  any	1.1.1.1	any	80	permit

• 80포트 listen

• 80포트에 대한 접근 허용(HTTP 포트)

• 무수히 많은 룰을 셋팅해야함

• 80번 포트를 열때 나가는 포트에 대해 많은 포트를 열어줘야함

  • 룰관리 이슈
  • 포트 개방에 따른 이슈

방화벽: 2세대 방화벽

• Stateful Inspection: TCP 접속 시 방화벽에서 패킷의 payload를 보면서 3way handshake의 state 추적, rule을 자동으로 추가

• 장점:

  • Response 패킷에 대한 룰을 불필요하게 작성할필요 없음
  • 동작하는 동안 checksum도 계산, 잘못된패킷은 폐기 가능

방화벽: 3세대 방화벽

• L7 방화멱 또는 애플리케이션 방화벽

• 실제 패킷 내용 검사, 단순한 포트/IP 조사뿐만 아니라 어떤 애플리케이션과 통신하고있는지 파악

  • 2세대 방화벽: 80/443 허용이나 차단 가능
  • 3세대 방화벽: 페이스북 차단, 인스타 허용같은 룰 가능

• L2, L3, L4 모두 커버 가능하지만 성능 이슈로 L7에 집중하기도 함

  • 범용적인 서비스보단 오피스용

방화벽 구성

• Intranet: 직원 내부망
• 서비스대역(DMZ): 네트워크 중립지역, 외부에 서비스를 제공할때 내부 네트워크와 분리시킨 공간

A구간: 외부에서 서버 접속 (서비스 대역으로 오는 접속)

• 외부로 공개된 웹서버가 존재하면, HTTP(80), HTTPS(443) 포트 허용
• 그밖의 모든 포트 차단 (E.g., RDP(3389), SSH(22))

B구간: 내부망에서 서버로 접속

• 내부망에 존재하는 엔지니어들을 위해 다양한 제어 포트를 열어둠
• E.g., HTTP(80), HTTPS(443), SSH(22), RDP(3389) 등

C구간: 서버에서 외부망 접속

• 서버 패치를 위해 Linux Repository 접근 허용
• 일반 사이트는 접속 불허용!

D구간: 내부망에서 외부망으로 접속

• 서버 패치를 위해 Linux Repository 접근 허용
• 파일 유출 방지를 위해 구글드라이브, 네이버 드라이브 불허용
• 악성코드 감염 방지를 위해 악성 사이트 접근 불허용

High Availability (HA)

• High Availability: 2대의 방화벽을 통해, 1개의 방화벽에 장애가 생길경우를 대비

• 한대는 온라인 상태, 한대는 대기/레디 상태 (Active-Standby)

• 두개가 항상 온라인 상태 (Active-Active)

바이패스 스위치

• 방화벽에 장애가 생겼을 경우, 우회경로 만들어줌
• 보안보다 서비스가 중요하다고 판단될 경우

Full Mesh

• 네트워크 장비를 2대 이상 준비한 후, 모두 연결

방화벽 룰 관리

• 오래된 룰은 정기적으로 확인 후, 필요없는 경우 해당룰을 지워줌
• 룰이 겹치지 않도록 튜닝하는것도 필요

---

침입탐지시스템

탐지 방법

• Signature 기반 공격 탐지

  • 악성 공격의 일정한 패턴(Signature)을 탐지 룰에 추가함으로 공격을 탐지
  • 알려지지 않은 공격을 탐지하지 못함
  • 한계를 극복하기 위해 Anomaly 기반 공격 탐지가 설계됨

• Anomaly 기반 공격 탐지

  • 비정상적인 트래픽이 발생하면 공격으로 감지
  • E.g., 평소 IP주소당 최대 1Mbps, 어느날 20Mbps? 공격이다!
  • 오탐존재

Signature 기반 공격 탐지

• IDS는 다음과 같은 탐지 룰을 기반으로 작동

  1 2	Alert tcp any any -> any any (msg: "LoCAL-RULE Test for TestMyIDS"; content: "testmyids.com"; classtype:misc-activity; sid:1000001;rev:1;)

• 알람 조건
  • Source ip 주소와 Destination ip 주소 any any
  • Source port number와 Destination port number any any
  • Payload에 “testmyids.com” 문구 포함

Anomaly 기반 공격 탐지

• IPS 트래픽을 학습하는 방법: 다양한 Machine learning 기반 방법

IDS 종류

• NIDS (Network-based IDS)

  • 네트워크 인프라를 기준으로 동작하는 IDS

• HIDS (Host-based IDS)

  • Host를 관리하는 상황헤서 동작하는 IDS

• 장점

  • NIDS: 네트워크 전체를 한군데서 분석 가능
  • HIDS: Host별 상세 분석 가능, 사용자단위 분석도 가능

• 단점

  • NIDS: IDS를 경우한 공격만 확인 가능, 암호화된 트래픽도 못봄
  • HIDS: 개별로 관리해야함

NIDS

• 탐지 위주 정책, 인라인으로 들어가지 않음(따로 삐져나와있음)

  • 장애를 예방하기위한 이중화 구성이 필수가아님
  • NIDS에 장애가 발생해도 네트워크 로그의 저장이 필요하면 이중화구성 해야함(Backup 장비 이용)

• NIDS에 필요한것: 전체 네트워크 패킷

  • 네트워크 패킷을 복사해서 IDS로 전송
  • Cisco에서는 트래픽복사하는 행위를 SPAN(Switch Port Analyzer)
  • 대부분의 스위치가 SPAN or 포트미러링 제공

• HIDS의 경우 호스트 네트워크 패킷, 시스템 로그 필요

포트 미러링

• 스위치 환경에서 포트 미러링을 통해 스니핑(패킷 엿듣기) 제공

  • 스위치 환경에서 패킷 분석을 위해 스위치포트에 스니퍼 연결

• 스위치가 포트미러링을 지원, 스니퍼를 연결하기 위한 포트가 있어야함

  • 포트 미러링을 할 때 미러링하는 포트의 처리율을 알아야 함.

HIDS

• HIDS 필요한것: 호스트 네트워크 데이터 + 시스템 로그 데이터

• utmp(x) 로그

  • utmp 데몬: utmp(x) 파일에 로그 남기는 프로그램
  • utmp 데몬은 리눅스의 가장 기본 로깅을 제공하는 데몬
    • 현재 시스템에 로그인한 사용자의 상태 출력
  • utmp 데몬에 저장된 로그를 출력하는 명령: w, who, users, whodo, finger 등
    • w: 현재 시스템에 로그인된 계정, 셸종류, 로그인시간, 실행중인 프로세스 종류
    • who: 접속한 시스템의 IP 확인

• wtmp(x) 로그

  • wtmp 데몬: wtmp(x) 파일에 로그 남김, /usr/include/utmp.h 파일 구조체 사용
  • utmp데몬과 비슷한 역할, 사용자들의 로그인,로그아웃,재부팅 정보 수록
  • last명령 이용

• su(switch user) 로그

  • 권한 변경에 대한 로그
  • cat /var/adm/sulog

• pacct 로그

  • 시스템에 로그인한 모든 사용자가 수행한 프로그램 정보 저장
  • acctcom 명령 이용
    • root 계정으로 vi에디터 실행한 기록: acctcom -u root -n vi

• lastcomm명령: 실행된 날짜 출력

리눅스 로그 분석과 설정

• syslog

  • 시스템의 로그 정보를 대부분 수집해서 로깅
  • 로그종류와 수준은 /etc/syslog.conf 파일

• authlog/loginlog

  • 실패한 로그인 시도에 대한 로깅 (loginlog 파일에 저장)
  • 설정: etc/default/login, 재부팅후 적용

IDS vs. IPS

• Intrusion Detection System

• Intrusion Prevention System

• IDS는 공격에 대한 블록기능 X, 탐지만 하는경우가 많음

	IPS	IDS
시스템 타입	액티브(모니터링, 차단까지)	패시브(모니터링, 경고)
매커니즘	Anomaly based detection\nSigniture detection	Anomaly based detection\nSigniture detection
위치	Inline형태로 설치	Out of band
대응방법	경고를 주거나 패킷을 Drop	알람 보냄
퍼포먼스 영향	패킷속도에 저하가 생길 수 있음	복사해서 분석하기 때문에 퍼포먼스적 영향 X
benefits	자동화되고, 방지도 되기 때문에 회사에서 선호	IPS가 차단할 합법적인 traffic을 차단하지 않음

---

Link layer: Introduction

• data-link layer: datagram을 서로 인접한 노드간에 전달해주는 책임을 가지고 있는 레이어

• Links: 인접한 노드들을 따라서 communication channels를 연결

  • wired links
  • wireless links
  • LANs

• Layer-2 packet: frame

  • Encapsulates datagram (데이타그램 캡슐화)

Link layer services

• Framing: datagram을 frame로 만들고, header와 trailer를 붙임

• Link access: share해서 사용할때 어떻게 나눠쓸건지 결정

  • “MAC” address in frame headers, source와 destination을 식별하는데 사용됨
    • IP address와 다름

• 인접한 노드 사이에 신뢰성있는 데이터 전송

  • Wireless links: error가 많음
  • 드물게 low bit-error link 사용

• Error detection: 신호 감소, 노이즈에 의한 에러 감지

• Error correction: receiver는 retransmisson에 의존하지 않고 비트오류를 식별한후 수정함

Link layer 구현되있는 곳?

• Network interface 카드
• Adaptors

Adaptors communicating

• sending side: datagram 캡슐화, frameing

• error checking bits, rdt등등 추가

• receiving side: 에러, rdt등등 확인

• 문제가 없으면 datagram를 추출해서 위로 보냄

Error detection

• EDC = Error Detection and Correction bits

• Error detection 100% 신뢰되진 않음

• 하지만 거의 놓치지 않는다

• EDC가 커질수록 detection과 correction이 쉬워짐

Parity checking

• single bit parity: detect single bit errors

  • parity bit에 1의 개수가 짝수인지 홀수인지 확인

• two-dimensional bit parity: detect and correct single bit errors

• Row와 column에서 짝수 개수 확인, 에러 correction 가능

Checksum: 에러를 체크하는데 사용되는 함수 통칭

• Sender send Msg with Checksum Value(CV)
• Receiver check CV with Checksum

Checksumming Methods

• Cyclic redundancy check (CRC)

  • error-detection coding으로 더 powerful

  • d bits(Data bits) + r bits(CRC bits)

  • CRC bits: D*2^r % G

Multiple access links, protocols

• 두가지 타입의 network links:
  • point-to-point link: single sender, single receiver
  • broadcast link (shared wire or medium): multiple sending and receiving

Multiple access protocols

• single shared broadcast channel

• 노드들에 의해서 동시에 데이터를 보낼 수 있어야함: interference

  • node가 동시에 signal을 보내려 하면 collision 발생

• Multiple access protocol

  • node들이 channel을 share 하고 있을 때 어떤 노드가 먼저 보낼지 결정
  • 알고리즘은 모든 노드들에게 분산된 상태에서 구동되야함
  • Channel sharing에 관한 communication은 channel 자체를 사용해야함
    • 조정을 위해 out-of-band channel 사용하면 안됨

Multiple access protocol에 대한 이상적인 상황

• Given: broadcast channel of rate R bps

• 원하는 특성

  1. 하나의 노드가 데이터를 쓸 때, sending rate: R
  2. M개의 노드와 share할 때, send average rate: R/M
  3. Fully decentralized(완벽한 탈중앙화):
  • transmission을 조정하는 특별한 노트 X
  • 네트워크 시간동기화 가정 X
  4. simple

MAC (Media Access Control) protocols

• Three broad classes:
  • channel partitioning
    • 채널을 작은 “조각”단위로 쪼개서 사용(time slots, frequency, code)
  • random access
    • 채널을 나누지 않고, 충돌이 일어나면 random한 delay로 대기
  • “taking turns”
  • 번갈아가면서 사용, 공평하지만 비효율적

Channel partitioning MAC protocols: TDMA

• TDMA: time division multiple access
  • 시분할방식, 시간을 n-slot으로 나눠서 사용
  • 노는 slot이 생길 수 있으므로 비효율적

Channel partitioning MAC protocols: FDMA

• FDMA: frequency division multiple access
  • 주파수 간격으로 데이터를 쪼갬

Random access protocols

• node가 패킷을 보낼 때

  • 전체 채널 send rate R 사용
  • 노드간의 사전 조절은 X

• 두개 이상의 노드가 동시에 사용하면 -> collision

• Random access MAC protocol 특징:

  • 어떻게 충돌을 detect 할건지
  • 충돌이 일어났을 때 어떻게 recover 할 건지 (e.g., via delayed retransmissions)

• Examples of random access MAC protocols:

  • slotted ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

Random Access protocols: Slotted ALOHA

• 가정

  • all frames same size
  • 동등한 사이즈로 쪼갠 time divided slots
  • node가 slot 시작시간에 바로 transmit을 할 수 있음
  • 모든 노드들은 동기화 되있음
  • 2개 이상의 node가 하나의 slot에서 데이터를 보내려 하면, 모든 nodes가 충돌을 detect

• 작업

  • 노드가 새로 보내야되는 frame이 있으면, 다음 slot에 transmits
    • if no collision: node는 새로운 frame을 다음 slot에 보낼 수 있음
    • if collision: node는 prob.p slot으로 retransmits, 성공할 때까지

• Pros:

  • single active node라 transmit 을 full rate로 사용가능
  • simple

• Cons

  • collisions, slot 낭비
  • 대기 슬롯
  • 시간 동기화

Random access protocols: CSMA

• CSMA (carrier sense multiple access): transmit 하기 전 누가 사용하는지 확인

  • if channel sensed idle: transmit entire frame
  • if channel sensed busy, defer transmission

• 대화하는데 끼어들지 않기

Random access protocols: CSMA collisions

• Collision이 발생할 수 있음

  • propagation delay(전파 지연)

• Collision

  • 패킷을 전부 보낼 때까지 시간 낭비됨

Random access protocols: CSMA/CD

• CDMA/CD (collision detection)

  • 짧은 시간에 collisions detected
  • 충돌된 transmission 중단, channel wastage 감소

• collsition detection:

  • easy in wired LANs: 신호 강도 측정, transmitted 비교, received signals
  • difficult in wireless LANs: 신호 왜곡이나 수신강도로 판단하기 어려움 (CSMA/CA 사용)

• 예의 바른사람(끼어들어도 봐줌)

• 구성

  1. NIC(Network Interface Card)가 datagram을 network layer로부터 받고 crates frame
  2. If NIC senses channel idle, frame transmission 시작, If NIC senses channel busy, channel이 idle 될때까지 대기후 tranmits.
  3. 만약 NIC가 다른 transmission의 방해 없이 transmit되면, 전송이 성공적으로 마무리됨
  4. 만약 NIC가 또다른 transmission detects하면, send를 abort(중단)함
  5. After aborting, NIC enter binary(exponential) backoff:
  • n-th의 collision이 발생하면, NIC는 {0, 1, 2, …, 2^n-1}중에 K를 랜덤하게 선택, NIC waits K*512 bits times, returns to Step 2
  • Longer backoff interval은 많은 collision이 있는것

Taking turns

Taking turns: polling protocol

• master node에서 slave nodes에게 순서대로 transmit을 invites해줌

  • 일반적으로 “dumb”한 slave devices에서 사용

• concerns(우려사항):

  • polling overhead
  • latency
  • single point of failure (master가 오류가 나면 전부 사용하지 못함)

Tacking turns: token passing

• 토큰 메시지가 한 노드에서 다음 노드로 순서대로 전달됨

• concerns(우려사항):

  • polling overhead
  • latency
  • single point of failure (token이 오류가 나면 전부 사용하지 못함)

---

Switched local networks

• 3개 학과, 2개 서버와 4개의 스위치 라우터
• 스위치들은 link-layer에서 동작
  1. link-layer frame으로 동작(L2 switch)
  2. network-layer address 인지못함
  3. routing algorithm 사용 못함(요즘은 됨)

MAC address and ARP

• 32-bit ip address:

  • Network-layer 에서 사용하는 주소
  • layer 3에서 forwarding하는데 사용

• MAC(or LAN or physical or Ethernet) address:

  • locally하게만 사용, 한 인터페이스마다 고유한 주소
  • 48 bit MAC address, NIC ROM에 고정되있음
  • e.g. 00:d0:ca:1c:f0:ed (3bytes: 제조업체 식별정보, 3bytes: 시리얼 넘버)

• 데이터를 보낼 때 보내고자하는 Destination MAC 주소를 사용

• Broadcast address (FF:FF:FF:FF:FF:FF)

MAC address (more)

• MAC address는 IEEE에서 관리

• 비유:

  • MAC address: 주민등록번호
  • IP address: 우편주소

• MAC flat address -> 휴대성

  • LAN카드만 옮기면 됨

• IP hierarchical address not protable

  • IP subnet때문에 휴대성 부족

ARP: address resolution protocol

• 모든 PC들은 network-layer address(IP주소)와 link-layer address(MAC주소)를 같이 가지고 있음
  • 두 addresses 사이에 translate 필요

ARP table

• 각 IP node들은 ARP table을 가지고 있음
• ARP table 구성: <IP address, MAC address, TTL>
• TTL(Time to Live): mapping이 유지되는 시간(일반적으로 20min)

ARP protocol: same LAN

1. A는 Local에 있는 B에게 datagram을 전송하고 싶어함

• A의 ARP table에는 B의 MAC address가 존재하지 않음

2. A가 ARP query packet을 만들어서 B의 IP address를 포함한 후 broadcast해줌

• Destination MAC address = FF-FF-FF-FF-FF-FF
• All nodes on LAN receive ARP query

3. B가 ARP packet 받음, A에게 자신의 MAC address 회신

• A의 MAC address로 unicast

4. A caches IP-to-MAC address를 pair로 ARP table에 저장

• ARP is “plug-and-play”

Addressing: routing to another LAN

• A에서 R을 거쳐 B로 datagram send

1. create IP datagram with IP source A, destination B
   link-layer frame의 destination address를 R의 MAC address로 전송
2. frame sent from A to R
   R에서 frame 수신, datagram removed, passed up to IP
3. R에서 IP source A, destination B로 datagram forward
   link-layer frame의 destination address는 B의 MAC address, source는 R
   회신도 같은 구조

Ethernet

• wired Lan technology의 표준:

  • 먼저 널리 사용된 LAN technology
  • 간단하고, 저렴함
  • 성능도 좋음

• bus: 90년도까지 사용

  • 모든 노드는 same colision domain (서로 충돌할 수 있음)

• star: 오늘날 사용

  • 중앙에 스위치 활성화
  • 각각 direct로 사용

Ethernet frame structure

• Sending adapter는 Ethernet frame에 IP datagram을 캡슐화

• Preamble (8bytes)

  • 정해져있는 패턴
  • 시작점을 포착하기 위함, 동기화용

• Addresses (6bytes)

  • source, destination MAC address

• Type (2bytes)

  • higher layer protocol을 나타냄 (주로 IP)

• Data field (46 to 1,500 bytes)

  • IP datagram 포함
  • 이더넷의 MTU(Maximum transmission unit)이 1,500 bytes로 정해짐

• CRC (4bytes)

  • Error detected

Ethernet: unreliable, conntectionless

• Connectionless (연결없음)

  • no handshaking betwween sending and receiving NICs

• Unreliable (신뢰하지 않는)

  • NIC는 acks랑 nacks를 보내지 않음

• initial sender가 higher layer rdt(e.g., TCP)를 사용하는 경우에만 dropped된 frames를 recovered해주고, 그외에는 데이터를 버림

• Ethernet’s MAC protocol

  • unslotted CSMA/CD with binary backoff

---

Link-layer Switches

• Link-layer device: takes an active role

  • switch의 역할: 받은 패킷을 다른쪽 links로 forawrd 해주는 역할

• transparent(투명함)

  • host는 switches의 존재를 알아차리기 어려움
  • forwarding만 해주기 때문

• plug-and-play, self-learning

Filtering과 forwarding

• Filtering: Switch function이 하는 역할, frame을 어디로 보내야할지, drop시켜야할지 결정
• Forwarding: Filtering에서 보내져야할 패킷이라고 결정되면, Input port에 따라서 어느 output port로 보내야할지 결정

Switch: multiple simultaneous transmissons

• 각 호스트는 switch와 개별로 연결되있음
• 동시에 들어와도 collision이 발생하지 않음

Switch: self-learning

• 스위치는 어떤 인터페이스를 통해 어떤 호스트로 갈 수 있는지 학습

  • frame을 가져오면, 스위치는 sender의 주소를 “학습”: 들어오는 LAN segment

  • sender/location pair 을 switch table에 기록

  • frame destination을 모르면, broadcast

  • reply 받으면 기록

Switches vs. Routers

• 둘 다 store and forward:

  • routers: network-layer devices
  • switches: link-layer devices

• 둘 다 forwarding table 존재:

  • routers: IP주소 기반
  • switches: MAC 주소 기반

• 하지만 최근엔 L3 switches 사용

VLAN (Virtual Local Area Network)

• single broadcast domain:

  • all layer-2 broadcast traffic
  • security/privacy, efficiency issues

• Virtual Local Area Network: broadcast domain을 나누어주는 역할

• 1개의 switch를 가상으로 2개의 switch가 있다고 생각할 수 있도록 만들어줌

• 라우터를 이용하여 VLAN끼리 통신

• trunk port: 여러개의 물리적인 스위치에 정의된 VLAN간에 프레임 전달

Summary: A day in the life of a web request

1. DHCP로 IP주소를 받아옴
2. ARP로 DNS서버 접근, 주소를 받아옴
3. TCP connection(3-way handshaking)
4. HTTP request를 보냄, reply 받음
5. 웹페이지 열림

---

Network-layer function

• Forwarding: 여러개의 패킷을 매칭되는 output 포트로 연결시켜주는 역할

• Routing: 포워딩한 패킷들이 정해진 목적지까지 가는것

• 예시: 여행

  • 포워딩: 교차로에서 어디로갈지 결정
  • 라우팅: 출발점에서 도착점까지 어떤 경로로 갈지 정하는것

Data plane

• router input port로 어떠한 데이터가 왔을 때 output port로 포워딩을 해주는것을 결정하는 역할

control plane

• datagram이 왔을때 어떤경로로 routing 해줄지 결정

• 2가지 control-plane approaches:

  • traditional routing algorithm: 패킷에서 최선의 결정으로 라우팅
  • software-defined networking(SDN): 중앙에서 소프트웨어적으로 라우팅을 변경해줌

Tanditional Approch

• Routing Alogrithm: forwarding table을 만들어줌 (control plane)
• table로 forwarding 시켜줌(data plane)

SDN

• 중앙서버에 RemoteController 존재.
• 각Router에 Control agents로 컨트롤

Router architecture

Input port functions

• line termination: 아날로그신호 -> 디지털
• link layer protocol: link layer에서 작업

decentralized switching

• lookup: 어느 output port로갈지 결정
• forwarding: output 출력 port 설정
• queueing: 나가는 속도보다 들어오는 속도가 빠르면 queueing

destination-based forwarding:

• 패킷에서 destination 해더 정보를 보고 어디로 보낼지 결정

generalized forwarding:

• 헤더의 여러 정보들을 보고 결정
• 특수한 경우에만 사용

Switch fabric

• 경로들이 엉킬수도 있음 (fabric: 직물)

destination-based forwarding

• destination IP Address 주소를 기반으로 어떤 Output Port로 데이터를 보낼 것인지를 결정하는 forwarding algorithm

longest prefix matching

• 원하는 부분만 정하고 나머지부분은 와일드카드로 설정하는 방법

Switching

• Switching fabric: 라우터의 핵심
• memory: 과거방식, 패킷을 받고 메모리에 보관후 포워딩 테이블을 보고 보냄, 인터럽트 기반.
• bus: 레이블을 붙여서 버스에 보냄, 자신의 레이블이면 받아서 처리, 아니면 드롭
• crossbar: interseption마다 on off 스위치 있음

Input port queueing

• Head-of-the-Line(HOL) blocking: 앞선 패킷(head)이 나가지 않았을 때 뒤에있는 패킷들도 계속 기다리는 현상

Output port queueing

• line termination에서 보내는 속도가 switch fabric에서 들어오는 속도보다 느릴 때 datagram buffer에서 queueing 발생
• scheduling discipline: 우선순위 기발 패킷 스케쥴링

Schedule mechanisms (스케쥴링 매커니즘)

• FIFO 스케쥴링: 먼저 들어온 패킷을 먼저 보냄(FCFS)

priority scheduling (우선순위 스케쥴링)

• 여러개 큐중 우선순위가 높은 큐의 패킷부터 전송
• 우선순위가 낮은 큐는 끝없이 밀릴 수 있음: 가중치를 줘서 우선순위를 가변적으로 만듬

Round Robin (RR)

• 각 클래스마다 한번씩 보냄

Weighted Fair Queueing (WFQ)

• Round Robin 방식에서 사용
• 각 클래스에 사이클의 weight를 줌

---

Internet network layer

• routing protocols -> forwarding table
• IP protocol

IP fragmentation, reassembly

• network links have MTU(max transfer size)
• fragmentation: 큰 패킷이 MTU때문에 작게 쪼개지는것
• reassembly: 쪼개진 패킷들을 합치는것 (final destination에서만 이루어짐)

example

• 4000byte datagram
• MTU = 1500bytes

1. length: 1500(1480 data field) / ID = x / fragflag = 1 / offset = 0
2. length: 1500(1480 data field) / ID = x / fragflag = 1 / offset = 185(1480/8)
3. length: 1040(1020 data field) / ID = x / fragflag = 0 / offset = 370

IP addressing

• ip address: 32-bit

• interface: host/router와 physical link 사이의 connection

• router: multiple interface

Subnets

• 높은 주소 비트: subnet part

• 낮은 주소 비트: host part

• ex: 233.1.1.0/24 (subnet mask: /24): 총 24비트(233.1.1)이 서브넷

IP addressing: classful addressing

• IP주소는 8, 16, 24비트 단위로 쪼개짐

classful addressing 문제

• class C(/24)를 보면 2^8 - 2 = 254개의 호스트만 사용가능 (기업에선 매우 작은 숫자)
• 그렇다고 class B(/16)을 사용하면 65,634개로 너무 많음

IP addressing: CIDR

• CIDR: Classless Inter Domain Routing

• 서브넷 임의의 길이

• address format: a.b.c.d/x, x는 서브넷을 의미하는 비트의 길이

• Broadcasting address: 255.255.255.255

IP addresses: how to get one?

• hard-coded by system admin in a file
• DHCP(Dynamic Host Configuration Protocol): 동적으로 서버에서 주소를 가져옴
  • plug and play

DHCP client-server scenario

1. DHCP discover: client broadcast로 DHCP 서버가 있는지 물어봄
2. DHCP offer: DHCP 서버가 broadcast해줌

• yiaddrr: your Internet address (너가 쓸 인터넷 주소)

3. DHCP request: yiaddrr 사용하겠다고 broadcast 해줌
4. DHCP ACK: 사용해도된다 허락해줌

ISP: Internet Service Provide

• ISP’s block: 200.23.16.0/20
• Organization 0: 200.23.16.0/23
• Organization 1: 200.23.18.0/23
• …
• Organization 7: 200.23.30.0/23

Q: ISP는 어떻게 address를 가져오나?
A: ICANN: Internet Corportaion for Assigned Names and Numbers

NAT: network address translation

• local network에서 내부 서브넷으로 통신(10.0.0/24)
• 외부로 나갈때는 외부에서 쓸 수 있는 주소로 바꿔줌 (138.76.29.7)
• 반대도 수행

---

용어 정리:

• 공인 IP 주소 (public IP address)

  • 전 세계적으로 고유한 주소 (예: 서울시 동작구 상도동 정보과학관 102호)

• 사설 IP 주소 (private IP address)

  • 주소가 고유하지 않음 (예: 624호)
  • 사용 예:
    • 공유기에 공인 IP 할당 후, 공유기에 연결된 다수의 컴퓨터에 사설 IP 할당

• 공인 IP와 사설 IP를 변환해주는것: NAT

NAT: network address translation

• 사설 네트워크를 구축하면 특정 IP range를 ISP로부터 사올 필요 없음
  • 모든 device에 하나의 IP
• 내부 사설 IP가 바뀌어도 외부에 통보필요x
• 내부 IP를 바꾸지 않고 ISP 변경 가능
• 외부에는 고정IP주소만 공개되기 때문에 보안적으로도 좋음

NAT implementation(구현)

1. source: 자신의 사설IP와 임의의 PORT NUMBER
2. NAT tranlation table 에 기록후 source change
3. destination에서 도착하면 table을 보고 맞는 destination으로 보내줌

IPv6

motivation (동기)

• 32비트 공간은 결국 부족해질것이다.
• IPv4의 format header에서 쓸모없는게 너무 많음 speed 증가시키기 위해
• QoS(Quality of Service)를 증가시키기 위해

IPv6 datagram format

• Traffic class: datagram의 priority(우선순위)를 주기위한 field
• Flow Label: datagram의 flow가 같은 flow 인지 identify(식별)
  • flow 개념이 정확하게 정의되지 않았음
• Next header: upper layer protocol의 정보를 기입할때 사용(tcp/udp)

IPv4 비교

• Checksum: 속도를 올리기 위해 빠짐
• Options: 필요하면 “Next header” 활용
• ICMPv6: new version of ICMP
  • 새로운 메시지 타입, e.g. “Packet Too Big”
  • MTU가 지원하지 않는 패킷이 도착하면, 버리고 다시 작게 보내라함

Transition from IPv4 to IPv6

• 모든 라우터가 동시에 업그레이드 할 수 없음

  • “flag days”가 없음

• tunneling: IPv4 dataram payload에 IPv6 datagram을 담는다.

---

Network-layer functions

• two network layer functions:

  • Forwarding: 라우터의 input에서 패킷을 라우터의 output으로 옮기는 역할

  • Data Plane

  • Routing: 전체 경로 결정 source to destination

  • Control Plane

• two approaches to structuring network control plane:

• 라우터마다 컨트롤(traditional)

• 중앙기관에서 컨트롤(Software defined networking)

Routing protocol

• Routing protocol goal: “good” paths 결정

Graph abstraction of the network

• Graph: G = (N,E)

• N = set of routers = {u,v,w,x,y,z}

• E = set of links = {(u,v), (u,x), (v,x) …}

• c(x, x’) = cost of link(x, x’)

  • cost는 bandwidth와 역관계
  • congestion와 역관계

• cost of path(x1, x2, x3, …, xp)

  • c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

Key question: u에서 z까지 얼마나 적은 코스트를 사용하여 이동할 수 있는가?
Routing alogrithm: source에서 destination까지 얼마나 효율적으로 보낼 수 있는가

Routing algorithm classification

• Global or Decentralized information

  • Global:

    • 모든 라우터들이 완벽한 topology에 대한 정보, link cost info 가짐
    • “link state” algorithm

  • Decentralized:

    • router는 물리적으로 연결된 이웃의 link cost만 알고 routing 진행
    • “distance vector” 알고리즘

• static or dynamic

  • static: 라우팅 알고리즘의 경로가 거의 변하지 않음
  • dynamic: 라우팅 알고리즘의 경로가 자주 바뀜, 빠르게 변경

link-state routing algorithm

• 다익스트라 알고리즘
  • 모든 네트워크 노드들의 edge에 대해서 cost를 다 알고있음
    • 각 라우터들이 자신과 관련된 “link state broadcast”를함
    • 모든 노드가 같은 정보를 가짐
  • source에서부터 모든 경로에대한 최소 path을 구할 수 있음
    • forwarding table에 반영

Dijkstra’s algorithm discussion

• Algorithm complexity: n nodes

  • 최대 O(n^2), 최적화해도 O(n log n)

• Oscillations possible:

  • 최적화된 경로가 계속 바뀌면서 무한루프 될 수 있음.

Distance vector algorithm

• Bellman-Ford equation

dx(y) := cost of least-cost path from x to y
then dx(y) = minv{c(x,v) + dv(y)}

• v: x의 모든 이웃 노드
• c(x,v): 이웃노드 v로 가는 코스트
• dv(y): v에서 y까지 최소 거리

결국 이웃노드를 계속 탐색하면서 최소 경로를 찾아감

Dx(y) = x에서 y까지 가는 최소 코스트로 추정되는 값

• x는 distance vector값을 유지 Dx = [Dx(y): y in N]

node x:

• 이웃노드의 코스트를 알고있음 v: c(x, v)
• v로부터 받은 추정값도 알고있음 Dv

key idea: 이웃노드들의 도움을 받아서 계산

• Dx(y) = minv{c(x,v) + Dv(y)} for each node y in N

Distance vector algorithm 사용될때:

• link cost 변경
• 주변 노드 Dv값 변경

Distributed(분배):

• 자신의 Dv가 변할 때 각 이웃노드들에게 알려줌

동작구조 - 각각의 노드들:

loop

• wait for (이웃노드들이나 local link cost값이 변경되었을때)
• recompute (다시계산)
• 이웃들에게 Dv가 변경되면 알려줌

Distance vector algorithm: link cost changes

• 노드에서 local link cost가 바뀐걸 알아챔
• routing info를 updates, distance vector 다시 계산
• 만약 Dv 가 바뀌면, 이웃에게 알림

“good news travels fast”

t0: y가 link-cost 변경된걸 확인, Dv 업데이트, 이웃에게 알림
t1: z는 그값을 y로부터 받음, 테비을 업데이트, z to x로 가는 최소값을 변경, 이웃에게 Dv 전달
t2: y는 z의 업데이트값 전달받음, distance table 수정, 변경되는점은 없음

bad news travels slow - “무한반복” 문제

link cost가 업데이트된걸 다른 노드들은 모르고 있기 때문에 생김
결국 -> 많이 반복해야함 -> inf problem

Distance vector algorithm: poisoned reverse

• If Z가 Y를 통해 X로 패킷을 라우팅할 때: Z로부터 X까지의 경로는 INF로 설정
• 하지만 단편적인 해결책
• INF problem 해결 못함

Link State vs Distance Vector

• Message complexity

  • LS: N nodes, E links, O(N*E) msg sent
  • DV: 이웃노드끼리만 교환
    • Convergence time varies

• Speed of convergence(수렴 속도)

  • LS: O(N^2) 알고리즘 O(N * E) 메시지
    • 진동이 있을 수 있음
  • DV: 제각각
    • routing loops
    • count-to-infinity problem

• Roubustness(견고성)

  • LS: 각자 계산하기 때문에 실수하면 자신의 포워딩 테이블만 에러
  • DS: 이웃노드에게 잘못 계산된 Dv를 알려주면 에러가 번식함

Intea-AS routing in the Internet: OSPF

Making routing scalable (라우팅을 확장가능하게 만듬)

• 지금까지 배운 라우팅 - 이상적임
  • 모든 라우터가 동일
  • 네트워크가 “flat”

Scale: 많은 destinations

• 지구상의 모든 destination을 가지고 routing table을 만들 수 없음

• communication cost도 무한 함

• Administrative autonomy (관리 자동화)

  • 각각의 노드들의 routing을 자동화
  • 자신의 네트워크를 컨트롤할 수 있어야함

scalable routing에대한 Internet approach

• Autonomous systems(AS): 라우터를 하나의 지역으로 모은것 (a.k.a. “domains”)

Intra-AS routing - 하나의 도메인 내에서 라우팅

• 같은 지역의 호스트, 라우터 간의 라우팅 지원
• 모든 한 지역에 있는 라우터들은 같은 intra-domain protocol 구동
• 다른 AS에 있는 ㄹ라우터들은 다른 intra-doamin routing protocol 돌릴 수 있음
• Gateway router: AS의 edge, 인프라들이 다른곳과 통신할 때 거쳐가는 라우터

Inter-AS routing

• 도매인간의 통신을 지원
• Gateway가 inter-domain routing 지원

Interconnected ASes

• Forwarding table = Intra-AS Routing algorithm + Inter-AS Routing algorithm
• intra-AS: 하나의 AS 안에서 destinations 결정
• inter-AS & intra-AS: AS 밖에 있는 destinatons 결정

Inter-AS tasks

• gateway router에서 Inter-AS 업무 수행

• AS2와 AS3를 어떤 데스크로 연결할 수 있는지

• 어디로 가야하는지 AS1의 모든 라우터에 전달

Inter-AS Routing

• interior gateway protocols (IGP)

• 주로 사용되는 intea-AS routing protocols:

  • RIP: Routing Information Protocol
  • OSPF: Open Shortest Path First
    • IS-IS (Intermediate System to Intermediate System) protocol: OSPF랑 유사
  • IGRP: Interior Gateway Routing Protocols (Cisco에서 2016까지 사적으로 사용)

OSPF (Open Shortest Path First)

• 표준: publicly available

  • link-state algorithm 기반
  • link state packet을 뿌려야함
  • 각 노드에 topology map을 만들 수 있어야함
  • 라우터에서 다익스트라 알고리즘 구현

• OSPF를 돌리는 라우터들은 항상 AS의 모든 라우터들에게 link-state를 광고해야함

• IS-IS routing protocol: 다익스트라기반, OSPF랑 유사

Large domains 에서는 Hierarchical(계층적) OSPF

• two-level hierarchy: local area, backbone

  • area 내에서만 link-state advertisement를 해줌
  • 각각의 노드들은 detailed한 area topology를 알고있음; 다른 도메인으로 이동하는 경로를 알고있음

• Area border routers: 자신의 area에 있는 네트워크들의 정보를 취합해서 다른 area border routers에게 advertise해줌

• Backbone routers: Backbone router들 끼리 OSPF 라우팅을 할 수 있음

• Boundary routers: 다른 AS 시스템이랑 연결

Internet inter-AS routing: BGP

• BGP (Border Gateway Protocol): inter-domain routing에서 사용하는 표준과 같은 형태

  • 이것을 통해 인터넷의 모든 노드들이 데이터를 주고 받음

• BGT는 AS에게 2가지 규격 제안:

  • eBGP (External BGP): AS간의 메시지 교환
  • iBGP (Internal BGP): 하나의 AS안에 있는 routers끼리 메시지 교환

• BGP는 특정 subnet에 자신의 존재를 알려주는 protocol

BGP basics

• BGP session: TCP connection을 통해서 BGP messages 교환
  • 다른 지역에 있는 network 들에게 자신의 존재를 알리는 역할 (path vector)

Path attributes & BGP routes

• 어떤식으로 BGP가 자신을 홍보할까

  • prefix + attributes = “route”
    prefix: CIDRized prefixes(subnet)

    • E.g. 138.16.68/22

  • two important attributes:

    • AS-PATH: 전체 경로를 나타냄
    • NEXT-HOP: 옆에 어떤 AS가 있는지 나타냄

• Policy-based routing:

  • Policy에 의하여 경로 결정

BGP messages

• TCP connection을 통해서 데이터를 주고받음
• BGP messages:
  • OPEN: BGP peer을 remote하는 TCP connection 오픈
  • UPDATE: 새로운 path를 광고
  • KEEPALIVE: 업데이트가 없을때 연결 유지
  • NOTIFICATION: 이전 msg에 오류 보고, connection을 닫을때도 사용

BGP route selection

• 라우터들은 destination AS에 대한 하나 이상의 경로를 학습
• 선택 기준:
  • local 기본 설정 값 속성: 정책 결정
  • shortest AS-PATH
  • closest NEXT-HOP router: hot potato routing
  • 추가 기준

Hot Potato Routing

• intra-domain에서 비용이 가장 적은 local gateway 선택

Why different Intra-, Inter-AS routing?

• Policy:

  • inter-AS: admin은 traffic을 cotrol하고 싶고, 누가 들어오는지 조절하기 때문에 중요
  • intra-AS: single admin이므로 별로 중요하지 않음

• Scale:

  • hierarchical routing을 사용, traffic을 줄임

• Performance:

  • intra-AS: performance에 focus 할 수 있음
  • inter-AS: 성능보단 policy가 더 중요

---

Congestion control

• Congestion: 너무 많은 소스에서 너무 많은 데이터를 빠르게 네트워크로 보낼 경우 네트워크가 처리할 수 있는 허용 용량(band width)을 넘어 혼잡 발생

• Flow control과 다름

  • Flow control: 상대방이 데이터를 받을 수 있을 때 그 허용량만큼 보내주는것
  • Congestion control: 네트워크 관점에서 데이터가 많아지면 그것을 조절

• 선제 조건:

  • 패킷 로스 발생
  • 큐잉 딜레이가 늘어남

Congestion: scenario 1

• two sender, two reiciver

• one router, inf buffer

• output link capacity: R (출력 링크 용량)

• 패킷이 유실되도 no retransmisson

• 람다in R/2씩 보내도 람다out R/2

• 딜레이관점에선 람다in이 증가할수록 딜레이는 기하급수적으로 증가

Congestion: scenario 2

• one router, fin buffers
• sender retransmission of timed-out packet
  • application-layer input = application-layer output
  • tranport-layer input includes retransmissions

이상적인 상황: perfect knowledge

• sender는 buffer에 유효공간이 있을 때만 data를 보냄
• 람다’in = 람다out

loss packets는 lost 될수있음, 라우터에서 버퍼가 꽉찼을때 드랍

• sender는 패킷이 유실된걸 알때 다시 보냄
• 람다’in >= 람다out

현실적인: 중복패킷

• queueing delay 때문에 timeout 발생후 재전송

• 최악의 경우 람다’in/2 = 람다out

• costs of congestion: network congestion이 많아지면 필요하지 않는 재전송이 많아짐

Congestion: scenario 3

• four senders
• multihop paths
• timeout/retransmission 존재

TCP congestion control:

• End-to-end congestion control: 데이터가 로스가 발생하거나 속도가 느려지면 보내는양 조절
• Network-assisted congestion control: 라우터들이 네트워크 복잡도 측정, 유저한테 알려줌

Sender가 transmission rate 정해두고 증가, loss가 생기면 조절

• congestion window, cwnd
• 매 RTT(round trip time)마다 1MSS(maximum segment size)만큼 증가
• 로스가 발생하면 반으로 줄임

TCP Congestion control: sender 측에서 돌아감

• sender에서는 window 2개 (cwnd, rwnd(recived window))

• LastByteSent-LastByteAcked<=min(cwnd, rwnd)

• TCP sending rate: cwnd/RTT bytes/sec

TCP Congestion control algorithm

• slow start
• congestion avoidance
• fast recovery

Slow start

• connection이 시작되면 TCP의 sending rate를 loss가 처음 발생할 때까지 1MSS단위로 증가
• every RTT 마다 sending rate가 2배씩 증가됨
• initial rate가 작지만, exponentially fast(기하급수적으로 빠르게)하게 증가

Congestion Avoidance

• ssthresh: congestion avoidance를 시작하는 시점(마지막 congestion이 발생했을 때 기점의 sending rate 절반)

Fast Recovery

• cwnd size를 duplicate ACKs의 갯수만큼 증가
• 필수적인건 아님

TCP Fairness

• K TCP 세션, Bandwidth R
• 각각 평균 rate R/K

Explicit Congestion Notification (ECN)

• Network-assisted congestion control:
  • ECN 비트: 라우터가 패킷이 혼잡하면 설정해줌

---

Greedy Algorithm

• Dynamic programming?
  • recursive property(재귀함수)로 풀 수 있는 문제를 DP로 풀 수 있음
• Greedy approach
  • 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택
  • simple is best
  • local에서는 최적, 최적을 모아서 최종답을 만들어도 검증까지 해야함

Greedy Approach 설계 절차

• Selection procedure (선정 과정)
  • 현재 상태에서 가장 좋다고 생각되는 해답을 찾음
• Fesibility check(적정성 점검)
  • 적절한지 결정
• Solution check(해답 점검)
  • 최적의 해인지 결정

Spanning Tree (신장 트리)

• 그래프의 모든 vertex G를 가지고 있는 트리
• 비방향성 그래프 G에서 순환 제거, 연결된 부분 그래프가 되도록 이음선 제거
• G안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분그래프

Minimum Spanning tree(최소비용 신장트리)

• 가중치의 합이 최소가 되는 신장트리
• 그래프는 트리형태(cycle없는)여야함

브루트포스 방식

• 모든 신장트리를 다 고려해보고, 그중에서 최소비용을 고름

• 분석:

  • 최악의경우, 지수보다 나쁨

Prim’s Algorithm

• v1에서 vi까지 모든 정점을 돌면서 가장 가까이 있는 vnear찾음

  • nearest[i]: vi에서 가장 가까운 정점
  • distance[i]: 거리

Every-case Time Complexity Analysis

• 단위연산: repeat 루프 안에 있는 두개의 for루프 안의 명령문

• inputSize: 마디개수, n

• 분석: repeat-루프가 n-1번 반복

  • T(n) = 2(n-1)(n-1)

최적여부 검증 (Optimality Proof)

• Definition

  • 만약 E의 부분집합 F에 MST가 되도록 이음선을 추가할 수 있으면 (MST에 F가 포함되어있으면) F는 Promising(유망하다) 하다고 함

• Lemma (*중요)

  • F는 E의 유망한 부분집합, Y는 F안에 있는 이음선 들에 의해서 연결된 정점의 집합.
  • 이때 Y에 있는 어떤 정점과 V-Y에 있는 어떤 정점을 잇는 이음선 중에서 가중치가 가장 작은 이음선을 e라고 하면..
  • F + e는 유망하다

Prim’s Algorithm 특징?

• 특정 v1을 기준으로 뻗어나감

Kruskal’s Algorithm

• edge그래프를 기준으로

1. Edge List를 sorting해줌
2. 순서대로 추가해도 되면 연결
3. subset을 merge해줌
4. 다연결될 때까지 반복

Worst-Cast Time Complexity Analysis

(시험출제)

• 단위연산: 비교문
• 입력크기: 정점의 수 n과 이음선의 수 m

1. 정렬하는데 걸리는 시간 O(m lg m);
2. n개의 서로소인 집합 set을 초기화 시간 O(n)
3. 루프 m번 수행, 서로소인 집합 자료구조 사용, find, equal, merge등 포함하면 O(m lg n)

• 여기서 m >= n-1, 1과 3은 2를 지배
  W(m, n) = O (m lg m);

• 최악의 경우 모든 정점이 다른 모든 정점과 연결,
  M = n(n-1) / 2 = O(n^2), 최악의 경우 시간복잡도는 W(m, n) O(n^2 lg n)

Dijikstra’s Algorithm

• 한 정점에서 다른 모든 정점으로 가는 최단경로 문제
• Single-Source Shortest Paths: 시작점v1

1. v1에서 갈수있는 경로로 table을 만듬
2. table에서 가장 짧은 거리를 선택해서 그지역을 경유하는 경로까지 비교
3. 모든 정점을 경유하는 거리를 비교함

Define touch & length

• touch[i]: I까지 가는 경로의 마지막 노드
• length[i]: 현재까지 구해진 최단거리

length[vnear] = -1로 만들어주는 이유?

• 현재 선택된 노드를 다시 선택하는걸 방지

The Knapsack Problem

• 배낭에 넣을 수 있는 최대 가치(Array)를 구하는 문제

The Knapsack Problem: Greedy

• 탐욕적알고리즘: n개의 물건에 대해 모든 부분집합 고려
• 부분집합의 수는 2^n개

The 0-1 Knapsack Problem

• 일반 Fractional Knapsack problem: 남은공간 물건을 잘라서 꽉채울수있음

• 0-1 Knapsack problem: 물건을 못자름

• Fractional Knapsack: Greedy로 구할 수 있음(무게당 가치가 가장 높은순)

Dynamic Programming Approach

• i > 0, w > 0 최대무게: w

• i번째 항목중에서 얻어진 최고의 이익(optimal profit) = P[i][w];
  if w[i] <= w:
  max(P[i-1][w], p[i] + P[i-1][w-w[i]]);
  else:
  p[i-1][w];

여기서 P[i-1][w]는 i번째 항목을 포함시키지 않은 경우의 최고 이익,
p[i] + P[i-1][w-w[i]]는 i번째 항목을 포함시키는 경우 최고 이익

최대이익 P[n][W]는?

• intP[0..n][0..W]의 2차원배열을 만든 후 각 항을 계산해서 넣음
• P[0][w] = 0, P[i][0] = 0이므로 O(nW);

DP방법 보완

• 임의로 W = n!이라 한다면 수행시간은 O(n*n!)이 되므로 무작정 알고리즘보다 나을게 없음

• 최악을 O[n^2]로 만드는법? 무작위보다 빠르게하는법?

  • **P[n][W]를 계산하기 위해 (n-1)번째 행을 모두 계산할 필요 없음)

  P[n][W] = max(P[n-1][W], p[n] + P[n-1][W-w[n]]]);
  따라서 (n-1)번째 항은 P[n-1][W]와 P[n-1][W-w[n]]만 필요
  i번째항에 필요한 항목만 결정해서 계산함

• Worst case

  • O(2^i)

• O(min(2^n, nW));

Greedy vs. Dynamic Programming

Greedy	DP
최적화문제	최적화문제
알고리즘이 존재하면 더 효율적	때론 불필요하게 복잡
단위출발점 최단경로 문제: O(N^2)	단위출발점 최단경로 문제: O(N^3)
알고리즘이 최적인지 증명해야함	최적화원칙이 적용되는지 점검만하면됨
0-1Knapsack은 못품	0-1Knapsack 풀수있음

---

Transport-layer services

Transport vs. Network layer

• Network: hosts 사이
• Transport: processes 사이

Internet transport-layer protocols

• Reliable in-order delivery -> Transmission Control Protocol(TCP)
• Unrealiable, unordered delivery -> User Datagram Protocol (UDP)

---

Principles of network applications

Application architectures

• client-server
• peer-to-peer

Client-server architecture

• server:

  • always-on host
  • permanent IP address

• clients:

  • communicate with server
  • may be intermittently connected
  • do not communicate directly

P2P architecture

• No always-on server

Processes communicating

• Process: program running within a host
  • 같은 host 에서, inter-process communication을 통하여 두개의 프로세스가 통신

Sockets

• Process sends/receives messages to/from its socket
• Socket analogous to door

Addressing processes

• Identifier includes both IP address and port numbers associated with process on host.

Example port numbers:

• HTTP server: 80

• mail server: 25

• to send HTTP message to usaint web server:

• IP address: 203.253.31.114

• port number: 80

App-layer protocol defines

• Types of messages exchanged,
  • E.g., request, response
• Message syntax
  • 구역 나누기

---

2020-1:
Host A 와 Host B 가 30,000 km 떨어진 곳에 위치하고 있고 R=5Mbps 의 속도의 네트워크 링크로
연결되어져 있다 해당 네트워크의 propagation delay 는 𝟐.𝟓×𝟏𝟎^𝟖 meters/sec 이다
Host A 에서 Host B 로 1,000,000 bits 의 파일을 분할없이 한번에 보낸다고 가정했을 경우 파일을
보내는 시간동안 네트워크 링크에 존재하는 최대 비트 수는 얼마인가
(네트워크 링크는 H ost A 와 Host B 만 사용하는 링크임 , Mega = 10^6)

transmission delay: 0.2s
prop delay: 0.12s
600,000 bits

2020-2:
네트워크를 통해 사이즈가 큰 데이터를 보낼 때 일반적으로 해당 데이터를 작은 사이즈의
패킷으로 쪼갠 후 보내게 된다 해당 패킷들을 받는 수신자는 수신한 패킷들을 재조합 하여
데이터 원본을 수신한다 이러한 과정을 message segmentation 이라고 부르기도 한다
아래 그림은 message segmentation 이 없는 데이터 전송과 message segmentation 이 적용된
데이터 전송을 나타내고 있다 Source 에서 Destination 사이에는 스위치가 2 개가 존재하고 ,
Source 가 Destination 으로 보내려는 데이터 의 크기는 𝟏.𝟐×𝟏𝟎^𝟖 bits 이다 네트워크 링크 전송
속도는 R=4Mbps 일 때 아래 물음에 답하시오 propagation, queuing, and processing delays 는
무시한다

1 - Message segmentation 이 없는 데이터 전송 (위 그림의 (a)) 를 고려했을 때 Source 에서 Destination 까지 전체 데이터를 보내는데 걸리는 시간은 얼마인가?
3*L/R = 3 * 1.2 * 10^8 / 4 * 10^6 = 3 * (1.2 * 10^2 / 4) = 3 * 0.3 * 10^2 = 3 * 30 = 90s

2 - 전체 데이터가 1200 개의 패킷으로 나누어지고 각 패킷의 길이는 100,000bit 라고 가정해보자 Message segmentation 가 적용된 데이터 전송 (위 그림 의 (b)) 를 고려했을 때 Source 에서 Destination 까지 첫번째 패킷을 보내는데 걸리는 시간은 얼마인가?
100,000 / 5,000,000 = 1/50 = 0.02s,
0.02s * 3 = 0.06s

3 - 전체 데이터가 1200 개의 패킷으로 나누어지고 각 패킷의 길이는 100,000bit 라고 가정해보자 Message segmentation 가 적용된 데이터 전송 (위 그림 의 (b)) 를 고려했을 때 Source 에서 Destination 까지 전체 패킷 총 1200 개의 패킷 을 보내는데 걸리는 시간은 얼마인가?
하나의 패킷이 걸리는 시간 0.6s, 하나의 구간을 통과하는 시간 0.2s, 3개를 동시에 하므로 1200 * 0.2s = 240s - 0.4s = 239.6s

4 - message segmentation 장단점
장점: message를 나눠서 보내면 중간에 라우터에서도 동시에 전송을 할 수 있어서 시간이 짧아짐
단점: 패킷이 중간에 없어질 수 도있음

---

What’s the Internet

“nuts and bolts” view

billions of connected computing devices:

• hosts = end systems
• running networks apps

communication links

• fiber, copper, radio, stellite
• transmission rate: bandwidth

packet switches: forward packets (chunks of data)

• routers and switches

Internet: “network of networks”

protocols control sending, receiving of message

• e.g., TCP, IP, HTTP, …

Internet standards

• Internet Engineering Task Force (IETF) 에서 Request for comment (RFC)라는 표준 문서들을 개발함

A service view

infrasturcture that provides services to applications:

• Web, VoIP, email, games, e-commerce, social nets, …

Socket interface

• allows sending and receiving app programs to “connect” to Internet
• provides service options, analogous to postal service

What’s a protocol?

network protocols:

• machine rather than humans
• three way handshaking

protocols define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt

Network edge

A closer look at network structrue

Network edge (종단 시스템)

• hosts: clients and servers

Access networks

• Home, Enterprise, Mobile, …

  Physical media

• wired, wireless communication links

Access networks and pysical media

How to connect end systems to end router?

• residential(Home) access networks
• institutional access networks
• mobile access networks

keep in mind:

• bandwidth (bits per second) of access network? (속도)
• shared or dedicated? (나만쓰는가?)

Home Access

Home Access: DSL

Digital Subscriber Line (DSL)

• 전화선을 이용한 통신

Home Access: Cable Internet Access

HFC: hybrid fiber coax (동축 케이블)

Coaxial and fiber cables attach homes to ISP router

• fiber와 Coaxial 동시에 사용

Home Access: FTTH

Fiber to the home

• fiber만 사용

Home Access: A typical home network

Enterprise access

Enterprise access: Ethernet

Physical media

Physical media: Twisted-Pair Copper Wire

• Unshielded twisted pair (UTP)
• Shielded twisted pair (STP)

Pysical media: Radio

• no physical “wire”

Network core

• Mesh of interconnected routers

Packet-switching

• Message는 application이 원하는 데이터를 포함
• Message를 잘게 쪼갠게 packets

Packet들이 Communication link로 이동할때 transmission rate기반으로 이동

• 패킷의 크기는 L bits, 전송 속도는 R bits/sec
  

Packet-switching: Store-and-Forward

• 저장하고 전달

Ex) L = 7.5 Mbits, R = 1.5 Mbps, one-hop transmisson delay = 5 s

• End to End Delay = 2L/R

• 3개의 패킷을 보내는 시간

  • L/R시간, 첫번째 패킷이 라우터에 도착
  • 2L/R시간, 첫번째 패킷이 목적지 도착, 두번째 패킷 라우터 도착
  • 3L/R시간, 두번째 패킷이 목적지 도착, 세번째 패킷 라우터 도착
  • 4L/R시간, 세번째 패킷이 목적지 도착

• 하나의 패킷을 N개의 링크가 있는 곳으로 보내는 End to End 딜레이 (N links (eash of rate R), N-1 Routers)

  • D_end-to-end = N X (L/R)

Queuing Delays and Packet Loss

Queuing and Loss:

• 도착하는 패킷보다 보내는 패킷이 느릴경우
• 딜레이 + 공간 꽉차면 Loss까지 생김
  

Forwarding and Routing

• Forwarding: input에서 output으로 움직이는것
• Routing: 어디로 갈지 정해주는것

Circuit switching

• 데이터 회선이 정해지고 회선단위로 데이터를 주고받음

frequency-division multiplexing (FDM) - 주파수분할

time-division multiplexing (FDM) - 시분할

Silend Period -> 네트워크 자원낭비로 이어짐

Packet Switching vs. Circuit switching

• Packet switching allows more user to use network

  • 1 Mb/s link
  • each user:
    • 100 kb/s when “active”
    • the probability that a specific user is active is 0.1

• circuit switching:

  • support only simultaneous 10 users (1 Mbs/ 100 Kbps)

• Packet switching:

  • With 35 users, probability > 10 active at same time is less than 0.0004
  • 35C11(0.9)24(0.1)11 < 0.0004

Packet switching이 좋지만, packet delay나 loss가 발생할 수 있음

• reliable한 데이터 전송이 필요

Network of networks

• End systems은 access ISPs (Internet Service Providers)

---

---

Delay, Loss, Throughput in Networks

Four sources of packet delay

• Total nodal delay (d_nodal)

  • nodal processing delay (d_proc),
  • queuing delay (d_queue),
  • transmission delay (d_trans),
  • propagation delay (d_prop)

  

d_proc: nodal processing

• check bit errors
• determine output link
• typically < msec

d_queue: queueing delay

• 라우터 개수에 의존
• 가장 중요

d_trans: transmission delay

• L: packet length (bits)
• R: link bandwidth (bps)
• d_trans = L/R

d_prop: propagation delay

• d: length of physical link
• s: propagation speed (통신매체에 따라 다름)
• d_prop = d/s

Transmission delay vs. Propagation delay

Caravan analogy

• cars “propagate” at 100 km/hr

• toll booth takes 12sec to service car (bit transmission time)

• 2번째 톨게이트까지 가는 시간?

  • 첫번째 톨게이트 12*10 = 120s
  • 100km 가는 시간 = 1hr
  • A: 62 min

Queueing delay

• R: link bandwidth (bits / sec)
• L: packet length (bits)
• a: average packet arrival rate (packets/sec)
• La/R: traffic intersity
  • La/R이 0에 가까우면: 딜레이가 거의 없음
  • La/R이 1에 가까우면: queueing delay가 커짐
  • La/R이 1보다 크면: 거의 무한대의 딜레이

Packet loss

• 버퍼가 가득 차면 loss 됨

End-to-End Delay

• N-1개의 라우터가 있을때
• End-to-End Delay = N x (d_proc+d_trans+d_prop)

Throughtput(처리량)

Networks under attack: Security

Network security