Data link layer(2023.10.31)

<Taxonomy of multiple-access protocols>
- Multiple-access protocols
  1. Random-access protocols
  - ALOHA
  - CSMA/CD
  - CSMA/CA

  2. Controlled-access protocols
  - Reservation
  - Polling
  - Token passing

  3. Chanelization protocols
  - FDMA
  - TDMA
  - CDMA




<Random Access>
- collision : to avoid access conflict




<ALOHA>
- earlist random access method
- it can be used on any shared medium
- potential collisions in this arrangement
- The data from the two stations collide and become garbled -> 충돌이 발생하는 경우 데이터를 전부 못쓰게 된다
- 다른사람이 데이터를 보내는것을 신경쓰지 않고 데이터를 보낸다




<Frames in a pure ALOHA network>
- Each station sends a frame whenever it has a frame to send : 언제든지 데이터를 보낸다
- collision(충돌 가능성이 높아진다)
- 프레임을 보낼 때 충돌이 난 station은 random amount of time(back-ff time)을 한다
- Random backoff : 동시에 프레임을 보낼 때(=time out이 되면) random한 시간만큼 재전송
- After maximum number of retransmission attempts Kmax' a station must give up and try later
- Why this should be a random number? : Tb = Tp * [0~(2^k)-1]
  (Tp : maximum propagation time, K : the no. of unsuccessful transimissions(재전송을 시도하는 횟수))




<Vulnerable time for pure ALOHA protocol>
ex) A pure ALOHA network transmits 200-bit frames on shared channel of 200kbps.
    What is the requirement to make this frame collision-free?

sol) Average frame transimission time Tfr is 200 bits/200 kbps or 1ms
  The vulnerable time is 2*1ms=2ms. This means no station should send later than 1 ms before this station starts
  transmission and no station should start sending during the period(1ms) that this station is sending





<Slotted ALOHA network> - pure ALOHA보다 효율이 2배 증가
- The time slot length is Tfr and the station can send only at the beginning of the time slot
- The vulnerabel time is reduced to 1/2, Tfr




<CSMA>
- 충돌의 가능성을 최소화하기 위한 방식
- Carrier sense(반송파) multiple access(CSMA) requires that each station first listen to the medium
- 반송파가 있는지 없는지를 먼저 감지하고 보낸다
- The possibility of collision still exists because of propagation(전달시간) delay




<Behavior of three persistence methods>
Q) What should a station do if the 'chnnal is busy'
1) 1-persistent
  1. After the station finds the idle(아무도 보내지 않으면), it sends its frame immediately(데이터를 보낸다) -> 충돌 가능성이 제일 높다
  2. The highest chance of collision
  3. Ethernet(유선랜) uses this method

2) Non-persistent
  1. If the line is idle, it sends immediately. If the line is not idle, it waits a random amount of time and then senses the line again(구간동안 back을 한 다음에 random한 시간만큼 기다렸다 다시 보낸다)
  2. The chance of collision is reduced
  3. The efficiency is decreased -> 효율성이 떨어진다(시간만큼 통신채널을 낭비, 시간지연)
*random한다는 뜻 : random한 시간만큼 back up하고 충돌 가능성이 줄어든다

3)p-Persisent
  - The chnnel has time slots
  - It reduces the chance of collision and improves efficiency(충동가능성 줄이고, 효율 최대화)
  - If the line is dle
  1. With probability p, the station sends its frame -> p의 확률로 데이터를 보낸다
  2. With probability q=1-p, the station waits for the beginning of the next time slot and checks the line again ->q의 확률로 기다린다
    - If the line is idle, it goes to step 1
    - If the line is busy, it uses the back-off procedures



<CSMA/CD>
- Carrier sense multiple access with collision detection
- 데이터를 보내면서도 충돌이 나는지 안나는지 모니터링한다
  만약 충돌이 발생하면 프레임을 재전송한다
*CSMA : data를 보내기전에만 channel을 모니터 




<Minimum frame size>
- For CSMA/CD, the frame transimission time Tfr must be at least two times the maximum propagation time Tp(=2t)
- 만약 A가 frame을 전송하는 동안에만 collision 여부를 감지하므로, 2r시간동안 계속 frame을 보내고 있어야 한다





<CSMA/CA>
- wireless networks(LAN)에서 충돌을 방지
- 충돌을 막기위한 세가지 전략 : inter-frame space, the contention window, and ACK
- IFS(Inter-frame Space)
  - IFS시간만큼 우선순위 결정가능 -> shorter IFS has a higher proprity
  - channel이 idle일 때, station을 wait시킨다 -> IFS
  - IFS time allows to reach the transmitted signal from a distant station




<Contention window> - 경쟁 window(이 안에서 서로 경쟁)
- channel이 busy인지 지속적으로 체크, IFS만큼 기다렸다가 데이터 전송을 시도하는데 binary exponential 만큼 전송하는게 아니라 렌댐하게 전송한다
- An amout of time divided into slots
- Choose a random number of slots(binary exoponential back-off algorithm)
- The station senese the chnnel for each time slot
- If it is busy, it stops the timer(timer을 clear) and restarts it when the chnnel is sensed as idle




<Hidden station problem> - 무선랜에서 나오는 problem
- 무선통신 : 통신거리가 제한, 전파 세기에 따라 통신세기를 조절
- B and C are hidden from each other with respect to A(B->A<-C), A, B, C는 무선 -> A와 C는 서로 도달하지 못한다
- RTS transmitted from B cannot reach C(C should not transmit data)
- sol)CTS responded from A can reach B and C
  C knows some hidden station is using the channel and refrains from transmitting until the duration is over





<CSMA/CA and NAV>
- DCF inter-frame space(DIFS), Request to Send(RTS), short inter-frame space(SIFS), Clear to Send(CTS)
- Network Allocation Vector(NAV)
  - An RTS frame includes the duration of data tramission time
  - The other stations start their NAV timer, and wait until the timer expires




<Controlled access>
- 네트워크에 master가 한명이 있다고 가정, Master station이 허가를 해줘야 데이터를 보낼 수 있다




<Reservation> - 예약 프로토콜
- Master는 존재x, 데이터를 보내기 전 먼저 예약을 한다
- Data station 앞에 Reservation frame이 존재한다 -> 예약을 하여 차례대로 보낸다
Q. 이 방식에는 master와 slave station의 구분이 있나? 
sol) 없다






<Polling> - 조사한다
- Master와 Slave가 존재
- 모든 데이터 통신의 통신은 Master station을 통해서만 통신이 가능하다
- Primary device가 link를 control한다




<Select and poll functions in polling-access method>
1. Select
  - the primary device has something to send

2. Poll
  - Used by the primary device to solicit(초대하다) transmissions from the secondary device
  


<Token Passing>
- 링 토폴리지가 아니더라도 토큰을 사용하여 데이터를 통신한다
- 토큰을 보내는 predecessor(선임자)와 토큰을 받는 successor(후임자)가 존재
- 토큰을 잃어버리면 통신을 못하게 된다





<Link-Layer Addressing> - 가정, IP주소는 알고있는데, MAC주소를 모를 때 알아내는 방법
*L2주소 : MAC, L3주소 : IP 
*IP address : source-destination, link-layer address : destination-source

- The source(소스주소) and destination IP address(목적지 IP주소) define the two ends but cannot define which links(links 주소는 모른다) the packet should pass through
- Destination and source IP addrss should not be changed
  - IP주소가 source로 부터 목적지로 전송하는 동안에 IP주소는 바뀌지 않는다
- The link layer address is necessary(link address, physical address, MAC address)
  - link layer 주소는 link address, physical address(L2주소), MAC address도 필요하다
- The link addresses are changed every time the frame moves from one link to another
  - data link address는 계속 바뀐다 -> point(node) to point(node)(L1->L2까지만 전달)




<Three Types of address>
1. Unicasting address
- one-to-one 통신을 할 때(source -> destination) 사용
- 하나의 노드를 사용해서만 전달된다

2. Multicasting address
- one-to-many 통신을 할 때 사용 -> 특정 다수에게 데이터를 보낸다

3. Broadcast address
- one-to-all 통신(라디오, TV, 남산의 통신기) -> 불특정 다수에게 데이터를 보낸다
- jurisdiction(담당구역) is local -> Broadcast되는 지역이 네트워크에서 일부분을 뜻한다

-ex) Ethernet, are 48bits, all 1s





<ARP> 
- L3(Network layer)에 해당하는 Address Resolution Protocol(ARP) -> Network 계층 프로토콜
- ARP(Network layer)를 이용하여 datalink 계층의 주소를 알아낼 수 있다
- 보낼 때는 Multicast, 주소를 찾고나서 수신기가 보낼 때는 Unicasting






<ARP(L3-Network protocol) procedure>
- ARP request packet을 만들어서 broadcasting(link layer) address를 만든다
- A노드가 B노드에게 packet을 보내려고할 때, A가 B에게 ARP request packet을 보내고 B는 A에게 recipient's IP address와 link layer address를 보낸다 -> Unicasting
  (가정, B노드의 IP주소는 알고, B노드의 data link 주소를 모를 때)
- A의 Caching 메모리에 B에 대한 데이터링크 주소를 저장하여 다음번에 A가 B에게 packet을 보낼 때 메모리를 찾아서 B의 주소를 알아서 바로 보낸다
  - A host has a cache to store IP address and the corresponding link layer address of another host/router  




<Channelization>
- FDMA, TDMA, CDMA는 time slot이 정해져 있다(Mux장치 -> 순서가 정해져 있어 충돌이 발생하지는 않는다)
- TDMA :  Time-division multiple access
- TDM에서 MUX는 하나의 장치에서 여러개의 time slot을 만들어 보내지만 TDMA는 각각의 단말기에서 자기 time slot에서만 보낸다
Q. TDM과 TDMA의 차이점
sol) TDM에서 MUX는 하나의 장치에서 여러개의 time slot을 만들어 보내지만 TDMA는 각각의 단말기에서 자기 time slot에서만 보낸다