Link capacity dimensioning is the periodic task where ISPs have to make provisions for sudden traffic bursts and network failures to assure uninterrupted operations. This provision comes in the form of link working capacities with noticeable amounts of headroom, i.e., spare capacities that are used in case of congestions or network failures. Distributed routing protocols like OSPF provide convergence after network failures and have proven their reliable operation over decades, but require overprovisioning and headroom of over 50 . However, SDN has recently been proposed to either replace or work together with OSPF in routing Internet traffic. This paper addresses the question of how to robustly dimension the link capacities in emerging hybrid SDN OSPF networks. We analyze the networks with various implementations of hybrid SDN OSPF control planes, and show that our idea of SDN Partitioning requires less amounts of spare capacity compared to legacy or other hybrid SDN OSPF schemes, outperformed only by a full SDN deployment.
SDN Partitioning, if deployed like in Figure b, allows to advertise routing updates individually customized for each of the three sub-domains, which in turn enables to control the routing of traffic flows between these sub-domains. It should be noted that the OSPF routing of sub-domain-internal traffic is not affected at all, but can therefore also not be controlled by the network management application. To enable SDN Partitioning's separation of the OSPF domain into distinct sub-domains, a few SDN-enabled routers must be placed in strategic positions in the network, such that their removal cuts the topology into disconnected components. Obviously, the way the network is clustered into sub-domains is determined solely by the operator's choice of nodes that will be exchanged with SDN nodes, i.e., the sub-domains are determined only once in the beginning and can be changed only by adding new or changing the position of existing SDN nodes. In graph theory parlance, this means that the SDN-enabled routers must constitute a vertex separator. The three example networks used in the numerical evaluation have been partitioned with the algorithm that we introduced in @cite_11 .
@cite_11
1619430436 2152964475 2116956900 2137996019
Network operators can and do deploy multiple routing control-planes, e.g., by running different protocols or instances of the same protocol. With the rise of SDN, multiple control-planes are likely to become even more popular, e.g., to enable hybrid SDN or multi-controller deployments. Unfortunately, previous works do not apply to arbitrary combinations of centralized and distributed control-planes. In this paper, we develop a general theory for coexisting control-planes. We provide a novel, exhaustive classification of existing and future control-planes (e.g., OSPF, EIGRP, and Open-Flow) based on fundamental control-plane properties that we identify. Our properties are general enough to study centralized and distributed control-planes under a common framework. We show that multiple uncoordinated control-planes can cause forwarding anomalies whose type solely depends on the identified properties. To show the wide applicability of our framework, we leverage our theoretical insight to (i) provide sufficient conditions to avoid anomalies, (ii) propose configuration guidelines, and (iii) define a provably-safe procedure for reconfigurations from any (combination of) control-planes to any other. Finally, we discuss prominent consequences of our findings on the deployment of new paradigms (notably, SDN) and previous research works. This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the maximum possible throughput. As an alternative to increasing the throughput fraction by designing new algorithms, we present a novel approach that takes advantage of the inherent multi-radio capability of WMNs. We show that this capability can enable partitioning of the network into subnetworks in which simple distributed scheduling algorithms can achieve 100 throughput. The partitioning is based on the notion of Local Pooling. Using this notion, we characterize topologies in which 100 throughput can be achieved distributedly. These topologies are used in order to develop a number of centralized channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms pre-partition a network in a manner that not only expands the capacity regions of the subnetworks but also allows distributed algorithms to achieve these capacity regions. We evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region. We note that while the identified topologies are of general interference graphs, the partitioning algorithms are designed for networks with primary interference constraints. The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology-control (CBTC) algorithm. This algorithm does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node u transmits with the minimum power p sub u, spl alpha required to ensure that in every cone of degree spl alpha around u, there is some node that u can reach with power p sub u, spl alpha . We show that taking spl alpha =5 spl pi 6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from s to t when every node communicates at maximum power then, if spl alpha spl les 5 spl pi 6, there is still a path in the smallest symmetric graph G sub spl alpha containing all edges (u,v) such that u can communicate with v using power p sub u, spl alpha . On the other hand, if spl alpha >5 spl pi 6, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations. Wireless ad hoc and sensor networks (WSNs) often require a connected dominating set (CDS) as the underlying virtual backbone for efficient routing. Nodes in a CDS have extra computation and communication load for their role as dominator, subjecting them to an early exhaustion of their battery. A simple mechanism to address this problem is to switch from one CDS to another fresh CDS, rotating the active CDS through a disjoint set of CDSs. This gives rise to the connected domatic partition (CDP) problem, which essentially involves partitioning the nodes V(G) of a graph G into node disjoint CDSs. We have developed a distributed algorithm for constructing the CDP using our maximal independent set (MlS)-based proximity heuristics, which depends only on connectivity information and does not rely on geographic or geometric information. We show that the size of a CDP that is identified by our algorithm is at least [delta+1 beta(c+1)] - f, where delta is the minimum node degree of G, beta les 2, c les 11 is a constant for a unit disk graph (UDG), and the expected value of f is epsidelta|V|, where epsi Lt 1 is a positive constant, and delta ges 48. Results of varied testing of our algorithm are positive even for a network of a large number of sensor nodes. Our scheme also performs better than other related techniques such as the ID-based scheme.