Abstract: In this paper, a novel configuration is proposed for
the implementation of an almost all-optical switch architecture
called the scheduling switch, which when combined with appropriate
wait-for-reservation or tell-and-go connection and flowcontrol protocols provides lossless communication for traffic
that satisfies certain smoothness properties. An all-optical 2 2
exchange/bypass (E/B) switch based on the nonlinear operation
of a semiconductor optical amplifier (SOA) is considered as the
basic building block of the scheduling switch as opposed to active
SOA-based space switches that use injection current to switch
between ON and OFF states. The experimental demonstration of
the optically addressable 2 2 E/B, which is summarized for
10–Gb/s data packets as well as synchronous digital hierarchy
(SDH)/STM-64 data frames, ensures the feasibility of the proposed
configuration at high speeds, with low switching energy and low
losses during the scheduling process. In addition, it provides
reduction of the number of required components for the construction
of the scheduling switch, which is calculated to be 50% in the
number of active elements and 33% in the fiber length.
Abstract: Two important performance parameters of distributed, rate-based flowcontrol algorithms are their locality and convergence complexity. The former is characterized by the amount of global knowledge that is available to their scheduling mechanisms, while the latter is defined as the number of update operations performed on rates of individual sessions until max-min fairness is reached. Optimistic algorithms allow any session to intermediately receive a rate larger than its max-min fair rate; bottleneck algorithms finalize the rate of a session only if it is restricted by a certain, highly congested link of the network. In this work, we present a comprehensive collection of lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, bottleneck, rate-based flowcontrol algorithms. Say that an algorithm is oblivious if its scheduling mechanism uses no information of either the session rates or the network topology. We present a novel, combinatorial construction of a capacitated network, which we use to establish a fundamental lower bound of dn 4 + n 2 on the convergence complexity of any oblivious algorithm, where n is the number of sessions laid out on a network, and d, the session dependency, is a measure of topological dependencies among sessions. Moreover, we devise a novel simulation proof to establish that, perhaps surprisingly, the lower bound of dn 4 + n 2 on convergence complexity still holds for any partially oblivious algorithm, in which the scheduling mechanism is allowed to use information about session rates, but is otherwise unaware of network topology. On the positive side, we prove that the lower bounds for oblivious and partially oblivious algorithms are both tight. We do so by presenting optimal oblivious algorithms, which converge after dn 2 + n 2 update operations are performed in the worst case. To complete the picture, we show that linear convergence complexity can indeed be achieved if information about both session rates and network topology is available to schedulers. We present a counterexample, nonoblivious algorithm, which converges within an optimal number of n update operations. Our results imply a surprising convergence complexity collapse of oblivious and partially oblivious algorithms, and a convergence complexity separation between (partially) oblivious and nonoblivious algorithms for optimistic, bottleneck rate-based flowcontrol.
Abstract: Flowcontrol is the main technique currently used to prevent some of the ordered traffic from entering a communication network, and to avoid congestion. A challenging aspect of flowcontrol is how to treat all sessions "fairly " when it is necessary to turn traffic away from the network. In this work, we show how to extend the theory of max-min fair flowcontrol to the case where priorities are assigned to different varieties of traffic, which are sensitive to traffic levels. We examine priorities expressible in the general form of increasing functions of rates, considering yet in combination the more elaborative case with unescapable upper and lower bounds on rates of traffic sessions. We offer optimal, priority bottleneck algorithms, which iteratively adjust the session rates in order to meet a new condition of max-min fairness under priorities and rate bounds. In our setting, which is realistic for today's technology of guaranteed quality of service, traffic may be turned away not only to avoid congestion, but also to respect particular minimum requirements on bandwidth. Moreover, we establish lower bounds on the competitiveness of network-oblivious schemes compared to optimal schemes with complete knowledge of network structure. Our theory extends significantly the classical theory of max-min fair flowcontrol [2]. Moreover, our results on rejected traffic are fundamentally different from those related to call control and bandwidth allocation, since not only do we wish to optimize the number and rates of accepted sessions, but we also require priority fairness.
Abstract: Let M be a single s-t network of parallel links with load dependent latency functions shared by an infinite number of selfish users. This may yield a Nash equilibrium with unbounded Coordination Ratio [E. Koutsoupias, C. Papadimitriou, Worst-case equilibria, in: 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS, vol. 1563, 1999, pp. 404-413; T. Roughgarden, E. Tardos, How bad is selfish routing? in: 41st IEEE Annual Symposium of Foundations of Computer Science, FOCS, 2000, pp. 93-102]. A Leader can decrease the coordination ratio by assigning flow {\'a}r on M, and then all Followers assign selfishly the (1-{\'a})r remaining flow. This is a Stackelberg Scheduling Instance(M,r,{\'a}),0≤{\'a}≤1. It was shown [T. Roughgarden, Stackelberg scheduling strategies, in: 33rd Annual Symposium on Theory of Computing, STOC, 2001, pp. 104-113] that it is weakly NP-hard to compute the optimal Leader's strategy. For any such network M we efficiently compute the minimum portion @b"M of flow r>0 needed by a Leader to induce M's optimum cost, as well as her optimal strategy. This shows that the optimal Leader's strategy on instances (M,r,@a>=@b"M) is in P. Unfortunately, Stackelberg routing in more general nets can be arbitrarily hard. Roughgarden presented a modification of Braess's Paradox graph, such that no strategy controlling {\'a}r flow can induce ≤1/{\'a} times the optimum cost. However, we show that our main result also applies to any s-t net G. We take care of the Braess's graph explicitly, as a convincing example. Finally, we extend this result to k commodities. A conference version of this paper has appeared in [A. Kaporis, P. Spirakis, The price of optimum in stackelberg games on arbitrary single commodity networks and latency functions, in: 18th annual ACM symposium on Parallelism in Algorithms and Architectures, SPAA, 2006, pp. 19-28]. Some preliminary results have also appeared as technical report in [A.C. Kaporis, E. Politopoulou, P.G. Spirakis, The price of optimum in stackelberg games, in: Electronic Colloquium on Computational Complexity, ECCC, (056), 2005].