Multiple Access Protocols - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 네트워크(\|[^\]]+)?\]\] +분류:컴퓨터 네트워킹\1)

2026-01-15T13:00:19Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 네트워크(\|[^\]]+)?\]\] +분류:컴퓨터 네트워킹\1)

← 이전 판		2026년 1월 15일 (목) 13:00 판
108번째 줄:		108번째 줄:

	==각주==		==각주==
	[[분류:컴퓨터 ~~네트워크~~]]		[[분류:컴퓨터 네트워킹]]

2025년 6월 17일 (화) 22:34에 Pinkgo님의 편집

2025-06-17T22:34:31Z

← 이전 판		2025년 6월 17일 (화) 22:34 판
2번째 줄:		2번째 줄:

	==개요==		==개요==
	네트워크 링크는 point-to-point 링크와 브로드캐스트(broadcast) 링크로 구분된다. Point-to-point 링크는 링크의 양쪽 끝에 각각 하나의 노드가 존재하는 구성이다. 많은 PPP(Point-to-Point Protocol)와 HDLC(High-Level Data Link Control)와 같은 여러 link layer의 프로토콜이 이 point-to-point 링크를 기준으로 설계되어 있다. 브로드캐스트 링크는 다수의 노드들이 하나의 공유 브로드캐스트 채널에 연결될 수 있는 링크이다. 이때 "브로드캐스트"는 하나의 노드가 프레임을 전송하면 채널이 그 프레임을 모든 노드에게 방송(broadcast)하여, 다른 모든 노드들이 그 복사본을 수신하게 됨을 의미한다. 이때 이더넷(Ethernet)과 무선 LAN(wireless LAN)과 같이 여러 기술들이 브로드캐스트 링크를 위해서 설계되어 있다.		네트워크 링크는 point-to-point 링크와 브로드캐스트(broadcast) 링크로 구분된다. Point-to-point 링크는 링크의 양쪽 끝에 각각 하나의 노드가 존재하는 구성이다. 많은 PPP(Point-to-Point Protocol)와 HDLC(High-Level Data Link Control)와 같은 여러 link layer의 프로토콜이 이 point-to-point 링크를 기준으로 설계되어 있다. 브로드캐스트 링크는 다수의 노드들이 하나의 공유 브로드캐스트 채널에 연결될 수 있는 링크이다. 이때 "'''브로드캐스트'''"는 하나의 노드가 프레임을 전송하면 채널이 그 프레임을 모든 노드에게 방송(broadcast)하여, 다른 모든 노드들이 그 복사본을 수신하게 됨을 의미한다. 이때 이더넷(Ethernet)과 무선 LAN(wireless LAN)과 같이 여러 기술들이 브로드캐스트 링크를 위해서 설계되어 있다.

	==Multiple access problem==		==Multiple access problem==
	브로드캐스트 링크에서 가장 중요한 문제 중 하나는, 여러 노드가 공유되는 브로드캐스트 채널은 어떻게 함께 사용할지에 대해 조율하는 문제, 즉, 다중 접근 문제(multiple access problem)이다. 모든 노드가 프레임을 전송할 수 있기 때문에, 두 개 이상의 노드가 동시에 하나의 브로드캐스트 채널을 통해 프레임을 전송할 수 있다. 이런 경우, 모든 노드들은 동시에 여러 프레임을 수신하게 되고, 전송된 프레임들이 충돌(collision)하게 된다. 일반적으로는 충돌이 발생하면 해당 프레임을 수신한 노드는 어떤 프레임도 제대로 해석할 수 없게 된다. 이렇게 되면 충돌에 관련된 모든 프레임은 무의미해지고, 충돌이 발생한 동안 브로드캐스트 채널은 낭비된다. 따라서 여러 노드들이 동시에 활성화되어 있을 때, 브로드캐스트 채널에 대한 이들의 전송을 조율하는 방법이 필요하며, 이는 다중 접근 프로토콜(multiple access protocol)을 통해서 ~~구현된다~~. 이상적인 다중 접근 프로토콜은 다음과 같은 특징을 만족해야 한다:		브로드캐스트 링크에서 가장 중요한 문제 중 하나는, '''여러 노드가 공유되는 브로드캐스트 채널은 어떻게 함께 사용할지에 대해 조율하는 문제''', 즉, '''다중 접근 문제(multiple access problem)'''이다. 모든 노드가 프레임을 전송할 수 있기 때문에, 두 개 이상의 노드가 동시에 하나의 브로드캐스트 채널을 통해 프레임을 전송할 수 있다. 이런 경우, '''모든 노드들은 동시에 여러 프레임을 수신하게 되고, 전송된 프레임들이 충돌(collision)'''하게 된다. 일반적으로는 충돌이 발생하면 해당 프레임을 수신한 노드는 어떤 프레임도 제대로 해석할 수 없게 된다. 이렇게 되면 충돌에 관련된 모든 프레임은 무의미해지고, 충돌이 발생한 동안 브로드캐스트 채널은 낭비된다. 따라서 여러 노드들이 동시에 활성화되어 있을 때, '''브로드캐스트 채널에 대한 이들의 전송을 조율하는 방법이 필요하며, 이는 다중 접근 프로토콜(multiple access protocol)을 통해서 구현'''된다. 이상적인 다중 접근 프로토콜은 다음과 같은 특징을 만족해야 한다:
	# 오직 하나의 노드만 데이터 전송이 필요할 경우, 그 노드는 채널의 최대 성능인 R bps의 처리량을 얻는다.		# 오직 하나의 노드만 데이터 전송이 필요할 경우, 그 노드는 채널의 최대 성능인 R bps의 처리량을 얻는다.
	# M개의 노드가 데이터 전송을 원할 경우, 각각의 노드는 채널의 대역폭을 공평하게 공유하여 평균적으로 R/M bps의 처리량을 갖는다.		# M개의 노드가 데이터 전송을 원할 경우, 각각의 노드는 채널의 대역폭을 공평하게 공유하여 평균적으로 R/M bps의 처리량을 갖는다.
61번째 줄:		61번째 줄:
	나머지 N-1 개의 노드가 전송하지 않을 확률: (1-p)<sup>N-1</sup>		나머지 N-1 개의 노드가 전송하지 않을 확률: (1-p)<sup>N-1</sup>
	특정 노드의 송신이 성공할 확률: p * (1-p)<sup>N-1</sup>		특정 노드의 송신이 성공할 확률: p * (1-p)<sup>N-1</sup>
	N개의 노드 중 어느 하나가 성공할 전체 확률: N * p * (1-p)<sup>N-1</sup>		'''N개의 노드 중 어느 하나가 성공할 전체 확률: N * p * (1-p)<sup>N-1</sup>'''
	즉, sloted ALOHA의 최대 효율은 <code>N * p * (1-p)<sup>N-1</sup></code>이다. 이를 최대화하기 위해서는 p에 대해 최적화해야 한다. 또한 활성 노드의 수 N이 매우 클 때의 효율을 구하기 위해서는 <code>N <math>\to \infty</math></code>일 때의 <code>N * p * (1-p)<sup>N-1</sup></code> 극한을 구해야 한다. 이를 계산하면, sloted I/O의 최대 효율은 아래와 같다:		즉, '''sloted ALOHA의 최대 효율은 <code>N * p * (1-p)<sup>N-1</sup></code>'''이다. 이를 최대화하기 위해서는 p에 대해 최적화해야 한다. 또한 활성 노드의 수 N이 매우 클 때의 효율을 구하기 위해서는 <code>N <math>\to \infty</math></code>일 때의 <code>N * p * (1-p)<sup>N-1</sup></code> 극한을 구해야 한다. 이를 계산하면, sloted I/O의 최대 효율은 아래와 같다:
	1/e ≈ 0.37		'''1/e ≈ 0.37'''
	즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.		즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.

87번째 줄:		87번째 줄:
	* 오직 하나의 노드만 활성 상태일 때, 그 노드는 채널의 대역폭인 R bps를 모두 사용할 수 있어야 한다.		* 오직 하나의 노드만 활성 상태일 때, 그 노드는 채널의 대역폭인 R bps를 모두 사용할 수 있어야 한다.
	* M개의 노드가 활성 상태일 경우, 각 활성 노드는 거의 R/M bps의 처리량을 가져야 한다.		* M개의 노드가 활성 상태일 경우, 각 활성 노드는 거의 R/M bps의 처리량을 가져야 한다.
	ALOHA와 CSMA 프로토콜은 첫 번째 속성은 만족하지만, 두 번째 속성은 만족하지 못한다. Taking-turns 프로토콜은 ALOHA와 CSMA의 이러한 특성을 극복하기 위해서 구현되었다. Taking-turns 프로토콜들 중, 가장 대표적인 프로토콜 두가지는 polling 프로토콜과 Token-Passing 프로토콜이다.		'''ALOHA와 CSMA 프로토콜은 첫 번째 속성은 만족하지만, 두 번째 속성은 만족하지 못한다.''' Taking-turns 프로토콜은 ALOHA와 CSMA의 이러한 특성을 극복하기 위해서 구현되었다. Taking-turns 프로토콜들 중, 가장 대표적인 프로토콜 두가지는 polling 프로토콜과 Token-Passing 프로토콜이다.

	===Polling Protocol===		===Polling Protocol===

Pinkgo: /* Pure ALOHA */

2025-05-29T06:28:43Z

Pure ALOHA

← 이전 판		2025년 5월 29일 (목) 06:28 판
73번째 줄:		73번째 줄:
	[[파일:Collision probability increases in pure ALOHA.png\|섬네일\|Figure 4. Collision probability increases in pure ALOHA]]		[[파일:Collision probability increases in pure ALOHA.png\|섬네일\|Figure 4. Collision probability increases in pure ALOHA]]
	# 다른 어떤 노드도 [t<sub>0</sub> – 1, t<sub>0</sub>] 구간에서 전송을 시작하면 안 된다.		# 다른 어떤 노드도 [t<sub>0</sub> – 1, t<sub>0</sub>] 구간에서 전송을 시작하면 안 된다.
	#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<~~sub~~>(N – 1)</~~sub~~> 이다.		#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<sup>(N – 1)</sup> 이다.
	# [t<sub>0</sub>, t<sub>0</sub> + 1] 구간에도 다른 노드가 전송을 시작하면 안 된다.		# [t<sub>0</sub>, t<sub>0</sub> + 1] 구간에도 다른 노드가 전송을 시작하면 안 된다.
	#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<~~sub~~>(N – 1)</~~sub~~> 이다.		#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<sup>(N – 1)</sup> 이다.
	따라서 특정 노드가 성공적으로 전송할 확률은 <code>p * (1 – p)<~~sub~~>2(N – 1)</~~sub~~></code>이다. 슬롯 ALOHA와 마찬가지로 극한을 취하는 방식으로 분석을 진행하면, 순수 ALOHA 프로토콜의 최대 효율은:		따라서 특정 노드가 성공적으로 전송할 확률은 <code>N * p * (1 – p)<sup>2(N – 1)</sup></code>이다. 슬롯 ALOHA와 마찬가지로 극한을 취하는 방식으로 분석을 진행하면, 순수 ALOHA 프로토콜의 최대 효율은:
	1/2e ≈ 0.18		1/2e ≈ 0.18
	즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.		즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.

Pinkgo: /* Taking-Turns Protocols */

2025-05-16T11:48:57Z

Taking-Turns Protocols

@@ 84번째 줄: / 84번째 줄: @@
 ==Taking-Turns Protocols==
 ==각주==
 [[분류:컴퓨터 네트워크]]

Pinkgo: /* CSMA */

2025-05-16T11:09:47Z

CSMA

← 이전 판		2025년 5월 16일 (금) 11:09 판
82번째 줄:		82번째 줄:
	==[[CSMA]]==		==[[CSMA]]==
	자세한 내용은 [[CSMA]] 문서를 참조하십시오.		자세한 내용은 [[CSMA]] 문서를 참조하십시오.

			==Taking-Turns Protocols==

	==각주==		==각주==
	[[분류:컴퓨터 네트워크]]		[[분류:컴퓨터 네트워크]]

Pinkgo: /* CDMA */

2025-05-15T09:24:41Z

CDMA

← 이전 판		2025년 5월 15일 (목) 09:24 판
80번째 줄:		80번째 줄:
	즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.		즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.

	==[[~~CDMA~~]]==		==[[CSMA]]==
	자세한 내용은 [[~~CDMA~~]] 문서를 참조하십시오.		자세한 내용은 [[CSMA]] 문서를 참조하십시오.

	==각주==		==각주==
	[[분류:컴퓨터 네트워크]]		[[분류:컴퓨터 네트워크]]

Pinkgo: /* Pure ALOHA */

2025-05-15T09:03:23Z

Pure ALOHA

← 이전 판		2025년 5월 15일 (목) 09:03 판
80번째 줄:		80번째 줄:
	즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.		즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.

			==[[CDMA]]==
			자세한 내용은 [[CDMA]] 문서를 참조하십시오.

	==각주==		==각주==
	[[분류:컴퓨터 네트워크]]		[[분류:컴퓨터 네트워크]]

Pinkgo: /* Pure ALOHA */

2025-05-15T07:13:47Z

Pure ALOHA

← 이전 판		2025년 5월 15일 (목) 07:13 판
66번째 줄:		66번째 줄:
	즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.		즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.

	==Pure ALOHA==		=== Pure ALOHA ===
	최초의 ALOHA 프로토콜은 sloted ALOHA과 달리 동기화를 요구하지 않고 완전히 decentralized된 프로토콜이다. Pure ALOHA에서는 프레임이 처음 도착하였을 때(송신 노드에서 데이터 그램이 link layer에 내려왔을 때), 노드는 즉시 해당 프레임 전체를 브로드캐스트 채널로 전송한다. 만약 프레임을 전송한 노드가 충돌을 경험한다면, 노드는 해당 프레임의 전송을 마친 후, 아래와 같이 작동한다:		최초의 ALOHA 프로토콜은 sloted ALOHA과 달리 동기화를 요구하지 않고 완전히 decentralized된 프로토콜이다. Pure ALOHA에서는 프레임이 처음 도착하였을 때(송신 노드에서 데이터 그램이 link layer에 내려왔을 때), 노드는 즉시 해당 프레임 전체를 브로드캐스트 채널로 전송한다. 만약 프레임을 전송한 노드가 충돌을 경험한다면, 노드는 해당 프레임의 전송을 마친 후, 아래와 같이 작동한다:
	* 확률 p에 따라 전송한다.		* 확률 p에 따라 전송한다.

Pinkgo: /* Random Access Protocols */

2025-05-15T07:12:52Z

Random Access Protocols

← 이전 판		2025년 5월 15일 (목) 07:12 판
47번째 줄:		47번째 줄:
	* 노드들은 동기화되어 있어, 동일한 슬롯을 공유한다.		* 노드들은 동기화되어 있어, 동일한 슬롯을 공유한다.
	* 두 개 이상의 프레임이 하나의 슬롯에서 충돌할 경우, 이와 연루된 모든 노드는 해당 슬롯이 끝나기 전에 충돌을 감지한다.		* 두 개 이상의 프레임이 하나의 슬롯에서 충돌할 경우, 이와 연루된 모든 노드는 해당 슬롯이 끝나기 전에 충돌을 감지한다.
			[[파일:Sloted ALOHA example.png\|대체글=Figure 3. Sloted ALOHA example\|섬네일\|Figure 3. Sloted ALOHA example]]
	이러한 상황이 가정되어 있을 때, p를 0과 1사이의 확률이라고 하자. 이때 Sloted ALOHA는 아래와 같이 작동한다:		이러한 상황이 가정되어 있을 때, p를 0과 1사이의 확률이라고 하자. 이때 Sloted ALOHA는 아래와 같이 작동한다:
	# 노드가 새로운 프레임을 보낼 준비가 되면, 다음 슬롯이 시작할 때 프레임 전체를 슬롯에 전송한다.		# 노드가 새로운 프레임을 보낼 준비가 되면, 다음 슬롯이 시작할 때 프레임 전체를 슬롯에 전송한다.
62번째 줄:		63번째 줄:
	N개의 노드 중 어느 하나가 성공할 전체 확률: N * p * (1-p)<sup>N-1</sup>		N개의 노드 중 어느 하나가 성공할 전체 확률: N * p * (1-p)<sup>N-1</sup>
	즉, sloted ALOHA의 최대 효율은 <code>N * p * (1-p)<sup>N-1</sup></code>이다. 이를 최대화하기 위해서는 p에 대해 최적화해야 한다. 또한 활성 노드의 수 N이 매우 클 때의 효율을 구하기 위해서는 <code>N <math>\to \infty</math></code>일 때의 <code>N * p * (1-p)<sup>N-1</sup></code> 극한을 구해야 한다. 이를 계산하면, sloted I/O의 최대 효율은 아래와 같다:		즉, sloted ALOHA의 최대 효율은 <code>N * p * (1-p)<sup>N-1</sup></code>이다. 이를 최대화하기 위해서는 p에 대해 최적화해야 한다. 또한 활성 노드의 수 N이 매우 클 때의 효율을 구하기 위해서는 <code>N <math>\to \infty</math></code>일 때의 <code>N * p * (1-p)<sup>N-1</sup></code> 극한을 구해야 한다. 이를 계산하면, sloted I/O의 최대 효율은 아래와 같다:
	1/e = 0.37		1/e ≈ 0.37
	즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.		즉, 많은 노드가 다량의 프레임을 전송하려는 경우, 슬롯의 최대 37%만이 실제로 유용한 전송에 사용된다. 따라서 채널의 유효 전송 속도는 R bps가 아니라 0.37R bps에 불과하다.

			==Pure ALOHA==
			최초의 ALOHA 프로토콜은 sloted ALOHA과 달리 동기화를 요구하지 않고 완전히 decentralized된 프로토콜이다. Pure ALOHA에서는 프레임이 처음 도착하였을 때(송신 노드에서 데이터 그램이 link layer에 내려왔을 때), 노드는 즉시 해당 프레임 전체를 브로드캐스트 채널로 전송한다. 만약 프레임을 전송한 노드가 충돌을 경험한다면, 노드는 해당 프레임의 전송을 마친 후, 아래와 같이 작동한다:
			* 확률 p에 따라 전송한다.
			* 확률 1-p에 해당된 경우, 프레임 전송 시간만큼 다시 대기한다. 대기가 끝난 후에는 다시 확률 p에 따라 재전송을 시도한다.
			Pure ALOHA의 최대 효율을 계산하기 위해서는 개별 노드 하나의 동작을 분석해야 한다. 이때 상황 가정은 sloted ALOHA와 동일한 과정을 사용하며, 프레임 전송 시간을 시간 단위로 사용한다. 임의의 시간에, 노드가 프레임을 전송할 확률은 p라고 하고, 어떤 프레임이 시간 t<sub>0</sub>일 때 전송을 시작한다고 하자. 이 프레임이 성공적으로 전송되기 위해서는, 다음의 조건이 만족되어야 한다:
			[[파일:Collision probability increases in pure ALOHA.png\|섬네일\|Figure 4. Collision probability increases in pure ALOHA]]
			# 다른 어떤 노드도 [t<sub>0</sub> – 1, t<sub>0</sub>] 구간에서 전송을 시작하면 안 된다.
			#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<sub>(N – 1)</sub> 이다.
			# [t<sub>0</sub>, t<sub>0</sub> + 1] 구간에도 다른 노드가 전송을 시작하면 안 된다.
			#* 다른 모든 노드가 이 구간 동안 전송을 시작하지 않을 확률은 (1 – p)<sub>(N – 1)</sub> 이다.
			따라서 특정 노드가 성공적으로 전송할 확률은 <code>p * (1 – p)<sub>2(N – 1)</sub></code>이다. 슬롯 ALOHA와 마찬가지로 극한을 취하는 방식으로 분석을 진행하면, 순수 ALOHA 프로토콜의 최대 효율은:
			1/2e ≈ 0.18
			즉, sloted ALOHA의 효율(1/e ≈ 0.37)의 정확히 절반이다.


	==각주==		==각주==
	[[분류:컴퓨터 네트워크]]		[[분류:컴퓨터 네트워크]]

Pinkgo: /* Random Access Protocols */

2025-05-15T04:42:51Z

Random Access Protocols

@@ 51번째 줄: / 51번째 줄: @@
 # 충돌이 없다면, 프레임 전송은 성공한 것이고, 재전송할 필요가 없다.
 # 충돌이 발생했다면, 노드는 슬롯이 끝나기 전에 충돌을 감지한다. 이후 각 노드는 성공할 때까지 각 슬롯마다 확률 p에 따라 프레임을 재전송한다.
 ==각주==
 [[분류:컴퓨터 네트워크]]