Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.12.015 Byline: Gang Quan (a), Garrison W. Greenwood (b), Donglin Liu (c), Sharon Hu (c) Keywords: Evolutionary computations; Scheduling; Utility theory; Preventive maintenance; Multi-objective optimization Abstract: Heavy industry maintenance facilities at aircraft service centers or railroad yards must contend with scheduling preventive maintenance tasks to ensure critical equipment remains available. The workforce that performs these tasks are often high-paid, which means the task scheduling should minimize worker idle time. Idle time can always be minimized by reducing the workforce. However, all preventive maintenance tasks should be completed as quickly as possible to make equipment available. This means the completion time should be also minimized. Unfortunately, a small workforce cannot complete many maintenance tasks per hour. Hence, there is a tradeoff: should the workforce be small to reduce idle time or should it be large so more maintenance can be performed each hour? A cost effective schedule should strike some balance between a minimum schedule and a minimum size workforce. This paper uses evolutionary algorithms to solve this multiobjective problem. However, rather than conducting a conventional dominance-based Pareto search, we introduce a form of utility theory to find Pareto optimal solutions. The advantage of this method is the user can target specific subsets of the Pareto front by merely ranking a small set of initial solutions. A large example problem is used to demonstrate our method. Author Affiliation: (a) Department of Computer Science and Engineering, University of South Carolina, Columbia, SC 29208, USA (b) Department of Electrical and Computer Engineering, Portland State University, Portland, OR 97207, USA (c) Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA

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.ejor.2005.08.012 Byline: Edmund K. Burke (a), Barry McCollum (b), Amnon Meisels (c), Sanja Petrovic (a), Rong Qu (a) Keywords: Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling Abstract: This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems. Author Affiliation: (a) Automated Scheduling Optimization and Planning Group, School of CSiT, University of Nottingham, Nottingham NG8 1BB, UK (b) School of Computer Science, Queen's University Belfast, Belfast BT7 1NN, UK (c) Department of Computer Science, Ben-Gurion University, Beer-Sheva 84 105, Israel Article History: Received 21 September 2004; Accepted 18 August 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.03.038 Byline: Helio R. Costa (a)(b), Marcio de O. Barros (b)(c), Guilherme H. Travassos (b) Keywords: Software project management; Software risk management; Software Engineering Economics; Empirical studies Abstract: As in any other business, software development organizations try to maximize their profits and minimize their risks. The risks represent uncertain events and conditions that may prevent enterprises from attaining their goals, turning risk management into a major concern, not only for project managers but also for executive officers involved with strategic objectives. In this sense, economical concepts can greatly support Software Engineers in the effort to better quantify the uncertainties of either a single project or even a project portfolio. In this paper, we present a technique for evaluating risk levels in software projects through analogies with economic concepts. This technique allows a manager to estimate the probability distribution of earnings and losses incurred by an organization in relation to its software project portfolio. This approach has been calibrated by data collected in an empirical study, which has been planned and accomplished to provide information about the relative importance of risk factors in software projects. A usage example of such an approach is presented. Finally, we introduce a case tool specially built to support the application of the proposed techniques. Author Affiliation: (a) CCA-RJ, Brazilian Air Force, Ponta do Galeao s/n[degrees], Ilha do Governador, CEP: 21941-510 Rio de Janeiro, Brazil (b) COPPE/UFRJ, System Engineering and Computer Science Department, Caixa Postal: 68511, CEP: 21945-970 Rio de Janeiro, Brazil (c) UNIRIOTEC, Applied Computer Science Department, Av. Pasteur 458, Urca, CEP: 22290-240 Rio de Janeiro, Brazil Article History: Received 1 October 2005; Revised 9 March 2006; Accepted 26 March 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.03.039 Byline: Sanghyun Yoo (a), Jin Hyun Son (b), Myoung Ho Kim (a) Keywords: Publish/subscribe system; XPath; Homomorphism; Subscription routing algorithm Abstract: XML-based publish/subscribe systems have gained popularity as one of the newly emerging communication paradigms. As the number of clients has increased, the concept of the scalability has become the most important factor in the distributed information processing. In this paper, we propose an efficient subscription routing algorithm as a part of efforts to achieve scalability, with subscriptions especially expressed in XPath patterns. We first discuss that the homomorphism relationship among XPath patterns can be utilized for routing XPath patterns. Then, we develop a lattice data structure called the partially ordered set of XPath patterns which is abbreviated as POX and its corresponding algorithm for efficiently maintaining homomorphism relationships. Finally, we present performance evaluation results which validate our algorithm with respect to system performance and scalability. Author Affiliation: (a) Division of Computer Science, Korea Advanced Institute of Science and Technology, 373-1 Guseong-dong, Yuseong-gu, Daejeon, Republic of Korea (b) Department of Computer Science and Engineering, Hanyang University, 1271 Sa-1-dong, Sangrok-gu, Ansan, Kyonggi-do, Republic of Korea Article History: Received 31 July 2005; Revised 8 March 2006; Accepted 26 March 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.04.036 Byline: Stef Tijs (a), Rodica Branzei (b), Stefano Moretti (c), Henk Norde (d) Keywords: Cost allocation; Minimum cost spanning tree situations; Cost monotonicity; Population monotonic allocation schemes Abstract: We consider the class of Obligation rules for minimum cost spanning tree situations. The main result of this paper is that such rules are cost monotonic and induce also population monotonic allocation schemes. Another characteristic of Obligation rules is that they assign to a minimum cost spanning tree situation a vector of cost contributions which can be obtained as product of a double stochastic matrix with the cost vector of edges in the optimal tree provided by the Kruskal algorithm. It turns out that the Potters value (P-value) is an element of this class. Author Affiliation: (a) Department of Mathematics, University of Genoa, Italy and CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands (b) Faculty of Computer Science, 'Alexandru Ioan Cuza' University, Carol I Bd., 11, 6600 Iasi, Romania (c) Unit of Molecular Epidemiology, National Cancer Research Institute of Genoa and Department of Mathematics, University of Genoa, Via Dodecaneso, 35, 16146 Genoa, Italy (d) CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands Article History: Received 28 July 2004; Accepted 11 April 2005 Article Note: (footnote) [star] The authors thank two anonymous referees for their careful and valuable comments.

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.compeleceng.2006.01.024 Byline: Chin-Chen Chang (a), Yeu-Pong Lai (b) Keywords: Chinese Remainder Theorem; Residue Number System; Euclidean algorithm; Montgomery algorithm; Division-free Abstract: In recent years, the conversion of residue numbers to a binary integer has been intensively studied. The Chinese Remainder Theorem (CRT) is a solution to this conversion problem of a number to the Residue Number System with a general moduli set. This paper presents a new division-free conversion approach for the conversion of residue numbers to a binary integer. The algorithm differs from others employing a great number of division instructions by using shift instructions instead. These simple instructions keep the power consumption lower. This algorithm can also be implemented with a lookup table or upon a vector machine. Both make the conversion process efficient. This division-free algorithm employs the concept of Montgomery multiplication algorithm. There are two variations of Montgomery algorithm proposed, which are algorithms MMA and IMA. The algorithm MMA is to transform the input number into the output presentation of Montgomery algorithm. Algorithm IMA is therefore inverse the computation of Montgomery algorithm to obtain the multiplicand. These two algorithms are in the complexity of O(n), where n is alog.sub.2 q.sub.i a. q.sub.i is a modulus. The proposed algorithm for converting the residues to a binary integer therefore runs on O(n xlog m) times on O(m) processors. There are O(log m) iterations of O(n) complexity. Compared with the traditional conversion algorithm, the advantages of this proposed algorithm are not only in employing simpler operations but also in performing fewer iterations. Author Affiliation: (a) Department of Information Engineering and Computer Science, Feng Chia University, Taichung 40724, Taiwan, ROC (b) Department of Computer Science and Information Engineering, Chung Cheng Institute of Technology, National Defense University, Tauyuan 335, Taiwan, ROC Article History: Received 4 April 2002; Accepted 17 January 2006

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.ejor.2005.01.052 Byline: Salem M. Al-Yakoob (a), Hanif D. Sherali (b) Keywords: Timetabling; Class scheduling; Mixed-integer programming; Employee scheduling; Gender policies Abstract: This paper presents mathematical programming models for assigning faculty members to classes including, among typical academic class scheduling issues, certain specialized central policies at Kuwait University. The time-slots for classes are initially assumed to be given and an integer programming model (CFAM) is constructed to solve the resulting problem, which aims to minimize the individual and collective dissatisfaction of faculty members in a fair fashion, where dissatisfaction is measured by a function of the assignment of faculty members to time-slots and specific classes. In order to enhance the quality of results obtained in practice, the model is modified (ECFAM) so that the time-slots for the classes can be changed, however, with restrictions related to efficient facility utilization and permitting an administratively regulated maximum number of changes. Gender-based modeling considerations are also introduced in order to maintain desirable class offering patterns. Computational results are presented based on solving the models directly by the CPLEX-MIP (version 7.5) package and also using a specialized LP-based heuristic. The faculty schedules generated via the proposed approach based on a number of case studies related to the Department of Mathematics and Computer Science at Kuwait University reveal that this approach yields improved schedules in terms of fairness and enhanced satisfaction levels among faculty members. Author Affiliation: (a) Department of Mathematics and Computer Science, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait (b) Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, United States Article History: Received 11 May 2004; Accepted 28 January 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.02.062 Byline: S.K. Mishra (a), S.Y. Wang (b)(d), K.K. Lai (c)(d) Keywords: Multi-objective programming; n-set functions; Optimality; Duality; Generalized convexity Abstract: In this paper, we introduce several generalized convexity for a real-valued set function and establish optimality and duality results for a multi-objective programming problem involving generalized d-type-I and related n-set functions. Author Affiliation: (a) Department of Mathematics, Statistics and Computer Science, College of Basic Sciences and Humanities, Govind Ballabh Pant University of Agriculture and Technology, Pantnagar 263 145, India (b) Institute of Systems Science, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, Beijing 100080, China (c) Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong (d) College of Business Administration, Hunan University, Changsha, China Article History: Received 3 November 2003; Accepted 21 February 2005 Article Note: (footnote) [star] The research was supported by the Department of Science and Technology, Ministry of Science and Technology, Government of India under SERC Fast Track Scheme for Young Scientists 2001-2002 through grant No. SR/FTP/MS-22/2001 and The National Natural Science Foundation of China.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2005.12.001 Byline: Hao Yin (a), Feng Qiu (a), Chuang Lin (a), Geyong Min (b), Xiaowen Chu (c) Keywords: Security; Video multicast; Data embedding; Media-dependent approach Abstract: The secure distribution and maintenance of key information are essential for controlling access to video multicast systems. Unlike the conventional approaches using a dedicated channel independent of the video stream, this paper proposes a novel data embedding scheme, which we refer to as SMDE (statistical modulation data embedding), to support the media-dependent approach that exploits data-dependent channel to transmit and maintain key information. Using embedded data to convey key information is able to achieve added security and reduce bandwidth resource consumption. To this end, we present some new algorithms to embed key messages. By adopting the statistical properties of host video signal, new coding approach for embedded data, and error control algorithm, the proposed SMDE scheme can provide error resilience, transparence for adaptation mechanism, high accuracy of detecting embedded data and real-time processing capability for video applications. These advantages have been demonstrated by the extensive experimental results. Author Affiliation: (a) Department of Computer Science, Tsinghua University, 100084 Beijing, China (b) Department of Computing, University of Bradford, Bradford BD7 1DP, UK (c) Department of Computer Science, Hong Kong Baptist University, Kowloon Tong, Hong Kong Article History: Received 8 December 2004; Accepted 1 December 2005 Article Note: (footnote) [star] This work is supported by the National Natural Science Foundation of China (Nos. 60372019, 90104002, 60173012 and 60473086), the Projects of Development Plan of the State High Technology Research (No. 2001AA112080).

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.jss.2005.11.576 Byline: Chin-Chen Chang (a)(b), Tzu-Chuen Lu (b) Keywords: Reversible information hiding; SMVQ; Lossy compression Abstract: Information hiding has become an interesting topic that receives more and more attention. Recently, many hiding techniques were proposed to directly conceal secret information on an image. However, for convenience and efficiency, images are usually stored and compressed by lossy or lossless compression mechanisms in indices format. The hidden information might be erased or cancelled when the stego image is lossy compressed. Hence, this paper proposes an information hiding scheme based on side-match vector quantization (SMVQ), which conceals the secret information on the indices of the SMVQ compressed images. The proposed scheme not only can embed information in the indices of the compressed image with low image distortion, but also can recover the original indices to reconstruct the SMVQ compressed image. As the experimental results indicated, the proposed scheme indeed outperforms other schemes in terms of image quality, hiding capacity, and compression rate. Author Affiliation: (a) Department of Information Engineering and Computer Science, Feng Chia University, 100 Wenhwa Rd., Seatwen, Taichung 40724, Taiwan, ROC (b) Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi 621, Taiwan, ROC Article History: Received 13 May 2005; Revised 15 November 2005; Accepted 24 November 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.09.003 Byline: Yusuf Hasan (a), J. Morris Chang (b) Keywords: Dynamic memory allocation; Performance; Tuning; Optimization Abstract: Dynamic memory management can make up to 60% of total program execution time. Object oriented languages such as C++ can use 20 times more memory than procedural languages like C. Bad memory management causes severe waste of memory, several times that actually needed, in programs. It can also cause degradation in performance. Many widely used allocators waste memory and/or CPU time. Since computer memory is an expensive and limited resource its efficient utilization is necessary. There cannot exist a memory allocator that will deliver best performance and least memory consumption for all programs and therefore easily tunable allocators are required. General purpose allocators that come with operating systems give less than optimal performance or memory consumption. An allocator with a few tunable parameters can be tailored to a program's needs for optimal performance and memory consumption. Our tunable hybrid allocator design shows 11-54% better performance and nearly equal memory consumption when compared to the well known Doug Lea allocator in seven benchmark programs. Author Affiliation: (a) Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA (b) Department of Electrical Engineering, Iowa State University, 3216 Coover Hall, Ames, IA 50011, USA Article History: Received 15 August 2004; Revised 5 September 2005; Accepted 10 September 2005 Article Note: (footnote) [star] A preliminary version of this paper titled "A Hybrid Allocator" appeared in the Proceedings of 2003 IEEE International Symposium on Performance Analysis of Systems and Software, Austin, TX, 6-8 March 2003, pp. 214-221.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jet.2004.10.007 Byline: Noam Nisan (a), Ilya Segal (b) Abstract: We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to allocate L indivisible items between two agents, a price must be revealed for each of the 2.sup.L-1 bundles. We prove that all monotonic prices for an agent must be used, hence exponential communication in L is needed. Furthermore, exponential communication is needed just to ensure a higher share of surplus than that realized by auctioning all items as a bundle, or even a higher expected surplus (for some probability distribution over valuations). When the utilities are submodular, efficiency still requires exponential communication (and fully polynomial approximation is impossible). When the items are identical, arbitrarily good approximation is obtained with exponentially less communication than exact efficiency. Author Affiliation: (a) Institute of Computer Science, Hebrew University, Jerusalem, Israel (b) Department of Economics, Stanford University, Stanford, CA 94305, USA Article History: Received 10 February 2004; Revised 12 October 2004 Article Note: (footnote) [star] An earlier version of this paper was circulated under the title 'The Communication Complexity of Efficient Allocation Problems.'

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.robot.2006.01.002 Byline: Antonio Morales (a), Pedro J. Sanz (a), Angel P. del Pobil (a), Andrew H. Fagg (b) Abstract: This paper addresses the problem of designing a practical system able to grasp real objects with a three-fingered robot hand. A general approach for synthesizing two- and three-finger grasps on planar unknown objects is presented. Visual perception is used to reduce the uncertainty and to obtain relevant information about the objects. We focus on non-modeled planar extruded objects, which can represent many real-world objects. In addition, particular mechanical constraints of the robot hand are considered. First, a vision processing module that extracts from object images the relevant information for the grasp synthesis is developed. This is completed with a set of algorithms for synthesizing two- and three-finger grasps taking into account force-closure and contact stability conditions, with a low computational effort. Finally, a procedure for constraining these results to the kinematics of the particular hand, is also developed. In addition, a set of heuristic metrics for assessing the quality of the computed grasps is described. All these components are integrated in a complete system. Experimental results using the Barrett hand are shown and discussed. Author Affiliation: (a) Computer Engineering and Science Department, Universitat Jaume I, Castellon, Spain (b) School of Computer Science, University of Oklahoma, Norman, OK, USA Article History: Received 2 August 2004; Revised 22 December 2005; Accepted 13 January 2006

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.robot.2006.02.008 Byline: Yonghuai Liu (a), Baogang Wei (b), Longzhuang Li (c), Hong Zhou (a) Abstract: In this paper, we propose a novel algorithm for the automatic registration of two overlapping range images. Since it is relatively difficult to compare the registration errors of different point matches, we project them onto a virtual image plane for more accurate comparison using the classical pin-hole perspective projection camera model. While the traditional ICP algorithm is more interested in the points in the second image close to the sphere centred at the transformed point, the novel algorithm is more interested in the points in the second image as collinear as possible to the transformed point. The novel algorithm then extracts useful information from both the registration error and projected error histograms for the elimination of false matches without any feature extraction, image segmentation or the requirement of motion estimation from outliers corrupted data and, thus, has an advantage of easy implementation. A comparative study based on real images captured under typical imaging conditions has shown that the novel algorithm produces good registration results. Author Affiliation: (a) Department of Computer Science, The University of Wales, Aberystwyth, Ceredigion SY23 3DB, Wales, UK (b) College of Computer Science, Zhejiang University, Hangzhou 310027, PR China (c) Department of Computer Science, Texas A and M University, Corpus Christi, TX 78412, USA Article History: Received 7 June 2004; Revised 23 December 2005; Accepted 21 February 2006

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.jss.2005.04.005 Byline: Seng W. Loke Keywords: Prolog; Integration; Logic programming; Web computing; Peer-to-peer computing; Declarative programming Abstract: Web and peer-to-peer systems have emerged as popular areas in distributed computing, and their integrated usage permits the benefits of both to be exploited. While much work in these areas have utilized the imperative programming paradigm, the need for declarative programming paradigms is increasingly being recognized, not only for the often cited advantages such as a higher level of abstraction and specialized language features, but also to tackle the querying and manipulation of knowledge and reasoning with semantics that will be the mainstay of the proposed next generation of the Web and peer-to-peer computing. This paper presents an approach towards integrative use of the Web and peer-to-peer systems within a declarative programming paradigm. We contend that logic programming can be useful in peer-to-peer computing, especially for querying and representing knowledge shared over peer networks, and for scripting applications that involve sophisticated search behaviour over peer networks. As an example of peer-to-peer querying expressed in a logic programming language, we propose a simple extension of Prolog, which we call LogicPeer, to enable goal evaluation over peers in a peer network. Using LogicPeer, we outline how a peer-to-peer version of a Yahoo-like system can be built and queried, and several other applications that involve decentralized knowledge sharing. We then show how LogicPeer can be used with LogicWeb, a Prolog extension to access Web pages, thereby integrating peer-to-peer querying and Web querying in a common declarative framework. Author Affiliation: School of Computer Science and Software Engineering, Monash University, 900 Dandenong Road, Caulfield East, Melbourne, Vic. 3145, Australia Article History: Received 20 August 2003; Revised 6 April 2005; Accepted 6 April 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2005.04.040 Byline: Juan J. Cuadrado-Gallego (a), Miguel-Angel Sicilia (a), Miguel Garre (a), Daniel Rodriguez (b) Keywords: Parametric software effort estimation; Clustering algorithms; Software cost drivers; EM algorithm Abstract: Parametric software effort estimation models consisting on a single mathematical relationship suffer from poor adjustment and predictive characteristics in cases in which the historical database considered contains data coming from projects of a heterogeneous nature. The segmentation of the input domain according to clusters obtained from the database of historical projects serves as a tool for more realistic models that use several local estimation relationships. Nonetheless, it may be hypothesized that using clustering algorithms without previous consideration of the influence of well-known project attributes misses the opportunity to obtain more realistic segments. In this paper, we describe the results of an empirical study using the ISBSG-8 database and the EM clustering algorithm that studies the influence of the consideration of two process-related attributes as drivers of the clustering process: the use of engineering methodologies and the use of CASE tools. The results provide evidence that such consideration conditions significantly the final model obtained, even though the resulting predictive quality is of a similar magnitude. Author Affiliation: (a) Computer Science Department, Polytechnic School, University of Alcala. Ctra. Barcelona km. 33.6, 28871 Alcala de Henares, Madrid, Spain (b) Computer Science Department, University of Reading, Reading RG6 6AY, UK Article History: Received 15 February 2005; Revised 23 April 2005; Accepted 23 April 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.anbehav.2005.04.018 Byline: Duncan E. Jackson, Stephen J. Martin, Mike Holcombe, Francis L.W. Ratnieks Abstract: Pheromone trails provide a positive feedback mechanism for many animal species, and facilitate the sharing of information about food, nest or mate location. How long pheromone trails persist determines how long these environmental memories are accessible to conspecifics. We determined the time frame over which Pharaoh's ant colonies can re-establish a long-lived trail and how the behaviour of individual workers contributes to trail re-establishment. We used artificially constrained pheromone trails on paper to investigate trail longevity and individual responses. Trails formed by traffic of 1000-2000 ant passages could be re-established after 24h, and after 48h for 4000-8000 ant passages. Only 27.5% of individual foragers were highly successful in a bioassay testing the ability to detect trails established 24h earlier. Trail-finding ability was significantly correlated with a low antennal position. Long-lived trail detection scores increased significantly in 57% of foragers after 5h of food deprivation and isolation, but declined again after feeding. In a control study, only 9% of foragers changed their scores, when isolated with food present. A high degree of conservatism was found such that, regardless of treatment, 21% always failed the bioassay and 17% always succeeded. Our demonstration of long-lived components in Pharaoh's ant trails and of a behavioural specialization in 'pathfinding' shows that pheromone trails are more complex at the individual level than is generally recognized. Author Affiliation: (a) Department of Computer Science, U.K. (a ) Department of Animal and Plant Sciences, University of Sheffield, U.K. Article History: Received 10 May 2004; Revised 28 June 2004; Accepted 27 April 2005 Article Note: (miscellaneous) MS. number: 8122R

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.jss.2004.10.012 Byline: Min-Jae Lee (a), Kyu-Young Whang (a), Wook-Shin Han (b), Il-Yeol Song (c) Keywords: Spatial join; Corner transformation; Databases Abstract: A transform-space index indexes spatial objects represented as points in the transform space. An advantage of a transform-space index is that optimization of spatial join algorithms using these indexes can be more formal. The authors earlier proposed the Transform-Based Spatial Join algorithm that joins two transform-space indexes. It renders global optimization easy with little overhead by utilizing the characteristics of the transform space. In particular, it allows us to globally determine the order of accessing disk pages, which makes a significant impact on the performance of joins. For this purpose, we use various space filling curves. In this paper, we propose a new space filling curve called the adaptive row major order (ARM order). The ARM order adaptively controls the order of accessing pages and significantly reduces the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page) and the number of disk accesses for a given buffer size. Through analysis and experiments, we verify excellence of the ARM order when used with the Transform-Based Spatial Join. The Transform-Based Spatial Join with the ARM order always outperforms those with other conventional space filling curves in terms of both measures used: the one-pass buffer size and the number of disk accesses. Specifically, it reduces the one-pass buffer size by up to 25.9 times and the number of disk accesses by up to 2.11 times. We conclude that we achieve these results mainly due to global optimization of the order of accessing disk pages using an adaptive space filling curve. Author Affiliation: (a) Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of Korea (b) Department of Computer Engineering, Kyungpook National University, Sankyuk-Dong, Buk-Gu, Daegu 702-701, Republic of Korea (c) College of Information Science and Technology, Drexel University, Philadelphia, PA, USA Article History: Received 4 December 2003; Revised 18 October 2004; Accepted 18 October 2004

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.jss.2004.05.029 Byline: Shi-Wu Lo (a), Tei-Wei Kuo (a), Kam-Yiu Lam (b) Keywords: Real-time disk scheduling; RAID-0; Multi-disk scheduling Abstract: In this paper, we study the scheduling problem of real-time disk requests in multi-disk systems, such as RAID-0. We first propose a multi-disk scheduling algorithm, called Least-Remaining-Request-Size-First (LRSF), to improve soft real-time performance of I/O systems. LRSF may be integrated with different real-time/non-real-time single-disk scheduling algorithms, such as SATF and SSEDV, adopted by the disks in a multi-disk system. We then extend LRSF by considering the serving requests on-the-way (OTW) to the target request to minimize the starvation problem for requests that need to retrieve a large amount of data. The pre-fetching issue in RAID-0 is also studied to further improve the I/O performance. The performance of the proposed algorithm and schemes is investigated and compared with other disk scheduling algorithms through a series of experiments using both randomly generated workload and realistic workload. Author Affiliation: (a) Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, ROC (b) Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong Article History: Received 21 March 2003; Revised 23 May 2004; Accepted 23 May 2004

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2004.12.002 Byline: Hamid Beigy (a)(b), M.R. Meybodi (b)(c) Abstract: In this paper, we first propose a new continuous action-set learning automaton and theoretically study its convergence properties and show that it converges to the optimal action. Then we give an adaptive and autonomous call admission algorithm for cellular mobile networks, which uses the proposed learning automaton to minimize the blocking probability of the new calls subject to the constraint on the dropping probability of the handoff calls. The simulation results show that the performance of the proposed algorithm is close to the performance of the limited fractional guard channel algorithm for which we need to know all the traffic parameters in advance. Author Affiliation: (a) Department of Computer Engineering, Sharif University of Technology, Hafez Avenue, Tehran 15914, Iran (b) Institute for Studies in Theoretical Physics and Mathematics (IPM), School of Computer Science, Tehran, Iran (c) Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran Article Note: (footnote) [star] This research was in part supported by a grant from Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran.

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