[논문]효율적인 서비스 기능 체이닝을 위한 최적의 플로우 분배 알고리즘

김명수; 이기원; 주석진; 백상헌; 김영화

doi:10.7840/kics.2015.40.6.1032

[국내논문] 효율적인 서비스 기능 체이닝을 위한 최적의 플로우 분배 알고리즘
Optimal Flow Distribution Algorithm for Efficient Service Function Chaining 원문보기

한국통신학회논문지 = The Journal of Korean Institute of Communications and Information Sciences, v.40 no.6, 2015년, pp.1032 - 1039

김명수 (Department of Electrical Engineering, Korea University) , 이기원 (Department of Electrical Engineering, Korea University) , 주석진 (Department of Electrical Engineering, Korea University) , 백상헌 (Department of Electrical Engineering, Korea University) , 김영화 (Electronics and Telecommunications Research Institute (ETRI))

초록
AI-Helper

서비스 기능 체이닝(SFC: Service function chaining)은 다수의 서비스 기능들을 순차적으로 구성하는 기술이다. 서비스 기능 체이닝에서는 확장성과 fault-tolerant를 위해 다수의 서비스 기능 인스턴스가 필요하며, 네트워크에 인입된 플로우는 다수의 서비스 기능 인스턴스로 적절하게 분배되어야 한다. 따라서 본 논문에서는 각 서비스 기능인스턴스들의 자원을 고려하면서 종단 간 지연시간(latency)을 최소화 할 수 있는 플로우 분배 문제를 정의한다. 또한 GT-ITM 토폴로지 생성 툴을 사용하여 보다 현실적인 네트워크 토폴로지 상에서 시뮬레이션을 수행하고, 그 결과 최적의 플로우 분배 기법이 전체 지연시간을 줄일 수 있음을 확인하였다.

Abstract ▼ AI-Helper

Service function chaining(SFC) defines the creation of network services that consist of an ordered set of service function. A multiple service function instances should be deployed across networks for scalable and fault-tolerant SFC services. Therefore, an incoming flows should be distributed to multiple service function instances appropriately. In this paper, we formulate the flow distribution problem in SFC aiming at minimizing the end-to-end flow latency under resource constraints. Then, we evaluate its optimal solution in a realistic network topology generated by the GT-ITM topology generator. Simulation results reveal that the optimal solution can reduce the total flow latency significantly.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 네트워크에 플로우가 인입되면 해당 플로우를 다수의 서비스 기능 인스턴스들에게 적절하게 분배시키는 플로우 최적화에 초점을 맞춘다. 서비스 기능 체이닝에서 플로우를 분배하는 기존의 연구에는 균등 플로우 분배 기법과 네트워크 인지 플로우 분배 기법 2가지가 있다^[12].

가설 설정

본 논문에서는 최적의 플로우 분배 기법(Optimal 기법), 균등 플로우 분배 기법(Uniform 기법), 네트워크 인지 플로우 분배 기법(Aware 기법)의 전체 지연 시간을 비교한다. Aware 기법에서는 서비스 기능 인스턴스가 동일한 transit domain 혹은 stub domain에 존재하는 경우 링크의 지연시간을 0으로 설정하고, 다른 domain에 존재하는 경우 링크의 지연시간을 1로설정하였다. 전체 플로우 N의 개수는 720개로 가정하였다.
먼저 서비스 기능 체인이 IPS-RE의 순서로 구성되어 있고, 각서비스 기능 IPS와 RE에는 3개와 4개의 서비스 기능 인스턴스가 존재한다고 가정한다. 또한 IPS1, IPS2, RE1, RE2 서비스 기능 인스턴스는 랙 A에 배치되어 있고, 나머지 IPS3, RE3, RE4 서비스 기능 인스턴스는 랙 B에 배치되어 있다고 가정한다. 먼저 균등 분배 기법에서는 만약 네트워크에 N개의 플로우가 인입되면 균등 플로우 분배 기법에서는 각 IPS 서비스 기능 인스턴스가 균등하게 N/3개의 플로우를 전달받고 처리하며, 처리를 마친 플로우는 N/12개만큼 균등하게 다음 RE 서비스 기능 인스턴스에게 분배된다.
transit-stub 네트워크 모델에서는 1개의 transit domain과 4개의 stub domain이 존재한다. 또한 transit-stub 네트워크 모델에서 transit domain은 stub domain들과 서로 연결되어 있는 구조이며, 각 domain에는 4개의 노드가 존재한다고 가정하였다. 서비스 기능 체이닝의 경우 3 개의 서비스 기능(즉, s = 3)이 있으며, 각 서비스 기능 인스턴스도 3개(즉, k_r = 3)가 존재한다고 가정하였다.
본 논문에서는 서비스 기능 체이닝에서 각 서비스 기능 인스턴스들의 자원을 고려하면서 종단 간 지연 시간을 최소화할 수 있는 플로우 분배 문제를 ILP(integer linear programming)로 정의한다. 또한 기존의 네트워크 인지 플로우 분배 기법과 다르게 본논문에서는 운영자의 네트워크에 초점을 맞추어 다수의 데이터 센터를 가정한다. 더불어 제안한 최적의 플로우 분배 기법의 성능 평가를 위해 GT-ITM^[13]토폴로지 생성 툴을 사용하여 보다 현실적인 네트워크 토폴로지 상에서 시뮬레이션을 수행하고, 그 결과 제안하는 최적의 플로우 분배 기법이 기존 기법들에 비해 전체 지연시간을 감소시킨 것을 확인하였다.
그림 2와 그림 3은 균등 플로우 분배 기법과 네트워크 인지 플로우 분배 기법의 비교를 보여준다. 먼저 서비스 기능 체인이 IPS-RE의 순서로 구성되어 있고, 각서비스 기능 IPS와 RE에는 3개와 4개의 서비스 기능 인스턴스가 존재한다고 가정한다. 또한 IPS1, IPS2, RE1, RE2 서비스 기능 인스턴스는 랙 A에 배치되어 있고, 나머지 IPS3, RE3, RE4 서비스 기능 인스턴스는 랙 B에 배치되어 있다고 가정한다.
또한 transit-stub 네트워크 모델에서 transit domain은 stub domain들과 서로 연결되어 있는 구조이며, 각 domain에는 4개의 노드가 존재한다고 가정하였다. 서비스 기능 체이닝의 경우 3 개의 서비스 기능(즉, s = 3)이 있으며, 각 서비스 기능 인스턴스도 3개(즉, k_r = 3)가 존재한다고 가정하였다. 또한 서비스 기능 인스턴스, 출발지 노드, 목적지 노드의 경우 초기에 transit domain과 stub domain에 랜덤으로 배치되며, 모든 인스턴스 혹은 노드들 간링크의 지연시간을 구하기 위해 Euclidean distance를 사용하였다^[20].
먼저 플로우 분배를 위한 시스템 모델은 그림 4와 같다. 시스템 모델에서는 서비스 기능 체이닝을 위한 서비스 기능 s가 존재한다고 가정하며, 서비스 기능 인덱스의 집합을 S= {1,2, ⋯, s}로 정의한다. 또한 r번째 서비스 기능 (r ∈ S)은 k_r개의 인스턴스를 갖으며, f_r,1,f_r,2, ⋯, f_r,k과 같이 정의한다.
Aware 기법에서는 서비스 기능 인스턴스가 동일한 transit domain 혹은 stub domain에 존재하는 경우 링크의 지연시간을 0으로 설정하고, 다른 domain에 존재하는 경우 링크의 지연시간을 1로설정하였다. 전체 플로우 N의 개수는 720개로 가정하였다.
반면 그림 3의 네트워크 인지 플로우 분배 기법에서는 랙 간에 이동하는 플로우의 양을 최소화시킬 수 있도록 플로우를 분배한다. 즉, 동일한 랙에 배치된 서비스 기능 인스턴스간 플로우를 분배시키는 경우 발생하는 비용을 0으로 가정하고, 다른 랙에 배치된 서비스 기능 인스턴스간 플로우를 분배시키는 경우 발생하는 비용을 1로 가정한다. 이와 같이 플로우 분배 시 발생하는 비용을 고려하여 종단 간 지연시간을 최소화하는 문제를 LP(linear programming)로 정의하였다.

제안 방법

기존의 균등 플로우 분배 기법의 한계점을 해결하기 위해 서비스 기능 인스턴스간 링크의 지연시간을 고려하는 네트워크 인지 플로우 분배 기법(network-aware flow distribution)이 제안되었다. 그림 2와 그림 3은 균등 플로우 분배 기법과 네트워크 인지 플로우 분배 기법의 비교를 보여준다.
본 논문에서는 최적의 플로우 분배 기법(Optimal 기법), 균등 플로우 분배 기법(Uniform 기법), 네트워크 인지 플로우 분배 기법(Aware 기법)의 전체 지연 시간을 비교한다. Aware 기법에서는 서비스 기능 인스턴스가 동일한 transit domain 혹은 stub domain에 존재하는 경우 링크의 지연시간을 0으로 설정하고, 다른 domain에 존재하는 경우 링크의 지연시간을 1로설정하였다.

데이터처리

또한 아마존 EC2와 같은 환경에서 시뮬레이션을 수행한 연구^[18]도 있지만 가상의 서비스 기능 인스턴스를 배치하고 임의로 플로우를 분배시키는 실험을 수행하기에는 어려움이 존재한다. 따라서 본 장에서는 GT-ITM 토폴로지 생성 툴과 Matlab을 사용하여 최적의 플로우 분배 문제를 시뮬레이션 한 결과를 살펴본다. 최적의 플로우 분배 문제를 시뮬레이션 하기 위해 GT-ITM 토폴로지 생성 툴을 사용하여 실제 네트워크 환경의 토폴로지를 생성하였다.
따라서 본 장에서는 GT-ITM 토폴로지 생성 툴과 Matlab을 사용하여 최적의 플로우 분배 문제를 시뮬레이션 한 결과를 살펴본다. 최적의 플로우 분배 문제를 시뮬레이션 하기 위해 GT-ITM 토폴로지 생성 툴을 사용하여 실제 네트워크 환경의 토폴로지를 생성하였다. 그림 5는 GT-ITM 토폴로지 생성 툴을 사용하여 생성한 transit-stub^[19] 네트워크 모델을 나타낸다.

이론/모형

서비스 기능 체이닝의 경우 3 개의 서비스 기능(즉, s = 3)이 있으며, 각 서비스 기능 인스턴스도 3개(즉, k_r = 3)가 존재한다고 가정하였다. 또한 서비스 기능 인스턴스, 출발지 노드, 목적지 노드의 경우 초기에 transit domain과 stub domain에 랜덤으로 배치되며, 모든 인스턴스 혹은 노드들 간링크의 지연시간을 구하기 위해 Euclidean distance를 사용하였다^[20].

성능/효과

또한 기존의 네트워크 인지 플로우 분배 기법과 다르게 본논문에서는 운영자의 네트워크에 초점을 맞추어 다수의 데이터 센터를 가정한다. 더불어 제안한 최적의 플로우 분배 기법의 성능 평가를 위해 GT-ITM^[13]토폴로지 생성 툴을 사용하여 보다 현실적인 네트워크 토폴로지 상에서 시뮬레이션을 수행하고, 그 결과 제안하는 최적의 플로우 분배 기법이 기존 기법들에 비해 전체 지연시간을 감소시킨 것을 확인하였다.
45% 감소한다. 따라서 Optimal 기법은 큰 스케일을 갖는 서비스 기능 체이닝 환경에서 더욱 효과적으로 플로우 분배가 가능함을 확인하였다.
본 논문에서는 서비스 기능 체이닝에서 서비스 기능 인스턴스들의 자원을 고려함과 동시에 종단 간 지연시간을 최소화할 수 있는 최적의 플로우 분배 문제를 ILP(integer linear programming)로 정의하였으며, 시뮬레이션 결과를 통해 최적의 플로우 분배 기법이 다른 기존의 기법에 비해 전체 지연시간이 감소했음을 확인할 수 있다. 또한 서비스 기능의 자원이 증가하고 서비스 기능 인스턴스의 개수가 많아지는 경우 제안하는 기법이 기존 기법에 비해 더욱 효율적인 것을 확인할 수 있다. 향후 연구에는 가상화된 서비스 기능과 물리적인 서비스 기능이 존재하는 경우에서 플로우 분배 문제에 대해서 연구할 예정이다.
본 논문에서는 서비스 기능 체이닝에서 서비스 기능 인스턴스들의 자원을 고려함과 동시에 종단 간 지연시간을 최소화할 수 있는 최적의 플로우 분배 문제를 ILP(integer linear programming)로 정의하였으며, 시뮬레이션 결과를 통해 최적의 플로우 분배 기법이 다른 기존의 기법에 비해 전체 지연시간이 감소했음을 확인할 수 있다. 또한 서비스 기능의 자원이 증가하고 서비스 기능 인스턴스의 개수가 많아지는 경우 제안하는 기법이 기존 기법에 비해 더욱 효율적인 것을 확인할 수 있다.

후속연구

또한 서비스 기능의 자원이 증가하고 서비스 기능 인스턴스의 개수가 많아지는 경우 제안하는 기법이 기존 기법에 비해 더욱 효율적인 것을 확인할 수 있다. 향후 연구에는 가상화된 서비스 기능과 물리적인 서비스 기능이 존재하는 경우에서 플로우 분배 문제에 대해서 연구할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	서비스 기능 체이닝은 무엇인가?	서비스 기능 체이닝(SFC: Service function chaining)은 다수의 서비스 기능들을 순차적으로 구성하는 기술이다. 서비스 기능 체이닝에서는 확장성과 fault-tolerant를 위해 다수의 서비스 기능 인스턴스가 필요하며, 네트워크에 인입된 플로우는 다수의 서비스 기능 인스턴스로 적절하게 분배되어야 한다.
	높은 CAPEX 및 OPEX를 해결하기 위해 어떤 기술이 등장했는가?	따라서 네트워크 운영자는 네트워크에 필수적인 기능들을 관리하기 위해 높은 CAPEX 및 OPEX가 든다. 이를 해결하기 위해 네트워크의 기능을 소프트웨어적으로 가상화 하여 다수의 서비스 기능들로 구성하는 네트워크 기능 가상화(NFV: Network function virtualization) 기술이 등장하였으며, 서비스 기능들을 순차적으로 처리하는 기술인 서비스 기능 체이닝 기술이 각광받고 있다[2-3]. 또한 서비스 기능 체이닝을 지원하는 기술로서 소프트웨어 정의 네트워킹(SDN: Software defined networking) 기술이 소개되었다[4-7].
	서비스 기능 체이닝은 어떤 이슈가 있는가?	서비스 기능 체이닝에서는 확장성과 fault-tolerant를 위해 동일한 기능을 수행하는 다수의 서비스 기능 인스턴스들을 생성하고 배치시키는데 많은 이슈가 있다. 이와 관련하여 IETF 인터넷 표준화 문서 중 자원 관리(resource management)[11] 문서 에서는 서비스 기능 인스턴스의 fault, 경로 최적화, 플로우 최적화, 부하 분산 등의 유즈케이스를 다루고 있다.

참고문헌 (20)

G. Lee, M. Kim, S. Choo, S. Pack, and Y. Kim, "Optimal flow distribution in service function chaining," in Proc. Int. Conf. Future Internet Technologies (CFI), Jun. 2015.
P. Quinn and J. Guichard, "Service function chaining: Creating a service plane via network service headers," J. Computer, vol. 47, no. 11, pp. 38-44, Nov. 2014.
W. John, K. Pentikousis, G. Agapiou, E. Jacob, M. Kind, A. Manzalini, F. Risso, D. Staessens, R. Steinert, and C. Meirosu, "Research directions in network service chaining," in Proc. IEEE SDN4FNS, pp. 1-7, Trento, Nov. 2013.
S. Mehraghdam, M. Keller, and H. Karl, "Specifying and placing chains of virtual network functions," in Proc. IEEE CloudNet, pp. 7-13, Luxembourg, Oct. 2014.
G. Lee, I. Jang, W. Kim, S. Joo, M. Kim, S. Pack, and C. Kang, "SDN-based middlebox management framework in integrated wired and wireless networks," J. KICS, vol. 39B, no. 6, pp. 379-386, Jun. 2014.

원문보기 상세보기
J. Jo, S. Lee, J. Kong, and J. Kim, "A centralized network policy controller for SDN-based service overlay networking," J. KICS, vol. 38B, no. 4, pp. 266-278, Apr. 2013.

원문보기 상세보기
H. Kim and H. Kim, "Control algorithm for virtual machine-level fairness in virtualized cloud data center," J. KICS, vol. 38C, no. 6, pp. 512-520, Jun. 2013.

원문보기 상세보기
IETF Service Function Chaining (SFC) Working Group (WG), Retrieved May 1, 2015, from https://datatracker.ietf.org/wg/sfc/charter/
J. Guichard and C. Pignataro, "Service function chaining (SFC) architecture," Internet-Draft draft-sfc-architecture-05, Feb. 2015.
W. Liu, H. Li, O. Huang, M. Boucadair, N. Leymann, Z. Cao, Q. Sun, and C. Pham, Service function chaining (SFC) general use cases, Internet-Draft draft-liu-sfc-use-cases-08, Sept. 2014.
S. Lee, S. Pack, M. Shin, and E. Paik, Resource management for dynamic service chain adaptation, internet-draft draft-lee-nfvrgresource- management-service-chain-00, Oct. 2014.
A. Gember, A. Krishnamurthy, S. S. John, R. Grandl, X. Gao, A. Anand, T. Benson, A. Akella, and V. Sekar, Stratos: A networkaware orchestration layer for middleboxes in the cloud, arXiv preprint arXiv:1305.0209, 2013.
K. Calvert and E. Zegura, GT internetwork topology models (GT-ITM), Retrieved May 1, 2015, from http://www.cc.gatech.edu/fac/Ellen.Zegura/gt-itm.
G. Wang and T. S. E. Ng, "The impact of virtualization on network performance of amazone EC2 data center," in Proc. IEEE INFOCOM 2010, pp. 1-9, San Diego, CA, Mar. 2010.
M. Xia, M. Shirazipour, Y. Zhang, H. Green, and A. Takacs, "Optical service chaining for network function virtualization," IEEE Commun. Mag., vol. 53, no. 4, pp. 152-158, Apr. 2015.

상세보기
S. Mehraghdam, M. Keller, and H. karl, "Specifying and placing chains of virtual network functions," in Proc. IEEE Cloud Netw. (CloudNet), pp. 7-13, Luxembourg, Jun. 2014.
M. Bagaa, T. Taleb, and A. Ksentini, "Service-aware network function placement for efficient traffic handling in carrier cloud," in Proc. IEEE Wirel. Commun. Netw. Conf. (WCNC) 2014, pp. 2402-2407, Istanbul, Apr. 2014.
C. Pham, H. D. Tran, S. I. Moon, K. Thar, and C. S. Hong, "A general and practical consolidation framework in CloudNFV," in Proc. IEEE Int. Conf. Inf. Netw. (ICOIN) 2015, pp. 295-300, Cambodia, Jan. 2015.
O. Heckmann, M. Piringer, J. Schmitt, and R. Steinmetz, "On realistic network topologies for simulation," in Proc. ACM SIGCOMM MoMeTools Workshop, pp. 28-32, Aug. 2003.
B. Zhang, T. S. E. Ng, A. Nandi, R. Riedi, P. Druschel, and G. Wang, "Measurement-based analysis, modeling, and synthesis of the internet delay space," IEEE/ACM Trans. Netw., vol. 18, no. 1, pp. 229-242, Feb. 2010.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증