Multirate Anypath Routing

In classic wireless network routing, each node forwards a packet to a single next hop. As a result, if the transmission to that next hop fails, the node needs to retransmit the packet even though other neighbors may have overheard it. In contrast, in anypath routing, each node broadcasts a packet to multiple next hops simultaneously. Therefore, if the transmission to one neighbor fails, an alternative neighbor who received the packet can forward it on. We define this set of multiple next hops as the forwarding set. A different forwarding set is used to reach each destination, in the same way a distinct next hop is used for each destination in classic routing.

When a packet is broadcast to the forwarding set, more than one node may receive the same packet. To avoid unnecessary duplicate forwarding, only one of these nodes should forward the packet on. For this purpose, each node in the set has a priority in relaying the received packet. A node only forwards a packet if all higher priority nodes in the set failed to do so. Higher priorities are assigned to nodes with shorter distances to the destination. As a result, if the node with the shortest distance in the forwarding set successfully received the packet, it forwards the packet to the destination while others suppress their transmission. Otherwise, the node with the second shortest distance forwards the packet, and so on. The source keeps rebroadcasting the packet until someone in the forwarding set receives it or a threshold is reached. Once a neighbor in the set receives the packet, this neighbor repeats the same procedure until the packet is delivered to the destination.

Since we now use a set of next hops to forward packets, every two nodes are connected through a mesh composed of the union of multiple paths. Figure 1 depicts this scenario where each node uses a set of neighbors to forward packets. The forwarding sets are defined by the multiple bold arrows leaving each node. We define this union of paths between two nodes as an anypath. In the figure, the anypath shown in bold is composed by the union of 11 different paths between a source s and a destination d. Depending on the choice of each forwarding set, different paths are included in or excluded from the anypath. At every hop, only a single node of the set forwards the packet on. Consequently, every packet from s traverses only one of the available paths to reach d. We show a path possibly taken by a packet using a dashed line. Succeeding packets, however, may take completely different paths; hence the name anypath. The path taken is determined on-the-fly, depending on which nodes of the forwarding set successfully receive the packet at each hop.


Figure 1 - An anypath connecting nodes s and d is shown in bold arrows. The anypath is composed of the union of 11 paths between the two nodes. Every packet sent from s traverses one of these paths to reach d, such as the path shown with a dashed line. Different packets may traverse different paths, depending on who receives the packet at each hop; hence the name anypath.

Existing work on anypath routing has focused on wireless networks that use a single transmission rate. This approach, albeit straightforward, presents two major drawbacks. First, using a single rate over the entire network underutilizes available bandwidth resources. Some links may perform well at a higher rate, while others may only work at a lower rate. Secondly and most importantly, the network may become disconnected at a higher bit rate. The key problem is that higher transmission rates have a shorter radio range, which reduces network density and connectivity. As the bit rate increases, links becomes lossier and the network eventually gets disconnected. Therefore, in order to guarantee connectivity, single-rate anypath routing must be limited to low rates.

In multirate anypath routing, these problems do not exist; however, we face different challenges. First, we must find not only the forwarding set, but also the transmission rate at each hop that jointly minimizes its cost to a destination. Secondly, loss probabilities usually increase with higher transmission rates, so a higher bit rate does not always improve throughput. Finally, higher rates have a shorter radio range and therefore we have a different connectivity graph for each rate. Lower rates have more neighbors available for inclusion in the forwarding set (i.e., more spatial diversity) and less hops between nodes. Higher rates have less neighbors available for the forwarding set (i.e., less spatial diversity) and longer routes. Finding the optimal operation point in this tradeoff is the focus of this work.

To date, the problem of how to select the transmission rate for anypath routing is still open. We provide a solution to this problem and incorporate the multirate capability inherent in IEEE 802.11 networks into anypath routing. For each destination, a node keeps both a forwarding set and a transmission rate used to reach this set. As a result, every two nodes will be connected through a mesh composed of the union of multiple paths, with each node transmitting at a selected rate. Figure 2 depicts the scenario where nodes use a selected bit rate to forward packets to a set of neighbors. We define this union of paths between two nodes, with each node using a potentially different bit rate as a multirate anypath. In the figure, assume that a packet is sent from s to d over the multirate anypath. Only one of the available paths is traversed depending on which nodes successfully receive the packet at each hop. We show a path possibly taken by the packet using dashed lines. We use different dash lengths to represent the different transmission rates used by each node. A shorter dash represents a shorter time to send a packet, hence a higher transmission rate. Succeeding packets may take completely different paths with other transmission rates along its way.


Figure 2 - A multirate anypath connecting nodes s and d is shown in bold arrows. Every packet sent from s traverses a path to reach d, such as the path shown with dashed lines. Different dash lengths represent the different bit rates used by each node, with a shorter dash for higher rates.

We address the problem of finding both the forwarding set and the transmission rate that minimize the overall cost to reach a particular destination. We call this the shortest multirate anypath problem, which generalizes the shortest anypath problem for the multirate scenario. Interestingly, the shortest multirate anypath will always have equal or lower cost than the shortest single path. Among all possible multirate anypaths between two nodes, we also have the shortest path. As a result, the cost of the shortest multirate anypath can never be higher than the cost of the shortest path. Likewise, due to the same argument, the shortest multirate anypath will also have equal or lower cost than any shortest anypath using a single rate.

Publications

  1. Rafael Laufer, Henri Dubois-Ferrière, Leonard Kleinrock, "Multirate Anypath Routing in Wireless Mesh Networks," IEEE INFOCOM'2009, Rio de Janeiro, Brazil, April 2009. [PDF] [PPT]

  2. Rafael Lauferand Leonard Kleinrock, "Multirate Anypath Routing in Wireless Mesh Networks," Technical Report UCLA-CSD-TR080025, UCLA Computer Science Department, August 2008. [PDF]

Source Code

File Size Date Version MD5sum
smaf-1.0.tar.gz 21KB 03/2009 1.0 d353d408bfa8a00f21487d4cf66d0887
This program is a simple proof of concept of multirate anypath routing. Given a topology file, it is possible to calculate the shortest multirate anypath from every node to a particular destination. It also calculates the shortest multirate anypath between every pair of nodes. The topology we used in the INFOCOM paper is provided as an example.

Generalized Bloom Filter

As the standard filter, the Generalized Bloom Filter is also a data structure used to represent a set S = {s1,s2,...,sn} of n elements in a compact form. It is constituted by an array of m bits and by k0 + k1 independent hash functions g1,g2,...,gk0,h1,h2,...,hk1 whose outputs are uniformly distributed over the discrete range {0,1,...,m - 1}. The GBF is built in a similar way to the standard filter. Nevertheless, the initial value of the bits of the array is not restricted to zero anymore. In the GBF, these bits can be initialized to any value. For each element si ∈ S, the bits corresponding to the positions g1(si),g2(si),...,gk0(si) are reset and the bits corresponding to the positions h1(si),h2(si),...,hk1(si) are set. In the case of a collision between a function gi and a function hj for the same element, we arbitrate that the resulting bit in the filter is always reset. The same bit can be set or reset several times without restrictions. Figure 2 depicts how an element is inserted into a Generalized Bloom Filter (GBF). After inserting the elements, membership queries can be easily conducted. To check if an element x belongs to S, we check if the bits of the array corresponding to the positions g1(x),g2(x),...,gk0(x) are all reset and if the bits h1(x),h2(x),...,hk1(x) are all set. If at least one bit is inverted, then x ∉ S with high probability. In the GBF, it is possible that an element x ∈ S may not be recognized as an element of the set, creating a false negative. Such anomaly happens when at least one of the bits g1(x),g2(x),...,gk0(x) is set or one of the bits h1(x),h2(x),...,hk1(x) is reset by another element inserted afterwards. On the other hand, if no bit is inverted, then x ∈ S also with high probability. In fact, an element x ∉ S may be recognized as an element of the set, creating a false positive. A false positive occurs when the bits g1(x),g2(x),...,gk0(x) are all reset and the bits h1(x),h2(x),...,hk1(x) are all set due to other inserted elements or due to the initial condition of the bit array.


Figure 2 - Insertion of an element into a Generalized Bloom Filter.

The main advantage of the Generalized Bloom Filter is that both the false-positive and the false-negative ratios are upper bounded. In addition, these upper bounds depend only on the chosen parameters of the filter and not on its initial condition. As a result, it can be used in distributed applications that require a secure and space-efficient set representation. See the publications for details.

Publications

  1. Rafael P. Laufer , Pedro B. Velloso, Daniel de O. Cunha, Igor M. Moraes, Marco D. D. Bicudo, Marcelo D. D. Moreira, and Otto Carlos M. B. Duarte, "Towards Stateless Single-Packet IP Traceback," 32nd IEEE Conference on Local Computer Networks - LCN'2007, Dublin, Ireland, October 2007. [PDF]

  2. Rafael P. Laufer, Pedro B. Velloso, Otto Carlos M. B. Duarte, "Generalized Bloom Filters," Technical Report GTA-05-43, COPPE/UFRJ, September 2005. [PDF]

  3. Rafael P. Laufer, Pedro B. Velloso, Daniel de O. Cunha, Igor M. Moraes, Marco D. D. Bicudo, Marcelo D. D. Moreira, Otto Carlos M. B. Duarte, "Towards Stateless Single-Packet IP Traceback," Technical Report GTA-06-38, COPPE/UFRJ, December 2006. [PDF]

  4. Rafael P. Laufer, Pedro B. Velloso, Daniel de O. Cunha, Igor M. Moraes, Marco D. D. Bicudo, and Otto Carlos M. B. Duarte, "A New IP Traceback System against Denial-of-Service Attacks", 12th International Conference on Telecommunications - ICT'2005, May, 2005. Capetown, South Africa. [PDF]

In Portuguese

  1. Marcelo D. D. Moreira, Gustavo L. Coutinho, Igor M. Moraes, Rafael P. Laufer, and Otto Carlos M. B. Duarte, "RAT: Implementação de um Serviço de Rastreamento de Pacotes," XI Workshop de Gerência e Operação de Redes e Serviços - WGRS'2006, Curitiba, PR, Brazil, May 2006. [PDF]

  2. Rafael P. Laufer, Igor M. Moraes, Pedro B. Velloso, Marco D. D. Bicudo, Miguel Elias M. Campista, Daniel de O. Cunha, Luís Henrique M. K. Costa, and Otto Carlos M. B. Duarte, "Negação de Serviço: Ataques e Contramedidas", Minicursos do Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais - SBSeg'2005, September 2005. Florianópolis, Brazil. [PDF]

  3. Rafael P. Laufer, Pedro B. Velloso, Daniel de O. Cunha, and Otto Carlos M. B. Duarte, "Um Procedimento Alternativo de Reconstrução de Rota para o Rastreamento de Pacotes IP", XXII Simpósio Brasileiro de Telecomunicações - SBrT'05, September 2005. Campinas, Brazil. [PDF]

  4. Rafael P. Laufer, Pedro B. Velloso, and Otto Carlos M. B. Duarte, "Um Novo Sistema de Rastreamento de Pacotes IP contra Ataques de Negação de Serviço", XXIII Simpósio Brasileiro de Redes de Computadores - SBRC'2005, May 2005. Fortaleza, Brazil. [PDF]

  5. Rafael P. Laufer, "Rastreamento de Pacotes IP contra Ataques de Negação de Serviço," M.Sc. Thesis, Universidade Federal do Rio de Janeiro - UFRJ, September 2005. [PDF]

Source Code

File Size Date Version MD5sum
gbf-1.0.tar.gz 4KB 09/2005 1.0 2845d73cff3c2983aa3a7013142ffc71
This program implements the Generalized Bloom Filter using a universal class of hash functions. The class used is defined as follows. Let the elements be integers from the universe S={1, 2,..., z - 1} and let the output range of the hash functions be {0, 1,..., m - 1}. The class H of hash transformations hc,d which map an element x ∈ S into the respective range is
H = {hc,d(.) | 0 < c < z, 0 ≤ z},
 (1)

where
hc,d(x) = [(cx + d) mod z] mod m.
(2)

The numbers c and d are integers within the interval defined by (1). For each hash function, c and d are arbitrarily chosen. The integer z is defined as a large prime.
gbf_traceback-1.0.tar.gz 77KB 09/2005 1.0 85d6342500c52aea718fe24b1a18aea8
This program simulates the proposed IP traceback scheme in an Internet-based topology. For each attack, one packet is sent towards the victim. The packet contains a GBF which stores the digests of the IP addresses of the traversed router. Once the packet reaches the victim, the reconstruction procedure starts. Two reconstruction procedures are implemented. In first one, each router tests its neighbors against the filter. When the router detects that a neighbor router is also in the filter, it forwards the GBF to that router so that the reconstruction procedure can proceed towards the attacker. The second procedure improves the false-negative ratio of the first procedure by using information from the previous routers in the reconstructed path. See [2] for details.


CSS Template courtesy of DesignsByDarren
Valid XHTML 1.0 Transitional