Computer Network: 12주차

Link Layer

          > Host 와 router 는 nodes 라 부른다

          > 이웃하는 노드들을 잇는 경로: links

                    >> wired, wireless, LANs

          > datagram -> frame

          

          >Datagram 은 다른 링크 프로토콜을 통해 링크 사이에 전달된다

          > 각 프로토콜은 서로 다른 서비스를 제공한다.

          > Transportation Analogy

                    >> tourist: Datagram

                    >> transport segment: Communication Link

                    >> Transportation mode: Link Layer Protocol

                    >> Travel agent: Routing Protocol

 

Link Layer Services

          > Framing, Link Access

                    >> Datagram을 암호화 하여 frame 으로 만들고 헤더와 trailer 추가

                    >> Shared medium 인 경우 channel access

                    >> 송신지와 수신지를 알기 위해, 헤더에 포함된 MAC 주소를 사용

          > 인접 노드 간의 신뢰성 있는 전송

                    >> low bit-error link에서는 거의 사용되지 않음

                    >> wireless: high error rates

          > Flow Control

                    >> 인접한 송신, 수신 노드간에 페이스를 맞춘다

          > Error Detection

                    >> 신호 감쇠, 노이즈로 인한 오류 발생

                    >> 수신자가 오류 감지

                    >> 재전송신호를 보내거나 프레임 삭제

          > Effort Correction

                    >> 비트오류를 식별 & 수정

          > Half-duplex, full-duplex

                    >> Half-duplex 를 사용하면 양 끝에 있는 노드 모두 전송이 가능하지만 동시에는 x

 

Where is Link Layer Implemented??

          > 모든 호스트에서

          > In Adapteor ( network interface card )

          > 호스트의 시스템 버스에 연결

          > HW, SW, Firmware 의 합작

 

Adaptors Communicating

# sending side

          > 데이터 그램을 프레임으로

          > error checking bit, rdt, flow control 등을 추가

# receiving side

          > 에러, rdt flow control 등을 찾는다

          > Datagram 을 추출, 상위 계층으로 전달

---

Error Detection

# Note 

          > EDC = Error Detection and Correction bits

          > D = Data protected by error checking

          > 에러 감지는 100% 신뢰성있지는 않다

Error Detection & Correction

# Parity Checking

          > Single bit parity : Detect single bit errors

Single bit parity check

          > Two-dimensional bit parity: Detect and correct bit errors

 

2D bit parity check

#Cyclic Redundancy Check

          > Data bits  = D (binary)

          > r+1 bit pattern 을 고른다: G

          > 목표: choose r CRC bits, R, such that

                    >> <D,R> is exactly divisable by G

                    >> 수신자가 G를 알고 <D,R>을 G로 나눈다. -> 0이외의 값이 나온다면 error

                    >> r+1 bit 보다 작은 에러들 모두 감지 가능

 

---

# 6.3 Multiple Access Protocols

      

# Multiple Access Links, Protocols

        > 두 종류의 링크

                 >> Point to point

                 >> Broadcast

         > Multiple access protocols

                 >> 하나의 공유된 broadcast channel

                 >>  노드들의 두개 이상의 동시 전송: Interference

                         >>> 한 노드가 두개 이상의 signal 을 한번에 받을 경우 : collision

                 >> Distributed Algorithm: 어떻게 노드들이 체널을 공유할지를 결정

                 >> 체널 공유에 대한 communication은 해당 체널을 사용해야 한다: no out-of-band channel for coordiantion

         

         > Ideal Multiple access protocol

                 >> 가정: broadcast channel rate (R bps)

                         1. 한 노드가 전송하고자 하면, rate R에 가능

                         2. M 개의 노드가 전송하고자 하면 각자 R/M rate 에 가능

                         3. Fully Decentralized

                                   - no special node to coordinate transmission

                                   - no synchronization of clocks, slots

                         4. simple

 

         >MAC Protocols: 3가지

                 >> Channel Partitioning

                         - 체널을 더 작은 조각으로 나누고 그 조각을 노드에게 할당

                         - 받은 조각은 독점적

                 >> Random Access

                         - 채널을 분할하지 않고 충돌을 허용

                         - 충돌 발생시 복구

                 >> Take Turns

                         - 노드들이 번갈아 가며 채널을 사용

                         - 많은 데이터를 전송해야 하는 노드는 더 길게 사용 가능

 

#Channel Partitioning

         > TDMA: Time Division Multiple Access

                 >> round 형식으로 채널에 접근

                 >> 각 스테이션은 라운드마다 고정길이 슬롯을 할당 받는다 ( length = packet transmission time)

                 >> 사용되지 않는 슬롯은 비활성화

         > FDMA: Frequency Division Multiple Access

                 >> 채널 은 frequency band로 나뉜다

                 >> 각 스테이션은 고정 frequency band를 할당 받음

                 >> 사용되지 않는 벤드는 비활성화

 

#Random Access Protocols 

         > 노드가 보낼 패킷이 있다면 

                 >> 그냥 최대 전송률로 보내버린다.

         > collison 발생

         > 이 프로토콜은 다음을 정의해야 함

                 >> collision 을 어떻게 감지하는지

                 >> collision으로 부터 어떻게 복구하는지

         > Slotted ALOHA

                 >> 가정

                         - 모든 프레임은 같은 크기

                         - 시간은 같은 슬롯크기로 나뉜다

                         - 노드는 슬롯 시작부분에서만 전송을 시작

                         - 노드들은 동기화 상태

                         - 둘 이상의 노드가 전송을 하면 모든 노드가 충돌 감지

                 >> 동작

                         - 노드가 fresh frame 을 얻으면 다음 슬롯에서 전송

                         - if ( no collision) : node can send new frame in next slot

                         - if (collision): node retransmits frome in each subsequent slot until success

                 >> Pros

                         - 하나의 활성화 된 노드는 최대 전송률로 보낼 수 있다

                         - Highly decentralized: 노드 내의 slot들만 동기화 필요

                         - simple

                 >> Cons

                         - Collisions

                         - Idle slots

                         - Node가 패킷이 전송되기 전 충돌을 감지할 수도 있다

                         - clock 동기화

 

         > Pure(unslotted) ALOHA

                 >> Frame 이 도착하면 즉시 재전송

                 >> Collition 확률이 높아진다

         > 각 방법 효율성

                 >> 가정(slotted)

                         - 프레임을 많이 보내야 하는 N개의 노드, 각 각 p의 확률로 전송

                         -  Success prob 특정노드: p(1-p)^N-1

                         -  아무 노드나 성공할확률: Np(1-p)^N-1

                         - Np(1-p)^N-1 을 최대화 하는 p 가 효울 제일 good

                         - N 이 무한대로 갈때 37%

                 >> Pure Efficiency

                         - p ( 1- p) ^(2*(N-1))

                         - N 이 무한대로 갈때 18%

 

+> CSMA(Carrier Sense Multiple Access)

                 >> Listen before transmit

                 >> Channel이 idle 감지시 전체 프레임을 전송

                         >>> 채널이 사용중일경우 전송을 연기

                         >>> 다른 사람 방해 x

                 >> 하지만 여전히 collision 이 발생 가능

                         >>> 전파지연(propagation delay) 는 서로의 전송을 듣지 못할 수 있음

                         >>> distance / propagation delay 는 충돌 확률 계산

                 >> Collision Detection

                         >>> Collision 이 감지되면 즉시 abort (reduce channel waste)

                         >>>  유선 LAN 에서는 쉽다: measure signal strength, compare transmitted, received signals

                         >>> 무선 LAN 에서는 어렵다: 시그널이 약해서

 

                 >> Ethernet CSMA/CD Algorithm

                         1. NIC 가 데이터그램을 받고 frame을 만든다

                          2. NIC가 휴식중인 체널 감지시 frame transmission을 시작한다

                                 - NIC 체널이 바쁨을 감지하면 휴식중인 체널을 기다린다

                         3. NIC가 다른 transmission 없이 전송에 성공하면 끝

                         4. 중간에 다른 transmission 이 감지되면 abort & jam

                         5. Abort 후 NIC는 binary backoff 수행

                                 - m 번째 collision에서는 K를 고른다 {0,1,2,...,2^m -1}

                                 - NIC 가 K*512 bit times 동안 기다리고 step 2로 복귀

                 >> CSMA/CD 효율성

                         >>> t(prop) = LAN 연결에서 두 노드 사이의 최대 prop delay

                         >>> t(trans) = time to transmit max size frmae

                         >>> 효율성은 1에 가까워진다 when

                                 - t(prop) 이 0과 가까워질때, t(trans)가 무한대가 될때

                         >>> better performance than ALOHA: simple, cheap, decentralized

 

         Taking Turns MAC Protocols

                 >> Channel Partitioning MAC protocols

                         >>> 체널을 효율적으로  이용

                         >>> 만약 비효율적이고 느리다면, channel access 에 delay, 1/N bandwidth. (even with one active node)

                 >> Random Access MAC Protocols

                         >>> Efficient at +low load: 하나의 노드가 체널을 전부 사용가능

                         >>> High load: collision+

                 >> Polling

                         >>> "Master Node" 가 slave node 들을 초대하여 각자의 turn  을 갖도록

                         >>> 멍청한 slave node들과 보통 사용

                         >>> concerns: polling overhead, latency , single point of failure

                 >> Token passing

                         >>> control token 이 한 노드에서 다른 노드로 순차적으로 전달

                         >>> concerns: token overhead, latency, single point of failure