Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTransiently Consistent SDN Updates: Being Greedy is Hard
45
0
0.0
(
0
)
Added by
Stefan Schmid
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible, optimized, yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. In particular, it has been shown that there exists an inherent tradeoff between update consistency and speed. This paper revisits the problem of updating an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (greedy) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.
rate research
Read More
Computer networks have become a critical infrastructure. In fact, networks should not only meet strict requirements in terms of correctness, availability, and performance, but they should also be very flexible and support fast updates, e.g., due to policy changes, increasing traffic, or failures. This paper presents a structured survey of mechanism and protocols to update computer networks in a fast and consistent manner. In particular, we identify and discuss the different desirable consistency properties that should be provided throughout a network update, the algorithmic techniques which are needed to meet these consistency properties, and the implications on the speed and costs at which updates can be performed. We also explain the relationship between consistent network update problems and classic algorithmic optimization ones. While our survey is mainly motivated by the advent of Software-Defined Networks (SDNs) and their primary need for correct and efficient update techniques, the fundamental underlying problems are not new, and we provide a historical perspective of the subject as well.
We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.
202 -
Adrien Friggeri
, Eric Fleury (ENS / LIPn Laboratoire de lInformatique du Parallelisme / INRIA Grenoblen Rh^one-Alpes
2011
We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
For many, this is no longer a valid question and the case is considered settled with SDN/NFV (Software Defined Networking/Network Function Virtualization) providing the inevitable innovation enablers solving many outstanding management issues regarding 5G. However, given the monumental task of softwarization of radio access network (RAN) while 5G is just around the corner and some companies have started unveiling their 5G equipment already, the concern is very realistic that we may only see some point solutions involving SDN technology instead of a fully SDN-enabled RAN. This survey paper identifies all important obstacles in the way and looks at the state of the art of the relevant solutions. This survey is different from the previous surveys on SDN-based RAN as it focuses on the salient problems and discusses solutions proposed within and outside SDN literature. Our main focus is on fronthaul, backward compatibility, supposedly disruptive nature of SDN deployment, business cases and monetization of SDN related upgrades, latency of general purpose processors (GPP), and additional security vulnerabilities, softwarization brings along to the RAN. We have also provided a summary of the architectural developments in SDN-based RAN landscape as not all work can be covered under the focused issues. This paper provides a comprehensive survey on the state of the art of SDN-based RAN and clearly points out the gaps in the technology.
Software Defined Networking (SDN) is a promising approach for improving the performance and manageability of future network architectures. However, little work has gone into using SDN to improve the performance and manageability of existing networks without requiring a major overhaul of the existing network infrastructure. In this paper, we show how we can dramatically improve, or supercharge, the performance of existing IP routers by combining them with SDN-enabled equipment in a novel way. More particularly, our supercharged solution substantially reduces the convergence time of an IP router upon link or node failure without inducing any reconfiguration of the IP router itself. Our key insight is to use the SDN controller to precompute backup forwarding entries and immediately activate them upon failure, enabling almost immediate data-plane recovery, while letting the router converge at its typical slow pace. By boosting existing equipments performance, we not only increase their lifetime but also provide new incentives for network operators to kickstart SDN deployment. We implemented a fully functional supercharger and use it to boost the convergence performance of a Cisco Nexus 7k router. Using a FPGA-based traffic generator, we show that our supercharged router systematically converges within ~150ms, a 900x reduction with respect to its normal convergence time under similar conditions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
