Review: PCoord
Li-wei Lehman and Steven Lerman, "PCoord: Network Position Estimation Using Peer-to-Peer Measurements", Proceedings of the Third IEEE International Symposium on Network Computing and Applications (NCA'04)
PCoord is another network positioning system for P2P networks. Similar to the GNP, each node in the system uses a set of landmarks, called as waypoints here, to find its coordinates in a global Cartesian space. The mechanism used for this positioning is the same as in GNP: pinging the waypoints and running a simplex downhill.
The novelity of PCoord comes in its algorithm to select the waypoints. Instead of having a fixed set of landmarks as in GNP, which the PCoord argues as introducing bottlenecks and making the system vulnarable to failures, PCoord allows any node to function as a waypoint to another peer and introduces three waypoint selection algorithms for a node to choose its waypoints dynamically. The governing argument in these algorithms is that the positioning algorithm performs better when the waypoints are well dispersed in the network.
The first algorithm, the RandPCoord, allows a node to randomly choose its waypoints from the set of already mapped peers.
In ClusterPCoord scheme, each node keeps a PCoord map of known PCoord nodes (list of nodes and their coordinates). A new node joining the system can ask a PCoord node for the PCoord map. The new node can then select a well-dispersed set of waypoints from the received PCoord map.
The issue is the ClusterPCoord scheme is that each node has to maintain the PCoord map which can require the large storage space. The ActivePCoord alleviates this problem. it assumes that each node knows a intial set of waypoints to commense operation. Later, each node uses gossiping to exchange information about other peers so that each node can select a better dispersed set of waypoints in the next iteration.
The paper clearly describes three attractive algorithms that helps to choose a set of well-dispersed waypoints (landmarks). In the performance section, it provides an simulation proof that accuracy of the coordinate system is improved when the landmarks are well dispersed.
Despite of the theory behind these algorithms being attractive, the performance of these algorithms are not that much differnt from a fixed landmark scheme (ofcourse properly dispersed). RandPCoord fails to perform better than the FixedLM scheme; ClusterPCoord performs a little better than FixedLM, but with a the cost of exessive storage in each node for PCoord map; ActivePCoord also barely performs better than FixedLM and that is after 20th iteration and for each iteration using 10 waypoints - message overhead incurred during these iterations is hard to be justified against its slightly increased performance.
The clustering mechanism used in ClusterPCoord is conceptually completely different than that is used in CLAP. Clustering in CLAP is used to adjust the coordinates against possible error caused by errorenous ping values; This clustering does not influence the landmark selection procedure. Further, the LAP being as a part of RAN has its own advantages because the LAP scheme need not enforce algorithms like ActivePCoord to find a dispersed set of landmarks. It comes free with the RAN routing infrastructure. The same with finding the closest neighbor (PCoord has seperate algorithm for this). This reduces the per-node storage requirement and message overhead by many folds.
PCoord is another network positioning system for P2P networks. Similar to the GNP, each node in the system uses a set of landmarks, called as waypoints here, to find its coordinates in a global Cartesian space. The mechanism used for this positioning is the same as in GNP: pinging the waypoints and running a simplex downhill.
The novelity of PCoord comes in its algorithm to select the waypoints. Instead of having a fixed set of landmarks as in GNP, which the PCoord argues as introducing bottlenecks and making the system vulnarable to failures, PCoord allows any node to function as a waypoint to another peer and introduces three waypoint selection algorithms for a node to choose its waypoints dynamically. The governing argument in these algorithms is that the positioning algorithm performs better when the waypoints are well dispersed in the network.
The first algorithm, the RandPCoord, allows a node to randomly choose its waypoints from the set of already mapped peers.
In ClusterPCoord scheme, each node keeps a PCoord map of known PCoord nodes (list of nodes and their coordinates). A new node joining the system can ask a PCoord node for the PCoord map. The new node can then select a well-dispersed set of waypoints from the received PCoord map.
The issue is the ClusterPCoord scheme is that each node has to maintain the PCoord map which can require the large storage space. The ActivePCoord alleviates this problem. it assumes that each node knows a intial set of waypoints to commense operation. Later, each node uses gossiping to exchange information about other peers so that each node can select a better dispersed set of waypoints in the next iteration.
The paper clearly describes three attractive algorithms that helps to choose a set of well-dispersed waypoints (landmarks). In the performance section, it provides an simulation proof that accuracy of the coordinate system is improved when the landmarks are well dispersed.
Despite of the theory behind these algorithms being attractive, the performance of these algorithms are not that much differnt from a fixed landmark scheme (ofcourse properly dispersed). RandPCoord fails to perform better than the FixedLM scheme; ClusterPCoord performs a little better than FixedLM, but with a the cost of exessive storage in each node for PCoord map; ActivePCoord also barely performs better than FixedLM and that is after 20th iteration and for each iteration using 10 waypoints - message overhead incurred during these iterations is hard to be justified against its slightly increased performance.
The clustering mechanism used in ClusterPCoord is conceptually completely different than that is used in CLAP. Clustering in CLAP is used to adjust the coordinates against possible error caused by errorenous ping values; This clustering does not influence the landmark selection procedure. Further, the LAP being as a part of RAN has its own advantages because the LAP scheme need not enforce algorithms like ActivePCoord to find a dispersed set of landmarks. It comes free with the RAN routing infrastructure. The same with finding the closest neighbor (PCoord has seperate algorithm for this). This reduces the per-node storage requirement and message overhead by many folds.
posted by Unknown at
12:05 PM
0 Comments:
Post a Comment
<< Home