Method, system, network nodes, routers and program for bandwidth estimation in multi-hop networks

A router comprising:

• a storage device configured to store a computer program;
• a communication section;
• and
• a processor for executing the computer program stored in the storage device,
• wherein, when the router receives probe packets from a node whose address is the same as a source address in the probe packets, the probe packets having a destination of a destination node, the processor is configured to measure a bandwidth on a link between the router and another router which is a next hop router in a multi-hop path to the destination node, the next hop router being determined by the routing protocol, generate a bandwidth discovery packet including the measured bandwidth, and transmit the bandwidth discovery packet to the next hop router and relaying the probe packets to the next hop router;
• wherein when router receives probe packets from another router and the bandwidth discovery packet, the processor is configured to determine if the router is a last-hop router on the multi-hop path to the destination node based upon the routing protocol, wherein if the router is not the last-hop router, the processor is configured measure a bandwidth on a link between the router and another router which is a next hop router in the multi-hop path to the destination node, the next hop router being determined by the routing protocol, compare the measured bandwidth on the link between the router and the next hop router with the measured bandwidth from the bandwidth discovery packet, modify the measured bandwidth from the bandwidth discovery packet based upon the comparing, transmit the bandwidth discovery packet to the next hop router, relay the probe packets and record either the modified the measured bandwidth from the bandwidth discovery packet or an unmodified measured bandwidth from the bandwidth discovery packet as a recorded bandwidth;
• and
• wherein when router receives probe packets from another router and the bandwidth discovery packet, the processor, is configured to determine if the router is a last-hop router on the multi-hop path to the destination node based upon the routing protocol, wherein if the router is the last-hop router, the processor is configured to record the measured bandwidth from the bandwidth discovery packet in the storage device, adjust the delay between the probe packets based upon the measured bandwidth from the bandwidth discovery packet and relay the probe packets to the destination node.

A method for determining a bottleneck bandwidth on a multi-hop path between a first and a second encrypted network endpoint comprising:

• receiving a first set of probe packets from a first host node by a last hop node in the multi-hop path, the last hop node being determined by a routing protocol, the first set of probe packets being relayed via the multi-hop path to the last hop node, the first set of probe packets being encrypted by the first encrypted network endpoint;
• receiving a second set of probe packets from a second host node by the last hop node, the second set of probe packets being encrypted by the second encrypted network endpoint,
• generating a bandwidth discovery packet including a maximum recordable bandwidth at a last hop node in a multi-hop path between the first and the second encrypted network endpoints;
• transmitting the bandwidth discovery packet to previous hop node, the previous hop node being a node within the multi-hop path that directly transmitted the first set of probe packets to the last hop node;
• relaying the second set of probe packets to the previous hop node;
• determining if the previous hop node is a first hop node on the multi-hop path based upon the routing protocol, wherein if the previous hop node is the first hop node, the method further comprises:
• recording the bandwidth from the bandwidth discovery packet;
• adjusting the delay between probe packets in the second set of probe packets based upon the bandwidth from the bandwidth discovery packet;
• and
• relaying the second set of probe packets to the first encrypted network endpoint, where the first encrypted network endpoint transmits the second set of probe packets to the first host node.