Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 11th International Conference on Distributed Computing and Networking, ICDCN 2010, held in Kolkata, India, during January 3-6, 2010.

There were 169 submissions, 96 to the networking track and 73 to the distributed computing track. After review the committee selected 23 papers for the networking and 21 for the distributed computing track. The topics addressed are network protocol and applications, fault-tolerance and security, sensor networks, distributed algorithms and optimization, peer-to-peer networks and network tracing, parallel and distributed systems, wireless networks, applications and distributed systems, optical, cellular and mobile ad hoc networks, and theory of distributed systems.

Inhaltsverzeichnis

Frontmatter

Keynotes

An Intelligent IT Infrastructure for the Future

The proliferation of new modes of communication and collaboration has resulted in an explosion of digital information. To turn this challenge into an opportunity, the IT industry will have to develop novel ways to acquire, store, process, and deliver information to customers - wherever, however, and whenever they need it. An ”Intelligent IT Infrastructure,” which can deliver extremely high performance, adaptability and security - will be the backbone of these developments. At HP Labs, the central research arm for Hewlett Packard, we are taking a multidisciplinary approach to this problem by spanning four areas: computing, storage, networking and nanotechnology. We are working on the design of an exascale data center that will provide 1000X performance while enhancing availability, manageability and reliability and reducing the power and cooling costs. We are working on helping the transition to effective parallel and distributed computing by developing the software tools to allow application developers to harness parallelism at various levels. We are building a cloud-scale, intelligent storage system that is massively scalable, resilient to failures, self-managed and enterprise-grade. We are designing an open, programmable wired and wireless network platform that will make the introduction of new features quick, easy and cost-effective. Finally, we are making fundamental breakthroughs in nanotechnology - memristors, photonic interconnects, and sensors - that will revolutionize the way data is collected, stored and transmitted. To support the design of such an intelligent IT infrastructure, we will have to develop sophisticated system-level design automation tools that will tradeoff system-level performance, power, cost and efficiency.

Prith Banerjee

Heavy Tails and Models for the Web and Social Networks

The literature is rich with (re)discoveries of power law phenomena; this is especially true of observations of link and traffic behavior on the Web. We survey the origins of these phenomena and several (yet incomplete) attempts to model them, including our recent work on the compressibility of the Web graph and social networks. We then present a number of open problems in Web research arising from these observations.

Prabhakar Raghavan

Data Structures and Algorithms for Packet Forwarding and Classification: Prof. A.K. Choudhury Memorial Lecture

Packet forwarding and classification at Internet speed is a challenging task. We review the data structures that have been proposed for the forwarding and classification of Internet packets. Data structures for both one-dimensional and multidimensional classification as well as for static and dynamic rule tables are reviewed. Sample structures include multibit one- and two-dimensional tries and hybrid shape shifting tries. Hardware assisted solutions such as Ternary Content Addressable Memories also are reviewed.

Sartaj Sahni

Spoken Web: A Parallel Web for the Masses: Industry Keynote

In India and several other countries, the number of mobile phone subscribers far exceeds the number of personal computer users, and continues to grow at a much faster pace (it has already crossed the 450 million mark in India). We will present Spoken Web, an attempt to create a new world wide web, accessible over the telephone network, for the masses in these countries. The Spoken Web is based on the concepts of Hyperspeech and Hyperspeech Transfer Protocol that allow creation of ”VoiceSites” and traversal of ”VoiceLinks”. We describe a simple voice-driven application, which allows people, without any information technology background, to create, host, and access such VoiceSites, and traverse VoiceLinks, using a voice interface over the telephone. We present our experience from pilots conducted in villages in Andhra Pradesh and Gujarat. These pilots demonstrate the ease with which a semi-literate and non-IT savvy population can create VoiceSites with locally relevant content, including schedule of education/training classes, agicultural information, and professional services, and their strong interest in accessing this information over the telephone network. We describe several outstanding challenges and opportunities in creating and using a Spoken Web for facilitating exchange of information and conducting business transactions.

Manish Gupta

India’s Mobile Revolution and the Unfinished Tasks: Invited Lecture

India has made great strides in use of Mobile telephones in recent years. Adding over 10 million phones a month, it is the fastest growing market today. The cell-phones are quickly reaching the deepest parts of the nation and serving the poorest people. The talk will examine what made this possible. It will also focus on what the unfinished telecom tasks for India are. It will examine what India is doing in terms of providing Broadband wireless connectivity to its people; what it is doing towards R&D and technology development in the county; and how it aims at building global telecom manufacturing and telecom operation companies in India.

Ashok Jhunjhunwala

Network Protocols and Applications

Scheduling in Multi-Channel Wireless Networks

The availability of multiple orthogonal channels in a wireless network can lead to substantial performance improvement by alleviating contention and interference. However, this also gives rise to non-trivial channel coordination issues. The situation is exacerbated by variability in the achievable data-rates across channels and links. Thus, scheduling in such networks may require substantial information-exchange and lead to non-negligible overhead. This provides a strong motivation for the study of scheduling algorithms that can operate with

limited information

while still providing acceptable worst-case performance guarantees. In this paper, we make an effort in this direction by examining the scheduling implications of multiple channels and heterogeneity in channel-rates. We establish lower bounds on the performance of a class of

maximal

schedulers. We first demonstrate that when the underlying scheduling mechanism is “imperfect”, the presence of multiple orthogonal channels can help alleviate the detrimental impact of the imperfect scheduler, and yield a significantly better efficiency-ratio in a wide range of network topologies. We then establish performance bounds for a scheduler that can achieve a good efficiency-ratio in the presence of channels with heterogeneous rates without requiring explicit exchange of queue-information. Our results indicate that it may be possible to achieve a desirable trade-off between performance and information.

Vartika Bhandari, Nitin H. Vaidya

Email Shape Analysis

Email has become an integral part of everyday life. Without a second thought we receive bills, bank statements, and sales promotions all to our inbox. Each email has hidden features that can be extracted. In this paper, we present a new mechanism to characterize an email without using content or context called Email Shape Analysis. We explore the applications of the email shape by carrying out a case study; botnet detection and two possible applications: spam filtering, and social-context based finger printing. Our in-depth analysis of botnet detection leads to very high accuracy of tracing templates and spam campaigns. However, when it comes to spam filtering we do not propose new method but rather a complementing method to the already high accuracy Bayesian spam filter. We also look at its ability to classify individual senders in personal email inbox’s.

Paul Sroufe, Santi Phithakkitnukoon, Ram Dantu, João Cangussu

Maintaining Safety in Interdomain Routing with Hierarchical Path-Categories

The stable-paths problem is an abstraction of the basic functionality of the Internet’s BGP routing protocol. It has received considerable attention due to instabilities observed in BGP. In this abstraction, each node informs its neighboring nodes of its current path to the destination node. From the paths received from its neighbors, each node chooses the best path according to some local routing policy. However, since routing policies are chosen locally, conflicts may occur between nodes, resulting in unstable behavior. Deciding if a set of routing policies is stable is NP-hard. Thus, current solutions involve restricting routing policies to avoid instabilities, while maintaining enough flexibility for the routing policies to be useful. Recently, path-categories have been introduced. E.g., a simple system consists of a category of regular paths, and a category of backup paths. By combining path-categories into a total order (regular paths have higher priority than backup paths), it has been shown that the resulting system is stable if each category by itself is stable. In this paper, we relax the total-order of categories into a partial-order, and thus provide greater flexibility of routing choices at each node. We extend the definition of the stable-paths problem to allow such flexibility, and show that if each category is stable in itself, then the whole system is stable. In addition, we show an upper bound on the convergence time of the whole system provided each category in itself has a bounded convergence time.

Jorge A. Cobb

Fault-tolerance and Security

On Communication Complexity of Secure Message Transmission in Directed Networks

We re-visit the problem of

perfectly secure message transmission

(PSMT) in a

directed network

under the presence of a threshold adaptive Byzantine adversary, having

unbounded computing power

. Specifically, we derive the lower bounds on communication complexity of (a) two phase PSMT protocols and (b)

three or more phase

PSMT protocols in directed networks. Moreover, we show that our lower bounds are

asymptotically tight

, by designing

communication optimal

PSMT protocols in directed networks, which are first of their kind.

We re-visit the problem of

perfectly reliable message transmission

(PRMT) as well. Any PRMT protocol that sends a message containing ℓ field elements by communicating

${\cal O}(\ell)$

field elements, is referred as

communication optimal PRMT

or

PRMT with constant factor overhead

. Here, we characterize the class of directed networks over which

communication optimal

PRMT or PRMT

with constant factor overhead

is possible. Moreover, we design a communication optimal PRMT over a directed network that satisfies the conditions stated in our characterization.

Arpita Patra, Ashish Choudhary, C. Pandu Rangan

On Composability of Reliable Unicast and Broadcast

In the recent past composability has emerged as a key requirement for various distributed protocols. It is not enough for a protocol to be robust when it runs in isolation or in a “stand-alone” setting but it should be robust even in an environment where several copies of the same protocol or other protocol(s) are running simultaneously. In this work, we investigate the composability for protocols that tolerate a bounded adversary modeled as a probabilistic polynomial time Turing machine. We examine composability of protocols for two fundamental problems in distributed computing - reliable unicast and reliable broadcast. We show that any composable protocol – for reliable unicast tolerating an adversary, that corrupts up to any

t

nodes, requires 2

t

 + 1 connectivity and for reliable broadcast tolerating an adversary, that corrupts up to any

t

nodes, requires

n

 > 3

t

and 2

t

 + 1 connectivity.

Anuj Gupta, Sandeep Hans, Kannan Srinathan, C. Pandu Rangan

A Leader-Free Byzantine Consensus Algorithm

The paper considers the consensus problem in a partially synchronous system with Byzantine faults. It turns out that, in the partially synchronous system, all deterministic algorithms that solve consensus with Byzantine faults are leader-based. This is not the case of benign faults, which raises the following fundamental question: is it possible to design a deterministic Byzantine consensus algorithm for a partially synchronous system that is not leader-based? The paper gives a positive answer to this question, and presents a leader-free algorithm that is resilient-optimal and signature-free.

Fatemeh Borran, André Schiper

Authenticated Byzantine Generals in Dual Failure Model

Pease

et al.

introduced the problem of Byzantine Generals (BGP) to study the effects of Byzantine faults in distributed protocols for reliable broadcast. It is well known that BGP among

n

players tolerating up to

t

faults is (efficiently) possible iff

n

 > 3

t

. To overcome this severe limitation, Pease

et al.

introduced a variant of BGP,

Authenticated Byzantine General

(ABG). Here players are supplemented with digital signatures (or similar tools) to thwart the challenge posed by Byzantine faults. Subsequently, they proved that with the use of authentication, fault tolerance of protocols for reliable broadcast can be amazingly increased to

n

 > 

t

(which is a huge improvement over the

n

 > 3

t

).

Byzantine faults are the most generic form of faults. In a network not

all

faults are always malicious. Some faulty nodes may only leak their data while others are malicious. Motivated from this, we study the problem of ABG in (

t

b

,

t

p

)-mixed adversary model where the adversary can corrupt up to any

t

b

players actively and control up to any other

t

p

players passively. We prove that in such a setting, ABG over a completely connected synchronous network of

n

nodes tolerating a (

t

b

,

t

p

)-adversary is possible iff

n

 > 2

t

b

+min(

t

b

,

t

p

) when

t

p

 > 0. Interestingly, our results can also be seen as an attempt to unify the extant literature on BGP and ABG.

Anuj Gupta, Prasant Gopal, Piyush Bansal, Kannan Srinathan

Sensor Networks

Mission-Oriented k-Coverage in Mobile Wireless Sensor Networks

The problem of sensor deployment to achieve

k

-coverage of a field, where every point is covered by at least

k

sensors, is very critical in the design of energy-efficient wireless sensor networks (WSNs). It becomes more challenging in mission-oriented WSNs, where sensors have to move in order to

k

-cover a

region of interest

in the field. In this paper, we consider the problem of

k

-coverage in mission-oriented mobile WSNs which we divide into two sub-problems, namely

sensor placement

and

sensor selection

. The sensor placement problem is to identify a subset of sensors and their locations in a region of interest so it is

k

-covered with a minimum number of sensors. The sensor selection problem is to determine which sensors should move to the above-computed locations in the region while minimizing the total energy consumption due to sensor mobility and communication. Simulation results show that our solution to the

k

-coverage problem in mission-oriented mobile WSNs outperforms an existing one in terms of the number of sensors needed to achieve

k

-coverage of a region of interest in the field as well as their total energy consumption.

Habib M. Ammari, Sajal K. Das

Lessons from the Sparse Sensor Network Deployment in Rural India

We discuss the key issues in the deployment of

sparse

sensor networks. The network monitors several environment parameters and is deployed in a semi-arid region for the benefit of small and marginal farmers. We begin by discussing the problems of an existing unreliable 1 sq km

sparse

network deployed in a village. The proposed solutions are implemented in a new cluster. The new cluster is a reliable 5 sq km network. Our contributions are two fold. Firstly, we describe a novel methodology to deploy a

sparse

reliable data gathering sensor network and evaluate the “safe distance” or “reliable” distance between nodes using propagation models. Secondly, we address the problem of transporting data from rural aggregation servers to urban data centres. This paper tracks our steps in deploying a sensor network in a village in India, trying to provide better diagnosis for better crop management. Keywords - Rural, Agriculture, GPRS, Sparse.

T. V. Prabhakar, H. S. Jamadagni, Amar Sahu, R. Venkatesha Prasad

A New Architecture for Hierarchical Sensor Networks with Mobile Data Collectors

Hierarchical sensor networks that use higher-powered

relay nodes

as cluster heads have gained popularity in recent years. An important design problem in such networks is to determine an appropriate placement scheme for the relay nodes, in order to ensure adequate coverage and connectivity requirements with as few relay nodes as possible. Current placement techniques available in the literature typically do not consider the effects of node mobility on the placement strategy. Recently, the use of mobile data collectors (MDC) have been shown to improve network performance in a variety of sensor network applications. In this paper, we have proposed a new hierarchical architecture for heterogenous sensor networks using relay nodes, with a MDC. Our goal is to use a minimum number of relay nodes and place them optimally, such that each sensor node can send its data to at least one relay node and the trajectory of the MDC visiting the relay nodes is as short as possible. We have presented an Integer Linear Program (ILP) that jointly optimizes the above objectives for such networks. We have shown that our integrated approach can lead to significant improvements compared to the case where the problems of relay node placement and determining an optimal trajectory of the MDC are considered independently.

Ataul Bari, Ying Chen, Arunita Jaekel, Subir Bandyopadhyay

Stability Analysis of Multi-hop Routing in Sensor Networks with Mobile Sinks

This paper presents a formulation for analyzing stability issues inherent to multi-hop routing in mobile sink based data collection systems. The paper parameterizes the extent of multi-hop routing as a hop-bound factor which is used to represent a wide spectrum of design options including single-hop with mobile sink, multi-hop with static sink, and different levels of mobile sink based multi-hop routing in between. An analytical model is developed for studying the impacts of multi-hop routing on collection delay performance. A number of thresholds are derived from the model for determining the amount of multi-hop routing that can be used for stable and efficient data collection in the context of constantly moving sinks. Finally, the system performance trends obtained from the model are validated using packet level simulations.

Jayanthi Rao, Subir Biswas

Distributed Algorithms and Optimization

Optimizing Distributed Computing Workflows in Heterogeneous Network Environments

Next-generation computation-intensive applications in various science and engineering fields feature large-scale computing workflows. Supporting such computing workflows and optimizing their network performance in terms of end-to-end delay or frame rate in heterogeneous network environments are critical to the success of these distributed applications that require fast response time or smooth data flow. We formulate six linear pipeline configuration problems with different mapping objectives and network constraints, and one general workflow mapping problem. We investigate the computational complexity of these problems and design optimal or heuristic algorithms with rigorous correctness proof and performance analysis. An extensive set of optimization experiments on a large number of simulated workflows and networks illustrate the superior performance of the proposed algorithms in comparison with that of existing methods.

Yi Gu, Qishi Wu

Radio Network Distributed Algorithms in the Unknown Neighborhood Model

The paper deals with radio network distributed algorithms where initially no information about node degrees is available. We show that the lack of such an information affects the time complexity of existing fundamental algorithms by only a polylogarithmic factor. More precisely, given an

n

-node graph modeling a multi-hop radio network, we provide a

O

(log

2

n

) time distributed algorithm that computes w.h.p., a constant approximation value of the degree of each node. We also provide a

O

(Δlog

n

 + log

2

n

) time distributed algorithm that computes w.h.p., a constant approximation value of the local maximum degree of each node, where the global maximum degree Δ of the graph is not known. Using our algorithm as a plug-and-play procedure, we show that the local maximum degree can be used instead of Δ to break the symmetry efficiently. We illustrate this claim by revisiting some fundamental algorithms that use Δ as a key parameter. First, we investigate the generic problem of simulating any point-to-point interference-free message passing algorithm in the radio network model. Then, we study the fundamental coloring problem in unit disk graphs. The obtained results show that the local maximum degree allows nodes to self-organize in a local manner and to avoid the radio interferences from being a communication bottleneck.

Bilel Derbel, El-Ghazali Talbi

Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks

A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external intervention in finite time. Unidirectional networks preclude many common techniques in self-stabilization from being used, such as preserving local predicates. The focus of this work is on the classical vertex coloring problem, that is a basic building block for many resource allocation problems arising in wireless sensor networks.

In this paper, we investigate the gain in complexity that can be obtained through randomization. We present a probabilistically self- stabilizing algorithm that uses

k

states per process, where

k

is a parameter of the algorithm. When

k

 = Δ + 1, the algorithm recovers in expected

O

n

) actions. When

k

may grow arbitrarily, the algorithm recovers in expected

O

(

n

) actions in total. Thus, our algorithm can be made optimal with respect to space or time complexity. Our case study hints that randomization could help filling the complexity gap between bidirectionnal and unidirectionnal networks.

Samuel Bernard, Stéphane Devismes, Katy Paroux, Maria Potop-Butucaru, Sébastien Tixeuil

A Token-Based Solution to the Group Mutual l-Exclusion Problem in Message Passing Distributed Systems

(Short Paper)

The Group Mutual

l-

Exclusion (GMLE) problem is an interesting combination of two widely studied generalizations of the classical mutual exclusion problem namely,

k

-exclusion and group mutual exclusion (GME). In GMLE, up to

l

sessions can be held simultaneously. In the present exposition, we propose a token-based algorithm to the GMLE problem. To the best of our knowledge, this is the first token-based algorithm for the GMLE problem. The proposed algorithm satisfies all properties necessary for a GMLE algorithm.

Abhishek Swaroop, Awadhesh Kumar Singh

Peer-to-Peer Networks and Network Tracing

The Weak Network Tracing Problem

Computing the topology of a network in the Internet is a problem that has attracted considerable research interest. The usual method is to employ Traceroute, which produces sequences of nodes that occur along the routes from one node (source) to another (destination). In every trace thus produced, a node occurs by either its unique identifier, or by the anonymous identifier ′′*′′. We have earlier proved that there exists no algorithm that can take a set of traces produced by running Traceroute on network

N

and compute one topology which is guaranteed to be the topology of

N

. This paper proves a much stronger result: no algorithm can produce a small set of topologies that is guaranteed to contain the topology of

N

, as the size of the solution set is exponentially large. This result holds even when every edge occurs in a trace, all the unique identifiers of all the nodes are known, and the number of nodes that are irregular (anonymous in some traces) is given. On the basis of this strong result, we suggest that efforts to exactly reconstruct network topology should focus on special cases where the solution set is small.

H. B. Acharya, M. G. Gouda

Poisoning the Kad Network

Since the demise of the Overnet network, the Kad network has become not only the most popular but also the only widely used peer-to-peer system based on a distributed hash table. It is likely that its user base will continue to grow in numbers over the next few years as, unlike the eDonkey network, it does not depend on central servers, which increases scalability and reliability. Moreover, the Kad network is more efficient than unstructured systems such as Gnutella. However, we show that today’s Kad network can be attacked in several ways by carrying out several (well-known) attacks on the Kad network. The presented attacks could be used either to hamper the correct functioning of the network itself, to censor contents, or to harm other entities in the Internet not participating in the Kad network such as ordinary web servers. While there are simple heuristics to reduce the impact of some of the attacks, we believe that the presented attacks cannot be thwarted easily in any fully decentralized peer-to-peer system without some kind of a centralized certification and verification authority.

Thomas Locher, David Mysicka, Stefan Schmid, Roger Wattenhofer

Credit Reputation Propagation: A Strategy to Curb Free-Riding in a Large BitTorrent Swarm

BitTorrent ensures cooperation among peers through its inbuilt collaborative mechanisms, however due to lack of proper incentives, significant amount of free riding is observed in it. Though in the existing literature, there exists some strategies to prevent free-riding, however, in case of large swarm sizes, it can be shown that they fail to stop free riding attempts effectively. To overcome this limitation, this paper presents a novel approach based on propagating the knowledge about the existence of possible free riders in the form of reputation among the peers within the swarm. It is shown, how a possible free riding attempt on a peer is reported to others and how this knowledge is utilized in deciding whether to upload to a particular peer or not within a BitTorrent swarm. Simulation results demonstrate how the proposed strategy effectively punishes free riders even in large swarm sizes.

Suman Paul, Subrata Nandi, Ajit Pal

Formal Understanding of the Emergence of Superpeer Networks: A Complex Network Approach

In this paper, we develop a formal framework which explains the emergence of superpeer networks on execution of the bootstrapping protocols by incoming nodes. Bootstrapping protocols exploit physical properties of the online peers like resource content, processing power, storage space etc as well as takes the finiteness of bandwidth of each online peer into consideration. With the help of rate equations, we show that application of these protocols results in the emergence of superpeer nodes in the network - the exact degree distribution is evaluated. We validate the framework developed in this paper through extensive simulation. Interestingly, our analysis reveals that increase in the amount of resource and the number of resourceful nodes in the network do not always help to increase the fraction of superpeer nodes. The impact of the frequent departure of the peers on the topology of the emerging network is also evaluated. As an application study, we show that our framework can explain the topological configuration of commercial Gnutella networks.

Bivas Mitra, Abhishek Kumar Dubey, Sujoy Ghose, Niloy Ganguly

Parallel and Distributed Systems

Parallelization of the Lanczos Algorithm on Multi-core Platforms

In this paper, we report our parallel implementations of the Lanczos sparse linear system solving algorithm over large prime fields, on a multi-core platform. We employ several load-balancing methods suited to these platforms. We have carried out process-level and thread-level parallel implementations under two different arithmetic libraries, and the best speedup obtained is 6.57 on eight cores. To the best of our knowledge, no implementation of the Lanczos algorithm on a multi-core platform is ever reported in the literature. Moreover, we seem to have achieved significantly larger speedup compared to all previously reported implementations of this algorithm.

Souvik Bhattacherjee, Abhijit Das

Supporting Malleability in Parallel Architectures with Dynamic CPUSETsMapping and Dynamic MPI

Current parallel architectures take advantage of new hardware evolution, like the use of multicore machines in clusters and grids. The availability of such resources may also be dynamic. Therefore, some kind of adaptation is required by the applications and the resource manager to perform a good resource utilization. Malleable applications can provide a certain flexibility, adapting themselves on-the-fly, according to variations in the amount of available resources. However, to enable the execution of this kind of applications, some support from the resource manager is required, thus introducing important complexities like special allocation and scheduling policies. Under this context, we investigate some techniques to provide malleable behavior on MPI applications and the impact of this support upon a resource manager. Our study deals with two approaches to obtain malleability: dynamic

CPUSETs

mapping and dynamic MPI, using the OAR resource manager. The validation experiments were conducted upon Grid5000 platform. The testbed associates the charge of real workload traces and the execution of MPI benchmarks. Our results show that a dynamic approach using malleable jobs can lead to almost 25% of improvement in the resources utilization, when compared to a non-dynamic approach. Furthermore, the complexity of the malleability support, for the resource manager, seems to be overlapped by the improvement reached.

Márcia C. Cera, Yiannis Georgiou, Olivier Richard, Nicolas Maillard, Philippe O. A. Navaux

Impact of Object Operations and Relationships on Concurrency Control in DOOS

(Short Paper)

The objective of this paper is to analyze the impact of object operations and relationships in concurrency control (CC)using multi granular locking model in Distributed object oriented system. The types and properties of object operations and relationships have been used to propose the lock types and granularity size. The sub types and properties of object relationships like inheritance, aggregation have been used to propose an enhanced compatibility matrix given in [KIM1] and [LEE1].

V. Geetha, Niladhuri Sreenath

Causal Cycle Based Communication Pattern Matching

(Short Paper)

A distributed system employing checkpoint and rollback-recovery as a fault tolerance mechanism, suffers from overhead attributed by the technique. Authors in [4] proposes a technique to automatically identify a checkpoint and recovery protocol based on a pre-estimated database of overhead measures. The technique depends on computation of similarity between a pair of communication patterns. The computation involves first partitioning both the communication patterns into small pieces or

splices

. A pair of splices, one taken from each of the two communication patterns in question, are then compared to compute a similarity measure. Splicing a communication pattern is an important step in the method since it bears heavy significance for later steps in the computation. This paper introduces a new method for splicing. Experimental results show that the technique yields better similarity measure values in comparison to results reported in [4].

Himadri Sekhar Paul

Wireless Networks

Channel Assignment in Virtual Cut-through Switching Based Wireless Mesh Networks

Conventional wireless networks employ a contention based channel access mechanism, which not only imposes high latency but also reduces goodput of the network. Lack of interference estimation algorithms over the entire network results in unpredictable collision, packet loss and retransmissions. Advances in multicarrier modulation techniques enable us to group subcarriers into orthogonal subchannels and treat them separately as information carriers. While this provides an increased number of non-interfering channels, intelligent utilization of the given spectrum is also required. In this paper, a solution for decreasing latency in mesh networks has been proposed by aptly incorporating a virtual cut-through switching technique to route packets in the network. To alleviate the impact of interference on packet reception, we also propose a fast pair-wise interference detection scheme, which is used for channel allocation. The cumulative performance of the proposed protocol shows improvement over existing Wi-Fi based mesh networks that provide a motivating platform for future protocol developments using this technique.

Dola Saha, Aveek Dutta, Dirk Grunwald, Douglas Sicker

Efficient Multi-hop Broadcasting in Wireless Networks Using k-Shortest Path Pruning

In this paper, we proposed a multi-hop wireless broadcast method called

k

-Shortest Path Pruning (

k

-SPP). It is based on the Dominant Pruning method of Lim and Kim, and improves upon it in the context of certain routing protocols, such as Zone Routing Protocol. In our approach, every node must know about its

k

-hop neighborhood, for some constant

k

 ≥ 3. Experimental results demonstrate that our technique requires fewer transmissions than Dominant Pruning broadcasting.

Michael Q. Rieck, Subhankar Dhar

Bandwidth Provisioning in Infrastructure-Based Wireless Networks Employing Directional Antennas

Motivated by the widespread proliferation of wireless networks employing directional antennas, we study the problem of provisioning bandwidth in such networks. Given a set of subscribers and one or more access points possessing directional antennas, we formalize the problem of orienting these antennas in two fundamental settings: (i) subscriber-centric, where the objective is to fairly allocate bandwidth among the subscribers and (ii) provider-centric, where the objective is to maximize the revenue generated by satisfying the bandwidth requirements of subscribers.

For both the problems, we first design algorithms for a network with only one access point working under the assumption that the number of antennas does not exceed the number of non-interfering channels. Using the well-regarded lexicographic max-min fair allocation as the objective for a subscriber-centric network, we present an optimum dynamic programming algorithm. For a provider-centric network, the allocation problem turns out to be NP-hard. We present a greedy heuristic based algorithm that guarantees almost half of the optimum revenue. We later enhance both these algorithms to operate in more general networks with multiple access points and no restrictions on the relative numbers of antennas and channels. A simulation-based evaluation using OPNET demonstrates the efficacy of our approaches and provides us further in insights into these problems.

Shiva Kasiviswanathan, Bo Zhao, Sudarshan Vasudevan, Bhuvan Urgaonkar

ROTIO+: A Modified ROTIO for Nested Network Mobility

The NEMO Basic Support (NBS) protocol ensures session continuity for all nodes in a moving network by maintaining a tunnel between Mobile Router (MR) and its Home Agent (HA). The NBS protocol, however, suffers from sub-optimality problem in routing, which gets amplified as the level of nesting increases [4]. The ROTIO [5] is a route optimization scheme for nested NEMO that restricts the number of tunnels to two thereby alleviating the pinball routing problem to a great extent. In this paper, we propose ROTIO+, a simple but practical extension of ROTIO scheme, to further reduce the number of tunnels to one in nested NEMO. In ROTIO+ scheme, the MR uses two binding updates (BUs): one to its HA and the other to the Top Level Mobile Router (TLMR). In the BU to its HA, it provides both the Care of Address (CoA) and Home Address (HoA) of the TLMR. Under normal circumstances, the HA routes all packets for the MR to the CoA of the TLMR. When the QoS decreases beyond a threshold i.e. the TLMR is changing the point of attachment, the HA sends the packet to the HoA of the TLMR. Thus, the scheme limits the number of visits to HA to one for a nested network and also has a fall back scheme when the TLMR changes point of attachment. The results show that it is an effective solution for route optimisation problem in nested NEMO.

Ansuman Sircar, Bhaskar Sardar, Debashis Saha

Applications of Distributed Systems

VirtualConnection: Opportunistic Networking for Web on Demand

Social networks such as Facebook and Secondlife are popular. Wireless devices abound from affluent countries to developing countries. Social networks need wide area Internet support. Wireless interfaces offer ad hoc networking capability, without the need for infrastructure support. Web on Demand (WoD) aims to bridge the gap between ad hoc social networks (people in close proximity with shared interests) and ad hoc networking. A key requirement for WoD is transparent connection management. This paper makes three contributions: First, an abstraction called VirtualConnection for transparent connection creation and migration, with socket-like API; second, an implementation on iPAQs (Windows Mobile) as a user level library, and proof of efficacy of using this abstraction for realizing WoD; third, evaluations to establish the performance of this abstraction. In particular, we show the performance degradation due to virtualizing the connection is negligible.

Lateef Yusuf, Umakishore Ramachandran

Video Surveillance with PTZ Cameras: The Problem of Maximizing Effective Monitoring Time

The effectiveness of the surveillance (monitoring a set of mobile targets with a set of cameras) depends on the resolution of the monitored images and the duration for which the targets are monitored. PTZ cameras are a natural choice to maintain a desired level of resolution for mobile targets. Maintaining resolution by controlling the camera parameters above a desired threshold value, however, implies that the field of regard of a camera cannot be arbitrarily broadened to include multiple targets. Camera for each target needs to be judiciously chosen to ensure monitoring for prolonged time interval. In this paper we propose a metric viz. average effective monitoring time (AEMT), towards capturing the effectiveness of video based surveillance. To achieve enhanced AEMT, we formulate an optimization problem in terms of associating cameras with the targets based on an appropriate weight function and design an efficient distributed algorithm. Simulation results show that our approach contributes significantly towards improving AEMT.

Satyajit Banerjee, Atish Datta Chowdhury, Subhas Kumar Ghosh

DisClus: A Distributed Clustering Technique over High Resolution Satellite Data

This paper presents a distributed Grid-Density based Satellite data Clustering technique,

DisClus

, which can detect clusters of arbitrary shapes and sizes over high resolution, multi-spectral satellite datasets. Quality of the clusters is further enhanced by incorporating a partitioning based method for the reassignment of the border pixels to the most relevant clusters. Experimental results are presented to establish the superiority of the technique in terms of scale-up, speedup as well as cluster quality.

Sauravjyoti Sarmah, Dhruba Kumar Bhattacharyya

Performance Evaluation of a Wormhole-Routed Algorithm for Irregular Mesh NoC Interconnect

Irregular routing algorithms are based on fault-tolerant algorithms. They are capable of use with some modifications for irregular networks, and conventionally use several virtual channels (VCs) to pass faults and irregular nodes. A well-known wormhole-switched routing algorithm named f-cube3 employs three virtual channels to overtake faulty blocks. We have estimated an irregular routing algorithm derived from f-cube3 as a solution to increase the utilization of links with a higher saturation point which uses fewer numbers of VCs in comparison to f-cube3 by reducing desired virtual channels to two supporting irregular network. Moreover, simulation of both algorithms, for the same setting has been presented. Over and above, as the simulation results show, our algorithm has a higher performance in comparison with f-cube3 even with one less VC. As well, the results show that our algorithm has less blocked messages in the network with higher switched and routed messages in Network-on-Chip (NoC).

Arshin Rezazadeh, Ladan Momeni, Mahmood Fathy

Optical, Cellular and Mobile Ad Hoc Networks

Dynamic Multipath Bandwidth Provisioning with Jitter, Throughput, SLA Constraints in MPLS over WDM Network

Multipath bandwidth provisioning is one of the prime interest of next generation optical networks. It is a policy to distribute the requested bandwidth in multiple link disjoint paths on the basis of some optimization function. It also helps to increase network throughput. By using backup path provisioning, we can meet availability requirement of service level agreement (SLA). But multipath bandwidth provisioning leads to problem like jitter which is the difference of delay between two paths. In this paper, we propose a dynamic multipath bandwidth provisioning scheme in telecom mesh network which takes both throughput and jitter into account. It also meets SLA requirement of incoming requests. Our provisioning scheme is dynamic in the sense that it allocates bandwidth for service requests that arrive periodically with no knowledge of future requests and hence requiring an online algorithm. Our algorithm uses 1:N protection scheme against restoration since only protection can guarantee connection availability which is very important to meet SLA. Simulation studies show that efficient multipath bandwidth provisioning using our proposed algorithm can result in total network throughput to be 70% to 90% as well as keeping the effect of jitter that is buffer space overhead to a substantial of 8% to 10% of total load. We will show the simulation result with mean down time 400 second/year and 500 second/year.

Palash Dey, Arkadeep Kundu, Mrinal K. Naskar, Amitava Mukherjee, Mita Nasipuri

Path Protection in Translucent WDM Optical Networks

Translucent WDM networks are receiving attention as long-haul back bone networks. One important aspect of such networks that has not received attention is the possibility of cycles in the path of a translucent network. This is the first work on implementing path protection in translucent networks, considering the possibility of cycles. Two formulations have been proposed here for dynamic lightpath allocation. The first is more comprehensive but may take an unacceptably long time. The second formulation is very fast but, in general, has slightly worse performance. We have studied the performances of these formulations using a number of well-known networks.

Q. Rahman, Subir Bandyopadhyay, Ataul Bari, Arunita Jaekel, Y. P. Aneja

Post Deployment Planning of 3G Cellular Networks through Dual Homing of NodeBs

3G Cellular networks typically consist of a group of NodeBs connected to a Radio Network Controller (RNC), and a group of RNCs to a Serving GPRS Support Node (SGSNs) as well as to a Mobile Switching Centre (MSCs). Post deployment planning of such network is to re-plan the connectivity among the above mentioned network elements with an objective to minimize the cost of operation of the network. This planning problem is traditionally solved under single homing consideration (i.e., one NodeB is homed with only one RNC). However, a single homing solution becomes ineffective when the subscriber distribution changes over time and groups of subscribers begin to show a specific diurnal pattern of their inter-MSC/SGSN mobility. One of the solutions for this problem is dual-homing where some selected NodeBs are connected to two RNCs to reduce the complex handoffs involving two different RNCs as well as two different MSCs/SGSNs. In this paper, we have mapped the dual-homing problem into a search problem and used Simulated Annealing (SA) and Tabu Search (TS) techniques to optimally select the NodeBs and RNCs to be connected. A comparison of the performances of the two meta-heuristic techniques reveals that, though both are efficient enough to produce good solutions, TS is found to be better than SA throughout.

Samir K. Sadhukhan, Swarup Mandal, Partha Bhaumik, Debashis Saha

K-Directory Community: Reliable Service Discovery in MANET

Service discovery in MANET suffers from frequent service unavailability due to failures of service providers or directory nodes. Ensuring network-wide service availability by replication requires minimizing costs associated with storage, update and discovery. Existing works in MANET have not addressed these challenging issues adequately. In this paper, we propose a distributed directory-based service discovery protocol (SDP) for MANET. Our protocol works by electing top K nodes with rich resources as directories, which are then divided into multiple quorums. Services registered with a directory are replicated among its quorum members. This approach reduces replication and update costs, and guarantees network-wide service availability using the quorum intersection property. An incremental election policy is adopted to cope with directory failures. We have carried out extensive simulations and also developed a prototype system. Our performance evaluation results show that, compared with similar work, our protocol significantly reduces message cost and improves system robustness.

Vaskar Raychoudhury, Jiannong Cao, Weigang Wu, Yi Lai, Canfeng Chen, Jian Ma

Theory of Distributed Systems

An Online, Derivative-Free Optimization Approach to Auto-tuning of Computing Systems

We develop an online optimisation framework for self tuning of computer systems. Towards this, we first discuss suitable objective functions. We then develop an iterative technique that is robust to noisy measurements of objective function and also requires fewer perturbations on the configuration. We essentially adapt the Nelder-Mead algorithm to work with constrained variables and also allow noisy measurements. Extensive experimental results on a queueing model and on an actual system illustrate the performance of our scheme.

Sudheer Poojary, Ramya Raghavendra, D. Manjunath

Consistency-Driven Probabilistic Quorum System Construction for Improving Operation Availability

Pessimistic quorum-based data replication strategies generally strive for maximizing operation availabilities while adhering to a strict consistency notion. Unfortunately, their operation availabilities are strictly upper-bounded. Probabilistically relaxing the consistency notion permits to overcome this bound, introducing probabilistic data replication strategies that allow for a data consistency vs. operation availabilities trade-off. We present two construction algorithms transforming strict quorum systems into probabilistic ones and compare them in terms of operation availabilities and degree of data consistency.

Kinga Kiss Iakab, Christian Storm, Oliver Theel

Hamiltonicity of a General OTIS Network

(Short Paper)

In this paper, we present a novel method to construct a Hamiltonian cycle for an

n

×

n

general OTIS network. Our method is common for both odd and even value of

n

in contrast to two separate schemes for odd and even

n

as described in [1]. We also provide an algorithm that generates a Hamiltonian cycle of a general (

n

+ 2

k

) ( (

n

+ 2

k

) OTIS network directly from a basic Hamiltonian cycle of an

n

(

n

OTIS network.

Nagendra Kumar, Rajeev Kumar, Dheeresh K. Mallick, Prasanta K. Jana

Specifying Fault-Tolerance Using Split Precondition Logic

(Short Paper)

The focus of the paper is to provide a formal logic, for specifying fault-tolerant systems, using a state and transition based approach. Another goal is to reason, formally, about the possible behaviors of a system consisting of some malicious nodes. The Byzantine agreement protocol serves as an illustration for the notation. The contribution is the development of a style of modeling and reasoning that allows for a straightforward and thorough analysis of fault-tolerant systems.

Awadhesh Kumar Singh, Anup Kumar Bandyopadhyay

Network Protocols

Fast BGP Convergence Following Link/Router Failure

A Modified Border Gateway Protocol (MBGP) has been proposed towards achieving faster BGP convergence in the Internet following link/router/ network failures. MBGP adopts the overall strategy of distributed fault detection-cum-identification, fault notification and rediscovery-cum-readvertisement of valid routes. In the assumed simplified model of the Internet, the sole MBGP router in each autonomous system (AS) identifies any failed component using the novel concept of special neighbors and notifies the identity of the failed component to all the MBGP routers in the Internet. Six new messages, including a query-response message pair and four permanent withdrawal messages, have been proposed in MBGP, without changing the BGP message format. The path exploration problem is significantly reduced because some failures cause no path exploration, the others do but only in a small number of nearby routers and, finally, no invalid messages are ever exchanged. Simulation studies have demonstrated significantly faster convergence of MBGP over BGP.

Swapan Kumar Ray, Susmit Shannigrahi

On Using Network Tomography for Overlay Availability

Overlay networks are logical abstraction on a physical network (underlay) where each overlay node corresponds to a specific underlay node and overlay links correspond to paths on the underlay. The use of network layer information for constructing overlay networks can greatly improve their performance. Knowledge of underlay properties such as available bandwidths, loss rates and topology can help in efficient construction, maintenance and optimization of overlays which have to provide service guarantees. In absence of any support from the network core, it becomes necessary to infer those properties by performing end-to-end measurements on the network. We develop probing techniques which infer information about the structure of the underlay and use it for construction of fault-tolerant overlay networks. Algorithms and measurement techniques for the same are presented together with the experimental findings.

Umesh Bellur, Mahak Patidar

QoSBR: A Quality Based Routing Protocol for Wireless Mesh Networks

In this paper we present a QoS based routing protocol for wireless mesh networks that tries to maximize the probability of successful transmissions while minimizing the end-to-end delay. The proposed routing protocol uses reactive route discoveries to collect key parameters from candidate routes to estimate the probability of success and delay of data packets transmitted over them. To make sure that it estimates these quantities for the flow of data packets and not control packets, we propose a new route quality metric that uses performance models of data packet transmissions that are obtained from offline experiments. We present simulation based performance evaluations of the proposed QoS based routing protocol and show its benefits in comparison to some other known routing protocols.

Amitangshu Pal, Sandeep Adimadhyam, Asis Nasipuri

An ACO Based Approach for Detection of an Optimal Attack Path in a Dynamic Environment

Attack graph

is a tool to analyze multi-stage, multi-host attack scenarios in a network. Each attack scenario is depicted by an

attack path

which is essentially a series of

exploits

with a severity score that presents a comparative desirability of a particular network service. In an

attack graph

with a large number of

attack paths

, it may not be feasible for the administrator to plug all the vulnerabilities. Moreover, in a dynamic environment where the severity of an

exploit

changes with time, a framework is required that detects an

optimal attack path

or

most favored path

from a given

attack graph

in an environment. This paper proposes a framework for finding out an

optimal attack path

using

Ant Colony Optimization (ACO)

technique under a dynamic environment. Given an

attack graph

and the severity scores of the

exploits

, an

optimal attack path

is detected using customized

ACO

algorithms. A case study has been presented to demonstrate the efficacy of the proposed methodology.

Nirnay Ghosh, Saurav Nanda, S. K. Ghosh

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!

Bildnachweise