도닦는공돌이

출처 : http://www.zdnet.co.kr/news/news_view.asp?artice_id=00000039135625

데이터 통신과 네트워크 디자인을 희망하는 사람이라면 누구나 알아야 하는 테크닉이 바로 큐잉 이론입니다. 전산학을 비롯한 거의 모든 컴퓨터 네트워크와 통신 분야의 디자이너들에게 큐잉은 시스템의 행동 특성을 빠르게 분석, 설계, 그리고 평가할 수 있게 해주는 주요한 툴로 사용되고 있습니다.

이번 연재에서는 이러한 큐잉을 대기와 처리의 관점에서 네트워크에 어떻게 적용되는지 설명하고 두 가지 예제를 함께 풀어보겠습니다. 

노드와 링크의 조합인 네트워크에는 데이터의 트래픽 조절과 혼잡 제어가 필요합니다. 트래픽 조절이란 고속도로에서의 교통상황처럼 데이터 송신 노드(source node)에서 목적 노드(destination node/sink node)로 데이터가 전송될 때 목적 노드 쪽에서 데이터를 너무 빠르게 처리하거나(자원 낭비) 너무 느리게 처리(낮은 효율)하지 않도록 하는 것을 말합니다. 

혼잡 제어는 2개 이상의 노드로부터 링크를 통해 데이터를 전송할 때 데이터 충돌을 피하거나 해결하기 위한 방법입니다. 이상의 방법들은 높은 데이터 전송 효율을 목표로 하는 네트워크엔 꼭 필요한 요소이며 네트워크 디자이너들은 이러한 트래픽 관리를 통해 현 상태와 앞으로의 네트워크 상태를 가늠할 수 있어야 합니다. 

이와 같은 데이터 통신과 네트워크 디자인을 희망하는 사람이라면 누구나 알아야 하는 테크닉이 바로 큐잉 이론(Queuing Theory)입니다. 독자들은 아마도 큐(queue)라는 용어를 자료구조 관련 서적에서 대기 행렬이라는 용어로 접해보았을 것입니다.

다시 이해를 돕자면 큐는 먼저 들어온 데이터가 먼저 처리되는(First In First Out) 데이터의 저장 형태라고 할 수 있습니다. 이러한 것은 큐잉의 기본 개념에 불과합니다. 전산학을 비롯한 거의 모든 컴퓨터 네트워크와 통신 분야의 디자이너들에게 큐잉은 시스템의 행동 특성을 빠르게 분석, 설계, 그리고 평가할 수 있게 해주는 주요한 툴로 사용되고 있습니다. 이번 글에서는 이러한 큐잉을 대기(queue)와 처리(serve)의 관점에서 네트워크에 어떻게 적용되는지 설명하고 예제를 풀어 봄으로써 독자 여러분의 이해를 돕겠습니다. 

얼마 전에 다이수케 테라사와의 ‘초밥왕’이라는 만화를 보았습니다. 주인공 세키구치 쇼타가 초일류 초밥을 준비하기 위하여 재료들을 배우고 준비하는 마음가짐을 보고 기본기의 중요성을 다시 한번 마음에 되새기는 계기가 되었습니다. 큐잉 이론과 네트워크 모델링에 관한 이야기를 하기에 앞서 독자들이 이미 알고 있을 내용이겠지만 잠시 확률에 관한 기본기를 살펴보며 확률에 대한 기억을 되새겨 보겠습니다. 

확률 되돌아보기
세 개의 빨간 구슬과 두 개의 파란 구슬이 담겨있는 항아리에서 빨간 구슬을 뽑을 사건을 시행할 때 사건의 결과가 목적을 만족시킬 확률을 묻던 산수책의 문제 기억납니까? 아마 대부분의 독자들은 이러한 문제들을 초등학교 때부터 지금까지 서적과 수업, 생활 속에서 많이 접해 보았으리라 생각합니다. 

확률은 17세기 파스칼과 페르마라는 수학자간의 도박에 관한 이야기 속에서 학문적으로 체계화되었다고 합니다. 또한 확률은 복잡한 통계적 계산에 대한 정확한 처리라는 컴퓨터 발전의 기본 목표이기도 하였습니다. 이러한 확률은 네트워크의 기본 설계에 녹아 있습니다.

예를 들면 대개의 디자이너들이 데이터 전송과 수신시의 성공과 실패를 확률로 구분하고 디자인의 제한 조건으로 둡니다. 여러분이 사용하고 있는 모든 네트워크 장치들은 이러한 것들을 모두 만족시켜 준 것들이라고 할 수 있습니다. 이렇게 네트워크 속에서 확률의 예를 찾자면 몇 권의 책, 며칠의 시간으로도 아마 모자랄 것입니다. 

확률의 기본 정의
공명(axioms)이라는 것은 수학에서 무증명 명제(無證明 命題)라고 불리는 것으로, 기초를 세우기 위해 받아들이는 수학적 단정(assertion)이라고 할 수 있습니다. 일단 이러한 공명이 받아들여지면 우리는 법칙을 증명할 수 있는 것입니다. 

어떠한 사건 Ω는 각각의 실험에서 발생한 사건의 모든 집합을 말하며 표본 공간(Sample Space, 그래서 S로 나타내기도 하지요)라고 합니다. 합집합 A∪B(A union B)는 사건 A와 B가 각각 혹은 동시에 일어날 수 있는 모든 사건의 집합을 말합니다. A∩B(A intersection B)는 사건 A와 B가 동시에 일어나는 사건을 말합니다. 만약에 A∩B={}라고 하면 A와 B는 동시에 일어나는 사건이 없어 서로 배반 관계(mutually exclusive)라고 합니다.

확률은 어떤 사건이 일어나는 확실성의 정도를 수량적으로 나타낸 것입니다. 주사위의 예를 들면 주사위를 던진 후 하늘을 향하는 숫자를 하나의 사건이라고 한다면 모두 6개의 사건이 일어날 수 있습니다. 주사위가 균등하게 모든 이벤트를 발생한다고 가정하면 3보다 작거나 짝수인 사건(1, 2, 4, 6)이 나올 확률은 Pr[{짝수}∪{3보다 작은 수}] = Pr[짝수] + Pr[3보다 작은 수] - Pr[{짝수}∩{3보다 작은 수}] = 1/2 + 1/3 - 1/6 = 2/3가 될 것입니다. 다음과 같이 확률의 공명을 정리해 보았습니다.

확률 변수
확률 변수(random variable)는 쉽게 설명하면 확률을 나타내는 변수를 말합니다. 다시 말해서 표본 공간에서 일어나게 될 모든 이벤트들을 숫자로 나타내는 것입니다. 예를 들면 동전을 세 번 던져서 순서에 상관없이 앞면이 한번이라도 나올 확률은 Pr{뒤,뒤,뒤}=1/8을 제외한 Pr{앞,뒤,뒤}= 3/8, Pr{앞,앞,뒤}=3/8, Pr{앞,앞,앞}=1/8입니다. 여기서 우리가 다시 앞면이 나온 횟수를 X로 나타내면 Pr{X=0}=1/8, Pr{X=1}=3/8, Pr{X=2}=3/8, Pr{X=3}=1/8로 나타낼 수 있습니다. 

확률 변수 X는 다음과 같이 밀도 함수(density function)와 분포 함수(distribution function)에 사용될 수 있습니다. 특히 확률 변수가 셀 수 없는 무한한 값에 대해서는 연속적(continuous)이라고 하며 반대의 경우에는 이산형(discrete)이라고 부릅니다. 

분포 함수란 일어날 사건의 범위에 대한 확률의 분포를 나타낸 것입니다. 반면 밀도 함수는 이러한 분포 함수를 나타낼 수 있는 함수를 정의하며 밀도 함수를 앞의 식과 같이 모든 범위에 대하여 적분을 하면 1이 됩니다. 

기대 값(expected value)이란 확률 변수 X를 사용하여 가 확률 현상의 결과가 수 값으로 나타날 경우 사건 시행의 결과로 기대되는 수 값의 크기를 말합니다. 예를 들면 10번의 데이터 통신을 하여 3번의 에러가 나는 네트워크에서 5번의 통신을 하면 몇 번의 에러가 발생하는가에 대한 기대 값 혹은 평균 값이라고 할 수 있습니다. 이러한 기대 값은 E[X] 혹은 μ(뮤)로 나타냅니다. 

포아송 분포
확률 통계에는 정규 분포, 이항 분포, 지수 분포 등과 같이 다양한 분포가 있습니다. 이 중 포아송 분포(Poisson Distribution)는 발생 확률이 작은 사건을 대량적으로 확대하여 그 발생 횟수가 만드는 분포를 확률적으로 정의한 것을 말합니다.

포아송 분포는 전화통화 시간, 전화통신 성공 횟수, 텔넷과 ftp 세션의 연결 등을 예상하여 디자인에 사용하기 적합한 분포입니다. 또한 이번 연재의 주제인 큐잉 이론에 가장 쉽게 사용되는 분포이기도 합니다. <그림 1>은 대표적인 포아송 분포의 그래프입니다. λ는 패킷이 도착하는 비율을 나타내며 다음의 식과 같은 분포 함수를 가지고 있습니다. 

네트워크 모델링에서 큐잉 이론
잠시 여러분이 2명의 주문 담당 직원이 있는 패스트푸드 음식점의 사장이라고 가정하겠습니다. 여러분의 음식점에는 오전 11시부터 오후 1시 30분까지는 평상시 2배의 손님이 들어와 주문을 하기까지 평균 15분의 대기 시간을 가져야 합니다. 이 문제를 해결하기 위해서 무엇을 가장 먼저 생각하겠습니까? 

우선 고객이 기다려야 하는 15분이라는 문제를 해결해야 겠지요. 그럼 몇 명의 주문담당 직원을 추가적으로 배치해야 효과를 얻을 수 있을까요? 2명? 3명? 이러한 문제에 대한 해답을 주는 것이 큐잉 이론입니다. 앞서 언급한 것처럼 큐잉 이론은 비단 컴퓨터 모델링뿐만 아니라 수많은 산업에서 모델링에 사용되고 있는 툴입니다. 네트워크에서는 데이터를 고객으로 생각하고 주문 담당을 서버로 생각하여 효율적인 디자인을 하는 데 많이 사용되고 있습니다. 큐잉 이론에 기저하여 디자인한 분석적 모델을 프로그래밍하고 실행한다면 아주 훌륭한 네트워크 시뮬레이션 모델이 될 것입니다. 

큐잉 모델

<그림 2>는 가장 간단한 큐잉 모델입니다. λ는 큐잉 시스템에 도착하는 패킷의 도착 시간의 비율(패킷/sec)입니다. 예를 들면 라우터에 도착하는 패킷이나 전화 교환기에 도착하는 전화, 그리고 독자들의 패스트푸드 가게에 도착하는 손님들의 시간 비율이 될 것입니다. 만약 어떤 특정한 시간에 패킷이 도착했을 때 대기열에서 서비스를 기다리고 있는 패킷이 없다면 그 손님은 줄을 서지 않고 서비스를 받을 것입니다.

w는 대기열에서 서비스를 기다리고 있는 패킷의 평균 개수입니다. Tw는 대기열에서 기다려야 하는 평균 시간입니다. 여기서 평균이라 함은 패킷이 기다리지 않는 시간까지 함께 포함합니다. Ts는 서버가 패킷에게 서비스를 제공하는 시간을 말합니다.

ρ(로)는 서비스 유틸라이제이션(utilization)입니다. 이것은 서버가 일을 하고 있는 비율입니다. 예를 들어 서버 유틸라이제이션이 1인 경우는 서버가 100% 일을 하고 있다는 의미로 도착한 패킷들은 서버에서 서비스를 제공받을 수 없으며 큐에서 대기해야 합니다. 

이러한 경우 디자이너들은 두 가지 선택을 할 수 있습니다. 대기열을 늘리거나 서버를 증설하거나 말이죠(들어오는 손님을 막을 수는 없겠죠?) 대기열을 늘리면 대기열에 들어오지 못하던 패킷들을 기다리게 할 수는 있지만 여전히 기다리는 패킷들의 불평은 해결할 수 없을 것입니다.

서버를 증설한다면 좀 더 원활한 서비스를 제공할 수 있겠지만 기존의 서버 유틸라이제이션이 낮아지면 전체적인 시스템 측면에서 낮은 효율의 원인이 될 수 있을 것입니다. 이러한 점이 엔지니어들이 디자인할 때 항상 고려해야 하는 트레이드 오프(trade-off)라는 것입니다. 

독자들의 서버가 100%(ρ=1)로 일을 하고 있다면 큐잉 시스템을 나가는 패킷의 시간 비율은 도착하는 패킷의 시간 비율과 상관없이 항상 일정할 것입니다. 이러한 제한적 환경에서 시스템이 최대로 해결할 수 있는 도착하는 패킷의 시간 비율은 이론적으로 다음과 같이 나타낼 수 있습니다. 

하나의 패킷, m이 도착했다고 가정합니다. m의 앞에는 평균적으로 w개의 패킷이 대기열에서 서비스를 받을 순서를 기다리고 있을 것입니다. m이 대기열을 떠나 서비스를 받으러 가면 대기열에는 다시 w개의 패킷이 기다리고 있을 것입니다. 

그리고 Tw는 평균 대기 시간이 됩니다. 그렇기 때문에 λ의 비율로 도착한 패킷을 이용하면 w=λTw라는 것을 알 수 있습니다. 비슷한 방법으로 우리는 r=λTr임을 알 수 있습니다. 이것이 바로 리틀의 이론(Little's Formula)입니다. 리틀의 이론을 좀 더 응용하면 ρ=λTs, r=w+ρ을 구해 낼 수 있습니다.

독자들의 상사는 하나 혹은 둘의 제한(패킷 서비스 비율이나 서버 유틸라이제이션)을 주고 네트워크를 디자인하기를 원하고 있습니다. 어떻게 디자인하겠습니까? 자 그럼 이제 가장 효율적인 네트워크 디자인을 위한 연장(tool)을 다시 챙겨보도록 하겠습니다. 일반적인 큐잉 시스템에서 디자이너들에게 다음과 같은 입력(input)이 주어집니다. 

그리고 다음의 결과를 요구합니다. 

가장 중요한 가정은 도착하는 패킷의 비율(arrival packet rate)에 관한 것입니다. 대개의 경우 성공적으로 도착하는 패킷과 패킷 사이의 시간(inter-arrival times)을 exponential하다고 가정하는데 이것은 패킷의 도착 비율 λ가 포아송 분포를 따른다는 말입니다. 이해를 돕자면 패킷이 무작위로 독립적(Independent)으로 도착한다는 말입니다.

또한 서비스 시간은 exponential하다고 합니다. 이러한 가정을 간단하게 켄돌(Kendall)의 표기법을 따서 M/M/1(엠엠원)이라고 합니다(1은 서버의 개수). M/M/1의 경우는 가장 간단한 큐잉 모델이라고 할 수 있습니다. 다음은 이러한 경우의 파라미터에 대한 대응 공식을 나타내고 있습니다. 

그럼 실제 예제를 통해 큐잉 이론을 네트워크에 적용해 보도록 하겠습니다. 

<예제 1>
여러분이 디자인하게 될 랜은 100명의 사용자가 연결될 것입니다. 그리고 한 개의 서버를 사용해야 합니다. 사용자의 요청에 따른 서버의 평균 서비스 타임은 0.6초입니다. 피크 타임에는 1분에 20명의 사용자가 사용 요청을 할 것입니다. 평균 대응 시간은 얼마입니까?

<풀이 1>
우선 큐잉 모델을 M/M/1로 가정합니다. 그리고 랜 상황에서 일어나는 지연(delay)은 충분히 무시할 만한 수준이라고 가정하고 디자인합니다. 예제로부터 Ts=0.6임을 알아냅니다.

<풀이 1>을 통해서 서버 요청에 따른 평균 응대 시간이 0.75초임을 알게 되었습니다. 

<예제 2>
독자의 상사가 다음의 질문을 물어 보았다고 가정합니다. 다른 네트워크로 연결된 랜으로 패킷들이 보내어지고 있습니다. 모든 패킷들은 랜에 연결된 라우터를 지나서 네트워크로 보내져야만 합니다.

패킷들은 평균 5/sec으로 라우터에 도착합니다. 그리고 평균 패킷의 길이는 144옥텟(octets)이며 패킷 길이는 지수 분포를 따릅니다. 라우터로부터 네트워크까지의 라인 스피드는 9600bps입니다. 라우터에 도착한 패킷이 처리되어 나갈 때까지의 평균 시간은 얼마입니까? 또한 대기열에 있는 패킷을 포함하여 얼마나 많은 패킷이 평균적으로 라우터에 머물게 됩니까?

<풀이 2>
큐잉 모델은 M/M/1이기 때문에 우리는 공식을 사용할 수가 있습니다. 문제로부터 우리는 λ=5패킷/sec임을 알고 있습니다.

<풀이 2>를 통해서 우리는 라우터 안에 평균적으로 1.5개의 패킷이 있으며 도착해서 서비스를 받고 라우터를 나가는 평균 시간이 0.3초임을 알 수 있었습니다

옥석같은 좋은 글이라서 공유합니다.

출처: http://www.zdnet.co.kr/news/news_view.asp?artice_id=00000039134745

(지디넷코리아)

네트워크 디자이너가 되기 위한 첫 번째 시간에는 기본적인 인터네트워킹 디자인을 위한 네트워크의 기본 개념과 모델, 데이터 전송 방법 등을 설명하겠습니다. 노드와 링크가 조합을 이루고 그 조합을 통해 메시지가 전해지는 과정을 하나하나 자세하게 살펴보겠습니다. 

네트워크는 노드(Nodes)와 링크(Link)의 조합입니다. 이러한 네트워크를 통해서 다양한 형태의 메시지를 전송하는 것이 통신(Communication)입니다. 네트워크 디자이너들은 이러한 조합을 통하여 전송 효율(Efficiency)을 최대한 높이는 데이터 전송망을 설계하는 사람들입니다.

그렇다면 네트워크 디자이너들은 무엇을 어떻게 이용하여 네트워크를 설계할까요? 그들은 보다 효율적인 네트워크 설계를 위하여 상황에 맞는 다양한 연장을 사용합니다. 때로는 수학적인 툴을 사용하기도 하고 때로는 소프트웨어 시뮬레이션과 같은 방법을 사용하여 시각적인 구현과 평가를 하기도 합니다. 

독자들은 그동안 어떤 방법으로 네트워크를 구성하고 평가해 보았습니까? 이제 막 네트워크에 입문하는 중이라면 어떤 방법을 상상해 봤습니까? 저는 3회에 걸친 연재를 통하여 네트워크 디자이너가 특정한 업체의 디바이스를 얼마나 유효적절하게 사용하기 위한 사람이라는 정의가 매우 소극적인 것이라는 것을 얘기하고 싶습니다. 네트워크 디자이너는 소극적인 정의에 더하여 필요에 따라 알맞은 형태의 네트워크 디바이스들을 창조적으로 디자인할 수 있는 사람이어야 합니다.

랜카드, 라우터, 브리지(Bridge) 등의 네트워크 장치들을 필요에 따라 설계하고 만들어 낼 수 있는 네트워크 디자이너가 많아야지만 대한민국이 진정한 IT 강국으로서의 면모를 세계 속에 나타낼 수 있을 것입니다. 필자 또한 이러한 목표를 더욱 견고히 하는 계기로 삼고 네트워크에 관한 입문 이야기를 써내려가려고 합니다. 독자 여러분들도 ‘why’와 ‘how’를 생각하면서 읽어준다면 좋겠습니다. 

생활 속의 네트워크
여러분은 현실에서 본인만의 네트워크를 설계해 본 적이 있습니까? 필자는 오늘 오전 제품 계약에 관한 업무를 수행하기 위해서 전세계에 지사가 있는 유명 택배회사를 통하여 중요한 서류를 미국 텍사스 달라스에 위치한 장비회사로 보냈습니다. 우선 작성한 서류를 본인이 다니는 회사 봉투에 넣고 택배회사 직원에게 전화로 연락하였습니다. 택배회사 직원이 사무실을 찾아와 준비해온 택배회사 봉투에 서류를 넣고 보내는 사람과 받는 사람의 주소를 기재하였습니다. 마지막으로 택배회사의 해외서비스 분류 방법에 기준하여 봉투에 고유 코드를 붙였습니다.

저는 이틀 이내에 제 서류가 장비회사에 전달되어야 한다고 요청하였고 택배회사 직원은 이 모든 것에 대한 가격을 책정해 지불하여 계약서류를 목적지로 보내는 일을 마무리하였습니다. 자 그럼 이 서류가 이제 어떻게 미국 텍사스 달라스에 위치한 회사로 전달될지 상상해 보겠습니까?

서류는 서울 사무소를 거쳐서 인천공항 지역에 위치한 택배회사의 분류창고로 옮겨 질 것입니다. 제가 이틀이라는 시간적인 제한을 요청하였기 때문에 제 서류는 특별하게 관리되어 아메리카 지역 구분으로 나뉘어있는 방으로 보내어 질 것입니다. 그리고 다시 미국 분류 상자 안으로 옮겨져 가장 빠른 비행기 편으로 미국 LA의 택배회사 창고에 도착할 것입니다.

다시 필자의 서류는 텍사스를 향하는 비행기로 옮겨지고 달라스에서 기다리고 있는 직원에 의해 마지막으로 세부 분류되어 필자의 회사와 계약을 체결하려고 기다리고 있는 업무 담당자의 손에 전해 질 것입니다. 택배회사는 담당자의 수신확인서를 이메일을 통해 저에게 전달해 줄 것입니다. 여러분도 이와 같은 경험을 해본 적이 있나요?

오늘 저는 보내는 사람(Source Node)과 받는 사람(Destination Node)이 노드가 되어 시간과 비용을 고려한 해외 택배 서비스(link)를 통하여 네트워크를 경험해본 것입니다. 이렇게 네트워크는 우리 생활 속에 있으며 또한 긴 역사를 가지고 있습니다. 단지 요즘 우리가 봇물처럼 터지는 노드와 노드의 전기적인 연결에 노출되어 이제서야 네트워크 세상 속에 사는 것처럼 느낄 뿐입니다. 마치 혁명과 같이 세상의 매일을 변화시키는 컴퓨터 노드와 노드의 링크, 네트워크. 짧은 인터넷의 역사와 함께 되짚어 보겠습니다.

인터넷의 역사
인터넷은 데이터 통신과 컴퓨터 네트워킹을 위한 수많은 새로운 통신규약(Protocol)과 기술들을 출현시켰습니다. 이러한 출현은 이제 너무나 일반적인 용어가 되어버린 월드 와이드 웹의 촉매 역할로 인해 그야말로 폭발적인 위력을 발휘하고 있습니다. 병상에 갇혀있는 환자에게 세상으로 연결되는 창을 주었으며 우주정복을 꿈꾸는 시골 소년에게 미국 항공 우주국(NASA)의 화성 프로젝트에 참여하는 우주인과의 대화를 가능하게 하였습니다.

인터넷의 기원은 거슬러 올라가 1969년 미국에서 시작되었던 알파넷(ARPANET) 과제에서 비롯됩니다. 알파넷은 미 국방성(Department of Defense)의 ‘Advanced Research Projects Agency’라는 이름으로 패킷 스위칭 기법을 이용하여 겨우 4개의 노드를 단지 50kbps로 연결하여 전송하는 네트워크의 설계와 구현으로 시작하였습니다(여러분은 3회의 연재에서 4개 혹은 그 이상의 노드를 연결하는 시뮬레이션을 해보게 될 것입니다).

이러한 알파넷은 텔넷과 FTP, 그리고 네트워크의 첫 번째 킬러 app이었던 전자메일을 통해 크게 발전하는 계기가 되었고 미국의 기관, 학교, 국가단체를 거쳐 세계로 연구와 개발이 확장되었고 드디어는 TCP/IP(1980), WWW(1991), Mosaic(1992), OC-3(155Mbps) Backbone(1996) 등 지금은 정확하게 셀 수도 없는 웹 페이지들이 인터넷에 올려져 있습니다. 

<그림 1>은 필자의 은사였던 헬미(Helmy) 교수의 강의 노트에서 따 온 것입니다. 왼쪽 그림은 100개의 노드로 이루어진 네트워크망을 디자인 해본 그림입니다. 오른쪽 그림은 자동 시뮬레이션 프로그램을 이용해서 왼쪽 디자인의 100개의 노드를 확장하여 5만여개의 노드가 연결되어 있는 인터넷 지도를 나타내 본 것입니다. 어떤 느낌이 드나요?

이 두 그림으로 인터넷이 얼마나 짧은 시간에 크게 확대되었는지 실감할 수 있을 것입니다. 이 모든 것이 처음에 말한 대로 두 개의 노드와 하나의 링크로 시작되었던 것입니다. 자 그럼 이제 두개의 노드와 그 링크가 어떠한 구조를 각각 가지고 있으며 어떠한 방법으로 데이터를 주고받고 있는지 좀 더 자세히 살펴보도록 하겠습니다. 

네트워크 모델
일반적으로 통신은 애플리케이션, 컴퓨터, 네트워크의 세 개의 에이전트를 사용하고 있습니다. 애플리케이션이라고 하면 우리가 매일 사용하는 전자메일, 파일 다운로드 등과 같은 것을 말합니다. 이러한 애플리케이션들은 컴퓨터에서 수행됩니다. 또한 컴퓨터들은 네트워크에 연결되어서 서로 간에 네트워크를 통해 데이터를 보내기도 하고 받기도 하는 것입니다.

다양한 형태의 메시지를 노드와 링크로 주고받는 네트워크는 어떠한 방법으로 보내는 사람으로부터 전하는 사람을 지나서 받는 사람에게 전해질까요? 네트워크는 이러한 문제를 해결하기 위해 공통된 프로토콜을 정의하여 기능을 부가하고 컴퓨터 통신을 위한 연구 개발에 표준으로 삼기로 했습니다.

그렇다면 프로토콜이란 무엇일까요? 프로토콜의 사전적 정의는 협안, 조약안이지만 컴퓨터 통신에서는 2대 이상의 컴퓨터 통신을 위한 통신 규약이라고 말하고 있습니다. 사용하는 언어가 다른 사람들이 모여 높은 탑을 쌓는 공사를 하고 있을 때 표준으로 사용하는 언어(Protocol)와 단계(Procedure)가 없다면 어렵게 쌓아가고 있던 탑이 무너지고 말겠죠.

많은 기업과 학교, 그리고 과학, 공학, 국가단체들은 효율성과 사업모델, 이해관계를 놓고 오랫동안의 연구개발과 협의를 통하여 컴퓨터 통신의 표준을 정하고 있습니다. 이러한 방법으로 정형화된 컴퓨터 네트워크 프로토콜 중에 ISO(International Organization for Standardization)에서 개발된 OSI(Open System Interconnection) 모델이 있습니다. 하지만 7개의 계층으로 구성된 OSI 모델은 각 층간의 기능이 유사한 면이 있다는 단점이 있어 좀 더 명확한 기능과 단순한 계층을 갖고 있는 TCP/IP 프로토콜의 출현하게 되었습니다. 

OSI 모델
1978년 제작 초기 당시에만 해도 많은 OSI 디자이너들은 컴퓨터 네트워크에 이 모델이 가장 널리 사용되리라는 데 의문을 갖지 않았습니다. 결과적으로는 OSI 모델은 TCP/IP에 의해서 대체되고 말았지만 이러한 시도를 통해서 많은 유용한 프로토콜들이 개발되었고 7개의 계층으로 나뉘어 설계되었던 기능들은 다른 형태지만 아직도 같은 기능으로 존재하고 있습니다.

<그림 2>의 왼쪽 모델은 7개의 계층으로 구성된 OSI 모델입니다. 흔히 물리 계층(Physical Layer)에서 네트워크 계층(Network Layer)까지를 하위 계층 프로토콜이라고 하며 트랜스미션 계층(Transmission Layer)에서 애플리케이션 계층(Application Layer)까지를 상위 계층 프로토콜이라고 합니다.

7개의 계층 중에서 가장 위에 위치한 애플리케이션 계층은 사용자들이 OSI 환경을 액세스할 수 있도록 해줍니다. 그러기 위해 애플리케이션 계층은 사용자가 통신에 사용할 프로토콜 타입을 결정합니다. 여러 가지 애플리케이션에 따라 파일전송, 데이터베이스 접근, 전자메일 서비스에 맞는 프로토콜을 제공합니다. 그 다음 단계인 프리젠테이션 계층(Presentation Layer)은 애플리케이션 계층으로부터 전해진 다양한 데이터 타입을 전송 형식과 무관한 구문(syntax)의 형태로 변환하고 암호화(Encryption)하는 기능을 수행합니다. 

세션 계층(Session Layer)은 데이터와 서비스를 교환하려는 애플리케이션과 프로세스(Process)간의 접속 설정, 관리, 종료에 관한 제어(Control)를 하는 계층입니다. 전송 계층(Transport Layer)은 데이터 전달과 접속에 신뢰성을 주는 곳으로써 데이터를 보내는 곳과 받는 곳 사이에서 에러(error)를 복구하고 흐름을 제어하는 기능을 수행합니다.

이러한 기능은 다음에 소개될 네트워크 계층과 유사하지만, 전자는 통신이 이루어지는 처음과 끝(End-to-End) 시스템 간의 데이터 전송에 관한 이야기이고 후자는 하나의 전송 링크에 관한 관리 기능을 제공하는 데 차이가 있습니다.

이러한 관리 기능을 수행하는 네트워크 계층은 경로의 선택과 중계 기능을 추가로 수행하고 있습니다. 또한 데이터의 전달 기능을 향상시키기 위해서 데이터의 크기를 알맞게 나누는 일을 수행합니다. 데이터 링크 계층(Data Link Layer)은 물리적인 링크간에 신뢰성 있는 정보를 제공하며 정보를 전송하기 위해서 데이터를 블록이나 프레임 단위의 일정한 크기로 전송하고 구분하는 기능을 수행합니다. 이렇게 나눠진 프레임은 각각 순차적인 번호를 부여 받게 되어 목적지에 도착했을 때 에러 검사와 순서화 기능에 사용됩니다.

물리 계층은 비트 레벨의 통신에 관심이 있는 계층입니다. 최하위의 계층으로써 가장 궂은 일을 한다고 볼 수도 있겠죠. 물리 계층은 전송 매체 사이의 인터페이스를 정의하여 데이터 링크 계층과의 사이에 기계적이고 전기적인 기능에 문제가 있는지를 살펴봅니다. 

TCP/IP 모델
TCP/IP(Transmission Control Protocol/Internet Protocol) 모델은 인터넷이 개발되었던 알파넷 연구에서 비롯되었습니다. 이러한 배경은 TCP/IP가 인터넷 통신에 가장 적합하게 설계된 이유 중 하나입니다. TCP/IP는 보내는 사람에서 받는 사람까지의 플로우(flow)를 제어할 수 있으며 TCP와 IP 두 개의 프로토콜로 나눠서 통신이 가능하도록 합니다. 무엇보다 가장 큰 장점은 TCP/IP가 간단한 구조를 가지고 OSI의 7개 계층의 역할을 아무 무리 없이 수행해 낸다는 것이지요.

TCP/IP는 이러한 기능을 수행할 수 있는 프로토콜의 집합이라고 볼 수 있습니다. 우리가 많이 들어 알고 있는 프로토콜 이름의 대부분이 바로 TCP/IP의 애플리케이션 계층이라고 할 수 있습니다. 웹 서비스에 사용되는 HTTP를 비롯해서 일반 사용자가 다른 원격 호스트에 원격 로그인하여 자신의 컴퓨터처럼 사용할 수 있는 기능을 제공하는 텔넷, 파일 전송에 사용되는 FTP, 그리고 전자 우편 전송에 사용되는 SMTP(Simple Mail Transfer Protocol) 등을 예로 들 수 있습니다. 이러한 다양한 애플리케이션 프로토콜들은 사용자에게 다양한 애플리케이션을 수행할 수 있도록 도와주는 역할을 합니다.

전송 계층은 호스트 투 호스트(Host-to-Host) 계층이라고도 불리며 출발지에서 보내진 데이터가 목적지에 도착했을 때 출발 당시의 순서대로 정렬될 수 있도록 하는 일처럼 데이터가 송신자에게서 수신자에게까지 신뢰성있게 전송되고 받을 수 있는 역할을 합니다. TCP는 이러한 기능을 수행하는 가장 대표적인 프로토콜입니다.

전송 계층에는 TCP와 함께 UDP(User Defined Protocol)라는 또 다른 프로토콜이 있는데 UDP는 TCP와 달리 신뢰성을 보장할 수 없는 프로토콜입니다 (Unreliable/Connectionless). 따라서 신뢰성이 필요 없는 데이터를 전송할 때는 IP 위에 UDP를 올려 사용하여 데이터의 크기를 줄일 수 있는 장점도 있습니다. TCP와 UDP는 오류 검사를 이용하여 모두 체크섬(Checksum)이라는 방법을 사용하는데, 체크섬은 간단한 2진 덧셈을 통하여 오류를 검색하는 방법입니다.

인터넷 계층(Internet Layer)에서는 인터넷 프로토콜(IP)을 사용하여 인터넷 라우팅과 전송에 사용되는 인터넷 주소를 메시지에 포함하여 송수신지를 결정하게 됩니다. OSI 모델에서는 네트워크 계층이 이러한 기능을 수행합니다. 2004년 현재까지 아직 주소 할당에 32비트를 제공하는 IPv4가 TCP/IP 프로토콜이 주되게 사용되고 있으나 수많은 무선 장치의 등장과 인터넷 사용자 증가로 인한 한계성을 인식하고 주소할당에 128비트를 제공하는 IPv6로의 전환을 준비하고 있습니다.

네트워크 액세스 계층(Network Access Layer)은 서버(Server)와 워크스테이션(Workstation)의 End System, 추가되는 네트워크를 통한 데이터 전송, 그리고 전송 매체에 관심을 가지고 있습니다. 이 계층에서는 사용되는 서비스의 우선순위를 관리하기도 하고 데이터 전달에 관한 주소를 제공하기도 합니다. 물리 계층은 OSI 모델의 그것과 유사한 기능을 수행합니다. 물리적인 수준의 데이터 전송 장치들과 전송 장비 혹은 네트워크간의 인터페이스를 제공하며 전송매체에 관한 특성, 전송 속도 등을 지정합니다. 

네트워크로 메시지 보내기
이제 TCP/IP 모델을 이용하여 어떻게 데이터를 소스에서 목적지까지 보내는지 송신자(Sender), 라우터(Router), 수신자(Receiver)의 단계로 구분해서 살펴보도록 하겠습니다. 우리가 살펴볼 예제는 하나의 라우터가 ATM으로 구성된 장거리 네트워크(WAN)에 연결되어 있어 보내는 쪽(서버)과 받는 쪽(사용자 컴퓨터)을 연결하고 있다고 가정하고 있습니다. 그리고 지금 막 사용자가 마우스를 이용하여 브라우저에서 임의의 아이콘을 클릭해서 파일전송이나 웹페이지의 데이터를 요구했다고 가정합니다. 그럼 서버(송신자)가 라우터를 통해 사용자 컴퓨터에게 어떻게 응답(Response)하여 메시지를 수신자에게 보내는지 살펴보도록 하겠습니다. 

TCP/IP: 송신자 메시지 보내기

사용자 컴퓨터(수신자)로부터 전해진 메시지 요구로 인하여 서버쪽(송신자) 애플리케이션 계층은 전송할 데이터 블록과 프로토콜을 결정합니다. 만약 전자메일에 관한 요구였다면 SMTP를, 파일이었다면 FTP를 말이죠. 이 단계에서 데이터 송신과 수신 쪽에서 교환하는 데이터의 형태에 대한 동의를 하게 되며 필요하다면 데이터는 목적지에서 압축 또는 암호화(Data Encryption)되거나 보기 쉬운 형태로 변형됩니다.

TCP가 접속을 허가하기로 약속하면 데이터를 세그먼트(segment)라고 불리는 데이터 블록으로 만듭니다. 각각의 세그먼트에는 헤더(header)가 포함되어 있어 전송 에러 검출과 함께 도착지에서 데이터의 순서를 알 수 있도록 해줍니다. 

또한 각각의 TCP 세그먼트는 목적지로의 전송시 데이터 손실 등의 경우를 대비해 목적지로부터 데이터가 잘 도착했다는 메시지(acknowledgment)가 도착하기 전까지 복사되어 보관되었다가 확인 메시지가 도착하면 복사본을 지웁니다. 다시 세그먼트는 IP 계층으로 전달되고 IP는 각각의 세그먼트들을 데이터그램(datagram) 단위로 나누어 네트워크 전송에 맞는 사이즈로 재정비합니다. 이때 각각의 데이터 그램은 목적지 주소, 프레임 검사 순서, 제어 정보 등을 가지게 되며 이러한 기능을 프래그먼팅(fragmenting)이라고 합니다.

우리는 첫 번째 네트워크가 서버가 ATM WAN에 연결되어 있다고 가정하고 있기 때문에 이러한 프래그먼트는 다시 ATM 헤더를 포함하여 ATM 네트워크에 전송에 적합한 형태(ATM cell)로 변하게 됩니다. 이러한 Cell은 비트로 표현되어 네트워크 미디엄(network medium)을 통해 라우터로 보내지게 됩니다.

TCP/IP: 메시지 라우터 지나가기

라우터는 서로 다른 분리된 네트워크를 연결해 주는 기능을 제공하는 장치입니다. 라우터는 데이터의 목적지 정보가 담겨 있는 헤더를 이용해서 네트워크 상의 가장 효율적인 경로를 선택 패킷을 목적지로 보냅니다. 또한 라우터는 흐름제어 역할과 네트워크 관리 기능을 수행함으로 네트워크의 꼭 필요한 구성 요소입니다. <그림 4>는 ATM Cell의 형태로 전달된 데이터가 물리 계층에 비트 형태로 전달되는 것을 시작으로 보여줍니다.

ATM 계층은 전달된 데이터의 ATM Cell 헤더를 제거하고 헤더를 통해서 라우터에 데이터가 도착하기까지 아무런 에러가 없었는지 살펴봅니다. 또한 접속 번호를 통해서 발신지를 알 수 있습니다. ATM Cell 헤더가 제거된 메시지는 IP 계층에서 IP 헤더를 검사하게 됩니다. 검사 후 IP는 어떠한 경로로 메시지를 목적지에 보낼 것인가를 확정하게 됩니다.

이러한 경로는 목적지와 다시 다른 라우터가 될 수 있지만 우리는 본 예제에서 하나의 라우터를 사용하는 관계로 IP는 데이터그램을 곧바로 목적지로 보내 줄 것입니다. 데이터그램은 LLC(Logical Link Control)로 보내어져 다시 LLC 헤더가 추가되고 LLC PDU(Protocol Data Unit)라고 불리는 세분화된 블록 단위로 사용됩니다. 이 헤더는 주소와 순서에 관한 정보가 포함되어 있습니다. 다시 LLC PDU는 MAC(Media Access Control)으로 보내지고, 여기서 MAC 프레임을 구성하게 됩니다.

특이하게도 이 과정에서는 MAC 헤더와 트레일러(trailer)가 LLC PDU의 시작과 끝에 붙는데 헤더에는 주소 정보가 트레일러에는 에러검출을 위한 프레임 체크 시퀀스 정보가 저장됩니다. 여태껏 우리가 살펴본 중 가장 긴 형태의 메시지는 이제 마지막 목적지를 향하게 됩니다. 

TCP/IP: 수신자가 메시지 받기
드디어 목적지에 메시지가 도착했지만 아직 이곳에서도 몇 번의 과정이 기다리고 있습니다. 물리 계층을 통해 비트 프레임의 형태로 전달된 시그널은 MAC 계층에서 헤더와 트레일러를 제거하고 트레일러를 이용해서 에러 검출을 하게 됩니다. 그리고 LLC 계층에서는 헤더를 제거하고 데이터 흐름과 에러 조절을 위해 순서를 조절하게 됩니다. IP 계층에서도 헤더를 제거하고 프레임 검사와 다른 제어정보가 전달되면서 IP 데이터그램의 형태가 됩니다.

TCP 계층 단에서는 다시 한번 헤더 삭제와 함께 흐름 조절이 이루어집니다. 또한 프레임을 체크하게 됩니다. TCP 단에서는 전송지에서 세그먼트 형태로 나뉘어졌던 사용자 데이터를 다시 블록으로 결합한 후에 애플리케이션 단으로 전달하게 됩니다. 마지막으로 메시지가 애플리케이션 단으로 전달되면서 압축을 풀거나(decompression), 암호화를 해제하는(decryption) 등의 기능을 수행하여 데이터가 적합한 파일과 목적지로 바르게 전달되도록 합니다. 

데이터 전송 방식, 유니캐스트 VS 멀티캐스트
네트워크의 데이터의 전송 방식은 송신자와 수신자의 입장에서 데이터를 전송하는 방식에 따라 유니캐스트(Unicast)와 멀티캐스트(Multicast)로 나누어집니다. 유니케스트는 네트워크상에서 단일 송신자와 단일 수신자 간의 데이터 전송 방식을 지칭합니다. <그림 7>을 보면 송신자는 목적지 R1, R2, R3과 R4에 독립된 각각의 데이터를 전송합니다.

이러한 방식을 특별하게 멀티플 유니캐스트(Multiple Unicast)라고 하는데, 예전 네트워크를 구성하던 노드 대 노드의 일 대 일(One to One) 연결에 적합한 데이터 전송 방식입니다. 만약 <그림 7>과 같이 데이터의 송신지가 많은 경우에는 특별한 목적이 아니라면 모두에게 데이터를 보내기 위해 각각의 수신자에게 여러 번 데이터를 보내야 하는 유니캐스트를 사용하지 않는 것이 네트워크의 효율을 높일 수 있을 것입니다. 하지만 요즘의 인터넷 통신은 일 대 일 연결이 보편화되어 있고 라우터가 유니캐스트 방식만을 지원하기 때문에 유니캐스트 방식이 가장 많이 사용되고 있습니다. 

멀티캐스트 전송 방식은 하나의 전송자가 하나 이상의 송신자들에게 한 번에 데이터를 전송하는 방식으로 다 대 다(Multipoint to Multipoint) 통신을 위한 방법입니다. <그림 7>의 멀티캐스트를 살펴보면, 전송자는 송신자들에게 동시에 같은 데이터를 전송하는 것을 알 수 있습니다.

이러한 멀티캐스트 전송 방법은 같은 LAN에 연결되어 있는 그룹 사용자들에게 한 번에 메시지를 전송하는 데 적합한 방식입니다. 실제로 이러한 방식은 다중 접속이 되어 있는 인터넷 전화와 영상통신에 많이 응용됩니다. 이러한 전송 방식의 구분은 연재의 마지막 시간에 다룰 NS-NAM으로 해볼 네트워크 시뮬레이션을 이해하는 데 도움이 될 것입니다. 

서비스의 속도와 질의 향상을 위해
인터넷과 인터넷 프로토콜은 최선형(best-effort)을 제공하기 위해 디자인되었습니다. 다시 말해서 인터넷과 IP 기반 네트워크는 네트워크상의 패킷을 각각 동일하게 취급하여 목적지로 전송한다는 뜻입니다. 이러한 기본 정의 하에서 네트워크상에 트래픽이 늘고 혼잡(congestion)이 생기기 시작하면 패킷 전송은 점차로 늦어지게 됩니다. 혼잡이 더 크게 발생되면 심지어는 패킷 들을 드랍하여 전송 데이터에 손실을 주게 됩니다. 때문에 네트워크 디자이너에게 Traffic과 Congestion Control은 무엇보다 더 중요한 요소가 됩니다.

평가와 분석 단계에서도 중요성은 계속 인식되어야 합니다. QoS란 높은 데이터 비율(data rate)을 가지고 정확하게 데이터를 전달하는 것을 말합니다. 물론 컴퓨터통신에서 전달에 관한 신뢰성은 매우 중요한 요소입니다. 이러한 QoS를 나타내는 지표로써 흔히 작업 처리량(Throughput), 지연(delay), 패킷 손실(packet loss) 등을 사용합니다.

이러한 요소들은 실생활의 예를 통해서도 쉽게 그 중요성을 인식할 수 있습니다. 늘 지연되곤 하는 네트워크를 이용하는 외환딜러는 그렇지 않은 딜러들과의 경쟁에서 항상 불이익을 받게 될 것입니다. 또 음성이나 비디오 파일 등의 실시간 트래픽(real time traffic)에서 패킷 손실이 많이 일어난다면 우리는 자연스러운 음성과 화면을 볼 수가 없겠지요. 다음 연재에서는 이러한 문제들을 ‘큐잉 이론과 네트워크 디자인’에 관한 주제로 독자 여러분과 함께 살펴보려고 합니다. @

* This is not a class material for commercial purpose. It's free for student.* 

본 포스팅은 Pure Aloha를 먼저설명하고, Slotted Aloha를 유도한다.

1. ALOHA란?

Random access method의 한 방법으로 1970년대에 제안되었으며 여전히 셀룰러 시스템에서 그 Simplicity를 장점으로 사용된다. assumption

알로하(ALOHA)는 하와이 대학에서 개발되었으며 시분할 다중접속 기술을 사용해 위성과 지구 사이의 무선 전송을 하는 프로토콜이다. 원래의 알로하에서 사용자는 언제든지 전송할 수 있지만, 다른 사용자들의 메시지는 충돌할 위험이 있다. 패킷이 준비되면 브로드캐스트되며, 만약 충돌이 일어나면 일정시간 후에 재전송된다. Slotted Aloha는 채널을 시간대별로 나누어서 충돌 위험을 줄이는 것으로, 각 사용자는 시간대의 시작에서만 전송이 가능하다.

2. Basic working

- 노드는 데이터 전송을 언제든지 할수있고 ACK를 받는다

- 만약 하나의 Frame 이상이 같은 시간에 전송된다면, 그들은 서로 간섭을 겪기때문에 충돌하거나 패킷을 잃어버린다. 

   (Collision or Lost)

- 만약 ACK 패킷이 지정된 시간안에 도착하지 않으면 Timeout이 발생하고 전송을 한 노도는 Backoff time만큼 기다린후 

   다시 전송을 시도한다. 

2-2. Vulnerable period

- Frame의 길이 (전송할 패킷의 사이즈)를 L이라고 둔다면, L 길이 패킷을 전송하는 소요시간은 X = L/R (data rate)이 됨.

- consider a frame with starting transmission time to the frame will be successfully transmitted if no other frame 

   collides with it.

     -> any transmission that begins in interval [t0, t0+X], or in the prior X seconds leads to collision

    vulnerable period = [ t0 – X, t0+ X ]

위의 그림은 Unslotted Aloha의 취약구간을 보여준다. L길이 만큼의 패킷이 전송될 동안 앞뒤로 2L길이만큼 다른 노드들의 전송시도가 없어야만 성공적인 전송이 가능하다.

3. Throughput =(def. Number of packets per unit time)

1) Successful throughput : X시간(unit time) 동안의 성공적인 Frame 전송의 평균값을 의미한다.

2) G-load : X시간 동안의 평균적인 전송시도를 의미한다. 

(큰 개념은 굵은 제목들만 봐도 충분히 이해가 된다. 하지만 이를 직접 Code로 구현하기 위해서는 아래의 확률과정에 대해서 충분히 이해해야 한다. G의 개념과 Qa, Qr의 개념만 안다면 코딩가능하다. 필요없는 분은 바로 3)으로 가세요)

"G" refer to the mean used in the Poisson distribution over transmission-attempts that is, on average, there are G transmission-attempts per frame-time in state n.

State (n) of system is number of backlogged nodes.

G(n) = λ + n*Qr

( Qr : re-transmission probability of backlogged stations. ) 

The number of attempted packets per slot in state n is approximately a Poisson random variable of mean g(n)

– P (m attempts) = {(G(n)^k)*exp^-G(n)}/m!

– P (idle) = probability of no attempts in a slot = exp^-G(n)

– p (success) = probability of one attempt in a slot = G(n)*exp^-G(n)

    : idel한 채널상태에서 혼자서 전송을 시도하는 경우 = 성공확률.

– P (collision) = P (two or more attempts) = 1 - P(idle) - P(success)

For any frame-time, the probability of there being k transmission-attempts during that frame-time is: 

{(G^k)*e^(-G)} / k!

If throughput is represented by S, under all load, S = G*Ps, where Ps is the probability that the frame does not suffer collision. A frame does not have collision if no frame are send during the frame time. Thus, in t time Ps=exp^-G.

In pure Aloha, Ps=exp^(-2G), as mean number of frames generated in 2t is 2G. From the above, throughput in pure Aloha S = G*exp^-2G.

*혼잣말: G= a node transmission-attempts , k= k nodes라면.. 2)과 3)의 설명에서 G와 k의 연결고리가 없는 느낌인데..

3) Successful  Probability (Ps): 성공적인 Frame전송의 확률

따라서 Successful throughput = Ps * G-load.가 된다.

if general, if frame arrivals are equally likely at any instant in time, and arrivals occur at an average rate of λ [arrivals per sec]

포아송 프로세스를 따라서 동일 프레임들K개가 T시간동안에 도착한다고 가정한다면, 위의 식으로 표현된다.

in our case, λ=G/X [arrivals per second] and T=2X, hence

그러나 앞서 이야기했듯이 Pure Aloha는 프레임길이의 2배동안 다른 노드들의 프레임전송이 없어야 충돌이 없기 때문에 전송이 성공하기 위한 조건들을 대입하면 아래와 같이 다시 쓸수가 있다. 

accordingly, probability of successful transmission (no collision) is:

이를 푸아송 프로세스의 성질을 이용하여, 어떠한 전송이 없을 확률을 구하면 = 다른 노드들이 모두 전송하지 않을 확률 = 성공확률을 의미한다. 

따라서 Throughput 은 평균적인 전송시도량 * 패킷전송 성공확률로 표현이 된다. 

4. Slotted Aloha

Slotted Aloha는 pure Aloha보다 향상된 성능을 가지는데, 이는 충돌량이 감소했기 때문이다. 

1) Assumption

   - 각각의 슬롯사이즈들은 X=L/R 의 크기로 나눠어 진다. (하나의 프레임전송에 맞는 시간)

   - 노드들은 전송을 슬롯의 시작부분에만 시작한다.

   - 노드들은 동기화를 통해서 슬롯의 시작을  알고있다고 가정한다.      

2) Operation

   (1) when node has a fresh frame to send, it waits until next frame slot and transmits

   (2) if there is a collision, node retransmits the frame after a backoff-time

        (backoff-time = multiples of time-frames)

위의 그림을 보면 왜 Slotted Aloha가 더 좋은 성능을 가지는지 알수있다. 사실 직관적으로 2배정도의 성능을 보일것이라고 생각이 든다.

3) Throughput

packet P will be transmitted successfully if no other packet becomes available for transmission during the same time slot. Pure Aloha에서 전송시 Vulnerable period가 패킷사이즈(L)의 2배시간동안 다른 노드들의 전송이 있다면 충돌이 발생한다고 했다면, Slotted Aloha의 경우는 Packet Size의 길이만큼만 충돌이 없도록 보장이 되기에 2배의 성능을 보인다.

vulnerable period = [ t0 – X, t0 ]

따라서, Slotted ALOHA와  Pure Aloha 의 성능을 비교해보면 아래와 같다. 

Slotted ALOHA의 MAX Throughput 은 G=1일때 0.36을 보인다. 

따라서 실질적인 Channel capacity는 36%이다.  
(legend가 반대로 들어갔습니다. 붉은색 = pure, 파란색이 slotted 입니다. 참고하시길 바랍니다.)

Q. What's the Backlogged packets?

A: 

it's a packet stuck in a buffer, unsent to the recipient because of network congestion. You probably don't see the word much in computer networking because it is used in cellular phone networks. In voice networks, where delivery is time sensitive but dropped packets can be tolerated, a backlogged packet is usually dropped.

네트워크분야에서는, 네트워크의 혼잡으로 (CSMA/CA에서 예를들면, 채널이 busy하거나, 패킷간 충돌이 발생했을때) 인하여 전송하려고 하던 패킷을 버퍼에 넣어두고 기다릴 때 전송지연되는 패킷을 말한다.

ex)

In slotted Aloha, If a transmission has a collision, the node become backlogged. 

What is the meaning of the Intended and Offered Load, Forwarding Rate?

I provide explanation of difference between Intended and Offered load and Forwarding Rates:

I note that the Intended load is what is being asked of the test, versus Offered load which is what the actual physical layer can do. Offered load is what should actual be transmitted.

The Intended Load is the number of frames per second in which an external source attempts to send to a DUT/SUT for forwarding to a specified output interface(s)."

The Offered Load is the number of frames per second that an external source can send to a DUT/SUT for forwarding to a specified output interface(s).

Note: 'There may occur an issue where -> Offered Load appears far too much lower than Intended Load.

I explain this may be causes when choosing -> Test Parameters -> Improve Time to Test -> Skip to next load when iteration fails.

When there is packet loss and because the iteration is configured due to this configuration to abruptly end, the configured rate is not caught by the analyzer.

If this is a concern, I recommend to deselect -> Test Parameters -> Improve Time to Test -> Skip to next load when iteration fails and retest in the same manner.'

The Forwarding Rate is the number of frames per second that a device can successfully send to the correct destination interface in response to a specified offered load.

The throughput is the fastest rate (Offered Load) at which the count of test frames transmitted by the DUT is equal to the number of test frames sent to it by the test equipment.

Site: http://ekb.spirentcom.com/index?page=content&id=FAQ11890&actp=LIST

OSI 7 Layer는 왜 만들어 졌을까?

OSI (Open System Interconnection) 7 Layes...왜 귀찮게 7계층으로 나누었을까?... 그냥 한번에 통신하면 되지..왜 나누었을까?...

7계층은 아래와 같다.

Application

Presentation

Session

Transport

Network

Data Link

Physical

"애-프-스-트-엔-들-피"

이유> 한마디로 "통신의 편리"를 위해서 나누어 놓은 것이다! 단계별접근..심플하지 아니한가요?..

1) 데이터의 흐름이 딱 보인다.

2) 문제 해결이 쉽다 (hierarchical Layer)

3) 표준화를 했기에 여러 브랜드의 상품사용이 가능하다

 예: 데이터케이블 or 허브 - PHY계층

      스위치나 브리지 - Data계층

      라우터 - Network계층

--------------------------------------------------------------------------------------------------------

추가적인 아래의 3계층에 대한 설명

PHY : 전기적,기계적인 특성을 이용하는 계층이다. 즉, 통신 케이블로 데이터를 전송한다. 0 1 0 1 0 1...

이것은 전기적으로 ON/OFF의 반복을 의미하는 것이다. 단지 데이터만을 전달하는 계층이다.

대표적인 통신장비로는 - 케이블, 리피터, 허브 등이 존재한다.

 *리피터 : 장거리 전송 회선의 중간에 삽입하여 신호의 증폭, 파형의 정형 등을 하는 중계장치.

DAT : 안전한 정보전달을 위해서 PHY단을 통하여 송수신 되는 정보의 오류와 흐름을 관리하는 역할을 한다. 

즉, 통신에서 오류검출, 재전송시도, MAC Address 를 통한 통신 을 할수있게 해준다. 전송되는 데이터의 단위는 "프레임"

이라고 부른다.

대표적인 장비로는 - 브리지, 스위치 등이 존재한다.

 *브리지 : 두 개의 LAN을 연결한다는 점에서 리피터(Reapeter)와 같을 수도 있지만, 리피터가 모든 신호를 한꺼번에 보내서 통신량을 증가시키지만, 브리지는 통신량을 조정할 수 있다. 즉 통신하고자 하는 노드가 같은 통신망 안에 있을 경우는 데이터가 다른 통신망으로 전달되지 않도록 한다. 또한 리피터와 마찬가지로 데이터를 재생성할 수 있다는 점에서는 같지만 데이터를 재생성하는 위치가 다르다.

NET : 데이터를 목적지까지 가장 빠르고 안전하게 전달하는 역할을 가지고 있다. =  이과정을 라우팅이라 함.

즉, 경로를 선택 - 주소를 정하고 - 경로에 따라 패킷전송을 해주는 것이다. 

대표적인 장비로는 - 라우터이며 스위치중에서도 라우팅기능을 가진 장비가 존재한다.

출처 : http://blog.naver.com/zizz37?Redirect=Log&logNo=70148414094