1 Introduction
-
According to the definition and coding condition of IRNC, we figure out two following solutions to help design a coding-aware opportunistic routing. The first is which nodes should be in the forwarding list for sending an encoded packet. The second is how to measure the price of network coding in an opportunistic transmission.
-
We propose a novel coding-aware opportunistic routing scheme called HCOR, which is based on anypath routing and finds out the minimal anypath cost path as the route with network coding. Compared with conventional NCOR schemes, HCOR is more feasible on choosing the coding opportunities. Meanwhile, HCOR is designed on a ‘multihop’ network coding structure, in which much more coding opportunities can be collected than with a ‘local’ coding structure [3].
-
We implement the HCOR scheme in ns-2 and carry out extensive evaluation to show the performance of HCOR.
2 Related work
3 Overview of HCOR
Term | Definition |
---|---|
Native packet (flow) | A non-encoded packet (flow) |
Encoded packet (flow) | A packet (flow) that is the XOR of multiple native packets (flows) |
Virtual native packet (flow) | The native packet (flow) that is XORed in an encoded packet (flow) |
Overheard information | The set of nodes which have overheard the native packet (flow) |
Coding node | The node which encodes native packets together |
Decoding node | The node which decodes the encoded packets |
Forwarding lists of an encoded packet | The set of forwarding lists for the virtual native packets |
Packet ID | A 32-bit hash of the packet’s IP source address and IP sequence number |
Output queue | A FIFO queue at each node to buffer the packets that need to be sent |
Packet pool | A buffer where a node stores all packets sent and overheard in the past T seconds |
4 Network coding and anypath cost
4.1 Opportunistic transmission and anypath cost
Lemma 4.1
Lemma 4.2
4.2 Inter-flow network coding
Definition4.1.
Lemma 4.3.
Proof.
Lemma 4.4.
Proof.
4.3 General coding condition
Coding condition.
5 Network coding in anypath routing
-
What nodes should be contained in the forwarding set of a coding node in HCOR?
-
What nodes should be the coding nodes in HCOR?
5.1 Forwarding set of a coding node
Theorem 5.1.
Proof.
5.2 Network coding price in anypath transmission
6 HCOR design
6.1 Multihop overheard information
6.2 Virtual flow list
Source
and Destination
identify a flow uniquely. Coding Flag
marks that the virtual flow is a potential encoded flow, or say being an encoded status. Coding Expire
is the expired time of this flow being the encoded status. Forwarding List
is the temporary forwarding list of this encoded flow. It contains the anypath cost of every potential nexthop and is set to null if no network coding happens. Expire
is the expired time of this virtual flow.
Expire
will be reset. The other is coding update which begins only after receiving an ACK packet from a coding node (we will discuss this ACK process in the following section). In the coding update, the Coding Flag
will be set to 1, Coding Expire
will be reset, and the Forwarding List
will be modified. In every node, there is a timer to purge the virtual flow list. The virtual flow will be removed if it is expired. The Coding Flag
will be set to 0 if this virtual flow is not being an encoded flow.6.3 Coding procedure and coding feedback
src
, dst
, and cost
. The src
and dst
record the source and destination of p
k
, respectively. The pair of src
and dst
identifies the flow f
k
. The cost
records the anypath cost of f
k
after doing network coding. In Equation 8, anypath cost is related to both f
k
and f
j
. Meanwhile, the gain of network coding is only from one broadcast of the encoded packet p. Hence, we define the temporary anypath cost of f
k
after doing network coding bynexthop
k
. After the neighbor of i receives this coding feedback, its virtual flow list will be updated. The virtual flow (src,
dst)
updates its forwarding list
by modifying the anypath cost of nexthop i to cost
. After doing this, the anypath cost of node i for flow f
k
is updated to , where α=1 if , and α=0 otherwise. Based on the update of virtual flow list, the nexthops recorded in the virtual flow will be more competitive to achieve a high priority to forward this packet. If network coding disappears, no coding feedback causes no virtual flow update. After reaching the expiration time, virtual flow will be purged, and then the new packet from this flow will be forwarded following its original anypath cost.6.4 Decoding
decoding
. Because we use the XOR coding method, the encoded packet can be decoded only by XORing any of the virtual native packets, such as p1=(p1⊕p2)⊕p2.