Thursday, October 30, 2008

Chord: A scalable Peer to Peer lookup service for Internet Applications

This paper goes into more depth specifically about the Chord routing method, which is a skiplist-like routing, according to the previous article. The paper lists the goal of Chord, which is to address load balancing, decentralization of control, scalability, availability and also flexible naming. The Consistent hashing is what takes care of the distributed and load balancing, since it can provide any joining node a distributed way of locating evey key in the network. Chord offers a simple way of searching for data in distributed P2P system. It also provides mechanism to continue its correctness of functionality despite partial correctness of a node's information.

I don't know much about P2P applications or the underlying functions of them, but from the previous paper and this one it seems there are a lot of challenges that need to be solved. And the distributed property of P2P applications seem like a very propelling motivation, to be able to spread data quickly from a distributed source. Chord is looking at the searching function of P2p applications, but other issues i image also can be looked into, including how to efficiently download data, and algorithms to distribute that.

Looking up Data in P2P Systems

This article gives a brief introduction to some of the difficulties of P2P computing. It does first list the attractive reasons for P2P systems, including fault tolerant because of its decentralized nature. The challenge of course is how to efficiently use the distributed system. The article specifically talks about the look up problem of trying to find data in this huge distributed system. A broad range of techniques are evaluated and compared to each other, and briefly explained. All of them are based on a distributed hash table. These include the Chord skiplist like routing, tree-like routing, and a multi-dimension routing.

It's hard to determine which routing method is the best, as the summary of the article lists several open questions about the fault tolerance, routing, and security behaviors for malicious nodes. In the article, it does acknowledge the fact that most people directly associate p2p applications with illegal file sharing, including napster or KaZaa. The paper mentions that there are other applications, but i'm not sure if i can think of any off the top of my head...

Tuesday, October 28, 2008

Resilient Overlay Networks

This paper presents an overlay network that is designed for the purpose of detecting faults in the network, including outages connections and nodes. Overlay networks introduces an application layer overlay on top of the current network. This allows for control over the forwarding and routing between the specific nodes that have this application layer overlay network. The authors use this idea to create a fault detection and correction network named Resilient Overlay Networks.

Each RON node detects problems by aggressively probing and monitoring the paths connecting the nodes. RON nodes and forward and route to other RON nodes depending on the route condition. RON networks listed 3 design goals. First, it wanted fast failure detection and recovery. This meant they needed to be constantly monitoring the links. Second, they wanted a tighter Integration with the application, which allow the applications themselves to specify at what level the fault tolerant should be. Third, they wanted a more expressive policy routing, which is allowed at the application layer by changing the routing in between the RON nodes. Several interesting research questions arose, including the performance metric in which they select the routes and paths, and how they categorize the routes as "good."

The results of the evaluation came out to be pretty good, as it only took on average 18 seconds to detect and recover from a fault, which is better than BGP-4. This paper offers a very interesting overlay network, and it even categorizes the latencies of each path. It seems like this would be a great way to test out different network service and protocols.

Monday, October 27, 2008

Active Network Vision and Reality: Lessons from a capsule based system

This paper written by David Wetherall is a reflection after their creation of ANTS active network toolkit. The idea of Active Networking was first described in a paper in 1996, also by the same author. Active networking allows for customized programs to be executed within the network. This allows for easy creation of new Internet services, including custom forwarding and routing tables at each node. But active networking has also been controversy because of performance and security concerns. However, the author in this paper tries to reflect upon the experience of implementing an active network.

He first explains the essentials of active network, and how it works. Basically there are active nodes in the network which acts as a programmable router. Users are provided an interface to program "capsules" which are passed around the network. As the capsules travel through active nodes, different services can occur, which the users can specify. Several advantages of this approach includes it's ability for gradual deployment, since not all nodes need to be active nodes. We are able to gradually deploy this service, and only the nodes that belong to the active node set will process the capsules. The implementation of active networks also contains some inherent properties. The author lists 4, which are expressible, compact, fast, incrementally deployable. Expressible is the fact that the service a user wishes to create must be expressed by the API and interface which is provided to the user. It must be compact because there is a limit of 16KB of code so the network isn't flooded with service code. It must be fast because the routine must run to completion at each node. And lastly, it must be incrementally deployable, meaning that the service must not fail if there are nodes that aren't active. Currently, it still seems that performance and the factors above will limit the usefulness of active networking. but with more research and time, it is a good platform to experiment with new services from the network.

Thursday, October 16, 2008

Directed Diffusion: A Scalable and Robust Comunication Paradigm for Sensor Networks

This paper also talks about a coordinated communication of sensor nodes in a sensor network that requires low power. The idea is similar to the TAG paper in that no centralized server should receive all the data onces it makes a request, because this consumes too much power. Thus, they call it a data centric communication method, is basically that a requester requests the data by a named attribute, and then the request is propagated throughout the network, with nodes sending the request to its neighbors, and then receiving the data and caching it in the local nodes. The terms used in this paper i found very confusing, which made this paper very hard to read. Nodes send "interests" which are basically just requests, through the network. There is also a "gradient" which keeps track of the freshness of data that's stored in the local cache. The "gradient" also determines when to evict a data in its cache.

The testing of the paper didn't take into account of congestion. Another question i had along those lines was the issue of the caches. It seems like if a lot of requests are made through certain nodes, the data caches will be filled up very quickly, and they would need to evict data that's requested. Especially if data is cached along the path from the source to the sink, certain nodes will be in the path more than others. But overall the idea is similar to that of TAG, which is basically localized communication, and also allowing the nodes to process the data before propagating through the network to save messages which in turn saves power.

Wednesday, October 15, 2008

TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks

This paper targets sensor networks which include devices that are in a low powered, distributed wireless environment. The sensor nodes communicate and gather data from the environment collectively and pass the data around through the wireless network. The paper proposes a language and communication mechanism for these network of motes to communicate and pass information. Because of its lower power nature, communication is best done by using multiple short hops instead of one long hop, which uses more power. Also, instead of a centralized server that all nodes send data to, several local interactions are used first to sum up the data gathered, then passed along. A tree routing topology is used so data is passed from the leafs up to the root, but each sub root sums up the data from its child nodes, so the amount of data that needs to be passed up is less, which saves power. The language proposed is a declarative language similar to SQL database query language which allow the users to query sensor data and filter, group the data gathered. Several aggregates can be specified by the language, which is all locally computed and then passed up the tree to the root.

I enjoyed reading this paper a lot, it was very clear in expressing its ideas, and the communication was definitely power efficient because you send out less messages due to the aggregation of data. Several optimizations have also been mentioned. These include mechanisms to maintain the topology and recover from errors and node losses. Also, adding a cache to cache data values also proves as a valuable optimization. Overall, for sensor networks which communicate a collective data set and require low power, the proposed methods seem promising.

Thursday, October 9, 2008

ExOR: Opportunistic Multi-Hop routing for wireless Networks

ExOR proposes a integrated routing and MAC protocol. The basic mechanism introduced is to use the inherit broadcast property of wireless links to broadcast a packet to multiple receivers. Once we know the receivers that actually received the packet, then based on the location of the receiver from the destination, we choose the best receiver to forward the packet. This effectively delays the forwarding decision until after the transmission of the packet. In the paper it mentions 4 key challenges. First, only a subset of nodes should receive the packet. Since there needs to be some sort of communication between the nodes to determine the best fit forwarder, the more nodes that receive the packet, the more communication overhead there will be. Thus, there needs to be a small yet effective set of nodes that receive the broadcast. Secondly, the metric used to determine which node forwards the packet needs to be well designed, and we need ot make sure that one and only one node forwards the packet. Third, similar to the first point, only a subset of useful nodes should receive the packet. Finally, ExOR must avoid simultaneous tranmission to minimize collisions. The results looked decent, giving on average a 2 to 4 times gain on the throughput.

Both the papers we read seems to rely on the fact that all nodes can openly see the packets being transmitted. Conceptually we can almost think of this like a bus, where only one sender can send at a time and all receivers can see if the packet is destined for them. So it seems like broadcasting is one of the essential features of improving throughput now. But with ExOR, one major concern is its compatibility with TCP. The results they obtained was not directly layering ExOR over TCP, they used a split way proxy, and only the connection between 2 proxy points were using ExOR, thus the deployment of this seems to need more improvement in terms of compatability with TCP.

Wednesday, October 8, 2008

XORs in the Air: Practical Wireless Network Coding

This paper puts a lot of theory into practice. The main idea that was introduced was basically doing packing coding to improve on the throughput. But XORing together different packets and broadcasting them, the receivers can XOR the received packet again to obtain the needed data. This way you can transmit multiple packets at once and save on number of transmissions. The paper lends itself to the natural broadcast that wireless networks come with. Receivers hear each other's packets all the time, which this method leverages.

Several issues arise, such as knowing which packets to XOR together to get maximum bandwidth. While reading the paper, it was still not clear to me how they determined what to XOR the packet with. They used simple examples of two nodes transmitting, but this method has to assume that the receiving node has the same data information as another sender's packet, or else how else would the router XOR 2 packets together? The results are more promising for UDP, as they don't implement congestion control in the protocol, thus it would get congested easier, which allows more packets to be XORed together. This of course improves the performance compared to the congested UDP, but does that mean that it can prevent network congestion?

All in all it seems like the implementation was rather complicated for a low gain. So many mechanisms need to be added to the hardware switches, and different packet headers need to be appended onto the data packets while being transmitted. Also, it now takes the receiver even more work after it receives it, and there's a chance that the XORed packet guessed wrong about the receiver node's packets, and the receiver actually can't XOR back the native packet. For this protocol to really become mainstream, it seems the gain in throughput needs to be off the roof for it to be convincing in anyway. But from the results, it wasn't spectacular, especially for the tcp cases. Congestion control would back off packets anyway, so throughput gain will be limited.

Tuesday, October 7, 2008

A performance comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

This paper compares different network routing protocols including the Destination-sequenced distance vector, Temporally-Ordered routing Algorithm, Dynamic source routing, and Ad Hoc On-Demand Distance Vector. The paper gives a brief summary of the different routing protocols and their implementation of each one. This provides a good amount of background for the paper. The paper takes into account the lower level layer characteristics into their simulation which they claim has not previously been done.

The way they test these protocols is that they setup the nodes to move around. The algorithm used to move the nodes cases each node to move and remain stationary for a pause time. When pause time is up, then it picks a destination within a 1500m x 300m space, and then moves to that location in a speed uniformly distributed between 0 and a max speed. Then it waits for another pause time (also random), and then moves again. Different packet sizes and source communicators were used to observe the different effects of the variants. The metrics used were: Packet delivery ratio, routing overhead, and path optimality.

The results showed that DSDV delivered all packets when mobility rate and movement speed are low, but does not perform well when mobility increses. TORA was a little better than DSDV, but introduced a high overhead in the routing protocol. DSR was good at all mobility rates, but the paths need to be determined ahead of time, and introduces more overhead at the source. The AODV performs as well as DSR at all mobility rates, but is more expensive to implement than DSR. This paper however doesn't really consider the effects of congestion on the protocols. In fact, it seems that most wireless protocols focus on the link loss and link quality of the physical layer, while wired protocols focus on congestion control. It makes sense, but i think wireless protocols would still need to consider congestion, and there probably needs to be a mechanism separating congestion loss and quality loss.

A high throughput path metric for multi hop wireless routing

This paper describes a new metric to be used for routing protocols to determine the best path to route in a wireless environment. Previously used metric is the minimum hop count, which favors the least hop path. This has several disadvantages. First, the paths now might be longer, because it takes the least amount of hops, this degrades signal quality since the longer the path, the more the signal is attenuated. This also maximizes loss ratio.

The new metric introduced in this paper is the expected transmission count. This metric takes into account the retransmission counts, and finds the effective transmission count. This allows the mtric to find the path with high throughput, even in the midst of losses. The ETX for a link is calculated by two different ratios, categorized as the forward and reverse ratio. The forward ratio is the ratio that data arrives at the recipient. The reverse ratio measure the ratio of the ack is received. By obtaining the ratio of these 2 values, the metric can then calculate the effective transmission count. The two values are obtained by dedicated link probe packets, which each node broadcasts at a fixed rate. Then depending on whether or not a node receives a probe packet at that rate, we can then calculate the loss ratio based on the last probe packet we received.

This metric takes into account link quality, along with the hop count. This is essential for wireless connections, where link layer losses are common. The minimum hop count path now may not be the ideal in this situation. Several questions arose in my mind when reading the paper. Based on the design of the protocol, it seems that sending the probe packets at that fixed rate is the key to determining the link quality. However, there seems to be ways to delay the sending of a probe packet, for example, if a large data packet is being transmitted etc. This issue will effectively skew the link quality and might lead to false information.

Thursday, October 2, 2008

Modeling Wireless Links for Transport Protocols

This paper lists several different intrinsic characteristics of wireless links for transport protocols and how we can model them in different environments. This paper specifically targets the design of transport layer protocols, thus the methods proposed are for the purpose of high level simulation. It split the wireless links into three main categories, cellular, WLAN and satellite. Previous protocol designs for TCP or other transport layer protocols have the assumption that dropped packets are all due to congestion, because the underlying links were physical connections, thus there were very few link layer corruptions. But for wireless links, several different factors come into play, including interference, data losses, delay variation, packet reordering, bandwidth variation etc.

Reading over this paper, it did help in reinforcing the different things that affect a wireless network, and the paper also mentioned the effects on the specific different type of wireless links (cellular, WLAN and satellite), but the modeling techniques mentioned seem intuitive. Also, there are still several issues that pure modeling can't emulate, such as network topology etc. But this paper provides a high level basic simulation method for designing higher level protocols, which is the target of this paper.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper evaluates the architecture of a wireless mesh network. This paper mainly evaluates the network with unplanned node placement and multi hop routing compared to a planned single hop network. The network implemented is the Roofnet 802.11b mesh network. The paper first explains the architecture and routing protocol of the Roofnet mesh network, which was tested in the MIT campus. The nodes were distributed in a unplanned but not completely random fashion. The routing protocol used was Srcr, which tries to find the highest throughput route between any pair of Roofnet nodes.

The evaluation method measures several different parameters to observe the effects of different values on the throughput of the network. From the results, we can see that the less hops means higher throughput. They also take into account the effect of link quality and distance. The observation was that as distance incrase, the throughput decreases, which makes complete sense because link quality should degrade and signal strength also degrades with distance. As density increases, the throughput also increases. This is a combined effect of lower hop count, but also interference. However, it offers a wider choice of high quality links.

The paper also compares multi-hop to a single hop network, which shows that multi-hop performs better, however the assumption is that the gateways are set and all connections are forced to operate in single hop. One could imagine a combination of planned and random multi-hop access to obtain the best performance results.