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.
In @cite_1 a rate achieving scheme for packet switching at the switch level is presented. Their scheme is based on convergence to the optimal multicommodity flow using delayed decision for queued packets. Their results somewhat resemble our @math algorithm. However, their scheme depends on the existence of an average packet size, whereas our scheme addresses the full routing-scheduling question for any size distribution and any (adversarial) arrival schedule. In @cite_11 queuing analysis of several optical transport network architectures is conducted, and it is shown that under some conditions on the arrival process, some of the schemes can achieve the maximum network rate. As the previous one, this paper does not discuss the full routing-scheduling question discussed here and does not handle unbounded job sizes. Another difference is that our paper provides an algorithm, @math discussed below, guaranteeing the ending time of a job at the time of arrival, which, as far as we know is the first such algorithm.
@cite_1 @cite_11
2125953414 2164101046
Input Queued (IQ) switches have been very well studied in the recent past. The main problem in the IQ switches concerns scheduling. The main focus of the research has been the fixed length packet-known as cells-case. The scheduling decision becomes relatively easier for cells compared to the variable length packet case as scheduling needs to be done at a regular interval of fixed cell time. In real traffic dividing the variable packets into cells at the input side of the switch and then reassembling these cells into packets on the output side achieve it. The disadvantages of this cell-based approach are the following: (a) bandwidth is lost as division of a packet may generate incomplete cells, and (b) additional overhead of segmentation and reassembling cells into packets. This motivates the packet scheduling: scheduling is done in units of arriving packet sizes and in nonpreemptive fashion. In M.A. (2001) the problem of packet scheduling was first considered. They show that under any admissible Bernoulli i.i.d. arrival traffic a simple modification of maximum weight matching (MWM) algorithm is stable, similar to cell-based MWM. In this paper, we study the stability properties of packet based scheduling algorithm for general admissible arrival traffic pattern. We first show that the result of extends to general regenerative traffic model instead of just admissible traffic, that is, packet based MWM is stable. Next we show that there exists an admissible traffic pattern under which any work-conserving (that is maximal type) scheduling algorithm will be unstable. This suggests that the packet based MWM will be unstable too. To overcome this difficulty we propose a new class of "waiting" algorithms. We show that "waiting"-MWM algorithm is stable for any admissible traffic using fluid limit technique. We compare three optical transport network architectures—optical packet switching (OPS), optical flow switching (OFS), and optical burst switching (OBS)—based on a notion of network capacity as the set of exogenous traffic rates that can be stably supported by a network under its operational constraints. We characterize the capacity regions of the transport architectures, and show that the capacity region of OPS dominates that of OFS, and that the capacity region of OFS dominates that of OBS. We then apply these results to two important network topologies—bidirectional rings and Moore graphs—under uniform all-to-all traffic. Motivated by the incommensurate complexity cost of comparable transport architectures, we also investigate the dependence of the relative capacity performance of the switching architectures on the number of switch ports per fiber at core nodes.