Preserving integrity of applications being executed in remote machines is an open problem. Integrity requires that application code is not tampered with, prior to or during execution, by a rogue user or a malicious software agent. This paper presents a methodology to enforce runtime integrity of application code by means of an integrity- preserving software component that is combined with the application. The software component is a trusted logic that can be replaced continuously from a remote location during run-time. For added assurance, the software component produces continuous sequence of proofs of its proper operation that are verified remotely.

Recently the Birkhoff-von Neumann load-balanced (LB) switch has become a promising switch design due to its high scalability properties and simple control. The performance of the LB switch was studied under strong assumptions such as infinite buffers and admissible traffic conditions. However, both such assumptions may be violated in multi-hop networks since admissibility requirement cannot be maintained unless some inter-switch feedback mechanism is implemented, and infinite buffers are not feasible either. This paper considers the performance of the LB switch with finite central stage buffers under both (i) admissible and (ii) inadmissible input traffic conditions. Its contributions are two folds: firstly, by means of mathematical model we demonstrate that the load-balanced switch has a non-zero cell dropping probability due to buffer overflow even under the admissible input traffic assumptions. Secondly, cell loss probabilities are even higher and large buffers are required under inadmissible traffic conditions to cope with such behavior.

This paper analyzes possible Banyan network solutions as a multistage interconnection network exploiting time and space domains. The well-known approach to replicate a Banyan in space provides non- blocking property, meanwhile increasing the cost index to a great extent. In order to keep the cost function under control we investigate how a Banyan network can be built that maintains the blocking probability below acceptable thresholds. To this extent we first discuss the non-blocking conditions for multistage networks in the space domain with arbitrary size of the basic switching element. Then we evaluate how exploiting time division multiplexing in such a network can help relieving the cost issue while keeping the blocking probability under control. The study compares all-optical vs. electronic implementations and analyzes the cost index. The traffic performance results of Banyan with different sizes of the switching element, with replications and TDM are presented.

This work addresses the high-rate session scheduling problem in fractional lambda switching (FlambdaS) networks. With its global phase synchronization and pipeline forwarding (PF) operation, FlambdaS offers promising network performance and scalability over its competitors, e.g., time division multiplexing (such as SONET/SDH) and wavelength division multiplexing (WDM). Yet, Non-Immediate Forwarding (NIF) brings challenging complexity to session scheduling, where other known scheduling methods (e.g. RWTA) are not applicable. A forwarding graph is used to wholly examine the huge schedule space for an end-to-end high-rate NIF session. An efficient scheduling algorithm, eSSM, is proposed to explore all possibilities on the graph and present the optimized non-blocking schedule. Complexity bounds are then devised analytically and experimentally verified under specific circumstances. A low-complexity heuristic is proposed to avoid the complexity of eSSM in low-load networks.

Fractional lambda switching (FlambdaS) is a novel approach for traffic management over all-optical networks with sub-wavelength provisioning capability. The unique characteristic of FlambdaS is the utilization of UTC (coordinated universal time) for switching with minimum or no buffers. Several central research issues are still open in FlambdaS and need to be formally defined and analyzed. In this paper, we introduce three novel switch designs that are based on the use of tunable lasers (which can be replaced in the future with wavelength converters). First, the paper presents analytical results of scheduling feasibility, which measures the total number of possible different schedules for each switch design. Then it is shown that the architecture with the highest scheduling feasibility is strictly non blocking in the space domain. Next, the paper provides a closed form analysis of the blocking probability in the time domain, which is applicable for any strictly non-space blocking switch, using combinatorics. In addition, the paper provides measures of the switching hardware complexity, which, for the strictly non-blocking architecture, has the same switching complexity as Clos interconnection network, i.e., O(N'radic(N')) where N' is the number of optical channels.

Efficient scheduling for heterogeneous fractional lambda switching (FlambdaS) networks is required but challenging. A heterogeneous network implies bandwidth mismatch between links of varied bit rates. Moreover, when non-immediate forwarding (NIF) is used in FlambdaS, it increases the scheduling complexity exponentially, while decreasing the blocking probability. Thus, NIF scheduling presents a serious challenge for an algorithm to be used in a large heterogeneous FlambdaS network. In this paper, an efficient scheduling algorithm that is combined with a flexible forwarding scheme is presented. The algorithm provides a full scheduling solution for an end-to-end request in heterogeneous FlambdaS networks. Furthermore, the algorithm has linear complexity in single-channel networks and quadratic complexity in multiple-channel WDM networks.

In order to achieve ultra scalable IP packet switching it is essential to minimize "stopping" of the serial bit streams. In our recent experimental work we demonstrated how this can be achieved with an ultra-scalable switching architecture reaching multi-terabits per second (10-100 Tb/s) in a single chassis. The implemented testbed uses only off-the-shelf optical and electronic components. The scalability of this architecture is the direct outcome of how global time (i.e., UTC - coordinated universal time) and pipeline forwarding are utilized. The paper presents the design of a prototype switch and experimental activity with it.

Future Internet traffic will be dominated by on-demand streaming media flows, such as IPTV, 3D/HD video, gaming, virtual reality, and many more. Consequently, future network architectures will need to implementscalable IP packet switchingcapable of offeringpredictable performancesto such applications. Our recent experimental work demonstrated how an IP network can be implemented without "stopping" the serial bit streams. The deployed switch is very simple, scalable to 10-100 terabits per second in a single chassis, and suitable for all optical implementation. The implemented testbed uses only off-the-shelf optical and electronic components and was completed in 9-month.

Time-driven Switching (TDS) networks with non-immediate forwarding (NIF) provides scheduling flexibility and consequently, reduces the blocking probability (blocking is defined to take place when transmission capacity is available, but without a feasible schedule). However, it has been shown that with NIF scheduling complexity may grow exponentially. Efficiently finding a schedule from an exponential set of potential schedules is the focus of this paper. The work first presents the mathematical formulation of the NIF scheduling problem, under a wide variety of networking requirements, then introduces an efficient (i.e., having at most polynomial complexity) search algorithm that guarantees to find at least one schedule whenever such a schedule exists. The novel algorithm uses 'trellis' representations and the well-known survivor-based searching principle.

As data traffic on the Internet continues to grow exponentially, there is a real need to solve the switch bottleneck by developing ultra-scalable switching fabrics and their control. Although in recent years there have been a lot of efforts to solve the switching fabric scalability problem, in the optical domain, the proposed solutions have been (very) expensive, (very) complex and (much) larger than electronic switching fabric alternatives. In order to increase scalability a coordinated universal time (UTC) based time-driven switching (TDS) is proposed. This novel low-complexity switching architecture capitalizes on the ubiquitous of UTC from GPS and Galileo. This work focuses on UTC-based FPGA (field programmable gate- array) controller that was implemented for controlling the TDS switch prototype at the University of Trento, Italy. The switch controller facilitate dynamic configuration of ultra scalable switch. The prototype is implemented using off-the-shelf components. TDS architecture is especially suitable to support high capacity streaming media applications over the Internet.

As traffic on the Internet continues to grow exponentially, there is a real need to solve transmission and switching scalability. Moreover, future Internet traffic will be dominated by streaming media flows, such as video-telephony, video-conferencing, 3D video, virtual reality, and many more. Consequently, network solutions will need to offer quality of service and traffic engineering together with the above mentioned scalability - i.e., over-provisioning is not likely be a viable solution to accommodate streaming media traffic. This paper describes the architecture of a ultra-scalable IP switch and the first experiments with a prototypal implementation. The switch scalability is a consequence of it operating pipeline forwarding of packets, which also results in quality of service guarantees for UDP-based streaming applications, while preserving elastic TCP-based traffic as is, i.e., without affecting any existing applications based on "best- effort" services. Moreover, the prototype demonstrates the low complexity of pipeline forwarding implementation as the deployed network gear was realized from off-the-shelf components in only nine months through the design, implementation, and testing efforts of the authors.

Fractional Lambda Switching (FλS) is a novel proposal for the management of all-optical networks with sub-wavelength provisioning capability. The unique characteristic of FλS is the utilization of the UTC (coordinated universal time) for alignment and switching. Several central research issues are still open in FλS and need to be formally defined and analyzed. Within the scope of this paper, we introduce three novel switch architecture designs that are based on the use of tunable lasers. As an important goal, we introduce the notion “scheduling feasibility” that measure the number of possible different scheduling between an input and output time-frames.

This work further studies blocking issues that are related to time driven switching (TDS). TDS is a novel and promising technology for the realization of low complexity and high scalability switches in the electrical and optical switching domains. TDS is unique in enabling the implementation of all-optical fractional wavelength switching with current state-of-the-art components. Furthermore, TDS provides deterministic QoS guarantees for all streaming media applications. Being a new technology, TDS requires investigation, especially regarding its performance and efficiency. The performance in this paper considers multiple scenarios with variety of optical transmission and switch parameters. The performance results show that blocking does not compromise the efficiency in most cases, even with elevated offered traffic load with the restrictive scheduling of immediate forwarding.

A new approach is introduced in this paper to make possible a flexible utilization of WDM networks using current technology. It is shown that the bandwidth made available end-to-end by a single wavelength can be simply broken up into smaller fractions by relying on worldwide free synchronization systems, such as GPS, previously deployed for different applications. It is shown how this new approach, called time driven switching, behaves in terms of call blocking when the basic parameters of the scheme are varied.

In general topology networks, routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(logn) links, n being the number of nodes in the network. Routing from one node to another over a ring embedded in the network results in route length of O(n) links. However, in group (many-to-many) multicast, the overall number of links traversed by each packet, i.e., the networks elements on which resources must possibly be reserved, is typically O(N) for both tree and ring embedding, where N is the size of the group. The paper focuses on tree versus ring embedding for real-time group multicast in which all packets should reach all the nodes in the group with a bounded end-to-end delay. Real-time properties are guaranteed by the deployment of time-driven priority in network nodes. In order to have a better understanding of the nontrivial problem of ring versus tree embedding, we consider static, dynamic and adaptive group multicast scenarios. Tree and ring embedding are compared using different metrics. The results are interesting and counterintuitive, showing that embedding a tree is not always the best strategy. In particular, dynamic and adaptive multicast on a tree require a protocol for updating state information during operation of the group. Such a protocol is not required on the ring where the circular topology and implicit token passing mechanisms are sufficient. Moreover, the bandwidth allocation on the ring for the three multicast scenarios is O(N), while on a general tree it is O(N) for the static multicast scenario and O(N/sup 2/) for the dynamic and adaptive multicast scenarios.

Fractional Lambda (/spl lambda/) Switching (F/spl lambda/S/spl trade/) adds the necessary efficiency to wavelength division multiplexing (WDM) while preserving the simplicity of whole /spl lambda/ switching. Due to its provisioning capability, from a fraction of STS-1 to a full optical channel capacity, F/spl lambda/S/spl trade/ will extend the reach of optical networking all the way to the network edges in the metro and enterprise. Finally, F/spl lambda/S/spl trade/ uniquely enables the implementation of dynamic all-optical switches since its operation does not require (1) optical processing (e.g., packet header processing) and (2) optical buffering.

We investigate the problem of self-stabilizing round-robin token management on a bidirectional ring of identical processors. Each processor is an asynchronous probabilistic finite state (i.e., constant space) machine which sends and receives constant-size messages and whose state transition is triggered by the receipt of a message. We also show that this problem is equivalent to symmetry breaking (i.e., leader election). Wejustify and suggest a two-layer (hardware and software) solution to the token management problem: The subproblem of reducing an arbitrary but nonzero number of tokens (in an otherwise arbitrary initial system state) to exactly one token (and a legal system state) is solved in hardware and takes only small polynomial time. The detection of a complete lack of tokens (communication deadlock) is done by a software clock. In high-speed networks the hardware layer can be implemented using fast universal switches (i.e., finite state machines) independent of the size of the network. We note that randomization is essential, since Dijkstra showed that for arbitrary rings the subproblem does not have a deterministic solution (regardless of the computational power of the identical processors). The use of the software layer (deadlock detection) in our solution is minimized.

Videoconferencing is an important global application-it enables people around the globe to interact when distance separates them. In order for the participants in a videoconference call to interact naturally, the end-to-end delay should be below human perception; even though an objective and unique figure cannot be set, 100 ms is widely recognized as the desired one-way delay requirement for interaction. Since the global propagation delay can be about 100 ms, the actual end-to-end delay budget available to the system designer (excluding propagation delay) can be no more than 10 ms. We identify the components of the end-to-end delay in various configurations with the objective of understanding how it can be kept below the desired 10-ms bound. We analyze these components step-by-step through six system configurations obtained by combining three generic network architectures with two video encoding schemes. We study the transmission of raw video and variable bit rate (VBR) MPEG video encoding over (1) circuit switching; (2) synchronous packet switching; and (3) asynchronous packet switching. In addition, we show that constant bit rate (CBR) MPEG encoding delivers unacceptable delay-on the order of the group of pictures (GOP) time interval-when maximizing the quality for static scenes. This study aims at showing that having a global common time reference, together with time-driven priority (TDP) and VBR MPEG video encoding, provides adequate end-to-end delay, which is (1) below 10 ms; (2) independent of the network instant load; and (3) independent of the connection rate. The resulting end-to-end delay (excluding propagation delay) can be smaller than the video frame period, which is better than what can be obtained with circuit switching.

This paper shows how to provide an adaptive real-time group multicast (many-to-many) communication service. Adaptive means that the number of nodes that transmit to the multicast group is continuously changing. In order to meet deterministic quality-of-service (QoS) requirements of a real-time group multicast, some communication resources are reserved. We show (1) how bandwidth is reserved for each multicast group and (2) how an active source can dynamically share the bandwidth allocated to this multicast group with other active group members. Quality-of-service support for a real-time multicast group is based on time-driven priority. In this scheme the time is divided into time frames of fixed duration, and all the time frames are aligned by using a common global time reference, which can be obtained from the Global Positioning System. Bandwidth is allocated to a multicast group as a whole, rather than individually to each user. The allocation is done by reserving time intervals within time frames in a periodic fashion. This type of allocation raises two problems that are studied in this paper: (1) scheduling: how time intervals are reserved to each multicast group and (2) adaptive sharing: how the active (transmitting) participants can dynamically share the time intervals that have been reserved for their multicast group. The proposed approach is based on the embedding of multiple virtual rings, one for each multicast group. By using the virtual rings, it is simple to route messages to all the participants while minimizing the bound on the buffer sizes and queueing delays. The final part of this paper introduces a scalable growth of the multicast group by adding multiple subtrees to the virtual ring.

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications. While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm: i) locality and congestion-driven-only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing. ii) Scalability-the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). iii) Linear access time in the congested subnetwork-measured by "the maximal clique in what we call the conflict graph to which a node belongs," and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).

In general topology networks, routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(log n) links, being n the number of nodes in the network. Routing from one node to another over a ring embedded in the network would result in route length of O(n) links. However, in group (many-to-many) multicast, the overall number of links traversed by each packet, i.e., the networks elements on which resources must be possibly reserved, is typically O(N) for both tree and ring embedding, where N is the size of the group. This paper focuses on the tree versus ring embedding for real-time group multicast in which all packets should reach all other nodes in the group with a bounded end-to-end delay. In this work, real-time properties are guaranteed by the deployment of time driven priority in network nodes. In order to have a better understanding of the non-trivial problem of ring versus tree embedding, we consider the following group multicast scenarios: (i) static-fixed subset of active nodes, (ii) dynamic-fixed number of active nodes (i.e., the identity of active nodes is changing over time, but its size remains constant), and (iii) adaptive the number and identity of active nodes change over time. Tree and ring embedding are compared using the following metrics: (i) end-to-end delay bound, (ii) overall bandwidth allocated to the multicast group, and (iii) signaling overhead for sharing of the resources allocated to the group. The results are interesting and counter-intuitive, since, as shown, embedding a tree is not always the best strategy. In particular, dynamic and adaptive multicast on a tree requires a protocol for updating state information and coordinates the operation of the group. Such a protocol is not required on the ring where the circular topology, and implicit token passing mechanisms are sufficient. Moreover, the bandwidth allocation on the ring for the three multicast scenarios is O(N); while on a general tree it is O(N) for the static multicast scenario and O(N/sup 2/) for the dynamic and adaptive multicast scenarios.

This paper presents an extensive performance study in order to identify some tradeoffs between tree-based and ring-based reliable group multicast protocols. The motivation for such a study is the following observation. In communications network routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(log n) links, while routing from one node to another over a ring embedded in the network would result in route length of O(n) links. However, in a group multicast (many-to-many) the overall number of links traversed by each packet for both tree and ring embedding is typically O(N), so both approaches have similar communication requirements. In reliable group multicast protocols the traffic pattern is complex, since packets are sent from a multicast source to the multiple destinations, and then some control packets are sent back to the source, and this can result in resending of some of the original packets. Consequently, determining under what condition the tree-based approach is better than ring-based approach is not obvious. The key criteria for evaluating the performance of a reliable group multicast protocol is (i) how many successful multicast were achieved per unit time, and (ii) what is the efficiency of the multicast, namely, the ratio between the number of successful transmission and the total number of packets that were transmitted. Under the above criteria it is shown that the ring-based multicast often performs better than the tree-based multicast. One of the main reasons for this result is that ring-based multicast is window-based with simple and effective management of acknowledgments and retransmissions, while the tree-base is rate-based with complex and slow management of acknowledgments and retransmissions.

Videoconferencing is an important global application -it enables people around the globe to interact when they are far from one another. In order for the participants in a video-conference call to interact naturally, the end-to-end delay should be below human perception-about 100 ms. Since the global propagation delay can be about 100 ms, the actual end-to-end delay budget available to the system designer (excluding propagation delay) can be no more than 10 ms. We identify the components of the end-to-end delay in various configurations with the objective of understanding how it can be kept below the desired 10 ms bound. We analyze these components going step-by-step through six system configurations obtained by combining three generic network architectures with two video encoding schemes. We study the transmission of raw video and variable bit rate (VBR) MPEG video encoding over (i) circuit switching, (ii) synchronous packet switching, and (iii) asynchronous packet switching. In addition, we show that constant bit rate (CBR) MPEG encoding delivers unacceptable delay, which is on the order of the group of pictures (GOP) time interval. This study shows that having a global common time reference, together with time-driven priority (TDP) and VBR MPEG video encoding, provides adequate end-to-end delay, which is (i) below 10 ms, (ii) independent of the network instant load, and (iii) independent of the connection rate. The resulting end-to-end delay (excluding propagation delay) can be smaller than the video frame period, which is better than what can be obtained with circuit switching.

This paper shows how to provide an adaptive real-time group multicast (many-to-many) communication service. Such a service can be used by applications, like audio/video tele-conferencing, that require low loss, and bounded delay and jitter. In order to meet deterministic quality of service (QoS) requirements of a real-time group multicast, some communication resources are reserved. In this work we show (i) how bandwidth is reserved for each group, and (ii) how an active user in a multicast group can dynamically share, in an efficient and fair manner, the bandwidth allocated to its group. Quality of service support for a real-time multicast group is based on time driven priority. In this scheme the time is divided into time frames of fixed duration and all the time frames are aligned by using a global time reference which can be obtained from GPS (global positioning system). Bandwidth is allocated to a multicast group as a whole, rather than individually to each user. The allocation is done by reserving time intervals within time frames in some periodic fashion. This sort of allocation raises two problems that are studied in this paper: (1) scheduling: how time intervals are reserved to each multicast group, and (2) adaptive sharing: how the participants dynamically share the time intervals that have been reserved for their multicast group. The proposed approach is based on embedding multiple virtual rings, one for each multicast group. By using the virtual rings it is simple to route messages to all the participants, while minimizing the bound on the buffer sizes and queuing delays.

This paper presents a protocol and design for concurrent and reliable group multicast (many-to-many) from bursty data sources in general networks. In a group multicast, any node can be a multicast source and multiple nodes may start to multicast simultaneously, i.e., an asynchronous access to the network. The reliable multicast protocol presented is window based with a combined sender and receiver initiation of the recovery protocol. In reliable multicasting the necessary requirement is to ensure that data is received correctly by all the active members of the multicast group. The approach taken is to combine the multicast operation with the internal flow control. As a result, it is possible to provide: (1) congestion-free multicast routing with a single and immediate acknowledgment message to the sender. Furthermore, in every multicast, (2) a node can access all the capacity allocated to its group with no delay, however, if several nodes are active in the same group, then the capacity will be shared fairly. In addition, (3) each sender in the multicast group uses a single timer, and (4) a node can become active or inactive in a transparent fashion, i.e., there is no need to explicitly notify the members of the group. A multiple criteria optimization study of the bandwidth allocation to each multicast group is presented. The optimization problem has two min-max objective functions: (1) for delay, which is caused by the number of links needed to connect the group, and (2) for congestion, which is caused by sharing a link among multiple multicast groups. The bandwidth allocation among multicast groups sharing the same link are further optimized using the max-min fairness criterion.

The problem solved in this work is how multiple nodes in a network with an arbitrary topology can broadcast concurrently, in an asynchronous manner, to all other nodes. Asynchronous means that the nodes do not coordinate their broadcast, and, therefore, it is possible that all nodes will start to broadcast at the same time. Simultaneous broadcast by many nodes can cause traffic congestion, which can result in a traffic loss. The main property of the broadcast algorithms presented in this work is that under any arbitrary broadcast pattern there will be no packet or cell loss due to internal traffic congestion. The routing mechanism used by the broadcast algorithm can be viewed as a variant of deflection routing, which means that a node makes on-line routing decisions based on the local flow of traffic (i.e., internal load conditions). Unlike other deflection techniques, the MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. Thus, we call this method convergence routing (previous deflection algorithms did not guarantee deterministic routing convergence, i.e., a cell/packet can be deflected indefinitely inside the network). As a result of the convergence property, the deflection routing used in this work is the only one with broadcast capability.

The main motivation for developing the MetaRing architecture was to increase the throughput of a ring-based local area network beyond its single link capacity by means of spatial bandwidth reuse. We describe and evaluate a protocol for integrating two types of traffic on the MetaRing architecture. Synchronous (reserved or real-time) traffic which is periodic and requires a connection set-up and will have guaranteed bandwidth and bounded delay, and asynchronous or bursty traffic with no real-time constraints that can use the remainder of the bandwidth in a fair manner. The integration mechanism is functionally equivalent to the timed-token function in FDDI, which is a shared media ring protocol. Simulation results are also presented to show the effects of the fairness and flow control signals on the performance of the network.

This paper shows how to optimize the routing decisions in a nondeterministic routing algorithm called convergence routing in which routes may change depending on the traffic conditions. The routing algorithm guarantees a loss-free delivery of data packets from bursty sources, and a deterministic bound on the route length in arbitrary topology networks. The routing decisions are based on assigning routing priorities to the links such that a packet is forwarded to the highest priority link which is not blocked. Routing priorities are assigned using a local-greedy metric which minimizes the distance (number of hops) to the destination. This work shows that routing decisions using a local-greedy metric are not optimal, and the performance of the algorithm can be improved substantially by using new measures. Thus, various look-ahead metrics which take into account the potential gain on the other switching nodes toward the destination of a packet are suggested. The contributions of this work are: (1) a new analytical model to capture the behavior of a switching node; (2) an iterative optimization technique to set routing priorities according to various look-ahead measures; and (3) heuristics to ensure the stability of the routing priorities. The optimization objective is to maximize the throughput by minimizing the maximum total flow carried on a link in the network under static traffic model. The performance is studied computationally on various networks and traffic matrices. It is shown that up to a 50% performance increase can be obtained by optimizing the routing priorities.

This paper presents a new design methodology and tools to construct a packet switched network with bursty data sources. This network design combines two important properties for arbitrary traffic pattern: (1) the aggregate throughput is scalable and (2) there is no packet loss within the subnet. More specifically, given a bounded number of ports in every switching node, the design is based on the construction of multiple virtual rings under the following constraints: (1) the virtual rings are pairwise edge-disjoint and (2) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The two constraints ensure no loss due to congestion inside a network with arbitrary traffic pattern and that packets will reach (or converge) their destinations. The virtual rings are constructed by using combinatorial block designs together with an algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(/spl radic/N) for an N-node network, This sublinear bound facilitates the throughput scalability property.

We consider real-time traffic in a heterogeneous internetworking environment with IP routers, MAC bridges, hubs, switched LANs etc. We assume that the current routing protocols remain unchanged. However in this environment, in order to provide quality of service (QoS): bandwidth, delay, constant-bounded jitter and no-loss due to congestion, we suggest a new flow control function called time-driven priority, which is an internal traffic shaping mechanism. We show how it supports two classes of connections: constant bit rate (CBR) with deterministic guarantees, and variable bit rate (VBR) with statistical multiplexing. The mechanism does not require to identify and separate the packet flows of different real-time sessions/connections inside the network. As a result, it achieves lower switching complexity when compared with other internal traffic shaping methods. As consequences of the time-driven priority mechanism we further achieve: (1) QoS parameters which are independent of the connection bandwidth, (2) QoS parameters which are independent of the existing heterogeneous internetworking asynchronous data traffic and (3) the capability for policing and securing the network QoS.

Max-min fairness has been recognized as an optimal throughput-fairness definition. However, its realization in packet switching networks and its computational requirements have not yet been understood. We attempt to take a step in this direction, in the context of local area network (LAN) traffic. The max-min definition is given in terms of transmission rates of sources sending to their destinations (sessions). In order to realize max-min rates in a packet switching environment, transmission schedules of packets need to be realized. We first show that finding max-min fair schedules (with given rates) requires global state and timing information of all the nodes in the network. We then design a local scheduling algorithm for ring and bus networks with minimum transmission-delay, concurrent access, and spatial bandwidth reuse. This distributed algorithm uses only partial state information and is based on locally exchanging simple signals only between directly conflicting sessions (sessions which share at least one link) rather than collecting global information. The results of this algorithm are novel in various ways: (1) we prove that each session has an access-delay of at most twice its bottleneck link; (2) we show that the algorithm operates adaptively with an optimal access-delay in a dynamic environment (bursty traffic sources); and (3) by means of simulation experiments we further show that this algorithm achieves, in a steady-state, max-min fair rates for a vast majority of sessions and an average aggregate throughput which is 99 percent the throughput obtained by max-min fair rates.

This paper presents a protocol and design for concurrent and reliable group multicast (many-to-many) from bursty data sources in general networks. In a group multicast, any node can be a multicast source and multiple nodes may start to multicast simultaneously, i.e., an asynchronous access to the network. The reliable multicast protocol presented in this work is window based with a combined sender and receiver initiation of the recovery protocol. In reliable multicasting the necessary requirement is to ensure that data is received correctly by all the active members of the multicast group. The approach taken in this work is to combine the multicast operation with the internal flow control, as a result, it is possible to provide: (1) loss-free multicast routing with a single and immediate acknowledgement message to the sender. Furthermore, in every multicast, (2) a node can access all the capacity allocated to its group with no delay, however, if several nodes are active in the same group then the capacity will be shared fairly. In addition, (3) each sender in the multicast group uses a single timer, and (4) a node can join and leave a multicast group in a transparent fashion, i.e., there is no need to explicitly notify the members of the group. A multiple criteria optimization study of the bandwidth allocation to each multicast group is presented. The optimization problem has two min-max objective functions: (1) for delay, which caused by the number of links needed to connect the group, and (2) for congestion, which is caused by sharing a link among multiple multicast groups. The bandwidth allocation among multicast group sharing the same link are further optimized using the max-min fairness criterion.

This paper presents a new distributed methodology for source destination synchronization for interactive teleconferencing. The method is based on a reference clock, which is synthesized from a distributed global clock. The global clock is generated by periodically exchanging inband synchronization signals with neighboring nodes. The timing jitter achieved with this method can be arbitrarily close to the jitter obtained by the centralized synchronous methods which usually use an out-of-band, hard-wired reference clock. The global clock synchronization algorithm, used in this work, guarantees frequency locking of all the network nodes to the slowest clock in the system. As a result, the slowest clock can be used as an implicit reference clock for source-destination synchronization protocols, such as synchronous frequency encoding technique (SFET) and synchronous residual time stamp (SRTS). This inband synchronization method does not require the explicit knowledge of which clock is actually the slowest in the system. Therefore, if the slowest clock fails, then another clock on a different node will be the slowest, and the nodes will use it as a reference clock for the source-destination synchronization protocol. The existing out-of-band reference clock techniques do not have this strong fault tolerant property.

The paper presents a new design methodology and tools to construct a switch-based LAN with (i) scalable throughput, (ii) no loss due to congestion, and (iii) two routing modes: FIFO or non-FIFO. More specifically, given a bounded degree (number of switch ports) at each node, the design is based on the construction of multiple virtual rings under the following constraints: (i) the virtual rings are pairwise edge-disjoint, and (ii) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The objectives of the above two constraints are (i) to ensure no loss due to congestion inside the network of bursty traffic sources, and (ii) to ensure convergence of packets/cells to their destinations. The virtual rings are constructed by a new methodology that employs combinatorial block designs together with a new algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(/spl radic/N) for an N-node network.

This paper presents a new source routing technique for ring and multi-ring networks, which uses short address labels. The main objectives for having this new method are that in case of one or more failures a frame will be guaranteed: (1) to be removed from the ring-termination property, and (2) to be copied at most once and only by its destinations-safety property. The scheme is based on dividing the label address space of each ring into subspaces, such that the address subspaces are physically disjoint. More specifically, each ring, in a multi-ring network, is divided into two or more parts such that adjacent address subspaces are disjoint. The route of each frame is described by a sequence of short address labels in the frame's header. The current route of a frame is determined by the first address label in its header, and it can be used for routing over at most one subspace of the ring.>

The MetaNet is a scalable local area network (LAN) architecture with an arbitrary topology and a switch at each node (i.e., a switch based LAN). Its design provides on one hand a service in which any node can try to transmit asynchronously in a bursty manner without reservation as much as it can (as in traditional LAN), and on the other hand the network access and flow control ensure the following properties: (1) no packet loss due to congestion, (2) fair access to the network, (3) no deadlocks, and (4) self-routing with broadcast. The switching over this network requires only a (5) single buffer per input link. The MetaNet is asynchronous, distributed, and designed for transmission of fixed size cells or variable size packets. It can be viewed as a "general-topology buffer-insertion architecture with fairness," thus generalizing the MetaRing architecture.>

This paper presents fault-tolerant protocols for fast packet switch networks with convergence routing. The objective is to provide, after a link or a node (switch) failure, fast reconfiguration and continuous host-to-host communication. Convergence routing is a variant of deflection routing, which combines in a dynamic fashion, the on-line routing decision with the traffic load inside the network. Unlike other deflection techniques, convergence routing guarantees that packets will reach or converge to their destinations. This fault-tolerant solution is designed for a switch-based (i.e., arbitrary topology) LAN architecture called MetaNet. The original MetaNet's convergence routing scheme has been modified in order to facilitate the property that the packet header need not be recomputed after a failure and/or a reconfiguration. This is achieved by having, at the network interface, a translator that maps the unique destination address to a virtual address. The virtual addresses are stored at the packet header, and used for convergence routing, with a global sense of direction over (i) a single spanning tree, and (ii) over two edge-disjoint spanning trees, for redundancy (fault tolerance) and greater efficiency.>

In computer networks there is usually a trade-off between the performance and implementation complexity of the routing protocol, and those of the protocol for reliable transmission of data. Often, the routing protocol can perform better if it is not required to retain the FIFO order of the routed data units. However, in such a case the protocol for reliable transmission of data has to maintain many logical timers and to have an accurate estimate of the round trip delay. The paper introduces a new notion: semi-FIFO service, which means that the routing layer retains the FIFO order in part. The paper shows that sometimes a non-FIFO routing layer may easily provide for a semi-FIFO service, without changing the routing concept. Then, at proposes a new protocol for reliable transmission of data over an unreliable semi-FIFO routing layer. The protocol uses only one logical timer and does not require an estimate of the round trip delay in order to operate with maximum capacity. Therefore, the contribution of the paper is eliminating the deficiencies associated with a non-FIFO routing layer that may offer a semi-FIFO service.>

This paper shows how to design an ATM network, for real-time traffic, such that under full network load (i) the maximum delay of a low-rate voice connection is minimized, (ii) the delay uncertainty or jitter is a fixed network parameter, and (iii) the required buffer sizes (inside the network) to ensure loss-free routing is minimized. In addition, this design does not exclude the integration of other classes of traffic, such as connectionless, which have lower priority. The isochronous timing information is used only for regulating and pacing the traffic forwarded inside the network rather than for routing as in traditional circuit switching networks. This means that an ATM cell is sent from one switch to another not at a very specific time but within a time frame of a relatively long duration as compared to the cell transmission time. The routing of cells of each connection is based on VCI and VPI, and as a result, timing errors do not affect the ATM routing. Analytical and simulation results are presented, which demonstrate the effectiveness of this switching approach.>

This work presents a coherent system solution for combining with no loss due to congestion, on one hand, bursty traffic with unpredictable pattern in time and space, and on the other hand, periodic real-time or connection-oriented traffic with bandwidth guaranteed requirements over fixed routes. This solution facilitates the implementation of a scalable high performance multimedia system for distributed/parallel computing with real-time interactive voice and video. The MetaNet real-time traffic has the following attributes: (1) guaranteed bandwidth with bounded delay, (2) fixed jitter-independent of the network size, (3) no loss due to congestion inside the network, (4) fixed path routing with FIFO order, and (5) support of complex periodicity scheduling. At the same time, the underlying MetaNet asynchronous (bursty) traffic properties (provided by previous works) remain unchanged. Namely, any node can try to transmit asynchronously (bursty traffic), without reservation as much as it can, and the network access and flow control ensure the following traditional LAN properties: (6) no loss with a single input buffer, (7) fair and deadlock-free access, and (8) self-routing with broadcast. The self-routing on the MetaNet is a variant of deflection routing. It makes on-line routing decisions based on the local flow of traffic (load conditions). Unlike other deflection techniques, the MetaNet routing is along a global sense of direction, which guarantees that cells will reach their destinations. Thus, this method is called convergence routing.>

Describes a new technique, based on exchanging control signals between neighboring nodes, for constructing a stable and fault-tolerant global clock in a distributed system with an arbitrary topology. It is shown that it is possible to construct a global clock reference with a time step that is much smaller than the propagation delay over the network's links. The synchronization algorithm ensures that the global clock "tick" has a stable periodicity, and therefore, it is possible to tolerate failures of links and clocks that operate faster and/or slower than nominally specified, as well as hard failures. The approach taken is to generate a global clock from the ensemble of the local transmission clocks and not to directly synchronize these high-speed clocks. The steady-state algorithm, which generates the global clock, is executed in hardware by the network interface of each node. At the network interface, it is possible to measure accurately the propagation delay between neighboring nodes with a small error or uncertainty and thereby to achieve global synchronization that is proportional to these error measurements. It is shown that the local clock drift (or rate uncertainty) has only a secondary effect on the maximum global clock rate. The synchronization algorithm can tolerate any physical failure. It will continue to operate correctly on any connected segment of the network, i.e., it can tolerate any number of link and node failures, as long as the network remains connected.>

In networks that use label swapping routing, like ATM, inconsistent routing tables, due to either incorrect setups or memory failures, may result in infinite looping of packets. This work proposes and analyzes a method for ensuring self-termination in such networks. The method is based on imposing linear order on the labels chosen by the stations along the route during connection setup, and on a simple on-line check performed by every station upon making routing decisions. We then analyze the probability of connection setup failure due to the linear order constraint, and show that it is very small.>

In networks that use label swapping routing, like asynchronous transfer mode (ATM), inconsistent routing tables, due to either incorrect setups or memory failures, can result in infinite looping of packets. A method for ensuring self-termination in such networks is proposed and analyzed. The method is based on imposing linear order on the labels chosen by the stations along the route during connection setup, and on a simple online check performed by every station upon taking routing decisions. the self-termination method along a simple route is then extended to routing over multicast trees.>

Various virtual embedding configurations for the MetaNet architecture are examined. The suggested embedding structures are compared and contrasted, and design parameters and their trade-off are identified. Fairness is used as a mechanism to ensure that the network internally will not be overloaded. Therefore, packets can be sent from source to destination on a route which is close to the shortest path. The routing on the MetaNet is a variant of deflection routing. It makes online routing decisions based on the local flow of traffic (load conditions). MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. This method is called convergence routing. The MetaNet is a LAN/MAN architecture with an "arbitrary topology" (i.e., a switch-based LAN).

The authors present an algorithm to provide local fairness for ring and bus networks with spatial bandwidth reuse. Spatial bandwidth reuse can significantly increase the effective throughput delivered by the network. The proposed algorithm can be applied to any dual ring or bus architecture such as MetaRing. In the dual bus configuration, when transporting ATM cells, the local fairness algorithm can be implemented using two generic flow control (GFC) bits in the ATM cell header. In the performance it is shown that this local fairness algorithm can exploit the throughput advantage offered by spatial bandwidth reuse better than a global fairness algorithm. This is accomplished because it ensures fair use of network resources among nodes that are competing for the same subset of links, while permitting free access to noncongested parts of the network. The performance advantage of the local fairness scheme is demonstrated by simulating the system under various traffic scenarios and comparing the results to that of the MetaRing SAT-based global fairness algorithm. It is also shown that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition.>

The design principles of a ring network with spatial bandwidth reuse are described. A distributed fairness mechanism for this architecture, which uses low latency hardware control signals, is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integration of asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: buffer insertion mode for variable-size packets and slotted mode for fixed-size packets or cells. Concurrent access and spatial reuse allow simultaneous transmissions over disjoint segments of a bidirectional ring and can increase the effective throughput by a factor of four or more. The combination of a full-duplex ring, spatial reuse, a reliable fairness mechanism, and the exploitation of advent in fiber-optic technology are the basis for the MetaRing network architecture.>

A protocol for setting up a tree connection for the purpose of multicast communication over a high-speed packet switched network is presented. The tree connection is based on the use of local identifiers, which are swapped at every intermediate node of the tree. Local identifiers are simple to manage, provide fast access to the routing tables, and are very efficient in terms of the size of the resulting routing space. The authors consider a high-speed network in which the local label swapping on data messages is performed in hardware by the switching subsystem, while the connection set-up is done in software by the switch control subsystem. A reliable protocol for setting up the tree connection is presented, and its correctness is formally proved. The protocol ensures the integrity of the tree and when failures occur, it is gracefully degraded into a smaller tree.>

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bidirectional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. We show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). Requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network. Our automata-based message-passing model has inherent deadlock possibility (i.e., when all processors are waiting for a message) which we assume is detected by an external timeout mechanism. Provided that there is no deadlock to begin with, we show how starting from an arbitrary con guration, the system never enters a deadlock state and further stabilizes in polynomial time. We note that Dijkstra showed that the last problem does not have a deterministic solution (even when the identical processors possess an arbitrary power): starting from a ring with a multitude of tokens, any deterministic system will either not stabilize or will enter a deadlock state.

The implementation of a local area network based on a passive optical star is considered. Two distributed synchronization problems are addressed: (1) generating a global event clock for synchronizing the nodes' operation, and (2) distributed scheduling for accessing the shared passive medium, which is a hybrid (deterministic and random) technique. A hybrid scheduling algorithm is presented that is fair and equivalent to a distributed queue.>

Broadcast and broadcast-with-feedback are presented for MetaNet, a novel network architecture which can be viewed as a LAN with an arbitrary topology. The broadcast and broadcast-with-feedback algorithms presented are functionally equivalent to the broadcast on current LANs, e.g. token-ring or Ethernet. The broadcast algorithms are completely loss free under the asynchronous access method. The broadcast is integrated into the routing mechanism such that it can coexist with any traffic pattern. The time complexity of broadcast on the MetaNet (measured in light-load) is O(log n), while on a ring-based LAN the complexity is n. The algorithms can be modified to serve as a multicast procedure.>

MetaRing is a Gigabit/second local area network architecture based on a dual(bi-directional) optical fiber ring with spatial reuse mechanism. The paper uses simulation to study the performance of MetaRing in the buffer insertion mode with variable length packets. It shows through various delay-throughput curves the major performance aspects of the MetaRing architecture. The results indicate that the combination of a full-duplex ring spatial reuse, and a simple and reliable fairness mechanism of the MetaRing architecture exhibit an excellent delay-throughput performance.>

The authors present a reliable protocol for setting up a tree connection for the purpose of multicast communication over a high-speed packet switched network. The tree connection is based on the use of local identifiers that are swapped at every intermediate node of the tree. Local identifiers are simple to manage, provide fast access to the routing tables, and are very efficient in terms of the size of the resulting routing space. The context of the present work is a high-speed network in which the local label swapping on data messages is performed in hardware by the switching subsystem, while the connection setup is done in software by the switch control subsystem. The correctness of the protocol is formally proved. The protocol ensures the integrity of the tree, and, when failures occur, the tree is gracefully degraded into a smaller tree.>

The design principles of a ring network with spatial reuse are described. The goal is to provide the same functions as designs that do not permit spatial reuse and concurrent transmission. A distributed fairness mechanism for this architecture is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integrating asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: a buffer insertion mode for variable-size packets and a slotted mode for fixed-size packets. As a result, this architecture is suitable for a wide range of applications and environments. Concurrent access and spatial reuse permit simultaneous transmissions over disjoint segments of a bidirectional ring and, therefore, can increase the effective throughput by a factor of four or more. The efficiency of this architecture does not degrade as the bandwidth and physical size of the system increase. The combination of a full-duplex ring, spatial reuse, a reliable fairness mechanism, and the exploitation of recent advances in fiber-optic technology are the basis for the Metaring network architecture.>

A high-speed network is a new environment motivated by recent advances in transmission technology.The highspeed environment requires that the network node operate (fast) based solely on local information (at least most of the time).This fact implies properties that are much different than those existing in current architectures and algorithms for traditional large-area networks.The new environment poses new challenges for the network architect and the algorithm designer.In this paper we present principles of operation for the basic control functions of a high-speed nelvrorP with an arbitrary topology, we then suggest a design of such a network.In the architecture we design, on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure no loss, fair access to the network, no deadlocks and self-routing.The switching over this network requires only a single buffer on each side of the full-duplex links.The transmission via the receiving buffer can be "cut through", i.e., the incoming packet can be sent to the next link before the entire packet has arrived (unlike "store-and-forward").A dynamic self-routing technique is implemented, in which the packet header contains only the destination identification when it leaves the source.This information is sufficient for reaching the destination, not necessarily on the same route each time, and to overcome congestions and failures.All these properties are implemented in a distributed manner.The system is asynchronous and designed for transmission of variable size packets.

A novel coding scheme for bit synchronization, the conservative code, is presented and analyzed. Each codeword is characterized by having a predefined number of transitions, with a known delimiting transition at the end, i.e. the number of transitions is conserved. As a result, it is possible to decode the incoming serial bit-stream without explicitly recovering the receiving clock with a phase-locked loop. Thus, it is possible to receive messages from asynchronous sources without any training period. This code can be extremely useful in communication over a passive optical star. In the analysis, the efficiency or capacity of the code is computed with two additional constraints: limited run-length and balancing. It is shown that this coding scheme is efficient when both constraints are applied. The objective of this analysis is to show that the additional constraints imposed on the encoding do not cause a significant reduction in its efficiency. The design of a serial electronic interface is described. Its goal is to maximize the interface bandwidth (greater than 1/Gb/s with GaAs technology), which is usually the bottleneck of an optical communication system. It is achieved by reducing the critical timing path to one flipflop and one NOR gate, and by having a hierarchical interface design.>

A technique is described for constructing a fault-tolerant global clock in a point-to-point distributed system with an arbitrary topology, which constitutes a wide-area network. It is assumed that the network is constructed of optical links with very high transmission rates. The approach used is to generate a global clock from the ensemble of the local transmission clocks, and not to synchronize these high-speed clocks directly. The steady-state algorithm which generates the global system clock is executed in hardware by the network interface of each node. As a result, it is possible to estimate accurately intermodal delays and thereby to achieve a much tighter synchronization than with other methods. The basic synchronization time step is proportional to the error or uncertainty in the measurement of the end-to-end network delay rather than to the actual value of the end-to-end network delay. Node and network models are presented, and the synchronization condition is defined. The synchronization algorithm, its bound, and its correctness proof are presented. A procedure is described for detecting and isolating a faulty component, while maintaining the integrity of the global clock.>

The optical hypergraph is a novel network architecture in which each edge of the hypergraph is a multiple-access broadcast medium constructed as a passive optical star coupler. Access to each net (edge) is time-slotted, and the system maintains global slot synchronization. The integration of voice into the system is done by reserving time slots in a periodic manner. A packet which contains several voice parcels from different phone conversations is transferred in these slots. These parcels may have different destinations on the optical net. As a result of the global end-to-end synchronization, the delay from the source to the destination is a known constant, with accuracy of plus or minus half a time slot. In the analysis, it is shown that the system improves its operation as the communication bandwidth increases. In other words, the algorithms and protocols improve in performance as the communication bandwidth increases. Two criteria are used to exhibit this phenomenon: (i) the utilization efficiency and (ii) the end-to-end delay.>