Advanced channel reservation is emerging as an important feature of ultra high-speed networks requiring the transfer of large files. Applications include scientific data transfers and database backup. In this paper, we present two new, on-line algorithms for advanced reservation, called BatchAll and BatchLim, that are guaranteed to achieve optimal throughput performance, based on multi-commodity flow arguments. Both algorithms are shown to have polynomial-time complexity and provable bounds on the maximum delay for 1+epsilon bandwidth augmented networks. The BatchLim algorithm returns the completion time of a connection immediately as a request is placed, but at the expense of a slightly looser competitive ratio than that of BatchAll. We also present a simple approach that limits the number of parallel paths used by the algorithms while provably bounding the maximum reduction factor in the transmission throughput. We show that, although the number of different paths can be exponentially large, the actual number of paths needed to approximate the flow is quite small and proportional to the number of edges in the network. Simulations for a number of topologies show that, in practice, 3 to 5 parallel paths are sufficient to achieve close to optimal performance. The performance of the competitive algorithms are also compared to a greedy benchmark, both through analysis and simulation.
Many papers have discussed the issue of path dispersion and attempted to achieve good throughput with limited dispersion, a survey of some results in this field is given in @cite_9 . In @cite_23 @cite_21 heuristic methods of controlling multipath routing and some quantitative measures are presented. As far as we know, our work proposes the first formal treatment allowing the approximation of a flow using a limited number of paths with any desired accuracy.
@cite_9 @cite_21 @cite_23
2063029333 2151962283 1481933765
Aggregation of resources is a means to improve performance and efficiency in statistically shared systems in general, and communication networks in particular. One approach to this is traffic dispersion, which means that the traffic from a source is spread over multiple paths and transmitted in parallel through the network. Traffic dispersion may help in utilizing network resources to their full potential, while providing quality-of-service guarantees. It is a topic gaining interest, and much work has been done in the field. The results are, however, difficult to find, since the technique appears under many different labels. This article is therefore an attempt to gather and report on the work done on traffic dispersion in communication networks. It looks at a specific instance of this general method. The processes are communication processes, and the resource is the link capacity in a packet switched network. Traditional multimedia streaming techniques usually assume single-path (unicast) data delivery. But when the aggregate traffic between 2 nodes exceeds the bandwidth capacity of single link path, a feasible solution is to appropriately disperse the aggregate traffic over multiple paths between these 2 nodes. In this paper we propose a set of multi-path streaming models for MPEG video traffic transmission. In addition to the attributes (such as load balancing and security) inherited from conventional data dispersion models, the proposed multimedia dispersion models are designed to achieve high error-free frame rate based on the characteristics of MPEG video structure. Our simulation results show that significant quality improvement can be observed if the proposed streaming models are employed appropriately. Internet service provider faces a daunting challenge in provisioning network efficiently. We introduce a proactive multipath routing scheme that tries to route traffic according to its built-in properties. Based on mathematical analysis, our approach disperses incoming traffic flows onto multiple paths according to path qualities. Long-lived flows are detected and migrated to the shortest path if their QoS could be guaranteed there. Suggesting nondisjoint path set, four types of dispersion policies are analyzed, and flow classification policy which relates flow trigger with link state update period is investigated. Simulation experiments show that our approach outperforms traditional single path routing significantly.