Search

Parallel computers are now popularly applied to applications where many calculations are required. In a NO Remote memory Access model (NORA) parallel computer, many processors are connected by communication links and calculation results are obtained by communications among processors. The message switching method, which controls message transmission in the parallel computer, is one of the most important parameters to improve the performance of the parallel computer. Since parallel computers include many processors, its failure rate is very high and many fault-tolerant switching methods have been proposed. The existing methods have problems, however, such as low communication throughput, low fault-tolerant capability, and large hardware overhead. We propose fault-tolerant switching by improving wormhole switching. The proposed method inserts dummy flits, having no information, after the header flit, the first flit of the packet. By overwriting the header flit to the dummy flit, backtracking is implemented without hardware overhead. Computer simulation says that in a 16 by 16 2D torus, for example, the throughput of the proposed method is almost equal to that of existing methods which require large hardware overhead if the number of the faulty nodes is less then 40.

Summary form only given. Ant colony optimization (ACO) technique can be successfully implemented to solve many combinatorial optimization problems. In this paper we use the ACO technique to route messages through an N/spl times/N optical multistage interconnection network (OMIN) allowing up to 'C' limited crosstalk's (conflicts between messages within a switch) where 'C' is a technology driven parameter and is always less than log/sub 2/N. Messages with switch conflicts satisfying the crosstalk constraint are allowed to pass in the same group, but if there is any link conflict, then messages are routed in a different group. The focus here is to minimize the number of passes required for routing allowing up to 'C' limited crosstalks in an N/spl times/N OMIN. In this paper we show how the ACO technique can be applied to the routing problem, and its performance is compared to that of the degree-descending algorithm using simulation techniques. Finally the lower bound estimate on the minimum number of passes required is calculated and compared to the results obtained using the two algorithms discussed. The results obtained show that the ACO technique performs better than the degree-descending algorithm and is quite close to optimal algorithms to the problem.

From a pure signal point of view, jitter can be defined as an interference on an analog line caused by a variation of the signal from its reference timing slot. The same effect can be experienced within an ATM switch buffer at the cell level mechanism due to that many traffic streams are concurring to be served. Therefore, a theoretical approach for a single quality of service (QoS) constant bit rate (CBR) cell stream being multiplexed firstly with an elastic short-range dependent (SRD) background traffic and thereafter with a long-range dependent (LRD) traffic is presented. Results show that jitter experienced by the CBR cell stream, is extremely high when LRD traffic is being multiplexed with. This is not the case when SRD traffic is taking into account. Furthermore, this work shows a very interesting result, for low Hurst parameter values (H < 0.70), a sort of cross-effect boundary is visualized; it means that there could exist a threshold where self-similarity could have no adverse effect on the network.

This paper extends the refusal testing for multi input-output systems (MIOTS) to make it also applicable to test those implementations with nonlockable output channels. Starting with the MIOTS refusal testing theory, we distinguish two types of output channels: lockable and nonlockable, and develop a more general multi input-output refusal testing relation. A test generation algorithm is proposed to derive a complete test suite from a specification.

Packets and packet switching were invented to utilize effectively, i.e., to multiplex, digital networks. We easily grasp the concepts of circuit switching, such as a voice telephone call, and message switching, such as the paper-based postal system, because there are many common and historical examples. In recent decades, we've discovered that digital techniques for transmission and switching information are far superior, faster, cheaper, and less error prone than the analog techniques devised in earlier times. These digital methods allowed for the invention of packets and packet switching, thereby making digital technology even more effective. Networks are built in layers. First, we look at some important layering models for different kinds of digital networks. We also mention how addresses fit into our layering schemes. Next, we briefly describe circuit and message switching before surveying the primary topic of packet switching. Keywords: baseband; broadband; circuit switching; IP (Internet protocol) address; message switching; OSI reference model; packet switching; TCP/IP mode

In the business world, exchange of signatures or receipts is a common practice in case of future dispute. Likewise, it is critical in e-commerce applications to have the security service that generates, distributes, validates, and maintains the evidence of an electronic transaction. Quite of number of non-repudiation protocols have been proposed in distributed systems and evaluated based on some evaluation criteria. However, in the context of e-commerce, there are additional evaluation criteria to be considered: fairness to both the message sender and the message receiver with respective to their control over the completion of a transaction, the degree of trust on a third party, and existence dependency on a third-party for dispute settlement on a committed transaction. We identify the set of requirements for a message transfer protocol in e-commerce, and propose a new non-repudiation message transfer protocol that meets these additional criteria. Our protocol protects the confidentiality of message contents such that no unauthorized intermediary is able to see the contents. And, the protocol is superior to other protocols in that continuous existence of the third-party authority is not needed beyond the completion of a message transfer. Furthermore, with respect to the control over the commitment of a transaction, our protocol is fair to both the message sender and the receiver.

Summary form only given. The introduction of cross-connects (XCs) into optical networks grants us the opportunity to rapidly provision high bandwidth connections. These connections are generally used to carry critical customer data. As such, connection reliability becomes a major concern for both carriers and their customers. We investigated the scalability of XC architectures and shared-mesh restoration signaling schemes for rapid restoration. The key findings are that: 1. Sequential processing of cross-connect requests is highly undesirable for cross-connects with significant per-node cross-connect times; and 2. Contention resolution schemes with message forwarding only after cross-connection completion (such as those used within current generalized-multi protocol label switching (GMPLS) proposals) provides significantly slower restoration as compared with contention avoidance schemes.

Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations of flooding, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where each node forwards a message with some probability, to reduce the overhead of the routing protocols. Gossiping exhibits bimodal behavior in sufficiently large networks: in some executions, the gossip dies out quickly and hardly any node gets the message; in the remaining executions, a substantial fraction of the nodes gets the message. The fraction of executions in which most nodes get the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, this simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. Our results suggest that the improvement should be even more significant in larger networks

In this paper, we generalize the line-communication model by relaxing the notion of conflictness between paths. We show that the problem of finding optimal schedules to route any set of messages under both our generalized line-communication model and the bufferless routing model is NP-hard even if restricted to binary trees. Finally, a simple offline 2-approximation algorithm for our model on trees is presented.

We consider, for d>1, a directed d-dimensional hypercube, Q/sub d/=(V,E), where V is a set of 2/sup d/ nodes, each denoted by a distinct binary string of length , and E is the set of edges (x,y), such that x,y/spl epsiv/V differ in exactly one position of their bit strings. Given a permutation of the vertices of Q/sub d/, which describes a source-destination mapping, we study the existence of a set of paths from each source to each destination such that no edge of Q/sub d/ is assigned to more than one path. For a multiprocessor connected in such a manner, such a set of paths could be used for circuit switching of messages between source destination processors (nodes). We show that for any automorphism of Q/sub d/ there is such a set of paths.

The authors present a detailed analysis of the CSMA/CD (carrier-sense-multiple-access-with-collision-detection) bus that forms the backbone of a multiprocessor-based communications system. Fiber-optic implementations of the Ethernet protocol (based on the IEEE 802.3 standard) and the Enet II protocol (proposed by M.K. Molloy in 1984) are modeled with the SIMAN simulation language. The primary difference between the two protocols is in the collision resolution scheme with subtle differences in the access mechanism. The communications system consists of multiple MicroVAX II and III processors, used primarily in this study to provide loading to the CSMA/CD bus. Various performance metrics are investigated, including bus utilization and queuing, packet and message response times, and pertinent collision statistics. It is found that both protocols meet the criteria for successful performance within the proposed system. Owing to the light input loading and corresponding low bus utilization, minimal impact to total system performance results when changing from protocol to protocol. However, it is evident from the results that the performance of the Enet II protocol is degrading more rapidly than that of the Ethernet. >

A slotted p/sub i/-persistent protocol and the effects of random message length are considered. Since the length of messages is not fixed, a message is divided into a number of equal-size packets such that a packet can fit into one slot. The utilization of the network degrades because of the increasing transmission overhead owing to excess packet headers and a possible empty portion in the last packet of any message. Furthermore, the increasing ratio of message-to-packet length increases the interdependence among the nodes and thus affects the bus access probabilities. An analytical model is presented to determine the upper and lower bounds to the access probabilities. Due to the complexity of this problem, only two nodes are considered. Simulation results showing average queue length performance versus different message statistics are also presented. >

An asymmetric prioritized token-ring operation with nonpreemptive priority queuing and a limited service discipline at each station is discussed. The number of message priority levels and the walktime vary from one station to another. Moreover, the assumed Poisson message arrival process and the message transmission time vary not only from one station to another but also from one class to another. The analysis focuses on the observation that upon the arrival of a tagged message at a station, the server is either performing walktime, serving a message at the station at which the tagged message arrived, or else serving a message at another station. On the basis of these mutually exclusive cases, three special period intervals required to carry the analysis through are defined. The analysis of the main message delay is based on characteristics of the cycle time as well as on these special period intervals, and in all cases the balance of flow is of particular interest. The performance as measured by the expected delay for any message class at any station is derived, and the numerical results are validated through simulation. >

A recursive equation performing the computation of the probabilistic characteristics of message flow in a quite general class of communication networks is presented. This formulation leads to the evaluation of average transit time through the network. The important point of the proposed model consists in the introduction of a second probability (that a message progresses from one stage to the next) joined with the probability of occupation of one buffer in then network. The overall amount of computations is reasonable, and the use of the recursion is almost as simple as the use of an analytic formula. >

Consideration is given to a flow-control problem involving a treelike network with multiple sources, multiple stages, and a single final destination. Nodes in the stages between the sources and the destination act both as receivers and transmitters. The flow of messages in the network is controlled by the allocation of time slots to the transmitters. The goal is to minimize the number of messages in the network. The authors formulate the problem as a Markovian decision process with an appropriate delayed information structure. They show that the global optimization problem can be decomposed into a set of local optimization problems. The authors also show that the optimal policies of the local problems obey certain structural properties similar to the ones derived in an earlier work of the authors (1988) that analyzes a single-stage network. >

A family of distributed algorithms for decentralized evaluation of associative and commutative functions is presented. It is shown that if N is the member of processes which cooperate to evaluate such a function, then for each positive integer c >

Several variants of the simple Chang-Roberts algorithm are simulated. The empirical analysis shows that the algorithms compare very favorably to other ring-based election algorithms. For various ring sizes and numbers of concurrent starters the average message complexity, its distribution, and its standard deviation were studied. Simulation results show that the algorithm is far better than the rather conservative mathematical estimations indicate. >

The problem addressed considers random arrivals (or generation) of packets at the nodes and poses the question of (a) existence of schedules that guarantee finite queueing delays and/or (b) finding schedules that produce minimum queueing delay. As such a problem involves interacting queueing systems, it is not feasible to attempt to solve it for a PRN (packet radio network) of general topology. Instead the focus is on a simple tandem topology with elementary routing requirements. A set of N deterministic servers, the ith of which receives from exogenous sources customers at a Bernoulli rate of lambda /sub i/, is considered. The servers are ordered from 1 to N and they are constrained so that no two consecutive servers can be busy at the same time. This model represents a PRN in which there are N links connecting N+1 nodes in tandem and in which each of the first N nodes receives packets at rates lambda /sub i/ and wishes to deliver them to its neighbor on the right (the model can easily incorporate the case in which there are messages that need to be transmitted to the left neighboring node). >

The authors address the problem of remote computing in a disturbed environment and describe the features of a simple hybrid protocol for program migration. Simulations indicate that the number of overhead messages can be reduced considerably. The algorithm uses a hybrid scheme (a combination of sender-initiated and receiver-initiated). The first approach is used when the system is heavily loaded, and the second when the system is lightly loaded. The system toggles between these two schemes on a dynamic basis. The algorithm exhibits fairness and collapse of one node does not lead to total system collapse. >

High-speed message communications is addressed. Each node in the system consists of multiple processors interconnected by a broadcast bus, but the individual nodes are interconnected by an arbitrary network. The concept of a poll number is proposed to control the access to an intranode bus, minimizing the probability of real-time messages missing their deadlines. When a task generates a time-constrained message, a poll number associated with the message is computed on the basis of the message deadline and the task priority. When the bus is free, the various tasks at a node which desire to use the bus write the poll number onto the bus and read it back, one bit at a time, starting from the most significant bit. If at any time the bit read back is different from the bit written, then that particular task drops out of the competition for the bus. The mechanism provides for not only decentralized control of the intranode bus, but also a high degree of flexibility in scheduling messages by different ways of generating poll numbers. The probability of a message missing its deadline in a token bus is found to be much higher than in a polled bus. >

Heuristics for constructing low-cost multicast spanning trees in a dynamic environment are investigated. Two heuristic algorithms are developed that update the multicast tree incrementally as the membership changes and reduce the total bandwidth required for sending data and control messages. The broadcast tree based algorithm makes use of a tree structure in the network, and the other algorithm joins a new member to the node that is nearest to it and is already in the multicast tree. A simulation model is used to study the performance of the algorithms and to compare them with the best-known heuristic algorithm developed by D.W. Wall (1980) which computes the multicast tree structure for a given membership of the group. >

The problem of obtaining a global state or snapshot of a distributed processing system is considered. A message-efficient protocol is presented for obtaining incremental snapshots. First, worst-case lower bounds on the number of messages used by any protocol that solves the incremental snapshot problem are given, and then a protocol that is message-efficient is provided. This protocol obtains a snapshot of the system using the most recent snapshot. The message complexity of the incremental snapshot protocol matches the two lower bounds simultaneously, and hence the protocol is asymptotically message optimal. For applications in database systems, debugging distributed programs, monitoring events, or checkpointing, the protocol is asymptotically message optimal. Because of its simplicity, the protocol can be used readily, and since it uses the minimum number of additional messages, the throughput of the distributed system is not adversely affected. >

The message transport network (MTN), a high-capacity message switch based on fast-packet technology, is described. In its initial form it has 32 nodes that can be simultaneously interconnected at a 32 Mb/s rate through a nonblocking matrix. In its full configuration it can interconnect 128 nodes at an aggregate rate of 2.5 million packets per second. Redundancy, fault detection and isolation, and maintenance features, facilitate achieving the desired availability and maintainability. The modular architecture of the MTN permits cost-effective solutions for a wide range of applications found in telephony. >

Several access control strategies are studied for handling a mixture of wideband and narrowband traffic over a common time-division-multiplexing communication link. The access control schemes are two-side moving-boundary strategies with blockable and queuable policies for wideband and narrowband messages. These strategies can provide some useful insight for the future broadband ISDN user access developments. >

The authors detail the system architecture of a communications processor that uses an existing distributed message switching data communications network as the transport medium for the Arinc Transaction Terminal Service (ATTS) application. Salient features of a powerful communications controller board are described and the organization of the software is outlined to show how the hardware/operating system dependence is minimized to enhance software portability. >

The process of designing the conformance testing specification manual X.403/CTSM.1 for interpersonal messaging systems is described. This CCITT document was developed by two working groups of the Swiss PTT project. The notation for test-case specification and a number of decisions taken to arrive at this notation are explained. The CTSM.1 manual was used as a reference for the other documents on X.400 conformance testing, the techniques are also valid from the CTSM.2 and CTSM.3 test manuals, concerning conformance testing of message transfer systems and reliable transfer servers, respectively. >

The allocation of slots or link-capacity assignment for throughput maximization in emerging synchronous time-division-multiplexing (TDM)-based networks is considered. Taking into account the increasing disparity between the very high speeds of optical communication and the current capabilities of the switching nodes, a communication model is presented, targeted towards preventing congestion from occurring at the intermediate switching nodes due to insufficient buffer space or switching capacity. The proposed model is based on limiting the number of messages the switching node is required to handle in any given time slot. To maximize throughput in these networks, a linear programming solution is presented. The approach is unique in accounting for end-to-end traffic and network routing in the solution. >

The authors perform an analysis and performance comparison of queueing systems operating under a message waiting-time or a delay-time constraint. Four different system admission and preemption policies are investigated. Under either a wait-time constraint or a delay-time limit, arriving messages are either always admitted (and then properly dismissed if their required residence limits are not met) or a determination is made upon arrival as to whether the new message can be served to completion within its required time limit, and only then is this message admitted. The authors investigate and compare the delay-throughput performance of these admission and service-preemption policies for communications and processing systems modeled as a single server M/G/1 queueing system. The authors also set up a cost function which incorporates cost components for system throughput, as well as for implementing the observation and monitoring function and for message residence times. >

Worldwide activities related to conformance testing of X.400 message-handling systems are discussed. The test laboratories and test tools are described. Technical and operation problems that are being encountered and their solutions are examined. >

A 100 Mb/s*2 optical dual ring system called Pana-Lan-100 has been developed which supports both packet switching and circuit switching service on a slotted ring. The circuit switching slots, which can be used for telephone and high-speed facsimile, are assigned dynamically on demand. The MAC (memory access controller) sublayer packet switching is done by a one-chip VLSI called the TRP (token ring processor), which executes a proprietary token protocol using all the remaining slots of the frame except circuit switching slots at the rate of 100 Mb/s. As the maximum packet size of the TRP is designed as 64 Kbyte it is suited to bulk data transmission. >

The authors consider a multiaccess communication channel, such as a token-based ring or bus network. A message priority based polling procedure is used to control access of messages onto the channel. This procedure requires the server to have no advance information concerning the number of messages resident at a station prior to its visit to the station. Messages arriving at each station belong to one of two priority classes: class-1 (high priority) and class-2 (low priority). Class-1 messages are served under an exhaustive service discipline while class-2 messages are served under a limited service discipline. Class-1 messages have nonpreemptive or preemptive-resume priority over class-2 messages resident at the same station. Two different schemes, corresponding to the nonpreemptive and preemptive-resume priority disciplines, respectively, are analyzed. Tight upper and lower bounds for the mean message waiting times for each individual message class are obtained. >

The authors explore the feasibility of a local name server for message handling services conforming to OSI standards but using ad hoc solutions for name-to-address mapping. The name server handles the restricted subset of names that correspond to the users of a single organization and can be managed under the responsibility of the organization. This strategy makes it possible to implement a simple name server that is capable of providing name-to-address mapping for messages sent to users belonging to the organization. The strict limitation to the scope of local names is necessary to relinquish interactions with other name servers, but it also makes it difficult to provide name-to-address mapping for messages within an outside destination. As a substitute, a global aliasing facility is proposed that provides a centrally managed set of aliases and is accessible to all users of the organization. As a verification of the feasibility of this approach, a prototype has been built. The prototype can be implemented as a gateway between the organization and the outside world. This technique has the advantage of permitting the interworking with almost all interim implementations of message handling systems and of being a good base for the migration to a real OSI name service once it becomes available. >

The effect of message-class dependent threshold-type scheduling on the queueing delay and resequencing delay for the M/M/n queueing system is analyzed. The authors derive the expressions for the mean queueing delay and resequencing delay for the M/M/n queueing system shared by C different message classes. A numerical calculation is carried out for the queueing system with two servers. It is found the message-class dependent threshold-type scheduling is effective in reducing the resequencing delay of some specific message class, and, thus, the proposed scheduling can satisfy the different requirements of the different message classes. >

A performance analysis of a hybrid circuit-switched transmission resource at a network node providing service to two traffic streams is presented. Type-1 messages gain access to the system if the node capacity is not saturated, otherwise they overflow to a buffer queue. Type-2 messages are assumed to enter directly into the buffer queue. The performance measure is the average number of messages in the buffer and is evaluated by means of exact and appropriate computational procedures. Comparative numerical results along with suggestions for further research are included. >

A flexible architecture model is presented to implement low-layer protocols into silicon. This model is especially well adapted to real-time features (as in industrial and control-command LANs) and provides a significant increase in the message processing speed. The goal is to propose a systematic approach to the problem of communication protocol implementation in hardware: the design methodology presented can lead to architecture synthesis starting from a behavioral description of the protocol in a dedicated language. >

The authors present a clock synchronization algorithm, a posteriori agreement, based on a new variant of the well-known convergence nonaveraging technique. Exploiting an obvious characteristic of broadcast networks, largely reduces the effect of message delivery delay variance. In consequence, the precision achieved by the algorithm is drastically improved. Accuracy preservation is near to optimal. The solution does not require the use of dedicated hardware. >

Generalized stochastic Petri nets were used to model time-constrained message transmission over a single multiple-access channel to get the performance limits, which show the percentage of successful message transmission. These Petri net models reflect different assumptions about the laxity and length distributions of real-time messages. The results from the Petri net models are shown to agree with those from queuing system models. >

Protocol specifications play an important role in telecommunications software specifications and many techniques exist to support design and analysis of protocol specifications. Among these are techniques for transformation between sequence charts and specification description language (SDL), which are discussed. Principles for translation between a specification in SDL and a specification in state transition diagrams are discussed, and a transformation technique between a specification in a state transition diagram and a specification in message sequence charts is described. A cyclic expansion-based protocol validation and component-based protocol synthesis are adopted to realize an efficient transformation. >

The authors describe the implications of Defense Message System (DMS) message time-of-delivery requirements in the Government Open Systems Interconnection Profile (GOSIP) environment. DMS precedence/priority handling mechanisms and their implementation in the protocols in the GOSIP stack are examined. It is shown that there are precedence-related mechanisms available in the communications protocols mandated by GOSIP. However, to guarantee timely delivery of DMS messages, a US Department of Defense protocol profile should be developed that mandates and specifies the implementation of these mechanisms in all appropriate layers of the systems/networks that handle DMS messages. >