Designing an efficient and scalable packet filter for modern computer networks becomes more challenging each day: Faster link speeds, the steady increase in the number of encapsulation rules (e.g., tunneling), and the necessity to precisely isolate a given subset of traffic cause filtering expressions to become more complex than in the past. Most current packet filtering mechanisms cannot deal with those requirements because their optimization algorithms either cannot scale with the increased size of the filtering code or exploit simple domain-specific optimizations that cannot guarantee to operate properly in case of complex filters. This paper presents pFSA, a new model that transforms packet filters into finite state automata and guarantees the optimal number of checks on the packet, also in case of multiple filters composition, hence enabling efficiency and scalability without sacrificing filtering computation time.

Current Peer-to-Peer (P2P) file sharing systems make use of a considerable percentage of Internet Service Providers (ISPs) bandwidth. This paper presents the Collaborative Locality-aware Overlay SERvice (CLOSER), an architecture that aims at lessening the usage of expensive international links by exploiting traffic locality (i.e., a resource is downloaded from the inside of the ISP whenever possible). The paper proves the effectiveness of CLOSER by analysis and simulation, also comparing this architecture with existing solutions for traffic locality in P2P systems. While savings on international links can be attractive for ISPs, it is necessary to offer some features that can be of interest for users to favor a wide adoption of the application. For this reason, CLOSER also introduces a privacy module that may arouse the users' interest and encourage them to switch to the new architecture.

Network virtualization has gained a lot of attention recently, because of some new interesting proposals in the field (i.e. Open Flow). This trend has had the effect of pushing some filtering operations up at the software level: i.e. extract a potentially large number of protocol fields from a packet, or dynamically combine different filters. The time constraints of working at line rate force the creation of a packet filter model that can guarantee the minimum number of packet checks. This poster proposes mp FSA, a packet filter model based on the Finite State Automata formalism, that aims at achieving optimality w.r.t. the number of packet accesses, without sacrificing efficiency and scalability.

Abstract Shared visualization environments represent an effective means to enhance collaborative work in engineering and scientific design tasks. The availability of high‐speed networks allows researchers to work together from geographically distributed locations, and mobile devices are able to carry out ubiquitous 3D visualization tasks through wireless network connections. This paper presents a scalable architecture for the delivery of shared 3D visualization services to heterogeneous terminals ranging from powerful workstations to mobile devices such as PDAs and smart‐phones. The framework design allows both desktop and mobile clients to simultaneously visualize the same model by sharing a common view. Remote‐rendering servers support effective visualization on thin clients, and a load balancing mechanism provides efficient resource usage. Copyright © 2011 John Wiley & Sons, Ltd.

The wide diffusion of network address translators (NATs) (and, in some respect, firewalls) may prevent some applications that require direct end-to-end connectivity (e.g. real-time media) from being able to connect to the remote party. Although the solutions currently adopted rely on centralised nodes as third party relays, the distributed connectivity service (DISCOS) architecture has been recently proposed and aims at distributing such functionalities across a peer-to-peer (P2P) overlay. The original study presented some performance characteristics of the overlay, but the ability to resist to both failures and attacks was not taken into consideration. This study illustrates the robustness feature of the DISCOS overlay and suggests some minor modifications to the original mechanisms, in order to improve the overall robustness. The key component of DISCOS is its dynamic scale-free topology. Hence, the study also extends the existing literature concerning the robustness of scale-free networks, which considers only static graphs.

While peer-to-peer networks are mainly used to locate unique resources across the Internet, new interesting deployment scenarios are emerging. Particularly, some applications (e.g., VoIP) are proposing the creation of overlays for the localization of services based on equivalent servants (e.g., voice relays). This paper explores the possible overlay architectures that can be adopted to provide such services, showing how an unstructured solution based on a scale-free overlay topology is an effective option to deploy in this context. Consequently, we propose EQUATOR (EQUivalent servAnt locaTOR), an unstructured overlay implementing the above mentioned operating principles, based on an overlay construction algorithm that well approximates an ideal scale-free construction model. We present both analytical and simulation results which support our overlay topology selection and validate the proposed architecture.

While in computer networks the number of possible protocol encapsulations is growing day after day, network admin- istrators face ever increasing difficulties in selecting accurately the traffic they need to inspect. This is mainly caused by the limited number of encapsulations supported by currently available tools and the difficulty to exactly specify which packets have to be analyzed, especially in presence of tunneled traffic. This paper presents a novel packet processing language that, besides Boolean filtering predicates, introduces special constructs for handling the more complex situations of tunneled and stacked encapsulations, giving the user a finer control over the semantics of a filtering expression. Even though this language is principally focused on packet filters, it is designed to support other advanced packet processing mechanisms such as traffic classification and field extraction.

Abstract Scientific research and practical applications of solar physics require data and computational services to be integrated seamlessly and efficiently. The European Grid for Solar Observations (EGSO) leverages Grid‐oriented concepts and technology to provide a high‐performance infrastructure for solar applications. In this paper, an architecture for a data brokerage service is proposed. Brokers interact with providers and consumers in order to build a profile of both parties. In particular, a broker interacts with providers in order to gather information on the data potentially available to consumers, and with the consumers in order to identify the set of providers that are most likely to satisfy specific data needs. The brokerage technique is based on a multi‐tier management of metadata. Copyright © 2006 John Wiley & Sons, Ltd.

A general digit-recurrence algorithm for the computation of the mth root (with an m integer) is presented in this paper. Based on the concept of completing the mth root, a detailed analysis of the convergence conditions is performed and iteration- independent digit-selection rules are obtained for any radix and redundant digit set. A radix-2 version for mth rooting is also studied, together with closed formulas for both the digit selection rules and the number of bits required to perform correct selections.

The Q-Coder algorithm is a very efficient compression technique for bi-level images based on the arithmetic coding. The paper presents a new and fast version of the Q-Coder algorithm in which the carry-propagated adders have been replaced by carry-save adders. In this way, all the additions can be performed with a delay time of a single fill adder, independently of the length of the operands. The compression method is faster than the traditional Q-Coder algorithm with an almost unnoticeable increasing of the hardware requirements.

Carry-save multipliers require an adder at the last step to convert the carry-sum representation of the most significant half of the result into a non-redundant form. This paper presents n/spl times/n multiplication schemes where this conversion is performed with a circuit operating in parallel with the carry-save array. The most relevant feature of the proposed multipliers is that the full 2n-bit result is produced, unlike similar multiplication schemes presented in the literature.

In a previous paper by P. Montuschi and L. Ciminiera (ibid., vol. 42, no.2 p239-246, Feb 1993), an architecture for shared radix 2 division and square root has been presented whose main characteristic is the ability to avoid any addition/subtraction, when the digit 0 has been selected. Here, we emphasize the characteristics of the digit selection mechanism used by Montuschi and Ciminiera by presenting a small modification of the digit selection hardware, which has the benefit to further reduce the computation delay with respect to the time estimated in that work.>

Over-redundant digit sets are defined as those ranging from /spl minus/s to +s, with s/spl ges/B, B being the radix. This paper presents new techniques for the direct computation of division, that use an over-redundant digit set for representing the quotient, instead of simply redundant ones used previously. In particular, general criteria for synthesizing the digit selection rules and remainder updating are given for any radix and index of redundancy. A methodology combining the use of over-redundant digit sets with the prescaling of the divisor is also studied in order to achieve radix-B division units with trivial digit selection functions. It is also shown, for the specific case of radix-4 that using a prescaling slightly wider than in a radix-4 unit by M.D. Ercegovac and T. Lang (1990) possible to avoid the digit selection table. The paper also presents a modified algorithm for on-the-fly conversion of the result into the irredundant form. The proposed methodology can be considered as an alternative to existing division techniques.>

Performance analysis and formal correctness verification of computer communication protocols and distributed systems have traditionally been considered as two separate fields. However, their integration can be achieved by using formal description techniques as paradigms for the development of performance models. This paper presents a novel extension of LOTOS, one of the two formal specification languages that were standardized by ISO. The extension is specifically conceived to integrate performance analysis and formal verification. The extended language syntax and semantics are formally defined, along with a mapping from extended specifications to performance models, The mapping preserves the specified observable behavior. Two simple examples, a stop-and-wait protocol and a time-sharing system, are used to concretely demonstrate the new approach and to validate it.>

Carry-save multipliers require an adder at the last step to convert the carry-sum representation of the most significant half of the result into an irredundant form. A multiplication scheme where by this conversion is performed with a circuit operating in parallel with the carry-save array is presented. The resulting implementation, when a radix-2 adder array is used, produces a result on 2n bits with a delay comparable to that of the multiplier proposed by M.D. Ercegovac and T. Lang (1990). When a radix-4 array is used, the proposed unit is almost twice as fast as units proposed previously.>

Abstract A new tool for generating implementation prototypes of communication protocols and concurrent systems specified using the ISO LOTOS language is presented in this paper. A brief introduction to LOTOS and a discussion of the main problems related to the efficient execution of specifications written in LOTOS are presented first. The design and implementation of the tool are then considered: LOTOS specifications are analysed and translated into C functions which are executed by co‐operating processes in the Unix environment. The set of LOTOS process definitions is first translated into a suitable number of extended finite‐state machines (EFSMs). The method proposed allows the problem of deriving unbounded EFSMs to be circumvented and a sort of control on the process number/size trade‐off to be obtained at the same time. The problem of implementing the LOTOS multi‐way rendezvous mechanism for process synchronization is solved by using an algorithm based on message‐passing techniques. An example of prototype derivation is also described, showing the form of C code generated by translating a simple specification. Finally, some performance figures are presented.

A new architecture is presented for shared radix 2 division and square root whose main characteristic is the ability to avoid any addition/subtraction, when the digit 0 has been selected. The solution presented uses a redundant representation of the partial remainder, while keeping the advantages of classical solutions. It is shown how the next digit of the result can be selected even when the remainder is not updated, and the subsequent tradeoff is presented. The proposed architecture is also extended in order to consider other implementations.>

A generative model for extending algebraic protocol specifications with probabilities is presented. The approach associates a simple probabilistic characterization with each algebraic operator occurrence in a behavior expression. The result is a compact notation in which the assignment of probabilities is more straightforward than with transition-based models. It is shown that an equivalent state machine with probabilities attached to transitions can be constructed automatically from an algebraic specification with probabilistic characterizations attached to operators. Specifically, it is shown how a probabilistic state machine can be derived from a basic LOTOS expression enriched by a probabilistic characterization. As an application example, a stop-and-wait protocol is examined.>

A study of the throughput and time characteristics of double-ring networks is presented, assuming that the two channels are used for balancing the traffic (when both are working) and for synchronous traffic generated according to a generic but periodic pattern. In addition, reconfiguration using portions of both rings to circumvent faulty elements in a double ring network is shown to be equivalent to the single ring configuration already studied. Examples of applications of the results are also illustrated.>

A radix 4 division architecture is presented which partially overlaps the updating of the remainder with the digit selection procedure. It is obtained by separating the radix 4 digit selection process into two concurrent substeps. The proposed unit requires a simple selection table and involves a small extra expense for the additional hardware compared to the usual radix 4 division units. Four possible implementations are derived from the general model, with different types of substeps. The high level evaluation shows that the proposed architectures offer an efficient alternative.>

The authors present a novel algorithm for shared radix 2 division and square root whose main characteristic is the ability to avoid any addition when the digit 0 has been selected. The solution presented uses a redundant representation of the partial remainder, while keeping the advantages of classical solutions. It is shown how the next digit of the result can be selected even when the remainder is not updated; the tradeoff arising is also indicated. The average occurrences of 0 digit selections are also estimated in order to assess the benefits of the algorithm presented.>

Two timed token protocols, the IEEE 802.4 and FDDI (fiber distributed data interface), are considered. Although IEEE 802.4 and FDDI have similar protocol rules, the different method of measuring the duration of the generic token rotation has imposed separate analyses for the two protocols. Presented is a general proof of equivalence between IEEE 802.4 and FDDI networks, where both consist of queues belonging to two priority classes. Having proved this equivalence, it is possible to extend results formally demonstrated for one protocol to the other. In particular, the results regarding the bounds on mean and maximum token rotation time derived for FDDI by Sevcik and Johnson (1987) can also be extended to IEEE 802.4 networks.>

It is noted that the implementation of the multiway rendezvous mechanism of the International Standards Organization (ISO) LOTOS specification language for protocols is very important in the development of tools for the execution of LOTOS. It involves problems such as global knowledge in a distributed environment and distributed agreement. The authors propose a novel algorithm which fully implements the multiway rendezvous of LOTOS within a distributed execution model based on a number of parallel processes. The processes are organized in a hierarchical topology and communicate with each other only by message transfers. The performance of the proposed algorithm is evaluated and is shown to be better than that achieved by other algorithms proposed in the literature. A formal specification of the algorithm in LOTOS is provided.>

A general discussion on nonrestoring square root algorithms is presented, showing bounds and constraints delimiting the space of feasible algorithms, for all the choices of radix, digit set and representation of the partial remainder. Two classes of algorithms are then derived from the general discussion, and it is shown how it is possible to determine two parameters with a relevant impact on the implementation: the number of radicand bits to be inspected in order to obtain a starting value, and the number of partial remainder bits to be examined for digit selection. The algorithms for the specific case of radix 4 digit set (-2, -1, 0, +1, +2), and partial remainder represented in carry-save form are derived in order to show that the algorithms introduced can lead to better results than those obtained with algorithms previously presented.>

Timed-token protocols are used to handle, on the same local area network, both real-time and non-real-time traffic. The authors analyze this type of protocol, giving worst-case values for the throughput of non-real-time traffic and the average token rotation time. Results are obtained for synchronous traffic generated according to a generic periodic pattern under heavy conditions for non-real-time traffic and express not only theoretical lower bounds but values deriving from the analysis of some real networks. A model which addresses the asynchronous overrun problem is presented. The influence of introducing multiple priority classes for non-real-time traffic on the total throughput of this type of message is shown. It is also shown that the differences between the values obtained under worst-case assumptions are close to those obtained under best-case assumptions; the method may therefore be used to provide important guidelines in properly tuning timed-token protocol parameters for each specific network installation.>

Square root nonrestoring algorithms operating with a radix higher than two (but power of 2) are discussed. Formulas are derived delimiting the feasibility space of the class of algorithms considered as a function of the different parameters. This definition leads to the determination of some of these parameters; in particular, it is possible to compute the number of partial reminder bits to be inspected for digit selection and the number of operand bits to be inspected to generate the first radicand value, as both parameters have a relevant impact on the implementation. The specific case of radix 4, digit set (-2, -1, 0, +1, +2) and partial remainder represented by the sum of two numbers is considered.>

Timed token protocols are both used to handle, on the same local area network, both real-time and non-real-time traffic. The authors analyze this type of protocols, giving worst-case values for the throughput of non-real-time traffic and the average token rotation time. The results were obtained for synchronous traffic generated according to a generic periodic pattern, under heavy traffic conditions. Finally, it is shown that the difference between the values obtained under worst-case assumptions are close to those obtained under best-case assumptions. Therefore, the method presented here may be used to provide important guidelines so as to properly tune timed token protocol parameters for each specific network installation.>

Timed-token protocols are used in local area networks to achieve bounded access times for a class of messages referred to as synchronous. An analysis is made of the behavior of this type of access protocol in a network with one redundant channel. Stations connected to both rings and stations connected to either ring are considered. A method of computing the minimum guaranteed throughput for asynchronous messages is shown, assuming that the two channels are used for balancing the traffic (when both are working) and for synchronous traffic generated according to a generic but periodic pattern.>

The problem of authenticating the users of a computer network in order to protect the shared resources against unauthorized use is discussed. Since intruders could enter the network and try to use services they have no right to access, the host implementing the service (or server) has to check the user's identity and access rights by searching in the relevant database. The author presents a method of carrying out such checks efficiently. The basic idea is that a suitable interface process is associated with each user-server connection in order to filter out unauthorized requests, thus implementing a sort of cache with parallel search where the working set of the whole database is stored and explored. The use of the interface process enables the system to exploit the hardware support for capability checking provided by new microprocessors. In particular, an implementation using iAPX432-based hosts is illustrated and performance issues are discussed.>

Abstract Communication protocols form a language which can be recognized by extended finite automata, and compiler generating tools can help with its implementation. This paper presents a project for implementing the ISO OSI layers which are most relevant to LANs. Taking advantage of modular and repetitive OSI architecture, a layer implementation model is proposed, introducing sharp distinctions between protocol layer‐dependent and independent modules, so that the implementation effort can be largely reduced. It is also shown that layer‐dependent modules can be generated automatically by using software tools developed for compiler construction. It is assumed that the protocols to be implemented have already been verified and validated in their abstract forms using other techniques, since these aspects are not covered by the method proposed. Measures of program sizes and execution speeds obtained following the approach proposed are reported; they show that most of the layer code can be produced by automatic tools and the overall software complexity enables the OSI architecture to be implemented for single‐board microcomputers.

Two new implementations of parallel multipliers, based on iterative arrays of logic cells are presented in this paper. Both are able to compute the product of two n bit numbers with a delay of n cells, rather 2n−l as in classical structures. The high speed operation is obtained by using pure horizontal compressors, to accelerate the horizontal signal propagation, and by adopting a suitable array structure, to shorten the vertical signal propagation. The cost and performance advantages over similar structures based on vertical compressors are discussed.

A new multistage interconnection network is presented in this paper. It is able to handle the communications between the connected devices correctly, even in the presence of fault(s) in the network. This goal is achieved by using redundant paths with a fast procedure able to dynamically reroute the message. It is also shown that the rerouting properties are still valid when broadcasting transmission is used.

Three new arrays for unsigned and signed multiplication, and for multiplication/addition are presented. It is assumed that the factors are axpressed in 2's complement, while the addend (in the latter array only) and the result are expressed in a redundant notation. The arrays operate in serial-parallel way, since one factor is input in parallel, while the second factor and the addend (in the case of multiplication/addition) are entered digit by digit starting from the most significant one; the result is also produced serially with the most significant digit first. Hence, the arithmetic unit presented is suitable to be used as basic block of special purpose processors performing functions such as non-recursive digital filtering, signal correlation and matrix multiplication. Indeed, they have the same speed improvements as other similar units using redundant representations for the result, with a cost equivalent to their counterparts based on full 2's complement representation.

A high speed multiplying array is presented. It is based on a new cell, which is able to generate and add a rectangular block of elementary products. A careful design of the cell allows us to obtain a small delay for the signals which should be propagated through the whole array. This feature leads to a remarkable improvement in the array speed.