Dynamic Graph Query Primitives for SDN-based Cloud Network Management Ramya Raghavendra, Jorge Lobo, Kang-Won Lee 2012 HotSDN 2016. 05. 25 정보통신공학과 1532061003 조경우

Contents Introduction NetGraph Software Architecture Design and implementation of shortest path algorithm Evaluation Conclusion

XaaS (Everything as a Service) 1. Introduction XaaS (Everything as a Service) 제공 방식에 따른 모델에 의한 분류 IaaS(Infrastructure as a Service) 서버, 스토리지, 방화벽 등의 설치형 어플리케이션 구축에 필요한 기반 환경 제공 PaaS(Platform as a Service) 서비스 또는 어플리케이션이 실행되는 환경(runtime 환경) 을 서비스 형태로 제공 OS, D/B 등의 소프트웨어 배포 단계까지의 모든 설정이 완료된 상태 SaaS(Software as a Service) 팩키지 된 소프트웨어 어플리케이션 소프트웨어를 서비스 형태로 제공 SaaS Hosted Applications Suites of Services Development Tools And Database Management Operating Systems Virtualization Servers and Storage Data Center Physical Plant/Building Networking Firewalls/Security PaaS IaaS NaaS

1. Introduction Cloud-Naas 네트워크 인프라 관리와 서비스 관리를 분리 클라우드 관리자의 부담 완화 네트워크 제어 용이 Network Controller function Network-aware VM placement QoS support Realtime network monitoring Flexible diagnostics Management and security function

NetGraph graph algorithm library 1. Introduction NetGraph graph algorithm library Cloud network topology 다양한 logical, physical 활동에 따라 유동적(dynamic) Addition of new racks VM addition, deletion, migration NetGraph library Graph computation algorithm 지원 Cloud controller, network management protocol 간의 interface 지원 Shortest path primitive practical computation time과 memory requirements의 Incremental algorithms 지원 Internet node edge

2. NetGraph Software Architecture Design of NetGraph Network Controller 내에 NetGraph module 추가 Provides a set of graph query APIs to be invoked by the service modules Obtain the physical and virtual topology from the underlying network Updates the network graphs Provides graph query support to the invoking service module [SNMP : Simple Network Management Protocol ]

2. NetGraph Software Architecture Design of NetGraph NetGraph Network service Broadcast : Control broadcast domains for virtual interface, can be useful for failover service. Support from minimum spanning tree algorithms. Routing and path computation : Support from shortest path and transitive closure algorithms. Monitoring : Support from simple queries such as vertex indegree, outdegree to advanced shortest path, transitive closure, etc. QoS : Features for virtual network path, for example bandwidth, delay control, traffic priority support. Support from k-shortest path algorithms, etc. Isolation : Security functions requiring support from bipartite graph matching algorithms.

2. NetGraph Software Architecture Interface Design Important aspects of NetGraph’s API Maintain Network Graph physical, logical Network topology 조회 및 graph algorithm을 실행할 수 있는 graph 표현으로의 변환 다른 software module과의 interface인 Graph class 구현 Graph class : setEdgeWeight, getEdgeWeight query를 통해 graph 목록 유지, 설정된 시간 간격으로 graph 갱신(잦은 재연산 방지) Vertices, node1 node2 Node Ip1 port1 Ip2 port2 Ip3 port3 link edge, weight(30), delay, etc. edge SDN-enabled Network Controller Service module NetGraph Topology 조회 Topology 반환 (node1, node2, edgeweight, …) ex. (node1, node2, 30) Topology (using SNMP, etc.)

2. NetGraph Software Architecture Interface Design Important aspects of NetGraph’s API Compute Graph Query NetGraph에 의해 지원되는 graph primitive가 다양한 service module에 호출될 수 있도록 API 제공 countInDegree, countOutDegree, countNeighbor와 같은 edge 연산, ComputeMST(), ComputeSSSP(), ComputeAPSP(), DoesRouteExist(), IsSubPath(Path1, Path2) 등의 함수 제공 ComputeMST(Source) : 소스로부터 Minimum Spanning Tree 연산 ComputeSSSP(Source) : 소스로부터 Single Source Shortest Path 연산. ComputekSSSP(Source, Destination, k)를 이용하여 Source와 Destination간 k-Shortest path 연산 가능 ComputeAPAS() : route의 배치가 유지, 반환되는 graph vertices에서 All Paire Shortest Path(전쌍 최단 경로) 연산 DoesRouteExist(Source, Destination) : Source와 Destination의 연결상태를 true, false로 반환 IsSubPath(Path1, Path2) : Path2가 Path1의 subpath인 경우 연산

3. Design and implementation of shortest path algorithm Background on shortest path algorithms Shortest path algorithm 최단 경로를 필요로 하는 Network module → 최단 경로를 사전 계산(using dijkstra’s algorithm, etc.) 이 경우, Network Graph가 크거나 topology의 변화 등과 같은 동적(dynamic) 환경에 대처하기 어려움 동적(dynamic) 환경에 대처하기 위한 최단 경로 알고리즘들은 더 큰 규모의 graph의 sub graph를 생성, network topology update에 따른 sub graph, graph 상의 최단 경로들을 update 그러나 network topology가 매우 큰 경우, 큰 storage 용량을 필요로 하며, network 확장 역시 어려움 또한, 중앙 집중식 구조에서는, network 크기 증가에 따라 확장할 수 있는 알고리즘을 설계하는 것이 중요 → 경로 변화를 요청하는 monitoring, management module을 고려하여 CPU 사용량과 memory 크기를 고려한 알 고리즘 고려

3. Design and implementation of shortest path algorithm Background on shortest path algorithms TEDI(TreE Decomposition based Indexing) Tree decomposition을 기반으로 하여 indexing 방식으로 최단 경로 탐색 Tree의 모든 bag(node의 집합) 내의 vertices 간 로컬 최단 경로를 기존 알고리즘들을 통해 저장 Graph의 크기가 아닌 height, tree의 bag cardinality(bag 내의 node의 수)에 의해 최단 경로 연산 시간 결정 해당 알고리즘은 큰 graph, topology의 잦은 변경, 중앙 집중식 네트워크 컨트롤러 상의 확장 graph 알고리즘이 필요 한 SDN-based cloud network에 적합할 것 그러나, TEDI는 web graph를 위해 제안되어, 가중, 동적 그래프에서도 동작하도록 알고리즘 변형 필요 2 4 5 1 3 [treewidth(G)가 3인 TEDI의 tree decomposition]

3. Design and implementation of shortest path algorithm Design of dynamic-TEDI(D-TEDI) D-TEDI Tree decomposition에 edge weight update를 처리하는 동적 APSP알고리즘인 D-TEDI에 관한 선행연구를 수행하 였으나, edge insert, delete는 처리하지 못함 Edge의 update, insert, delete는 Virtual Machine의 추가, 삭제, migration과 같은 cloud management를 위한 필수 요건 새로운 workload들의 추가 → edge, vertices의 insert 필요 Workload의 완료, migration → edge, vertices의 delete 필요 기존 연구를 확장하여, edge의 insert, delete가 가능한 D-TEDI 설계 [APSP : All Pairs Shortest Path;전쌍 최단 경로 ]

3. Design and implementation of shortest path algorithm Design of dynamic-TEDI(D-TEDI) Delete 각 vertex에서, vertex로부터 발생하는 edge의 count 유지 삭제된 edge를 포함하는 tree_node 유지 tree_node에서 연결된 edge가 없는 경우, 해당 bag 삭제 Edge (b, d)를 포함하는 tree_node의 neighbor count Count 결과가 1보다 작다면 해당 bag 삭제 3 4 5 𝑡𝑟𝑒e_node(0)=3

3. Design and implementation of shortest path algorithm Design of dynamic-TEDI(D-TEDI) Insert BFS(Breadth Frist Search) algorithm을 통해 edge b 가 처음 발생되는 𝑡𝑟𝑒𝑒𝑛𝑜𝑑𝑒_𝑏 탐색 𝑡𝑟𝑒𝑒𝑛𝑜𝑑𝑒_𝑏 가 있는 경우 Root (R)로부터 edge d의 첫번째 발생 탐색 𝑡𝑟𝑒𝑒𝑛𝑜𝑑𝑒_𝑏와 𝑡𝑟𝑒𝑒𝑛𝑜𝑑𝑒_𝑑에서 최단 경로 SP 탐색. 만일 (R)의 경로가 d를 포함하지 않는 b에 있다면 두 노드의 최 단 경로는 두 경로를 연결한 것 (R)의 경로에서 d가 b를 포함하는 경우 최단 경로는 𝑡𝑟𝑒𝑒𝑛𝑜𝑑𝑒_𝑑 → b를 포함한 첫번째 조상(ancestor)에 의해 주어짐

4. Evaluation Evaluation setup Algorithm Graph (1) S-DIJ, (2) D-PUP, (3) D-TEDI algorithm을 통한 평가 수행 각 algorithm 상에서 (a) 초기화 및 update 시간, (b) 메모리, (c) query 시간 비교 Graph Internet graphs : 오리건 대학 Route View Architecture Project 4 상의 AS(Autonomous System)사이의 연결 고 려 AS_500~AS_3000은 500~3000개의 노드들과 2,406~13,734개의 edge를 가지며, edge weigh는 최대 20,000 P2P network : Stanford Large Network Dataset Collection의 2002년 8월 중 Gnutella P2P 네트워크의 연결 고 려 그래프는 8,111~22,686개의 노드들과 20,781~65,373개의 edge들로 달라짐 Data center network topology : 일반적인 3-tier 데이터 센터 architecture에 기초하여 16대의 서버의 경우를 사용 하여 표현 1,024개의 노드들과 16, 48 port의 스위치들로 이루어진 환경

4. Evaluation Evaluation setup Graph Data center network topology : 일반적인 3-tier 데이터 센터 architecture에 기초하여 16대의 서버의 경우를 사용 하여 표현 1,024개의 노드들과 16, 48 port의 스위치들로 이루어진 환경

4. Evaluation Evaluation result

5. Conclusion Cloud-NaaS상의 다수의 module을 지원하려면 network의 physical, logical topology의 동적 특성을 고려 한 빠른 graph query 지원이 중요 이를 위해 NetGraph는 topology의 update를 받을 수 있는 API와 같은 software module을 구현, query를 동적으로 재계산하고 호출된 module에 계산 결과 제공 TEDI를 동적(dynamic) 환경에 맞도록 수정한 D-TEDI를 사용하여 APSP algorithm을 구현하고, 다른 algorithm과의 비교 수행 제안한 알고리즘이 기존보다 효율적인 계산 시간을 달성하였으며, 중앙 집중식 구조에 적합함을 확인하여 SDN-based cloud network에 해당 algorithm이 유용함을 증명