|
Literature Review
:
This literature review is categorized in following sections: |
| a. | Maximum length subsequence |
| b. | Predictive power management |
| c. | Power consumption and conservation of the Internet, networks and networking equipments |
| d. | Dynamic power management and its impact |
| e. | Optimal algirithms for power management |
| f. | P2P Networks and Bittorrent |
a. Maximum length subsequence: |
| [1] |
W. L. Ruzzo and M. Tompa,
"A linear time algorithm for finding all maximal scoring subsequences", in Seventh International Conference on Intelligent Systems for Molecular Biology, pp. 234 - 241, 1999.
The authors have presented an algorithm, that finds nonoverlapping contiguous subsequences having greatest total scores. The algorithm runs linearly.
The algorithm provides a contribution in analysing (biological) sequences.
|
| [2] |
Anders Bergkvist, Peter Damaschke,
"Fast algorithms for finding disjoint subsequences with extremal densities, Pattern Recognition", Vol. 39, Issue 12, pp. 2281-2292, Dec. 2006.
The authors have derived a fast algorithm for the problem: "Given a set of n points on the real line and two parameters s and p, now find s disjoint intervals of maximum total length
that contain at most p of the given points". The algorithm mainly contributes to improve timebound in comparision to the straightforward dynamic programming algorithm.
|
| [3] |
L. Allison and T.I. Dix,
"A Bit-String Longest-Common-Subsequence Algorithm", presented at Inf. Process. Lett., pp.305-310, vol. 23, Dec. 1986.
A longest-common-subsequence algorithm is described which operates in terms of bit or bit-string operations. It offers a speedup of the order of the word-length
on a conventional computer. The longest-common-subsequence (LCS) problem is to find the maximum possible length of a common subsequence of two strings, 'a' of length |a| and 'b' of length |b|.
|
| [4] |
David Liben-Nowell, Erik Vee, and An Zhu,
"Finding Longest Increasing and Common Subsequences in Streaming Data", Technical Report MIT-LCS-931, Laboratory for Computer Science MIT, Nov. 2003.
In this paper, the authors have present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS)
problems in the data streaming model.
|
| [5] |
K. Perumalla, N. Deo,
"Parallel algorithms for maximum subsequence and maximum subarray", Parallel Process. Lett., Vol. 5(3) pp. 367–373, 1995.
The authors have present two O(log n)-time parallel algorithms: one for finding the maximum subsequence sum of a given sequence,
and the other for finding the maximum subarray sum of a given array.
|
| [6] |
Algorithmist, "Longest Common Subsequence,
http://www.algorithmist.com/index.php/Longest_Common_Subsequence"
Describes the problem of finding the longest common subsequence of two sequences of items
|
| | |
| | Goto top ⇑ |
b. Predictive power management: |
| [1] |
C. Hwang, and A. C. Wu,,
"A predictive system shutdown method for energy saving of event-driven computation", Proceedings of the IEEE/ACM, November 1997, ACM, pp. 226-241.
The paper presents a system level power management technique for energy conservation when running event
driven application. The authors have presente a new predictive system-shutdown method to exploit sleep modes for
the purpose of energy saving.
|
| [2] |
F. Douglis, P. Krishnan, and B. Marsh,
"Thwarting the power-hungry disk" , Proceedings of the USENIX, Winter 1994, USENIX Association, pp. 1-15.
The paper presents a simulation technique for minimizing the power consumption of hard disks on mobile computers by spinning the disk only
when necessary. The authors have investigate two types of algorithms for spinning a disk up and down: off-line, which can use future
knowledge, and on-line, which can use only past behavior.
|
| [3] |
Y. Lu, E.Chung, T. Simunic, L. Benini, and De Micheli,
"Quantitative comparison of power management algorithms", Proceedings of the Conference on Design, Automation and Test, March 2000, ACM pp. 20-26.
This paper quantitatively compares the power saving and performance impact of different algorithms on hard disks of a notebook and desktop computers.Firstly,
a framework in Windows NT has been built to implement different power managers running realistic workloads and directly interacting with users. Secondly, define the
performance degradation that reflects user perception and finally the analysis of power saving and performance are the main contributions of the paper.
|
| [4] |
E. Chung, L. Benini, and De Micheli,
"Dynamic power management using adaptive learning tree", Proceedings of the 1999 IEEE/ACM international Conference on Computer-Aided Design, November 1999, pp. 274-279.
The authors have presented a novel Dynamic Power Management scheme based on idle period clustering and adaptive learning trees. Moreover, the paper also provide
a design guideline for applying the scheme to components with multiple sleep states.
|
| [5] |
E. Chung, L. Benini, A. Bogiolo, and G. De Micheli,
"Dynamic power management for non-stationary service requests", Proceedings of the 1999 IEEE/ACM international Conference on Design, Automation and Test, 1999, pp. 1345-1361.
This paper work have presented an online adaptive Dynamic Power Management scheme for systems that can be modeled as finite-state Markov chains. Online adaptation is required
to deal with initially unknown or nonstationary workloads, which are very common in real-life systems. Moreover a two-dimensional interpolation technique is introduced to obtain
adaptive policies from precomputed look-up table of optimum stationary policies.
|
| | |
| | Goto top ⇑ |
c. Power consumption and conservation of the Internet, networks and networking equipments |
| [1] |
M. Gupta, and S. Singh,
"Greening of the internet", Proceedings of the SIGCOMM, August 2003, ACM, pp. 19-26.
This seminal position paper demonstrate the problem of excessive energy consumption in the Internet and proposes the idea of changing routing protocol inorder to
determine the sleeping strategy to make it energy economic.
|
| [2] |
M. Gupta, and S. Singh,
"Using Low-Power Modes for Energy Conservation in Ethernet LANs", Proceedings of the 26th IEEE International Conference May 2007, IEEE, pp. 2451-2455.
The authors have proposed methods that allow detecting the idle or under-utilized period of the link in order to obtain energy conservation with a little impact on loss or delay.
|
| [3] |
M. Rodriguez-Perez, S. Herreria-Alonso, M. Fernandez-Veiga, C. Lopez-Gracia
"Improved Opportunistic Sleeping Algorithms for AAN Switches", Proceedings of the IEEE GLOBECOM, December 2009, IEEE.
Two algorithms for opportunistically powering down unused network interfaces in order to save some of the wasted energy when the computing devices are under-utilized,
are introduced in this proceeding paper. The new algorithms can be easily implemented in Ethernet hardware to exploit around 75% of power saving with respect to the
non-power aware Ethernet card for typical workloads.
|
| | |
| | Goto top ⇑ |
d. Dynamic power management and its impact |
| [1] |
T. Simunic, L. Benini, P. Glynn, and G. De Micheli,
"Dynamic Power Management for Portable Systems", Proceedings of the SIGCOMM 6th Annual Int'l Conf. MOBICOM, August 2000, ACM, pp. 11-19.
This Proceeding conference paper presents a new optimal Dynamic Power Management (DPM) policy for portable systems. The policy based on the Time Indexed Semi-Markov
Decision Process (TISMDP) that has been used to derive optimal policies for DPM in portable systems.
|
| | |
| | Goto top ⇑ |
e. Optimal algirithms for power management |
| [1] |
P. Krishnan, M.P. Long, and S. J. Vitter,
"Adaptive Disk Spindown Via Optimal Rent-To-Buy in Probabilistic Environments.", Technical Report. Duke University TR-95-08, pp. 31-56.
This technical report is the study of algorithms that make a sequence of single rent-to-buy decisions, using the assumption that the resource use times are independently drawn
from an unknown probability distribution. This framework helps to model the system problems such as disk spindown problem in mobile machine.
|
| | |
| | Goto top ⇑ |
f. P2P Networks and Bittorrent |
| [1] |
B. Cohen,
"Incentives Build Robustness in BitTorrent", in Proceedings of Workshop on Economics of Peer-to-Peer Systems (P2PEcon’03),Berkeley, CA, USA, June, 2003.
In this paper, the author has explained how economic methods are used to achieve robustness and resource
utilization better than other cooperative techniques.
|
| [2] |
Tian, Y.; Wu, D.; Ng, K. W.; ,
"Modeling, Analysis and Improvement for BitTorrent-Like File Sharing Networks", INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings , vol., no.,
pp.1-11, April 2006.
In this paper, the Authors have presented a simple mathematical model for studying the
performance of the BitTorrent file sharing system. The authors are especially interested in
the distribution of the peers with different states of the download job completeness.
|
| [3] |
Huang, N., Chu, Y., Tsai, C., Huang, W., and Tzeng,
"A Resource-Efficient Traffic Localization Scheme for Multiple BitTorrents", Proceedings of the 2009 IEEE international Conference on Communications June 14-18 2009, IEEE, pp. 1393-1397.
In this paper the authors has probosed an effective B-Proxy scheme to evaluate through realistic
simulation on PlanetLab, where hundreds of BitTorrent clients were executed during experiment. The simulation results
show that more than thirty percent of inter-ISP traffic could be saved in a torrent with relatively small cache size
consumend which is only eighth times of that original file.
|
| [4] |
Cuevas, Ruben; Laoutaris, Nikolaos; Yang, Xiaoyuan; Siganos, Georgos; Rodriguez, Pablo; ,
"Deep Diving into BitTorrent Locality", ACM, SIGMETRICS'10, 14-18 June 2010
In this paper work, the authors have aim to answer some critical questions such as "What is the minimum
and the maximum transit traffic reduction across hundreds of ISPs?" and so on...
|
| [5] |
Leung, A.K.-H.; Yu-Kwong Kwok; ,
"On Localized Application-Driven Topology Control for Energy-Efficient Wireless Peer-to-Peer File Sharing", Mobile Computing, IEEE Transactions on , vol.7, no.1, pp.66-80, Jan. 2008.
The authors have proposed a new protocol, which consists of two components, namely, Adjacency Set Construction (ASC)
and Community-Based Asynchronous Wakeup (CAW). The new protocol is shown to be able to enhance the fairness and provide an incentive
mechanism in wireless P2P file sharing applications. It is also capable of increasing energy efficiency.
|
| [6] |
Xie, H., Yang, Y. R., Krishnamurthy, A., Liu, Y. G., and Silberschatz, A. ,
"P4P: Provider Portal for Applications", SIGCOMM Comput. Commun. Rev. 38, 4 (Oct. 2008), 351-362.
In this paper, a simple architecture called P4P has been proposed to allow for more effective cooperative
traffic control between applications and network providers.
|
| [7] |
Blackburn, J.; Christensen, K.;,
"A Simulation Study of a New Green BitTorrent", Communications Workshops, 2009. ICC Workshops 2009. IEEE International Conference on , vol., no., pp.1-6, 14-18 June 2009.
In the paper, the authors have shown that a simple changes to the BitTorrent protocol, including long-lived knowledge of
sleeping peers and a new wake-up semantic, can enable clients to sleep when not actively downloading or uploading yet still be responsive
swarm members.
|
| [8] |
Anastasi, G.; Conti, M.; Giannetti, I.; Passarella, A.; ,
"Design and evaluation of a BitTorrent proxy for energy saving", Computers and Communications, 2009. ISCC 2009. IEEE Symposium on , vol., no., pp.116-121, 5-8 July 2009.
In this paper, the authors have proposed a novel proxy-based BitTorrent architecture.
BitTorrent users can delegate the download operations to the proxy and then power off, while the proxy downloads the requested files.
|
| [9] |
Yang, W.; Abu-Ghazaleh, N.; ,
"GPS: A General Peer-to-Peer Simulator and its Use for Modeling BitTorrent", Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2005. 13th IEEE International Symposium on , vol., no., pp.
425- 432, 27-29 Sept. 2005.
This paper presents an extensible framework for simulating P2P networks efficiently and accurately. Efficiency is accomplished
by using message level simulation rather than packet level simulation, accuracy is maintained by tracking the network infrastructure and using a
flow model to accomplish accurate estimate of the message behaviour. The second contribution of this paper is to model the BitTorrent (BT)protocol.
|
| | |
| | Goto top ⇑ |
| | |
| | |
|