[paper]
In an active network, packets carry code that is executed by the routers that handle the packet while it is in transmission. Nodes in an active network need to be able to understand and execute packet code, but it is possible to mix and match active and normal routers. Packets can therefore react to changing network conditions and choose new routing paths for themsleves. This is very much the opposite of the "dumb core" from the end-to-end argument.
ANTS is the active network system developed by the author. A "capsule" is an extended packet that has code associated with it. In their design, capsules do not actually carry code. Rather, each active node has a set list of forwarding functions that it will execute, and each capsule says which forwarding function should be used for the packet. New forwarding functions can be provided for new services; these functions can query the router about network state. They suggest that code should be certified by an overseeing authority. Code is always executed in a sandbox.
- They do not actually want to load all possible functions in all active nodes (memory constraints), nor do they want packets to actually carry the executable code (certifying the code every time would be slow). Instead, they cache the most recently seen functions. Since they expect a small number of functions to be very popular, this would be good for those popular functions. For less-popular functions, the code is requested from the last active node that the packet was at, which (hopefully?) will still have the code.
- Forwarding functions are identified by their MD5 hash. This is an old paper, so this was probably OK at the time. However, MD5 shouldn't be used anymore. Also -- at first I was concerned because a hash function alone will only provide integrity but say nothing about authenticity -- you need an HMAC if you want both. However, after thinking about it, authenticity doesn't really matter in this scenario, we really do just care about integrity.
- They duly note that active networks won't work very well when you have end-to-end encryption and your function depends on packet contents. Seems like this will be an increasingly big problem.
They do an evaluation. Their use of Java is a significant cause of poor performance; they compare a Java relay to a C relay and the C relay has a lot more throughput (4x) and much lower latency (~5x). However, processing forwarding functions doesn't add much on top of that, although it does seem like a poorly-written forwarding function could do much worse than their example forwarding function. Use of C would make it harder to sandbox the code but it is certainly still possible.
Comment: I don't think the paper explained the concept of an "active network" well. I was confused about whether the point was to use the network for arbitrary computation or to change the way routing works. I ended up reading the Wikipedia article and this GE page. I think the authors should have defined "capsule" in the introduction so that I didn't have to read the third section to understand the intro. Sections 3 and onwards are quite good, but I found the intro & background less than helpful for someone who didn't know anything about active networks.
--------------
Class Notes
- Things you might want to do in a network: app-relevant metrics; DOS prevention with capabilities; NAT address translation; media transcoders; compression/decompression.
- Many of those apps can be done with a box on either end rather than in every router.
- No killer app! However, this does sort of happen near the edges, but at the application layer.
- PROS of active networks vs application-layer services: common way of implementing services; potentially more efficient since packets stay in their "natural path"
- CONS of active networks vs application-layer services: performance (esp latency), security, isolation (if one crashes, do they all?), state
Wednesday, October 28, 2009
Resilient Overlay Networks
[paper]
Problem: BGP's fault recovery mechanisms take several minutes; new routes are slow to converge. Outages can be 10+ minutes. This is a problem for distributed applications.
Solution: RON, a Resilient Overlay Network. A RON node constantly monitors the quality of the path ("virtual link") between it and other RON nodes in terms of latency, throughput, and packet loss rate. RON networks are meant to be small so each node can keep track of alternate routes as well as primary routes. Each RON node is a forwarder as well as a client. Interesting point: some applications may be more fault tolerant than others, so applications can define their own "failure" settings and prioritize certain metrics over others.
- Fast detection & recovery. They want to recover from link or route failures in seconds. When a probe is lost, a series of high-frequency probes are sent. If the link is dead or bandwidth is degraded by 50%+, and a good alternative path is available, then it will use the alternative path to send data. A potential problem is "flapping" between two routes; you don't want to frequently switch because that could cause a lot of reordering. To solve this, they favor the "last good route."
Evaluation: Looked at two RON networks, one with 12 nodes and one with 16. In an experiment averaging packet loss rate over 30-min intervals, they showed that BGP routing suffered 32 significant outages and RON suffered none. They also present RON Win/Loss/No change statistics based on loss rates and it seems like RON does very well.
An interesting point about this paper is that they assume that RON networks will be small. I question whether this makes a lot of sense given that they are targeting distributed applications. Does Google do distributed computing across different data centers? That would be much larger scale. I guess Google has their own fiberoptic network though so they wouldn't need to worry about these BGP-based routing concerns. But there must be large distributed applications that don't have their own networks, too.
--------------------
Class Notes
- overlay: network on top of a network
- application-specific routing means that you get to pick your own routing metric
- RON's concern is reachability, period, not latency.
- BGP doesn't broadcast alternate routes between ASes. this is how RON gets its improvement: it can identify a path through a different set of ASes that avoids the problem. this means that you need one overlay node in each AS that you care about; two nodes in the same AS won't see any improvement.
- overlays over overlays cause fairness problems. if they all see an area with no congestion and try to use it at once, then all of a sudden that will be congested.
- scalability issue with RON because of their active probing. won't scale up to more than 50 nodes.
Problem: BGP's fault recovery mechanisms take several minutes; new routes are slow to converge. Outages can be 10+ minutes. This is a problem for distributed applications.
Solution: RON, a Resilient Overlay Network. A RON node constantly monitors the quality of the path ("virtual link") between it and other RON nodes in terms of latency, throughput, and packet loss rate. RON networks are meant to be small so each node can keep track of alternate routes as well as primary routes. Each RON node is a forwarder as well as a client. Interesting point: some applications may be more fault tolerant than others, so applications can define their own "failure" settings and prioritize certain metrics over others.
- Fast detection & recovery. They want to recover from link or route failures in seconds. When a probe is lost, a series of high-frequency probes are sent. If the link is dead or bandwidth is degraded by 50%+, and a good alternative path is available, then it will use the alternative path to send data. A potential problem is "flapping" between two routes; you don't want to frequently switch because that could cause a lot of reordering. To solve this, they favor the "last good route."
Evaluation: Looked at two RON networks, one with 12 nodes and one with 16. In an experiment averaging packet loss rate over 30-min intervals, they showed that BGP routing suffered 32 significant outages and RON suffered none. They also present RON Win/Loss/No change statistics based on loss rates and it seems like RON does very well.
An interesting point about this paper is that they assume that RON networks will be small. I question whether this makes a lot of sense given that they are targeting distributed applications. Does Google do distributed computing across different data centers? That would be much larger scale. I guess Google has their own fiberoptic network though so they wouldn't need to worry about these BGP-based routing concerns. But there must be large distributed applications that don't have their own networks, too.
--------------------
Class Notes
- overlay: network on top of a network
- application-specific routing means that you get to pick your own routing metric
- RON's concern is reachability, period, not latency.
- BGP doesn't broadcast alternate routes between ASes. this is how RON gets its improvement: it can identify a path through a different set of ASes that avoids the problem. this means that you need one overlay node in each AS that you care about; two nodes in the same AS won't see any improvement.
- overlays over overlays cause fairness problems. if they all see an area with no congestion and try to use it at once, then all of a sudden that will be congested.
- scalability issue with RON because of their active probing. won't scale up to more than 50 nodes.
Tuesday, October 20, 2009
White Space Networking with Wi-Fi like Connectivity
[paper]
The problem: How can we use UHF white spaces (unregistered portions of the wireless spectrum) for network connectivity? This is more challenging than standard WiFi because:
--------------------
Class notes:
White space: Lower frequency. Many frequencies are assigned but not used widely. Digital TV opened up a lot of space between channels because it is compressed with coding. Great frequencies for wide area transmissions.
Wifi = ISM
The problem: How can we use UHF white spaces (unregistered portions of the wireless spectrum) for network connectivity? This is more challenging than standard WiFi because:
- Spatial variation in spectrum matters more in white spaces because the FCC requires non-interference with wireless transmissions of incumbent users (e.g., TV).
- White spaces are more likely to have spectrum fragmentation, which each fragment potentially being a different width.
- Temporal variations because of wireless microphones. Need to immediately switch to another channel when wireless mic is transmitting.
- They propose an adaptive spectrum assignment algorithm that periodically checks space availability of both the access point AND the clients. Every AP & client maintains a spectrum map that knows what channels are in use and an estimate of how much each channel has been used. Clients periodically send the AP updates on their spectrum map. An AP looks for a new channel if an incumbent starts to use part of the channel: this can either be voluntary (incumbent is causing minor performance degradation) or involuntary (a wireless mic has completely killed the channel). When a switch happens, the AP looks for the best available space as determined by both the AP's and its clients' spectrum & availability maps. The AP then broadcasts the choice to all users. (Question: how does this broadcast work if the wireless mic is totally killing the channel?)
- Variable width channels makes AP discovery hard. They propose SIFT (Signal Interpretation before Fourier Transform) to determine packet widths based on signal amplitudes. They can then search the space using SIFT, which will figure out the width of the channels.
- This one answers my earlier question about how to handle an involuntary disconnection. Each AP maintains a backup channel. If there is a disconnection, the AP will broadcast the new channel information on the backup channel and/or the client will chirp that it's been disconnected (depending on who first discovers the disconnection).
--------------------
Class notes:
White space: Lower frequency. Many frequencies are assigned but not used widely. Digital TV opened up a lot of space between channels because it is compressed with coding. Great frequencies for wide area transmissions.
Wifi = ISM
Interactive WiFi Connectivity For Moving Vehicles
[paper]
Problem: This paper looks at how to best provide Internet connectivity to moving (i.e., vehicular) clients in a city where WiFi is ubiquitous. Their work is tested on and tuned for a city network with many overlapping base stations and bursty and independent packet losses across senders and receivers. They assume base stations can talk to each other but are bandwidth-constrained. They also want to avoid batching since they claim it increases latency & they want to support highly interactive mobile applications.
Past approaches: The standard "hard handoff" approach is to connect to a single base station and then switch to a new, "better" one when the first connection becomes too "bad". This paper evaluates five different hard handoff strategies: RSSI, BRR, Sticky, History, and BestBS. These strategies differ in how they determine when to switch between connections:
Number of packets delivered: AllBSes had the highest average number of packets delivered per day, but is within 25% of all the other methods except for Sticky, which (perhaps predictably) had by far the lowest. Distribution of session length: Median session length of AllBSes is 2x BestBS, 7x over BRR. However looking at the full distribution graph (Fig 3d), I'm not sure whether "median" properly captures the difference; AllBSes doesn't look that much better than BestBS on the graph. Periods of disconnection: On their drive, BRR had 6 disconnections, BestBS had 2, AllBSes had 0.
Their proposal: Inspired by the success of AllBSes, the authors propose ViFi. ViFi picks one main "anchor" base station using any strategy (their implementation uses the highest exponentially averaged beacon reception ratio like BRR). The mobile client can then designate other BSes as "auxiliary" connection points. If an auxiliary point hears a packet sent between the client & anchor but not an ACK, the aux BS probabilistically relays it. This is often better than retransmission by the original sender because (assuming bursty losses) if the original was lost then the resent packet is likely to be lost too. However, an aux tries to only relay (as modeled by the probability computation) if other auxiliaries are unlikely to relay, given that auxes with better connectivity have preference. Each BS knows the anchor and aux set for the client because it is periodically broadcast. Also, a new anchor will check for packets at the old anchor, which they call "salvaging." Note that ACKs may take longer than usual since there's an optional relay step in the middle that doesn't require retransmission. Also, packet reordering may occur; they claim that this is infrequent enough to not hurt TCP performance.
Comment: This reminds me of ExOR, although here they don't go for "luckiness" (the case where a packet goes unexpectedly far) -- they just try to fix "unluckiness" (a packet doesn't make it far enough) with eavesdropping on broadcast packets. Both need to pick a set of points to interact with, and each node needs to determine whether other nodes might be transmitting. ViFi is simpler though: it chooses a primary point (the anchor) and doesn't require slotting.
-------------------
Class notes:
Probabilistic choosing:
-- Which packet is supposed to forward?
-- Try to make probability that it is relayed = 1.
-- Trying to minimize # of redundant transmissions, but that is LESS important than making sure it is relayed -- transport layer protocols are usually resilient to duplication.
Salvaging has a big impact on performance because TCP is loss intolerant.
Problem: This paper looks at how to best provide Internet connectivity to moving (i.e., vehicular) clients in a city where WiFi is ubiquitous. Their work is tested on and tuned for a city network with many overlapping base stations and bursty and independent packet losses across senders and receivers. They assume base stations can talk to each other but are bandwidth-constrained. They also want to avoid batching since they claim it increases latency & they want to support highly interactive mobile applications.
Past approaches: The standard "hard handoff" approach is to connect to a single base station and then switch to a new, "better" one when the first connection becomes too "bad". This paper evaluates five different hard handoff strategies: RSSI, BRR, Sticky, History, and BestBS. These strategies differ in how they determine when to switch between connections:
- RSSI - base station strength (note: standard familiar metric),
- BRR - highest exponentially averaged beacon reception ratio,
- Sticky - stays with a base station until disconnected for a set time period, then picks highest signal strength,
- History - historic best average performance for a location,
- BestBS - for each 1sec period, uses BS with best predicted future 1sec reception ratio.
Number of packets delivered: AllBSes had the highest average number of packets delivered per day, but is within 25% of all the other methods except for Sticky, which (perhaps predictably) had by far the lowest. Distribution of session length: Median session length of AllBSes is 2x BestBS, 7x over BRR. However looking at the full distribution graph (Fig 3d), I'm not sure whether "median" properly captures the difference; AllBSes doesn't look that much better than BestBS on the graph. Periods of disconnection: On their drive, BRR had 6 disconnections, BestBS had 2, AllBSes had 0.
Their proposal: Inspired by the success of AllBSes, the authors propose ViFi. ViFi picks one main "anchor" base station using any strategy (their implementation uses the highest exponentially averaged beacon reception ratio like BRR). The mobile client can then designate other BSes as "auxiliary" connection points. If an auxiliary point hears a packet sent between the client & anchor but not an ACK, the aux BS probabilistically relays it. This is often better than retransmission by the original sender because (assuming bursty losses) if the original was lost then the resent packet is likely to be lost too. However, an aux tries to only relay (as modeled by the probability computation) if other auxiliaries are unlikely to relay, given that auxes with better connectivity have preference. Each BS knows the anchor and aux set for the client because it is periodically broadcast. Also, a new anchor will check for packets at the old anchor, which they call "salvaging." Note that ACKs may take longer than usual since there's an optional relay step in the middle that doesn't require retransmission. Also, packet reordering may occur; they claim that this is infrequent enough to not hurt TCP performance.
Comment: This reminds me of ExOR, although here they don't go for "luckiness" (the case where a packet goes unexpectedly far) -- they just try to fix "unluckiness" (a packet doesn't make it far enough) with eavesdropping on broadcast packets. Both need to pick a set of points to interact with, and each node needs to determine whether other nodes might be transmitting. ViFi is simpler though: it chooses a primary point (the anchor) and doesn't require slotting.
-------------------
Class notes:
Probabilistic choosing:
-- Which packet is supposed to forward?
-- Try to make probability that it is relayed = 1.
-- Trying to minimize # of redundant transmissions, but that is LESS important than making sure it is relayed -- transport layer protocols are usually resilient to duplication.
Salvaging has a big impact on performance because TCP is loss intolerant.
Wednesday, October 14, 2009
XORs in The Air: Practical Wireless Network Coding
[paper]
This paper uses the idea of network coding to improve throughput on wireless networks in the form of COPE. The introductory example they give is Alice and Bob each sending each other packets through 1 router. This takes 4 transmissions. Instead, the router XORs the two packets together and then broadcasts the XOR value. This is 3 transmissions. Basically, their idea is to reduce the number of packets sent by doing opportunistic coding so that end points can "figure out" what the message is without actually needing to see the message. The goal is to combine as many packets as possible into one transmission. Other approaches try to minimize the number of broadcasts to raise throughput; they instead capitalize on the idea of broadcasts as a way to minimize the overall number of transmissions. XOR is a quick, cheap operation with hardware support.
Something that was not immediately clear to me is how this works with hidden terminals. I think the solution to this is by learning neighbor state with "reception reports", and so the encoder does not assume that 2 nodes it can communicate with can also see each other's transmissions. It still seems to me though that they are going to have hidden terminal issues.
To decode, each node has a packet pool with packets it has recently received or sent; the packets are hashed and keyed by packet ID. When it receives an encoded packet, it gets the relevant packets from the packet pool if they have not yet been garbage collected. Also, they do hop-by-hop acks and retransmissions.
Their results from different toy topologies are a 1.1-1.3 throughput gain for Alice-and-Bob and X-topologies with long-lived TCP flows, and 1.35-1.5 throughput gain for the cross topology. They do a lot better with UDP flows -- 1.58-2 for Alice-and-Bob, 1.5-1.75 for X-topology, and 2-4 for cross. All of these throughput gains are less than the theoretical Coding+MAC gains because of header overhead. In a 20-node wireless ad hoc network, TCP didn't have much improvement with coding (2-3%) because of TCP backoff after a collision loss. This is a hidden terminal problem. When they bring all the nodes closer together and remove hidden terminals, they get a 38% improvement. They get a 3-4x improvement for UDP when congestion is high.
-----------------
Class notes:
-- topology matters - wheel is best
-- symmetry also matters -- need symmetry to do coding
-- hosts need to cache for long enough, and the sending proxy needs to keep track of cached state correctly
This paper uses the idea of network coding to improve throughput on wireless networks in the form of COPE. The introductory example they give is Alice and Bob each sending each other packets through 1 router. This takes 4 transmissions. Instead, the router XORs the two packets together and then broadcasts the XOR value. This is 3 transmissions. Basically, their idea is to reduce the number of packets sent by doing opportunistic coding so that end points can "figure out" what the message is without actually needing to see the message. The goal is to combine as many packets as possible into one transmission. Other approaches try to minimize the number of broadcasts to raise throughput; they instead capitalize on the idea of broadcasts as a way to minimize the overall number of transmissions. XOR is a quick, cheap operation with hardware support.
Something that was not immediately clear to me is how this works with hidden terminals. I think the solution to this is by learning neighbor state with "reception reports", and so the encoder does not assume that 2 nodes it can communicate with can also see each other's transmissions. It still seems to me though that they are going to have hidden terminal issues.
To decode, each node has a packet pool with packets it has recently received or sent; the packets are hashed and keyed by packet ID. When it receives an encoded packet, it gets the relevant packets from the packet pool if they have not yet been garbage collected. Also, they do hop-by-hop acks and retransmissions.
Their results from different toy topologies are a 1.1-1.3 throughput gain for Alice-and-Bob and X-topologies with long-lived TCP flows, and 1.35-1.5 throughput gain for the cross topology. They do a lot better with UDP flows -- 1.58-2 for Alice-and-Bob, 1.5-1.75 for X-topology, and 2-4 for cross. All of these throughput gains are less than the theoretical Coding+MAC gains because of header overhead. In a 20-node wireless ad hoc network, TCP didn't have much improvement with coding (2-3%) because of TCP backoff after a collision loss. This is a hidden terminal problem. When they bring all the nodes closer together and remove hidden terminals, they get a 38% improvement. They get a 3-4x improvement for UDP when congestion is high.
-----------------
Class notes:
-- topology matters - wheel is best
-- symmetry also matters -- need symmetry to do coding
-- hosts need to cache for long enough, and the sending proxy needs to keep track of cached state correctly
ExOR: Opportunistic Multi-Hop Routing for Wireless Networks
[paper]
"Traditional" routing protocols choose a single path for a packet before sending the packet. In contrast, "cooperative diversity schemes" simultaneously transmit information through multiple paths and the route may dynamically change. ExOR is a cooperative diversity scheme geared towards highly lossy wireless connections.
At each hop, ExOR broadcasts each packet and then chooses the next hop in the path based on who actually received the packet. The benefit of broadcasting is to increase the chance that at least one node successfully receives the packet. Unlike standard cooperative diversity schemes, only one node is chosen to forward the packet (chosen by all the recipient nodes agreeing on who the chosen sender is). ExOR batches packets together, and each packet has a list of preferred next hops. If not all the batch makes it to one node, then other nodes that have the remaining packets will forward those packets separately. Once 90% of the packets have reached the end, traditional routing is used to send the last 10%. The forward priority list is made based on ETX with only forward delivery probability.
Their evaluation was conducted on Roofnet. They measure throughput between 65 random node pairs. First to kickstart ETX they broadcast 1500-byte packets every 10 seconds for 10 minutes and distributed the delivery probabilities. Then each selected pair transferred a 1MB file using traditional routing and then 1.1MB using ExOR. They used the different sizes because in actual ExOR the last 10% is transferred using traditional routing; they chose to omit that part and only transfer the first 90% of the 1.1MB. This is kind of weird because .9*1.1=.99, not quite 1MB. This is also weird because their actual protocol isn't pure ExOR, it's a 90/10 mix of ExOR and traditional routing; you'd think they would want to measure the actual end-to-end performance of their system.
I couldn't figure out what the heck Figure 6 is showing. Why did they only show part of the second batch? Why does it look like 2 packets left N5 and 3 ended up at N24? Shouldn't N24 have only received one copy of each packet? In general though their other results show that ExOR improves throughput, with more improvement for longer traditional routes. The main benefit seems to come from ExOR's ability to use long-distance, lossy, and asymmetric links that otherwise wouldn't have been chosen by a traditional routing protocol. I wonder though whether that would be true if the traditional routing protocol used something other than ETX?
When I first read the design of ExOR, I had a question: At what point is a longer successful path (including the cost of an agreement protocol) faster than the cost of retransmission? This seems like it would be a function of how long the path is and how likely it is for the retransmission to also fail. However looking at their evaluation I get the sense that their routes must not be much longer than the traditional routes.
Also -- I am wondering about doing traditional routing but with retransmission for each hop (meaning each interior node checks to see if the next hop received it or not and it retransmits in case of failure; but only one copy is sent out). How would that compare with ExOR?
----------------------
Class notes:
-- trying to exploit luckiness - maybe a packet will make it extra far! also unluckiness - maybe it didn't make it as far as you'd expect, but still made it a bit closer to destination.
0. determine batch size / forwarding group
1. forwarding order. topo order based on ETX to DST
2. schedule transmission of local cached packets
3. approx shared view of which node has which packets
Problems with TCP:
- batching requires more packets than typical TCP window
- changes RTT estimates a lot; will make TCP retransmission timer confused
- lots of packet reordering probably
"Traditional" routing protocols choose a single path for a packet before sending the packet. In contrast, "cooperative diversity schemes" simultaneously transmit information through multiple paths and the route may dynamically change. ExOR is a cooperative diversity scheme geared towards highly lossy wireless connections.
At each hop, ExOR broadcasts each packet and then chooses the next hop in the path based on who actually received the packet. The benefit of broadcasting is to increase the chance that at least one node successfully receives the packet. Unlike standard cooperative diversity schemes, only one node is chosen to forward the packet (chosen by all the recipient nodes agreeing on who the chosen sender is). ExOR batches packets together, and each packet has a list of preferred next hops. If not all the batch makes it to one node, then other nodes that have the remaining packets will forward those packets separately. Once 90% of the packets have reached the end, traditional routing is used to send the last 10%. The forward priority list is made based on ETX with only forward delivery probability.
Their evaluation was conducted on Roofnet. They measure throughput between 65 random node pairs. First to kickstart ETX they broadcast 1500-byte packets every 10 seconds for 10 minutes and distributed the delivery probabilities. Then each selected pair transferred a 1MB file using traditional routing and then 1.1MB using ExOR. They used the different sizes because in actual ExOR the last 10% is transferred using traditional routing; they chose to omit that part and only transfer the first 90% of the 1.1MB. This is kind of weird because .9*1.1=.99, not quite 1MB. This is also weird because their actual protocol isn't pure ExOR, it's a 90/10 mix of ExOR and traditional routing; you'd think they would want to measure the actual end-to-end performance of their system.
I couldn't figure out what the heck Figure 6 is showing. Why did they only show part of the second batch? Why does it look like 2 packets left N5 and 3 ended up at N24? Shouldn't N24 have only received one copy of each packet? In general though their other results show that ExOR improves throughput, with more improvement for longer traditional routes. The main benefit seems to come from ExOR's ability to use long-distance, lossy, and asymmetric links that otherwise wouldn't have been chosen by a traditional routing protocol. I wonder though whether that would be true if the traditional routing protocol used something other than ETX?
When I first read the design of ExOR, I had a question: At what point is a longer successful path (including the cost of an agreement protocol) faster than the cost of retransmission? This seems like it would be a function of how long the path is and how likely it is for the retransmission to also fail. However looking at their evaluation I get the sense that their routes must not be much longer than the traditional routes.
Also -- I am wondering about doing traditional routing but with retransmission for each hop (meaning each interior node checks to see if the next hop received it or not and it retransmits in case of failure; but only one copy is sent out). How would that compare with ExOR?
----------------------
Class notes:
-- trying to exploit luckiness - maybe a packet will make it extra far! also unluckiness - maybe it didn't make it as far as you'd expect, but still made it a bit closer to destination.
0. determine batch size / forwarding group
1. forwarding order. topo order based on ETX to DST
2. schedule transmission of local cached packets
3. approx shared view of which node has which packets
Problems with TCP:
- batching requires more packets than typical TCP window
- changes RTT estimates a lot; will make TCP retransmission timer confused
- lots of packet reordering probably
Thursday, October 8, 2009
A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols
This paper compares four different routing protocols for ad hoc networks: DSDV, TORA, DSR, and AODV. They extend a simulator to model node mobility, a radio propagation model, radio network interfaces, and MAC DCF (which, like MACA(W) tries to reduce the probability of collisions due to hidden terminals).
DSDV: "hop-by-hop distance vector routing protocol requiring each node to periodically broadcast routing updates." Each node maintains a routing table with info about its neighbors.
TORA: goal is to find routes quickly and react to mobility changes; shortest path routing is secondary to this goal. When a node needs a route, it broadcasts a packet asking for the route which propagates through the network until it reaches the destination or a neighbor of the destination. At that point, the destination/neighbor sends back a packet with a "height" parameter that is incremented as it goes back to the requester.
DSR: source routing, so intermediate nodes don't need to maintain a whole bunch of state. Each packet has all the routing information it needs (this seems like it might be dangerous in a mobile network with rapidly changing topology). For path discovery, route requests are broadcast & the destination responds. Route maintenance occurs periodically to discover broken paths.
AODV: combination of DSR and DSDV. When a node needs a route, it broadcasts a ROUTE REQUEST. Anyone with a path will respond with that route and create a reverse route along the way to connect the two.
Simulation results... (1) Unsurprisingly, mobility impairs the performance of all of the routing protocols. (2) Huge variation between protocols in terms of overhead -- TORA (most) has an order of magnitude more than DSR (least). (3) DSDV does poorly with high rates of mobility when links are broken. (4) Despite its huge overhead, TORA is the most reliable, delivering 90+% of packets.
DSDV: "hop-by-hop distance vector routing protocol requiring each node to periodically broadcast routing updates." Each node maintains a routing table with info about its neighbors.
TORA: goal is to find routes quickly and react to mobility changes; shortest path routing is secondary to this goal. When a node needs a route, it broadcasts a packet asking for the route which propagates through the network until it reaches the destination or a neighbor of the destination. At that point, the destination/neighbor sends back a packet with a "height" parameter that is incremented as it goes back to the requester.
DSR: source routing, so intermediate nodes don't need to maintain a whole bunch of state. Each packet has all the routing information it needs (this seems like it might be dangerous in a mobile network with rapidly changing topology). For path discovery, route requests are broadcast & the destination responds. Route maintenance occurs periodically to discover broken paths.
AODV: combination of DSR and DSDV. When a node needs a route, it broadcasts a ROUTE REQUEST. Anyone with a path will respond with that route and create a reverse route along the way to connect the two.
Simulation results... (1) Unsurprisingly, mobility impairs the performance of all of the routing protocols. (2) Huge variation between protocols in terms of overhead -- TORA (most) has an order of magnitude more than DSR (least). (3) DSDV does poorly with high rates of mobility when links are broken. (4) Despite its huge overhead, TORA is the most reliable, delivering 90+% of packets.
A High-Throughput Path Metric for Multi-Hop Wireless Routing
This paper presents the ETX (Expected Transmission Count) metric, which finds the most reliable path on a multi-hop wireless network. This metric takes into account problems that cause loss on the network, unlike a simple minimum hop-count. The idea is that a longer path might still be faster than a shorter path if the longer path is more reliable. They attempt to calculate the expected number of retransmissions using packet loss measurements.
They set up a 29-node wireless testbed across five floors of an office building. They then showed that a minimum hop-count metric did not find the highest-throughput route. I'm a little suspicious of their calculation of the highest-throughput route after the fact; they have to estimate the interference on each route. I also found Figure 2 really darn confusing. It seems like the min hop-count metric gets closer to the highest-throughput as the packets per second increases, and at one point (around 200-250 pps) EXCEEDS the highest throughput??
Their experiment on the testbed shows that their design of a new metric needs to account for a wide range of loss ratios; asymmetric loss ratios; and interference between successive hops in a multi-hop path. The ETX for a single link is the predicted number of data transmissions based on the forward and reverse delivery ratios of the link. The ETX for a route is the sum of the ETX for each link in that route.
This paper fits into our ongoing discussion of how the network stack is broken up into layers. ETX assumes that the link layer is making retransmissions (since they are trying to minimize the number of retransmissions). ETX doesn't route around congestion; they say this is a bonus because it avoids oscillations, but I wonder if this actually could be a useful feature?
They then implement ETX (as part of both DSDV and DSR) and compare the paths it finds to min hop-count. I find their graphs pretty impossible to read -- I can't tell which line is which in Figure 6. Looking at Figure 7, it appears that ETX did perform better (at least on paths that were longer than one hop). One question I'd have about their methodology is whether a network should really be modeled as just random pairs of communicating nodes; it seems like network usage might be clustered in certain areas (i.e., one node is getting a lot more traffic), which would change interference patterns.
They set up a 29-node wireless testbed across five floors of an office building. They then showed that a minimum hop-count metric did not find the highest-throughput route. I'm a little suspicious of their calculation of the highest-throughput route after the fact; they have to estimate the interference on each route. I also found Figure 2 really darn confusing. It seems like the min hop-count metric gets closer to the highest-throughput as the packets per second increases, and at one point (around 200-250 pps) EXCEEDS the highest throughput??
Their experiment on the testbed shows that their design of a new metric needs to account for a wide range of loss ratios; asymmetric loss ratios; and interference between successive hops in a multi-hop path. The ETX for a single link is the predicted number of data transmissions based on the forward and reverse delivery ratios of the link. The ETX for a route is the sum of the ETX for each link in that route.
This paper fits into our ongoing discussion of how the network stack is broken up into layers. ETX assumes that the link layer is making retransmissions (since they are trying to minimize the number of retransmissions). ETX doesn't route around congestion; they say this is a bonus because it avoids oscillations, but I wonder if this actually could be a useful feature?
They then implement ETX (as part of both DSDV and DSR) and compare the paths it finds to min hop-count. I find their graphs pretty impossible to read -- I can't tell which line is which in Figure 6. Looking at Figure 7, it appears that ETX did perform better (at least on paths that were longer than one hop). One question I'd have about their methodology is whether a network should really be modeled as just random pairs of communicating nodes; it seems like network usage might be clustered in certain areas (i.e., one node is getting a lot more traffic), which would change interference patterns.
Subscribe to:
Posts (Atom)