Peer-to-peer systems or applications are distributed systems that have no centralized control or hierarchy. P2P systems have presented numerous advantages including but not limited to being cost-effective, providing redundant storage and their robustness to faults or intentional attacks.
As discussed in the paper [1], a fundamental problem in P2P systems is the process of locating the node that stores a particular data item. This was called the lookup problem, or simply stated as "how to find a particular data item that is stored at some dynamic set of nodes in the P2P systems". Various algorithms and approaches have already been proposed on how to solve this lookup problem such as through the use of structured lookups (i.e., maintaining a central database, use of hierarchy), symmetric lookup algorithms (i.e, broadcast approach, Freenet), or the combination of both. The paper also mentioned different algorithms that can scale well with large number of nodes; locate keys in low latency; handle node arrival and departures; ease individual maintenance of node's routing tables; and load balance of key distribution among nodes. Examples of these algorithms are the Use of Distributed Hash Table, routing in One Dimension and Routing in Multiple Dimension. Apparently, these algorithms have their own set of strengths and weaknesses.
The emegence of P2P systems in the growing internet technology has presented a lot of advantages (compared to disadvantages) to internet users worlwide. They have simplified file sharing and storage without having to rely on a centralized source of data. However, P2P systems need to also adapt to the growing number of internet users (increased in number of computers and users) and should be able to employ an efficient lookup algorithm that can scale well. In addition, P2P systems should also address legal battles on copyright infringements and abuse .
Reference:
[1] Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking Up Data in P2P Systems., Vol. 46, No. 2. February 2003.
Thursday, September 3, 2009
Review: "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"
In a peer-to-peer system, it is trivial to find the location of the source computer or node that carries/stores a particular data item. Discussed in the paper [1], is a distributed lookup protocol called Chord, which was described to provide and support a single operation. This operation involves the mapping of a key onto a node when given a key. As mentioned by the authors of the paper, the Chord protocol uses consistent-hashing technique (i.e., SHA-1) in assigning keys to Chord nodes, which in effect balances the load of the nodes since all of them receive the same number of keys.
Based on their conducted experiments and simulations, Chord was said to be adaptable to system changes. They also confirmed that Chord scales well with the number of nodes; recovers from large numbers of simultaneous node joins and failures; and returns most looups correctly.
Also, based on the discussed features of the Chord protocol, it appears that Chord does not only have a very well-thought system design but is also a very attractive protocol that can be implemented in a large-scale distributed peer-to-peer systems or applications.
Further, Chord seems to be suited in other applications such as in the field of mobile adhoc networks. In this regard, future researchers may extend Chord's functionalities in the implementation of MANET's.
Reference:
[1] Ion Stoica, Robert Morris, David Karger. M. Frans Kaashoek, and Hari Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. AACM SIGCOMM '01. August 2001.
Based on their conducted experiments and simulations, Chord was said to be adaptable to system changes. They also confirmed that Chord scales well with the number of nodes; recovers from large numbers of simultaneous node joins and failures; and returns most looups correctly.
Also, based on the discussed features of the Chord protocol, it appears that Chord does not only have a very well-thought system design but is also a very attractive protocol that can be implemented in a large-scale distributed peer-to-peer systems or applications.
Further, Chord seems to be suited in other applications such as in the field of mobile adhoc networks. In this regard, future researchers may extend Chord's functionalities in the implementation of MANET's.
Reference:
[1] Ion Stoica, Robert Morris, David Karger. M. Frans Kaashoek, and Hari Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. AACM SIGCOMM '01. August 2001.
Friday, July 3, 2009
Review: On Inferring Autonomous System Relationships in the Internet
The paper presented heuristic algorithms (i.e., Basic Algorithm, Refined Algorithm and Final Algorithm) that infer the augmented AS graph from BGP routing tables, which classified an interconnected AS pair into customer-provider, peering and sibling relationships [1].
They performed experimental study of AS relationships in the Internet using BGP routing tables, which were retrieved from the Route Views server in Oregon. Their inference results were verified with AT&T internal information and, overall, classifies more than 90.5% of AS pairs into provider-customer relationships, less than 1.5% of AS pairs into sibling relationships, and less than 8% of AS pairs into peering relationships. Also, they were able to identify routing table entries that stem from unusual AS relationships or router misconfigurations.
The rest of the paper elaborated on (a) overview of interdomain routing and related work, (b) AS relationships and routing table entry patterns, (c) heuristic algorithms for inferring AS relationships, (d) inferring AS relationships in the internet and (e) conclusion and future work.
The experiment is beneficial for ISPs in improving their routing policies and configuration (i.e., filtering of routes) as well as for planning their future contractual agreements with other ISPs. Ultimately, end-users will be mutually benefited if Internet routing will become more reliable. Hopefully, intelligent systems/applications can be incorporated in automating routing policies.
Reference:
[1] Lixin Gao, On Inferring Autonomous System Relationships in the Internet, IEEE/ACM Transactions on Networking, vol.9, no.6, p.733-745, December 2001
They performed experimental study of AS relationships in the Internet using BGP routing tables, which were retrieved from the Route Views server in Oregon. Their inference results were verified with AT&T internal information and, overall, classifies more than 90.5% of AS pairs into provider-customer relationships, less than 1.5% of AS pairs into sibling relationships, and less than 8% of AS pairs into peering relationships. Also, they were able to identify routing table entries that stem from unusual AS relationships or router misconfigurations.
The rest of the paper elaborated on (a) overview of interdomain routing and related work, (b) AS relationships and routing table entry patterns, (c) heuristic algorithms for inferring AS relationships, (d) inferring AS relationships in the internet and (e) conclusion and future work.
The experiment is beneficial for ISPs in improving their routing policies and configuration (i.e., filtering of routes) as well as for planning their future contractual agreements with other ISPs. Ultimately, end-users will be mutually benefited if Internet routing will become more reliable. Hopefully, intelligent systems/applications can be incorporated in automating routing policies.
Reference:
[1] Lixin Gao, On Inferring Autonomous System Relationships in the Internet, IEEE/ACM Transactions on Networking, vol.9, no.6, p.733-745, December 2001
Thursday, July 2, 2009
Review: Interdomain Internet Routing
The lecture entitled "Interdomain Internet Routing", provided a thorough understanding of how the internet works and operates in the real-world. It ponders on the interconnection of networks (i.e., how routers hook up with other routers and their respective exchange of routing protocols) in order to provide internet service [1].
The internet is an interconnection of unequal networks [2] and is administered by different domains and commercial enterprises. Hence, business competition and issues of trust arise amongst Internet Service Providers (ISPs) in providing global connectivity to their subscribers.
Throughout the lecture, more detailed Internet routing infrastructure and issues were discussed. Among the interdomain routing concepts addressed were Autonomous Systems (ASes), Inter-AS relationships and features of the Border Gateway Protocol (BGP). Under Inter-AS relationships, the lecture focused on peering vs transit and exporting and importing routes (route filtering). Also explained were design goals, protocol, disseminating routes within AS, policy expression (filters and rankings) and exchanging reachability of BGP. Failover and Security including Multi-homing, Convergence and Correctness Problems were also addressed.
It is noted that BGP is a simple protocol but its operation was said to be extremely complex. I wonder whether its design goals are still achievable with the growing internet demand? Will it still scale? How about being flexible? How will it handle security and failure? Are there any alternatives or recent modifications on its protocol? Is there a chance that the cost of internet service becomes cheaper or even free?
References:
[1] Hari Balakrishnan and Nick Feamster, "Lecture 4: Interdomain Internet Routing"
[2] http://www-inst.eecs.berkeley.edu/~ee122/sp04/network%20layer2_print.pdf
The internet is an interconnection of unequal networks [2] and is administered by different domains and commercial enterprises. Hence, business competition and issues of trust arise amongst Internet Service Providers (ISPs) in providing global connectivity to their subscribers.
Throughout the lecture, more detailed Internet routing infrastructure and issues were discussed. Among the interdomain routing concepts addressed were Autonomous Systems (ASes), Inter-AS relationships and features of the Border Gateway Protocol (BGP). Under Inter-AS relationships, the lecture focused on peering vs transit and exporting and importing routes (route filtering). Also explained were design goals, protocol, disseminating routes within AS, policy expression (filters and rankings) and exchanging reachability of BGP. Failover and Security including Multi-homing, Convergence and Correctness Problems were also addressed.
It is noted that BGP is a simple protocol but its operation was said to be extremely complex. I wonder whether its design goals are still achievable with the growing internet demand? Will it still scale? How about being flexible? How will it handle security and failure? Are there any alternatives or recent modifications on its protocol? Is there a chance that the cost of internet service becomes cheaper or even free?
References:
[1] Hari Balakrishnan and Nick Feamster, "Lecture 4: Interdomain Internet Routing"
[2] http://www-inst.eecs.berkeley.edu/~ee122/sp04/network%20layer2_print.pdf
Thursday, June 25, 2009
Review: The Design Philosophy of the DARPA Internet Protocols
Internet architecture has evolved through the years and is still evolving. It was originally designed to work in a military context through interconnection of existing networks to provide some larger service [1].
In the paper, “The Design Philosophy of the DARPA Internet Protocols” by David D. Clark [1], different design goals, protocols used, as well as the architecture and implementation of the Internet, were addressed. The author discussed the flexibility and survivability of the Internet, in terms of the various services it can offer and some tradeoffs (i.e., accountability). It was also emphasized that the fundamental architectural feature of the Internet was the use of datagrams. However, the author also suggested that there may be another building block that can provide enhanced performance than the datagram.
Indeed, the Internet has truly evolved and has been widely used globally. Its fundamental goals are continuously changing according to the needs of its users. But along with the Internet’s growing popularity comes numerous new challenges. Security, cost, administration and control are just few of the recent concerns on Internet use or abuse. Also, sophisticated types of communication services have been developed. Will the suggested Internet design still be as flexible as it was? Will it still be cost effective?
In the paper, “The Design Philosophy of the DARPA Internet Protocols” by David D. Clark [1], different design goals, protocols used, as well as the architecture and implementation of the Internet, were addressed. The author discussed the flexibility and survivability of the Internet, in terms of the various services it can offer and some tradeoffs (i.e., accountability). It was also emphasized that the fundamental architectural feature of the Internet was the use of datagrams. However, the author also suggested that there may be another building block that can provide enhanced performance than the datagram.
Indeed, the Internet has truly evolved and has been widely used globally. Its fundamental goals are continuously changing according to the needs of its users. But along with the Internet’s growing popularity comes numerous new challenges. Security, cost, administration and control are just few of the recent concerns on Internet use or abuse. Also, sophisticated types of communication services have been developed. Will the suggested Internet design still be as flexible as it was? Will it still be cost effective?
References:
[1] D. D. Clark, "The design philosophy of the DARPA Internet protocols," ACM SIGCOMM Computer Communication Review, vol. 18, issue 4, August 1988.
Review: End-to-End Arguments in System Design
It is essential for system designers to feasibly and reasonably organize placements of functions among the different modules of a distributed computer system in order to achieve enhanced performance results. While doing so, it is not only sound but also beneficial in the application development if system designers are guided with established system design principles.
In the paper, “End-to-End Arguments in System Design” by J.H. Saltzer, D.P. Reed and D.D. Clark [1], a design principle called end-to-end argument was presented. The paper provided numerous examples of end-to-end arguments such as “careful file transfer”, “data encryption” and “duplicate message suppression” among others. The end-to-end argument opposes low-level function implementation whereas it suggests that functions be carefully placed at the endpoints. But is it always true that functions are strategically better placed at the higher-levels? Also, how do we identify the endpoints?
In some of the examples discussed, it is apparent that realizing the potential threats and applying the possible adjustments are very important in the design process. Such tradeoffs like reliability and performance exist. Do we really have to choose performance over reliability or can we get both?
In the paper, “End-to-End Arguments in System Design” by J.H. Saltzer, D.P. Reed and D.D. Clark [1], a design principle called end-to-end argument was presented. The paper provided numerous examples of end-to-end arguments such as “careful file transfer”, “data encryption” and “duplicate message suppression” among others. The end-to-end argument opposes low-level function implementation whereas it suggests that functions be carefully placed at the endpoints. But is it always true that functions are strategically better placed at the higher-levels? Also, how do we identify the endpoints?
In some of the examples discussed, it is apparent that realizing the potential threats and applying the possible adjustments are very important in the design process. Such tradeoffs like reliability and performance exist. Do we really have to choose performance over reliability or can we get both?
References:
[1] J. H. Saltzer, D.P. Reed and D. D. Clark, "End-to-end arguments in system design," ACM Transactions in Computer Systems, vol. 2, no. 4, pp. 277-288, November 1984.
Subscribe to:
Posts (Atom)