CH6. Link Layer and LANs

1. Introduction, services

• Link : 통신 경로를 따라 인접 node를 연결시키는 채널
• Layer-2의 packet = frame(Layer 3의 datagram을 encapsulate한것)
• data-link layer는 frame을 링크를 통해 인접한 노드로 전송하는데 사용이 되어 진다.
• Issues of Data Link Layer
  • Framing, link access 
    • Framing : 데이터그램에 헤더와 trailer(datagram의 마지막 부분에 붙이는것)를 붙여 encapsulate 과정을 거치는것
    • "MAC address"(IP와 달리 물리적 주소이다.)를 사용하여 목적지와, 출발지를 구분할수가 있다.
  • Error Control
    • parity bit, CRC(Cyclic Redundancy Code)를 이용하여 에러 검출을 한다.
    • Error recovery(FEC, ARQ) => Layer4에서 실행하던 error recovery와는 다른 형식이다.
  • MAC(Medium Access Control)
    • 브로드캐스트 네트워크에 관여를 한다.
    • 공유되는 매체를 제어하여 충돌을 억제하는 역할을한다.
  • Framing 
    • frame의 경계를 표시한다고 생각하면 된다.
    • 두가지 방식이 존재한다.

Bit-Stuffing     - frame 앞에 항상 Flag(01111110)를 붙여 다른 frame과의 경계를 지을수 있도록 하는 방식으로     - flag와 flag사이에서는 1이 연속적으로 6개 나타나서는 안된다.     - sender : 1이 연속으로 5개가 나오면 무조건 0을 추가한다.     - receiver : 1이 연속으로 5개가 나온뒤 0이 있다면 무조건 삭제한다.     => 받는 입장에서는 1이 6개가 연속이라 0을 붙인건지 5개만 있는데 0을 붙인건지 구분이 불가능 하므로 그냥 5개 뒤에는 무조건 붙이는 것이다.

Octet Stuffing     - 이것 또한 01111110를 통해 frame을 구분 짓는다.         - 이 경우는 byte 단위의 전송이다     - flag와 flag 사이에는 01111110가 있어서는 안된다.     - PPP packet에 01111110가 있게 되면 문제가 생긴다.     - sender : 01111110의 데이터가 오게 되면 앞에 control escape octet인 0x7d(01111101)을 붙이도록 한다, 01111110의 데이터는 0x20(0010000)과 xor 시켜 0x5E로 만든다.      - receiver : 0x7D가 있으면 뒤의 데이터를 다시 0x20과 xor시켜 원래의 데이터로 바꾸어 준다.

2.Error detection, correction

• Reliable Transmission
  • Forward Error Correctino(FEC) : 중복비트를 추가해서 receiver측에서 에러를 잡아낼수 있도록 하는것을 의미한다.
  • Retransmission : receiver측에서 에러 감지를 할수있고 에러 감지시 에러가 난 부분에대해 재전송을 요청하는것
• Error Control
  • channel coding(수신측에서 정보에 오류의 유무를 판단할수 있도록 수신측에서 신호를 변환하는 과정)에 사용이 되어진다.
  • 추가적인 비트가 에러를 검출하기 위해 프레임 뒤에 붙게 된다.
  • error correction과 error detection이 사용이 되어 진다.
• Parity checking
  • even parity check 와 odd parity check가 존재한다.
  • 각각은 데이터 bit와 parity bit에 속한 1이 짝수인가, 홀수 인가로 판단을 하게 된다.
  • odd parity check : 01111100 의 경우 마지막 bit는 parity bit, 앞의 7bit는 data를 의미하는데 현재 1의 개수가 짝수개이므로 error가 발생했음을 감지할수가 있다.
• Cyclic Redundancy Check(CRC)
  • 다항 코딩을 기본으로 한다.
    • 110100 = (X^5)*(X^4)*(X^2) 와 같은 형식으로 표현이 된다.
    • 주어진 다항식에 modulo-2 을 취해 코드 비트를 만들어낸다.

Reliable to handle erroed framesReliable to handle erroed frames

- P(x) = 전송될 frame의 형식이 다음과 같음을 의미한다.      - P(x)%G(x) = 0이 되게 되면 제대로 전송을 받음을 의미한다.      - 각각의 연산시에는 exclusive or을 시켜야 한다.  D(x) : message polynomial : 데이터로 오게 되는 값 G(x) : generator polynomial R(x) : remaider[R(x) = (D(x)x^r)/G(x)] Q(x) : quotient(몫), D(x)x^r = G(x)Q(x)+R(x) P(x) : 완전히 전송된 메세지 다항식, P(x) = D(x)x^r + R(x) = G(x)Q(x) 에러가 없는 코드라면 P(x)가 G(x)로 나누어 떨어져야 한다.

 

• CRC error detection rule
  • sender는 항상 연산이된 P(x)를 receiver에게 보내게 된다.
  • Receiver는 P(x)+E(x)를 받게 된다.
  • E(x) : 데이터가 전송되면서 만들어진 에러를 다항식으로 표현한것.(에러가 발생하지 않았다면 E(x) = 0)
  • (P(x)+E(x))%G(x) = 0이면 에러가 발생하지 않았다고 판단한다.
  • (P(x)+E(x))%G(x) > 0이라면 에러가 발생한것이다.

3. multiple access protocols

• Multiple Access Links and Protocols
  • link에는 두가지 타입이 존재한다.
  • : point-to-point - 이더넷, 스위치, 호스트 사이의 링크
  • : broadcast - traditional Ethernet, upstream HFC, 무선 랜
• Multiple Access protocols
  • MAC(Medium Access Control) protocols
  • 매체를 공유할때 전송을 공평하고 효율적으로 중재해준다.
  • 한곳에 서로 두개의 데이터가 동시에 오게 되는것 : "collision" 
  • collision을 최소화 시켜야 한다.
• Idle Multiple Access Protocol
  • Broadcast channel of rate R bps
  • 하나의 노드만 해당 채널을 사용하게 되면 R bps를 다 사용한다.
  • n명이 나누어 사용시 R/n bps로 사용하게 된다.
  • 항상 분산된 제어 알고리즘을 써야 한다.(하나의 노드가 전체의 전송을 제어하게 되면 위험하다.)
• MAC protocols : a taxonomy

- Channel Partitioning       - channel을 작은 조각으로 나누어 사용하는 것       - FDMA, TDMA(time), CDMA(code)       - Random Access        - channel을 나누지 않고, collision을 허용한다.        - collison 난 것에 대해 회복 알고리즘 필요        - ALOHA, CSMA, CSMA/CD, CSMA/CD       - Controlled-access protocols        - Taking turns        - Reservation, Polling, Token passing

• Channel Partitioning MAC procotocols : TDMA
  
  • Time division multiple access
  • 채널에는 각각의 라운드에 접근을 하도록 한다.
  • 각각 station(사용처)은 매 라운드 마다 고정된 길이의 slot(length = pkt trans time)을 할당 받게 된다.
  • 사용하지 않는 slot은 Idle 상태로 들어가게 된다.(낭비가 된다.)

TDMA : 6개의 station 에게 각각의 slot을 할당하고 보내도록 한다. 이때 1,3,4번의 station에서만 데이터를 보내고 있다.

• Channel Partitioning MAC protocols : FDMA
  • Frequency division multiple access
  • 채널을 여러 주파수 대역으로 나누어 사용한다.
  • 각각의 station들은 고정된 주파수 대역만 사용 하게 된다.
  • 사용하지 않는 station은 Idle 상태로 들어가게 된다.(그 동안 해당 주파수 대역은 낭비된다.)

FDMA : 6개의 station이 각각의 주파수 대역을 나누어 가지게 되고 보내고 싶은 것이 있을때 보내는 형식이다.

• Channel Partitioning MAC protocols : CDMA
  • Code Divisino Multiple Access
  • 주로 wireless broadcast channel에 사용이 되어 진다.
  • code를 사용하는데 데이터를 인코드 하기 위해서 각각의 유저에게 등록되어 진 것이다.
  • code가 직교하게 되면 여러 유저가 공존할수가 있고 동시에 데이터를 전송할수 있게 된다.

코드를 디코드 하는 식을 의미한다.

	1. sender 측에서 보내는 데이터를 해당 유저가 가지고 있는 코드와 곱하여 encode 과정을 거치게 된다. 2. eoncoding된 데이터가 보내지게 되고 receiver측에 가기전 Decode 과전을 거치게 된다. 3. decode 과정은 한슬롯 안에서의 code와 encoding된 데이터를 곱하여 더하는 과정을 의미하게 된다. 4. receiver 측은 decoding된 온전한 데이터를 전달 받게 된다.
	1. 이 경우는 두개의 유저가 한번에 데이터를 보내게 된 경우이다. 2. 각각의 데이터에 각각의 유저의 code를 곱하고 해당 값을 더하여 보내게 된다. (그림의 설명은 첫번째 슬롯을 가지고 한것이다.) 3. 자신이 받고자 하는 데이터의 코드를 곱해 다 더하게 되면 자신이 받고자 하는 데이터를 알수가 있다.

• Random Access Protocols
  • node가 자신이 보낼 packet을 가지고 있을경우 사용 가능한 모든 R bps를 사용하여 보내게 된다.
  • 사전에 서로간에 누가 보낼것인지에 대한 사전 조율이 존재 하지 않는다.
  • 두개이상의 node에서 보내게 되면 collision이 발생하게 된다.
  • collsion을 어떻게 발견하고, collsion을 어떻게 회복할지가 큰 관건이 된다.
  • ALOHA, slotted ALOHA, CSMA, CSMA/CD, CSMA.CA 가 존재한다.
• Slotted ALOHA
  • 각각의 프레임은 모두 같은 사이즈를 가져야 한다.
  • 각각의 slot들은 모두 같은 사이즈로 나누어져 있게 된다.(단위시간당 1 frame을 보내게)
  • 노드들 간에는 서로 동기화가 돼있어야 한다.
  • 노드들은 프레임을 slot이 시작할때만 보낼수가 있다.
  • 두개이상의 프레임이 하나의 slot에 들어오게 되면 노드들은 collision을 감지한다.

• Pure ALOHA
  • slot으로 나누어져 있지 않다, 동기화 되어 있지 않다.
  • collision은 sender에 의해 감지 된다.
  • collision이 발상해게 되면 sender는 무작위의 시간동안 기다리다가 해당 데이터를 다시 보낸다.
  • collision발생 확률이 더 높다.
• CSMA
  • carrier sense를 통해 collision을 줄이는 방식을 의미한다.
  • carrier sense : channel이 현재 idle 한 상태인지 busy 상태인지 확인을 하는것을 의미한다.
  • 다른곳에서 데이터를 보내고 있다면 보내지 않는다.
  • non-persistent, 1-persistent, p-persistent가 존재한다.
  • propagation delay 때문에 처음 carrier sense할때는 데이터가 없다고 느낄수가 있지만 데이터를 보내다가 다른 데이터 해당 channel을 통해 보내지고 있음을 확인할수가 있다. => collision 발생이 가능하다.

non-persistent	1-persistent	p-persistent
- carrier sense 당시 해당 채널이 busy 상태라면 랜덤 시간동안 해당 채널을 확인하지 않다가 해당 시간이 지나게 되면 확인을 다시 확인하여 데이터 전송 여부를 결정한다.	- carrier sense당시에 busy이면 계속해서 해당 channel이 Idle 될때까지 carrier sense를 이어간다.      - Idle 상태가 되게 되면 무조건 데이터를 보내본다.	- carrier sense당시에 busy이면 계속해서 해당 channel이 Idle 될때까지 carrier sense를 이어간다.      - Idle 상태가 되게 되면 p의 확률로 데이터를 보내본다. (1-p의 확률로 데이터를 보내지 않고 다시 대기한다.)

• CSMA/CD (Collision Detection)
  • collsion이 발생하게 되면 보내던 데이터들을 보내지 않는것

 

• "Taking Turns" MAC protocols
  
  • Token Passing : 순서대로 토큰을 다음 노드로 넘기면서 토큰을 잡은 노드가 데이터를 보낼수 있도록 하는 방식
    • token을 전달하는데에 overhead가 생길수도 있고, token을 전송중 잃거나, 경로가 끊기게된다면 다음 node는 token을 전달 받지 못하는 경우가 생길수 있다.
    • => 일정시간 동안 token이 안오게 되면 token을 만들어서 보내게 된다.
  • Token Ring protocol
    • 초기의 token protocol의 형태이다.
    • 각각의 node는 token을 받을때까지 기다리게 되고 token을 받게 되면 데이터를 보낸다,
    • 다 보내고 나면 해당 token을 다음 node로 넘긴다.
  • Token Bus
    • ring 구조와 달리 일직선 구조이다.
    • token 전달이 MAC protocol에 의해서 이루어 지게 된다.
    • Physical Bus, Logical Ring이 함께 존재한다.