System and method for optimally configuring border gateway selection for transit transit traffic flows in a computer network

[0001] The present invention is directed, in general, to computer networks and, more specifically, to a system and method for optimally configuring border gateway selection for transit traffic flows in a computer network.

[0002] The primary responsibility of an Internet Service Provider (ISP) is to provide transit service from its set of customers to the remainder of the Internet and to bring traffic from its own upstream providers and peers destined to its customers. The interface from the ISP to the customers, upstream providers, and peers is through a set of border routers of the ISP. Currently, a border gateway protocol (BGP) allows border gateways (border router and border gateway will be used interchangeably) to be selected to carry transit traffic flows.

[0003] This responsibility is balanced with an objective of the ISP to minimize the resources used on its network in carrying transit traffic. The ISP wishes to get traffic on its way toward its ultimate destination as quickly as possible.

[0004] A poorly designed selection of border routers for the flows of traffic through the ISP can result in numerous problems. Ingress and/or egress traffic from/to neighbors may exceed the capacity of the selected border routers and its links, causing the ISP to fail to meet its responsibility. On the other side, underutilization of the potential capacity at border routers, or carrying traffic across the ISP network longer than necessary results in inefficient use of costly resources of the ISP.

[0005] Unfortunately, ISPs today have few tools or algorithms to help with this problem. Policies governing inter-domain routing and border router selection are arrived at manually through applying intuition, ad-hoc methods and constant tuning.

[0006] Accordingly, what is needed in the art is a better way to determine a selection of border routers used for ingress and egress of transit traffic that reduces, and ideally minimizes, provider network utilization and better balances the load of traffic flows from neighbors across the selected border routers by respecting capacity constraints.

[0007] To address the above-discussed deficiencies of the prior art, the present invention provides a system for, and method of, configuring border gateway selection for transit traffic flows in a computer network. In one embodiment, the system includes: (1) a model of the computer network that includes border routers and their capacities, and distances between the border routers and (2) a traffic flow optimizer, associated with the model. Given input data for transit traffic to the computer network, the traffic flow optimizer uses approximation techniques for integer programs and novel algorithms to improve (and advantageously maximize) resource usage and decrease (and advantageously minimize) cost in the computer network represented by the model.

[0008] The present invention is the first to address the problem of optimizing the cost of routing traffic through a provider's network while also considering load balancing based on the capacity of the border routers. Other work in BGP policy has focused on providing guidelines to assure stability of Internet routing (see, L. Gao and J. Rexford, Stable Internet Routing Without Global Coordination, Proceedings of ACM SIGMETRICS, June 2000; and R. Govindan and A. Reddy, An Analysis of Internet Inter-domain Topology and Route Stability, INFOCOM '97, April 1997, both incorporated herein by reference). The present invention, however, is best viewed as a form of traffic engineering. In contrast, previous work in this area has centered on intra-domain routing and the setting of weights for OSPF traffic across the provider network (see B. Fortz and M. Thorup, Internet Traffic Engineering by Optimizing OSPF Weights, Proceedings of IEEE INFOCOM, 2000, pp. 519-528, incorporated herein by reference). The present invention is the first to take traffic engineering as a means of providing the right information to optimally set BGP policy to control inter-domain transit traffic flow.

[0009] In one embodiment of the present invention, the traffic flow optimizer assumes a single egress point for all traffic intended for a given address. Given this assumption, the optimization problem becomes an instance of what is known to those skilled in the pertinent art as the generalized assignment problem (GAP). The approximation algorithm may violate the capacity constraints of the border routers, so in a second phase, the traffic flow optimizer moves traffic from violated routers to routers with spare capacity. Traffic is moved so as to minimize the cost.

[0010] In one embodiment of the present invention, the traffic flow optimizer assumes multiple egress points can be used for traffic to a given address. However, these multiple egress points should respect the proximity constraints of the BGP. The traffic flow optimizer formulates this problem as an integer program then solves the linear program relaxation of the integer program. Approximation techniques are then used to round the linear program solution to an integer solution. The integer solution may violate proximity and capacity constraints, so, in a final phase, the traffic flow optimizer moves traffic from violated routers to routers with spare capacity. Again, traffic is moved so as to minimize the cost.

[0011] The foregoing has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.

[0012] For a more complete understanding of the present invention, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

[0013] FIGS. 1A-1D together illustrate examples of optimal assignments for single and multiple egress cases;

[0014] FIG. 2 illustrates a pseudo-code listing of a greedy heuristic for the generalized assignment problem;

[0015] FIG. 3 illustrates a pseudo-code listing of an iterative heuristic for single egress selection;

[0016] FIG. 4 illustrates a psuedo-code listing for step 7 of a multiple egress selection heuristic;

[0017] FIG. 5 illustrates a block diagram of one embodiment of a system for configuring border gateway selection for transit traffic flows in a computer network constructed according to the principles of the present invention; and

[0018] FIG. 6 illustrates a method of managing a computer network carried out according to the principles of the present invention.

[0019] BGP and Inter-Domain Routing

[0020] To understand how to control the selection of border routers used for inter-domain routing of transit traffic flows and the input information available to solve the problem, one should first understand BGP and its use in inter-domain routing (see, Y. Rekhter and T. Li, A Border Gateway Protocol 4, Internet-Draft (RFC1771), February 1998; and J. W. Stewart III, BGP4: Inter-Domain Routing in the Internet, Addison-Wesley, 1999, both incorporated herein by reference).

[0021] The area of network infrastructure under a single technical and administrative control defines the boundaries of an Autonomous System (AS). Typically, an ISP is associated with a single AS. ASes interconnect via dedicated links and public network access points, and exchange routing reachability information through external BGP peering sessions. BGP itself is a distance vector protocol that allows import and export policies to modify the routing decision from the shortest-path default.

[0022] The unit of routability provided by BGP is the network prefix (or just prefix), which is an aggregation of IP addresses in a contiguous block (e.g., 10.20.30.0/24). A route advertisement is received from a neighbor AS over a BGP peering session and contains a prefix, an IP address of the next-hop, a multi-exit discriminator (MED) and a list of ASes along the path to the specified destination prefix. Receipt of an advertisement from a neighbor AS conveys the ability to egress data traffic toward the given prefix through that neighbor. Upon receiving an advertisement, a BGP speaker must decide whether or not to use this path and, if the path is chosen, whether or not to propagate the advertisement to neighboring ASes (after adding its own AS number to the AS path). When propagating an advertisement, the MED is used to differentiate the preference of the AS among a set of ingress routers.

[0023] BGP import policy allows an AS to favor one advertisement over another by assigning a local preference. The advertisement, with the assigned local preference, may then be disseminated among all the BGP speakers within the receiving AS1. An acceptance process then occurs wherein each BGP speaker picks the best route advertisement for each prefix. The decision criteria for the acceptance process proceeds as follows:

[0024] 1. Accept the advertisement with the highest local-preference.

[0025] 2. Break ties by accepting the advertisement with the shortest AS path.

[0026] 3. Break ties by accepting the advertisement with the smallest MED.

[0027] 4. Break ties by accepting the advertisement with the smallest intra-domain cost to the egress border router.

[0028] 5. Break any remaining tie by accepting the advertisement with the smallest next-hop address.

[0029] Note that, since step 4 employs intra-domain cost, two BGP speakers may select different best advertisements for the same prefix, favoring the closest (in cost) egress border router.

[0030] The import policy and decision process described above control the selection of the border router used to egress traffic for any particular prefix. BGP export policy allows an AS to control ingress traffic as advertisements are propagated to neighbor ASes. In particular, the export policy may choose not to readvertise a route to a neighbor at a particular border router, or it may assign a MED value, or it may prepend the current AS number to the AS path some number of times, effectively discouraging use of the route through the current border router.

[0031] Problem Detail

[0032] Recall that the unit of routability for BGP, and thus the association of traffic to an ingress border router and to an egress border router, is the network prefix. The problem addressed in this paper becomes: for each neighbor and each prefix the ISP must transit traffic for, select an ingress border router and an egress border router for that traffic with the objective of optimizing network utilization. This selection must be accomplished respecting ingress and egress capacity constraints of the border routers, thus balancing prefixes between routers where such constraints would be violated.

[0033] A common approach to improving network resource utilization is to egress incoming traffic as quickly as possible. This is essentially equivalent to minimizing the total distance traversed by transit traffic within the ISP network, which in some sense represents the cost incurred by the ISP to carry the transit traffic. The focus is on minimizing this cost.

[0034] For each neighbor AS ingressing traffic for a particular prefix, a single ingress border router is selected. If a neighbor AS is connected to the provider through multiple border routers, different border routers may be selected for different prefixes, but a single prefix is not split among multiple ingress routers to the same neighbor. This allows the control necessary to account for all traffic for the prefix to ingress at the desired border router, which is natural given the prefix as the basic unit assigned to selected border routers. BGP export policies are employed to ensure that the proper advertisement is only propagated from the selected ingress router. The details will now be covered.

[0035] Problem Variants

[0036] Two variants of the problem distinguish themselves in how egress traffic is constrained to an egress border router.

[0037] In the first, simpler, variant, a single egress router is selected for each prefix. Thus, for all neighbors ingressing traffic destined for that prefix, traffic will egress from the same border router. This problem variant is referred to herein as Single Egress Selection (SES). Though simplified, SES is not an unreasonable simplification given the manner in which BGP operates. Given a set of advertisements for the same prefix, the acceptance process executed at all BGP speakers will select the same best route provided the tie-breaking procedure does not come down to step 4, intra-domain cost.

[0038] In practice, it is possible that egressing traffic for a prefix at multiple egress routers could improve network utilization. This is because the BGP acceptance process breaks ties between multiple candidate egress routers for a prefix (in step 4) based on the intra-domain cost to each router. The Multiple Egress Selection (MES) variant of the problem allows the egress for a given prefix to differ for two different neighbors. However, for any given neighbor, it is still the case that only a single egress router is selected for a particular prefix.

[0039] For both problem variants, mechanisms for controlling egress router selection through BGP are detailed below.

[0040] In addition to available topological information, including the set of border routers and their capacities, the set of neighbor connections, and the set of intra-domain distances, and the BGP provided information of the advertisements and prefixes, available traffic information is assumed to be available. Whether measured or estimated, this specifies the transit traffic from each neighbor AS to each prefix.

[0041] This router selection problem is, for purposes of the present discussion, assumed to be an off line problem, which is already quite challenging. Most of the information cited above is relatively static. For instance, in C. Labovitz, G. R. Malan and F. Jahanian, Internet Routing Instability, in Proceedings of ACM SIGCOMM, 1997 (incorporated herein by reference), it is claimed that only a very small portion of BGP route advertisement updates each day reflect network events such as router failures and leased line disconnectivity. In fact, a majority of BGP updates were found to consist entirely of pathological duplicate withdrawals. The exception is the expected traffic which prior work has shown to have a periodicity across times of day and days of the week. This could be handled by solving the problem multiple times, once for each equivalence class of traffic pattern.

[0042] Results and Contributions

[0043] The present invention is the first to address the problem of optimizing the cost of routing traffic through a provider's network while also considering load balancing based on the capacity of the border routers. Other work in BGP policy has focused on providing guidelines to assure stability of Internet routing (Gao, et al., supra; and Govindan, et al., supra). The present invention, however, is best viewed as a form of traffic engineering. In contrast, previous work in this area has centered on intra-domain routing and the setting of weights for OSPF traffic across the provider network (Fortz, et al., supra). The present invention is the first to take traffic engineering as a means of providing the right information to optimally set BGP policy to control inter-domain transit traffic flow.

[0044] Problem formulations are specified as linear programs, and the generalized assignment problem (GAP) is a special case of formulations disclosed herein. Solving GAP is well-known to be NP-hard, so heuristics are presented for solving both the SES and the MES variants of the problem. Experiments show that the SES heuristic exhibits improvements of up to 26% over an intuitive heuristic based on routing the biggest jobs first.

[0045] System Model

[0046] For the transit provider AS under consideration, a set of neighbors A₁,K,A_qA1 and a set of border routers b₁,K,b_n linking the neighbors to the transit provider are given. Multiple neighbors may be connected to the AS through a given border router and each neighbor may be connected to the AS through multiple border routers.

TABLE I
Notation
	Notation	Description
	P1, K Pm	Set of network prefixes for
		transit routing
	A1, K, Aq	Set of AS neighbors
	b1, K, bn	Set of border routers
	Out(k)	Set of egress routers for Pk
	In(h)	Set of ingress routers from
		neighbor Ah
	d(i, j)	Intra-domain distance
		between bi and bj
	t(h, k)	Traffic flow from
		neighbor Ah to prefix Pk
	Ci	Ingress bandwidth capacity
		for router bi
	Kj	Egress bandwidth capacity
		for router bj
	(h, k)	Ingress, egress router pair
		for traffic from AS Ah to
		prefix Pk

[0047] For each neighbor A_h, let In(h) denote the set of border routers through which A_h may ingress data traffic. Each border router b_i, has an ingress capacity constraint C_i and an egress capacity constraint K_i. The intradomain topology provides the shortest path distance between any two border routers b_i and b_j, which is denoted by d(i, j).

[0048] The external BGP peering sessions at the border routers receive advertisements for network prefixes. Let P_lK P_m denote the set of prefix advertisements received across all border routers and, for each such prefix P_k, let Out(k) denote the set of border routers at which an advertisement for P_k has been received. This notation is employed, since these are the border routers that may egress outgoing data traffic destined for P_k. Also, for simplicity of exposition, it is assumed that the set of prefixes are non-overlapping. Finally, traffic may be measured or estimated between each neighbor A_h and any destination prefix P_k. Let t(h,k) denote such traffict(h,k). is set to zero for any neighbor A_h for which it is not desired to transit traffic destined for P_k.

[0049] Note that the capacity constraints, C_i and K_j are specified per router. The solutions presented herein can be extended in a straightforward manner to provide for capacities specified on a border interface granularity.

[0050] Given this notation (see Table I for a summary), the problem statement for the two problem variants discussed above may be formulated.

[0051] Problem Statement

[0052] The BGP router selection problem involves selecting a pair of ingress and egress routers for traffic from each neighbor AS to every advertised prefix such that the total cost of carrying transit traffic is minimized. It is assumed that all the traffic from a neighbor to a specific prefix ingresses at a single border router. This can be ensured in BGP by either (1) setting the export policy to only advertise the prefix at the selected ingress router, or (2) including a relatively low MED value in the advertisement at the router, or (3) artificially extending the length of the AS path attribute at routers different from the selected router. Further, the selection of both ingress and egress border routers must be consistent with the BGP route acceptance mechanism.

[0053] MES Problem: Compute an assignment function :(1,K,q,1,K m)(1,K,n,1,K,n) from (AS, prefix) pairs to (ingress, egress) router pairs such that _h,kt(h,k)d((h,k)) is minimized, and satisfies the following constraints:

[0054] If (h,k)(i,j), then iIn(h) and jOut(k).

[0055] Ingress capacity constraints of routers are satisfied, that is, for all i, _{h,k:(h,k)(i,l)}t(h,k)C_i.

[0056] Egress capacity constraints of routers are satisfied, that is for all j, _{h,k:(h,k)(l,j)}t(h,k)K_j.

[0057] For a prefix P_k, if for some h,(h,k)(i,j), then there does not exist a g,iIn(g) and lQ(i,j,k) such that (g,k)(i,l).

[0058] The objective function of the MES problem requires that the computed minimizes the total distance traversed by transit traffic within the network, which reflects the cost of transporting transit traffic. While the intra-domain shortest path distance d is used in the objective function, other distance measures such as the minimum number of hops could be substituted in lieu of d. Also, in the final constraint, Q is a utility function that is used to specify, for a given ingress and egress router pair b_i and b_j and a given prefix P_k, the set of alternative egress routers for P_k that are closer than b_j. Thus Q(i,j,k) is defined as the set of routers llOut(k)d(i,l)<d(i,j)³. This final constraint, which is referred to as the proximity constraint, ensures that an (A_h,P_k) pair cannot be assigned an egress router b_j if a g exists such that (A_g,P_k) is assigned to an egress router b_l,lQ(i,j,k).

[0059] The proximity constraint ensures that the choice of ingress and egress routers made by are enforceable in the context of the BGP selection process. In order to enable a set of routers SOut(k) to egress traffic for P_k, the import policy at each router in S assigns an equal (but high) local-preference to the advertisement for P_k and manipulates the AS path so that they are equal. Thus, Step 4 of the BGP acceptance process is used to break ties, and each ingress router selects the closest router from S to egress traffic for P_k. The proximity constraint ensures that is indeed consistent with this choice.

[0060] The SES problem is identical to MES, except that the proximity constraint is replaced with the following constraint which forces all traffic for a prefix P_k to egress through a single egress router.

[0061] For all g,h,(g,k)(h,k).

[0062] The single egress constraint for each prefix P_k can be realized in BGP by setting a higher value for local-preference at the selected egress router for P_k in the import policy.

[0063] Consider the AS illustration in FIG. 1A having four border routers b₁,K,b₄. Routers b₁ and b₂ serve as ingress routers (so K₁K₂0) with capacity constraints C₁50 and C₂60, respectively. Routers b₃ and b₄ are egress routers (so C₁C₂0) with bandwidth constraints K₃75 and K₄50, respectively. The intra-domain distances between ingress and egress routers are as shown in FIG. 1A. Thus, d(1,3)10 and d(1,4)50. Two prefixes P₁ and P₂ are advertised at both egress routers, and so Out(1)Out(2)3,4. Two AS neighbors A₁ and A₂ ingress data traffic through the ingress routers, so In(1)In(2)1,2 Finally, the amount of traffic from the AS neighbors to the destination prefixes is given by t(1,1)t(2,2)30,t(1,2)15 and t(2,1)25.

[0064] FIG. 1B depicts the optimal assignment _s for the single egress case. In the assignment, _s(1,1)(1,3), _s(1,2)(1,4), _s(2,1)(2,3) and _s(2, 2)(2,4). Router b₁ ingresses all the traffic from A₁, while b₂ ingresses all traffic from A₂. Also, b₃ egresses traffic for P₁ and b₄ egress traffic for P₂ Assignment _s satisfies the ingress and egress capacity constraints of the routers, with traffic ingressing at b₁ and b₂ is 45 and 55, respectively, while the traffic egressing from b₃ and b₄ is 55 and 45, respectively. The total cost of transporting traffic is. Observe that b₄ cannot be chosen to egress all 55 units of traffic for P₁ since this would exceed its capacity constraint of 50. Similarly, alternate assignments like the one which selects b₁ to ingress all traffic for P₂ and b₂ to ingress all traffic for P₁, while meeting ingress capacity constraints, results in a substantially higher cost of 3350.

[0065] FIG. 1C illustrates the optimal assignment _m for the multiple egress case. Here, as for the single egress case above, b₁ ingresses traffic from A₁, b₂ ingresses traffic from A₂ and b₃ egresses traffic for P₁. However, egress traffic for P₂ is split between b₃ and b₄, with b₃ egressing traffic from A₁ to P₂ and b₄ egressing traffic from A₂ to P₂. The new assignment _m has a cost of 1250 which is lower than the cost of 1850 for _s presented above. In this case, the traffic from A₁ to P₂ traverses a shorter distance d(1,3)10 in _m compared to d(1,4)50 in _s. Note that even though router b₃ egresses more traffic (70 units) in _m, its capacity constraint of 75 is still not violated. Also, _m satisfies the proximity constraint since traffic for P₂ from A₁ and A₂ egress at routers b₃ and b₄, respectively, which are closest to the respective ingress routers for the traffic. FIG. 1D illustrates an example of an assignment that does not satisfy the proximity constraint. The assignment is illegal because traffic from A₂ to P₁ ingresses at router b₂ and egresses at router b₃ even though a closer router b₄ is egressing traffic for P₁ (from A₁).

[0066] Integer Program Formulation

[0067] The BGP router selection problem may be formulated as an integer program. For each prefix P_k and each neighbor ingressing traffic for P_k, A_h, an ingress border router b_i,iIn(h) and an egress border router b_j,jOut(k) should be selected. A variable x_ij^hk is defined to denote such selection, so x_ij^hk1 if b_i is selected as the ingress router and b_j is selected as the egress router for traffic from A_h to prefix P_k, and x_ij^hk0 otherwise.

[0068] The integer program for the BGP route advertisement problem is then formulated as follows: $\begin{array}{cc}\min \underset{k}{}\underset{h}{}\underset{i\mathrm{In}\left(h\right)}{}\underset{j\mathrm{Out}\left(k\right)}{}{x}_{\mathrm{ij}}^{\mathrm{hk}}d\left(i,j\right)t\left(h,k\right)& \left(1\right)\end{array}$

[0069] subject to $\begin{array}{cc}j:\underset{k:j\mathrm{Out}\left(k\right)}{}\underset{h}{}\underset{i\mathrm{In}\left(h\right)}{}{x}_{\mathrm{ij}}^{\mathrm{hk}}t\left(h,k\right)K_j& \left(2\right)\\ i\underset{hi\mathrm{In}\left(h\right)}{}\underset{k}{}\underset{j\mathrm{Out}\left(k\right)}{}{x}_{\mathrm{ij}}^{\mathrm{hk}}t\left(h,k\right)C_i& \left(3\right)\\ k,h:\underset{i\mathrm{In}\left(h\right)}{}\underset{j\mathrm{Out}\left(k\right)}{}{x}_{\mathrm{ij}}^{\mathrm{hk}}=1& \left(4\right)\end{array}$

[0070] Equation (1) is the integer programming extension to the minimization objective noted for both problem variants in the problem statement. Likewise, equations (2) and (3) specify the egress and ingress capacity constraints in the integer program. Equation (4) is used to specify that, for any prefix and any neighbor to which that prefix must be advertised, the solution must include exactly one selected ingress router from the given neighbor and one selected egress router toward the destination prefix.

[0071] The formulation as presented thus far allows for multiple egress routers for a given prefix across different neighbors, but does not enforce the proximity constraint. To constrain the formulation further, an additional set of integer variables z_j^k is defined such that z_j^k1 if b_j is chosen as an egress router for traffic to prefix P_k for one or more ingress neighbors, and z_j^k0 otherwise.

[0072] Constraint (7) essentially captures the proximity constraint. This completes the integer programming formulation for the multiple egress selection.

[0073] To change the formulation for the single egress selection case, z_j^k is further constrained. To assure that for a prefix P_k, only a single egress is selected across all border routers, Equation 7 is replaced by the following: $\begin{array}{cc}k:\underset{j\mathrm{Out}\left(k\right)}{}{z}_j^k=1& \left(8\right)\end{array}$

[0074] Algorithms for Single Egress Variant

[0075] The SES problem can be shown to be a generalization of the generalized assignment problem (GAP) which is known to be NP-hard and has been well-studied in the operations research and theoretical computer science communities. See for example, J. H. Lin and J. S. Vitter, -approximations with Minimum Packing Constraint Violation, Proceedings of the 24th Annual ACM Symposium on the Theory of Computation, Victoria, Canada, May 1992, pp. 771-782; and D. B. Shmoys and E. Tardos, An Approximation Algorithm for the Generalized Assignment Problem, Mathematical Programming A, vol. 62, pp. 461-474, 1993, both incorporated herein by reference). The definition of GAP is as follows.

[0076] Generalized Assignment Problem: Given jobs and machines, a processing time p_rs and cost c_rs for processing job r on machine s, and a total processing time T_s available for each machine s, compute an assignment f:1,K,1,K, of jobs to machines such that:

[0077] the total cost of processing jobs is minimized, that is, _rC_rf(r) is minimal, and

[0078] the processing time for jobs on each machine s does not exceed T_s, that is, _r.f(r)sP_rsT_s.

[0079] To show that SES is at least as difficult as GAP and thus also NP-hard, GAP is shown to be only a special case of SES. Consider the instance of SES where Out(k)1 for every prefix P_k, and K_j for each egress router b_j is very large. This corresponds to the case when there is only one egress router per prefix, and thus, egress routers for prefixes are held constant, as well as have unconstrained capacity. The resulting problem of computing ingress routers for each (A_h,P_k) pair is equivalent to GAP, where each ingress router b_i corresponds to a machine with total processing time C_i, and each (A_h,P_k) pair corresponds to a job with processing time and cost on the machine for ingress router b_i as follows (let b_jk be the fixed egress router for prefix P_k)

[0080] Processing time: t(h,k) if iIn(h); otherwise.

[0081] Cost: d(i,j_k)t(h,k) if iIn(h); otherwise.

[0082] Revisiting Example 1, consider the AS in FIG. 1. Suppose that egress router b₃ is selected to egress traffic for prefix P₁ and egress router b₄ is chosen to egress traffic for P₂. Then, the problem of computing the optimal ingress routers for traffic from ASes A₁ and A₂ to prefixes P₁ and P₂ is equivalent to GAP. In the GAP instance, there are two machines 1 and 2 corresponding to ingress routers b₁ and b₂ with processing times T₁C₁50 and T₂C₂60. Further, there are four jobs corresponding to (A_h,P_k) pairs (1,1), (1,2), (2,1) and (2,2). The processing time of job (1,1) on both machines is t(1,1)30, while the processing time of job (1,2) is t(1,2)15. The cost of processing job (1,1) on machine 2 is d(2,3)t(1,1)600 (since b₃ is egress router for P₁), while that of processing job (1,2) on machine 1 is d(1,4)t(1,2)750 (since b₄ is egress router for P₂) Clearly, the optimal assignment for the GAP instance is also the optimal cost assignment for the SES instance with egress routers for P₁ and P₂ held constant at b₃ and b₄, respectively.

[0083] It can be also be shown that, if ingress routers for each (A_h,P_k) pair are held constant, then the problem of computing egress routers for each prefix can be mapped to GAP by considering each egress router b_j to be a machine and each prefix P_k to be a job with processing time and cost _ht(h,k) and _hd(i_hk,j)t(h,k), respectively on machine j (here, i_hk is the ingress router for the pair(A_h,P_k)).

[0084] GAP is not only intractable, but also very difficult to solve approximately. Even ignoring costs (e.g., setting all job costs to 0), it is intractable to compute an assignment of jobs to machines such that the total processing time constraints of machines is not violated (see, J. K. Lenstra, D. B. Shmoys and E. Tardos, Approximation Algorithms for Scheduling Unrelated Parallel Machines, Mathematical Programming A, vol. 46, pp. 259-271, 1990, incorporated herein by reference). Thus, the only option available is to rely on heuristics to solve GAP, and its generalizations like SES.

[0085] The illustrated approach to solving the SES problem is iterative, and essentially relies on reducing it to GAP by fixing either the ingress or egress routers as described above. In each iteration, either the ingress or egress is held constant, and the resulting GAP instance is solved. The problem, however, is that existing algorithms for solving GAP do not guarantee that processing time constraints of machines will be met. Thus, in the following subsection, a heuristic for solving GAP without violating machine constraints should first be established, and subsequently use this as the building block for the illustrated SES heuristic.

[0086] Generalized Assignment Problem Heuristic

[0087] As mentioned above, much previous work has been performed on GAP, and good polynomial-time approximation algorithms for GAP exist that relax machine processing time constraints. Let C be the cost of the optimal solution to GAP that does not violate any capacity constraints. Then an (,) approximation algorithm for GAP is one that gives a solution with cost at most C and with capacity constraints violated by, at most, a factor of . The best known result is by Shmoys and Tardos, supra, where a (1,2) approximation algorithm is given. Lenstra, Shmoys and Tardos, supra, have also shown that it is NP-hard to obtain (1,) approximation algorithm for GAP for <3/2.

[0088] The algorithm of Shmoys and Tardos, supra, is based on first solving the LP relaxation of the integer programming formulation for GAP, and then rounding the fractional solution to a nearby integer solution. The total cost of the assignment computed by the Shmoys and Tardos algorithm is optimal, but, as noted above, the processing times of jobs assigned to a machine may exceed the machine's total processing capacity by at most a factor of 2 (thereby respecting a predetermined multiple of the capacities). FIG. 2 presents a greedy heuristic (Procedure GREEDY) that uses the assignment f computed by the Shmoys Tardos algorithm as the basis to compute a new assignment f that satisfies processing time constraints and still has a low cost.

[0089] In Procedure GREEDY, jobs on machines in which processing times constraints are violated are re-assigned to other machines with sufficient capacity to process the jobs. This process of rescheduling jobs from violated machines to non-violated machines is continued until either no violated machines remain or no more jobs on violated machines can be re-assigned. The critical issue is which jobs on violated machines should be chosen for migration and which machines they should be migrated to. A greedy approach is adopted in which, during each iteration, the job r and machine t for which transferring r to t results in the smallest increase in cost per unit decrease in the violation amount is chosen. Note that in Step 11, c_rtc_rs is the increase in cost associated with re-assigning r from s to t, while minp_rs,U_sT_s is the decrease in the violation.

[0090] The time complexity of Procedure GREEDY can be shown to be O(²), but this is subsumed by the time complexity of the underlying Shmoys Tardos algorithm.

[0091] Single Egress Selection Problem Heuristic

[0092] The SES solution should compute the optimal cost assignment function from (h,k) pairs to (i,j) pairs, where iIn(h) and jOut(k) are the ingress and egress routers, respectively, for traffic from AS A_h to prefix P_k. Further, the computed assignment should also satisfy the bandwidth constraints of ingress and egress routers, and assign all pairs involving a specific prefix to a single egress router. A key observation, made earlier in the section, is that if the egress (ingress) routers for traffic involving all (A_h,P_k) pairs were to be held constant, computing the minimum cost ingress (egress) routers that meet the constraints is essentially the GAP problem. Starting with an initial assignment of egress routers to (A_h,P_k) pairs, GAP can be iteratively invoked to first compute a set of good ingress routers (for the initial egress routers), and then fix the newly computed ingress routers to compute a better set of egress routers by invoking GAP again, and so forth.

[0093] This is the idea underlying the heuristic presented in FIG. 3. Instead of computing the optimal ingress and egress routers for (A_h,P_k) routers at the same time, the procedure computes them separately by fixing one or the other at their most recent values, and repeats this process for a sufficient number of iterations until the cost of the solution becomes stable.

[0094] The input parameter to Procedure SINGLEEGRESS is a counter that controls the number of iterations, where each iteration computes a new set of ingress/egress routers. The variable function keeps track of the most recent values of ingress and egress routers for (A_h,P_k) pairs, with (h,k)1 and (h,k)2 denoting the ingress and egress routers for the pair (A_h,P_k), respectively. For the initial assignment of egress routers to (A_h,P_k) pairs, ingress router capacity constraints are ignored. This can be shown to be equivalent to the GAP problem with individual prefixes corresponding to jobs, egress routers corresponding to machines and costs/processing times for jobs on machines as described in step 1. For this infinite ingress capacity preliminary step, note the calculation of the cost c_kj of assigning job k (for prefix P_k) to machine j (for egress router b_j). To minimize the overall cost, the ingress router b_i,iIn(h) that is closest to b_j for the traffic from A_h to P_k is chosen. Also, the processing time p_kj of job k is constant for all machines j, and is the totality of traffic directed to P_k from all the ASes. The assignment function f as a result of solving GAP assigns prefixes to egress routers, which are captured in in step 2.

[0095] In the body of the while loop of the procedure, new ingress routers are computed in step 5 with egress routers held constant at their most recently computed values stored in ( )2, and new egress routers are computed in step 7 relative to the most recently computed ingress routers in ( )1. values are updated to reflect the newly computed values in steps 6 and 8. Note that when computing egress routers in step 7, each prefix is treated as a separate job, but in the computation of ingress routers in step 5, each (AS, prefix) pair becomes a separate job. This is because of the single egress constraint which is asymmetric and requires all (A_h,P_k) pairs involving the same prefix to be assigned to a single egress router, while different (A_h,P_k) pairs with identical prefixes or ASes, can be mapped to different ingress routers.

[0096] Algorithms for Multiple Egress Variant

[0097] An iterative approach similar to the one used for the single egress case (see FIG. 3) can also be used to compute multiple egress routers for each prefix. The high-level idea is again to fix one of ingress or egress routers for (A_h,P_k) pairs, and then compute the other, and to repeat this process for a certain number of iterations. However, since prefixes can now have multiple egress routers, the simple approach of solving an instance of GAP with each prefix as a job as is done in step 7 of Procedure SINGLEEGRESS is not available. Instead, in this section, a new heuristic is proposed that for fixed ingress routers (h,k)1, computes multiple egress routers for each prefix such that for each (A_h,P_k) pair, the traffic from A_h towards P_k egresses through the egress router for P_k that is closest to (h,k)1, and egress router bandwidth constraints are not violated.

[0098] Procedure MULTIPLEEGRESS is similar to Procedure SINGLEEGRESS except for steps 5 and 7. step 1 which computes an initial assignment of egress routers for prefixes can be used as is. This is because the single egress router computed for each prefix in step 1 of SINGLEEGRESS satisfies both the bandwidth constraint as well as the constraint that traffic for each (A_h,P_k) pair egress through the router for P_k that is closest to the ingress router for (A_h,P_k). step 5 of SINGLEEGRESS computes a single ingress router for each (A_h,P_k) pair when the egress router for it is held constant at (h,k)2. To handle multiple egress routers per prefix, Procedure MULTIPLEEGRESS requires only a slight modification to the c_(h,k),i of assigning job (h,k) to ingress router b_i. This is needed to reflect the fact that (A_h,P_k) cannot be assigned to ingress router b_i if there is an egress router for P_k that is closer to b_i than (h,k)2 f. Thus, c_(h,k),id(i,(h,k)2)t(h,k) if iIn(h) and for every g,(g,k)Q(i,j,k); otherwise, c_(h,k),i. Recall from above that Q(i,j,k) denotes the set of egress routers in Out(k) that are closer to b_i than b_j.

[0099] The remainder of this section focuses on developing a heuristic for step 7 that involves computing an egress router for each (A_h,P_k) pair when the ingress router for it is held constant at (h,k)1.

[0100] Integer Program Formulation for Step 7

[0101] In the multiple egress case, for a given prefix P_k, different (A_h,P_k) pairs may be assigned different egress routersthis is a big departure from the single egress case where egress routers for all (A_h,P_k) pairs are identical for a given prefix. Thus, instead of a single job per prefix, a separate job (h,k) should be defined for each (A_h,P_k) pair. A simple approach would be to solve GAP to compute egress routers in the same way ingress routers were solved in step 5 of Procedure SINGLEEGRESS.

[0102] The problem with using GAP in this manner is that it does not incorporate the additional proximity constraint which states that an (A_h,P_k) pair cannot be assigned an egress router b_j if a g exists such that (A_g,P_k) is assigned to an egress router b₁,lQ(i,j,k) Fortunately, the proximity constraint can be captured in an integer program, whose linear relaxation can subsequently be solved and rounded (using the Shmoys Tardos technique for GAP from Shmoys and Tardos, supra, to yield a better solution than simply solving GAP to compute the egress routers. Suppose that variable y_j^hk is 1 if b_j is chosen as the egress router for traffic from AS A_h to prefix P_k, where the ingress router is held constant at (h,k)1. The following integer program captures all the constraints on the selection of egress routers (for fixed ingress routers), while minimizing cost. $\begin{array}{cc}\min \underset{k}{}\underset{h}{}\underset{j\mathrm{Out}\left(k\right)}{}{y}_j^{\mathrm{hk}}d\left(\left(h,k\right)\left[1\right],j\right)t\left(h,k\right)& \left(9\right)\end{array}$

[0103] subject to the following constraints: $\begin{array}{cc}h,k:\underset{j\mathrm{Out}\left(k\right)}{}{y}_j^{\mathrm{hk}}=1& \left(10\right)\\ j:\underset{k:j\mathrm{Out}\left(k\right)}{}\underset{h}{}{y}_j^{\mathrm{hk}}t\left(h,k\right)K_j& \left(11\right)\end{array}$ g,hkjOut(k): $\begin{array}{cc}\underset{l\left(\mathrm{Out}\left(k\right)-Q\left(\left(h,k\right)\left[1\right],j,k\right)\right)}{}{y}_l^{\mathrm{hk}}+\underset{lQ\left(\left(h,k\right)\left[1\right],j,k\right)}{}{y}_l^{\mathrm{gk}}1& \left(12\right)\end{array}$ h,k,j:y_j^hk0,1(13)

[0104] Without Constraint (12), the remaining constraints essentially reduce to GAP, with costs and processing times for jobs (h,k) and machines j as described for the GAP-based approach earlier in this subsection. Constraint (12) captures the proximity constraint by ensuring that if for some h,k and jOut(k), the egress router for (A_h,P_k) is not selected from Q((h,k)1,j,k) (that is, the egress router for (A_h,P_k) is chosen from Out(k)Q((h,k)1,j,k)), then for all g, the egress router for (A_g,P_k) cannot be chosen from Q((h,k)1,j,k). Note that the optimal fractional solution to the linear relaxation of the above integer program is a feasible solution to the LP without Constraint (12), which is essentially GAP. Thus, the LP rounding technique of Shmoys and Tardos can be used to compute an assignment of (A_h,P_k) pairs to egress routers from the optimal fractional solution to the LP comprising of Constraints (9)-(12), since this fractional solution is a feasible solution to GAP.

[0105] Heuristic for Step 7

[0106] The assignment of (A_h,P_k) pairs to egress routers obtained as a result of rounding the optimal fractional solution for the LP consisting of Constraints (9)-(12) has two basic problems: (1) The capacity constraints of egress routers may be violated (by at most a factor of 2), and (2) the proximity constraints may be violated. A Procedure MULTIPLEEGRESSSTEP7 attempts to remedy this by using heuristics to reassign (A_h,P_k) pairs to egress routers such that both capacity as well as proximity constraints are met. The pseudo-code for this procedure is set forth in FIG. 4. Procedure MULTIPLEEGRESSSTEP7 accepts as an input parameter the assignment for which ( )1 stores the most recently computed ingress router for each (A_h,P_k) pair. It computes in ( )2 new egress routers for each (A_h,P_k) pair without modifying any of the input ingress router assignments. Further, Procedure MULTIPLEEGRESSSTEP7 attempts to ensure that the returned assignment satisfies both capacity as well as proximity constraints.

[0107] As discussed earlier, the assignment f computed in step 2 may not meet capacity and proximity constraints. Suppose that for each prefix P_k, f_p(k) is the set of all egress routers for prefix P_k (step 3). Then, for the ingress routers specified by ( )1 and for egress routers for prefixes as in f_p(k), a unique assignment ( )2exists that maps each (A_h,P_k) pair to an egress router, and that satisfies the following two properties: (1) satisfies proximity constraints, and (2) for all h,k,(h,k)2f_p(k). To see this, suppose for an (A_h,P_k) pair, jf_p(k) is the egress router closest to (h,k)1, the ingress router for the pair. Then (h,k)2j satisfies the above two properties. A function called compute egress in MULTIPLEEGRESSSTEP7 returns such a ( )2.

[0108] Procedure MULTIPLEEGRESSSTEP7 iteratively applies one of two basic transformations to to reduce the total violation amount. The first is to delete a violated egress router j from f_p(k) for a prefix P_k. This has the effect of diverting all the egress traffic for P_k passing through j to other routers, thus decreasing the degree to which j is violated. Note, however, that the violation amount of other routers carrying the re-directed traffic from j could increase. The second primitive transformation is to add an egress router j that satisfies capacity constraints to f_p(k) for a prefix P_k. This has the potential to reduce the violation amount by assigning to j, egress traffic for P_k passing through other violated egress routers. It is straightforward to observe that addition of router j to f_p(k) can cause the violation amount for only j (and no other router) to increase. Procedure MULTIPLEEGRESSSTEP7 repeatedly applies one of the two transformations to until no capacity constraints are violated or there is no remaining transformation for reducing the violation amount.

[0109] In Procedure MULTIPLEEGRESSSTEP7 V_jmax0,_{h,k (h,k)2j}t(h,k)K_j represents the amount by which capacity of egress router j is violated, and C_hkt(h,k)d((h,k)1,(h,k)2) represents the cost of transporting traffic from ASes to prefixes. In each iteration of the main loop of the procedure, the prefix P_k and egress router j is chosen for which the increase in cost per unit decrease in violation amount is minimum; that is, if is the new assignment (that satisfies proximity constraints) after deleting or inserting j from f_p(k), then $\frac{C_j^{{}^{}}-C_j^{}}{\underset{l}{}{V}_l^{}\underset{l}{}{V}_l^{{}^{}}}$

[0110] is minimum. An egress router j is a candidate for addition/deletion from f_p(k) only if (1) the operation results in a decrease in the overall amount of violation of the capacity constraints of egress routers, and (2) the operation does not cause an egress router that previously satisfied capacity constraints to now violate them.

[0111] Finally, for a prefix P_k, only egress routers j that violate capacity constraints are candidates for deletion, while for insertion only routers that satisfy capacity constraints are candidates.

[0112] Bressoud, et al., supra, demonstrates that the worst-case complexity of Procedure MULTIPLEEGRESSSTEP7 is O(n²mq(mlog n)).

[0113] Turning now to FIG. 5, illustrated is a block diagram of one embodiment of a system, generally designated 500, for configuring border gateway selection for transit traffic flows in a computer network constructed according to the principles of the present invention.

[0114] The system 500 includes a border gateway modeler 510. The border gateway modeler 510 builds a model 530 of cooperating border gateways. The model 530 includes capacities of the border gateways as described above.

[0115] The system 500 further includes a traffic flow optimizer 520. The traffic flow optimizer is associated with the border gateway modeler 510 and analyzes traffic thus. First, the traffic flow optimizer 520 assigns traffic to the border gateways in accordance with GAP. Next, the traffic flow optimizer 520 reassigns the traffic to the border gateways based on cost until the capacities are respected (i.e., such that no capacities are violated). In the illustrated embodiment of the present invention, the system 500 is embodied in a sequence of software instructions executable in a computer. The heuristics of FIGS. 2 and 3 are examples of the processes that can be carried out within the system 500.

[0116] Turning now to FIG. 6, illustrated is a method, generally designated 600, of managing a computer network carried out according to the principles of the present invention. The method 600 begins in a start step 610, wherein it is desired to improve, and advantageously optimize, the operation of the border routers of a computer network (which may be an AS). The method 600 may be carried out upon configuration of the network or during operation of the computer network. During operation, the method 600 may be carried out, e.g., per a predetermined schedule, periodically according to a predetermined interval, in response to computer network operating conditions or upon explicit command.

[0117] Once started, the method 600 calls for the collecting of route advertisement information from border routers in the computer network (a step 620). The method 600 further calls for the retrieving of existing policy information regarding each of the border routers (a step 630). The method further calls for the collecting of traffic information regarding each of the border routers (a step 640). The steps 620, 630 640 can be carried out in any desired order. Further, the method 600 may call for the collection of further data from the computer network as may be advantageous to a particular application.

[0118] Next, in a step 650, the method calls for employing the route advertisement information, the existing policy information and the traffic information to compute updated policy information. This may be performed in accordance with the above general teachings or in any other advantageous manner. Finally, to ensure that the computer network operates in accordance with the updated policy information, the method 600 calls for the replacing of the existing policy information with the updated policy information. In this manner, it is expected that traffic through the computer network will be decreased, and perhaps minimized. The method ends in an end step 670.

[0119] Although the present invention has been described in detail, those skilled in the art should understand that they can make various changes, substitutions and alterations herein without departing from the spirit and scope of the invention in its broadest form.