Method and apparatus for efficient routing of variable traffic
A method and apparatus for provide highly efficient traffic routing for a wide range of possible traffic matrices (TM) in an intra-domain network. That routing optimally balances the traffic loads over a range of traffic matrices so as to minimize the deviation for any particular traffic matrix from the optimal routing. Such a routing provides a guaranteed performance ratio against the best possible network routing. The invention utilizes a method of optimally configuring a traffic network based on solving a linear program to obtain the optimal routing, and then configuring the routing on the network accordingly.
1. A method of configuring a network, comprising:
obtaining information about a plurality of nodes and a plurality of links in the network;
identifying possible origin-destination pairs;
computing an optimum oblivious ratio of the network, wherein the optimum oblivious ratio is an oblivious ratio of a routing having a minimum oblivious ratio, wherein the oblivious ratio is a worst performance ratio the routing can obtain with respect to any traffic matrix of the network, wherein the computing the optimum oblivious ratio is performed by solving a linear program, wherein the linear program is based on a reduced set of input topologies, wherein degree-one nodes are removed, wherein the optimum oblivious ratio is computed by partitioning the network to 2-edge connected components and taking a maximum of the optimum oblivious ratio over the 2-edge connected components; and
configuring the network in accordance with the optimum oblivious ratio.
2. The method of claim 1 , wherein the optimum oblivious ratio is computed using linear constraints on origin-destination pair demands.
3. The method of claim 1 , wherein the input topologies where a path diversity is not possible are removed.
4. A method of configuring a network, comprising:
obtaining information about a plurality of nodes and a plurality of links in the network;
identifying possible origin-destination pairs;
computing an optimum network routing, wherein the computing the optimum network routing is performed by solving a linear program, wherein the linear program is based on a reduced set of input topologies, wherein degree-one nodes are removed, wherein the optimum network routing is computed by partitioning the network to 2-edge connected components and taking a maximum of an optimum oblivious ratio over the 2-edge connected components, wherein the optimum oblivious ratio is an oblivious ratio of a routing having a minimum oblivious ratio, wherein the oblivious ratio is a worst performance ratio the routing can obtain with respect to any traffic matrix of the network; and
configuring the network in accordance with the optimum network routing.
5. The method of claim 4 , wherein the optimum network routing is computed using linear constraints on origin-destination pair demands.
6. The method of claim 4 , wherein the input topologies where a path diversity is not possible are removed.
7. A network comprising:
a plurality of routers that support path-based routing; and
a plurality of links that are connected to the plurality of routers, wherein each path-based routing is configured in accordance with an oblivious routing configuration based on the plurality of routers and the plurality of links, wherein the oblivious routing configuration is derived by:
identifying possible origin-destination pairs;
computing an optimum network routing based on linear constraints placed on origin-destination pair demands, wherein the computing the optimum network routing is performed by solving a linear program, wherein the linear program is based on a reduced set of input topologies and wherein degree-one nodes are removed; and
configuring each path-based routing in accordance with the optimum network routing, wherein the oblivious routing configuration is further derived by partitioning the network to 2-edge connected components and taking a maximum of an optimum oblivious ratio over the 2-edge connected components, wherein the optimum oblivious ratio is an oblivious ratio of a routing having a minimum oblivious ratio, wherein the oblivious ratio is a worst performance ratio the routing can obtain with respect to any traffic matrix of the network.
8. The network of claim 7 , wherein the input topologies where a path diversity is not possible are removed.
9. A network, comprising:
a plurality of network nodes, each of which has configurable routing characteristics;
means for obtaining information about the network;
means for identifying possible origin-destination pairs of network nodes;
means for computing an optimum oblivious ratio of the network, wherein the optimum oblivious ratio is an oblivious ratio of a routing having a minimum oblivious ratio, wherein the oblivious ratio is a worst performance ratio the routing can obtain with respect to any traffic matrix of the network, wherein the means for computing computes the optimum oblivious ratio by solving a linear program, wherein the linear program is based on a reduced set of input topologies and wherein degree-one nodes are removed, and wherein the means for computing computes the optimum oblivious ratio by partitioning the network to 2-edge connected components and taking a maximum of the optimum oblivious ratio over the 2-edge connected components; and
means for configuring the plurality of network nodes in accordance with the optimum oblivious ratio.
10. The network of claim 9 , wherein the means for computing computes the optimum oblivious ratio by using linear constraints on origin-destination pair demands.