# US 10,454,839 B1 · Deadlock avoidance in leaf-spine networks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,454,839 B1 - Document ID: US10454839B1 - Status: Granted - Kind: B1 - Application number: 15/979,865 - Filed: 2018-05-15 - Granted: 2019-10-22 - Earliest claimed: 2018-05-15 - Assignees: Cisco Technology, Inc. - Applicants: Cisco Technology, Inc. - Inventors: Liangi Lin; Thomas J. Edsall; Ayan Banerjee - Web page: https://patentgrep.com/patent/US10454839B1 ## CPC - H04L 43/0882: Utilisation of link capacity - H04L 12/44: Star or tree networks - H04L 12/462: {LAN interconnection over a bridge based backbone} - H04L 43/16: Threshold monitoring - H04L 45/18: Loop-free operations - H04L 45/28: using route fault recovery - H04L 45/48: Routing tree calculation - H04L 47/2425: for supporting services specification, e.g. SLA - H04L 47/2475: for supporting traffic characterised by the type of applications - H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes - H04L 47/32: by discarding or delaying data units, e.g. packets or frames - H04L 47/6275: based on priority - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Techniques for implementing deadlock avoidance in a leaf-spine network are described. In one embodiment, a method includes monitoring traffic of a plurality of packets at a leaf switch in a network having a leaf-spine topology. The method includes marking a packet with an identifier associated with an inbound uplink port of the leaf switch when the packet is received from one of a first spine switch and a second spine switch. The method includes detecting a valley routing condition upon determining that the packet marked with the identifier is being routed to an outbound uplink port of the leaf switch to be transmitted to the first spine switch or the second spine switch. Upon detecting the valley routing condition, the method includes dropping packets associated with a no-drop class of service when a packet buffer of the inbound uplink port reaches a predetermined threshold. ## Claims ### Claim 1 A method comprising: monitoring traffic of a plurality of packets at a leaf switch in a network having a leaf-spine topology, the network including a first spine switch connected to the leaf switch and a second spine switch connected to the leaf switch; marking a packet of the plurality of packets with an identifier associated with an inbound uplink port of the leaf switch when the packet is received from one of the first spine switch and the second spine switch; detecting a valley routing condition in the network upon determining, by the leaf switch, that the packet marked with the identifier associated with the inbound uplink port of the leaf switch is being routed to an outbound uplink port of the leaf switch to be transmitted to one of the first spine switch and the second spine switch; and upon detecting the valley routing condition in the network, dropping packets associated with a no-drop class of service, at the leaf switch, when a packet buffer of the inbound uplink port reaches a predetermined threshold. ### Claim 2 (depends on 1) The method of claim 1, wherein the method further comprises: upon detecting the valley routing condition in the network, changing a service level of the packets associated with a no-drop class of service to a class of service that is eligible to be dropped. ### Claim 3 (depends on 2) The method of claim 2, wherein the packets that are eligible to be dropped are not dropped unless the packet buffer associated with the inbound uplink port reaches the predetermined threshold. ### Claim 4 (depends on 1) The method of claim 1, further comprising receiving information associated with packet buffer usage of a plurality of network ports of the leaf switch, including at least the inbound uplink port and the outbound uplink port. ### Claim 5 (depends on 1) The method of claim 1, wherein the packets associated with the no-drop class of service are not dropped when the packet buffer associated with the inbound uplink port is less than the predetermined threshold. ### Claim 6 (depends on 1) The method of claim 1, wherein the packets are dropped by an application-specific integrated circuit in the leaf switch. ### Claim 7 (depends on 1) The method of claim 1, wherein the leaf switch includes a downlink port connected to at least one host device; and wherein the valley routing condition is detected when the packet marked with the identifier associated with the inbound uplink port of the leaf switch is being routed to the outbound uplink port of the leaf switch to be transmitted to one of the first spine switch and the second spine switch without traversing the downlink port to the least one host device. ### Claim 8 One or more non-transitory computer readable storage media encoded with instructions that, when executed by a processor of a leaf switch in a network having a leaf-spine topology, cause the processor to: monitor traffic of a plurality of packets in the network, the network including a first spine switch connected to the leaf switch and a second spine switch connected to the leaf switch; mark a packet of the plurality of packets with an identifier associated with an inbound uplink port of the leaf switch when the packet is received from one of the first spine switch and the second spine switch; detect a valley routing condition in the network upon determining that the packet marked with the identifier associated with the inbound uplink port of the leaf switch is being routed to an outbound uplink port of the leaf switch to be transmitted to one of the first spine switch and the second spine switch; and upon detection of the valley routing condition in the network, drop packets associated with a no-drop class of service, at the leaf switch, when a packet buffer of the inbound uplink port reaches a predetermined threshold. ### Claim 9 (depends on 8) The non-transitory computer readable storage media of claim 8, wherein the instructions further cause the processor to: upon detection of the valley routing condition in the network, change a service level of the packets associated with a no-drop class of service to a class of service that is eligible to be dropped. ### Claim 10 (depends on 9) The non-transitory computer readable storage media of claim 9, wherein the packets that are eligible to be dropped are not dropped unless the packet buffer associated with the inbound uplink port reaches the predetermined threshold. ### Claim 11 (depends on 8) The non-transitory computer readable storage media of claim 8, wherein the instructions further cause the processor to: receive information associated with packet buffer usage of a plurality of network ports of the leaf switch, including at least the inbound uplink port and the outbound uplink port. ### Claim 12 (depends on 8) The non-transitory computer readable storage media of claim 8, wherein the packets associated with the no-drop class of service are not dropped when the packet buffer associated with the inbound uplink port is less than the predetermined threshold. ### Claim 13 (depends on 8) The non-transitory computer readable storage media of claim 8, wherein the packets are dropped by an application-specific integrated circuit in the leaf switch. ### Claim 14 (depends on 8) The non-transitory computer readable storage media of claim 8, wherein the leaf switch includes a downlink port connected to at least one host device; and wherein the valley routing condition is detected when the packet marked with the identifier associated with the uplink port of the leaf switch is being routed to the outbound uplink port of the leaf switch to be transmitted to one of the first spine switch and the second spine switch without traversing the downlink port to the least one host device. ### Claim 15 An apparatus comprising: a plurality of network ports configured to receive inbound packets and to send outbound packets in a network having a leaf-spine topology, the network including a first spine switch connected to one of the plurality of network ports and a second spine switch connected to one of the plurality of network ports; a processor coupled to the plurality of network ports, wherein the processor is configured to: mark a packet of a plurality of packets with an identifier associated with an inbound uplink port of the plurality of network ports when the packet is received from one of the first spine switch and the second spine switch; detect a valley routing condition upon determining that the packet marked with the identifier associated with the inbound uplink port is being routed to an outbound uplink port to be transmitted to one of the first spine switch and the second spine switch; and upon detection of the valley routing condition in the network, drop packets associated with a no-drop class of service when a packet buffer of the inbound uplink port reaches a predetermined threshold. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein the processor is further configured to: upon detection of the valley routing condition in the network, change a service level of the packets associated with a no-drop class of service to a class of service that is eligible to be dropped. ### Claim 17 (depends on 16) The apparatus of claim 16, wherein the packets that are eligible to be dropped are not dropped unless the packet buffer associated with the inbound uplink port reaches the predetermined threshold. ### Claim 18 (depends on 15) The apparatus of claim 15, wherein the processor is further configured to receive information associated with packet buffer usage of the plurality of network ports. ### Claim 19 (depends on 15) The apparatus of claim 15, wherein the packets are dropped by an application-specific integrated circuit disposed in the apparatus. ### Claim 20 (depends on 15) The apparatus of claim 15, further comprising a downlink port of the plurality of network ports that is connected to at least one host device; and wherein the valley routing condition is detected when the packet marked with the identifier associated with the inbound uplink port is being routed to the outbound uplink port of the plurality of network ports to be transmitted to one of the first spine switch and the second spine switch without traversing the downlink port to the least one host device.