[go: up one dir, main page]

KR101524472B1 - 네트워크에서 다중 경로 설정 방법 및 장치 - Google Patents

네트워크에서 다중 경로 설정 방법 및 장치 Download PDF

Info

Publication number
KR101524472B1
KR101524472B1 KR1020140149587A KR20140149587A KR101524472B1 KR 101524472 B1 KR101524472 B1 KR 101524472B1 KR 1020140149587 A KR1020140149587 A KR 1020140149587A KR 20140149587 A KR20140149587 A KR 20140149587A KR 101524472 B1 KR101524472 B1 KR 101524472B1
Authority
KR
South Korea
Prior art keywords
transmission
traffic
information
network
multipath
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020140149587A
Other languages
English (en)
Inventor
정종문
한동혁
Original Assignee
연세대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 연세대학교 산학협력단 filed Critical 연세대학교 산학협력단
Priority to KR1020140149587A priority Critical patent/KR101524472B1/ko
Application granted granted Critical
Publication of KR101524472B1 publication Critical patent/KR101524472B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/24—Multipath
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/121—Shortest path evaluation by minimising delays
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/70—Admission control; Resource allocation

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

네트워크에서 전송 지연을 최소화할 수 있는 다중 경로 설정 방법 및 장치에 관한 기술이 개시된다. 개시된 다중 경로 설정 방법은 상기 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 단계; 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 단계; 및 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하고, 상기 전송 경로에 트래픽을 할당하는 단계를 포함한다.

Description

네트워크에서 다중 경로 설정 방법 및 장치{Method and Device for Routing Multipath of Network}
본 발명은 네트워크에서 다중 경로 설정 방법 및 장치에 관한 것으로서, 더욱 상세하게는 네트워크에서 전송 지연을 최소화할 수 있는 다중 경로 설정 방법 및 장치에 관한 것이다.
네트워크에서 데이터가 전송될 때, 다중 경로 라우팅(Multipath Routing)이 이용된다. 다중 경로 라우팅은 두 단말간 데이터 전송을 위해 다수의 경로를 설정하고 필요한 경로를 데이터 전송에 사용하는 방식으로, 여러 경로 중 일부가 유실되거나 오류가 발생해도 다른 경로에서 데이터 전송이 이루어지므로 데이터 전송이 유지되는 장점이 있다. 다중 경로 라우팅은 2개 이상의 경로를 사용함에 따라 전송 경로의 관리, 전송 스케줄링, 혼잡 제어 기술 등 다양한 기술의 최적화가 필요한 기술이다.
다중 경로 라우팅 프로토콜로는, IETF에서 2000년 10월에 RFC 2960으로 제정한 SCTP (Stream Control Transmission Protocol), RFC 6824로 제정한 MPTCP (Multipath Transmission Control Protocol), AODV (Ad hoc On-Demand Distance Vector) 프로토콜을 다중 경로를 위해 확장한 AOMDV (Ad hoc On-Demand Multipath Distance Vector) 프로토콜 등이 있다.
그리고 다중 경로 라우팅 프로토콜에 따라 다중 경로가 설정된 이후, 다중 경로에 트래픽을 분배하기 위한 알고리즘으로, ADM (Average Delay Minimisation) 알고리즘 및 MDM (Maximum Delay Minimisation) 알고리즘이 있다. AMD 알고리즘 및 MDM 알고리즘은 네트워크 트래픽이 포아송 분포(Poisson Distribution)를 따르는 것을 가정하며, ADM 알고리즘은 다중 경로의 평균 시간 지연을 최소화하며 MDM은 다중 경로의 최대 시간 지연을 최소화할 수 있다.
그러나, 실제 네트워크의 트래픽은 자기 유사(self-similar) 특성을 가지므로 ADM 및 MDM 알고리즘에 따라 트래픽 분배가 이루어질 경우, 잘못된 트래픽 모델링으로 인해 최적화가 이루어지지 않는 단점이 있다.
이와 관련된 선행 문헌으로, 대한민국 공개특허 제2003-0033711호(공개일: 2003.05.01)가 있다.
본 발명은 네트워크에서 전송 지연을 최소화할 수 있는 다중 경로 설정 방법 및 장치를 제공하기 위한 것이다.
상기한 목적을 달성하기 위해 본 발명의 일 실시예에 따르면, 상기 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 단계; 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 단계; 및 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하고, 상기 전송 경로에 트래픽을 할당하는 단계를 포함하는 네트워크에서 다중 경로 설정 방법을 제공한다.
또한 상기한 목적을 달성하기 위해 본 발명의 다른 실시예에 따르면, 상기 네트워크 링크의 큐 길이에 따라, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 단계; 상기 네트워크 링크의 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하는 단계; 및 상기 네트워크의 자기 유사성 정보 및 상기 전송 용량 정보를 이용하여, 상기 전송 경로에 트래픽을 할당하는 단계
또한 상기한 목적을 달성하기 위해 본 발명의 또 다른 실시예에 따르면, 데이터를 수신하는 단계; 상기 데이터를 이용하여, 상기 노드의 자기 유사성 정보를 생성하는 단계; 상기 자기 유사성 정보 및 상기 노드의 전송 용량 정보를 포함하는 메시지를 생성하는 단계; 및 상기 메시지를 기 설정된 노드로 전송하는 단계를 포함하는 네트워크 노드의 다중 경로 설정 방법을 제공한다.
또한 상기한 목적을 달성하기 위해 본 발명의 또 다른 실시예에 따르면, 상기 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 정보 생성부; 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 판단부; 및 상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하고, 상기 전송 경로에 트래픽을 할당하는 경로 설정부를 포함하는 네트워크의 다중 경로 설정 장치를 제공한다.
본 발명에 따르면, 네트워크에서 목적지 노드까지의 전송 지연을 최소화할 수 있는 다중 경로를 설정할 수 있다.
또한 본 발명에 따르면, 전송 지연을 최소화하는 데이터 전송 경로의 개수를 먼저 산출하고, 산출된 개수 이하로 전송 경로를 선정하고 트래픽을 할당함으로써, 최적의 다중 전송 경로를 설정하기 위해 필요한 연산량 및 시간을 감소시킬 수 있다.
도 1은 본 발명에 따른 다중 경로 설정 방법의 개념을 설명하기 위한 도면이다.
도 2는 본 발명의 일실시예에 따른 다중 경로 설정 방법을 설명하기 위한 도면이다.
도 3은 본 발명의 일실시예에 따른, 노드 사이에서 교환되는 메시지를 설명하기 위한 도면이다.
도 4 및 도 5는 본 발명의 일실시예에 따른 다중 경로 설정 방법(SDM)과, ADM 및 MDM 알고리즘의 성능을 비교하기 위한 도면이다.
도 6은 본 발명의 일실시예에 따른 다중 경로 설정 장치를 설명하기 위한 도면이다.
도 7은 본 발명의 구체적 실시예에 따른 다중 경로 설정 장치를 설명하기 위한 도면이다.
본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 각 도면을 설명하면서 유사한 참조부호를 유사한 구성요소에 대해 사용하였다.
도 1은 본 발명에 따른 다중 경로 설정 방법의 개념을 설명하기 위한 도면이다. 도 1에서는 17개의 라우터로 구성된 네트워크가 일실시예로서 설명된다.
도 1에 도시된 바와 같이, 각각의 노드(라우터 또는 사용자 단말) 사이에는 복수의 데이터 전송 경로가 존재할 수 있다. 그리고 예를 들어, 제1노드에서 제8노드까지 데이터가 전송될 경우, 하나의 경로로만 데이터가 전송되는 것이 아니라, 복수의 데이터 전송 경로 중에 하나 이상의 경로가 선택되어 트래픽이 할당되어 선택된 경로로 데이터가 전송된다.
본 발명은 네트워크에 존재하는 복수의 데이터 전송 경로 중에서, 전송 지연 시간을 최소화할 수 있는 다중 경로 설정 방법을 제공한다. 도 1에 도시된 바와 같이, 노드 사이의 전송 경로는 매우 많기 때문에, 최적의 전송 경로를 설정하기 위해 상당한 연산 및 시간이 필요한데, 본 발명은 최적의 경로를 설정하는데 필요한 연산 시간을 감소시킬 수 있다. 이를 위해, 본 발명은 전송 지연을 최소화하는 데이터 전송 경로의 개수를 먼저 산출하고, 산출된 개수 이하로 전송 경로를 선정하고 트래픽을 할당한다.
본 발명에 따른 다중 경로 설정 방법은 네트워크의 노드에서 수행될 수 있으며, 근원지 노드나 목적지 노드에서 모두 수행될 수 있다. 또한 네트워크의 노드는 라우터 또는 라우터와 연결된 사용자 단말일 수 있다.
이하에서, 본 발명에 따른 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다.
도 2는 본 발명의 일실시예에 따른 다중 경로 설정 방법을 설명하기 위한 도면이다.
본 발명에 따른 라우터는 네트워크의 자기 유사성 정보(self-similarity) 및 네트워크 링크의 전송 용량 정보를 생성(S201)한다. 라우터는 네트워크의 다른 노드로부터 트래픽 정보 및 네트워크 정보를 수신하여, 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성할 수 있다. 트래픽 정보 및 네트워크 정보는 메시지 형태로 송수신될 수 있다.
자기 유사성 정보는 트래픽 관련 정보로서, 트래픽의 표준 편차, 트래픽의 평균 전송 속도, 오버플로우 확률 및 허스트(Hurst) 파라미터를 포함할 수 있다. 허스트 파라미터는 자기 유사의 정도를 나타내는 파라미터이다. 전송 용량 정보는 링크의 평균 전송 용량에 대한 정보일 수 있다.
라우터는 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단(S203)한다. 라우터는 자기 유사성 정보 및 전송 용량 정보를 이용하여 각 링크의 큐 길이를 계산할 수 있으며, 잔여 큐 길이가 가장 작은, 즉 로드가 작은 링크를 전송 지연을 최소화하는 데이터 전송 경로로 판단한다. 예를 들어, 데이터 전송 경로의 개수가 5개로 결정되면, 후술되는 단계 S205에서 라우터는 5개 이하의 전송 경로를 선택하고 트래픽을 할당할 수 있다.
라우터는 일실시예로서, 컨벡스 최적화 알고리즘에 따라 데이터 전송 경로의 개수를 판단할 수 있다. i번째 전송 경로의 트래픽 평균 전달 속도를
Figure 112014104814142-pat00001
, 트래픽 표준 편차를
Figure 112014104814142-pat00002
, 트래픽 분배율을
Figure 112014104814142-pat00003
, Hurst parameter를
Figure 112014104814142-pat00004
, 오버플로우 확률을
Figure 112014104814142-pat00005
, 각 링크(u,v)의 전송 용량(캐패시티)를
Figure 112014104814142-pat00006
라 할 때, 각 링크의 큐 길이
Figure 112014104814142-pat00007
는 [수학식 1]과 같이 구할 수 있다. 여기서, 트래픽 분배율은 기 설정된 값으로 할당될 수 있으며, 예를 들어 균등하게 분포되는 값으로 설정될 수 있다.
Figure 112014104814142-pat00008
표현의 간략화를 위해
Figure 112014104814142-pat00009
를 정의하면, n개의 전송 경로를 구성하는 링크의 큐 길이를 합산한 값과 대응되는, 전송 지연 시간 d(n)은 [수학식 2]와 같이 얻을 수 있다. 즉, d(1)은 제1경로를 구성하는 링크의 큐 길이를 합산한 값이 되며, d(2)는 제2경로를 구성하는 링크의 큐 길이를 합산한 값이 된다.
Figure 112014104814142-pat00010
모든 링크 (u,v)의 캐패시티(
Figure 112014104814142-pat00011
)는 평균 캐패시티(
Figure 112014104814142-pat00012
) 및 종단간 평균 홉 수(l)로 추정될 수 있으며, 이에 따라 [수학식 2]는 아래 [수학식 3]과 같이 표현될 수 있다.
Figure 112014104814142-pat00013
Figure 112014104814142-pat00014
은 평균 캐패시티 값을 이용한 d(n)의 추정치로 그 값의 차이가 있으나, 그 차이
Figure 112014104814142-pat00015
값은 고정 값으로 수렴한다. 즉, 링크 캐패시티의 최소값을
Figure 112014104814142-pat00016
이라할 때
Figure 112014104814142-pat00017
가 성립하며, 링크 캐패시티의 최대값을
Figure 112014104814142-pat00018
라 할 때
Figure 112014104814142-pat00019
가 성립하므로
Figure 112014104814142-pat00020
는
Figure 112014104814142-pat00021
보다 작은 값을 가진다.
이 때,
Figure 112014104814142-pat00022
는 컨벡스 함수이므로 전송 경로의 수 n에 대해 다음과 같이 컨벡스 최적화를 수행할 수 있다.
Figure 112014104814142-pat00023
을 n에 대해 미분한 함수
Figure 112014104814142-pat00024
는
Figure 112014104814142-pat00025
일 때 그 값이 0이 되며, 미분값
Figure 112014104814142-pat00026
이 성립하는 n은 전송 경로의 전송 지연 시간(
Figure 112014104814142-pat00027
)을 최소화 하는 경로의 개수가 된다. 이로부터, 전송 경로의 전송 지연 시간 추정값(
Figure 112014104814142-pat00028
)을 최소화하는 데이터 전송 경로의 개수(
Figure 112014104814142-pat00029
)를 [수학식 4]와 같이 구할 수 있다.
Figure 112014104814142-pat00030
여기서,
Figure 112014104814142-pat00031
는 천장 함수(ceiling function)로
Figure 112014104814142-pat00032
와 같이 정의되며, Z는 정수의 집합이다.
라우터는 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 이용하여, 단계 S203에서 판단된 데이터 전송 경로의 개수 이하로, 전송 경로를 설정하고, 설정된 전송 경로에 트래픽을 할당(S205)한다. 보다 구체적으로 라우터는 전송 용량 정보를 이용하여, 최소 비용 경로인 전송 경로를 설정하며, 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 경로에 트래픽을 할당한다.
라우터는 일실시예로서, Suurballe 알고리즘에 따라, 링크의 전송 용량의 역수를 라우팅 비용으로 계산하여 최소 비용 경로를 판단할 수 있다. 즉, 전송 용량과 라우팅 비용은 반비례 관계이다. 예를 들어, 네트워크의 총 전송 경로가 100개이고, 전송 지연을 최소화하는 전송 경로의 개수가 5개일 경우, 라우터는 라우팅 비용이 최소가 될 수 있는 5개 또는 그 이하의 전송 경로 집합을 전송 경로로 설정하고, 이와 같이 설정된 전송 경로가 최소 비용 경로가 된다.
이후 라우터는 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 경로에 트래픽을 할당한다. 보다 구체적으로 라우터는 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 트래픽 분배율을 산출하고, 트래픽 분배율에 따라 트래픽을 설정된 전송 경로에 할당한다. 라우터는 일실시예로서, 게임 이론에 따라 트래픽 분배율을 산출하여 트래픽을 할당할 수 있다.
최소 비용 경로 집합에 포함된 n 개의 전송 경로가 협력하여 데이터를 전송할 때의 전송 시간 지연에 대한 이득(
Figure 112014104814142-pat00033
)은 [수학식 5]와 같이 정의될 수 있다. 전송 경로의 협력 함수
Figure 112014104814142-pat00034
를 위해 i번째 전송 경로에 대한 트래픽 분배
Figure 112014104814142-pat00035
의 초기값은 균등 배분 1/n이며, 트래픽의 표준편차
Figure 112014104814142-pat00036
는
Figure 112014104814142-pat00037
라 가정한다. 즉, 트래픽은 균등분포(Uniform Distribution)를 따른다.
Figure 112014104814142-pat00038
여기서, S는 전송 경로간의 협력 집합(coalition set)을 나타내며 A는 모든 협력 집합(grand coalition set)을 나타낸다. 예를 들어, 전송 경로(n)가 3개일 때, S는
Figure 112014104814142-pat00039
,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}이며, A는 {
Figure 112014104814142-pat00040
,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}일 수 있다.
상기 [수학식 5]로부터 [수학식 6]과 같이 Shapley value를 구할 수 있다. Shapley value는 전송 경로 협력에 대한 효용이 최대가 되는 해, 즉 전송 시간 지연이 최소가 되는 해를 나타낸다. 각 전송 경로에 분배되는 트래픽 비율
Figure 112014104814142-pat00041
는 Shapley value로 설정된다.
Figure 112014104814142-pat00042
여기서,
Figure 112014104814142-pat00043
는
Figure 112014104814142-pat00044
번째 경로에 대한 Shapley value를 의미한다.
전술된 바와 같이, 본 발명에 따르면 전송 지연을 최소화할 수 있는 다중 전송 경로를 설정할 수 있으며, 전송 지연을 최소화하는 데이터 전송 경로의 개수를 먼저 산출하고, 산출된 개수 이하로 전송 경로를 선정하고 트래픽을 할당함으로써, 최적의 다중 전송 경로를 설정하기 위해 필요한 연산량 및 시간을 감소시킬 수 있다.
또한 본 발명에 따르면, 큐 길이가 작고 전송 지연이 작은 경로를 선택하여 패킷을 전송하므로, 라우터의 평균 큐 길이가 줄어들고 따라서 무작위 조기 탐지(RED, Random Early Detection), 큐 관리 기법 등에 의한 패킷 탈락이 줄어들어, 전송 신뢰도를 보장할 수 있다.
한편, 통신 환경의 작은 변화에 민감하게 반응하여 데이터 전송 경로를 재계산할 경우, 잦은 전송 경로 재설정으로 네트워크 불안정(instability)이 야기될 수 있다. 반대로, 통신 환경에 변화에 둔감하게 반응하는 경우 네트워크 및 단말이 경험하는 종단간 시간 지연이 최적해와 큰 차이가 날 수 있다.
본 발명의 일실시예에 따른 다중 경로 설정 방법은, 보다 효율적으로 다중 경로를 설정하기 위해, 전송 지연 시간의 변화율이 기 설정된 임계 범위를 초과하는지 여부를 판단하는 단계를 더 포함할 수 있다. 그리고 라우터는 임계 범위 초과 여부에 따라 데이터 전송 경로의 개수를 갱신할 수 있다.
즉, 본 발명은 네트워크 환경이 변화하여 설정된 전송 경로에서 전송 시간 지연이 증가 또는 감소할 경우에, 전송 지연 시간의 변화율이 기 설정된 임계 범위를 초과하는지 여부에 따라 데이터 전송 경로의 개수를 다시 판단하고 전송 경로를 다시 설정하고 트래픽을 할당한다.
전송 지연 시간의 변화율은 [수학식 7]과 같이 나태낼 수 있으며, [수학식 3]으로부터 도출될 수 있다.
Figure 112014104814142-pat00045
여기서,
Figure 112014104814142-pat00046
과
Figure 112014104814142-pat00047
는 각각 임계 범위의 하한(lower bound) 및 상한(upper bound)를 의미하며,
Figure 112014104814142-pat00048
은 변화한 트래픽의 평균 전달 속도를 의미한다.
도 3은 본 발명의 일실시예에 따른, 노드 사이에서 교환되는 메시지를 설명하기 위한 도면이다.
도 3에 도시된 메시지에서, Hop Count, Prefix Size, Destination IP Address, Destination Sequence Number, Originator IP Address, Originator Sequence Number 필드는 종래 라우팅에서 사용되는 메시지에 포함된 필드이다. 본 발명에 따른 메시지 필드는 노드의 자기 유사성 정보 및 노드의 전송 용량 정보를 포함한다. 자기 유사성 정보는 전술된 트래픽 평균 전달 속도(
Figure 112014104814142-pat00049
), 트래픽 표준 편차(
Figure 112014104814142-pat00050
), 허스트 파라미터(
Figure 112014104814142-pat00051
), 오버플로우 확률(
Figure 112014104814142-pat00052
)를 포함한다. 오버플로우 확률이란 노드로 입력되는 트래픽에 의한 데이터가 해당 노드의 큐 길이보다 길 확률을 나타낸다.
본 발명의 일실시예에 따르면, 네트워크의 노드는 트래픽 발생에 따라 수신되는 데이터를 이용하여, 노드의 자기 유사성 정보를 생성한다. 그리고 노드의 자기 유사성 정보 및 노드의 전송 용량 정보를 포함하는 메시지를 생성하여 기 설정된 노드로 전송한다.
본 발명에 따른 메시지를 수신한 노드는 네트워크를 구성하는 노드의 트래픽 정보 및 네트워크 정보를 이용하여 자기 유사성 정보 및 네트워크의 전송 용량 정보를 생성하여, 본 발명에 따라 다중 경로를 설정할 수 있다.
도 4 및 도 5는 본 발명의 일실시예에 따른 다중 경로 설정 방법(SDM)과, ADM 및 MDM 알고리즘의 성능을 비교하기 위한 도면으로서, 도 1에 도시된 네트워크 상에서 시뮬레이션된 결과를 나타낸다.
보다 자세히, 도 1의 네트워크는 광 네트워크(optical network)로서, 17개의 라우터를 포함하며, Carrier 3 (OC-3)로 155.52 Mbps의 전송율을 지원하는 백본 네트워크 및 균일 랜덤 분포(uniform random distribution)에 따라 40개의 노드로 구성된 랜덤 네트워크로 이루어진다.
도 4는 트래픽 평균 전달 속도(
Figure 112014104814142-pat00053
)를 1 Gbps에서 4 Gbps까지 변화시키며 속도 변화에 따른 종단간 시간 지연 결과를 분석한 시뮬레이션 결과이다. 백본 네트워크에서 트래픽 평균 전달 속도(
Figure 112014104814142-pat00054
)가 4 Gbps일 때 SDM은 4.76 초의 전송 시간 지연을 보이며, MDM은 12.39 초, ADM은 9.97초의 전송 시간 지연 성능을 보인다. 랜덤 네트워크에서 트래픽 평균 전달 속도(
Figure 112014104814142-pat00055
)가 4 Gbps일 때 SDM은 2.63 초, MDM은 5.85 초, ADM은 4.27 초의 시간 지연을 보인다. 1~4 Gbps에서의 시간 지연 성능 평균을 비교할 때, 백본 네트워크에서 SDM의 전송 지연 시간은 MDM과 ADM에 비해 각각 51.40%, 66.06% 단축되며, 랜덤 네트워크에서 SDM의 전송 지연 시간은 MDM과 ADM에 비해 각각 32.47%, 45.80% 단축된다.
도 5는 트래픽 평균전달 속도(
Figure 112014104814142-pat00056
)를 1 Gbps에서 4 Gbps까지 변화해갈 때, 백본 네트워크와 랜덤 네트워크에서 RED에 의한 패킷 손실을 0 초에서 10,000 초까지 관찰한 시뮬레이션 결과이다. 백본 네트워크에서 SDM의 패킷 손실율은 MDM, ADM의 패킷 손실율의 74.44%, 67.78%에 해당하며, 랜덤 네트워크에서 SDM의 패킷 손실율은 MDM, ADM의 패킷 손실율의 77.08%, 68.21%에 해당한다.
도 6은 본 발명의 일실시예에 따른 다중 경로 설정 장치를 설명하기 위한 도면이다.
도 6에 도시된 바와 같이, 본 발명에 따른 다중 경로 설정 장치는 정보 생성부(601), 판단부(603) 및 경로 설정부(605)를 포함한다.
정보 생성부(601)는 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성한다. 정보 생성부(601)는 다른 노드로부터 트래픽 관련 정보 및 전송 용량 정보를 수신하여 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성할 수 있다.
판단부(603)는 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단한다. 그리고 경로 설정부(605)는 자기 유사성 정보 및 전송 용량 정보를 이용하여, 판단된 개수 이하로, 다중 전송 경로를 설정하고, 다중 전송 경로에 트래픽을 할당한다.
한편, 본 발명에 따른 다중 경로 설정 장치의 판단부(603)는 전송 지연 시간의 변화율이 기 설정된 임계 범위를 초과하는지 여부를 판단할 수 있으며, 임계 범위 초과 여부에 따라 데이터 전송 경로의 개수를 갱신할 수 있다.
도 7은 본 발명의 구체적 실시예에 따른 다중 경로 설정 장치를 설명하기 위한 도면이다.
도 7에 도시된 바와 같이, 본 발명에 따른 다중 경로 설정 장치는 통신부(710), 프로세서부(720) 및 전력 공급부(730)를 포함한다.
통신부(710)는 주변 노드와의 데이터 송수신을 위한 입출력 인터페이스를 포함할 수 있다. 통신부(710)는 프로세서부(720)의 제어에 따라 데이터를 전송하며, 수신한 데이터를 프로세서부(720)로 전달한다.
프로세서부(720)는 컨트롤러(721) 및 저장부(729)를 포함한다. 컨트롤러(721)는 네트워크 상태와 트래픽 파라미터를 스캐닝하여, 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 정보 생성부(723), 자기 유사성 정보 및 전송 용량 정보를 이용하여 컨벡스 최적화를 수행하고 목적지 노드까지의 전송 지연 시간을 최소화하는 데이터 전송 경로의 개수를 판단하는 판단부(725) 및 자기 유사성 정보 및 전송 용량 정보를 이용하여, 최소 비용 경로 집합을 전송 경로로 설정하고, 설정된 전송 경로에 게임 이론에 따라 트래픽을 할당하는 전송 경로 설정부(727)를 포함한다. 저장부(729)는 컨트롤러(721)에 의해 처리된 데이터 및 통신부(710)를 통해 수신된 데이터를 저장한다.
전력 공급부(730)는 통신부(710) 및 프로세서부(720)로 전력을 공급한다.
앞서 설명한 기술적 내용들은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 실시예들을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 하드웨어 장치는 실시예들의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
이상과 같이 본 발명에서는 구체적인 구성 요소 등과 같은 특정 사항들과 한정된 실시예 및 도면에 의해 설명되었으나 이는 본 발명의 보다 전반적인 이해를 돕기 위해서 제공된 것일 뿐, 본 발명은 상기의 실시예에 한정되는 것은 아니며, 본 발명이 속하는 분야에서 통상적인 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형이 가능하다. 따라서, 본 발명의 사상은 설명된 실시예에 국한되어 정해져서는 아니되며, 후술하는 특허청구범위뿐 아니라 이 특허청구범위와 균등하거나 등가적 변형이 있는 모든 것들은 본 발명 사상의 범주에 속한다고 할 것이다.

Claims (13)

  1. 네트워크에서 다중 경로 설정 방법에 있어서,
    상기 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 단계;
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 단계; 및
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하고, 상기 전송 경로에 트래픽을 할당하는 단계를 포함하며,
    상기 전송 경로에 트래픽을 할당하는 단계는
    상기 전송 용량 정보를 이용하여, 최소 비용 경로 집합을 상기 전송 경로로 설정하는 단계; 및
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 전송 경로에 트래픽을 할당하는 단계
    를 포함하는 다중 경로 설정 방법.
  2. 삭제
  3. 제 1항에 있어서,
    상기 전송 경로에 트래픽을 할당하는 단계는
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 전송 지연을 최소화하는 트래픽 분배율을 산출하는 단계; 및
    상기 트래픽 분배율에 따라 상기 트래픽을 할당하는 단계
    를 포함하는 다중 경로 설정 방법.
  4. 제 1항에 있어서,
    상기 전송 경로에 트래픽을 할당하는 단계는
    게임 이론에 따라 상기 트래픽을 할당하는
    다중 경로 설정 방법.
  5. 제 1항에 있어서,
    상기 자기 유사성 정보는
    트래픽의 표준 편차, 트래픽의 평균 전송 속도, 오버플로우 확률 및 허스트(Hurst) 파라미터
    를 포함하는 다중 경로 설정 방법.
  6. 제 1항에 있어서,
    상기 전송 지연 시간의 변화율이 기 설정된 임계 범위를 초과하는지 여부를 판단하는 단계를 더 포함하며,
    상기 데이터 전송 경로의 개수를 판단하는 단계는
    상기 임계 범위의 초과 여부에 따라, 상기 데이터 전송 경로의 개수를 갱신하는
    다중 경로 설정 방법.
  7. 제 1항에 있어서,
    상기 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로는
    상기 네트워크 링크의 큐 길이에 따라 결정되는
    다중 경로 설정 방법.
  8. 제 1항에 있어서,
    상기 데이터 전송 경로의 개수를 판단하는 단계는
    컨벡스 최적화 알고리즘에 따라, 상기 데이터 전송 경로의 개수를 판단하는
    다중 경로 설정 방법.
  9. 네트워크에서 다중 경로 설정 방법에 있어서,
    상기 네트워크 링크의 큐 길이에 따라, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 단계; 및
    상기 네트워크 링크의 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하는 단계; 및
    상기 네트워크의 자기 유사성 정보 및 상기 전송 용량 정보를 이용하여, 상기 전송 경로에 트래픽을 할당하는 단계
    를 포함하는 다중 경로 설정 방법.
  10. 삭제
  11. 삭제
  12. 네트워크의 다중 경로 설정 장치에 있어서,
    상기 네트워크의 자기 유사성 정보 및 네트워크 링크의 전송 용량 정보를 생성하는 정보 생성부;
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 전송 지연을 최소화하는 목적지 노드까지의 데이터 전송 경로의 개수를 판단하는 판단부; 및
    상기 자기 유사성 정보 및 전송 용량 정보를 이용하여, 상기 개수 이하로, 전송 경로를 설정하고, 상기 전송 경로에 트래픽을 할당하는 경로 설정부를 포함하며,
    상기 판단부는
    상기 전송 지연 시간의 변화율이 기 설정된 임계 범위를 초과하는지 여부를 판단하며, 상기 임계 범위 초과 여부에 따라 상기 데이터 전송 경로의 개수를 갱신하는
    다중 경로 설정 장치.
  13. 제 12항에 있어서,
    상기 다중 경로 설정 장치는
    라우터 또는 상기 라우터와 연결된 사용자 단말인
    다중 경로 설정 장치.
KR1020140149587A 2014-10-30 2014-10-30 네트워크에서 다중 경로 설정 방법 및 장치 Expired - Fee Related KR101524472B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020140149587A KR101524472B1 (ko) 2014-10-30 2014-10-30 네트워크에서 다중 경로 설정 방법 및 장치

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020140149587A KR101524472B1 (ko) 2014-10-30 2014-10-30 네트워크에서 다중 경로 설정 방법 및 장치

Publications (1)

Publication Number Publication Date
KR101524472B1 true KR101524472B1 (ko) 2015-06-02

Family

ID=53490858

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020140149587A Expired - Fee Related KR101524472B1 (ko) 2014-10-30 2014-10-30 네트워크에서 다중 경로 설정 방법 및 장치

Country Status (1)

Country Link
KR (1) KR101524472B1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017150946A1 (ko) * 2016-03-04 2017-09-08 삼성전자 주식회사 적응적 스트리밍 서비스에서 데이터 버퍼링 방법 및 장치

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20030017477A (ko) * 2000-03-15 2003-03-03 인포심 네트워킹 솔루션스 아게 데이터 트래픽 제어 방법 및 시스템
KR20130020862A (ko) * 2011-08-19 2013-03-04 고려대학교 산학협력단 자기 유사성을 이용한 ｓｃａｄａ 네트워크의 이상증후를 탐지하는 장치 및 방법

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20030017477A (ko) * 2000-03-15 2003-03-03 인포심 네트워킹 솔루션스 아게 데이터 트래픽 제어 방법 및 시스템
KR20130020862A (ko) * 2011-08-19 2013-03-04 고려대학교 산학협력단 자기 유사성을 이용한 ｓｃａｄａ 네트워크의 이상증후를 탐지하는 장치 및 방법

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017150946A1 (ko) * 2016-03-04 2017-09-08 삼성전자 주식회사 적응적 스트리밍 서비스에서 데이터 버퍼링 방법 및 장치
KR20170103542A (ko) * 2016-03-04 2017-09-13 삼성전자주식회사 적응적 스트리밍 서비스에서 데이터 버퍼링 방법 및 장치
US11082474B2 (en) 2016-03-04 2021-08-03 Samsung Electronics Co., Ltd. Data buffering method and apparatus in adaptive streaming service
KR102399082B1 (ko) * 2016-03-04 2022-05-17 삼성전자주식회사 적응적 스트리밍 서비스에서 데이터 버퍼링 방법 및 장치

Similar Documents

Publication Publication Date Title
US9325626B2 (en) Method and apparatus to reduce cumulative effect of dynamic metric advertisement in smart grid/sensor networks
JP5021769B2 (ja) マルチラジオ・マルチチャネル・マルチホップ無線ネットワークのための無線・帯域幅認識型ルーティング・メトリック
JP5235622B2 (ja) 通信ネットワークにおける経路付け及び負荷バランシングのための方法
WO2014112250A1 (en) Node and method for routing packets based on measured workload of node in low-power and lossy network
KR101892262B1 (ko) Dodag 구조 기반의 배압 라우팅 방법 및 장치
KR20120017972A (ko) 무선 메쉬 네트워크에서 데이터 전송의 혼잡 상황을 통지/회피하는 방법 및 이를 위한 메쉬 노드
KR101524472B1 (ko) 네트워크에서 다중 경로 설정 방법 및 장치
Ashfaq et al. Optimizing message delivery in opportunistic networks with replication-based forwarding
Lin et al. An efficient traffic control system using dynamic thresholding techniques in wireless mesh networks
Wang et al. Performance modeling and analysis of multi-path routing in integrated fiber-wireless networks
KR101460879B1 (ko) 애드혹 네트워크에서 메시지 라우팅 방법 및 그 장치
Blywis et al. Gossip routing, percolation, and restart in wireless multi-hop networks
JP6558728B2 (ja) 無線メッシュネットワークシステム
Osunade A packet routing model for computer networks
Okamura et al. Opportunistic routing for heterogeneous IoT networks
Gálvez et al. A feedback-based adaptive online algorithm for multi-gateway load-balancing in wireless mesh networks
Guidoum et al. Enhancing performance AODV routing protocol to avoid congestion
JP2013197734A (ja) 経路選択装置、経路選択方法および経路選択プログラム
KR101670809B1 (ko) 다중 홉 구조 무선통신 시스템에서 부하 분산을 고려한 부모 노드 선택 방법 및 이를 위한 장치
WO2018006619A1 (zh) 传输路径的负载信息的方法和网络节点
Biradar et al. Multipath Load Balancing in MANET via Hybrid Intelligent Algorithm
Sharma et al. Congestion Aware Link Cost Routing for MANETS
KR101489674B1 (ko) 부하 분산을 위한 다중 경로 지역 최적화 기법
Rahem et al. Node Cooperation to Avoid Early Congestion Detection Based on Cross-Layer for Wireless Ad Hoc Networks.
Bhardwaj et al. Congestion aware multi-path routing protocol for mobile ad-hoc networks

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20141030

PA0201 Request for examination
PA0302 Request for accelerated examination

Patent event date: 20141217

Patent event code: PA03022R01D

Comment text: Request for Accelerated Examination

Patent event date: 20141030

Patent event code: PA03021R01I

Comment text: Patent Application

PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20150119

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20150518

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20150526

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20150526

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

Termination category: Default of registration fee

Termination date: 20190306