Accurate link latency information is essential for various traffic engineering problems, such as routing design and network diagnosis. However, due to the routing constraints, link latency measurement is still a challenging problem in hybrid software-defined networks (SDNs) and little literature has been found in this field. Due to cost, a hybrid SDN composed of conventional routers and SDN switches will exist for some time to come, which shows the necessity and the urgency to address this problem. In this paper, we investigate this link latency measurement problem in two different scenarios: 1) the conventional routers can only support the shortest path routing protocol, and 2) the conventional routers can support source routing protocol. For both of these scenarios, we show how to deploy a minimum number of monitors and how to construct measurement paths between monitors to measure all the link latencies. Several algorithms are presented to solve these problems and the evaluations on different topologies prove the superiority of the proposed methods.

Accurate link latency information is required for solving many traffic engineering problems, such as congestion avoidance routing and load balancing. Many link latency measurement schemes have been proposed for Software-Defined Networks (SDNs), and many of these require the SDN controllers to inject and remove entries into and from flow tables dynamically. If done frequently, this process can generate a large amount of traffic overhead and consume a lot of processing and computation resources. In this paper, we present a link latency measurement scheme, where entries for latency measurement are already embedded inside flow tables. The main challenge in designing such a scheme lies in how to select measurement paths that can minimize the number of entries added to the expensive TCAM-based flow tables and the amount of traffic generated for latency measurement. We present solutions that can minimize both in this paper.

An NoC (network on chip) constructed with silicon photonic microrings can be implemented with CMOS technology and integrated with processor cores on the same die. Each microring in the NoC has two switching states, one consuming significantly less power than the other. Different routing schemes can lead to different numbers of microrings in the high-power consumption state, and result in different power consumptions for the NoC. In an earlier work, a looping-based routing algorithm was proposed which exploits the different power consumption characteristics of the two switching states of a microring so as to minimize the power consumption of a Benes-type NoC; but this algorithm cannot provide an optical solution. In this paper, we will show the necessary and sufficient conditions for finding the optimal solution for a Benes-type NoC. We also present a new routing algorithm. Compared with the algorithm of the previous work, the new algorithm can reduce the number of microrings in the high-power-consumption state by as many as (n - 2) · 2n-2in a 2n× 2nBenes-type NoC for certain interconnection patterns.

In many survey-free Wi-Fi indoor localization systems, including the Adaptive indoor Wi-Fi Positioning System (AWPS) we proposed earlier, there is a need to associate unlabeled measurements to a floor plan. In this paper, we address the problem of how to associate a topological radio graph generated by crowd-sourced RSS measurements to an isomorphic Euclidean graph representing the physical space which may come from a geographic information system (GIS) or through automatic image analysis of a paper floor plan. We introduce the concept of Minimum Symmetric Structures (MSS) and Co-rooted Congruent Structures (COCS) as new ways of characterizing automorphism which prevent unambiguous association, and present a structure analysis algorithm for detecting these structures. Then, we derive rules on the number and locations of markers, or RSS measurements with location labels, needed for resolving the automorphism. Applying the analysis proposed in this paper to hypothetical floor plans as well as floor plans used in AWPS and other existing systems, we will demonstrate that often very few location labels are needed in a SLAM system.

Accurate traffic matrix estimation is critical to solving many networking problems, such as routing and network provisioning, etc. This task in a traditional IP network is tackled with link load measurements. But the accuracy of such an approach is low because the underlying system of linear equations governing the traffic estimation problem is highly under-determined in this approach. A software-defined network (SDN) provides measurements of more types of flows, and thus opens up new opportunities for tackling the traffic matrix estimation problem. Furthermore, the controller of an SDN can dynamically install flows in the flow table of an SDN router for traffic measurement. But there is one constraint: the number of entries in a flow table for traffic measurement is limited because the flow table in an SDN node is usually constructed with expensive ternary content addressable memory (TCAM) devices. How to use the limited number of entries in a flow table for traffic measurement is a challenging task in SDNs. In this paper, we present a new framework for solving the traffic matrix estimation problem in an SDN-based IP network. An important feature of the proposed framework is that any flow added to the flow table of an SDN router can increase the rank of the underlying equations governing the traffic matrix estimation problem. This greatly improves the utilization efficiency of TCAM entries for traffic measurement. Detailed performance evaluation given in this paper demonstrates that the proposed approach can achieve significant performance gains over other approaches.

Mobile Cloud Computing (MCC) has draw extensive research attentions due to the increasingly demand on the energy consumption and execution time constraints on Mobile Devices (MDs). MCC has been well investigated in the scenarios when workload is offloaded to a remote cloud or a cloudlet. However, in those scenarios, infrastructure is required to provide connections between MDs and the cloud/cloudlet. To facilitate MCC for environment when infrastructure is not available, Ad-hoc MCC which allows MDs to share and process workload coordinately is discussed [1]. In this study, the detailed resource allocation problem in Ad-hoc MCC, including how to assign tasks to MDs, how tasks are executed on each MD, and how to arrange task and task result return transmissions so that interference among different MDs can be avoided are carefully studied. Since the problem is NP-hard, a heuristic algorithm is then introduced. As shown in the evaluation section, when no infrastructure is available, compared with the case when an application is executed solely on a single MD, the proposed algorithm can reduce an application's response time significantly.

In spatial time division multiple access wireless mesh networks, not all links can be activated simultaneously, as links scheduled for transmission must satisfy the specified SINR requirements. Previously, slot assignment has been done on a link basis, where a set of links is selected for transmission in a given slot. However, if selected links are in deep fade or have no traffic to transmit, the slot is wasted. Thus, a node-based scheme was proposed, where a set of nodes is selected for transmission. Which link to be used by a node depends on the links' instantaneous traffic load. Although this allows us to exploit multi-user diversity, it creates a planning discrepancy: slot assignment is designed based on long-term channel statistics, but scheduling on short-term channel fading conditions. Consequently, the performance gain of the node-based scheme is not consistent: it is marginal under certain scenarios. To avoid the design discrepancy, we develop a new slot-assignment and routing framework in this paper. The new approach incorporates short-term channel fading statistics to optimize the long term slot assignment, routing and scheduling simultaneously. Hence, multi-user diversity can be exploited more efficiently. Not only is the performance gain of the resulting system significant (can be as much as 64% higher throughput than the scheme introduced by Chen and Lea), it is also less topology dependent compared with the one by Chen and Lea.

In this paper, we describe a framework for designing a discrete-bandwidth nonblocking network. The theoretical foundation of the framework combines theories from both networking and switching. While the conventional Clos theory must assume a particular topology, the new theory allows us to design a nonblocking network with an arbitrary topology. Thus it can be considered as a generalization of the Clos theory. In addition to the design of WDM or SONET networks, applications such as grid computing and supercomputing can also benefit from the results developed in the paper.

Real-time group communication is fundamental to many emerging interactive multimedia applications. Communication among the group members is N-to-N in that any number of group members may generate data and control packets destined to all the other members at the same time. Redundancy Reduction Gossip (RRG) is a highly effective real-time N-to-N dynamic group protocol over the Internet and demonstrates churn and sporadic traffic coping capability. In this paper, a peer-to-peer (P2P) real-time group communication protocol based on RRG is proposed for Content-Centric Network (CCN). A highly effective synergy between RRG and the capability of CCN is exploited. Effects include connectivity expansion, traffic reduction and latency improvement. The proposed protocol allows information distributed from an arbitrary number of dynamic sources in a group. It has low latency and minimal membership maintenance.

For indoor location estimation based on wireless local area networks fingerprinting, how to reduce the offline calibration effort while maintaining high location estimation accuracy is of major concern. In this paper, a hybrid generative/discriminative semi-supervised learning algorithm is proposed that utilizes a large number of unlabeled samples to supplement a small number of labeled samples. This hybrid method allows us to combine the modeling power and flexibility of generative models with the superior performance of discriminative approaches. Other related issues, such as learning efficiency enhancement and distribution estimation smoothing, are also discussed. Extensive experimental results show that our proposed method can effectively reduce the calibration effort and exhibit superior performance in terms of localization accuracy and robustness.

It is well known that without admission control, network congestion is bound to occur. However, to implement admission control is difficult in IP-based networks, which are constructed out of the end-to-end principle, and semantics of most major signaling protocols can only be interpreted at the edge of the network. Even if routers can perform admission control internally, the path computation and the state updating activities required for setting up and tearing down each flow will overwhelm the network. A new QoS architecture, called a nonblocking network, has been proposed recently, and it requires no internal admission control and can still offer hard QoS guarantees. In this architecture, as long as each edge node admits not more than a specified amount of traffic, the network will never experience link congestion. For multicast networks, the main problem with this approach is low throughput. Conventional tree-based multicast routing algorithms lead to a throughput so low that the nonblocking concept is rendered impractical. In this paper, we show how network coding can solve this problem. We demonstrate that a nonblocking unicast network and a multicast network share the same optimal paths, and that a nonblocking multicast network with network coding can admit the same amount of traffic as a nonblocking unicast network. The above conclusions apply to explicit-routing (MPLS-like) and shortest-path routing (IP-like) networks.

Interference management is a fundamental issue of a wireless network. In this paper, an interference management scheme based on partial loading is presented. The advantage of partial loading is that it does not require any protocol changes and renders an easy implementation. The partial loading scheme can be combined with other interference management techniques. In this paper, we present various partial loading schemes and evaluated their performances. These schemes divide the total channels into subgroups. By intelligently select the loading probability for each subgroup, we show that the performance, in terms of coverage and spectrum efficiency, of the network can be greatly improved. An analytical model is developed in the paper to verify the performance gains of these proposed partial loading schemes.

Routing with QoS guarantee has been studied extensively for wireless mesh networks. While most of previous research assumes a static and known traffic demand, this assumption often does not hold in a real network. Oblivious routing has been proved an effective approach to tackle the routing and QoS problem when traffic demand uncertainty exists. In this paper, an oblivious-routing based QoS architecture, called a nonblocking network, is proposed to guarantee hard QoS in wireless mesh networks. In this architecture, as long as each edge node admits traffic no more than a specified amount, the network will never experience link congestion. The main difficulty in designing such a network is to find the optimal routing that can maximize the amount of traffic admissible to the network. We develop analytical models to find the optimal routing schemes for both unicast and multicast networks. For multicast networks, we show that if the network uses network coding, the optimal solution to the multicast routing network problem can be solved with linear programming. The analytical results indicate that our optimal QoS routing schemes perform much better than traditional shortest tree based multicast routing algorithm.

The nine papers in this special issue focus on recent advances in autonomic communications. This issue addresses four areas in which autonomics play a central role: network architectures, traffic management, monitoring, and resource management.

Wireless localization has drawn significant attention over the past decade and the received signal strength (RSS) based localization scheme provides a low-cost, low-complexity and easy-implementation solution. When the statistics of the RSS measurement error is known, the Maximum Likelihood (ML) estimator is asymptotically optimal. However, due to the nature of the localization problem itself, the formed ML estimator is nonconvex, causing the search for the global minimum very difficult. In addition, its performance highly depends on the initial point provided if a local optimization method is applied to find the solution. To circumvent this problem, we apply the Semidefinite Programming (SDP) relaxation technique to the RSS-based localization problem. After reformulation and relaxation, we finally form a convex SDP estimator. A superior property of a convex estimator is that the solution is not affected by the initial point provided since any local minimum is also its global minimum. The Cramer-Rao Lower Bound (CRLB) is then derived as a benchmark for the performance comparison. Simulation results show that the proposed SDP estimator exhibit excellent performance in the RSS-based localization system and it is very suitable for the case when there are only very limited base stations hearable.

This paper presents GConf, a peer-to-peer Gossip-based delay sensitive N-to-N information dissemination protocol, intended for applications such as real-time multiparty conferencing. Through 3-way gossip-based exchanges with randomly selected peers, information frames can be spread throughout the whole community within a delay of 1.5 round-trip-times. The non-delivery probability can be improved exponentially as a function of the peer fanout. Performance evaluations based on a mathematical model and simulations are presented.

The eight papers in this special issue focus on delay and disruption tolerant wireless communication. The papers cover routing and network coding for spare mobile ad hoc networks, cross-layer design for sensor networks, satellite communication, and DTN architectural issues.

Abstract We study necessary and sufficient conditions for multirate, multicast, and wide‐sense nonblocking (WSNB) log 2(N, m, p) networks. We show necessary and sufficient conditions for different values of m. The results allow us to find a speedup requirement in the network for a given traffic load. We also present a sufficient condition for making the network nonblocking when a limit is imposed on the multicast group size. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

In this paper we explore the optimal weight setting to maximize QoS traffic admissible to a hop-by-hop routing network (such as the Internet). We try to answer the following questions: (1) How much ingress and egress traffic can be admitted to a hop-by-hop routing network (such as the Internet) without causing congestion of any link, and (2) what is the optimal link weight setting that can maximize the amount of traffic admissible to the network? We first present a mixed-integer programming formulation to compute the optimal link weights that can maximize the ingress and egress QoS traffic admissible to a hop-by-hop routing network. We then present a heuristic search algorithm to find the optimal weights. The heuristic algorithm has a performance comparable to the optimal link weights, but its computation complexity is much lower.

We investigate the impact of mobility on downlink scheduling in multi-user multiple antenna systems. We formulate several different designs of the cross-layer scheduler and evaluate how their throughput and fairness performance change as user mobility varies. Our model captures both the physical layer and system-level parameters affected by mobility. The results have shown how sensitive the different scheduler designs are with regard to user mobility and provide new insights into how the scheduler should be designed according to mobility conditions.

The seven papers in this special issue focus on developments in the area of vehicular networks.

In this paper, we explore new optical time-division multiplexing (OTDM) ring architectures. The objective of our study is to achieve high space-reuse efficiency of each time slot without using time-slot interchanges, which are expensive and difficult to implement in the optical domain. Although a TDM slot is often compared to a wavelength channel in a wavelength-division multiplexing (WDM) network, we show that the intrinsic propagation delay in an OTDM network will lead to a phenomenon, called a slot cycle in the paper, that has no counterpart in WDM networks. By exploring the concept and the algebraic relationship between the frame size and the total propagation delay of the ring, we discover a novel OTDM ring architecture that achieves a high space-reuse efficiency without using time-slot interchanges. The equivalent of this architecture in the WDM domain can only be achieved with the use of many wavelength converters. We also study the efficiency of the architecture based on different types of traffic demand models in the network.

Optical TDM allows multiple traffic streams to share the bandwidth of a wavelength. This paper presents a framework for determining the capacity and routing strategy needed to establish different logical topologies on an optical TDM ring network with propagation delay but no Optical Time Slot Interchange (OTSI); OTSI requires optical buffering which is not practical at the current time. We show that an optical TDM ring is characterized by a parameter called cycle length. The impact of the cycle length on the capacity of a bi-directional optical TDM ring is evaluated and joint routing and time-slot assignment strategies are developed.

Optical-switching technologies exhibit many characteristics that the electronic-switching technologies do not have. One such characteristic lies in switching states. An electronic crosspoint, having open and close as its two switching states, only allows one traversing signal. But an optical-switching crosspoint, such as a directional coupler or a microelectromechanical systems mirror, usually allows two traversing signals. This paper studies how to exploit the characteristic to expand the switching capabilities of an optical switch, and shows new ways of building more crosspoint-efficient rearrangeable nonblocking switches. We show that an optical 2n/spl times/2n rearrangeable nonblocking switch can be created by cascading only two n/spl times/n optical crossbars.

Buffer minimization is an important design issue in optical circuit switching networks because of the high cost of optical buffers. In this paper, we show how to design routing strategies that can reduce buffer requirement in such networks. We propose two classes of buffer-efficient routing schemes and compare their performance in terms of complexity, buffer requirement and blocking probability.

The memory used in high-speed switching often needs to be customer designed and is expensive. As the link speed approaches 10-G and 40-G rates, reducing the memory requirement can translate into significant cost saving. In this paper, we study an optimal memory partition scheme between ingress ports and egress ports of a crossbar-based switch. We show how the optimal partition between ingress and egress ports can save memory, and how the partition is affected by the queue structure in the switch. Compared with the 50-50 partition, the optimal partition scheme can reduce buffer requirements by at least 30%.

Optical TDM (O-TDM) networks can provide a finer bandwidth granularity than WDM networks, and will play an important role in future all-optical networks. Since optical buffers are expensive, a small buffer size is characteristic of O-TDM systems. This paper analyzes the problem of routing and time-slot assignment in O-TDM networks. The results lead to the proposal of a Dijkstra-like shortest-path routing scheme that intends to maximize the performance of an optical network with a small number of optical buffers. Performance evaluation of the proposed scheme is also presented.

We show how conventional call admission needs to be modified in CDMA networks to accommodate mobility accurately. We evaluate the impact of mobility on several important system performance and design parameters of CDMA networks. This includes (1) the maximum system capacity (2) the best call admission control thresholds, and (3) the tradeoff between the new call blocking probability and call dropping probability.

Optical time-division multiplexing (O-TDM) networks can provide a finer bandwidth granularity than wavelength-division multiplexing networks, and will play an important role in future all-optical networks. Since optical buffers are expensive, a small buffer size will be the characteristic of O-TDM systems. This paper analyzes the problem of routing and time-slot assignment in O-TDM networks. The results lead to the proposal of a Dijkstra-like shortest-path routing scheme that intends to maximize the performance of an optical network with a small number of optical buffers. Performance evaluation of the proposed scheme is also presented.

The maximum residual energy path (MREP) routing has been shown an effective routing scheme for energy conservation in a battery wireless network. Past studies on MREP are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgement is required, or if the ad hoc network has deployed the energy-conservation mode (sleeping mode). When backward energy consumption is present in transmission (i.e. the receiving end consumes energy), finding an MRE path that has enough energy for finishing the transmission has become NP-hard. We show in this paper a Dijkstra-like heuristic algorithm for finding the optimal MRE path. The new algorithm guarantees that once a path is found, it will have enough energy to finish the transmission task, while the original MREP algorithm, ignoring the backward energy costs, cannot guarantee that. We also show another routing technique that can extend the system life. The technique works for both MREP-based routing schemes.

This paper presents cost-based QoS routing and compares its performance with the commonly used widest-shortest-path routing. The advantages of cost-based routing are demonstrated in two major areas. First, it is stable under heavy-loaded conditions. Second, it requires a lower state-update overhead and is more robust to the inaccuracy of state information. The concept presented in the paper can be applied to any reservation-based QoS approach - like IntServ or MPLS type networks.

We show in the paper that mobility and capacity can be viewed as equals, and develop an analytical model to study the conversion process between the two. The goal of the study is to design a network with a free convertibility between mobility and capacity. Such a network can support more users because whenever user mobility drops, it can convert that change into a capacity gain.

The capacity of a switch is built out of two factors: space parallelism and speedup. A switch has space parallelism if more than one input port can transmit simultaneously. Speedup is the ratio of the switch's internal link speed over the incoming link speed. An input-queuing switch uses only the first factor (space parallelism), and a share-medium or a share-memory output queuing switch uses only the second factor (speedup). However, to build a large switch, both factors are normally used. A large switch's capacity can be built with less space parallelism (the space factor), but more speedup (the time factor), or vise versa. Buffers are needed at both the input and the output ports. In this paper, we show how to divide the buffers between the input and the output queues and how the optimal division is affected by the (space, time) combinations.

We introduce the notion of photonic circuit switching (PCS) networks and investigate the routing and time-slot assignment (RTA) problem for such networks. PCS is analogous to TDM circuit switching in electronic switching networks. It provides a way for sub-division of the capacity of a wavelength channel in optical networks. By finding routes and assigning time slots carefully, the optical buffering requirement in such networks can be greatly reduced.

One common theme in designing optical switches is crosstalk reduction. Although this is a device level problem, it can also be solved at the system level. One approach is to use more switching elements. This is the so called "space approach". In the paper we show how to take advantage of the multiple-wavelength characteristic of a WDM signal to reduce crosstalk without adding more switching elements. Although we use directional-coupler photonic switching technologies for our discussion, the principle can be used for any photonic switching technology.

As the deployment of wavelength-division multiplexing (WDM) transmission facilities speeds up, the next step is to add cross-connects to route WDM signals. Electro-optical directional couplers (DCs) are well suited for the task since they can pass WDM signals. However, DCs suffer an intrinsic crosstalk problem. Removing crosstalk has been an important design issue. In this paper, we show how to take advantage of the multiple-wavelength characteristic of a WDM signal to reduce crosstalk in a DC-based photonic switching system.

No abstract available.

Directional-coupler (DC)-based switching systems can switch signals at the rate of several terabits per second. Such switches can also transmit signals with multiple wavelengths simultaneously. Despite these advantages, DCs suffer from an intrinsic crosstalk problem that must be overcome in building a robust switching system. In this paper, the principles of constructing strictly nonblocking DC-based photonic switching systems under various crosstalk constraints are explored. We demonstrate how crosstalk adds a new dimension to the theory of switching systems. We find the sufficient nonblocking condition for photonic networks under crosstalk constraints and demonstrate that some well-known nonblocking networks can tolerate a stricter crosstalk constraint while retaining their hardware complexity. The theory developed in the paper can guide us in making the design tradeoff between the level of crosstalk and the amount of hardware.

Directional couplers are electro-optical switching devices that are capable of switching multiple wavelength signals. Once the state of a coupler is set up, optical signals can pass through the coupler with a rate of tera bits per second. A directional coupler-based photonic switching system however, suffers from the intrinsic crosstalk problem. This shortcoming has been the most limiting factor in building a large switching network of this kind. It has been shown that by using more hardware (couplers) we can reduce the number of crosstalk-generating couplers along the path of a connection in a Banyan-type switching system. We explore the wavelength approach to achieve this task. We show that if there are two wavelengths available, the number of couplers suffering the first-order crosstalk can be reduced to zero while the total number of couplers will remain the same as a network without any crosstalk constraint.

Photonic switching systems based on directional coupler switching elements can switch multiple-wavelength signals at the speed of tera-bits per second. Crosstalk is an intrinsic shortcoming of the directional couplers which must be overcome in the construction of an efficient switching system. Therefore, it adds a new dimension to the design of the networks based on directional couplers. We explore the principles of constructing strictly nonblocking directional coupler-based photonic switching systems under various crosstalk constraints. We show that a lower level of crosstalk can be achieved at a cost of additional hardware. We also introduce a rule that limits the routing of the new connections based on the state of the switching network. Such a rule can significantly reduce the undesired crosstalk and the hardware complexity of the strictly nonblocking network at the same time. The resulting network is therefore categorized as a wide-sense nonblocking network.

Directional couplers are capable of switching signals with multiple wavelengths. They are the ideal technology for building light-path switches to configure wavelength division multiplexing (WDM) transmission facilities. This technology, however, has a major constraint: crosstalk. Design of a strictly nonblocking directional coupler-based photonic switching system under a specified crosstalk constraint has previously been studied. The results indicate that a lower level of crosstalk can be achieved at a cost of some extra amount of hardware. In this paper, we show that if a simple rule is followed in setting up the connections, both the amount of hardware for nonblocking networks and the connection setup time can be greatly reduced. The resulting networks thus belong to the class of wide-sense nonblocking networks.

One of the elements missing in most literature related to power control is mobility. Without it, the performance of a power control scheme and its convergence cannot be reliably predicted. In the paper we use random walk to model mobility. Combining the mobility model with a conventional CCI analysis, we study linear power control in a more dynamic environment.

Quantization, a process to restrict a continuous variable to a discrete one, has been a powerful technique for many fields of engineering. We show how to use the concept of quantization to compute the cost function of a Markov decision process (MDP)-based routing and admission policy in a broadband network. In the discussion we assume a multirate circuit switching environment.

Current cellular systems are based on the concept of a cell. Although the cell allows channel reuse, it has also become a metaphor for channel confinement and leads to the thorny problem of handoff and call dropping. The problem will get much worse as cellular services move toward high-speed and multirate. This paper presents a new wireless network architecture: called MAWCC for its main characteristic-Macrodiversity Without Channel Confinement. In MAWCC, mobility equals capacity. The convertibility between the two (capacity and mobility) makes MAWCC a total departure from a conventional wireless network. It offers more options for tackling the issues of mobility, handoff, and call dropping.

Two implementation styles (buffered and unbuffered) have been used for constructing multistage interconnection networks for ATM switching. Conventional studies have shown that an unbuffered network, while having a simpler design, produces a lower throughput than a buffered network. But most of these studies, based on the assumption that each cell is routed independently (i.e. per-cell routing), ignored the out-of-sequence transmission problem of a buffered network in a virtual-channel environment. One way to keep the packet sequence for a buffered network without adding additional hardware is to fix the path for each virtual channel. We compute the throughput of this approach in designing nonblocking networks and compare it with that of the unbuffered approach. The base of our comparison is log/sub d/(N,e,p) networks. The results show that a fixed-path-routing buffered network will have a throughput even lower than that of an unbuffered network.

If a network supports only certain rates, we say its bandwidth is quantized. In a quantized-bandwidth network, a customer may be forced to use the next higher rate if the requested rate is not supported. The result is a higher blocking probability and a lower throughput. The throughput loss due to quantization is called the quantization loss, and its related issues are the focus of this paper. We show that the quantization loss is insensitive to capacity scaling and traffic-loading. More important, it is hardly as large as is thought. Even for a network, such as ATM, intending to support a continuous bit rate, bandwidth quantization can be a powerful tool for states reduction. States reduction is shown to be indispensable for solving many problems, such as routing and capacity planning, of a broadband network.>

Previously, a new class of switching networks, called Log/sub 2/ (N, m, p) networks, has been created for high-speed switching systems. The basic switching element used is a 2/spl times/2 crossbar. Although it is generally true that different sizes of switching elements can be used as the basic building block for the same design paradigm, the results are quite different. The sizes of the basic building block are often a trade-off among many factors such as combinatorial power, computation time of routing, fault tolerance, hardware complexity, and growth rate of a network. The authors study the design principle for Log/sub 2d/ (N, m, p) systems in this paper where d/spl ges/1.>

A multicast broadband packet switch architecture is proposed. It has the following attractive features: little extra cost compared to a unicast switch, fast packet duplication, and easy addition and deletion of calling parties. A simulation study of this multicast system is presented to verify its performance.>

An algorithmic method for constructing protocol converters to achieve interoperability between networks that implement incompatible protocols is presented. The converter constructed using this approach does not cause unspecified receptions or deadlocks if the original protocols are safe. The method is guaranteed to generate a valid converter if one exists for the given protocols, with the conversion requirements defined by an ordered mapping set. Since the approach consists of six algorithms, it can be automated, thereby substantially reducing the complexity of the converter construction process. A protocol conversion example involving incompatible protocols is used to illustrate the method.>

The authors indicate that the number of rates supportable in an asynchronous transfer mode (ATM) broadband network has to be limited unless a network is acceptable without knowing its grade of service. The quantization of the channel bandwidth, given the traffic arrival rate as a function of requested bandwidth, is considered. Capacity sharing models in ATM networks are presented. The calculation procedure for blocking probability which will be affected by the quantization problem is described. A class of control methods that can render a product-form solution is introduced. The results indicate that there is little performance difference between a quantized channel and a continuous-rate channel as the level of quantization exceeds ten.>

Conventional bounds for the maximum throughput of an unbuffered banyan network and its topology equivalents are based on the parallel path setup (PPS) assumption, i.e. paths are set up simultaneously. But the bounds derived under the PPS assumption can be surpassed with a slight variation on the path setup scheme. The authors study the maximum throughputs of an unbuffered banyan network and its topology equivalents in an incremental path setup (IPS) environment. The results represent the ultimate bounds for the maximum throughputs of unbuffered banyan networks. Although the exact analysis of this problem involves a combinatorial explosion, an approximate analysis is given in this work to verify the simulation results.>

The design of several unbuffered self-routing networks for wideband packet switching is presented. These networks possess many attractive characteristics, including simple node design, simple fault diagnosis, tolerance of faults, tolerance of unbalanced load, and packets delivered in sequence. It is shown, through analysis and simulation, that the maximum throughput of an unbuffered self-routing network is greater for fixed packet lengths than for exponentially distributed packet lengths. This means that the maximum throughput of an unbuffered self-routing network will be different for such applications as ATM (asynchronous transfer mode) and frame-relay, if they do not have the same packet length distribution.>

A class of rearrangeable nonblocking networks is presented. The proposed networks are fault-tolerant, self-routing, and intended for a very-high-speed environment. Self-routing networks have one major problem when applied to switching: they are blocking networks. To solve this problem, two methods have been used to create self-routing rearrangeable nonblocking networks: horizontal cascading (HC) and vertical stacking (VS). The authors unify the two approaches and propose a novel class of switching networks. The proposed design principle allows the best tradeoffs among design parameters such as fault tolerance, hardware cost, and the frequency of rearrangement activities. A study of the frequency of rearrangement activities is also presented.>

A class of self-routing strictly nonblocking switching networks, called the Log/sub 2/ (N, m, p) network, is introduced. The proposed networks are self-routing and have O (Log/sub 2/ N) stages between each inlet-outlet pair. The self-routing capability makes it attractive for high-speed switching; the small number of crosspoints between each inlet-outlet pair also makes the network well suited for many nonlogic photonic switching technologies. The complexity and the fault-tolerant capability of the strictly nonblocking Log/sub 2/ (N, m, p) network are analyzed. To show the merits of the proposed network, the authors compare it to the Cantor network, which is also strictly nonblocking and has similar characteristics.>

It is shown, through analysis and simulation, that the maximum throughput of an unbuffered self-routing network is greater for fixed packet lengths than for exponentially distributed packet lengths. This means that the maximum throughput of an unbuffered self-routing network will be different for different applications if they do not have the same packet length distribution.>

Several attributes of a bipartite graph are exploited in designing switching systems. First, in a network based on bipartite graphs, no two paths are allowed to intersect at a vertex. This attribute is used to design a directional coupler-based photonic switching network with very low crosstalk. Since crosstalk is the most limiting factor in constructing a large directional-coupler-based photonic switching network, crosstalk reduction on the device and architecture levels is an important design issue. Secondly, broadcast, which is an intrinsic property of a bipartite graph (the same is always true with a crossbar representation), is used in designing multiconnection switching networks. Thirdly, it is shown that the nonplanar nature of bipartite graphs makes them well suited for designing three-dimensional free-space-transmission photonic switching systems.>

A class of switching networks is proposed to remove the time and space bottlenecks of conventional RAM-controlled switching architectures. The advantages of these networks, such as tolerance of faults O(log/sub 2/N) stages between each inlet-outlet pair, self-routing capability, easy path hunt, and easy fault diagnosis, and their implementation are discussed. Graph theory is used to construct strictly nonblocking or rearrangeable nonblocking networks that are based on the new architecture.>

A novel class of switching networks has been proposed to remove the time and space bottlenecks in conventional RAM-controlled switching architectures. The proposed networks possess many desirable characteristics for high-speed electronic and photonic switching systems, such as tolerance of faults, O(log/sub 2/N) stages between each inlet-outlet pair, self-routing capability, easy path hunt and easy fault diagnosis. Graph theory provides the basis for the proposed networks. It is shown that the key problem in the construction of this class of networks is related to the coloring problem in graph theory.>

Methods of design directional-coupler-based switching networks with minimum number of crossovers are presented. Also presented is a modular construction scheme that allows large switching networks (with minimum of crossovers) to be built using identical chips containing smaller networks of the same type. The total number of crossovers and the maximum number of crossovers between an inlet-outlet pair have been analyzed in three major self-routing networks. Since many networks are based on these topologies, the results can be applied extensively to the study of many other switching networks.>

A rearrangeable broadcast switching network is proposed. Under the condition that the number of outlets (customers) is much larger that the number of source inlets (video channels), the network normally has fewer switching nodes than other approaches. The approach is based on the decomposition of the multiconnection function into two subfunction: consecutive spreading and routing. I offers modular construction, easy growth, and an easy path hunt. The network is especially suitable for the directional-coupler photonic-switching technology and an implementation based on this technology is presented. The number of crosspoints required for electronic and photonic implementations is compared.>

A new multiaccess protocol is proposed for an integrated voice/data application. The protocol, which is a variation of virtual time CSMA (VT-CSMA), takes advantage of the periodicity of voice packets and possesses a number of important features. With this protocol, voice stations appear to have a dedicated time-division multiplexed (TDM) slot, and the delay of a voice packet is bounded by the length of a frame (defined to be the period between two consecutive voice packets from a voice station). Also, the amount of data added to the channel has little effect on the voice traffic. When silence detection is used, many more voice conversations can be supported without losing the dedicated-slot characteristic. This is in contrast to a movingboundary TDM system where the excessive bandwidth saved by silence detection can only be used for data. The protocol requires no global synchronization and is easy to implement. Simulation results are presented to evaluate its performance.

Banyan networks, as well as many other self-routing networks, have a simple and regular topology, and can be easily diagnosed and maintained. However, like many other self- routing networks, Banyan networks have only one path between each input and output pair. Failures of a single link or node will make many paths unavailable, and certain traffic patterns can cause severe congestion in the networks.

A comprehensive study of the stability and optimization of the infinite population, slotted, nonpersistent CSMA and CSMA/ CD channels is presented. The approach to both stability and performance optimization differs significantly from previous work, and provides a number of new results including robustness in stability and performance in the presence of channel and control parameter variations. It is first shown that both channels are unstable under the usual assumption of random retransmission delay. Pake's lemma is then applied to study the properties of a type of distributed retransmission control which provides stable channels. Basic results are in the form of inequalities which define stability regions in the space of channel and control parameters, and further permit one to specify controls which maximize channel throughput as a function of packet length and CD time with stability guaranteed. The delay versus throughput characteristic for the stabilized channels is derived and used to demonstrate the performance achievable with these channels.