Path selection for routing traffic in a network

1. A method for communicating among stations in a network comprising:

at a determining station

determining costs between the determining station and a headend for a plurality of paths through a respective plurality of stations, the determining comprising:

receiving bandwidth data from a first station indicating an effective bandwidth of a first network section, the first network section connecting the first station and the headend,

measuring a bandwidth of a second network section, the second network section connecting the determining station and the first station, wherein measuring includes determining a network load between the determining station and the first station during a listening period, and

estimating an effective bandwidth of a composite network that comprises the first network section and the second network section based on the effective bandwidth of the first network section and the measured bandwidth of the second network section, the composite network connecting the determining station and the headend through the first station;

selecting a low cost path between the determining station and the headend based on the determined costs; and

transmitting the determined cost of the selected low cost path.

2. The method of claim 1 , wherein determining costs between the determining station and the headend comprises:

receiving cost data from the plurality of stations; and

estimating the cost between the determining station and the headend through at least two of the plurality of stations.

3. The method of claim 2 , wherein cost data is periodically transmitted by the plurality of stations.

4. The method of claim 1 , wherein selecting a low cost path comprises:

selecting a path from among the pluralities of paths having a lowest estimated cost.

5. The method of claim 4 , wherein the path having the lowest estimated cost is a path having the highest estimated downlink bandwidth.

6. The method of claim 4 , wherein the path having the lowest estimated cost is a path having the highest estimated uplink bandwidth.

7. The method of claim 4 , wherein the path with the lowest estimated cost is a path having the lowest number of hops to the headend.

8. The method of claim 1 , wherein transmitting the determined cost of selected low cost path comprises:

transmitting at least one of: an estimated downlink bandwidth, an estimated uplink bandwidth, and a number of hops to reach the headend.

9. The method of claim 1 , wherein determining costs between the determining station and the head end comprises:

receiving bandwidth data from the first station indicating the effective downlink bandwidth of the first network section;

measuring the downlink bandwidth of the second network section; and

estimating the effective downlink bandwidth of the composite network.

10. The method of claim 9 , wherein estimating the effective downlink bandwidth of the composite network comprises calculating the effective downlink bandwidth of the composite network according to the formula:

BW_Eff

comp

=

1

1

BW_Eff

first

+

1

BW_Meas

wherein BW_E.ffcomp is the effective downlink bandwidth of the composite network, BW_E.fftzrstiS the effective downlink bandwidth of the first network section, and BW Meas is the measured downlink bandwidth of the second network section.

11. The method of claim 9 , wherein transmitting the determined cost of the selected low cost path comprises:

transmitting the effective downlink bandwidth of the composite network.

12. The method of claim 9 , wherein estimating the effective downlink bandwidth of the composite network comprises calculating the effective downlink bandwidth of the composite network based on: the effective downlink bandwidth of the first network section, and the measured downlink bandwidth of the second network section.

13. The method of claim 1 , wherein determining costs between the determining station and the head end comprises:

receiving bandwidth data from the first station indicating the effective uplink bandwidth of the first network section;

measuring the uplink bandwidth of the second network section; and

estimating the effective uplink bandwidth of the composite network.

14. The method of claim 13 , wherein estimating the effective uplink bandwidth of the composite network comprises calculating the effective uplink bandwidth of the composite network according to the formula:

BW_Eff

comp

=

1

1

BW_Eff

first

+

1

BW_Meas

wherein BW_E.ffcomp is the effective uplink bandwidth of the composite network, BW_E.flfirstis the effective uplink bandwidth of the first network section, and BW_Meas is the measured uplink bandwidth of the second network section.

15. The method of claim 13 , wherein transmitting the determined cost of the selected low cost path comprises:

transmitting the effective uplink bandwidth of the composite network.

16. The method of claim 13 , wherein estimating the effective uplink bandwidth of the composite network comprises calculating the effective uplink bandwidth of the composite network based on: the effective uplink bandwidth of the first network section, and the measured uplink bandwidth of the second network section.

17. The method of claim 1 further comprising:

transmitting a data packet from the determining station to the headend through the selected low cost path.

18. The method of claim 17 , further comprising:

decrementing a maximum hop count of the data packet at an intermediate station; and

dropping the packet if the maximum hop count is zero.

19. The method of claim 1 further comprising:

receiving a data packet at the determining station from the headend through the selected low cost path.

20. The method of claim 19 , further comprising:

decrementing a maximum hop count of the data packet at an intermediate station; and

dropping the packet if the maximum hop count is zero.

21. The method of claim 1 , wherein the network comprises a plurality of power lines.

22. The method of claim 21 , wherein the power lines are transmission lines.

23. The method of claim 21 , wherein the power lines are distribution lines.

24. The method of claim 21 , wherein the headend routes Internet traffic to a power line network.

25. The method of claim 21 , wherein the headend connects a power line network to a wide area network.

26. The method of claim 25 , wherein the wide area network is the Internet.

27. The method of claim 21 , wherein the network is configured to provide broadband Internet access to a plurality of subscribers.

28. The method of claim 1 , further comprising:

storing an identifier of the first station of the selected low cost path in a routing table.

29. The method of claim 28 further comprising:

storing a value of a cost parameter in the routing table.

30. The method of claim 29 , wherein the cost parameter comprises at least one of:

an estimated effective downlink bandwidth between the determining station and the headend, an estimated effective uplink bandwidth between the determining station and the headend, and a number of hops between the determining station and the headend.

31. The method of claim 29 , further comprising:

transmitting the cost parameter value in a periodic beacon message.

32. The method of claim 28 further comprising:

storing an estimated effective downlink bandwidth between the determining station and the headend in the routing table;

storing an estimated effective uplink bandwidth between the determining station and the headend in the routing table;

storing a number of hops from between the determining station and the headend in the routing table.

33. The method of claim 32 , further comprising:

transmitting the effective downlink bandwidth, the effective uplink bandwidth, and the number of hops in a periodic beacon message.

34. The method of claim 28 further comprising:

storing a list of downstream station identifiers in the routing table, each downstream station more than one hop away from a current station being associated with a corresponding next hop station identifier through which the downstream station can be reached.

35. A method for communicating among stations in a network comprising:

receiving a route update request from a downstream station at a current station, the route update request including a list of station identifiers corresponding to stations that can be reached through the downstream station;

updating a routing table by storing the list of stations identifiers in the routing table, the list of stations being stored with an association to a servicing station identifier, the servicing station identifier being an identifier of the downstream station, the association indicating that the stations can be reached via the downstream station; and

transmitting the route update request that was received at the current station to an upstream station from the current station;

wherein the transmitting the route update request comprises transmitting the list of station identifiers and associated servicing station identifier to the upstream station, the upstream station being a next hop station corresponding to a next hop station identifier stored in the routing table.

36. A network station comprising:

a network interface module configured to:

determine costs between the network station and a headend for a plurality of paths through a respective plurality of stations, the determining comprising:

receiving bandwidth data from a first station indicating an effective bandwidth of a first network section, the first network section connecting the first station and the headend,

measuring a bandwidth of a second network section, the second network section connecting the network station and the first station, wherein measuring includes determining a network load between the determining station and the first station during a listening period, and

estimating an effective bandwidth of a composite network that comprises the first network section and the second network section based on the effective bandwidth of the first network section and the measured bandwidth of the second network section, the composite network connecting the network station and the headend through the first station; and

select a low cost path between the network station and the headend based on the determined costs; and

communication circuitry configured to transmit the determined cost of the selected low cost path.

37. The network station of claim 36 , wherein:

the network station is configured to determine costs between the network station and the headend by:

receiving cost data from the plurality of stations; and

estimating the cost between the determining station and the headend through at least two of the plurality of stations, and

the network station is configured to select a low cost path by:

selecting a path from among the pluralities of paths having a lowest estimated cost.