(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2003/0147400 A1
`Devi
`(43) Pub. Date:
`Aug. 7, 2003
`
`US 2003O147400A1
`
`(54) OPTIMIZING PATH SELECTION FOR
`MULTIPLE SERVICE CLASSES IN A
`NETWORK
`
`(22) Filed:
`
`Feb. 1, 2002
`
`Publication Classification
`
`(75) Inventor: Bharathi B. Devi, Plano, TX (US)
`
`Correspondence Address:
`BAKER BOTTS LLP.
`2001 ROSS AVENUE
`SUTE 600
`DALLAS, TX 75201-2980 (US)
`(73) ASSignee
`: Fujitsu Network Communications, Inc.
`(21) Appl. No.:
`
`10/061,426
`
`(51) Int. Cl. ............................................. H04L 12/56
`(52) U.S. Cl. ............... 370/395.21; 370/351; 370/395.43
`(57)
`ABSTRACT
`A method for routing traffic in a network includes determin
`ing topology information for the network and determining
`traffic demands for multiple service classes. The method
`further includes determining an objective function for an
`optimization problem using the topology information and
`demands, and determining a Solution to that Specifies a
`network path for each demand.
`
`INTERFACE
`
`PROCESSOR
`
`SERVER
`200
`
`
`
`
`
`
`
`212
`
`
`
`
`
`SOURCE
`DESTINATION
`SERVICE CLASS
`
`
`
`216
`218
`
`Arista Networks, Inc.
`Ex. 1009, p. 1
`
`

`

`Patent Application Publication
`
`Aug. 7, 2003 Sheet 1 of 3
`
`US 2003/0147400 A1
`
`HIC. 1
`
`
`
`
`
`
`
`18Y)
`Ng
`
`SERVER
`200
`
`
`
`TOPOLOGY
`214 - INFORMATION
`
`
`
`o L13
`
`SERVER
`
`200
`
`214
`
`Arista Networks, Inc.
`Ex. 1009, p. 2
`
`

`

`Patent Application Publication Aug. 7, 2003 Sheet 2 of 3
`
`US 2003/0147400 A1
`
`FIC 3
`
`
`
`
`
`TOPOLOGY
`INFORMATION
`
`
`
`
`
`
`
`
`
`OPTIMIZATION
`MODULE
`
`
`
`SERVICE
`SOURCE DESTINATION CLASS
`
`
`
`PATH
`
`1
`
`N2
`
`Arista Networks, Inc.
`Ex. 1009, p. 3
`
`

`

`Patent Application Publication
`
`Aug. 7, 2003 Sheet 3 of 3
`
`US 2003/0147400 A1
`
`FIC 4
`START
`
`400
`
`402
`
`COLLECT DEMANDS
`
`404
`
`POPULATE DEMAND MATRIX
`
`406
`
`408
`
`410
`
`412
`
`418
`
`COLLECT TOPOLOGY
`INFORMATION
`
`COLLECT CONSTRAINT
`INFORMATION
`
`DETERMINE
`OBJECTIVE FUNCTION
`
`DETERMINE TRIAL SOLUTION
`
`
`
`
`
`
`
`OPTIMUM
`SOLUTION FOUND
`p
`
`414
`
`YES
`ASSIGN NETWORK PATHS
`
`END
`
`416
`
`UPDATE TRIAL SOLUTION
`
`Arista Networks, Inc.
`Ex. 1009, p. 4
`
`

`

`US 2003/0147400 A1
`
`Aug. 7, 2003
`
`OPTIMIZING PATH SELECTION FOR MULTIPLE
`SERVICE CLASSES IN A NETWORK
`
`TECHNICAL FIELD OF THE INVENTION
`0001. This invention relates in general to telecommuni
`cations, and more particularly to a method and System for
`optimizing path Selection for multiple Service classes in a
`network.
`
`BACKGROUND OF THE INVENTION
`0002 Telecommunication systems continue to carry
`more and different kinds of traffic over their networks.
`Certain types of traffic require a high degree of reliability, So
`that few or no packets are lost in transit. Other types of traffic
`may be Sensitive to timing, So that Some packets may be lost,
`but the packets that are received need to arrive on time.
`Furthermore, some traffic may be order sensitive, while
`other traffic may be communicated asynchronously. AS
`demand increases, telecommunication Systems must adapt to
`handle increasing amounts and types of traffic.
`
`SUMMARY OF THE INVENTION
`0003. In accordance with the present invention, a method
`and System for optimizing network path Selection for mul
`tiple Service classes in a network is disclosed. In accordance
`with the present invention, the disadvantages and problems
`asSociated with previous methods of optimization have been
`Substantially reduced or eliminated. In particular, certain
`embodiments of the present invention have the advantage of
`allowing Simultaneous optimization for Several Service
`classes.
`In accordance with one embodiment of the present
`0004.
`invention, a method for routing traffic in a network includes
`determining topology information for a network and deter
`mining demands for multiple Service classes. The method
`further includes determining an objective function using the
`topology information and the demands, and determining a
`Solution that Specifies a network path for each demand using
`the objective function.
`0005. In accordance with another embodiment of the
`present invention, a Server includes a memory and a pro
`ceSSor. The memory Stores topology information of a net
`work along with traffic demands for multiple Service classes.
`The processor determines an objective function for an
`optimization problem using the topology information and
`the demands, determines a Solution to the optimization
`problem, and determines a network path for each demand
`using the Solution.
`0006 Technical advantages of certain embodiments of
`the present invention include load balancing. The objective
`function may include a load balancing term So that the
`optimization accounts for load balancing among many linkS.
`This results in a more uniform distribution of traffic among
`links, thus providing more efficient use of network
`CSOUCCS.
`0007. Other technical advantages of certain embodiments
`of the present invention include leSS dependency on indi
`vidual linkS. Unlike previous Systems that always direct
`traffic to the shortest available path, certain embodiments of
`the present invention allow more flexible path determination
`including multiple alternative routes. Thus, when a link fails,
`
`the traffic can often be redirected more easily, and less traffic
`overall is disrupted by the link failure.
`0008 Additional technical advantages of certain embodi
`ments of the present invention include automatic fail-over
`path determination. Certain embodiments of the present
`invention include detection of component failure in the
`network and automatic recalculation of network paths in
`response to the failure. This allows quick recovery from
`component failure. Particular embodiments of the invention
`may include Some, all or none of the enumerated technical
`advantages. These and other technical advantages of certain
`embodiments of the present invention will be apparent from
`the following figures, description and claims.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0009 For a more complete understanding of the present
`invention and its advantages, reference is now made to the
`following description, taken in conjunction with the accom
`panying drawings, in which:
`0010 FIG. 1 illustrates a network including nodes, links,
`and an optimization Server,
`0011 FIG. 2 illustrates the optimization server of FIG. 1
`in more detail;
`0012 FIG. 3 illustrates conceptually a method in accor
`dance with the present invention for providing optimum path
`Selection in a network, and
`0013 FIG. 4 is a flow chart illustrating the steps of a
`method for optimizing path Selection in a network.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`0014 FIG. 1 illustrates a network 100 that includes
`nodes 102, links 104, and an optimization server 200 that
`assigns paths between nodes 102 in network 100. "Nodes'
`refer to any hardware and/or Software that sends and/or
`receives information in network. Nodes 102 may include
`Switches, endpoints, routers, Servers, clients, or any other
`suitable network component. Nodes 102 are denoted by “N”,
`and numbered by Subscripts. A “circuit” refers to any
`connection between a node 102 that is the Source of infor
`mation and a node 102 that is the final destination of the
`information. A “path” refers to the series of links 104 in a
`circuit.
`0015 Links 104 represent any physical and/or logical
`connection between nodes 102. Links 104 may include
`cables, fiber optics, wireless links, or any other Suitable
`method for communicating information between nodes 102.
`A Single logical link 104 may represent more than one
`physical link, in which case the logical link 104 is known as
`an “aggregated link.” LinkS are denoted by "L', and num
`bered with subscripts.
`0016 Optimization server 200 performs various provi
`Sioning tasks including assigning circuits between nodes
`102. Server 200 represents any hardware and/or software
`configured to proceSS information and perform taskS Such as
`Selecting circuits between nodes 102, and communicating
`instructions to nodes 102 to send traffic to particular links
`104. Server 200 may communicate with one or all of nodes
`102 using network 100. Alternatively, server 200 may be an
`out-of-network server 200 that determines an optimal path
`
`Arista Networks, Inc.
`Ex. 1009, p. 5
`
`

`

`US 2003/0147400 A1
`
`Aug. 7, 2003
`
`Selection, which is then used to provision paths manually.
`Network 100 contemplates any suitable connectivity of
`server 200 to nodes 102 to perform in-band, out-of-band,
`flow-through or other Suitable provisioning.
`0.017. In operation, network 100 communicates packets,
`frames, cells, or other segments of information (generally
`referred to as “packets”) between nodes 102. Depending on
`the type of information, packets may be communicated
`Synchronously, asynchronously, Sporadically, Sequentially,
`randomly or in any other Suitable arrangement. Traffic is
`divided into “service classes” that specify conditions
`required for the traffic to be communicated effectively. Such
`conditions or parameters may include low latency, available
`bit rate (ABR), constant bit rate (CBR), error rate, band
`width guarantees, rate of packet loss, “best effort' (no delay
`guarantees and possible overbooking), or any other Suitable
`measure of network effectiveness, including customized
`measurements for particular types of traffic. For example,
`Voice traffic may require a latency ceiling, Since excessive
`latency impairs the experience of Voice communication. On
`the other hand, the occasional Voice packet may be dropped
`without impairing voice quality. In contrast, data traffic may
`be relatively insensitive to latency, but particular applica
`tions may be quite Sensitive to packet loSS. Since voice and
`data traffic have different requirements to be communicated
`effectively, voice traffic and data traffic would be assigned to
`different Service classes.
`0018 Server 200 determines a path for traffic of a par
`ticular Service class between a Source node 102 and desti
`nation node 102. One technique for path selection first
`assigns traffic of the highest Service class to the shortest
`available path. Once the paths for the highest Service class
`are assigned, the technique assigns lesser Service classes in
`order to the shortest of the remaining network paths. This
`approach may assign all of the traffic of the highest class
`between particular nodes to a single path, which does not
`necessarily result in a balanced traffic load. Furthermore,
`should one of the links on the shortest path fail, the entire
`optimization routine must be re-run and traffic re-assigned.
`Server 200 simultaneously develops an assignment for more
`than one Service class, therefore allowing the resulting path
`assignment to be load balanced and to include redundant
`paths that can be used as backups should particular linkS 104
`fail.
`0019. To simultaneously optimize path selection for ser
`vice classes, server 200 collects multiple demands, each for
`a requested amount of traffic of a particular class between a
`Source node and a destination node. Server 200 also collects
`network topology information, which may be collected
`directly from network 100. Network 100 contemplates any
`suitable technique to allow server 200 to collect demands
`and topology information. Server 200 may also collect
`constraints, representing limits on the path assignments for
`particular types of traffic.
`0020 Server 200 uses the collected information to deter
`mine an assigned path for each demand. Server 200 may
`perform path assignments during initial provisioning and
`may also perform path assignment at the time information is
`collected in response to a change in demands and/or topol
`ogy information. ASSigned paths may be provisioned manu
`ally or automatically using in-band, out-of-band, flow
`through or any other Suitable provisioning techniques.
`
`0021 FIG.2 shows server 200 in more detail. Server 200
`includes an interface 202, a processor 204, and memory 206.
`In a particular embodiment, interface 202 allows server 200
`to communicate with components of network 100 to gather
`topology information and/or demands, and to provision
`network 100 based on optimization determinations. Inter
`face 202 may be any port, real or virtual, logical or physical,
`that allows server 200 to communicate with network 100.
`Interface 202 also contemplates a user interface 202 that
`allows server 200 to communicate with a user. The user may
`enter information using a graphical user interface (GUI) or
`other Suitable input/output hardware and/or Software and
`may receive optimized path assignments from Server 200,
`which may then be implemented in network 100.
`0022 Processor 204 represents a microprocessor, micro
`controller, digital signal processor (DSP) , or any other
`Suitable hardware and/or Software configured for processing
`information. Processor 204 performs all calculations neces
`Sary to provide optimum path Selection, as described below.
`Processor 204 may access information received from inter
`face 202, and may store and retrieve information from
`memory 206.
`0023 Memory 206 may include any memory, volatile or
`non-volatile, local or remote, that Stores information.
`Memory may include magnetic media, optical media, ran
`dom access memory (RAM), read-only memory (ROM),
`CD-ROMs, DVD-ROMs, removable media, or any other
`Suitable form of information Storage. In a particular embodi
`ment, memory 206 stores code 208 executed by processor,
`a set of network constraints 210, information about demands
`212, and information about the topology of network 100.
`0024 Code 208 includes an optimization routine that
`allows optimization of path Selection using data Stored in
`memory 206. In a particular embodiment, code 208 also
`includes instructions for collecting information from net
`work 100 automatically to perform updates of topology
`information 214. Code 208 also contemplates instructions
`for receiving, aggregating and Storing demands. Code 208
`may also include instructions for provisioning, Such as
`instructions for generating a message to components of
`network 100 for flow-through provisioning. The optimiza
`tion algorithm of code 208 is described in greater detail in
`conjunction with FIGS. 3 and 4 below.
`0025 Constraints 210, also known as “policies,” are
`restrictions on types of traffic that may be carried over
`certain links 104 of network 100. For example, a constraint
`210 may include assigning colors (e.g., red, blue, and green)
`to links 104 to indicate their reliability. Such a constraint 210
`may then restrict Service classes that require a high degree
`of reliability to particular links 104. For example, if green
`links 104 were considered to be virtually failure-free, server
`200 may assign traffic of the Service class that requires high
`link reliability to them. Constraints 208 may also be used to
`indicate capacity of linkS 104, restrictions on usage of links
`104, or any other suitable restriction.
`0026 Demands 212 indicate demands for information to
`be communicated over network 100. Demands 212 are
`typically collected from customers and Stored as they
`become available, but demands may also include any Suit
`able specification of traffic requirements, whether calculated
`or entered manually. Demand 212 may include a Source
`node 216 for traffic, a final destination 218 for the traffic, and
`
`Arista Networks, Inc.
`Ex. 1009, p. 6
`
`

`

`US 2003/0147400 A1
`
`Aug. 7, 2003
`
`the service class 220 for the traffic, which may be further
`subdivided by any quality-of-service (QoS) factor or value.
`Demands 212 of a particular Service class may be aggre
`gated among Several requests demanding a particular Service
`class between a particular Source 216 and a particular
`destination 218, Such as multiple customer demands. Thus,
`one demand 212 may represent the Sum of Several individual
`demands.
`0.027 Topology information 214 generally characterizes
`network 100. For example, topology information 214 may
`include node information 222 and link information 224.
`Node information 222 may describe the availability of
`particular nodes 102 as well as particular information about
`a node 102, Such as its Switching capacity, Supported inter
`faces (e.g., optical, electrical, wireless), Supported protocols,
`assigned resources, available resources, physical configura
`tion, or any other information describing the availability of
`node 102 for a particular service class. Link information 224
`includes information about particular linkS 104, including
`type of link 104 (e.g., optical, electrical, wireless), reliability
`of link 104, error rate, total capacity, assigned bandwidth,
`available bandwidth or any other suitable measure of link
`availability. Link information 224 may be used in conjunc
`tion with constraints 210 to determine if a particular link 104
`is appropriate for carrying traffic of a particular Service class.
`0028. In operation, server 200 collects appropriate infor
`mation from a variety of Sources and Stores it in memory
`206. Server may collect information in a variety of ways,
`including receiving entries from a user, receiving messages
`from components of network 100, polling components of
`network 100 periodically, detecting failure alarms for com
`ponents, receiving calculated estimates of customer demand,
`monitoring usage of network 100, or any other suitable
`method of gathering information useful for path assignment.
`0029 Processor 204 provides optimum path selections on
`demand. “On demand” may refer to performing the optimi
`Zation calculation whenever a user indicates a need for the
`information. Alternatively, processor 204 may perform the
`calculation automatically or periodically based on time,
`changes to network topology, updated demands, link failure,
`or any other Suitable condition that may require updated path
`assignments. Server 200 may provide assignment of paths
`directly to network 100, or may provide the information to
`the user who then assigns paths manually in network 100.
`0030) The particular server 200 described is only one of
`many possible embodiments of a device for optimizing path
`selection. Various components of server 200 may be
`replaced, and the functions of components may be distrib
`uted among several components of network 100 or consoli
`dated within particular components without changing the
`overall operation of server 200.
`0.031
`FIG. 3 shows a conceptual illustration of optimi
`zation flow 300. Information in memory 206 includes topol
`ogy information 214, demands 212, and network constraints
`210. Information stored in memory 206 is communicated to
`optimization module 310 which outputs a solution 312
`assigning network paths between nodes 102. The network
`paths in the output describe circuits between particular
`nodes 102.
`0.032
`Optimization module 310 represents any combina
`tion of hardware and/or Software for performing calculations
`
`of network paths from topology information 214, demands
`212, and network constraints 210. Optimization module 310
`may represent software stored as code 208 in memory 206,
`but may also contemplate Separate hardware, Software and/
`or memory components as well. Optimization module 310
`determines an objective function that specifies an optimiza
`tion problem, uses an optimization algorithm to determine a
`Solution to the optimization problem, and determines path
`assignments based on the Solution. The objective function
`may be any mathematical representation of the collected
`information. Optimization module 310 may employ any
`Suitable optimization tools, including constrained integer
`calculations, to obtain Solution 312.
`0033. In a particular embodiment, the objective function
`F takes the form:
`
`0034) where:
`0035) F=the objective function,
`0036 M=the number of links 104 in network 100,
`0037), L=the loading from all path assignments
`to the link between node N, and node N (as shown
`in FIG. 1),
`0.038
`<L>=the average load on all links,
`0039) C=the capacity of the link between node
`N, and node N.
`0040. The first sum of the objective function is a load
`balancing term, representing the deviation between the load
`on any given link and the average load on all links. The
`Second Sum is a capacity constraint, which requires the
`loading on each link to be less than the capacity of the link.
`Although the capacity constraint may take the Simpler form
`(C-L), the capacity constraint here has been expressed in
`the form S=T log T, an “entropy function.” Because the
`entropy function is a way of measuring the disorder in a
`System, minimizing the entropy function as part of F also
`minimizes variations in loading from link to link, thus
`preventing the path assignments from being too random or
`lopsided.
`0041) Demands 212 may be expressed in any appropriate
`mathematical form as minimum bandwidth requirements for
`a particular class between particular nodes. In one embodi
`ment, demands 212 are collected into a demand matrix 322.
`Demand matrix 322 may associate amounts of demand
`between particular nodes with constraints 210 on the type of
`traffic. For example, demand matrix 322 may take the form
`Itil, where t=(t", p'))" with k=1,..., c (c=the number of
`Service classes, 3 in the depicted example), ti-the amount
`of traffic demanded of service class k between node N and
`node N. p'-the constraint information for the type of
`traffic. The respective amounts of traffic represent require
`ments for bandwidth for a particular Service class, which
`may be minimum requirements, maximum requirements,
`average requirements over time, or any other Suitable form
`of bandwidth request. For example, certain classes of traffic
`that are less time-Sensitive may take bandwidth when it
`becomes available rather than requiring a constant level of
`bandwidth. Such requirements may be specified as con
`straints 210.
`
`Arista Networks, Inc.
`Ex. 1009, p. 7
`
`

`

`US 2003/0147400 A1
`
`Aug. 7, 2003
`
`Constraints 210 express mathematical restrictions
`0.042
`on possible Solutions that minimize the objective function.
`Constraints 210 may correspond to particular requirements
`for particular Service classes. For example, Voice traffic
`requires low latency (time of transmission). The constraint
`210 for voice traffic could be expressed as:
`0043 “from all possible paths P. between node N,
`and node N. choose the path P. with min(-
`li"d), where d-the distance of a link Linn
`between nodes N and N, p=the Service class of
`voice traffic, and li"={1 if L is in the path Pi,
`and 0 if L is not in the path P}”
`0044) This constraint 210 minimizes the distance that
`voice traffic must travel, and therefore implicitly lowers the
`latency of the voice traffic. The constraint 210 may also
`include a bandwidth usage limit, such as 70%, to prevent
`excessive congestion from increasing the transmission time
`in a link. In cases where delay is leSS important, the
`constraint 210 might be expressed as a more tolerant con
`dition, Such as:
`inni
`mnp1 ''
`0045 where h is the average number of “hops” (links) in
`a path acroSS all Service classes. This constraint 210 prevents
`traffic of class p from taking a path with a length longer than
`the average, but does not force the traffic to the shortest
`available path.
`0.046
`Constraints 210 may also incorporate information
`in demand matrix 322. For example, each link 104 could be
`assigned a “color mn indicating the link's Suitability for
`carrying particular classes of traffic. To maximize efficient
`use of available link colors, constraint 210 is expressed as:
`0047) “from all available paths P. between node N,
`and node N. choose the path with
`aX (alki"(anxP).
`0.048 where
`mnxp'-1 if n=p', and 0 otherwise)"
`0049 so that the overall number of links matching the
`appropriate color is optimized.
`0050. Obviously, the examples presented are only a small
`Selection of the many possible types of objective functions,
`demand requirements, topology information, and con
`Straints. Numerous additional embodiments using multiple
`Service classes will be apparent to one skilled in the art.
`Consequently, the particular embodiments described should
`be viewed as illustrations rather than exclusive definitions.
`0051 FIG. 3 also shows one example of a solution 312
`to the optimization problem. Solution 312 may be stored in
`memory 206, output to a user using a graphical user inter
`face, printed in hard copy, or otherwise output and/or Stored.
`The notations N, and L. refer respectively to the nodes 102
`and links 104 in network 100 of FIG. 1. Solution 312
`includes Sources 314, destinations 316, service classes 318,
`and paths 320. Solution 312 may be provisioned in a variety
`of ways, including manual provisioning, automated provi
`Sioning by a component of server 200, flow-through provi
`Sioning by Sending messages to nodes 102, or any other
`suitable method of assigning paths in network 100.
`0.052 One notable feature of Solution 312 is that the path
`for the highest Service class need not necessarily be the
`
`shortest path between two nodes 102. For example, traffic of
`Service class 1 between node N, and node N is carried over
`path 320 of link L, link L, and link L, even though link
`L and link L would be the shortest path (i.e., the least
`number of network hops) between node N and node N.
`Furthermore, in the solution 312 shown, less traffic may be
`Sent acroSS link L than link L. This is indicative of load
`balancing, and that even when a shorter path might be
`available, more traffic can go to high capacity linkS 104 So
`that overall each link 104 is using a roughly equal percent
`age of its capacity.
`0053. The depicted embodiment is only one example of
`an optimization flow. Numerous modifications will be appar
`ent to one skilled in the art. For example, optimization flow
`300 could receive additional or different information about
`network 100, and Solution 312 could include additional or
`different information as well. Because of the wide range of
`variations available, the description of optimization flow
`300 should be viewed as illustrative rather than restrictive.
`0054 FIG. 4 is a flow chart 400 illustrating a method for
`optimizing path selection. Server 200 collects demands 212
`from customers at step 402. Server 200 uses the demands to
`populate a demand matrix 322 at step 404.
`0055. At step 406, server 200 collects topology informa
`tion 214 for network 100. Topology information 214 may be
`collected automatically if server 200 is connected to network
`100. Server 200 may include a network management capa
`bility to poll nodes 102 for information about the status of
`nodes 102 and links 104, to determine available resources,
`to receive alarms about component failure, or to perform any
`other useful information gathering techniques in network
`100. In certain embodiments, server 200 detects failures in
`nodes 102 or links 104, and automatically redistributes
`traffic if necessary.
`0056. At step 408, server 200 collects network con
`straints 210. Constraints 210, which may be automatically
`generated or entered by a user, limit the range of acceptable
`path Selections. Constraints 210 may take any appropriate
`form that may be expressed as a mathematical constraint on
`path Selection Solutions.
`0057 Server 200 determines an objective function based
`on the collected information at step 410. The objective
`function is a mathematical representation of network 100
`and constraints 210 on traffic in network 100. The objective
`function specifies a Single optimization problem that can be
`Solved, with the Solutions of that problem being optimal path
`Selections for the Selected Service classes.
`0.058 Server 200 determines a trial solution for the
`optimization problem Specified by the objective function at
`Step 412. A trial Solution may be generated by any Suitable
`method, including using existing Shortest path algorithms. In
`an alternative embodiment, server 200 generates solutions
`randomly, checks the Solutions against constraints 210 on
`the network, and uses any Solutions that meets constraints
`210 as the first trial Solution. In other embodiments, the
`optimization method itself may include a method for deter
`mining the first guess at a Solution.
`0059) Server 200 determines whether the trial solution is
`an optimum Solution to the optimization problem Specified
`by objective function at step 414. If the trial solution does
`not optimize the objective function, server 200 updates trial
`
`Arista Networks, Inc.
`Ex. 1009, p. 8
`
`

`

`US 2003/0147400 A1
`
`Aug. 7, 2003
`
`Solution at Step 416. The trial Solution is updated according
`to rules for the particular optimization method used to bring
`the trial Solution closer to the optimal Solution. Any recur
`Sive or iterative techniques, numerical methods, or other
`optimization methods for determining critical points, Such as
`global minima or maxima or local minima or maxima, may
`be used to bring trial solution closer to optimal solution 312.
`Optimal solutions 312 specifies path 320 for each demand
`212 in demand matrix 322. Such that each demand 212 is
`Satisfied.
`0060 Once optimal solution 312 is determined, server
`200 assigns network paths to node 102 at step 418. Server
`200 may assign paths directly, or alternatively may provide
`path assignments to a user who then updates network paths
`accordingly. Optimal Solution 312 may also include backups
`in case of link failure.
`0061 The described method is only one of many possible
`methods for providing optimized path Selection for multiple
`Service classes. The method and the described variations of
`that method should be taken as illustrative steps rather than
`restrictive Statements. It should be understood that the Steps
`of the described method may be performed concurrently or
`continuously, that particular Steps of the method may be
`performed in a different order, and that certain Steps may be
`added, modified or omitted without changing the overall
`operation of the method.
`0.062 Although the present invention has been described
`with Several embodiments, a myriad of changes, variations,
`alterations, transformations, and modifications may be Sug
`gested to one skilled in the art, and it is intended that the
`present invention encompass Such changes, variations, alter
`ations, transformations, and modifications as fall within the
`Scope of the appended claims.
`
`What is claimed is:
`1. A method for routing traffic in a network, comprising:
`determining topology information for a network compris
`ing a plurality of nodes and a plurality of links between
`the nodes;
`determining a plurality of demands, each demand com
`prising a requested amount of traffic between a Source
`node and a destination node for one of a plurality of
`Service classes;
`determining an objective function using the topology
`information and the demands, and
`using the objective function, determining a Solution that
`Specifies a network path for each demand.
`2. The method of claim 1, wherein the step of determining
`a Solution to the optimization problem comprises:
`determining a trial Solution to the optimization problem;
`determining whether the trial Solution is an optimized
`Solution to the optimization problem; and
`if the trial Solution is not an optimized Solution, updating
`the trial Solution.
`3. The method of claim 1, wherein:
`the objective function further comprises constraints Speci
`fying restrictions on traffic of one or more of the Service
`classes, and
`
`the Solution is further determined based on the con
`Straints.
`4. The method of claim 1, wherein:
`the objective function comprises a load-balancing term;
`and
`the Step of determining a Solution to the optimization
`problem includes load balancing as a factor in the
`determination.
`5. The method of claim 1, wherein:
`the objective function comprises a maximum capacity
`term; and
`the Solution is determined Such that each link is Subject to
`a traffic load less than a capacity of the link.
`6. The method of claim 5, wherein the maximum capacity
`term is weighted by multiplying the maximum capacity term
`by a logarithmic function of the capacity.
`7. The method of claim 6, wherein:
`the demands are used to populate a demand matrix
`comprising a plurality of paired entries, one of the
`entries of each pair comprising a bandwidth require
`ment between the Source node and the destination node
`for one of the Services classes and the other entry
`comprising a constraint on the Service class, and
`the Step of determining a Solution uses the demand matrix.
`8. A Ser