[go: up one dir, main page]

KR102018093B1 - 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법 - Google Patents

네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법 Download PDF

Info

Publication number
KR102018093B1
KR102018093B1 KR1020180137019A KR20180137019A KR102018093B1 KR 102018093 B1 KR102018093 B1 KR 102018093B1 KR 1020180137019 A KR1020180137019 A KR 1020180137019A KR 20180137019 A KR20180137019 A KR 20180137019A KR 102018093 B1 KR102018093 B1 KR 102018093B1
Authority
KR
South Korea
Prior art keywords
spanning tree
node
network
nodes
information
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
KR1020180137019A
Other languages
English (en)
Other versions
KR20190063389A (ko
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 한국항공대학교산학협력단
Publication of KR20190063389A publication Critical patent/KR20190063389A/ko
Application granted granted Critical
Publication of KR102018093B1 publication Critical patent/KR102018093B1/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/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H04L12/44—Star or tree networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing data switching networks
    • H04L43/08—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
    • H04L43/0876—Network utilisation, e.g. volume of load or congestion level
    • 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/64—Routing or path finding of packets in data switching networks using an overlay routing layer

Landscapes

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

Abstract

네트워크에서의 스패닝 트리 형성 방법에 관한 것이며, 네트워크에서의 스패닝 트리 형성 방법은, (a) 이더넷 기반 망 내의 어느 하나의 노드가, 상기 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 상기 망 내의 다른 노드들과 교환하며 수집하는 단계; (b) 상기 어느 하나의 노드가, 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하고, 생성된 상기 자신을 루트로 하는 스패닝 트리 정보를 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계; 및 (c) 상기 어느 하나의 노드가, 선택된 스패닝 트리 정보를 상기 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계를 포함할 수 있다.

Description

네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법 {NODE APPARATUS FOR COMPOSITING SPANNING TREE IN NETWORK AND METHOD OF COMPOSITING SPANNING TREE IN NETWORK USING THE THEORY}
본원은 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법에 관한 것으로서, 특히 트래픽 부하를 고려한 오버레이 스패닝 트리를 형성하기 위한 노드 장치 및 그를 이용한 오버레이 스패닝 트리 형성 방법에 관한 것이다.
스패닝 트리(Spanning Tree)는 망 내의 모든 노드들을 연결하면서 loop-free를 보장하며, 이러한 성질 때문에 네트워크 구성에 널리 쓰인다.
이더넷(Ethernet)에서는 loop-free를 위하여 스패닝 트리 프로토콜(Spanning Tree Protocol, STP) 기술이 존재하며, 장애 발생시 스패닝 트리의 빠른 재구성을 위하여 Rapid Spanning Tree Procol(RSTP)이 규정되어 있다. STP에서는 스패닝 트리를 생성하기 위해 루트 노드를 먼저 정하며, 네트워크의 다른 노드들은 루트 노드로의 최단 경로로 연결한다.
한편, 최적 스패닝 트리에 대한 연구는 과거부터 널리 수행되어 왔으며, 스패닝 트리를 구성하는 링크들의 비용의 합이 최소가 되는 최소 스패닝 트리(Minimum Spanning Tree, MST)의 도출에 대한 많은 알고리즘들이 존재한다. 그런데, 네트워크에서는 스패닝 트리의 구성(형성 구조)에 따라 스패닝 트리를 통해 전달되는 전체 트래픽의 부하가 달라짐에도 불구하고, 종래에는 이를 고려한 스패닝 트리의 구성(형성) 기술이 특별히 존재하지 않는 실정이다.
본원의 배경이 되는 기술은 한국공개특허공보 제10-2005-0116363호에 개시되어 있다.
본원은 전술한 종래 기술의 문제점을 해결하기 위한 것으로서, 스패닝 트리의 구성(형성 구조)에 따라 스패닝 트리를 통해 전달되는 전체 트래픽의 부하가 달라짐을 고려하여, 트래픽 부하를 고려한 오버레이 스패닝 트리의 구성할 수 있는 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법을 제공하려는 것을 목적으로 한다.
본원은 기반망이 주어진 상황에서 스패닝 트리를 통해 전송되는 총 트래픽의 양을 최소화하는 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법을 제공하려는 것을 목적으로 한다.
본원은 망 내의 두 노드들의 쌍마다 전달되는 트래픽 양이 주어지고 트래픽 전송이 스패닝 트리를 통해서 이루어지는 경우에, 총 트래픽 전송량을 최소로 하는 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법을 제공하려는 것을 목적으로 한다.
다만, 본원의 실시예가 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제들로 한정되지 않으며, 또 다른 기술적 과제들이 존재할 수 있다.
상기한 기술적 과제를 달성하기 위한 기술적 수단으로서, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법은, (a) 이더넷 기반 망 내의 어느 하나의 노드가, 상기 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 상기 망 내의 다른 노드들과 교환하며 수집하는 단계; (b) 상기 어느 하나의 노드가, 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하고, 생성된 상기 자신을 루트로 하는 스패닝 트리 정보를 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계; 및 (c) 상기 어느 하나의 노드가, 선택된 스패닝 트리 정보를 상기 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계를 포함할 수 있다.
또한, 상기 (c) 단계에서, 상기 어느 하나의 노드는, 상기 선택된 스패닝 트리 정보의 교환시 상기 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 상기 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환할 수 있다.
또한, 상기 (c) 단계는, 교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 상기 망 내의 전체 노드들의 리스트와 동일해질 때까지 반복 수행될 수 있다.
또한, 상기 (c) 단계에서, 상기 어느 하나의 노드는, 상기 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 상기 망 내의 최적 스패닝 트리로서 결정할 수 있다.
또한, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법은, (d) 상기 어느 하나의 노드가, 상기 (c) 단계에서의 스패닝 트리 정보의 비교가 상기 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 상기 망 내의 최적 스패닝 트리에서 위치 변경시, 상기 망 내의 전체 노드들에 의한 트래픽 부하의 변화량을 고려하여 상기 어느 하나의 노드의 위치 변경 여부를 결정하는 단계를 더 포함할 수 있다.
또한, 상기 (d) 단계에서, 상기 어느 하나의 노드는, 상기 트래픽 부하의 변화량이 줄어들면 상기 최적 스패닝 트리에 대한 탐색을 반복 수행할 수 있다.
또한, 상기 (d) 단계에서, 상기 어느 하나의 노드는, 상기 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 상기 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 상기 탐색의 반복 수행을 중지할 수 있다.
또한, 상기 (a) 단계에서, 상기 어느 하나의 노드는 상기 망의 토폴로지에 대한 정보를 상기 망 내의 다른 노드들과 교환하고, 상기 (b) 단계에서, 상기 어느 하나의 노드는 상기 자신을 루트로 하는 스패닝 트리의 생성시 상기 망의 토폴로지에 대한 정보를 고려할 수 있다.
한편, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성을 위한 노드 장치는, 이더넷 기반 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 상기 망 내의 다른 노드들과 교환하며 수집하는 수집부; 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하는 스패닝 트리 생성부; 및 생성된 상기 자신을 루트로 하는 스패닝 트리 정보를 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 선택부를 포함하고, 상기 선택부는, 선택된 스패닝 트리 정보를 상기 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다.
또한, 상기 선택부는, 상기 선택된 스패닝 트리 정보의 교환시 상기 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 상기 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환할 수 있다.
또한, 상기 선택부는, 교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 상기 망 내의 전체 노드들의 리스트와 동일해질 때까지, 선택된 스패닝 트리 정보를 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 과정을 반복 수행할 수 있다.
또한, 상기 선택부는, 상기 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 상기 망 내의 최적 스패닝 트리로서 결정할 수 있다.
또한, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성을 위한 노드 장치는, 상기 선택부에 의한 스패닝 트리 정보의 비교가 상기 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 상기 망 내의 최적 스패닝 트리에서 노드의 위치 변경시, 상기 망 내의 전체 노드들에 의한 트래픽 부하의 변화량을 고려하여 상기 노드의 위치 변경 여부를 결정하는 위치 변경 여부 결정부를 더 포함할 수 있다.
또한, 상기 위치 변경 여부 결정부는, 상기 트래픽 부하의 변화량이 줄어들면 상기 최적 스패닝 트리에 대한 탐색을 반복 수행할 수 있다.
또한, 상기 위치 변경 여부 결정부는, 상기 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 상기 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 상기 탐색의 반복 수행을 중지할 수 있다.
또한, 상기 수집부는, 상기 망의 토폴로지에 대한 정보를 상기 망 내의 다른 노드들과 교환하고, 상기 스패닝 트리 생성부는, 상기 자신을 루트로 하는 스패닝 트리의 생성시 상기 망의 토폴로지에 대한 정보를 고려할 수 있다.
상술한 과제 해결 수단은 단지 예시적인 것으로서, 본원을 제한하려는 의도로 해석되지 않아야 한다. 상술한 예시적인 실시예 외에도, 도면 및 발명의 상세한 설명에 추가적인 실시예가 존재할 수 있다.
전술한 본원의 과제 해결 수단에 의하면, 이더넷 기반 망 내의 어느 하나의 노드가 이더넷 기반 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 고려하여 자신을 루트로 하는 스패닝 트리 정보를 생성하고, 생성된 스패닝 트리 정보를 다른 노드들(어느 하나의 노드의 이웃 노드 및 이웃 노드 외의 다른 주변 노드 포함)의 스패닝 트리 정보와 교환하며 비교하여 트래픽 부하가 작은 스패닝 트리 정보를 선택함으로써, 트래픽 부하를 고려한 스패닝 트리(달리 표현하여, 오버레이 스패닝 트리라 할 수 있음)를 형성할 수 있다.
본원은 이더넷 기반 망이 주어진 상황에서 스패닝 트리를 통해 전송되는 총 트래픽의 양을 최소화하는 스패닝 트리를 형성할 수 있다.
본원은 망 내의 두 노드들의 쌍마다 전달되는 트래픽 양이 주어지고 트래픽 전송이 스패닝 트리를 통해서 이루어지는 경우에, 총 트래픽 전송량을 최소로 하는 스패닝 트리를 형성할 수 있다.
본원은 기반망에서 스패닝 트리의 전체(총) 트래픽 부하를 최소화하는 스패닝 트리(오버레이 스패닝 트리)를 형성할 수 있어 전체적인 망 전송의 성능을 향상시킬 수 있다.
다만, 본원에서 얻을 수 있는 효과는 상기된 바와 같은 효과들로 한정되지 않으며, 또 다른 효과들이 존재할 수 있다.
도 1은 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성을 위한 노드 장치의 개략적인 구성을 나타낸 도면이다.
도 2는 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법에 대한 개략적인 동작 흐름도이다.
도 3은 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법에 대한 다른 동작 흐름도이다.
아래에서는 첨부한 도면을 참조하여 본원이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 본원의 실시예를 상세히 설명한다. 그러나 본원은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본원을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.
본원 명세서 전체에서, 어떤 부분이 다른 부분과 "연결"되어 있다고 할 때, 이는 "직접적으로 연결"되어 있는 경우뿐 아니라, 그 중간에 다른 소자를 사이에 두고 "전기적으로 연결" 또는 "간접적으로 연결"되어 있는 경우도 포함한다.
본원 명세서 전체에서, 어떤 부재가 다른 부재 "상에", "상부에", "상단에", "하에", "하부에", "하단에" 위치하고 있다고 할 때, 이는 어떤 부재가 다른 부재에 접해 있는 경우뿐 아니라 두 부재 사이에 또 다른 부재가 존재하는 경우도 포함한다.
본원 명세서 전체에서, 어떤 부분이 어떤 구성 요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성 요소를 제외하는 것이 아니라 다른 구성 요소를 더 포함할 수 있는 것을 의미한다.
본원은 네트워크에서 트래픽 부하를 최소화하는 스패닝 트리(달리 표현하여 오버레이 스패닝 트리) 형성을 위한 노드 장치 및 그를 이용한 스패닝 트리 형성 방법에 관한 것이다. 이하 본원을 설명함에 있어서 스패닝 트리의 형성은 스패닝 트리의 구성, 생성, 구축 등의 의미로 넓게 이해될 수 있다.
도 1은 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성을 위한 노드 장치(10)의 개략적인 구성을 나타낸 도면이다.
도 1을 참조하면, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성을 위한 노드 장치(10)(이하 설명의 편의상 '본 노드 장치(10)'라 함)는 수집부(11), 스패닝 트리 생성부(12), 선택부(13) 및 통신부(14)를 포함할 수 있다.
본 노드 장치(10)는 네트워크에서 스패닝 트리를 형성할 수 있다. 이때, 본 노드 장치(10)의 적용이 가능한 네트워크는 일예로 이더넷(Ethernet) 네트워크일 수 있다. 여기서, 이더넷 네트워크는 이하 설명에서 이더넷 기반 망이라 달리 지칭될 수 있다.
또한, 본 노드 장치(10)의 적용이 가능한 네트워크는 이더넷 네트워크로만 한정되는 것은 아니고, 다른 일예로 3GPP(3rd Generation Partnership Project) 네트워크, LTE(Long Term Evolution) 네트워크, WIMAX(World Interoperability for Microwave Access) 네트워크, 인터넷(Internet), LAN(Local Area Network), Wireless LAN(Wireless Local Area Network), WAN(Wide Area Network), PAN(Personal Area Network), 블루투스(Bluetooth) 네트워크, NFC(Near Field Communication) 네트워크, 위성 방송 네트워크, 아날로그 방송 네트워크, DMB(Digital Multimedia Broadcasting) 네트워크 등이 포함될 수 있다.
또한, 본 노드 장치(10)는 스위치, 라우터 등을 의미할 수 있으나, 이에만 한정되는 것은 아니다.
수집부(11)는 이더넷 기반 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 통신부(14)를 통해 이더넷 기반 망 내의 다른 노드들과 교환(공유)하며 수집할 수 있다. 여기서, 노드쌍에 대한 트래픽 부하에 대한 정보는 노드쌍별 트래픽 부하 정보, 기대 전송 트래픽의 양 등으로 달리 지칭될 수 있다.
스패닝 트리 생성부(12)는 수집부(11)를 통해 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성할 수 있다.
또한, 수집부(11)는 이더넷 기반 망의 토폴로지(Topology)에 대한 정보를 통신부(14)를 통해 이더넷 기반 망 내의 다른 노드들과 교환할 수 있으며, 스패닝 트리 생성부(12)는 자신을 루트로 하는 스패닝 트리의 생성시 이더넷 기반 망의 토폴로지에 대한 정보를 고려할 수 있다. 여기서, 토폴로지는 네트워크의 물리적 연결 형태를 의미하는 것으로서, 일예로, 통신에 참여하고 있는 컴퓨터, 리피터, 라우터, 스위치, 허브와 같은 네트워크 장비들이 어떤 형태로 연결되어 있는지를 의미할 수 있다. 일예로, 망의 토폴로지의 유형으로는 버스형, 링형, 스타형 등이 있으며, 이에만 한정되는 것은 아니다.
선택부(13)는 스패닝 트리 생성부(12)를 통해 생성된 자신을 루트로하는 스패닝 트리의 정보(즉, 자신을 루트로하는 스패닝 트리 정보)를 통신부(14)를 통해 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다. 즉, 선택부(13)는 두 스패닝 트리 정보로서, 본 노드 장치(10) 자신을 루트로하여 생성한 스패닝 트리 정보와 이웃 노드의 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다. 이때, 본 노드 장치(10) 자신을 루트로하여 생성된 스패닝 트리 정보와 이웃 노드의 스패닝 트리 정보 중 선택된 트래픽 부하가 작은 스패닝 트리 정보는 이하 설명의 편의상 제1 선택된 스패닝 트리 정보라 하기로 한다. 또한, 이웃 노드의 스패닝 트리 정보는, 구체적으로 이웃 노드가 이웃 노드 자신을 루트로하여 생성한 스패닝 트리의 정보를 의미할 수 있다. 이에 따르면, 이더넷 기반 망 내의 복수의 노드(노드 장치) 각각이 자신을 루트로하는 스패닝 트리를 생성할 수 있다.
이후, 선택부(13)는 선택된 스패닝 트리 정보(즉, 제1 선택된 스패닝 트리 정보)를 통신부(14)를 통해 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다. 여기서, 선택된 스패닝 트리 정보(즉, 제1 선택된 스패닝 트리 정보)는 본 노드 장치(10) 자신을 루트로하여 생성한 스패닝 트리 정보와 이웃 노드의 스패닝 트리 정보 중에서 선택된 트래픽 부하가 작은 스패닝 트리 정보를 의미할 수 있다. 또한, 여기서 두 스패닝 트리 정보라 함은 선택된 스패닝 트리 정보(제1 선택된 스패닝 트리 정보)와 다른 주변 노드의 스패닝 트리 정보를 의미할 수 있다. 이때, 제1 선택된 스패닝 트리 정보와 다른 주변 노드의 스패닝 트리 정보 중 선택된 트래픽 부하가 작은 스패닝 트리 정보는 이하 설명의 편의상 제2 선택된 스패닝 트리 정보라 하기로 한다.
또한, 이때 제2 선택된 스패닝 트리 정보의 산출시 고려되는 다른 주변 노드의 스패닝 트리 정보는, 일예로 다른 주변 노드 자신을 루트로하여 생성된 스패닝 트리 정보(즉, 다른 주변 노드의 스패닝 트리 정보)를 의미할 수 있다. 다만, 이에만 한정되는 것은 아니고, 다른 일예로, 제2 선택된 스패닝 트리 정보의 산출시 고려되는 다른 주변 노드의 스패닝 트리 정보는, 다른 주변 노드 자신을 루트로 하여 생성된 다른 주변 노드의 스패닝 트리 정보 및 다른 주변 노드를 기준으로 다른 주변 노드와 이웃한 이웃 노드의 스패닝 트리 정보 중 선택된 트래픽 부하가 작은 스패닝 트리 정보를 의미할 수 있다.
또한, 선택부(13)는 선택된 스패닝 트리 정보의 교환시, 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 통신부(14)를 통해 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환할 수 있다.
구체적인 일예로, 제2 선택된 스패닝 트리 정보의 산출시 고려된 다른 주변 노드의 스패닝 트리 정보가 다른 주변 노드 자신을 루트로하여 생성된 스패닝 트리 정보라 가정하자. 이러한 경우, 선택부(13)는 선택된 스패닝 트리 정보로서 제1 선택된 스패닝 트리 정보를 다른 주변 노드와 교환할 때, 선택된 스패닝 트리 정보(제1 선택된 스패닝 트리 정보)를 선택하는데 관여한 노드들의 리스트를 다른 주변 노드와 교환할 수(주고받을 수) 있다.
달리 표현하여, 다른 주변 노드가 다른 주변 노드와 이웃한 이웃 노드 간에 스패닝 트리 정보의 비교를 수행하지 않아 다른 주변 노드 및 다른 주변 노드와 이웃한 이웃 노드 간에 선택된 스패닝 트리 정보가 존재하지 않는 경우, 선택부(13)는 제1 선택된 스패닝 트리 정보 및 제1 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트(즉, 본 노드 장치 노드 및 본 노드 장치와 이웃한 이웃 노드를 포함한 리스트)를 다른 주변 노드의 스패닝 트리 정보와 교환할 수 있다. 이러한 교환 이후 선택부(13)에 의하여 비교를 통해 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 과정이 이루어진 경우, 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트는 본 노드 장치 및 본 노드 장치와 이웃한 이웃 노드를 포함하는 리스트에서 본 노드 장치, 본 노드 장치와 이웃한 이웃 노드 및 다른 주변 노드를 포함하도록 업데이트될 수 있다.
다른 일예로, 제2 선택된 스패닝 트리 정보의 산출시 고려된 다른 주변 노드의 스패닝 트리 정보가, 다른 주변 노드 자신을 루트로 하여 생성된 다른 주변 노드의 스패닝 트리 정보 및 다른 주변 노드를 기준으로 다른 주변 노드와 이웃한 이웃 노드의 스패닝 트리 정보 중 선택된 트래픽 부하가 작은 스패닝 트리 정보라 가정하자. 이러한 경우, 선택부(13)는 선택된 스패닝 트리 정보로서 제1 선택된 스패닝 트리 정보를 다른 주변 노드와 교환할 때, 선택된 스패닝 트리 정보(제1 선택된 스패닝 트리 정보)를 선택하는데 관여한 노드들의 리스트를 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환할 수(주고받을 수) 있다.
달리 표현하여, 다른 주변 노드가 다른 주변 노드와 이웃한 이웃 노드 간에 스패닝 트리 정보의 비교를 수행하여 다른 주변 노드 및 다른 주변 노드와 이웃한 이웃 노드 간에 선택된 스패닝 트리 정보가 존재하는 경우, 선택부(13)는 제1 선택된 스패닝 트리 정보와 제1 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트(즉, 본 노드 장치 노드 및 본 노드 장치 노드와 이웃한 이웃 노드를 포함한 리스트)를 다른 주변 노드에 의해 선택된 스패닝 트리 정보(즉, 다른 주변 노드 및 다른 주변 노드와 이웃한 이웃 노드 간에 선택된 스패닝 트리 정보)와 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트(즉, 다른 주변 노드 및 다른 주변 노드와 이웃한 이웃 노드를 포함한 리스트)를 교환할 수 있다. 이러한 교환 이후 선택부(13)에 의하여 비교를 통해 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 과정이 이루어진 경우, 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트는 본 노드 장치 및 본 노드 장치와 이웃한 이웃 노드를 포함하는 리스트에서 본 노드 장치, 본 노드 장치와 이웃한 이웃 노드, 다른 주변 노드 및 다른 주변 노드와 이웃한 이웃 노드를 포함하도록 업데이트될 수 있다.
이에 따르면, 스패닝 트리 정보 간의 비교가 수행될 때마다, 스패닝 트리 정보 간의 비교에 의하여 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 업데이트될 수 있다.
선택부(13)는 교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 이더넷 기반 망 내의 전체 노드들의 리스트와 동일해질 때까지, 선택된 스패닝 트리 정보를 통신부(14)를 통해 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 과정을 반복 수행할 수 있다. 여기서, 다른 주변 노드라 함은 제1 선택된 스패닝 트리 정보와 관련된 이웃 노드 및 제2 선택된 스패닝 트리 정보와 관련된 다른 주변 노드 외의 또 다른 주변 노드를 의미할 수 있다.
달리 말해, 선택부(13)는 다른 노드들과의 스패닝 트리 정보 비교시마다 업데이트되는 리스트(즉, 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트)가 이더넷 기반 망 내의 전체 노드들의 리스트와 동일해질 때까지, 이더넷 기반 망 내의 다른 노드들과의 스패닝 트리 정보의 교환에 따른 비교 과정을 반복 수행할 수 있다.
이때, 선택부(13)는 자신이 보유한 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 이더넷 망 내의 전체 노드들의 리스트와 동일해지면, 통신부(14)를 통한 다른 주변 노드와의 스패닝 트리 정보의 교환을 중단할 수 있다.
선택부(13)는 망 내의 전체 노드들의 리스트와 동일해질 때까지 선택된 스패닝 트리 정보의 교환을 반복 수행한 경우, 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 이더넷 기반 망 내의 최적 스패닝 트리로서 결정할 수 있다. 즉, 선택부(13)에 의한 최적 스패닝 트리의 결정으로 하여금, 이더넷 기반 망 내의 전체 노드들 각각의 스패닝 트리 중 유발 트래픽 부하가 가장 작은 스패닝 트리가 결정될 수 있다.
다시 말해, 선택부(13)는 이웃 노드를 루트로 하는 스패닝 트리 정보와 자신을 루트로하는 스패닝 트리 정보를 비교함으로써, 그 중 트래픽 부하가 더 작은 스패닝 트리 정보를 선택할 수 있다. 이후, 선택부(13)는 선택된 스패닝 트리 정보와 상기 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 다른 주변 노드와 교환하며(주고받으며), 선택된 스패닝 트리 정보와 다른 주변 노드의 스패닝 트리 정보를 비교하여, 그 중 트래픽 부하가 더 작은 스패닝 트리 정보를 선택할 수 있다. 선택부(13)는 이러한 과정을 또 다른 주변 노드들에 대하여 반복 수행할 수 있다. 이때, 이러한 반복 수행은 스패닝 트리 정보의 선택에 관여한 노드들의 리스트가 이더넷 기반 망 내의 전체 노드들의 리스트와 동일해질 때까지 이루어질 수 있다. 이때, 스패닝 트리 정보의 선택에 관여한 노드들의 리스트가 전체 노드들의 리스트와 동일해졌을 때 선택된 스패닝 트리 정보에 대응하는 스패닝 트리는, 이더넷 기반 망 내의 전체 노드들에 의하여 선택된 최소 트래픽을 갖는 스패닝 트리라 할 수 있다. 선택부(13)는 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 이더넷 기반 망 내의 전체 노드들 각각에 의하여 생성된 복수의 스패닝 트리들 중 유발 트래픽 부하가 작은 이더넷 망 내의 최적 스패닝 트리인 것으로 결정할 수 있다.
통신부(14)는 이더넷 망 내의 다른 노드들과의 통신이 이루어지도록 할 수 있다. 통신부(14)는 다른 노드들과 트래픽 부하에 대한 정보, 후술할 망의 토폴로지에 대한 정보, 스패닝 트리 정보, 리스트 정보 등의 교환이 이루어질 수 있도록 할 수 있다.
또한, 본 노드 장치(10)는 위치 변경 여부 결정부(15)를 포함할 수 있다.
위치 변경 여부 결정부(15)는 선택부(13)에 의한 스패닝 트리 정보의 비교가 이더넷 기반 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 이더넷 기반 망 내의 최적 스패닝 트리에서 노드의 위치 변경시, 이더넷 기반 망 내의 전체 노드들에 의한 트래픽 부하의 변화량(즉, 전체 트래픽 부하의 변화량)을 고려하여 노드의 위치 변경 여부를 결정할 수 있다. 여기서, 위치 변경 여부의 결정 대상인 노드라 함은 본 노드 장치(10)를 의미할 수 있다.
이때, 위치 변경 여부 결정부(15)는 트래픽 부하의 변화량이 줄어들면 노드(본 노드 장치)의 위치 변화가 수행된 것으로 보아, 최적 스패닝 트리에 대한 탐색을 반복(iteration) 수행할 수 있다.
또한, 위치 변경 여부 결정부(15)는 이더넷 기반 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 이더넷 기반 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 최적 스패닝 트리에 대한 탐색의 반복 수행을 중지할 수 있다.
이때, 노드(본 노드 장치)의 위치 변경시 트래픽 부하의 변화량은 하기 수학식 1을 만족할 수 있다.
[수학식 1]
Figure 112018111218861-pat00001
여기서,
Figure 112018111218861-pat00002
는 총 트래픽 부하의 변화량, H는 노드(본 노드 장치)가 연결된 부모 노드의 레벨, K는 노드(본 노드 장치)가 연결될 수 있는 후보 부모 노드의 레벨, Q는 현재 부모 노드와 후보 부모 노드를 모두 포함하는 최소의 서브트리(subtree)의 루트 노드의 레벨을 나타낸다. 또한,
Figure 112018111218861-pat00003
는 현재 부모 노드쪽 서브트리에서 현재 부모 노드와 최소 서브트리의 루트를 잇는 경로상에 있는 h레벨의 노드로 인한 트래픽 부하를 나타내며, 이는 이 h레벨 노드와 그 자손노드들의 총 유발 트래픽 부하에서 h+1레벨 노드와 그 자손노드들로 인한 총 유발 트래픽 부하를 제외한 것일 수 있다. 또한,
Figure 112018111218861-pat00004
는 후보 부모 노드쪽 서브트리에서 후보 부모와 최소 서브트리의 루트를 잇는 경로상에 있는 k 레벨의 노드로 인한 총 유발 트래픽 부하를 나타내며, 이는 이 k 레벨 노드와 그 자손노드들의 총 유발 트래픽 부하에서 k+1 레벨 노드와 그 자손노드들로 인한 총 유발 트래픽 부하를 제외한 것일 수 있다. 또한,
Figure 112018111218861-pat00005
는 최소 서브트리의 루트노드로 인한 트래픽 부하를 나타내며, 이는 이더넷 기반 망 전체의 트래픽 발생량에서 현재 부모 노드쪽과 후보 부모 노드쪽의 자손 노드들에 의한 트래픽 발생량을 제외한 것일 수 있다.
달리 말해, 본 노드 장치(10)에서 루트 노드가 주어진 경우 스패닝 트리의 탐색은 반복(iteration)을 통해 수행될 수 있다. 본 노드 장치(10)는 최적 스패닝 트리에서 노드(본 노드 장치)의 위치 변경시 상기의 수학식 1에 따른 트래픽 부하의 변화량을 고려하여 노드(본 노드 장치)의 위치 변경 여부를 결정할 수 있다. 일예로, 위치 변경 여부 결정부(15)는 트래픽 부하의 변화량이 줄어들면 최적 스패닝 트리에서 노드(본 노드 장치)의 위치 변경이 이루어지도록 위치 변경 여부를 결정할 수 있다.
이때, 최적 스패닝 트리 내의 본 노드 장치(10)의 위치를 기본 망(즉, 이더넷 기반 망)의 가능한 링크를 이용하여 변경시킬 때의 전체 트래픽 부하량은 상기 수학식 1과 같을 수 있다. 달리 표현하여, 최적 스패닝 트리에 속한 어느 하나의 노드(예를 들어 본 노드 장치)의 위치를 변경시킬 때의 전체 트래픽 부하량은 상기 수학식 1과 같을 수 있다. 또한, 일예로, 최적 스패닝 트리 내에 속한 모든 노드에 대하여 상기 수학식 1을 적용시켰을 때 트래픽 부하가 감소하지 않은 것으로 판단되면, 위치 변경 여부 결정부(15)는 최적 스패닝 트리에 대한 탐색이 이루어지지 않도록 최적 스패닝 트리에 대한 탐색의 반복(iteration)을 중지할 수 있다.
한편, 본 노드 장치(10)가 적용되는 네트워크(예를 들어, 이더넷 기반 망) 내에는 복수의 노드(노드 장치)가 포함될 수 있다. 이때, 본 노드 장치(10)에 대하여 설명된 내용은 네트워크 내에 포함된 복수의 노드(노드 장치) 각각에 대해서도 동일 내지 유사하게 이해될 수 있다.
이에 따르면, 본 노드 장치(10)가 포함된 이더넷 기반 망 내의 복수의 노드 장치(10) 각각은, 망 내의 다른 노드들을 목적지로 하는 트래픽을 발생시키게 되며, 이를 고려하여 다른 노드들 각각에 대한 트래픽 부하를 파악할 수 있다. 구체적으로, 복수의 노드 장치(10) 각각은 망의 토폴로지에 대한 정보와 망 내 노드쌍에 대한 트래픽 부하에 대한 정보를 다른 노드들과 서로 교환(공유)할 수 있다. 이러한 본원은 복수의 노드 장치(10) 각각이 서로 간에 공유된 정보로 하여금 트래픽 부하를 최소화하는 스패닝 트리(오버레이 스패닝 트리)가 형성될 수 있도록 할 수 있다. 이때, 복수의 노드 장치(10) 각각은 최소화된 스패닝 트리에 대한 정보를 다른 노드들과 서로 공유할 수 있다.
달리 표현하여, 복수의 노드 장치(10) 각각은, 다른 노드들의 전송쌍에 대한 기대 전송 트래픽의 양과 전체 망의 토폴로지 정보를 수집할 수 있으며, 수집된 정보들로 하여금 스패닝 트리(오버레이 스패닝 트리)의 링크들을 통과하는 전체 트래픽의 양을 최소화하는 스패닝 트리(오버레이 스패닝 트리)를 형성(달리 말해, 최적 스패닝 트리를 결정)할 수 있다.
다시 말해, 본원에서는 이더넷 기반 망에서 스패닝 트리(오버레이 스패닝 트리)를 형성(구성)하기 위해, 각 노드 장치(10)들끼리 가능한 노드쌍에서의 트래픽 부하에 대한 정보를 서로 교환할 수 있다. 또한, 노드 장치(10)들 각각은 트래픽 부하에 대한 정보의 교환을 통해 수집된 트래픽 부하에 대한 정보를 이용하여, 노드 장치(10)들 각각이 자신을 루트로 하는 스패닝 트리를 생성하고, 노드 장치(10)들 각각에 의하여 생성된 스패닝 트리의 정보를 서로 교환하여 비교함으로써 최적 스패닝 트리를 도출할 수 있다.
또한, 최적 스패닝 트리에서 노드의 위치를 변화시킬 때에는 상기의 수학식 1을 통해 예측된 노드의 위치 변경시 트래픽 부하의 변화량을 이용함으로써 노드의 위치 변경 여부를 결정할 수 있다.
한편, 본원의 다른 일 실시예에 따르면 중앙집중식 방식에 의해 최적 스패닝 트리를 형성할 수 있다. 이를 위해, 본원의 다른 일 실시예에서는 중앙 제어기 및 복수의 노드(노드 장치)를 포함할 수 있다. 간단히 설명하면, 중앙집중식 방식에서 중앙 제어기는 망 포톨로지 정보와 노드별 트래픽 정보를 수집하고, 수집된 정보를 이용하여 최저 트래픽 스패닝 트리를 생성할 수 있다. 또한, 중앙 제어기는 각 노드를 루트로 하는 최적 트래픽 스패닝 트리를 찾고, 그 중 가장 트래픽이 작은 스패닝 트리와 루트를 선택할 수 있다. 이후 중앙 제어기는 선택된 트래픽이 가장 작은 스패닝 트리와 루트 관련 정보를 망 내의 전체 노드들과 공유할 수 있다.
이하에서는 상기에 자세히 설명된 내용을 기반으로, 본원의 동작 흐름을 간단히 살펴보기로 한다.
도 2는 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법에 대한 개략적인 동작 흐름도이다.
도 2에 도시된 네트워크에서의 스패닝 트리 형성 방법은 앞서 설명된 본 노드 장치(10)에 의하여 수행될 수 있다. 따라서, 이하 생략된 내용이라고 하더라도 본 노드 장치(10)에 대하여 설명된 내용은 네트워크에서의 스패닝 트리 형성 방법에 대한 설명에도 동일하게 적용될 수 있다.
도 2를 참조하면, 단계S11에서는 이더넷 기반 망 내의 어느 하나의 노드가, 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 통신부를 통해 망 내의 다른 노드들과 교환하며 수집할 수 있다. 이때, 어느 하나의 노드는 앞서 설명된 본 노드 장치(10)를 의미할 수 있다.
다음으로, 단계S12에서는 어느 하나의 노드가, 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하고, 생성된 자신을 루트로 하는 스패닝 트리 정보를 통신부를 통해 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다.
이때, 단계S11에서 어느 하나의 노드는 망의 토폴로지에 대한 정보를 통신부를 통해 망 내의 다른 노드들과 교환할 수 있으며, 단계S12에서 어느 하나의 노드는 자신을 루트로 하는 스패닝 트리의 생성시 망의 토폴로지에 대한 정보를 고려할 수 있다.
다음으로, 단계S13에서는 어느 하나의 노드가, 선택된 스패닝 트리 정보를 통신부를 통해 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다.
또한, 단계S13에서 어느 하나의 노드는, 선택된 스패닝 트리 정보의 교환시 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 통신부를 통해 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환할 수 있다.
또한, 단계S13은 교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 망 내의 전체 노드들의 리스트와 동일해질 때까지 반복 수행될 수 있다.
또한, 단계S13에서 어느 하나의 노드는, 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 망 내의 최적 스패닝 트리로서 결정할 수 있다.
또한, 도면에 도시하지는 않았으나, 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법은 어느 하나의 노드가, 단계S13에서의 스패닝 트리 정보의 비교가 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 망 내의 최적 스패닝 트리에서 위치 변경시, 망 내의 전체 노드들에 의한 트래픽 부하의 변화량을 고려하여 어느 하나의 노드의 위치 변경 여부를 결정하는 단계(이하 단계S14라 함)를 포함할 수 있다.
이때, 단계S14에서 어느 하나의 노드는, 트래픽 부하의 변화량이 줄어들면 어느 하나의 노드의 위치 변화가 수행된 것으로 보아 최적 스패닝 트리에 대한 탐색을 반복 수행할 수 있다.
또한, 단계S14에서 어느 하나의 노드는, 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 최적 스패닝 트리에 대한 탐색의 반복 수행을 중지할 수 있다.
이때, 어느 하나의 노드의 위치 변경시 트래픽 부하의 변화량은 상기의 수학식 1을 만족할 수 있다. 상기 수학식 1에 대한 설명은 앞서 자세히 설명했으므로, 이하 중복되는 설명은 생략하기로 한다.
상술한 설명에서, 단계 S11 내지 S13은 본원의 구현예에 따라서, 추가적인 단계들로 더 분할되거나, 더 적은 단계들로 조합될 수 있다. 또한, 일부 단계는 필요에 따라 생략될 수도 있고, 단계 간의 순서가 변경될 수도 있다.
도 3은 본원의 일 실시예에 따른 네트워크에서의 스패닝 트리 형성 방법에 대한 다른 동작 흐름도이다.
도 3에 도시된 네트워크에서의 스패닝 트리 형성 방법은 앞서 설명된 본 노드 장치(10)에 의하여 수행될 수 있다. 따라서, 이하 생략된 내용이라고 하더라도 본 노드 장치(10)에 대하여 설명된 내용은 네트워크에서의 스패닝 트리 형성 방법에 대한 설명에도 동일하게 적용될 수 있다.
도 3을 참조하면, 단계S21에서는 망 내의 노드쌍별 트래픽 부하 정보(즉, 노드쌍에 대한 트래픽 부하에 대한 정보)를 수집할 수 있다.
다음으로, 단계S22에서는 수집된 트래픽 부하 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성할 수 있다.
다음으로, 단계S23에서는 이웃 노드와 스패닝 트리 정보를 교환할 수 있다. 즉, 단계S23에서는 자신을 루트로 하는 스패닝 트리 정보와 이웃 노드의 스패닝 트리 정보를 교환할 수 있다.
다음으로, 단계S24에서는 교환된 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다. 즉, 단계S24에서는 자신을 루트로 하는 스패닝 트리 정보와 이웃 노드의 스패닝 트리 정보를 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다.
다음으로, 단계S25에서는 이더넷 기반 망 내의 전체 노드들의 스패닝 트리 정보와의 비교가 이루어졌는지 여부를 판단할 수 있다.
이때, 단계S25에서 전체 노드들의 스패닝 트리 정보(즉, 전체 노드들 각각에 의하여 생성된 모든 스패닝 트리 정보)와의 비교가 이루어지지 않은 것으로 판단된 경우(S25-NO), 단계S23으로 되돌아갈 수 있다. 이때, 단계S23에서는 이웃 노드 외의 다른 주변 노드와 스패닝 트리 정보를 교환할 수 있다. 이후, 단계S24에서는 이전에 선택된 스패닝 트리 정보와 다른 주변 노드의 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택할 수 있다.
한편, 단계S25에서 전체 노드들의 스패닝 트리 정보와의 비교가 이루어진 것으로 판단된 경우(S25-YES), 단계S26에서는 최적 스패닝 트리를 도출할 수 있다. 이때, 전체 노드들의 스패닝 트리 정보와의 비교가 이루어졌는지에 대한 판단은 교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 망 내의 전체 노드들의 리스트와 동일해졌는지로 판단될 수 있다.
상술한 설명에서, 단계 S21 내지 S26은 본원의 구현예에 따라서, 추가적인 단계들로 더 분할되거나, 더 적은 단계들로 조합될 수 있다. 또한, 일부 단계는 필요에 따라 생략될 수도 있고, 단계 간의 순서가 변경될 수도 있다.
본원의 일 실시 예에 따른 네트워크에서의 스패닝 트리 형성 방법은 다양한 컴퓨터 수단을 통하여 수행될 수 있는 프로그램 명령 형태로 구현되어 컴퓨터 판독 가능 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능 매체는 프로그램 명령, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체에 기록되는 프로그램 명령은 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록 매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체(magnetic media), CD-ROM, DVD와 같은 광기록 매체(optical media), 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 롬(ROM), 램(RAM), 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함한다. 상기된 하드웨어 장치는 본 발명의 동작을 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
전술한 본원의 설명은 예시를 위한 것이며, 본원이 속하는 기술분야의 통상의 지식을 가진 자는 본원의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.
본원의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본원의 범위에 포함되는 것으로 해석되어야 한다.
10: 노드 장치
11: 수집부
12: 스패닝 트리 생성부
13: 선택부
14: 통신부
15: 위치 변경 여부 결정부

Claims (19)

  1. 네트워크에서의 스패닝 트리 형성 방법에 있어서,
    (a) 이더넷 기반 망 내의 어느 하나의 노드가, 상기 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 상기 망 내의 다른 노드들과 교환하며 수집하는 단계;
    (b) 상기 어느 하나의 노드가, 수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하고, 생성된 상기 자신을 루트로 하는 스패닝 트리 정보를 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계; 및
    (c) 상기 어느 하나의 노드가, 선택된 스패닝 트리 정보를 상기 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 단계,
    를 포함하는 스패닝 트리 형성 방법.
  2. 제1항에 있어서,
    상기 (c) 단계에서,
    상기 어느 하나의 노드는, 상기 선택된 스패닝 트리 정보의 교환시 상기 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 상기 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환하는 것인, 스패닝 트리 형성 방법.
  3. 제2항에 있어서,
    상기 (c) 단계는,
    교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 상기 망 내의 전체 노드들의 리스트와 동일해질 때까지 반복 수행되는 것인, 스패닝 트리 형성 방법.
  4. 제3항에 있어서,
    상기 (c) 단계에서,
    상기 어느 하나의 노드는, 상기 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 상기 망 내의 최적 스패닝 트리로서 결정하는 것인, 스패닝 트리 형성 방법.
  5. 제1항에 있어서,
    (d) 상기 어느 하나의 노드가, 상기 (c) 단계에서의 스패닝 트리 정보의 비교가 상기 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 상기 망 내의 최적 스패닝 트리에서 위치 변경시, 상기 망 내의 전체 노드들에 의한 트래픽 부하의 변화량을 고려하여 상기 어느 하나의 노드의 위치 변경 여부를 결정하는 단계,
    를 더 포함하는 스패닝 트리 형성 방법.
  6. 제5항에 있어서,
    상기 (d) 단계에서,
    상기 어느 하나의 노드는, 상기 트래픽 부하의 변화량이 줄어들면 상기 최적 스패닝 트리에 대한 탐색을 반복 수행하는 것인, 스패닝 트리 형성 방법.
  7. 제6항에 있어서,
    상기 (d) 단계에서,
    상기 어느 하나의 노드는, 상기 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 상기 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 상기 탐색의 반복 수행을 중지하는 것인, 스패닝 트리 형성 방법.
  8. 제6항에 있어서,
    상기 어느 하나의 노드의 위치 변경시 트래픽 부하의 변화량은 하기 수학식 1을 만족하는 것인, 스패닝 트리 형성 방법;
    [수학식 1]
    Figure 112018111218861-pat00006

    여기서,
    Figure 112018111218861-pat00007
    는 총 트래픽 부하의 변화량, H는 상기 어느 하나의 노드가 연결된 부모 노드의 레벨, K는 상기 어느 하나의 노드가 연결될 수 있는 후보 부모 노드의 레벨, Q는 현재 부모 노드와 후보 부모 노드를 모두 포함하는 최소의 서브트리(subtree)의 루트 노드의 레벨,
    Figure 112018111218861-pat00008
    는 현재 부모 노드쪽 서브트리에서 현재 부모 노드와 최소 서브트리의 루트를 잇는 경로상에 있는 h레벨의 노드로 인한 트래픽 부하,
    Figure 112018111218861-pat00009
    는 후보 부모 노드쪽 서브트리에서 후보 부모와 최소 서브트리의 루트를 잇는 경로상에 있는 k 레벨의 노드로 인한 총 유발 트래픽 부하,
    Figure 112018111218861-pat00010
    는 최소 서브트리의 루트노드로 인한 트래픽 부하를 나타냄.
  9. 제1항에 있어서,
    상기 (a) 단계에서, 상기 어느 하나의 노드는 상기 망의 토폴로지에 대한 정보를 상기 망 내의 다른 노드들과 교환하고,
    상기 (b) 단계에서, 상기 어느 하나의 노드는 상기 자신을 루트로 하는 스패닝 트리의 생성시 상기 망의 토폴로지에 대한 정보를 고려하는 것인, 스패닝 트리 형성 방법.
  10. 네트워크에서의 스패닝 트리 형성을 위한 노드 장치에 있어서,
    이더넷 기반 망 내의 노드쌍에 대한 트래픽 부하에 대한 정보를 상기 망 내의 다른 노드들과 교환하며 수집하는 수집부;
    수집된 트래픽 부하에 대한 정보를 이용하여 자신을 루트로 하는 스패닝 트리를 생성하는 스패닝 트리 생성부; 및
    생성된 상기 자신을 루트로 하는 스패닝 트리 정보를 이웃 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 선택부를 포함하고,
    상기 선택부는,
    선택된 스패닝 트리 정보를 상기 이웃 노드 외의 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 것인, 노드 장치.
  11. 제10항에 있어서,
    상기 선택부는,
    상기 선택된 스패닝 트리 정보의 교환시 상기 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트를 상기 다른 주변 노드에 의해 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트와 교환하는 것인, 노드 장치.
  12. 제11항에 있어서,
    상기 선택부는,
    교환되는 선택된 스패닝 트리 정보를 선택하는데 관여한 노드들의 리스트가 상기 망 내의 전체 노드들의 리스트와 동일해질 때까지, 선택된 스패닝 트리 정보를 다른 주변 노드의 스패닝 트리 정보와 교환하며 비교함으로써 두 스패닝 트리 정보 중 트래픽 부하가 작은 스패닝 트리 정보를 선택하는 과정을 반복 수행하는 것인, 노드 장치.
  13. 제12항에 있어서,
    상기 선택부는,
    상기 반복 수행에 의하여 선택된 스패닝 트리 정보에 대응하는 스패닝 트리를 상기 망 내의 최적 스패닝 트리로서 결정하는 것인, 노드 장치.
  14. 제10항에 있어서,
    상기 선택부에 의한 스패닝 트리 정보의 비교가 상기 망 내의 전체 노드들에 대하여 이루어짐에 따라 결정된 상기 망 내의 최적 스패닝 트리에서 노드의 위치 변경시, 상기 망 내의 전체 노드들에 의한 트래픽 부하의 변화량을 고려하여 상기 노드의 위치 변경 여부를 결정하는 위치 변경 여부 결정부,
    를 더 포함하는 노드 장치.
  15. 제14항에 있어서,
    상기 위치 변경 여부 결정부는,
    상기 트래픽 부하의 변화량이 줄어들면 상기 최적 스패닝 트리에 대한 탐색을 반복 수행하는 것인, 노드 장치.
  16. 제15항에 있어서,
    상기 위치 변경 여부 결정부는,
    상기 망 내의 전체 노드들에 대한 트래픽 부하의 변화량에 기초하여, 상기 망 내의 전체 노드들에 대해 트래픽 부하가 감소하지 않는 것으로 판단되면 상기 탐색의 반복 수행을 중지하는 것인, 노드 장치.
  17. 제15항에 있어서,
    상기 노드의 위치 변경시 트래픽 부하의 변화량은 하기 수학식 2를 만족하는 것인, 노드 장치;
    [수학식 2]
    Figure 112018111218861-pat00011

    여기서,
    Figure 112018111218861-pat00012
    는 총 트래픽 부하의 변화량, H는 상기 노드가 연결된 부모 노드의 레벨, K는 상기 노드가 연결될 수 있는 후보 부모 노드의 레벨, Q는 현재 부모 노드와 후보 부모 노드를 모두 포함하는 최소의 서브트리(subtree)의 루트 노드의 레벨,
    Figure 112018111218861-pat00013
    는 현재 부모 노드쪽 서브트리에서 현재 부모 노드와 최소 서브트리의 루트를 잇는 경로상에 있는 h레벨의 노드로 인한 트래픽 부하,
    Figure 112018111218861-pat00014
    는 후보 부모 노드쪽 서브트리에서 후보 부모와 최소 서브트리의 루트를 잇는 경로상에 있는 k 레벨의 노드로 인한 총 유발 트래픽 부하,
    Figure 112018111218861-pat00015
    는 최소 서브트리의 루트노드로 인한 트래픽 부하를 나타냄.
  18. 제10항에 있어서,
    상기 수집부는, 상기 망의 토폴로지에 대한 정보를 상기 망 내의 다른 노드들과 교환하고,
    상기 스패닝 트리 생성부는, 상기 자신을 루트로 하는 스패닝 트리의 생성시 상기 망의 토폴로지에 대한 정보를 고려하는 것인, 노드 장치.
  19. 제1항 내지 제9항 중 어느 한 항의 방법을 컴퓨터에서 실행하기 위한 프로그램을 기록한 컴퓨터에서 판독 가능한 기록매체.
KR1020180137019A 2017-11-29 2018-11-09 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법 Expired - Fee Related KR102018093B1 (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1020170161650 2017-11-29
KR20170161650 2017-11-29

Publications (2)

Publication Number Publication Date
KR20190063389A KR20190063389A (ko) 2019-06-07
KR102018093B1 true KR102018093B1 (ko) 2019-09-04

Family

ID=66850299

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020180137019A Expired - Fee Related KR102018093B1 (ko) 2017-11-29 2018-11-09 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법

Country Status (1)

Country Link
KR (1) KR102018093B1 (ko)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2022092632A2 (ko) * 2020-10-30 2022-05-05 한국항공대학교산학협력단 종단간 주기적 저지연 트래픽 전송을 위한 오프셋 기반의 전송 경로 및 슬롯 탐색 방법과 그를 수행하는 제어 장치
KR102762610B1 (ko) * 2024-10-10 2025-02-07 주식회사에스비정보기술 네트워크 스위치의 설정 변경을 감지하고 설정을 복원하는 방법 및 이러한 방법을 수행하는 장치

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010087551A (ja) 2008-09-29 2010-04-15 Oki Electric Ind Co Ltd ネットワーク経路設定システム、ネットワーク経路設定方法、及び、ネットワーク設定サーバ
WO2016168603A9 (en) 2015-04-15 2016-12-08 Nokia Solutions And Networks Oy Self-organizing network concepts for small cells backhauling

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20150142506A (ko) * 2014-06-12 2015-12-22 한국전자통신연구원 네트워크 연결 장치 및 데이터 라우팅 테이블 생성 방법

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010087551A (ja) 2008-09-29 2010-04-15 Oki Electric Ind Co Ltd ネットワーク経路設定システム、ネットワーク経路設定方法、及び、ネットワーク設定サーバ
WO2016168603A9 (en) 2015-04-15 2016-12-08 Nokia Solutions And Networks Oy Self-organizing network concepts for small cells backhauling

Also Published As

Publication number Publication date
KR20190063389A (ko) 2019-06-07

Similar Documents

Publication Publication Date Title
CN103202005B (zh) 低功率有损网络中用于管理节点的方法和系统
Müller et al. Survivor: An enhanced controller placement strategy for improving SDN survivability
US10348611B2 (en) Generating a loop-free routing topology using routing arcs
US9929938B2 (en) Hierarchal label distribution and route installation in a loop-free routing topology using routing arcs at multiple hierarchal levels for ring topologies
CN112104558B (zh) 区块链分发网络的实现方法、系统、终端及介质
JP5362743B2 (ja) 最短経路決定のタイブレイク
US9628391B2 (en) Recursive load balancing in a loop-free routing topology using routing arcs
KR100973695B1 (ko) 노드 장치 및 스패닝 트리를 이용한 최단 경로 결정 방법
US8036144B2 (en) Gateway selection method for wireless mesh network
US9246794B2 (en) Label distribution and route installation in a loop-free routing topology using routing arcs
CN101483610B (zh) 链路状态路由协议的路由更新方法
Kim et al. Probability-based spray and wait protocol in delay tolerant networks
KR102018093B1 (ko) 네트워크에서의 스패닝 트리 형성을 위한 노드 장치 및 그를 이용한 네트워크에서의 스패닝 트리 형성 방법
CN112887202A (zh) 一种基于子拓扑网络的sdn链路故障网络收敛方法
KR102045444B1 (ko) 종단간 저지연 전송을 위한 종단간 전송 경로 및 전송 슬롯 탐색 방법과 그를 수행하는 노드 장치
Seetha et al. Optimal placement techniques of mesh router nodes in wireless mesh networks
CN106559266A (zh) 一种电力通信网络中基于密度聚类算法的ospf区域划分方法
CN104618130A (zh) 一种软件定义数据中心网络控制器的最小代价同步方法
US8842575B2 (en) Method and apparatus for providing a non-overlapping ring-mesh network topology
Sakai et al. Multi-initiator connected dominating set construction for mobile ad hoc networks
Fan et al. An optimization algorithm for spatial information network self-healing based on software defined network
Bonada et al. RSTP-SP: Shortest path extensions to RSTP
JP5618268B2 (ja) ネットワーク設計方法及びプログラム
Xin et al. A distributed multipath routing algorithm to minimize congestion
Ho et al. Using local search for traffic engineering in switched ethernet networks

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20181109

PA0201 Request for examination
PG1501 Laying open of application
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: 20190827

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20190829

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20190829

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20220607

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20230607

Start annual number: 5

End annual number: 5

PC1903 Unpaid annual fee

Termination category: Default of registration fee

Termination date: 20250609