86,963 research outputs found
Very large-scale neighborhood search algorithms for the design of service overlay networks
No full textService Overlay Networks (SONs) allow virtual operators to create and deploy value-added Internet services with Quality of Service guarantees, while leaving the underlying network infrastructure unchanged. The deployment of a SON can be very expensive, and hence its planning requires careful decisions, including the overlay nodes’ placement and the capacity provisioning of the access links that connect the end-users to the SON infrastructure.
In this work we first propose a novel Integer Linear Programming (ILP) model for the overlay network design problem which selects the optimal number and position of overlay nodes, the capacity reserved on each overlay link, as well as the optimal routing of the incoming traffic demands.
Since such model can be solved to the optimum only for small network instances, we further propose an efficient and novel tabu search based heuristic for the planning of SONs that combines polynomial size and very large-scale neighborhoods. The very large-scale neighborhood of the solution given by tabu search is explored efficiently to obtain in a short time a new one that is both far from the current solution and cost-decreasing.
We provide numerical results of the proposed heuristic on a set of realistic, large-size instances, including real ISP topologies, and discuss the effect of different parameters on the characteristics of the planned networks. Furthermore, we compare such results with the bound obtained solving our ILP model in small network scenarios. We show that in the considered network topologies the proposed heuristic performs very close to the optimum with a short computation time, thus providing a promising framework for the design of SONs
Quality of Service Routing of Bandwidth Guaranteed Connections in MPLS Networks
No full textFinding a path in the network for a new incoming connection able to guarantee some quality parameters such as bandwidth and delay is the task of QoS routing techniques developed for new IP networks based on label forwarding. In this paper we focus on the routing of bandwidth guaranteed flows in a dynamic scenario where connection requests arrive at the network edge nodes. When more than a path satisfying the bandwidth demand exists, the selection of the path is done in order to minimize the blocking probability of future requests. We propose a new routing algorithm named Virtual Flow Deviation which exploits the information of the ingress and egress nodes of the network and the traffic statistics. We show that this new algorithm allows to reduce remarkably the blocking probability in most scenarios with respect to previously proposed schemes
A Multi-Commodity Flow Model for Optimal Routing in Wireless MESH Networks
No full textAbstract — We propose a mathematical programming model of the routing problem in multi-hop wireless networks that takes into account quality of service requirements considering bandwidth constraints. The proposed approach is suitable for Wireless MESH Networks (WMN) where topology is almost fixed and routes can be optimized based on global objectives. We then consider and solve the scheduling problem, illustrating how routing and scheduling models can be combined to route flows with guaranteed bandwidth. As an interesting application of the proposed approach, we present some numerical examples that show how our model can be used to estimate the impact of transmission range on network capacity
Power-Controlled Directional Medium Access Control for Wireless Mesh Networks
No full textWireless Mesh Networks have emerged recently as a technology for next-generation wireless networking. To increase the performance of wireless nodes in such networks many approaches have been proposed, including directional and adaptive antennas. However, while adaptive antennas can improve the utilization of the wireless medium by reducing radio interference and the impact of the exposed nodes problem, they can also exacerbate the hidden nodes problem. Thus, MAC protocols for adaptive antennas need to be carefully designed to cope with this issue. In this regard we propose a novel MAC protocol that exploits the potentials offered by adaptive antennas in Wireless Mesh Networks to improve system performance. As key innovative feature of the proposed MAC protocol with respect to existing solutions, the information about wireless medium reservation is spread to the maximum possible extent without interfering with the connections already established in the network. This is achieved by transmitting RTS/CTS frames in all antenna sectors at the maximum allowed power that does not cause interference with ongoing transmissions. The DATA/ACK exchange then takes place directionally and at the minimum necessary power. We measure the performance of the proposed MAC protocol by simulation in several realistic network scenarios, and we compare it with the most notable solutions proposed in the literature. The results show that our proposed scheme allows to increase considerably both the total traffic accepted by the network and fairness between competing connections
Loss Differentiation Schemes for TCP over Wireless Networks
No full textThe use of loss differentiation schemes within the congestioncontrol mechanism of TCP was proposed recently as a way of improvingTCP performance over heterogeneous networks including wirelesslinks affected by random loss. Such algorithms provide TCP with an estimateof the cause of packet losses. In this paper, we propose to usethe Vegas loss differentiation algorithm to enhance the TCP NewRenoerror-recovery scheme, thus avoiding unnecessary rate reduction causedby packet losses induced by bit corruption on the wireless channel.We evaluate the performance of the so-enhanced TCP NewReno source(TCP NewReno-LP) with both extensive simulation and real test bedmeasurements, and we compare it with that achieved by existing solutions,namely TIBET [1], TCP Westwood [2] and the standard TCPNewReno. For that purpose, Linux implementations of TCP NewReno-LP, TIBET and TCP Westwood have been developed and compared withan implementation of NewReno.We show that TCP NewReno-LP achieves higher goodput over wirelessnetworks, while guaranteeing fair share of network resources withclassical TCP versions over wired links. Finally, by studying the TCP behavior with an ideal scheme having perfect knowledge of the causeof packet losses, we provide an upper bound to the performance of allpossible schemes based on loss differentiation algorithms. The proposed TCP enhanced with Vegas loss differentiation algorithm well approachesthis ideal bound
On the performance of dynamic online QoS routing schemes
No full textSeveral dynamic QoS routing techniques have been recently proposed for new IP networks based on label forwarding. However, noextensive performance evaluation and comparison is available in the literature.In this paper, after a short review of the major dynamic QoS routing schemes, we analyze and compare their performance referringto several networks scenarios. In order to set an absolute evaluation ofthe performance quality we have obtained the ideal performance of anyrouting scheme using a novel and flexible mathematical programmingmodel that assumes the knowledge of arrival times and duration of theconnections offered to the network. This model is based on an extensionof the maximum multi-commodity flow problem. Being an integer linearprogramming model, its complexity is quite high and its evaluation isconstrained to networks of limited size. To overcome the computationalcomplexity we have defined an approximate model, based on the multiclass Erlang formula and the minimum multi-commodity cut problem,that provides an upper bound to the routing scheme performance. Theperformance presented in the paper has been obtained by simulation. From the comparison of the schemes considered it turns out that the Virtual Flow Deviation routing algorithm performs best and it almostreaches, in several scenarios, the ideal performance showing that no much gain is left for alternate new schemes
Directional MAC and Routing Schemes for Power Controlled Wireless Mesh Networks with Adaptive Antennas
No full textWireless Mesh Networks (WMNs) have emerged recently as a technology for next-generation wireless networking. Several approaches that exploit directional and adaptive antennas have been proposed in the literature to increase the performance of WMNs. However, while adaptive antennas can improve the wireless medium utilization by reducing radio interference and the impact of the exposed nodes problem, they can also exacerbate the hidden nodes problem. Therefore, efficient MAC protocols are needed to fully exploit the features offered by adaptive antennas. Furthermore, routing protocols that were designed for omnidirectional communications can be redesigned to exploit directional transmissions and the cross-layer interaction between the MAC and the network layer.
In this paper we first propose a novel Power-Controlled Directional MAC protocol (PCD-MAC) for adaptive antennas. PCD-MAC uses the standard RTS–CTS–DATA–ACK exchange procedure. The novel difference is the transmission of the RTS and CTS packets in all directions with a tunable power while the DATA and ACK are transmitted directionally at the minimal required power.
We then propose the Directional Deflection Routing (DDR), a routing algorithm that exploits multiple paths towards the destination based on the MAC layer indication on channel availability in different directions.
We measure the performance of PCD-MAC and DDR by simulation of several realistic network scenarios, and we compare them with other approaches proposed in the literature. The results show that our schemes increase considerably both the total traffic accepted by the network and the fairness among competing connections
- …
