Hits:

Date:2019-03-11

Indexed by:Journal Article

Date of Publication:2018-02-26

Journal:COMPUTER NETWORKS

Included Journals:EI、SCIE

Volume:132

Page Number:26-39

ISSN:1389-1286

Key Words:Dynamic unicast and multicast request admissions; Network resource allocation; Online algorithms; Competitive ratio analysis; Ternary content addressable memory (TCAM); Software-defined networks; Combinatorial optimization

Abstract:Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the control plane from the data plane. In a software-defined network, the forwarding table at each switch node usually is implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited numbers of entries. In addition, the bandwidth capacity at each link is limited as well. Provisioning quality services to users by admitting their requests subject to such critical network resource constraints is a fundamental problem, and very little attention has been paid. In this paper, we study online unicasting and multicasting in SDNs with an objective of maximizing the network throughput under network resource constraints, for which we first propose a novel cost model to accurately capture the usages of network resources at switch nodes and links. We then devise two online algorithms with competitive ratios 0(logn) and 0(K-is an element of log n) for online unicasting and multicasting, respectively, where n is the network size, K is the maximum number of destinations in any multicast request, and is an element of is a constant with 0 < is an element of <= 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising. (C) 2017 Elsevier B.V. All rights reserved.