Path selection for routing traffic in a network

• US 8,930,572 B2
• Filed: 04/29/2013
• Issued: 01/06/2015
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Yonge, Lawrence Winston III, Katar, Srinivas, Krishnam, Manjunath Anandarama
• Primary Examiner(s): TOWFIGHI, AFSHAWN M
• Application Number:
  US13/873,168
• Publication Number:
  US 20130235730A1
• Time in Patent Office: 617 Days
• Field of Search: None
• US Class Current: 709/241
• CPC Class Codes: H04B 2203/5445 Local network
• CPC Class Codes: H04L 12/2801 Broadband local area networks
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 47/787 Bandwidth trade among domains

Abstract

Methods, systems, and apparatuses are described for communicating among stations in a network. A station in the network can determine costs between that station and a headend through a number of other stations. The station can select a low cost path from among the possible paths. Cost data from the determination can be transmitted from the station to other stations in the network for use in selecting low cost paths at those stations.

Claims

1. A method comprising:

receiving, at a listening station of a network, a bandwidth of a first network section from a first station, wherein

the first network section couples the first station to a second station;

determining a bandwidth of a second network section coupling the listening station and the first station;

determining costs for a plurality of paths between the listening station and the second station based, at least in part, on received cost data related to the plurality of paths, wherein

the cost data indicates a bandwidth for a third network section coupling a third station and the second station, and

the listening station is coupled to the third station, and

a cost for a first path of the plurality of paths is determined based, at least in part, on the bandwidth of the first network section and the bandwidth of the second network section;

selecting a path from the plurality of paths based, at least in part, on the costs determined for the plurality of paths; and

transmitting, from the listening station to the network, a cost of the selected path.

2. The method of claim 1, wherein determining the costs for the plurality of paths comprises:

determining a cost for a second path of the plurality of paths based, at least in part, on the bandwidth of the third network section.

3. The method of claim 1, wherein the cost data is received from at least one other station via at least one of the plurality of paths.

4. The method of claim 1, wherein transmitting the cost of the selected path comprises:

transmitting at least one member of a group consisting of a downlink bandwidth, an uplink bandwidth, and a number of hops to reach the second station.

5. The method of claim 1, wherein selecting the path comprises selecting the path from the plurality of paths having a lowest cost.

6. The method of claim 5, wherein the path having the lowest cost is the path with at least one member of a group consisting of a highest downlink bandwidth, a lowest number of hops to the second station, and a highest uplink bandwidth.

7. The method of claim 1, wherein

the first network section comprises at least one hop between the first station and the second station, and

the bandwidth of the first network section indicates a bandwidth of a second path through the first network section that comprises the at least one hop.

8. The method of claim 1, wherein determining the costs for the plurality of paths comprises:

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

determining a downlink bandwidth of the second network section; and

determining, based at least in part, on the downlink bandwidth of the first network section and on the downlink bandwidth of the second network section, a downlink bandwidth of a composite network, wherein

the composite network includes the first network section and the second network section.

9. The method of claim 8, wherein transmitting the cost of the selected path comprises transmitting the downlink bandwidth of the composite network.

10. The method of claim 1, further comprising:

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

determining a measured downlink bandwidth of the second network section; and

determining an effective downlink bandwidth of a composite network based, at least in part, on calculating the effective downlink bandwidth according to a formula;

11. The method of claim 1, wherein

determining the bandwidth of the second network section is performed in response to the listening station being added to the network.

12. The method of claim 1, further comprising:

storing, in a routing table,

an identifier of the first station, and

cost data related to the first station.

13. The method of claim 1, wherein the cost data comprises at least one member of a group consisting of a downlink bandwidth of the first network section, a downlink bandwidth of the second network section, and a number of hops between the listening station and the first station.

14. The method of claim 1, wherein the second station is a headend station.

15. The method of claim 1, wherein

the network comprises a broadband power line network (BPLN).

16. The method of claim 15, wherein the BPLN comprises at least one member of a group consisting of low voltage lines, medium voltage lines, and high voltage lines.

17. The method of claim 15, wherein the BPLN provides broadband internet access.

18. The method of claim 15, wherein the BPLN provides smart grid management.

19. A method comprising:

determining a first bandwidth of a first network section between a first station and a second station;

determining a second bandwidth of a second network section between a listening station and the first station;

determining a cost for a first path between the listening station and the second station based, at least in part, on the first bandwidth and on the second bandwidth;

receiving cost data related to a second path, wherein

the cost data indicates a third bandwidth for a third network section between a third station and the second station, and

the listening station is coupled to the third station,

determining a cost for the second path based, at least in part, on the third bandwidth;

selecting a path from the first path and the second path based, at least in part, on the cost for the first path and the cost for the second path; and

transmitting, from the listening station to a network, a cost of the selected path.

20. The method of claim 19, wherein determining the cost for the first path is based, at least in part, on a number of hops between the listening station and the second station on the first path and determining the cost for the second path is based, at least in part, on a number of hops between the listening station and the second station on the second path.

21. The method of claim 19, wherein determining the first bandwidth is based, at least in part, on estimating a downlink bandwidth between the second station and the listening station.

22. The method of claim 19, wherein determining the first bandwidth is based, at least in part, on receiving bandwidth data from the second station.

23. The method of claim 19, wherein determining the cost for the first path is further based, at least in part, on a network load of the first path.

24. The method of claim 19, wherein the cost data is received periodically.

25. The method of claim 19, wherein the cost data is included in a beacon message.

26. The method of claim 19, wherein

the cost data indicates that the third network section comprises at least one hop between the third station and the second station, and

the second path comprises the at least one hop.

27. The method of claim 19, wherein selecting the path is based, at least in part, on selecting the path having a lowest cost.

28. The method of claim 27, wherein selecting the path having the lowest cost comprises selecting the path with at least one member of a group consisting of:

a highest bandwidth, and

a fewest number of hops.

29. The method of claim 27, wherein

determining the first bandwidth is performed in response to the first station being added to the network.

30. The method of claim 19, wherein the cost of the selected path is periodically transmitted by the listening station.

31. A first station comprising:

a network interface module to;

receive bandwidth data from a second station indicating a bandwidth of a first network section coupling the second station to a third station;

determine a bandwidth of a second network section coupling the first station to the second station;

determine costs for a plurality of paths between the first station and the third station, where

the network interface module to determine the costs comprises the network interface module to receive cost data related to the plurality of paths, wherein

the cost data indicates a bandwidth for a third network section coupling a fourth station to the third station, and

the first station is coupled to the fourth station, and

a cost for a first of the plurality of paths is determined based, at least in part, on the bandwidth of the first network section and the bandwidth of the second network section;

select a path from the plurality of paths based, at least in part, on the costs determined for the plurality of paths; and

transmit, from the first station to a network, a cost of the selected path.

32. The first station of claim 31, wherein the network interface module to select the path comprises the network interface module to select the path with a lowest cost from the plurality of paths.

33. The first station of claim 32, wherein the path with the lowest cost is the path with at least one member of a group consisting of a highest downlink bandwidth and a highest uplink bandwidth.

34. The first station of claim 32, wherein the path with the lowest cost is the path having a lowest number of hops to the third station.

35. A non-transitory computer-readable medium comprising program instructions, the program instructions to:

receive bandwidth data from a first station indicating a bandwidth of a first network section coupling the first station and a second station;

determine a bandwidth of a second network section coupling a listening station and the first station;

determine costs for a plurality of paths between the listening station and the second station, by receiving cost data related to the plurality of paths, wherein

the cost data indicates a bandwidth for a third network section coupling a third station and the second station, and

the listening station is coupled to the third station, and

a cost for a first path of the plurality of paths is determined based, at least in part, on the bandwidth of the first network section and the bandwidth of the second network section;

select a path from the plurality of paths based, at least in part, on the costs determined for the plurality of paths; and

transmit, from the listening station to the network, a cost of the selected path.

36. The non-transitory computer-readable medium of claim 35, wherein the program instructions to determine the costs for the plurality of paths comprises the program instructions:

determine a cost for a second path of the plurality of paths based, at least in part, on the bandwidth of the third network section.

37. The non-transitory computer-readable memory medium of claim 35, wherein the cost data is received from at least one other station via at least one of the plurality of paths.

38. The non-transitory computer-readable medium of claim 35, wherein the program instructions to transmit the cost of the selected path comprises the program instructions to:

transmit at least one member of a group consisting of a downlink bandwidth, an uplink bandwidth, and a number of hops to reach the second station.

39. The non-transitory computer-readable medium of claim 35, wherein the program instructions to select the path comprises the program instructions to select the path from the plurality of paths having a lowest cost.

40. The non-transitory computer-readable medium of claim 35, wherein the program instructions to determine the costs for the plurality of paths comprises the program instructions to:

receive bandwidth data from the first station indicating a downlink bandwidth of the first network section;

determine a downlink bandwidth of the second network section; and

determine, based at least in part, on the downlink bandwidth of the first network section and on the downlink bandwidth of the second network section, the downlink bandwidth of a composite network, wherein the composite network includes the first network section and the second network section.