Network routing and congestion control

• US 20030048771A1
• Filed: 09/11/2002
• Published: 03/13/2003
• Est. Priority Date: 03/31/2000
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Shipman, Robert A
• Granted Patent: US 7,349,343 B2
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

In a communications network of nodes (110) connected by links (115), routing of traffic is done according to routing tables available to the nodes (110). The routing table for each node shows fields for destination nodes (210) and for next hop nodes (205) towards those destination nodes, and traffic is routed at each node according to values entered in those fields. The nodes modify the values in the fields according to messages received from neighbouring nodes. This controls traffic flow in that values are raised on receipt of messages from neighbouring nodes. If messages are received less frequently from a node, for instance because of congestion in the network or failure of a node, the values for that node will be relatively depressed and the network will tend to route traffic away from the node.

Claims

1. Routing control apparatus for use in a communications network comprising nodes connected to each other by links, the nodes being provided with routing tables for routing traffic towards a destination node via intermediate nodes, the routing control apparatus comprising in respect of a network node:

(i) a routing table for use in routing traffic transmitted by the node;

(ii) routing table updating means;

(iii) routing message receiving and processing means for receiving routing-related messages transmitted by destination nodes and for identifying an intermediate node by which the routing messages have been transmitted; and

(iv) routing means to output traffic to one or more other network nodes.

wherein the routing table updating means is adapted to update entries for intermediate nodes in the table in accordance with receipt of routing messages from the destination nodes.

2. Apparatus according to claim 1 wherein an intermediate node comprises a neighbouring node.

3. Apparatus according to either one of the preceding claims wherein a received routing message identifies a node at which the message originated, and the routing table updating means is further adapted to update entries for originating nodes in the table in association with an intermediate node identified for the received routing message.

4. Apparatus according to any one of the preceding claims wherein content of a received message identifies an intermediate node by which it has been transmitted.

5. Apparatus according to any one of claims 1 to 3 wherein the path a received message has taken identifies an intermediate node by which it has been transmitted.

6. Apparatus according to any one of the preceding claims wherein the routing table updating means comprises means to weight existing entries in the routing table.

7. Apparatus according to any one of the preceding claims, wherein the network node is provided with a queuing mechanism for queuing traffic to be transmitted by the node, the means to output a message being arranged to output the message to the queuing mechanism such that a message is output with a delay related to transmission delays at the network node.

8. Apparatus according to either one of claims 6 or 7 wherein the routing table updating means is adapted to change the weight of an entry for a neighbouring node on receipt of a message transmitted by that neighbouring node, and traffic is routed by the network node towards a destination node by selecting a neighbouring node according to the weight assigned to entries in the routing table for that neighbouring node.

9. Apparatus according to any one of the preceding claims wherein the routing means in respect of the network node comprises means to build a routing table from data associated with received messages.

10. Apparatus according to claim 9 wherein a routing table built by the routing means comprises entries made in respect of

i) each destination node identified from the content of a received message, and

ii) each neighbouring node identified by the path taken by the received message associated with a destination node identified from the content of said received message.

11. Apparatus according to claim 9 wherein a routing table built by the routing means comprises entries made in respect of each destination node identified from the content of a received message, in association with a neighbouring node identified from the content of said received message.

12. Apparatus according to any one of the preceding claims wherein received routing messages comprise time data, indicating time of their creation, and the routing message receiving and processing means is adapted to discard routing messages where the time data indicates at least a threshold period of time has passed since a message was created.

13. Apparatus according to any one of claims 3 to 11 wherein received routing messages comprise time data, indicating time of their creation, the apparatus further comprising means for storing time data and the identity of an originating node for each routing message received, and the routing message receiving and processing means is adapted to discard routing messages where the time data and identity of the originating node match data already stored for a previously received routing message.

14. Apparatus according to any one of the preceding claims wherein received routing messages comprise hop count data, indicating the number of nodes having already transmitted the message, and the routing message receiving and processing means is adapted to discard routing messages where the hop count data indicates at least a threshold number of nodes have already transmitted the message.

15. Apparatus according to any one of the preceding claims, which further comprises means for generating messages and outputting them from a node of the network provided with processing capacity, the messages being output at a rate determined by the quantity of processing capacity available at the node, each message containing an identifier for the node, such that traffic for processing can be routed by other nodes of the network towards a node with processing capacity to an extent determined by its available processing capacity.

16. A method of routing traffic between nodes in a network, which method comprises:

a. receiving a routing-related message at a network node;

b. identifying by means of the received message a node at which it originated and a neighbouring node from which it was received; and

c. making or modifying an entry in a routing table, for use in routing traffic towards said originating node via said neighbouring node.

17. A method according to claim 16, further comprising routing traffic in accordance with the routing table.

18. A method according to either one of claims 16 or 17 which further comprises weighting entries in the routing table and routing traffic in accordance with relative weighting between neighbouring nodes associated with the same originating node.

19. A method according to any one of claims 16 to 18 which further comprises transmitting messages from the network node at a rate determined by the available capacity of the node.

20. A method according to claim 19 which further comprises queuing messages for processing at the node, together with traffic for transmission by the node, such that the volume of traffic at the node determines the rate at which messages are transmitted from the node.

21. A method according to any one of claims 16 to 20 wherein the neighbouring node by which a message is received is identifiable by the path by which the message was received a the network node.

22. A method according to any one of claims 16 to 20 wherein the neighbouring node by which a message is received is identifiable by content of the message received at the network node.

23. A method according to any one of claims 16 to 22 wherein a received routing-related message comprises a time stamp indicating the time of its creation and the method further comprises processing the time stamp and discarding the message in the event that its time stamp indicates a threshold period of time has elapsed since said time of creation.

24. A method according to any one of claims 16 to 22 wherein a received routing-related message comprises an identifier for the message and the method further comprises storing identifiers for received messages, comparing the identifiers for received messages with the stored identifiers and discarding messages for which the identifier matches a stored identifier.

25. A method according to claim 24 wherein a message identifier comprises a time stamp indicating its time of creation and an identifier for the node from which it originated.