Distributed Computing – IWDC 2005

Recently there have been a number of efforts to study issues related to coordination and control algorithms for systems of multiple autonomous mobile robots (also known as

robot swarms

) from the viewpoint of distributed computing. This paper reviews the literature in the area and discusses some open problems and future research directions.

This paper deals with compact label-based representations for trees. Consider an

n

-node undirected connected graph

G

with a predefined numbering on the ports of each node. The

all-ports

tree labeling

${\mathcal L}_{all}$

gives each node

v

of

G

a label containing the port numbers of all the

tree

edges incident to

v

. The

upward

tree labeling

${\mathcal L}_{up}$

labels each node

v

by the number of the port leading from

v

to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted

M

up

(

T

) and

S

up

(

T

) for

${\mathcal L}_{up}$

and

M

all

(

T

) and

S

all

(

T

) for

${\mathcal L}_{all}$

. The problem studied in this paper is the following: Given a graph

G

and a predefined port labeling for it, with the ports of each node

v

numbered by 0,...,deg(v) – 1, select a rooted spanning tree for

G

minimizing (one of) these measures. We show that the problem is polynomial for

M

up

(

T

),

S

up

(

T

) and

S

all

(

T

) but NP-hard for

M

all

(

T

) (even for 3-regular planar graphs). We show that for every graph

G

and port numbering there exists a spanning tree

T

for which

S

up

(

T

) =

O

(

n

log log

n

). We give a tight bound of

O

(

n

) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.

Ideal communication channels in asynchronous systems are reliable, deliver messages in FIFO order, and do not deliver spurious or duplicate messages. A message vocabulary of size two (i.e., single-bit messages) suffices to encode and transmit messages of arbitrary finite length over such channels. This note proves that single-bit messages are insufficient once channels potentially deliver duplicate messages. In particular, it is shown that no protocol allows the sender to notify the receiver which of three values it holds, over a bidirectional, reliable, FIFO channel that may duplicate messages. This implies that messages must encode some additional control information, e.g., in the form of headers or tags.

The fundamental question considered in this paper is when program

Q

, if executed immediately after program

P

, is guaranteed not to interfere with

P

and be safe from interference by

P

. If a message sent by one of these programs is received by the other, it may affect and modify the other’s execution. The notion of

communication closed layers (CCLs)

introduced by Elrad and Francez in 1982 is a useful tool for studying such interference. CCLs have been considered mainly in the context of reliable FIFO channels (without duplication), where one can design programs layers that do not interfere with any other layer. When channels are less than perfect such programs are no longer feasible. The absence of interference between layers becomes context-dependent. In this paper we study the impact of message duplication and loss on the safety on the safety of layer composition. Using a communication phase operator, the

fits after

relation among programs is defined. If program

Q

fits after

P

then

P

and

Q

will not interfere with each other in executions of

P

 ∗ 

Q

. For programs

P

and

Q

in a natural class of programs we outline efficient algorithms for the following: (1) deciding whether

Q

fits after

P

; (2) deciding whether

Q

seals

P

, meaning that

Q

fits after

P

and no following program can communicate with

P

; and (3) constructing a

separatorS

that both fits after

P

and satisfies that

Q

fits after

P

 ∗ 

S

.

Over the past decade, a pair of instructions called load-linked (LL) and store-conditional (SC) have emerged as the most suitable synchronization instructions for the design of lock-free algorithms. However, current architectures do not support these instructions; instead, they support either CAS (e.g., UltraSPARC, Itanium) or restricted versions of LL/SC (e.g., POWER4, MIPS, Alpha). To bridge this gap, a flurry of algorithms that implement LL/SC from CAS have appeared in the literature. Some of these algorithms assume that

N

, the maximum number of participating processes, is fixed and known in advance. Others make no such assumption, but are either non-blocking (not wait-free), implement small LL/SC objects, or require that a process performs

O

(

N

) work to join the algorithm. Specifically, no constant-time, word-sized, wait-free LL/SC algorithm that does not require the knowledge of

N

exists. In this paper, we present such an algorithm.

An important problem of mobile communication is placing a given number of base-stations in a given convex region, and to assign range to each of them such that every point in the region is covered by at least one base-station, and the maximum range assigned is minimized. The algorithm proposed in this paper uses Voronoi diagram, and it works for covering a convex region of arbitrary shape. Experimental results justify the efficiency of our algorithm and the quality of the solution produced.

Sensor networks are increasingly being used for applications which require fast processing of data, such as multimedia processing. Distributed computing can be used on a sensor network to reduce the completion time of a task and distribute the energy consumption equitably across all sensors. The distribution of task modules to sensors should consider not only the time and energy savings, but must also improve reliability of the entire task execution. We formulate the above as an optimization problem, and use the

A

*

algorithm with improvements to determine an optimal static allocation of modules among a set of sensors. We also suggest a faster but suboptimal algorithm, called the greedy

A

*

algorithm. Both algorithms have been simulated, and the results have been compared in terms of energy savings, decrease in completion time of the task, and the deviation of the sub-optimal solution from the optimal one. The sub-optimal solution required 8-35% less computation, at the cost of 2.5-15% deviation from the optimal solution in terms of average energy spent per sensor node. Both the

A

*

and greedy

A

*

algorithms have been shown to distribute energy consumption more uniformly across sensors than centralized execution. The greedy

A

*

algorithm is found to be scalable, as the number of evaluations in determining the allocation increases linearly with the number of sensors.

Authors in [1] have recently introduced an interesting model, COSMOS (Cluster-based heterOgeneouS MOdel for Sensor networks) for sensor networks; COSMOS is a hierarchical network architecture that consists of a large number of low cost sensors with very limited computation capability and a smaller number of more powerful “clusterheads”. The clusterheads can communicate between each other in an asynchronous fashion while the low capability sensors under each clusterhead operate in a synchronous way with their respective clusterheads. Our purpose in the present paper is to design several protocols for benchmark programs like broadcast, matrix multiplication and matrix chain multiplication using this model and provide detailed complexity analysis of these protocols. Our results further illustrates the usefulness of the model for use in sensor networks.

Data streams from sensors are usually characterized as continuous, with very frequent updates. Queries over those data streams need to be processed in near real-time. So it is needed to design the index structure for supporting the frequent updates and fast retrieval of data efficiently. In this paper, CLUR-Tree (Cache-conscious Lazy Update R-Tree) is proposed, which is a spatial index for efficient processing of frequent updates of data streams in locality preserving monitoring applications. CLUR-Tree has two characteristics. First, it excludes index reconstruction overhead by permitting modification of only the index node of the sensor which moves out of the corresponding MBR (Minimum Bound Rectangle). Second, it reduces the key spaces by applying new compression method for MBR used as key in R-Tree and by considering cache to prevent bottleneck due to speed difference between main memory and CPU. The experimental results indicate that the proposed CLUR-Tree enhances update performance and gives a good retrieval performance simultaneously.

This paper presents a new routing approach for wireless networks based on the combination of both lifetime and routing cost. As the nodes in the wireless sensor and ad hoc networks are limited in power, a power failure occurs if a node has insufficient remaining energy to send a message. So, it is important to minimize the energy expenditure as well as to balance the remaining battery power among the nodes. In ad hoc networks, movement of nodes also causes frequent disconnections of routes and thus effects on network stability. Cost effective routing algorithms attempt to minimize the total power needed while lifetime prediction routing algorithms try to balance the remaining energies among the nodes in the networks. However, because of ignoring other parameter, each method fails to achieve the objective of other. The proposed routing protocol suggests a tradeoff between these two parameters, and ensures a balanced utilization to achieve maximum overall performance.

Multipath source routing is an effective way to exploit the redundant routes that are usually common in dense sensor networks. In this paper, we present a multipath source routing algorithm that uses a ranking technique to distinguish between the quality of different routes for the same source-destination pair. A ranking coefficient is calculated for each route based on three different metrics- energy, delay and reliability. The number of parallel routes that is considered is governed by the minimum reliability requirements. Simulation experiments are conducted that show that multipath routing can increase the reliability, and dissipate energy more evenly among the nodes.

In this paper, we propose a reliable time synchronization protocol (RTSP) in sensor networks considering topology changes. Due to movement of sensor nodes, running out of energy or crashes in the network, the topology of sensor networks changes very frequently. In the proposed method, synchronization error is decreased by creating a hierarchical tree with lower depth and reliability is improved by maintaining and updating the information of candidate parent nodes. The RTSP reduces recovery time and cost compared to the TPSN (Timing–sync Protocol for Sensor Networks) when there are changes in topology. Simulation results show that RTSP has about 10% better performance than TPSN in synchronization accuracy. The number of messages in RTSP is 10%~30% lower than that in TPSN when there are topology changes.

This presentation covers a synthesizing overview of the structural organisation of the brain, viewed as a complex network. Such an organisation is encountered in social, information, technological, and biological networks. The underlying conclusions may, in future, lead to interesting studies in the areas of cognition, and distribution computing. It is also hoped that the brain network structure studied through scale-free, small world, and clustering concepts may facilitate better understanding and design of brain-computer interface (BCI) systems.

Checkpointing and rollback recovery are established techniques for handling failures in distributed systems. Under synchronous checkpointing, each process involved in the distributed computation takes checkpoint almost simultaneously. This causes contention for network stable storage and hence degrades performance. To overcome this problem, checkpoint staggering under which checkpoints by various processes are taken in a staggered manner, has been proposed. In this paper, we propose a staggered quasi-synchronous checkpointing algorithm which reduces contention for network stable storage without any synchronization overhead. We also present an asynchronous recovery algorithm based on the checkpointing algorithm.

In this paper, we develop a new self-stabilizing (fault tolerant) protocol for publish/subscribe scheme in a P2P network. We provide a complexity analysis of the recovery (stabilization) time of the protocol after arbitrary failures in the network. The protocol converges in at most

$n^{2}({\it \Delta}+1)m+n^{3} - n$

time in the worst case where

n

,

m

, and

${\it \Delta}$

denote respectively the number of nodes, edges, and the maximum degree of a node in the system graph (network). We also propose a a space efficient way to utilize this self-stabilizing publish/subscribe scheme, which allows flexibility in implementations.

If the variables used for a checkpointing algorithm have data faults, the algorithm may fail. In this paper, a self-stabilizing checkpointing algorithm is proposed for handling data faults in a ring network. The proposed algorithm can deal with concurrent initiations of checkpointing and at most one data fault per process. However, several processes may be faulty.

Since the Web started in 1990, it has shown an exponential growth. It is essential that the Web’s scalability and performance keep up with increased demand and expectations. The key to achieving these goals of scalability, robustness and responsiveness lies in the practices of caching and replication. Quorum Consensus is a popular protocol used for data replication. This paper describes an implementation of two special cases of Quorum Consensus protocol, namely Majority Voting and Read-One-Write-All (ROWA) and compares their performance. The performance evaluation was done using a number of systems located at PlanetLab member institutions at different locations over the world. This enabled simulation of real world Internet conditions. The study shows that the ROWA protocol performs better than the Majority Voting under no-site-failure conditions in terms of response time, communication overhead and growing number of users.

This paper proposes a novel method for achieving a distributed self-refined fault tolerance by dynamically partitioning the processes into smaller groups, which are mutually disjoint and collectively exhaustive of the whole system. The present model provides tolerance for frequent faults, makes the roll back recovery simple and less time consuming. An optimal checkpoint interval is found using a mathematical approximation and a spare process is made to capture all the in-transit messages when a process fails at its ends. Piggybacking the events of dependent processes on the outgoing messages is used for process grouping. A process with maximum information can scatter chunk values to the other dependent processes in its group. Each process constructs a checkpoint when the received chunk matches with its log.

The impact of different routing and wavelength assignment algorithms on the in-band crosstalk performance of a 4 x 4 mesh-torus and a 15-node network has been studied. This paper considers both switch-induced crosstalk and the crosstalk induced by the multiplexers and demultiplexers. Fixed routing and fixed-alternate routing of connection requests have been considered. First-fit and random wavelength assignment algorithms have been employed. A crosstalk-aware wavelength assignment has also been considered. In-band crosstalk leads to poor received signal quality at the destination node. This results in increased receiver bit error rate (BER). This implies that some of the routes will deliver a signal quality which is unsatisfactory. To ensure that no resources are wasted on those connections which cannot deliver an unacceptable signal quality, this paper uses an event-driven simulation which incorporates on-line BER calculations. A call request is accepted only if the BER at the destination node is less than 10

− 12

; otherwise it is rejected.

This paper studies a series of reconfiguration processes corresponding to a series of traffic demand changes in a WDM (Wavelength Division Multiplexing) optical network. The proposed reconfiguration framework consists of two objective functions, a reconfiguration process, and a reconfiguration policy. The two objective functions are AHT (objective function of minimizing Average Hop distance of Traffic) and NLC (objective function of minimizing Number of Lightpath routing Changes). The reconfiguration process finds a set of non-dominated solutions using the PEAP (Pareto Evolutionary Algorithm adapting the Penalty method) that optimizes two objective functions by using the concept of Pareto optimality. The reconfiguration policy picks a solution from the set of non-dominated solutions using the MDA (Markov Decision Action). Experimental results show that our reconfiguration framework incorporating the PEAP and the MDA yields efficient performance in the entire series of reconfiguration processes.

In this paper, we have suggested a novel way to implement the interconnections in the Multi-Mesh (MM) network using optical devices. In a traditional, copper-based approach, the long connections between processors in an interconnection network create major limitations with respect to the speed of communication. Our approach for inter-block communication in a MM uses optical communication using Wavelength Division Multiplexing (WDM). Rather than passive stars or free-space optics, used to implement some recent optoelectronic communication schemes for interconnection networks, this design uses wavelength routed fiber-based networks.

There has been considerable research interest in the use of path protection techniques for the design of survivable WDM networks. In this paper, we present a distributed algorithm for dynamic lightpath allocation, using both dedicated and shared path protection. The objective is to minimize the amount of resources (wavelength-links) needed to accommodate the new connection. We have tested our algorithms on a number of well-known networks and compared their performance to “optimal” solutions generated by ILPs. Experimental results show that our algorithm generates solutions that are comparable to the optimal, but are significantly faster and more scalable than corresponding ILP formulations.

Optical splitting capability at some nodes is necessary to get efficient multicast routing in the wavelength routed wavelength division multiplexing (WDM) networks. There is a growing interest in efficiently protecting multicast sessions against the failure of network components. We propose algorithms for protecting multicast sessions against failure of network components such as links and nodes in a network with sparse splitting and sparse wavelength conversion. The effectiveness of the proposed algorithms is verified through extensive simulation experiments.

Peer-to-peer systems and applications are distributed systems without any centralized control. P2P systems form the basis of several applications, such as file sharing systems and event notification services. P2P systems based on Distributed Hash Table (DHT) such as CAN, Chord, Pastry and Tapestry, use uniform hash functions to ensure load balance in the participant nodes. But their evenly distributed behaviour in the virtual space destroys the locality between participant nodes. The topology-based hierarchical overlay networks like Grapes and Jelly, exploit the physical distance information among the nodes to construct a two-layered hierarchy. This highly improves the locality property, but disturbs the concept of decentralization as the leaders in the top layer get accessed very frequently, becoming a performance bottleneck and resulting in a single point of failure. In this paper, we propose an enhanced m-way search tree (EMST) based P2P overlay infrastructure, called Oasis. It is shown through simulation that Oasis can achieve both the decentralization and locality properties along with high fault tolerance and a logarithmic data lookup time.

Gnutella’s notoriously poor scaling led some to propose distributed hash table solutions to the wide-area file search problem. Contrary to that trend, in this paper, we advocate retaining Gnutella’s simplicity while proposing

GToS

, a

G

nutella-like

T

opology-

o

riented

S

earch protocol for high-performance distributed file sharing, by examining the role of overlay topology on system performance improvement. Building upon prior research [10], we propose several modifications as enhancements and then refine these novel ideas, with the aim of trying to remedy the “mismatch” between the logical overlay topology and its projection on the underlying network. We test our design through extensive simulations and the results show a significant system performance improvement.

Partitioning is one of the main problems in p2p group membership. This problem rises when failures and dynamics of peer participation, or churn, occur in the overlay topology created by a group membership protocol connecting the group of peers. Solutions based on Gossip-based Group Membership (GGM) cope well with the failures while suffer from network dynamics. This paper shows a performance evaluation of SCAMP, one of the most interesting GGM protocol. The analysis points out that the probability of partitioning of the overlay topology created by SCAMP increases with the churn rate. We also compare SCAMP with DET – another membership protocol that deterministically avoids partitions of the overlay. The comparison points out an interesting trade-off between (i) reliability, in terms of guaranteeing overlay connectivity at any churn rate, and (ii) scalability in terms of creating scalable overlay topologies where latencies experienced by a peer during join and leave operations do not increase linearly with the number of peers in the group.

Peer-to-peer (P2P) overlay networks, such as CAN, Chord, Pastry and Tapestry, lead to high latency and low efficiency because they are independent of underlying physical networks. A well-routed lookup path in an overlay network with a small number of logical hops can result in a long delay and excessive traffic due to undesirably long distances in some physical links. In these DHT-based P2P systems, each data item is associated with a key and the key/value pair is stored in the node to which the key maps, not considering the data semantic. In this paper, we propose an effective P2P routing algorithm, called Uinta, to adaptively construct a structured P2P overlay network. Uinta not only takes advantages of physical characteristics of the network, but also places data belonging to the same semantic into a cluster and employs a class cache scheme to reduce the lookup routing latency. Simulations make some comparisons between Chord and our Uinta algorithm all running on the GT-ITM transit stub topology. The results show Uinta routing algorithm significantly improves P2P system lookup performance.

We present a new approach to find a collision-free transmission schedule for mobile ad hoc networks (MANETs) in a TDM environment. A hexagonal cellular structure is overlaid on the MANET and then the actual demand for the number of slots in each cell is found out. We assume a 2-cell buffering in which the interference among different mobile nodes do not extend beyond cells more than distance 2 apart. Based on the instantaneous cell demands, we propose optimal slot assignment schemes for both homogeneous (all cells have the same demand) and non-homogeneous cell demands by a clever reuse of the time slots, without causing any interference. The proposed algorithms exploit the hexagonal symmetry of the cells requiring

O

(log log

m

 + 

mD

 + 

n

) time, where

m

is the number of mobile nodes in the ad hoc network,

n

and

D

being the number of cells and diameter of the cellular graph.

Ad Hoc LAN systems are noncooperative MAC settings where regular stations are prone to "bandwidth stealing" by greedy ones. The paper formulates a minimum-information model of a LAN populated by mutually impenetrable groups. A framework for a noncooperative setting and suitable MAC protocol is proposed, introducing the notions of verifiability, feedback compatibility and incentive compatibility. For Random Token MAC protocols based on voluntary deferment of packet transmissions, a family of winner policies called RT/ECD-

Z

is presented that guarantees regular stations a close-to-fair bandwidth share under heavy load. The proposed policies make it hard for greedy stations to select short deferments, therefore they resort to smarter strategies, and the winner policy should leave the regular stations the possibility of adopting a regular strategy that holds its own against any greedy strategy. We have formalized this idea by requiring evolutionary stability and high guaranteed regular bandwidth shares within a set of heuristic strategies.

This paper addresses the problem of power aware data routing strategies within ad hoc networks using directional antennas. Conventional routing strategies usually focus on minimizing the number of hops or route errors for transmission but they do not usually focus on the energy depletion of the nodes. In our proposal, if a node in the network has depleted its battery power, then an alternative node would be selected for routing so that not only the power is used optimally but there is an automatic load sharing or balancing among the nodes in the network. The usage of directional antenna in this scheme has some key advantages outperforming the omni-directional counterpart. The space division multiple access, range extension capabilities and power requirement of the directional antenna is itself a reason for its choice. We illustrate how directional antenna can be combined with the power aware routing strategy and using simulations, we quantify the energy benefits and protocol scalability.

In Ad Hoc networks a routing protocol is either proactive or reactive. The former maintains consistent up-to-date routing information from each node to every other node in the network, whereas the latter creates route to the destination only when desired by the source node using “flooding”. In flooding packets are broadcast to all destinations with the expectation that they eventually reach their intended destination. This proves to be very costly in terms of the throughput efficiency and power consumption. For reactive protocols, researchers have tried to enhance the throughput efficiency and reduce power consumption using techniques that cut down flooding. In this paper we propose a routing protocol called Power Aware Cluster Efficient Routing (PACER) protocol for multi-hop wireless networks. In PACER, the network is dynamically organized into partitions called clusters with the objective of maintaining a relatively stable effective topology. The protocol uses the Weight Based Adaptive Clustering Algorithm (WBACA), developed by us for cluster formations. The main objective is to significantly reduce the number of overhead messages and the packet transfer delay. We demonstrate the efficiency of the proposed protocol with respect to average end-to-end delay, control overheads, throughput efficiency and the number of nodes involved in routing.

Most of the proposed algorithms in ad hoc networks assume homogeneous nodes with similar transmission range and capabilities. However, in heterogeneous ad hoc networks, it is not necessary that all nodes have bidirectional link with each other and hence, those algorithms may not perform well while deployed in real situations. In this paper, we propose a scheme for an ad hoc on-demand routing protocol which utilizes the unidirectional links during the data transmission. Simulation shows that it is not only possible to use unidirectional links but it is also better in terms of performance metrics we defined in different situations.

Columbia is a 10,240-processor supercomputer consisting of 20 Altix nodes with 512 processors each, and currently ranked as one of the fastest in the world. In this paper, we briefly describe the Columbia system and its supporting infrastructure, the underlying Altix architecture, and benchmark performance on up to four nodes interconnected via the InfiniBand and NUMAlink4 communication fabrics. Additionally, three science and engineering applications from different disciplines running on multiple Columbia nodes are described and their performance results are presented. Overall, our results show promise for multi-node application scaling, allowing the ability to tackle compute-intensive scientific problems not previously solvable on available supercomputers.

For a connected graph, representing a sensor network, distributed algorithms for the Set Covering Problem can be employed to construct reasonably small subsets of the nodes, called

k

-SPR sets. Such a set can serve as a virtual backbone to facilitate shortest path routing, as introduced in [4] and [14]. When employed in a hierarchical fashion, together with a hybrid (partly proactive, partly reactive) strategy, the

k

-SPR set methods become highly scalable, resulting in guaranteed minimal path routing, with comparatively little overhead.

Energy efficient self-organization is a crucial method to prolong the lifetime of wireless sensor networks consisting of energy constrained sensor nodes. In this paper, we focus on a distributed node scheduling scheme to extend network lifespan. We discuss the network coverage performance when sensor nodes are deployed according to Poisson point process and reveal the internal relationship among the required coverage performance, expected network lifetime and the intensity of Poisson point process. Also the impact of uniformly distributed time asynchrony on network coverage performance is analyzed. Simulation results demonstrate that the proposed scheme works well in the presence of time asynchrony.

Key pre-distribution is an important area of research in Distributed Sensor Networks (DSN). Two sensor nodes are considered connected for secure communication if they share one or more common secret key(s). It is important to analyze the largest subset of nodes in a DSN where each node is connected to every other node in that subset (i.e., the largest clique). This parameter (largest clique size) is important in terms of resiliency and capability towards efficient distributed computing in a DSN. In this paper, we concentrate on the schemes where the key pre-distribution strategies are based on transversal design and study the largest clique sizes. We show that merging of blocks to construct a node provides larger clique sizes than considering a block itself as a node in a transversal design.

In this paper, we propose a stochastic rate control method to provide seamless video streaming for vertical handoff between WLAN and 3G cellular network. In the proposed method, we first estimate the channel rate by using the state transition probabilities that can be found from the relationship between the packet loss ratio (PLR) and the medium access control (MAC) layer parameters. The proposed method performs bit allocation at the frame level using the estimated channel rate, minimizing the average distortion over an entire sequence as well as variations in distortion between frames. Experimental results indicate that the proposed method provides better visual quality than the existing TMN8 rate control method in heterogeneous wireless network.

An efficient deployment of a mobile Ad Hoc network (MANET) requires a realistic approach towards the mobility of the hosts who want to communicate with each other over a wireless channel. Since Ad Hoc networks are driven by the human requirements, instead of considering the random movement of the mobile nodes, we concentrate on the social desire of the nodes for getting connected with one another and provide here a framework for the mobility model of the nodes based on Social Network Theory. In this paper, we capture the preferences in choosing destinations of pedestrian mobility pattern on the basis of social factor (

ψ

F

) and try to find out the essential impact of

ψ

F

on the pause time of the nodes. Further, our paper also provides a mobility distribution pattern, and a relative comparison has been done with Random Way- Point (RWP) Model under a certain constrained simulation.

This paper proposes and analyzes the performance of an efficient error control scheme for time sensitive applications on wireless sensor networks. The proposed scheme divides DCF into HDCF and LDCF without changing PCF, aiming at maximizing the successful retransmission of a packet that carries critical data. While channel estimation obviates the unnecessary polls to the node in channel error during PCF, two level DCF enables prioritized error recovery by making only the high priority packet be retransmitted via HDCF. A good chop value can distribute the retransmission to each period, maximizing recovered weight, or criticality as well as keeping low the possible loss of network throughput. The simulation results show that the proposed scheme can improve recovered weight by 8% while showing 97% successful transmission at maximum for the given simulation parameter.

Location area (LA) planning in PCSN is a NP-hard problem. In this paper we modeled it as a clustering problem where each LA is considered to be a cluster. Agglomerative Hierarchical Algorithm (AHA) is applied to form the cell clusters. The algorithm starts assuming each cell as a separate cluster. In successive iterations the clusters are merged randomly in a bottom up fashion based on a total cost function (TCF) till the desired numbers of clusters are obtained. Total Cost Evaluation Metric (TCEM) is proposedto compare AHA with other schemes. Experimental results show that AHA provides better results in most of the cases compared to Greedy Heuristic based approach.

Two Internet-based frameworks, IntServ and Differentiated DiffServ, have been proposed to support service guarantees in the Internet. Both frameworks focus on packet scheduling; as such, they decouple routing from QoS provisioning. This typically results in inefficient routes, thereby limiting the ability of the network to support QoS requirements and to manage resources efficiently. To address this shortcoming, we propose a scalable QoS routing framework to identify and select paths that are very likely to meet the QoS requirements of the underlying applications. Scalability is achieved using selective probing and clustering to reduce signaling and routers overhead. A thorough study to evaluate the performance of the proposed

d

-median clustering algorithm is conducted. The results of the study show that for power-law graphs the

d

-median clustering based approach outperforms the set covering method. The results of the study also show that the proposed clustering method, applied to power-law graphs, is robust to changes in size and delay distribution of the network. Finally, the results suggest that the

delay bound

input parameter of the

d

-median scheme should be no less than 1 and no more than 4 times of the average delay per one hop of the network. This is mostly due to the weak hierarchy of the Internet resulting from its power-law structure and the prevalence of the small-world property.

In this paper we present a fair and reliable e-commerce model for P2P network, in which communication parties can buy and sell products by P2P contact. In particular, we focus on a fair exchange protocol that is based on collaboration with distributed communication parties and distinguished from the traditional fair exchange protocols based on a central trusted authority. This feature makes our model very attractive in P2P networking environment which does not depend on any central trusted authority for managing communication parties.

For a secure highly distributed computing environment, we suggest an efficient role based access control using attribute certificate. It reduces management cost and overhead incurred when we change the specification of the role. In this paper, we grouped roles and structured them into the role group relation tree. It results in secure and efficient role updating and distribution. For scalable role specification certificate distribution, multicasting packets are used. We take into account the packet loss and quantify performance enhancements of structuring role specification certificates.

A multisignature scheme for implementing safe delivery rule in group communication systems (MSGC) was recently proposed by Rahul and Hansdah. In this paper we show that the MSGC scheme is insecure against forgery attack and signature integrity attack. We propose an improved scheme that resists the weaknesses of MSGC scheme.

In this paper we propose an improved alternative for the path key establishment phase of bootstrapping in a sensor network. Our scheme lets the network adapt to the deployment configuration by secure transmission of predistributed keys. This results in better connectivity than what path key establishment can yield. The communication overhead for our scheme is comparable with that for path key establishment. Moreover, the assurance of good connectivity allows one to start with bigger key pools, thereby improving resilience against node capture.

Recently, Wu and Hsu showed that Lee and Chang’s anonymous user identification and key establishment protocol was insecure with regard to two attacks and proposed an improved protocol, called the WH protocol. In this paper, we show that the WH protocol is still vulnerable to an unknown-key share attack. Then, we propose an improved protocol to address this problem by applying a mutual authentication method.

Service routing across different MPLS and access networks domains is a critical issue in next generation networks. In spite of being a de facto inter domain routing standard, BGP can not fulfill the inter domain traffic engineering needs and it does not take into account service metrics, which results in the low routing efficiency of BGP. We set up a system model by decomposing the problem. Based on the model, we set up a service network reduction algorithm. At the initial stage we use a grid service instance to map service paths of different MPLS domains, then we construct service network graph, and set up index for service routing based on ontology. At the last stage, we get a single service metric to set up service routing by applying the service ontology metric function.

Effective task scheduling is crucial for achieving good performance in high performance computing. Many scheduling algorithms have been devised for heterogeneous computing, but most of algorithms have not been considered in realistic heterogeneous environments which are not arbitrarily heterogeneous but have locality in communication. In this paper we present new scheduling algorithms by considering the locality. It is thought that critical-path tasks are often important in reducing schedule length, however one of the previous scheduling algorithms, CPOP (Critical-Path-On-a-Processor) does not show good result against to expectation. Our first heuristic uses a cluster of processors for critical-path tasks while a single processor is used in the CPOP. This heuristic well exploits realistic computing environments in which communication costs are not arbitrarily heterogeneous. In an additional heuristic the critical-path tasks are considered to finish (or start) as early as possible when even non critical-path tasks are scheduled. For a performance study five scheduling algorithms are compared by experimenting on three different environments. The experimental results show our scheduling algorithm outperforms the others in the realistic heterogeneous environments.

Current TCP congestion control can be inefficient and unstable in high-speed wide area networks due to its slow response with a large congestion window. Several congestion control proposals have already been suggested to solve these problems and two properties have been considered: TCP friendliness and scalability, to ensure that a protocol does not take away too much bandwidth from TCP, while utilizing a bandwidth of high speed networks efficiently. In this paper, we propose a new variant of TCP for a high-speed network which combines delay-based congestion control with loss-based congestion control. Our simulation results show that proposed scheme performs better than the existing high-speed TCP protocols in terms of fairness, stability and scalability, while providing friendliness at the same time.

Research in embedded networked sensing has primarily focused on the design of hardware architectures for sensor nodes and infrastructure protocols for long lived operation of resource constrained sensor network deployments. There is now an increasing interest in the programming aspects of sensor networks, especially in the broader context of pervasive computing. This paper provides a brief overview of ongoing research in programming of sensor networks and classifies it into layers of abstraction that provide the application developer with progressively higher level primitives to express distributed, phenomenon-centric collaborative computation. As a specific instance of a macroprogramming methodology, we discuss the data driven Abstract Task Graph (ATaG) model and the structure of its underlying runtime system. ATaG separates the application functionality from non-functional aspects, thereby enabling end-to-end architecture-independent programming and automatic software synthesis for a class of networked sensor systems. A prototype visual programming, software synthesis, functional simulation and visualization environment for ATaG has been implemented.

The revoke mechanism in generalized relaxed distributed mutual exclusion algorithm GRME [1] for eliminating a potential deadlock can cause extensive unnecessary revoke actions by the nodes which fail to receive the required granted-replies to their resource requests within a certain predefined time limit. It may happen that there is actually no deadlock present or that only a few nodes need to revoke some of their resource requests to eliminate the deadlock. We show that if the interference graph

G

is triangle-free (no three nodes are mutually adjacent), then we can choose the request-sets R

i

in GRME in such a way that deadlocks are prevented altogether and there is no need to use revoke-messages, while keeping the resource-use decisions fully distributed and allowing non-interfering nodes to use the resource simultaneously.

In this paper a fault tolerant routing algorithm for unicasting on star graph is proposed. The routing algorithm does not involve back tracking and uses

fault-vectors

. Each node in an

n

-star has a fault-vector of

$\lfloor\frac{3(n-1)}{2}\rfloor$

bits. The

k

th bit of a node’s fault-vector is a measure of its routing ability to nodes which are at distance

k

from itself. The fault-vector of each node can easily be calculated through

$\lfloor\frac{3(n-1)}{2}\rfloor$

rounds of information exchanges among neighbor nodes. For a given source destination pair (

u

,

v

), the routing algorithm finds a path of length

d

+

h

where

d

is the length of the shortest path between

u

and

v

in a fault-free star graph and

h

= 0, 2 or 4. The space requirement for storing the fault vector is

O

(

n

) in each node. Simulation results show that the proposed algorithm far outperforms the routing algorithm based on

safety vectors

[13].

Concurrency control algorithms for real-time database systems satisfy not only consistency requirements but also meet transaction-timing constraints. Two Phase Locking (2PL) is used often in traditional database systems. However, it has some inherent problems such as the possibility of deadlocks as well as long and unpredictable blocking times. Optimistic concurrency control protocols are non-blocking and deadlock free, but they have the problems of late conflict detection and transaction restarts. Other Concurrency Control techniques, such as Dynamic Adjustment of Serialization Order (DASO) have been found to be better at reducing number of transaction restarts. In this paper, we propose a new optimistic concurrency control algorithm based on DASO using firm deadline in order to effectively reduce number of unnecessary restarts. Since firm real time transaction imparts no value to the system once its deadline expires, therefore in our algorithm, we adjust the timestamp intervals of all conflicting active transactions only after the validating transaction is guaranteed to meet its deadline during the validation phase. A simulator is designed to verify the effectiveness of the proposed method. The simulation results show that the proposed method can significantly reduce the number of unnecessary restarts and thereby improve the miss ratio, commit ratio.

This study deals with the VOD system having limited number of channels and servicing of requests for mixed movies of different durations and popularity. The performance measures such as channel utilization, number of channels in use, blocking probability of channels, etc. are quantified in terms of various design parameters like, total number of channels, users request arrival rate, batching interval and request service rate etc.

Most of the past researches [1], [2], [3] investigate the behavior of distributed real time commit protocols either under update or blind write model. The effect of both types of models has not been investigated collectively. These protocols also require a considerable amount of memory for maintaining temporary objects (data structure) created during execution of transactions and block the WORKDONE message if cohort is dependent. This paper presents an optimized distributed real time commit protocol (MEFCP) based on new locking scheme and write operation divided into update and blind write. The proposed protocol optimizes the memory required for maintaining the transient information of lender & borrower [1]. It also sends the WORKDONE message if borrower has locked the data in mode 2 only. We also compared MEFCP with PROMPT and 2SC commit protocols through simulation.

In this paper we approach the solution of large instances of the distribution design problem. Traditional approaches do not consider that the size of the instances can significantly affect the efficiency of the solution process. This paper shows the feasibility to solve large scale instances of the distribution design problem by compressing the instance to be solved. The goal of the compression is to obtain a reduction in the amount of resources needed to solve the original instance, without significantly reducing the quality of its solution. In order to preserve the solution quality, the compression summarizes the access pattern of the original instance using clustering techniques. In order to validate the approach we tested it on a new model of the replicated version of the distribution design problem that incorporates generalized database objects. The experimental results show that our approach permits to reduce the computational resources needed for solving large instances, using an efficient clustering algorithm. We present experimental evidence of the clustering efficiency of the algorithm.

This paper presents a new location management scheme that integrates two key ideas, namely, (i) Subscriber Movement Profile (SMP) based on spatial and temporal locality of the movement of a mobile terminal and (ii) localized updates known as Time-bound Self Purging Indicators (TSPI) generated by a probabilistic approach when a mobile terminal does not adhere to registered profile. The SMP registered by a mobile host is used to predict its cell location based on time specific movement history. The transient deviations from the registered SMP are handled efficiently by TSPIs using a Regional Route Map (RRM).

The next generation wireless communication devices are expected to be capable of communicating with the best possible network as well as to utilize multiple networks, simultaneously. Existing solutions such as the interoperability mechanisms and the Always Best Connected (ABC) paradigm limit the access of wireless devices to only one, preferably the best possible network. Such schemes, though found to be better than the traditional single interface communication, are limited in their ability to utilize the services in the best possible way. Existing work focuses mainly on network layer or transport layer bandwidth aggregation mechanisms which either need to change the existing TCP protocol or require proxy nodes to perform the bandwidth scheduling process. We, in this paper, propose a new wireless access paradigm for multi-homed hosts based on a session layer bandwidth aggregation mechanism. The major advantages of our solution are the high end-to-end throughput, glitch free transition during both mobility and interface changes, dynamic selection of number of end-to-end paths, and above all our solution can work with existing transport and network layer protocols in today’s Internet. In this paper, we provide the architectural and protocol solutions for the proposed scheme and results from extensive simulations and a Linux based implementation.

Caching has been widely used to improve system performance in wireless mobile environment. Mobility management is a key component in allowing a client to maintain normal communication with the server while on the move, independent of its location. A cache invalidation strategy ensures that any cached item by a client has same value as on the origin server. Mobility of clients makes the cache maintenance task more complex. This paper extends our previous caching strategy in a wireless environment to handle inter-cell clients’ mobility. Experiments are performed to evaluate the proposed strategy and compare the results with other existing strategies.

In this paper, we analyze the performance of hierarchical multicast protocol in IP micro mobility networks. The most important parameters to provide multicast service in IP micro mobility networks are the connection recovery time and the reconstruction cost of multicast tree according to the host mobility. So we derive the average connection recovery time and total tree reconstruction cost due to the handoff of mobile hosts by considering the hierarchical structure of IP micro mobility networks. We also verify the analytical results by simulation.

Passive clustering does not employ control packets to collect topological information in ad hoc networks. In our proposal, we avoid making frequent changes in cluster architecture due to repeated election and re-election of cluster heads and gateways. Our primary objective has been to make Passive Clustering more practical by employing optimal number of gateways and reduce the number of rebroadcast packets.

The wide availability of mobile devices together with the technical possibility to form ad-hoc networks paves the way for building highly dynamic communicating communities of mobile users. A challenge is how to deliver messages in such networks incurring least routing overhead. Cooperative routing is a mobile-agent assisted team approach, which utilizes a set of fixed cluster head nodes to provide proper coordination and cooperation for exchanges and sharing of messages in the team. Our routing strategy aims at reducing routing overheads, message traffic and unnecessary random node visits in the network for delivering data. The main benefit provided by cooperative routing is considerable network traffic reduction at high load. We highlight the main components of the system and discuss the agent life cycle in detail together with the parameters and strategies governing the migration of agents, their merging and termination.

This paper proposes an efficient network mobility management scheme for mobile networks such as trains and buses moving on the predetermined path. In this scheme, each mobile router maintains a database about the list of access routers, their network prefixes, and cell radii on the moving path. The mobile router therefore knows in advance network prefixes and its care-of addresses of all subnets without beacon signals. Using this database and current location information, the mobile router can prepare network layer hand-over with predictive binding update before link layer handover occurs, thereby the service disruption time due to handover will be reduced to the link layer handover latency.

We identify a type of distributed system where the notion of space in planning is important. We give a formal modeling of the distributed system where planning is done. We show that several interesting planning goals in the model can be specified in a spatio-temporal logic STL. We develop an efficient planning procedure for these goals in the distributed setting.

We study the problem of distributed, self-interested agents searching for high-quality service providers where the performance of a service provider depends on its work load. Agents use referrals from peers to locate satisfactory providers. While stable environments may facilitate fast convergence to satisfying states, greedy and myopic behaviors by distributed agents can lead to poor and variable performances for the entire community. We present mechanisms for resource discovery that involve learning, over interactions, both the performance levels of different service providers as well as the quality of referrals provided by other agents. We study parameters controlling system performance to better comprehend the reasons behind the observed performances of the proposed coordination schemes.

Distributed methodologies to find pareto-optimal frontier with concern to privacy, of objectives and constraints, of parties is of interest in scenarios like negotiations. Adaptation of lagrangian method to solve distributed weighting method for both strictly concave and not strictly concave (e.g. linear) value functions is proposed for a maximization problem.