Lecture 3b-1 ~ 3b-8: Link Layer, Part B

3b-1 Overview of the Link Layer

 

Where we are in the Course

 

Topics

 

 

 

 

3b-2 Retransmissions

 

Topic

 

 

Context on Reliability

- Reliability function은 어느 계층에서 도맡아야 하는가??

 

- 물리 계층과 같이 낮은 계층에서는 에러를 방지함으로써 reliability에 기여한다

- 높은 계층에서는 에러를 수정함으로써 reliability에 기여한다

 

 

 

ARQ

- ARQ는 에러가 자주 발생하는 WIFI나 TCP에서 주로 사용된다

- 수신측에서는 올바른 frame을 받았을 때 ACK 신호를 전송하게 되고, 송신측은 ACK를 받지 못하면 해당 신호를 재전송한다

 

- Timeout 이전에 수신측이 Frame을 전송받고 ACK 신호를 송신측이 받게되어 재전송이 일어나지 않는다

 

- Timeout 발생 시 송신측은 다시 Frame을 전송한다

- 위의 경우와 다르게 오류를 감지한 경우도 ACK 신호를 전송하지 않으면 재전송 받을 수 있다

 

 

So What's Tricky About ARQ?

- timeout을 어느 기준으로 선정할 것인가?

- 오류가 발생한 부분부터 재송신하므로 중복전송의 단점이 있다

 

 

Timeouts

- LAN, wifi 등에서는 적당한 시간대로 timeout을 설정할 수 있다

- Internet 상에서는 timeout을 적절히 설정하기 어렵다

 

 

Duplicates

- 송신측은 timeout으로 인해 frame을 재전송했는데 수신측에서는 이 frame이 새로운 것인지, 재전송으로 인한것인지 알 수 없다

 

- 짧은 timeout으로 인해서도 중복 전달이 일어날 수 있다

 

 

Sequence Numbers

위의 문제들을 해결하기 위한 방안

 

Stop-and-Wait

- 송신측에서 한개의 블록을 전송한 후 수신측으로부터 응답을 기다리는 방식

- 구현방법이 간단하나 블록을 전송할 때마다 응답을 기다리므로 전송 효율이 낮다

일반적인 경우

ACK loss 인 경우

early timeout 인 경우

 

 

Limitation of Stop-and-Wait

- 송신측이 ACK 혹은 NAK를 받을 때까지 다음 프레임을 받을 수 없으므로 전송효율이 떨어진다

- 아래 예시에서 RTT = 100ms 이므로 초당 전송 프레임 수는 10개이며, 한 프레임이 10,000 bit라고 가정하면 100kbps 밖에 전송하지 못한다

- 이는 R이 10Mbps로 높아진다 하더라도 증가하지 않는다

 

 

Sliding Window

- 위의 한계를 해결하는 방식

 

 

 

 

3b-3 Multiplexing

 

Topic

 

Time Division Multiplexing (TDM)

- 하나의 전송로 대역폭을 시간 슬롯으로 나누어 채널에 할당함으로써 몇 개의 채널들이 한 전송로의 시간을 분할하여 사용한다

 

Frequency Division Multiplexing (FDM)

- 전송되어야 하는 신호들의 대역폭을 합한 것보다 링크의 대역폭이 클 때 적용할 수 있는 아날로그 기술로, 한 전송로의 대역폭을 여러개의 작은 패널로 분할하여 여러 단말기가 동시에 이용하는 방식

 

TDM versus FDM

 

 

TDM / FDM Usage

 

 

Multiplexing Network Traffic

- bursty : 간헐적인

- 사용자마다 네트워크를 사용하는 정도가 시간마다 다르므로 색칠한 영역은 낭비된다

- 유저들간에 사용하는 네트워크를 공유하면 각자 필요한 대역폭보다 적은 대역폭으로도 대응이 가능하다

 

Multiple Access

- multiple access protocol의 대표적인 두가지 방식

         - 랜덤하게 네트워크에 접근 권한을 가짐

         - (Contention-free) 경쟁 회피 정책

 

 

 

 

 

3b-4 Random Multiple Access

 

Topic

- 하나의 링크를 어떻게 노드간에 공유할 것인가?

        - 앞서 배운 TDM, FDM 방식은 network의 bursty함을 해결하지 못한다

- 관리자가 없는 분산 시스템을 생각해야 한다

- MAC protocol은 bursty network의 문제를 해결하며, classic Ethernet의 기초가 된다

 

 

ALOHA Network

- TDM, FDM이 아닌 새로운 protocol이 사용되었다

 

- 노드는 항상 보내려고 노력한다

- 충돌이 있으면 랜덤한 시간동안 기다렸다가 다시 송신한다

 

- 음영이 존재하는 부분은 충돌이 발생되었으므로 전송되지 못한다

 

- 탈중앙화가 되었고 low load 하에서는 잘 작동하는 나쁘지는 않은 방식이다

       - 대부분의 네트워크는 low load한 상황이다

- high load에서는 효율적이지 못하다

       - 대략 4 / 5 의 패킷이 제대로 전송되지 못한다

       - 시분할 된 슬롯을 사용하면 효율이 높아지기는 하는데 더 좋은 방안이 있을 듯 하다

 

 

Classic Ethernet

- 다수의 컴퓨터가 하나의 wire에 연결된 환경

 

 

CSMA (Carrier Sense Multiple Access)

- 패킷을 전송하기 전에 바쁜지 한번 확인하는 방식

 

- 충돌을 완벽하게 제거하지는 못하는 방식이다

- 하단의 예시에서 양 끝단이 중간 매개체가 바쁘지 않은지 확인 이후 패킷을 전송했지만 전파 delay에 의해 충돌이 발생하게 된다

 

- CSMA는 대역폭이 작을 때만 (less than 1 packet) 충돌을 방지할 수 있는 방식이다

 

 

CSMA / CD (with Collision Detection)

- 전송하기 전에 확인하는 것 뿐만 아니라 동시에 전송한다는 것을 알아차리면 전송을 중단하는 방식이다

 

 

CSMA / CD Complications

- 한쪽에서 보낸 패킷이 거의 도착할 때쯤 다른쪽에서 패킷을 송신하는 경우 발생하는 충돌로 인해 2배의 전파 시간이 소요된다

 

- 데이터가 충돌했음을 어떻게 알 수 있는가?

      - 전송 과정에서 충돌 신호가 나타나면 알 수 있다

      - 이를 알기 위해서는 계속해서 전송하는 것이 필요하며, 그래야만 충돌/ 손상된 데이터가 자신의 데이터임을 확신할 수 있다

      - 만약 패킷이 충분히 크다면 충돌 신호가 송신 측으로 올때까지 스테이션은 여전히 데이터의 왼쪽 부분을 전송하고 있음을 의미하며, 그러면 충돌로 인해 자체 데이터가 손실되었음을 인식할 수 있다

 

 

 

CSMA "Persistence"

- 반대 입장에서 다른 노드가 패킷을 전달하고 있음은 어떻게 알 수 있는가?

       - 마냥 기다린다?

 

- 다른 신호가 끝나자마자 패킷을 전송하려는 스테이션이 여러대라면?

 

- 송신을 기다리는 스테이션이 n 개일 때, 1/n 확률로 전송하는건 어떤가?

     - 분산 시스템에서 n이 몇인지 어떻게 알 수 있는가?

 

 

Binary Exponential Backoff (BEB)

- 매번 충돌이 발생할 수록 지수 배로 대기 시간을 늘려나가는 방식

- 실제로 매우 효율적으로 작동하는 방식이다

 

 

 

Classic Ethernet, or IEEE 802.3

- 위의 문제들을 모두 해결하여 탄생한 것이 classic ethernet이다

        - 1-persistent : 현재 링크에 액세스하고 있는 데이터의 전송이 끝나면 바로 액세스를 시도하는 방식

        - CS (Carrier Sensing) : 데이터를 보내기 전에 스테이션이 먼저 캐리어를 감지

        - MA (Multiple Access) : 채널이 있는 경우 액세스를 시도하는 스테이션이 많음

        - CD (Collide Detection) : 충돌 감지, 패킷 데이터 충돌 시 해결

        - BEB : 다수의 스테이션이 동시에 액세스를 요청할 때 이를 해결하기 위한 효율적인 방식

 

 

Ethernet Frame Format

- 다중 액세스가 가능한 링크에 연결되어 있으므로 address가 존재

      - Destination address가 앞쪽에 존재한다

- Preamble : 네트워크 통신에서 두 개 이상의 시스템간에 전송 타이밍을 동기화하기 위해 사용되는 신호

      - "누군가가 지금 막 데이터를 전송하려 한다" 는 의미로서 통신 시스템들이 이해할 수 있는 일련의 특정 송신 펄스를 정의

- Check-sum : CRC-32 등을 사용해 에러를 감지

      - Ethernet은 wire를 통한 통신 방법으로 에러가 잘 발생하지 않으므로 ACK나 retransmission이 없다

      - CRC-32를 통해서 높은 계층에서 에러 수정도 가능할 것이다

 

 

Modern Ethernet

- 현재 사용되는 이더넷은 multiple access 방식을 사용하지 않으며, 스위치를 사용한다

 

 

 

CSMA/CD 참고

CSMA / CD (충돌 감지 기능이있는 CSMA) 란? - 다른

 

 

 

 

 

3b-5 Wireless Multiple Access

 

Topic

- wireless 환경에서 언제 어떻게 신호를 보내야 할까?

 

 

 

Wireless Complications

- 무선통신은 유선통신보다 매우 복잡하므로 기존의 기술을 사용하지 못한다

       - 노드는 다른 커버리지 영역을 가진다

               - 유선에 연결된 모든 스테이션이 데이터의 전송을 감지할 수 있는 상황과 다르다 (Carrier Sense가 작동하지 않을 것이다)

       - 신호마다 신호 강도가 다르기 때문에 감지를 못할수도 있다

 

 

Different Coverage Areas

- C는 A가 신호를 보내고 있음을 알 수가 없다

- B는 A, B가 보내는 신호를 모두 감지할 수 있다

 

 

Hidden Terminals

- A, C는 서로 hidden terminal이라 B로 동시에 패킷을 전송할 수 있으며, 그렇게 되면 B에서 충돌이 발생한다

 

 

Exposed Terminals

- B, C가 서로 exposed terminal인데 B는 A로만 보내고 C는 D로만 보내기 때문에 서로 간섭이 되지 않는 경우에는 충돌이 발생해도 상관이 없다

 

 

Nodes Can't Hear While Sending

-  유선 통신과는 달리 무선 통신은 신호 강도가 약하거나 hidden terminal일 수 있기 때문에 충돌 감지가 효과가 없다

 

 

Possible Solution: MACA

- short handshake 사용

- 송신 측은 보낼 프레임 길이와 함께 RTS를 보냄

- 수신 측은 받을 프레임 길이와 함께 CTS를 보냄

- 송신 측은 프레임을 전송하며, CTS를 들은 나머지 노드는 조용히 기다린다

 

 

MACA - Hidden Terminals

1

2

3

4

- hidden terminal 간의 충돌을 방지하는 방식

 

 

MACA - Exposed Terminals

1

2

3

4

- exposed terminal 간의 전송 방식

- 실제 프레임 전송에는 아무런 간섭이 존재하지 않는다

 

 

802.11, or WiFi

- 무선 통신에서의 Ethernet

- 대부분 유선으로 연결된 AP로 연결한다

- 하나의 AP로 부터 여러대의 노트북이 연결되는 multi-access problem이 존재한다

- 다양한 WiFi가 발전되어 왔다 (802.11b/g/n/a...)

 

 

802.11 Physical Layer

- 802.11b 버전은 레거시라 OFDM 변조를 사용하지 않는다

 

 

802.11 Link Layer

- Multiple access를 위해 CSMA/CA를 사용하고 RTS/CTS를 선택적으로 사용한다

         - 특정 wifi에서는 굳이 RTS/CTS를 사용할 필요가 없는 경우가 있다

- ACK과 ARQ를 사용해 retransmit 된다

         - 유선에서는 CRC-32를 통해 에러를 감지하고 해당 신호를 버렸지만, 무선에서는 이렇게하면 상당량의 패킷이 버려질 것이다

- AP 때문에 몹시 구린 (funky) 주소값을 3개나 가져야한다

- CRC-32를 통해 에러를 감지하며 기타 많은 특징을 가지고 있다

 

 

802.11 CSMA/CA for Multiple Access

- 802.11에서는 충돌을 방지하기 위해 RTS/CTS를 사용하는 대신 랜덤한 gap을 추가한다

- 위의 예시에서는 C가 B보다 작은 gap을 추가했기 때문에 C가 먼저 프레임을 전송한다

 

 

The Future of 802.11 (Guess)

그냥 추론일 뿐

 

 

Collision Aviodance 참고

Collision Avoidance in wireless networks - GeeksforGeeks

OFDM 참고

[디지털통신] OFDM: (1) OFDM 기초

CSMA, CSMA/CD, CSMA/CA 참고

CSMA, CSMA/CD, CSMA/CA 란?

 

 

 

 

 

3b-6 Contention-Free Multiple Access

 

Topic

- 랜덤으로 순서가 정해지는 것이 아니라 AP에 순서를 가지고 접근

 

 

 

Issues with Random Multiple Access

- 앞서 살펴본 CSMA가 low load에서는 잘 작동하지만 high load에서는 효율적이지 못하다

 

 

Turn-Taking Multiple Access Protocols

- 노드간에 순서를 갖게 된다

 

 

Token Ring

- Token이 노드간에 회전하며 해당 토큰을 가지고 있는 노드가 프레임을 전달할 권리를 갖게 된다

 

 

Turn-Taking Advantages

- 충돌이 없으므로 오버헤드가 사라졌으며 결과적으로 high load에서도 효율적이다

- 모든 노드에 공평한 기회를 갖게 해준다

 

 

Turn-Taking Disadvantages

- 복잡하다

        - 토큰이 사라지면 복구해야한다

        - low load에서는 높은 오버헤드를 갖게 된다

 

 

 

 

 

3b-7 LAN Switches

 

Topic

- 지금까지 multiple access scheme에 대해서 자세히 알아보았으며, 대표적으로는 802.11이 있었다

- 다만 유선 통신에서는 모든 host를 switch device에 연결하는 것을 사용한다

- 상단의 구조가 modern Ethernet의 기초가 된다

 

 

Switched Ethernet

- 대부분의 host에 연결된 switch를 통해 프레임이 전달된다

 

 

What's in the box?

- Hub or Repeater : bit 전송

- Switch : 다른 포트로의 frame 전송

- Router : 다른 IP로의 packet 전송

 

 

Inside a Hub

- 물리 계층 디바이스

- 하나의 포트에서 허브로 신호가 전달되면 나머지 모든 포트로 해당 신호가 전달된다

- 한 디바이스가 고장났다고 해도 허브를 쓰면 다른 디바이스로의 전송에는 문제가 없다 (reliable)

 

 

Inside a Switch

- 링크 계층 디바이스

- 전송해야 하는 포트로만 프레임을 전송해야 한다

- 각 포트간의 연결 통로는 다르며, 스위치에서의 fabric은 grid 구조를 이루고 있다

 

- 포트로 연결된 wire가 하나로 보이지만 full-duplex이므로 실제로는 2개의 wire가 존재한다

- multiple access protocol이 없으며 host는 switch로 데이터를 그냥 전송할 뿐이고 switch가 알아서 전달한다

         - hub에서는 하나의 호스트가 데이터를 허브로 전송하면 다른 모든 호스트로 이 정보가 전달되므로 병렬 처리가 불가능했다

         - switch에서는 서로 관련 없는 호스트 간의 통신은 병렬으로 가능하다

 

- 두개의 input이 하나의 output으로 전달되어야 하는 경우가 동시에 발생한다면?

- input과 output 모두에 버퍼가 필요하다

 

- 여러개의 input이 하나의 output으로 전달되어야 하는 경우가 동시에 발생하면 버퍼의 overflow 발생할텐데?

       - contentional congestion 문제

       - TCP/IP에서 다시 다룰 예정

 

 

Advantages of Switches

- 물론 스위치가 고장나면 모든 호스트간의 통신이 불가능해지겠지만 단순히 스위치를 교체함으로써 훨씬 쉽게 문제를 해결할 수 있다

- 포트간의 데이터 전송에서 병렬처리가 가능해서 scalable 하다

 

 

Switch Forwarding

- 스위치는 어떻게 Ethernet Frame을 가지고 올바른 다른 포트로 이를 전송해줄 수 있는가?

        - Ethernet Frame은 Ethernet address만 가지고 있으며 스위치의 포트를 가지고 있지는 않다

- 포트에 대한 모든 테이블을 가지고 있는 것은 메모리를 낭비하는 해결책일 듯 하다..

- host를 찾아 떠나다니는 알고리즘을 생각해볼 수도 있겠다..

 

 

Backward Learning

- 스위치는 주소값과 포트를 잇는 테이블이 필요하다

- 입력 부의 주소 값을 먼저 찾아본다

- 알고 있다면 해당 포트로 보내고 모른다면 모든 포트로 브로드캐스팅한다

 

- 스위치의 테이블에 아무 정보가 없으므로 브로드캐스팅한다

- 이후 A의 포트가 1이라는 것을 업데이트한다

 

- A에 대한 포트 정보는 알고 있으므로 바로 보낸다

- 이후 D의 포트가 4라는 것을 업데이트한다

 

 

- 브로드캐스팅이 필요 없다

 

 

Learning with Multiple Switches

loop가 없어야 한다

- A에서 D로 전송

- B1에 D에 대한 정보가 없으니 브로드 캐스팅

- B1의 1번 포트에 A 정보 저장

- B2에 D에 대한 정보가 없으니 브로드 캐스팅 (허브까지 전파)

- B2의 4번 포트에 A 정보 저장

- D에서 A로 전송

- B2에 A에 대한 정보가 있으니 바로 4번 포트로 전송

- B2의 1번 포트에 D 정보 저장

- B1에 A에 대한 정보가 있으니 바로 1번 포트로 전송

- B1의 4번 포트에 D 정보 저장

 

 

 

 

 

3b-8 Switch Spanning Tree

 

Topic

- 실제 네트워크에서는 루프가 존재하지 않을 수 없다!

 

 

Problem - Forwarding Loops

- failure을 대비해 여분의 연결을 해둔 상태에서는 loop가 생긴다

- 실수를 했을 때에도 loop가 생긴다

 

 

- A에서 F로 보내는 과정에서 C에서 D로 보내는 신호가 2곳이기 때문에 D에서 C로 다시 각기 다른 포트로 신호를 전송하게 되면서 순환이 발생한다.

 

 

Spanning Tree Solution

- spanning tree를 사용하면 해결된다

- 트리이므로 loop가 있을 수 없다

 

- 기존 토폴로지에서 기준 노드를 잡고 각 노드에 한번씩 방문하는 선을 그리면 spanning tree를 만들 수 있다.

 

 

Spanning Tree Algorithm

 

- 1번 2번 과정은 병렬로 처리 가능하다

1. 루트 노드를 선정하고 가장 작은 주소 값과 바꾼다

2. 루트로부터 가장 가까운 거리부터 트리를 확장시켜 나간다

3. spanning tree에 없으면 네트워크에서 특정 포트를 차단 상태로 바꾼다

 

 

 

Spanning Tree Example

 

- D가 F로 처음 보낼 때는 브로드 캐스팅이 일어난다

- F가 D로 응답을 보낼 때는 브로드 캐스팅없이 전송 가능하다

- 물론 D, F 간에 distance 1을 가진 간선이 존재하지만 스패닝 트리 알고리즘을 쓰므로 해당 간선을 사용할 수 없다

 

 

참고

스패닝 트리 프로토콜(STP, Spanning Tree Protocol)

 

Spanning Tree Protocol(스패닝 트리 프로토콜) 예제