Journal of High Speed Networks

Network resource provisioning techniques need to perform both inter-path and intra-path load balancing to maximize the network's resource usage efficiency while supporting end-to-end QoS guarantees. This paper focuses on the intra-path load balancing problem: How to partition the end-to-end QoS requirement of an aggregate network flow along the links of a given path such that the deviation in the loads on these links is as small as possible? We propose a set of new algorithms, called Load-balancing Slack Allocation (LSA), to solve this QoS partitioning problem for unicast and multicast traffic. The key concept in the LSA algorithms is the notion of slack, which quantifies the flexibility available in partitioning the end-to-end QoS requirement across the links of a selected path or tree. We show that one can improve network resource usage efficiency by carefully selecting a slack partition that explicitly balances the loads on the underlying links. These algorithms can simultaneously partition multiple QoS requirements such as delay and delay violation probability bounds. A detailed simulation study demonstrates that, compared with previous approaches, the LSA algorithms can increase the total number of long-term flows that can be provisioned along a network path by up to 1.2 times for deterministic and 2.8 times for statistical delay guarantees.

In this paper, we address the issue of optimizing the per request cost and maximizing the number of requests that can be served by a networked system that demands staging of data at vantage sites. In order to provide a guaranteed Quality of Services, generation of multicast trees with end-to-end delay constraints is recommended to minimize the costs. Since such an issue has been proved to be NP-complete in a networked environment, we proposed two efficient and practically realizable heuristic algorithms, referred to as Source-Initiated Scheduling (SIS) algorithm and Client-Initiated Scheduling (CIS) algorithm to solve the problem in polynomial time. Both SIS and CIS algorithms judiciously combine the concept of QoS-constrained multicast routing and network caching, so that the copies of data to be staged can be dynamically cached in the network. These strategies are carefully designed to consider the underlying resource constraints imposed by the dynamic network environments, such as link bandwidth availability, data availability on the network, and the storage capabilities of a site. We analyze and quantify the performance under several influencing parameters such as link availability, cache capacity and the data availability. Simulation results show that both of the proposed algorithms are able to reduce the service cost and achieve a high acceptance ratio.

Traffic grooming is one of the most important problems in optical networks with high scientific and commercial value. Efficient grooming of traffic can not only effectively reduce the network's cost but also optimize its performance. To deal with the grooming of changing traffic in SONET/WDM rings, we classified it into the following two types: (1) reconfigurable grooming of deterministic dynamic traffic (REGDT); (2) reconfigurable grooming of non-deterministic dynamic traffic (REGNT). Two types of REGNT are studied, and two cases (best-fit and full-fit) for handling it were proposed in this paper. Further more, two heuristic algorithms, GA1 and GA2, which combine genetic algorithm with traffic-splitting heuristics, were developed to deal with each case. Computer simulations showed that the algorithms proposed in this paper can achieve much better results than previous ones for these two cases.

Ternary content-addressable memory (TCAM) has been widely used to perform fast packet classification due to its ability of solving the problem in O(1) time without considering the number of entries, mask continuity and their lengths. However, it also comes with several shortcomings, such as the limited number of entries, expensive cost and power consumption. We propose an efficient algorithm to reduce the required TCAM bits by encoding the IP address portion of the policies. With the proposed scheme, the achieved compression ratio can be as small as 9% for IPv6 policies. Moreover, the TCAM throughput is improved by a factor of 175% with pipelining design. Obviously, the proposed scheme is attractive for the forthcoming IPv6.

Active and Programmable networks change the functionality of intermediate nodes by using agents and active packets. This paper presents a novel packet scheduling scheme called Active Scheduling to maintain QoS in virtual private networks (VPNs) within the domain of adaptive and programmable networks. In Active Scheduling agents on the router monitor the accumulated queuing delay for each service. In order to keep the end-to-end delay within the bounds, the weights for services are adjusted dynamically by agents on the routers spanning the VPN. If there is a rise or fall in queuing delay of a service, an agent on a downstream router informs the upstream routers to alter the weights of their queues. This keeps the end-to-end delay of services within the defined bounds and offers better QoS compared to VPNs using static WFQ. The paper describes Active Scheduling, and presents simulation results and these are compared with WFQ.

In computer networks, switching is used as a juncture to provide a path to a message to pass on. The knockout switch is a specially designed architecture having equal number of input and output lines. An input cell, in this switch, passes through several stages like filters, concentrators and shifters (or queue). The cell may be under unicasting or multicasting depending upon the number of tokens of output lines allotted. This paper considers the random movement of a cell, inside the design of knockout switch, up to the output line. A Markov chain model is proposed to explain the transitions on various states of filter, concentrator and shifter. The outgoing probability is computed using the number of transitions performed by the cell. Several theorems and corollaries are derived for explaining the behavior of the cell movement. The expected number of transitions are computed keeping various situational constraints. A simulation study is performed to support the derived theorems under the model.