A robustly engineered monitoring and measurement capability provides comprehensive and timely performance information that allows broadband network operators and service providers to observe and proactively respond to events that occur during deployment and operation of their respective networks. As network complexity increases, so do the requirements for monitoring and measurement to ensure the high-quality service to internal and external customers. A methodology for monitoring and measurement of complex broadband networks is presented. This methodology includes a framework and reference architecture, essential metrics categories to refine and focus the collection of information and extensions to support net-centric enterprise systems driven by service-oriented architecture (SOA). Examples of the application of the methodology to complex broadband networks are provided along with suggestions for further work.

Fiber optic transmission media can deliver broadband network performance measurement data at a rate faster than economically available electronics components can process them. Commercial implementations seek to limit the amount of high-speed, high-cost electronics needed to recognize the performance parameters in the bit stream passing a monitoring point. A means is presented here for transforming these finite state recognizers into new machines that perform the same function but operate at slower speed for implementation in reconfigurable hardware. This is accomplished by mapping N-bit sets from the input stream into new symbols that can be processed at rate 1/N while also generating N-bit output symbols. The process is illustrated by example and a time versus space tradeoff analysis is presented.

The authors analyze the reliability of two FDDI computer communication network architectures and make comparisons; these structures are a fault-tolerant dual-homing ring of trees and a failsoft ring of trees. They calculate the probability P[h(s,t)] that two arbitrarily positioned terminal stations (s and t) can communicate by deriving closed-form polynomial expressions for P[h(s,t)] in terms of component failure probabilities. The new expression for dual homing permits efficient quantitative reliability comparisons for networks with an arbitrary number of terminal stations, an arbitrary number of concentrator tree root pairs in the counter rotating dual ring, and varying numbers of ports in the concentrators.>

The authors model the delay-throughput performance of a class of multiple-access circuit-switched ring local area networks that allow multiple messages to be transferred concurrently on the ring. In particular, they model analytically the PLAYTHROUGH protocol under assumptions of uniform and symmetric traffic, infinite buffers, and a first-in, first-out (FIFO) queueing discipline at each station to predict message mean waiting times that adequately approximate waiting times observed through simulation. The queue is analyzed at an arbitrary station as a M/G/1 vacation system having a Bernoulli schedule with parameter p. Expressions for the vacation duration and p are derived in terms of service times and competing traffic intensities on PLAYTHROUGH rings. The vacation period is modeled as a series of subvacations because the server is allowed to take multiple subvacations when the queue is nonempty. Application of this modeling strategy is shown to provide good agreement between analytical predictions and simulation results. The performance of this class of networks is compared with that of token rings.>

The reliability of three fiber distributed data interface (FDDI) network topologies is examined. The three interconnection topologies considered are a tree, a double ring, and a ring of trees. The reliability measure is terminal-pair reliability in which the probability P(h(s,t)) that two arbitrarily positioned terminal stations (s and t) can communicate with each other is calculated. For the three FDDI network topologies considered, closed-form expressions are obtained for worst-case reliability as a function of the stations' positions. The expressions are used to optimize the number of ports in and the topological interconnections of the wiring concentrators in order to achieve highest reliability for a given number of stations.>

Analytical models are presented and shown to approximate adequately simulation results for average message queuing time, service time, and control frame round trip time on ring-topology local area networks. These LANs use a PLAYTHROUGH protocol, a data link layer medium access control protocol that achieves concurrent transfer of multiple messages of arbitrary length. The analytical predictions of data message service time and control frame round trip time are used in a queuing system model of average message waiting times versus throughput for this class of multiserver circuit-switched ring under assumptions of uniform and symmetric traffic and a shortest outbound distance first service discipline at each node. The analytical models are validated using simulation results. The analysis includes both the effects of competing traffic originating at other nodes on the ring and the effects of the medium access control mechanism overhead on the waiting times experienced by messages arriving at an arbitrarily chosen node.>

A comparison is made of the reliability of several fault-tolerant single- and double-ring networks. The reliability measure adopted is the probability that all operative nodes can communicate (P(C)). Although computing P(C) has been proven an NP-hard problem for general networks, closed-form expressions for P(C) are presented for several ring network structures. These networks include (1) the basic single ring, (2) a single ring with nodal bypass switches, (3) a star-shaped ring, (4) a dual ring, (5) a double ring, (6) a double ring with bypass switches, and (7) a double ring with both nodal-bypass and link-reversing switches. The expressions for these seven rings are evaluated under varying failure-probability assumptions, and reliability comparisons are made.>

The authors model delay-throughput performance of high- and low-priority message transfer on PLAYTHROUGH rings and compare analytical approximations to simulation results. Both analytical and simulation results show that high-priority messages gain rapid access to the ring independently of low-priority traffic intensity. The analytical model predictions for both service time and queueing time are in good agreement with simulation results for both priority classes. The models presented are completely analytical and do not rely on curve fitting of simulation data to predict message waiting time.>

The authors consider the reliability of fail-soft ring networks using as a measure the probability that all operative nodes can communicate P(C). Although computing P(C) is in general an NP-hard problem, it is shown that, for ring networks, closed-form expressions can be derived in terms of the failure probabilities of nodes, links, and switches (the configuration components used in attempts to achieve fail-soft operation of the rings). The authors derive closed-form expressions of P(C) for five simplex rings: (1) the basic unidirectional ring, (2) rings with nodal bypass switches, (3) rings with both bypass switches and a standby ring, (4) rings with self-heal switches, and (5) star-shaped rings. The expressions for these five rings are evaluated under varying failure probability assumptions, and reliability comparisons are made.>

The authors present analytical models to approximate average message queueing time, service time, and token round trip time on ring topology local area networks that use a Playthrough protocol. Playthrough's data-link-layer protocol uses a continually circulating control token, source removed update control messages, and destination-removed data messages to achieve concurrent transfer of multiple messages of arbitrary length. The models of data-message service time and token round trip time are used in a queueing system model for average message waiting time in this class of multiserver circuit-switched ring. The collection of analytical models is shown to adequately approximate simulated queueing times for messages transmitted using a shortest-outbound-distance-first queueing discipline. This analysis differs from earlier approximations in that it includes the effects of both bridge traffic and downstream blocking traffic on the waiting times experienced by messages arriving at an arbitrary node.>

For the convex polygon P having n vertices entirely contained in a convex polygon K having m vertices, an optimal algorithm with running time O(n + m) is presented to compute and name regions in the boundary of K from which it is possible to illuminate the exterior of P. It is also shown that this illumination region algorithm can be used to improve the worst case O(nm) running time of a related two dimensional simplex coverability algorithm so that it too has running time O(n + m), and is thus optimal to within a constant factor.

The optimization of read-only memory (ROM) digit dimension for microprogrammed digital computers is considered. The design of integrated injection logic (I2L) multiple valued ROMs is reviewed and designs for corresponding digit-line decoders are presented. Results are presented for determining microoperation groupings that achieve the lower bound digit dimension for multivalued encodings, thus extending to arbitrary radix the theory for the binary case. To illustrate the applicability of these results, the microprogram specifications for previously published optimization examples, as well as that for the Digital Equipment Corporation EDP-9, are shown to have optimal encodings using either three- or four-valued ROMs and either ternary- or quaternary-to-binary decoders, resulting in dramatic savings in device count for the control memory portion of the corresponding machine.

The problem of determining the existence of a simplex which covers a given convex polytope inside another given convex polytope in two-dimensional Euclidean space is shown to be efficiently solvable, and an effective procedure is derived to find a suitable covering simplex or show that none exists. This solution provides a finite algorithm for satisfying a necessary condition in the search for a simplicial (fewest states) stochastic sequential machine (SSM) which either covers or is covered by a given SSM of rank three. Theorems are proved which establish necessary and sufficient conditions restricting the class of corresponding simplexes through which a search must proceed to those whose vertices lie in the boundary of the bounding polytope and whose facet-supporting flats contain certain specified vertices of the polytope to be covered. The problem is then reduced to testing roots in the finite solution tree of a set of second degree algebraic equations against a finite table of linear constraints. An algorithm to generate the constraint sets for the equations to be solved is also presented along with examples of its application.