Path estimation in a wireless mesh network
AssigneeMicrosoft Corporation
InventorsBozidar Radunovic, Christos Gkantsidis, Dinan Gunawardena, Peter B. Key
Life of this patent
Estimating the term…
Abstract
In example methods and algorithms, a node in a wireless mesh network calculates an estimated cost for a packet flow through the node. The estimation may be based on the back-log at the node and the cost of downstream neighbor nodes for the flow. Further, selection of a downstream flow and a downstream neighbor node may be based on the estimation. A packet re-ordering algorithm is also described which intercepts packets received at a node and delays delivery of the packet to the IP layer if an earlier packet in the sequence of packets has not been received.
Claims20
A method of operating a node in a wireless mesh network comprising:
- receiving a node cost from each of a plurality of downstream neighbor nodes;
- selecting a flow from a set of flows passing through the node, the selecting comprising selecting the flow having a queue of packets that will take a longest time to clear relative to other flows passing through the node;
- selecting a destination node for a packet from said flow, the destination node being selected from a set of downstream neighbor nodes associated with said flow and being selected based at least on a node cost for said flow received from each of the set of downstream neighbor nodes;
- and
- forwarding the packet to the selected destination node.
A method of operating a node in a wireless mesh network comprising:
- receiving, at an upstream node, cost data from a plurality of downstream nodes;
- selecting said node to receive one or more packets based at least on the cost data received at the upstream node;
- receiving, at said node, a first packet from a flow passing through the upstream node, the flow having a queue of packets taking a longest time to clear relative to other flows passing through the upstream node;
- on receipt of the first packet from a sequence of packets, determining if all packets prior to said first packet in said sequence have been received;
- and
- when a packet prior to said first packet in said sequence has not been received, delaying delivery of said first packet to a higher layer in a protocol stack at said node.
One or more tangible storage devices with computer-executable instructions stored thereon for performing steps comprising:
- when an opportunity to transmit a packet occurs at a node in a wireless mesh network, selecting a flow from a set of packet flows through said node, the flow being selected based on at least a queue size at said node for each of the set of packet flows and on node costs received from a plurality of downstream neighbor nodes,
- wherein the selecting comprises selecting the flow having a queue of packets that will take a longest time to clear relative to other flows passing through said node;
- selecting a destination node for transmission of a packet, the destination node being selected from a set of downstream neighbor nodes for the selected flow and being selected based on at least a node cost of each of the set of downstream neighbor nodes for said flow and a transmission rate from said node to each of the set of downstream neighbor nodes;
- and
- forwarding the packet to the selected destination node.
Dependencies are inferred from the claim text.