CHAP 4. LAN(Local Area Network): Part 2

강의내용 - Stalling책

Chap. 12. 이더넷(Ethernet)

• 강의 내용

- LAN의 MAC(Medium Access Control) protocol

Contention Protocols

3. CSMA (Carrier Sense Multiple Access)

- In LAN, it is possible for stations to detect what 'other' stations are doing.

⇒ "Carrier sense" protocols are possible.

- Idea: Stations listen for a carrier (전송신호), and act "accordingly".

⇒ How? On a metal cable, we can easily "detect" the existence of a signal being transmitted.

⇒ 'Less' collisions

⇒ The max. utilization achievable using CSMA can far exceed that of ALOHA or slotted ALOHA.

- Method:

․ A station wishing to transmit first "listens" to the medium

⇒ To determine if another transmission is in progress (carrier sense).

․ If the medium is 'idle', the station may transmit.

If the medium is 'in use', the station must wait.

⇒ What a station should do if the medium is found busy?

① 1-persistent CSMA - 전송신호 감지시, 언제나 '살아남아' 기다렸다가 다시 보냄.

② Non-persistent CSMA - 전송신호 감지시, 언제나 나중에 다시 try함.

③ p-persistent CSMA - 전송신호 감지시,  확률 p만큼은 '살아남아' 기다렸다가 보내고, 확률 (1-p)만큼은 나중에 다시 try함.

(Stallings 10th ed.) p.376 Fig. 12.2

(Stallings 7th ed.) p.596 Fig. 16.1

1-persistent

medium busy

a frame is ready

wait and transmit as soon as medium goes idle

medium busy

a frame is ready

with prob. p, transmit

medium busy

a frame is ready

wait constant or variable time delay and decide again

Non-persistent

p-persistent

with prob. q(=1-p), delay one time unit (τ)

and decide again with p & q

wait until medium goes idle

- 3 CSMA's

․ 1-persistent CSMA - 'selfish' (greedy) protocol

① If the medium is idle, transmit; otherwise, go to step ②.

② If the medium is busy, continue to listen until the medium is sensed idle; then transmit 'immediately'.

․ Non-persistent CSMA - 'deferential' (공손한) protocol

① If the medium is idle, transmit; otherwise, go to step ②.

② If the medium is busy, wait an 'amount of time' drawn from a prob. distribution (the retransmission delay) and repeat step ①.

⇒ 'Better' channel utilization (∵충돌횟수 감소), but 'longer' delays than 1-persistent CSMA

․ p-persistent CSMA - 'hybrid' protocol

① If the medium is idle, transmit with prob. p, or delay one time unit with prob. (1-p). The time unit is typically equal to the max. propagation delay (τ).

② If the medium is busy, continue to listen until the medium is sensed idle and repeat step ①.

③ If transmission is delayed one time unit, repeat ①,

- In spite of carrier sense, a collision occurs, if two or more stations attempts to transmit at "about" the same time.

Case 1: the propagation delay

sender

receiver

ready

"signal not yet reached"

begins to send

Case 2: 1-persistent

sender

receiver

ready

Upon finishing,  both begin

to send simultaneously

ready

"signal is sensed, so both wait"

․ How long will it take a sender to realize that there has been a collision?

⇒ 2τ

ready(Sn)

"signal not yet reached"

begins to send

τ

"signal not yet reached"

begins to send

τ

sender(S1)

⇒ Worst case:

① S1 issues a signal before it reaches Sn.

② Then, Sn issues another signal. S1 collides with Sn at time τ.

③ The collision is passed back to S1 after another τ.

Thus, it needs 2τ to "make sure" if or not a collision occurs.

(ex) On a 1Km long coaxial cable, τ= 5 μsec.

4. CSMA/CD

- Idea:

ALOHA/Slotted ALOHA: Stations always send the frame whenever they are ready.

CSMA: Carrier sense - No station begin to transmit when it senses the medium busy.

CSMA/CD: Collision detection 기능 추가- Stations 'abort' their transmission "as soon as" they detect a collision.

⇒ "Quickly terminating" damaged frames saves the time and bandwidth.

⇒ CSMA/CD에서는 collision이 ‘발생하자마자 탐지’하여 transmission을 ‘중지’함.

- Collision detection:

․ The station's H/W must "listen" to the cable (수신기) while it is "transmitting" (송신기).

․ If what it "reads back" is different from what it is "putting out", it knows a collision is occurring.

① No collision: 보낸 signal = original signal

받은 signal = original signal

② Collision: 보낸 signal = original signal

받은 signal = original signal + other signal

송신기

수신기

송신기

수신기

ready

- Method:

① If the medium is idle, transmit; otherwise, go to step ②.

② If the medium is busy, continue to listen until the medium is idle, then transmit immediately.

⇒ 1-persistent

③ If a collision is detected during transmission (max. 2τ만큼 기다림 - 충돌탐지 시간), transmit a brief "jamming" signal.

⇒ To assure that ‘all’ stations know that there has been a collision and then cease transmission.

④ After transmitting the jamming signal, wait a "random" amount of time, then attempt to transmit again (repeat from step ①).

(ex) (Stallings 10th ed.) p.378 Fig. 12.3

(Stallings 7th ed.) p.599 Fig. 16.2

t0: Station A begins transmitting a packet addressed to D.

t1: Both B and C are ready to transmit.

⇒ B ‘senses’ a transmission and so defers.

C, however, is still unaware of A's transmission and begins its own transmission.

t2: When A's transmission reaches C, C detects the collision and ceases transmission.

t3: The effect of the collision propagates back to A, A detects the collision and ceases transmission.

t4:  A and C wait a "random" amount of time, then attempt to transmit again.

- Characteristics

․ Simple & efficient

․ Most popular when τ<< m (frame transmission time)

Why? τ가 크면 충돌탐지 시간(2τ)이 커짐

⇒ 충돌탐지 시간이 실제 frame전송 시간보다 상당히 작아야 효율적.

․ The key: ‘Immediate’ detection of collision: a (= τ/ m) << 1

⇒ If a >> 1 (i.e., τ>> m), it has a similar behavior as the pure ALOHA

․ May content for the bus "heavily" when heavily loaded.

⇒ 즉, station이 많거나 보낼 frame이 많으면 충돌이 많이 발생함.

⇒ bridge로 LAN을 나눔.

- Performance analysis

․ CSMA/CD consist of alternating "contention" and "transmission" period with "idle" period occurring when all stations are quiet.

․ What is the avg. cycle time limi→∽|Ci| = ?	( ∵ U = m / |Ci| )

2τ

2τ

2τ

2τ

2τ

τ

τ

m

m

contention period

trans. period

trans. period

contention period

frame

frame

Ci

Ci+1

, where 2τ: one contention slot

m  : frame transmission time

τ  : complete current transmission

|Ci| = (m + τ) + 2τ․J	, where J: the 'avg.' no. of contentions

= m + τ(1 + 2J)	(dependent on no. of stations, n)

= m․{1 + a (1+2J)}	, where a = τ/m

U	= m / m․{1 + a (1+2J)} , where U: utilization

(= 실제 frame 전송시간/frame 전송하는데 걸린 시간)

How to get J?

Given that each contention period has a prob. of v to succeed,

prob. of 1 contention: v

frame

frame

prob. of 2 contention: (1-v)․v

frame

prob. of 3 contention: (1-v)2․v

…	…

∽

avg. no of contention  J = ∑i=0 i․(1-v)i-1․v

= v․[ 1 / {1-(1-v)}2 ] = 1/v

What is v?

the prob. of success

⇒ v is the prob. that exactly "one" station wants to transmit.

v = nC1․(1-p)n-1․p

= n․(1-p)n-1․p

, where we have n stations,

each has a prob. of transmitting p, not transmitting (1-p)

when p = 1/n, v is maximized.

n=4의 경우

1/4    1

v

p

Why? dv/dp = 0 이면 max. or min.

dv/dp = n(n-1)(1-p)n-2p(-1) + n(1-p)n-1

= n(1-p)n-2{-p(n-1) + (1-p)}

= n(1-p)n-2{1 - np}

∴ p=1/n or p=1

즉, n 개의 station이 같은 확률로 보내려할 때 v는 최대가 됨.

Thus,  v = n․(1 - 1/n)n-1․1/n

= (1 - 1/n)n-1

[ limn→∽ (1 - 1/n)n-1 = e-1

∴ vmax = e-1 ; 한 frame을 보내려할 때 성공할 확률의 최대값

(= 0.368)  ]

Thus,  J =	1 / (1 - 1/n)n-1

[ Jmin = e when n→∽ ; 평균 충돌횟수는 적어도 e(=2.718)번 발생 ]

∴ |Ci| = m․{1 + a (1+2e)} ; avg. cycle (service) time of CSMA/CD

∴  U = m / m․{1 + a (1+2e)}

= 1 / (1 + 6.44a)	; utilization of CSMA/CD

⇒ The key:  a (= τ/ m) << 1

⇒ 충돌탐지 시간이 실제 frame 전송시간보다 상당히 작아야 "효율적"임.

(Stallings 10th ed.) p.379 부록 K

(Stallings 7th ed.) p.634 Fig. 16.15, c.f. U=1 / (1+a)

• IEEE Standard 802.3 and Ethernet

- Protocol: 1-persistent CSMA/CD

- History

․ In 1976, Xerox built a 2.94Mbps CSMA/CD LAN to connect over 100 personal workstations on a 1Km cable.

․ Xerox, DEC and Intel drew up a standard for a 10Mbps Ethernet.

⇒ a basis for IEEE 802.3

(Stallings 10th ed.) p.381 Tab. 12.1

(Stallings 7th ed.) p.603 Tab. 16.2

- Structure

․ 10Base5: transceiver, transceiver cable & controller (LAN card)

①Transceiver (송수신기, transmitter + receiver)

□Its ‘tap’ makes contact with the inner core.

⇒ Bus와의 연결부분.

□contains the electronics that handle "carrier detection" and "collision detection".

②Transceiver cable

□up to 50m long.

□contains 5 individually shielded twisted pairs.

⇒ data in, data out, control in, control out, powering the transceiver, respectively

③Controller (=LAN card)

□transmit frames to and receives frames from the transceiver.

□responsible for

- assembling the data into the proper format (header & tail)

- computing checksum on outgoing frames and verifying them on incoming frames

- a queue of buffers to be transmitted

- DMA transfers with the host computers

- other aspects of network management

․ 10Base2: connector, transceiver + controller

․ 10BaseT: hub, twisted pair, controller

⇒ most popular due to the ease of "maintenance"

․ 100Mbps Fast Ethernet is developed.

(ex) 100Base-Tx, Fx, T4 (1993)

100Base-VG (1995)

(Stallings 10th ed.) p.387 Fig. 12.6, p.382 Tab. 12.2

(Stallings 7th ed.) p.604 Fig. 16.4, p.604 Tab. 16.3

⇒ switch를 사용: no collision

(Stallings 10th ed.) p.384

․ 1Gbps/10Gbps Gigabit Ethernet is developed.

(Stallings 10th ed.) p.385 Fig.12.5, p.388 Fig.12.7, p.389 Fig.12.8

(Stallings 7th ed.) p.607 Fig.16.5

• IEEE Standard 802.11: CSMA/CA for Wireless LAN MAC

- Carrier sense multiple access with collision avoidance (CSMA/CA) in computer networking, is a network multiple access method in which carrier sensing is used, but nodes attempt to avoid collisions by transmitting only when the channel is sensed to be 'idle'.

- It is particularly important for wireless networks, where the collision detection of the alternative CSMA/CD is unreliable due to the hidden node problem.

- the hidden node problem

▸carrier sense가 가능하지 않는 서로 다른 두 node가 존재

e.g. ALOHA, slotted ALOHA

STA1

STA2

AP

STA3

▸무선 단말 STA1과 STA3, STA2와 STA3는 무선 신호가 도달하지 않고, 채널의 사용 상황을 서로 알 수 없음.

⇒ STA1/STA2가 AP에 송신하고 있는 것과는 관계없이 STA3도 송신을 하고, 따라서 AP에서는 프레임의 충돌이 발생.

- RTS(Request to Send)/CTS(Clear to Send)

RTS frame	(단위: byte)

2	2	6	6	4
프레임 control	duration	수신기 address	송신기 address	FCS

CTS frame	(단위: byte)

2	2	6	4
프레임 control	duration	수신기 address	FCS

duration: 무선 채널을 사용하는 예정 시간

- Collision Avoidance Algorithm (from http://en.wikipedia.org/)

- Four Frame Exchange

▸ Basic data transfer involves exchange of two frames, i.e. RTS/CTS

▸ To further enhance reliability, four-frame exchange may be used

① Source (STA) issues a Request to Send (RTS) frame to destination (AP)

② Destination (AP) responds with Clear to Send (CTS)

③ After receiving CTS, source (STA) transmits data

④ Destination (AP) responds with ACK

STA1

STA2

AP

STA3

①RTS받은후 duration시간동안 wait

①RTS

②CTS

②CTS

②CTS받은후 duration시간동안 wait

③frame송신

④ACK

④ACK

④ACK

▸ RTS alerts all stations within range of source that exchange is under way

▸ CTS alerts all stations within range of destination

▸ Stations refrain from transmission to avoid collision

▸ RTS/CTS exchange is required function of MAC but may be disabled