# US 11,451,482 B2 · Bin packing of flows in a dynamic bandwidth underlay > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,451,482 B2 - Document ID: US11451482B2 - Status: Granted - Kind: B2 - Application number: 17/110,445 - Filed: 2020-12-03 - Published: 2021-03-25 - Granted: 2022-09-20 - Earliest claimed: 2018-03-09 - Assignees: Cisco Technology, Inc. - Applicants: Cisco Technology, Inc. - Inventors: Mark Ross Mitchiner; Dana Lynn Blair - Web page: https://patentgrep.com/patent/US11451482B2 ## CPC - H04L 47/125: by balancing the load, e.g. traffic engineering - H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS - H04L 45/38: {Flow based routing} - H04L 47/805: {QOS or priority aware} - H04W 28/0268: {using specific QoS parameters for wireless networks, e.g. QoS class identifier [QCI] or guaranteed bit rate [GBR] (negotiating SLA or negotiating QoS H04W28/24)} - H04W 28/10: Flow control {between communication endpoints} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) ## Abstract A method including: receiving a flow; for each interface in the plurality of interfaces, determining the preference of the interface for the flow; when only a single interface has a preference for the flow, assigning the flow to that single interface; when multiple interfaces having a preference for the flow have comparable headroom, assigning the flow to the interface of the multiple interfaces with the fewest flows currently assigned to it; and when multiple interfaces having a preference for the flow do not have comparable headroom, assigning the flow to the interface within the multiple interfaces having a preference for the interface that has the greatest headroom. ## Claims ### Claim 1 A method of assigning a flow to one of a plurality of interfaces, the method comprising: assigning, by a processor, a flow to an interface of a plurality of interfaces based on a size of the flow, a Differentiated Service Code Point (DSCP) value of the flow, a preference of the interface, and an available headroom of the interface; and when a new interface comes up, searching, by the processor, through a plurality of flows assigned to the plurality of interfaces and moving at least one flow from at least one of the plurality of interfaces to the new interface based on a flow bandwidth of the at least one flow and the DSCP value of the at least one flow. ### Claim 2 (depends on 1) The method of claim 1, wherein assigning the flow to the interface of the plurality of interfaces comprises: receiving, at the processor, the flow having a flow bandwidth; determining, by the processor, the DSCP value of the flow; determining, by the processor, that the plurality of interfaces have available headroom to process the flow based on the flow bandwidth; determining, by the processor for each interface in the plurality of interfaces, the preference for the flow based on the DSCP value of the flow; and assigning, by the processor, the flow to the interface of the plurality of interfaces based on the preference for the flow. ### Claim 3 (depends on 2) The method of claim 2, wherein assigning the flow to the interface of the plurality of interfaces based on the preference for the flow comprises: assigning, by the processor, when only a single interface has the preference for the flow, the flow to the single interface. ### Claim 4 (depends on 2) The method of claim 2, wherein assigning the flow to the interface of the plurality of interfaces based on the preference for the flow comprises: assigning, by the processor, when multiple interfaces of the plurality of interfaces having the preference for the flow have a comparable available headroom, the flow to another interface of the multiple interfaces with the fewest flows currently assigned to it. ### Claim 5 (depends on 2) The method of claim 2, wherein assigning the flow to the interface of the plurality of interfaces based on the preference for the flow comprises: assigning, by the processor, when multiple interfaces of the plurality of interfaces having the preference for the flow do not have a comparable headroom, the flow to the one interface within the multiple interfaces having the preference for the one interface that has the greatest headroom. ### Claim 6 (depends on 5) The method of claim 5, further comprising moving, by the processor, the at least one flow in order to minimize a difference in the available headroom between the plurality of interfaces and the new interface. ### Claim 7 (depends on 1) The method of claim 1, further comprising shrinking, when the available headroom of the interface in the plurality of interfaces becomes negative, by the processor, flow bandwidths of flows assigned to the interface so that the headroom becomes greater than or equal to zero. ### Claim 8 (depends on 1) The method of claim 1, further comprising moving, by the processor, when a first interface of the plurality of interfaces goes down, flows from the first interface that went down to other interfaces in the plurality of interfaces based on flow bandwidths of the flows and DSCP values of the flows. ### Claim 9 (depends on 1) The method of claim 1, further comprising swapping, by the processor, when a first interface of the plurality of interfaces has an increase in an available bandwidth, a first flow from the first interface of the plurality of interfaces with a second flow in a second interface of the plurality of interfaces in order to minimize a difference in the available headroom between the first interface of the plurality of interfaces and the interface second of the plurality of interfaces. ### Claim 10 (depends on 1) The method of claim 1, further comprising, when a first interface of the plurality of interfaces has a decrease in an available bandwidth, moving, by the processor, at least one flow from the first interface to a second interface of the plurality of interfaces based on the DSCP value of at least one flow. ### Claim 11 An apparatus comprising: a memory; and a processor coupled to the memory, the processor being configured to; assign a flow to an interface of a plurality of interfaces based on a size of the flow, a Differentiated Service Code Point (DSCP) value of the flow, a preference of the interface, and an available headroom of the interface, and shrink, when the available headroom of the interface in the plurality of interfaces becomes negative, flow bandwidths of flows assigned to the interface so that the headroom becomes greater than or equal to zero. ### Claim 12 (depends on 11) The apparatus of claim 11, wherein the processor being operative to assign the flow to the interface of the plurality of interfaces comprises the processor being operative to: receive the flow having a flow bandwidth; determine the DSCP value of the flow; determine that the plurality of interfaces have available headroom to process the flow based on the flow bandwidth; determine, for each interface in the plurality of interfaces, the preference for the flow based on the DSCP value of the flow; and assign the flow to a interface of the plurality of interfaces based on the preference for the flow. ### Claim 13 (depends on 12) The apparatus of claim 12, wherein the processor being operative to assign the flow to the interface of the plurality of interfaces based on the preference for the flow comprises the processor being operative to: assign, when only a single interface has the preference for the flow, the flow to the single interface. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein the processor being operative to assign the flow to the interface of the plurality of interfaces based on the preference for the flow comprises the processor being operative to: assign, when multiple interfaces of the plurality of interfaces having the preference for the flow have a comparable available headroom, the flow to the one interface of the multiple interfaces with the fewest flows currently assigned to it. ### Claim 15 (depends on 12) The apparatus of claim 12, wherein the processor being operative to assign the flow to the interface of the plurality of interfaces based on the preference for the flow comprises the processor being operative to: assign when multiple interfaces of the plurality of interfaces having the preference for the flow do not have a comparable headroom, the flow to the one interface within the multiple interfaces having the preference for the one interface that has the greatest headroom. ### Claim 16 A non-transitory computer-readable medium that stores a set of instructions which when executed by a processor perform a method comprising: assigning, by a processor, a flow to an interface of a plurality of interfaces based on a size of the flow, a Differentiated Service Code Point (DSCP) value of the flow, a preference of the interface, and an available headroom of the interface, wherein assigning the flow to the interface of the plurality of interfaces comprises: receiving, at the processor, the flow having a flow bandwidth; determining, by the processor, the DSCP value of the flow; determining, by the processor, that the plurality of interfaces have available headroom to process the flow based on the flow bandwidth; determining, by the processor for each interface in the plurality of interfaces, the preference for the flow based on the DSCP value of the flow; and assigning, by the processor, the flow to the interface of the plurality of interfaces based on the preference for the flow. ### Claim 17 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein assigning the flow to the interface of the plurality of interfaces based on the preference for the flow comprises: assigning, by the processor, when only a single interface has the preference for the flow, the flow to the single interface.