Communication Networks Laboratory (CNL) - Research
The Communication Networks Laboratory (CNL), led by Professor Varvarigos at the University of Patras, is developing solutions to some of the most challenging problems in networking and optical communications. The Communication Networks Lab is entirely devoted to research activities, and it includes 3 PhD Researchers and 9 Engineers-PhD Students. The group has strong cooperation with other research centres, universities, industrial partners and important scientists worldwide.
Our current focus is on the next generation of optical network switches, for both circuit- and packet-switched optical networks, as well as novel protocols that will provide efficient communication at the projected multigigabit speeds. Other problems in which we have been working include QoS, grid computing, communication aspects of distributed computation, interconnection networks, VLSI layouts, mobile networks, and fault tolerance.
Implementing and evaluating scheduling policies in gLite middleware
Data Consolidation in Grid Networks
Grid Job Modelling
Grid QoS Scheduling
Multicost QoS Routing in Wireless Networks
Impairment-Aware Routing and Wavelength Assignment Algorithms
OpenRSM: a lightweight integrated open source remote management solution
All-Optical Packet Switching
Design and Analysis of Gigabit Network Protocols
Design of timed and in-advance reservation protocols
Design of tell-and-go protocols
Scalable communication protocols for high-speed networks
Performance of all-optical switch architectures when the burstiness constraints are not satisfied/ Interoperability issues between packet and circuit switching
Flow Control Protocols
Quality of Servise Routing (QoS) in WDM Networks
Wavelength Conversion in WDM networks
QoS Resource Management in GRIDS
Switching formats for interconnection and general networks
Graph Theory and Network topologies
Routing in Interconnection Networks
Broadcasting and Multicasting
Mobile and Packet Radio Networks
VLSI layouts of interconnection networks
Optimal Fault Tolerant Communication and Computing
Threshold Circuits
Implementing and evaluating scheduling policies in gLite middleware
A Grid middleware is a software package providing a number of fundamental Grid services, such as information services, resource discovery and monitoring, job submission and management, brokering, data management and resource management. A number of production Grid middlewares exist today, such as gLite, Globus Toolkit 4 (GT4), UNICORE, etc. The gLite is the result of the collaborative efforts of different academic and industrial research centers as part of the Enabling Grids for E-sciencE (EGEE) project .The gLite's development is performed by a close group of researchers and relatively little information exists on how to extend or change its functionality Furthermore, since gLite is a production Grid middleware, it consists of a large number of components, whose installation and configuration can be quite difficult.
We implemented and incorporated in gLite different task scheduling algorithms, such as the Simple Fair Execution Time Estimation (abbreviated SFETE) algorithm. SFETE assigns a job to the resource that minimizes what we call its fair execution time estimation. The fair execution time of a job at a resource is obtained assuming that the job gets a fair share of the resource?s computational power. Even though space-shared scheduling is used in the actual system, the estimates of the fair execution times are found assuming time-sharing is used. gLite implements two scheduling algorithms, which we refer to as Max Rank and Fuzzy Rank. Our results show that SFETE performs better than the other two scheduling algorithms, by achieving smaller job execution delay and better distribution of the jobs to the available computational resources.
Data Consolidation in Grid Networks
Data Consolidation (DC) arises when a task requests concurrently multiple pieces of data, possibly scattered throughout the grid network that have to be present at a selected site before task?s execution starts. In such a case, the scheduler and the data manager must select (i) the data replicas to be used, (ii) the site where these data will be gathered for the task to be executed, and (iii) the routing paths to be followed; assuming that the selected datasets are transferred concurrently to the execution site. The algorithms or policies for selecting the data replicas, the data consolidating site and the corresponding paths comprise a Data Consolidation scheme. We are interested in DC schemes of polynomial complexity that attempt to estimate the cost of the concurrent data transfers, to avoid congestion that may appear due to these transfers and to provide fault tolerance.
The job inter-arrival times, the job execution times, and the times jobs spent at different phases of processing in Grids are unknown and are better modeled probabilistically. Finding good probabilistic models for the job submission process, the job delay components, and the job characteristics gives us important insight into the operation of Grid systems and can be used by the developers and the research community in several ways. By observing the system behavior under different values of the parameters involved the developers can evaluate the performance, study the way it depends on the choice of different parameters, and possible identify problems and propose new methods to improve and optimize the employed middleware. Given the high cost involved in setting up actual hardware implementations, simulations are a viable alternative. A necessary prerequisite to obtain useful results is an adequate model of the traffic (i.e. job arrival process) and the times the job spend at different states. Probabilistic models can be used to facilitate the dimensioning of Grid systems and the prediction of their performance under different scenarios.
We have conducted a thorough analysis of the job arrival process in the EGEE infrastructure and of the time durations a job spends at different states in the EGEE environment. We observed that the job inter-arrival times at the Grid level can be adequately modelled by a rounded exponential distribution, while the total job delay (from the time it is generated until the time it completes execution) is dominated by the computing element's register and queuing times and the worker node?s execution times. Further, we evaluated the efficiency of the EGEE environment by comparing the job total delay performance with that of a hypothetical ideal super-cluster and conclude that we would obtain similar performance if we submit the same workload to a super-cluster of size equal to 34% of the total average number of CPUs participating in the EGEE infrastructure. We also analyzed the job inter-arrival times, the CE's queuing times, the WN's execution times, and the data sizes exchanged at the kallisto.hellasgrid.gr cluster, which is a node in the EGEE infrastructure. In contrast to the Grid level, we found that at the cluster level the job arrival process exhibits self-similarity/long-range dependence. We have also proposed simple and intuitive models for the job arrival process and the execution times at the cluster level.
Today's Grids provide only a best effort service to the users and their tasks. This is inadequate if the Grid Network is to be used for real world commercial applications and time-critical scientific computations. Best-effort service also limits the economic importance of Grids, since users will be reluctant to pay, directly or indirectly (e.g., by contributing resources to the Grid), for the service they receive, if they are not given performance guarantees. As a result, there is a growing need for Grid scheduling and resource management algorithms to be able to provide QoS to the users. Under these thoughts we believe that future Grids will serve two types of user. Some users will be relatively insensitive to the performance they receive from the Grid and will be happy to accept whatever performance they are given. Even though these Best Effort (BE) users do not require performance bounds, it is desirable for the Grid Network to allocate resources to them in a fair way. In addition to BE users, we also expect the Grid Network to serve users that do require a guaranteed QoS, namely Guaranteed Service (GS) users.
As part of the research performed in our lab for Grids, we have proposed and implemented a QoS framework for handling GS and BE users. For GS users, the framework guarantees an upper bound on the delay of the submitted tasks. A task's delay is defined as the time between the task's creation and the time the results of its execution return to the user. The delay guarantees imply that a GS user can choose a resource to execute a task before its deadline expires, with absolute certainty. In order to achieve this goal, the GS users are leaky-bucket constrained, so as to follow a self constrained task generation pattern, which is agreed separately with each resource during a registration phase. For BE users, the proposed framework describes a fair scheduling procedure that provides fairness among users instead of fairness among tasks. We validated experimentally the proposed QoS framework for Grids, verifying that it satisfies the delay guarantees promised to users and provides fairness among BE users, while simultaneously improving performance in terms of deadlines missed and resource utilization.
Though this idea has been originally proposed for Grid Networks its actual application may be cumbersome, since it requires the reservation and adaptation of the resources? CPU capacity assigned to each user. We believe that the dynamicity and flexibility of a virtualized infrastructure as the one envisioned through Clouds provides the ground for actually implementing this framework and offering QoS to its users. Also, the requirement of the proposed framework for the estimation of the users average long term needs is in accordance with service oriented character (e.g., sell & buy) of such an infrastructure.
Multicost QoS Routing in Wireless Networks
Advances in battery lifetime during recent years have not kept in pace with the significant decline in computation and communication costs in wireless mesh networks. Thus, considering the lack of any fixed infrastructure and the requirements for long operating lifetime, energy is a crucial resource limiting the performance and range of applicability of such networks. As a result, the design of protocols that make best use of the nodes? energy resources has been a very active research field. Also, the cooperative nature of mesh networks, makes multicasting and broadcasting two of the most frequently performed primitive communication tasks. Being able to perform these communication tasks in an energy-efficient manner is, therefore, an important priority for such networks.
Optimal Total and Residual Energy Multicost Multicast (abbreviated OTREMM) is a an optimal energy efficient multicasting algorithm for wireless mesh networks consisting of nodes with preconfigured levels of transmission power. OTREMM is optimal, in the sense that it can optimize any desired function of the total power consumed by the multicasting task and the minimum of the current residual energies of the nodes, provided that the optimization function is monotonic in each of these parameters. This algorithm takes into account these two energy related parameters in selecting the optimal sequence of nodes for performing the multicast, but it has non-polynomial complexity. The Near-Optimal Total and Residual Energy Multicost Multicast (abbreviated NOTREMM) algorithm is a relaxation of the optimal algorithm, that produces a near-optimal solution to the energy-efficient multicasting problem in polynomial time. These two algorithms have been compared against established solutions for energy-aware multicasting and broadcasting. The performance results obtained showed that the proposed algorithms outperform previous schemes with respect to both energy consumption and network lifetime. Moreover, it is shown that the near optimal multicost algorithm obtains most of the performance benefits of the optimal multicost algorithm at a smaller computational overhead.
Impairment-Aware Routing and Wavelength Assignment Algorithms
Since lightpaths are the basic switched entities of a WDM network architecture, their effective establishment is crucial. It is thus important to propose efficient algorithms to select the routes to be followed by the requested connections and to assign wavelengths on each of the links along these routes, among the possible choices, so as to optimize a certain performance metric. This is known as the routing and wavelength assignment (abbreviated RWA) problem.
Figure presents a conceptual view of the two phases that a wavelength routed WDM network undergoes: (a) the planning phase and (b) the operational phase. In the planning phase the network is designed and configured based on the traffic it is predicted to handle during its normal operation or based on an a priori given set of connection requests. The traffic that is to be handled is described through a traffic matrix that specifies the number of connections to be established between each source-destination pair. In contast, in the operational phase new lightpaths requests arrive and terminate dynamically in thenetwork, and they are handled, one be one, taking into account the already established lightpaths.
Thus, given that the planning and the operational phases of a WDM network differ in their characteristics and objectives, the RWA problem is usually considered under two alternative traffic models: i) Offline (or static ) and ii) Online (or dynamic ) lightpath establishment. Offline (or static ) lightpath establishment addresses the case where the set of connections is known in advance, given in the form of a traffic matrix.
The majority of RWA algorithms proposed in the literature assume an ideal physical layer where signal transmission is error free. However, in transparent or translucent WDM networks, where the signal of the lightpaths remains in the optical domain for more than one links, signal transmission is significantly affected by physical limitations of fibers and optical components, reducing the quality of transmission (QoT). For the rest of this deliverable we will refer to such phenomena as physical layer impairments (PLI). Some of the more significant PLIs include ASE, CD, PMD, FC, SPM, XPM, FWM, etc. All these PLIs may degrade the received signal quality to the extent that the bit-error rate (BER) at the receiver may be so high that signal detection may be infeasible for some lightpaths.
Our work in recent years have focus on providing online and offline impairment-aware RWA algorithms, resulting in a complete tool for the planning and operation of optical networks.
OpenRSM: a lightweight integrated open source remote management solution
The management of the corporate information technology (IT) environment is rapidly increasing in complexity as server logic architecture becomes more distributed and the number of entities deployed increases, forcing enterprises to resort to thick, complex and expensive high-end integrated systems and network management solutions. Investing in such systems can be inefficient for small and medium corporations, since the vast majority of management tasks performed are routine tasks, while personnel specialization requirements and costs are high. At the same time, the open source community has not yet produced a reliable and complete system and network management solution. Even though there are open source initiatives specializing in specific fields of remote management, such as network management, there has been no integrated open source solution yet.
The Open Source Remote Systems Management (OpenRSM) platform is an integrated remote management system created by our group integrating individual specialized open source management initiatives and signifi cantly augmenting them to support additional functionality, so that a complete lightweight system and network management solution is produced. The system implemented facilitates daily management by providing an efficient, simple and adaptable environment for the majority of management operations.
More information here
Optical systems have rapidly expanded in capacity from early systems at 55Mbps in 1978 to present commercial systems at 10Gbps per wavelength (with commercial systems at 40Gbps per wavelength with up to hundreds of wavelengths also announced), a quadrupling of capacity every four years. The functionality and the efficiency of the switches connecting the links is however what really transforms these raw bit rates into effective bandwidth.
Switching in core optical telecommunications networks is currently performed using high-speed electronic or all-optical circuit switches. Switching with high-speed electronics requires optical-to-electronic (O/E) conversion of the data stream, making the switch a potential bottleneck of the network: any effort for electronics to approach the optical speeds has already reached its practical limits. Circuit switching on the other hand, is known to be inefficient for bursty traffic, involves a pre-transmission delay for call setup, and requires the aggregation of microflows into circuits, meaning that fine granularity and the control over individual microflows and their QoS are lost.
These limitations can be overcome by means of all-optical packet switching, where data packets remain in the optical domain avoiding the electronic bottleneck, and offering bandwidth use on demand, flexibility, and granularity. Optical packet switches proposed to date are either TDM circuit switches or deflection switches; the former do not meet the requirements for on-demand use of bandwidth for bursty traffic without excessive packet losses, while the latter do not preserve the order of packets, making resequencing a hard problem at the destination, they are inconsistent with virtual circuit switching, cannot support QoS, and require a routing algorithm to handle each data packet, making processing a potential bottleneck.
In the area of switching for all-optical networks, our group has been evaluating novel switching architectures for all-optical gigabit networks, such as the
- Scheduling Switch
- Packing Switch and
- l-Scheduler Architecture
Previous researchers have proposed a number of optical packet switch architectures. None of them however can guarantee lossless communication and they will all try to use delay lines to emulate buffering. Since internet traffic is inherently bursty, such architectures will not succeed in providing low loss probability. Our approach is that we should aim for zero loss probability. To achieve this, we have examined new optical packet switch architectures which when combined with appropriate high layer flow control protocols can guarantee lossless communication.
More specifically, the main attributes of these architectures that differentiate them from previous designs are the following:
- The proposed switch architectures guarantee loss-less communication, for sessions that obey a specified burstiness property or that can tolerate the delay induced when transforming them into smooth sessions through the use of input flow control. This burstiness property is easily enforced at the source and is afterwards maintained with no additional effort by the switch design at the intermediate links of the path. The burstiness parameter of the traffic that may be handled by the switch is one of its design parameters and may be chosen at will. Finally, when combined with appropriate connection establishment protocols, the switch can provide lossless communication for both wait-for-reservation and for tell-and-go type of traffic.
- Low packet loss ratio for unconstrained traffic. The probability of losing packets at the output is very low, even if traffic that does not satisfy any burstiness property; the packet loss probability drops as a very rapid exponential when the traffic arrival process is geometric; it is also drops exponentially uniformly for any choice of the statistics of the arrival process. This is a particularly strong property, since earlier switch designs showed low loss probabilities for specific models of the arrival process, but they did not show similar performance for real traffic, which is more bursty and self-similar than could be captured by these models.
- The proposed switches are true packet switches that take advantage of statistical multiplexing, in the sense that packets make on demand use of the outgoing capacity and their arrivals can be bursty. This is in contrast to TDM circuit switches that assume regular, periodic traffic, and fixed allocation of packet slots to circuits.
- The switches are consistent with label and virtual circuit switching and are suitable not only for optical packet switching but for optical circuit (TDM) switching as well.
- The proposed switches are non-blocking when used as packet (or as circuit) switches. A new virtual circuit will always be routed as long as there is available capacity at the outgoing link.
- The switches use batch processing of packet headers/labels in a frame. Instead of processing each packet individually and make routing and switching decisions per packet, batch processing permits the calculation of a contention free path inside the switch for all the packets during all frames of the incoming links. The processing times for the switch control are optimal in terms of operations per packet through the use of batch processing of all labels in a frame. This is an important feature that makes the processing feasible during the frame time and is also the reason that lossless communication is guaranteed.
- The proposed switches preserve the order of packets that use a given input-output pair, maintains thus frame integrity, and does not require re-sequencing at the destination. Other architectures that use recirculating loops or deflection routing do not guarantee packet arrival in the correct order.
- The proposed switches are modular, so that they can be easily expanded to handle more burstiness in the traffic (in a way similar to the way a conventional electronic switch is expanded by adding more buffer). The cost of the switch grows optimally (that is, logarithmically) with respect to the degree of burstiness allowed and with respect to the number of outputs. For example adding only 2 elementary switching elements per port for the Scheduling and the l-Scheduling switches, or one switching element per port for the Packing Switch, the switch can accommodate twice the burstiness.
- Finally the proposed switches accumulate all the advantages of a usual optical packet switch, which means transparency in the payload data type and bit rate. In the switch, time slots are switched, where a time slot can contain anything. The data rates switched may vary from a few Mbps to the full line rate.
Design and Analysis of Gigabit Network Protocols
In the area of the design of protocols for optical networks our group has been designing new routing, flow control, and connection establishment protocols for high-speed networks and examining the issues involved in implementing these protocols on the next generation of optical networks. These protocols are designed to overcome the problems imposed by multigigabit-per-second transmission speeds, and meet the technological constraints imposed by the switch design in such networks. The main objective of this work is to design protocols for a high-speed network that permit high (close to 100%) and efficient utilization of bandwidth, while guaranteeing lossless communication and low delay.
Design of timed and in-advance reservation protocols
Most of the protocols for connection establishment use a set-up phase to set the routing tables and reserve the required capacity before starting to transmit any data. This is inefficient, since during the set-up phase, the capacity allocated to a session at a node remains idle; this is because it is reserved immediately upon the arrival of the set-up packet at that node even though it is actually needed at least one round-trip delay later (the set-up packet has to travel from the node to the destination, an acknowledgement has to be sent back to the source and the first data packet of the session has to arrive at the intermediate node). Even with fast reservation the efficiency factor e that can be achieved by such protocols is at most
where X and 2tp are typical values of the session holding time and the roundtrip delay, respectively; for high-speed networks and/or short session (or burst) durations, this upper bound may be much smaller than 1. In our work we have investigated a series of connection establishment protocols, which rely on timed and on advance reservations of capacity, and on pipelining of the set-up and transmission phases. The unique feature of these protocols is that session durations are recorded, and each node keeps track of the utilization profile of each outgoing link, which describes the amount of residual capacity available on the link as a function of time. Capacity is only reserved starting at the time that it is actually needed and for duration equal to the holding time of the session. This translates into more efficient capacity utilization and a substantially lower blocking probability for new sessions than previous reservation protocols. These protocols also have the "reservation ahead'" feature that allows a node to calculate the time at which the requested capacity will be available and reserve it in advance, avoiding in this way the wasteful repetition of the call set-up phase. Burst switching (with reservations made in advance for each burst) can be thought of as a special case of such protocols.
Design of tell-and-go protocols
For sessions with very strict delay requirements, tell-and-go type of protocols, instead of wait-for-connection-establishment types of protocols have to be used. Deflection routing is the only tell-and-go type of protocol, proposed to date, that could work with optical packet switches has previously been proposed for both general data network and for multiprocessor parallel computers. An important disadvantage of existing ("datagram") deflection schemes (especially for high-speed data networks) is the need for packet resequencing at the destination. We have proposed a variation of deflection routing, where a set-up packet is sent to the destination, followed after a short offset delay by the data packets. This offset delay should be large enough to permit the processing of the set-up packet (that will establish the routing tables, announce at the intermediate nodes the average rate of the session, etc), without it being overpassed by the data packets. If the available capacity on a link of the preferred path is inadequate, the session (virtual circuit) may have to follow another path (session deflection), or, occasionally, to be split into two or more smaller sessions that are routed through different paths (session splitting). Deflection or splitting of sessions may happen only when the topology or link utilization information available at the source is outdated. Resequencing of packets, which is the major drawback of conventional packet-by-packet deflection schemes. If a session is split, a few blocks of data (each of which is ordered) will have to be resequenced, which is a considerably easier task than resequencing (millions of, in the case of high-speed networks) individual packets. The protocol is consistent with the switch architectures discussed earlier, and provides loss-free transmission, while avoiding the pre-transmission delay associated with wait-for-connection-establishment. Using new analytical techniques, we have analyzed the throughput, average path length, and other performance parameters of the protocol.
Scalable communication protocols for high-speed networks
We proposed the scalable networking scheme for the design of reservation and flow-control mechanisms, routing algorithms, and switching techniques that combine the advantages of low latency, high throughput, quality of service (QoS) guarantees, and loss-free communications, and provide effective tradeoffs between important performance metrics. The proposed scheme is particularly suitable for current and future high-speed networks, where the roundtrip delay is not negligible compared to packet transmission times.
An important difference between the scalable networking scheme and previous protocols is that the former allows heterogeneous nodes in the same network, and it leaves considerable freedom to the implementer to choose the parameters so as to achieve the desired operational and performance characteristics at an affordable price. The nodes that form the performance bottlenecks may implement advanced features of the scheme to improve performance, while the remaining nodes may implement the basic features only. With the advance of networking technologies, some advanced features may become less expensive to implement at all nodes in the future, and in the meantime, nodes with advanced features can co-exist with simpler nodes in a correct and efficient manner. This property greatly increases the flexibility and scalability of networks based on the scalable networking scheme.
Performance of all-optical switch architectures when the burstiness constraints are not satisfied/ Interoperability issues between packet and circuit switching
As mentioned earlier, provide lossless communication for traffic that has a certain burstiness property, which can be easily enforced at the network inputs. This task will examine the situation where the burstiness property is not enforced and calculate the loss rate in that case. For example, questions that will be investigated are the following. What will be the loss rate for a Scheduling switch designed to be lossless for (n,T1) traffic, when the arriving traffic has burstiness parameter T2 instead of T1? Or, what will be an upper bound on the loss rate when the arriving traffic is not known to satisfy any burstiness property at all? Our preliminary work indicates that in that case it is possible to obtain bounds on the loss rate that are independent of the particular packet arrival process (i.e., they hold uniformly for all arrival processes). Such bounds will be particularly useful for performance evaluation and for admission control in the important case where traffic characteristis are unknown and uncontrolled.
Another related issue concerns the interoperability between packet and circuit switching. Clearly, traffic from a circuit-switched network can be almost directly fed into a packet-switched network. However, in the case where packet traffic that has a certain smoothness property, like (n,T) smoothness, is fed into a circuit switched network, the (n,T) smooth traffic has to be converted to periodic. This procedure will involve some buffering and associated queueing delays, which has to be calculated.
There are three basic approaches that can be used in a communication network to control congestion. The first is admission control, by which we mean the decisions to admit or not admit data into the network. The second is routing, by which we mean the decisions on which outgoing link to use for each packet at each node. The third is flow control which, fundamentally, is the set of decisions about what data to accept at each node, and when and in what order to transmit it.
Two general flow control strategies being discussed for high-speed networks are open-loop control and closed-loop control. Open-loop control tries to prevent congestion build-up and is based on the notion of traffic contract. This is combined with strategies like the leaky-bucket scheme, which converts a bursty stream into a more regular pattern, and special queueing structures like stop-and-go queueing, which attempt to maintain certain smoothness properties throughout the network. Open-loop control may be insufficient, because the bandwidth requirements of many applications are not likely to be known at connection set up time. We have found upper bounds on the packet loss probability that depend only on the parameters of the leaky-bucket scheme and are independent of the particular characteristics of the external packet arrival processes.
These bounds can provide useful admission criteria to block sessions whose packet loss probability requirements cannot be met, or whose admission would adversely affect the QOS provided to the existing users. The bounds are particularly useful in the usual case where the source statistics are complicated or unknown.
Credit-based flow control is considered better-suited for bursty traffic than (open or closed loop) rate-based flow control, but it requires complex book-keeping at the nodes on a per session (i.e., per VC) basis. Multigigabit-per-second transmission speeds impose the constraint that a FIFO queueing discipline be used for all packets, including packets belonging to different sessions this is not consistent with the credit-based protocols proposed to date, which have generally assumed that per session queueing is feasible. Per session queueing, in addition to being difficult to implement at high speeds, also poses an excessive constraint on network equipment companies, who would like to have more flexibility when designing a system.
We have proposed a novel protocol that combines credit- and rate-based control, and works with both per session queueing and FIFO queueing. The challenge posed by FIFO queueing is, briefly, that control over the rate of an individual session is lost, since all the sessions sharing a common buffer are affected when the rate at which the buffer is served changes. Also, since the content of a buffer changes dynamically, the buffer composition becomes difficult to determine.
Quality of Servise Routing (QoS) in WDM Networks
Given a path in a network from a source to some destination, we have some knowledge about how to set-up a connection along the path and how to avoid packet loss and shape the traffic at the edges, but it is still unclear how to find a good path (at least in real time). Given a graph it is easy to find the best path based on a single criterion, like number of hops, total delay, or residual path capacity. In multiservice networks, however, the performance criterion is going to be a vector and not a scalar, and in different applications different components of that vector (QoS measures) matter. Finding a path that best satisfies multiple constraints is in general an NP-complete problem. In a recent work, we found an efficient (polynomial time) algorithm to generate non-dominating paths for a given source-destination pair (a path A dominates path B, if A is better than B with respect to all criteria) for the important case where we have one additive cost parameter (e.g., delay, hop count, reliability) and one restrictive cost parameter (e.g., bandwidth). We also investigated through simulations the role that the overall optimization function plays in the blocking performance of the network.
Wavelength Conversion in WDM networks
We are also working on the performance analysis of wavelength division multiplexing (WDM) networks employing limited-wavelength translation, where, due to technological constraints in designing practical optical transmitters, data on an incoming wavelength can be switched only on to a small subset of the available output wavelengths. A critical functionality for the scalability and the improved performance of multihop WDM networks is wavelength translation, that is, the ability of network nodes to switch data from an incoming wavelength to an outgoing wavelength. Two different classes of wavelength-routing nodes are important in this context: nodes with a full-wavelength translation capability, which translate an incoming wavelength to any outgoing wavelength and nodes with no-wavelength translation, which map each incoming wavelength to the same outgoing wavelength, the so-called wavelength continuity contsraint. Although full-wavelength translation is desirable because it substantially decreases call blocking probability, it is difficult to implement in practice due to technological limitations. Since all-optical converters are still being prototyped in laboratories and are likely to remain expensive, researchers have turned their attention to searching for suitable alternatives. It has been shown that there is no significant degradation in performance even when only a few (as opposed to all) of the network nodes have a full-wavelength translation capability. A natural question that arises is whether or not similar performance advantages can be obtained by using switches that have only a limited translation capability, where an incoming wavelength can be translated to only a small subset (as opposed to all) of the available outgoing wavelengths. Our recent results used probabilistic modeling to demonstrate that limited wavelength translation can achieve, even with greedy routing and wavelength assignment, can practically achieve most of the performance advantages of full-wavelength conversion at a fraction of the cost. In our current work, we are investigating specific algorithms for performing routing and wavelength assignment in networks that have limited wavelength translation. This problem is practically significant since all-optical wavelength translators demonstrated in laboratories to date are, in general, capable only of limited translation.
QoS Resource Management in GRIDS
The critical resources in Grid computing are the computational power, memory, communication bandwidth, and devices of all kinds that have to be shared. Clearly, it is these resources that will account for the largest fraction of its cost. In many cases, the time required for communication is more than the time spent by machines on computations. The success stories of the Grid are currently limited mainly to coarse grain computation. It is therefore important that the Grid resource manager takes communication delays into account when reserving resources and scheduling tasks to processors and further to consider the interdependence between communication tasks and computation tasks and to obtain the best performance through the use of pipelining techniques and clever scheduling.
The work of CNL is focusing on the design of new resource reservation schemes for providing Quality of Service in Grids. Supporting QoS is important for the success of Grid computing because without it users will be reluctant to pay for services or contribute to Grid resources. New abstractions and concepts should be introduced at the architecture level to allow users to make service level agreements (SLAs) with the Grid, and new capabilities are required to enable the enforcement of these SLAs. The objectives that we set for the grid resource manager is to assign computational resources to computational tasks in an efficient and fair way, while meeting the QoS requirements of the individual tasks.
In our work, we have designed a new protocol for resource reservation, called the TARR protocol (timed and advance reservation protocol) that estimates the communication delays and the task execution times in order to reserve (computational and communication) resources only for the exact time periods during which they are actually used by a task, and leave these resources free to be used by other tasks for the remaining of the time. Using such a scheme, the grid resource manager may decide when and where a certain task should be executed in order to make efficient use of the available resources of the underlying infrastructure. The resource manager maintains an utilization profile for each resource, which keeps track, as a function of time, of the future utilization of that resource. More specifically, the utilization profile of a computational resource records the (future) time intervals for which the resource has already been reserved for executing tasks. When a resource is released, the scheduler is informed in order to keep this information up to date. When a request for a task is sent to the Scheduler, the Scheduler allocates a resource to the task for a specific future time interval.
In calculating the start and end of that time interval the Scheduler takes into account the estimated communication delays and the workload of the task respectively. The idea is that when one task ends the data for the next task are already there and so that the new task can begin execution immediately. This maximizes the efficiency of the resources and the efficiency factor e can get very close to 1. The concept of the timed and in advance reservation is depicted in next Figure.
Figure: Resource reservations when advance and timed reservations are used. The main idea behind timed/advance resource reservation is that the resources are reserved only for the time during which they are actually used by a task.
Fairness in the use of grid resources is another important objective of the resource manager, because it is inherent in the notion of sharing with Grid computing. Meeting the QoS requirements of one user should not be achieved by sacrificing the QoS of another user. When the desired QoS cannot be provided, the degradation in the QoS provided should be graceful and fair to all users.
We are working on new QoS Scheduling algorithms based on the max-min fair share concept. These algorithms assign jobs to computation resources, by taking into account the QoS requirements of the users, and a weighting parameter that is determined by economic considerations. The weighting parameter permits us, in case of congestion, to treat more favourably (in a quantifiable way) users who are willing to pay more for the service they get or who have contributed more resources to the common Grid infrastructure, or who have to be treated preferentially for some other reason. When there is no congestion, each user gets the requested QoS, but when congestion arises (meaning that the desired QoS cannot be delivered to all users), the QoS that each user receives (as measured by the computational power he is given, or his completion time, or the amount of time by which he misses his deadline) is degraded in a way determined by his requested QoS and the weighting factor.
Switching formats for interconnection and general networks
We have proposed two new switching format for multiprocessor interconnection networks, called the Conflict-Sense Routing (CSR) protocol and Dynamic Scheduling Communication (DSC) protocol. These protocols are superior to packet switching in that they provide lossless communication, and do so with minimal buffer-space and without the need for an explicit ACK packet or an explicit flow-control mechanism, while ensuring packet arrival in correct order. We have analyzed their performance for popular topologies of interests and shown that their throughput are superior to that of both packet-switching and circuit-switching.
The CSR protocol, uses reservations to provide lossless communication, and can outperform packet switching when the reservation overhead is small; when, however, the data packets are short and/or the network diameter is large, it becomes inefficient. The DSC protocol, is a lossless communication protocol that can achieve high throughput even when the buffer space per node is small. It is a hybrid of circuit and packet switching, where a packet enters the network only after having reserved its route (links and buffer space). This resembles circuit switching. A packet, however, reserves a resource only for the slot (or slots) during which the resource will be used. This resembles packet switching, since the links and the buffer space are used on a demand basis. The data structures required to implement the protocol are simple. In the analysis carried out for butterfly type of networks, the DSC protocol was found to be more efficient than packet switching, circuit switching, and CSR switching, even when the reservation overhead is taken into account. Our plan for the future is to consider in more detail implementation issues of the DSC protocol when used for intra-switch communication.
We have also analyzed circuit-switching with input-queueing multiprocessor systems. Unlike previous works, our analysis provides closed-form solutions for the delay parameters of the system, such as average waiting time, average connection time, etc, and provides a simple graphical method to obtain the stability region and system throughput.
Graph Theory and Network topologies
We have proposed a new class of interconnection networks, called the Macro-Star networks, which form a subclass of Cayley graphs, and use the star graph as a basic building module. Some of the desirable characteristics of the new topology include: 1) small node degree [of the order of O(sqrt(logN/loglogN)), depending on the choice of some parameters], 2) small diameter [of the order of O(logN/loglogN)], 3) symmetry properties, 4) efficient emulation of popular topologies, 5) effective tradeoffs between cost and performance, 6) balanced traffic, and 7) suitability for VLSI implementation. Our analysis shows that the macro-star has a node degree considerably smaller than that of a star graph of the same size, and diameter that is asymptotically with a factor of 1.25 from a universal lower bound, given its node degree. Furthermore the new topology has: small node degree, small diameter, symmetry properties, and balanced traffic. It is amenable to an easy VLSI implementation, and enables efficient emulation of other popular topologies, while allowing an effective trade-off between cost and performance. The strategy used to derive Macro-Star networks can be generalized to a much wider class of Cayley graphs. For example, we have recently obtained networks that have even smaller node degree and a diameter to lower bound ratio equal to 1, asymptotically, while maintaining most of the desirable properties above. We have also proposed ways to partition the processors into modules (e.g., multiprocessor chips) in order to minimize delay (on-module link delays are considerably smaller than off-module delays), and increase the processor-memory bandwidth. Our aim is to to obtain efficient and design-feasible parallel architectures that are adaptive to the advances of processor, packaging, and interconnect technologies (e.g., using identical processors in memory (PIM) or computing in RAM modules). Our work on topologies also includes studying the structural properties of random graphs.
Routing in Interconnection Networks
Communication efficiency is the key to the broad success of massively parallel computation. One can see that by looking at the success stories of parallel computation, which are currently limited to applications that have small communication requirements, or use a small number of processors. In order to use massively parallel computation for a broader range of applications, efficient algorithms to execute the underlying interprocessor communications have to be developed.
The objective of this research is to create a library of algorithms to execute a number of generic communication tasks in several multiprocessor topologies. Communication tasks and traffic patterns that arise often in applications have been examined, with emphasis given on finding easily implementable communication algorithms to execute these tasks in optimal or near-optimal time. These algorithms can be called as communication primitives by the programmer or the compiler of a multiprocessor computer, in the same way that subroutines implementing standard functions are called from a library of functions in a conventional computer.
We are working on many aspects of routing in regular interconnection networks (such as hypercubes, tori, etc) both for static (prototype) routing problems and for dynamic (random) routing problems. This work has resulted in obtaining a rather complete library of communication algorithms for such problems, including algorithms for solving the multinode broadcast task, total exchange, partial exchange, single node scatter, and isotropic tasks in a variety of interconnection topologies.
All the tasks described above are static in the sense that there is some work to be performed once and for all. All the nodes know which task they execute, and (for the multinode tasks) they are synchronized to start at the same time; the only objective is to finish the job as fast as possible. Except for the static tasks, where conditions are rather favorable, one can envision situations where communication requests are not deterministic, but they are generated at random instants. We call such an environment dynamic. The execution of asynchronous computation algorithms is one such situation, but it is reasonable to expect that in many systems a dynamic, largely unpredictable communication environment may be the rule and not the exception.
Three dynamic problems on which we have focused, both because of their potentiality for increasing the general understanding of dynamic problems and for their importance in their own right are the dynamic broadcasting, the dynamic scattering and the dynamic 1-1 communication problems. In these dynamic problems broadcast, scatter, or 1-1 communication requests are generated at random instants at each node of a network. The performance criteria that we use are the mean number of communication requests that are executed per unit of time, and the mean delay to serve a request.
A communication task that arises often in data networks is the partial multinode broadcast (PMNB), where an (arbitrary) subset of the nodes has some information to broadcast to all other nodes of the network. In the dynamic version of the PMNB problem, called the dynamic broadcasting problem (DBP), we assume that broadcast requests are generated at each node according to a random process, and we are interested in broadcasting schemes that work continuously and execute the requests in such a stochastic environment. We consider two performance criteria. The first is the average delay, that is, the average time between the arrival of a packet at a node and the completion of its broadcast. The second criterion is the stability region of the scheme, that is, the maximum load ?that it can sustain with the average delay being finite. We set two objectives for a dynamic broadcasting scheme: stability for as big a load as possible, and average delay that is of the order of the diameter for any fixed load in the stability region.
Algorithms to execute for the PMNB and the dynamic broadcasting problem topologies were considered in some of our previous works for a variety of regular topologies. In a more general work, we have found on-line algorithms to execute a PMNB and in an arbitrary topology, without assuming any information about the location of the active nodes. The execution time of this algorithm is within a factor of at most 2 from being optimal, independently of the location of the active nodes. For the dynamic broadcasting problem, under the half-duplex communication model, the schemes proposed for general graphs have a stability region that tends to the maximum possible as the number of nodes tends to infinity, and an average delay that is of the order of the diameter of the network. However, for the full-duplex communication model (where a link can be used in both directions simultaneously) the stability region is only 50% of the maximum possible, and the problem is still open. In our future work, we plan to consider the more general case where the destination nodes are a strict subset of the total set of nodes (i.e., multicasting as opposed to broadcasting). Also, additional research is needed in order to incorporate flow control mechanisms in broadcasting and multicasting schemes. Since much of the traffic (video, multimedia teleconferencing, topology information updates) that will be generated in a high-speed network is going to be of the one-to-all (broadcast) or one-to-many (multicast) type, the practical importance of the problems described above is evident.
The methodology used in the analysis of the dynamic broadcasting problem suggests that there is a connection between static and dynamic routing problems. The technique that we intend to use for solving other dynamic problems is to first try to find an algorithm for the static version of the problem, and then use an approach similar to that used to deal with the dynamic version.
Mobile and Packet Radio Networks
We are are working on the design and evaluation of a new class of protocols for mobile packet radio networks. Specifically, we have developed a lossless, media-access and connection-establishment protocol for the Quasi Synchronous ad-hoc Packet Radio Network (QSPNET), which uses a novel linear decorrelator receiver for multiuser detection which permits the reception of Quasi-Synchronous Code Division Multiple Access (QS-CDMA) waveforms. Using OPNET we have also characterized the performance of the network.
VLSI layouts of interconnection networks
We have developed optimal and near-optimal VLSI layouts for many interconnection topologies of interest and have developed a new model for multiplayer VLSI layouts. This work has resulted in many cases in finding the best layouts that have appeared in the literature so far.
We have proposed the recursive grid layout scheme for the systematic layout and packaging of hierarchical networks and a variety of other important networks. Some of the obtained optimal results are summarized in Table 1. In particular, the gap between the upper and lower bounds on the are of star graphs was improved from a factor of 3528+o(1) in earlier works to a factor of 1+o(1), which solved an open problem posed by Akers and Krishnamurthy in 1986. We also derived layout and packaging of butterfly networks with optimal area and pin-out at the same time.
Optimal Fault Tolerant Communication and Computing
We have developed techniques for transforming techniques to transform distributed algorithm developed for a particular network into robust algorithms that can tolerate the presence of faults. We proposed the robust algorithm approach for fault-tolerant communication and computing in parallel and distributed systems without relying on any hardware technology. In particular, we showed that 1-1 sorting can be performed in 2.5n+o(n) communication steps and 2n+o(n) comparison steps on an nxn bidirectional mesh that has an arbitrary pattern of o(sqrt(n)) faults, assuming that each healthy and connected processor has one of the keys to be sorted. Surprisingly, this running time has exactly the same leading constant as the best known algorithms for 1-1 sorting on an nxn fault free mesh. We also applied the robust algorithm approach to a variety of important problems and showed that the fast Fourier transform (FFT), permutation routing, total exchange (TE), and ascend/descend algorithms can also be executed on faulty arrays (i.e., meshes, tori, or k-ary n-cubes) with a factor of 1+o(1) slowdown relative to a fault-free array of the same shape.
Previously the research community in this area mainly focused on reconfigurable meshes/tori with spare processors and links for fault-tolerant computing; the industry, however, has never implemented such systems due to their higher implementation cost. Our work sheds some light on the possibility of using cost-effective software approaches for efficient fault-tolerant communication and computing.
We have also devised new efficient trade-off methods for the computation of arithmetic functions using majority circuits, which substantially improve existing results. We have also provided threshold circuits of restricted fan-in to perform multiplication and to compute symmetric functions, and have also proposed a class of threshold circuits that are optimized for floating point computations.