KR20000025560A - 다중 접속 망에서의 전송 우선순위 결정장치 및 방법 - Google Patents

Abstract

이 발명은 데이터 전송 우선순위 결정에 공정성을 부여하는 장치 및 방법에 관한 것으로, 전송되는 프레임 길이를 카운트하는 송신비트 카운터와 충돌감지 시점까지의 전송된 프레임 길이를 슬롯타임/2에 해당하는 길이와 비교하는 송신비트 비교부를 포함하여 충돌에 관여한 단말기들 중에 먼저 데이터 전송을 시작했던 단말기는 랜덤(random)하게 결정되는 지연시간을 대기할 필요없이 바로 재전송을 시도하도록 함으로써 공정한 전송이 이루어지도록 한다.

Description

다중 접속 망에서의 전송 우선순위 결정장치 및 방법

이 발명은 다중 접속 방식(multiple access protocol)에 관한 것으로, 보다 상세하게는 다중 접속 망(multiple access network)에서 통신로를 점유하는데 있어서 공정성을 부여하여 전송 우선순위를 결정하는 장치 및 방법에 관한 것이다.

다중 접속 방식은 전송채널을 공유하는 방법적 문제를 해결하기 위해 설계된 것으로, 현재의 네트워크에서 가장 많이 사용되는 방식은 이더넷(ethernet) 통신에서 사용하는 CSMA/CD(carrier sense multiple access with collision detection)방식이다. 상기 CSMA/CD방식은 랜덤접속방식에 속한다. 랜덤접속 방식이란 전송 차례에 대한 중앙 통제가 없으므로 전송 중에 데이터 충돌이 발생했을 때는 랜덤(random)하게 주어지는 지연시간 후에 또다시 전송을 하는 방식이다.

다음은 종래의 CSMA/CD방식의 동작원리를 도1의 흐름도를 참조하여 설명한다.

CSMA/CD방식은 데이터(data)를 전송하기 전에, 전송선로가 사용중인가를 조사하여 사용중이면 일정 시간동안 기다렸다 다시 전송을 시도하고(S10), 사용중이 아니면 데이터를 프레임(frame)단위로 전송한다(S20). 전송선로에 두 개 이상의 데이터 프레임이 존재하여 충돌(collision)이 발생하면(S30) 데이터 프레임의 송신을 즉시 중단하고 충돌신호를 송신한 후(S40), 랜덤(random)하게 결정되는 지연시간만큼 기다린 다음에(S50) 다시 전송을 시작한다.

만약, 충돌에 개입한 모든 단말기들이 같은 지연시간 후에 재전송을 시도하게 된다면 충돌은 또다시 발생하게 된다. 따라서 이러한 문제를 해결하기 위해서 CSMA/CD방식은 지연시간의 길이가 랜덤하게 결정되도록 하는 알고리즘을 채택하여 사용한다. 재전송 시도를 백오프(back off)라고 하며 이를 위한 알고리즘을 백오프 알고리즘이라고 한다.

그러나 이러한 백오프 알고리즘에 의하면 지연시간의 길이가 랜덤하게 결정되므로 전송차례도 랜덤하게 결정된다는 문제점이 있다. 또한 여러번의 충돌을 겪은 단말기보다 나중에 한 번의 충돌을 겪은 단말기가 먼저 전송라인을 획득하게 될 확률이 높다는 보다 심각한 문제점이 있다.

다음은 이러한 문제점을 종래의 랜덤 지연시간 결정방법과 관련하여 보다 상세히 설명한다.

재전송을 하기 전에 랜덤하게 주어지는 지연시간은 다음 수학식1에 의해서 결정되어 진다.

0 ≤ 랜덤 정수(N)〈2^충돌횟수

지연시간(delay time) = 슬롯타임(slot time) × 랜덤정수(N)

여기서, 수학식1의 슬롯타임이란 데이터 프레임의 첫 비트(bit)가 전송된 시간부터 충돌사실이 감지되어 전송을 중지할 수 있는 충분한 시간을 말한다.

그런데, 수학식1에 의하면 충돌을 많이 하면 할수록 충돌할 확률은 높아짐을 알 수 있다.

예를 들면, 9번의 충돌을 겪은 단말기는 0에서 2⁹ 까지의 임의의 랜덤정수를 가지므로 9번의 충돌 후에 슬롯타임× 2^0∼9 만큼까지의 지연시간을 가진다. 그러나, 충돌을 처음 겪는 단말기는 0에서 2¹ 까지의 랜덤정수를 가지므로 슬롯타임× 2^0∼1 만큼의 지연시간을 가진다. 이러한, 두 지연시간의 비교에 의하면 한 번의 충돌을 겪은 단말기가 9번의 충돌을 겪은 단말기보다 먼저 전송라인을 획득할 수 있는 확률이 높다는 것을 알 수 있다.

여러번의 충돌을 겪은 단말기의 경우에는 지연시간이 확률적으로 점점 커지게 되므로 결과적으로 여러번의 충돌을 겪은 단말기보다는 나중에 한 번의 충돌을 겪은 단말기가 먼저 전송라인을 획득하게 되는 것이다. 따라서, 먼저 전송라인을 점유하고 전송을 시작해도 나중에 전송을 시작한 단말기에 의해 전송이 지연되는 문제를 야기시킨다.

이와 같이, 종래의 CSAM/CD방식은 전송 우선순위에 대한 공정성에 어긋난다는 심각한 문제점이 있다.

따라서, 이 발명의 과제는 이러한 문제점을 해결하여 전송 우선순위에 대한 공정성을 부여하기 위한 것으로서 두 단말기가 프레임 전송 충돌 후 재전송을 시도할 때 먼저 전송을 시작했던 단말기가 나중에 전송을 시작했던 단말기보다 먼저 전송라인을 점유하도록 하는데 있다.

도1은 종래의 CSMA/CD의 송신부 동작을 나타낸 흐름도이다.

도2a는 최소 이더넷 프레임 길이에 대한 규정을 표현한 도면이다.

도2b, 도2c 및 도2d는 슬롯타임과 프레임 길이의 관계를 나타낸 도면이다.

도3은 이 발명의 실시예에 따른 전송 우선순위 결정을 위한 장치를 포함한 MAC계층의 블록도이다.

도4는 이 발명의 실시예에 따른 CSMA/CD의 송신부 동작을 나타낸 흐름도이다.

이러한 과제를 달성하기 위해 이 발명은, 이더넷 망으로 전송되는 프레임 길이를 카운트하여 충돌발생 후 충돌이 감지된 시점까지 전송된 프레임 길이를 검출한다. 검출된 프레임 길이를 슬롯타임/2에 해당하는 비트수와 비교하여 전송 우선순위가 앞서는가를 결정한다. 이 결정에 의하여 충돌에 관여한 다른 단말기들보다 전송 우선순위가 앞서는 경우에는 랜덤하게 결정되는 지연시간의 대기없이 바로 재전송을 시도하도록 한다.

이와 같은, 전송 우선순위 결정을 위해 이 발명은 데이터 링크 계층의 부계층인 MAC계층에 속하는 MAC 컨트롤러(controller)와 MAC 드라이버 그리고 공유 로컬 메모리로 구현되는 송수신용 프레임 버퍼로 구성된다.

MAC 컨트롤러는 하드웨어로 구성되었으며 내부에 프레임 송신비트 카운터(transfer bit counter)를 가진다.

MAC 드라이버는 전송 우선순위 결정을 위해 소프트웨어로 구현된 송신비트 비교 부분을 포함한다.

MAC 컨트롤러 내부의 송신비트 카운터는 프레임 전송 개시 후 전송되는 프레임 비트수를 카운트한다. 충돌 감지 후에는 송신된 프레임 길이에 해당하는 상기 카운트된 값을 상기 MAC 드라이버에 넘겨준다.

MAC 드라이버 내부의 송신비트 비교부분은 송신비트 카운터에서 넘겨준 상기 카운트 값을 슬롯타임/2에 해당하는 비트와 비교한다. 이 비교에 의하여 랜덤하게 결정되는 지연시간의 대기 여부가 결정된다.

이 발명의 실시예에 앞서 우선, 도면을 참조하여 충돌 감지 시점까지 송신비트 카운터에서 카운트된 값에 해당하는 전송된 프레임 길이와 MAC 드라이버 내부에서 비교되어지는 슬롯타임의 관계를 설명한다.

슬롯타임은 앞서 종래 기술에 설명한 바와 같이 충돌이 있은 후 이 사실을 감지하고 전송을 중지할 수 있는 충분한 시간을 말하는 것으로 전파지연(propagation)시간의 두 배에 리피터(repeater)나 단말기에서 겪는 송수신 지연시간을 합한 것이다. 이와 같이 결정되는 슬롯타임은 프레임의 최소길이를 규정한다. 규정보다 짧은 프레임이 전송될 때, 충돌이 발생한다면 충돌감지 신호가 감지되기도 전에 프레임은 이미 전송되어 버리므로 송신을 완료한 후에야 뒤늦게 충돌을 감지하게 된다. 따라서 10㎒ 이더넷통신인 경우에 슬롯타임은 51.2㎲로 이에 해당하는 최소프레임 길이는 512비트(51.2㎲×10㎒=512비트)가 된다.

도2a에 나타난 바와 같이 단말기A(100)가 슬롯타임보다 길이가 짧은 프레임을 전송할 경우에는 단말기B(110)와 충돌이 발생해도 단말기A(100)는 전송이 완료된 후에야 뒤늦게 충돌을 감지하게 되는 경우가 발생한다. 이는 충돌이 일어났을 때 이 사실을 감지하려면 슬롯타임만큼의 시간이 걸리는데 그 시간동안에 단말기A(100)가 보낸 짧은 프레임은 모두 전송되기 때문이다. 그 결과 단말기A(100)는 송신을 성공한 것으로 간주하여 더 이상 재전송을 시도하지 않는다.

반면, 도2b는 단말기C(200)가 슬롯타임보다 길이가 긴 프레임을 전송할 경우로 단말기D(210)와 충돌이 발생해도 전송 완료 전에 충돌감지가 가능하다.

도2c는 단말기E(300)와 단말기F(310)가 같은 시간에 동시에 프레임을 전송한 경우를 나타낸 도면이다. 이 경우에 충돌은 전송로의 중간에서 발생한다. 여기서 리피터나 단말기에서 겪는 송수신 지연시간은 단말기E(300)와 단말기F(310)가 같으며 이 두 단말기의 전송속도는 같다고 간주한다. 신호가 상대측 단말기까지 보내졌다가 되돌아오는 전파지연시간이 포함된 슬롯타임에 해당하는 비트수가 10㎒ 이더넷통신인 경우에는 512비트이므로 단말기E(300)와 단말기F(310)가 전송로의 중간에서 충돌을 겪었다면 각각의 단말기E(300)와 F(310)는 128비트씩 전송한 상태가 된다. 여기서, 128비트는 슬롯타임의 반인 256비트에 해당하는 전송로의 중간에서 충돌을 겪으므로 해서 계산된 값이다. 그러나 충돌이 발생한 후 충돌사실을 MAC계층에서 감지하려면 충돌 감지신호가 MAC계층에 도달하는 시간이 필요한데 이 시간동안 단말기는 128비트를 더 전송하게 된다. 결과적으로 전송로 중간에서 일어난 충돌을 감지했을 때 두 단말기는 슬롯타임에 해당하는 비트의 반인 256비트를 전송한 상태가 된다.

이러한, 사실로부터 도2d에 표현된 바와 같은 결론을 이끌어낼 수 있다. 즉, 단말기G(400)가 단말기H(410)와 충돌이 일어난 후, 이를 감지하여 전송을 중지하기까지 단말기G(400)가 256비트보다 많은 프레임 길이를 전송하였다면 단말기H(410)보다 먼저 전송로를 점유하고 전송을 시작했음을 알 수 있다.

이와 같은 사실을 이용하면 데이터 프레임 전송 중에 충돌이 발생하였을 때, 충돌이 감지된 시점까지 전송된 프레임의 길이가 슬롯타임의 반에 해당하는 길이보다 긴 단말기는 충돌에 관여한 상대 단말기보다 먼저 전송로를 점유했음을 알 수 있게 된다.

따라서, 본 발명은 이와 같은 원리를 이용한 것으로 단말기들은 충돌이 감지되었을 때, 그 시점까지 전송한 프레임 길이를 검출하여 슬롯타임/2에 해당하는 비트수와 비교한다. 이 비교에 의해 자신이 먼저 전송을 했는지 여부를 판단한다. 먼저 전송을 했음이 판명되면 지연시간을 랜덤하게 결정할 필요없이 바로 재전송을 시도한다. 그러나 충돌에 관여한 다른 상대 단말기는 랜덤하게 결정되는 지연시간 만큼 대기한 후 재전송을 시도하게 된다. 이와 같은 과정을 통해 이 발명은 먼저 전송을 시작한 단말기가 먼저 전송라인을 점유할 수 있도록 하는 공정성을 부여할 수 있다.

이하, 도면을 참조하여 이 발명의 실시예에 따른 데이터 프레임 재전송에 있어서 공정성을 제공하기 위한 전송 우선순위 결정장치 및 방법을 설명한다.

도3은 이 발명의 실시예에 따른 이더넷 프레임 재전송 시에 공정성을 제공하기 위한 전송 우선순위 결정장치를 나타낸 블록도이다.

도3에 도시한 바와 같이 전송 우선순위 결정장치는 이더넷 계층에 속하는 MAC계층(600)과 상위계층(500) 그리고 물리층(700)으로 이루어지며, 단말기내의 MAC계층은 크게 MAC드라이버(610)와 공유로컬 메모리(620) 그리고 MAC컨트롤러(630)로 이루어진다.

MAC계층(600)은 상위계층(500)으로부터 전송할 데이터를 받아 이더넷 프레임 형태로 만든 다음 전송선로 상태를 점검한다.

MAC계층(600)에 속하며 소프트웨어로 구현된 MAC드라이버(610)는 이더넷 프레임이 저장된 공유 로컬 메모리(620)의 시작주소와 길이 정보를 MAC 컨트롤러(630)에 알려주면서 전송을 요구한다.

MAC컨트롤러(630)는 내부에 전송되는 프레임 비트수를 카운트하는 송신비트 카운터(640)를 갖는다. MAC컨트롤러(630)는 CSMA/CD동작에 따라 물리층(700)에서 보고되는 전송로의 상태를 먼저 검사한 후, 전송로가 사용중이 아니면 물리층(700)이 제공하는 송신 클럭(Tx clock)에 맞춰 송신을 개시한다. 송신 개시와 함께 MAC 컨트롤러 내부의 송신비트 카운터(640)가 전송되는 프레임 비트수를 카운트한다.

송신도중 충돌감지신호(collision detect)가 물리층(700)을 경유하여 MAC 컨트롤러(630)에 보고되면 프레임 송신은 중지되고 송신비트 카운터(640)에서 카운터된 프레임 전송 비트값은 MAC드라이버(610)로 입력된다.

MAC드라이버(610)로 입력된 상기 프레임 전송 비트값은 MAC드라이버(610) 내부의 소프트웨어로 구현된 비교 알고리즘에 의하여 슬롯타임의 반에 해당하는 비트수와 비교된다.

이 비교에 의하여 MAC드라이버(610)에 입력된 프레임 전송 비트값이 슬롯타임의 반에 해당하는 비트수보다 작다면 MAC드라이버(610) 지연시간을 결정하기 위한 백오프 알고리즘을 수행한다. 반면 입력된 프레임 전송 비트값이 슬롯타임의 반에 해당하는 비트수보다 크다면 MAC드라이버(610)는 바로 재전송을 준비한다.

도 4는 본 발명의 실시예에 따른 전송 우선순위 결정장치의 동작 방법을 나타낸 흐름도이다.

단말기의 MAC계층은 프레임 전송 전에 전송선로 상태를 점검하여 캐리어 신호가 감지되면 캐리어가 없어질 때까지 전송선로의 상태를 계속 감시한다(S800). 캐리어가 없어지면 일정시간 대기 후 다시 전송선로의 상태를 점검하여 캐리어가 감지되지 않으면 준비된 프레임 전송을 시작한다(S810) 전송을 시작한 이후로 충돌이 없으면 전송이 완료된다. 충돌이 감지되면(S820) 전송을 중지하고 충돌감지 신호를 송신한 후 전송한 프레임의 길이를 검출한다(S830).

프레임 길이의 검출은 MAC컨트롤러 내부의 송신비트 카운터에서 이루어진다. 검출된 프레임의 길이는 MAC드라이버에 입력된다. MAC드라이버로 입력된 프레임 길이는 슬롯타임/2에 해당하는 비트길이와 비교된다(S840).

위의 비교에 의하여 입력된 프레임 길이가 슬롯타임/2에 해당하는 비트길이보다 작다면 MAC드라이버는 백오프 알고리즘을 수행하여 랜덤하게 결정되는 지연시간을 갖는다(S850). 그러나 입력된 프레임 길이가 슬롯타임/2에 해당하는 비트길이보다 크다면 MAC드라이버는 지연시간을 결정할 필요없이 바로 프레임 재전송을 시도한다.

이로서, 충돌에 관여한 단말기들 중에 가장 먼저 전송을 시작했던 단말기 즉, 전송된 프레임 길이가 슬롯타임/2에 해당하는 길이보다 긴 단말기는 먼저 전송을 하게 된다.

위에, 설명한 실시예에서는 데이터 프레임 길이의 검출로 전송 우선순위를 결정하는 데 있어서 슬롯타임의 절반에 해당하는 비트길이를 기준으로 하였으나, 이더넷 망의 여건에 따라 추가되는 지연요소 인자를 두어 슬롯타임/2에 추가 지연요소를 더한 것을 비교대상으로 하는 적용이 가능하다.

또한 이 발명의 실시예는 송신비트 카운터를 MAC컨트롤러 내부에 장착하였으며, 송신비트 비교부를 MAC드라이브 내부에 소프트웨어적으로 구성하였으나, 송신비트 카운트를 MAC컨트롤러 외부에 장착하는 응용이 가능하며 송신비트 비교부를 MAC계층 내에 하드웨어로 나타낼 수 있다.

이 발명에서는 IEEE(Institute of Electrical and Electronics Engineers) 802.3 규정을 따르는 이더넷의 구성을 바탕으로 설명하였으나, 이 발명은 IEEE 802.3에 한하는 것이 아니고 다양한 이더넷 프로토콜을 사용한 다중 접속 망에 적용될 수 있다.

이 발명에 따르면 이더넷 통신방식에서 프레임 전송시 충돌이 일어났을 때 전송된 프레임의 길이를 검출하여 슬롯타임과 비교함으로써 충돌한 단말기들 중에 먼저 전송을 시작했던 단말기를 찾아낼 수 있다. 찾아낸 단말기는 랜덤하게 주어지는 지연시간을 거치지 않고 바로 재전송을 개시하게 된다. 따라서 프레임 전송에 있어서 충돌을 하면 할수록 더욱 충돌할 확률이 높아지는 CSMA/CD방식의 단점을 보완할 수 있다.

이와 같이, 이 발명을 통해 충돌이 발생했을 때, 먼저 전송을 시작했던 단말기가 먼저 재전송을 할 수 있도록 함으로써 공정한 전송이 이루어지게 하는 효과를 가진다.

또한, 먼저 전송을 시작했던 단말기는 충돌이 발생했을 때, 랜덤하게 결정되는 지연시간을 대기하지 않고 바로 재전송을 하게 함으로써 네트웍의 전송효율을 높이는 효과를 가질 수 있다.

Claims (6)

1. 이더넷 프레임이 일정단위로 전송됨에 따라 카운트 동작을 수행하는 송신비트 카운터;

   프레임 전송 중에 충돌발생이 감지되면 상기 송신비트 카운터의 동작을 중지하고 상기 송신비트 카운터에 의해 카운트된 값을 출력하는 MAC컨트롤러;

   상기 MAC컨트롤러의 출력을 입력으로 받아 전송 우선순위를 결정하는 MAC드라이버를 포함하는 전송 우선순위 결정장치.
2. 제1항에서,

   상기 MAC컨트롤러는,

   상기 송신비트 카운터의 카운트 동작에 의해서 프레임 충돌이 감지된 시점까지 전송된 프레임 길이를 검출하는 것을 특징으로 하는 전송 우선순위 결정장치.
3. 제1항에서,

   상기 MAC드라이브는,

   상기 송신비트 카운터에 의해서 카운트된 프레임 길이와 슬롯타임과 비교하여 랜덤하게 결정되는 지연시간의 대기여부를 결정하는 것을 특징으로 하는 전송 우선순위 결정장치.
4. 제3항에서,

   상기 지연시간의 대기여부는,

   상기 카운트된 프레임 길이가 슬롯타임/2보다 작다면 상기 지연시간을 대기하고, 크다면 상기 지연시간을 대기하지 않고 바로 재전송을 시도하도록 결정되는 것을 특징으로 하는 전송 우선순위 결정장치.
5. 프레임 충돌 발생시 상기 충돌을 감지하여 전송을 중지하고 충돌신호를 송신하는 제1 단계;

   상기 충돌이 감지된 시점까지 전송된 상기 프레임의 길이를 검출하여 상기 프레임 길이가 슬롯타임/2에 해당하는 길이보다 큰 값을 갖는지를 판단하는 제 2단계;

   상기 프레임 길이가 상기 슬롯타임/2에 해당하는 길이보다 큰 값을 갖는 경우, 랜덤하게 결정되는 지연시간을 대기할 필요없이 바로 재전송을 준비하는 제3 단계;

   상기 프레임 길이가 상기 슬롯타임/2에 해당하는 길이보다 작은 값을 갖는 경우, 랜덤하게 결정되는 지연시간을 대기한 후에 재전송을 준비하는 제4 단계를 포함하는 것을 특징으로 하는 전송 우선순위 결정방법.
6. 제5항에서,

   상기 제 2단계는,

   전송 개시후 이더넷 프레임이 일정단위로 전송됨에 따라 송신비트 카운터가 카운트를 시작하는 단계와;

   상기 송신비트 카운터가 카운트를 시작한 후 프레임 충돌이 감지되었을 때, 카운트를 종료하는 단계와;

   상기 송신비트 카운터에 의해 카운터된 값을 상기 슬롯타임/2에 해당하는 길이와 비교하는 단계를 더 포함하는 것을 특징으로 하는 전송 우선순위 결정방법.