[데이터 통신과 네트워킹] Media Access Control (MAC)

개요

media 종류

1) Bus 형

2) Star 형 (중앙 집중)

• Media를 사용할떄는 여러 사람이 사용한다.

→ 어떻게 사용할까?

• Random Access
• Controlled Access
• Channelization

Multiple Access

• Node와 Stations은 broadcast link를 사용한다.
• 공유 link에 대한 접근을 조정하려면, multiple access protocol이 필요하다.

Random Access

Random Access(or Contention)

• 어떤 station도 우선권이 없다.
• 어떤 station도 다른 station을 control하지 않는다.
• station은 데이터를 보낼지 말지 결정한다.
  • 이 결정은 medium 의 상태에 의존한다. (idle or busy)
  • medium을 미리 조사해야 한다.

ALOHA

• 1970년 초에 하와이 대학에서 개발되었다.
• 초기 random access 방법이다.
• ALOHA는 무선 LAN을 위해 설계되었다.
  • medium은 station들 간에 공유되었다.
  • 채널 하나 만을 사용했다.
• 전송 성공 여부 확인을 위해 ACK를 사용

Pure ALOHA

• 각 station은 전송할 frame이 있을때 frame을 보낸다. (multiple access)
  • 여러 군데에서 동시에 일어날 수 있다.
  • frame을 받았을때 잘 받았으면, ack로 응답을한다.
  • timer가 존재하고 time out 이후에 ack가 도착하지 않으면 frame을 다시 보낸다.
• collide(충돌)가 일어날 수 있다.
  • 단 하나의 공유 채널에 여러 스테이션이 경쟁하고 있기 때문에

Pure ALOHA Network에서의 frame

• 공유할 채널이 하나 밖에 없기 때문에, 충돌이 발생할 수 있다.

Pure ALOHA Protocol 절차

• K : 시도 횟수
• Tp : 전송하는데 걸리는 시간
• Tfr : frame 하나를 보내는 시간, 첫 비트부터 마지막 비트까지 보내는데 걸리는 시간
• Tb : (Back-off time), 기다리는 시간, R x Tp or R x Tfr
• R : (Random number), random하게 선택, 0 to 2^K - 1

Slotted ALOHA

• 충돌이 조금 줄어들 수 있음
• 시간을 Tfr 초에 slot으로 나눈다.
• station은 slot의 시작에만 보낼 수 있음
• 만약 두 statiion이 동시에 시작되면, 충돌이 발생한다.

Slotted ALOHA Network에서의 frame

CSMA

Carrier Sense Multiple Access (CSMA)

• 전송 신호를 감지하고 판단함
• 충돌을 줄이기 위함 → 누가 사용하고 있는지 medium을 감지하고 보냄
  • 각 station은 전송하기 전에 먼저 medium을 들음 (medium 상태를 감지함)
    • “sense before transmit” or “listen before talk’

CSMA내 충돌의 Space/Time model

• Eternet - Bus 형
  • 케이블에 컴퓨터가 선으로 연결됨

1) 채널이 비었기 때문에 B가 데이터를 보냄

2) B의 데이터가 도착하기전에 C가 채널이 비었기 때문에 데이터를 보냄

→ 충돌이 발생 (회색 부분)

CSMA내 Vulnerable Time

• Vulnerable time 동안은 다른 컴퓨터들은 데이터를 보낼 수 있음

Three Persistent method

• 충돌을 줄이는 방법

1) 1-persistent method

• 노드는 medium이 idle인지 busy인지 감지한다
  • 만약 idle이면, 즉시 보낸다. (probability=1)
  • 만약 busy이면, 끊임없이 medium을 감지한다.
• 채널이 비어있으면 100% 보낸다.

2) Non-persistent metod

• 노드는 medium이 idle인지 busy인지 감지한다.
  • 만약 idle이면, 즉시 보낸다.
  • 만약 busy이면 random period 동안 기다린다.

3) p-persistent method

• 노드는 medium이 idle인지 busy인지 감지한다.
• medium이 busy이면, idle이 될 때까지 지속적으로 감지한다.
  • 만약 idle이면, p 확률로 보낸다.
  • 만약 확률이 1-p 이면, 다음 사용 가능한 시간대까지 기다린다.
    • 보낼 확률 : p, 사용자가 많으면 낮게 사용자가 적으면 높게
• 0~1 사이의 R(Random Number)를 구함
  • 값이 P보다 작으면 보냄
  • 값이 P보다 크면 기다림

CSMA/CD

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

• 충돌 감지 알고리즘을 다루기 위한 알고리즘 추가됨
• Station은 frame 전송 후에 medium을 모니터링해서 충돌이 발생했는지 여부를 확인한다.
  • 충돌 없음 : 전송 성공
  • 충돌 발생 : frame을 재전송
• 전송 성공 여부 확인을 위해 ACK를 사용하지 않음, 프레임을 다 보내는 동안에 충돌 여부로 판단

CSMA/CD내 첫번째 비트 충돌

1) t1 시점에 A의 첫번째 비트를 보냄

2) C 입장에서는 시점에 아무도 매체를 사용하지 않아서 데이터를 보낸다.

3) 충돌이 발생한다.

4) C는 t3 시점에 충돌 여부를 알게된다.

5) A는 t4 시간에 충돌 여부를 알게된다.

• 충돌이 일어난 것을 알게되면 자신이 보낸 신호를 취소시키라는 신호를 보냄

충돌 여부를 알아내는 법

• manchester 신호가 전달됨
• 신호가 충돌하게 되면 신호가 갑자기 커지게 됨
  • 신호의 규칙을 위반하게 됨

→ 충돌을 알 수 있음

CSMA/CD내의 충돌과 취소

• 이더넷에서 사용되는 방법
• frame의 최소 크기가 존재한다.
  • 최소 크기를 정하는 법

• 프레임 크기를 t1~t4으로 잡으면 A는 충돌이 일어난 것을 알 수 없음
  • 프레임 크기를 늘려줘야 함 : 2배를 잡아줘야 함 (신호를 보냈다고 돌아오는 시간)

Minimum Frame Size

• CSMA/CD가 동작하기 위해서는 프레임 크기에 제한을 두어야 한다.
• 프레임 시간(Tfr, frame transmission time)은 최대 전파 시간(Tp, maximum propagation time)의 2배가 되어야한다.

station A가 D까지 frame을 보낸다고 가정하자

• 먼저 누가 사용하고 있는지 감지한다. (carrier sensing), medium에 에너지 레벨을 측정
  • 사용하고 있지 않으면 → buffer에 복사본(재전송을 위한)을 만들고 frame을 보낸다.
  • 누가 사용중이면 → medium을 끊임없이 모니터링한다.
• A가 512 bit를 보내기전에 충돌이 감지되지 않았다. → 충돌 없음
• A가 512 bit를 보내기전에 충돌이 감지되었다. → 충돌
  • 보내던것을 그만 보내고 buffer에 frame을 다시 보낸다.

이더넷에서 프레임의 최소 크기 512bit (64bytes) 계산 방법

• 초기에 CSMA/CD network는 10Mbps에 bandwidth를 가졌다.
• maimum propagtion time TP는 25.6μs (구리선에 전기가 흘러가는 속도와 길이로 계산)
  • maximum propagation time - 케이블의 한 끝에서 반대편 끝으로 보내는데 걸리는 전파 속도
  • 길이는 최대 2500m (500m 케이블을 장치로 연결함)

• minimum frame transmission time Tfr = 2 x Tp = 51.2μs
  • station은 충돌을 감지하기 위해 51.2μs 기간 동안 전송해야한다.
• frame의 최소 사이즈는 10Mbps x 51.2μs = 512bits(64bytes) 이다.
  • 이것은 표준 이더넷의 경우에 프레임의 최소 크기이다.

CSMA/CD 동작 흐름

• 표준 이더넷 네트워크 프로토콜은 broadcast network이다
  • sharing medium을 접근하기 위한 제어를 하는 접근 방법
• 표준 이더넷 프로토클은 1-persistent 방법의 CSMA/CD를 사용한다.

• 신호는 Bus에 퍼져 연결된 컴퓨터는 모두 받게 된다.
  • 자기 것이 아닌 신호는 무시함

Ethernet

• Eternet LAN은 1970년 대에 Robert Metcalfe와 David Boggs에 의해 개발되었다.

Standard Eternet의 구현

Medium

• Thick coax : 굵은 동축 케이블 (coaxial cable)
• Thin coax : 가는 동축 케이블
• UTP : 연선 (Unshielded Twisted Pair Cable)

Implementation

• 10 : 10 Mbps
• Base : Baseband로 신호를 전달

표준 이더넷 Encoding 방법

전송, 유휴, 충돌 동안 Energy level

• 0 level : 유휴 상태
• 정상 level : station이 frame을 보내고 있음
• 비정상 level : level이 충돌이 일어나 두 배가 됨

연결 장치의 세 종류

Hub & Switch

• 신호를 수신하고, bit pattern을 다시 만든다.

Hub

• phsyical layer에서 동작
• 신호를 받아서 그냥 전달, 약해진 신호를 좀 더 키워서 보내줌
• A가 D한테 보낸다고 하면 모든 노드들이 신호를 다 받음
  • 자신 것이 아니면 폐기

Switch

• A가 D한테 보낸다고 하면 각 port에 연결된 MAC 주소를 가지고 있어서 직접 전달한다.

CSMA/CA

• Colision Avoidence : 충돌을 피해보자
• wirless LAN에서는 충돌 감지가 불가능하다.
  • node가 다른 node에서 보낸 신호를 감지하지 못 할 수 있다.
  • hidden terminal problem, fading

• A와 C는 신호가 잘 잡히지 않음
• A와 C가 데이터를 보내면 B는 데이터 충돌이 일어난다.
• 신호가 멀어지면 급격히 떨어진다.
  • A는 C의 상태를 알지 못한다.

Basic Service Set(BSS)

• wirless LAN의 기본 서비스 구성 2가지
  1) Ad Hoc BSS : AP 없이 통신, 연결 장치 없이 node들끼리 서로 통신
  2) Infrastructure BSS : AP에 연결되어 통신, 연결 장치를 중심으로 통신
  

AP : Access point

IEEE 802.11은 두가지 MAC sublayer를 정의한다.

• Distributed Coordination Function (DCF)
• Point Coordination Function (PCF)

• IEEE : 국제 전기 전자 협회
• 802 project : LAN에 대한 표준 정의

layer들 사이의 관계

• wifi에 관한 것만 그려놓음
• 무선 전송 방식

Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)

• wireless network를 위해 발명되었다.
  • 충돌을 탐지가 어렵다. 될 수 있으면 충돌이 없도록 해보자
• CSMA/CA의 3가지 전략을 사용하여 충돌을 피한다.
  1) InterFrame Space (IFS)
  2) Contention Window
  3) Acknowledgment - 잘받았는지, 못 받았는지 확인
  

• 채널이 비면 IFS 시간 동안 기다림
• 필요하면 Contention window만큼 더 기다림

Inter-frame Space (IFS) : Access Defer (frame 보내는 것을 연기한다)

• 만약 medium이 IFS 기간동안 지속적을 유휴 상태인 경우, 그때 frame 전송을 허용한다.
  • 비록 채널이 유휴 상태이더라, 멀리 떨어진 station에서 전송을 시작했을 수도 있기 때문
• 802.11에서 IFS
  • DIFS(DCF IFS) : 늦추는 시간을 길게 잡음
    • RTS(Request to send),
  • SIFS(Short IFS) : 늦추는 시간을 짧게 잡음
    • Data frame, CTS(Clear to sned), ACK frame
  • PIFS : 늦추는 시간을 중간 정도로 잡음
• DCF (Distirbuted Coordination Function)
  • station이 채널에 접근하는 것을 추가 시간 동안 연기하도록 강제한다.

Contention window

• 조금 더 기다렸다가 보내자
• Contention window는 slot으로 나누어진 시간의 양을 의미한다.
• station은 slot의 random number를 선택해서 더 기다린다.
• Binary exponential backoff 전략

Acknowledgment

• data를 받은 이후, SIFS만큼 기다린 후에, receiver는 frame을 안전하게 수신했다는 ACK를 보낸다.

NAV(Network Allocaton Vector)

• Hidden Terminal Problem을 해결한다.
• idea : 송신자가 채널을 예약할 수 있도록 함. 긴 data frame에 충돌을 피하기 위함
• NAV는 medium에 연결을 얼마나 지연해야 하는지에 대한 timer이다.
  - 이 시간 동안은 다른 station은 보내지 말라는 뜻, medium 접근 연기

CSMA/CA & NAV

• 충돌은 handshake period동안만 발생한다. (RTS, CTS)
• RTS : Request To Send
  • 송신측이 수신측에게 본격적인 데이터를 전송할 의사가 있음을 알리는 신호
• CTS : Clear To Send
  • 수신측이 송신측에게 데이터를 받을 준비가 되어서 전송해도 좋다는 허락 신호
• DIFS : Distributed Interframe Space
• SIFS : Short Interframe Space

• CTS 신호를 받으면 NAV 상태로 넘어감
  • 누가 신호를 보내고 있다는 것을 알게 됨
  • 신호 감지를 하지 않아도 됨, medium에 접근 연기

PCF (Point Coordination Function)

• PCF는 WLAN 기반의 IEEE 802.11에 사용되는 MAC 기술이다.
  • PCF는 중앙집중식(centrallized) 경쟁 없는(contention-free) pooling 접근 방법이다.
• AP에 있는 기능이다.
  • point corindinator가 frame 전송을 허용하기 위해 CF-Poll frame을 전송한다.
  • pooling된 station이 보낼 frame이 없는 경우, null frame을 보낸다.

MAC sublayer

Repetition invterval 예시

• Beacon Frame : 각 station에게 통신하겠다는 것을 알려줌
  • station들은 데이터를 받기 위해 시간 동기화를 맞춤
• Poll frame을 통해 물어봄
  • 데이터를 보낼 것이 있으면 SIFS 만큼 기다리고 ACK와 data를 보냄
  • 데이터를 보낼 것이 없으면 Null frame을 보내고, NAV 상태로 넘어감
• AP가 중심이 되어 데이터를 보낼지 안 보낼지 확인
• contention-free 시간이 끝나면 CF end 신호를 보냄

SIFS, PIFS, DIFS

CSMA/CA 동작 흐름

Channelization

channelization (Channel Partition)

• link에 bandwidth를 station 사이에서 time, frequency, code로 나누어서 사용하는 것

Channelization Protocol

• Frequency Division Multiple Access (FDMA)
• Time Division Multiple Access (TDMA)
• Code Division Multiple Access (CDMA)

FDMA

Frequency Division Multiple Access (FDMA)

• bandwidth를 frequency로 나누어서 사용한다.
• 각 frequency band는 항상 station에 예약되어 사용된다.
• 각 station은 또한 bandpass filter를 사용하여 송신기 frequnecy를 제한한다.

• 주파수를 배정받아 24시간 내내 사용한다.

TDMA

Time Division Multiple Access (TDMA)

• bandwidth를 time으로 나누어서 사용한다.
• 각 station은 데이터를 전송할 수 있는 time slot이 할당된다.

CDMA

Code Division Multiple Access (CDMA)

• 여러 node들이 동일한 주파수를 사용하여 동시에 전송한다.

  • 신호는 mix해서 사용한다.
  • 신호는 code division 기술을 사용해서 분리한다.

• CDMA와 FDMA 차이

  • link의 전체 bandwidth를 하나의 채널이 차지한다.

• CDMA와 TDMA 차이

  • 모든 station이 동시에 데이터를 전송할 수 있다; time sharing이 없다.

Code를 가지고 통신하는 방법

CDMA는 coding theory에 기반을 둔다.

• 각 station은 code를 할당받는다.
• code는 Chip이라고 불리는 숫자 sequence이다.

Chip Sequence

Orthogonal Sequence

• 3가지 조건

CDMA에서 데이터 표현

• 만약 station이 0 bit를 보내면, -1로 인코딩된다.
• 만약 station이 1 bit를 보내면, +1로 인코딩된다.
• station이 idle 상태이면, no siganl을 보낸다. (0 volage level)

CDMA내 Sharing Channel

CDMA 내 4 station에 의해 만들어진 디지털 신호

CDMA 내 복합 신호 디코딩

• Station 3 이 Station 2의 신호를 감지하는 예

Chip Sequence 만드는 법

• 2차원 Walsh table
• Walsh table의 각 행은 chip에 sequence이다.