Computer_Network_Link_Layer

Link Layer

단위 : frame

- 노드들이 서로 인접해 있어야함

- 각 링크 프로토콜은 다른 서비스들을 제공

 

framing

datagram -> frame으로 캡슐화됨 (헤더랑 트레일러 붙여서)

- 맥주소 : source, destination 구별함 (ip 주소와 다름)

 

services

- flow control

- error detection

- error correction

- half-duplex and full-duplex (half-duplex ex. 무전기)

- 링크 레이어는 NIC나 Ethernet, wifi card chip 등에 구현되어있음

 

communicate

sender : datagram을 frame으로 캡슐화 (+error checking이나 flowcontrol 붙여서)

receiver : error나 flow control 확인, datagram으로 추출 후 윗 계층에 보냄

 

Error detection

data + EDC(error detect bits)

1. single bit parity : 1의 갯수를 세서 홀수면 1, 짝수면 0

2. two-dimensional bit parity : 2차원 좌표 형식으로 detect + correct(위치 파악)까지 가능. 하지만, 에러가 2개 이상이면 불가능

 

CRC(Cyclic Redundancy Check)

D : data bits

G : 공개키 (길이가 r+1임)

R : CRC bits (r bits)

<D, R> = D * 2^r XOR R

이때 D*2^r은 D를 r만큼 시프트시킨거임

결국 <D,R>은 D를 r만큼 왼쪽으로 미뤄넣고 0으로 된 공간에 R을 넣어서 D + R을 만든거임 ㅇ

<D,R>이랑 G랑 나뉘었을때 나머지가 0인 R을 찾자!

-> r+1 미만의 비트 오류를 검증할 수 있음

 

D*2^r XOR R = nG

D*2^r = nG XOR R

R = D*2^r / G 의 나머지

 

Multiple access protocols

두 타입의 링크

1. point- to-point

2. broadcast (shared wire or medium)

 

- 공유가능한 broadcast channel이 하나 있음

- 만약 두개이상의 노드에서 동시에 접근할려 하면 충돌이날거임

- 즉, multiple access protocols에서는 어떻게 공유된 채널 하나를 공유할것인지 분산된 알고리즘을 짜야하고

- 어떻게 공유할건지 노드끼리 통신해야하는데 통신할땐 이 공유된 채널을 이용해서만 통신해야함

 

ideal

- 하나올땐 Rbps 쓰고 M개오면 R/Mbps 쓰면될듯?

 

MAC Protocols 분

방법 1. channel partitioning

- channel을 작은 조각으로 잘라 할당함

방법 2. random access

- channel은 분할되지 않고 충돌도 허용함

- 대신 충돌에 대해 회복할줄 알아야함

방법3. taking turns

- 걍 돌아가며 전송 하지만 오래걸림

 

Channel Partitioning

TDMA : time division multiple access

- 고정길이의 슬롯을 할당받음

- 사용되지 않는 슬롯들은 낭비됨

- 주로 음성통화 등에 사용

 

FDMA : frequenncy division multiple access

- frequency를 나눔

- 만약 보낼게 없으면 frequency bands가 낭비된다

 

Random access Protocols

- 노드간 미리 조종하는 기능없음

- 충돌이 일어날거임

- 어떻게 충돌을 감지하고 회복하냐가 관건

- ex. ALOHA, Slotted ALOHA , CSMA, CSMA/CD(유선) , CSMA/CA(무선)

 

Slotted ALOHA

- 모든 프레임은 같은 사이즈이고, time도 일정한 크기의 슬롯으로 나뉘어짐

- 슬롯이 시작할때만 노드들은 전송하기 시작함

- 노드들은 동기화되어있음 (동시에 보내는거 ㄱㄴ 대신 충돌 일어날거)

- 충돌 x : 프레임 전송 가능하고 노드는 다음 슬롯에도 프레임을 보낼 수 있음

- 충돌 O : 노드는 프레임을 다음슬롯에 재전송할건데 p의 확률(random화)로 보낼거임

- 장점 : 하나만 보내면 full bandwith 사용가능, 슬롯에 있는 노드의 슬롯만 동기화하면 됨

- 단점 : 슬롯이 버려지고 게으름, clock 동기화해야하는데 개어려움(모든 노드가 시간맞춰야함)

- 효율 : 0.37

 

Pure ALOHA

- slot구분 안함, 만약 프레임이 처음 오면 걍 보내버림

- 동기화하지 않았기에 충돌할 가능성이 올라감

- 만약 두 슬롯동아 나를 제외한 다른패킷이 오지 않으면 전송

- 효율성 0.18

 

CSMA

- 먼저 어떤 노드가 작업중인지 파악

- 아무도 없거나 여유 있으면 전송, 바쁘면 전송 늦추기

- 하지만 propaation delay때문에 여전히 출동발생

- 충돌나면 전체 전송시간 낭비됨

 

CSMA/CD

- CSMA + 충돌 감지

- 충돌 감지되면 전송 중단됨 (채널 버려지는거 감소)

- 충돌감지 유선에선 쉬운데 무선엔선 어려움

- 만약 충돌이 m번 일어난 후면은 NIC는 {0, 1,2,.... 2^m-1}에서 K를 찾고 랜덤넘버 부여해주고 순서대로 보내줌 (K*512bit time을 기다림)

- 즉 충돌이 많이 일어날수록 늦게 간다는거임 

- Tprop가 0으로가면 효율성 1

- Ttrans가 무한대로가면 효율성 1 (Ttrans가 무한대로가면 안좋은거임)

- 그래도 ALOHA보단 좋음

 

low load : random access는 효율적, channel partitioning은 비효율적

high load : random access는 비효율적, channel partitioning은 효율적

 

Taking turns

polling

- controller노드가 다른 노드들을 보낼 순서대로 초대함

- overhead일어나고 나머지 다 보내고 그다음에 보내야함

- 만약 controller 죽으면 아무것도 못함

 

token passing

- token을 하나의 노드에서 다음 노드로 전달

- token을 가지고 있는 노드가 전송 가

- 얘도 overhead일어나고 좀 기다려야함

- token이 사라질수도 있음

 

MAC address

- 얘는 같은 네트워크 즉  같은 LAN 인터페이에서 사용하는 주소임

- 48비트로 16진수 2자리씩 끊어서 표현 1A-2F-BB-76-09-AD

- MAC 주소는 ip처럼 막 변하지 않고 고유함

- MAC 주소는 ip처럼 subnet, host처럼 안나뉨 => 계층구조가 없음- 그렇기에 MAC주소는 이식성이 뛰어남(저리갔다 이리갔다 ㄱㄴ)

 

ARP : address resolution protocol

ARP table: IP, MAC주소를 매핑한 테이블 + TTL까지 (TTL이후 매핑 잊어버림)<IP address; MAC address; TTL>

 

ARP Protocol 작동 방식 ex. A 에서 B로 데이터그램 전달 (B의 맥주소를 알아내야함)1. MAC dest주소를 FF-FF-FF-FF-FF-FF로 지정하고 보냄2. IP dest가 해당되면 자신의 MAC dest주소 포함시켜서 A한테 보냄3. A는 B의 응답 받은다음 B의 MAC주소를 테이블에 저장

 

이번엔 다른 서브넷으로 보내기

ex. A에서 B로 보냄 (A는 B의 ip주소와 first hop router인 R router의 Ip와 MAc주소를 알고있음)

 

1. 먼저 R의 맥주소를 dest로 해서 보냄 (이때 ip dest는 당연 B로 설정)2. R에 도착하면 프레임에서 데이터그램으로 받음3. R은 도착 인터페이스를 결정하고(ARP table 활용) B의 MAC주소를 dest로하여 데이터그램에서 link layer frame으로 캡슐화하여 만들어냄4. B는 프레임 받아서 datagram추출해서 ip layer로 전달

 

Ethernet

- 쉽고 싸고 젤 많이쓰이는 LAN 기술

 

bus : 옛날에 쓰이더 구식 기술 하나로만 연결되어서 충돌 자주 발생

switched : 요즘 많이쓰이는거 => 중앙에 스위치 있고 보내는거 받는거 링크 따로따로있어서 충돌확률 낮음

 

Ethernet frame 구조

- preamble : 클럭속도 동기화를 위해 사용, 끝에 10101011 이렇게 11 바이트와서 preamble이 끝남을 의미함

- address : 48바이트 MAC주소로 되어있음. 만약 받은 이더넷프레임의 dest주소가 자신과 같다면 network layer로 데이터를 올려보냄

- type : 더 높은 레이어 프로토콜을 나타냄

- CRC : error detect

 

- connectionless : handshakng 없음

- unreliable : Ack나 Nak를 보내지 않음 (위쪽 계층이 처리할거임)

- Ethernet의 MAC Protocol : unslotted CSMA/CD with binary backoff

binary backoff : CSMA/CD에서도 사용하던 기술인데 랜덤넘버 2^m-1인가 까지 받은다음에 순서대로 보내는거

-많은 Ethernet standards들이 있음

하지만 MAC PRotocol과 frame format은 동일함

standards의 종류에 따라 스피드가 달라짐

 

Ethernet switch

- link-layer device임

- 다른 호스트들은 스위치의 존재를 모름(투명성)

- 호스트들은 직접 연결 되어있으며 각 링크가 있음

- 여러군데 동시에 보낼 수있음

- 하지만 같은 dest에 두개 이상 동시에 전송은 못함

 

Switch Table

- 각 스위치는 어떤 인터페이스를 걸쳐 어떤 호스트로 갈 수 있을지의 경로를 저장하고 있는 스위치 테이블을 가지고 있음

- 프레임을 받을때 스위치는 self-learning을 함(경로 저장)

- 만약 스위치 테이블에 없는 dest이면은 모든 인터페이스로 보내고 들어오는 인터페이스 경로 저장

- self lerarning swith들끼리는 서로 연결될 수 있음

 

Switch vs Router

- 둘다 Store and forward방식

- 둘다 forwarding table 갖고 있음

 

-routers : network- layer, 라우팅 알고리즘을 이용해서 테이블 작성, ip 주소

-switchs : link-layer, flooding을 사용해서 테이블 작성, mac 주소

 

VLAN

만약 기본 LAN에서 사이즈를 업시킨다면? broadcast하는데만 시간 한참 소요 될거임

그래서 하나의 LAN을 여러개로 나뉘어서 다중의 LAN들을 사용할 수 있도록 함(VLAN)

 

Port-based VLAN

- port에 따라 그룹화

- 굳이 port말고 MAC 주소 기반도 가능하다.

- 자신의 포트들끼리만 프레임을 전송할 수 있는데 1~8번 포트는 1~8번포트끼리만 broadcast 메시지를 받는다.

- 빨강과 파랑연결할려고 굳이 라우터를 안사도 되는 제품들이 많다.

trunk port : 다른 LAN 상에 VLAN이랑 연결 위해 사용

- 얘도 다만 위에처럼 빨강은 빨강끼리 파랑은 파랑끼리 전파가능하다.

VLAN 적용한 802.1Q frame 구조

MPLS : Multiprotocol label switching

- longest prefix 대신 고정된 길이의 label 을 통고속 ip forwarding을 진행한다.

- forward되는 패킷을 오직 label값만 보고 나갈 interface를 결정한다. (IP 주소 고려 X)

- 원래 longest prefix에선 dest ip만 보고 같으면 그 경로로만 갔지만 MPLS는 dest + source address 로 같은 dest address여도 다른 루트가 가능하다.(flexibility) 

 

- label을 여러개 써서 경로 즉 링크가 실패했을때 fast reroute가 가능함

- MPLS forwarding table에 어떻게 됐을때 어떻게 할지 다 적혀있음

- 원래라면 OSPF 나 link-state 같은거 써야하지만 이들을 좀 수정해서 그냥 MPLS를 어떻게 쓸지로 바꿈

- R1이 테이블을 작성했으면 각 MPLS 사용하는 라우터들에게 또 R1의 테이블 정보를 알려주고 받은 얘들은 그걸 적음

- 자신만의 unique 한 번호 label로 사용 

Datacenter Networks

-여러개의 호스트가 모인것

- 기본적으로 트리 구조

요청을 받으면 Load Balancer가 가장 널널한 host에게 요청을 날림 그럼 그 host는 다른 host의 정보도 참조해서 일을 처리함 

- 여러개 링크 연결해서 reliability와 throughput 높임

 

Web Request

예시 : 사용자가 학교 네트워크에 접속해 www.google.com에 접속하려 함

 

1. 먼저 랩탑에 연결하기 위해서 자신의 ip주소와 dns 서의 주소를 받아와야함

2. DHCP에 보낼 메시지를 캡슐화해서 FFFFFFFFFFFF 를 dest로 해서 broadcast함

3. DHCP는 요청을 받아서 demux 한다음(UDP 위에 DHCP)에 DHCP ACK를 보냄 이때, 사용자의 ip 주소, first-hop router의 ip 주소, dns 서버의 ip주소를 포함해서 보냄

4. 클라이언트는 DHCP에서 온 메세지를 받고 reply함 ( 2 way handshaking )

5. 그다음 이제 www.google.com에 http  request를 보내야 하는데  그 전에 도메인의 ip 주소를 얻어야함 (DNS 서버에 접속해야함)

6. 그래서 일단 router의 MAC주소를 알기 위해 ARP query를 먼저 생성한다음에 ARP query를 broadcast함

7. ARP 서버에서 쿼리를 받고 router의 mac주소를 포함시켜서 reply함

8. 그럼 클라이언트는 first hop roouter의 mac주소를 알게 됐고 dns 서버에 접속할 수 있게됨

9. IP datagram을 DNS query에 포함시킨다음 전송하는데 학교 네트워크를 걸쳐 DNS 서버로 감 (이떄 ,BGP, OSPF등을 사용해 routing table이 제작됨 , 사실 이전부터 제작되긴했음)

10. 그다음 DNS서버에서 해당 도메인의 ip 주소를 reply함

11. 그다음 TCP소켓을 열어 3hand shakin을 통해 TCP연결이 성립됨

12. 그다음 TCP 소켓으로 http request를 보내고 http response를 받음