Search

This special issue contains four papers selected from the 26th UK Performance Engineering Workshop (UKPEW), which was held during 8–9 July 2010 in the Department of Computer Science at the University of Warwick. UKPEW is the leading UK forum for the presentation of work relating to all aspects of performance modelling and the analysis of computer and telecommunication systems. This year's selected papers demonstrate the variety of topics on offer at UKPEW: performance issues in cloud computing, energy-aware routing in packet networks, source location privacy and multi-hop ad hoc networks for wireless networks. [ABSTRACT FROM AUTHOR]

To solve the problem of group task allocation with time constraints in open and dynamic network environments, this paper proposes a decentralized combinatorial auction-based approach for group task allocation. In the proposed approach, both resource providers and consumers are modeled as intelligent agents. The proposed approach is decentralized, so all the agents are limited to communicating with their neighboring agents. The proposed approach also allows agents to enter and leave the network environments freely, and is robust for the dynamism and openness of the network environments. Tasks in the proposed approach have deadlines, and may need the collaboration of a group of self-interested providers. The experimental results demonstrate that the proposed approach outperforms two well-known task allocation approaches in terms of success rate of task allocation, the individual utility of the agents, the speed of task allocation and scalability. [ABSTRACT FROM AUTHOR]

IEEE 802.22 wireless regional area network (WRAN) is a cognitive radio-based network. WRANs are intended to be deployed by different service providers and designed to opportunistically utilize the unused TV bands. WRANs have to self-coexist with other overlapped WRANs in a distributed manner. Therefore, every service provider tries to acquire a band free of interference from others to satisfy a required quality of service. This self-coexistence problem is one of the major challenges in WRAN. In this paper, we propose a Markov-based distributed approach for mitigating this problem. We model the problem as an absorbing discrete-time Markov chain. In this model, if two or more overlapped WRANs select the same band, then each one should either stay or switch to another band according to a certain switching probability. This process continues until each one of the WRANs finds an interference-free band. In this case, the Markov chain reaches the absorbing state. This model is employed to find the optimal switching probability, which in turn minimizes the time required to reach the absorbing state. The switching probability is numerically found as a function of the number of overlapped WRANs and available bands. Extensive simulation has been conducted to validate our numerical results. [ABSTRACT FROM PUBLISHER]

Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increasing interest as a way to uncover the structure of networks by grouping nodes into communities more densely connected internally than externally. Yet most of the effective methods available do not consider the potential levels of organization, or scales, a network may encompass and are therefore limited. In this paper, we present a method compatible with global and local criteria that enables fast multi-scale community detection on large networks. The method is derived in two algorithms, one for each type of criterion, and implemented with six known criteria. Uncovering communities at various scales is a computationally expensive task. Therefore, this work puts a strong emphasis on the reduction of computational complexity. Some heuristics are introduced for speed-up purposes. Experiments demonstrate the efficiency and accuracy of our method with respect to each algorithm and criterion by testing them against large generated multi-scale networks. This study also offers a comparison between criteria and between the global and local approaches. In particular, our results suggest that global criteria seem to be more robust to noise and thus more accurate than local criteria. [ABSTRACT FROM PUBLISHER]

Sensor networks (SNs) consist of spatially distributed sensors which monitor an environment, and which are connected to some sinks or backbone system to which the sensor data is being forwarded. In many cases, the sensor nodes themselves can serve as intermediate nodes for data coming from other nodes, on the way to the sinks. Much of the traffic carried by SNs will originate from routine measurements or observations by sensors that monitor a particular situation, such as the temperature and humidity in a room or the infrared observation of the perimeter of a house, so that the volume of routine traffic resulting from such observations may be quite high. When important and unusual events occur, such as a sudden fire breaking out or the arrival of an intruder, it will be necessary to convey this new information very urgently through the network to a designated set of sink nodes where this information can be processed and dealt with. This paper addresses the important challenge by avoiding the routine background traffic from creating delays or bottlenecks that impede the rapid delivery of high priority traffic resulting from the unusual events. Specifically we propose a novel technique, the ‘Randomized Re-Routing Algorithm (RRR)’, which detects the presence of novel events in a distributed manner, and dynamically disperses the background traffic towards secondary paths in the network, while creating a ‘fast track path’ which provides better delay and better quality of service (QoS) for the high priority traffic which is carrying the new information. When the surge of new information has subsided, this is again detected by the nodes and the nodes progressively revert to best QoS or shortest-path routing for all the ongoing traffic. The proposed technique is evaluated using a mathematical model as well as simulations, and is also compared with a standard node by a node priority scheduling technique. [ABSTRACT FROM PUBLISHER]

In the design of power-aware on-demand routing protocols in mobile ad hoc networks, it must be taken into account that nodes may use a great amount of power to find the desired routing path during the path-discovery phase. In addition, in previous research on power-aware routing protocols, the path bandwidth was often not considered. In this paper, we tackle these issues by proposing a power-aware routing protocol with low route requests (LRR) to find a path with high path bandwidth. By making a low number of routing requests (RREQs), mobile nodes help to broadcast the routing request only when they first receive the routing requests. In addition, based on the receipt of the routing requests from the neighboring nodes, mobile nodes record the location information of its one-hop neighboring nodes. In the path-reply phase, mobile nodes in the found path use the collected location information of their neighbors and our proposed relay model to modify the found path so that the found path has high bandwidth. In our simulation, we compared our proposed routing protocol (LRR) with ad hoc on-demand distance vector, dynamic source routing and min–max battery capacity routing in terms of the following: power consumption in the path-discovery phase and the path-reply phase, bandwidth of the found path, power consumed during data transmission and overall power consumption. In addition, we compared our two proposed routing protocols, the minimum power consumption routing protocol that selects one path with minimum transmission power from all paths and the LRR routing protocol, in terms of the following: the power consumption in the path-discovery phase, the path bandwidth and the overall power consumption. From the simulation results and the analysis, we can see that the proposed LRR routing protocol that uses a low number of routing requests and our proposed relay model to improve path bandwidth can efficiently reduce the overall power consumption. [ABSTRACT FROM PUBLISHER]

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]

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]

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]

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]

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]