logo

SCIENCE CHINA Information Sciences, Volume 63 , Issue 7 : 172102(2020) https://doi.org/10.1007/s11432-019-2644-8

From model to implementation: a network algorithm programming language

More info
  • ReceivedJan 25, 2019
  • AcceptedJul 22, 2019
  • PublishedJun 1, 2020

Abstract

Software-defined networking (SDN) is a revolutionary technology that facilitates network management and enables programmatically efficient network configuration, thereby improving network performance and flexibility. However, as the application programming interfaces (APIs) of SDN are low-level or functionality-restricted, SDN programmers cannot easily keep pace with the ever-changing devices, topologies, and demands of SDN. By deriving motivation from industry practice, we define a novel network algorithm programming language (NAPL) that enhances the SDN framework with a rapid programming flow from topology-based network models to C+ implementations, thus bridging the gap between the limited capability of existing SDN APIs and the reality of practical network management. In contrast to several state-of-the-art languages, NAPL provides a range of critical high-level network programming features:łinebreak (1) topology-based network modeling and visualization; (2) fast abstraction and expansion of network devices and constraints; (3) a declarative paradigm for the fast design of forwarding policies; (4) a built-in library for complex algorithm implementation; (5) full compatibility with C+ programming; and (6) user-friendly debugging support when compiling NAPL into highly readable C+ codes. The expressiveness and performance of NAPL are demonstrated in various industrial scenarios originating from practical network management.


References

[1] McKeown N. Software-defined networking. In: Proceedings of Keynote Talk at the 28th Conference on Computer Communications, Valencia, 2009. Google Scholar

[2] McKeown N, Anderson T, Balakrishnan H. Openflow: enabling innovation in campus networks. SIGCOMM Comput Commun Rev, 2008, 38: 69 CrossRef Google Scholar

[3] Kreutz D, Ramos F M V, Esteves Verissimo P. Software-Defined Networking: A Comprehensive Survey. Proc IEEE, 2015, 103: 14-76 CrossRef Google Scholar

[4] Nunes B A A, Mendonca M, Nguyen X N. A Survey of Software-Defined Networking: Past, Present, and Future of Programmable Networks. IEEE Commun Surv Tutorials, 2014, 16: 1617-1634 CrossRef Google Scholar

[5] Hakiri A, Gokhale A, Berthou P. Software-Defined Networking: Challenges and research opportunities for Future Internet. Comput Networks, 2014, 75: 453-471 CrossRef Google Scholar

[6] Monsanto C, Foster N, Harrison R, et al. A compiler and run-time system for network programming languages. In: Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Philadelphia, 2012. 217--230. Google Scholar

[7] Foster N, Harrison R, Freedman M J, et al. Frenetic: a network programming language. In: Proceeding of the 16th ACM SIGPLAN International Conference on Functional Programming, Tokyo, 2011. 279--291. Google Scholar

[8] Monsanto C, Reich J, Foster N, et al. Composing software-defined networks. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, Lombard, 2013. Google Scholar

[9] Katta N P, Rexford J, Walker D. Logic programming for software-defined networks. In: Proceeding of Workshop Cross Model Design Validation, Copenhagen, 2012. Google Scholar

[10] Soule R, Basu S, Kleinberg R, et al. Managing the network with Merlin. In: Proceeding of the 12th ACM Workshop on Hot Topics in Networks, College Park, 2013. Google Scholar

[11] Hunt J. Inheritance considered harmful In: Guide to the Unified Process featuring UML, Java and Design Patterns. Berlin: Springer, 2003. Google Scholar

[12] Ziegelmann M. Constrained Shortest Paths and Related Problems — Constrained Network Optimization. Saarbrücken: VDM Verlag, 2007. Google Scholar

[13] Anderson C J, Foster N, Guha A, et al. Netkat: semantic foundations for networks. SIGPLAN Not, 2014, 49: 113--126. Google Scholar

[14] Voellmy A, Hudak P. Nettle: taking the sting out of programming network routers. In: Proceedings of the 13th International Conference on Practical Aspects of Declarative Languages, Austin, 2011. 235--249. Google Scholar

[15] Nelson T, Guha A, Dougherty D J, et al. A balance of power: expressive, analyzable controller programming. In: Proceedings of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013. 79--84. Google Scholar

[16] Voellmy A, Wang J, Yang Y R, et al. Maple: simplifying SDN programming using algorithmic policies. In: Proceedings of ACM SIGCOMM 2013 Conference, Hong Kong, 2013. 87--98. Google Scholar

[17] Bosshart P, Varghese G, Walker D. P4: programming protocol-independent packet processors. SIGCOMM Comput Commun Rev, 2014, 44: 87-95 CrossRef Google Scholar

[18] Gude N, Koponen T, Pettit J. NOX: towards an operating system for networks. SIGCOMM Comput Commun Rev, 2008, 38: 105-110 CrossRef Google Scholar

[19] Hinrichs T L, Gude N, Casado M, et al. Practical declarative network management. In: Proceedings of the 1st ACM SIGCOMM Workshop on Research on Enterprise Networking, New York, 2009. Google Scholar

[20] Huang S S, Green T J, Loo B T. Datalog and emerging applications: an interactive tutorial. In: Proceedings of ACM SIGMOD International Conference on Management of Data, Athens, 2011. 1213--1216. Google Scholar

[21] 2-NSoftw-Pract Exper 2000, 30: 1203--1233. Google Scholar

[22] Levine J R, Mason T, Brown D. Lex & Yacc. 2nd ed. Sebastopol: O'Reilly, 1992. Google Scholar

  • Table 1  

    Table 1Commonly used network properties

    Name Type Description
    NodeType String Type of the node (“ip"/“optical")
    LinkType String Type of the link (“ip"/“optical")
    Bandwidth Float Bandwidth of the link
    HopCount Integer Number of hops through the device
    Cost Float Cost of the network device or link
    Delay Float Delay of the network device or link
    Availability Boolean Availability of the device or link
  • Table 2  

    Table 2Performance evaluation of NAPL with a set of benchmark NAPL programs

    Category ID Name Lines of code Bytes of code Time (ms)
    NAPL C+ NAPL C+ NAPL C+
    1 Basic type 60 72 1357 1784 2 2
    2 Complex type 94 116 2219 2763 2 2
    3 Data structure 98 154 1941 3438 78 74
    4 Expression 57 79 1050 1819 23 22
    5 Function 60 72 872 1271 22 21
    General grammar 6 I/O 24 99 830 2886 20 19
    7 Statement 71 83 1448 1715 12 12
    8 Class definition 42 54 753 1197 18 17
    9 Polymorphism 40 52 452 914 13 12
    10 Attribute 81 93 2078 2625 20 19
    11 Comprehensive examples 211 331 4166 6792 2 2
    12 C+ code plug-in 28 40 652 1062 2 2
    13 Dynamic library calls 6 18 328 586 3 3
    External interfacing 14 Third-party library calls 52 68 1594 1886 3 3
    15 Boost 67 84 2555 3006 6 6
    16 Lemon 67 85 1872 2161 6 6
    17 Custom attributes 41 768 900 16533 14 13
    18 Custom demands 24 254 548 6205 16 15
    19 Graph 28 844 816 24376 26 25
    Network objects 20 Link 43 817 779 17802 29 28
    21 Node 42 769 704 17105 21 20
    22 Path 16 1146 354 25518 21 20
    23 Service 25 378 690 8635 26 24
    24 Network 21 1289 508 33290 3 3
    25 Network statements 67 1920 3368 62648 20 19
    26 Routing statements 72 1792 3469 57172 23 22
    27 Network object operations 23 1508 609 40155 28 27
    Network statements 28 Others 21 1856 515 47295 12 11
    29 Weight 67 1197 1409 27213 16 15
    30 Statements in network algorithms 49 1997 3014 62640 4 4
    31 Attributes of network objects 50 1535 1306 44032 5 5
    Network algorithms 32 CSPF 14 1671 485 51745 30 29
    33 CSPDP 14 2170 492 62675 65 62
    34 IP + optical 19 1893 586 56709 14 13
    35 Optical 111 1430 3294 39366 14 13
    36 P2MP 157 2347 4404 68280 76 72
    37 Recovery 22 1914 734 56277 11 10

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号