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

강의내용 - Stalling책

• Chap. 11. 근거리 통신망(LAN) 개요

Chap. 12. 이더넷(Ethernet)

Chap. 13. 무선 LAN

• 강의 내용

- LAN의 구조(architecture): 여러 형태의 매체(medium)

LAN의 제어(protocol): 분산 방식

Topics

• LAN(Local Area Network)

- Def.:	근거리 통신망

(Stallings 10th ed.) p.342 학습목표, p.365 fig.11.12

(Stallings 7th ed.) p.555 fig.15.1

- 구조: Bus/Star

(Stallings 10th ed.) p.344 fig.11.1, p.345 fig.11.2

(Stallings 7th ed.) p.558 fig.15.2

- Protocols: 두 계층의 protocol이 필요

① LLC(Logical Link Control) protocols

② MAC(Medium Access Control) protocols

⇒ (Stallings 10th ed.) p.346 fig.11.3, p.347 fig.11.4

(Stallings 7th ed.) p.564 fig.15.5, p.565 fig.15.6

• Medium Access: LAN에서는 computer들이 전달매체(medium)을 '공유'.

- 'Frame' Transmission

⇔ 'Packet': Network Layer에서 사용 - Routing의 단위

① Bus:  (Stallings 10th ed.) p.344 Fig.11.1

(Stallings 7th ed.) p.559 Fig.15.3

② Star:	(Stallings 10th ed.) p.345 Fig.11.2

(Stallings 7th ed.) p.561 Fig.15.4

- Frame 구조

(Stallings 10th ed.) p.350 Fig.11.5

(Stallings 7th ed.) p.568 Fig.15.7

• Medium Access Control (MAC) protocol:

- LAN에서 computer들이 '공유'하고  있는 전달매체를 어떻게 사용할 것인가?

- 제어 종류: 분산방식 (not 중앙집중식)

① 라운드로빈(round-robin)

② 예약(reservation)

③ 경쟁(contention)

(Stallings 10th ed.) p.351-p352

(Stallings 7th ed.) p.570-p571

(ex) 네거리에서 차량들이 충돌하지 않도록 어떻게 통행시킬 것인가?

⇒ 중앙집중식/분산방식의 장․단점?

LAN Architectures

• Bus/Star/Wireless LAN

1. Bus (버스 LAN)

- 주로 Coaxial cable (동축케이블) 사용.

① Baseband: 'Bi'-Directional, Digital signal 전송.

(Stallings 10th ed.) p.378 fig.12.3, p.381 Tab.12.1 (Wiki: Ethernet)

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

② Broadband: 'Uni'-Directional, Analog signal 전송, 거의 사용되지 않음.

- Optical fiber (광섬유): 'Uni'-Directional

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

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

2. Star (성(星)형 LAN)

- Hub: repeater로서 동작.

⇒ 하나의 station이 송신하면 hub는 그 신호를 각 station으로의 출력선으로 재생하여 송신함.

⇒ 물리적으로 star일지라도 논리적으로는 bus임.

- Hub (and Twisted Pair): 전체 전송량 공유

(Stallings 10th ed.) p.362 Fig.11.10	(Stallings 7th ed.) p.582 Fig.15.12

- Switch: 각 line당 ‘독립적인’ 전송량 제공.

(Stallings 10th ed.) p.363 Fig.11.11, p.365 Fig.11.12

(Stallings 7th ed.) p.583 Fig.15.13, p.586 Fig.15.14

→ 방식: store-and-forward/cut-through

c.f., 브리지: p.363

3. Wireless (무선 LAN)

- 구조:

① 단일 셀 구조

(Stallings 10th ed.) p.409 Fig.13.1

(Stallings 7th ed.) p.644 Fig.17.1

② 다중 셀 구조

(Stallings 10th ed.) p.410 Fig.13.2

(Stallings 7th ed.) p.645 Fig.17.2

- Ad hoc Network: 필요한 작업을 하기 위하여 일시적으로 사용자끼리만 연결된 네트워크.

(Stallings 10th ed.) p.411 Fig.13.3	(Stallings 7th ed.) p.646 Fig.17.3

- 무선 LAN 표준: IEEE 802.11

(Stallings 10th ed.) p.412 Tab.13.1, p.424 Tab.13.4

• 브리지(bridge):

- 기능: LAN의 분할 및 연결

⇒ 신뢰성/성능/보안/배치

(Stallings 10th ed.) p.353	(Stallings 7th ed.) p.572-p.573

⇒ 동일한 물리 계층과 링크계층의 protocol을 사용하는 ‘같은 종류’의 LAN들을 연결.

- 기능: 'store-and-forward' packets

① LAN A에서 전송되는 모든 frame을 읽는다. LAN B에 있는 station에 주소가 지정된 경우에 frame을 ‘저장’한다.

② LAN B를 위한 MAC protocol을 사용하여 LAN B로 frame을 ‘재전송’한다.

③ LAN B에서 LAN A로의 traffic인 경우에도 같은 방법으로 수행된다.

(Stallings 10th ed.) p.354 Fig.11.6, p.355 Fig.11.7

(Stallings 7th ed.) p.573 Fig.15.8, p.575 Fig.15.9

- 경로배정 문제: bridge가 frame을 받았을 때, ‘어느 LAN으로 frame을 전달해야 할 것인가’를 결정해야 함.

① 고정 경로배정(fixed routing): Hop 수가 ’최소’인 경로가 선택되도록 bridge table을 작성.

(Stallings 10th ed.) p.357 Fig.11.8	(Stallings 7th ed.) p.576 Fig.15.10

⇒ Central routing directory를 작성한 다음, 각 bridge table들을 작성.

⇒ 비교적 작은 네트워크나 변하지 않는 네트워크에 적합.

(Stallings 10th ed.) p.357 예제 11.4

② 스패닝트리(spanning tree) 경로배정: 동적 기법

□bridge가 자동으로 경로배정표를 발전시키고, 네트워크의 변화에 따라 표를 바꾸는 기법.

□최소비용 스패닝트리(minimum spanning tree) algorithm 이용.

□3단계로 구성: 프레임 전달(forwarding)/주소학습/루프(loop) 해결

Contention Protocols

(Stallings 10th ed.) p.373-375, 학습목표, ALOHA/슬롯 ALOHA

(Wiki: ALOHAnet)

(Stallings 6th ed.) p.543-544 ALOHA, 슬롯 ALOHA

1. (Pure) ALOHA

- '70: N. Abramson and his collegues at the U. of Hawaii devised a new method to solve the "Channel" access problem.

- Idea: Doing-nothing protocol → without any access control.

- Method

․ Let users transmit whenever they have a frame to be sent.

․ If the frame was "destroyed", the sender just wants a "random" amount of time and sent it again.

⇒ Due to the "feedback" property of broadcasting, the sender can always find out whether or not its frame was destroyed by "listening" to the channel.

⇒ No polling from host. (즉, teminal의 전송순서를 정하지 않음.)

- Performance analysis

․ safe interval: 2τ

⇒ If there are "two" frames during [t, t+2τ], there is a "collision".

⇒ 즉, 2τ시간 내에 오직 하나의 frame만 보내야 함.

τ

t

t+τ

t+2τ

t+3τ

collision occurs

- Given input rate, λ(= G frames/τtime units = G/τ), we have to get the

G: new arrivals + retried one

prob. that no frame is in the channel for the time interval 2τ.

⇒ P0(2τ) = e-2G : 2τ시간동안 frame이 없을 확률

⇒ 2τ시간동안 channel이 비어있을 확률

⇒ 즉, 1 frame을 보내려고 할 때, 성공할 확률

Poisson distribution: t시간동안 n개가 도착할 확률

Pn(t) = (λt)n/n!․e-λt

(ex) 2τ시간동안 n개의 frame이 도착할 확률

Pn(2τ) = (G/τ․2τ)n/n!․e-G/τ․2τ

= (2G)n/n!․e-2G

S(throughput) = G․e-2G : G개의 frame을 보내려고 할 때 성공하는 frame수

( load * the prob. of a transmission being successful)

G=0.5일 때, S = (0.5)․e-2(0.5) = (1/2)․e-1 = 0.184

⇒ 즉, 2τ에 1개를 보낼 때 최대 (Wiki: ALOHAnet)

2. Slotted ALOHA

- '72: Roberts published a method for "doubling" the capacity of ALOHA.

- Idea: "discrete" time interval - put some "control"

(pure ALOHA: continuous time - NO control at all)

- Method:

․ Divide time up into "discrete" intervals, each interval corresponding to one frame.

․ Packets can be sent only in this time interval.

τ

t

t+τ

t+2τ

One special station (host) emit a "pip" (시작신호)

at the start of each interval

- Performance analysis

․ safe interval: τ

⇒ τ시간 내에 오직 하나의 frame만 보내야 함.

․ 1 frame을 보내려고 할 때, 성공할 확률

⇒ τ시간동안 channel이 비어있을 확률

P0(τ) = (G/τ․τ)0/0!․e-G/τ․τ

= e-G

S(throughput) = G․e-G : G개의 frame을 보내려고 할 때 성공하는 frame수

- System performance

․ The best we can hope for using slotted ALOHA is

when λ(=G/τ) = 1/τ, (즉, τ시간에 1개를 보낼 때 최대)

S = 1․e-1 = 0.368 ; 36.8% of tramsmission

P0(τ) = e-G= 0.368 ; 36.8% of the slot empty

0.264 ; 26.4%(나머지) of collision

․ Operating at "higher" values of G?

⇒ Reduces the no. of empties, but increases the no. of collisions "exponentially".

⇒ Why? 평균 충돌횟수 ∝ eG ; G에 관한 “지수”함수

․ Given a G, what is the avg. no. of "attempts" for a frame to be transmitted?	no. of attempts

1st try	& success:  P1 = P0(τ) = e-G

1st collision & success:  P2 = (1- P0(τ))․P0(τ) = (1-e-G)․e-G

2nd collision & success:  P3 = (1- P0(τ))2․P0(τ) = (1-e-G)2․e-G

…	…	…	…

(k-1)th collision & success:  Pk = (1- P0(τ))k-1․P0(τ) = (1-e-G)k-1․e-G

∽

평균 시도횟수, E(no. of attempts) = ∑k=1 k․Pk

∽

= ∑k=1 k․(1-e-G)k-1․e-G

∽

= e-G․∑k=1 k․(1-e-G)k-1

= e-G․1 /[1- (1-e-G)]2

∽

(∵ ∑i=1 i․xi-1 = 1 /(1 - x)2 )

= e-G․1 /e-2G

∽

= eG  (G에 관한 “지수”함수)

∽

[Appendix: 부록]

∙ Poisson distribution

- Poisson process: a counting process - "pure birth"

⇒ Mathematical modeling of the no. of the jobs/customers arrived in the system at time t.

⇒ 도착률 λ로 계속 job이 도착하는 상태의 수학적 모델

⇒ 즉, 도착률 λ로 계속 job이 도착할 때, t시간동안 n개의 job이 도착할 확률의 분포

⇒ What is the prob. that the system has n customers at any time instant t?

Pn(t) = (λt)n/n!․e-λt

(ex) 은행에서 도착률 λ(= G customers/τmin.)로 계속 고객이 도착할 때,  t시간 후에 n명의 고객이 은행에 있을 확률의 분포

λ

n

Pn(t) = (λt)n/n!․e-λt : discrete distribution

(not contiunous such as normal distribution)

no. of customers

p

0	1	2	3	…	n	…

(ex) Fire Insurance Co. (화재보험 회사)

- policy holders (총 가입자 수): m = 1860

- Any one of the policy holders will file at least one claim in any given year (1년 동안 어느 한 가입자가 보험 청구를 할 확률):

p = 1/600

⇒ 도착률 (λt, 1년간의 평균 claim수) = m․p

= 1860 × 1/600 = 3.1

⇒ 1년간 n개의 claim이 발생할 확률의 분포

Pn(a year) = (λt)n/n!․e-λt

= (mp)n/n!․e-mp

P0(a year) = (3.1)0/0!․e-3.1 = 0.045 : prob. of 0 claim/year

P1(a year) = (3.1)1/1!․e-3.1 = 0.140 : prob. of 1 claim/year

P2(a year) = (3.1)2/2!․e-3.1 = 0.216 : prob. of 2 claims/year

P3(a year) = (3.1)3/3!․e-3.1 = 0.223 : prob. of 3 claims/year max.

P4(a year) = (3.1)4/4!․e-3.1 = 0.173 : prob. of 4 claims/year

…	……

Poisson distribution with mp = 3.1

0.25

no. of claims

p

0	1	2	3	4	…

- Characterize the behavior of interarrival time intervals.

① memoryless property: special case of Markov process.

⇒ Any future arrival is independent of the "current" and "past" states.

(Markov process: A stochastic process {Xt} - 시간(t)에 따른 어떤 양 X의 변화를 "추정" - is said to have the Markovian property, if P{Xt+1=j| X0=k0, X1=k1, …, Xt-1=kt-1, Xt=i} = P{Xt+1=j| Xt=i}

⇒ The conditional prob. of any future event, given any past event and the present state Xt=i, is independent of the past event and depends upon "only the present" state of the proces.)

⇒ 다음 단계의 상태는 현재 단계의 상태에만 의존하는 시스템 모델 - 즉, 전 단계의 상태들은 고려하지 않음.

(ex)

n+1

n

P{Xt+1=n+1| Xt=n}

앞 단계로 넘어가는 transition

prob.가 현재 단계에만 의존

② From the memoryless property, the prob. of "one" arrival during Δt is equal to λ․Δt (λ: 비례상수 - 도착률)

(즉, Δt시간 동안 하나의 도착이 일어날 확률은 전 단계는 고려할 필요없이 Δt에만 비례함.)

Thus,	Pn(t+Δt) = λΔt․Pn-1(t) + (1 - λΔt)․Pn(t)

( t+Δt 시간에 n명이 있을 확률

= t 시간에 n-1명이 있을 확률 * Δt시간 동안 1명이 도착할 확률 +

t 시간에 n명이 있을 확률 * Δt시간 동안 1명도 도착하지 않을 확률)

Pn(t+Δt) - Pn(t) = λΔt․Pn-1(t) - λΔt․Pn(t)

(Pn(t+Δt) - Pn(t))/Δt = λ․Pn-1(t) - λ․Pn(t)

양변에 limΔt→0를 취하여 미분방정식을 만들면,

limΔt→0 (Pn(t+Δt)-Pn(t))/Δt = limΔt→0 (λ․Pn-1(t) - λ․Pn(t))

Pn‘(t) = λ․Pn-1(t) - λ․Pn(t)	-  (1)

By solving (1),

P0‘(t) = - λP0(t)  ⇒  P0(t) = e-λt

(어떤 함수를 미분하면 같은 함수가 생성 → solved by substitution)

P1‘(t) = λe-λt - λP1(t)  ⇒  P1(t) = λt․e-λt

…	……	……

⇒  Pn(t) = (λt)n/n!․e-λt

Poisson Distribution with λand t

∽

E(no. of customers at t) = ∑n=0 n․Pn(t)

(ex) Fire Insurance Co. (화재보험 회사)

Expected no. of claims/year = 0․P0(a year) + 1․P1(a year) + … +

n․Pn(a year) + …

= 0․(0.045) + 1․(0.140) + 2․(0.216) +

3․(0.223) + …

∙ M/M/1 Queuing system

- Birth-and-death process

⇒ job이 도착하고 처리되는 상태의 수학적 모델

λ:도착률

μ:처리율

no. of customers in the queue?

- M/M/1 queue

λand μ: follows exponential distribution

no. of the queue: 1

- Characterize λ and μ

Within Δt, the prob. of simultaneous "arrival" = 0

⇒ No two arrival occurs whithin Δt.

Within Δt, the prob. of simultaneous "departure" = 0

⇒ No two departure occurs whithin Δt.

- Derivation of Pn(t)

Pn(t+Δt) = [1 - (λ+μ)Δt]․Pn(t) + λΔt․Pn-1(t) + μΔt․Pn+1(t)

( t+Δt 시간에 n명이 있을 확률

= t 시간에 n명이 있을 확률 * Δt시간 동안 그대로 있을 확률 +

t 시간에 n-1명이 있을 확률 * Δt시간 동안 1명이 도착할 확률 +

t 시간에 n+1명이 있을 확률 * Δt시간 동안 1명이 출발할 확률)

양변에 limΔt→0를 취하여 미분방정식을 만들면,

limΔt→0 (Pn(t+Δt)-Pn(t))/Δt = limΔt→0 (λPn-1(t) + μPn+1(t) - (λ+μ)Pn(t))	Pn‘(t) = λ․Pn-1(t) + μPn+1(t) - (λ+μ)․Pn(t)

We put Pn‘(t) = 0 ; steady state - 안정상태

(Pn‘(t)는 증가율 ⇒ if Pn‘(t) > 0, the queue will be always growing.)

λ․Pn-1(t) + μPn+1(t) - (λ+μ)․Pn(t) = 0

λ․Pn-1(t) + μPn+1(t) = (λ+μ)․Pn(t)

λ․Pn-1(t) + μPn+1(t) = λ․Pn(t) + μ․Pn(t) : inflow = outflow

①	②	③	④

n-1

n

n+1

λ

λ

μ

μ

①

③

②

④

inflow = outflow이므로 λ․Pn(t) = μ․Pn+1(t)

n-1

n

n+1

λ

λ

μ

μ

①

②

λ․Pn(t) = μ․Pn+1(t)  - (1) ; inflow = outflow (steady state)

∽

∑n=0 Pn(t) = 1	- (2) ; probability distribution

From (1),  Pn+1(t)	= λ/ μ․Pn(t)

= ρPn(t)

From (2), P0(t) + ρP0(t) + ρ2P0(t) + … … = 1

( 1 + ρ + ρ2 + … … ) P0(t) = 1

[1 / (1-ρ)] P0(t) = 1     (	ρ< 1)

P0(t) = 1 - ρ

Thus,  P1(t) = ρP0(t) = ρ(1 - ρ)

P2(t) = ρ2P0(t) = ρ2(1 - ρ)

…	…	…

Pn(t) = ρnP0(t) = ρn(1 - ρ)

∽

E(no. of customers at t) = ∑n=0 n․Pn(t)

= 0․(1 - ρ) + 1․ρ(1 - ρ) + 2․ρ2(1 - ρ) + …

∽

= (1 - ρ)․∑i=0 i․ρi

= (1 - ρ)․[ρ/(1 - ρ)2]

= ρ/(1 - ρ)

- 무한수열의 합

∽

∑i=1 i․xi-1 = 1 /(1 - x)2

Why?	1 + x + x2 + … + xn + … = 1 /(x - 1),      -1 < x < 1

d/dx (1 + x + x2 + … + xn + … ) = d/dx ((x - 1)-1)

1 + 2x + 3x2 + … + (n-1)xn + …  = -1․(1 - x)-2․d/dx (1 - x)

= 1/(1 - x)2

∽

∑i=0 i․xi	= x /(1 - x)2

Why?	윗 식의 양변에 x를 곱하면,

x․(1 + 2x + 3x2 + … + (n-1)xn + … )  = x․( 1/(1 - x)2 )

x + 2x2 + 3x3 + … + nxn + … = x /(1 - x)2