Rationale, directions, and issues surrounding high speed networks

An examination is made of the rationale behind the need for ever higher networking speeds, the technological developments that are making them possible on a commercial basis, the directions being taken in their development, and the issues surrounding their construction and use. Roadblocks to providing high-speed networks are discussed. The impact of standardization efforts on development efforts is considered, focusing on the HSC channels, the fiber distributed data interface (FDDI), and metropolitan- and wide-area networks (MANs and WANs). Possibilities for future technologies and architectures are described     

Tractable analytic models of demand assignment protocols innetworks with arbitrary buffer capacity

The authors introduce analytic models for evaluating demand assignment protocols in realistic finite-buffer/finite-station network configurations. A solution for protocols with gated and nongated service disciplines that enables one to model demand assignment protocols as found, for example, in local and metropolitan area networks and in satellite communication systems is presented. A tractable approximate solution based on linear equations whose number is also linear is given. It is demonstrated that in addition to its computational efficiency, the presented approach does not incur a significant penalty in terms of accuracy     

Fair Algorithms for Maximal Link Activation in Multihop Radio Networks

We present a distributed algorithm for obtaining a fair time slot allocation for link activation in a multihop radio network. We introduce the concept of maximal fairness in which the termination of a fair allocation algorithm is related to maximal reuse of the channel under a given fairness metric. The fairness metric can be freely interpreted as the expected link traffic load demands, link priorities, etc. Since respective demands for time slot allocation will not necessarily be equal, we define fairness in terms of the closeness of allocation to respective link demands while preserving the collision free property. The algorithm can be used in conjunction with existing link activation algorithms to provide a fairer and fuller utilization of the channel.     

Quadro-Star: a high performance optical WDM star network

This paper proposes an original approach to controlling WDM Passive optical stars, termed queuing arrivals for delayed reception operation (Quadro). In WDM stars the fundamental problem of receiver conflicts leads to severe performance degradation. In current solutions conflicts are prevented by scheduling transmissions or resolved by retransmissions. Both approaches waste bandwidth and involve electronic processing and buffering. The proposed approach is conceptually different in introducing a local conflict resolution mechanism at each receiver incorporating delay lines. This solution brings optical star networks a step closer to an all-optical realization. In addition, it allows an almost total utilization of the channels, as obtainable until now only by TDM control. Contrary to TDM, however, the proposed solution does not suffer performance degradation under heterogeneous traffic conditions and increasing number of nodes. It is thus unique in offering the potential of an all-optical solution providing at the same time high throughput, low delay, small buffer requirements, and robustness under all traffic conditions     

Planar Crossing Numbers of Graphs of Bounded Genus

Pach and Tóth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c ^g dn, for a constant c>1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.     

General Lower Bounds for the Minor Crossing Number of Graphs

There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs and establish a lower bound for the standard crossing number in terms of Randič index.     

Modeling PCS networks under general call holding time and cellresidence time distributions

In a personal communication service (PCS) network, the call completion probability and the effective call holding times for both complete and incomplete calls are central parameters in the network cost/performance evaluation. These quantities will depend on the distributions of call holding times and cell residence times. The classical assumptions made in the past that call holding times and cell residence times are exponentially distributed are not appropriate for the emerging PCS networks. This paper presents some systematic results on the probability of call completion and the effective call holding time distributions for complete and incomplete calls with general cell residence times and call holding times distributed with various distributions such as gamma, erlang, hyperexponential, hyper-erlang, and other staged distributions. These results provide a set of alternatives for PCS network modeling, which can be chosen to accommodate the measured data from PCS field trials. The application of these results in billing rate planning is also discussed     

Scalable WDM access network architecture based on photonic slotrouting

This paper introduces an approach to solving the fundamental scalability problem of all-optical packet switching wavelength-division multiplexing (WDM) access networks. Current optical networks cannot be scaled by simply adding nodes to existing systems due to the accumulation of insertion losses and/or the limited number of wavelengths. Scalability through bridging requires, on the other hand, the capability to switch packets among adjacent subnetworks on a wavelength basis. Such a solution is, however, not possible due to the unavailability of fast-switching wavelength sensitive devices. In this paper, we propose a scalable WDM access network architecture based on a recently proposed optical switching approach, termed photonic slot routing. According to this approach, entire slots, each carrying multiple packets (one on each wavelength) are “transparently” routed through the network as single units so that wavelength sensitive data flows can be handled using fast-switching wavelength nonsensitive devices based on proven technologies. The paper shows that the photonic slot routing technique can be successfully used to achieve statistical multiplexing of the optical bandwidth in the access network, thus providing a cost-effective solution to today's increasing bandwidth demand for data transmissions     

Edge-transitive products

This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph G is edge-transitive if and only if it is vertex-transitive and if G is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph H, or if G is the weak Cartesian power of a connected, bipartite, edge-transitive graph H that is not vertex-transitive.