Class_2022_2

1. 데이터네트워크


Evaluation
  • midterm 35% + final 40%
  • quiz/homework/term report 15%
  • attendance 10%

Textbook
Behrouz A. Forouzan
Data Communications and Networking with TCP/IP Protocol Suite
6th Edition, McGraw-Hill Education

19년까지는 William Stallings 교재를 사용했었다

Chap 1-13 중 1-8까지 다루며, 9 10은 시간 남으면 하고 아마 안할거같다

Chap 1 Intro
Chap 2 physical_layer
Chap 3 datalink_layer
Chap 4 LAN
Chap 5 WAN
Chap 6 장치연결과 가상랜
Chap 7 network_layer: data transfer
Chap 8 network_layer: routing of packets
Chap 9 transport_layer
Chap 10 application_layer
Chap 11 multimedia
Chap 12 network management
Chap 13 cryptography and network_security


네트워크 관련 자료들




network_topology?
{
네트워크,network 위상,topology?
각 station을 연결하는 방법들

mesh topology
star topology
central controller에 연결, 그것을 대개 hub라 칭함.

bus topology
하나의 긴 cable인 backbone이 있고, 각 station에서 거기에 drop line으로 연결. 그 접점은 tap.

ring topology
하나의 긴 ring이 있고, 각 station에서 거기에 연결하는 접점은 repeater.

hybrid topology

(Forouzan)
}

network_model
OSI_model

1.1. 20220915 2장

//curr at 비트,bit
bit_length = 1 / bit_rate
비트길이,bit_length

디지털신호,digital_signal
{
A digital signal is a composite analog signal with frequency between zero and infinity.
그래서 bandwidth가 무한이 된다.
이 때 transmission 방법은 두 가지가 있는데,
  • 베이스밴드 : 디지털신호를 (아날로그 신호로 바꾸지 않고) 그대로 보냄
  • 브로드밴드 : 디지털신호를 아날로그 신호로 바꾸어 보냄
(원문)
  • baseband : sending the digital signal without changing it to analog signal. // baseband_transmission
  • broadband : changing the digital signal to analog signal and send the analog signal. // broadband_transmission
(Forouzan)

...merge...

// 띠,band? or 밴드,band later
baseband : sending the digital signal without changing it to analog signal
broadband : changing the digital signal to analog signal and send the analog signal
}


signal impairment
attenuation 감쇠?
distortion 왜곡?
noise 잡음, 노이즈


attenuation 감쇠?

이것을 보상하기 위한
행동이 증폭,amplification
장치가 amp(amplifier), repeater
amp는 잡음도 같이 증폭하는데, repeater는 decoding을 하고 증폭한다.

Ex 2.5
신호,signal가 transmission_medium을 지나면서 power가 절반으로 줄어들었다. 즉
$P_2=0.5P_1$
이 때 attenuation(loss of power) 계산은
$10\log_{10}{P_2 \over P_1} = 10\log_{10}{0.5P_1 \over P_1}$
$=10\log_{10}0.5$
$=10\times (-0.3)$ ..... approximation?
$=-3\,{\rm dB}$
결론은 (power가 절반으로 줄은 것) = 3 dB가 줄은 것(−3 dB)


noise


비슷한 방식으로 SINR도 생각할 수 있다.
${\rm SINR} = \frac{\rm signal}{\rm noise+interference}$
QQQ 통신에서의 간섭,interference이란 정확히?

둘 다 통신 상황에 대한 metric.


2.2.3 data rate limits (slide p31)

data_rate는 세 factors에 의존
  1. 가능한 bandwidth
  2. 신호의 level
  3. 채널의 quality (noise의 level)



Nyquist bit rate
noiseless channel에 대해,
이론적으로 가능한 최대의 (upper limit) bit_rate를 정의함.
${\rm bit rate} = 2 \cdot B \cdot \log_2 L$
여기서
$L$ - 레벨 수, 즉 $\log_2 L$ 은 몇 비트가 필요한지를. 예를 들어
L=2 levels : 1 bit/signal
L=8 levels : 3 bits/signal

Ex 2.6
256kbps를 noiseless channel로 보낸다. bandwidth=20kHz. 얼마나 많은 singal levels가 필요한가?
Sol.
Nyquist formula에 대입하면
265000 = 2 × 20000 × log2L
log2L = 6.625
L = 26.625 = 98.7 levels
근데 이게 2의 거듭제곱이 아니므로, 레벨수를 높이거나 bitrate를 줄여야 한다.
L = 64 levels인 경우 - bitrate = 240kbps ... 이건 256kbps보다 작으므로 부족하다.
L = 128 levels인 경우 - bitrate = 280kbps


Shannon capacity
noisy channel에 대해.
$C=B \cdot \log_2 (1+{\rm SNR})$
여기서
$C$ 는 capacity.

SNR이 0이라는 것은 S/N에서 N이 무한하다는 것, 즉 노이즈가 매우 심한 상태.

Ex 2.8
전화선의 bandwidth는 300 to 3300Hz(즉 3000Hz)이고 SNR은 보통 3162이다. 이 채널의 용량은
$C=3000\log_2(1+3162)=34881\,{\rm bps}$

Nyquist, Shannon 둘 다 쓰인다.

Ex 2.9
채널,channel의 bandwidth가 1MHz. 이 채널의 SNR은 63. 적절한 bit rate와 signal level?
Sol.
먼저 upper limit을 계산하기 위해 Shannon formula를 쓰면
$C=10^6 \log_2 (1+63) = 10^6 \log_2 64 = 6 \,{\rm Mbps}$
이게 upper limit인데 성능을 위해 좀 낮게 4 Mbps로 잡고, signal level 수를 구하기 위해 Nyquist formula를 쓰면
$4\,{\rm Mbps} = 2\times1\,{\rm MHz}\times\log_2 L$
$\log_2 L = 2$
$L=4$

1.2. 20220920 2장

채널용량,channel_capacity
C = B log2(1 + SNR)

그리고 C/B = log2(1 + SNR) 이건 스펙트럼효율? spectrum_efficiency { Up: 스펙트럼,spectrum 효율,efficiency } 이라 한다.

bandwidth
{
띠/밴드 폭/너비 - 띠폭, 띠너비, 대역폭 - https://www.kps.or.kr/content/voca/search.php?et=en&find_kw=bandwidth

Compare:
data_rate { WpEn:Data_rate } 와 구분.
throughput
}

throughput
{
(총 데이터 양) / (총 걸린 시간).
단위 bits/sec = bps.
data_rate와 같음.
다만 data rate는 가능한 최대용량이고 throughput은 그 중 사용한 용량.
}



latency (delay)
전체 메시지,message가,
source에서 첫 비트를 보낸 시각부터
destination에 완전히 도착할 때까지 얼마나 걸리는지 그 시간,time.

latency =
propagation delay +
transmission delay +
queuing delay +
processing delay

propagation delay = 전파되는 시간 = 거리 / 속도
물리적 선이 얼마나 긴 지에 관련

transmission delay = packet size / data rate
(= transmission time)

BDP (bandwidth-delay product) 얘기
Google:bandwidth-delay product

1.3. 20220922


'추가자료 - Line and Blocking Coding'

line_coding and blocking_coding

여러 line coding schemes

한 bit가 전달되는 시간은 bit duration.

Unipolar NRZ
0은 0, 1은 0이 아닌 어떤 값?
Polar ...bipolar와 동의어??
NRZ-L (L : level) - 0과 1의 부호(전압?)가 다름.
NRZ-I (I : inversion) - next bit가 0이면 no inversion, next bit가 1이면 inversion.
RZ - bit duration 전반은 NRZ-L과 같고, bit duration 중간에 0으로 돌아옴. (hence the name)
Polar biphase
Manchester - 0은 high→low, 1은 low→high
Differential Manchester - next bit가 0이면 inversion, next bit가 1이면 no inversion
Bipolar ...Polar와 동의어??
AMI - 0은 0이고, 1은 번갈아가며(alternating).
Pseudoternary - (AMI와 정반대) 1은 0V이고, 0은 부호를 번갈아가며.

B8ZS scrambling - AMI에서 비트가 0이 연속해서 8개나 나올 경우 일부러 AMI 규칙(alternating)을 어기는 신호를 집어넣는.
(1 뒤에 오는 0 8개) 00000000 → 000VB0VB
여기서 V는 바로 앞에 오는 1의 부호가 연속하도록, 즉 AMI규칙을 깨도록 부호를 정함(V는 violation, 위반)

HDB3 scrambling - 0000을 바꾸어주는.
현재까지의 1이 짝수개: 0000 → B00V
현재까지의 1이 홀수개: 0000 → 000V

Google:b8zs scrambling
Google:hdb3 scrambling

4B/5B - 4비트를 5비트로 보내는. 여러 control sequence를 추가하기 위해서.



2.3.2 Analog-to-Digital Conversion

PCM,pulse_code_modulation or pulse-code modulation

(Figure 2.90 Components of PCM encoder)
아날로그신호,analog_signal
PCM encoder에서 다음 세 단계를 거친다.
샘플링,sampling하고 - 출력은 Google:PAM signal
,encoding하고 - 출력은 quantized signal
,quantizing한다 (양자화,quantization)
그러면 출력은 digital_data.

sampling의 시간 간격은 보통 maximum frequency의 두 배로 정하면 된다고. (sampling_theory에 따르면) ... Google:sampling theory maximum frequency

Ex 2.13
human_voice를 digitize하고자 한다. 8 bits per sample이라면 bit rate는?
Sol.
인간 목소리는 주로 0-4000Hz 범위에 있으므로
sampling_rate = 4000 × 2 = 8000 samples/s
bit rate = 8000 × 8 = 64000 bps = 64 kbps

delta_modulation 언급.
간단. input analog signal의 진폭,amplitude그래프가 - 올라갈때 1 내려갈때 0

2-4 Analog Transmission

ASK amplitude_shift_keying
FSK frequency_shift_keying
PSK phase_shift_keying
QAM : ASK + PSK


1.4. 20220927 중에서 2장

2.4.1 Digital-to-Analog Conversion

0과 1을 sine 곡선으로 전송하므로 진폭,amplitude 주파수,frequency=진동수,frequency 위상,phase ...(tbw) 에 따라
ASK
FSK
PSK

2.4.2 Analog-to-Analog Conversion

2-5 Multiplexing

2.5.1 Frequency-Division Multiplexing (FDM)
중간에 guard band를 띄운다

2.5.2 Time-Division Multiplexing (TDM)
시간을 나누어 round-robin 형식으로
중간에 guard time을 띄운다
synchronous TDM과 statistical TDM 설명

2-6 Transmission Media
transmission_medium에는 크게 두 가지
guided
unguided - 무선 wireless

guided중에선 세 가지
twisted-pair cable
coaxial cable
fiber-optic cable
언급됨

unguided (wireless)에선
전자기스펙트럼,electromagnetic_spectrum (curr 스펙트럼,spectrum)에서 주로
radio_wave (3 kHz ~ 1 GHz)
microwave (1 GHz ~ 300 GHz)
infrared_wave (300 GHz ~ 400 THz)
각각의 특징(omnidirectional/unidirectional etc)

여기까지가 physical_layer였고, 다음부터는 data link layer.

1.5. 20220927 중에서 3장



Figure 3.3

datalink_layer는 둘로 나누어 질 수 있다(dual-link layer)
a. data-link layer of a broadcast link
위: data-link-control sublayer - flow_control, error_control, framing, ...
아래: media-access-control sublayer
b. data-link layer of a point-to-point link
위: data-link-control sublayer
아래: (X)

1.6. 20220929

3.2.2 Error Control

error_control : both error_detection and error_control

아래 둘 비교 todo

FEC,forward_error_correction
{
}

ARQ,automatic_repeat_request
{
}

Hybrid ARQ (H-ARQ) : FEC, ARQ 둘 다 쓰는 기법

Q 채널 상태가 좋으면(에러가 발생하지 않으면) FEC ARQ 둘중에 뭐가 좋을까?
A ARQ가 좋다. FEC는 부가정보를 계속해서 붙여야 한다. ARQ는 에러가 나면 다시 보내면 되므로 ARQ가 더 효율이 좋다. 그렇지 않을 땐 FEC가 좋다. 왜냐면 ARQ는 복구를 위해 round trip을 필요로 한다.

single-bit error
burst error
항상 연속적이지는 않음, 인접함.

bit error rate(BER)
비트 하나가 에러로 뒤집힐 확률 p?

block_coding
{
// slide p22
메시지,message를 각 $k$ bits의 블록blocks으로 나누며, 하나하나를 dataword라 한다.
여기에 각 블럭마다 $r$ 개의 redundant bits를 붙여 길이를 $n=k+r$ 로 만든다.
그렇게 만든 $n$ 비트 블럭을 codeword라 한다.

( $k$ bits dataword ) + ( $r$ bits ) → ( $k+r$ bits codeword )
}

// p26 Hamming Distance
해밍_거리,Hamming_distance - 서로 다른 비트,bits의 수


1.8. 20221006 1부

Data-link Layer Protocols
datalink_layer_protocol

전통적으로 여기서 flow and error control을 위해 정의된 프로토콜은 네가지
  • Simple
  • Stop-and-Wait (SAW)
  • Go-Back-N
  • Selective-Repeat (SR)
위 둘만 쓰이고 아래 둘은 사라졌다.

프로토콜,protocol 설명을 위해 FSM,finite-state_machine 사용.

대충 이런 식.
FSM for the stop-and-wait protocol:
https://i.imgur.com/jFCZfzVl.png


utilization이란?
https://i.imgur.com/dVDzcozl.png


Go-Back-N
ACK마다 숫자가 있다 - ACK(n)
ACK(n)은 n번까지 받았다는 얘기.
패킷 1을 받았으면 ACK(1)
2를 받았으면 ACK(2)
3이 안오고 4를 받았으면 ACK(2)
이른바 'cumulative ACK'.
buffer는 있을 수도 없을 수도 있다. receiver에 out-of-order packet을 위한 공간이 없을 수 있다.
sender 입장에서 packet2가 timeout이면, 2번 이후는 모두 재전송하게 된다. - 따라서 이름이 go-back-n.

Selective Repeat
receiver에 buffer가 존재. (buffer는 out-of-order packet을 저장)


1.9. 20221006 2부

HDLC - High-level Data Link Control
bit-oriented protocol for communication over point-to-point and multipoint links
implements the stop-and-wait(SAW) protocol

I-frame
S-frame
U-frame

PPP - Point-to-Point Protocol

1.10. 20221011

// p57 3-3 Media Access Protocols
MAC

알아봤듯 data link control은 두 그룹으로 나뉨:
  • data link control
  • media access control (= multiple access control)

(대충) MAC란, 동시에 여러 (..)이 있고 이들이 서로 (...)할 때, 어떻게 겹치지 않도록 처리를 (/할당을/ .../나눠주는) ...tbw
방법은
channelization
채널,channel을 나누는? chk
TDMA
CDMA
FDMA
random access = distributed access ... distributed random access?
controlled access
coordinater가 있어서 schedule을 짜 준다고.

3.3.1 Random Access
여기선 한 station이 다른 station보다 superior하지 않고,
다른 것을 control하도록 된 것도 없다(and none is assigned the control over another)

///// pure ALOHA /////
pure_ALOHA

random access 기법 중 간단한 것 하나가 ALOHA

두 station의 data가 충돌...

Frames in a pure ALOHA network
시간축에 놓인 frame(폭은 transmission time)들이 겹치는 일이 발생.
이 때 겹쳐진 시간은 collision duration이라 한다.
겹쳐지지 않으면 전송 성공.
collision이 일어나면 랜덤한 시간 후 재전송retransmit 시도. 무한번 반복하는 건 아니고 유한번.

// p62 Figure 3.25 Procedure for pure ALOHA protocol

그 연기할 랜덤한 시간은 2배씩 - exponential binary backoff

$T_{\rm fr}$ = frame transmission time

vulnerable time = 휘발성 구간 = $2\cdot T_{\rm fr}$
(상수 2를 곱함에 주목. 이건 그림 보면 바로 이해 가능, 설명하자면... '앞뒤'?)

(event를 count할 때 가장 많이 쓰는 분포?)
푸아송_분포,Poisson_distribution 식은
$P(N=k)=\frac{e^{-\lambda t}\cdot ( \lambda t )^k}{k!}$
여기서
$N$ 은 event의 수고, (사건,event)
$P(N=k)$ 는 그게 $k$ 번 발생할 확률이고,
$\lambda$ 는 평균적으로 발생할 횟수고,
$t$ 는 내가 보고자하는 시간 길이고, (시간,time)

그리고 $T_{\rm fr}$ 을 1로 정규화,normalization한다.
$T_{\rm fr} \to 1$
$2T_{\rm fr} \to 2$
그리고 여기선 람다 대신 G라고 쓸 것이다. $\lambda=G$ (frames/sec)

Q. 그렇다면 pure ALOHA에서 전송이 성공할 확률은?

A. 다른애들과 충돌하지 않아야.
$k=0$ 여야 할 것이다.
성공할 확률은 $P_{\rm succ}=e^{\lambda t}=e^{-2G}$
여기서 throughput { 초당 성공적으로 보내는 frames의 수 }를 정의할 수 있을건데, 이것은
$G$
를 보낼건데 실제로 성공할확률을 곱하면 throughput은
$S=G\cdot e^{-2G}$

///// slotted ALOHA /////
slotted_ALOHA

시간의 시작점과 끝점이 정해져 있다. 단말들끼리 동기화되어있다.
(collision duration이 그 한 slot을 차지한다)
이렇게 하면 성능이 pure ALOHA보다 두 배가 좋아진다.

이 때도 Poisson 분포를 보면
$P(N=k)=\frac{e^{-\lambda t}(\lambda t)^k}{k!}$
일 때 $k=0$ 이므로
$P_{\rm succ}=e^{-\lambda t}=e^{-G}$
가 성공할 확률.
(지수의 2대신 1)
$S=G\cdot e^{-G}$

1.11. 20221013

pure ALOHA
$S=Ge^{-2G}$
$\frac{dS}{dG}=e^{-2G}-2Ge^{-2G}=0$ 즉 극대값을 구하기 위해 미분이 0인 점을 찾으면
$G=1/2$
$S^{*}=\frac1{2e}$
// $S^*:\,S$ 의 최대값

slotted ALOHA
$\frac{dS}{dG}=(G-1)e^{-G}=0$
$G=1$
$S^*=\frac1e$


CSMA
Carrier Sense Multiple Access


ALOHA는 그냥 보내보지만, CSMA는 'carrier sensing'을 해서, 즉 ...
QQ 그래서 결국 목적은 collision을 줄이는?

// Figure 3.30 Vulnerable time in CSMA

여기선 vulnerable time = propagation time


CSMA/CD (유선)
CSMA/CA (무선)
token passing을 / physical topology에 따라 어떻게 하는지

3.3.3 channelization (= channel partition)
  • FDMA (frequency division multiple accesss)
  • TDMA (time division multiple accesss)
  • CDMA (code division multiple accesss)

1.12. 20221018

3.4.1 three types of addresses

L5 address - domain name
L3 address - IP_address
L2 address - MAC_address

L5 → L3 mapping은 DNS

L3 ↔ L2는 ARP(address resolution protocol)

Chap 4

이더넷,Ethernet
이더넷 프레임 Ethernet frame

Bytes
7 preamble 56 bits of alternating 1s and 0s L1 header
1 SFD start frame delimiter 10101011(2) L1 header
6 dest. addr. L2 header
6 src. addr. L2 header
2 type L2 header
46 to 1500 payload data and padding (L3)
4 FCS CRC L2 trailer

위에서 dest. addr. 에서 FCS까지의 frame length의 범위는
최소길이: 46+18 = 64
최대길이: 1500+18 = 1518

LAN에서
hub : half-duplex
switch : full-duplex

(hub와 switch를 엄격히 구분하지는 않는다)

1.13. 20221020


1.14. 20221027

무선랜 wireless LAN 이야기

BSS - Basic Service Set
Ad hoc BSS
Infrastructure BSS
ESS - Extended Service Set - 둘 이상의 BSS

Figure 4.9
IEEE 802.11의 datalink layer 중 MAC sublayer에는

위에 PCF - point coordination function - polling 방식
아래에 DCF - distributed coordination function - CSMA/CA 방식



1.15. 20221101

fragmentation

SDU - service data unit
PDU - protocol data unit

MSDU - MAC 계층으로 내려오는 SDU
MPDU - MAC 계층으로 내려온 PDU

A-MSDU - SDU들이 붙어있고 FCS가 하나
A-MPDU - SDU들이 떨어져 있고 FCS가 각각 여러개

Addressing Mechanisms

802.11 frame의 address field가 4개인 이유

802.11의 frame에는 management frame, control frame, data frame이 있고

control frame에는
RTS frame : 주소 필드가 둘
CTS, ACK frame : 주소가 하나

Bluetooth:
Piconet
Scatternet

1.16. 20221103


Chap4 (LAN) 끝

telephone - circuit_switching
Internet - packet_switching

DSL

유선전화망(PSTN)

무선전화망
MS : mobile station 단말
BS : base station 기지국

1.17. 20221108

frequency reuse

MSC (mobile switching center)

이동전화(MS)가 위치를 옮길 때 위치 DB에 location update 얘기

무선전화의 handoff(=handover) 개념

roaming

1.18. 20221110

Wireshark 실습

1.19. 20221115

위성통신

GEO(높음)
MEO
LEO(낮음)

GPS

Chap 6

Hub (L1)
Switch (L2)

(self-)learning switch : 내부에 Address → Port mapping table이 있다.

Switch 연결에 loop가 있을 때 발생하는 문제.
→ loop를 없애야 함. tree (spanning tree)를 찾아야 해결됨.

1.20. 20221117

spanning tree 찾는 algorithm.

L3 router

virtual LAN (VLAN)
frame tagging : MAC frame에 destination VLAN을 가리키는 tag를 추가

1.21. 20221122

spanning tree 추가 설명

Chap 7

network layer의 역할
packetizing
routing, forwarding

7-2 packet switching
datagram approach
virtual-circuit approach
packet에 flow label 포함
virtual circuit identifier, packet이 따라야 할 virtual path를 정의.

1.22. 20221129

IPv4

네트워크계층의
Addressing (7장)
Routing (8장)

IPv4 address
이건 prefix와 suffix가 있다. 각각 network id, host id.

그 크기는
Class A: 8 + 24
Class B: 16 + 16
Class C: 24 + 8

시작 binary:
Class A: 0
Class B: 10
Class C: 110
Class D: 1110
Class E: 1111

network를 쪼개는 것 : subnetworking

slash notation (CIDR)
슬래시 뒤 숫자가 prefix length
즉 network id의 길이.

IPv4 주소 쪼개기, subnet mask 등.

1.23. 20221201

IPv4 주소. address aggregation.

IP datagram (header + payload)

IP header
이것의 HLEN은 4를 곱해야 하는 수.
이것의 fragmentation에서
offset field는 8을 곱해야 하는 수.
M bit
1 : 더 있다
0 : 이제 끝이다
Options

IPSec

ICMPv4

1.24. 추가 동영상

ping, traceroute

Mobile IP
Home address (HoA) : session 유지용, permanent
Care-of address (CoA) : 데이터 송수신 용

여기에 Home Agent (HA)라는 기기를 쓰는.

여기에 tunneling 언급.

triangle routing

1.25. 20221206

IP packet forwarding

forwarding table

address aggregation

longest mask addressing
: longest prefix matching (LPM)

label switching - switching table을 사용.
  • ATM
  • MPLS
lookup time을 줄일 수 있다.
이것은 virtual circuit 방식이라 한다.

IPv6 addressing
IPv4가 net id, host id로 둘로 쪼개지듯이, 이건 3개로 쪼개진다.
  • global routing prefix
  • subnet identifier
  • interface identifier

autoconfiguration of hosts (IPv4에서는 DHCP를 썼어야만 했던 그거)

IPv6 datagram

1.26. 20221208

Chap 8

unicast routing

least-cost routing - 최단거리,shortest_path
least-cost tree

8-2 routing algorithms

distance-vector (DV) routing

Bellman-Ford equation

two-node instability : count-to-infinity problem

Dijkstra

1.27. 20221215

인터넷의 큰 구조

AS (autonomous system)
inter-AS routing
intra-AS routing

multicast routing
RPF - reverse path forwarding
RPB - reverse path broadcasting
RPM - reverse path multicasting

PIM - protocol independent multicast
PIM-SM (sparse mode) → shared multicast tree - RP(rendez-vous point)를 기준으로 공유되는 tree를 만든다.
PIM-DM (dense mode) → source-based tree - 각 source에 최적화된 tree.

2. 데구알




...




정렬,sort
stable_sort
unstable_sort
internal_sort ?
external_sort



parameter = formal parameter - 함수선언 () 속의
argument = actual parameter - 함수호출 () 속의

value parameter - copy of its argument
reference parameter - address of its argument