We consider fair allocation of sessions at the outputs of optical cross-connects employing wavelength division multiplexing (WDM). Each session consists of traffic on one or more wavelengths (channels). We identify lexicographic fairness as the most appropriate fairness criterion that is relevant to this setting. Achieving a fair lexicographic solution, commonly referred to as lexicographic optimality (LEX), is trivial and polynomial-time computable when any incoming wavelength can be converted to any outgoing wavelength (full conversion). This is not apparent in the practical and realistic case of limited conversion. We prove that LEX is also polynomial-time computable for the limited conversion case by reducing the problem to a min-cost max-flow optimization objective in network flows. We also motivate, formulate and solve a stronger variant of lexicographic optimality that we refer to as worst-case fair lexicographic optimal (W-LEX). Although our effective setting is an optimization problem in bipartite graphs (the request graph is bipartite), the network-flow based algorithms are applicable to unit capacity graphs in general. Further, we provide fast polynomial-time algorithms that furnish solutions for LEX and the W-LEX optimality problems for arbitrary bipartite graphs (i.e. arbitrary wavelength-conversion rules) and are computationally less expensive than network-flow methods. Finally we report simulation results to validate our findings.

A good crossbar switch scheduler should be able to sustain full bandwidth and maintain fairness among competing flows. A pure input-queued (IQ) non-buffered switch requires an impractically complex scheduler to achieve this goal. Common solutions are to use crossbar speedup and/or buffered crossbar. In this paper, we explore this issue in a buffered crossbar without speedup. We first discuss the conflict between fairness and throughput and the fairness criteria in crossbar switch scheduling, and justify that a desirable scheduler should sustain full bandwidth for admissible traffic and ensure max-min fairness for non-admissible traffic. Then we describe anadaptive max-min fair scheduling(AMFS) algorithm and show by analysis and simulation that it can provide both 100% throughput and max-min fairness. Finally we briefly discuss the hardware implementation of the AMFS algorithm.

We address the quality of service (QoS) provisioning problem in an aggregated multi-server environment. The input packet stream traffic to the system is categorized at a macro level into a few "flow-classes" that require service differentiation; each class is further subdivided into "flows" at the micro-level. Flows can be serviced by any server: however; the service rate is a function of the class and the particular server. Given such an environment, we have a multi-criteria optimization objective: (i) provide differentiated service to flows, (ii) achieve load balancing of the servers and (iii) maximize their throughput (amount of bytes serviced). We present an on-line fluid-based approximation scheme to schedule packets. Modeling the accumulated traffic in a class as fluid we use linear programming to first determine the optimal fractions that should be directed to different servers while ensuring fairness and high server throughput. We propose a packet scheduling strategy for the multi-server framework (by extending a well-known fair round-robin algorithm for single link systems) that effectively incorporates the optimal service fractions determined in the previous step. We validate the proposed algorithm with extensive simulations. The results show that the algorithm imparts high throughput with good service differentiation. We also evaluate reordering of packet requests within flow streams by presenting relevant metrics that quantify reordering

A smooth scheduling with guaranteed rate service and bounded packet delay is a desired objective of any switch scheduling algorithm. We present a scheme that generates low jitter schedules with low computational complexity. The scheduler uses an integer decomposition of the rate-matrix, similar to the Birkhoff-von Neumann decomposition. It improves the delay and jitter performance of the smooth scheduler as described in Keslassy et al. with an increase in the number of permutation matrices that the switch fabric has to cycle through. This increase is shown to be a constant for all practical purposes. Two algorithms are presented that have time complexity O(n/sup 2/ + log n) and space complexity O(n/sup 2/) and O(n) respectively. An existing scheduling algorithm for single links, smoothed round robin, is employed for scheduling the permutation matrices. This algorithm has a computational complexity overhead of O(1) and ensures smooth scheduling.

Provisioning quality of service (QoS) across an aggregate of transmission entities (e.g., link aggregation) or processing elements (e.g. network processors) is a challenging problem. The difficulty lies in simultaneously satisfying fairness to flows (with different bandwidth requirements) and ensuring minimized intra-flow reordering. This problem is crucial to many applications (that utilize parallel communication or processing paths) like multi-path load distribution, multi-path storage I/O, web service, data processing by network processors in the datapath of routers, transcoding multimedia flow traffic content over the Internet to name a few. We present two algorithms for multi-link systems that aim at reducing undesired reordering, ensure fair sharing of flows and optimal utilization of the links. Our algorithms are based on a new approach of dynamically partitioning flows among links. We perform simulations on real Internet traces to validate our algorithmic approach.

The traditional framework for discrete-event control is extended to include the case of control with active events, in which both the user and the environment have events that they can trigger. A variety of liveness and safety specifications can be considered within this extended framework. A synthesis algorithm of minimally restrictive controllers is outlined.

An optimal control theory for designing a controller, that selects unique control actions is developed for controlling discrete event systems (DESs). Prior work on supervisor synthesis problems studied the design of supervisors for satisfying qualitative specifications within the framework of the DESs. In this paper we define and investigate the synthesis of an optimal controller in the sense that, regardless the state of the plant, the worst cost of all surviving paths from that state to the set of frontier marked states is minimized. Our work differs from prior works on optimal control of DESs in that the controller selects a unique controllable event to be executed per state, rather than a set of admissible controllable events. An efficient algorithm is provided to solve this problem under complete observation.