Predictable network performance is critical for cloud applications and can be achieved by providing tenants a dedicated virtual data center (VDC) with bandwidth guarantee. Recently, the extended Hose model was applied to the VDC abstraction to characterize the tradeoff between cost and network performance. The acceptability determination problem of a VDC with heterogeneous bandwidth demand was proved to be NP-complete, even in the simple tree topology. In this paper, we investigate the embedding problem for heterogeneous bandwidth VDC in substrate networks of general topology. The embedding problem involves two coupled sub-problems: virtual machine (VM) placement and multipath route assignment. First, we formulate the route assignment problem with linear programming to minimize the maximum link utilization, and provide K-widest path load-balanced routing with controllable splitting paths. Next, we propose a polynomial-time heuristic algorithm, referred to as the perturbation algorithm, for the VM placement. The perturbation algorithm is congestion-aware as it detects the bandwidth bottlenecks in the placement process and then selectively relocates some assigned VMs to eliminate congestion. Simulation results show that our algorithm performs better in comparison with the existing well-known algorithms: first-fit, next-fit, and greedy, and very close to the exponential-time complexity backtracking algorithm in typical data center network architectures. For the tree substrate network, the perturbation algorithm performs better than the allocation-range algorithm. For the homogeneous bandwidth VDC requests, the perturbation algorithm produces a higher success rate than the recently proposed HVC-ACE algorithm. Therefore, it provides a compromised solution between time complexity and network performance.

Network virtualization supports predicted network performance for applications by providing tenants with a virtual data center in multi-tenant data centers. The Hose model was recently extended for the virtual network abstraction and deployed in an Oktopus system, which offers the trade-off between cost and network performance. Embedding algorithms based on Oktopus model were well studied in the single-root tree topology. In this paper, we investigate congestion-aware allocation of virtual data centers in multipath networks. First, we formulate bandwidth constraints with linear programming, and provide a complete solution with exhaustive searching. Next, to reduce time complexity, we propose a perturbation algorithm to VM placement, which detects the bandwidth bottleneck of the current virtual machine placement and then adjusts the assignment to reduce congestion. The perturbation algorithm is compatible with both load-balanced and single-path routing algorithms. We compare the performance of the exhaustive searching algorithm and perturbation algorithm with load-balanced or single-path routing by simulations. The perturbation algorithm with load-balanced routing performs close to the exhaustive searching algorithm while significantly reduces the time complexity. Therefore, it offers a good tradeoff between time complexity and network performance.

The wireless fading channels with finite input buffer, Poisson arrivals and two-state Markov modulated service processes (MMSP) are modeled as M/MMSP/1/K queues in this paper. The existing performance analyses of Markov channels are almost all based on the matrix-geometric method, which provides little physical insights for system design. By contrast, we focus on deriving closed-form analytic expressions with physical interpretations in terms of system parameters of interest. Our main contribution is to derive the generalized Pollaczek-Khinchin (P-K) formula of M/MMSP/1/K queue from start-service probability to explore the impact of state transitions on the queueing behavior of Markov channels. This generalized P-K formula reveals that the performance of wireless channels with varying rates can be fully characterized by a newly defined system parameter, called state transition factor β, which clearly explains the reason that the channel with slow state transition rate owns a larger delay for the same channel capacity. In the extreme case when the state transition factor β approaches 0, we show that the channel under consideration can be approximately modeled as an M/G/1 queue. We use the Type I Hybrid ARQ system with a fixed data-rate as an example in this paper to illustrate our results.

This paper studies the performance of Non-persistent CSMA/CA protocols with Exponential Backoff scheduling algorithms. A multi-queue single-server system is proposed to model multiple access networks. The input buffer of each access node is modeled as a Geo/G/1 queue, and the service time distribution of head-of-line packets is derived from the Markov chain of underlying scheduling algorithm. The main results include the complete analysis of the throughput and delay distribution, from which we derived the characteristic equation of network throughput and obtained stable regions with respect to the throughput and bounded mean delay of the Exponential Backoff scheme. We show that the stable throughput region of Exponential Backoff can be obtained even for an infinite population. Since the variance of service time of Exponential Backoff can be unbounded due to the capture effect; thus, its bounded delay region is only a sub-set of its stable throughput region, and the maximum achievable throughput of the network within this region is slightly smaller than the absolute maximum throughput. Analytical results presented in this paper are all verified by simulation.

High-speed photonic switching networks can switch optical signals at the rate of several terabits per second. However, they suffer from an intrinsic crosstalk problem when two optical signals cross at the same switch element. To avoid crosstalk, active connections must be node-disjoint in the switching network. In this paper, we propose a sequence of decomposition and merge operations, called conjugate transformation, performed on each switch element to tackle this problem. The network resulting from this transformation is called conjugate network. By using the numbering-schemes of networks, we prove that if the route assignments in the original network are link-disjoint, their corresponding ones in the conjugate network would be node-disjoint. Thus, traditional nonblocking switching networks can be transformed into crosstalk-free optical switches in a routine manner.

Relational information systems, systems that can be represented by tables of finite states, are commonly used in many areas such as logic circuits, finite-state machines, and relational databases. Decomposition is a natural method of handling complex systems and removing redundancies. It splits a table into a network of smaller, simpler, and interrelated new tables. In order to preserve the original features of the system, any valid decomposition must be lossless. Commutative partitions play an important role in the decomposition. The commutative property is essentially a general algebraic formulation of independency of two partitions. We express the interdependency of two commutative partitions by a bipartite graph, and classify the hierarchical independency structures by the topological property of bipartite graphs. In particular, we show that two partitions are decomposable, the strongest version of dependency, if and only if the associate bipartite graph is uniform. We also adopt Shannon's entropy to quantify the amount of information contained in each partition, and formulate the information-lossless decomposition by the entropy conservation identity. Under the assumption of running intersection property, we show that the general formulation of information-lossless decomposition of relational systems is given by the entropy inclusion-exclusion equality. Applications of these formulations to Boolean logic circuits and relational databases are presented to manifest the information-lossless decomposition processes.

Scheduling packet transmission over wireless links requires quantification of the QoS performance such as delay and packet loss in terms of known system parameters. One of the key issues is how to account for effects of the compensation mechanism on the system's QoS performance. In this paper, we develop a model, namely the two-stage tandem queuing (TSTQ), to characterize the behaviors of packet flows in the system, which applies the wireless fair scheduling with the compensation mechanism. Using queueing analysis, we derive performance parameters: average delay and packet loss rate, in closed-form expressions. These expressions are functions of the source, wireless channel and compensation mechanism parameters. Moreover, the trade-off relationship between delay and packet loss rate is revealed, which is controlled by the parameter of lagging bound. Numerical and simulation results are used to verify the validity of the modeling and analysis work.

We develop a general framework for a novel switch architecture, the cross-path switch, to provide per-session statistical quality of service (QoS) guarantees. With characterizing the service each session receives by service curves, we derive a set of statistical bounds on the delay, backlog, and departure processes at the switch on a per-session manner using exponential bounded burstiness processes as source session traffic models. These bounds show that the service guarantees offered by the cross-path switch depend on the way of token assignment in the central stage of the switch. To provide better performance guarantees, we determine the criteria for designing a token assignment algorithm for the cross-path switch. Also, we quantify the service guaranteed by the cross-path switch with the central stage implemented in optical domain, which is important for the provision of QoS guarantees to each session in semioptical networks.

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.

We take the point of view that a Markov random field is a collection of so-called full conditional mutual independencies. Using the theory of I-measure, we have obtained a number of fundamental characterizations related to conditional mutual independence and Markov random fields. We show that many aspects of conditional mutual independence and Markov random fields have very simple set-theoretic descriptions. New insights into the structure of conditional mutual independence and Markov random fields are obtained. Our results have immediate applications in the implication problem of probabilistic conditional independency and relational database. We obtain a hypergraph characterization of a Markov random field which makes it legitimate to view a Markov random field as a hypergraph. Based on this result, we naturally employ the Graham reduction, a tool from relational database theory, to recognize a Markov forest. This connection between Markov random fields and hypergraph sheds some light on the possible role of hypergraph theory in the study of Markov random fields.

Recently, a quasi-static routing scheme called path switching was proposed for large-scale packet switch systems. The path-switched Clos network is called a cross-path switch. The cross-path switch is capable of supporting multirate and multicast traffic. In this paper, we develop a general framework for it to handle multimedia traffic. We study the statistical behavior of the cross-path switch using exponential bounded burstiness (EBB) processes as source session traffic models. With characterizing the service guarantees by service curves, we derive a set of statistical bounds on the delay, backlog and departure processes at the switch on a per-session basis. These bounds are necessary for providing per-session statistical quality of service (QoS) guarantees in the cross-path switch and achieving high system utilization.

The three-stage Clos network has been studied extensively as a framework for the implementation of large-scale ATM switches. Previously, a quasi-static routing scheme for three-stage Clos networks, called the path-switching scheme, has been proposed by Lee and Lam to achieve low switch complexity and high throughput. We derive in this paper the nonblocking conditions when the bandwidth requirements of traffic are rounded up to simplify switch operation. We discuss the implications of these results for switch implementation. In particular, we show how use the results to build a semi-optical network to reduce switch complexity.

This letter addresses issues related to achieving optimal performance in a class of scalable asynchronous transfer mode switches. In particular, we propose an algorithm to implement a multilevel stop-and-go queueing strategy that integrates the routing and scheduling functions. The algorithm provides a tight delay bound and ensures that desirable traffic characteristics are preserved when cells traverse across the switch.

Previously, a quasi-static routing scheme called path switching was proposed for large-scale ATM packet switches, and a Clos network implementing this routing scheme is called a cross-path switch. In principle, a cross-path switch supports both multicast and multirate traffic and now we add the capacity of supporting per-connection quality of service (QoS) guarantees. In this paper we develop a model to guarantee per-connection QoS in cross-path switches. By characterizing the output traffic, we observe that due to the quasi-static nature of path switching, traffic always becomes more bursty after passing through the cross-path switch. This traffic distortion would greatly degrade performance guarantees at the successive switches along the path. In order to achieve better end-to-end performance guarantees, we propose two regulation schemes for the cross-path switch to reduce distortion. For comparison, their delay bounds are derived. Our results show that with the designed control strategies, both schemes can effectively preserve or even reduce the burstiness of individual traffic streams across the switch with optimal performance guarantees.

In asynchronous transfer mode (ATM) switching systems, switch fabrics must be able to provide not only internally conflict-free paths for cells, but also quality of service (QoS) guarantee for calls. Most research concerning QoS guarantee focuses on the service disciplines of output-buffered switches. However, the scalability of output-buffered switches is rather low because of high implementation complexity. Previously, a new switching implementation called the cross-path switch has been proposed to achieve high throughput and low complexity. This paper addresses fundamental issues related to service disciplines in such a switch that are needed to achieve optimal performance. In particular we propose an algorithm to implement a multi-level stop-and-go queueing strategy that integrates the routing and scheduling functions. We show that our algorithm provides a tight delay bound and ensures that desirable traffic characteristics are preserved when cell traverse across the switch.

In this paper a novel class of network topologies known as the multi-dimensional shuffle-exchange network (MDSXN) is proposed. We show that the well-known de Bruijn graph and hypercube in fact both belong to the same class of graphs represented by MDSXN. The MDSXN is therefore the unification and generalization of the de Bruijn graph and hypercube. We show that members of MDSXN inherit the topological properties of both the de Bruijn graph and hypercube to a varying degree. This allows us to trade-off cost and performance effectively and construct networks which are most suitable for a particular purpose. Examples of applications of MDSXN include structure for switching and multicasting networks, optical network topology, and virtual topology for local and metropolitan area networks.

A generalized non-blocking copy network based on a broadcast Clos (1953) network is proposed. We show that if the set of input connection requests is ordered, the broadcast Clos network is non-blocking and route assignment can be done by using the rank of each connection request. Packet replications and routing are achieved by the generalized interval splitting algorithm. We show that the broadcast Clos network can be considered as the cascade combination of a reverse omega network and a broadcast omega network. The construction of copy network is therefore no longer limited to 2/spl times/2 switching elements. By recursively constructing the reverse omega and the omega networks using 2/spl times/2 switching elements, we show that the proposed copy network is the generalization of Lee's architecture (1988).

A newly proposed large-scale ATM switch called the cross-path switch has been shown to be capable of handling multirate traffic efficiently. We study two replication approaches to enhance the switch to support multicasting. The first approach replicates multicast cells at both the input and output stages, while the second one replicates cells at the input stage only. A feasible configuration for each scheme is considered and the effect of multicast traffic on the switch performance in terms of the throughput and cell loss probability is studied. We observed that, to achieve the same throughput and loss requirement, the second architecture may require fewer switching elements than the first one.

A quasi-static routing scheme called path switching for large-scale ATM packet switch systems is proposed. Previously the Clos network has been used as the model for many large-scale ATM switch architectures, in which the most difficult issue is path and bandwidth assignment for each connection request. The static routing scheme, such as multirate circuit switching, does not fully exploit the statistical multiplexing gain. In contrast, the dynamic routing scheme, such as straight matching, requires slot-by-slot computation of route assignment. Path switching is a compromise of these two routing schemes. It uses a predetermined periodical connection pattern in the central stage, look-ahead selection in the input stage, and output queueing in the last stage. The scheduling of path switching consists of capacity assignment and route assignment. The capacity assignment is constrained by the quality of service of connection requests. The route assignment is based on the timespace interleaving of the coloring of bipartite multigraphs. We show that path switching can handle multirate and multimedia traffic effectively in the Clos network.

This paper describes an end-to-end parallel communications scheme based on a vector routing algorithm (VRA) for ATM network control and management. An information string is partitioned into m parts, which are then coded into k > m parts and sent out on k separate subchannels to the receiver. When m of the k parts are received correctly, the original information can be reconstructed. Two desirable effects are achieved in the context of ATM traffic control: (1) the burstiness of the source traffic can be smoothed out by the partition process; (2) the quality of service in terms of error, loss and delay can be controlled using the number of redundant routes k — m as a control parameter. Our results show that VRA is especially suitable for services with highly bursty traffic. We argue that several network management issues, including reliability, evolution and integration, security, and administration and billing can be addressed in a simple manner using the VRA framework.

A new parallel algorithm for route assignment in Benes-Clos network is studied. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously and to accommodate packets requesting for connections in real-time as they arrive at the inputs. Most known sequential route assignment algorithms, such as the looping algorithm for Benes (1962) networks or Clos (1953) networks, are designed for circuit switching systems where the switching configuration can be rearranged at a relatively low speed. Most existing parallel routing algorithms are not practical for packet switching because they either assume the set of connection requests is a full permutation or fail to deal with output contentions among the set of input packets. We develop a parallel routing algorithm by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the Benes network. Our approach can handle both the partial permutations and the output contention problem easily. The time complexity of our algorithm is O(log/sup 2/N), where N is the network size. Furthermore, we extend the algorithm and show that it can be applied to the Clos network if the number of central modules is a power of two.

To simplify traffic control in a network, it is desirable that the traffic-control policy at a network node depends only on the external traffic loads on the input and output links, but not on the detail addressing or distribution of packets from inputs to outputs. In other words, it should be possible to guarantee the grade-of-service of an input-output connection by controlling the aggregate loads on the input and output. Switch nodes in which such a traffic-control policy is possible are said to have the property of the sufficiency of the knowledge of external loads (SKEL). One way to demonstrate the feasibility of SKEL for a particular switch is to show that the performance under any nonuniform traffic distribution from inputs to outputs is better than or close to the performance under the uniform traffic distribution. The contributions of this paper are twofold: clarifying issues related to SKEL and establishing its feasibility for generic input- and output-buffered switches on a rigorous basis. The following summarizes our major results: (1) The packet-loss probability due to the Knockout switch-design principle for packets destined for an arbitrary output is maximum when the traffic to that output originates uniformly from all inputs; (2) The packet-loss probability for packets destined for a particular output under uniform traffic closely approximates the loss probability for packets from the worst-case input to that output under nonuniform traffic; (3) For mean and variance of delay, similar results as in (1) and (2) can be obtained; (4) For an input-queued switch, external link loadings that do not give rise to queue saturation under uniform traffic will not do so under nonuniform traffic either.

A class of recursive sorting networks based on mod(s) m-merging, a generalization of Batcher′s odd-even merging, is studied in this paper. Iterative decomposition of a sorter into smaller comparator modules, an equivalent problem but in a different setting, is also resolved based on the scheme proposed here. We first show that it is impossible to generalize the principle of odd-even merging in a three-stage network. Then the condition on generalized mod(s) m-merging with four stages is proven. This scheme degenerates to the three-stage odd-even merging network when m = 2 and s = 2. An algorithm for computing the optimal configuration is also given. Applications of this sorting network include parallel relational database computers and modular construction of sorting networks for large packet switches.

A theoretical foundation for the evaluation and comparison of a very broad spectrum of fast packet-switching techniques is developed. Based on this framework, the authors investigate the complexity of various packet switch designs, and demonstrate the advantage of dilation as a switch-design technique. Packet switches are classified either as loss systems or waiting systems, according to whether packets losing contention are dropped or queued. In a loss system, the packet loss probability can be made arbitrary small by providing enough paths between inputs and outputs. The authors focus on the question: how does the switch complexity grow as a function of switch size for a given loss probability requirement? A uniform approach to this problem is developed. It is shown that for an N/spl times/N switch, the required number of switch elements for both the parallel-banyan network and the tandem-banyan network is of order N(log N)/sup 2/, whereas the complexity of a dilated-banyan network is of order N log N(log log N). Within the class of waiting systems, it is shown that the parallel banyan networks in a Batcher-parallel-banyan network can be replaced by a dilated-banyan network without sacrificing the nonblocking property. Thus, as with parallelization, dilation can also be used to increase the throughput of a waiting system. In addition, the authors also explore the application of dilation in a large modular switch design which is realized by an interconnection structure consisting of Batcher-dilated-banyan networks and statistical multiplexers.>

Describes a dual shuffle-exchange switching network (DSN) that makes use of the principle of error-correcting routing. For motivation, parallels are drawn between error-correcting routing in switching and error-correcting coding in transmission. Based on a novel error-correcting and self-routing algorithm, the authors show by analysis and simulation that the DSN can achieve the Shannon's lower bound Nlog N on switch complexity while satisfying four desirable criteria: 1) self-routing property; 2) no queueing of packets at the inputs or inside the switch; 3) arbitrarily small packet-loss probability; 4) close-to-100% throughput. Different implementations of the basic DSN concept and their trade-offs are discussed.>

The paper describes several improvements to a nonblocking copy network proposed previously for multicast packet switching. The improvements provide a complete solution to some system problems inherent in multicasting. The input fairness problem caused by overflow is solved by a cyclic running adder network (CRAN), which can calculate running sums of copy requests starting from any input port. The starting point can change adaptively in every time slot based on the overflow condition of the previous time slot. The CRAN also serves as a multicast traffic controller to regulate the overall copy requests. The throughput of a multicast switch can be improved substantially if partial service of copy request is implemented when overflow occurs. Call-splitting can also be implemented by the CRAN in a straightforward manner. Nonuniform distribution of replicated packets at outputs of the copy network may affect the performance of the following routing network. This output fairness problem due to underflow is solved by cyclically shifting the copy packets in every time slot. An approximate queueing model is developed to analyze the performance of this improved copy network. It shows that if the loading on each output of the copy network is maintained below 80%, the average packet delay in an input buffer would be less than two time slots.>

It is desirable that the traffic control policy at a network node depend on the external traffic loads on the input and output links, but not on the detailed addressing or distribution of packets from inputs to outputs. It should be possible to guarantee the grade of service of an input-output connection by controlling the aggregate loads on the input and output. Switch nodes in which such a traffic control policy is possible are said to have the property of the sufficiency of the knowledge of external loads (SKEL). The authors clarify issues related to SKEL and establish its feasibility for a generic switch node on a rigorous basis.>

Multicast switching is emerging as a new switching technology that can provide efficient transport in a broadband network for video and other multipoint communication services. The authors develop and analyze call scheduling algorithms for a multicast switch. In particular, they examine two general classes of scheduling algorithms: call packing algorithms and call splitting algorithms. The performance improvement by the call packing algorithms examined is shown to be negligible. In contrast, the call splitting algorithms can provide significantly lower blocking by reducing the level of output port contention. However, excessive call splitting could degrade performance because of the additional load introduced to the input ports. The authors present a simple call splitting algorithm called greedy splitting which achieves near-optimal performance.>

Multicast traffic encounters higher blocking probability than point-to-point traffic because of simultaneous output port contentions. To ensure adequate performance for multicast traffic, the authors develop and analyze a class of call scheduling algorithms via call splitting. Call splitting algorithms reduce output contention by generating smaller subcalls from a multicast call. It is shown that slot contention blocking is the predominant factor of blocking a multicast call, which suggests that call splitting may be an efficient strategy for a multicast call. The authors devise a deterministic call splitting algorithm and show that excessive call splitting can degrade performance because of the additional load introduced to the input ports. The authors also investigate an adaptive splitting algorithm which achieves performance approach the optimum by avoiding excessive call splitting.>

Switch modules, the building blocks of this system, are independently operated packet switches. Each module consists of a Batcher sorting network, a stack of binary trees, and a bundle of banyan networks. The modular architecture is a unification of the Batcher-banyan switch and the knockout switch, and can be physically realized as an array of three-dimensional parallel processors. Switch modules are interconnected only at the outputs by multiplexers. The partitioned switch fabric provides a flexible distributed architecture, which is the key to simplify the operation and maintenance of the whole switching system. The modularity implies less stringent synchronization requirements and makes higher-speed implementation possible. The proposed modular switch is intended to meet the needs of broadband telephone offices of all sizes. It is estimated that a modular switch with terabit capacity can be built using current VLSI technologies.>

The authors propose an architecture that can switch hundreds of gigabits while meeting a wide variety of service requirements. The switch can be constructed out of a few atomic cell types with regular interconnection patterns. This simple structure lends itself to very effective VLSI implementation. The multicast packet switch consists of three internally nonblocking, self-routing subnetworks. First, the selector subnetwork arbitrates among competing demands for copies to satisfy real-time requirements. The copy subnetwork then makes the copies and the switch subnetwork routes the packet copies to their final destinations. The authors detail the architecture and operation of the multicast switch.>

In addition to handling point-to-point connections, a broadband packet network should be able to provide multipoint communications that are required by a wide range of applications. The essential component to enhance the connection capability of a packet network is a multicast packet switch, capable of packet replications and switching, which is usually a serial combinations of a copy network and a point-to-point switch. The copy network replicates input packets from various sources simultaneously, after which copies of broadcast packets are routed to their final destination by the switch. A nonblocking, self-routing copy network with constant latency is proposed. Packet replications are accomplished by an encoding process and a decoding process. The encoding process transforms the set of copy numbers, specified in the headers of incoming packets, into a set of monotone address intervals which form new packet headers. The decoding process performs the packet replication according to the Boolean interval splitting algorithm through the broadcast banyan network, the decision making is based on a two-bit header information. This yields minimum complexity in the switch nodes.>

Communications protocols are usually modeled by a pair of finite-state machines that generate the interaction between processes. Protocol verification is a procedure to validate the logical correctness of these interaction sequences and to detect potential design errors. A relational approach is proposed to represent a finite-state machine as a transition table. On this basis, the well-established theory of relational databases can be utilized to derive the global-state transitions of the system. Furthermore, logical errors of a protocol such as deadlocks, incomplete specifications and nonexecutable interactions can be formulated in terms of relational algebra. This approach has been implemented on the INGRES database system and applied to the verification of several protocols.>

Processes participating in a communications protocol are usually modeled by finite-state machines interacting each other. Protocol verification is a procedure to validate the logic correctness of these interaction sequences and detect the potential design errors. A relational approach is proposed to represent a finite-state machine as a transition relation. On this basis, relational algebra can be utilized to derive the global-state transitions of the system. Furthermore, the logic errors of the protocol such as deadlocks, incomplete specifications and nonexecutable interactions can all be formulated in terms of relational algebra. This approach has been implemented on the INGRES and DBASE-III database systems running on various machines and applied to the verification of several protocols including the CCITT X.21. Protocol verification represents a non-traditional data processing application of relational database systems.

Database design is based on the concept of data dependency, which is the interrelationship between data contained in various sets of attributes. In particular, functional, multivalued and acyclic join, dependencies play an essential role in the design of database schemas. The basic definition of an information metric and how this notion can be used in relational database are discussed in this paper. We use Shannon entropy as an information metric to quantify the information associated with a set of attributes. Thus, we prove that data dependencies can be formulated in terms of entropies. These formulas make the numerical computation and testing of data dependencies feasible. Among the different types of data dependencies, the acyclic join dependency is most important to the design of a relational database schema. The acyclic join dependency, with multivalued dependency as a special case, impose a constraint on the information-preserving decomposition of a relation. It is interesting that this constraint on a relation is similar to Gibbs' condition for separating physical systems in statistical mechanics. They both assert that entropy is preserved during the decomposition process. That is, the entropies of the corresponding set of attributes must satisfy the inclusion–exclusion identity.

The structural properties of acyclic database schemas, especially the interrelationships between acyclic join dependencies and multivalued dependencies, are examined in this paper. The intersection closure of a database schema is a semilattice, which is usually represented by Hasse diagram in algebra. The Hasse diagram of a schema is analogous to the Bachman diagram of a network model. Based on the topological structures of Hasse diagrams, the acyclic join dependency is proved to be equivalent to a set of conflict-free multivalued dependencies. Furthermore, we show that if the Hasse diagram is loop free, then the corresponding set of multivalued dependencies is also contention-free. This result is consistent with previous results derived from the Bachman diagram.