Summary
The authors of this paper aim to understand more about Active Networks. They do so by designing, implementing and evaluating ANTS active network toolkit, which provides a flexible network layer and addresses some of the performance and security concerns due to code injected into the network. They also point to 3 areas that they have not yet resolved: capsule model of programming, accessibility of that model to all users, and applications can be constructed using that model.
Criticism & Questions
I think this is an interesting contract to RON. Both are trying to solve the general problem of application-aware routing, but in different ways. While RON is implemented at the application layer, active networks are at the IP layer. Although I think active networks are a great idea in theory, they will be a pain to implement correctly. And, since they allow users to input code into the network, without proper isolation, it could lead to a security nightmare.
Thursday, October 29, 2009
Resilient Overlay Networks
Summary
A Resilient Overlay Network (RON) is an architecture at the application-layer that allows distributed Internet applications to detect outages and recover quickly (on the order of seconds rather than minutes as it is in BGP). The RON nodes sit on top of the network, constantly monitoring it. This network information is used when sending packets to decide whether to send by the normal path through the Internet or to send to another RON node.
RON was evaluated based on 2 deployments. It was able to detect all the outages that took place and reroute packets, all of which took less than 20 seconds on average. RON was also able to improve throughput by 5% and reduce loss probability by 5% in some cases.
RON nodes aggresively probe and monitor the paths connecting their nodes. They exchange information about the quality of each path using a routing protocol. They build a forwarding table with lots of path information, including latency, loss rate and throughput. The authors argue that RON should be limited in size, between 2 and 50 nodes in order to reduce the bandwidth overhead resulting from the aggressive probing.
RON has 3 major goals:
The entry node has a lot of control over the flow of the packet. The packet is tagged with a flow ID, and subsequent nodes attempt to keep the packet on the same path as the rest of the flow.
When building up its routing table, RON keeps track of (i) latency, (ii) packet loss and (iii) throughput. It uses a link-state routing protocol. The latency-minimizer forwarding table uses an exponential weighted moving average of round-trip latency.
RON was implemented and evaluated. It was found to detect and recover from errors in 18 seconds. It also improves throughput, loss rates and latency.
Criticisms & Questions
I think this was an interesting paper. It was well organized and presented the protocol well. Their evaluation also seemed sound given that they did 2 implementations and RON was found to help in all cases.
I think RON is a good way to allow applications to give information to the transport protocol without breaking the end-to-end argument. It solves many of the problems with application-specific needs.
A Resilient Overlay Network (RON) is an architecture at the application-layer that allows distributed Internet applications to detect outages and recover quickly (on the order of seconds rather than minutes as it is in BGP). The RON nodes sit on top of the network, constantly monitoring it. This network information is used when sending packets to decide whether to send by the normal path through the Internet or to send to another RON node.
RON was evaluated based on 2 deployments. It was able to detect all the outages that took place and reroute packets, all of which took less than 20 seconds on average. RON was also able to improve throughput by 5% and reduce loss probability by 5% in some cases.
RON nodes aggresively probe and monitor the paths connecting their nodes. They exchange information about the quality of each path using a routing protocol. They build a forwarding table with lots of path information, including latency, loss rate and throughput. The authors argue that RON should be limited in size, between 2 and 50 nodes in order to reduce the bandwidth overhead resulting from the aggressive probing.
RON has 3 major goals:
- allow nodes to communicate with each other, even in the face of outages.
- integrate routing with distributed applications more closely than before, allowing for application-specific metrics to be used.
- provide a framework for the implementation of expressive routing policies, which allow paths to be chosen based on criteria such as forwarding rate controls or notions of acceptable use.
The entry node has a lot of control over the flow of the packet. The packet is tagged with a flow ID, and subsequent nodes attempt to keep the packet on the same path as the rest of the flow.
When building up its routing table, RON keeps track of (i) latency, (ii) packet loss and (iii) throughput. It uses a link-state routing protocol. The latency-minimizer forwarding table uses an exponential weighted moving average of round-trip latency.
RON was implemented and evaluated. It was found to detect and recover from errors in 18 seconds. It also improves throughput, loss rates and latency.
Criticisms & Questions
I think this was an interesting paper. It was well organized and presented the protocol well. Their evaluation also seemed sound given that they did 2 implementations and RON was found to help in all cases.
I think RON is a good way to allow applications to give information to the transport protocol without breaking the end-to-end argument. It solves many of the problems with application-specific needs.
Tuesday, October 27, 2009
On Inferring Autonomous System Relationships in the Internet
Summary
This paper proposes a graph representation of the AS relationships in the Internet at the time it was written. The authors characterize the relationships into customer-provider, peering and sibling relationships. They came up with heuristic algorithms that look at the BGP routing tables and infer the augmented AS graph.
They test the graph generated by their algorithm on AT&T's internal information and find that over 99% of their graph is accurate. They also test sibling-to-sibling relationships using the WHOIS lookup service and find that over half of their graph is accurate.
Their annotated AS graph consists of nodes connected by one of 3 kinds of edges: provider-to-customer, peer-to-peer and sibling-to-sibling.
They explain the basic 3-phase heuristic algorithm they use. The first phase parses the routing tables and calculates the degree of each AS. The next phase goes through all the entries in the routing table and parses it to find the top provider and consecutive AS pairs before and after the top provider. Finally, in the third phase, it assigns all those consecutive AS pairs with a transit relationship.
The basic algorithm assumes that there are no misconfiguration errors. They also propose a refined algorithm that accounts for any misconfiguration errors. Furthermore, they propose another algorithm that infers peering relationships in addition to the provider-customer and sibling relationships that the previous 2 infer.
Finally, they implement all 3 algorithms and using AT&T's internal data and the WHOIS service, they determine that their algorithms are fairly accurate.
Criticisms & Questions
I think this was an interesting paper. I think they did a decent job of explaining the algorithms and their experimental results. I would, however, have liked them to expand more on the motivation for their work. They spend a lot of time talking about how BGP works and what each of the different relationships are. However, they only briefly mention several use cases for the augmented graph representation they present. And, with those few examples, I find it hard to understand why any ISP would need to know the entire representation if they wanted to find out information about a specific ISP. If it's just one ISP, can't they just ask them?
This paper proposes a graph representation of the AS relationships in the Internet at the time it was written. The authors characterize the relationships into customer-provider, peering and sibling relationships. They came up with heuristic algorithms that look at the BGP routing tables and infer the augmented AS graph.
They test the graph generated by their algorithm on AT&T's internal information and find that over 99% of their graph is accurate. They also test sibling-to-sibling relationships using the WHOIS lookup service and find that over half of their graph is accurate.
Their annotated AS graph consists of nodes connected by one of 3 kinds of edges: provider-to-customer, peer-to-peer and sibling-to-sibling.
They explain the basic 3-phase heuristic algorithm they use. The first phase parses the routing tables and calculates the degree of each AS. The next phase goes through all the entries in the routing table and parses it to find the top provider and consecutive AS pairs before and after the top provider. Finally, in the third phase, it assigns all those consecutive AS pairs with a transit relationship.
The basic algorithm assumes that there are no misconfiguration errors. They also propose a refined algorithm that accounts for any misconfiguration errors. Furthermore, they propose another algorithm that infers peering relationships in addition to the provider-customer and sibling relationships that the previous 2 infer.
Finally, they implement all 3 algorithms and using AT&T's internal data and the WHOIS service, they determine that their algorithms are fairly accurate.
Criticisms & Questions
I think this was an interesting paper. I think they did a decent job of explaining the algorithms and their experimental results. I would, however, have liked them to expand more on the motivation for their work. They spend a lot of time talking about how BGP works and what each of the different relationships are. However, they only briefly mention several use cases for the augmented graph representation they present. And, with those few examples, I find it hard to understand why any ISP would need to know the entire representation if they wanted to find out information about a specific ISP. If it's just one ISP, can't they just ask them?
On Power-Law Relationships of the Internet Topology
Summary
This paper characterizes the structure of the Internet between Nov. 1997 and Dec. 1998. They authors find that power-laws fit the topology really well. The power-laws that they generate could be used to understand more characteristics of the network, such as average neighborhood size, and can be used to help design protocols.
During the time they studied, the internet by 45%. Unless this time was a transition phase for the Internet, the authors believe the power laws they came up with should continue to hold in the future.
Some characteristics of the Internet during the time of their study are:
Criticisms & Questions
This was an interesting paper, especially since it was one of the first to characterize the topology of the Internet. Seeing as this was a decade ago, I am very curious to find out of these power-laws still hold. Since the way the internet is used has changed in the last 10 years, I would be really surprised if they were still true.
The authors mention several practical applications for the power-laws. I wonder if anyone has used these power-laws to inform any future research.
This paper characterizes the structure of the Internet between Nov. 1997 and Dec. 1998. They authors find that power-laws fit the topology really well. The power-laws that they generate could be used to understand more characteristics of the network, such as average neighborhood size, and can be used to help design protocols.
During the time they studied, the internet by 45%. Unless this time was a transition phase for the Internet, the authors believe the power laws they came up with should continue to hold in the future.
Some characteristics of the Internet during the time of their study are:
- Nov. 1997: 3015 nodes, 5156 edges, 3.42 avg. outdegree
- April 1998: 3530 nodes, 6432 edges, 3.65 avg outdegree
- Dec. 1998: 4389 nodes, 8256 edges, 3.76 avg outdegree
- Power-Law 1 (rank exponent): The outdegree, dv, of a node v, is proportional to the rank of the node, rv, to the power of a constant, R.
- Power-Law 2 (outdegree exponent): The frequency, fd, of an outdegree, d, is proportional to the outdegree to the power of a constant, O
- Power-Law 3 (eigen exponent): The eigenvalues, lambda_i, of a graph are proportional to the order, i, to the power of a constant.
Criticisms & Questions
This was an interesting paper, especially since it was one of the first to characterize the topology of the Internet. Seeing as this was a decade ago, I am very curious to find out of these power-laws still hold. Since the way the internet is used has changed in the last 10 years, I would be really surprised if they were still true.
The authors mention several practical applications for the power-laws. I wonder if anyone has used these power-laws to inform any future research.
Tuesday, October 20, 2009
Interactive WiFi Connectivity for Moving Vehicles
Summary
This paper presents an evaluation of 6 different handoff protocols for WiFi in moving vehicles. It also proposes ViFi, a protocol that exploits basestation diversity to minimize disruptions and support interactive applications for mobile clients.
For the evaluation, they test these protocols in a 2-month long experiments on 2 platforms. One is VanLAN, which consists of 11 basestations and 2 vehicles used for shuttle service around the Microsoft campus in Redmond. The other consists of vehicles in Amherst. One of these vehicles logs all the beacons heard from all the surrounding BSes.
They test the following 2 applications: VoIP and short TCP transfers.
When evaluating the different handoff protocols, they use 2 metrics:
1. aggregate performance: considers total number of packets delivered and the total time or distance over which the vehicle is connected.
2. periods of uninterrupted connectivity: measures contiguous time intervals when the performance of the application is above a certain threshold.
The 6 handoff policies evaluated are:
1. RSSI
2. BRR
3. Sticky
4. History
5. BestBS
6. AllBSes
When testing performance related to BS density, they found that all protocols' performance increases with density but that relative performance of protocols stays the same throughout. And, AllBSes is found to have the best performance while History, RSSI and BRR are found to perform similar in most cases.
When looking at uninterrupted connectivity results, they found that AllBSes had the fewest regions of inadequate connectivity (because it uses multiple BSes), while BestBS had a few more and BRR had the most.
Then, the authors explain the design and implementation of ViFi. ViFi, motivated partially by AllBSes, leverages BS diversity to reduce disruptions. ViFi designates one of the BSes as the anchor, which is responsible for connecting to the internet. The other BSes are designated as auxiliary.
The authors evaluate ViFi and find that the link-layer performance of ViFi is close to ideal. ViFi has a two-fold application performance improvement over current handoff methods.
Criticism & Questions
I liked reading this paper. It did a great job of evaluating the current protocols and then building off one of those protocols to come up with ViFi. They also had a solid implementation and evaluation of ViFi.
What I am most curious about is the practical application of WiFi connectivity in moving vehicles. They motivate their work by mentioning the growing need and opportunity. I would have liked them to expand more on that and possible current use cases of this technology.
In addition, I would like to know more about what the topology of cities that are covered by WiFi are. When I think about the possible uses for interactive WiFi, I would imagine it would be most useful in longer trips, which generally means crossing multiple cities. If wifi is unavailable in many the cities along the path, that would impact the practical application of this technology.
This paper presents an evaluation of 6 different handoff protocols for WiFi in moving vehicles. It also proposes ViFi, a protocol that exploits basestation diversity to minimize disruptions and support interactive applications for mobile clients.
For the evaluation, they test these protocols in a 2-month long experiments on 2 platforms. One is VanLAN, which consists of 11 basestations and 2 vehicles used for shuttle service around the Microsoft campus in Redmond. The other consists of vehicles in Amherst. One of these vehicles logs all the beacons heard from all the surrounding BSes.
They test the following 2 applications: VoIP and short TCP transfers.
When evaluating the different handoff protocols, they use 2 metrics:
1. aggregate performance: considers total number of packets delivered and the total time or distance over which the vehicle is connected.
2. periods of uninterrupted connectivity: measures contiguous time intervals when the performance of the application is above a certain threshold.
The 6 handoff policies evaluated are:
1. RSSI
2. BRR
3. Sticky
4. History
5. BestBS
6. AllBSes
When testing performance related to BS density, they found that all protocols' performance increases with density but that relative performance of protocols stays the same throughout. And, AllBSes is found to have the best performance while History, RSSI and BRR are found to perform similar in most cases.
When looking at uninterrupted connectivity results, they found that AllBSes had the fewest regions of inadequate connectivity (because it uses multiple BSes), while BestBS had a few more and BRR had the most.
Then, the authors explain the design and implementation of ViFi. ViFi, motivated partially by AllBSes, leverages BS diversity to reduce disruptions. ViFi designates one of the BSes as the anchor, which is responsible for connecting to the internet. The other BSes are designated as auxiliary.
The authors evaluate ViFi and find that the link-layer performance of ViFi is close to ideal. ViFi has a two-fold application performance improvement over current handoff methods.
Criticism & Questions
I liked reading this paper. It did a great job of evaluating the current protocols and then building off one of those protocols to come up with ViFi. They also had a solid implementation and evaluation of ViFi.
What I am most curious about is the practical application of WiFi connectivity in moving vehicles. They motivate their work by mentioning the growing need and opportunity. I would have liked them to expand more on that and possible current use cases of this technology.
In addition, I would like to know more about what the topology of cities that are covered by WiFi are. When I think about the possible uses for interactive WiFi, I would imagine it would be most useful in longer trips, which generally means crossing multiple cities. If wifi is unavailable in many the cities along the path, that would impact the practical application of this technology.
White Space Networking with Wi-Fi like Connectivity
Summary
This paper proposes the first network prototype demonstrating the feasibility of WiFi-like networking over UHF white spaces.
The authors contribute a new spectrum assignment algorithm that determines variable bandwidth during communication, a new AP discovery mechanism using a new technique called SIFT, and a novel method for seamlessly handling unexpected disconnections.
There are several properties of the UHF white space spectrum that pose problems to networking. First is the spatial spectrum variation, which implies that the AP must get information from clients before deciding the channel to operate on. The second is spectrum fragmentation, which results in several problems related to choosing a channel. And, finally temporal variation, which is due to interference from wireless mics.
The authors built the KNOWS hardware platform to address some of the problems with white space networking. The 2 main features it adds are Variable Channel Widths and Signal Inspection before Fourier Transform (SIFT). Variable channel widths allows the channel bandwidth to be greater than 5 MHz. SIFT addresses the problems with intermittent data transmissions and that transmissions can be sent over multiple channel widths.
They describe the details of the spectrum assignment algorithm which takes an adaptive approach to choosing a channel and periodically re-evaluating this choice based on feedback from the clients.
Finally, they perform an evaluation of WhiteFi, using both simulations and experiments on the prototype. They found that SIFT for pretty accurate, with a worst case loss of 2%. When testing SIFT with low signal strengths, they found that it performs well until it hits a threshold of 96 dB. They evaluated the L-SIFT and J-SIFT to discover APs and found that L-SIFT outperforms J-SIFT for narrow white spaces while J-SIFT is much more efficient for wider white spaces and both outperform the baseline algorithm. They also tried this in more realistic settings and found that J-SIFT still outperformed the baseline by 34%. They found that it took about 4 seconds to reconnect following a disconnection. Simulations of the spectrum assignment algorithm indicate that it yields a reasonably accurate prediction.
Criticism & Questions
I think this was an interesting paper. I was not too familiar with white space networking, so this was a good introduction, especially with all the background information they added about problems.
They explained the setup and results of their evaluations very clearly for the most part. However, when they were talking about handling disconnections, they didn't spend much time on that, only briefly mentioning that there was a lag of at most 4 seconds before reconnection. Without any baseline value to compare that to, I'm unsure of how much of a performance gain that is.
This paper proposes the first network prototype demonstrating the feasibility of WiFi-like networking over UHF white spaces.
The authors contribute a new spectrum assignment algorithm that determines variable bandwidth during communication, a new AP discovery mechanism using a new technique called SIFT, and a novel method for seamlessly handling unexpected disconnections.
There are several properties of the UHF white space spectrum that pose problems to networking. First is the spatial spectrum variation, which implies that the AP must get information from clients before deciding the channel to operate on. The second is spectrum fragmentation, which results in several problems related to choosing a channel. And, finally temporal variation, which is due to interference from wireless mics.
The authors built the KNOWS hardware platform to address some of the problems with white space networking. The 2 main features it adds are Variable Channel Widths and Signal Inspection before Fourier Transform (SIFT). Variable channel widths allows the channel bandwidth to be greater than 5 MHz. SIFT addresses the problems with intermittent data transmissions and that transmissions can be sent over multiple channel widths.
They describe the details of the spectrum assignment algorithm which takes an adaptive approach to choosing a channel and periodically re-evaluating this choice based on feedback from the clients.
Finally, they perform an evaluation of WhiteFi, using both simulations and experiments on the prototype. They found that SIFT for pretty accurate, with a worst case loss of 2%. When testing SIFT with low signal strengths, they found that it performs well until it hits a threshold of 96 dB. They evaluated the L-SIFT and J-SIFT to discover APs and found that L-SIFT outperforms J-SIFT for narrow white spaces while J-SIFT is much more efficient for wider white spaces and both outperform the baseline algorithm. They also tried this in more realistic settings and found that J-SIFT still outperformed the baseline by 34%. They found that it took about 4 seconds to reconnect following a disconnection. Simulations of the spectrum assignment algorithm indicate that it yields a reasonably accurate prediction.
Criticism & Questions
I think this was an interesting paper. I was not too familiar with white space networking, so this was a good introduction, especially with all the background information they added about problems.
They explained the setup and results of their evaluations very clearly for the most part. However, when they were talking about handling disconnections, they didn't spend much time on that, only briefly mentioning that there was a lag of at most 4 seconds before reconnection. Without any baseline value to compare that to, I'm unsure of how much of a performance gain that is.
Thursday, October 15, 2009
XORs in The Air: Practical Wireless Network Coding
Summary
This paper proposes COPE, a new architecture for wireless mesh networks. It uses packet coding in order to reduce the number of required transmissions. Like ExOR, it takes advantage of the broadcast nature of the wireless channel.
The packet coding algorithm makes sure to never delay a packet in order to code a packet. It gives preference to XORing packets of similar length. It will never XOR packets headed to the same nexthop. It tries to limit reordering packets from the same flow. Finally, it ensures that each neighbor who gets a coded packet has a high probability of being able to decode it.
They use "coding gain" as the performance metric for COPE. Coding game is the ratio of the number of transmissions required by the current non-coding approach, to the minimum number of transmissions used b COPE to deliver the same set of packets.
COPE was implemented on a 20-node wireless testbed over 3 topologies. It was found to have about a 1.33 coding gain. The cross topology over TCP was found to be a little lower than expected which they attributed to header overhead, imperfect overhearing and an asymmetry in throughputs of the 4 flows.
Finally, they mention fairness and claim that when packets are coded, increasing fairness will increase the overall throughput of the network.
Criticism & Questions
I thought this paper was interesting, definitely another interesting way to make use of the broadcast nature of wireless. I'm not sure if COPE could be used together with ExOR, maybe if ExOR were modified to accommodate multiple flows at once. But, if not, I would really like to see a side-by-side comparison of the two to determine which has greater performance.
This paper proposes COPE, a new architecture for wireless mesh networks. It uses packet coding in order to reduce the number of required transmissions. Like ExOR, it takes advantage of the broadcast nature of the wireless channel.
The packet coding algorithm makes sure to never delay a packet in order to code a packet. It gives preference to XORing packets of similar length. It will never XOR packets headed to the same nexthop. It tries to limit reordering packets from the same flow. Finally, it ensures that each neighbor who gets a coded packet has a high probability of being able to decode it.
They use "coding gain" as the performance metric for COPE. Coding game is the ratio of the number of transmissions required by the current non-coding approach, to the minimum number of transmissions used b COPE to deliver the same set of packets.
COPE was implemented on a 20-node wireless testbed over 3 topologies. It was found to have about a 1.33 coding gain. The cross topology over TCP was found to be a little lower than expected which they attributed to header overhead, imperfect overhearing and an asymmetry in throughputs of the 4 flows.
Finally, they mention fairness and claim that when packets are coded, increasing fairness will increase the overall throughput of the network.
Criticism & Questions
I thought this paper was interesting, definitely another interesting way to make use of the broadcast nature of wireless. I'm not sure if COPE could be used together with ExOR, maybe if ExOR were modified to accommodate multiple flows at once. But, if not, I would really like to see a side-by-side comparison of the two to determine which has greater performance.
ExOR: Opportunistic Multi-Hop Routing for Wireless Networks
Summary
This paper proposes ExOR, an integrated routing and MAC technique that uses cooperative diversity to increase throughput of large unicast transfers in multi-hop wireless networks.
ExOR takes advantage of broadcast transmission to send data to multiple nodes at once. The furthest (to source and closest to destination) node that heard the broadcast will then broadcast it out again, until it reaches the destination. This results in a higher throughput because ExOR makes use of transmissions that reach unexpectedly far or fall short. It also increases network capacity since it needs fewer retransmissions than traditional routing.
Data is sent in batches and is stored by each intermediate node until all the data is sent before deciding which node is closest to destination. ExOR schedules when each node sends its fragments so that only one node sends at a time. Once 90% of the packets have been sent, the remaining 10% get sent using traditional routing.
ExOR was implemented on Roofnet. It was found to outperform traditional routing by a factor of 2. It was also found to have the most performance gains on the longest routes.
Criticism & Questions
I think cooperative diversity routing is a very interesting idea. I think it makes sense intuitively why it would have good performance. I am however concerned about its incompatibility with regular TCP, a hindrance to its use in most practical settings. In addition, when doing the experiment, the authors spend about 10 minutes initially just setting up the nodes and then every 20 minutes, stop the experiment to update their link loss measurements. I'm not sure how practical that is and how it would affect overall throughput.
This paper proposes ExOR, an integrated routing and MAC technique that uses cooperative diversity to increase throughput of large unicast transfers in multi-hop wireless networks.
ExOR takes advantage of broadcast transmission to send data to multiple nodes at once. The furthest (to source and closest to destination) node that heard the broadcast will then broadcast it out again, until it reaches the destination. This results in a higher throughput because ExOR makes use of transmissions that reach unexpectedly far or fall short. It also increases network capacity since it needs fewer retransmissions than traditional routing.
Data is sent in batches and is stored by each intermediate node until all the data is sent before deciding which node is closest to destination. ExOR schedules when each node sends its fragments so that only one node sends at a time. Once 90% of the packets have been sent, the remaining 10% get sent using traditional routing.
ExOR was implemented on Roofnet. It was found to outperform traditional routing by a factor of 2. It was also found to have the most performance gains on the longest routes.
Criticism & Questions
I think cooperative diversity routing is a very interesting idea. I think it makes sense intuitively why it would have good performance. I am however concerned about its incompatibility with regular TCP, a hindrance to its use in most practical settings. In addition, when doing the experiment, the authors spend about 10 minutes initially just setting up the nodes and then every 20 minutes, stop the experiment to update their link loss measurements. I'm not sure how practical that is and how it would affect overall throughput.
Thursday, October 8, 2009
A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols
Summary
This paper presents the results of a performance comparison between 4 multi-hop wireless ad hoc network routing protocols. This paper also proposed and implemented changes to ns so that it could be used to study multi-hop ad hoc networks.
The 4 protocols that were tested were:
- Destination-Sequenced Distance Vector (DSDV)
- Temporally-Ordered Routing Algorithms
- Dynamic Source Routing (DSR)
- Ad Hoc On-Demand Distance Vector (AODV)
The changes that were made to ns included a model of the physical and data link layer. The link layer implements the MAC protocol. There was also an implementation of ARP to resolve IP address to link layer addresses. Finally, each protocol has a packet buffer of max size 50 packets.
The authors ran a simulation of 50 nodes on ns to see how each protocol would react to changes in the network topology. The simulation was run using 3 different CBR sources in order to approximate 3 different data sending rates.
They chose the following 3 metrics to evaluate the simulation results:
- packet delivery rate
- routing overhead
- path optimality
When evaluating path delivery rate, DSR and AODV-LL were found to have the best performance at all pause times. TORA performs a little worse, and while DSDV-SQ performs better than TORA when pause time is over 300 ms, it fails to converge at pause times below 300 ms.
When evaluating routing overhead, DSR was found to have the lowest number of overhead packets while AODV-LL was found to have a slightly higher number of overhead packets. However, when looking at the number of overhead bytes, AODV-LL actually has the smallest number of total overhead bytes.
When evaluating path optimality, DSR and DSDV-SQ were found to use routes close to the optimal, while AODV-LL and TORA used routes that were sometimes 4 hops longer than optimal.
Criticism & Questions
I think this paper was interesting to read. The simulation results do suggest many differences between the 4 protocols and would be informative to those choosing between them. However, since these are purely simulation results, I wonder how accurate they are. One of the features of ad-hoc networks is their unpredictability, and without doing a real deployment, I'm not sure how accurately you can test the various protocols.
The authors didn't include a future works section, but I would really like to see the results of a real deployment as the next step.
A High-Throughput Path Metric for Multi-Hop Wireless Routing
Summary
This paper proposes a new metric to use when finding the highest-throughput path on multi-hope wireless routing. This new metric, called Expected Trasmission Count, uses link loss ratios, asymmetry in loss ratios and interference between successive links in a path to find the path that requires the lowest number of transmissions, including retransmissions, to successfully deliver the packet to its destination.
The typical metric currently used in multi-hop wireless routing is minimum hop-count. The authors first determined the performance of minimum-hop-count routing using a 29-node wireless testbed. They used both the DSDV and DSR protocols. They found that minimum-hop-count works well when the shortest route is also the fastest one. However, when it has a choice among a number of multi-hop routes, it usually picks a much slower than optimal path.
Next, the authors explain, implement and evaluate ETX. The ETX metric measures the number of transmissions required to send a packet to its destination.
ETX = 1 / (df * dr)
where df = forward delivery ratio and dr = reverse delivery ratio.
When testing ETX with DSDV, ETX was found to perform better than DSDV when the packet is being sent on a high loss ratio link and the best path is multi-hop. Some part of ETX's improvement is due to avoiding extremely asymmetric links, even better than the handshaking scheme with the same goal.
ETX was tested with DSR with its link-layer feedback turned on and off. When it was turned off, ETX showed a significant improvement in initial route selection. However, when feedback was turned on, ETX showed only a slight improvement to some pairs of nodes.
One drawback to ETX is that it uses a fixed packet size to make its calculations. However, it was shown that packet size has a significant effect on delivery ratio. Because of this, ETX tends to underestimates the delivery ratio of ACK packets, resulting in a overestimation of the number of required transmissions.
Criticism & Questions
I enjoyed reading this paper. I think they had very sound methodology, especially in testing minimum-hop-count so they could have a fair comparison. Since there are at least 2 more ad-hoc multi-hop routing protocols (which we read about in the next paper), I would like to see the effect that ETX would have on those protocols as well. One complaint about the paper is that the graphs were really hard to read and really hard to differentiate between the various lines.
Tuesday, October 6, 2009
Architecture and Evaluation of an Unplanned 802.11b Mesh Network
Summary
This paper evaluated the architecture and performance of Roofnet, an unplanned 802.11b Mesh Network. It explored the effect of node density on connectivity and throughput, the links that the routing protocol uses, performance of a highly connected mesh and comparison to a single-hop network using the same nodes as Roofnet.
Roofnet is primarily characterized by the following design decisions:
Then, the authors use 4 sets of measurements on Roofnet to evaluate many characteristics of Roofnet.
The authors conclude that Roofnet works. Throughput and latency are comparable to that of a DSL link. The average throughput was measured to be 627 kbits/second. Roofnet is shown to be robust as it does not depend on a small number of nodes. It also shown that multi-hop forwarding performs better than single-hop forwarding.
Criticism & Questions
This paper was very well organized and easy to follow. Their evaluation considered many characteristics and they made sound arguments when analyzing their data. The charts and graphs were very helpful in understanding their points.
Feedback
I would vote to keep this paper in the syllabus.
This paper evaluated the architecture and performance of Roofnet, an unplanned 802.11b Mesh Network. It explored the effect of node density on connectivity and throughput, the links that the routing protocol uses, performance of a highly connected mesh and comparison to a single-hop network using the same nodes as Roofnet.
Roofnet is primarily characterized by the following design decisions:
- unconstrained node placement
- omni-directional antennas
- multi-hop routing
- optimization of routing for throughput in a slowly-changing network
Then, the authors use 4 sets of measurements on Roofnet to evaluate many characteristics of Roofnet.
The authors conclude that Roofnet works. Throughput and latency are comparable to that of a DSL link. The average throughput was measured to be 627 kbits/second. Roofnet is shown to be robust as it does not depend on a small number of nodes. It also shown that multi-hop forwarding performs better than single-hop forwarding.
Criticism & Questions
This paper was very well organized and easy to follow. Their evaluation considered many characteristics and they made sound arguments when analyzing their data. The charts and graphs were very helpful in understanding their points.
Feedback
I would vote to keep this paper in the syllabus.
Modeling Wireless Links for Transport Protocols
Summary
This paper puts forth a model to evaluate the performance of wireless links. The authors argue that this is especially useful when trying to decide if link layer protocols should have knowledge of the transport layer and use that knowledge when deciding what to do or if transport protocols should be redesigned for better performance on current wireless links.
This paper considers 3 main classes of wireless links: wireless LANs, wide-area cellular links and satellite links. The authors go into detail on the essential aspects of the model: types of wireless links in each class, topologies most common in each class and the traffic patterns in each class.
The performance metrics used for this experiment are throughput, delay, fairness, dynamics and goodput.
Then, the authors explain that current models are inadequate because they are either unrealistic, realistic but explore only a small part of the parameter space, overly realistic or lacking reproducibility.
The authors then choose several link characteristics and for each, explain what the current state is and how to model it:
I enjoyed this paper. It was well organized and easy to follow. I especially liked how they organized the various link characteristics to consider by explaining what the current state of each was as well as how to model that characteristic.
I am very curious to know if this model caught on or is being used by any networking researchers in the present time.
This paper puts forth a model to evaluate the performance of wireless links. The authors argue that this is especially useful when trying to decide if link layer protocols should have knowledge of the transport layer and use that knowledge when deciding what to do or if transport protocols should be redesigned for better performance on current wireless links.
This paper considers 3 main classes of wireless links: wireless LANs, wide-area cellular links and satellite links. The authors go into detail on the essential aspects of the model: types of wireless links in each class, topologies most common in each class and the traffic patterns in each class.
The performance metrics used for this experiment are throughput, delay, fairness, dynamics and goodput.
Then, the authors explain that current models are inadequate because they are either unrealistic, realistic but explore only a small part of the parameter space, overly realistic or lacking reproducibility.
The authors then choose several link characteristics and for each, explain what the current state is and how to model it:
- error losses and corruption: not a big concern because of FEC and link layer retransmissions. Can be modeled by dropping packets on a per-packet, per-bit or time-based loss probability
- delay variation: delay spikes can cause spurious timeouts, causing retransmissions. Can be modeled by suspending data transmission on the link.
- packet reordering: reordering is not widely enabled in practice. Can be modeled by swapping packets or delaying one packet for a given time.
- on-demand resource allocation
- bandwidth variation
- asymmetry in bandwidth and latency
- queue management
- effects of mobility
I enjoyed this paper. It was well organized and easy to follow. I especially liked how they organized the various link characteristics to consider by explaining what the current state of each was as well as how to model that characteristic.
I am very curious to know if this model caught on or is being used by any networking researchers in the present time.
Thursday, October 1, 2009
A Comparison of Mechanisms for Improving TCP Performance over Wireless Links
Summary
This paper presents an evaluation of several schemes to improve the performance of TCP over lossy links, such as wireless. The authors classify the schemes into the following 3 categories:
1. end-to-end protocols: have the sender detect and handle losses using techniques such as SACKs and ELN
2. link-layer protocols: hide link-layer losses from the transport layer and handle them in the link-layer instead using techniques such as local retransmissions and forward error correction.
3. split-connection protocols: terminate the TCP connection at the station so that the sender is not aware of the wireless link at the end. Use a different protocol from the station to the receiver that deals with losses.
After evaluating the various schemes they got the following results: the enhanced link-layer scheme that has knowledge of the TCP protocol and uses SACKs works much better than a simple link-layer retransmission scheme. Out of the various end-to-end protocols, selective acknowledgements was found to be better than partial acknowledgements or ELN, but not better than the enhanced link-layer scheme. The split-connection protocol is worse than the two schemes above, and shows that a split-connection is not necessary to get optimal performance.
Overall, the link-layer scheme that was TCP aware and uses SACKs was found to be the best scheme.
Criticism & Questions
I would be very interested in finding out which schemes, if any, are currently used in lossy networks. They touch on this a little, but I would like to learn more about the practicality of each of the schemes and have that be one of the criteria considered when choosing the optimal scheme.
Feedback
I enjoyed reading this paper. It was great to learn about the various schemes available to improve performance in lossy links. I think the authors did a great job at explaining each of the schemes and why one was better than the other. I vote to keep this paper in the syllabus.
This paper presents an evaluation of several schemes to improve the performance of TCP over lossy links, such as wireless. The authors classify the schemes into the following 3 categories:
1. end-to-end protocols: have the sender detect and handle losses using techniques such as SACKs and ELN
2. link-layer protocols: hide link-layer losses from the transport layer and handle them in the link-layer instead using techniques such as local retransmissions and forward error correction.
3. split-connection protocols: terminate the TCP connection at the station so that the sender is not aware of the wireless link at the end. Use a different protocol from the station to the receiver that deals with losses.
After evaluating the various schemes they got the following results: the enhanced link-layer scheme that has knowledge of the TCP protocol and uses SACKs works much better than a simple link-layer retransmission scheme. Out of the various end-to-end protocols, selective acknowledgements was found to be better than partial acknowledgements or ELN, but not better than the enhanced link-layer scheme. The split-connection protocol is worse than the two schemes above, and shows that a split-connection is not necessary to get optimal performance.
Overall, the link-layer scheme that was TCP aware and uses SACKs was found to be the best scheme.
Criticism & Questions
I would be very interested in finding out which schemes, if any, are currently used in lossy networks. They touch on this a little, but I would like to learn more about the practicality of each of the schemes and have that be one of the criteria considered when choosing the optimal scheme.
Feedback
I enjoyed reading this paper. It was great to learn about the various schemes available to improve performance in lossy links. I think the authors did a great job at explaining each of the schemes and why one was better than the other. I vote to keep this paper in the syllabus.
Subscribe to:
Posts (Atom)