Routing for a communications network

• US 20030012145A1
• Filed: 07/12/2002
• Published: 01/16/2003
• Est. Priority Date: 07/13/2001
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Bragg, Nigel
• Granted Patent: US 7,286,479 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths

Abstract

For routing in a communications network, alternate paths to a destination are aggregated into a single composite route, prior to onward propagation of the route. Ideally, aggregation is performed at each point of route convergence in the network. Consequently, failure in only one of the paths does not then require that the composite route be withdrawn, and thus visibility of and reaction to the fault is restricted to parts of the network directly affected. The method is particularly applicable to border gateway protocols employed between Autonomous Systems as in, for example, the Internet.

Claims

1. A method of performing routing in a communications network comprising the steps of, at a routing node:

receiving a plurality of routes to at least one destination address;

aggregating a plurality of the routes into a single composite route prior to onward propagation of the composite route.

2. A method according to claim 1 in which the plurality of the routes comprises:

a first route selected according to first predetermined selection criteria as a most preferred route;

a second route selected according to second predetermined selection criteria as a second most preferred route.

3. A method according to claim 2 in which the second predetermined selection criteria are the same as the first predetermined selection criteria as applied to the plurality of routes excluding the most preferred route.

4. A method according to claim 1 in which each node on any of the plurality of routes is represented only once in the representation of the composite route.

5. A method according to claim 4 in which divergence of the plurality of routes is represented only between the routing node and a first common point at which the plurality of routes converges.

6. A method according to claim 1 in which the step of aggregating takes place at each point of route convergence within the communication network.

9. A method according to claim 1 in which the communications network is an autonomous system.

7. A method of performing data forwarding in a communications network comprising the steps of, at a routing node:

receiving a composite route representative of a plurality of routes to a given destination;

selecting the composite route as a preferred route to the given destination;

forwarding data traffic via the composite route;

upon at least one, but not all, of the plurality of routes becoming unavailable, continuing to forward traffic to the given destination via the composite route.

8. A method according to claim 7 additionally comprising the steps of;

upon restoration of the one route, continuing to forward traffic to the destination via the composite route.

10. A method of performing automated routing at a routing node in a communications system comprising the steps of:

importing representations of at least two distinct routes to at least one destination address;

selecting representations of at least two of those distinct routes;

pre-pending an indication of the routing node to a single composite representation of the selected representations to form a new composite representation;

exporting the new composite representation.

11. A method according to claim 10 in which the steps of importing and exporting are to and from respective distinct autonomous systems.

12. A method according to claim 10 in which the node is a border gateway.

13. A method according to claim 12 in which the steps of importing and exporting employ a Border Gateway Protocol.

15. A communications network comprising at least one router node according to claim 14.

17. A communications network comprising a router according to claim 16.

19. A communications network comprising a router according to claim 18.

14. A communications network router comprising:

a path aggregator arranged to receive representations of one or more paths to at least one destination network address and, where a plurality of those paths is received, to aggregate a plurality of the paths into a composite route for onward propagation.

16. A communications network router comprising:

an input port arranged to receive a composite route representative of a plurality of routes to a given destination address;

a processor arranged to select the composite route as a preferred route to the given destination;

a data routing processor arranged to forward data via the selected composite routing.

18. A communications network comprising a router comprising:

an input arranged to import representations of at least two distinct routes to at least one destination address;

a processor arranged to select representations of at least two of those distinct routes, and to pre-pend an indication of the router'"'"'s identity to a single composite representation of the selected representations to form a new composite representation;

an output arranged to export the new composite representation.

20. Software for a computer in a machine-readable medium and arranged to perform the steps of;

receiving a plurality of paths to at least one destination;

aggregating a plurality of the paths to the destination into a composite route for onward propagation.

21. A signal in a communications network, comprising;

a representation of a composite route to a given destination.

22. A data structure for representation of a composite route in a communications network, the composite route comprising a plurality of alternative routes, the data structure comprising:

a first portion representative of an initial portion of the composite route common to each of the plurality of alternative routes;

a second portion representative of a final portion of the composite route common to each of the plurality of alternative routes;

a third portion representative of those portions of the composite route not common to each of the plurality of alternative routes.

23. A data structure according to claim 22 in which at least one of the first portion and the second portion are empty.