---

Review Matlab

Array

---

Search Problems

consist

• A state space
• A succeossor function

problem

1. Initial state

Search Strategies

1. Completeness

• Solution을 찾을 수 있는가

2. Optimality

• 최소 코스트가 항상 나오는가

3. Time complexity

4. Space complexity

Uninformed Search Strategies

• DFS
• BFS
• UNIFORM

---

Depth First Search(깊이우선탐색)

• 노드의 모든 후손노드를 방문한다. (preorder tree traversal)

State Space Tree(상태 공간 트리)

• 뿌리 노드에서 잎노드까지의 경로가 해답후보(candidate solution)가 되는 트리
• DFS를 하여 해답을 찾을 수 있음. 그러나 가능성이 없는 노드도 검색해서 비효율적

Back Tracking

• 정의: promising

  • 전혀 해답이 나올 가능성이 없는 노드: (non-promising)
  • 그렇지 않은 노드: promising

• 되추적?

  • 유망성 점검 후 유망하지 않으면, 부모노드로 돌아가서(“backtrack”) 다음 후손에 대한 검색을 진행

BackTracking 개념

• 상태공간트리에서 깊이우선검색 실시
• 유망하지 않으면 가지쳐서(pruning) 검색하지 않음
• 유망한 노드만 자식노드 검색

The 0-1 Knapsack Problem

• Optimization problem이므로 검색이 끝나기 전까진 해답을 알 수 없음

Let:

• profit: 가치 총합
• weight: 무게 총합
• totweight: 무게 count
• bound: 가치 추정치

풀이:

• 단위당 가치가 높은 순으로 sort

  • 탐욕적 방법처럼 보이지만 탐욕적인 알고리즘은 아니다.

• bound와 totweight를 profit과 weight값으로 초기화

• 탐욕적으로 아이템 취하기

• toweight이 W초과할때까지

• 남은부분에 마지막일부취하고 profit을 bound에 더함

분석

• 점검하는 마디의 수: O(2^n)

• DP보다 좋은가? 확실하지 않음

  • DP worst(O(min(2^n, nW)))
  • BT worst(O(2^n))

• –

Branch-and-Bound (분기한정법)

• backtracking과 비슷

  • state space tree 사용

• Backtracking과 차이점

  • 트리를 순회하는 방법을 제한하지 않는다.
  • 최적화 문제에서만 사용

Breadth-First Search ( 너비우선탐색)

1. 뿌리마디 먼저 검색
2. 다음 수준1에있는 모든 마디를 검색
3. 다음 수준2에있는 모든 마디를 검색
4. …

• Queue 사용

Best-First Search (최고우선탐색)

• 최고의 한계를 가진 마디를 우선으로 선택
• 우선순위 큐(Priority QUeue) 사용

---

The Travveling Salesperson Problem (TSP)

• 외판원의 집이 위치하고 있는 도시에서 출발,
  다른 도시들을 각각 한번씩만 방문하고, 다시 집으로 돌아오는
  가장 짧은 일주여행경로(tour)을 결정하는 문제

• 여러개의 징루 여행경로 중에서 길이가 최소가 되는 경로가 최적일주여행경로(optimal tour)가 된다.

• 부르트포스 알고리즘:

  • 가능한 일주여행경로의 총 개수는 (n-1)!

DP를 이용한 접근방법

• V: 모든 정점의 집합

• A: V의 부분집합

• D[vi][A]: A에 속한 각 정점을 한번씩만 거쳐서 vi에서 v1로 가는 최단경로 길이

• D[vi][V-{v1}] = min(W[1][j] + D[vj][V-{v1, vj}])

• n=40일때 DP로 6년…. O(n^2*s2^n)

분기한정법을 이용한 접근방법

상태공간트리 구축방법

• 각 마디는 출발마디로부터 일주여행경로

• 리프노드에있는 일주여행경로를 찾음

• lowerbound 가져오기

Branch-and-Bound

• Backtracking은 속해있다.

---

Minimum Spanning Tree

• 정의
• 알고리즘(Prim’s and Kruskal’s) complexities, 이게 greedy appraoch인가??

Dijkstra’s Algorithm for Single-Source Shortest Paths

• 소스코드레벨 구현

Knapsack Problem (fractional & 0-1) 차이

• Greedy approach로 Optimal(최적)한 Solution을 찾을 수 있는가? 어떨때 가능한가?
• Greedy vs. Dynamic Programming
• Backtracking & Branch-and-Bound
  • DPS, BPS, Best-First searches…
  • pruning

TSP (Traveling Salesperson Problem)

• DP vs. Greedy? or Branch-and-Bound?
• 유전 알고리즘, 다른것들과 차이, 장단점, 최적의 Solution을 가질 수 있는가?

Search Algorithms

• Actual tree searches…

  • 방문하는 노드들 & 최적경로 ()
  • 방문 트리 구성

• 장단점

• 최적의 해를 찾는 보장은?

• Complexities & 구현방법(data structures?)

---

Nonlinear Unconstrained Optimizations

• Heuristic: 짐작, 경험등 규칙을 통하여 수행하는 알고리즘
• Optimality: X

Genetic Algorithms (GE) : 유전 알고리즘

• N개의 hypotheses(가설), 유지해나가는 알고리즘
• 집단 유전학의 개체 진화 원리르 이용하는 문제해결공간 탐색 방법

• In population:
  • Selection: 어떤것을 선택할것인가
  • Crossover: Selection한 후보중 어떤식으로 Mixable 할것인가
  • Mutation: 어떻게 변이를 줄건가
  • Replacement: 새로운 N개를 대치

유전알고리즘 표현

• 순서 기반 표현: 각각의 노드들을 하나하나 index줘서 표현

선택 연산

• 교차에 쓰이는 두개의 부모 해를 고르기 위한 연산
  • 우수한 해가 선택될 확률이 높아야함

품질 비례 룰렛휠 선택

• 각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절
• fi = (Cw - Ci) + ( Cw - Cb ) / (k - 1), k>1
  • Cw : 해집단 내에서 가장 나쁜 해의 비용
  • Cb : 해집단 내에서 가장 좋은 해의 비용
  • Ci : 해 i의 비용

순위기반 선택

• 해잡단 내에서 해들을 품질 순으로 순위를 매긴 후 다음 가장 좋은 해부터 일차 함수적으로 적합도 배정
• fi = max + ( i - 1 ) X (min - max ) / (n - 1)

교차 연산

• 유전 알고리즘의 대표 연산
• 연산 중 가장 다양한 대안 존재

일점 교차(point crossover)

• 길이가 n인 일차원 문자열로된 염색체 상에서 일점 교차로 자르는 방법(총 n-1가지)

다점 교차(multipoint crossover)

• 염색체의 길이가 n일 때 k점 교차로 자르는 방법의 총 수는 n-1Ck가지

• 일점교차보다 교란의 정도가 커서 보다 넓은 탐색 공간을 탐색할 수 있음

• 교란이 강하면 수렴성이 떨어져 주어진 시간 예산내에 제대로 수렴하지 않을 가능성

균등 교차(uniform crossover)

• 자름선을 이용하지않음
• 이론적으로 완벽(모든 재조합 가능성 open)
• 난수를 사용

사이클 교차(cycle crossover)

• 염색체가 순열일경우 사용
• S2[index] = S1

순서 교차(order crossover)

• 염색체가 순열일경우 사용
• 한 부분집합을 고정함, 남은부분 부분집합 뒤부터 순서대로

간선 재조합

• TSP를 위해 개발된 교차연산

• 부모해의 특성을 보존, 변이가 적으면 교란이 너무 적음

• 인접도시목록을 이용하여 TRACKING

• 장단점?

  • 각각이 생각했던 최종 SOLUTION을 유지해나갈 수 있음

BFS를 이용한 유전자 재배치

• 유전알고리즘 시작 전에 문제에 깃든 정보(유전자들 간의 관계)를 이용하여 유전자들의 위치를 재배치

변이 연산

• 부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산

전형적 변이

비균등 변이

수선

기타 변이 연산

세대형 유전 알고리즘

• 해집단 내에서 염색체가 대부분(전체) 대치되므로 대치 연산이 비교전 간단

• convergence(수렴)이 일어나기 어려움

• 안정 상태 유전 알고리즘은 한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해들과 대치하게 되므로 대치될 대상을 고르는 작업이 매우 중요한 영향을 미침
  -> 부분적인 최적화가 어렵다

GA가 유용한 문제들

• 전통적 방법으로(결정론적인(deterministic)방법으로) 좋은 해를 잘 구하지 못하는 문제

GA가 소용 없는 문제들

• 결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리는 문제

• 결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리지 않으나 크기가 너무 작은 문제

  • 5-city TSP 등

• Solution Space가 가늠할 수 없는 근사치 최대값을 찾기 유용한 알고리즘이다.

GA 장단점

장점

• 빠르다 (메모리 사용량 적음) 엄청 큰 Search space에서.
• 쉽다.

단점

• Randomized - optimal하지 못하고 complete하지 못함
• local maxima에 빠질 수 있음

---

Downhill Simplex Method

• Starting Guess
• N+1 각형을 유지

N+1개의 꼭짓점 갖는 구조
하나 이상의 테스트 포인트 유지

기본적인 Operation

• 4개의 scalar parameters을 지정
  • reflection p
  • expansion w
  • contraction y
  • shrinkage a
    • Standard: p = 1, w = 2, y = 1/2 and a = 1/2

진행방식

1. Order: 어떤 포인트가 가장 유명한지 판단
2. Reflect
3. Expand
4. Contract

• outside
• inside

---

암호기술

암호학적 해쉬 함수

• 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 비트: 라우터가 패킷이 혼잡하면 설정해줌