Both begin with the observation that although it may be convenient to treat wireless routing graphs as though they were wired networks, it doesn't make sense. Issues like hidden terminals, the capture effect and asymmetric links frustrate this model, making layering violations like forcing reliable transfer facilities into the link layer mandatory for reasonable performance. Instead of maintaining this model and hacking the protocols to mask the problems, both papers argue that wireless routing should embrace the broadcast nature of the medium: blast as much information onto the grid as possible.
The first paper (EXOR, as in logical exclusive OR, as in, an exclusive OR of the recipients of a broadcast message is elected as the forwarder) uses multi-pathing and synchronization to address the issue of lossy links. The decision about who is the next-hop forwarder is made AFTER all the candidate forwarders receive the message: ideally, the node among them closest to the destination should send as many of the packets it can, saving hops. Even better, assuming lossy links it is likely that this ideal forwarder has received only a subset of the total transmission: in lock step, after its transmission, the other candidates have opportunities to forward on the subset of packets not already transmitted by higher priority hosts. Thus, messages are sent in parallel through several paths in the network, and it is easy to see how this improves throughput and reduces retransmissions. On the surface, this sounds like it could be a complicated and message-expensive approach (consensus and leader election protocols are hard) but the paper shows how the order and timing can be decided deterministically.
The second paper (XOR, as in bitwise exclusive OR), though inspired by similar principles, takes a quite different approach. Given broadcast (actually, pseudo-broadcast, for the reliability reasons discussed) communication, many bottlenecked topologies could benefit by increasing the information content of individual packets (this means fewer transmissions generally AND passing more data through a congested network). The idea is to broadcast coded packets containing the XOR'd information from as many native packets as possible, with the constraint that the next node must have received ALL component packets except the one destined to it. Given this constraint and a packet header with the list of packet ids encoded in the payload, it is a simple matter to repeatedly XOR the packet with all of the component packets: the result is the new native packet addressed to you. The authors show that the potential information gain due to this form of compression is 2, but that because this approach allows greater utilization of networks with full queues, the actual gain is much greater than that: in fact, with the right topology and congestion conditions is it unbounded.
No comments:
Post a Comment