기초컴퓨터네트워크 26 (CSMA/CD, CSMA/CA, Controlled Access, Reservation, Polling, Token Passing, Channelization, FDMA, TDMA, CDMA)

TonyHan·2021년 6월 4일

21) 기초컴퓨터네트워크

목록 보기

27/30

3. CSMA/CD (Collision Detection)

• Collision detection
– If a collision occurs, the sender detects the collision and acts upon it

• Used in Ethernet

CSMA + CD(Collision Detection)인 매체 제어 방식을 이야기 한다. CD는 shared 매체의 여러 device가 동시에 frame전송시 신호가 섞이게 된다. 이것을 수신자 측에서 잘 받지 못하게 되는데 이걸 collision이라고 한다. 이것에 맞추어서 행동을 하는 것이다.

• Collision situation
– Node A transmits a frame, but C transmits before the frame reaches C

충돌이 발생하는 상황을 생각해보자. A가 t1이라는 시간에 전송을 시작하고 어떤 노드가 전송시 모든 bit를 회선에 올리는데 시간이 걸린다. C가 데이터를 전송하려고 하는데 A로 부터 전송한 bit가 C에 도달을 했으면 C는 전송하지 않았을 것이다. 문제는 C가 A로 부터 bit가 오기전까지 t2에는 회선이 idle상태라고 생각하고 전송할 수 있다. 그러면 shared 매체에서 A, C는 섞이게 된다.

collision을 detect할 수 있는 순간은 C에서 전송한 데이터가 A에 도달한 것이다. 그게 t4라고 하면 t4에 가서 collision이 발생했는지 아닌지를 판단할 수 있다. collision이 있었으면 그것에 맞는 조치를 할 것이다.

• How a node detects collision
– While transmitting my frame, another frame arrives -> detect collision

무엇을 기준으로 collision인지 판단하는가? A가 전송하는 동안에 다른 signal이 감지된 경우 그것을 collision으로 본다. 만약 A는 전송이 끝나고 C가 도달했다면 충돌로 볼 수 없다.

즉 내가 전송하는 중간에 다른 노드의 signal이 오면 collision이라고 판단하는 것이다.

• Successful collision detection
– If a collision occurs, the node should be able to detect it
– When the collided frame arrives, I should still be transmitting my frame
– If I finish my transmission too early, I might not be able to detect collision

내가 내 frame 전송중에 collision이 발생하도록 한 frame이 나한테 도달해야 collision detection을 할 수 있다. 만약 내 transmission이 빨리 끝나서 collision 발생 frame이 이후에 들어오면 collision이 detect못하는 것이다.

• Condition for collision detection failure
– Node A transmits at t1
– Node C transmits at t2 -> collides with A’s frame
– The collided frame reaches node A at t4
– If node A finishes transmission before t4, A fails to detect collision

t4라고 하는 시간 이전에 A의 전송이 끝나면 collision을 확인못한다.

Then how long should node A transmit?
- If A starts transmission at t1, the first bit reaches C at t1+tp
- If C transmits before t1+tp, it is a collision
  - C cannot transmit after t1+tpbecause of carrier sensing.

즉 collision을 잘 detect하기 위해서는 frame을 짧게 전송하면 안된다.

이를 수식으로 나타내면 A가 C에 도달하는 시간은 t1+Tp(Tp는 t1에서 t3까지의 시간) 그럼 이때의 t2는 t1+Tp보다는 이전시간이어야 한다.

• Then how long should node A transmit?
– Suppose C transmits just before t1+Tp.
– The collided frame reaches node A at t1 + 2 * Tp
– At t1+2tp, node A should still be transmitting
– Thus, Tfr ≥ 2 * Tp

따라서 collision detect를 위해서는 전송시간 Tfr이 2 * tp보다 크거나 같아야 collision detect가 가능하다.

Example

• A network using CSMA/CD has a bandwidth of 10Mbps. If the maximum propagation time is 25.6μs, what is the minimum size of the frame?

회선의 전송속도가 10Mbps이고 최대 지연시간이 25.6us일때(끝과 끝 간격)

결국에는 collision을 detect 하기 위해서는 51.2정도 보다는 커야 하기 떄문에

(전송시간 = frame size/10Mbps) >= 51.2us 라는 식이 나온다. 그래서 minimum size of the frame을 구할 수 있다.

• When collision is detected
– Binary exponential backoff similar to ALOHA

collision이 발생했다면 ALOHA와 유사하게 진행한다. 특정 숫자를 뽑아서 그 숫자만큼 time slot을 기다렸다가 보내는 것이다.

4. CSMA/CA (Collision Avoidance)

• Used in systems that cannot detect collision

• Used in Wi-Fi

• The Wi-Fi interface is half-duplex, which means it cannot transmit and receive at the same time -> cannot detect collision as CSMA/CD

Wi-Fi에서 사용하는 방법, Wi-Fi는 CSMA/CD를 쓰기에는 무선은 유선에 비해서 신호의 세기 차이가 매우크다. 데이터 전송 Tx와 수신 Rx가 있을때 Wi-Fi에서는 Tx의 세기가 Rx의 세기에 비해 엄청크다. 그래서 Tx도중에는 Rx를 감지할 수 없다.

• Do random backoff before a collision occurs

• Wait for ACK

• If ACK does not come, regard it as collision -> increase backoff exponentially

random backoff는 CSMA/CD에서는 collision 발생시에 한다. 하지만 CSMA/CA는 collision이 없어도 random backoff를 하게 된다.

collision을 감지할 수 없기 때문에 ACK를 받는다.ACK이 특정시간안에 오지 않으면 collision이 발생했다고 판단한다. 그때 exponentially backoff 한다. 그리고 k의 값을 증가시킨다.

• IFS (inter-frame spacing)
– Even if channel is sensed idle, another node might just started transmission. IFS is inserted in order to avoid collision.

프레임을 전송하려면 처음에는 carrier sensing을 한다. 그런데 busy상태이면 계속 sensing을 하다가 idle 상태가 될것이다.

그러면 IFS라는 시간 간격만큼 기다려본다. 왜냐하면 나는 idle라고 판단했지만 신호가 퍼지어 있어서 아직 도착하지 못했을 수 있기 때문이다.

• Contention window
– A range from where a node selects a random number (e.g. 0-31)
– A node selects a number from the contention window
– For each time slot, if the channel is idle, count down the number (e.g. time slot = 20us)
– If the counter becomes zero, start transmitting.

노드가 random number 중에 하나를 고른다. 그런다음에 그만큼 기다린다.

바로 전송하지 않고 Contetntion window라고 하는 Binary exponential backoff하는 구간이 나온다. 그것을 contention window라고 부른다. node가 random number중에 하나를 고른다. 예를 들어 내가 15를 고르면 15 * 20us 를 해서 300us만큼 기다렸다가 전송을 하는 것이다.
그보다는 count down을 한다. 20us가 지날때마다 카운트하고 counter가 0이 되면 그때 transmission을 한다.

• Contention window
– Suppose a node selects 15 as the random number (time slot = 20us)
– If the channel is idle for 15x20=300us, the node transmits
– If the channel becomes busy while counting, the node pauses until the channel becomes idle again
– If the channel becomes idle, the node waits for IFS and then restart counting

300us만큼 기다리는데 반드시 이 동안은 channel이 idle상태여야 하는 것이다.(즉 sensing을 하면서 idle 상태이어야 count down을 한다)

만약 채널이 busy가 되면 계속 기다린다.

그러다가 idle상태가 되면 다시 count down을 한다. 그리고 IFS만큼 기다렸다가 이전에 카운트 한 곳에서 다시 시작해서 카운트를 시작한다.

• Binary exponential backoff
– If a collision occurs, the contention window size doubles (e.g. 0-31 -> 0-63)
– If a frame is successfully transmitted, the contention window reduces to initial range

time out이 발생한 경우 collision이 발생했다고 판정하고 그때는 contetntion window size를 2배로 늘린다.(0-31 -> 0-63)

정상적을 ACK가 온 경우 contention window를 다시 처음의 크기로 바꾼다.

Example

• Assumptions
– time slot = 20us
– IFS = 50us
– initial contention window: [0-31]
– transmission time of a frame = 100us
– propagation time = 0 (neglected)
– no ACK

• Nodes A, B, C are in the same wireless LAN
– If node A transmits, node B and C both can see the signal

• 0us: A, B, and C has frames to send, they all wait for IFS (50us).

• 50us: A, B, and C selects a random number. A chooses 10, B chooses 15, and C chooses 20. They start counting down.

• 250us: A’s counter becomes 0. A starts transmission. B and C see A’s signal and pause count down.

0us에 A,B,C가 모두 전송할 프레임이 있다고 가정하자. 그리고 모두다 채널이 busy상태에 있다가 idle상태가 된 시간이 0us로 잡는것이다. IFS는 50us만큼 쉬게 된다.

50us에 A,B,C가 random number을 선택한다. A는 10, B는 15, C는 20을 선태갰다고 가정하자

250us가 되면 A의 카운트가 0이 된다. 그 순간에 A가 전송한다. B, C는 그것을 감지한다. 그러면 A는 busy상태이고 count를 멈춘다.

• 350us: A’s transmission finishes. B and C sense channel as idle. B and C wait for IFS.

• 400us: B and C resume counting. B’s counter = 5, C’s counter = 10

• 500us: B’s counter becomes 0. B starts transmission. C pauses counting.

100us가 다시 지나서 A의 전송이 끝난다. 그러면 B와 C는 idle 상태를 감지한다. IFS만큼 기다린다.

400us IFS가 다 지나고 B는 5가 남았고 C는 10이 남았다.

500us에 B는 0이 되고 B가 전송하기 시작한다. C는 멈춘다.

• 600us: B’s transmission finishes. C waits for IFS.

• 650us: C resumes count down. C’s counter = 5

• 750us: C starts transmission

• 850us: C finishes transmission

600us에 idle 상태가 되고 C는 IFS기다리낟.

650us에 C는 5만큼 count한다.

750us에 C는 전송한다.

850us에 C의 전송이 끝난다.

=== Controlled Access ===

1. Controlled Access

• Does not depend on random number to avoid collision

• Nodes agree on a rule to take turns and transmit

• Reservation
• Polling
• Token Passing

Controlled Access는 random number에 의지하지 않고 collision을 처리하고자 하는 방식을 이야기 한다. 규칙을 정하고 이에 따르게 한다. 그래서 Reservation, Polling, Token Passing의 방식이 존재한다.

2. Reservation

• Before transmission, a node “reserves” a time slot.

• There is a “reservation slot” before data slots, where nodes reserve their transmission.

• If there are N nodes, the reservation slot has N mini slots, where a node can send signal to announce that it will be transmitting.

전송이 일어나기 전에 time slot을 reserve하는 시간이 있다.

reservation slot동안에 전송할게 있는 node들은 예약을 하는 것이다.

시스템에 N개 노드가 있으면 reservation slot에 N개의 mini slot이 있다. mini slot 동안 내가 보낼 frame이 있으면 signal을 보내서 내가 transmit 할게 있다고 말하는 것이다.

• In the first period, nodes 1, 3, and 4 reserve channel

• In the second period, only node 1 reserves channel

참고로 오른쪽에서 왼쪽으로 읽는거다.

reservation구간과 데이터 전송구간이 나뉘어져 있는 것을 확인할 수 있다. 각자 자기의 mini slot이 있다. 그래서 자기의 mini slot구간에 데이터를 보내야 한다면 signal을 보낸다. signal을 보내면 station이 이것을 듣는 것이다. reservation frame에 1,3,4번이 transmission을 하겠다는 signal을 보내는 것이다. 그럼 reservation frame이 모든 station들에게 전달되었다고 보는 것이다.

그러면 transmission id가 더 작은 것부터 전송하게 된다.

reservation 구간이 데이터 전송 구간이 아니기 때문에 overhead가 존재한다.

3. Polling

• One of the nodes become the “primary node”

• Other nodes become secondary nodes

• The primary node controls data transmissions
– It decides who sends when

• The data should always go through the primary node
– Two secondary nodes cannot communicate

대장 노드를 primary node라고 부르고 다른 노드를 secondary node라고 부른다.

primary node가 다 관리한다. 누구를 언제 전송할지 결정한다.

이런 polling의 특징은 secondary node들끼리 데이터를 전송하려고 해도 그 데이터가 primary node를 거치어서 가게된다.

• Select (SEL): a primary node sends data to a secondary node
• Poll: a secondary node sends data to a primary node

primary node가 secondary node로 보낼 데이터가 있다면 select를 보낸다.

SEL을 보내면 ACK가 오고 Data가 가고 ACK가 온다.

A,B는 직접 데이터 전송을 할 수 없다. 그냥 primary node가 poll하기를 기다린다. 보낼게 없다면 NAK이 오고 보낼게 있다면 Data가 보내진다. primary는 그것에 대해 ACK를 전송한다.

4. Token Passing

• The goal of medium access control is to have only a single node transmit at a time

• This mechanism uses a unique “token” to determine who should transmit.
– There is only one token in the system

• A node can transmit only if it possesses the token.
After data transmission, the node passes the token to
the next node in the predefined sequence.Introduction to Computer Networks

medium access control을 하는 이유가 한 순간에 한 노드만 전송할 수 있도록 하는 것이다.

그런 목적을 달성하기 위해서 token이라는 것을 사용하는 것이다. token을 소유한 node가 데이터를 전달할 수 있다. 그러면 token은 그 시스템 상에서 하나만 존재해야 한다.

token을 소유한 노드가 데이터 전송하고 그 다음 노드로 token을 pass해준다. 그러면 token을 가진 노드만 전송하니 collision이 발생안한다.

• Various types of token passing sequence(topology)

• Physical ring
– Simple, token does not need to have address of next node
– If a link breaks, the system is stalled

link에 break가 생기면 system이 멈출 수도 있다.

• Dual ring
– When a link breaks, the system can continue using the second link

physical ring의 문제점을 해결하기

• Bus
– The token should indicate the next node
– Tolerant to link break

• Star
– The token is always passed through the hub
– Easy to add/remove node from the system

결국 token 은 계속해서 token을 전달할 수 있도록 하는 것이 중요한 것이다.

=== Channelization ===

1. Channelization

• A mechanism to divide the medium into multiple channels using time, frequency, and code division techniques

• Frequency-Division Multiple Access (FDMA)

• Time-Division Multiple Access (TDMA)

• Code-Division Multiple Access (CDMA)

여러면이 share하는 것을 막기 위해 매체를 여러개로 나누는 것이다. 주파수로 나누기(FDMA), 시간으로 나누기(TDMA), 코드로 나눈다(CDMA)

2. FDMA

• Divide the bandwidth into multiple frequency sub-channels, and allocate sub-channels to different users

주파수를 나누고 데이터를 실어서 보내게 된다.

• Guard band needed between sub-channels

• Suppose we divide a 20MHz channel into 1MHz sub-channels. If we need 100kHz of guard band, how many sub-channels can we make?

나한테 주어진 주파수 영역을 나누는데 너무 가깝게 나누면 간섭이 생긴다. 그래서 주파수 사이를 guard band 만큼 띄우는 것이다.

예를 들어 20MHz안에 1MHz를 만든다면 못해도 0.1MHz(=100kHz)의 구간을 만든다.

3. TDMA

• Divide the channel into time slots and allocate time slots to different users

시간으로 나누어서 전송하는 방법도 있다.

• TDMA is more flexible than FDMA, since we can change the allocation rate dynamically.

• However, TDMA requires time synchronization among nodes, which is a difficult problem.

시간축으로 나누는 것이 보다 dynamic하게 이용할 수 있다.

그러나 TDMA는 time synchronization 문제가 있다. 노드간의 시간이 맞지 않을 수 있다는 문제점이 있다.

4. CDMA

• In CDMA, multiple nodes transmits at the same time, using the same frequency

• The signals will be mixed, but they can be separated using code division technique

CDMA는 여러개의 노드가 같은 시간 같은 주파수 대역에서 전송했음에도 충돌이 나지 않는 것이다.

code division technique으로 신호를 분리하는 것이다.

• Suppose 4 nodes transmit data

같은 시간 같은 주파수 대역에 d1,d2,d3,d4를 전송한다. 그런데 각 node에 c1,c2,c3,c4 곱해서 보내지고 4개의 signal이 다 더해진다.

• Codes are allocated to nodes. Suppose ci is the code allocated to node i. The codes have the following characteristics:
– ci x cj = 0, if i ≠ j
– ci x ci = 4 (number of nodes)

수신자는 4개가 다 더해진 신호를 분리해낼 수 있어야 한다. ci x cj = 0이고 ci x ci = 4가 되도록 보내는 것이다.

• When a node transmits data, it multiplies its data and its code. (di x ci)

• If all four nodes transmit, the mixed data willbe:

• The receiver multiplies the sender’s code to the received data
• If a node wants to receive node 1’s data, it multiplies
c1 and the received data
• Then, divide the result by 4 (number of nodes)

node 1번을 수신하기 위해서 1번의 code를 받은 데이터에 곱한다. 그러면 1번이 보내고자 했던 코드가 나온다.

CDMA

• The following code set can be used in CDMA

자기자신하고 곱하면 4가 나온다. 하지만 다른 것과 곱하면 0이 나온다. 그래서 원하는 주파수만을 구할 수 있게 된다.

• The code set has the required characteristics
– If multiplied by itself (inner product), the result is 4.
– If multiplied by other code, the result is 0.