基于MPLS-DiffServ的LSP动态抢占算法研究

在支持具有不同优先级和不同QoS需求的多业务网络中,抢占是带宽分配和管理的有效策略,但同时也对网络造成了振荡。基于普通的LSP路由方案,提出了一个动态的LSP抢占算法——Min_Prec算法:总是首先抢占最低优先级的LSP;在同一个优先级别内最优化被抢占的带宽和LSP数目。最后,通过引入一个抢占策略对于路由过程的反馈机制,减少抢占引起的重路由,增强网络稳定性。仿真结果验证了算法的有效性、优越性。     

A core stateless bandwidth broker architecture for scalable support of guaranteed services

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.     

Providing End-to-End Quality of Service with Optimal Least Weight Routing in Next-Generation Multiservice High-Speed Networks

Routing algorithms play a critical role in meeting both the stringent quality of service (QoS) requirements of guaranteed services and the certain QoS requirement of assured services over next-generation multiservice high-speed networks. In this paper, we propose the use of optimal least weight routing (OLWR) algorithm for routing QoS flows in high-speed networks. The main principle of our algorithm is that the choice of the most appropriate route is based on a set of parameters (least weight parameters) that estimate and consider the impact that the acceptance and routing decision of a call request belonging to a specific class would have on the network and other classes of service. Effective bandwidth, bandwidth and trunk reservation techniques, along with load balancing and packing trade-off considerations, are also introduced in the proposed routing algorithm. The performance evaluation of our algorithm is achieved via modeling and simulation of multiclass service routing in various network topologies. The performance results demonstrated that OLWR outperforms both the multihop least-loaded routing algorithms and the multihop most-loaded routing algorithms in terms of both revenue and carried load.     

A Hybrid End-to-End QoS Path Computation Algorithm for PCE-Based Multi-Domain Networks

Inter-domain quality of service (QoS) routing is a challenging problem for today’s Internet. This problem requires the computation of paths that cross multiple domains and meet different QoS constraints. In addition, the used computation methods must meet the constraints of confidentiality and autonomy imposed by the domains of different operators. Path computation element (PCE)-based architecture offers a promising solution for inter-domain QoS routing. It ensures the computation of end-to-end QoS paths while preserving the confidentiality and the autonomy of the domains. In this paper, we propose a novel hybrid end-to-end QoS path computation algorithm, named HID-MCP, for PCE-based networks. HID-MCP is a hybrid algorithm that combines the advantages of pre-computation and on-demand computation to obtain end-to-end QoS paths. Moreover, it integrates a crankback mechanism for improving path computation results in a single domain or in multiple domains based on the PCE architecture. Detailed analyses are provided to assess the performance of our algorithm in terms of success rate and computational complexity. The simulation results show that our algorithm has an acceptance rate of the requests very close to the optimal solution; precisely, the difference is lower than 1 % in a realistic network. Moreover, HID-MCP has a low computational complexity. Besides, our solution relies on the PCE architecture to overcome the limitations related to inter-domain routing such as domain autonomy and confidentiality.     

Impact of bandwidth request schemes for Best-Effort traffic in IEEE 802.16 networks

In IEEE 802.16 networks, bandwidth request–grant schemes are employed for reducing data collision and supporting various QoS requirements. In this paper, we investigate the impact of such schemes on Best-Effort (BE) traffic. We examine three candidate schemes. In the first scheme, each Subscribe Station (SS) attempts to request bandwidth in every frame to reduce delay. In the second scheme, the number of bandwidth request is limited to avoid collisions in bandwidth request. In the third scheme, a base station allocates bandwidth to each SS based on the measured sending rate without explicit bandwidth request. We quantitatively analyze the performance of these schemes in terms of the collision rate and buffer length. We also present a simulation study to validate our analysis and to observe the impact of these schemes on BE traffic. This paper shows that IEEE 802.16 networks can be effectively managed through appropriate bandwidth request schemes. It is also shown that bandwidth allocation without request can be an alternative for increasing utilization.     

多跳无线局域网中的QoS路由(MQR)协议

针对多跳无线局域网(MWLAN)的带宽受限以及网络拓扑动态性等特点,本文提出了一种优化的多跳无线局域网QoS路由(MQR)协议,该协议提出的节点生成树算法可以根据移动节点和AP之间的跳数以及节点剩余能量组织MWLAN的树形网络拓扑;同时,该协议改进了传统的节点剩余带宽估计算法,使得网络节点可用带宽估计更加精确,在寻路过程中根据节点可用带宽信息为数据流提供软状态QoS保证.仿真结果表明,MQR协议可以有效的降低平均寻路确认时延并提高网络带宽利用率,同时,寻路开销和平均端对端分组时延也得到较好的控制.     

Exploiting slack time for just-in-time scheduling in wireless sensor networks

We consider the problem of real-time data collection in wireless sensor networks, in which data need to be delivered to one or more sinks within end-to-end deadlines. To enhance performance with respect to end-to-end deadline miss ratio, existing approaches schedule packets by prioritizing them based on per-packet deadlines and other factors such as the distance to the sink. However, important factors affecting the end-to-end performance such as queuing delays and buffer overruns have largely been ignored in the existing real-time schemes. Packet prioritization by itself cannot assist with these issues, and may in fact, exacerbate them for real-time data collection, since many high priority packets may simultaneously contend for the constrained network resources. In sensor networks, where the channel bandwidth and buffer space are often quite limited, these issues can dramatically impact real-time performance. Based on this observation, we propose Just-in-Time Scheduling (JiTS) strategies where packets are judiciously delayed within their slack time to reduce contention and load balance the use of the network buffers. We explore several policies for delaying data packets at different intermediate nodes considering potential contention. In addition, we also show that the routing protocol has a significant impact on real-time performance. In particular, shortest path routing leads to considerably better performance than geographic forwarding, which is often used for real-time data transmission in wireless sensor networks. Using an extensive simulation study, we demonstrate that JiTS can significantly improve the deadline miss ratio and packet drop ratio compared to two state-of-the-art approaches for real-time packet delivery for sensor networks (RAP and SPEED) under various scenarios. Notably, JiTS requires neither lower layer (e.g., MAC layer) support nor synchronization among the sensor nodes.     

Flow-level QoS for a dynamic load of rate adaptive sessions sharing a bottleneck link

We consider the flow-level quality of service (QoS) seen by a dynamic load of rate adaptive sessions sharing a bottleneck link based on fair share bandwidth allocation. This is of interest both in considering wired networks supporting rate adaptive multimedia sessions and wireless networks supporting voice with rate adaptation to realize graceful degradation during congested periods. Two QoS metrics are considered: the time-average instantaneous utility of the allocated bandwidth, and the time-average of transition penalties associated with the changes in allocation seen by a flow. We present a simple model for rate adaptation, where (heterogeneous) flows can vary their rates within (different) ranges, and present closed-form results for these perceived flow-level QoS metrics. We then prove asymptotic results for large capacity systems exhibiting the salient features of rate adaptation in a dynamic network. Finally, we provide a concrete example, showing how the QoS seen by sessions with different degrees of adaptivity would vary under a natural fair bandwidth allocation policy.     

Load-Balancing in Multistage Interconnection Networks under Multiple-Pass Routing

Multistage interconnection networks (MINs) have been widely used in multiprocessor systems, and recently they have been adopted as a way to construct ATM switches for broadband networks. In such systems, the fault-tolerant ability is an important issue. Many researchers have proposed ways to enhance the reliability of MINs, among them a low-cost and efficient way is to use multipass routing schemes in MINs in which thedynamic full access(DFA) property exists. The performance of multipass routing, however, has been largely ignored by researchers in the past. In this paper, we show that multipass routing may degrade the system performance if the communication loads are not well balanced among processors; congestion may appear in some processors and the useful communication bandwidth is badly affected. We propose methods to design DFA routing schemes that are load-balanced and thus can utilize system resources (i.e., the bandwidth) more efficiently.     

Dynamic load balancing in IP-over-WDM optical burst switching networks

In this paper, we consider the problem of dynamic load balancing in wavelength division multiplexing (WDM)-based optical burst switching (OBS) networks. We propose a load balancing scheme based on adaptive alternate routing aimed at reducing burst loss. The key idea of adaptive alternate routing is to reduce network congestion by adaptively distributing the load between two pre-determined link-disjoint alternative paths based on the measurement of the impact of traffic load on each of them. We develop two alternative-path selection schemes to select link-disjoint alternative paths to be used by adaptive alternate routing. The path selection schemes differ in the way the cost of a path is defined and in the assumption made about the knowledge of the traffic demands. Through extensive simulation experiments for different traffic scenarios, we show that the proposed dynamic load balancing algorithm outperforms the shortest path routing and static alternate routing algorithms.