Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 1 of 23 Page ID #:93
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 1 of 23 Page ID #:93
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 2 of 23 Page ID #:94
`Case8=20-CV'00529 Wm“ 1'1 'lllllllllllllllfllllllllfllllfllll'llllllllllfillllllllllfilll
`
`USOO7266079B2
`
`(12) United States Patent
`(10) Patent No.:
`US 7,266,079 B2
`
`Fan
`(45) Date of Patent:
`Sep. 4, 2007
`
`(54) DYNAMIC NETWORK LOAD BALANCING
`OVER HETEROGENEOUS LINK SPEED
`
`EP
`
`0 910 195
`
`4/1999
`
`(75)
`
`Inventor: Kan Frankie Fan, Diamond Bar, CA
`(US)
`
`.
`.
`(73) ASSIgnee: Broadcom Corporation, Irvme, CA
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1127 days.
`
`(21) Appl. No.: 09/897,660
`
`(22)
`
`Filed:
`
`Jul. 2, 2001
`
`(65)
`
`Prior Publication Data
`US 2002/0054567 A1
`May 9, 2002
`
`Related US. Application Data
`
`(60) Provisional application N0~ 60/233338: filed on Sep.
`18: 2000'
`
`(51)
`
`Int. Cl'
`(200601)
`H04L 12/26
`(52) US. Cl.
`....................... 370/230; 370/235; 370/468
`(58) Field of Classification Search ................ 370/230,
`370/2301: 229, 235, 232, 468
`See application file for complete search history.
`References Cited
`
`(56)
`
`US. PATENT DOCUMENTS
`......... 709/239
`6,611,874 B1 *
`8/2003 Denecheau et a1.
`
`6 628 617 B1 *
`9/2003 Karol et al
`370/237
`6,831,893 B1 * 12/2004 Ben Nun et a1.
`370/235
`a
`a
`FOREIGN PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`Zhiro Cao et a1., “Performance of Hashing-Based Schemes for
`Internet Load Balancing,” Infocom 2000, 19th Annual Joint Con-
`ference of the IEEE Computer and Communications Societies,
`Proceedings, IEEE Tel Aviv, Israel Mar. 26-30, 2000, Piscataway,
`NJ, USA, IEEE, US, PP. 332-341.
`*
`. d b
`.
`we
`Y exammer
`Primary Examineriwmg Chan
`Assistant ExamineriRichard Chang
`(74) Attorney, Agent, or Firmisquire, Sanders & Dempsey,
`LLP
`
`(57)
`
`ABSTRACT
`
`A method, apparatus, and computer program product for
`balancing transmission unit
`traffic over network links,
`including disposing transmission units into flows; grouping
`flows into first flow lists, each corresponding to a selected
`network link; determining a traffic metric representative of
`a traffic load on the selected network link; responsive to the
`traffic metric, regrouping flows into second flow lists cor-
`responding to the selected network link,
`the regrouping
`balancing the transmission unit trafiic among the network
`links; and transmitting the respective second flow list over
`the respective selected network link. The invention also can
`include a method for transmitting transmission units through
`a network, mcludmg rece1vmg a transm1551on umt from a
`transmission unit source; classifying the transmission unit
`accordmg to a predetermmed flow characteristlc, selecting a
`preselected network link over which the transmission unit is
`to be transmitted; and transmitting the transmission unit over
`the preselected network link.
`
`EP
`
`0 891 061
`
`1/1999
`
`68 Claims, 9 Drawing Sheets
`
`
`
`
`
`@(W
`V
`31D
`PACKET INTO TRAFFIC
`
`CLASSIFV NETWORK JFLOWS
`
`V
`32°
`DERIVE
`EACH FLOW
`
`TRAFFIC METRICS FOR 1
`
`ORDER FLOWS INTO
`330
`i
`LINK
`TRAFFIC LIST FOR EACH /
`
`
`340
`DETERMINE
`MEI'RICS FOR TRAFFIC
`AGGREGATE TRAFFIC /
`
` LIST FoR EACH LINK
`
`CHARACTERIZE
`SELECTED TRAFFIC
`LIST PARAMETERS
`
`
`360
`CHARACTERIZE
`NETWORK LINKS USING
`
`PARAMETERS
`TRAFFIC LIST J
`I
`BALANCE TRAFFIC
`37D
`FLOW ACCORDING TO
`NETWORK LINKAND
`A66. TRAFFIC METRICS
`CHARACTERIZATIDNS
`
`
`
`
`
`
`35°
`
`—+
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 3 of 23 Page ID #:95
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 3 of 23 Page ID #:95
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 1 0f 9
`
`US 7,266,079 B2
`
`
`
`CLIENTD
`CLIENTF
`CLIENTE
`CLIENTA
`CLIENTC
`CLIENTB
`
`
`
`NETWORKSWITCH
`
`COMMUNICATIONNETWORK
`
`
`
`
`LINK1
`
`106
`
`NETWORK
`
`SERVER
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 4 of 23 Page ID #:96
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 4 of 23 Page ID #:96
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 2 0f 9
`
`US 7,266,079 B2
`
`1000Mbps
`
`SOURCE
`
`225
`
`SERVER
`
`n:
`023
`g2
`45
`D
`
`<C
`
`PACKET
`
`BUFFER
`
`PACKET/
`
`STREAM
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 5 of 23 Page ID #:97
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 5 of 23 Page ID #:97
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 3 0f 9
`
`US 7,266,079 B2
`
`300
`
`CLASSIFY NETWORK
`PACKET INTO TRAFFIC
`FLOWS
`
`DERIVE
`TRAFFIC METRICS FOR
`EACH FLOW
`
`ORDER FLOWS INTO
`TRAFFIC LIST FOR EACH
`LINK
`
`
`
`DETERMINE
`AGGREGATE TRAFFIC
`METRICS FOR TRAFFIC
`LIST FOR EACH LINK
`
`CHARACTERIZE
`SELECTED TRAFFIC
`LIST PARAMETERS
`
`CHARACTERIZE
`NETWORK LINKS USING
`TRAFFIC LIST
`PARAMETERS
`
`BALANCE TRAFFIC
`FLOW ACCORDING TO
`NETWORK LINK AND
`AGG. TRAFFIC METRICS
`CHARACTERIZATIONS
`
`FIG. 3
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 6 of 23 Page ID #:98
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 6 of 23 Page ID #:98
`
`U.S. Patent
`
`eS
`
`4n
`
`m
`
`m.hS
`
`9f
`
`US 7,266,079 B2
`
`59¢>>o._u_
`
`omov
`
`7Nov
`2,ax225:07:25
`
`mEx225:o_n_u_<E.
`
`OEHZE
`
`V65%
`
`:x225:
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 7 of 23 Page ID #:99
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 7 of 23 Page ID #:99
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 5 0f 9
`
`US 7,266,079 B2
`
`8
`Ln
`
`z
`0
`IEDO
`(9 LL <1: -
`i<0$o: _l
`I—
`CC
`
`o
`Q
`LL
`
`TD\—
`Q
`
`+ EE
`
`a
`
`E”
`
`:3.
`\—
`Q
`
`é 2
`
`______________________________________._
`
`< __ D Z
`2 “-
`Q
`fig—J." n: & 6 (.9
`0 n: _I L“
`z |--
`DE
`
`——————————————————————————————————
`
`MO
`
`mw TRAFFIC
`
`LOAD
`
`REGION
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 8 of 23 Page ID #:100
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 8 of 23 Page ID #:100
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 6 0f 9
`
`US 7,266,079 B2
`
`
`
`6101»W
`
`612
`
`613
`
`614
`
`615
`
`611
`
`
`
`6201.m
`
`
`TRAFFIC LIST(LINK n) — LOW FLOW
`630—1» M
`
`TRAFFIC LIST(LINK 1) — HIGH FLOW
`
`621
`
`622
`
`623
`
`TRAFFIC LIST(LINK 2) - NORMAL FLOW
`
`631
`
`632
`
`-
`
` 600
`
` 611
`610-1»We a
`
`612
`
`613
`
`614
`
`TRAFFIC LIST(LINK 1) - NORMAL FLOW
`
`
`
`
`
`621
`
`622
`
`623
`
`620—1»m
`
`TRAFFIC LIST(LINK 2) — NORMAL FLOW
`
`,’
`
`,I
`
`650
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 9 of 23 Page ID #:101
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 9 of 23 Page ID #:101
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 7 0f 9
`
`US 7,266,079 B2
`
`INITIALIZE accT(i,t) = 0
`
`VISIT NEXT SELECTED TRAFFIC
`FLOW IN TRAFFIC LIST
`
`SUM FLOW TRAFFIC METRICS IN
`
`LIST TO GET LINK aCCT(I',t)
`
`COMPARE LINK aCCT(i,l‘) TO
`Adm/3030
`
`IS accT(i,t) >
`M(t) + 00‘) ?
`
`BALANCING
`
`NVISITED FLOWS
`FOR LINK i?
`
`MOVE UNVISITED
`FLOWS TO LOW FLOW
`
`MOVE ALL FLOWS TO
`HIGHER SPEED LOW
`FLOW LINK
`
`PROCEED TO
`NEXT LIST/LINK IN
`FLOW TABLE
`
`ERE ALL HIG
`FLOW LINKS
`V'S'TED?
`
`DYNAMIC
`LOAD
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 10 of 23 Page ID #:102
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 10 of 23 Page ID #:102
`
`U.S. Patent
`
`Sep. 4, 2007
`
`Sheet 8 0f 9
`
`US 7,266,079 B2
`
`HASHINGPROCESS
`
`FIG.8
`
`,_0-
`
`>-'
`L'-
`CD
`2
`.4
`o
`
`t
`25
`cox
`20
`§<
`
`UPDATE
`
`METRICS
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 11 of 23 Page ID #:103
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 11 of 23 Page ID #:103
`
`U.S. Patent
`
`D...&
`
`9mmm4,
`
`2B970,662.}7SU
`
`mgk1.
`
`mjmfi25d..........._5&8...w
`
`
`mm>>o-_u__T--Neso-E0x2:
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 12 of 23 Page ID #:104
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 12 of 23 Page ID #:104
`
`US 7,266,079 B2
`
`1
`DYNAMIC NETWORK LOAD BALANCING
`OVER HETEROGENEOUS LINK SPEED
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This patent application claims the benefit of the filing date
`of US. Provisional Patent Application No. 60/233,338, filed
`Sep.
`18, 2000, and entitled “DYNAMIC NETWORK
`LOAD BALANCING OVER HETEROGENEOUS LINK
`
`SPEED,” the entire contents of which are hereby expressly
`incorporated by reference.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates to communications appara-
`tus and methods, particularly to computer networking appa-
`ratus and methods, and more particularly to computer net-
`working apparatus and methods for balancing data flow
`therethrough.
`2. Description of the Relevant Art
`A common problem in communication networks is main-
`taining efficient utilization of network resources, particularly
`with regard to bandwidth, so that data traffic is efficiently
`distributed over the available links between sources and
`
`destinations. Prior art solutions include apparatus and meth-
`ods that balance data traffic over homogeneous (same-speed)
`links between heterogeneous or homogeneous computing
`platforms (servers, clients, etc.). Increasingly, high-perfor-
`mance computing platforms communicate with other com-
`puters, routers, switches, and the like, using multiple links
`which, for a variety of reasons, may operate at disparate link
`speeds. For example, a server may communicate with other
`devices using a combination of new and legacy network
`cards, thus producing a heterogeneous-link-speed environ-
`ment; or adverse network conditions may degrade the per-
`formance of one or more links, effectively presenting a
`heterogeneous-link-speed environment to the server and its
`link partner(s). What is needed is a method to dynamically
`balance transmission unit traffic in a heterogeneous-link-
`speed environment, and an apparatus and computer program
`product therefor.
`
`SUMMARY OF THE INVENTION
`
`The present invention satisfies the above needs by pro-
`viding a method for balancing transmission unit traffic over
`heterogeneous speed network links,
`including disposing
`transmission units into flows; grouping flows into first flow
`lists corresponding to a selected network link; determining
`a traffic metric representative of a traffic load on the selected
`network link; responsive to the traffic metric, regrouping
`flows into second flow lists corresponding to the selected
`network link, the regrouping balancing the transmission unit
`traffic among the network links; and transmitting the respec-
`tive second flow list over the respective selected network
`link using a predetermined link-layer transmission protocol.
`The transmission units can include source information,
`destination information, and a combination thereof, and the
`flows are generated by characterizing each of the transmis-
`sion units according to the source information, the destina-
`tion information, or a combination thereof. Each of the
`transmission units can be a packet, a frame, a cell, or a
`combination thereof. It is desirable that the flow lists be
`
`decreasing-size-ordered linked lists. The predetermined
`link-layer transmission protocol can communicate the trans-
`
`2
`
`mission unit traffic over the network links in cooperation
`with a network-layer protocol; and the network-layer pro-
`tocol cooperates with a transport-layer protocol to commu-
`nicate the transmission unit traffic across the network links.
`
`Either the network-layer protocol or the transport-layer
`protocol can be a connectionless protocol or a connection-
`based protocol.
`The predetermined link-layer transmission protocol is one
`of an IEEE STD. 802 protocol, an ATM protocol, an FDDI
`protocol, an X.25 protocol, an ISDN protocol, a CDPD
`protocol, and a Frame Relay protocol. The network-layer
`protocol can be an intemet protocol (IP), a Switched Multi-
`megabit Data Service protocol (SMDS), a general packet
`radio service (GPRS), a Message Transfer Part Level 3
`protocol (MTP3), a an intemet packet exchange protocol
`(IPX), an X.25/X.75 protocol, a connectionless network
`protocol (CLNP), internet datagram protocol (IDP), a data-
`gram delivery protocol (DDP), a Xerox Network Systems
`protocol OiNS), or a combination thereof. The transport-
`layer protocol can be a transmission control protocol (TCP),
`a user datagram protocol (UDP), a NetBIOS protocol, an
`H.323 protocol, a GSM/CDMA protocol, a Stream Control
`Transmission Protocol (SCTP), or a combination thereof.
`The Traffic Metric representative of a traffic load on the
`selected network link characterized by:
`
`Naif» I)*Ki +N51(fxa 1)
`DI
`
`2
`
`T
`+ 1(fxal
`
`—l
`
`)
`
`T;(J’X,I)=
`
`where
`
`Ti(fx,t) is a Traffic Metric of Flow f,C in selected link i,
`sampled at time t,
`NLi,(fX,t) is the number of transmission units of Flow f,C in
`selected link i, with a transmission unit size greater than
`or equal
`to a preselected size threshold, observed
`between time t—l and time t,
`NSZ.(fX,t) is the number of transmission units of Flow f,C in
`selected link i, with a transmission unit size less than a
`preselected size threshold, observed between sampling
`time t—l and time t,
`Ki,C is a predetermined link load factor for Flow x in link
`i having a value in a range between about 4.0 and about
`5.0, and
`At is the inter-sampling time, measured as the interval
`between time t—l and time t, in selected link i.
`
`Also, an Aggregate Traffic Metric can be employed, which
`can be characterized by
`
`TA(i, r) = 2 TM, 0
`
`where
`
`TA(i,t) is an Aggregate Traffic Metric for selected link i,
`and
`
`Tl.(fx,t) is the Traffic Metric of Flow f,C in link i, sampled
`at time t.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Furthermore, the Aggregate Traffic Metric can be a Scaled
`Aggregate Traffic Metric characterized by
`
`STA (i, z):TA (i, z)*S(z', z)
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 13 of 23 Page ID #:105
`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 13 of 23 Page ID #:105
`
`where
`
`3
`
`US 7,266,079 B2
`
`4
`
`nique, such as the one mentioned above. The method also
`can include monitoring the operation of a plurality of
`preselected network links, and re-assigning the predeter-
`mined flow characteristic from a first preselected network
`link to a second preselected network link, if the first prese-
`lected network link operationally fails.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other features, aspects and advantages of the
`present invention will be more fully understood when con-
`sidered with respect to the following detailed description,
`appended claims and accompanying drawings, wherein:
`FIG. 1 is a block diagram of a communication network in
`which the present invention can reside;
`FIG. 2 is a block diagram of a communication server in
`according to an embodiment of the present invention;
`FIG. 3 is a flow diagram of a dynamic load balancing
`method according to an embodiment of the present inven-
`tion;
`FIG. 4 is an illustration of a Flow Table having Flow Lists
`within the context of the invention herein;
`FIG. 5 is a diagrammatic representation of flow classifi-
`cation within the context of the invention herein;
`FIG. 6A is a block diagram illustration of a Flow Table
`having Flow Lists therein, according to the present inven-
`tion;
`FIG. 6B is a block diagram illustration of a Flow Table
`having Flow Lists with re-assigned Flows therein, according
`to the present invention;
`FIG. 7 is a flow diagram of another aspect of a dynamic
`load balancing technique according to the present invention;
`FIG. 8 is a diagrammatic representation of another
`embodiment of the present invention; and
`FIG. 9 is a block diagram representation of a Flow Table
`having Flow Lists with re-assigned Flows therein, according
`to another aspect of the present invention.
`
`DESCRIPTION OF THE EMBODIMENTS
`
`The present invention is oriented to a flow-based method,
`apparatus, and computer program product for dynamically
`balancing transmission unit loads over heterogeneous-speed
`links between two devices in a communication network. A
`
`flow is a sequence of transmission units transmitted from a
`particular source to a particular destination, using unicast,
`multicast, or broadcast techniques. As used herein, a trans-
`mission unit is an ordered sequence of data bits, including,
`without limitation, packets, frames, and cells. Transmission
`units typically are transmitted through a communication
`network using one or more protocols arranged in protocol
`layers, similar to the international standard of a seven-layer
`Reference Model for Open System Interconnection (OSI
`model, ISO STD. 7498), which standard is herein incorpo-
`rated by reference in its entirety. In general, a transmission
`unit includes data, and communication-related information
`prepended and appended to the data. The communication-
`related information can include network, routing, control,
`priority, and state information, synchronization sequences,
`source and destination addresses, protocol-specific informa-
`tion, as well as error-correction/checking sequences, data-
`length information, and a potential myriad of other bit
`sequences used to facilitate the transmission of data across
`a communication network. The term “data” includes all
`
`forms of digital information, including without limitation,
`data, text, voice, video, graphics, and the like.
`
`the Scaled Aggregated Traffic Metrics
`is
`STA(i,t)
`observed at time t for network link i,
`TA(i,t) is the Trafiic Metric observed at time t for network
`link i, and
`S(i,t) is a preselected scaling factor for network link i at
`time t.
`
`5
`
`The scaled value can be used to determine a Link Group
`Arithmetic Mean characterized by
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`where
`
`is the Link Group Arithmetic Mean of Scaled
`M(t)
`Aggregated Traffic Metrics summed over all network
`links i,
`the Scaled Aggregated Traffic Metrics
`is
`STA(i,t)
`observed at time t for network link i, and
`n is the number of active network links.
`
`The aforementioned Link Group Arithmetic Mean and the
`Scaled Aggregated Trafiic Metric can be used to determine
`a Link Group Absolute Deviation characterized by
`
`|STA(i, I) — M(t)|
`
`n 2
`
`D(t) = ‘:1
`
`where
`
`D(t) is the Link Group Absolute Deviation of the Scaled
`Aggregated Traffic Metrics summed over all network
`links i,
`STA(i,t) is the Scaled Aggregated Traffic Metric observed
`at time t for network link i,
`M(t) is the Link Group Arithmetic Mean of the Scaled
`Aggregated Traffic Metrics summed over all network
`links i, and
`n is the number of active network links.
`
`thus is possible to classify a
`it
`With this information,
`network link according to its relative load:
`(I) a HIGH trafiic load on link i can be characterized by
`STA(i,t) §M(t)+D(t),
`(2) a LOW traffic load on link i can be characterized by
`STA(i,t)<M(t)—D(t), and
`(3) a NORMAL traffic load on link i can be characterized
`by M(t)+D(t)>STA(i,t) §M(t)—D(t).
`When a preselected link having a HIGH traffic load is
`detected preselected flow from a first flow list corresponding
`to the HIGH traffic load are re-assigned to a second flow list,
`preferably corresponding to a second preselected link having
`a LOW traffic load.
`
`The present invention also includes a method for trans-
`mitting transmission units through a network,
`including
`receiving a transmission unit from a transmission unit
`source; classifying the transmission unit according to a
`predetermined flow characteristic; selecting a preselected
`network link over which the transmission unit
`is to be
`
`transmitted; and transmitting the transmission unit over the
`preselected network link. The preselected network link can
`be selected according to the predetermined flow character-
`istic using a predetermined dynamic load balancing tech-
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 14 of 23 Page ID #:106
`Case 8:20-cv-00529 Document 1—1 Filed 03/13/20 Page 14 of 23 Page ID #:106
`
`US 7,266,079 B2
`
`5
`For the purposes of illustrating embodiments of the
`present invention, three exemplary protocol layers of the
`OSI model hierarchy will be described: the link layer (Layer
`Two), the network layer (Layer Three), and the transport
`layer (Layer Four). A skilled artisan would realize that there
`is no bright-line distinction between these layers, and that
`the functionality of one layer often overlaps with the func-
`tionality of an adjacent layer, particularly as the nature of the
`reference model employed varies. Furthermore, a link-layer
`protocol can encompass functionality extending well into
`the physical layer (Layer One) and, in the context of the
`present invention, references to link layer, or Layer Two,
`protocols will also be considered to include Layer One
`where appropriate.
`Exemplary Layer Two protocols can include, without
`limitation, an IEEE STD. 802-1990 protocol, an ATM pro-
`tocol, an FDDI protocol, an X.25 protocol, an ISDN proto-
`col, a CDPD protocol, a Frame Relay protocol, and a
`combination thereof. IEEE STD. 802-related protocols are
`inclusive of protocols such as IEEE STD. 802.3 (CSMA-
`CD/Ethernet), IEEE STD. 802.4 (Token Bus), IEEE STD.
`802.5 (Token Ring), IEEE STD. 802.11 (Wireless LAN),
`IEEE STD. 802.15 (Wireless Personal LAN) and IEEE
`STD. 802.16 (Broadband Wireless Access). Exemplary
`Layer Three (network layer) protocols can include, without
`limitation, connection-oriented and connectionless protocols
`such as an intemet protocol (IP), a Switched Multi-megabit
`Data Service protocol
`(SMDS), a general packet radio
`service (GPRS), a Message Transfer Part Level 3 protocol
`(MTP3), a an intemet packet exchange protocol (IPX), an
`X.25/X.75 protocol, a connectionless network protocol
`(CLNP), intemet datagram protocol (IDP), a datagram deliv-
`ery protocol (DDP), a Xerox Network Systems protocol
`(XNS), and a combination thereof. Exemplary Layer Four
`(transport layer) protocols can include, without limitation,
`connection-oriented and connectionless protocols such as a
`transmission control protocol (TCP), a user datagram pro-
`tocol (UDP), a NetBIOS protocol, an H.323 protocol, a
`GSM/CDMA protocol, a Stream Control Transmission Pro-
`tocol (SCTP), and a combination thereof. All of the stan-
`dards representative of the aforementioned protocols are
`hereby incorporated by reference herein in their entireties.
`A particular source device can be identified by its IP
`(intemet protocol) address, and a port number. The particu-
`lar port number at the source device is identified by either a
`port number which is specific to a particular process, or by
`a standard port number for the particular transmission pro-
`tocol type. For example, a standard port number for the TCP
`protocol type is 6 and a standard port number for the UDP
`protocol type is 17. Other protocols which may have stan-
`dard port numbers include the FTP protocol, the TELNET
`protocol, an internet telephone protocol, or an internet video
`protocol; these protocols are known in the art of networking.
`Similarly, the particular destination device is identified by its
`IP address; the particular port number at the destination
`device is identified by either a port number which is specific
`to a particular process, or a standard port number for the
`particular transmission protocol type.
`Flows can be classified using a variety of characteristics,
`including source address, destination address, or both. Other
`characteristics of a particular transmission unit, such as
`priority, protocol type, control data, and the like may be
`used. Typically, in a communication network, a transaction
`between devices involves bidirectional flows, e.g., a device
`responds to a received sequence of transmission units from
`a sender by transmitting other transmission units to the
`sender. With regard to the present invention, however, it is
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`desirable to analyze and balance unidirectional flows, e.g.,
`flows being transmitted by a server, although bidirectional
`flow balancing may be effected under the inventive prin-
`ciples herein.
`In an exemplary IP-oriented flow, it is desirable that all
`packets belonging to the same flow bear the same source
`address, destination address, and priority. Similarly, in an
`exemplary TCP-oriented flow, it is desirable that all packets
`belonging to the same flow bear the same source port and/or
`destination port, and priority.
`For the purposes of illustration, the present invention is
`described within the context of unidirectional flows ema-
`
`nating, for example, from a device employing multiple,
`heterogeneous-speed links in an environment defined by
`IEEE STD. 802.3, 2000 Ed., which standard is hereby
`incorporated herein in its entirety. Hereinafter, “Standard
`Ethernet” will describe 10 Mbps service under IEEE STD.
`802.3,“Fast Ethernet” for 100 Mbps service, and “Gigabit
`Ethernet” for 1000 Mbps service.
`In the communication network 100 of FIG. 1, network
`server 105 communicates, via network switch 110, with
`multiple clients 120-125. Server 105 is coupled with switch
`110 using, for example, 11 communication links, with each
`link 106, 107, 108 being configured to transmit data at
`disparate link speeds. For example,
`link 106 may be a
`Standard Ethernet link, link 107 may be a Fast Ethernet link,
`and link 108 may be a Gigabit Ethernet link. The invention
`herein provides dynamic flow balancing of communication
`traffic over heterogeneous-speed links 106, 107, 108 such
`that each active link bears a desirable load, generally com-
`mensurate with the link’s physical transmission character-
`istics.
`
`FIG. 2 illustrates a simplified server 200 having packet
`source 210 coupled with network 220 through load balancer
`225, using network interface card (NIC) A 230, NIC B 240,
`and NIC C 250. Server 200 also can employ packet buffer
`215 interposed between source 210 and load balancer 225.
`Although three NICs are shown in FIG. 2, a modern server
`can employ an arbitrary number of network interfaces,
`subject to resource constraints. In this example, NIC A can
`be a 1000 Mbps NIC, with Link A being a Gigabit Ethernet
`link; NIC B can be a 100 Mbps NIC, with Link B being a
`Fast Ethernet link; and NIC C can be a 10 Mbps NIC, with
`Link C 255 being a standard Ethernet link. Because each
`NIC and associated link can provide differing bandwidth
`capacities when active, each will exhibit differing traffic
`handling characteristics, potentially leading to overutiliza-
`tion of one or more links, while others are underutilized.
`When used with the present invention, links A, B, and C can
`be a variety of links of arbitrary capacities, and potentially
`have heterogeneous link speeds, and not merely the three
`types of links illustrated. The present invention also may be
`used with homogeneous speed links as well. Given its
`configuration, Link A can transmit transmission units at a
`rate approximately two orders of magnitude greater than
`transmission rate of Link C. Link A can transmit transmis-
`
`sion units at a rate approximately one order of magnitude
`greater than transmission rate of Link B. Similarly, Link B
`can transmit transmission units at a rate approximately two
`orders of magnitude greater than transmission rate of Link
`C. A corollary to Link C having lower throughput than either
`Link A, or Link B, is having a longer transmission time than
`either Link A, or Link B, for a given transmission unit size.
`Thus, the impact of a larger transmission unit on the slowest
`link can be disproportionate to the same transmission unit’s
`impact on the highest-capacity link in a system. Accord-
`ingly, it is desirable to take into consideration factors other
`
`

`

`Case 8:20-cv-00529 Document 1-1 Filed 03/13/20 Page 15 of 23 Page ID #:107
`Case 8:20-cv-00529 Document 1—1 Filed 03/13/20 Page 15 of 23 Page ID #:107
`
`US 7,266,079 B2
`
`7
`than raw link speed, such as time-for-transmission, when
`balancing transmission unit traffic among the several links in
`a communication system. Because the transmission capacity
`on a given link can vary over time due to conditions of the
`network to which a link is coupled, the physical environment
`of the link, and the state of the NIC, it is desirable to provide
`adaptive, dynamic load balancing responsive to sensed
`conditions, and an aspect of the present
`invention can
`include such dynamic load balancing. The present invention
`also can provide desirable automatic failover among the 10
`multiple NICs disposed within a server, thereby maintaining
`transmission unit transmission in the face of one or more
`
`5
`
`link failures, and affording fault-tolerance in addition to
`dynamic load balancing.
`FIG. 3 illustrates one embodiment of method 300 for
`
`15
`
`effecting dynamic load balancing of heterogeneous-speed
`links in a communication network. Solely for the sake of
`illustration,
`transmission units are described in terms of
`packets, although other forms of transmission units, includ-
`ing without limitation, cells, frames, and combinations of 20
`packets, cells, and frames may be used, as well as any
`sequence of data bits intended to convey information.
`In general, method 300 includes classifying a received
`network transmission unit (e.g., a packet) into a traffic flow,
`operation 310; deriving metrics, such as traffic metrics, for 25
`selected flows, operation 320; and ordering flows into a
`link-specific traffic list, operation 330. It is desirable that
`metrics be derived for each flow, that the traffic lists so
`created be ordered, for example, by flow size, and that the
`traffic lists be linked lists. Once flows have been thus 30
`
`it further is desirable to determine aggregated
`arranged,
`metrics for a selected flow list related to a particular link,
`operation 340, and to derive preselected link group charac-
`teristics of the group of flows represented in the flow list for
`a selected link, operation 350. The utilization of a selected 35
`link can then be determined using the preselected link group
`characteristics, operation 360. For example, the utilization
`of a link may be HIGH, NORMAL, or LOW relative to the
`link’s inherent transmission capacity, and to other links.
`With link utilization thus determined, it then is desirable to 40
`balance the traffic flow according to aggregated traffic met-
`rics, or the associated network link characterizations, or
`both, operation 370. For example, a particular flow may be
`re-assigned from a first link having HIGH utilization, or
`traffic, to a second link having LOW utilization, or traffic, 45
`responsive to the aforementioned metrics and/or link char-
`acterizations.
`
`Exemplary techniques for implementing each of the
`operations of method 300 follow forthwith.
`Determine Traffic Metric for Each Flow in Each Link.
`
`In one embodiment of the present invention, it is desirable
`to determine a metric of a flow f,C in a selected link i, which
`in this case is a traffic-related metric according to the
`equation:
`
`Wolf» I))* Ki + Naif» 1)
`Ar
`
`2
`
`T-
`+ 1(fxal
`
`—1
`
`)
`
`TM, 0 =
`
`8
`NSZ.(fX,t) is the number of packets of Flow f,C in link i, with
`a size less than a preselected size threshold, observed
`between sampling time t—1 and t;
`Ki,C is a predetermined link load factor; and
`At is the inter-sampling time, measured between the time
`sample t—1 and sample t are taken in link i.
`
`Empirically, a suitable value for link loading factor, Km, can
`be between about 1.0 and about 10.0, although network
`conditions, components, and other network architectural and
`operational
`factors, may warrant other values.
`In one
`embodiment of the present invention, the link loading factor,
`Km,
`is desired to be a constant with a desired range of
`between about 4.0 and about 5.0. Additionally, a suitable
`size for the aforementioned preselected size threshold is
`about
`1 kilobyte (1,024 bytes), although different values
`may be selected to accommodate different network condi-
`tions, components, and other network architectural and
`operational factors.
`Order Flows in Each Link
`
`FIG. 4 illustrates a Flow Table, T], 400, here composed of
`three Traffic Flow Lists 401, 402, 403, each corresponding
`to a respective selected link i (where i:1 .
`.
`. 11 links). Traffic
`Flow List T1 401, corresponding to link 1, includes infor-
`mation corresponding to Flow fl 401a, Flow f2 401b, and
`Flow f3 4010; Traffic Flow List T2 402, corresponding to link
`2, includes information corresponding to Flow f4 402a, Flow
`f5 402b, and Flow f6 4020; and Traffic Flow List Tn 403,
`corresponding to link 11, includes information corresponding
`to Flow f7, Flow f8, and Flow f9. It is desirable that each
`Traffic Flow List, Ti, be constructed as a linked list.
`Although Flow Table 400 is symmetric, there is no require-
`ment for symmetry in Table 400 or in any list 401-403 in
`Table 400. Also, Flow Table 400 may include information
`for a large number of Flows (e.g., on the order of 104 flows),
`which Flows are distributed according to the link/network
`conditions. It is desirable that each Flow entry e.g., entry
`401a, 401b, 4010, in a selected list, e.g., Traffic Flow List
`401, be ordered by traffic metric value, associated with
`sample time t. For example,
`in one embodiment,
`it
`is
`desirable to order traffic flows by descending traffic metric
`value:
`
`Tim, 02mm;
`
`E@11)3T(13,l); and
`
`201103001)-
`
`Although other orderings may be effected, descending met-
`ric size order permits adjustments of potentially finer granu-
`larity to the balance of the traffic load.
`
`