yongmin

1. 문제해결과 알고리즘

    - 문제해결과정

    - 알고리즘 분석 

2. 데이터 추상화와 자료구조

    - 데이터 추상화

    - 자료구조 : tree, binary tree, stack, queue, heap, union-find, dictionary, ...

4. Sorting

    - 정렬 : insertion sort, quick sort, merge sort, heap sort, radix sort

6.  Dynamic sets & Searching

    - array doubling & amortized analysis

    - BST

    - Red-Black tree

7. Graph and Graph Search

    - Graph

    - Graph traversal : pre-order, in-order, post-order

    - Graph search : DFS, BFS

    - Strongly Connected Components

8. Graph optimization problem & greedy algorithm

    - optimization problem

    - graph optimization problem : MST, shortest path

    - MST -> Prim algorithm, Kruskal algorithm

    - shortest path -> dijkstra algorithm

9. Transitive Closure & All-pairs shortest paths

    - transitive closure, Floyd-Warshall algorithm

    - All-pairs shortest paths

10. Dynamic Programming

    - dynamic programming & recursive algorithm

    - Matrix-chain Multiplication

11. String Match

    - string match

    - Brute-Force

    - KMP

    - Boyer-Moore

13. NP-Complete Problem

    - Optimization problem vs Decision problem 

    - Class P, Class NP, Class NP-hard problem

    - Class NP-Complete problem

상황 : host A가 www.google.com에 접속하려고 함.

1. host A는 LAN에 접속 (no IP)

2. host A는 DHCP request 메세지를 flooding 기법으로 broadcast (UDP)
-> switch는 호스트의 MAC address와 inteface를 learning

3. DHCP 서버는 UDP demux로 request 메세지를 이해

4. DHCP 서버는 DHCP ACK 메시지 전송 ( yiaddr, ip addr of first hop router, DNS server name & id 포함)
-> 2번에서 host의 MAC address와 inteface를 learning했으므로 uni cast 가능

5. host A는 ip 할당 받음 , www.google.com에 접속하기 위해 ip 필요 => LAN에 없으면 DNS query

6. DNS query송신시, 

    source ip            : A's IP

    destination ip      : DNS ip

    source MAC        : A's MAC addr

    destination MAC  : router's MAC addr

query메세지를 전송함으로써 router가 LAN외부로 나가는 메세지임을 확인 => ARP

7. router는 DNS IP를 보고 해당 메세지를 DNS 서버가 있는 곳 routing (RIP, OSPF, BGP) 및 forwarding

8. DNS query를 수신한 DNS 서버는 DNS 계층을 거치면서 www.google.com의 주소를 알아내고 host A에게 알려줌

9. host A는 www.google.com의 ip를 가지고 3-way handshaking으로 tcp connection 설정  

10. host A는 http request로 원하는 객체 요구 및 google 서버는 http response로 host A에게 해당 파일 전송

1. link layer intro

2. MAC : multiple access protocol

3. LANs

4. MPLS – link virtualization

5. Data center network

1. network layer intro 

network layer

송수신 호스트간의 패킷을 전달하는 서비스 제공

주요기능

forwarding : 라우터의 입력링크로 들어온 패킷의 올바른 출력링크 결정

routing : 라우팅 알고리즘으로 출발end-도착 end 까지의 경로 결정

network service model

송수신 호스트 간의 패킷 전송 특정 정의

종류

- datagram network (-> connectionless service )

: 패캣과 수신자 ip를 가지고 어떤 경로로 가던지 간에 특정시간에 패킷이 도착할 수 있음을 보장

- virtual circuite nework (-> connection service)

: 경로를 설정하고 패킷을 스트림 형식으로 보내어 순서대로 패킷전달

2. virtual circuite network ,datagram network 

virtual circuite network

경로를 설정하고 패킷을 스트림 형식으로 보내어 순서대로 패킷전달

VC의 3요소 : path, vc number, forwarding테이블

datagram network

목적지 주소를 가지고 각각의 패킷에 대한 경로가 설정되므로, 결로가 라우터 상황에 따라 바뀐다

3. Inside Router 

router 구조

input port

output port

routing processor : 라우팅알고리즘으로 forwarding talbe 업데이트

switching fabric

종류

swtiching via memory

switching via a bus

switching via interconnection network

4. IP : Internet Protocol 

network layer의 주요 프로토콜

routing protocol : end-to-end경로설정, forwarding table 업데이트

IP, internet protocol
: 네트워크 계층의 데이터 전송 프로토콜

ICMP
: 오규가 발생한 ip 패킷에 대해 원인을 송신 호스트에게 전달할 수 있는 기능을 지원하는 프로토콜

ip fragmentation/reassembly

- link type 마다 다른 MTU를 가지고 있으므로 large ip 패킷은 여러 small ip packet으로 분할
=> identifier(데이터그램식별), flags(1=다음패킷존재, 0=마지막패킷), offset(순서) 정보를 이용하여 분할
=> 호스트에서 위의 3가지 정보를 이용하여 reassembly

IPv4

ipv4는 32비트 주소로 host, router interface(host와 router간의 connection)의 식별자 역할

ipv4 address는 network prefix와 host number로 구성
=> nerwork prefix : nerwork 식별
=> host number : host식별

classful ip

class A : ip가 0으로 시작(0~127), prefix가 8비트. 2^24-1개의 호스트를 가지는 네트워크

class B : ip가 10으로 시작(128~191). prefix가 16비트. 2^16-1개의 호스트를 가지는 네트워크

class C : ip가 110으로 시작(192~223). prefix가 24비트. 2^8-1개의 호스트를 가지는 네트워크

class D : ip가 1110으로 시작 (224~239). multicast를 위한 ip

classful ip address의 문제점

1. large network ( class A, B)를 위한 network address가 너무 적음 -> A:128개, B:64개

2. network prefix, host number의 two-layer 계층구조는 large network에 부적합 -> host를 낭비문제 발생
-> 해결법 : subnetting

3. inflexbible -> 해결법 : CIDR

subnet

정의 : ip의 subnet part가 같은 디바이스들이 구성하는 네트워크 -> subnet에 속한 디바이스들은 라우터를 거치지 않고 브로드캐스팅 가능

subnetting

hostnumber를 subnet number와 host number로 나눔으로써 ip를 network prefix, subnet number, host number의 3계층으로 구성

subnetting 장점

subnet을 자유롭게 구성 가능

네트워크 내부적으로는 subbet을 구분된 network로 인식

외부에서는 subnet 구조를 파악할 수 없음 -> 보안

subnet mask

ip address와 and연산으로 network prefix + subnet number (= extended network prefix)를 구할수 있다. 이를 이용해 host number도 구할수 있다

CIDR, classless interdomain routing

network id의 길이가 고정되어 있지 않고 가변적인 ip주소 -> network id의 길이(network prefix)를 따로 명시

address assignment
: ISP가 클라이언트가 요구하는 만큼의 ip address block을 할당 -> 클라이언틑 이를 가지고 host ip에 할당 -> DHCP기법 이용

DHCP, dynamic host configuration protocol

host가 network에 join하면 network server로부터 host에게 ip address를 동적할당 받는다
=> ip address는 빌리고 반납하는 형식이므로 address는 재사용 가능

할당과정

1. DHCP discover : host가 브로드캐스팅으로 dhcp discover msg전송
src : 0.0.0.0
dest : 255.255.255.255
yiaddr : 0.0.0.0

2. DHCP offer : DHCP server가 브로그캐스팅으로 dhcp offer msg 전송하여 ip주소 할당
src : 223.1.2.5 // 서버의 ip주소
dest : 255.255.255.255
yiaddr : 223.1.2.4 // 할당할 주소

3. DHCP request : host는 브로드캐스팅으로 수신받은 해당주소를 사용하겠다는 dhcp request msg 전송
src : 0.0.0.0 // 아직 사용x
dest : 255.255.255.255
yiaddr: 223.1.2.4

4. DHCP ACK : 서버는 브로드캐스팅으로 해당 ip 사용 확인하는 dcp ack msg 전송
src : 223.1.2.5 //서버의 ip
dest : 255.255.255.255
yiaddr : 223.1.2.4

DHCP가 포함하고 있는 정보

1. yiaddr

2. address of first-hop router

3. dns server 이름,주소

4. network mask

NAT, network address translation

2^32개의 ip주소가 부족해지자 이를 해결하기 위한 임시방편으로 외부에서 통용되는 하나의 public ip와 local network에서 통용되는 여러 private ip를 라우터가 NAT translation table을 가지고 변환

NAT 특징

local network는 외부에서 통용되는하나의 ip만 사용

local network의 내부는 외부와 분리됨

local network의 디바이스들의 ip를 마음대로 설정가능

외부의 isp가 바뀌어도 local network에는 영향x

외부에서는 local network의 ip를 볼 수 없음 ->보안

구현조건

-NAT router는 local network안에서 밖으로 나가는 모든 datagram의 출발지 ip와 포트번호를 NAT ip와 포트번호로 변환

-변환정보를 NAT router 내부의 NAT translation table에 저장

-밖에서 들어오는 datagram의 NAT ip와 포트번호를 NAT router가 table을 보고 local network의 ip와 포트번호로 변환

NAT 약점
: 라우터는 3계층까지만 관여하는 장비인데 4계층에 해당하는 ip정보를 핸들링 -> 3계층 장비가 4계층에 침범하는 것은 네트워크의 계층화 원칭 위반

NAT 문제점
: 외부의 client가 local network 내부의 서버에 연결하고 싶은데 내부는 unvisible하므로 연결 불가능
=> 해결방안1 : NAT table을 외부에 공개 -> NAT translation table의 정보가 변경되는데 변경전 정보를 이용하면 연결 불가능
=> 해결방안2 : UPnp 프로토콜 사용 -> 자동으로 public IP를 privite ip로 맵핑하는 서비스제공
=> 해결방안3 : relay가 NAT client와 외부 client에 각각 연결되어 두 연결사이의 패킷 중계

ICMP

에러발생시 라우터가 host에게 보고할 수 있도록 ip대신 사용되는 프로토콜

icmp msg : type + code + description

traceroute : 경로추적 과정

TTL 값을 1부터 하나씩 증가시키면서 udp 세그먼트를 목적지로 전송

n번째 datagram이 n번째 라우터까지 도달하면 n번째 라우터는 (type:11, code:0 -> TTL expired) 메시지 전송

목적지는 (type3,code3->destination unreachable) 메시지 전송 -> traceroute stop

=> 목적지까지 구간의 정보기록가능
=> n 구간의 딜레이 계산가능

IPv6

32비트인 ipv4가 부족하므로 128비트 주소인 ipv6 개발

ipv6 format -> 강의자료 p82

ipv4 -> ipv6 translation

모든 라우터가 ipv6를 지원하지 않음

해결방안 : tunneling 기법
=> ipv4안에 ipv6를 넣으면 ipv4라우터가 ipv6운반가능

5. routing algorithm 

graph abstraction

네트워크를 graph, router를 node, link를 edge로 표현

routing algorithm으로 최저비용경로 탐색

Link state routing algorithm

-node가 global inforamtion(전체 link의 state)을 알고 있는 경우, 한 노드에서 다른 모든 노드로 까지의 경로비용을 계산 할 수있다

-다익스트라 알고리즘 사용 : d(s,z) = min( d(s,y) + w(yz) )

distance vector algorithm

-node가 주변노드까지의 비용정보만 알고있는 경우, 나의 정보와 주변노드가 주는 정보를 가지고 비용 계산

-bellman ford algorithm 사용 : dx(y) = min( cost(x,y) + dv(y) )
=> 인접노드로부터 새 정보가 올때마다 나의 table업데이트
=> 계속 반복하여 업데이트하면 실제비용에 수렴

link cost change

good new : link cost가 줄어드는 경우 -> 짧은 iteration으로 update 가능

bad news : link cost가 늘어나는 경우 -> update를 위해 많은 iteration 필요 : “count-to-infinity problem”
-> 해결법 : poisoned reverse : 방문했었던 노드를 다시 돌아가는 경우 cost를 무한대로 설정

link state algorithm vs distance vector

1. message complextiy
LS : O(nE) : n 노드갯수, E edge갯수
VS : 이웃과 주고받는 것이 전부

2. speed of convergence
LS : O(n^2)
DV : 매우다양, count-to-infinity problem 가능

3. robustness
LS : 각각의 노드는 자신만의 table만을 계산
DV : 이웃 노드가 전달한 잘못된 path cost는 네트워크 전체로 전파됨

Hierachical Routing

- AS, Autonomous System : 공통의 routing protocol을 사용하는 라우터 집합

- intra-AS routing protocol : AS에서 통용되는 routing protocol

- inter-AS routing protocol : 서로다른 intra-AS routing protocol을 사용하는 AS간의 연동을 위한 routing protocol

- gateway router : 서로다른 AS들을 연결하는 라우터

6. Routing in the internet 

intra-AS routing protocol
: AS에서 통용되는 routing protocol
ex) RIP, OSPF

inter-AS routing protocol
: 서로다른 intra-AS routing protocol을 사용하는 AS간의 연동을 위한 routing protocol / ex) BGP

RIP

-distance vector algorithm 사용

-30초마다 이웃들과 정보교환 (advertisement는 UDP)

-link failure : 180초동안 advertisement 없으면 해당링크는 버림

OSPF

link state algorithm 사용

OSPF advertisement는 AS전체로 전파

BGP

inter-AS routing protocol

eBGP : 이웃 AS들끼리 subnet reachability 정보제공

iBGP : AS 내부의 router들에게 reachability 정보 전파

intra-AS vs inter-AS

1. policy

intra-AS : 단일 admin이므로 policy decision 필요x

inter-AS : admin은 트래픽경로 어떻게 설정될지 control

2. performance

intra-AS : 성능이 중요

inter-AS : 성능보다 policy가 더 중요

7. Boradcast and Multicast routiong

broadcast routing

패킷을 다른 모든 노드들에게 전달

방법1 : flooding : broadcast packet을 받은 노드는 인접노드에게 복사하여 전송 -> cycle&broadcast storm문제

방법2 : controlled flooding : 내가 이전에 받았었던 패킷이면 broadcast x

방법3 : spanning tree : cycle이 없고 모둔 노드를 포함하는 spanning tree를 만들어 노들의 경로를 따라서 패킷을 forwarding -> kruskal, prim

multicast rouiting

특정 다수 node에게 동일한 패킷을 전달하기 위해 multicast tree를 구성하는 routing protocol

1. transport layer service
2. multiplexing and demultiplexing
3. connectionless transport : UDP
4. principle of reliable data transfer
5. connection-oriented transport : TCP
6. principle of congestion control
7. TCP congestoin control

1. 네트워크 어플리케이션 원리

네트워크 어플리케이션
: 웹, 전자메일, ...

네트워크 어플리케이션 구조
1. client-server 구조 -> web, 파일전송, 전자메일
2. peer-to-peer 구조

client-server구조의 server
- 항상 켜져 있는 호스트
- 영구적인 ip주소를 갖는다
- 클라이언트 호스트들의 요청을 받는다
- 많은 요청에 응답하기 위해 수 많은 호스트로 구성된 데이터센터가 서버로 사용

client-server구조의 client
- 서버에게 연결요청을 하는 호스트
- 서버와 간헐적으로 연결된다
- 동적 ip를 갖는다
- 클라이언트간에 직접통신은 하지 않는다

p2p 구조
- 항상 켜져있는 특정서버는 존재하지 않는다
- 임의의 호스트(peer)는 서로 직접 통신한다
- peer들은 서로 서비스를 요청하고 제공도 한다
- self-scalability : 새로운 peer는 새로운 서비스 요청임과 동시에 새로운 서비스 제공
- 피어들은 간헐적으로 연결되며 ip주소가 변화한다
- p2p구조의 분산구조특성으로 복잡성관리, 성능, 신뢰성등 control 필요

flow : 다른 두 프로세스가 통신할 때의 data흐름
- 5요소 : src ip, src port, dest ip, dest port, protocol

application layer protocol
: 호스트에서 실행되는 어플리케이션의 프로세스가 다른 호스트의 프로세스와 서로 메시지를 보내는 방법을 정의 => 1교환메세지타입, 2메시지타입문법, 3message semantic, 4언제 어떻게 메시지를 전송하고 응답하는지 결정하는 규칙

네트워크 어플리케이션과 application layer protocol => application layer protocol은 네트워크 어플리케이션의 한 요소

2. Web 과 HTTP 

웹 : 사용자가 필요에 따라 문서를 얻는 네트워크어플리케이션

웹 구성요소
1. 웹 페이지 : 웹서버에서 얻는 문서,객체로 구성
2. URL : 객체의 주소
3. 웹 브라우저 : 요청한 웹페이지를 보여준다
4. 웹서버 : 클라이언트의 요청에 대한 응답으로 객체를 보낸다
5. HTTP : 어플리케이션 계층 프로토콜 -> 어떻게 웹페이지를 요청하고 전송하는지 정의 -> TCP이용

HTTP connection
- non-persistent http : 서버가 클라이언트에게 객체를 전송할 때마다 연결을 생성 및 종료
- persistent http : 하나의 connection을 만들고 여러 객체를 보낸다

non persistent http 연결과정

http client가 tcp 연결시도. req 메시지 전송

http server는 연결수락, res 메시지 전송

client는 원하는 객체를 req메세지로 요구

server는 req를 받고 client가 원하는 객체를 res 메시지에 담아서 전송

server는 tcp 연결 끊는다

client는 원하는 res 메시지로 원하는 객체를 받음. 다른 객체를 원할 때마다 새로 tcp 연결요청

=> non persistent http의 response time
= 2RTT + file transmission
= 1RTT(1~2) + 1RTT(3~4) + file전송
* RTT= 패킷이 서버에 갔다가 돌아오는데 걸리는시간
=> 한계
1. 요청 객체마다 새로운 연결 설정

2. 객체 요청마다 2RTT 소요 -> 비용 크다

persistent http 과정

1. http client가 tcp 연결시도. req 메시지 전송

2. http server는 연결수락, res 메시지 전송

3. client는 원하는 객체를 req메세지로 요구

4. server는 req를 받고 client가 원하는 객체를 res 메시지에 담아서 전송

5. 이후 객체 요청과 응답을 같은 연결을 통해 보냄

=> 각 객체는 1RTT 소요

cookie

: 서버가 history정보를 기록하여 사용자를 추적할 수 있도록 함으로써 사용자의 다음 웹브라우징시 다양한 편의제공

쿠기 4가지 요소

http response message

http request message

user host에서 쿠키파일 유지

back-end database

쿠키를 이용한 상태유지
: cookie를 사용시 protocol endpoint에서 state을 유지하며 http message가 state을 운반함으로써 stateless한 http가 stateful한 서비스 제공
ex) authorization, shopping cart, 추천

쿠키장점 : 사용자정보를 저장하여 다양한 기능 제공

쿠키단점 : 보안

web cache = proxy server

-정의 : 웹서버를 대신하여 http request를 충족시키는 네트워크 개체

-작동방식

브라우저는 웹캐시와 먼저 tcp 연결하고 웹 캐시에 http request를 보낸다

웹 캐시는 요구된 객체의 copy가 자신에게 있는지 확인하고 저장되어 있으면 해당 객체를 http response 메시지로 클라이언트에게 전송

저장되어 있지 않으면 웹 캐시는 웹 서버와 tcp 연결하고 클라이언트가 요청했었던 객체를 웹 서버에 http request메세지로 요청

웹 캐시가 웹 서버로부터 http response 수신시 객체를 local storage에 저장하고 객체의 copy를 tcp연결한 클라이언트에게 전송

=> 웹캐시는 클라이언트이자 서버

-효과

클라이언트의 request에 대한 응답시간 감소

서버로 접속하는 링크상의 트래픽감소

인터넷 전체 웹 트래픽 감소

속도비교 => 강의정리 ch2 6페이지

3. FTP

ftp 정의

: file을 주고 받을 때 사용하는 프로토콜 -> 21번포트

FTP connection

ftp 서버의 21번포트로 tcp control connection

클라이언트는 connection을 통해 file transfer command전송

서버가 file transfer command 수신시, 2nd tcp data connection을 open

파일전송이후, server는 data connection을 닫는다

=> ftp는 2채널 이용 : “out-of-bound” : control connection과 data connection이 다른 밴드에서 이루어짐

4. 전자메일

전자메일 구성요소

user agent

mail server

SMTP

mail access protocol : POP3, IMAP

user agent : 사용자가 메일을 읽고 작성하게 해주는 프로그램 -> 메일 서버로부터 메시지를 가져오거나 보낸다

mail server : 메시지를 유지관리하는 프로그램

구성요소

메일박스 : 메시지 수신시, 수신한 메시지를 유지관리

메시지 큐 : 메시지 송신시, 메시지는 큐에 보관되어 차례대로 송신됨

SMTP

인터넷 전자메일을 위한 application layer protocol

역할 : 클라이언트(송신자)메일서버에서 서버(수신자)의 메일서버로 tcp를 이용하여 메시지전송

transfer 과정 : handshaking->transfer->closure

SMTP 특징

SMTP는 25번 포트 사용

direct transfer : 중간 메일서버를 사용하지 않음

command/response interaction

메시지는 7비트 ASCII

SMTP는 persistent connection 이용

SMTP 메일전송 시나리오

A가 user agent를 이용하여 메시지를 작성하고 B의 전자메일 주소로 전송하라고 명령

A의 user agnet는 메시지를 mail server에 보내고 메시지는 message queue에 놓인다

A의 mail server의 SMTP 클라이언트는 B의 mail server의 SMTP server와 tcp cconnection open

SMTP 클라이언트는 메시지 전송 : push protocol

B의 mail server의 mail box에 메시지가 놓인다

B는 user agent로 mail box의 메시지를 가져온다
=> how? message access protocol : POP3, IMAP

mail accesss protocol

mail 수신자가 자신의 메일서버에 있는 메시지를 얻기위해 사용하는 프로토콜

종류

POP3 : 간단한 mail access protocol로 사용자인증, 메시지다운로드 기능만 수행

IMAP : 좀더 다양한 조작 기능 제공

POP3

pop3의 3단계

authorization : 사용자인증위해 이름, pw 입력

transaction : 메일다운로드, 삭제표시, 삭제표시취소

update : quit 명령시 삭제표시된 메시지 삭제

pop3 특징

“download and delete” 모드에서 user agent가 메일 읽으면 mail server에서 해당 메일 삭제

“download and keep”모드에서 user agent가 메일 읽어도 해당 메시지의 복사본이 mail server에 남겨짐

pop3서버는 pop3의 상태정보 전달x -> stateless

IMAP

pop3보다 더 다양한 기능을 지닌 mail access protocol

특징

imap server(mail server)는 메시지를 폴더에서 관리하는 방식 사용, 처음 메시지가 서버에 도착하면 하나의 폴더에 모든 메시지 저장

imap protocol은 사용자로 하여금 메시지를 폴더별로 관리할 수 있게함

imap 세션을 통해 user state 정보 유지 -> stateful

HTTP vs SMTP

http : pull protocol : 사용자가 서버로부터 정보를 가져온다
SMTP : push protocol : smtp client가 smtp server에게 메시지 전송

http와 smtp 둘다 ASCII command/response interaction 사용

http는 non-persistent connectoin 또는 persistent connection으로 연결
smtp는 persistent connection으로 연결

5. DNS 

dns 정의

distributed database로써의 dns
: 많은 name server들의 계층구조로 구현

application layer protocol로써의 dns
: 호스트가 distributed database의 name server와 질의를 하여 hostname을 Ip address로 변환할 수 있도록함

DNS 기능

hostname to ip address translation

host aliasing

mail server aliasing : 기업의 메일서버와 웹서가 같은 hostname으 갖도록 함

load distribution

centrailize DNS 단점

singli point of failure : name server고장시 전체 서비스 다운

traffic volume

distant centrailize database

maintenance

확장성이 없다

DNS동작원리->hostname to ip address translation

1. 클라이언트가 www.amazon.com에 접속 시도

2. 클라이언트가 local dns server에 접속하여 www.amazon.com의 ip주소 질의

3. local dns server가 해당 주소 있으면 ip주소 보내고 없으면 root dns server에 com dns server의 ip주소 질의

4. root dns server가 com dns serv를 갖는 TLD server의 ip주소를 local dns server에 보낸다

5. local dns server는 TLD server에 접속하여 amazon.com dns serv의 ip주소질의

6. TLD 서버가 amazon.com의 dns server를 가진 authoritative server의 ip주소 보낸다

7. local dns serv는 해당 authoritative server에 접속하여 www.amazon.com의 ip주소 질의

8. authoritative 서버는 www.amazon.com의 ip주소 전송.

9. local dns server는 name-to-address translation 쌍을 캐시에 보관하고 클라이언트에게 ip 주소 전송

DNS 계층

- root dns server
: 최상위 서버, local name server가 hostname을 풀지 못하면 다음으로 접속되어 hostname에 해당하는 TLD server의 ip주소를 보낸다

- TLD server (top level domain server)
: com, org, kr와 같은 상위도메인이나 국가 도메인을 담당하는 서버. authoritative dns server들에 대한 ip주소 제공

- authoritative dns server
: hostname을 ip주소로 매핑하는 dns레코드를 제공

- local dns server

dns 계층구조에는 속하지 않지만, dns 구조 중심에서 호스트가 송신한 dns query는 local dns serverd에 제일 먼저 전송. local dns servers는 name-to-address translation 쌍을 캐시에 보관하고 있으며 proxy와 같은 역할 한다.

dns name resolution 방식

- iterated query
: local dns server가 root dns server부터 차례대로 박복적으로 질문하고 응답 받으며 hostname에 해당 하는 ip주소 찾아간다

- reculive query
: query를 받은 서버가 다음 server에게 질의를 하며 hostname의 ip주소를 찾아간다 -> local dns server의 load를 줄임

dns caching
: 응답을 맏은 모든 server(local, roo, tld, authoritative)는 해당 정보를 로컬메모리에 저장. 캐시엔트리는 TTL지나면 사라진다

6. p2p 

p2p 특징

no always-on server

임의의 호스트들이 직접 통신

peer들은 간헐적으로 연결되며 ip가 바뀌기도 한다

peer는 서버이면서 클ㄹ라이언트이다

self-scalability를 가진다

1. 인터넷이란? 

구성요소로 본 인터넷
: 수십 억개의 호스트(end system)을 통신링크와 패킷스위촐 연결하는 네트워크들로 구성된 네트워크

프로토콜
: 메시지 송수신의 형식과 순서를 정의하고, 메시지 송수신의 액션을 정의하는 규약

서비스로서의 인터넷
: 인터넷은 한 edge system에서 다른 edge system으로 데이터를 전달하는 서비스를 애플리케이션에게 제공하는 인프라구조

2. 네트워크 엣지

네트워크 엣지
: 인터넷에 연결된 디바이스

엑세스 네트워크
: 데이터 전송 경로상에서 호스트와 첫 번째 라우터가 연결되어 이루는 네트워크

physical media
: 비트가 전달될 때 거치는 매체
- guided media : 광섬유 케이블 같은 견고한 매체
- unguided media : 무선 LAN처럼 야괴공간에서 파형으로 전파하는 매체

transmission rage R = bits/sec

packet transimission delay D = 비트길이(L)/R

3. 네트워크 코어

네트워크 코어
: 라우터와 링크들의 연결망

주요기능
1. routing: 목적지까지 최저비용경로를 계산 및 설정
2. forwarding : 패킷이 라우터에 도착하면 목적지에 도착하기 위한 올바른 출력링크 설정

packet switching
: 패킷의 목적지주소정보를 보고 올바른 경로로 전달하는 기법

=> store-and-forward
: 라우터는 입력링크로 전체 패킷을 받은 후에 출력링크로 전송할 수 있다.
=> 문제점1 end-end delay : 경로상의 링크 개수만큼 전송 속도 증가 D = L(비트길이)/R * N(링크갯수)
=> 문제점2 queuing delay : 라우터에서 패킷이 나가는 속도보다 들어오는 속도가 더 ᄈᆞ르면 패킷은 버퍼에서 대기해야 하므로 delay 발생
=> 문제점3 packet loss : 라우터의 버퍼가 꽉차 있는 경우 새로 도착한 패킷은 drop

circuit switching
: 데이터 통신에 사용될 전용회선을 결정. 이렇게 결정된 회선은 공유되지 않고 해당 통신을 위해서만 할당됨
=> 문제점 : 한 통신을 위해서만 회선이 할당되므로 효율성 떨어짐
=> 해결방안 : 다증화기술
1. FDM : 주파수대역으로 나누어 여러사용자가 사용
2. TDM : 시간단위로 나누어 여러사용자가 사용

packet switching vs circuit switching
1. packet switching은 필요시만 링크의 사용을 할당하므로 circuit switching보다 더 많은 사용자가 네트워크 이용할 수 있다
2. packet switching은 혼잡제어, reliable data tansfer를 위해서는 delay and loss protocol 필요

4. 패킷교환 네트워크의 delay, loss, throughput

delay 발생원인 : 라우터에 패킷이 들어오는 속도가 나가는 속도보다 빠르면 버퍼에 패킷들이 대기하는 현상 발생

delay 유형
1. nodal processing delay : dproc
: 패킷헤더를 조사, 어느 출력링크로 보낼지 계산, 비트 오류 검사등을 하는데 걸리는 시간
2. queuing delay : dqueue
: 패킷이 큐에서 링크로 전송되기를 기다리는 시간
3. transmission delay : dtrans
: 라우터가 패킷의 모든 비트를 밀어내는데 걸리는 시간 dtrans = L(패킷길이)/R(링크의 전송률)
4. propagation delay : dprop
: 링크의 처음부터 다음 라우터까지 전파에 걸리는 시간 dprop = d(피지컬링크길이)/s(전파속도)
=>total d = dproc + dqueue + dtrans + dprop

delay example
1. caravan analogy -> ch1 강의자료 p60
2. traceroute : 구간 n(n-1라우터~n라우터)의 delay = (sender~n라우터 전송시간)-(sender~n-1라우터 전송시간)

loss 발생원인 : 버퍼가 꽉 차 있는 상태에서 새로운 패킷이 들어오는 경우 해당 패킷은 drop
=> 어ᄄᅠᆫ packet을 drop할 것인가?

throughput(처리율)
: 얼마만큼의 비트를 단위시간동안 전송할 수 있는가
sender – link(R1) - router – link(R2) - recevier
R1 < R2 인 경우, 문제없이 패킷은 수신측에 도착
R2 < R1 인 경우, delay, loss 발생, bottleneck link = link2, R(total) = min(R1, R2, ..., Rn)

5. Protocol layer 

layering 계층화
: 네트워크 프로토콜을 기능별로 모듈화하여 해당 모듈은 특정서비스만을 구현

계층화 필요성
1. explicit structure : 네트워크의 명확한 구조 덕분에 시스템간의 관계나 기능 파악 용이
2. modularization : 모듈화는 시스템의 유지보수 및 업데이트를 용이하게 한다

protocol stack
: 다양한 계층의 프로토콜 집합
ex) 인터넷 프로토콜 스택(=tcp/ip 5계층), osi 7계층

인터넷 프로토콜 스택
- application layer(5계층) : 네트워크 어플리케이션을 지원(메세지) -> http, ftp, smtp, ..
- transport layer(4계층) : 프로세스간 통신 서비스 제공(세그먼트) -> tcp, udp
- network layer(3계층) : 호스트간 통신 서비스 제공(패킷=데이터그램) -> ip프로토콜, 라우팅프로토콜..
- link layer(2계층) : 물리적연결된 노드간 브로드캐스팅 서비스 제공(프레임) -> mac protocol
- physical layer(1계층) : 프레임 내부의 비트를 한 노드에서 다른 노드로 이동시키는 서비스제공

osi 7계층
- application
- presentation
- session
- transport
- network
- link
- physical

Encapsulation
: 상위계층의 정보를 받아 현재계층의 헤더정보를 추가하는 것
메시지(5계층)->세그먼트(4)->패킷=데이터그램(3)->프레임(2)

1. Business process and Funcrtional modeling

requirement를 functional model로 설계

requirements들로부터 use-case 설계

use-cases들로부터 activity diagram 설계

2. Use-case & use-case diagram

Use-Case 정의

- 소프트웨어 시스템이 주변 환경과 어떻게 상호작용하는지, 유저가 소프트웨어 시스템을 어떻게 사용하는지 표현

각각의 use-case는 1개의 기능만을 묘사

use-case는 block들을 만들고 block들에는 연속적인 activity들이 담겨있다

Use-Case identification

1. 요구사항 분석

2. subject boundary 확인하여 시스템이 해야하는 일과 안해도 되는 일 구분

3. 주요 actors과 그들의 목표 확인

4. business process와 주요 use-cases 확인

5. 현재 만들어진 use case들을 재검토하여 올바른 size인지, 추가적인 use cases가 있는지 확인

use-case diagram 정의

- Use Case를 그림으로 표현한 것

Use Case Diagram의 4가지 원소.

1. Actors : 유저 또는 소프트웨어 시스템이 상호작용하는 다른 시스템

2. Associations : actors와 use-cases를 연결하는 선으로 interaction, inclusion, extension, generalization과 같은

관계를 나타낸다

3. Use-case : 요구사항에 따라 만들어져서 유저에게 이익을 주는 시스템의 주요한 프로세스

4. Subject boundary : 시스템의 범위를 나타내는 박스

Use-ase Diagram 생성과정

1. use cases를 그리고 배치

2. actors를 그리고 배치

3. subject boundary를 그린다

4. actors와 use cases의 관계, use case와 use case의 관계를 추가

3. Activity Diagram

Activity Diagram

business processes를 구성하는 activity들의 sequence를 묘사하는 활동다이어그램

- 함축적이며, 일반적인 상황에서의 프로세스들을 표현한다

- object들의 독릭접인 행동들을 설계한다

- 모든 타입의 프로세스에 사용될 수 있다.

Activity Diagram syntax

action & activity : 엑션과 액션집합 표시

control flow : 실행의 순서 표시

initial node : 액션집합의 시작점

final node : 액티비티에서 flow가 끝나는 지점

decision node : test condition 표시

Activity Diagram elements

- Actions : 특정 비즈니스 reason을 위해 수행되는 것, 동사와 명사로 표시됨, action은 더 이상 나눠질 수 없다

- Activities : 특정 비즈니스 reason을 위해 수행되는 것, 동사와 명사로 표시됨, activities는 더 나눠질 수 있다.

- Object Nodes : 한 activity에서 다른 activity로의 정보흐름을 나타냄

- Control Flows : 실행 경로를 설계

- Object Flows : object들의 흐름을 설계

- Control Nodes : 여러 activities들중에 어느 activity로 진행 할 것인지 결정하는 node

Control Nodes의 7가지 타입

- initial node : actions/activities의 시작

- final-activity node : actions/activities의 끝

- final-flow node : 한 excution path는 멈추지만 다른 excution path들은 계속 수행되는 node

- decision node : 어떤 path는 계속진행 되고, 어떤 path는 멈추는지 결정하는 node

- merge node : 상호 연관성 없는 path들을 하나로 결합하는 node

- fork node : 하나의 excution path를 한개 이상의 병렬 path들로 나누는 node

- join node : 병렬 excution paths들을 하나로 결합하는 node

Swimlanes

- Activity Diagram의 대표적 형태 중 하나

- object들 마다 어떤 activity를 수행해야 하는지 object마다 나누어서 표현

- object들 사이의 구분된 역활을 나타낸다

- 가로 혹은 세로로 표현될 수 있다.

Guideline for Activity Diagrams

- 설계된 activity의 scope를 정한다.

- activities들을 선언하고, flowsfh activities들을 연결

- control node를 선언하여 어떤 path로 decision을 할지 만든다

- 프로세스에서 parallelism을 만든다.

- Activity Diagram을 그린다

Creating an Activity Diagram

- 요구사항, use-case diagram, documentation을 review하고 business process를 선택한다

- business process에서 사용되는 activities들을 선언

- control flows와 control nodes를 선언

- object flows와 object noodes를 선언

- 레이아웃을 하고 diagram을 그린다. 이때 crossing line을 최소화 하도록 한다

4. Use-case description

정의 : use-case를 표현하는 하는 문서

Elements of Use-case description

1. use-case name : use-case 이름

2. id : use-case의 id 번호

3. importance level : use-case의 중요도

4. primary actor : use-case의 주요 actor

5. use-case type

6. stakeholders and interests : 해당 use-case 사용자들과 그들의 관심

7. brief description : use-case에 대해나 짧은 설명

8. trigger : use-case를 trigger하는 조건상황

9. type

- external = 외부의 actor가 트리거

- internal = 내부의 또다른 use-case가 트리거

10. relationship

- association : 연관관계 -해당 use-case와 연관 있는 actor 또는 다른 use-case

- include : 포함관계

- extend : 확장관계

- generalization : 상속관계

11. normal flow of events : use-case 안에서 일어나는 stepe들. 한 step안에서는 작은 여러 step들 존재 가능

12. subflows : normal flow 외에 수행되는 부가적인 flow

13. alternative/exceptional flows : 필요시, 추가적으로 수행되는 flow

Use-case description 생성과정

1. high prority use-case를 선택하고 overview를 작성

- primary actor 나열

- tpye 결정 : overview 또는 detail / essential 또는 real

- 모든 stakeholders 과 그들의 interests 나열

- use-case의 importance level 결정

- brief description 작성

- 무엇이 use-case를 trigger하는지 나열

- 해당 use-case와 다른 use-case간의 관계 나열

2. normal flows of events의 step들을 작성

3. step들이 너무 복잡하지 않고, 길지 않고, 다른 step들과 일관성있는 사이즈가 있도록 한다

4. alternate/exceptional flow를 결정하고 작성

5. use-case description을 검토하고 올바름을 결정

6. 위의 과정들을 반복 실행

5. Verifying & Validating a use-case

use-case는 structural and behavioral modeling 단계 이전에 검증되어야 한다

지금까지 만들어진 model들과 diagram들을 review한다

사용자와 development team이 같이 검토한다

facilitator : 미팅을 스케쥴을 잡고 진행

presenter : review된 것을 프리젠테이션한다

recorder : review를 기록하고 에러들을 기록한다.

1. Project initiation

project management : 올바른기능, 최소비용, 명시된시간 안에 진행되는 시스템개발을 관리 및 계획하는 프로세스

project manager : task와 role이 잘 조절되도록 관찰 및 관리

Project identification : 프로젝트의 목표, 방향, 결과정의

-project는 비즈니스밸류로부터 도출

business value

tangible value : 셀 수 있고 측정가능한 밸류 (ex: 비용)

intangible value : 셀 수 없고 측정불가능한 밸류 (ex: 사용만족도)

System request

: 새로운 시스템을 만들 때 해당 기능을 가져야하는지 이유와 어떤 가치가 추가되는지를 명세하는 문서.

다음의 5가지 요소 포함

1. Project sponsor : 프로젝트의 일차적인 연락 지점

2. Business need : 프로젝트를 시작하는 이유

3. Business requirements : 상업적 요구사항을 만족 시킬 시스템의 기능

4. Business value : 시스템의 기능으로 하여금 어떻게 사용자들이 가치, 이익을 엊게 될 것인가

5. Special issues : 그외 프로젝트를 진행하면서 고려해야 할 사항.

2. Feasibility Analysis

: 프로젝트에 어떤 리스트가 있고 해당 리스크를 극복할 수 있는지 프로젝트의 실효성 분석

Techinal feasibility

Economic feasibility

3. Organizational feasibility

Techinal feasibility, 기술적 실효성

개발하고자 하는 소프트웨어를 실제로 개발할 수 있는 역량, 기술을 가지고 있는지 분석한다.

이를 위해 다음 4가지 risk를 파악해야 한다.

1. the functional area : 분석가가 소프트웨어가 사용되는 해당 비즈니스 영역에 대해 잘 알고 있는가

2. the technology : 사용하고자 하는 기술을 잘 알고 있는가

3. project size : 프로젝트의 사이즈가 클 수록 더 많은 risk 존재

4. compatibility : 개발하고자 하는 소프트웨어가 사용환경 속에서 다른 소프트웨어들과 호환이 가능한가

Economic feasibility 경제적 실효성

경제적가치가 있는지 분석하기위해 비용(인건비, 자원, 특허권사용)과 이익(매출, 미래가치)을 파악하고 가치를 할당해야한다.

비용과 이익을 파악하여 cashflow(현금흐름)을 산정한다.

가치를 산정하기 위해서는 다음과 같은 방법들이 있다.

1. ROI (Return on Investment) = (total benefits - total costs) / total costs : 투자대비 얼마나 이익을 얻었는가

2. Break-Even Point = (yearly net cash flow - cumulative net cash flow) / yearly net cash flow : 손익분기점

3. Present Value (PV) = cash flow amount / (1 + interest rate)^n (n = number of years in the future) : 현재가치

4. Net Present Value = Σ PV benefits - Σ PV costs : 순현재가치

Organization feasibility, 사회적 실효성

: 사용자에게 잘 받아들여질 것인가 또는 사회에게 소프트웨어가 윤리적, 사회적에서 허용될 수 있는지 분석하는 단계이다.

- Stakeholder analysis : 프로젝트에 의사결정권을 가진 관계자들의 분석

- sponsor : 시스템의 중요성에 대해 다른 관련자들과 의사결정을 논의

- organizational management : 소프트웨어를 사용할 사람들이 잘 받아들이도록 분석

- system user : 실제 사용자들의 의견을 분석하여 반영

3. Project selection

프로젝트는 가치와 리스트에 의해 승인되거나 거절되거나 지연된다

4. Project management tools

workplans을 만드는데 도움을 주는 tool로써

큰 작업을 작은 여러 작업들로 어떻게 나눌지 정의하며 작업들의 순서와 작업소요시간을 결정한다.

Work Breakdown Structures(WBS) 라는 계층적 구조로 나타냄으로써 작업들의 duration, current state, task dependency를 명확히 표현할 수 있다

대표적은 WBS로는 Gantt chart와 PERT가 있다.

Gantt chart는 WBS를 나태내는 수평적인 바 차트로써 작업들의 dependency, duration, current state를 이해하기 쉽게 나타내며

PERT는 diagram으로 표현된 task들을 network형식으로 나타내어 dependeny를 한 눈에 알아볼 수 있다.

5. Project effort estimation

프로젝트의 functionality, time, cost간의 trad-off를 측정하고 프로젝트의 시간과 비용에 대한 value를 할당하는 과정

use-case estimatoin에는 technical complexity factors(13)와 environmental factors(8)존재

6. Creating & Managing the Workplan

workplan : 프로젝트를 완료에 필요한 task들을 변화하고 순차적인 리스트로 표현한 것이다.

workplan은 기존 또는 완료된 프로젝트의 workplan을 변경하여 사용

Structured Development Methodology나 Rapid Application Development Methodology를 적용하여 task들을 생성‘

Work Breakdown Structure (WBS)

전체 프로젝트에서 일관성있게 task들을 조직하고, 반복적이고 증강되는 방식으로 커다란 work를 task 단위로 나누어서 생성하는 구조

과거의 실패나 성공으로부터의 학습을 현재에 적용해 나간다.

Scope Management : task의 사이즈인 "scope"를 관리

scope creep(변화)는 프로젝트가 진행 후 발생하며, 새로운 요구사항을 추가해야 하는 경우가 발생한다.

스케줄상에서 해로운 효과를 가지기 때문에 project manager는 scope creep을 줄이기 위한 노력을 해야한다.

프로젝트 scope 관리 기술

1. 시작단계에서 모든 요구사항 정의

2. 절대적으로 필요한 변화만을 허용

3. 변화에 의한 영향을 면밀히 검사

4. 꼭 필요한 변화가 아니면 다음 버전을 위해 지연

5. time boxing, 시간관리

7. Staffing the project

목표

얼마나 많은 사람이 필요한지 결정

필요한 activity에 맞는 스킬 셋 연결

팀에게 올바른 목표를 설정

갈등 최소화

산출물 : staffin plan (다음의 요소 포함)

어떤 사람이 얼마나 할당되는가

보고체계

project charter 프로젝트 선언

Staffing plan

필요한 사람의 수 = 한사람이 프로젝트 완료하는데 걸리는 시간 / 프로젝트완료 제한기간

Motivating People

motivation은 퍼포먼스에 가장 큰 영향을 준다

돈으로 보상하는 것은 motivate이 되지 않는다

motivateing 기술

사람대 사람간의 친분

팀 오너쉽

멤버들이 흥미있는 것에 집중할 수 있도록한다

공평한 보상

그룹 오너쉽 격려

Handling confilct : 갈등을 예방하고 완하는 것

cohesiveness는 가장 큰 효과 있다

역할을 분명히 하고 팀 멤버들이 책임감 있도록 한다

work 와 커뮤니케이션 규칙을 확립

8. Environment & Infrastructure management

Environment : 올바른 tools을 선택

올바른 CASE tool 사용

생산성증가, 정보 집중화

다이어그램 활용하여 이해도 향상

기준을 확립하여 복잡도 감소

Infrastructure

프로젝트를 올바르게 문서화하여 산출물생성

산출물과 커뮤니케이션을 저장

unified process standart document 이용