Method for routing traffic using traffic weighting factors

Patent metadata

Field	Value
Publication number	US-9160649-B2
Application number	US-95116904-A
Country	US
Kind code	B2
Filing date	Sep 27, 2004
Priority date	Sep 27, 2004
Publication date	Oct 13, 2015
Grant date	Oct 13, 2015

Abstract

The invention includes a method for routing traffic from a first node towards a plurality of intermediate nodes. A method includes receiving traffic at a first node and routing respective portions of the received traffic toward respective intermediate nodes according to respective traffic weighting factors associated with the intermediate nodes. Upon receiving the respective portions of the traffic, the intermediate nodes may then route the traffic toward one or more destination nodes, or may route the traffic toward another plurality of intermediate nodes before the traffic is routed to a destination node. The intermediate node traffic weighting factors may be dependent on the first node and the destination node, or may be independent of the first node and the destination node.

First claim

What is claimed is:

1. A method for adapting traffic flow within a network having a first node, a plurality of intermediate nodes, and a destination node, the method comprising:
receiving traffic at the first node, the first node having associated therewith a plurality of intermediate node traffic weighting factors associated with the respective plurality of intermediate nodes, wherein the traffic is intended for the destination node;
in a first phase of routing, routing a plurality of portions of the traffic from the first node to the respective intermediate nodes according to the respective traffic weighting factors associated with the respective intermediate nodes, wherein one of the intermediate nodes receiving one of the respective portions of the traffic in the first phase of routing receives the respective portion of the traffic from the first node via at least one other of the intermediate nodes of the plurality of intermediate nodes; and
in a second phase of routing, routing the respective portions of the traffic received at the respective intermediate nodes in the first phase of routing from the respective intermediate nodes to the destination node, wherein one of the intermediate nodes routing one of the respective portions of the traffic received in the first phase of routing to the destination node in the second phase of routing routes the respective portion of the traffic to the destination node via at least one other of the intermediate nodes of the plurality of intermediate nodes;
wherein the intermediate node traffic weighting factors are configured to provide a constant utilization of a path from a first one of the intermediate nodes to a second one of the intermediate nodes, wherein the constant utilization of the path has a capacity given by Θ j R i +Θ i C j , wherein Θ j R i represents an amount of traffic routed from the first one of the intermediate nodes to the second one of the intermediate nodes via the path in the first phase of routing and Θ i C j represents an amount of traffic routed from the first one of the intermediate nodes to the second one of the intermediate nodes via the path in the second phase of routing, wherein Θ i is the intermediate node traffic weighting factor of the first one of the intermediate nodes and R i is an ingress capacity of the first one of the intermediate nodes, wherein Θ j is the intermediate node traffic weighting factor of the second one of the intermediate nodes and C j is an egress capacity of the second one of the intermediate nodes.

2. The method of claim 1 , wherein the traffic weighting factors are adapted by a management system.

3. The method of claim 1 , wherein the routing of the traffic in the first phase and the second phase is performed independent of a traffic matrix.

4. The method of claim 1 , wherein the intermediate node traffic weighting factors are independent of the first node and the destination node.

5. The method of claim 1 , wherein the intermediate node traffic weighting factors are dependent on the first node and independent of the destination node.

6. The method of claim 1 , wherein the intermediate node traffic weighting factors are dependent on the first node and the destination node.

7. The method of claim 1 , wherein the traffic comprises packets from a single connection.

8. The method of claim 1 , wherein the traffic comprises packets from multiple connections.

9. A non-transitory computer-readable storage medium storing instructions which, when executed by one or more computers, cause the one or more computers to perform a method for adapting traffic flow within a network having a first node, a plurality of intermediate nodes, and a destination node, the method comprising:
receiving traffic at the first node, the first node having associated therewith a plurality of intermediate node traffic weighting factors associated with the respective plurality of intermediate nodes, wherein the traffic is intended for the destination node;
in a first phase of routing, routing a plurality of portions of the traffic from the first node to the respective intermediate nodes according to the respective traffic weighting factors associated with the respective intermediate nodes, wherein one of the intermediate nodes receiving one of the respective portions of the traffic in the first phase of routing receives the respective portion of the traffic from the first node via at least one other of the intermediate nodes of the plurality of intermediate nodes; and
in a second phase of routing, routing the respective portions of the traffic received at the respective intermediate nodes in the first phase of routing from the respective intermediate nodes to the destination node, wherein one of the intermediate nodes routing one of the respective portions of the traffic received in the first phase of routing to the destination node in the second phase of routing routes the respective portion of the traffic to the destination node via at least one other of the intermediate nodes of the plurality of intermediate nodes;
wherein the intermediate node traffic weighting factors are configured to provide a constant utilization of a path from a first one of the intermediate nodes to a second one of the intermediate nodes, wherein the constant utilization of the path has a capacity given by Θ j R i +Θ i C j , wherein Θ j R i represents an amount of traffic routed from the first one of the intermediate nodes to the second one of the intermediate nodes via the path in the first phase of routing and Θ i C j represents an amount of traffic routed from the first one of the intermediate nodes to the second one of the intermediate nodes via the path in the second phase of routing, wherein Θ i is the intermediate node traffic weighting factor of the first one of the intermediate nodes and R i is an ingress capacity of the first one of the intermediate nodes, wherein Θ j is the intermediate node traffic weighting factor of the second one of the intermediate nodes and C j is an egress capacity of the second one of the intermediate nodes.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the traffic weighting factors are adapted by a management system.

11. The non-transitory computer-readable storage medium of claim 9 , wherein the routing of the traffic in the first phase and the second phase is performed independent of a traffic matrix.

12. The non-transitory computer-readable storage medium of claim 9 , wherein the intermediate node traffic weighting factors are independent of the first node and the destination node.

13. The non-transitory computer-readable storage medium of claim 9 , wherein the intermediate node traffic weighting factors are dependent on the first node and independent of the destination node.

14. The non-transitory computer-readable storage medium of claim 9 , wherein the intermediate node traffic weighting factors are dependent on the first node and the destination node.

15. The non-transitory computer-readable storage medium of claim 9 , wherein the traffic comprises packets from a single connection.

16. The non-transitory computer-readable storage medium of claim 9 , wherein the traffic comprises packets from multiple connections.

17. A system configured for adapting traffic flow, the system comprising:
a network including a first node, a plurality of intermediate nodes, and a destination node;
wherein the first node is configured to receive traffic intended for the destination node, wherein the first node has associated therewith a plurality of intermediate node traffic weigh

Assignees

• Kodialam Muralidharan Sampath
• Lakshman Tirunell V
• Alcatel Lucent

Inventors

• Kodialam Muralidharan Sampath
• Lakshman Tirunell V

Classifications

• H04L47/10

  Flow control; Congestion control · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/12 Primary

  Shortest path evaluation · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title