A deterministic approach for route selection in the Internet and other multi-homed networks is presented that is based upon a mathematical model that takes into consideration performance and costs while satisfying commitment constraints. The approach is expressed with a linear programming formulatio
A deterministic approach for route selection in the Internet and other multi-homed networks is presented that is based upon a mathematical model that takes into consideration performance and costs while satisfying commitment constraints. The approach is expressed with a linear programming formulation that can be solved with conventional linear programming solver software. Performance metrics can be defined and combined in order to achieve the best route selection depending on requirements. Some of the potential benefits of the approach include: a global optimal solution for routing traffic (using metrics such as performance, cost, and other constraints), a dynamic weight assignment for performance metrics, and a flexible problem definition to add routing rules (e.g. static and restricted routes) to the model.
대표청구항▼
1. A method of routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has capacity associated therewith, said method comprising: determining a first, second, and third traffic flow demand for a first, second, and third prefix, respectively, in a netw
1. A method of routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has capacity associated therewith, said method comprising: determining a first, second, and third traffic flow demand for a first, second, and third prefix, respectively, in a network prefix set;gathering performance data for each of said first, second, and third prefixes along each of said plurality of routes;making first, second, and third routing decisions in a computer for routing each of said first, second, and third prefixes, respectively, along one of said plurality of routes, said computer using a linear programming technique to make said first, second, and third routing decisions, said linear programming technique including solving an objective function subject to a plurality of constraints, wherein said plurality of constraints includes said capacity, as well as prices associated with said routes; wherein: said first routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;said second routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; andforwarding Internet Protocol (IP) packets along said plurality of routes in accordance with said first, second, and third routing decisions. 2. The method of claim 1 further including: determining a plurality of additional traffic flow demand for a plurality of additional prefixes in the network prefix set;gathering performance data for each of said plurality of additional prefixes along each of said plurality of routes;making a plurality of additional routing decisions in the computer for routing each of the plurality of additional prefixes along one of said plurality of routes, wherein:said first routing decision also takes into account said plurality of additional traffic flow demand;said second routing decision also takes into account said plurality of additional traffic flow demand;said third routing decision also takes into account said plurality of additional traffic flow demand; andsaid plurality of additional routing decisions each take into account said first, second, and third flow demands, as well as said capacity of said plurality of routes. 3. The method of claim 1 further including; inputting a route-specific constraint into said computer for a specific prefix, said route specific constraint identifying at least one route to be avoided or used for the specific prefix; andusing said route-specific constraint when determining the first, second, and third routing decisions for each prefix in said network prefix set. 4. The method of claim 3 further including: inputting a minimum commitment level into said computer for each of said plurality of routes, said minimum commitment level identifying a level of traffic for each route above which additional charges are incurred;inputting a price weighting into said computer, said price weighting being indicative of an importance of routing traffic in a manner that reduces price;inputting a capacity relaxation value into said computer for a first one of said routes, said capacity relaxation value identifying an acceptable degree to which traffic routed to said first one of said routes may exceed the minimum commitment level for said first one of said routes;using said minimum commitment level and said price weighting when making each of said first, second, and third routing decisions; andusing an increased capacity for said first one of said routes when determining routing decisions for said first, second, and third prefixes, said increased capacity corresponding to said capacity relaxation value. 5. The method of claim 4 further including: using a first linear programming iteration to determine said first routing decision;subsequently using a second linear programming iteration to determine said second routing decision, wherein said second linear programming iteration is based on a first reduced capacity, said first reduced capacity accounting for an amount of the capacity consumed by the traffic flow demand of said first prefix; andsubsequently using a third linear programming iteration to determine said third routing decision, wherein said third linear programming iteration is based on a second reduced capacity, said second reduced capacity accounting for an amount of the capacity consumed by the traffic flow demand of said first and second prefixes. 6. A system for routing computer network traffic from a multi-homed location to a plurality of routes wherein each route has a capacity associated therewith, said system comprising: memory;a processor configured to execute instructions in the memory to carry out the following functions;a traffic estimator adapted to determine a traffic flow demand for a first, second, and third prefix in a network prefix set;a performance evaluator adapted to gather performance data for each of said first, second, and third prefixes along each of said plurality of routes;a routing engine adapted to make first, second, and third routing decisions for routing each of said first, second, and third prefixes, respectively, along one of said plurality of routes, wherein:said first routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;said second routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes;said third routing decision takes into account said first, second, and third flow demands, as well as said capacity of said plurality of routes; andwherein said routing engine performs the following: (a) determines a performance value for each of said first, second, and third prefixes based upon said performance data, said performance values including a weighted sum of a latency metric and a loss metric;(b) receives from a user a plurality of weights to be used in computing said weighted sum;(c) determines a set of said first, second, and third routing decisions that maximizes a sum of said performance values;(d) forwards Internet Protocol (IP) packets along said plurality of routes in accordance with said set of first, second, and third routing decisions; and(e) uses a linear programming technique to make said first, second, and third routing decisions, wherein said linear programming technique includes solving an objective function subject to a plurality of constraints including said capacity of said plurality of routes, as well as prices associated with said routes. 7. The system of claim 6 wherein: said traffic estimator determines a plurality of additional traffic flow demand for a plurality of additional prefixes in the network prefix set;said performance evaluator gathers performance data for each of said plurality of additional prefixes along each of said plurality of routes; andsaid routing engine makes a plurality of additional routing decisions for routing each of the plurality of additional prefixes along one of said plurality of routes; wherein:said first routing decision also takes into account said plurality of additional traffic flow demand;said second routing decision also takes into account said plurality of additional traffic flow demand;said third routing decision also takes into account said plurality of additional traffic flow demand; andsaid plurality of additional routing decisions each take into account said first, second, and third flow demands, as well as said capacity of said plurality of routes. 8. The system of claim 6 wherein said routing engine is adapted to receive a route-specific constraint for a specific prefix and use said route-specific constraint when determining the routing decisions for each prefix in said network prefix set, wherein said route-specific constraint identifies a specific route either be used or avoided for the specific prefix. 9. The system of claim 6 wherein said routing engine is configured to receive from a user a minimum commitment level for each of said plurality of routes, said minimum commitment level identifying a level of traffic for each route above which additional charges are incurred; and said routing engine is further adapted to receive a capacity relaxation value for a selected one of said routes, said capacity relaxation value identifying an acceptable degree to which traffic routed to said selected one of said routes may exceed the minimum commitment level for said selected one of said routes; and said routing engine being is further configured to use an increased capacity for said selected one of said routes when determining routing decisions for said first, second, and third prefixes, said increased capacity corresponding to said capacity relaxation value. 10. The system of claim 9 wherein: said traffic estimator updates said traffic flow demand for said first, second, and third prefixes;said performance evaluator updates performance data for said first, second, and third prefixes along each route; andsaid routing engine determines a revised routing decision for each of said first, second, and third prefixes, wherein each of said revised routing decisions is based upon said updated traffic flow demand, said updated performance data, and the capacity associated with each route.
Belser David ; Bussiere Richard ; Cioli Jeff ; Fee Brendan ; Haggerty William T., Aggregation of mac data flows through pre-established path between ingress and egress switch to reduce number of number connections.
Bubien ; Jr. Walter J. (Prescott AZ) Learish Donald B. (Roselle Park NJ), Best rate telecommunication access code and data transceiver/facilitator (BRTF).
Andrews G. Wayne (Amherst NH) Webber Steven H. (Groton MA) Kelly James P. (Newbury MA) Johnson Lawrence E. (Sudbury MA) Stern Jerry A. (Sudbury MA) Milano ; Jr. Vincent J. (Westwood MA) Davis Charles, Communications system using a central controller to control at least one network and agent system.
Bertin Olivier,FRX ; Galand Claude,FRX ; Maurel Olivier,FRX, Dynamic bandwidth reservation for control traffic in high speed packet switching networks.
Hashimoto Akira (Tokyo JPX) Ito Yuji (Shizuoka JPX), Dynamic updating of routing information for routing packets between LAN\s connected to a plurality of routers via a publ.
Rostoker Michael D. (Boulder Creek CA) Stelliga D. Tony (Pleasanton CA), Error detection and correction method for an asynchronous transfer mode (ATM) network device.
Merkley Kevin L. (Longmont CO) Schumacher Kurt G. (Boulder CO) Sutton Alan R. (Boulder CO), Fault-tolerant system-to-system communications system and method utilizing multiple communications methods to transfer a.
Mahany Ronald L. (Cedar Rapids IA) West Guy J. (Lisbon IA) Bunte Alan G. (Cedar Rapids IA), Hierarchical communication system using premises, peripheral and vehicular local area networking.
Jabs Armin O. (White Marsh VA) Hammel Roy A. (Frederick MD) Garner Jon E. (Purcellville VA), Interface between mobile telecommunication stations and trunks that link to communication carriers.
Balonado,Omar C.; Finn,Sean P.; Karam,Mansour J.; Lloyd,Michael A.; Madan,Herbert S.; McGuire,James G.; Villaverde,Jose Miguel Pulido, Method and apparatus for coordinating routing parameters via a back-channel communication medium.
Aggarwal Ajay (Somersworth NH) Scott Walter (Salem NH) Rustici Eric (Londonderry NH) Bucciero David (Nashua NH) Haskins Andrew (Lee NH) Matthews Wallace (Exeter NH), Method and apparatus for determining a communications path between two nodes in an Internet Protocol (IP) network.
Crawley Eric S. ; Goransson Paul N. ; Shieh Shu Ching ; Burch Gregory A., Method and apparatus for determining alternate routes in a network using a connection-oriented protocol.
Guido M. Schuster ; Michael S. Borella ; Jacek A. Grabiec ; Ikhlaq S. Sidhu, Method and apparatus for measurement-based conformance testing of service level agreements in networks.
Baldonado,Omar C.; Finn,Sean P.; Karam,Mansour J.; Lloyd,Michael A.; Madan,Herbert S.; McGuire,James G.; Villaverde,Jose Miguel Pulido, Method and apparatus for performance and cost optimization in an internetwork.
Burke Christopher J. (Maple Valley WA) Chaffee Janice M. (Auburn WA) Nir Erez (Bellevue WA) Kee Thomas E. (Lynnwood WA), Method and apparatus for selecting between a plurality of communication paths.
Alfonsi Jean-Pierre (La Gaude FRX) Galand Claude (Cagnes Sur Mer FRX) Lebizay Gerald (Vence FRX) Maurel Olivier (Le Cannet FRX), Method and apparatus to speed up the path selection in a packet switching network.
Ayers, Matt; Black, Benjamin J.; Brown, Chris; Carlson, John; Cohn, Dan; Laird, Scott; Miller, Jonathan; Ramsey, Stephen; Ronen, Ophir; Schachter, Paul; Stiffelman, Oscar, Method and system for directing requests for content to a content server based on network performance.
Olivier Bertin FR; Gerard Brun FR; Claude Galand FR; Olivier Maurel FR; Laurent Nicolas FR, Method and system for minimizing the connection set up time in high speed packet switching networks.
Ahuja, Abha; Ayers, Matt; Black, Ben; Brown, Chris; Cohn, Daniel T.; Ramsey, Stephen; Ronen, Ophir; Schachter, Paul J.; Stiffelman, Oscar B.; Wheeler, Christopher D., Method and system for optimizing routing through multiple available internet route providers.
Bertin Olivier,FRX ; Levy-Abegnoli Eric,FRX, Method and system for selecting path according to reserved and not reserved connections in a high speed packet switchin.
Simon Georges-Henri (Wissous FRX) D\Silva Cdric (Fontenay Le Fleury FRX), Method for Radio transmitting information using aircrafts as open transmission relays.
Brocken Franciscus W. A. (Voorhout NLX) Houben Cyrillus G. J. (Utrecht NLX), Method of detecting a routing loop in a telecommunication network, telecommunication network for using the method, and d.
Clarke Kathryn E. (Little Silver NJ) Drake ; Jr. John E. (Pittsboro NC) Pozefsky Diane P. (Chapel Hill NC) Siddall William E. (Chapel Hill NC), Method of selecting least weight routes in a communications network.
Ahmadi Hamid (Somers NY) Chen Jeane S. (Briarcliff Manor NY) Chow Chee-Seng (Ossining NY) Gurin Roch (Yorktown Heights NY) Gn Levent (Durham NC) Lee Anthony M. (White Plains NY) Tedijanto Theodore E., Methods and apparatus for optimum path selection in packet transmission networks.
Ludwig Lester F. (Foster City CA) Lauwers J. Chris (Menlo Park CA) Lantz Keith A. (Los Altos CA) Burnett Gerald J. (Atherton CA) Burns Emmett R. (Incline Village NV), Multimedia collaboration system with separate data network and A/V network controlled by information transmitting on the.
Cain Joseph B. (Indialantic FL) Adams Stanley L. (Indialantic FL) Noakes Michael D. (Melbourne FL), Multiple path routing mechanism for packet communications network.
Krause Jeffrey (Los Altos CA) Strohl Niles E. (Tracy CA) Seaman Michael J. (San Jose CA) Russell Steven P. (Menlo Park CA) Hart John H. (Saratoga CA), Network station with multiple network addresses.
Morrison John A. ; Ramakrishnan Kajamalai Goplaswamy ; Mitra Debasis, Optimization method for routing and logical network design in multi-service networks.
van Tetering Johannes A. M. (Zevenbergen NLX) Denissen Frank L. (Boom BEX), Performance measurement system for a telecommunication path and device used therein.
Wheeler, Christopher D.; Ronen, Ophir; Black, Benjamin J.; McMillin, Michael; Carlson, John, Private network access point router for interconnecting among internet route providers.
Mousseau Gary P. (Waterloo CAX) Lazaridis Mihal (Waterloo CAX) Little Herb A. (Waterloo CAX) Barnstijn Michael A. (Waterloo CAX), Remote control of gateway functions in a wireless data communication network.
Hershey Paul C. (Manassas VA) Waclawsky John G. (Frederick MD), System and method for a workstation monitoring and control of multiple networks having different protocols.
Hluchyj Michael G. (Wellesley MA) Humblet Pierre A. (Cambridge MA) Lee Whay C. (Dorchester MA), System and method for call-by-call source routing with rule-based fallbacks.
Courtois Pierre-Jacques F. C. (Brussels BEX) Scheys Guy F. J. (Brussels BEX) Semal Pierre N. W. (Brussels BEX), System and method for controlling the access rates of packet switching network stations.
Bell Robert T. (Garland TX) Platt Richard B. (Allen TX), System and method for signalling and call processing for private and hybrid communications systems including multimedia.
Miller Phillip (Cedar Rapids IA) Koenck Steven E. (Cedar Rapids IA) Walter Jerry L. (Cedar Rapids IA) Kubler Joseph J. (Boulder CO) Cargin ; Jr. Keith K. (Cedar Rapids IA) Hanson George E. (Cedar Rap, Vehicular data system for communicating with remote host.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.