Search

Various middleboxes are ubiquitously deployed in networks to perform packet processing functions, such as firewalling, proxy, scheduling, etc., for the flows passing through them. With the explosion of network traffic and the demand for multiple types of network resources, it has never been more challenging for a middlebox to provide Quality-of-Service (QoS) guarantees to grouped flows. Unfortunately, all currently existing fair queueing algorithms fail in supporting hierarchical scheduling, which is necessary to provide QoS guarantee to the grouped flows of multiple service classes. In this paper, we present two new multi-resource fair queueing algorithms to support hierarchical scheduling, collapsed Hierarchical Dominant Resource Fair Queueing (collapsed H-DRFQ) and dove-tailing H-DRFQ. Particularly, collapsed H-DRFQ transforms the hierarchy of grouped flows into a flat structure for flat scheduling while dove-tailing H-DRFQ iteratively performs flat scheduling to sibling nodes on the original hierarchy. Through rigorous theoretical analysis, we find that both algorithms can provide hierarchical share guarantees to individual flows, while the upper bound of packet delay in dove-tailing H-DRFQ is smaller than that of collapsed H-DRFQ. We implement the proposed algorithms on Click modular router and the experimental results verify our analytical results.

The recent proposed two-phase mechanism is a provable theory to achieve consistent updates for SDN. However, how to make it work for practical rules is important yet unsolved—(1) two-phase mechanism requires that rules in the new configuration after an update are assigned with a distinct version number from rules in the old configuration before an update; but (2) setting rules in each configuration with a distinct version number causes serious rule-space overheads in practice due to the sophisticated “covered” relationships between practical wildcard rules. In this letter, we design a simple yet generic solution for the problem. By using well-designed wildcard-based version number matchings, we simplify the update procedure, make a stream of updates easy to be processed in parallel, and avoid all unwanted rule-space overheads. We think that our mechanism bridges the gap between the theory of two-phase consistent update and the practical issue of how to use it for today's networks.

Network virtualization facilitates sharing and effi- cient utilization of computing and bandwidth resources of an underlying substrate network. As network virtualization becomes popular, it is important to efficiently map a virtual infrastructure (VI) onto a substrate network, such that the survivability of the former can be guaranteed against failures in the latter. In this paper, we study a virtualization layer approach to survivability, whereby the virtualization layer customizes a VI request with redundant nodes and links according to its reliability require- ments and then passes limited information about the augmented VI to the physical layer, where the mapping of the augmented VI takes place. More specifically, we develop a flexible scheme to enhance the original VI graph with K redundant nodes, in order to fight against an arbitrary substrate node failure. In addition, a scenario-based component group (SBCG) concept is proposed to describe resource sharing of enhanced VI requests at the physical layer. We also develop an efficient heuristic that takes advantage of the limited information on SBCG to reduce costs when mapping the enhanced VI to the substrate network. The efficiency of the proposed solution is compared using extensive simulation under various performance metrics. It is shown that the K-redundant-node scheme with SBCG information is more cost efficient than the existing 1-redundant-node solution.

Virtualization is a common technology for resource sharing in data center. To make efficient use of data center resources, the key challenge is to map customer demands (modeled as virtual data center, VDC) to the physical data center effectively. In this paper, we focus on this problem. Distinct with previous works, our study of VDC embedding problem is under the assumption that switch resource is the bottleneck of data center networks (DCNs). To this end, we not only propose relative cost to evaluate embedding strategy, decouple embedding problem into VM placement with marginal resource assignment and virtual link mapping with decided source-destination based on the property of fat-tree, but also design the traffic aware embedding algorithm (TAE) and first fit virtual link mapping (FFLM) to map virtual data center requests to a physical data center. Simulation results show that TAE+FFLM could increase acceptance rate and reduce network cost (about 49% in the case) at the same time. The traffic aware embedding algorithm reduces the load of core-link traffic and brings the optimization opportunity for data center network energy conservation.

Information-centric networking, ICN, is a promising technology for future Internet design, with which a user can directly obtain a content object by its name (or identification), without specifying the location of the content object. In recent years, various ICN architectures have been proposed, and they differ significantly in terms of naming, routing, etc. Consequently, it becomes a major challenge to convince network service providers to deploy ICN-enabled networks. In this article, we will address this challenging issue by proposing a novel deployment framework, versatile ICN, based on software-defined networking concepts, which can efficiently enable different ICN architectures and can facilitate interoperation among ICN instances. Specifically, we first review existing ICN architectures and abstract their core functions. We then elaborate on the main ideas of the VICN framework, including application scenarios, design criteria, and key hardware and software components. To illustrate how the framework can be applied, we develop a prototype that can enable two major ICN architectures, and also facilitate interoperation between them. Using the prototype, we conduct evaluations to show how a user of one ICN instance can obtain a content object from another ICN instance, where the two ICN instances adopt different ICN architectures and are deployed on two NSP networks. Evaluation results confirm that the proposed framework is viable and can lead to much better delay and throughput performance.

As the size and the complexity of optical mesh networks grow, double-link failures become more probable. To protect against double-link failures, we generally have to provision more backup resources with respect to single-link failures. To improve the resource efficiency, it is important to reduce backup resources used for surviving double-link failures. In this paper, we investigate some representative sharing schemes and propose an enhanced resource sharing scheme with resource contention resolution for double-link failures in survivable optical mesh networks. By fully taking into account the temporal and spatial factors, our scheme can accommodate reasonable contention for sharing resources and minimize backup resources for reservation with 100% protection guarantee. Simulation results show that this enhanced resource sharing scheme can achieve satisfactory performance in terms of resource utilization ratio and blocking probability.

Reliability has been well recognized as an important design objective in the design of modern high-speed networks. While traditional approaches offer either 100% protection in the presence of single link failure or no protection at all, connections in real networks may have multiple reliability requirements. The concept of differentiated reliability (DiR) has been introduced in the literature to provide multiple reliability requirements in protection schemes that provision spare resources. In this paper, we consider the problem of routing connections with differentiated reliability in wavelength-division multiplexing (WDM) mesh networks when backup sharing is not allowed. Our objective is to route connections with minimum network cost (e.g., network resources) while meeting their required reliability. We assume connections arrive dynamically one-at-a-time and a decision as to accept or reject a connection has to be made without a priori knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. In this paper, we first present an integer linear programming (ILP) formulation for the problem. By solving the ILP formulation, we can obtain an optimal solution with respect to the current network state for each dynamic arrival. To solve the ILP formulation, however, is time consuming for large networks. We thus propose two approximation algorithms for the problem. The first one, called Shortest-Path-Pair-based Auxiliary graph (SPPA), can obtain an epsiv-approximation solution whose cost is at most 1 + epsiv times the optimum in O((n2(n + 1) + 2mn)(log log(2n) + 1/epsiv)) time, where n and m are the number of nodes and links in a network, respectively. To reduce the computational complexity of the first algorithm, the second algorithm, called Auxiliary graph-based Two-Step Approach (ATSA), is proposed and can obtain a near optimal solution with cost at most 2 + epsiv times that of the optimal solution in O(mn(log log n + 1/epsiv)) time. Results from extensive simulations conducted on two typical carrier mesh networks show the efficiency of the two algorithms.

In this paper, we investigate survivability in wavelength division multiplexing (WDM) mesh networks and propose a new algorithm called improved shared-path protection (ISPP) to completely tolerate the double-link failures. Compared with previous algorithms for protecting double-link failures, i.e., shared-path protection (SPP) and shared-link protection (SLP), the advantage of ISPP is to allow primary paths and backup paths to share the mixed wavelength-links based on the proposed new rules in which some primary wavelength-links can be changed to mixed wavelength-links, which can be shared by primary paths and backup paths. In addition, some mixed wavelength-links also can be shared by different backup paths for saving resources. Simulation results show that ISPP algorithm performs better in resource utilization ratio and blocking probability than conventional SPP and SLP algorithms.

The advances in wavelength-division multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast applications. A single fiber failure in such a network, however, can disrupt the information dissemination to several destination nodes in a "Iight-tree"-based multicast session. Thus it is imperative to protect the multicast sessions. In this paper, we propose a novel protection scheme, called multicast protection through spanning paths (MPSP), for resource efficient multicast protection with spare capacity sharing. Here, a spanning path is a path from a leaf node to any other leaf node of a multicast tree. The key idea of MPSP is first to identify a backup path for each spanning path and then to appropriately select parts of these backup paths to protect the primary multicast tree, so that the total bandwidth allocated to the primary multicast tree and its protection paths (or trees, etc.) is minimized. While previous studies only consider self-sharing and intra-request sharing, to the best of our knowledge, this is the first time to take inter-request sharing of spare capacity into consideration when protecting dynamic multicast sessions. We use simulations to demonstrate the performance of the MPSP scheme. It is shown that significant performance improvements are achieved in terms of average cost per multicast session and blocking probability. Compared with existing schemes, the average cost is reduced by about 22% and the blocking probability can be reduced by about 27% in average.

Previous research on survivability with differentiated reliability in wavelength-division-multiplexing (WDM) optical mesh networks mostly considered the failure probability of a fiber link with the link length that may not be a good solution for consideration of shared-risk link groups (SRLGs). In this paper, we propose a new model of failure probability with the SRLG constraints in WDM optical mesh networks. Based on this model, we present the backup resources assignment and the routing selection method with the differentiated reliable requirements of users. To evaluate the performances of this model, we propose a novel survivable routing algorithm called partial SRLG-disjoint protection (PSDP) to tolerate the single-SRLG failure. Compared with the previous algorithm, PSDP can obtain a better resource utilization ratio and lower blocking probability. Simulation results are shown to be promising.

In this paper, we investigate the problem of dynamic survivable routing in wavelength-division-multiplexing optical networks and propose a new path-protection algorithm called Enhanced Shared Backup Paths Protection (ESBPP) to provide the complete survivability for double-link failures. In order to improve the resource-utilization ratio, we present the new rule of sharing backup resources that can yield better resource-utilization ratio than previous methods. In order to overcome the problem of trap paths, we develop a new routing method to find the feasible solution with three link-disjoint paths for each connection request. Compared to previous algorithms for double-link failures, ESBPP can obtain higher resource-utilization ratio and lower blocking probability

In this paper, the authors focus on studying the problem of survivable routing provisioning to prevent single link failure in wavelength-division-multiplexing (WDM) mesh networks, and propose a novel protection scheme called mixed shared path protection (MSPP). With MSPP, the authors define three types of resources: 1) primary resources that can be used by primary paths; 2) spare resources that can be shared by backup paths; and 3) mixed resources that can be shared by both the primary and the backup paths. In the proposed protection scheme, each connection is assigned a primary path and a link disjoint backup path. Differing from pervious protection schemes, MSPP allows some primary paths and backup paths to share the common mixed resources if the corresponding constraints can be satisfied. In this paper, the authors consider three types of path-based protection schemes, i.e., dedicated path protection (DPP), shared path protection (SPP), and MSPP, and evaluate their performance for both the static and the dynamic provisioning problems. Simulation results show that MSPP outperforms DPP and SPP

The medium-access control (MAC) protocol is one of the key components in wireless local area networks (WLANs). The main features of a MAC protocol are high throughput, good fairness, energy efficiency, and support priority guarantees, especially under distributed contention-based environment. Based on the current standardized IEEE 802.11 distributed coordination function (DCF) protocol, this paper proposes a new efficient collision resolution mechanism, called GDCF. Our main motivation is based on the observation that 802.11 DCF decreases the contention window to the initial value after each success transmission, which essentially assumes that each successful transmission is an indication that the system is under low traffic loading. GDCF takes a more conservative measure by halving the contention window size after c consecutive successful transmissions. This "gentle" decrease can reduce the collision probability, especially when the number of competing nodes is large. We compute the optimal value for c and the numerical results from both analysis and simulation demonstrate that GDCF significantly improve the performance of 802.11 DCF, including throughput, fairness, and energy efficiency. In addition, GDCF is flexible for supporting priority access by selecting different values of c for different traffic types and is very easy to implement it, as it does not requires any changes in control message structure and access procedures in DCF.

This paper studies multihop optical networks in which nodes employ wavelength routing switches that enable the establishment of wavelength division multiplexed (WDM) channels, called lightpaths, between node pairs. In fact, most optical networks are multifiber networks. The problem of dynamical routing and assignment of wavelength (RAW) in such networks is studied in this paper. Two resource assignment strategies, PACK and SPREAD, are proposed. By virtue of a layered-graph, routing and assignment of wavelength subproblems can be considered simultaneously. These two strategies can be used to solve the RAW problem in networks with even links as well as that in networks with uneven links. Simulation shows that layered-graph-based RAW algorithms perform better than the existing ones. It also shows that SPREAD with distributive use of network resources can achieve better performance than PACK with collective use of resources in multifiber networks. The layered-graph-based algorithms can effectively deal with the failure of the fiber/link and node. By making use of the special structure of the layered-graph, we propose a shortest path algorithm, whose complexity is lower than that of the standard shortest path algorithm.

The problem of provisioning survivable multicast sessions in WDM mesh networks has been studied in the literature, and several heuristics have been proposed. We in this paper propose a novel and efficient heuristic algorithm, called segment exclusion (SE), to improve existing algorithms in terms of the cost (e.g., resources) used for provisioning a multicast session. Simulations are conducted to verify the effectiveness of SE.

This letter proposes a novel dynamic shared protection algorithm called multiple sub-backup paths (MSBP) to survive multiple links failures in WDM optical networks. In MSBP, each connection will be first assigned one primary path and one link-disjoint backup path, and following will be assigned multiple sub-backup paths based on the corresponding routing policy. Compared to previous algorithm DLFP, MSBP not only has the close protection ability to the DLFP but also can save significant resources

The maximum throughput of an N/spl times/N nonblocking packet switch with input queues and two priority classes is analyzed. Packets are of fixed length and the switch operation is slotted. Packets of both priority classes are queued when waiting for service. High-priority packets preempt low-priority ones and move ahead of all low-priority packets waiting in the queue. A new method of analysis is employed. The calculated results of the maximum throughput obtained are close to the simulation results. >

In this comment, two typos in Ho , 2004, ldquoSegment shared protection in mesh communication networks with bandwidth guaranteed tunnelsrdquo, are pointed out (see ibid., vol.12, no.6, p1105-18, 2006). These typos may puzzle readers or prevent them from correctly understand this paper. In the second part of this comment, we present corrections to the typos.