bluuebunny/crossref_metadata_2025 huggingface dataset:
Complexity of approximation algorithms for combinatorial problems
Authors: Gens Georgii , Levner Evgenii
Published: October 2004

In this survey we examine recent results on the complexity of approximation algorithms which have appeared in Russian.
On teaching theoretical foundations of Computer Science
Authors: Mandrioli Dino
Published: October 2004

Theoretical foundations of Computer Science (Automata Theory, Complexity, Formal Languages . . .) are taught almost everywhere within Computer Science curricula. However little effort is usually done to present this material in an integrated and motivated way, that is in such a way that its application and use in the solution of practical problems appears to any student.A proposal is developed in order to overcome this inadequacy and to emphasize the basic aspects of theoretical Computer Science.
Coin flipping by telephone a protocol for solving impossible problems
Authors: Blum Manuel
Published: October 2004

Alice and Bob want to flip a coin by telephone. (They have just divorced, live in different cities, want to decide who gets the car.) Bob would not like to tell Alice HEADS and hear Alice (at the other end of the line) say "Here goes . . . I'm flipping the coin. . . . You lost!"Coin-flipping in the SPECIAL way done here has a serious purpose. Indeed, it should prove an INDISPENSABLE TOOL of the protocol designer. Whenever a protocol requires one of two adversaries, say Alice, to pick a sequence of bits at random, and whenever it serves Alice's interests best NOT to pick her sequence of bits at random, then coin-flipping (Bob flipping coins to Alice) as defined here achieves the desired goal:1. It GUARANTEES to Bob that Alice will pick her sequence of bits at random. Her bit is 1 if Bob flips heads to her, O otherwise.2. It GUARANTEES to Alice that Bob will not know WHAT sequence of bits he flipped to her.Coin-flipping has already proved useful in solving a number of problems once thought impossible: mental poker, certified mail, and exchange of secrets. It will certainly prove a useful tool in solving other problems as well.
A variant of a public key cryptosystem based on Goppa Codes
Authors: Jordan John P.
Published: October 2004

This paper suggests a way in which an interesting Public Key Cryptosystem based on Goppa Codes introduced by R. J. McEliece can be modified and used in a classical way to yield several advantages. The primary benefit is that the rate of the code (or data expansion reciporocal) can be increased by approximately 75%. Secondly (for public key and classical versions), by using a polynomial with no linear or repeated factors instead of an irreducible one to generate the Goppa Code, the code parameters remain the same and the decoding apparatus can be used to test candidate generators. Lastly, a wider range of transformations is made possible. No degradation in security is incurred.
An expression model for graphical command languages
Authors: Olsen Dan R. , Badler Norman
Published: October 2004

A unified command model for interactive systems is presented based on the expression syntax of PASCAL-like languages. The relationships between command specification and feedback as they relate to command structure are reviewed for both continuous and discrete interactions. The advantages of a discrete prefix command structure are presented in relationship to the PASCAL expression mechanism.The procedure mechanism of PASCAL-like languages is presented as a basis for graphical command specifications. The advantages of such a model are discussed in terms of borrowed knowledge from compiler construction and user familiarity. The automatic generation of interactive systems from such a model is discussed.An extended example of how procedure declarations can serve as the basis for interactive command definition is given. It is shown how menu-driven systems can be automatically generated from such a description. It is also shown how by extending the procedure declaration it is possible to support iconic identifiers, function buttons and locater and valuator type devices.The role of data types in such a command model is explored in depth. The notion of using a typed data value as a pick identifier is presented. It is shown how such typed identifiers can be integrated into the command model to provide automatic error checking and resolution of ambiguous pointing.
Sense of direction, topological awareness and communication complexity
Authors: Santoro Nicola
Published: October 2004

Based on some recent results, it is here argued that the communication complexity of distributed problems can be greatly affected by two factors hereby identified as 'sense of direction' and 'topological awareness'. It is also suggested that 'insensitivity' to either or both factors is an indicator of the inherent difficulty of a distributed problem. A bibliography of recent results is included.
Dynamic code replacement and Ada
Authors: Tindell Ken
Published: October 2004

There is a problem in trying to maintain highly reliable software which must continue executing over a long period of time. This problem is characterised by the international space station
Freedom
. The space station has a long planned lifetime and requires that the computer system remain running for this period. Updates to software normally require reloading. This paper reports on a study into eliminating the need for reloading by providing mechanisms whereby Ada programs can be changed in a consistent manner, permitting the execution of the system to continue.
Deterministic priority inversion in Ada selective waits
Authors: Lander Leslie , Mitra Sandeep , Piatkowski Thomas
Published: October 2004

Priority inversion is any situation where low priority tasks are served before higher priority tasks. It is recognized as a serious problem for real-time systems. In the course of building a performance model for multi-tasking Ada software, we have noticed that a fair algorithmic selection procedure may be likely to cause priority inversion in selective waits. This effect is in addition to the well-known priority inversion due to the FIFO nature of entry queues. As an illustration, we present a semi-formal partial model of the selective wait algorithm of the Alsys
1
' 286 DOS Ada Compiler v4.2, running under PC-DOS Version 3.30 on an IBM PC/AT
2
The model was deduced from a series of experiments designed to illuminate the scheduling features of the system. These results may provide useful insight for users of this and other Ada compilers since priority inversion may occur in the way we describe in many systems. We also indicate one standard technique to avoid priority inversion at selective waits.
A method for converting abstract objects to discrete objects
Authors: Weidman Henry
Published: October 2004

This paper specifies how to use truth tables to convert abstract objects to discrete objects. An abstract object is defined as an object which has no specific parameters assigned to describe its dimensions. A discrete object has specific well defined parameters which describe its dimensions. A mechanical method for producing program code from a truth table is specified. Procedure steps are provided for using the method. A real world object conversion example is discussed. Program code examples are written in Ada.
Some applications of a technique of Sakoda and Sipser
Authors: Ravikumar B.
Published: October 2004

Sakoda and Sipser [Sa78] introduced a technique for constructing certain regular languages over a large alphabet and used these languages as candidates for proving lower bounds on the size increase when converting a nondeterministic finite automaton (NFA) to a deterministic one (DFA). The purpose of this note is to show that their method is quite useful in solving several problems in the theory of regular languages. In view of its intuitive appeal, we recommend it as a pedagogic aid for presenting lower bound proofs.
Figures of merit: the sequel
Authors: Tompa Martin
Published: October 2004

Science has marched on despite the appearance of the original "Figures of Merit" [18]. The purpose of this survey is to bring the community up to date on the most recent bounds, so that we may collaborate to improve them.
A formal protocol conversion method
Authors: Okumura K
Published: October 2004

The need for the protocol conversion has been recognized with the proliferation of heterogeneous networks. From a formal viewpoint, we regard that problem as generating a protocol which satisfies the properties of the conversion. In this paper, we prove that, one can determine whether a converter exists, for some protocol classes, given protocols in the form of communicating finite automata, Moreover, we give a construction method for such a converter for those classes, and derive an upper bound of the computational complexity of the construction algorithm.
A model for evaluating demand assignment protocols with arbitrary workloads
Authors: Koren Z , Chlamtac I , Ganz A
Published: October 2004

Demand assignment protocols have been implemented in a large number of operational LANs. However, the analytic models for protocol evaluation currently capture only a limited range of LAN operational circumstances. In this paper we present an analytic tool for evaluating fair and prioritized demand assignment protocols with a relatively general workload model. We consider arbitrary and station dependent message size distributions and arrival rates. This allows the modeling of LANs with heterogeneous workloads, thus permitting a larger correspondence between the modeled system and the real life network.
Implementing priorities in multiaccess protocols for optical fiber-based local area netorks
Authors: Vo-Dai T
Published: October 2004

Most recently proposed optical fiber-based LAN architectures may be considered as different implementations of the basic round-robin transmission service in different topologies using special signal patterns or events to achieve the effect of the token passing protocol. Prioritizing the transmission of various data and control messages is necessary for time-critical applications (e.g. in data sensor or process control applications). Some extensions of the basic CSMA-CD protocol to handle packet priorities have been proposed for bidirectional channels but prioritized multiaccess protocols taking advantage of the unidirectional property of optical channels do not appear to be widely available yet. The main thrust of this paper is to propose some
distributed
prioritized multiaccess protocols for twin-bus optical channels. We will introduce two prioritized protocols: one uses the token packet to convey and enforce priorities and the other employs time-outs to achieve prioritization. Our protocols require only backlogged stations to be active.
Real-time voice communications over a token-passing ring local area network
Authors: Friedman E , Ziegler C
Published: October 2004

This paper describes an implementation of a real-time, packetized voice communication system over a personal computer (PC) based token-passing ring local area network. System configuration and operation are presented. The system implements real-time, conversational transmission of voice packets between two stations on the network. An analysis is shown to calculate the maximum number of two way conversations that can be handled by the system without any reconstitution delay.
Command execution in a heterogeneous environment
Authors: Korb J T , Wills C E
Published: October 2004

As a user's computing environment grows from a single time-shared host to a network of specialized and general-purpose machines, the capability for the user to access all of these resources in a consistent and transparent manner becomes desirable. Instead of viewing commands as binary files, we expect the user to view commands as services provided by servers in the network. The user interacts with a personal workstation that locates and executes services on his behalf.

Executing a single service provided by any server in the network is useful, but the user would also like to combine services from different machines to perform complex computations. To provide this facility we expand on the UNIX notion of pipes to a generalized pipeline mechanism containing services from a variety of servers. In this paper we explain the merits of a multi-machine pipeline for solving problems of accessing services in a heterogeneous environment. We also give a design and performance evaluation of a general mechanism for multi-machine pipes using the DARPA UDP and TCP protocols.
Voice transmission in a priority CSMA/AC LAN: an efficient protocol using hybrid switching
Authors: van da Lagemaat J , Daemen J M A , Niemegeers I G
Published: October 2004

The integration of voice and data transmission on a CSMA/CD LAN with message priority and deterministic collision resolution is studied. As a result an efficient Stream Traffic Protocol using hybrid switching and implicit token passing is designed. The performance of the protocol both for voice and data is analysed using a discrete event simulation model. The protocol increases the system capacity for voice while the strict real-time constraints for its transmission are still met. It supports a number of subscribers comparable with the equivalent to the capacity of a small PABX, with a good performance for data. The work is part of an overall project of an integrated services LAN offering ISDN S-interfaces.
A framed movable-boundry protocol for integrated voice/data in a LAN
Authors: Sharrock S M , Maly K J , Ghanta S , Du H C
Published: October 2004

A new, fully-distributed protocol for integrated voice/data traffic in a local-area, random-access broadcast network is described. The protocol introduces a movable voice-data boundary to framed TDMA/CSMA and eliminates the requirement of system-wide synchronized clocks. The movable boundary is a major advantage in any system where fluctuations in voice and data loads are expected because assignment of idle capacity from one traffic class to the other increases the utilization of the channel. The protocol provides collision-free virtual circuits for voice and periods of non-persistent CSMA/CD for data traffic and call establishment, and can support multi-party calls as well as two-way conversations. The protocol allows variable-size voice packets that have very low overhead and variable-size data packets that may be much longer than voice packets. This is of significant practical advantage over previous work, which has required fixed-size voice and/or data packets, or voice packets with high overhead. A method of dynamically controlling the movable boundary to balance the voice and data traffic is also proposed.
Tier automation representation of communication protocols
Authors: Bavel Z , Grzymala-Busse J , Hsia Y , Mancisidor-Landa R
Published: October 2004

The tier automation is presented as a model for communication protocols. Several advantages of the model are cited, among which are universality of representation and manipulability. A scheme for using the tier automation to model specific distributed architectures and their protocols is described. The scheme is then used on a sample protocol and a transmission session with the sample protocol as exhibited.
A petri net reduction algorithm for protocol analysis
Authors: Ramamoorthy C V , Yaw Y
Published: October 2004

Petri net is a powerful model for analyzing communication protocols because they share many common properties. Currently, protocol analysis suffers the state explosion problem especially for error-recoverable protocols and multi-party protocols. Protocol synthesis relieves this problem by generating new and complicated protocols from simple subsets of the protocol models. Reduction analysis provides theoretical ground for correct synthesis or expansion. Thus, reduction is a very important research area. In this paper, we present a general Petri net reduction algorithm that reduces the number of states while preserving all desirable and
undesirable
properties. To the best of our knowledge, this is the first general Petri net reduction algorithm for protocol analysis. We first present and extend Dong's [DON 83] definition of WBMs to include more subnets as WBMs. To render the reductions automated, a new concept of simple well-behaved modules (SWBMs) is introduced. Recursively performing reductions of SWBMs, complicated WBMs can be reduced. A main program is written to implement this recursive procedure. The problem is then reduced to finding conditions for SWBMs. We do this by progressing from simpler SWBMs to more complicated ones, i.e., from single-arc ones to multi-arcs ones. Finally, we demonstrate the usefulness of this algorithm by applying it to the state exploration in protocol synthesis. Other applications such as error detection, performance evaluation, and software engineering will be discussed in future.
Frequency-time controlled (FTC) networks for high speed communication
Authors: Chlamtac I , Ganz A
Published: October 2004

The development of “very high speed” networks is being motivated by emerging applications and is therefore attracting increasing attention. As demonstrated in the past, in conventional high speed systems the high ratio between the end-to-end propagation delay and the message transmission time severely restricts the system performance. Thus the increase in channel bandwidth may be accompanied by only a marginal increase in actual system capacity. In this paper we propose a network architecture which eliminates this problem by introducing a combined Frequency - Time Division based control of the high speed channel. We consider the implementation characteristics of the resulting multichannel system and show that the design of protocols in these systems is subject to unique channel control penalties. Specifically, we show that in addition to the relatively high cost of channel sensing, the allocation of channel on a demand assignment basis is hindered in the multichannel configuration by the time penalty involved in locating an idle channel and by practical limitations of multichannel node interface design. We therefore introduce a new class of “allocation” protocols in which the channel access is obtained without the aforementioned penalties. The allocation protocols build on message source and destination oriented transmission rights allocation, taking into account the implementation aspects of multichannel networks. We show that the class of “multichannel allocation” protocols covers the whole range of random access to fixed channel access control policies and introduce an analytic approach for a uniform analytic treatment. The analysis demonstrates the potential for a significant improvement in the system capacity and the average message delay, when compared to a conventional single (undivided) channel system.
Performance analysis of a satellite communications backchannel architecture
Authors: Baum D
Published: October 2004

The definition of a backchannel architecture for open systems interconnection over satellite links has been the subject of the SENS-project
1
The new proposal is based on existent international standards and uses the options of the ISO-class 4 transport layer protocol in order to enclose in level 4 data link control functions for unidirectional satellite links following the rules of the IBM-checkpoint protocol. This paper provides performance values of the SENS architecture in comparison with those of common satellite communication systems. With means of elementary probability theoretical methods an approximate analysis of the IBM-checkpoint protocol is accomplished. The results show that for large amounts of data the new architecture proves to be best suited for cost efficient use of public satellite data links.
A closer look at Noahnet
Authors: Faber D J , Parulkar G M
Published: October 2004

Noahnet is a robust, highly available, high bandwidth local area network (LAN) architecture, in the implementation phase at the University of Delaware. Noahnet uses a distributed switch-oriented node topology, a flooding approach for message routing, and high bandwidth communication media. The purpose of this paper is to consider some of the important issues in detail such as: the various ways flood control can be implemented; their relative advantages/disadvantages; the functions of a node; and one possible implementation of a node in Noahnet. Expected performance of the Noahnet in comparison to Ethernet and token ring networks is also discussed. Though Noahnet uses more complex structure and protocol, we demonstrate that the overhead of using flooding in Noahnet is minimal and that a Noahnet node implementation is very simple and inexpensive. The paper concludes that Noahnet provides features such as robustness, high availability, high throughput, and high communication band width at almost no additional cost.
An interactive test sequence generator
Authors: Ural H , Short R
Published: October 2004

The interactive test sequence generator (ITSG) is a software tool which provides the capability of generating test sequences from logic specifications in an interactive manner. A logic specification is a collection of Horn clauses coded in Prolog describing the externally observable behaviour of a system. ITSG facilitates a controlled traversal of the execution paths described by a logic specification and is written in C_Prolog running under UNIX 4.2 on Vax 750.

In this paper, first the form of logic specifications is described and an outline of a logic specification for a protocol entity (i.e., protocol specification) is presented. Then, ITSG is introduced and its functionality is explained. As well, the possible usage of ITSG in constructing conformance test suites for protocol implementation testing is discussed and a simple scenario for developing a conformance test suite is presented.
Inter-organization networks: implications of access control: requirements for interconnection protocol
Authors: Estrin D
Published: October 2004

When two or more distinct organizations interconnect their internal computer networks they form an
Inter-Organization Network(ION)
. IONs support the exchange of cad/cam data between manufacturers and subcontractors, software distribution from vendors to users, customer input to suppliers' order-entry systems, and the shared use of expensive computational resources by research laboratories, as examples. This paper analyzes the technical implications of interconnecting networks across organization boundaries.

After analyzing the organization context in which IONs are used, we demonstrate that such interconnections are not satisfied by traditional network design criteria of connectivity and transparency. To the contrary, a primary high-level requirement is access control, and participating organizations must be able to limit connectivity and make network boundaries visible. We describe a scheme based on non-discretionary control which allows interconnecting organizations to combine gateway, network, and system-level mechanisms to enforce cross-boundary control over invocation and information flow, while minimizing interference with internal operations.

Access control requirements such as these impose new requirements on the underlying interconnection protocols. We demonstrate such alternative interconnection protocols that support loose coupling across administrative boundaries and that accommodate the necessary control mechanisms. Message-based gateways that support non-real-time invocation of services (e.g., file and print servers, financial transactions, VLSI design tools, etc.) are a promising basis for such loose couplings.
Extending a capability based system into a network environment
Authors: Sansom R D , Julin D P , Rashid R F
Published: October 2004

The Mach operating system supports secure local communication within one node of a distributed system by providing protected communication abstraction can be extended over a network by Network Server tasks. The network servers effectively act as local representatives for remote tasks by implementing an abstraction of Network Ports. To extend the security of the port-based communication abstraction into the network environment, the network servers must protect both the messages sent over the network to network ports and the access rights to network ports. This paper describes in detail the protocols used by the network servers to support security.
Communication services under EMCON
Authors: Nguyen B , Rom R
Published: October 2004

Hosts are under EMCON condition, short for Emission Control, when they are prohibited from transmitting any data. Under such condition, hosts can only receive data passively and can not acknowledge any data reception. This unidirectionality of the communication channel breaks down all currently defined transport protocols. In this paper, we present architectural alternatives that would support limited communication service under such condition and also discuss other open issues.
Access control for network directory systems
Authors: Goodwin M , McDonell K J
Published: October 2004

Directory Systems to support communications networks are currently the subject of serious international standardization efforts. The most recent CCITT and ISO proposals for Directory Systems are summarized, and within this context the requirements for flexible and robust access control mechanisms are examined. The existence of varied access control policies at the international, national and local levels and the need to maintain the integrity of Directory System information are identified as major factors determining access control procedures. Techniques are suggested for access control mechanisms capable of
capturing
and
enforcing
the relevant access control semantics at each network site.
Control procedures for slotted Aloha systems that achieve stability
Authors: Clare L P
Published: October 2004

A class of slotted ALOHA dynamic control strategies is considered. These strategies are simple to implement and can yield lossless and stable operation for arbitrarily large user populations with aggregate arrival rates below
e
-1
packets/slot. An ergodicity analysis is given that provides conditions on the system parameters, such that any specified set of control parameters that satisfies the given conditions is guaranteed to yield stable performance. The system state is modelled as a two-dimensional Markov chain that incorporates the backlog (the number of packets awaiting retransmission) and the estimate of the backlog. The geometrical concepts are illustrated by figures corresponding to an example case. Simulation results are presented that compare alternative control schemes.
A two-bit contention-based TDMA technique for data transmissions
Authors: Tsai D , Chang J
Published: October 2004

The performance of a contention-based TDMA technique is studied in this paper. The frame structure of the time-axis is similar to [1] and [2]. The protocols proposed in [1],[2] and here are all active multiaccess techniques. The protocol in [1] is contention free and suitable for heavy traffic while a contention-based protocol suitable for light traffic is considered in [2]. The protocol to be studied in this paper is also contention in nature and performs considerably better than [2]. This protocol is less complicated than [1] and out-performs [1] unless traffic is very high. Performance analyses, both transient and steady-state, have been successfully completed. Results obtained include average queue length and packet delay, etc. The validity of analysis is also verified by computer simulations.
A reliable datagram protocol on local area networks
Authors: Lee D , Chon K , Chung C
Published: October 2004

Most of interprocess communications in transaction oriented distributed systems are based on client-server model, in which one process communicates with several processes simultaneously. Datagram service fits this type of communication rather than virtual circuit service. Transaction oriented distributed systems sometimes need to move large data such as a file or a part of database from a machine to other. The reliable delivery is fairly important since an error might cause retransmission of a whole data. In this paper, we propose the efficient mechanism for reliable datagram service, i) the concept of
semi-virtual circuit
and ii) the simple error detection and recovery algorithm based on our existing transport protocol, UDSTP. We describe implementation details supporting those facilities and performance results.
A model of file server performance for a heterogeneous distributed system
Authors: Ramakrishnan K K
Published: October 2004

In this paper, we study the performance characteristics of a client-server style distributed system by a queueing network model. The system being modeled was based on an experimental distributed system currently being prototyped. As a specific detailed case study, we have evaluated the performance of a file server. A file server is a key component to achieve the data sharing necessary in a distributed system. The file server is probably the most heavily used resource of the distributed system and as a result, its performance is critical to the success of the system. The primary goal of the study was to identify and quantify the effects of the bottlenecks in the server and assess design alternatives to enhance performance. In particular, the improvements due to file caching, outboarding transport functions and the effect of multiple network interfaces were studied. We model in detail the various stages of processing of a request to a file server. Parameterization of the model was achieved by initial measurements made on the prototype system. An important characteristic modeled was the buffer overflow from the network interfaces. This required the approximate solution of a non-product-form queueing network.
Distributed system V IPC in LOCUS: a design and implementation retrospective
Authors: Fleisch B D
Published: October 2004

This paper describes new interprocess communications facilities that have been added to the Locus system [POPEK 81][WALKER 83]. The facilities improve Locus's interprocess communication repertoire by providing distributed support for three separate subsystems from System V UNIX:
messages, semaphores
, and
shared memory
. Here we describe these subsystems and their integration into in the Locus architecture.
VMTP: a transport protocol for the next generation of communication systems
Authors: Cheriton D
Published: October 2004

The Versatile Message Transaction Protocol (VMTP) is a transport-level protocol designed to support remote procedure call, multicast and real-time communication. The protocol is optimized for efficient page-level network file access in particular.

In this paper, we describe the significant aspects of the VMTP design, including the VMTP treatment of sessions, addressing, duplicate suppression, flow control and retransmissions plus its provision for multicast. The VMTP design reflects a change in the use of computer communication as well as a change in the underlying hardware base for the next generation of communication systems. It also challenges certain established notions in the design of protocols.
Formal specification and verification of a connection establishment protocol
Authors: Schwabe Daniel
Published: October 2004

This paper presents an exercise in the verification of a connection establishment protocol. A specification language named SPEX, tailored for the needs of communications protocols, is proposed, and its relation to a semi-automated verification system, AFFIRM, is discussed. This language is then used to specify a connection protocol currently being used. Certain errors are uncovered by analysis using the verification system. However, the major portion of the protocol's operation are shown to be correct.
HDLC reliability and the FRBS method to improve it
Authors: Selga J. , Rivera J.
Published: October 2004

This paper arrived late and can be found, published in full, on pages 260-267 of the Proceedings.
Digital signature schemes for computer communication networks
Authors: Meijer Henk , Akl Selim
Published: October 2004

This paper introduces four new digital signature schemes for computer communication networks. These involve one or more arbitrators who validate and authenticate messages and signatures without having access to the actual contents of the messages.
SNATCH opens manufacturers' networks through gateways
Authors: Einert D. , Glas G.
Published: October 2004

At the present manufacturers' network architectures do not provide co-operation between systems exceeding the boundaries of their own homogeneous networks, i.e. open systems as defined the ISO Reference Model of Open Systems Inter-connection do not yet exist. Project SNATCH shows to open the closed network architectures of two important computer manufacturers by means of gateway system. Mapping the manufacturers protocols onto neutral protocols and vice versa, gateway system acts as a channel between the closed manufacturers' networks. Since this solution is in principle not restricted to systems of only two manufacturers, SNATCH points out a practicable way to a generally open system.
A heuristic method for optimizing an intercity data transmission network
Authors: Pazos Rodolfo A.
Published: October 2004

This paper deals with the problem of finding the minimum cost flow pattern for a large intercity data transmission network which provides private lines between pairs of cities and which is subject to capacity constraints. This problem can be formulated as a minimum cost multicommodity flow problem. The most efficient linear and integer programming approaches yield programs with memory requirements proportional to the square of the problem size, making impractical their use for large scale problems. In this paper a heuristic method is described which produces suboptimal solutions with smaller execution time requirements, and memory requirements linear with the problem size. Experimental results are presented comparing the proposed method with a Linear Programming approach.
Modeling and analysis of flow controlled packet switching networks
Authors: Lam Simon S. , Lien Y. Luke
Published: October 2004

Packet switching networks with flow controlled virtual channels are modeled by closed multi-chain queueing networks. The tree convolution algorithm for an exact analysis of such models is discussed. The algorithm is very efficient when routing chains have sparseness and locality properties that are typical of communication network models. The accuracy of an approximate model of equivalent open chains was investigated. An optimal routing criterion for adding a virtual channel (with a window size of one) to an existing network is explored.
TORNET
Authors: Vranesic Z. G. , Hamacher V. C. , Loucks W. M. , Zaky S. G.
Published: October 2004

TORNET is an experimental local area computer network presently being designed and built in the Computer Group Laboratory of the Department of Electrical Engineering at the University of Toronto. The network consists of a number of local rings, each attached to a central ring. The local rings employ a variation on the slotted-ring format that uses a limited insertion technique to achieve reasonable response times for character traffic among many devices and small computers. Two fixed-length packet formats (one byte or 128 bytes of data) are used on the local rings. Only the longer format is used on the central ring which generally provides record level access to shared specialized equipment.

The main objective in the local ring design is a low-cost port for inexpensive terminals, sensors, etc. The paper concentrates on the functional characteristics of the local rings, including delay-throughput comparisons with other well-known ring schemes.
The cost of data replication
Authors: Garcia-Holina Hector , Barbara Daniel
Published: October 2004

With the advent of data communication networks, researchers have been looking at the possibility of placing copies of a database at two or more nodes of a network. Such data replication is interesting because it makes the database accessible even when some of the nodes in the system fail. Furthermore, transactions which only read data may get faster access to the data when multiple copies exist.

Due to the complex and time consuming update protocols, and due to the additional required hardware, data replication has a definite cost. This cost factor is often overlooked in discussions on replicated data, so in this paper we examine some of the cost issues involved. We argue that the cost of replicating data is so high that only in very special cases will data be replicated at different nodes of a computer communication network and kept in a consistent state. We also discuss some alternate approaches to data replication (like data replication at a single node and shadow copies).
Isolated word recognition based upon source coding techniques
Authors: Buzo Andres , Martinez Horacio , Rivera Carlos , Jazcilevich Aron
Published: October 2004

This paper arrived late and can be found, published in full, on pages 268-270 of the Proceedings.
Why a ring?
Authors: Saltzer Jerome H. , Clark David D. , Pogran Kenneth T.
Published: October 2004

In a world increasingly populated with Ethernets and Ethernet-like nets a few sites continue to experiment with rings of active repeaters for local data communication. This paper explores some of the engineering problems involved in designing a ring that has no central control, and then compared the M.I.T.-designed ring with Ethernet on a variety of operational and subtle technical grounds, on each of which the ring may possess important or interesting advantages.
An overview of BLN
Authors: Coates K. E. , Dvorak D. L. , Watts R. M.
Published: October 2004

The Bell Laboratories Network (BLN) provides a host-to-host networking service that has been specifically designed for the heterogeneous computer environment at Bell Laboratories. BLN incorporates two important concepts: a 7-layer architecture similar to the one currently being proposed by ISO and CCITT, and implementation techniques that allow most of the networking software to reside in totally portable modules. BLN has been operational since March, 1979 in first a 3-node and then in an 8-node prototype network. It is now being deployed to replace the existing interlocation network in Bell Labs. In this paper we provide an overview of the network service requirements and the architecture and implementation that was developed to provide those services.
48-bit absolute internet and Ethernet host numbers
Authors: Dalal Yogen K. , Printis Robert S.
Published: October 2004

Xerox internets and Ethernet local computer networks use 48-bit absolute host numbers. This is a radical departure from practices currently in use in internetwork systems and local networks. This paper describes how the host numbering scheme was designed in the context of an overall internetwork and distributed systems architecture.
HDLC reliability and the FRBS method to improve it
Authors: Selga J. , Rivera J.
Published: October 2004

In view that some international bodies in the field of Telecontrol systems propose reliability requirements for line protocols which are not fulfilled by standard HDLC,here a detailed analysis of the reliability of HDLC is given and the statistical properties of sequences using the Bit Insertion Mechanism are analyzed. The final result is a proposal of a method,the Four Redundancy Bit Sequence method: (FRBS),which seems able to be added without much trouble before and after the HDLC layer to yield a protocol with the desired characteristics.
Dragnet
Authors: Hill Dwight D.
Published: October 2004

This paper proposes a topology for local computer networks. Called "Dragnet", it is similar to the Ethernet network in function, but rather different in the following respects:1. Instead of a single long bidirectional cable, there are multiple short unidirectional cables.2. Just as an Ethernet network may require some number of signal repeaters to join multiple segments, the proposed system always uses one or more simple concentrator units, each one merging several signals into one.3. Each concentrator unit also provides the facility to silence the lines coming into it, thus providing security against any number of bad (jammed) transmitters. (It is this capability that inspired the name "Dragnet.") Most of the remaining good transmitters in the system can continue to send, and all units can receive regardless of the number of errant transmitters.The paper discusses the strengths and weaknesses of the Dragnet approach. The key disadvantage is that the active medium is potentially less reliable than the simplest Ethernet network (one with no repeaters). The key advantages are: simpler, potentially more reliable drivers and receivers; better fault tolerance; and better message verification. In principle, the systems are compatible, and the two might be combined into a hybrid network.
Examining IT professionals' adaptation to technological change
Authors: Gallivan Michael J.
Published: October 2004

This paper examines the challenge of adapting to technological changes in IS departments. It develops a set of hypotheses about how two personal attributes (tolerance of ambiguity and openness to experience) will be associated with IT professionals' ability to adapt to a technological innovation. It also examines the literature on gender in the IT profession, positing that women IT employees will exhibit some differences in job performance (relative to men), but no differences in terms of job satisfaction or turnover intentions. Based on a mixed-method study of two firms that were adopting client/server development, the paper first describes the different implementation strategies employed by each firm, and then analyzes employees' responses to the change. In combining the insights from both case studies and surveys, the results showed that four out of eight hypotheses were fully supported and two received partial support. Women reported lower job satisfaction on a dimension that captures job stress, and this effect was exacerbated in the firm that expected its IT employees to demonstrate considerable initiative to master the innovation. In contrast, the women at the second firm, while showing no differences in job stress (relative to their male peers), nevertheless exhibited a very different pattern of job skills and performance than the men. Finally, the personal attribute that was strongly associated with employees' job satisfaction (openness to experience) was negatively correlated with one aspect of job performance - directly opposite to what was hypothesized. The paper concludes with insights for IS researchers and managers interested in IS personnel and technology implementation.
The impact of e-commerce on the role of IS professionals
Authors: Cash Eugene , Yoong Pak , Huff Sid
Published: October 2004

Understanding the knowledge, skills and abilities of information systems professionals has been a longstanding goal of information systems research. An IS professional's ability to perform in his or her role is vital to the utilisation of information systems within an organisation. This research addresses the question: in what ways has the recent ascension of Internet-based electronic commerce altered the competency requirements of IS professionals? Semi-structured interviews were conducted with fifteen participants from a variety of public and private organizations, who are currently participating or had participated in e-commerce projects. The findings indicate that the implementation of e-commerce in organisations has introduced three main types of business changes: expectations, perceptions, and compliance. These three changes have in turn driven project changes and subsequent changes in the competency requirements and role of the IS professional. The implications of these changes for IS professionals and the organizations for which they work are discussed.
Changing patterns in IT skill sets 1988-2003
Authors: Gallivan Michael J. , Truex Duane P. , Kvasny Lynette
Published: October 2004

This paper examines trends in required job skills for IT professionals. Through an empirical study of classified job advertising for IT professionals over the past 17 years, we evaluate whether the observed trends support earlier predictions offered by researchers who sought to anticipate future job and skill demands (Leitheiser 1992; Trauth, Farwell, & Lee 1993). Many of the findings are consistent with previous studies and support the notion that employers are seeking an ever-increasing number and variety of skill sets from the new hires. In addition, we found ongoing evidence of a recruitment gap (Todd, McKeen & Gallupe 1995) where, despite many firms' stated emphasis on well-rounded individuals with business knowledge and strong "soft skills," the job advertising aspect of the recruiting process continues to focus on "hard skills". The changing demand patterns for IT professionals necessitate life-long learning skills not only for IT practitioners but also for the academics who teach them.
Assessing information technology personnel
Authors: Chilton Michael A. , Hardgrave Bill C.
Published: October 2004

Performance ratings are used as a means to measure and record performance of individuals on any particular job. Results can then be used for promotion, increases in pay and other incentives. They, therefore, can have a large impact on a person's career and are viewed by both employers and employees as extremely important. Performance ratings vary widely and typically include a variety of measures - some of which the employee can control, and others over which the employee has no direct control. Overall, the various types of performance ratings are not perfect; each has its flaws along with its advantages. In this study, one particular type of scale - a behavioral rating scale - is proposed by taking the results of a previous study performed by Green (1989) and empirically testing a set of critical skills for use as a performance assessment instrument for information technology (IT) personnel. The instrument is provided for researchers who wish to incorporate a behavior-oriented measure in their research and for practitioners who may be looking for a behavior-oriented scale to evaluate IT personnel. The psychometric properties of the instrument as observed in this study are also presented.
PERSON
Authors: Rosen Sheldon A. , Melrose Joseph H.
Published: October 2004

Hiring projections, union demands, projecting current trends and the potential impact of new or proposed legislation are the
raison d'etre
for the Department of State Personnel Simulation On-Line System (PERSON). It projects the distribution of Foreign Service Officers and provides an annual analysis of promotions and separations over a ten-year period.A "scratch pad" technique allows up to twenty sets of parameters to be updated from a CRT. Each pad consists of nine matrices representing various aspects of attrition, promotion, requirements and recruitment. The model program then uses these parameters as batch input. Calculations start with the highest Foreign Service class. Within classes, records are processed by job function.Conceptually, individual records are passed against these matrices and can be thought of as passing through two groups of filters. The first group tends to remove people from the system. The second group moves people upward or laterally through the system. This process is repeated for each year of the simulation requested by the user.The PERSON system has been operative since July 1972.