Supporting multicast applications has drawn increased attention in the development of WDM based optical networks. To provide a high level of availability in the face of node or link failure for multicast traffic, pre-assigned spare capacity in the networks is needed. This paper studies the problem of constructing a minimum-cost, two-connected subgraph, satisfying the wavelength conversion constraint, for a multicast request in a WDM network. It is known that the problem of finding the minimum cost of a two-connected graph is NP-hard. We prove that the problem of the optimal wavelength assignment for a given graph is also NP-hard. We propose a routing and wavelength assignment heuristic which aims not only to minimize the cost of the subgraph but also to reduce the number of wavelength conversions in the networks. Simulation experiments show that our proposed algorithm achieves performance close to the optimal solution when the average number of wavelengths in the networks is not low

Routing of QoS guaranteed tunnels with failure protection requires bandwidth reservation along both primary and alternate paths. By judicious selection of alternate paths, a significant amount of resilient bandwidth can be shared among backup paths. This paper presents maximum sharing schemes for alternate paths that protect against single as well as double simultaneous link failures in the network.

This paper proposes a new multicast protocol for mobile ad hoc networks, called the multicast routing protocol based on zone routing (MZR). MZR is a source-initiated on-demand protocol, in which a multicast delivery tree is created using a concept called the zone routing mechanism. It is a source tree based protocol and does not depend on any underlying unicast protocol. The protocol's reaction to topological changes can be restricted to a node's neighborhood instead of propagating it throughout the network. A detailed simulation and performance analysis of MZR is presented.

Facsimile (fax) transmission is very important to the world of business. In a world where a significant percentage of long distance public switched telephone network (PSTN) traffic is composed of fax, great savings in toll charges are possible by utilizing IP networks instead. We study the use of T.38 facsimile in conjunction with session initiation protocol (SIP) for transmission of fax traffic over IP networks. Since the interactions of these protocols are not completely standardized, we investigate and propose some practices for this transmission process. Through network simulations of both signaling and data traffic, we determine that real-time fax transmission using SIP is achievable and that it is important to utilize the SIP contact-header for reducing the load on SIP proxy servers and links associated with them.

This paper demonstrates that an optimum light-tree-based virtual topology has improved performance over an optimum lightpath-based virtual topology with respect to minimizing network-wide average packet hop distance in the network.

Configuration management is an integral part of the network management effort. ATM network configuration management must support the creation, modification, and termination of virtual path and channel connections, provide ILMI support for neighboring nodes, and support interface and buffer management for intermediate systems. Currently, permanent virtual circuits (PVCs) are established manually by creating a permanent virtual path link to form the desired connection. As ATM networks grow in size, configuration management must implement an intelligent approach for creating, re-configuring, and destroying permanent virtual circuits. This paper presents a mobile agent based connection management scheme for establishment and teardown of PVCs in an ATM network.

With the proliferation of new networking technologies, and the demand for new services, it will become increasingly difficult, and nearly impossible, to manage large-scale networks without an intelligent, automated management system. Discovering and keeping track of the topology of a network is essential for effective network management. We introduce a distributed algorithm for discovering the connectivity graph of an ATM network using intelligent mobile agents. In the proposed scheme links are discovered in a distributed fashion, thereby making this approach significantly more scaleable than applications using the traditional client/server model and SNMP.

We investigate ways in which UIO-based conformance testing can fail to catch faults, including single and multiple faults, faults with extra or missing states, and faults at both the test sequence and subsequence levels. Given a particular error and test method, the error is masked if it is not detected by the test method. Many forms of fault masking are possible, and all test methods we have considered exhibit some forms of masking. Faults captured at the test subsequence level may become masked at the sequence level, and vice versa. Fault masking has been used to argue relative merits of various testing methods. Because of the pervasiveness of masking, we cannot use masking alone to argue that one UIO-based test method is superior to another. Information about the density of masked faults among all faults is needed to evaluate a test method.>

Protocols are large and complex software systems. Complete conformance testing of an implementation against its standard may not be feasible in terms of the resources available. This paper discusses a new approach, the P-method, to the testing of meaningful subsets of communication protocols for an asynchronous model of communication. The approach is based on the probabilistic verification of protocols, which is carried out on the more probable part of the protocol first. The technique can be used for generating probabilistic test sequences for the conformance testing of communication protocols to standards. The proposed method yields meaningful protocol test sequences which test the most probable behaviors of a protocol when the testing of the complete protocol is not feasible. Probabilistic test sequences can be categorized into different classes. The higher the class a probabilistic test sequence is in, the larger the extent of the protocol it covers, and the better is the fault coverage. If the class of a test sequence is high enough, its fault coverage is comparable to the fault coverage of test sequences generated by other methods. Results from a study of the P-method, using alternating bit protocol (ABP) and a subset of NBS TP4 as examples, support the claims above. It can also be shown that if errors are introduced only to the more probable part of the protocol, the fault coverage of P-method is also comparable to other methods.>

Open Shortest Path First (OSPF) is a dynamic, hierarchical routing protocol designed to support routing in TCP/IP networks. A simulation of the OSPF Election Protocol shows three results: (1) The Designated Router (DR) can be elected in constant time. (2) If a router has a limited number of input buffers, a competition for buffers between the Election and the Flooding Protocols increases the election time and causes an oscillatory behavior.At each router, the Router-ID of the DR continuously changes causing instability. (3) In the worst case, when the DR and the BDR fail at the same time, the DR-agreement-time is bounded above by twice the HelloInterval. A simulation of the OSPF Flooding Protocol, using 20, 50 and 80 router point-to-point networks, shows three results: (1) For the 50 router network, as link speed exceeds 4000 Kbps, the probability of overflowing the input buffers increases causing retransmissions. The increase in bootup-convergence-time from retransmissions is bounded by two and three times the RxmtInterval for link speeds of 4000 to 6000 Kbps and above 50 Mbps respectively. The increase in the bootup-convergence-time is due to large number of unacknowledged flooding packets received within RxmtInterval. (2) For 20 and 50 router networks, the input buffer size has little impact on the bootup-convergence-time. For the 80 router network, a small change in the input buffer size drastically changes the bootup-convergence-time. (3) Reducing the value of the RxmtInterval lowers the bootup-convergence-time at high link speeds.

The authors consider a protocol specification represented as a fully specified Mealy automata, and the problem of testing an implementation for conformance to such a specification. No single sequence-based test can be completely reliable, if one allows for the possibility of an implementation with an unknown number of extra states. They define a hierarchy of test sequences, parameterized by the length of behaviors under test. For the reset method of conformance testing, they prove that the hierarchy has the property that any fault detected by test i is also detected by test i+1, and show that this sequence of tests converges to a reliable conformance test. For certain bridge sequence methods for constructing test sequences, this result does not always hold. In experiments with several specifications, they observe that given a small number of extra states in an implementation, the sequence of tests converge to a total fault coverage for small values of i, for both reset and bridge sequence methods. They also observe that the choice of characterizing sequence has less effect on fault coverage than the choice of behavior length or number of extra states in the implementation.>

article Finding disjoint paths in networks Share on Authors: Deepinder Sidhu Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MD Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MDView Profile , Raj Nair Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MD Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MDView Profile , Shukri Abdallah Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MD Department of Computer Science, University of Maryland, BC, Baltimore, MD and Institute for Advanced Computer Studies, University of Maryland, CP, College Park, MDView Profile Authors Info & Claims ACM SIGCOMM Computer Communication ReviewVolume 21Issue 4Sept. 1991 pp 43–51https://doi.org/10.1145/115994.115998Published:01 August 1991 108citation2,329DownloadsMetricsTotal Citations108Total Downloads2,329Last 12 Months68Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Test sequences are used for the conformance testing of communication protocols to standards. This paper discusses a new approach to generating test sequences. The approach is based on probabilistic concepts about protocol state transitions and communication channels. The novel feature of the test sequences generated by this technique is that the most probable states of a protocol will be tested more promptly.

The closed-cover technique for verifying progress for two communicating finite-state machines exchanging messages over two lossless, FIFO channels is considered. The authors point out that the definition of a closed cover in M.G. Gouda (ibid., vol.SE-10, no.6, p.846-55, Nov. 1984) may be too restrictive, while that in M.G. Gouda and C.K. Chang (ACM Trans. Prog. Lang., vol.8, no.1, p.154-82, Jan. 1986) is not correct. They then show how a condition of the closed-cover definition can be modified to relax restriction to various degrees. They also discuss the similarities and relationship between the structural partition technique and the closed-cover technique.>

The authors present a detailed study of four formal methods (T-, U-, D-, and W-methods) for generating test sequences for protocols. Applications of these methods to the NBS Class 4 Transport Protocol are discussed. An estimation of fault coverage of four protocol-test-sequence generation techniques using Monte Carlo simulation is also presented. The ability of a test sequence to decide whether a protocol implementation conforms to its specification heavily relies on the range of faults that it can capture. Conformance is defined at two levels, namely, weak and strong conformance. This study shows that a test sequence produced by T-method has a poor fault detection capability, whereas test sequences produced by U-, D-, and W-methods have comparable (superior to that for T-method) fault coverage on several classes of randomly generated machines used in this study. Also, some problems with a straightforward application of the four protocol-test-sequence generation methods to real-world communication protocols are pointed out.>

The authors present an estimation of fault coverage of four protocol test sequences generation techniques (T-, U-, D-, and W-methods) using Monte Carlo simulation on a simple protocol machine. The ability of a test sequence to decide whether a protocol implementation conforms to its specification heavily relies upon the range of faults that it can capture. This study shows that a test sequence produced by T-method has a poor fault detection capability whereas test sequences produced by U-, D- and W-methods have fault coverage comparable to each other and superior to that for T-method on several classes of randomly generated machines used.>

This paper presents results on the application of four protocol test sequence generation techniques (T-, U-, D-, and W-methods) to the NBS Class 4 transport protocol (TP4). The ability of a test sequence to decide whether a protocol implementation conforms to its specification depend on the range of faults that it can capture. The study shows that a test sequence produced by the T-method has a poor fault detection capability whereas test sequences produced by the U-, D- and W-methods have comparable (superior to that for T-method) fault coverage on several classes of randomly generated machines. The lengths of test sequences produced by the four methods tend to be different. The length of a test sequence produced by the T-method (W-method) is the smallest (largest). The length of a test sequence from the U-method is smaller than that for the D-method and lengths for both are greater than that for the T-method and less than that for the W-method.

Applications of an automated tool for module specification (ATMS) that finds the specification for a submodule of a system are presented. Given the specification of a system, together with the specification for n-1 submodules, the ATMS constructs the specification for the nth addition submodule such that the interaction among the n submodules is equivalent to the specification of the system. The implementation of the technique is based on an approach proposed by P. Merlin and G.B. Bochmann (1983). The specification of a system and its submodules consists of all possible execution sequences of their individual operations. The ATMS uses finite-state machine concepts to represent the specifications and interactions of the system and its submodules. The specification found by the ATMS for a missing module of a system is the most general one, if one exists. Application of the ATMS in the area of communication protocols is discussed. A manual process to find the specification for a missing module using the Merlin-Bochmann technique is time-consuming and prone to errors. The automated tool presented proves a reliable method for constructing such a module.>

A general, formal modeling technique for protocol service interfaces is discussed. An executable description of the model using a logic-programming-based language, Prolog, is presented. The specification of protocol layers consists of two parts, the specification of the protocol interfaces and the specification of entities within the protocol layer. The specification of protocol interfaces forms the standard against which protocols are verified. When a protocol has been implemented, the correctness of its implementation can be tested using the sequences of events generated at the service interface. If the behavior of the protocol implementation is consistent with the behavior at the service interface, the implementation conforms to its standard. To illustrate how it works, the model is applied to the service interfaces of protocol standards developed for the transport layer of the ISO/OSI architecture. The results indicate that Prolog is a very useful formal language for specifying protocol interfaces.>

This paper discusses the verification of the connection management aspects of the IEEE 802.2 logical link control (LLC) protocol standard for local area networks. An automated protocol development technique is used to verify a subset of the protocol with respect to the protocol properties of completeness, deadlock freeness, boundedness, and termination. These properties are found to hold for the subset of the protocol analyzed here. The technique is also used to derive user event sequences for some interesting subsets of the protocol. These user event sequences together make up a partial service specification of the protocol.

This paper discusses the verification of the connection management aspects of a transport layer protocol available from the National Bureau of Standards. An automated protocol development technique is used to verify a subset of the protocol with respect to the protocol properties of completeness, deadlock freeness, boundedness, and termination. The analysis points out several error situations in which the completeness property does not hold for the protocol. We first give an overview of the protocol development technique used in specification and verification of the protocol. We then describe the transport layer protocol, and present the results obtained by applying the automated verification technique to this protocol.

An automated technique for protocol development is discussed along with its application to the specification, verification, and semiautomatic implementation of an authentication protocol for computer networks. An overview is given of the specification language, implementation method, and software tools used with this technique. The authentication protocol is described, along with an example of its operation. The reachability analysis technique for the verification of some protocol properties is discussed, and protocol verification software that uses this technique is described. The results of mechanical verification of some properties of this protocol are presented with a partial implementation generated automatically from the protocol specification.

In this note, we discuss a generalization to Dijkstra's Dining Philosophers problem and a distributed solution to it. We also show that the solution is deadlock-free and starvation-free and also robust, in the sense that failure of some nodes does not affect all the nodes. The results of this paper have implications for problems in the areas of resource sharing, routing in networks, processor interconnections, fault-tolerant computing, and decentralized control in distributed systems.

This paper discusses the use of logic programming techniques in the specification and verification of secure systems. The secure systems specifications discussed are formal and directly executable. The advantages of executable specifications are: (1) the specification is itself a prototype of the specified system, (2) incremental development of specification sis possible, (3)behavior exhibited by the specification when executed can be used to check conformity of the specification with security requirements such as DoD security policy, or discretionary and integrity policies.We discuss Horn clause logic, which has a procedural interpretation, and we use the predicate logic programming language, PROLOG, to specify and verify the functional correctness of secure systems, The PROLOG system possesses a powerful pattern-matching feature which is based on unification. An executable specification is very useful in checking completeness of a design and rectifying flaws in it before the expensive step of coding starts. In this paper, three examples of executable logic specifications are given a "login" command from military message system experiment, a security kernel for an imaginary computer architecture, and a simple downgrade trusted process. Executable logic specifications for secure systems could prove very useful to the DoD Computer Security Center in assessing computer products according to trusted computer system evaluation criteria.

The problem of security flow into n-dimensional arrays is considered. It is shown that in the security flow analysis for an array assignment A(B1, B2···,Bn) = 〈expression〉, it is sufficient to analyze the flows Bj→ A( B1, B2,··· Bn), i.e., show that L[Bj]≤ L[A(B1, B2,···,Bn)], where L[X] denotes the security level of a variable X.

Computer communication networks provide means for user-computer, user-user, computer-computer interaction where the two communicating entities may be ●t remote places. A user at one site has potential access to the resources of all the computers connected throygh the network. A network-wide and foolproof authentication scheme is needed to allow authorized access to resources and also to prevent spoofing. Such an authentication ●echanism is also needed for charging a customer for the use of ● system resources, remote updating of software, etc.

This paper presents a high-level design for a local area network (LAN) that will support subscribers (terminals or hosts) operating at various security levels. Subscribers may be "single-level", which means they are untrusted and can operate at only one security level, or they may be "multilevel" and trusted to operate at a range of security levels [Nibaldi79].