Method and apparatus for border gateway protocol route management and routing policy modeling

• US 7,602,796 B2
• Filed: 03/04/2005
• Issued: 10/13/2009
• Est. Priority Date: 03/04/2005
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Scudder, John, Ward, David D., Barron, Thomas P.
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US11/073,351
• Publication Number:
  US 20060209851A1
• Time in Patent Office: 1,684 Days
• Field of Search: None
• US Class Current: 370/401
• 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/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A method and apparatus is described for Border Gateway Protocol (BGP) route management and routing policy modeling. In one aspect, the performance of one or more actions associated with one or more routes is disallowed. One or more routing policies associated with the one or more routes are configured. The performance of the one or more actions is then allowed. In one feature of the aspect, the one or more actions comprise forwarding packets on the one or more routes. The one or more actions may also comprise advertising the one or more routes to BGP peers.

Claims

1. A method of managing network routes at a Border Gateway Protocol (BGP) host, the method comprising the computer-implemented steps of:

the BGP host disallowing the performance of one or more actions that are associated with first one or more routes;

wherein the first one or more routes are stored in a BGP Routing Information Base (RIB) that stores only routes received over BGP;

the BGP host configuring two or more routing policies that are associated with the first one or more routes that are stored in the BGP RIB, wherein configuring the two or more routing policies comprises;

applying a first routing policy of the two or more routing policies to the first one or more routes, wherein applying the first routing policy comprises modifying one or more attributes of a particular route of the first one or more routes based on whether one or more conditions associated with the first routing policy of the two or more routing policies are satisfied;

storing second one or more routes at the BGP host, wherein the second one or more routes are the same as the first one or more routes; and

applying a second routing policy of the two or more routing policies to the second one or more routes, wherein the second routing policy is different than the first routing policy;

the BGP host allowing the performance of the one or more actions for the first one or more routes stored in the BGP RIB that have been configured according to one of the two or more routing policies.

2. A method as recited in claim 1, wherein the one or more actions comprise at least one of forwarding packets on the first one or more routes and advertising the first one or more routes to BGP peers of the BGP host.

3. A method as recited in claim 1, further comprising:

receiving the first one or more routes at the BGP host; and

storing the first one or more routes in the BGP RIB.

4. A method as recited in claim 3, wherein receiving the first one more routes comprises at least one of:

receiving the first one or more routes over a BGP session that is established between the BGP host and a BGP peer; and

receiving the first one or more routes over a routing protocol that is different than BGP.

5. A method as recited in claim 1, further comprising the step of charging a fee, to an entity that uses the BGP host, for forwarding network traffic of the entity on the first one or more routes.

6. A method of managing routes, the method comprising the computer-implemented steps of:

at a Border Gateway Protocol (BGP) host, establishing a BGP session with a BGP peer;

storing first one or more routes at the BGP host, wherein the first one or more routes are received over the BGP session;

the BGP host placing the first one or more routes in an inactive state, wherein packet forwarding is disallowed on any route that is in the inactive state;

wherein placing the first one or more routes in the inactive state comprises storing the first one or more routes in a first routing table;

the BGP host configuring two or more routing policies that are associated with the first one or more routes, wherein configuring the two or more routing policies comprises;

applying a first routing policy of the two or more routing policies to the first one or more routes, wherein applying the first routing policy comprises modifying one or more attributes of a particular route of the first one or more routes based on whether one or more conditions associated with the first routing policy of the two or more routing policies are satisfied;

storing second one or more routes at the BGP host, wherein the second one or more routes are the same as the first one or more routes; and

applying a second routing policy of the two or more routing policies to the second one or more routes, wherein the second routing policy is different than the first routing policy; and

the BGP host placing the first one or more routes in an active state, wherein packet forwarding is allowed on any route in the active state;

wherein placing the first one or more routes in the active state comprises storing the first one or more routes in a second routing table, wherein the second routing table is different than the first routing table.

7. A method as recited in claim 6, wherein:

route advertising is disallowed for any route in the inactive state; and

route advertising is allowed for any route in the active state.

8. A method as recited in claim 6, wherein:

the BGP session is a first BGP session;

the first one or more routes are received over the first BGP session; and

the method further comprises;

establishing a second BGP session between the BGP host and the BGP peer;

receiving the second one or more routes over the second BGP session; and

placing the second one or more routes in the active state.

9. A method as recited in claim 8, wherein configuring the two or more routing policies further comprises:

selecting a particular routing policy of the two or more routing policies based on information obtained as a result of applying at least the first and the second routing policies.

10. A method as recited in claim 6, wherein configuring the two or more routing policies further comprises:

selecting a particular routing policy from the two or more routing policies, wherein the particular routing policy is used to govern routing on the first one or more routes when the first one or more routes are placed in the active state.

11. A method as recited in claim 6, wherein configuring the two or more routing policies further comprises any one of:

modifying one or more attributes of a particular route of the first one or more routes according to the first routing policy of the two or more routing policies; and

filtering out a particular route of the first one or more routes based on the first routing policy of the two or more routing policies.

12. A method as recited in claim 6, wherein:

configuring the two or more routing policies comprises selecting a particular route of the first one or more routes based on one of the first routing policy and the second routing policy of the two or more routing policies; and

placing the first one or more routes in the active state comprises placing only the particular route in the active state.

13. A method as recited in claim 6, wherein configuring the two or more routing policies further comprises, in response to receiving a command from a user, modifying one or more attributes of a particular route of the first one or more routes based on a parameter included in the command.

14. A method as recited in claim 6, further comprising:

advertising the first one more routes to the BGP peer, wherein the first one or more routes are in the inactive state and have been configured according to the first routing policy;

at the BGP peer, receiving the first one or more routes and placing the first one or more routes in the inactive state; and

at the BGP peer, applying at least one routing policy of the two or more routing policies to the first one or more routes.

15. A method as recited in claim 6, wherein the steps of placing the first one or more routes in the inactive state and placing the first one or more routes in the active state comprise, for each route of the first one or more routes, changing the value of an attribute associated with each route.

16. A method as recited in claim 6, wherein:

the method comprises the computer-implemented step of the BGP host executing a BGP process;

establishing the BGP session with the BGP peer comprises the BGP process establishing the BGP session with the BGP peer;

storing the first one or more routes at the BGP host comprises the BGP process storing the first one or more routes in a BGP Routing Information Base (RIB), wherein the BGP RIB stores only routes that are received over BGP, and wherein the BGP RIB comprises the first routing table and the second routing table;

placing the first one or more routes in the inactive state comprises the BGP process placing the first one or more routes in the inactive state;

configuring the two or more routing policies comprises the BGP process configuring the two or more routing policies; and

placing the first one or more routes in the active state comprises the BGP process placing the first one or more routes in the active state.

17. An apparatus for routing that is operable to execute a Border Gateway Protocol (BGP) process, the apparatus comprising:

means for disallowing the performance of one or more actions that are associated with first one or more routes;

wherein the first one or more routes are stored in a BGP Routing Information Base (RIB) that stores only routes received over BGP;

means for configuring two or more routing policies that are associated with the first one or more routes that are stored in the BGP RIB, wherein the means for configuring the two or more routing policies comprise;

means for applying a first routing policy of the two or more routing policies to the first one or more routes;

means for storing second one or more routes at the BGP host, wherein the second one or more routes are the same as the first one or more routes; and

means for applying a second routing policy of the two or more routing policies to the second one or more routes, wherein the second routing policy is different than the first routing policy;

means for allowing the performance of the one or more actions for the first one or more routes stored in the BGP RIB that have been configured according to one of the two or more routing policies, wherein the means for configuring the two or more routing policies further comprise means for modifying one or more attributes of a particular route of the first one or more routes based on whether one or more conditions associated with the first routing policy of the two or more routing policies are satisfied.

18. An apparatus as recited in claim 17, wherein the one or more actions comprise at least one of forwarding packets on the first one or more routes and advertising the first one or more routes to peering BGP processes.

19. An apparatus as recited in claim 17, further comprising:

means for receiving the first one or more routes, wherein the first one or more routes are received over at least one of a BGP session and a routing protocol that is different than BGP; and

means for storing the first one or more routes in the BGP RIB.

20. An apparatus for routing, comprising:

one or more processors;

one or more stored sequences of instructions, which are stored in one or more volatile or non-volatile media and which, when executed by the one or more processors, are operable at least to;

execute a Border Gateway Protocol (BGP) process;

establish a BGP session with a BGP peer;

store first one or more routes, wherein the first one or more routes are received over the BGP session;

place the first one or more routes in an inactive state, wherein packet forwarding is disallowed on any route that is in the inactive state;

wherein the instructions operable to place the first one or more routes in the inactive state comprise instructions operable to store the first one or more routes in a first routing table;

configure two or more routing policies that are associated with the first one or more routes, wherein the instructions operable to configure the two or more routing policies comprise instructions operable to;

apply a first routing policy of the two or more routing policies to the first one or more routes, wherein applying the first routing policy comprises modifying one or more attributes of a particular route of the first one or more routes based on whether one or more conditions associated with the first routing policy of the two or more routing policies are satisfied;

store second one or more routes, wherein the second one or more routes are the same as the first one or more routes; and

apply a second routing policy of the two or more routing policies to the second one or more routes, wherein the second routing policy is different than the first routing policy; and

place the first one or more routes in an active state, wherein packet forwarding is allowed on any route in the active state;

wherein the instructions operable to place the first one or more routes in the active state comprise instructions operable to store the first one or more routes in a second routing table, wherein the second routing table is different than the first routing table.

21. An apparatus as recited in claim 20, wherein:

route advertising is disallowed for any route in the inactive state; and

route advertising is allowed for any route in the active state.

22. An apparatus as recited in claim 20, wherein:

the BGP session is a first BGP session;

the first one or more routes are received over the first BGP session; and

the one or more stored sequences of instructions further comprise instructions which are stored in the one or more volatile or non-volatile media and which, when executed by the one or more processors, are operable to;

establish a second BGP session with the BGP peer;

receive the second one or more routes over the second BGP session; and

place the second one or more routes in the active state.

23. An apparatus as recited in claim 22, wherein the instructions operable to configure the two or more routing policies comprise instructions which, when executed by the one or more processors, are operable to:

select a particular routing policy of the two or more routing policies based on information obtained as a result of applying at least the first and the second routing policies.

24. An apparatus as recited in claim 20, wherein the instructions operable to configure the two or more routing policies further comprise instructions which, when executed by the one or more processors, are operable to:

select a particular routing policy from the two or more routing policies, wherein the particular routing policy is used to govern routing on the first one or more routes when the first one or more routes are placed in the active state.

25. An apparatus as recited in claim 20, wherein the instructions operable to configure the two or more routing policies further comprise instructions which, when executed by the one or more processors, are operable to:

modify one or more attributes of a particular route of the first one or more routes according to the first routing policy of the two or more routing policies; and

filter out a particular route of the first one or more routes based on the first routing policy of the two or more routing policies.

26. An apparatus as recited in claim 20, wherein:

the instructions operable to configure the two or more routing policies comprise instructions which, when executed by the one or more processors, are operable to select a particular route of the first one or more routes based on one of the first routing policy and the second routing policy of the two or more routing policies; and

the instructions operable to place the first one or more routes in the active state comprise instructions which, when executed by the one or more processors, are operable to place only the particular route in the active state.

27. An apparatus as recited in claim 20, wherein the instructions operable to configure the two or more routing policies further comprise instructions which, when executed by the one or more processors, are operable to modify, in response to receiving a command from a user, one or more attributes of a particular route of the first one or more routes based on a parameter included in the command.

28. An apparatus as recited in claim 20, wherein the instructions operable to place the first one or more routes in the inactive state and the instructions operable to place the first one or more routes in the active state comprise instructions which, when executed by the one or more processors, are operable to change, for each route of the first one or more routes, the value of an attribute associated with each route.

29. An apparatus as recited in claim 20, wherein:

the instructions operable to establish the BGP session with the BGP peer are included in the instructions operable to execute the BGP process;

the instructions operable to store the first one or more routes at the BGP host are included in the instructions operable to execute the BGP process and further comprise instructions which, when executed by the one or more processors, are operable to store the first one or more routes in a BGP Routing Information Base (RIB), wherein the BGP RIB stores only routes that are received over BGP, and wherein the BGP RIB comprises the first routing table and the second routing table;

the instructions operable to place the first one or more routes in the inactive state are included in the instructions operable to execute the BGP process;

the instructions operable to configure the two or more routing policies are included in the instructions operable to execute the BGP process; and

the instructions operable to place the first one or more routes in the active state are included in the instructions operable to execute the BGP process.

30. A computer-readable storage medium storing one or more sequences of instructions for managing routes at a Border Gateway Protocol (BGP) host, which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

establishing a BGP session with a BGP peer;

storing first one or more routes at the BGP host, wherein the first one or more routes are received over the BGP session;

placing the first one or more routes in an inactive state, wherein packet forwarding is disallowed on any route that is in the inactive state;

wherein placing the first one or more routes in the inactive state comprises storing the first one or more routes in a first routing table;

configuring two or more routing policies that are associated with the first one or more routes, wherein configuring the two or more routing policies comprises;

applying a first routing policy of the two or more routing policies to the first one or more routes, wherein applying the first routing policy comprises modifying one or more attributes of a particular route of the first one or more routes based on whether one or more conditions associated with the first routing policy of the two or more routing policies are satisfied;

storing second one or more routes at the BGP host, wherein the second one or more routes are the same as the first one or more routes; and

applying a second routing policy of the two or more routing policies to the second one or more routes, wherein the second routing policy is different than the first routing policy; and

placing the first one or more routes in an active state, wherein packet forwarding is allowed on any route in the active state;

wherein placing the first one or more routes in the active state comprises storing the first one or more routes in a second routing table, wherein the second routing table is different than the first routing table.

31. A computer-readable storage medium as recited in claim 30, wherein:

the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of executing a BGP process;

the instructions that cause the one or more processors to perform the step of establishing the BGP session with the BGP peer further comprise instructions which, when executed by the one or more processors, cause the one more processors to perform the step of the BGP process establishing the BGP session with the BGP peer;

the instructions that cause the one or more processors to perform the step of storing the first one or more routes at the BGP host further comprise instructions which, when executed by the one or more processors, cause the one more processors to perform the step of the BGP process storing the first one or more routes in a BGP Routing Information Base (RIB), wherein the BGP RIB stores only routes that are received over BGP, and wherein the BGP RIB comprises the first routing table and the second routing table;

the instructions that cause the one or more processors to perform the step of placing the first one or more routes in the inactive state further comprise instructions which, when executed by the one or more processors, cause the one more processors to perform the step of the BGP process placing the first one or more routes in the inactive state;

the instructions that cause the one or more processors to perform the step of configuring the two or more routing policies further comprise instructions which, when executed by the one or more processors, cause the one more processors to perform the step of the BGP process configuring the two or more routing policies; and

the instructions that cause the one or more processors to perform the step of placing the first one or more routes in the active state further comprise instructions which, when executed by the one or more processors, cause the one more processors to perform the step of the BGP process placing the first one or more routes in the active state.