Network routing and congestion control

• US 7,349,343 B2
• Filed: 03/29/2001
• Issued: 03/25/2008
• Est. Priority Date: 03/31/2000
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Shipman, Robert A
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): HOANG, THAI D
• Application Number:
  US10/221,318
• Publication Number:
  US 20030048771A1
• Time in Patent Office: 2,553 Days
• Field of Search: 370/392, 370/236
• US Class Current: 370/236
• 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 connected by links, routing of traffic is done according to routing tables available to the nodes. The routing table for each node shows fields for destination nodes and for next hop nodes 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 neighboring nodes. This controls traffic flow in that values are raised on receipt of messages from neighboring 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 directly and indirectly by links, the nodes being provided with routing tables for routing traffic towards respectively corresponding destination nodes 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 other nodes that may be destination nodes for future traffic and for identifying one or more intermediate nodes 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 neighboring node.

3. Apparatus according to claim 1 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 claim 1 wherein content of a received message identifies an intermediate node by which it has been transmitted.

5. Apparatus according to claim 1 wherein the path a received message has taken identifies an intermediate node by which it has been transmitted.

6. Apparatus according to claim 1 wherein the routing table updating means comprises means to weight existing entries in the routing table.

7. Apparatus according to claim 1, 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 claim 6 wherein the routing table updating means is adapted to change the weight of an entry for a neighboring node on receipt of a message transmitted by that neighboring node, and traffic is routed by the network node towards a destination node by selecting a neighboring node according to the weight assigned to entries in the routing table for that neighboring node.

9. Apparatus according to claim 1 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 routing message, and

ii) each neighboring node identified by the path taken by the received routing message associated with a destination node identified from the content of said received routing 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 form the content of a received routing message, in association with a neighboring node identified from the content of said received routing message.

12. Apparatus according to claim 1 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 claim 1 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 claim 1 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 claim 1, 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 nods in a network, which method comprises:

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

b. identifying by means of the received routing-related message a node at which it originated and a neighboring 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 neighboring node.

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

18. A method according to claim 16 which further comprises weighting entries in the routing table and routing traffic in accordance with relative weighting between neighboring nodes associated with the same originating node.

19. A method according to claim 16 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 routing-related 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 routing-related messages are transmitted from the node.

21. A method according to claim 16 wherein the neighboring 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 claim 16 wherein the neighboring node by which a message is received is identifiable by content of the message received at the network node.

23. A method according to claim 16 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 claim 16 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 routing-related message identifier comprises a time stamp indicating its time of creation and an identifier for the node from which it originated.