Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.001 Byline: Yu-Chen Kuo Keywords: Ad hoc network; Chinese Remainder Theorem; Multicast protocol; Power management; Quorum systems Abstract: The asynchronous PS (Power-Saving) unicast protocol was designed for two PS wireless hosts to transmit the unicast message in the ad hoc network even their clocks are asynchronous. However, as regard to transmit a multicast message among more than two PS hosts, the protocol could not guarantee that all PS hosts can wake up at the same time. Some PS hosts may be in the PS mode when the multicast message is transmitted. Thus, the multicast message should be retransmitted again and again until all PS hosts receive the message. It will increase the energy consumption and the usage of the bandwidth. In this paper, we propose quorum-based PS multicast protocols for PS hosts to transmit multicast messages in the asynchronous ad hoc network. In those protocols, PS hosts use quorums to indicate their wakeup patterns. We introduce the rotation m-closure property to guarantee that m different quorums have the intersection even quorums are rotated due to asynchronous clocks. Thus, m PS hosts adopting m quorums satisfying the rotation m-closure property could wake up simultaneously and receive the multicast message even their clocks are asynchronous. We propose two quorum systems named the uniform k-arbiter and the CRT (Chinese Remainder Theorem) quorum system, which satisfy the rotation m-closure property. As shown in our analysis results, our quorum-based PS multicast protocols adopting those quorum systems can save more energy to transmit multicast messages. Author Affiliation: Department of Computer Science and Information Management, Soochow University, 56, Kueiyang St. Sec. 1, Taipei 100, Taiwan Article History: Received 19 July 2009; Revised 20 January 2010; Accepted 1 March 2010 Article Note: (footnote) [star] The preliminary version of this paper was presented in the Proceeding of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC), 2008, pp. 332-337.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.10.007 Byline: Javad Akbari Torkestani (a), Mohammad Reza Meybodi (b)(c) Keywords: Wireless ad hoc networks; Backbone formation; Broadcast storm problem; Connected dominating set; Distributed learning automata Abstract: In wireless ad hoc networks, due to the dynamic topology changes, multi hop communications and strict resource limitations, routing becomes the most challenging issue, and broadcasting is a common approach which is used to alleviate the routing problem. Global flooding is a straightforward broadcasting method which is used in almost all existing topology-based routing protocols and suffers from the notorious broadcast storm problem. The connected dominating set (CDS) formation is a promising approach for reducing the broadcast routing overhead in which the messages are forwarded along the virtual backbone induced by the CDS. In this paper, we propose an intelligent backbone formation algorithm based on distributed learning automata (DLA) in which a near optimal solution to the minimum CDS problem is found. Sending along this virtual backbone alleviates the broadcast storm problem as the number of hosts responsible for broadcast routing is reduced to the number of hosts in backbone. The proposed algorithm can be also used in multicast routing protocols, where the only multicast group members need to be dominated by the CDS. In this paper, the worst case running time and message complexity of the proposed backbone formation algorithm to find a 1/(1-I[micro]) optimal size backbone are computed. It is shown that by a proper choice of the learning rate of the proposed algorithm, a trade-off between the running time and message complexity of algorithm with the backbone size can be made. The simulation results show that the proposed algorithm significantly outperforms the existing CDS-based backbone formation algorithms in terms of the network backbone size, and its message overhead is only slightly more than the least cost algorithm. Author Affiliation: (a) Department of Computer Engineering, Islamic Azad University, Science and Research Branch, Tehran, Iran (b) Computer Engineering and IT Department, Amirkabir University of Technology, Tehran, Iran (c) Institute for Studies in Theoretical Physics and Mathematics (IPM), School of Computer Science, Tehran, Iran Article History: Received 1 September 2008; Revised 1 October 2009; Accepted 8 October 2009 Article Note: (miscellaneous) Responsible Editor: Edwin Chong

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.05.008 Byline: Patrick P.C. Lee (a), Tian Bu (b), Thomas Woo (b) Keywords: 3G wireless; Security; DoS attacks Abstract: Third generation (3G) wireless networks based on the CDMA2000 and UMTS standards are now increasingly being deployed throughout the world. Because of their complex signaling and relatively limited bandwidth, these 3G networks are generally more vulnerable than their wireline counterparts, thus making them fertile ground for new attacks. In this paper, we identify and study a novel denial of service (DoS) attack, called signaling attack, that exploits the unique vulnerabilities of the signaling/control plane in 3G wireless networks. Using simulations driven by real traces, we are able to demonstrate the impact of a signaling attack. Specifically, we show how a well-timed low-volume signaling attack can potentially overload the control plane and detrimentally affect the key elements in a 3G wireless infrastructure. The low-volume nature of the signaling attack allows it to avoid detection by existing intrusion detection algorithms, which are often signature or volume-based. As a counter-measure, we present and evaluate an online early detection algorithm based on the statistical CUSUM method. Through the use of extensive trace-driven simulations, we demonstrate that the algorithm is robust and can identify an attack in its inception, before significant damage is done. Apart from 3G networks, we also show that many emerging wide-area networks such as 802.16/WiMax share the same vulnerability and our solution can also apply. Author Affiliation: (a) Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong (b) Bell Labs, Alcatel-Lucent, 600-700 Mountain Avenue, Murray Hill, NJ 07974, USA Article History: Received 15 September 2008; Revised 27 April 2009; Accepted 20 May 2009 Article Note: (footnote) [star] An earlier and shorter conference version of this paper appeared in IEEE INFOCOM'07 . This paper additionally includes a discussion of the signaling attack in WiMax/802.16, provides evaluation on different dimensions of attacks, and presents more rigorous arguments in some of our analysis.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.03.012 Byline: Yuan He (a), Hao Ren (b), Yunhao Liu (a), Baijian Yang (c) Keywords: Cut vertex; Peer-to-peer; Reliability; Detection; Distributed method Abstract: In large-scale, self-organized distributed systems, such as peer-to-peer (P2P) overlays and wireless sensor networks (WSN), a small proportion of the nodes are likely to be more critical to the system's reliability than others. This paper focuses on detecting cut vertices so that we can either neutralize or protect these critical nodes. Detection of cut vertices is trivial if the global knowledge of the whole system is known but it is very challenging when the global knowledge is not available. In this paper, we propose a completely distributed scheme where every single node can determine whether it is a cut vertex or not. In addition, our design can also confine the detection overhead to a constant instead of being proportional to the size of a network. The correctness of this algorithm is theoretically proved and the key performance gains are measured and verified through trace-driven simulations. Author Affiliation: (a) Hong Kong University of Science and Technology, Department of Computer Science and Engineering, Hong Kong (b) College of Computer, National University of Defense Technology, Changsha, Hunan 410073, China (c) Department of Technology, Ball State University, Muncie, IN 47306, United States Article History: Received 12 August 2008; Revised 25 March 2009; Accepted 25 March 2009 Article Note: (miscellaneous) Responsible Editor: A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.09.016 Byline: Haibin Sun (a), John C.S. Lui (a), David K.Y. Yau (b) Keywords: Network security; Dos attack; Low-rate attack Abstract: In this paper, we consider a distributed mechanism to detect and to defend against the low-rate TCP attack. The low-rate TCP attack is a recently discovered attack. In essence, it is a periodic short burst that exploits the homogeneity of the minimum retransmission timeout (RTO) of TCP flows and forces all affected TCP flows to backoff and enter the retransmission timeout state. When these affected TCP flows timeout and retransmit their packets, the low-rate attack will again send a short burst to force these affected TCP flows to enter RTO again. Therefore these affected TCP flows may be entitled to zero or very low transmission bandwidth. This sort of attack is difficult to identify due to a large family of attack patterns. We propose a distributed detection mechanism to identify the low-rate attack. In particular, we use the dynamic time warping approach to robustly and accurately identify the existence of the low-rate attack. Once the attack is detected, we use a fair resource allocation mechanism to schedule all packets so that (1) the number of affected TCP flows is minimized and, (2) provide sufficient resource protection to those affected TCP flows. Experiments are carried out to quantify the robustness and accuracy of the proposed distributed detection mechanism. In particular, one can achieve a very low false positive/negative when compare to legitimate Internet traffic. Our experiments also illustrate the the efficiency of the defense mechanism across different attack patterns and network topologies. Author Affiliation: (a) Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, NT, Hong Kong (b) Department of Computer Science, Purdue University, USA Article History: Received 5 January 2005; Revised 9 July 2005; Accepted 8 September 2005 Article Note: (footnote) [star] The preliminary version of this paper appeared in the International Conference of Network Protocols (ICNP) 2004, Berlin, Germany.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.11.019 Byline: Min-You Wu (a), Yan Zhu (b), Wei Shu (b) Abstract: Proxy-based multicast is an approach to implementing the multicast function with proxy servers, which has many advantages compared to the IP multicast. When proxy locations are predetermined, many routing algorithms can be used to build a multicast overlay network. On the other hand, the problem of where to place proxies has not been extensively studied yet. A study on the placement problem for proxy-based multicast is presented in this paper. The objectives of proxy placement can be minimization of delay time, minimization of bandwidth consumption, or minimization of both. These performance metrics are studied in this paper and a number of algorithms are proposed for multicast proxy placement. Performance study is presented and practical issues of proxy placement are also discussed. Author Affiliation: (a) Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China (b) Department of Electrical and Computer Engineering, The University of New Mexico, MSC01 1100, Albuquerque, NM 87131-0001, USA Article Note: (miscellaneous) Responsible Editor: I. Matta

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.09.001 Byline: Jack Snoeyink (a), Subhash Suri (b), George Varghese (c) Keywords: Multicast; Security; Protocol analysis Abstract: With the rapidly growing importance of multicast in the Internet, several schemes for scalable key distribution have been proposed. These schemes require the broadcast of I(log n) encrypted messages to update the group key when the nth user joins or leaves the group. In this paper, we establish a matching lower bound (Independently, and concurrently, Richard Yang and Simon Lam discovered a similar bound with slightly different properties and proofs. An earlier version of our paper appeared in Infocom 2001 while their result appears in [R. Yang, S. Lam, A secure group key management communication lower bound, Technical Report TR-00-24, Department of Computer Sciences, UT Austin, July 2000, revised September 2000].), thus showing that I(log n) encrypted messages are necessary for a general class of key distribution schemes and under different assumptions on user capabilities. While key distribution schemes can exercise some tradeoff between the costs of adding or deleting a user, our main result shows that for any scheme there is a sequence of 2n insertion and deletions whose total cost is I[c](n log n). Thus, any key distribution scheme has a worst-case cost of I[c](log n) either for adding or for deleting a user. Author Affiliation: (a) Department of Computer Science, UNC-Chapel Hill, Chapel Hill, NC 27599-3175, USA (b) Department of Computer Science, University of California, Santa Barbara, CA 93106, USA (c) Computer Science and Engineering Department, University of California, 9500 Gilman Drive, La Jolla, CA 92093-0114, USA Article History: Received 2 September 2002; Revised 3 March 2004; Accepted 7 September 2004 Article Note: (miscellaneous) Reponsible Editor: S. Lam

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.07.016 Byline: Bin Guo (a)(b), Daqing Zhang (a), Michita Imai (b) Keywords: Ubiquitous computing management; Meta-design; Cooperation; Semantic Web; End user development; Smart object; Wireless sensor network Abstract: This paper presents iPlumber, a user-oriented management system for ubiquitous computing environments. Different from previous low-benefit "zero-configuration" systems or high cognitive-cost "end user programming" tools, our work attempts to attain a better balance between user benefits and cost by exploring the meta-design approach. A set of typical management activities in ubicomp environments are supported, from basic-level software sharing, foraging, and low-cost software configuration to advanced-level cooperative software co-design and error handling. These activities are elaborated through a smart home control scenario. The usability of our system is validated through an initial user study with a total of 33 subjects to test the management activities from an open exhibition environment and a controlled university environment. Author Affiliation: (a) Telecommunication Network and Services Department, Institut TELECOM SudParis, 9, rue Charles Fourier, 91011 Evry Cedex, France (b) Department of Information & Computer Science, Keio University, Japan Article History: Received 28 December 2009; Revised 20 June 2010; Accepted 9 July 2010

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.04.008 Byline: Lei Zhang (a), Bo Qin (a)(b), Qianhong Wu (a)(c), Futai Zhang (d)(e) Keywords: Information security; Message authentication; Digital signature; Certificateless cryptography Abstract: Aggregate signatures allow an efficient algorithm to aggregate n signatures of n distinct messages from n different users into one single signature. The resulting aggregate signature can convince a verifier that the n users did indeed sign the n messages. This feature is very attractive for authentications in bandwidth-limited applications such as reverse multicasts and senor networks. Certificateless public key cryptography enables a similar functionality of public key infrastructure (PKI) and identity (ID) based cryptography without suffering from complicated certificate management in PKI or secret key escrow problem in ID-based cryptography. In this paper, we present a new efficient certificateless aggregate signature scheme which has the advantages of both aggregate signatures and certificateless cryptography. The scheme is proven existentially unforgeable against adaptive chosen-message attacks under the standard computational Diffie-Hellman assumption. Our scheme is also very efficient in both communication and computation and the proposal is practical for many-to-one authentication. Author Affiliation: (a) Department of Computer Engineering and Mathematics, Universitat Rovira i Virgili, Av. PaA[macron]sos Catalans 26, E-43007 Tarragona, Catalonia, Spain (b) Department of Maths, School of Science, Xi'an University of Technology, China (c) School of Computer, Key Lab. of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan University, China (d) School of Computer Science and Technology, Nanjing Normal University, Nanjing, China (e) Jiangsu Engineering Research Center on Information Security and Privacy Protection Technology, Nanjing, China Article History: Received 1 March 2009; Revised 20 November 2009; Accepted 6 April 2010 Article Note: (miscellaneous) Responsible Editor: R. Molva

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.013 Byline: Josephina Antoniou (a), Vicky Papadopoulou (b), Vasos Vassiliou (a), Andreas Pitsillides (a) Keywords: Next generation networks; Access network selection; Game theory; Cooperative games; Present value Abstract: Next Generation Communication Networks employ the idea of convergence, where heterogeneous access technologies may coexist, and a user may be served by anyone of the participating access networks, motivating the emergence of a Network Selection mechanism. The triggering and execution of the Network Selection mechanism becomes a challenging task due to the heterogeneity of the entities involved, i.e., the users and the access networks. This heterogeneity results in different and often conflicting interests for these entities, motivating the question of how they should behave in order to remain satisfied from their interactions. This paper studies cooperative user-network interactions and seeks appropriate modes of behaviour for these entities such that they achieve own satisfaction overcoming their conflicting interests. Author Affiliation: (a) University of Cyprus, Dept. of Computer Science, 75 Kallipoleos Street, P.O. Box 20537, CY-1678 Nicosia, Cyprus (b) European University Cyprus, Dept. of Computer Science, 6, Diogenes Street, P.O. Box 22006, CY-1516 Nicosia, Cyprus Article History: Received 19 May 2009; Revised 28 February 2010; Accepted 25 March 2010 Article Note: (miscellaneous) Responsible Editor: A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.024 Byline: Di Wu (a), Chao Liang (b), Yong Liu (b), Keith W. Ross (c) Keywords: P2P applications; Video streaming Abstract: In current multi-channel P2P live video systems, there are several fundamental performance problems including exceedingly-large channel switching delays, long playback lags, and poor performance for less popular channels. These performance problems primarily stem from two intrinsic characteristics of multi-channel P2P video systems: channel churn and channel-resource imbalance. In this paper, we propose a radically different cross-channel P2P streaming framework, called View-Upload Decoupling (VUD). VUD strictly decouples peer downloading from uploading, bringing stability to multi-channel systems and enabling cross-channel resource sharing. We propose a set of peer assignment and bandwidth allocation algorithms to properly provision bandwidth among channels, and introduce substream-swarming to reduce the bandwidth overhead. We evaluate the performance of VUD via extensive simulations as well with a PlanetLab implementation. Our simulation and PlanetLab results show that VUD is resilient to channel churn, and achieves lower switching delay and better streaming quality. In particular, the streaming quality of small channels is greatly improved. Author Affiliation: (a) Department of Computer Science, Sun Yat-Sen University, Guangzhou 510006, China (b) Department of Electrical and Computer Engineering, Polytechnic Institute of NYU, Brooklyn, NY 11201, United States (c) Department of Computer Science and Engineering, Polytechnic Institute of NYU, Brooklyn, NY 11201, United States

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.002 Byline: Xiaofeng Lu (a), Pan Hui (b), Don Towsley (c), Juahua Pu (a), Zhang Xiong (a) Keywords: Location privacy; Anti-localization; Anonymous routing; Delay Tolerant Network Abstract: This paper focuses on the problem of how to allow a source to send a message without revealing its physical location and proposes an anti-localization routing protocol, ALAR, to achieve anonymous delivery in Delay/Disruption Tolerant Networks. The objectives of ALAR are to minimize the probability of a data source being localized and to maximize the destination's probability of receiving the message. ALAR can protect the sender's location privacy through message fragmentation and forwarding each segment to different receivers. ALAR is validated on two real-world human mobility datasets. This study indicates that ALAR increases the sender's anonymity performance by over 81% in different adversary densities with a 5% reduction in delivery ratio. Author Affiliation: (a) School of Computer Science, Beijing University of Aeronautics and Astronautics, Xueyuan Road 37, Beijing 100191, China (b) Deutsche Telekom Laboratories and TU-Berlin, Berlin, Germany (c) Department of Computer Science, University of Massachusetts, Amherst, United States Article History: Received 9 April 2009; Revised 19 December 2009; Accepted 1 March 2010 Article Note: (miscellaneous) Responsible Editor: J. Misic

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.02.013 Byline: Bheemarjuna Reddy Tamma (a), Anirudh Badam (b), C. Siva Ram Murthy (c), Ramesh R. Rao (a) Keywords: Ad hoc wireless networks; Video multicasting; Multicast trees; Path-diversity; Multiple description coding Abstract: In this paper, we address the problem of video multicast over Ad hoc wireless networks. Multicasting is an efficient means of one-to-many communication and is typically implemented by creating a multicast tree. Video multicasting demands high quality of service with a continuous delivery to receivers. However, most of the existing multicast solutions do not guarantee this because they are not resilient to mobility of the nodes and do not exploit error-resilient nature of recently available video coding techniques. Uninterrupted video transmission requires continuous reachability to receivers which emphasizes the usage of path-diversity. Hence, we propose a multiple tree multicast protocol which maintains maximally node-disjoint multicast trees in the network to attain robustness against path breaks. We further enhance the robustness by using the error-resilient multiple description coding (MDC) for video encoding. We prove that finding a given number of node-disjoint multicast trees for a multicast session in a given network is NP-Hard. Then we propose a protocol called K-Tree which maintains the maximal node-disjointedness property of K trees by using a distributed online heuristic. Through extensive simulation experiments, we show how the proposed protocol improves the video quality as we use two or three trees instead of a single tree for multicasting video stream. We also show, through simulations, that the protocol efficiently, in terms of overhead, provides high quality video as compared to an existing two tree video multicast protocol and a well known mesh-based multicast protocol. Author Affiliation: (a) California Institute for Telecommunications and Information Technology, University of California San Diego, CA 92093, USA (b) Department of Computer Science, Princeton University, NJ 08544, USA (c) Department of Computer Science and Engineering, Indian Institute of Technology Madras, TN 600036, India Article History: Received 16 July 2008; Revised 5 February 2010; Accepted 24 February 2010 Article Note: (miscellaneous) Responsible Editor: Prof. Qian Zhang

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.10.017 Byline: N.M. Mosharaf Kabir Chowdhury (a), Raouf Boutaba (b)(c) Keywords: Network virtualization; Virtual networks; Next-generation Internet architecture Abstract: Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. By introducing a plurality of heterogeneous network architectures cohabiting on a shared physical substrate, network virtualization promotes innovations and diversified applications. In this paper, we survey the existing technologies and a wide array of past and state-of-the-art projects on network virtualization followed by a discussion of major challenges in this area. Author Affiliation: (a) Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94702, United States (b) Cheriton School of Computer Science, University of Waterloo, ON, Canada N2L 3G1 (c) Division of IT Convergence Engineering, POSTECH, Pohang KB 790-784, Republic of Korea Article History: Received 3 March 2008; Revised 21 October 2009; Accepted 25 October 2009 Article Note: (footnote) [star] This work was jointly supported by the Natural Science and Engineering Council of Canada (NSERC) under its Discovery program, Cisco Systems, and WCU (World Class University) program through the Korea Science and Engineering Foundation funded by the Ministry of Education, Science and Technology (Project No. R31-2008-000-10100-0).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.09.004 Byline: Abdul Hasib (a), Abraham O. Fapojuwo (b) Keywords: Heterogeneous wireless network; Network selection; Call admission control; Performance analysis Abstract: This paper proposes a mobility adaptive network selection scheme in the context of wireless wide area network (WWAN) and wireless local area network (WLAN) radio access technologies (RATs) that supports both real-time (RT) and non-real-time (NRT) service classes. Physical layer information based call admission control (CAC) is considered for the two RATs to enforce service specific QoS requirements. The effectiveness of the cross-protocol-layer information for radio resource management (RRM) in integrated WWAN and WLAN networks is assessed analytically for individual service classes in a multi-service environment using the theory of Markov chains. The impact of non-uniform user and mobility distributions due to the existence of hotspot in the macro-cell area and the effect of network selection parameter measurement errors on the RRM performance are also evaluated. Numerical results show that the proposed network selection scheme minimizes the rate of unnecessary vertical handoffs, thereby providing stable communication without degrading the call blocking probability and call outage probability performance metrics. Author Affiliation: (a) Dept. of Elect. Engg. and Computer Science, North South University, Dhaka-1212, Bangladesh (b) Dept. of Elect. and Computer Engineering, The University of Calgary, Calgary, Alberta, Canada Article History: Received 6 November 2008; Revised 23 May 2009; Accepted 11 September 2009 Article Note: (miscellaneous) Responsible Editor: E. Gregori

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.09.008 Byline: Satish Chand (a), Hari Om (b) Keywords: Fast broadcasting scheme; Staircase scheme; Seamless channel transition; Video channel Abstract: Video applications require large amount of bandwidth and also storage space. The Fast Broadcasting (FB) scheme is one of the simplest schemes to provide video services, but it requires considerably large buffer storage. This scheme assumes constant video popularity and thus has fixed amount of bandwidth requirement. The popularity of videos generally does not remain the same. It varies over a period of time and accordingly the bandwidth allocation should be adjusted. The variability in bandwidth requirement for videos based on popularity is overcome by incorporating seamless channel transition mechanism in a broadcasting scheme. After incorporating seamless channel transition mechanism, the scheme still delivers continuous video data to old and new users without jerks and hiccups. The FB scheme with seamless channel transition mechanism requires less buffer storage than the FB scheme. The staircase scheme also allocates a fixed amount of bandwidth to a video. The FB and staircase schemes divide a video into same number of segments; thus have same user's waiting time. The basic difference between the FB and staircase schemes is that in the staircase scheme the segments are further divided into subsegments in order to reduce the buffer requirement. To consider variability of video popularity in the staircase scheme, seamless channel transition for staircase (SCTS) scheme has been discussed. The SCTS scheme performs better than the seamless Fast Broadcasting scheme as regard the buffer storage, while maintaining the same user's waiting time. In this paper, we propose an efficient staircase scheme with seamless channel transition mechanism that performs better than the SCTS scheme. In the proposed scheme, the video (ESS scheme) data is downloaded at slower rate than that in the SCTS scheme without disrupting the user services and requiring less buffer storage. Author Affiliation: (a) Computer Engineering Division, Netaji Subhas Institute of Technology, Sector-3, Dwarka, New Delhi 110 078, India (b) Department of Computer Science and Engineering, Indian School of Mines University, Dhanbad 826 004, India Article History: Received 15 September 2008; Revised 23 June 2009; Accepted 18 September 2009 Article Note: (miscellaneous) Responsible Editor: N. Agoulmine

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.05.002 Byline: Yang Xiao (a), Yanping Zhang (a), Miao Peng (a), Hui Chen (b), Xiaojiang Du (c), Bo Sun (d), Kui Wu (e) Keywords: Wireless sensor network; Randomized scheduling algorithm; Coverage; Intrusion object; Energy consumption; Two-dimensional; Three-dimensional Abstract: We are interested in wireless sensor networks which are used to detect intrusion objects such as enemy tanks, cars, submarines, etc. Since sensor nodes have a limited energy supply, sensor networks are configured to put some sensor nodes in sleep mode to save energy. This is a special case of a randomized scheduling algorithm. Ignored by many studies, an intrusion object's size and shape are important factors that greatly affect the performance of sensor networks. For example, an extremely large object in a small sensor field can easily be detected by even one sensor node, no matter where the sensor node is deployed. The larger an intrusion object is, the fewer sensor nodes that are required for detection. Furthermore, using fewer sensor nodes can save resources and reduce the waste of dead sensor nodes in the environment. Therefore, studying coverage based on intrusion object's size is important. In this paper, we study the performance of the randomized scheduling algorithm via both analysis and simulation in terms of intrusion coverage intensity. In particular, we study cases where intrusion objects occupy areas in a two-dimensional plane and where intrusion objects occupy areas in a three-dimensional space, respectively. We also study the deployment of sensor nodes when intrusion objects are of different sizes and shapes. First, sensor nodes are deployed in a two-dimensional plane and a three-dimensional space with uniform distributions. Then, they are deployed in a two-dimensional plane and a three-dimensional space in two-dimensional and three-dimensional Gaussian distributions, respectively. Therefore, our study not only demonstrates the impact of the size and shape of intrusion objects on the performance of sensor networks, but also provides a guideline on how to configure sensor networks to meet a certain detecting capability in more realistic situations. Author Affiliation: (a) Dept. of Computer Science, Univ. of Alabama, United States (b) Dept. of Mathematics and Computer Science, Virginia State Univ., United States (c) Dept. of Computer and Information Sciences, Temple Univ., United States (d) Dept. of Computer Science, Lamar Univ., United States (e) Dept. of Computer Science, Univ. of Victoria, Canada Article History: Received 18 June 2008; Revised 30 April 2009; Accepted 3 May 2009 Article Note: (miscellaneous) Responsible Editor: J. Lopez

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.02.023 Byline: Suat Ozdemir (a), Yang Xiao (b) Keywords: Secure data aggregation; Survey; Wireless sensor networks Abstract: Wireless sensor networks often consists of a large number of low-cost sensor nodes that have strictly limited sensing, computation, and communication capabilities. Due to resource restricted sensor nodes, it is important to minimize the amount of data transmission so that the average sensor lifetime and the overall bandwidth utilization are improved. Data aggregation is the process of summarizing and combining sensor data in order to reduce the amount of data transmission in the network. As wireless sensor networks are usually deployed in remote and hostile environments to transmit sensitive information, sensor nodes are prone to node compromise attacks and security issues such as data confidentiality and integrity are extremely important. Hence, wireless sensor network protocols, e.g., data aggregation protocol, must be designed with security in mind. This paper investigates the relationship between security and data aggregation process in wireless sensor networks. A taxonomy of secure data aggregation protocols is given by surveying the current "state-of-the-art" work in this area. In addition, based on the existing research, the open research areas and future research directions in secure data aggregation concept are provided. Author Affiliation: (a) Computer Engineering Department, Gazi University, Maltepe, Ankara, TR-06570, Turkey (b) Department of Computer Science, The University of Alabama, Tuscaloosa, AL 35487-0290, United States Article History: Received 8 July 2008; Revised 29 November 2008; Accepted 22 February 2009 Article Note: (footnote) [star] Dr. Ozdemir's work is supported in parts by the Gazi University Scientific Research Project Fund No. 06/2007-44. Prof. Y. Xiao's work is supported in parts by the US National Science Foundation (NSF) under Grants Nos. CCF-0829827, CNS-0716211, and CNS-0737325.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.02.018 Byline: Moonjeong Chang (a), Hyunjeong Lee (b), Meejeong Lee (a) Keywords: Per-application mobility management; Application-specific handover decision; Vertical handover; Cross-layer approach Abstract: With the advance of various wireless access technologies, the demand for a mobile user equipped with multiple air interfaces simultaneously executing diverse applications emerged. In such network environments, per-application mobility management is a key to allow each application of an end user device to dynamically and fully take advantage of the most suitable access technology. In this paper, we devised a comprehensive architectural platform with cross-layer techniques to realize this disruptive technology, i.e., per-application mobility management. The proposed platform enables the triggering of vertical handover decisions based on the dynamic measurements from the entire protocol stack. For per-application, the handover decision as well as the mobility management and the transport/application protocol control adaptation for handover performance optimization are made with cross-layer techniques. Through the simulation results, it is shown that multi-layer handover triggering of the proposed platform enhances the QoS of the application services by making handover decisions when the QoS requirements of an application is not satisfied as well as when a mobile user moves out of the current access network in overlay network environments. It is also presented that per-application handover based on the proposed platform enhances the QoS of the application services compared to the handover approaches which make every on-going service flows handover together to the same access network. Author Affiliation: (a) Dept. of Computer Science and Engineering, Ewha Womans University, 11-1 Daehyun-dong, Seodaemun-gu, Seoul 120-750, Republic of Korea (b) Wireless Communication Lab, Intel, USA Article History: Received 21 January 2008; Revised 4 January 2009; Accepted 23 February 2009 Article Note: (miscellaneous) Responsible Editor: W. Wang

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.01.008 Byline: Demetrios Zeinalipour-Yazti (a), Zografoula Vagena (b), Vana Kalogeraki (c), Dimitrios Gunopulos (d), Vassilis J. Tsotras (e), Michail Vlachos (f), Nick Koudas (g), Divesh Srivastava (h) Keywords: Distributed Top-K query processing; P2P networks; Sensor networks Abstract: In this paper, we present an algorithm for finding the k highest-ranked (or Top-k) answers in a distributed network. A Top-K query returns the subset of most relevant answers, in place of all answers, for two reasons: (i) to minimize the cost metric that is associated with the retrieval of all answers; and (ii) to improve the recall and the precision of the answer-set, such that the user is not overwhelmed with irrelevant results. Our study focuses on multi-hop distributed networks in which the data is accessible by traversing a network of nodes. Such a setting captures very well the computation framework of emerging Sensor Networks, Peer-to-Peer Networks and Vehicular Networks. We present the Threshold Join Algorithm (TJA), an efficient algorithm that utilizes a non-uniform threshold on the queried attribute in order to minimize the transfer of data when a query is executed. Additionally, TJA resolves queries in the network rather than in a centralized fashion which further minimizes the consumption of bandwidth and delay. We performed an extensive experimental evaluation of our algorithm using a real testbed of 75 workstations along with a trace-driven experimental methodology. Our results indicate that TJA requires an order of magnitude less communication than the state-of-the-art, scales well with respect to the parameter k and the network topology. Author Affiliation: (a) University of Cyprus, Dept. of Computer Science, 75 Kallipoleos Str., P.O. Box 20537, CY-1678, Nicosia, Cyprus (b) Microsoft Research Cambridge, Cambridge, United Kingdom (c) AUEB, Athens, Greece and UC - Riverside, Riverside, CA, United States (d) University of Athens, Athens, Greece (e) UC - Riverside, Riverside, CA, United States (f) IBM Research Zurich, Rueschlikon, Switzerland (g) University of Toronto, Toronto, ON, Canada (h) AT&T Research Labs, Florham Park, NJ, United States Article History: Received 25 March 2008; Revised 25 October 2008; Accepted 12 January 2009 Article Note: (miscellaneous) Responsible Editor: A. Kshemkalyani

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.09.013 Byline: Ai Chen, Dongwook Lee, Prasun Sinha Keywords: Wireless LAN; Association control; Algorithm/protocol design; Algorithm/protocol analysis Abstract: Support for efficient multicasting in WLANs can enable new services such as streaming of TV channels, radio channels, and visitor's information. With increasing deployments of large-scale WLANs, such services can be made available to a large number of users. However, any new multicast based services must minimally impact the existing unicast services which are currently the core services offered by most WLANs. In this paper, we leverage the flexibility of associating with different access-points (APs), which occurs often due to overlapping coverage of APs, to optimize the network's objective. Motivated by different revenue functions and network scenarios, three different optimization objectives are considered which are: maximizing the number of admitted users (MNU), balancing the load among APs (BLA), and minimizing the load of APs (MLA). We show that these problems are NP-hard and present centralized approximation algorithms and distributed approaches to solve them. These algorithms compute which AP a user should be associated with. Using simulations we evaluate their performance and compare them to a naive approach in which users associate to the AP with the best RSSI (Received Signal Strength Indicator). Author Affiliation: Department of Computer Science and Engineering, The Ohio State University, 395 Dreese Laboratories, 2015 Neil Avenue, Columbus, OH 43210-1277, USA Article History: Received 15 January 2008; Revised 15 September 2008; Accepted 16 September 2008 Article Note: (miscellaneous) Responsible Editor A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.08.018 Byline: Wei Wei (a), Bing Wang (a), Chun Zhang (b), Jim Kurose (c), Don Towsley (c) Keywords: Access network classification; Packet pair; Network measurement Abstract: Ethernet, wireless LAN, ADSL, cable modem, and dialup are common access networks that have dramatically different characteristics. Fast and accurate classification of access networks can benefit a wide range of applications. In this paper, we propose a simple and efficient end-to-end scheme to classify access networks into three categories: Ethernet, wireless LAN and low-bandwidth connection. Our scheme is based on the intrinsic characteristics of the various access networks, and utilizes the median and entropy of packet-pair inter-arrival times. Extensive experiments show that our scheme obtains accurate classification results in a very short time (95% accuracy in 2s, with 10 packet pairs). Author Affiliation: (a) Computer Science and Engineering Department, University of Connecticut, Storrs, CT 06269, United States (b) IBM T.J. Watson Research Center, Hawthorne, NY 10532, United States (c) Computer Science Department, University of Massachusetts, Amherst, MA 01003, United States Article History: Received 29 April 2008; Revised 6 August 2008; Accepted 12 August 2008 Article Note: (miscellaneous) Responsible Editor: L.G. Xue

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.08.017 Byline: Vijay K. Verma (a), Ramesh C. Joshi (a), Bin Xie (b), Dharma P. Agrawal (b) Keywords: Bloated state; Cloning; Itinerary partitioning; Mobile agent; Network management; Simple network management protocol (SNMP) Abstract: As computer networks increase in size, it is critical to provide efficient and scalable network management. Integration of mobile agents (MAs) with simple network management protocol (SNMP) provides a decentralized network management architecture that overcomes the limitations of the legacy SNMP client/server structure. However, as an MA travels through its itinerary, acquiring the network state at each managed node, its size linearly increases node-by-node and it may be unexpectedly bloated. As a result, a bloated MA will have difficulty in migrating from one node to another. We show that the network response time grows exponentially as the MA size increases linearly. In this paper, we propose a new strategy called itinerary partitioning approach (IPA) that exploits cloning capability of MAs to effectively address this bloated state phenomenon. The analytical model shows the effectiveness of our proposed IPA in terms of network response time. We have implemented the IPA in a practical test-bed network and the results seem to be very encouraging. Author Affiliation: (a) Department of Electronics and Computer Science, Indian Institute of Technology (IIT) - Roorkee, Roorkee, India (b) OBR Center of Distributed and Mobile Computing, Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221, United States Article History: Received 15 August 2006; Revised 9 April 2008; Accepted 4 August 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2006.06.009 Byline: Jenshiuh Liu (a), Zhi-Jian Lee (a), Yeh-Ching Chung (b) Keywords: Denial-of-service; IP; Network security; Probabilistic packet marking; IP traceback Abstract: Recently, denial-of-service (DoS) attack has become a pressing problem due to the lack of an efficient method to locate the real attackers and ease of launching an attack with readily available source codes on the Internet. Traceback is a subtle scheme to tackle DoS attacks. Probabilistic packet marking (PPM) is a new way for practical IP traceback. Although PPM enables a victim to pinpoint the attacker's origin to within 2-5 equally possible sites, it has been shown that PPM suffers from uncertainty under spoofed marking attack. Furthermore, the uncertainty factor can be amplified significantly under distributed DoS attack, which may diminish the effectiveness of PPM. In this work, we present a new approach, called dynamic probabilistic packet marking (DPPM), to further improve the effectiveness of PPM. Instead of using a fixed marking probability, we propose to deduce the traveling distance of a packet and then choose a proper marking probability. DPPM may completely remove uncertainty and enable victims to precisely pinpoint the attacking origin even under spoofed marking DoS attacks. DPPM supports incremental deployment. Formal analysis indicates that DPPM outperforms PPM in most aspects. Author Affiliation: (a) Department of Information Engineering and Computer Science, Feng-Chia University, Taichung 407, Taiwan, ROC (b) Department of Computer Science, National Tsing Hua University, HsingChu 300, Taiwan, ROC Article History: Received 23 May 2005; Revised 20 December 2005; Accepted 28 June 2006 Article Note: (footnote) [star] A preliminary version of this paper has appeared in the Proc. of the 11th IEEE Intl. Conf. on Network, pp. 475-480, September 2003.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2006.05.012 Byline: Jianping Pan (a), Lin Cai (b), Xuemin (Sherman) Shen (c), Jon W. Mark (c) Keywords: Wireless ad hoc networks; Peer collaboration; Identity-based cryptography Abstract: Voluntary peer collaboration is often assumed in media access, route discovery, packet forwarding, and upper-layer protocols designed for wireless ad hoc networks. This assumption has been seriously challenged when peers are autonomous, selfish, or malicious in large-scale, heterogeneous networks. In this paper, based on the latest advances in identity-based cryptography, we design a lightweight and cheat-resistant micropayment scheme to stimulate and compensate collaborative peers that sacrifice their resources to relay packets for other peers. We also demonstrate that when security and collaboration measures are properly enforced, profitable collaboration is a preferable strategy for all peers in ad hoc networks. Author Affiliation: (a) Department of Computer Science, University of Victoria, Victoria, BC, Canada V8W 3P6 (b) Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada V8W 3P6 (c) Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada N2L 3G1 Article History: Received 1 May 2006; Accepted 10 May 2006 Article Note: (miscellaneous) Responsible Editor: Dr. R. Boutaba

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2006.04.010 Byline: Junfeng Wang (a)(b), Lei Li (b), Mingtian Zhou (a) Keywords: Low earth orbit (LEO); Satellite networks; Topological dynamics; Snapshots characterization Abstract: The highly topological dynamics characterizes the most fundamental property of satellite networks with respect to terrestrial ones. The manifest feature directs the researches on various aspects of satellite networks, including protocol architecture investigations, routing protocol and reliable transmission control protocol design and enhancement, etc. This paper systematically quantifies the dynamical activities of regular low earth orbit (LEO) satellite network topologies. The number and length of network snapshots are formulated concisely. With this work, it compensates for the simplified topological assumptions in many LEO satellite network related researches. The thorough understanding of this basic feature not only provides for an accurate quantification of network behavior for researchers on satellite network community, but also could act as a guidance for future satellite constellation design and optimization. Author Affiliation: (a) School of Computer Science and Engineering, Sichuan University, Chengdu 610064, China (b) National Key Laboratory of Integrated Information System Technology, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China Article History: Received 6 February 2006; Accepted 5 April 2006 Article Note: (miscellaneous) Responsible Editor: K. Bhasin

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.11.007 Byline: Patrick McDaniel (a), William Aiello (b), Kevin Butler (a), John Ioannidis (c) Keywords: Routing; Security; Address management; BGP; Delegation; Authentication Abstract: Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication; there is no way to validate claims of address ownership or location. The lack of such services not only enables attacks by malicious entities, but also indirectly allows seemingly inconsequential misconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize original, broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via trace-based simulation, which demonstrates that the enhanced proof systems can significantly reduce resource costs associated with origin authentication. Author Affiliation: (a) Computer Science and Engineering, Pennsylvania State University, 344 IST Building, University Park, PA 16802, United States (b) Department of Computer Science, University of British Columbia, 201 Main Mall, Vancouver, Canada, BC V6T 1Z4 (c) Center for Computational Learning Systems, Columbia University, 475 Riverside Ave, New York, NY 10115, United States Article History: Received 11 April 2005; Revised 27 July 2005; Accepted 19 November 2005 Article Note: (miscellaneous) Responsible Editor: L.G. Xue

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.11.001 Byline: Hai Liu (a), Pengjun Wan (a)(b), Xiaohua Jia (a) Keywords: Energy efficiency; Lifetime; Scheduling; Sensor network; Surveillance system Abstract: This paper addresses the maximal lifetime scheduling for k to 1 sensor-target surveillance networks. Given a set of sensors and targets in Euclidean plane, a sensor can watch only one target at a time and a target should be watched by k sensors (k [greater than or equal to]2) at anytime. Our task is to schedule sensors to watch targets, such that the lifetime of the surveillance system is maximized, where the lifetime is the duration that all targets are watched. We propose an optimal solution to find the target watching schedule for sensors that achieves the maximal lifetime. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. Our solution consists of three steps: (1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; (2) decomposing the workload matrix into a sequence of schedule matrices by extending the Hall's theory, to achieve the maximal lifetime; (3) obtaining a target watching timetable for each sensor based on the schedule matrices. The time complexity of our optimal method is O(m.sup.2 n.sup.3), where m, n are the number of targets and the number of sensors, respectively. We illustrate our optimal method by a numeric example and experiments in the end. Author Affiliation: (a) Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong SAR, Hong Kong (b) Department of Computer Science, Illinois Institute of Technology, United States Article History: Received 11 October 2004; Revised 22 July 2005; Accepted 4 November 2005 Article Note: (miscellaneous) Responsible Editor: R. Sivakumar

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.09.038 Byline: Xiaoqiao Meng (a), Thyaga Nandagopal (b), Li Li (b), Songwu Lu (a) Keywords: Sensor network; Contour map; Spatio-temporal sampling Abstract: Large-scale sensor networks impose energy and communication constraints, thus it is difficult to collect data from each individual sensor node and process it at the sink. In this paper, we propose an efficient data-collection scheme that can be used for event monitoring or network-wide diagnosis. Our scheme relies on the well-known representation of data -- contour maps, which trade off accuracy with the amount of samples. The scheme consists of three novel algorithms to build contour maps: distributed spatial and temporal data suppression, contour reconstruction at the sink via interpolation and smoothing, and an efficient mechanism to convey routing information over multiple hops. By reducing the number of transmissions required to convey relevant information to the sink, the proposed contour mapping scheme saves energy and improves network lifetime. In a sharp contrast to related work in this area, the scheme does not require all nodes to explicitly share information. The contour mapping scheme can be applied for tasks such as: (1) presenting a global picture of the network in both temporal and spatial domains, (2) being used as a diagnosis tool, e.g., to detect faulty sensors and to scan for residual energy, (3) working in concert with in-network aggregation schemes to further reduce the communication overhead of aggregation schemes. The proposed scheme imposes little processing and storage overhead, allowing for the sensor networking paradigm of 'dumb sensor, smart sink' which enables economical deployment of large-scale sensor networks. Simulation results show that our scheme is resilient to both high packet loss rate and measurement noise. The design is also energy efficient, resulting in up to an-order-of-magnitude power savings when compared with the base line scheme where every sensor sends its report to the sink. Author Affiliation: (a) Computer Science Department, University of California, Los Angeles, CA 90095, United States (b) Bell Laboratories, Holmdel, NJ 07733, United States Article History: Received 26 January 2005; Revised 17 August 2005; Accepted 30 September 2005 Article Note: (miscellaneous) Responsible Editor: E. Ekici

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.09.035 Byline: Wenye Wang (a), Guoliang Xue (b) Keywords: Wireless networks; Location tracking; Partition; Optimization Abstract: Location tracking is one of the most important issues in providing real-time applications over wireless networks due to its effect to quality of service (QoS), such as end-to-end delay, bandwidth utilization, and connection dropping probability. In this paper, we study cost minimization for locating mobile users under delay constraints in mobile wireless networks. Specifically, a new location tracking algorithm is developed to determine the position of mobile terminals under delay constraints, while minimizing the average locating cost based on a unimodal property. We demonstrate that the new algorithm not only results in minimum locating cost, but also has a lower computational complexity compared to existing algorithms. Furthermore, detailed searching procedures are discussed under both deterministic and statistic delay bounds. Numerical results for a variety of location probability distributions show that our algorithm compares favorably with existing algorithms. Author Affiliation: (a) Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC 27695, United States (b) Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-8809, United States Article History: Received 10 March 2005; Revised 9 August 2005; Accepted 26 September 2005 Article Note: (miscellaneous) Responsible Editor: B. Baykal

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.09.001 Byline: Lotfi Mhamdi (a), Mounir Hamdi (b), Christopher Kachris (a), Stephan Wong (a), Stamatis Vassiliadis (a) Keywords: Buffered crossbar fabric; Matched scheduling; Priority Abstract: As buffer-less crossbar scheduling algorithms reach their practical limitations due to higher port numbers and data rates, internally buffered crossbar (IBC) switches have gained a lot of interest recently due to their great potential in solving the complexity and scalability issues faced by their buffer-less predecessors. The IBC switching architecture combined with the virtual output queueing (VOQ) architecture was shown, through distributed scheduling algorithms, to be able to sustain the current and expected increases in Internet throughput rates. Due to the architectural similarity between the input queued (IQ) and IBC switches, all the algorithms proposed for the latter were just a simple mapping of earlier algorithms proposed for the former. In this paper, we propose a set of scheduling schemes that are purely advocated for the VOQ/IBC switch architecture. We first address the issue of the internal buffers importance in the arbitration process. We propose a weighted scheduling algorithm, named Critical internal Buffer First (CBF), which takes full advantage of the internal buffer elements and makes its decision exclusively on the internal buffer information. Second, in order to simplify the scheduling scheme and make it practical, we propose a class of scheduling algorithms, named Current Arrival First-Priority Removal (CAF-PRMV) that use priority levels instead of weights. We argue that the interaction, through the internal buffer element, between the input and output schedulers is very important in designing such practical and highly scalable schemes for the IBC switching architecture. Our hardware implementation, in reconfigurable logic, shows that our CAF-PRMV class of algorithms can sustain a 10Gbps line speed for a 32x32 VOQ/IBC switch. Author Affiliation: (a) Computer Engineering Laboratory, Delft University of Technology, The Netherlands (b) Department of Computer Science, The Hong Kong University of Science and Technology, Clear Water Bay, Sai Kung, Kowloon, Hong Kong Article History: Received 28 July 2004; Revised 29 April 2005; Accepted 1 September 2005 Article Note: (miscellaneous) Responsible Editor: G. Parr

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.08.004 Byline: Florin Baboescu (a), Priyank Warkhede (b), Subhash Suri (c), George Varghese (d) Keywords: IP lookups; Classifiers; Filter conflicts; Packet classifications; VPN Abstract: Routers can use packet classification to support advanced functions such as QoS routing, virtual private networks and access control. Unlike traditional routers, which forward packets based on destination address only, routers with packet classification capability can forward packets based on multiple header fields, such as source address, protocol type, or application port numbers. The destination-based forwarding can be thought of as one-dimensional packet classification. While several efficient solutions are known for the one-dimensional IP lookup problem, the multi-dimensional packet classification has proved to be far more difficult. While an O(log w) time scheme is known for the IP lookup, Srinivisan et al. [V. Srinivasan, S. Suri, G. Varghese, Packet classification using tuple space search, in: Proceedings of SIGCOMM'99, 1999] show a lower bound of I[c](w.sup.k-1) for k-dimensional filter lookup, where w is the number of bits in a header field. In particular, this lower bound precludes the possibility of a binary search like scheme even for two-dimensional filters (say, IP source and destination pairs). In this paper, we examine this lower bound more closely, and discover that the lower bound depends crucially on conflicts in the filter database. We then show that for two-dimensional conflict-free filters, a binary search scheme does work! Our lookup scheme requires O(log.sup.2 w) hashes in the worst case, and uses O(n log.sup.2 w) memory. Alternatively, our algorithm can be viewed as making O(log w) calls to a prefix lookup scheme. It has been observed in practice that filter databases have very few conflicts, and these conflicts can be removed by adding additional filters (one per conflict). Thus, our scheme may also be quite practical. Our simulation and experimental results show that the proposed scheme also performs as good as or better than existing schemes. For example, on real firewall data sets with over 200 rules consisting of source and destination IP prefixes, our algorithm performs worst case 12 hashes. For filter sets containing arbitrarily many filtering rules with IP prefixes, the worst case search time guaranteed is utmost 25 hashes. Author Affiliation: (a) Qualcomm Inc., United States (b) Cisco Systems, United States (c) Computer Science, Engineering I, University of California, Santa Barbara, CA 93106, United States (d) Computer Science and Engineering, University of California, San Diego, CA 92040, United States Article History: Received 28 July 2004; Revised 11 May 2005; Accepted 1 August 2005 Article Note: (miscellaneous) Responsible Editor: D. Stiliadis

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.05.035 Byline: T. Bheemarjuna Reddy (a), S. Sriram (b), B.S. Manoj (c), C. Siva Ram Murthy (a) Keywords: Multi-path routing; QoS; Security; Dispersity routing; Diversity coding; Erasure channel; Corruption channel; Ad hoc wireless networks Abstract: In this paper, we present MuSeQoR: a new multi-path routing protocol that tackles the twin issues of reliability (protection against failures of multiple paths) and security, while ensuring minimum data redundancy. Unlike in all the previous studies, reliability is addressed in the context of both erasure and corruption channels. We also quantify the security of the protocol in terms of the number of eavesdropping nodes. The reliability and security requirements of a session are specified by a user and are related to the parameters of the protocol adaptively. This relationship is of central importance and shows how the protocol attempts to simultaneously achieve reliability and security. In addition, by using optimal coding schemes and by dispersing the original data, we minimize the redundancy. Finally, extensive simulations were performed to assess the performance of the protocol under varying network conditions. The simulation studies clearly indicate the gains in using such a protocol and also highlight the enormous flexibility of the protocol. Author Affiliation: (a) Department of Computer Science and Engineering, HPCN Lab, BSB 358, Indian Institute of Technology Madras, Chennai 600 036, Tamil Nadu, India (b) Department of Computer Science, University of California, Berkeley, CA 94720, USA (c) CalIT2, Jacobs School of Engineering, University of California, San Diego, CA 92093, USA Article History: Received 2 June 2004; Revised 5 May 2005; Accepted 23 May 2005 Article Note: (footnote) [star] This work was supported by the iNautix Technologies India Private Limited, Chennai, India and the Department of Science and Technology, New Delhi, India.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.06.005 Byline: Hongli Luo (a), Mei-Ling Shyu (a), Shu-Ching Chen (b) Keywords: Adaptive transmission rate; Quality-of-service (QoS); End-to-end congestion control; Network delay; TCP-friendly; Network resource optimization Abstract: In this paper, we propose an optimal resource utilization scheme with end-to-end congestion control for continuous media stream transmission. This scheme can achieve minimal allocation of bandwidth for each client and maximal utilization of the client buffers. By adjusting the server transmission rate in response to client buffer occupancy, playback requirements in the client, variations in network delays and the packet loss rate, an acceptable quality-of-service (QoS) level can be maintained at the end systems. Our proposed scheme can also achieve end-to-end TCP-friendly congestion control, which the multimedia flows can share fairly with the TCP flows instead of starving the TCP flows and the packet loss rate is reduced. Simulations to compare with different approaches under different network congestion levels and to show how our approach achieves end-to-end congestion control and inter-protocol fairness are conducted. The simulation results show that our proposed scheme can generally achieve high network utilization, low losses and end-to-end congestion control. Author Affiliation: (a) Department of Electrical and Computer Engineering, University of Miami, Coral Gables, FL 33124, USA (b) Distributed Multimedia Information System Laboratory, School of Computer Science, Florida International University, Miami, FL 33199, USA Article History: Received 5 November 2004; Revised 24 February 2005; Accepted 29 June 2005 Article Note: (miscellaneous) Responsible Editor: G. Morabito

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.07.010 Byline: Xiaotao Liu (a), Jiang Lan (b), Prashant Shenoy (a), Krithi Ramaritham (c) Keywords: P2P; Consistency; Overlay network Abstract: In this paper, we present techniques to maintain temporal consistency of replicated objects in data-centric peer-to-peer overlay applications. We consider both structured and unstructured overlay networks, represented by Chord and Gnutella, respectively, and present techniques for maintaining consistency of replicated data objects in the presence of dynamic joins and leaves. We present extensions to the Chord and Gnutella protocol to incorporate our consistency techniques and implement our extensions to Gnutella into a Gtk-Gnutella prototype. An experimental evaluation of our techniques shows that: (i) a push-based approach achieves near-perfect fidelity in a stable overlay network, (ii) a hybrid approach based on push and pull achieves high fidelity in highly dynamic overlay networks and (iii) the run-time overheads of our techniques are small, making them a practical choice for overlay networks. Author Affiliation: (a) Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA (b) Verizon Corp, GTE Labs, Verizon Data Services, 40 Sylvan Road, Waltham, MA 02451, USA (c) Department of Computer Science and Engineering, India Institute of Technology, Bombay, Powai, Mumbai 400 076, India Article Note: (footnote) [star] This research was supported by NSF grants CCR-9984030, CCR-0098060, CCR-0219520 and EIA-0080119.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.07.016 Byline: Beichuan Zhang (a), Wenjie Wang (b), Sugih Jamin (b), Daniel Massey (c), Lixia Zhang (d) Keywords: IP multicast; End-host multicast; Overlay multicast Abstract: A ubiquitous and efficient multicast data delivery service is essential to the success of large-scale group communication applications. The original IP multicast design is to enhance network routers with multicast capability [S. Deering, D. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems 8(2) (1990) 85-110]. This approach can achieve great transmission efficiency and performance but also poses a critical dependency on universal deployment. A different approach, overlay multicast, moves multicast functionality to end hosts, thereby removing the dependency on router deployment, albeit at the cost of noticeable performance penalty compared to IP multicast. In this paper we present the Universal Multicast (UM) framework, along with a set of mechanisms and protocols, to provide ubiquitous multicast delivery service on the Internet. Our design can fully utilize native IP multicast wherever it is available, and automatically build unicast tunnels to connect IP Multicast "islands" to form an overall multicast overlay. The UM design consists of three major components: an overlay multicast protocol (HMTP) for inter-island routing, an intra-island multicast management protocol (HGMP) to glue overlay multicast and native IP multicast together, and a daemon program to implement the functionality at hosts. In addition to performance evaluation through simulations, we have also implemented parts of the UM framework. Our prototype implementation has been used to broadcast several workshops and the ACM SIGCOMM 2004 conference live on the Internet. We present some statistics collected during the live broadcast and describe mechanisms we adopted to support end hosts behind Network Address Translation (NAT) gateways and firewalls. Author Affiliation: (a) Computer Science Department, University of Arizona, Tucson, AZ 85721-0077, USA (b) EECS Department, University of Michigan, Ann Arbor, MI 48109-2122, USA (c) Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873, USA (d) Computer Science Department, UCLA, Los Angeles, CA 90095-1596, USA

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.03.003 Byline: Jun-Hong Cui (a), Li Lao (b), Michalis Faloutsos (c), Mario Gerla (b) Keywords: Multicast; QoS; State scalability; Diff-Serv; MPLS Abstract: The deployment of IP multicast support is impeded by several factors among which are the state scalability problem, the cumbersome management and routing, and the difficulty of supporting QoS. In this paper, we propose an architecture, called Aggregated QoS Multicast (AQoSM), to provide scalable and efficient QoS multicast in Diff-Serv networks. The key idea of AQoSM is to separate the concept of groups from the concept of distribution tree by "mapping" many groups to one distribution tree. In this way, multicast groups can now be routed and rerouted very quickly by assigning different labels (e.g., tree IDs) to the packets. Therefore, we can have load-balancing and dynamic rerouting to meet QoS requirements. In addition, the aggregation of groups on fewer trees leads to routing state reduction and less tree management overhead. Thus, AQoSM enables multicast to be seamlessly integrated into Diff-Serv without violating the design principle of Diff-Serv of keeping network core "QoS stateless" and without sacrificing the efficiency of multicast. Finally, efficient resource utilization and strong QoS support can be achieved through statistical multiplexing at the level of aggregated trees. We design a detailed MPLS-based AQoSM protocol with efficient admission control and MPLS multicast tree management. By simulation studies, we show that our protocol achieves significant multicast state reduction (up to 82%) and tree maintenance overhead reduction (up to 86%) with modest (12%) bandwidth overhead. It also reduces the blocking ratio of user requests with strong QoS requirements due to its load balancing and statistical multiplexing capabilities. Author Affiliation: (a) Computer Science & Engineering Department, University of Connecticut, Storrs, CT, United States (b) Computer Science Department, University of California, Los Angeles, CA, United States (c) Computer Science & Engineering Department, University of California, Riverside, CA, United States Article History: Received 8 November 2004; Revised 17 February 2005; Accepted 29 March 2005 Article Note: (footnote) [star] This material is based upon work supported by the National Science Foundation under Grant No. CNS-0435515, CNS-0435230, ANIR-9985195 (CAREER award), and IDM-0208950.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.11.028 Byline: Christos Nomikos (a), Aris Pagourtzis (b), Katerina Potika (b), Stathis Zachos (b)(c) Keywords: Graph theory; Wavelength assignment; Multifiber optical networks Abstract: Motivated by the increasing importance of multifiber WDM networks we study a routing and wavelength assignment problem in such networks. In this problem the number of wavelengths per fiber is given and the goal is to minimize the cost of fiber links that need to be reserved in order to satisfy a set of communication requests; we introduce a generalized setting where network pricing is non-uniform, that is the cost of hiring a fiber may differ from link to link. We consider two variations: undirected, which corresponds to full-duplex communication, and directed, which corresponds to one-way communication. Moreover, for rings we also study the problem in the case of pre-determined routing. We present exact or constant-ratio approximation algorithms for all the above variations in chain, ring and spider networks. Author Affiliation: (a) Department of Computer Science, University of Ioannina, P.O. Box 1186, 45 110 Ioannina, Greece (b) School of Electrical and Computer Engineering, National Technical University of Athens, 157 80 Athens, Greece (c) CIS Department, Brooklyn College and Graduate Center, City University of New York, NY 11210, USA Article History: Received 29 July 2004; Accepted 22 November 2004 Article Note: (footnote) [star] Research supported in part by the European Social Fund (75%) and the Greek Ministry of Education (25%) through grants "Pythagoras" and "Heraclitus", of the Operational Programme on Education and Initial Vocational Training. Some of the results presented in this paper have appeared in preliminary form in 'Fiber Cost Reduction and Wavelength Minimization in Multifiber WDM Networks', Proc. Networking 2004, LNCS 3042, pp. 150-161.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.11.027 Byline: Harsha V. Madhyastha (a), Girish V. Chowdhary (c), N. Srinivas (b), C. Siva Ram Murthy (c) Keywords: Optical WDM ring networks; Routing and wavelength assignment; Multicast sessions; Optical splitter; Traffic grooming; ILP formulation; Circle construction Abstract: With the introduction of WDM into the metro environment, the need to cost-effectively handle finer "sub-wavelength" capacities has become paramount. In this paper, we address the problem of routing and wavelength assignment of multicast sessions with sub-wavelength traffic demands, in the scenario of metropolitan WDM ring networks. In order to support multicasting, individual nodes need to have the capability to duplicate traffic. We consider two different node architectures which perform the duplication in optical and electronic domain, respectively. As traffic duplication at the electronic level is much more expensive than the optical alternative [X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, J. Gu, Optimization of wavelength assignment for QoS multicast in WDM networks, IEEE Trans. Commun. 49 (2) (2001) 341-350], we study the problem of assigning routes and wavelengths to the multicast sessions so as to minimize electronic copying. We present an ILP formulation of this problem. The solution to this problem can be divided into three phases -- 1. routing of multicast sessions, 2. construction of circles by grouping non-overlapping arcs and 3. grouping these circles onto wavelengths. We propose a heuristic algorithm which implements the routing as well as circle construction phases simultaneously and then groups the circles. We present extensive simulation results to show that our approach leads to much lower equipment cost than that obtained by routing each multicast session along its minimum spanning tree and then using the best known heuristic for circle construction [X. Zhang, C. Qiao, An effective and comprehensive approach to traffic grooming and wavelength assignment in SONET/WDM rings, IEEE/ACM Trans. Networking 8 (5) (2000) 608-617]. Author Affiliation: (a) Department of Computer Science and Engineering, University of Washington, Seattle, WA 98195, USA (b) Microsoft India (R&D) Pvt. Ltd., 9th Floor, Room # 9008, Cyber Towers, HiTech City, Hyderabad 500 081, India (c) Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai 600 036, India Article History: Received 2 April 2004; Revised 15 September 2004; Accepted 29 November 2004 Article Note: (footnote) [star] This work was supported by the Department of Science and Technology, New Delhi, India.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.01.007 Byline: Jyh-haw Yeh (a), Wei Zhang (a), Wen-chen Hu (b), Chung-wei Lee (c) Keywords: Internet policy routing; Border gateway protocol; Internet topology; Routing simulation Abstract: Internet policy routing has attracted a lot of attention in the last decade and it is believed that this topic will become even more important in the foreseeable future. The growing diversity of the Internet brings in many organizations under different authorities with conflicting interests. Each such organization forms an Autonomous System (AS), with its own policy regulating network traffic across its boundaries to protect valuable network resources. As a result, a policy violation at any intermediate AS may cause a packet to be silently dropped before reaching its destination. The Border Gateway Protocol (BGP) was introduced to solve this packet-dropping problem in the mid-1990s, followed by a series of revisions. Currently, BGP is the dominant protocol in this field. However, BGP is a distance-vector and hop-by-hop protocol, resulting in a loss of reachability information for some destinations, even though feasible routes to those destinations may physically exist. Unreachable destinations under BGP are not necessarily truly unreachable. To overcome this deficiency, this paper presents a source policy route discovery protocol to supplement BGP. Simulation results show that almost all the false negative unreachable destinations can be resolved by the proposed protocol. Author Affiliation: (a) Department of Computer Science, Boise State University, 1910 University Drive, Boise, ID 83725, United States (b) Department of Computer Science, University of North Dakota, Grand Forks, ND 58202, United States (c) Department of Computer Science and Software Engineering, Auburn University, Auburn, AL 36849, United States Article History: Received 22 October 2003; Revised 10 December 2004; Accepted 5 January 2005 Article Note: (miscellaneous) Responsible Editor: Y. Shavitt

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.11.004 Byline: Kamil Sarac (a), Kevin C. Almeroth (b) Abstract: The successful deployment of multicast in the Internet requires the availability of good network management solutions. One of the first management tasks for multicast is to verify its availability in the network. This task is usually referred to as reachability monitoring. Reachability ensures that sources can reach all existing and potential group members. Reachability also implies that receivers have multicast connectivity and can reach all sources. As a result, verifying reachability becomes very important to maintain availability and robustness of the multicast service between sources and receivers. In this paper, we present an application layer mechanism to monitor multicast reachability. First, we justify the need for reachability monitoring systems. Then, we present our monitoring system called sdr-monitor. Sdr-monitor leverages an existing application and provides close to real-time reachability monitoring for the multicast infrastructure. It is the first system that is developed and deployed for monitoring multicast reachability. We present the architecture of the system and then discuss its operation. Finally, we include our evaluations on a data set that we collected using this system. With this analysis, we present long term reachability characteristics of multicast infrastructure during a four year monitoring period between 1999 and 2003 and discuss potential causes for reachability problems. Author Affiliation: (a) Department of Computer Science, University of Texas at Dallas, 2601 N. Floyd Rd., Richardson, TX 75083, USA (b) Department of Computer Science, University of California Santa Barbara, Santa Barbara, CA 93106, USA Article Note: (miscellaneous) Responsible Editor: I. Nikolaidis

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2004.08.008 Byline: Kemal Bicakci (a), Nazife Baykal (b) Keywords: Server-assisted signature; One-time signature; Digital signature; Nonrepudiation; Network security Abstract: It is well known that excessive computational demands of public key cryptography have made its use limited especially when constrained devices are of concern. To reduce the costs of generating public key signatures one viable method is to employ a third party; the server. In open networks, getting help from a verifiable-server has an advantage over proxy-based solutions since as opposed to proxy-server, verifiable-server's cheating can be proven. Verifiable-server assisted signatures were proposed in the past but they could not totally eliminate public key operations for the signer. In this paper, we propose a new alternative called SAOTS (server assisted one-time signatures) where just like proxy signatures generating a public key signature is possible without performing any public key operations at all. This feature results in both computational efficiency and implementation simplicity (e.g. a reduction in the code size) of the proposed protocol. In addition, SAOTS is a more promising approach since the signature is indistinguishable from a standard signature, no storage is necessary for the signer to prove the server's cheating and the protocol works in less number of rounds (two instead of three). On the other hand, the drawback of SAOTS is the increased bandwidth requirement between the sender and server. Author Affiliation: (a) Department of Computer Science, Vrije Universiteit, De Boelelaan 1083, 1081 HV Amsterdam, Netherlands (b) Informatics Institute, Middle East Technical University, 06531 Ankara, Turkey Article History: Received 6 April 2004; Revised 9 August 2004; Accepted 9 August 2004 Article Note: (miscellaneous) Responsible Editor: D. Frincke