=================================================== From amsaha@cs.rice.edu Tue Apr 6 17:11:47 2004 =================================================== TITLE: "A Load-Balanced Switch with an Arbitrary Number of Linecards" Normally internet switches consist of multiple line cards and packets arrive at each of them and then the packet are buffered in queues and then sent out through the line cards. The incoming packets are buffered uniformly across all Qs. However, for this switch to work all the linecards have to be present which is not always true because some linecards may be missing and some might need to be replaced, etc. Hence the switch needs to be reconfigured to handle such a scenario since the number of Qs keep on varying and the packets must be uniformly distributed amongst them. In a previous paper the authors suggest an architecture which can handle such dynamic reconfiguration. In this paper the authors explain the algorithm that achieves this dynamic reconfiguration. This algorithm runs in polynomial time and will always give a valid configuration. The algorithm is based on Ford-Fulkerson max-flow algo and edge coloring in bipartite graphs. The weakest part of the paper is the evaluation. The authors themselves say that the algorithm is very slow and suggest precalculating the results and then look it up when the results are actually needed. However, if that is the case then their algorithm has nothing special and any slow algorithm can be used to compute the results offline and then use a table lookup to get the results. Also, as accepted by the authors an ASIC based implementation of this algorithm seems unlikely. However, the paper completes the authors previous work in which they propose an architecture and in this paper they complement that work with an algorithm which makes the architecture work. - Amit -------------------------------- http://www.cs.rice.edu/~amsaha -------------------------------- =================================================== From gulati@is.rice.edu Tue Apr 6 19:29:40 2004 =================================================== A Load-Balanced Switch with an Arbitrary number of Linecards This paper uses a load balanced switch, first described in a previous paper by Chang et al. and extended by authors to achieve 100% throughput for any traffic pattern. In a static configuration when all the Linecards are present, its easy to configure MEM switches and design a Linecard to Linecard schedule for each frame (consisting of N time slots, where N is total number of linecards) . The paper targets the problem of missing linecards, or the reconfiguration that needs to be done whenever a linecard is added or removed. The authors define valid schedules of 3 types: G-G (group to group), L-G(linecards to group) and L-L(linecard to linecard). They claim that each of the schedules can be obtained from any other one. Finally they give an algorithm to find G-G schedule and obtain L-G and L-L schedule from it. The prototype implementation seems to run in polynomial time but its not fast enough for real time calculations. One surprising thing is that authors show that the algorithm runs in polynomial time but they didn't compute the exact bound in terms of input. It might be interesting to see if its O(n^2) or O(n^12). I think that algorithms presented are a good contribution but paper should have mentioned something about their practical use other than just saying that some configuration changes can be precomputed. It may be a good theoretical result which is difficult to use in practice. -Ajay =================================================== From muhammed@ece.rice.edu Thu Apr 8 02:01:25 2004 =================================================== This paper describes algorithms to configure the functioning of a high speed multistage optical packet switch. The configuration of such a packet switch is non-trivial only if the number of incoming ports is arbitrary with respect to the number of stage 2 MEMS blocks. This is the problem the paper addresses: How to compute the connection state of the multistage switch over a frame of N slots where N is the number of incoming line cards subject to certain constraints. The paper proves a lower bound result on the minimum number of MEMS switches and comes up with a polynomial time algorithm to compute valid schedules which work with the minimum the number of MEMS. The paper does not say what a group of linecards physically corresponds to...what do they have in common to be grouped so in the first place? The paper tries to minimize the number of MEMS. Why does one need to minimize them (they are small passive optical devices)? It is not clear what the MEMS constraint is. The paper talks about MEMS constraints on groups and on linecards without clearly saying how they differ. The notation is not adequately explained and is confusing. It is not proper to write an inequality between two matrices (step 3 of iterative algorithm for calculating a valid G-G schedule). =================================================== From takhoa@rice.edu Thu Apr 8 12:17:16 2004 =================================================== This paper provides a nice little mathematical document on how to derive scheduling of linecard-to-linecard from a group-to-group scheduling. Given an arbitrary set of groups and their linecards, the paper can calculate the schedule to allow uniform traffic distribution from linecard to linecard. This is very helpful since the user of the switch can freely add or remove linecards as long as the number of MEMS switches are L+G-1, or the switch can be configured to automatically rebalance its load if a linecard fails. As the authors point out, however, it would have been better if the algorithm can be computed realtime so that the switch does not have to be taken offline, or does not suffer packet loss. (So, does this mean some data (packets that are sent to the failed linecard) will be lost during the 50s of computation?) I am not very familar with switch scheduling research, but it seems like these uniform scheduling issues are some of the fundamental issues and should have already been solved a long time ago. If existing ways of rebalancing switch scheduling already exist with the same computation time and complexity then this paper is not worth applauding. However, if existing methods to determine switch scheduling requires more rigid constraints, and more computational intensive, then this paper does offer a new and simple solution to solve the problem. =================================================== From ahae@cs.rice.edu Thu Apr 8 12:55:05 2004 =================================================== The authors address robustness issues in a specific switch architecture, the load-balanced switch. This architecture is based on a passive mesh of switching components, which is only guaranteed to work when all the components are present and working. If a component is removed or fails, traffic needs to be re-routed. This is essentially a scheduling problem, for which the authors present a solution. The solution is convincing and well supported with formal proofs. It is also highly relevant to future high-performance switch architectures. However, the overhead of the algorithm exceeds the acceptable level by several orders of magnitude, so in a practical system, its results would have to be precomputed. Since this is clearly a weakness, the paper could benefit significantly from a complexity analysis.