Method and apparatus for exchanging routing information in a packet-based data network

• US 6,728,779 B1
• Filed: 05/31/2000
• Issued: 04/27/2004
• Est. Priority Date: 12/01/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wilfong, Gordon Thomas, Griffin, Timothy G.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): WANG, LIANG CHE A
• Application Number:
  US09/583,595
• Time in Patent Office: 1,427 Days
• Field of Search: 709/238, 709/239, 379/221.02, 370/469, 714/4
• US Class Current: 709/239
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols

Abstract

Routing information is exchanged between edge routers in different autonomous systems that independently define their routing policies. A Simple Path Vector Protocol extends the prior art Border Gateway Protocol in a manner that is guaranteed to converge by adding a new attribute to the routing messages sent by an edge router to its peers in the different systems. This attribute is a path history, which is dynamically computed at each router as the routing path to a particular destination is changed. The path history attribute is sent in a routing message by a router to its peers together with the sending router'"'"'s path to that destination. By observing the dynamic path history that is computed at a router as a received routing message from a peer router that contains a history attribute is processed, a cycle can be identified in the newly computed history and associated with a policy conflict at that receiving router'"'"'s associated autonomous system. A path whose history contains a cycle is automatically suppressed as a permitted path to that destination.

Claims

1. A method at a first router comprising:

a) selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path;

b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message;

c) dynamically computing a new path history associated with the determined new path; and

d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.

2. The method of claim 1 wherein determining the new path comprises choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and determining whether that new path is different than the old path from the first router to the destination end router.

3. The method of claim 2 wherein when the new path is determined to be different than the old path, dynamically computing the history of the new path as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.

4. The method of claim 3 wherein when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.

5. The method of claim 3 wherein when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.

6. The method of claim 1 further comprising,

e) after dynamically computing the new path history, determining whether there is a cycle present in the new path history determined in step b).

7. The method of claim 6 further comprising, when in step e) a cycle is determined to be present in the new path history determined in step b):

f) determining a newer path from the first router to the destination end router from the set of stored paths to the destination and the path in the routing message, which excludes as being the newer path the new path determined in step b) which associated path history was determined in step e) to contain the cycle.

8. The method of claim 7 further comprising determining whether the newer path determined in step f) is different than the original old path, and when it is different, setting the history of the newer path determined in step f) to a function of the history of the original old path.

9. The method of claim 1 wherein the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.

10. A router comprising:

means for selecting for processing a routing message received from one peer router from among a group of a plurality of peer routers of the first router, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path;

means for determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message; and

means for dynamically computing a new path history associated with the determined new path.

11. The router of claim 10 wherein the means for determining the new path comprises means for choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and means for determining whether the new path is different than the old path from the first router to the destination end router.

12. The router of claim 11 wherein when the new path is determined to be different than the old path, then the means for dynamically computing the new path history computes the history as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.

13. The router of claim 12 wherein when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.

14. The router of claim 12 wherein when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.

15. The router of claim 10 further comprising means for determining whether there is a cycle in the new path history.

16. The router of claim 15 wherein when a cycle is determined to be present in the new path history, then the means for determining a new path determines a newer path from the router to the destination end router from the set of stored paths to the destination and the path in the selected received routing message from the one peer router, which excludes as being the newer path the new path which associated path history was determined to contain the cycle.

17. The router of claim 10 wherein the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.

18. A computer readable media tangibly embodying a program of instructions executable by a computer to perform at a first router a method for exchanging routing information with a group of a plurality of peer routers, the method comprising:

a) selecting for processing a routing message received from one of the peer routers, the routing message comprising a path from the peer router to a destination end router and an associated path history associated with that path, the path history indicating a sequence of any number of path change events that allowed the one peer router to adopt that path;

b) determining a new path from the first router to the destination end router from a set of stored paths to the destination end router and the path in the routing message;

c) dynamically computing a new path history associated with the determined new path; and

d) sending the determined new path and its associated new path history to one or more of the plurality of peer routers.

19. The media of claim 18 wherein in the method determining the new path comprises choosing as the new path the highest ranked permitted path from the first router to the destination end router from a rank-ordered set of permitted paths, and determining whether that new path is different than the old path from the first router to the destination end router.

20. The media of claim 19 wherein in the method when the new path is determined to be different than the old path, dynamically computing the history of the new path as a function of whether the rank order of the new path is lower, higher, or equal to the rank order of the old path.

21. The media of claim 20 wherein in the method when the rank order of the old path is lower than the rank order of the new path, then the history of the new path is a combination of a signed new path with a path history, the sign indicating that the new path is ranked higher than the old path and the path history indicating a sequence of events that led to the one peer router to adopt a specific sub-path of the new path.

22. The media of claim 20 wherein in the method when the rank order of the old path is higher than the rank order of the new path, then the history of the new path is a combination of a signed old path with a path history, the sign indicating that the new path is ranked lower than the old path and the path history indicating a sequence of events that led to the one peer router to abandon a specific sub-path of the old path.

23. The media of claim 18 wherein the method further comprises,

e) after dynamically computing the new path history, determining whether there is a cycle present in the new path history.

24. The media of claim 23 wherein the method further comprises,

f) when a cycle is determined to be present in the new path history, determining a newer path from the first router to the destination end router from the set of stored paths to the destination end router and the path in the routing message, which excludes as being the newer path the new path determined in step b) which associated path history was determined in step c) to contain the cycle.

25. The media of claim 24 wherein the method further comprises determining whether the newer path is different than the original old path, and when it is different, setting the history of the newer path to a function of the history of the original old path.

26. The media of claim 18 wherein in the method the routing message selected for processing from the one peer router is the oldest unprocessed received routing message from the one peer router.