Week ending 30th April

The whole week was spent in coding and testing the new algorithm I developed from the previous week's research. The SpringEq algorithm I call.

I am testing the new algorithm

• In landmark placement scenario
• Test for the convergence speed (no of iteration), computational speed, and accuracy.
• Tested with synthetic network and all-to-all Planetlab ping data
• When using Planetlab data smoothing is required. Did some review and testing of existing approaches (absolute average, moving average, exponential weighted average, and double exponential weighted average) and selected the exponential smoothing for my purpose.

The testing is not completely finished.

Also by the end of the week, I realized the need for comparing the simplex and spring algorithms for the node placement application. I am doing that too now.

Read more!

Week Ending 23rd April

This week was spent on analyzing the distributed landmarking algorithm. I searched for clues in the Internet for a proper way to analyze a spring network. Surprisingly the google search did not give enough reference points. I had to refer a number of papers along the way. And finally hit a paper from Fluid dynamics that helped me a lot in resolving my problem. The rest of the week spent on refreshing my linear algebra knowledge - solving simultaneous equation. Also had a discussion with prof on Friday and drafted a small problem statement document to state my new solution.

Read more!

Distributed Landmarking: Spring Network in Equilibrium

After two days of search for a material on analysis spring network, I came across a paper from Fluid mechanics.
Frederic. J. Blom, "Considerations on Spring Analogy", International Journal for Numerical Methods in Fluids, Vol. 32, pp. 647-668, 2000.
One of my previous major struggle is to find the equilibrium condition in a spring network. From this paper, I found out that the condition is "the resultant force in every node is zero"! It's embarrassing how I didn't think about it (or actually forgot it)!!.

The major idea I got from this paper is that a spring network can be modeled as linear simultaneous equations (variables are the displacement vectors). Once modeled as simultaneous equations, we can use iterative methods to solve this system. Iterative methods are preferred here as they can be easily fit as a distributed algorithm.

The thing that puzzles me is why no body approach this as linear simultaneous equations. Everybody tried optimization approaches to minimize the stress between nodes or the energy in the system. Solving the linear simultaneous equations provides the same results: minimize the stress/energy.

Jacobi method is one way of solving the linear simultaneous equations iteratively. Actually, Vivaldi's Spring algorithm is very close to this Jacobi iteration, even though Vivaldi does not recognize this so. Jacobi iteration still needs O(I*n^2) messages, where I is the number of iterations. Fortunately there are some fast iterative methods such as accelerated Gauss-Seidel method to reduce I. The advantage is much reduced computational complexity; there is no complex optimization procedure, but just multiplications and additions.

Read more!

Review: Big-Bang Simulation

Yuval Shavitt and Tomer Tankel, "Big-Bang Simulation for Embedding Network Distances in Euclidean Space", IEEE Infocom, 2003.

A rather complex paper on mapping the Internet nodes on to a Cartesian space. In this work all the nodes are treated as molecules floating in an imaginary Euclidean space acting upon repulsive/attractive forces created by one on another. As all the nodes' initial position is at the origin and then they move away under these forces, the algorithm is called big-bang simulation (BBS). The fundamental principle of the BBS algorithm is to minimize the energy in the system; the energy can be both potential energy due to the inter-molecular forces and kinetic energy due to the movement of the molecules under these forces.

The paper elaborately explain the energy equations used in the algorithm. However, no mathematical proof is given to ensure a convergence. Each iteration involves four phases each applying the energy equations to minimize the total energy or tuning the coordinates so that tension is distributed evenly. Communication complexity is O(I n^2), where I is the number of iteration. Still at each step, message complexity is 4n^2.

Read more!

Surface Reconstruction

When searching for some clue on analysis spring systems, I came across this thesis:
Hugues Hoppe, "Surface Reconstruction from Unorganized Points", Ph.D. thesis, University of Washington, 1994.

The content of the paper is mostly not of my interest as it is a paper on Image Processing area. I also got disappointed about their spring based algorithm. They model the surface mesh of a computer image as a spring system. One of constraints in the surface reconstruction is to reduce the total energy stored in this spring system. However, I got disappointed to see that they are using the potential energy stored in the spring system just as to tune their other node/edge adjustment procedure. They are not using the spring system directly to adjust the surface mesh.

So again nothing useful for my work from this thesis.

Read more!

Review: Hydrodynamic Load Balancing

Following the discussion on the need for a scalable distributed landmarking algorithm, I came across these two papers. These are not directly related to landmarking problem, but address the problem of distributed load balancing with a potential energy based approach. Even though their potential energy comes from hydrodynamic point of view, I wonder whether that can be twisted into my spring system.

• C. Hui and S.T. Chanson, "Hydrodynamic Load Balancing", IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 11, Nov. 1999
• C. Hui and S.T. Chanson, "A Hydro-dynamic Approach to Heterogeneous Dynamic Load Balancing in a Network of Computers", In Proceedings of the International Conference on Parallel Processing, 1996

The first paper goes deep into the theory behind the proposed mechanism proving the convergence and accuracy of the algorithm. The other paper describes the algorithm as it to be implemented in the system.

In the hydrodynamic approach, the network is considered as graph of V nodes and E edges. Each node is assumed to have a water cylinder and the load in a node is represented by the liquid contained in the cylinder; The cross section of the cylinder is represented by the capacity of the node. Each edge in E is assumed to be a liquid channel connecting the cylinders at the end nodes. The paper proves that the load sharing becomes fair when the global potential energy presented by the liquid columns is minimized, in another words, when the heights of the liquid columns are same in all cylinders. The papers provides a systematic way of transfer of liquids between cylinders that leads to this equilibrium condition. And it is proven that this convergence will occur within a finite period of time.

There are two issues regarding applying the same theory in my work:

1. The potential energy in the hydrodynamic system is stored in the cylinder, i.e. in the nodes of the graph whereas in the spring system, the energy is stored in the springs, i.e. in the edges. Further, we don't have the "equal liquid column height when equilibirium" type of phenomena in a spring system; i.e. we can't claim at minimum potential energy all the spring will have same stretch factor, same force, or anything (or I couldn't think about any).
2. The distributed load balancing mechanism is more concerned about devising a distribute scheme that reacts to the load changes dynamically than producing an algorithm that produce less message overhead.

So still the distributed landmarking problem remains open.

Read more!

Week ending 16th April

This is week is kind of unproductive in terms of research: I had to spent almost all the week in marking the assignments of the OS course I am TAing. So, this week:

• Read PCoord paper.
• Had discussion about landmarking algorithm with Yuanyuan and prof.
• Drafted an outline for the journal paper we are planning to publish and had discussion about it with prof.

Read more!

Distributed Landmarking

We are posed with a problem when Yuanyuan implemented the distributed landmarking in Planetlab. The distributed landmarking, the mechanism for placing the landmarks themselves at appropriate position in the Cartesian space, is found out to be very slow and incur a large message overhead. A quick analysis of the algorithm immediately showed that the communication complexity of this algorithm is of O(s*n^2), where s is the number of convergence steps and n is the number of landmarks. This presented us with a need of designing a new algorithm for distributed landmarking.

There are two things to be noted from the message complexity of the spring-based distributed landmarking: (a) we need an algorithm that is fast (so that the convegence step is less); (b) probably the algorithm should manage to run by contacting only a subset of landmark nodes.

One simple solution is to collect all the information and run the optimization algorithm locally. That is, all the nodes ping others to find out others' coordinates and ping distances to them. Now all the nodes have an array of ping distances. In the second iteration they exchange the array with every others so that, at the end of the second iteration, every node has (n x n) ping distance matrix and an array of coordinates of all the nodes. Now all the nodes can individually carry out the optimization algorithm to find out the coordinates of the nodes. In this way, computational complexity per node is increased, but the number of message needed is only 2n^2. However, the messages can be huge and the algorithm is not truly distributed (each node doing a part of the total work).

Another approach is to use the PCoord method: in each iteration, a node use only a part of the total landmarks to position itself and this set changes with iteration. The message complexity will be O(s*n*k), where k is the number of nodes contacted each time. Even though this method can reduce the message complexity, there is no guaranttee for that (i.e. s can be arbitarily large).

Therefore, finding a proper distributed landmarking algorithm is still an open problem. Prof suggested an idea of thinking this optimization procedure as reducing the total potential energy stored in the (imagined) spring network. Even though the spring algorithm does approach in this way, it is mostly concerned about reducing local energy than the global energy. I am thinking....

Read more!

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.

Read more!

Optimization Algorithims in RAN

Until now, I was in favour with using Spring algorithm in RAN. Long time back, I tested Spring algorithm against Simplex Downhill and found that they perform with comparable accuracy. But Spring requires much lesser amount of coding and theoretically has low order of complexity.

However, for curiosity shake (or to further validate my argument), I implemented Simplex algorithm too for landmark aided positioning (LAP). And suprisingly found out my simulation sped-up hundreds of times faster (10 min compared to four hours)!

When discussed with prof, we agreed that even though Simplex is more complex in theory, practically it can be fast. This is what many literature claims too (I spent some times yesterday reading some books om Simplex). On the other hand, Spring can be slow in practice even though it is very easy to implement.

Further discussion with prof revealed that I can actually change my stopping creteria for the Spring algorithm to make it faster. Earlier I was checking the convergence after each move imposed by each landmarks. Actually it is the resultant movement, i.e. the movement after adjustments for all the landmarks, is the one to be checked for convergence. I have to compare the results of this new spring algorithm and simplex algorithm.

Read more!