Search

In this paper we introduce a typed λ-calculus in which computer networks can be formalized and directed at situations where the services available on the network are stationary, while the information can flow freely. For this calculus, an analogue of the ‘propositions-as-types ’interpretation of constructive type theory holds with respect to information push and pull in computer networks: in the calculus a type represents a task that the user wants to carry out, while a term inhabiting this type represents a procedure that will yield the desired result. Under this interpretation, techniques for theorem proving can be used for finding a procedure to achieve a certain task on the network. Techniques for type checking can be used for checking a complex network program before running it. Reductions on terms can be used for finding alternative procedures to achieve a certain task. Terms constructed in this abstract calculus can be ‘compiled ’to procedures which are executable on the actual network. We show this for a simple Unix network. [ABSTRACT FROM PUBLISHER]

In this paper we deal with interval routing on $n$-node networks of diameter $D$. We show that, for all $n$ and $D$ such that $2 \leq D \leq \Theta(n)$, there exists a network on which every interval routing scheme with less than $\Omega(n/(D\log (n/D)))$ intervals per link has a routing path length at least $\lfloor 3D/2\rfloor-1$. It improves the lower bound on the routing path lengths for the range of a very large number of intervals. Moreover, we build a network of bounded degree, for all $n$ and $D$ such that $\Theta(\log n) \leq D \leq \Theta(n)$, on which every interval routing scheme with less than $\Omega(n/D^2)$ intervals per link has a routing path length at least $3D/2 - O(\log n)$. [ABSTRACT FROM PUBLISHER]

The reliability of a distributed computing system depends on the reliability of its communication links and nodes and on the distribution of its resources, such as programs and data files. Many algorithms have been proposed for computing the reliability of distributed computing systems, but they have been applied mostly to distributed computing systems with perfect nodes. However, in real problems, nodes as well as links may fail. This paper proposes two new algorithms for computing the reliability of a distributed computing system with imperfect nodes. Algorithm I is based on a symbolic approach that includes two passes of computation. Algorithm II employs a general factoring technique on both nodes and edges. Comparisons with existing methods show the usefulness of the proposed algorithms for computing the reliability of large distributed computing systems. [ABSTRACT FROM PUBLISHER]

Communication protocols designed for database applications are not necessarily suitable for other applications, like multimedia communication, due to the former's requirement of reliable and ordered communication, and the latter's ability to withstand occasional losses and misordering of messages as long as real-time communication can be supported. This paper presents the slotted-FIFO communication mode that supports communication primitives for the entire spectrum of reliability and ordering requirements of distributed applications: for example, FIFO as well as non-FIFO, and reliable as well as unreliable communication. It provides communication with a run-time variable degree of reliability and/or ordering. Hence, the slotted-FIFO communication mode is suitable for applications that can work with relaxed reliability and/or ordering constraints such as multimedia applications. The protocol is simple and has low overheads. As FIFO ordering is not required for all messages, message buffering requirements are considerably reduced. Also, message latencies are lower. We demonstrate such advantages by means of a simulation study. A low overhead protocol implementing slotted-FIFO communication is also presented. The protocol incurs a small resequencing cost. [ABSTRACT FROM AUTHOR]

This paper presents detection algorithms for baseline interconnection networks in the presence of multiple faults. We develop a procedure for finding the constraints of test vectors. This reduces the number of distinct test vectors and solves the problems efficiently. Furthermore, we design a new and systematic procedure for generating admissible permutations and reduction rules to find constraints easier. By using this novel approach, we are able to derive the following new results. (1) Four distinct test vectors are necessary and sufficient for detecting multiple faults in an 8*8 baseline network. (2) Six distinct test vectors are sufficient for detecting multiple faults in a 16 * 16 baseline network. (3) Six tests are necessary and sufficient for detecting multiple faults in a 16 * 16 baseline network. This improves the previous result of [1], which needs 8 tests to accomplish the same task. (4) We show that (2log2 N) − 2 tests are sufficient for detecting multiple faults in an N * N baseline network for N ≥ 16. This also improves the result of [1], which needs 2 log2 N tests. [ABSTRACT FROM AUTHOR]

There has been much interest in testing from finite-state machines (FSMs). If the system under test can be modelled by the (minimal) FSM N then testing from an (minimal) FSM M is testing to check that N is isomorphic to M. In the distributed test architecture, there are multiple interfaces/ports and there is a tester at each port. This can introduce controllability/synchronization and observability problems. This paper shows that the restriction to test sequences that do not cause controllability problems and the inability to observe the global behaviour in the distributed test architecture, and thus relying only on the local behaviour at remote testers, introduces fundamental limitations into testing. There exist minimal FSMs that are not equivalent, and so are not isomorphic, and yet cannot be distinguished by testing in this architecture without introducing controllability problems. Similarly, an FSM may have non-equivalent states that cannot be distinguished in the distributed test architecture without causing controllability problems: these are said to be locally s-equivalent and otherwise they are locally s-distinguishable. This paper introduces the notion of two states or FSMs being locally s-equivalent and formalizes the power of testing in the distributed test architecture in terms of local s-equivalence. It introduces a polynomial time algorithm that, given an FSM M, determines which states of M are locally s-equivalent and produces minimal length input sequences that locally s-distinguish states that are not locally s-equivalent. An FSM is locally s-minimal if it has no pair of locally s-equivalent states. This paper gives an algorithm that takes an FSM M and returns a locally s-minimal FSM M′ that is locally s-equivalent to M. [ABSTRACT FROM AUTHOR]

In wireless sensor networks (WSN), the clustering technique reduces energy efficiency and network lifetime. In this paper, a Fuzzy-based clustering architecture is proposed for cooperative communication in WSN in order to overcome this issue. In this work, a Cluster Head (CH) is chosen based on the parameters residual energy, trust, signal-to-interference-plus-noise ratio and load. Then, the intra-cluster routing is performed using network coding-based probabilistic routing scheme. The fuzzy-based clustering protocol helps in determining the cooperative node (CN) which joins the cluster. Finally, particle swarm optimization is used to establish the optimum path between each CN and the CH for data transmission. The simulation results show that the proposed technique enhances the network lifetime and energy efficiency. [ABSTRACT FROM AUTHOR]

We present our work on the dimensioning of a packet-switching wavelength division multiplexing ring in order to reduce its infrastructure (capital expenditure) cost. We study a new all-optical architecture: the packed optical add-drop multiplexer (POADM). We aim to minimize the overall cost of the network by reducing the number of indispensable devices in the nodes and the number of required wavelengths. We formalize the packing problems underlying the ring dimensioning. The elements to be packed are made up of transmissions that share the same destination. We assume that elements can be cut before being packed into boxes. We furnish a complete theoretical analysis of the complexity and approximability of these problems. We define also several measures of quality for a cut and provide an optimal cutting strategy, according to these measures. Our subsequent contribution is a heuristic solution that solves the bi-criteria packing problem (the number of boxes and the number of cuts are minimized simultaneously). The exhaustive numerical results of this heuristic algorithm come next. We rely on our optimal cutting strategy to appraise the efficiency of other strategies. We also adapt the only existing POADM dimensioning algorithm, more restrictive than ours, and we confront it with our solution. The analysis of results allows us to provide network design guidelines to perform the dimensioning in the most efficient way. [ABSTRACT FROM AUTHOR]

Providing efficient transport services over multi-hop ad hoc networks is a fundamental building block for this wireless technology. The typical approach is modifying transmission control protocol (TCP) to fix one (or a few of) its inefficiency while preserving compatibility with the original protocol. However, a complete solution should include a significant number of modifications, such that the original TCP design is deeply modified. In this paper we explore a different approach. We include the desired modifications to TCP in the design of a new transport protocol [transport protocol for ad-hoc (TPA)]. In this way we are able to blend together these features in a unique design framework, and better control interactions among the different (modified) components. We then compare TCP and TPA through field tests, in terms of throughput and total number of transmitted segments. We consider several possible configurations of the protocol parameters, different routing protocols and various networking scenarios. In all the cases taken into consideration, TPA significantly outperforms TCP. To achieve a more thorough understanding of the TPA behaviour, we compare TPA and TCP also in terms of fairness and scalability (both in static and mobile configurations) over a wide range of representative topologies. To this end, we adopt a simulation approach, which is more suitable to this kind of analysis. Simulation results confirm field tests, and show that TPA is able to outperform TCP with respect to all analysed performance figures. [ABSTRACT FROM AUTHOR]

Digital signatures have been proposed by several researchers as a way of preventing execution of malicious code. In this paper, we propose a general architecture for performing the signature verification as part of the kernel execution process. The proposed architecture does not require any change in the interpreters used to execute code and it can accommodate any executable format. We also report on our implementation for the Linux operating system that focuses on ELF and script executables. Experimental results show that our solution is of potential interest as virtually no slowdown is experienced in the execution. [ABSTRACT FROM AUTHOR]

Recent advances in computer storage architectures, high-speed networking technologies and compression techniques support a proliferation of multimedia information dissemination via computer networks. For example, applications such as video-on-demand (VOD) and home shopping services are now possible. A major requirement of VOD application is that the VOD storage server has to store and retrieve a huge amount of video data in a continuous manner. Therefore, near-line storage devices, such as robotic tape libraries, have to be employed in VOD storage servers which can contain thousands of large video objects. In this paper, we study in detail the design issues of a hierarchical multimedia storage server that consists of a disk array for caching and a robotic tape library for the storage of all the video objects. We propose and study in detail the file layout policy in the disk subsystem, the scheduling of the tape subsystem, the video object replacement algorithms, the read/write scheduling of the disk subsystem and the memory buffer requirement. [ABSTRACT FROM AUTHOR]

Generally, tasks in a distributed system must reach agreement. This requires a set of processors to agree on a common value even though some components may be corrupt. There have been several significant studies on this agreement problem in regularized network environments such as the fully connected, broadcast and multicast networks. Recently, many large complex networks have emerged displaying a scale-free feature that influences the system to reach a common value in a novel way. This unanimity problem is called Byzantine agreement (BA). The BA problem is one of the most significant problems in designing a fault-tolerant distributed system. Unfortunately, existing BA protocols cannot cope with the new network environment, and the BA problem thus must be revisited. In this paper, a new BA protocol is proposed that adapts to the scale-free network (SFN) environment and derives its limit of allowable faulty components while maintaining the minimum number of message exchanges. The correctness and complexity of this protocol have been proved. It is observed that an SFN in conjunction with the proposed agreement protocol can tolerate the maximum number of faulty components. [ABSTRACT FROM AUTHOR]

Intrusion prevention systems (IPSs) not only attempt to detect attacks but also block malicious traffic and pro-actively tear down pertinent network connections. To effectively thwart attacks, IPSs have to operate both in real-time and inline fashion. This dual mode renders the design/implementation and more importantly the testing of IPSs a challenge. In this paper, we propose an IPS testing framework termed IPS Evaluator which consists of a trace-driven inline simulator-engine, mechanisms for generating and manipulating test cases, and a comprehensive series of test procedures. The engine features attacker and victim interfaces which bind to the external and internal ports of an IPS-under-testing (IUT). Our engine employs a bi-directional injection policy to ensure that replayed packets are subject to security inspection by the IUT before they are forwarded. Furthermore, the send-and-receive mechanism of our engine allows for the correlation of engine-replayed and IUT-forwarded packets as well as the verification of IUT actions on detected attacks. Using dynamic addressing and routing techniques, our framework rewrites both source and destination addresses for every replayed packet on-the-fly. In this way, replayed packets conform to the specific features of the IUT. We propose algorithms to partition attacker/victim-emanated packets so that they are subjected to security inspections by the IUT and in addition, we offer packet manipulation operations to shape replayed traces. We discuss procedures that help verify the IUTs detection and prevention accuracy, attack coverage and behavior under diverse traffic patterns. Finally, we evaluate the strengths of our framework by mainly examining the open-source IPS Snort-Inline. IPS deficiencies revealed during testing help establish the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The study of artificial neural networks has originally been inspired by neurophysiology and cognitive science. It has resulted in a rich and diverse methodology and in numerous applications to machine intelligence, computer vision, pattern recognition and other applications. The random neural network (RNN) is a probabilistic model which was inspired by the spiking behaviour of neurons, and which has an elegant mathematical treatment that provides both its steady-state behaviour and offers efficient learning algorithms for recurrent networks. Second-order interactions, where more than one neuron jointly act upon other cells, have been observed in nature; they generalize the binary (excitatory–inhibitory) interaction between pairs of cells and give rise to synchronous firing (SF) by many cells. In this paper, we develop an extension of the RNN to the case of synchronous interactions, which are based on two cells that jointly excite a third cell; this local behaviour is in fact sufficient to create SF by large ensembles of cells. We describe the system state and derive its stationary solution as well as a O(N3) gradient descent learning algorithm for a recurrent network with N cells when both standard excitatory–inhibitory interactions, as well as SF, are present. [ABSTRACT FROM AUTHOR]

The open distributed processing (ODP) computational viewpoint describes the functionality of a system and its environment in terms of a configuration of objects interacting at interfaces, independently of their distribution. Quality of service (QoS) contracts and service level agreements are an integral part of any computational specification, which are specified in ODP in terms of environment contracts. Up until unified modeling language (UML) version 2, both the lack of precision in the UML definition and the semantic gap between the ODP concepts and the UML constructs hindered its application for ODP computational viewpoint modeling. With the advent of UML 2 the situation has changed, because its semantics have been more precisely defined and it now incorporates a whole new set of concepts more apt for modeling the structure and behavior of distributed systems. In this paper, we explore the benefits provided by the new extension mechanisms of UML for modeling the ODP computational specifications and, in particular, we show how ODP environment contracts can be modeled with this approach. [ABSTRACT FROM AUTHOR]

Software systems grow each day in size and complexity. In an effort to manage increasing complexity and to maximize the reuse of code, the software engineering community has, in recent years, put considerable effort into the design and development of component-based software methodologies and tools. Inspired by the notion of connector (Allen and Garlan (1994) Formal connectors. Technical report CMU-CS-94-115, Carnegie Mellon University, PA, USA) in software architecture and the ‘Design by Contract’ metaphor proposed by Meyer ((2000) Object-Oriented Software Construction. Prentice Hall, USA), this paper presents a methodology for component composition, coordination and dynamic adaptation. Our proposal is based on connectors enriched with contracts, making software architecture more explicit at the implementation level. Those connectors will be components in our system. Therefore, we can use subtyping techniques for connectors development and we could offer a set of generic connectors implementing standard behavior patterns. In addition, the connectors will use semantic web techniques and a Prolog machine to solve functional adaptation problems, such us name or parameters mismatching of a service, at run-time. [ABSTRACT FROM AUTHOR]

In recent years, many distributed rating systems have been proposed against the increasing misbehaviors of peers in peer-to-peer (P2P) networks. However, the low accuracy, long-response time and vulnerabilities under the adversary attacks of P2P rating systems have long been criticized and hindering the practical deployment of such a mechanism. There is also a lack of systematic analysis and evaluation for understanding the systems. In this paper, we first present a framework of stochastic analytical model for evaluating P2P rating systems. The performances of two representative designs, namely the unstructured self-managing rating (UMR) system and the structured supervising rating (SSR) system, are then studied with our model. We identify the positive features as well as the negative ones of the two designs with different design choices and under various network environments and adversary attacks. We also propose a configurable loosely supervising rating system, and show that this system works inexpensively, and could make trade-off between the false rating attack resistance of the UMR system and the accuracy, responsiveness, whitewashing attack resistance as well as a failure resilience of the SSR system, thus providing a better overall performance according to the application context. [ABSTRACT FROM AUTHOR]

Flexible network management requires explicit control of the exact paths taken by different network flows. Whatever the way this endeavour is achieved (e.g. Multiprotocol Label Switching, Virtual Local Area Networks and OpenFlow), this need may lead to an explosion of entries in the forwarding tables of network equipment. In this article, we present an algorithm that aggregates many network paths in a reduced number of trees, thus allowing shrinking the forwarding state in switching devices. Path aggregation algorithms are often deployed to reduce data-plane state with different routing approaches and the presented algorithm achieves better results than existent algorithms with similar goals. Additionally, we show that most types of popular routing and switching equipment, even using off-the-shelf routing software, may be used to implement multi-path routing with trees. This highlights the applicability of the proposed algorithm and its significance in light of the current trend of separating the data- and the control-planes in modern networks. [ABSTRACT FROM AUTHOR]

Related-key attacks (RKAs) are a flavor of powerful physical attacks, which allow an adversary to modify the secret key stored in a cryptographic device and subsequently observe the effect of such modifications on the output of the device. Designing secure encryption schemes against such attacks is a challenging task, especially for a large class of such physical attacks which are usually captured by related-key derivation functions. In this work, we achieve the security of public key encryptions (PKEs) against a new and broad function class that consists of almost all efficiently invertible functions in two different ways. Specifically, we first give a generic construction of PKE which is proven secure against such a broad function class under the standard chosen-ciphertext security. Moreover, we present two practical concrete constructions, both of which are shown to be secure against such function class under standard assumptions in the standard model. At last, we give a detailed performance analysis, which shows that our constructions can not only resist to a large class of RKAs but also achieve a good efficiency. [ABSTRACT FROM AUTHOR]

The iTrust system is a decentralized and distributed publication, search and retrieval system that makes it difficult to censor or filter information accessed over the Internet. iTrust employs a completely distributed membership algorithm, and a detection and defensive adaptation algorithm that protects against malicious nodes in the membership. These algorithms depend on information that cannot be observed or measured directly, the current size of the membership and the current proportion of malicious nodes in the membership. They use statistical estimation to approximate these network environment parameters, and then they dynamically adapt accordingly. These algorithms provide accurate and timely management of the iTrust system in the presence of membership churn and malicious nodes. [ABSTRACT FROM AUTHOR]

As a result of increasing communication demands, application-specific and scalable Network-on-Chips (NoCs) have emerged to connect processing cores and subsystems in Multiprocessor System-on-Chips. A challenge in application-specific NoC design is to find the right balance among different tradeoffs, such as communication latency, power consumption and chip area. We propose a novel approach that generates latency-aware heterogeneous NoC topology. Experimental results show that our approach improves the total communication latency up to 27% with modest power consumption. [ABSTRACT FROM AUTHOR]

Today's wireless networks are connecting more and more devices around us, leading to the birth of a new distributed computing platform, in the form of a spatial computer. The main difference with traditional computing models is that space and time become intertwined with computation, especially when scaling up the system. Computations performed by each element are now related to its spatial position. This property is the key ingredient when assuring the availability for variousdistributed networking services and applications. Computations become linked to the concept of space. Estimating distances between components (especially in dynamic networks characterized by the node mobility) thus becomes one of the most important building blocks for spatial computing. The majority of the algorithms that come from the MANET community presume knowledge about node position via systems such as GPS, or employ a one-time manual network topology configuration. While for some application scenarios this approach is feasible, for a lot of cases it suffers from frequent unavailability (e.g. indoors) and high costs in terms of energy consumption. Therefore, intense demand exists for a new kind of distance estimation algorithm using only simple local interactions, without knowledge of global information. The main contribution of the article is the introduction of a novel distributed algorithm, called gradient-based distance estimation (GDE), for the estimation of distances in networks characterized by mobility, specifically targeting the context of spatial computing. GDE is based on a gossiping mechanism to estimate distances between nodes with only local interactions. It significantly improves current state of the art by employing statistical analysis and making better use of the information available at each node.We analyze the parameters that should be considered by real applications, and present mathematical models to compensate their influence for distance estimation. Three spatial computing applications using GDE are presented: geographical cluster center detection, topological overlay shape construction and geographic routing. The simulation-based evaluation shows that GDE succeeds in estimating the distance between nodesin both static and mobile scenarios with considerably high accuracy for various simulations setups, such as varying node density, node speed or spatial node distribution. [ABSTRACT FROM AUTHOR]

We present two spatially distributed computing systems that operate in a building and provide intelligent navigation services to people for evacuation purposes. These systems adapt to changing conditions by monitoring the building and using local communication and computation for determining the best evacuation paths. The first system, called distributed evacuation system (DES), comprises a network of decision nodes (DNs) positioned at specific locations inside the building. DNs provide people with directions regarding the best available exit. The second system, called opportunistic emergency support system (OESS), consists of mobile communication nodes (CNs) carried by people. CNs form an opportunistic network in order to exchange information regarding the hazard and to direct the evacuees towards the safest exit. Both DES and OESS employ sensor nodes deployed at fixed locations for monitoring the hazard. We evaluate the spatial systems using simulation experiments with a purpose-built emergency simulator called DBES. We show how parameters such as the frequency of information exchange and communication range affect the system performance and evacuation outcome. [ABSTRACT FROM AUTHOR]

Pinning adaptive synchronization is investigated in weighted complex networks and several criteria are obtained for globally exponentially asymptotic synchronization. The number of pinned nodes can be obtained by calculating the eigenvalue of the minor matrix of an extended coupling matrix. Especially, pinning adaptive controllers are rather simple compared with some traditional controllers. Specifically and randomly pinning schemes are considered. When the network Control Rank information is known, the specifically pinning scheme of the most highly connected nodes is shown to require a significantly smaller number of local controllers when compared with the randomly pinning scheme. Finally, numerical simulations are provided to illustrate the effectiveness of the proposed synchronization criteria in weighted dynamical networks. [ABSTRACT FROM PUBLISHER]

Many scientific experiments are carried out in collaboration with researchers around the world to use existing infrastructures and conduct experiments at massive scale. Data produced by such experiments are thus replicated and cached at multiple geographic locations. This gives rise to new challenges when selecting distributed data and compute resources so that the execution of applications is time- and cost-efficient. Existing heuristic techniques select ‘best’ data source for retrieving data to a compute resource and subsequently process task-resource assignment. However, this approach of scheduling, which is based only on single source data retrieval, may not give time-efficient schedules when: (i) tasks are interdependent on data, (ii) the average size of data processed by most tasks is large and (iii) data transfer time exceeds task computation time by at least one order of magnitude. In order to address these characteristics of data-intensive applications, we propose to leverage the presence of replicated data sources, retrieve data in parallel from multiple locations and thus achieve time-efficient schedules. In this article, we propose two multi-source data-retrieval-based scheduling heuristic that assigns interdependent tasks to compute resources based on both data retrieval time and task-computation time. We carry out experiments using real applications and deploy them on emulated as well as real environments. With a combination of data retrieval and task-resource mapping technique, we show that our heuristic produces time-efficient schedules that are better than existing heuristic-based techniques for scheduling application workflows. [ABSTRACT FROM PUBLISHER]

We consider large queueing networks for which transient and stationary probability distributions are very difficult or impossible to obtain due to the state space explosion problem. In performance analysis, we need in general to study only a part of the network (a node or a path). Thus, we propose to define bounding systems that lead to compute bounds on performance measures of the considered subsystem. The original large state space is mapped into a smaller space to overcome the state space explosion problem, and bounds both on stationary and on transient performance measures are computed from these reduced-size models. This approach provides an interesting solution for complex networks since we have a trade-off between the quality of the bounds and the state space size, thus the computational complexity. As an application, we study a general multi-server queueing network, with finite capacity queues. We define bounding systems to compute blocking probabilities. The influence of parameters on the precision of the computed bounds are studied through some numerical examples in order to give more insights into the proposed approach. [ABSTRACT FROM AUTHOR]

We propose a probabilistic model based on stochastic geometry to analyze cognitive radio in a large wireless network with randomly located users sharing the medium with carrier sensing multiple access. Analytical results are derived on the impact of the interaction between primary and secondary users, on their medium access probability, coverage probability and throughput. These results can be seen as the continuation of the theory of priorities in queueing theory to spatial processes. They give insight into the guarantees that can be offered to primary users and more generally on the possibilities offered by cognitive radio to improve the effectiveness of spectrum utilization in such networks. [ABSTRACT FROM AUTHOR]

Model checking is a promising approach to automatic verification, which has concentrated on specification expressed in temporal logics. Comparatively little attention has been given to temporal logics of knowledge, although such logics have been proven to be very useful in the specifications of protocols for distributed systems. In this paper, we addressed the model checking problem for a temporal logic of knowledge (Halpern and Vardis logic of CKLn). Based on the semantics of interpreted systems with local propositions, we developed an approach to symbolic CKLn model checking via Ordered Binary decision diagrams and implemented the corresponding symbolic model checker MCTK. In our approach to model checking specifications involving agents knowledge, the knowledge modalities are eliminated via quantifiers over agents non-observable variables. We then modelled the Dining Cryptographers protocol and the five-hands protocol for Russian Cards problem in MCTK. Via these two examples, we compare MCTKs empirical performance with two different state-of-the-art epistemic model checkers, MCK and MCMAS. [ABSTRACT FROM AUTHOR]

It is widely recognized that a prerequisite for the commercial penetration of the ad hoc networking technologies is the integration with existing wired/wireless infrastructure-based networks to provide an easy and transparent access to the Internet and its services. However, most of the existing solutions for enabling the interconnection between IPv4-based mobile ad hoc networks and the Internet are based on complex and inefficient mechanisms, as Mobile-IP and IP tunnelling. In this paper, we describe an alternative approach to build multi-hop and heterogeneous proactive ad hoc networks, which can be used as flexible and low-cost extensions of traditional wired local area networks (LANs). Our proposed architecture provides transparent global Internet connectivity and address autoconfiguration capabilities to mobile nodes without requiring configuration changes in the pre-existing wired LAN, and relying on basic layer-2 functionalities. We have prototyped the core components of this architecture for Optimized Link State Routing-based ad hoc networks and we have conducted several experiments comparing the throughput performance obtained using our scheme and a well-known alternative (network address translation) NAT-based solution. The experimental outcomes show that our proposed technique ensures higher perconnection throughputs than the NAT-based solution in the considered network scenarios. [ABSTRACT FROM AUTHOR]

Recently many scalable and efficient solutions for event dissemination in publish/subscribe (pub/sub) systems have appeared in the literature. This dissemination is usually done over an overlay network of brokers and its cost can be measured as the number of messages sent over the overlay to allow the event to reach all intended subscribers. Efficient solutions to this problem are often obtained through smart dissemination algorithms that avoid flooding events on the overlay. In this paper, we propose a complementary approach that obtains efficient event dissemination by reorganizing the overlay network topology. More specifically, this reorganization is done through a self-organizing algorithm executed by brokers whose aim is to directly connect, through overlay links, pairs of brokers matching same events. In this way, on average, the number of brokers involved in an event dissemination decreases, thus reducing its cost. Even though the paradigm of the self-organizing algorithm is general and then applicable to any overlay-based pub/sub system, its concrete implementation depends on the specific system. As a consequence, we studied the effect of the introduction of the self-organizing algorithm in the context of a specific system implementing a tree-based routing strategy, namely SIENA, showing the actual performance benefits through an extensive simulation study. In particular, performance results point out the capacity of the algorithm to converge to an overlay topology accommodating efficient event with respect to (w.r.t) dissemination a specific scenario. Moreover, the algorithm shows a significant capacity to adapt the overlay network topology to continuously changing scenarios while keeping an efficient behavior w.r.t. event dissemination. [ABSTRACT FROM AUTHOR]

Biswapped networks of the form Bsw(G) have recently been proposed as interconnection networks to be implemented as optical transpose interconnection systems. We provide a systematic construction of κ+1 vertex-disjoint paths joining any two distinct vertices in Bsw(G), where κ≥1 is the connectivity of G. In doing so, we obtain an upper bound of max{2Δ(G)+5, Δκ(G)+Δ(G)+2} on the (κ+1)-diameter of Bsw(G), where Δ(G) is the diameter of G and Δκ(G) the κ-diameter. Suppose that we have a deterministic multipath source routing algorithm in an interconnection network G that finds κ mutually vertex-disjoint paths in G joining any two distinct vertices and does this in time polynomial in Δκ(G), Δ(G) and κ (and independently of the number of vertices of G). Our constructions yield an analogous deterministic multipath source routing algorithm in the interconnection network Bsw(G) that finds κ+1 mutually vertex-disjoint paths joining any two distinct vertices in Bsw(G) so that these paths, all have length bounded as above. Moreover, our algorithm has time complexity polynomial in Δκ(G), Δ(G) and κ. We also show that if G is Hamiltonian, then Bsw (G) is Hamiltonian, and that if G is a Cayley graph, then Bsw(G) is a Cayley graph. [ABSTRACT FROM AUTHOR]

IP multimedia subsystem (IMS) is over IP network architecture, but mobile IP cannot directly support session mobility controlled by session initiation protocol-based signaling. The long signaling delay for session reestablishment in application layer always results in session interruptions during the handoff. Therefore, handoff poses a challenge for quality of service (QoS) maintenance in IMS that targets to offer real-time multimedia applications over wireless mobile networks. The existing approaches to solve this problem depend on the advance resource reservation and the optimization of handoff control. Unfortunately, big cost of the advance resource reservation in neighboring domains is a major problem that leads to a serious signaling load and a waste of wireless bandwidth. To solve this issue, we present an enhanced IMS handoff mechanism (EHM) based on user mobility prediction to save network resources by avoiding multiple useless advance reservations. In addition, to support the heterogeneous access networks in IMS domain, EHM evolves a network selective scheme to utilize the network resources more efficiently. The architecture of EHM and the advance QoS negotiation signaling are also presented. We model the cost, the handoff delay and the session blocking probability for EHM and the previous work. Analytical and simulation results show that EHM can enhance the handoff performance, such as reducing resource reservation cost greatly, decreasing session reestablishment delay and making good use of multiple access network resources. [ABSTRACT FROM AUTHOR]

Internet protocol multimedia subsystem (IMS) is an overlaid infrastructure above the packet-switched domain of the universal mobile telecommunication system core network. IMS enables and enhances real-time multimedia mobile services. IMS signaling and media are separated in IMS. For media session negotiation, two basic procedures in IMS are (i) IMS registration procedure and (ii) IMS incoming call setup procedure. IMS signaling needs to traverse a set of call session control functions (CSCFs), which are proxy-CSCF, interrogating-CSCF (I-CSCF) and serving-CSCF (S-CSCF). However, we observe that I-CSCFs need to query the home subscriber server (HSS) to obtain the name of S-CSCF for each subscriber's request in both the basic procedures. It results in a certain load occuring in the HSS and a certain procedure delay also occurs. Therefore, we employ the distributed hash table (DHT) into IMS to form a DHT-based I-CSCF network. Each I-CSCF in the DHT-based I-CSCF network can share and relieve HSS's load. As a result, the incoming call setup procedure can be speeded up. We also propose two maintaining procedures to maintain the DHT-based I-CSCF network for I-CSCFs join and leave scenarios. We propose one maintaining mechanism to guarantee the proposed system to be able to work well in the failure scenario of I-CSCF. According to the performance evaluation results, the load of HSS is reduced and shared among I-CSCFs in the home network and the signaling delay cost of the incoming call setup procedure is less than that of existent systems even if failure occurs and then is removed. [ABSTRACT FROM PUBLISHER]

Denial of service (DoS) is a prevalent threat in today's networks because DoS attacks are easy to launch, while defending a network resource against them is disproportionately difficult. Despite the extensive research in recent years, DoS attacks continue to harm, as the attackers adapt to the newer protection mechanisms. For this reason, we start our survey with a historical timeline of DoS incidents, where we illustrate the variety of types, targets and motives for such attacks and how they evolved during the last two decades. We then provide an extensive literature review on the existing research on DoS protection with an emphasis on the research of the last years and the most demanding aspects of defence. These include traceback, detection, classification of incoming traffic, response in the presence of an attack and mathematical modelling of attack and defence mechanisms. Our discussion aims to identify the trends in DoS attacks, the weaknesses of protection approaches and the qualities that modern ones should exhibit, so as to suggest new directions that DoS research can follow. [ABSTRACT FROM PUBLISHER]

Consistent with the divide-and-conquer approach to problem solving, a recursive result is presented in the domain of stochastic modelling that derives product-form solutions for the steady state probabilities of certain networks composed from interacting Markov chains. Practical applications include multi-tasking operating systems, communication channels and multi-tiered storage systems. The approach is also applied to the computation of response time quantiles, which are vital in transaction processing, computer communication service level agreements and other operational systems. The joint probability distribution of the sojourn times of a tagged task at each node in a network is determined by noting that this is the same in both the forward and reversed processes. In this way, existing results for response time probability densities in tandem, tree-like, and overtake-free Markovian queueing networks are quickly and systematically obtained. We further show how to apply the method in more general networks. [ABSTRACT FROM PUBLISHER]

A silent self-stabilizing asynchronous distributed algorithm is given for constructing a k-dominating set, and hence a k-clustering, of a connected network of processes with unique IDs and no designated leader. The algorithm is comparison-based, takes O(k) time and uses O(k log n) space per process, where n is the size of the network. It is known that finding a minimum k-dominating set is -hard. A lower bound is given, showing that any comparison-based algorithm for the k-clustering problem that produces clusters of average size more than 2 in the worst case takes Ω(diam) time, where diam is the diameter of the network. [ABSTRACT FROM PUBLISHER]

Current and future multimedia networks require connections under specific quality of service (QoS) constraints which can no longer be provided by the best-effort Internet. Therefore, ‘smarter’ networks have been proposed in order to cover this need. The cognitive packet network (CPN) is a routing protocol that provides QoS-driven routing and performs self-improvement in a distributed manner, by learning from the experience of special packets, which gather on-line QoS measurements and discover new routes. The CPN was first introduced in 1999 and has been used in several applications since then. Here we provide a comprehensive survey of its variations, applications and experimental performance evaluations. [ABSTRACT FROM PUBLISHER]

Active networking introduces a novel programming paradigm to applications by injecting codes into networks in order to program them. Among the approaches to injecting codes into networks, active networking attracts most research communities to explore the capsule-based active network, where the packet named the capsule can carry codes and data together to customize the processing of the packet in network devices with the codes. Because a capsule has space limitations that harm application developments in capsule-based active networks, the just-in-time cache (JITC) is proposed to alleviate capsule space limitations. The JITC is an innovative idea to introduce a cache into a capsule besides into a network device. The JITC automatically tailors codes to the need of a capsule while processing the capsule in a network device. The JITC allows a capsule merely to carry the necessary codes to traverse active networks and makes a network device download codes on behalf of the capsule on demand. The JITC allows applications to disable the cache, control the cache size, and specify the required cache placement policy in a capsule to achieve the optimal performance. Currently, the JITC supports six canonical cache placement policies. The JITC is implemented in Windows 2000 as a proof of concept. In the experiments, the JITC has trivial overheads in contrast to other common overheads in the existing solutions. The JITC outperforms the existing solutions in throughput, processing delay, resource sensitivity, and bandwidth conservation in the cache-policy-free situation. Besides, the JITC has examples for the six cache placement policies to demonstrate the performance improvement with each of them. [ABSTRACT FROM PUBLISHER]

We develop a framework for the analysis of Denial of Service (DoS) attacks in computer networks. In this framework, we identify the components and resources that collectively and in time, construct a service that may become unavailable due to the unavailability of those resources as a result of a DoS. We also construct the notion of service resilience pre-ordering to compare the effectiveness of solutions proposed to improve a system's resilience against DoS. We apply our framework and methods to some cases, and show their usefulness and applicability in practice. [ABSTRACT FROM AUTHOR]

Abstract Syntax Notation One (ASN.1) is a standard language for defining data types whose values may be exchanged across a network between two communicating applications, independently of the possible heterogeneity of the peers. ASN.1 has been adopted by a wide range of applications, such as network management, secure email, mobile telephony, voice over IP etc. It offers a very involved subtyping paradigm consisting of constraints upon recursive types, which restrict their sets of values in a set-theoretic manner or in a structural way. Because of this great expressiveness, most ASN.1 compilers are not likely to fully check arbitrary combinations of subtyping constraints. We propose to fully validate the X.680 specifications, i.e. the main part of ASN.1, by means of an algorithm which relies on the set constraints theory. Set constraints are inclusions between expressions interpreted over the domain of sets of trees which may be recursively defined. We define a system of constraints which can model all the specifications, provide a complete collecting algorithm which extracts such constraints from a given specification and, finally, we give a solving procedure which relies upon an algorithm of Aiken and Wimmers. As a result, either the constraints have no solutions (and the specification must be rejected), or the value sets can be finitely represented. It is straightforward to determine whether these value sets are empty; if they are empty then the specification is rejected. This article addresses both the network tool implementors and the theorist audience. [ABSTRACT FROM AUTHOR]

A novel and efficient protocol based on a single logical ring for multicast communication among a group of processes is presented. The senders and receivers are merged in the same group and this peer group reflects a cooperative (mirror) group of information servers. The protocol maintains consistency in the group by using two strategies. First, by placing a total sequence number in each of the multicast messages, it guarantees total ordering of message delivery for each member. Second, in contrast to other ring protocols which are based on real token passing, it uses a virtual token and achieves message atomicity by using up to n point-to-point control messages. Since no real token passing messages are rotating on the ring, the position of the token holder is calculated by using a logical clock located in each of the processes. The protocol can tolerate communication faults, process crash failures and network partitioning. The protocol has been implemented and experimental results show that the protocol achieves satisfactory performance. [ABSTRACT FROM PUBLISHER]

Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schemes (k-IRS), links carry up to k intervals each. A message is routed over a certain link if its destination belongs to one of the intervals of the link. We present some results for the necessary value of k in order to achieve shortest-path routing. Even though low values of k suffice for very structured networks, we show that for ‘general graphs’ interval routing cannot significantly reduce the space requirements for shortest-path routing. In particular we show that for suitably large n, there are suitable values of p such that for randomly chosen graphs G ∈ Gn, p the following holds, with high probability: if G admits an optimal k-IRS, then [equation: see PDF]. The result is obtained by means of a novel matrix representation for the shortest paths in a network. [ABSTRACT FROM AUTHOR]

We consider here two basic fault-secure scheduling problems for multiprocessor systems. First, given the number of processors in the system and a set of computational tasks of unit length expressed as a complete binary tree, a scheduling algorithm is proposed such that the total execution time is a minimum and no undetected single error result will be delivered. Second, given a deadline and a computation tree, another algorithm is given which generates a fault-secure scheduling using a minimum number of processors. We show that two previous approaches are special cases of these algorithms. We also discuss the way to modify our scheduling to ensure a given fault latency requirement. Finally, extensions that cover multiple errors, non-unit length tasks and computation graphs of arbitrary binary trees are discussed. [ABSTRACT FROM AUTHOR]