[go: up one dir, main page]

KR101481757B1 - 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체 - Google Patents

동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체 Download PDF

Info

Publication number
KR101481757B1
KR101481757B1 KR1020140097511A KR20140097511A KR101481757B1 KR 101481757 B1 KR101481757 B1 KR 101481757B1 KR 1020140097511 A KR1020140097511 A KR 1020140097511A KR 20140097511 A KR20140097511 A KR 20140097511A KR 101481757 B1 KR101481757 B1 KR 101481757B1
Authority
KR
South Korea
Prior art keywords
flow
module
modules
flows
cost
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.)
Active
Application number
KR1020140097511A
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 KR1020140097511A priority Critical patent/KR101481757B1/ko
Application granted granted Critical
Publication of KR101481757B1 publication Critical patent/KR101481757B1/ko
Active 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
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS

Landscapes

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

Abstract

본 발명은 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체에 관한 것이다.
본 발명의 일 태양에 따르면, 네트워크 장치를 이용하여 플로우 처리를 수행하는 방법에 있어서, (a) 플로우 처리를 수행하는 복수의 모듈의 가가 모듈의 플로우에 대한 처리 비용에 기반하여 복수의 모듈들 중 플로우를 처리할 모듈을 결정하는 단계 및 (b) 상기 결정된 모듈에게 상기 플로우의 처리를 할당하는 단계를 포함하는 방법이 제공된다.

Description

동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체{METHOD, APPARATUS AND COMPUTER-READABLE RECORDING MEDIUM FOR PROCESSING FLOW USING DYNAMIC FLOW DISTRIBURION}
본 발명은 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체에 관한 것으로, 보다 상세하게는, 플로우 처리를 수행하는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 복수의 모듈들 중 플로우를 처리할 모듈을 결정하고, 플로우에 해당하는 패킷을 결정된 모듈을 사용하여 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체에 관한 것이다.
일반적으로, 네트워크 장치의 인터페이스는 네트워크 장치의 제조자에 의해 결정된다. 말하자면, 인터넷 벤더의 라우터(또는, 스위치)는 데이터 평면(Data plane), 제어 평면(Control plane) 및 관리 기능을 비롯한 여타 응용 기능들을 모두 하드웨어 제품 내에 내장하고 있으며, 라우터에 대한 설정 방법 또한 벤더마다 상이하게 되어있다. 말하자면, 다양한 제조자들의 네트워크 장치들은 서로 상이한 어플리케이션 프로그래밍 인터페이스(API: Application Programming Interface, 이하 "API"라고 함)를 제공할 수 있다.
동일 또는 유사한 기능을 제공하는 다양한 네트워크 장치들이 제조사 또는 버전 별로 서로 상이한 인터페이스를 제공하기 때문에, 네트워크의 운영자가 네트워크의 환경에 맞추어 기능을 추가, 개발 또는 구성함에 있어서 어려움을 겪는 문제가 발생할 수 있다. 따라서, 네트워크 장치에 대한 표준 API 또는 개방된(open) 인터페이스 등과 같은 통일된 인터페이스가 요구된다.
또한, 라우터에서 사용하는 프로토콜들은 국제 인터넷 표준화 기구(IETF: Internet Engineering Task Force, 이하 "IETF"라고 함) 등을 비롯한 표준화 단체에 의해 결정되므로 사용자에 의해 요구되는 특수한 기능이 만들어질 여지가 없다.
또한, 벤더에 의한 프로토타입 구현 및 기존의 다양한 장치들과의 호환성 시험을 위한 시간 및 비용 또한 많이 요구된다.
소프트웨어 정의된 네트워킹(SDN: Software Defined Networking, 이하 "SDN"이라고 함)은 오픈 네트워크 파운데이션(ONF: Open Network Foundation, 이하 "ONF"라고 함)에 의해 표준화가 추진되는 기술로서, 소프트웨어 프로그래밍을 통해 네트워크 경로 설정, 네트워크 제어 및 기타 네트워크 운용 관리를 처리할 수 있게 한다.
SDN은 네트워크의 제어 기능이 물리적 네트워크와 분리되어 있는 네트워크 구조를 의미한다. 말하자면, SDN은 네트워크의 데이터 평면 및 제어 평면을 분리하며, 양 평면들의 사이에서의 표준화된 인터페이스를 제공한다. 네트워크의 운영자는 제어 평면에 대한 프로그래밍을 통해 제공되는 인터페이스를 사용할 수 있고, 상기의 인터페이스를 통해 네트워크의 상황에 맞춰 데이터 평면에서 이루어지는 통신 기능을 제어할 수 있다.
SDN에 의해 제공되는 기능들 중 대표적인 기능들로서, 소프트웨어 정의 포워딩(Software defined forwarding) 및 글로벌 관리 추상화(Global management abstraction)가 있다.
소프트웨어 정의 포워딩은 스위치 또는 라우터의 하드웨어에 의해 처리되는 패킷 포워딩 기능이 개방형 인터페이스 및 소프트웨어에 의해 제어되는 것을 의미한다. 말하자면, 소프트웨어 정의 포워딩은 경로 구성이 소프트웨어에 의해 제어된다는 것을 의미한다.
소프트웨어 정의 포워딩을 위한 표준 인터페이스로서 오픈플로우(OpenFlow)가 널리 사용된다. 오픈플로우는 스위치 및 라우터의 기능에 대한 프로그래밍을 지원하기 위해 정의된 오픈 소스(Source) API로서, SDN을 위한 흐름 제어, 보안 및 가상화 등을 제공한다.
오픈플로우와 결합된 SDN은 기존의 네트워크에서는 구성될 수 없는 복잡한 경로 구성을 제공할 수 있으며, 경로 구성을 통해 트래픽 패턴의 변화에 대해 효과적으로 대처할 수 있고, 가상 머신(VM: Virtual Machine, 이하 "VM"이라고 함)의 생성, 삭제 및 이동이 빈번한 클라우드 환경에서 요구되는 가상 네트워크를 빠르게 구성할 수 있다는 장점을 갖는다. 또한, OpenFlow와 결합된 SDN은 빅 데이터(Big Data)의 분석을 위해 요구되는 대용량 네트워크를 상대적으로 적은 비용으로 구축할 수 있으며, 라인 레이트(Line rate)의 성능을 실현할 수 있다는 장점 또한 갖는다.
또한, 오픈플로우에 의해 하부의 멀티 벤더 네트워크 장치들이 통합하여 제어될 수 있으므로, 사용자는 벤더에 따라 상이한 API를 사용하여 네트워크 장치 별로 복잡한 절차에 따라 구성을 할 필요가 없다. 말하자면, 사용자가 소프트웨어로 네트워크를 제어한다는 특성에 따라, SDN은 복잡한 정책을 용이하게 실현할 수 있게 하고, 벤더 의존성이라는 불가피한 문제를 일시에 해결할 수 있다는 장점을 갖는다.
한국공개특허공보 제10-2013-0052030호는 '스위치 시스템, 모니터링 집중 관리 방법'에 관한 것으로서, 오픈플로우 기술에 기초한 패킷 전송 방법에 관한 내용을 개시하고 있다. 다만, 한국공개특허공보 제10-2013-0052030호의 '스위치 시스템, 모니터링 집중 관리 방법'을 포함한 종래의 오픈플로우 기술에 있어서는, 데이터 평면의 기능을 담당하는 스위치는 하드웨어에 기반하며, 하드웨어에 기반하는 스위치는 제한된 자원(Resource)를 갖는다는 근본적인 문제가 있으며, 또한 패킷을 상황에 맞게 유동적으로 처리하지 못한다는 문제점이 있다.
오픈플로우를 사용하는 네트워크 장치는 플로우 처리 엔진(Flow Processing Engine)의 구현을 위해 고성능의 플로우 처리 모듈을 사용해야 한다. 고성능의 플로우 처리 모듈로서 하드웨어 주문형 반도체(ASIC: Application Specific Integrated Circuit, 이하 "ASIC"라고 함) 및 삼진 내용 주소화 기억장치(TCAM: Ternary Content-Addressable Memory, 이하 "TCAM"이라고 함)에 기반한 구현이 성능적인 측면에서 대체 불가능한 구현 방식으로서 사용되고 있다.
하드웨어 ASIC 및 TCAM의 플로우 처리 모듈은 완전한 플로우 액션(Full flow action) 및 높은 플로우 엔트리(High flow entry)를 지원하기 위해서 높은 비용을 요구한다는 문제점을 갖는다. 말하자면, 하드웨어 ASIC 및 TCAM의 플로우 처리 모듈은 높은 하드웨어 비용 및 높은 연구 개발 비용을 요구한다는 문제점을 갖는다.
이에 본 발명자는, 하드웨어 ASIC 및 TCAM의 플로우 처리 모듈 등 다양한 플로우 처리 모듈들을 사용하여 플로우를 처리하는 것을 가능하게 하는 기술을 개발하기에 이르렀다.
본 발명은 상술한 문제점을 모두 해결하는 것을 그 목적으로 한다.
또한, 본 발명은 플로우 처리를 수행하는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 복수의 모듈들 중 플로우를 처리할 모듈을 결정하고, 플로우에 해당하는 패킷을 결정된 모듈을 사용하여 처리함으로써 제한적인 하드웨어 자원을 효율적으로 이용하여 네트워크 장치의 전체 성능을 향상시키는 것을 다른 목적으로 한다.
또한, 본 발명은 복수의 모듈들을 사용하여 플로우를 처리하는 유연한 방식을 제공함으로써 네트워크 장치의 개발 시간 및 개발 비용을 감소시키는 것을 다른 목적으로 한다.
상기 목적을 달성하기 위한 본 발명의 대표적인 구성은 다음과 같다.
본 발명의 일 태양에 따르면, 네트워크 장치를 이용하여 플로우 처리를 수행하는 방법에 있어서, (a) 플로우 처리를 수행하는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 상기 복수의 모듈들 중 플로우를 처리할 모듈을 결정하는 단계 및 (b) 상기 결정된 모듈에게 상기 플로우의 처리를 할당하는 단계를 포함하는 방법이 제공된다.
본 발명의 다른 태양에 따르면, 플로우 처리를 수행하는 네트워크 장치에 있어서, 플로우 처리를 수행하는 복수의 모듈들 및 상기 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 상기 복수의 모듈들 중 플로우를 처리할 모듈을 결정하고, 상기 결정된 모듈에게 상기 플로우의 처리를 할당하는 스케줄링부를 포함하는 장치가 제공된다.
본 발명에 의하면, 플로우 처리를 수행하는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 복수의 모듈들 중 플로우를 처리할 모듈을 결정하고, 플로우에 해당하는 패킷을 결정된 모듈을 사용하여 처리함으로써 제한적인 하드웨어 자원이 효율적으로 이용될 수 있으며, 하드웨어 자원의 효율적인 이용을 통해 네트워크 장치의 전체 성능이 향상될 수 있다.
도 1은 본 발명의 일 실시예에 따른 플로우 처리를 수행하는 네트워크 장치의 구성을 나타내는 도면이다.
도 2는 본 발명의 일 실시예에 따른 플로우의 추가에 따른 스케줄링 방법을 설명하는 흐름도이다.
도 3은 본 발명의 일 실시예에 따른 플로우의 삭제에 따른 스케줄링 방법을 설명하는 흐름도이다.
도 4는 본 발명의 일 실시예에 따른 모듈에 할당된 플로우에 대해서 할당을 재조정하는 스케줄링 방법을 설명하는 흐름도이다.
도 5는 본 발명의 일 실시예에 따른 단순 플로우 엔트리 스케줄링 방법을 설명하는 흐름도이다.
도 6은 본 발명의 일 실시예에 따른 교환 플로우 엔트리 스케줄링 방법을 설명하는 흐름도이다.
후술하는 본 발명에 대한 상세한 설명은, 본 발명이 실시될 수 있는 특정 실시예를 예시로서 도시하는 첨부 도면을 참조한다. 이들 실시예는 당업자가 본 발명을 실시할 수 있기에 충분하도록 상세히 설명된다. 본 발명의 다양한 실시예는 서로 다르지만 상호 배타적일 필요는 없음이 이해되어야 한다. 예를 들어, 여기에 기재되어 있는 특정 형상, 구조 및 특성은 일 실시예에 관련하여 본 발명의 정신 및 범위를 벗어나지 않으면서 다른 실시예로 구현될 수 있다. 또한, 각각의 개시된 실시예 내의 개별 구성요소의 위치 또는 배치는 본 발명의 정신 및 범위를 벗어나지 않으면서 변경될 수 있음이 이해되어야 한다. 따라서, 후술하는 상세한 설명은 한정적인 의미로서 취하려는 것이 아니며, 본 발명의 범위는, 적절하게 설명된다면, 그 청구항들이 주장하는 것과 균등한 모든 범위와 더불어 첨부된 청구항에 의해서만 한정된다. 도면에서 유사한 참조부호는 여러 측면에 걸쳐서 동일하거나 유사한 기능을 지칭한다.
이하, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자가 본 발명을 용이하게 실시할 수 있도록 하기 위하여, 본 발명의 바람직한 실시예들에 관하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.
도 1은 본 발명에 일 실시예에 따른 플로우 처리를 수행하는 네트워크 장치의 구성을 나타내는 도면이다.
도 1에 도시되어 있는 바와 같이, 네트워크 장치(100)는 동기화부(Sync) (110), 정책부(Policy engine)(120), 스케줄링부(Scheduler)(130), 통계부(Statistics)(140), 배치부(Dispatcher)(150), 복수의 모듈들 및 복수의 드라이버들을 포함하여 구성될 수 있다. 동기화부(110), 정책부(120), 스케줄링부(130), 통계부(140), 배치부(150), 복수의 모듈들 및 복수의 드라이버들은 그 중 적어도 일부가 외부와 통신하는 프로그램 모듈들일 수 있다. 이러한 프로그램 모듈들은 운영 시스템, 응용 프로그램 모듈 및 기타 프로그램 모듈의 형태로 네트워크 장치(100)에 포함될 수 있으며, 물리적으로는 여러 가지 공지의 기억 장치 상에 저장될 수 있다. 또한, 이러한 프로그램 모듈 중 적어도 일부는 네트워크 장치(100)와 통신 가능한 원격 기억 장치에 저장될 수도 있다. 한편, 이러한 프로그램 모듈들은 본 발명에 따라 후술할 특정 업무를 수행하거나 특정 추상 데이터 유형을 실행하는 루틴, 서브루틴, 프로그램, 오브젝트, 컴포넌트, 데이터 구조 등을 포괄하지만, 이에 제한되지는 않는다. 프로그램 모듈들은 네트워크 장치(100)가 포함하는 프로세서에 의해 수행될 수 있다.
본 발명의 일 실시예에 따르면, 네트워크 장치(100)는 복수의 모듈들을 사용하여 플로우를 처리할 수 있다. 복수의 모듈들의 각 모듈은 플로우 처리 모듈일 수 있다. 도 1에서, 복수의 모듈들로서 제1 모듈(161), 제2 모듈(162) 및 제3 모듈(163)이 도시되었다.
본 발명의 일 실시예에 따르면, 복수의 모듈들의 각 모듈은, 1) 스위칭 ASIC 및 TCAM의 모듈(또는, 스위칭 패브릭(Fabric) TCAM의 모듈), 2) 네트워크 프로세서(Network processor)의 모듈, 3) 최적화된 소프트웨어 데이터 평면(Optimized software dataplane)의 모듈, 4) 커널 데이터 평면(Kernel dataplane)의 모듈, 5) 사용자 공간 데이터 평면(Userspace dataplane)의 모듈 및 6) 제어기 데이터 평면(Controller dataplane)의 모듈(또는, 원격 데이터 평면(Remote dataplane)의 모듈) 중 하나일 수 있다. 예를 들면, 제1 모듈(161)은 스위칭 ASIC 및 TCAM의 모듈일 수 있고, 제2 모듈(162)은 네트워크 프로세서일 수 있고, 제3 모듈(163)은 최적화된 소프트웨어 데이터 평면의 모듈일 수 있다.
본 발명의 일 실시예에 따르면, 복수의 모듈들은 기능 및 성능 중 적어도 하나에 있어서 서로 상이할 수 있다. 예를 들면, 복수의 모듈들 중 상대적으로 제한적인 기능이 제공되나 상대적으로 우수한 성능(빠른 플로우 처리)을 갖는 모듈이 있을 수 있으며, 상대적으로 넓은 기능이 제공되나 상대적으로 낮은 성능(느린 플로우 처리)을 갖는 모듈이 있을 수 있다.
본 발명의 일 실시예에 따르면, 복수의 모듈들은 기능에 있어서 서로 상이할 수 있다. 플로우의 매치 키(Match key) 및 액션(Action)에 따라, 플로우 별로 복수의 모듈들 중 플로우를 처리할 수 있는 모듈이 제한될 수 있다. 말하자면, 모든 플로우들이 동일한 모듈을 통해 처리될 수 있는 것은 아니다. 말하자면, 플로우의 매치 키 및 액션에 따라 적용 가능한(Applicable) 모듈 목록(List) 내의 모듈 집합(Set)이 서로 상이할 수 있다. 예를 들면, TCAM의 모듈에 대해서는 매치에 이용될 수 있는 키가 제한될 수 있다. 또한, ASIC을 통한 액션의 처리는 주어진 세트(예를 들면, VLAN TAG 푸쉬(Push) 및 팝(Pop))에 대해서만 가능할 수 있다.
본 발명의 일 실시예에 따르면, 복수의 모듈들 및 복수의 드라이버들은 각각 대응할 수 있다. 도 1에서, 제1 모듈(161), 제2 모듈(162) 및 제3 모듈(163)에 각각 대응하는 제1 드라이버(171), 제2 드라이버(172) 및 제3 드라이버(173)가 도시되었다. 드라이버는 대응하는 모듈에 접근하기 위한 기능을 제공할 수 있다. 배치부(150)는 복수의 드라이버들을 추상적(Abstraction)으로 표현함으로써 스케줄링부(130)에게 복수의 드라이버들에 대한 접근을 제공할 수 있다. 말하자면, 스케줄링부(130)는 배치부(150) 및 드라이버를 통해, 드라이버에 대응하는 모듈에 접근할 수 있다.
본 발명의 일 실시예에 따르면, 배치부(150) 및 드라이버를 통해, 모듈 및 스케줄링부(130) 간의 표준 인터페이스가 제공될 수 있다. 표준 인터페이스를 사용함으로써, 새로운 모듈이 스케줄링부(130)에 독립적으로 개발될 수 있고, 복수의 모듈들에 용이하게 추가될 수 있다.
아래에서, 본 발명의 일 실시예에 따른 네트워크 장치(100)를 이용하여 플로우 처리를 수행하는 방법이 설명된다.
(i) 먼저, 동기화부(110)는 플로우에 관련된 정보를 동기화할 수 있다.
플로우에 관련된 정보는 네트워크 장치(100)가 처리하는 하나 이상의 플로우들에 대한 정보 및 상기의 하나 이상의 플로우들에 대한 플로우 별 통계 값을 포함할 수 있다.
동기화부(110)는 커널 데이터 평면과의 동기화를 수행함으로써 커널 데이터 평면으로부터 플로우에 관련된 정보를 획득할 수 있다. 동기화부(110)는 네트워크 장치(100)의 커널 데이터 평면으로부터 하나 이상의 플로우들에 대한 정보를 획득할 수 있고, 획득한 하나 이상의 플로우들에 대한 정보를 사용하여 플로우의 추가, 플로우의 삭제 및 플로우의 동기화를 수행할 수 있다. 말하자면, 동기화부(110)는 네트워크 장치(100)의 커널 데이터 평면을 동적 플로우 분배기와 동기화할 수 있다. 동적 플로우 분배기는 네트워크 장치 중 동적 플로우 분배의 기능을 수행하는 부분을 의미할 수 있다.
동기화에 의해 동기화부(110)는 동기화된 하나 이상의 플로우들의 엔트리들을 스케줄링부(130)에게 제공할 수 있다.
동기화부(110)는 통계부(140)로부터 플로우 별 통계 값을 획득할 수 있다.
(ii) 다음으로, 정책부(120)는 구성된 정책을 스케줄링부(130)에게 제공할 수 있다. 정책은 네트워크 장치(100)의 동적 플로우 분배의 기능을 제어할 수 있다.
네트워크 장치(100)의 사용자는 정책 API를 호출하는 사용자 공간 어플리케이션(Userspace application)을 사용하여 정책을 구성할 수 있다.
정책 API는 명령어 세트를 제공할 수 있다. 하기의 표 1은 본 발명의 일 실시예에 따른 명령어 세트를 설명한다.
명령어 설명
스케줄러 온/오프(ON/OFF) 스케줄링부(130)를 사용하는 복수의 모듈들의 스위칭의 수행 여부를 결정
플로우 우선 순위(Priority) 설정 플로우의 우선 순위를 지정. 플로우의 우선 순위를 조정하기 위해 사용됨.
모듈 별 플로우 우선 순위 설정 모듈 별로 플로우의 우선 순위를 지정. 특정한 모듈에 대한 플로우의 우선 순위를 조정하기 위해 사용됨.
예를 들면, 레이턴시(Latency)가 낮은 모듈에 할당될 것이 요구되는 플로우는 복수의 모듈들 중 레이턴시가 낮은 모듈에 대해서는 높은 모듈 별 플로우 우선 순위를 갖고, 레이턴시가 높은 모듈에 대해서는 낮은 모듈 별 플로우 우선 순위를 가짐.
모듈 우선 순위 설정 모듈의 우선 순위를 지정. 모듈에서 장애가 발생할 경우, 장애 극복(Fail-Over)를 위해서 사용됨.
즉시 스케줄(Schedule NOW) 즉시 스케줄링을 수행함.
예를 들면, 모듈에서 장애가 발애가 발생하여 모듈의 우선 순위가 조정된 경우, 조정된 우선 순위를 빠르게 적용하기 위해 새로운 스케줄링이 수행됨.
정책부(120)는 구성된 정책에 따라 스케줄링부(130)를 제어할 수 있다.
(iii) 다음으로, 스케줄링부(130)는 정책에 기반하여 플로우 처리를 수행하는 복수의 모듈들 중 플로우를 처리할 모듈을 결정할 수 있다.
스케줄링부(130)는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 플로우를 처리할 모듈을 결정할 수 있다.
본 발명의 일 실시예에 따르면, 플로우에 대한 처리 비용은 복수의 모듈들에 대해서 2개 이상의 상이한 방식으로 결정될 수 있다. 예를 들면, 소프트웨어 데이터 평면의 모듈에서의 플로우의 처리는 컨텍스트 스위칭(Context switching)의 비용을 감소시키기 위해 단일 쓰레드(Single thread)에 의해 실행되므로, 소프트웨어 데이터 평면의 모듈의 플로우에 대한 처리 비용은 타임 스탬프 카운터(Time Stamp Counter) 명령어에 의해 계산될 수 있다. 또한, 스위칭 ASIC 및 TCAM의 모듈의 플로우에 대한 처리 비용은 패킷의 실제 레이턴시(Latency)에 의해 계산될 수 있다.
또한, 본 발명의 일 실시예에 따르면, 복수의 모듈들 중 적어도 하나의 모듈은 플로우에 대한 처리 비용을 실측할 수 있다.
본 발명의 일 실시예에 따르면, 정책 중 하나는 네트워크 장치(100)가 처리하는 하나 이상의 플로우들에 대한 총 비용이 최소값이 되도록 하나 이상의 플로우들의 각 플로우를 처리할 모듈을 복수의 모듈들 중에서 결정하는 것일 수 있다.
하기의 표 2는 본 발명의 일 실시예에 따른 비용과 관련된 변수들을 설명한다.
변수 약어 설명
총 비용(Total Cost) TC 네트워크 장치(100)의 복수의 모듈들이 처리하는 하나 이상의 플로우들에 대한 총 비용.
모듈 비용(Module Cost) MC 복수의 모듈들 중 하나의 모듈에 대한 비용. 모듈에 할당된 플로우들에 대한 총 비용.
모듈 비용 우선 순위(Module Cost PRIority modifier) MC_PRI 모듈의 우선 순위. 모듈의 우선 순위를 설정 및 변경하기 위해 사용됨.
MC_PRI에 의해 모듈 별로 우선 순위가 조정될 수 있고, MC_PRI의 조정을 통해 모듈 결함(Failure)에 대한 대응이 이루어질 수 있다.
플로우 비용(Flow Cost) FC 플로우에 대한 처리 비용. 플로우를 처리하기 위해 소모되는 비용.
초 당 패킷(Packet Per Sec) PPS 플로우에 해당되는 패킷의 초(또는, 단위 시간) 당 개수.
패킷 당 처리 비용 (Cost Per Packet) CPP 플로우에 해당되는 패킷의 패킷당 처리 비용.
플로우 비용 우선 순위(Flow Cost PRIority modifier) FC_PRI 플로우의 우선 순위. 플로우의 우선 순위를 설정 및 변경하기 위해 사용됨.
FC_PRI에 의해, 플로우 별로 우선 순위가 조정될 수 있고, 특정한 플로우의 우선 순위가 상승될 수 있음.
모듈 별 플로우 비용 우선 순위(Per Module Flow Cost PRIority modifier) PM_FC_PRI[] 특정한 모듈에서의 플로우의 우선 순위. 플로우의 특정한 모듈에서의 우선 순위를 설정 및 변경하기 위해 사용됨.
PM_FC_PRI를 통해 플로우의 모듈 선호도가 지정될 수 있으며, 플로우의 속성에 맞는 모듈 선호도가 지정될 수 있음.
모듈 별 CPP(Per Module CPP) PM_CPP 모듈에게 할당된 플로우들의 CPP들의 평균.
모듈 별 PPS(Per Module PPS) PM_PPS 모듈에게 할당된 플로우들의 PPS들의 평균.
기본 PPS(Default PPS) DEFAULT_PPS 플로우의 기본적인 PPS
이하에서, 상기의 변수들은 함께 설명된 약어를 사용하여 약술한다.
본 발명의 일 실시예에 따르면, 상기의 변수들은 하기의 수학식 1 내지 수학식 3에 따라서 정의될 수 있다.
Figure 112014072436999-pat00001
예를 들면, TC의 값은 복수의 모듈들의 MC들의 합일 수 있다.
Figure 112014072436999-pat00002
예를 들면, MC의 값은 모듈에 할당된 플로우들의 FC들의 전체의 합에 MC_PRI를 적용한 값일 수 있다.
Figure 112014072436999-pat00003
예를 들면, FC의 값은 모듈에서의 플로우의 처리를 위하여 소모된 비용(또는, 비용을 나타내는 값)에 FC_PRI 및 모듈의 PM_FC_PRI를 적용한 값일 수 있다. MODULE_ID는 모듈의 식별자이다.
본 발명의 일 실시예에 따르면, 수학식 1 및 수학식 2에서 나타난 것과 같이, TC는 복수 모듈들의 각 모듈에 대한 MC에 기반하여 결정될 수 있고, 각 모듈의 MC는 하나 이상의 플로우들 중 각 모듈에게 할당된 플로우들의 각 플로우에 대한 처리 비용에 기반하여 결정될 수 있다.
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 하나 이상의 플로우들에 대한 스케줄링을 주기적으로 수행할 수 있다.
본 발명의 일 실시예에 따른 스케줄링 방법들이 하기에서 도 2 내지 도 6을 참조하여 상세하게 설명된다.
(iv) 다음으로, 스케줄링부(130)는 플로우를 처리할 것으로 결정된 모듈에게 플로우의 처리를 할당할 수 있다.
스케줄링부(130)는 배치부(150)를 통해 모듈의 드라이버에게 플로우를 분배할 수 있다. 드라이버에게 분배된 플로우는 모듈에게 할당될 수 있다.
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 배치부(150) 및 복수의 드라이버들을 통해 복수의 모듈들에게 하나 이상의 플로우들을 할당할 수 있다. 말하자면, 스케줄링부(130)는 하나 이상의 플로우들의 각 플로우를 복수의 모듈들 중 상기의 각 플로우를 처리하도록 결정된 모듈에게 할당할 수 있다.
(v) 다음으로, 플로우를 처리하도록 결정된 모듈은 플로우에 해당하는 패킷의 처리를 수행할 수 있다. 복수의 모듈들의 각 모듈은 상기의 각 모듈에게 할당된 플로우를 처리할 수 있다.
(vi) 다음으로, 통계부(140)는 플로우의 처리에 관련된 통계값을 생성할 수 있다.
본 발명의 일 실시예에 따르면, 통계값은 표 1을 참조하여 설명된 변수를 포함할 수 있다.
본 발명의 일 실시예에 따르면, 배치부(150)는 복수의 모듈들에 대응하는 복수의 드라이버들로부터 모듈에 할당된 플로우들에 관련된 통계값 또는 통계값의 데이터를 획득할 수 있다. 통계부(140)는 배치부(150)로부터 통계값 또는 통계값의 데이터를 획득할 수 있다. 통계값 드라이버는 대응하는 모듈에 할당된 플로우들에 관련된 통계값을 배치부(150)를 통해 통계부(140)에게 제공할 수 있다. 말하자면, 드라이버는 통계값의 생성에 요구되는 데이터를 측정하여 측정된 데이터를 스케줄링부(130)에게 제공하거나, 통계값을 측정하여 측정된 통계값을 스케줄링부(130)에게 제공할 수 있다.
본 발명의 일 실시예에 따르면, 통계부(140)는 통계값을 생성 또는 저장할 수 있다. 일 실시예에 따르면 통계부(140)는 플로우 별 통계값을 생성 또는 저장할 수 있으며, 모듈 별 통계값을 생성 또는 저장할 수 있다.
본 발명의 일 실시예에 따르면, 동기화부(110)는 통계부(140)로부터 통계값을 획득하고, 획득한 통계값에 기반하여 하나 이상의 플로우들에 대한 스케줄링을 수행할 수 있다. 스케줄링부(130)는 주기적으로 통계부(140)에 저장된 통계값을 검사할 수 있고, 통계값이 변경된 경우 스케줄링을 다시 수행할 수 있다.
본 발명의 일 실시예에 따르면, 통계값은 특정한 모듈이 플로우에 대해 실측한 비용일 수 있다. 플로우의 복잡도에 따라 플로우 처리 성능(또는, 플로우의 처리에 따른 비용)에서 차이가 발생할 수 있다. 플로우의 처리에 따른 비용을 스케줄링에 있어서의 판단 기준으로 사용하기 위해, 플로우의 처리에 따른 비용이 실제로 계측될 수 있고, 실측에 기반하여 통계값이 생성될 수 있다.
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 복수의 모듈들이 플로우에 대해 실측한 비용에 기반하여 플로우를 처리할 모듈을 결정할 수 있다. 예를 들면, 스케줄링부(130)는 복수의 모듈들이 하나 이상의 플로우들의 각 플로우에 대해 실측한 비용에 기반하여 복수의 모듈들 중 상기의 각 플로우를 처리할 모듈을 결정할 수 있다.
본 발명의 일 실시예에 따르면, 모듈 및 드라이버에 의해 실측된 비용은 네트워크 장치(100)의 실제 동작을 반영할 수 있고, 모듈들 간의 연관 관계 등을 모두 반영할 수 있다. 스케줄링부(130)는 주기적인 비용에 대한 실측 및 상기의 실측의 반영을 통해 복수의 모듈들 중 상호 연관 관계를 갖거나, 자원을 공유하는 2개 이상의 모듈들의 비용들을 적응적으로 조정할 수 있다.
정책에 따른 스케줄링의 실시예
도 2는 본 발명의 일 실시예에 따른 플로우의 추가에 따른 스케줄링 방법을 설명하는 흐름도이다.
하기의 단계들(S210 내지 S280)은 네트워크 장치(100)가 새로운 플로우를 네트워크 장치(100)가 처리할 하나 이상의 플로우들로서 추가하기 위해 수행될 수 있다.
(i) 스케줄링부(130)는 네트워크 장치(100)의 복수의 모듈들 중 플로우의 처리가 가능한 하나 이상의 모듈들을 식별할 수 있다(S210). 스케줄링부(130)는 식별된 하나 이상의 모듈들의 모듈 목록을 생성할 수 있다. 모듈 목록은 플로우가 추가될 수 있는 모듈들의 목록일 수 있다.
본 발명의 일 실시예에 따르면, 복수의 모듈들 중 플로우의 처리가 가능한 모듈은 플로우의 속성에 따라 제한될 수 있다. 예를 들면, 플로우의 매치 키(Match Key) 및 액션(Action) 에 의해, 특정한 모듈은 플로우를 처리하지 못할 수 있다. 말하자면, 특정한 모듈이 특정한 플로우의 처리를 할 수 있는지 여부는 모듈의 속성 및 플로우의 속성에 따라 결정될 수 있다.
이하에서, 스케줄링부(130)는 플로우의 처리가 가능한 것으로 식별된 하나 이상의 모듈들 중 플로우를 처리할 모듈을 결정할 수 있다(S220 내지 S290)
(ii) 스케줄링부(130)는 식별된 하나 이상의 모듈들의 각 모듈에 대해서, 상기의 각 모듈에 플로우가 삽입될 경우에 예상되는 플로우에 대한 처리 비용 FC를 계산할 수 있다(S220). PPS의 값이 DEFAULT_PPS의 값과 같고, CPP의 값이 PM_CPP[MOUDLE_ID]의 값과 같다면, FC의 값은 하기의 수학식 4와 같이 계산될 수 있다.
Figure 112014072436999-pat00004
스케줄링부(130)는 식별된 하나 이상의 모듈들에 대해 계산된 FC들에 대해, FC들의 목록을 생성할 수 있다.
(iii) 스케줄링부(130)는 식별된 하나 이상의 모듈들을 소정의 우선 순위에 따라 정렬할 수 있다(S230).
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 식별된 하나 이상의 모듈들을 계산된 FC의 오름차순으로 정렬할 수 있다(S230). 스케줄링부(130)는 플로우를 새로운 플로우로서 추가함에 있어서, 네트워크 장치(100)의 복수의 모듈들에 대하여 플로우에 대한 처리 비용의 오름차순으로 플로우를 처리할 모듈을 결정할 수 있다. 스케줄링부(130)는 우선 기대되는 비용이 가장 낮은 모듈에 플로우의 추가를 시도할 수 있고, 추가가 불가능한 경우 순차적으로 다음으로 비용이 낮은 모듈에 플로우의 추가를 시도할 수 있다.
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 복수의 모듈들 중 계산된 FC가 소정의 값 이하인 모듈이 우선적으로 선택되도록 식별된 하나 이상의 모듈들을 정렬할 수 있다.
또한, 본 발명의 일 실시예에 따르면, 스케줄링부(130)는 식별된 하나 이상의 모듈들에 대해 계산된 FC들이 플로우의 할당에 반영되도록, 계산된 FC들에 기반하여 식별된 하나 이상의 모듈들을 정렬할 수 있다. 계산된 FC들이 정렬에 사용되지 않을 경우, 단계(220)는 생략될 수 있다.
(iv) 스케줄링부(130)는 우선 순위에 따라 정렬된 하나 이상의 모듈들 중 첫 번째의 모듈을 선택할 수 있다(S240).
(v) 스케줄링부(130)는 선택된 모듈에 플로우의 삽입이 가능한지 여부를 확인할 수 있다(S250).
본 발명의 일 실시예에 따르면, 복수의 모듈들의 각 모듈들은 제한된 자원을 가질 수 있다. 말하자면, 각 모듈은 제한된 개수의 플로우 엔트리(entry)를 가질 수 있다. 모듈의 플로우 엔트리는 모듈에게 할당된 플로우에 대응할 수 있으며, 모듈이 처리하는 플로우를 나타낼 수 있다. 각 모듈은 모듈이 가진 플로우 엔트리의 개수만큼의 플로우들만 처리할 수 있고, 플로우 엔트리의 개수만큼의 플로우들만 할당 받을 수 있다. 일반적으로, 고성능 및 고속의 하드웨어 모듈일수록 제한된 개수의 플로우 엔트리를 가질 수 있다.
선택된 모듈이 여분의 플로우 엔트리(말하자면, 플로우가 할당되지 않은 플로우 엔트리)를 가진 경우, 선택된 모듈에 플로우가 삽입될 수 있다.
삽입이 가능한 경우 단계(S260)가 수행될 수 있다. 삽입이 가능하지 않은 경우 단계(S270)가 수행될 수 있다.
(vi) 스케줄링부(130)는 선택된 모듈에 플로우를 삽입할 수 있다. 스케줄링부(130)는 복수의 모듈들 중 선택된 모듈을 플로우를 처리할 모듈로서 결정할 수 있다(S260).
플로우가 선택된 모듈에 삽입된 후 절차가 종료할 수 있다.
(vii) 스케줄링부(130)는 식별된 하나 이상의 모듈들 중 남은 모듈이 존재하는지 여부를 판단할 수 있다(S270).
남은 모듈이 존재하는 경우 단계(S280)가 수행될 수 있다. 남은 모듈이 존재하지 않는 경우, 어떤 모듈에도 플로우의 삽입이 가능하지 않을 수 있다. 플로우의 삽입이 가능한 모듈이 존재하지 않는 경우 플로우의 추가는 실패하고, 절차가 종료할 수 있다.
(viii) 스케줄링부(130)는 남은 모듈이 존재할 경우 다음으로 비용이 낮은 모듈을 선택할 수 있다(S280). 다음으로, 단계(S250)가 반복될 수 있다.
도 3은 본 발명의 일 실시예에 따른 플로우의 삭제에 따른 스케줄링 방법을 설명하는 흐름도이다.
하기의 단계들(S310 및 S320)은 네트워크 장치(100)가 네트워크 장치(100)가 처리할 하나 이상의 플로우들 중 선택된 플로우를 제거하기 위하 수행될 수 있다.
(i) 스케줄링부(130)는 복수의 모듈들 중 선택된 플로우가 할당된 모듈을 식별할 수 있다(S310).
(ii) 스케줄링부(130)는 식별된 모듈에서 선택된 플로우를 삭제할 수 있다(S320).
본 발명의 실시예에 따르면, 스케줄링부(130)는 식별된 모듈의 플로우 엔트리에서 선택된 플로우를 삭제할 수 있다.
도 4는 본 발명의 일 실시예에 따른 모듈에 할당된 플로우에 대해서 할당을 재조정하는 스케줄링 방법을 설명하는 흐름도이다.
스케줄링부(130)는 플로우의 할당의 재조정을 통해 플로우가 할당된 모듈을 교체함으로써 TC를 감소시킬 수 있다. 스케줄링부(130)는 플로우를 서로 상이한 PM_CPP를 갖는 모듈들 사이에서 교체하여 할당함으로써 TC를 감소시킬 수 있다.
하기의 단계들(S410 내지 S475)은 네트워크 장치(100)가 하나 이상의 플로우들의 각 플로우가 할당된 모듈을 변경하기 위해 수행될 수 있다. 하기의 단계들(S410 내지 S475)에서, 스케줄링부(130)는 하나 이상의 플로우들에 대한 비용들을 종합하여, 모듈들 간의 플로우의 할당의 이동 또는 교환의 여부를 결정할 수 있다. 플로우의 할당을 이동 또는 교환함으로써 TC가 감소될 수 있는 경우, 플로우의 할당의 이동 또는 교환이 이루어질 수 있다.
(i) 스케줄링부(130)는 네트워크 장치(100)가 처리할 하나 이상의 플로우들을 소정의 우선 순위에 따라 정렬함으로써 정렬된 하나 이상의 플로우들의 목록을 생성할 수 있다.
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 네트워크 장치(100)가 처리할 하나 이상의 플로우들을 플로우의 FC의 내림차순으로 정렬함으로써 정렬된 하나 이상의 플로우들의 목록을 생성할 수 있다(S410). 말하자면, FC의 값이 더 클수록 모듈의 교체를 통한 FC의 감소의 가능성이 더 상승할 수 있기 때문에, FC의 값이 더 큰 플로우일수록 더 우선적으로 모듈의 교체의 대상이 될 수 있다.
(ii) 스케줄링부(130)는 정렬된 하나 이상의 플로우들의 목록에서, 할당된 모듈의 변경에 의한 FC의 감소가 불가능한 플로우를 제거할 수 있다(S415). 말하자면, 하나 이상의 플로우들 중 이미 최적의 모듈에 할당된 플로우는 이하의 처리의 대상에서 제외될 수 있다.
(iii) 스케줄링부(130)는 정렬된 하나 이상의 플로우들 중 첫 번째의 플로우를 선택할 수 있다(S420).
(iv) 스케줄링부(130)는 네트워크 장치(100)의 복수의 모듈들 중 선택된 플로우의 처리가 가능한 하나 이상의 모듈들을 식별할 수 있다(S425). 스케줄링부(130)는 식별된 하나 이상의 모듈들의 모듈 목록을 생성할 수 있다.
(v) 스케줄링부(130)는 식별된 하나 이상의 모듈들의 각 모듈에 대해서, 상기의 각 모듈에 선택된 플로우가 삽입될 경우에 예상되는 플로우에 대한 처리 비용 FC를 계산할 수 있다(S430).
스케줄링부(130)는 식별된 하나 이상의 모듈들에 대해 계산된 FC들의 목록을 생성할 수 있다.
(vi) 스케줄링부(130)는 식별된 하나 이상의 모듈들을 소정의 우선 순위에 따라 정렬할 수 있다.
스케줄링부(130)는 식별된 하나 이상의 모듈들을 계산된 FC의 오름차순으로 정렬할 수 있다. 상기의 정렬을 통해 이하의 처리에 있어서 TC의 감소의 기대값이 더 큰 모듈이 더 우선적으로 스케줄링의 대상이 될 수 있다.
(vii) 스케줄링부(130)는 우선 순위에 따라 정렬된 하나 이상의 모듈들 중 첫 번째의 모듈을 선택할 수 있다(S440).
(viiii) 스케줄링부(130)는 선택된 플로우에 대한 선택된 모듈의 FC 및 플로우가 현재 할당된 모듈의 FC를 비교할 수 있다(S445).
선택된 모듈의 FC가 현재 할당된 모듈의 FC의 이상이라면, 선택된 플로우에 대한 모듈의 변경이 불필요할 수 있다. 말하자면, 선택된 플로우에 대해 모듈이 변경되더라도, TC는 감소하지 않을 수 있다. 선택된 모듈의 FC가 현재 할당된 모듈의 FC의 이상인 경우 단계(S450)가 수행될 수 있고, 선택된 모듈의 FC가 현재 할당된 모듈의 FC 보다 더 작은 경우 단계(S465)가 수행될 수 있다.
(ix) 스케줄링부(130)는 정렬된 하나 이상의 플로우들 중 남은 플로우가 존재하는지 여부를 판단할 수 있다(S450).
남은 플로우가 존재할 경우 단계(S460)가 수행될 수 있다. 남은 플로우가 존재하지 않은 경우 모든 플로우들에 대한 처리가 완료되고, 절차가 종료할 수 있다.
(x) 스케줄링부(130)는 남은 플로우가 존재할 경우 정렬된 하나 이상의 플로우들 중 다음의 플로우를 선택할 수 있다(S460). 다음으로, 새로 선택된 플로우에 대해 단계(S425)가 다시 수행될 수 있다.
전술된 단계(S420) 및 단계(S460)에 의해 하나 이상의 플로우들에 대해 스케줄링이 반복(iteration)될 수 있다.
아래에서는, 본 발명의 일 실시예에 따른, 선택된 플로우에 대한 구체적인 처리 과정이 설명된다.
(xi) 우선, 스케줄링부(130)는 선택된 플로우에 대한 단순 플로우 엔트리 스케줄링을 시도할 수 있다(S465).
본 발명의 일 실시예에 따르면, 단순 플로우 엔트리 스케줄링은 선택된 플로우의 할당을 선택된 모듈로 이동시키는 것일 수 있다. 단순 플로우 엔트리 스케줄링은 선택된 모듈로 플로우의 할당을 이동할 수 있는 경우 성공할 수 있고, 선택된 모듈로 플로우의 할당을 이동할 수 없는 경우 실패할 수 있다.
단순 플로우 엔트리 스케줄링이 성공한 경우, 다음의 플로우에 대한 처리를 위해 단계(S450)가 수행될 수 있다. 단순 플로우 엔트리 스케줄링이 실패한 경우, 단계(S470)가 수행될 수 있다.
선택된 플로우 본 발명의 일 실시예에 따른 단순 플로우 엔트리 스케줄링에 대해, 하기에서 도 5를 참조하여 상세히 설명된다.
(xii) 다음으로, 스케줄링부(130)는 선택된 플로우에 대한 교환(Swap) 플로우 엔트리 스케줄링을 시도할 수 있다(S470).
교환 플로우 엔트리 스케줄링은 선택된 플로우를 선택된 모듈에 할당하면서, 선택된 모듈에게 할당된 다른 플로우를 선택된 플로우를 처리하고 있던 모듈에게 할당하는 것일 수 있다. 말하자면, 교환 플로우 엔트리 스케줄링은 2개의 모듈들 간의 할당된 플로우들의 교환일 수 있다. 교환 플로우 엔트리 스케줄링은 선택된 모듈과 플로우의 할당을 교환할 수 있는 경우 성공할 수 있고, 선택된 모듈과 플로우의 할당을 교환할 수 없는 경우 실패할 수 있다.
교환 플로우 엔트리 스케줄링이 성공한 경우, 다음의 플로우에 대한 처리를 위해 단계(S450)가 수행될 수 있다. 교환 플로우 엔트리 스케줄링이 실패한 경우, 다음의 모듈에 대한 처리를 위해 단계(S475)가 수행될 수 있다.
본 발명의 일 실시예에 따른 교환 플로우 엔트리 스케줄링에 대해, 하기에서 도 6을 참조하여 상세히 설명된다.
(xiii) 스케줄링부(130)는 다음으로 비용이 낮은 모듈을 선택할 수 있다(S475). 다음으로, 새로 선택된 모듈에 대해 단계(S445)이 다시 수행될 수 있다.
전술된 단계(S440) 및 단계(S475)에 의해 복수의 모듈들에 대해 스케줄링이 반복(iteration)될 수 있다.
도 5는 본 발명의 일 실시예에 따른 단순 플로우 엔트리 스케줄링 방법을 설명하는 흐름도이다.
하기의 단계들(S510 내지 S540)은 도 4를 참조하여 전술된 단순 플로우 엔트리 스케줄링을 위해 수행될 수 있다.
아래에서, 제1 플로우는 도 4를 참조하여 전술된 단계(S420) 또는 단계(S460)에서 선택된 플로우를 나타낼 수 있다. 제1 모듈은 복수의 모듈들 중 제1 플로우가 할당된 모듈을 나타낼 수 있다. 제2 모듈은 복수의 모듈들 중 도 4를 참조하여 전술된 단계(S440) 또는 단계(S475)에서 선택된 모듈을 나타낼 수 있다. 말하자면, 제1 모듈은 플로우의 이동에 있어서의 소스(Source) 모듈이고, 제2 모듈은 플로우의 이동에 있어서의 타겟(Target) 모듈일 수 있다.
(i) 스케줄링부(130)는 제2 모듈에 플로우를 추가로 할당할 수 있는지 여부를 판단할 수 있다(S510).
전술된 것처럼, 모듈은 제한된 개수의 플로우 엔트리들을 가질 수 있다. 본 발명의 일 실시예에 따르면, 스케줄링부(130)는 제2 모듈의 플로우 엔트리들 중 플로우가 할당되지 않은 빈 플로우 엔트리가 있을 경우 제2 모듈에 플로우를 추가로 할당할 수 있는 것으로 판단할 수 있고, 빈 플로우 엔트리가 없는 경우 제2 모듈에 플로우를 추가로 할당할 수 없는 것으로 판단할 수 있다.
제2 모듈에 플로우를 추가로 할당할 수 있는 경우 단계(S520)가 수행될 수 있고, 제2 모듈에 플로우를 추가로 할당할 수 없는 경우 단계(S550)가 수행될 수 있다.
(ii) 제2 모듈에 플로우를 추가로 할당할 수 있는 경우, 스케줄링부(130)는 제1 플로우의 할당을 제1 모듈에서 제2 모듈로 이동할 수 있다(S530). 스케줄링부(130)는 제1 모듈에서 제1 플로우를 삭제할 수 있고, 제2 모듈에 제1 플로우를 할당할 수 있다.
(iii) 플로우가 이동되면, 스케줄링부(130)는 단순 플로우 엔트리 스케줄링의 결과로서 "성공"을 반환할 수 있다(S540).
(iv) 제2 모듈에 플로우를 추가로 할당할 수 없는 경우, 스케줄링부(130)는 단순 플로우 엔트리 스케줄링의 결과로서 "실패"를 반환할 수 있다(S540).
도 6은 본 발명의 일 실시예에 따른 교환 플로우 엔트리 스케줄링 방법을 설명하는 흐름도이다.
하기의 단계들(S610 내지 S670)은 도 4를 참조하여 전술된 교환 플로우 엔트리 스케줄링을 위해 수행될 수 있다.
아래에서, 제1 플로우는 도 4를 참조하여 전술된 단계(S420) 또는 단계(S460)에서 선택된 플로우를 나타낼 수 있다. 제1 모듈은 복수의 모듈들 중 제1 플로우가 할당된 모듈을 나타낼 수 있다. 제2 모듈은 복수의 모듈들 중 도 4를 참조하여 전술된 단계(S440) 또는 단계(S475)에서 선택된 모듈을 나타낼 수 있다. 제2 플로우는 제2 모듈에 할당된 플로우들 중 후술될 반복에서 선택된 플로우를 나타낼 수 있다. 말하자면, 제1 모듈은 플로우의 이동에 있어서의 소스(Source) 모듈이고, 제2 모듈은 플로우의 이동에 있어서의 타겟(Target) 모듈일 수 있다. 제1 플로우 및 제2 플로우는 교환의 대상인 플로우들일 수 있다.
(i) 스케줄링부(130)는 제2 모듈에 할당된 플로우들 중 제1 모듈에 할당될 수 있는 하나 이상의 플로우들을 식별할 수 있다. 스케줄링부(130)는 식별된 하나 이상의 플로우들의 목록을 생성할 수 있다(S610).
(ii) 스케줄링부(130)는 식별된 하나 이상의 플로우들의 각 플로우에 대하여 상기의 각 플로우가 제1 모듈에 삽입될 경우에 예상되는 플로우에 대한 처리 비용 FC를 계산할 수 있다(S620).
(iii) 스케줄링부(130)는 식별된 하나 이상의 플로우들 중 가장 낮은 FC를 갖는 플로우를 제2 플로우로서 선택할 수 있다(S630). 플로우들의 교환을 통해 TC를 감소시키기 위해, 가장 낮은 FC를 갖는 플로우가 제1 플로우에 대한 교환의 대상으로서 선택될 수 있다.
(iv) 스케줄링부(130)는 제1 플로우 및 제2 플로우의 교환에 의해 TC가 감소하는지 여부를 검사할 수 있다(S640). 여기서, 제1 플로우 및 제2 플로우의 교환은 제2 모듈에게 제1 플로우를 할당하고, 제1 모듈에게 제2 플로우를 할당하는 것을 의미할 수 있다.
본 발명의 일 실시예에 따르면, 교환 전의 제1 플로우의 FC 및 제2 플로우의 FC의 합을 제1 합이라고 하고, 교환 후의 제1 플로우의 FC 및 제2 플로우의 FC의 합을 제2 합이라고 하면, 제1 합에 비해 제2 합이 더 작으면 교환에 의해 TC가 감소한다고 볼 수 있다. 말하자면, 교환 후에 TC가 증가하지 않도록, 스케줄링부(130)는 교환 후에 제1 플로우의 FC 및 제2 플로우의 FC의 합이 감소하는 경우에 교환을 수행할 수 있다.
본 발명의 일 실시예에 따르면, 플로우의 FC의 값은 "(PPS*CPP)*FC_PRI*PM_FC_PRI[MODULE_ID]"일 수 있다. 따라서, 플로우가 할당된 모듈을 변경하였을 때의 예상되는 FC는, PM_CPP[MODULE]의 값이 결정되어 있을 경우 "(PPS*PM_CPP[MODULE_ID])*FC_PRI*PM_FC_PRI[MODULE_ID]"일 수 있고, PM_CPP[MODULE]의 값이 결정되어 있지 않을 경우 "(PPS*CPP)*FC_PRI*PM_FC_PRI[MODULE_ID]"일 수 있다.
제1 플로우 및 제2 플로우의 교환에 의해 TC가 감소할 경우 단계(S650)가 수행될 수 있고, 제1 플로우 및 제2 플로우의 교환에 의해 TC가 감소하지 않는 경우 단계(S670)가 수행될 수 있다.
(v) 제1 플로우 및 제2 플로우의 교환에 의해 TC가 감소할 경우, 스케줄링부(130)는 제1 플로우 및 제2 플로우의 교환을 수행할 수 있다(S650).
본 발명의 일 실시예에 따르면, 스케줄링부(130)는 복수의 모듈들 중 제1 모듈에 할당된 제1 플로우 및 복수의 모듈들 중 제2 모듈에 할당된 제2 플로우에 대하여 상기 제1 플로우를 처리할 모듈 및 상기 제2 플로우를 처리할 모듈을 서로 간에 교환함으로써 TC를 감소시킬 수 있다.
(vi) 제1 플로우 및 제2 플로우가 교환되면, 스케줄링부(130)는 교환 플로우 엔트리 스케줄링의 결과로서 "성공"을 반환할 수 있다(S660).
(iv) 제1 플로우 및 제2 플로우가 교환되지 않는 경우, 스케줄링부(130)는 교환 플로우 엔트리 스케줄링의 결과로서 "실패"를 반환할 수 있다(S670).
전술된 단계들(S610 내지 670)을 통해, 복수의 모듈들 간의 부하 분배 및 스케줄링을 위해, 스케줄링부(130)는 플로우 처리 부하를 능동적으로 복수의 모듈들 간에서 이동시킬 수 있다. 플로우 처리 부하의 이동에 의해 네트워크 장치(100)의 전체 성능이 향상될 수 있다.
전술된 실시예들에서 설명된 것과 같이, 하드웨어 모듈과 같은 고성능이지만 제한적인 자원을 갖는 모듈에 대한 실측된 성능에 따라서, 스케줄링부(130)는 네트워크 장치(100)가 처리하는 하나 이상의 플로우들을 복수의 모듈들에게 효율적으로 분배할 수 있다. 스케줄링부(130)는 서로 상이한 사양을 갖는 복수의 모듈들에 대해, 모듈의 속성에 맞춰 하나 이상의 플로우들을 균등하게 분배할 수 있다. 또한, 상기의 분배는 실측된 성능에 기반하기 때문에, 스케줄링부(130)는 복수의 모듈들에게 하나 이상의 플로우들을 적응적으로 분배할 수 있다.
이상 설명된 본 발명에 따른 실시예들은 다양한 컴퓨터 구성요소를 통하여 수행될 수 있는 프로그램 명령어의 형태로 구현되어 컴퓨터 판독 가능한 기록 매체에 기록될 수 있다. 상기 컴퓨터 판독 가능한 기록 매체는 프로그램 명령어, 데이터 파일, 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 컴퓨터 판독 가능한 기록 매체에 기록되는 프로그램 명령어는 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 분야의 당업자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능한 기록 매체의 예에는, 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광기록 매체, 플롭티컬 디스크(floptical disk)와 같은 자기-광 매체(magneto-optical media), 및 ROM, RAM, 플래시 메모리 등과 같은 프로그램 명령어를 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령어의 예에는, 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드도 포함된다. 상기 하드웨어 장치는 본 발명에 따른 처리를 수행하기 위해 하나 이상의 소프트웨어 모듈로서 작동하도록 구성될 수 있으며, 그 역도 마찬가지이다.
이상에서 본 발명이 구체적인 구성요소 등과 같은 특정 사항들과 한정된 실시예 및 도면에 의해 설명되었으나, 이는 본 발명의 보다 전반적인 이해를 돕기 위해서 제공된 것일 뿐, 본 발명이 상기 실시예들에 한정되는 것은 아니며, 본 발명이 속하는 기술분야에서 통상적인 지식을 가진 자라면 이러한 기재로부터 다양한 수정 및 변형을 꾀할 수 있다.
따라서, 본 발명의 사상은 상기 설명된 실시예에 국한되어 정해져서는 아니되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등하게 또는 등가적으로 변형된 모든 것들은 본 발명의 사상의 범주에 속한다고 할 것이다.
100: 네트워크 장치
110: 동기화부
120: 정책부
130: 스케줄링부
140: 통계부
150: 배치부

Claims (25)

  1. 네트워크 장치를 이용하여 플로우 처리를 수행하는 방법에 있어서,
    (a) 플로우 처리를 수행하는 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 상기 복수의 모듈들 중 상기 플로우를 처리할 모듈을 결정하는 단계; 및
    (b) 상기 결정된 모듈에게 상기 플로우의 처리를 할당하는 단계를 포함하되,
    상기 (a) 단계에서,
    상기 복수의 모듈들 중 적어도 하나의 모듈은 상기 플로우에 대한 처리 비용을 실측하는 것을 특징으로 하고,
    상기 네트워크 장치는, 상기 실측을 통해 상기 복수의 모듈들 중 자원을 공유하는 2 개 이상의 모듈들의 비용들을 적응적으로 조정하는 것을 특징으로 하는 방법.
  2. 제1항에 있어서,
    (c) 상기 네트워크 장치의 커널 데이터 평면과의 동기화를 수행함으로써 상기 커널 데이터 평면으로부터 상기 플로우에 관련된 정보를 획득하는 단계
    를 더 포함하는 것을 특징으로 하는 방법.
  3. 제1항에 있어서,
    상기 복수의 모듈들은 기능 및 성능 중 적어도 하나에 있어서 서로 상이한 것을 특징으로 하는 방법.
  4. 제1항에 있어서,
    상기 (a) 단계에서,
    상기 네트워크 장치는, 상기 복수의 모듈들 중 상기 플로우의 처리가 가능한 하나 이상의 모듈들을 식별하고, 상기 식별된 하나 이상의 모듈들 중 상기 플로우를 처리할 모듈을 결정하는 것을 특징으로 하는 방법.
  5. 제1항에 있어서,
    상기 (a) 단계에서,
    상기 플로우에 대한 처리 비용은 상기 복수의 모듈들에 대해서 2 개 이상의 상이한 방식으로 결정되는 것을 특징으로 하는 방법.
  6. 삭제
  7. 삭제
  8. 제1항에 있어서,
    상기 (a) 단계에서,
    상기 네트워크 장치는, 상기 플로우를 새로운 플로우로서 추가함에 있어서, 상기 복수의 모듈들에 대하여 상기 플로우에 대한 처리 비용의 우선 순위를 참조로 하여 상기 플로우를 처리할 모듈을 결정하는 것을 특징으로 하는 방법.
  9. 제1항에 있어서,
    상기 네트워크 장치는 하나 이상의 플로우들에 대한 총 비용이 최소값이 되도록 하나 이상의 플로우들의 각 플로우를 처리할 모듈을 상기 복수의 모듈들 중에서 결정하는 것을 특징으로 하는 방법.
  10. 제9항에 있어서,
    상기 총 비용은 상기 복수의 모듈들의 각 모듈에 대한 모듈 비용에 기반하여 결정되고,
    상기 각 모듈의 모듈 비용은 상기 하나 이상의 플로우들 중 상기 각 모듈에게 할당된 플로우들의 각 플로우에 대한 처리 비용에 기반하여 결정되는 것을 특징으로 하는 방법.
  11. 제9항에 있어서,
    상기 (a) 단계에서,
    상기 네트워크 장치는, 상기 복수의 모듈들 중 제1 모듈에 할당된 제1 플로우 및 상기 복수의 모듈들 중 제2 모듈에 할당된 제2 플로우에 대하여 상기 제1 플로우를 처리할 모듈 및 상기 제2 플로우를 처리할 모듈을 서로 간에 교환함으로써 상기 총 비용을 감소시키는 것을 특징으로 하는 방법.
  12. 제11항에 있어서,
    상기 (a) 단계에서,
    상기 네트워크 장치는 상기 하나 이상의 플로우들 중 플로우에 대한 처리 비용의 내림차순으로 상기 제1 플로우를 선택하는 것을 특징으로 하는 방법.
  13. 제1항 내지 제5항 및 제8항 내지 12항 중 어느 한 항에 따른 방법을 실행하기 위한 컴퓨터 프로그램을 기록한 컴퓨터 판독 가능한 기록 매체.
  14. 플로우 처리를 수행하는 네트워크 장치에 있어서,
    플로우 처리를 수행하는 복수의 모듈들; 및
    상기 복수의 모듈들의 각 모듈의 플로우에 대한 처리 비용에 기반하여 상기 복수의 모듈들 중 상기 플로우를 처리할 모듈을 결정하고, 상기 결정된 모듈에게 상기 플로우의 처리를 할당하는 스케줄링부를 포함하되,
    상기 복수의 모듈들 중 적어도 하나의 모듈은 상기 플로우에 대한 비용을 실측하고,
    상기 스케줄링부는 상기 실측을 통해 상기 복수의 모듈들 중 자원을 공유하는 2 개 이상의 모듈들의 비용들을 적응적으로 조정하는 것을 특징으로 하는 장치.
  15. 제14항에 있어서,
    상기 장치의 커널 데이터 평면과의 동기화를 수행함으로써 상기 플로우에 관련된 정보를 획득하는 동기화부
    를 더 포함하는 장치.
  16. 제14항에 있어서,
    상기 복수의 모듈들은 기능 및 성능 중 적어도 하나에 있어서 서로 상이한 것을 특징으로 하는 장치.
  17. 제14항에 있어서,
    상기 스케줄링부는 상기 복수의 모듈들 중 상기 플로우의 처리가 가능한 하나 이상의 모듈들을 식별하고, 상기 식별된 하나 이상의 모듈들 중 상기 플로우를 처리할 모듈을 결정하는 것을 특징으로 하는 장치.
  18. 제14항에 있어서,
    상기 플로우에 대한 처리 비용은 상기 복수의 모듈들에 대해서 2개 이상의 상이한 방식으로 결정되는 것을 특징으로 하는 장치.
  19. 삭제
  20. 삭제
  21. 제14항에 있어서,
    상기 스케줄링부는 상기 플로우를 새로운 플로우로서 추가함에 있어서, 상기 복수의 모듈들에 대하여 상기 플로우에 대한 처리 비용의 우선 순위를 참조로 하여 상기 플로우를 처리할 모듈을 결정하는 것을 특징으로 하는 장치.
  22. 제14항에 있어서,
    상기 스케줄링부는 하나 이상의 플로우들에 대한 총 비용이 최소값이 되도록 하나 이상의 플로우들의 각 플로우를 처리할 모듈을 상기 복수의 모듈들 중에서 결정하는 것을 특징으로 하는 장치.
  23. 제22항에 있어서,
    상기 총 비용은 상기 복수의 모듈들의 각 모듈에 대한 모듈 비용에 기반하여 결정되고,
    상기 각 모듈의 모듈 비용은 상기 하나 이상의 플로우들 중 상기 각 모듈에게 할당된 플로우들의 각 플로우에 대한 처리 비용에 기반하여 결정되는 것을 특징으로 하는 장치.
  24. 제22항에 있어서,
    상기 스케줄링부는 상기 복수의 모듈들 중 제1 모듈에 할당된 제1 플로우 및 상기 복수의 모듈들 중 제2 모듈에 할당된 제2 플로우에 대하여 상기 제1 플로우를 처리할 모듈 및 상기 제2 플로우를 처리할 모듈을 서로 간에 교환함으로써 상기 총 비용을 감소시키는 것을 특징으로 하는 장치.
  25. 제24항에 있어서,
    상기 스케줄링부는 상기 하나 이상의 플로우들 중 플로우에 대한 처리 비용의 내림차순으로 상기 제1 플로우를 선택하는 것을 특징으로 하는 장치.
KR1020140097511A 2014-07-30 2014-07-30 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체 Active KR101481757B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020140097511A KR101481757B1 (ko) 2014-07-30 2014-07-30 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020140097511A KR101481757B1 (ko) 2014-07-30 2014-07-30 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체

Publications (1)

Publication Number Publication Date
KR101481757B1 true KR101481757B1 (ko) 2015-01-21

Family

ID=52590477

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020140097511A Active KR101481757B1 (ko) 2014-07-30 2014-07-30 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체

Country Status (1)

Country Link
KR (1) KR101481757B1 (ko)

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20080009131A (ko) * 2005-04-21 2008-01-24 노키아 코포레이션 다중모드 단말기의 정책 기반 통신 인터페이스의 선택
KR20110103889A (ko) * 2010-03-15 2011-09-21 한국전자통신연구원 네트워크 장비의 가상화 장치 및 방법
KR20120001585A (ko) * 2010-06-28 2012-01-04 한국전자통신연구원 플로우 이동성 제공 방법

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20080009131A (ko) * 2005-04-21 2008-01-24 노키아 코포레이션 다중모드 단말기의 정책 기반 통신 인터페이스의 선택
KR20110103889A (ko) * 2010-03-15 2011-09-21 한국전자통신연구원 네트워크 장비의 가상화 장치 및 방법
KR20120001585A (ko) * 2010-06-28 2012-01-04 한국전자통신연구원 플로우 이동성 제공 방법

Similar Documents

Publication Publication Date Title
JP5954074B2 (ja) 情報処理方法、情報処理装置、及びプログラム。
Webb et al. Blender: Upgrading tenant-based data center networking
CN111857946B (zh) 基于位置的虚拟化工作负载放置
CA2829001C (en) Technique for resource creation in a cloud computing system
JP5851618B2 (ja) 複数の企業データセンタおよびクラウドにおける複数の仮想マシンマイグレーションのネットワーク対応調整
US8386825B2 (en) Method and system for power management in a virtual machine environment without disrupting network connectivity
US20140064066A1 (en) Data Processing
CN112052068A (zh) 一种Kubernetes容器平台CPU绑核的方法与装置
US11126461B2 (en) Techniques for container scheduling in a virtual environment
CN106681839B (zh) 弹性计算动态分配方法
WO2013104375A1 (en) Network device control in a software defined network
CN113672391B (zh) 一种基于Kubernetes的并行计算任务调度方法与系统
WO2019006907A1 (en) SYSTEMS AND METHODS FOR ASSIGNING COMPUTER RESOURCES IN A DISTRIBUTED COMPUTER SYSTEM
US9836322B1 (en) Methods and apparatus for virtualizing switch control plane engine
CN110838939B (zh) 一种基于轻量级容器的调度方法及边缘物联管理平台
CN107222327A (zh) 一种基于云平台管理服务器的方法及装置
US20200186475A1 (en) Network resource management for hyper-converged infrastructures
KR102860210B1 (ko) 기계학습 추론 작업을 위한 다중 gpu 환경 기반 시공간분할 스케줄링 sw
CN110086726A (zh) 一种自动切换Kubernetes主节点的方法
CN105553882A (zh) 用于sdn数据平面资源调度的方法
WO2016197301A1 (zh) Nfv系统中的策略协调方法和装置
US11838389B2 (en) Service deployment method and scheduling apparatus
KR101481757B1 (ko) 동적 플로우 분배를 이용하여 플로우를 처리하기 위한 방법, 장치 및 컴퓨터 판독 가능한 기록 매체
CN112527450B (zh) 基于不同资源的超融合自适应方法、终端及系统
He et al. Firebird: Network-aware task scheduling for spark using sdns

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20140730

PA0201 Request for examination
PA0302 Request for accelerated examination

Patent event date: 20140812

Patent event code: PA03022R01D

Comment text: Request for Accelerated Examination

Patent event date: 20140730

Patent event code: PA03021R01I

Comment text: Patent Application

PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20140926

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: 20150102

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20150106

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20150106

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20180105

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20180105

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20190103

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20190103

Start annual number: 5

End annual number: 5

FPAY Annual fee payment

Payment date: 20200103

Year of fee payment: 6

PR1001 Payment of annual fee

Payment date: 20200103

Start annual number: 6

End annual number: 6

PR1001 Payment of annual fee

Payment date: 20210104

Start annual number: 7

End annual number: 7

PR1001 Payment of annual fee

Payment date: 20220105

Start annual number: 8

End annual number: 8

PR1001 Payment of annual fee

Payment date: 20240103

Start annual number: 10

End annual number: 10

PR1001 Payment of annual fee

Payment date: 20250106

Start annual number: 11

End annual number: 11