METHOD OF ROUTING TRAFFIC IN A NETWORK

• US 20080298252A1
• Filed: 04/23/2008
• Published: 12/04/2008
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: Qualcomm Atheros Incorporated (Qualcomm, Inc.)
• Original Assignee: Intellon Corporation (Qualcomm, Inc.)
• Inventors: Yonge, Lawrence W. III, Krishnam, Manjunath, Katar, Srinivas
• Granted Patent: US 8,510,470 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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 and selecting 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 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;

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 the 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 headend comprises:

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

measuring the downlink bandwidth of a second network section, the second network section connecting the determining station and the first station; and

estimating the effective downlink bandwidth of a composite network section, the composite network section connecting the determining station and the headend.

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:

${\mathrm{BW\_Eff}}_{\mathrm{comp}}=\frac{1}{\frac{1}{{\mathrm{BW\_Eff}}_{\mathrm{first}}}+\frac{1}{\mathrm{BW\_Meas}}}$

wherein BW_Eff_comp is the effective downlink bandwidth of the composite network, BW_Eff_first is 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 1, wherein determining costs between the determining station and the headend comprises:

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

measuring the uplink bandwidth of a second network section, the second network section connecting the determining station and the first station; and

estimating the effective uplink bandwidth of a composite network section, the composite network section connecting the determining station and the headend.

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

${\mathrm{BW\_Eff}}_{\mathrm{comp}}=\frac{1}{\frac{1}{{\mathrm{BW\_Eff}}_{\mathrm{first}}}+\frac{1}{\mathrm{BW\_Meas}}}$

wherein BW_Eff_comp is the effective uplink bandwidth of the composite network, BW_Eff_first is the effective uplink bandwidth of the first network section, and BW_Meas is the measured uplink bandwidth of the second network section.

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

transmitting the effective uplink bandwidth of the composite network.

15. The method of claim 1 further comprising:

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

16. The method of claim 15, further comprising:

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

dropping the packet if the hop count is zero.

17. The method of claim 1 further comprising:

receiving a data packet at the determining station from the headend through the selected 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 hop count is zero.

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

20. The method of claim 19, wherein the power lines are transmission lines.

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

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

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

24. The method of claim 23, wherein the wide area network is the Internet.

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

26. The method of claim 1, further comprising:

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

27. The method of claim 26 further comprising:

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

28. The method of claim 27, 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.

29. The method of claim 27, further comprising:

transmitting the cost parameter value in a periodic beacon message.

30. The method of claim 26 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.

31. The method of claim 30, further comprising:

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

32. The method of claim 26 further comprising:

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

33. 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 a route update request to an upstream station.

34. The method of claim 33, wherein transmitting a route update request to an upstream station comprises:

transmitting the list of station identifiers and associated servicing station identifiers to the upstream station.

35. The method of claim 34, wherein the upstream station is a next hop station corresponding to a next hop station identifier stored in the routing table.

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

monitoring periodic beacon messages from a first and a second upstream station at a monitoring station, the first upstream station being designated as a next upstream hop station for the current station, the beacon messages including first and second cost data for communicating with a headend through the first and second upstream station respectively.

37. The method of claim 36 further comprising:

sending network traffic to the second upstream station based on a comparison of the first and second cost data.

38. The method of claim 37 further comprising:

receiving network traffic at the second upstream station;

storing a station identifier of the monitoring station in a routing table of the upstream station; and

forwarding the network traffic.

39. A network station configured to:

determine costs between the network station and a headend for a plurality of paths through a respective plurality of stations;

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

transmit the determined cost of the selected low cost path.

40. The network station of claim 39, 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.