A CRITICAL IMPROVEMENT ON OPEN SHOP SCHEDULING ALGORITHM FOR ROUTING IN INTERCONNECTION NETWORKS

 Stavros Birmpilis and Timotheos Aslanidis 

National Technical University of Athens, Athens, Greece 

ABSTRACT 

In the past years, Interconnection Networks have been used quite often and especially in applications where parallelization is critical. Message packets transmitted through such networks can be interrupted using buffers in order to maximize network usage and minimize the time required for all messages to reach their destination. However, preempting a packet will result in topology reconfiguration and consequently in time cost. The problem of scheduling message packets through such a network is referred to as PBS and is known to be NP-Hard. In this paper we haveimproved, critically, variations of polynomially solvable instances of Open Shop to approximate PBS. We have combined these variations and called the induced algorithmI_HSA (Improved Hybridic Scheduling Algorithm). We ran experiments to establish the efficiency of I_HSA and found that in all datasets used it produces schedules very close to the optimal. In addition, we tested I_HSA with datasets that follow non-uniform distributions and provided statistical data which illustrates better its performance.To further establish I_HSA’s efficiency we ran tests to compare it to SGA, another algorithm which when tested in the past has yielded excellent results. 

KEYWORDS 

Interconnection networks, packet scheduling, preemption, approximation

More Details........ 

TRUST BASED CLUSTERING AND SECURE ROUTING SCHEME FOR MOBILE AD HOC NETWORKS

 Pushpita Chatterjee

 School of Information Technology Indian Institute of Technology, 

Kharagpur, India 

 ABSTRACT 

In this paper we present a distributed self-organizing trust based clustering framework for securing ad hoc networks. The mobile nodes are vulnerable to security attacks, so ensuring the security of the network is essential. To enhance security, it is important to evaluate the trustworthiness of nodes without depending on central authorities. In our proposal the evidence of trustworthiness is captured in an efficient manner and from broader perspectives including direct interactions with neighbors, observing interactions of neighbors and through recommendations. Our prediction scheme uses a trust evaluation algorithm at each node to calculate the direct trust rating normalized as a fuzzy value between zero and one. The evidence theory of Dempster-Shafer [7], [8] used in order to combine the evidences collected by a clusterhead itself and the recommendations from other neighbor nodes. Moreover, in our scheme we do not restrict to a single gateway node for inter cluster routing. 

Keywords:

Ad hoc networks, Trust, Cluster, Security, Distributed Leader Election


More Details.............

Pollution in P2P Live Video Streaming

 Prithula Dhungel1 , Xiaojun Hei2 , Keith W. Ross1 and Nitesh Saxena1 

1Department of Computer Science and Engineering Polytechnic Institute of New York University  2Department of Electronics and Information Engineering Huazhong University of Science and Technology

 Abstract 

P2P mesh-pull live video streaming applications – such as CoolStreaming, PPLive, and PPStream – have become popular in the recent years. In this paper, we examine the stream pollution attack, for which the attacker mixes polluted chunks into the P2P distribution, degrading the quality of the rendered media at the receivers. Polluted chunks received by an unsuspecting peer not only effect that single peer, but since the peer also forwards chunks to other peers, and those peers in turn forward chunks to more peers, the polluted content can potentially spread through much of the P2P network. The contribution of this paper is twofold. First, by way of experimenting and measuring a popular P2P live video streaming system, we demonstrate that the pollution attack can be devastating. Second, we evaluate the applicability of four possible defenses to the pollution attack: blacklisting, traffic encryption, hash verification, and chunk signing. Among these, we conclude that the chunk signing solutions are most suitable. 

More details...

Congestion Propagation among Routers with TCP Flows

Hiroyuki Ohsaki, Kouhei Sugiyama, and Makoto Imase 

Graduate School of Information Science and Technology, Osaka University, Japan 

Abstract 

In recent years, various non-linear phenomena of the Internet have been discovered. For instance, it is reported that congestion of a router propagates to neighboring routers like a wave. Several researches on congestion propagation among routers have been performed. However, in these researches, cause of congestion propagation and condition that congestion propagation occurs have not been sufficiently investigated. In this paper, we reveal a cause of congestion propagation, and also investigate under what conditions congestion propagation is observed. Consequently, we show that speed of congestion propagation is affected by the bandwidth and the propagation delay of links, and that periodicity of congestion propagation becomes less obvious as randomness of network traffic increases. 

Keywords 

Congestion Propagation, TCP (Transmission Control Protocol), Router, Nonlinear Phenomena, Ring Network 

More Details.......

Hop-by-Hop TCP for Sensor Networks

 Yao-Nan Lien 

Computer Science Department, National Chengchi University, Taipei, Taiwan, R.O.C. 

 Abstract 

Communication links in a sensor network are unstable such that running conventional TCP protocol over a high loss rate sensor networks will suffer from severe performance degradation. To handle a packet loss, conventional TCP retransmits the lost packet from its source. However, when error rate is high, it may have difficulty to deliver a packet to its destination. Considering that most applications on a sensor network prefer faster and reliable packet delivery to higher throughput, this paper proposes to use the Hop-byHop TCP protocol for sensor networks aiming to accelerate reliable packet delivery. Hop-by-Hop TCP makes every intermediate node in the transmission path execute a light-weight local TCP to guarantee the transmission of each packet on each link. It takes less time in average to deliver a packet in an error-prone environment. The performance of our approach is evaluated by simulation using NS-2 simulator. Our experiments show that Hop-by-Hop TCP outperforms TCP NewReno in both throughput and average packet delivery time. The fairness requirement is also achieved while Hop-by-Hop TCP coexists with other major TCP variants. 

Keywords: 

Sensor Network, TCP

SOLS: Self Organising Distributed Location Server for Wireless Ad Hoc Networks

Gareth Owen  and Mo Adda 

 1) Computing Laboratory, University of Kent, Canterbury, CT2 7NZ, UK. 

 2) School of Computing, University of Portsmouth, Buckingham Building, Lion Terrace, Portsmouth, PO1 3HE, UK.

 Abstract 

Ad hoc networks allow wireless devices to form a network without any pre-existing knowledge of configuration or topology. Large-scale networks consist of hundreds or more nodes and are unable to use traditional broadcast routing algorithms due to lack of scalability. Geographic algorithms use nodes' geographical locations to route traffic without topology knowledge, but still require knowledge of the destination node's location. This location is often provided up by location service protocols although many of these too use broadcast schemes which limit their scalability. This work describes a location server that uses self-organising behaviour that is often seen in nature to minimise transmission overhead and maximize scalability. The approach outperforms existing solutions by significant margins. 

KEYWORDS 

Geographical routing, Location server, quorum systems, wireless LAN.

More details................

Mobile Ad-Hoc Network Based Relaying Data System for Oceanic Flight Routes in Aeronautical Communications

Ho Dac Tu and Shigeru Shimamoto 

Graduate School of Global Information and Telecommunication Studies Waseda University 29-7 building, 1-3-10 Nishi-Waseda, Shinjuku-ku, Tokyo 169-0051 Japan 

ABSTRACT 

This paper proposes a reliable system to overcome the weakness of current the HF radio communication system for oceanic aeronautical flight routes. This system uses only one aeronautical VHF channel with air-toair radio relay system based on local mobile Ad-hoc networks. For access to/from all aircrafts in the system, a TDMA (Time Division Multiple Access) scheme is proposed to be used where each aircraft is assigned one time slot during its presence in the system in order to transmit its own packet by itself or relay them using neighbouring aircrafts. These packets contain aircraft position, ID, relative direction which are used to build a routing table at each aircraft. In addition, several algorithms for relaying packets; schemes to reduce the packet-loss-ratio as well as to reduce the interference caused by surrounding aircrafts have been proposed. The simulations have shown the improvement of such proposals when examining system performance under real air-traffic scenarios. This system strengthens the reliability of oceanic aeronautical communication and increases situational awareness of all oceanic flights as an effective solution to operate more flights on the ocean but in higher safety. 

KEYWORDS 

Oceanic air traffic control communications, air-to-air communication, air-to-ground, mobile Ad-hoc networks

More Details............

Service Re-routing for Service Network Graph: Efficiency, Scalability and Implementation

 David Lai and Zhongwei Zhang 

University of Southern Queensland Toowoomba, Queensland

 Abstract

 The key to success in Next Generation Network is service routing in which service requests may need to be redirected as in the case of the INVITE request in Session Initiation Protocol [21]. Service Path (SPath) holds the authentication and server paths along side with service information. As the number of hops in a redirection increases, the length of SPath increases. The overhead for service routing protocols which uses SPath increases with the length of SPath. Hence it is desirable to optimize SPath to ensure efficiency and scalability of protocols involving service routing. In this paper, we propose a re-routing strategy to optimize service routing, and demonstrate how this strategy can be implemented using SPath to enhance the efficiency and scalability of Service Network Graph (SNG).

 Keywords 

Service Routing, Service Path, Service Network Graph, Optimization, Authentication Delegation


More Details...........

AOM: AN EFFICIENT APPROACH TO RESTORE ACTOR-ACTOR CONNECTIVITY IN WIRELESS SENSOR AND ACTOR NETWORKS

Azadeh Zamanifar1 , Omid Kashefi2 and Mohsen Sharifi3 

123Computer Engineering Department, Iran University of Science and Technology, Tehran, Iran 

 ABSTRACT

 Wireless sensor and actor networks (WSANs) consist of powerful actors and resource constraint sensors that are linked together in wireless networks. They mostly rely on actors to make proper decisions and perform desired coordination to achieve the goals of the entire network. They are usually deployed in critical applications and actor-actor network connectivity is thus vital to their effective utilization. Since WSAN applications are mostly deployed in harsh environments, actor nodes may fail and so partition their network. We propose a comparatively more efficient distributed approach, nicknamed AOM, to restore actor-actor connectivity upon the failure of any actor. We identify critical actors by combining the result of determining critical actors using the Stojmenovich’s method with the connectivity dominating set (CDS) of the network. This hybrid method of detecting critical actors helps in detecting critical nodes and candidate replacement actors more precisely while minimizing the total number of required messages for network restoration. The failure handling of actors is done in a proactive manner. Our proposed method minimizes both the restoration time of network and the total number of actor movements. When a failed actor is a critical node, actors in its neighborhood are relocated in a coordinated way to reconnect the actor network. The superiority of our approach compared to other works is shown by simulative experiments measuring two important parameters to WSANS, namely, the total number of transmitted messages and the total number of actor movements during actor-actor network reconnection process. 

KEYWORDS

Wireless Sensor and Actor Network; Network Restoration; Actor Connectivity; Cut Vertex; Connectivity Dominating Set (CDS) 

More Details....

EMPIRICAL EXAMINATION OF MOBILE AD HOC ROUTING PROTOCOLS ON WIRELESS SENSOR NETWORKS

 Zhongwei Zhang and Hong Zhou 

1 Department of Mathematics and Computing, University of Southern Queensland, Toowoomba, QLD 4350 

2 Department of Electronic Engineering, University of Southern Queensland, Toowoomba, QLD 4350

ABSTRACT 

Wireless sensor networks (WSNs) have great potential of being deployed in many places where traditional wired or wireless networks are not feasible. But they have also many new challenges more than other wireless networks. These challenges include the design of embedded intelligent sensors and wireless networking technology, ie. routing protocols and network security. WSNs also have some constraints such as sensor nodes failure which render WSN unavailable. The routing protocol in the sensor networks plays a critical role. They influence the performance of the WSNs and have significant impact on the security and the availability of WSNs. Wireless sensor networks (WSNs) have been regarded as an incarnation of Ad Hoc Networks for a specific application. Since a WSN consists of potentially hundreds of low cost, small size and battery powered sensor nodes, it has more potentials than a MANET to be deployed in many emerging areas. However, they also raised many new challenges, and these challenges include the design of embedded sensors and wireless networking technology, ie. routing protocols and network security. Many ad hoc routing protocols such as AODV, DSR, DSDR, TORA and OLSR, which have been developed particularly for the mobile wireless ad hoc networks (MANETs), performed satisfactorily on MANETs. Research has shown that these ad-hoc routing protocols work well for MANETs with different characteristics and requirements. In this paper, we investigate how well these ad-hoc routing protocols work on wireless sensor networks (WSNs). We focus on their performances in terms of average end-toend delay, packet delivery ratio and routing overheads. 

KEYWORDS 

Wireless technology, Sensor nodes, Dynamic routing, Throughput, Wireless Network, End-to-End delay 

More Details.....