# US 7,613,116 B1 · Method and apparatus for preventing head of line blocking among ethernet switches > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,116 B1 - Document ID: US7613116B1 - Status: Granted - Kind: B1 - Application number: 10/955,893 - Filed: 2004-09-29 - Granted: 2009-11-03 - Earliest claimed: 2004-09-29 - Assignees: Marvell Israel (M.I.S.L) Ltd. - Inventors: Eitan Medina - Web page: https://patentgrep.com/patent/US7613116B1 ## CPC - H04L 49/351: for local area network [LAN], e.g. Ethernet switches - H04L 49/501: {Overload detection} - H04L 49/508: {Head of Line Blocking Avoidance} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract An Ethernet switch for preventing head of line blocking by passing an Ethernet packet carrying congestion status information among Ethernet switches over the Ethernet. When a port of an Ethernet switch is congested, the switch informs other Ethernet switches by broadcasting to other switches over the Ethernet an Ethernet packet indicating that the port is congested. If another Ethernet switch finds that one of its traffic classes is destined to the congested port, this switch drops packets of that traffic flow until receiving an Ethernet packet indicating that the congestion is alleviated. ## Claims ### Claim 1 An Ethernet switch comprising: a plurality of ports, including at least one port communicating with an Ethernet network, wherein each of said ports contains one or more queues; a management module receiving over the Ethernet network an Ethernet packet carrying congestion status information from an Ethernet switch in the Ethernet network; a switch fabric for providing switching connections, the switch fabric communicating between the plurality of ports and the management module such that communication between the plurality of ports and the management module passes through the switch fabric; an address database associating addresses with ports or queues of Ethernet switches in the Ethernet network; and an address parse module communicating between the switch fabric and the address database such that communication between the switch fabric and the address database passes through the address parse module and such that communication between the management module and the address parse module passes through the switch fabric. ### Claim 2 (depends on 1) The Ethernet switch according to claim 1, wherein the management module further identifies a congested port or queue of the Ethernet switch. ### Claim 3 (depends on 2) The Ethernet switch according to claim 2, wherein the management module further generates a second Ethernet packet which contains congestion status information about the Ethernet switch and said one of the Ethernet switches in the Ethernet network, and sends the second Ethernet packet over the Ethernet network. ### Claim 4 (depends on 1) The Ethernet switch according to claim 1, wherein the management module further identifies a congested port or queue of another of the Ethernet switches in the Ethernet network from the Ethernet packet carrying congestion status information. ### Claim 5 (depends on 4) The Ethernet switch according to claim 4, wherein the management module further decides whether a packet passing through the Ethernet switch is destined to the congested port or queue. ### Claim 6 (depends on 5) The Ethernet switch according to claim 5, wherein the management module drops packets destined to the congested port or queue. ### Claim 7 (depends on 6) The Ethernet switch according to claim 6, wherein the management module determines whether to re-transmit the dropped packets. ### Claim 8 (depends on 6) The Ethernet switch according to claim 6, wherein the management module further stops dropping packets when congestion of the congested port or queue is alleviated. ### Claim 9 (depends on 5) The Ethernet switch according to claim 5, wherein the management module further determines whether congestion of the congested port or queue is alleviated. ### Claim 10 (depends on 1) The Ethernet switch according to claim 1, wherein each address corresponds to a port of one of the Ethernet switches in the Ethernet network. ### Claim 11 (depends on 1) The Ethernet switch according to claim 1, wherein each address corresponds to a queue of a port of one of the Ethernet switches in the Ethernet network. ### Claim 12 (depends on 1) The Ethernet switch according to claim 1, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 13 (depends on 12) The Ethernet switch according to claim 12, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 14 (depends on 12) The Ethernet switch according to claim 12, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 15 (depends on 1) The Ethernet switch according to claim 1, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 16 (depends on 15) The Ethernet switch according to claim 15, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 17 (depends on 15) The Ethernet switch according to claim 15, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 18 (depends on 1) The Ethernet switch according to claim 1, wherein each address is a media access control (MAC) address. ### Claim 19 (depends on 1) The Ethernet switch according to claim 1, wherein each address is a network address. ### Claim 20 (depends on 1) The Ethernet switch according to claim 1, wherein each address is used to identify a network flow. ### Claim 21 (depends on 1) The Ethernet switch according to claim 1, further comprising a packet buffer, indicating whether a port or queue is suffering congestion. ### Claim 22 (depends on 1) The Ethernet switch according to claim 1, wherein the database further stores a plurality of paths for Ethernet packets. ### Claim 23 (depends on 22) The Ethernet switch according to claim 22, wherein the management module further reroutes the Ethernet packets according to the congestion status information. ### Claim 24 (depends on 1) A line card in an Ethernet system, comprising: at least one Ethernet switch according to claim 1; at least one network interface communicating data with the Ethernet switch; and at least one processor communicating data with the network interface. ### Claim 25 Ethernet switching means comprising: a plurality of ports, including at least one port communicating with an Ethernet network, wherein each of said ports contains one or more queues; management means receiving over the Ethernet network an Ethernet packet carrying congestion status information from an Ethernet switching means in the Ethernet network; switch fabric means for providing switching connections, the switch fabric means communicating between the plurality of ports and the management means such that communication between the plurality of ports and the management means passes through the switch fabric means; an address database associating addresses with ports or queues of Ethernet switching means in the Ethernet network; and address parse means communicating between the switch fabric means and the address database such that communication between the switch fabric means and the address database passes through the address parse means and such that communication between the management means and the address parse means passes through the switch fabric means. ### Claim 26 (depends on 25) The Ethernet switching means according to claim 25, wherein the management means further identifies a congested port or queue of the Ethernet switching means. ### Claim 27 (depends on 26) The Ethernet switching means according to claim 26, wherein the management means further generates a second Ethernet packet which contains congestion status information about the Ethernet switching means and said one of the Ethernet switching means in the Ethernet network, and sends the second Ethernet packet over the Ethernet network. ### Claim 28 (depends on 25) The Ethernet switching means according to claim 25, wherein the management means further identifies a congested port or queue of another of the Ethernet switching means in the Ethernet network from the Ethernet packet carrying congestion status information. ### Claim 29 (depends on 28) The Ethernet switching means according to claim 28, wherein the management means further decides whether a packet passing through the Ethernet switching means is destined to the congested port or queue. ### Claim 30 (depends on 29) The Ethernet switching means according to claim 29, wherein the management means drops packets destined to the congested port or queue. ### Claim 31 (depends on 30) The Ethernet switching means according to claim 30, wherein the management means determines whether to re-transmit the dropped packets. ### Claim 32 (depends on 30) The Ethernet switching means according to claim 30, wherein the management means stops dropping packets when congestion of the congested port or queue is alleviated. ### Claim 33 (depends on 29) The Ethernet switching means according to claim 29, wherein the management means further determines whether congestion of the congested port or queue is alleviated. ### Claim 34 (depends on 25) The Ethernet switching means according to claim 25, wherein each address corresponds to a port of one of the Ethernet switching means in the Ethernet network. ### Claim 35 (depends on 25) The Ethernet switching means according to claim 25, wherein each address corresponds to a queue of a port of one of the Ethernet switching means in the Ethernet network. ### Claim 36 (depends on 25) The Ethernet switching means according to claim 25, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 37 (depends on 36) The Ethernet switching means according to claim 36, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 38 (depends on 36) The Ethernet switching means according to claim 36, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 39 (depends on 25) The Ethernet switching means according to claim 25, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 40 (depends on 39) The Ethernet switching means according to claim 39, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 41 (depends on 39) The Ethernet switching means according to claim 39, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 42 (depends on 25) The Ethernet switching means according to claim 25, wherein each address is a media access control (MAC) address. ### Claim 43 (depends on 25) The Ethernet switching means according to claim 25, wherein each address is a network address. ### Claim 44 (depends on 25) The Ethernet switching means according to claim 25, wherein each address is used to identify a network flow. ### Claim 45 (depends on 25) The Ethernet switching means according to claim 25, further comprising packet buffer means, indicating whether a port or queue is suffering congestion. ### Claim 46 (depends on 25) The Ethernet switching means according to claim 25, wherein the database further stores a plurality of paths for Ethernet packets. ### Claim 47 (depends on 46) The Ethernet switching means according to claim 46, wherein the management means further reroute the Ethernet packets according to the congestion status information. ### Claim 48 (depends on 25) A line card in an Ethernet system, comprising: at least one Ethernet switching means according to claim 25; at least one network interfacing means communicating data with the Ethernet switching means; and at least one processing means communicating data with the network interfacing means. ### Claim 49 A method for preventing head of line blocking in an Ethernet system, the method comprising: associating, in a database of an Ethernet switch, addresses with ports or queues of Ethernet switches in an Ethernet network; and receiving over the Ethernet network into a management module of the Ethernet switch an Ethernet packet carrying congestion status information from one of the Ethernet switches in the Ethernet network, the congestion status information passing from one of a plurality of ports of the Ethernet switch through a switch fabric of the Ethernet switch to the management module, the switch fabric communicating between the management module and an address parse module of the Ethernet switch such that communication between the management module and the address parse module passes through the switch fabric the address parse module communicating between the switch fabric and the database such that communication between the switch fabric and the database passes through the address parse module, wherein the plurality of ports includes at least one port communicating with the Ethernet network, each of said ports containing one or more queues. ### Claim 50 (depends on 49) The method according to claim 49, further comprising identifying a congested port or queue of the Ethernet switch. ### Claim 51 (depends on 50) The method according to claim 50, further comprising: generating a second Ethernet packet which contains congestion status information about the Ethernet switch and said one of the Ethernet switches in the Ethernet network; and sending the second Ethernet packet over the Ethernet network. ### Claim 52 (depends on 49) The method according to claim 49, further comprising identifying a congested port or queue of another of the Ethernet switches in the Ethernet network from the Ethernet packet carrying congestion status information. ### Claim 53 (depends on 52) The method according to claim 52, further comprising deciding whether a packet passing through the Ethernet switch is destined to the congested port or queue. ### Claim 54 (depends on 53) The method according to claim 53, further comprising dropping packets destined to the congested port or queue. ### Claim 55 (depends on 54) The method according to claim 54, further comprising determining whether to re-transmit the dropped packets. ### Claim 56 (depends on 54) The method according to claim 54, further comprising stopping dropping packets when congestion of the congested port or queue is alleviated. ### Claim 57 (depends on 53) The method according to claim 53, further comprising determining whether congestion of the congested port or queue is alleviated. ### Claim 58 (depends on 49) The method according to claim 49, wherein each address corresponds to a port of one of the Ethernet switches in the Ethernet network. ### Claim 59 (depends on 49) The method according to claim 49, wherein each address corresponds to a queue of a port of one of the Ethernet switches in the Ethernet network. ### Claim 60 (depends on 49) The method according to claim 49, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 61 (depends on 60) The method according to claim 60, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 62 (depends on 60) The method according to claim 60, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 63 (depends on 49) The method according to claim 49, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 64 (depends on 63) The method according to claim 63, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 65 (depends on 63) The method according to claim 63, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 66 (depends on 49) The method according to claim 49, wherein each address is a media access control (MAC) address. ### Claim 67 (depends on 49) The method according to claim 49, wherein each address is a network address. ### Claim 68 (depends on 49) The method according to claim 49, wherein each address is used to identify a network flow. ### Claim 69 (depends on 49) The method according to claim 49, further comprising storing a plurality of paths for Ethernet packets. ### Claim 70 (depends on 69) The method according to claim 69, further comprising rerouting the Ethernet packets according to the congestion status information. ### Claim 71 An Ethernet switch comprising: a plurality of ports, including at least one port communicating with an Ethernet network, wherein each of said ports contains one or more queues; a management module identifying a congested port or queue of the Ethernet switch and generating an Ethernet packet carrying congestion status information about the Ethernet switch to be sent over the Ethernet network; a switch fabric for providing switching connections the switch fabric communicating between the plurality of ports and the management module such that communication between the plurality of ports and the management module passes through the switch fabric; an address database associating addresses with ports or queues of Ethernet switches in the Ethernet network; an address parse module communicating between the switch fabric and the address database such that communication between the switch fabric and the address database passes through the address parse module and such that communication between the management module and the address parse module passes through the switch fabric. ### Claim 72 (depends on 71) The Ethernet switch according to claim 71, wherein the management module further sends the Ethernet packet carrying congestion status information over the Ethernet network. ### Claim 73 (depends on 71) The Ethernet switch according to claim 71, wherein each address corresponds to a port of one of the Ethernet switches in the Ethernet network. ### Claim 74 (depends on 71) The Ethernet switch according to claim 71, wherein each address corresponds to a queue of a port of one of the Ethernet switches in the Ethernet network. ### Claim 75 (depends on 71) The Ethernet switch according to claim 71, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 76 (depends on 75) The Ethernet switch according to claim 75, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 77 (depends on 75) The Ethernet switch according to claim 75, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 78 (depends on 71) The Ethernet switch according to claim 71, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 79 (depends on 78) The Ethernet switch according to claim 78, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switch, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 80 (depends on 78) The Ethernet switch according to claim 78, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 81 (depends on 71) The Ethernet switch according to claim 71, wherein each address is a media access control (MAC) address. ### Claim 82 (depends on 71) The Ethernet switch according to claim 71, wherein each address is a network address. ### Claim 83 (depends on 71) The Ethernet switch according to claim 71, wherein each address is used to identify a network flow. ### Claim 84 (depends on 71) The Ethernet switch according to claim 71, further comprising a packet buffer, indicating whether a port or queue is suffering congestion. ### Claim 85 (depends on 71) A line card in an Ethernet system, comprising: at least one Ethernet switch according to claim 71; at least one network interface communicating data with the Ethernet switch; and at least one processor communicating data with the network interface. ### Claim 86 Ethernet switching means comprising: a plurality of ports, including at least one port communicating with an Ethernet network, wherein each of said ports contains one or more queues; management means identifying a congested port or queue of the Ethernet switching means and generating an Ethernet packet carrying congestion status information about the Ethernet switching means to be sent over the Ethernet network; switch fabric means for providing switching connections the switch fabric means communicating between the plurality of ports and the management means such that communication between the plurality of ports and the management means passes through the switch fabric means, an address database associating addresses with ports or queues of Ethernet switching means in the Ethernet network; and address parse means communicating between the switch fabric means and the address database such that communication between the switch fabric means and the address database passes through the address parse means and such that communication between the management means and the address parse means passes through the switch fabric means. ### Claim 87 (depends on 86) The Ethernet switching means according to claim 86, wherein the management means further comprising sending sends the Ethernet packet carrying congestion status information over the Ethernet network. ### Claim 88 (depends on 86) The Ethernet switching means according to claim 86, wherein each address corresponds to a port of one of the Ethernet switching means in the Ethernet network. ### Claim 89 (depends on 86) The Ethernet switching means according to claim 86, wherein each address corresponds to a queue of a port of one of the Ethernet switching means in the Ethernet network. ### Claim 90 (depends on 86) The Ethernet switching means according to claim 86, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 91 (depends on 90) The Ethernet switching means according to claim 90, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 92 (depends on 90) The Ethernet switching means according to claim 90, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 93 (depends on 86) The Ethernet switching means according to claim 86, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 94 (depends on 93) The Ethernet switching means according to claim 93, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 95 (depends on 93) The Ethernet switching means according to claim 93, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 96 (depends on 86) The Ethernet switching means according to claim 86, wherein each address is a media access control (MAC) address. ### Claim 97 (depends on 86) The Ethernet switching means according to claim 86, wherein each address is a network address. ### Claim 98 (depends on 86) The Ethernet switching means according to claim 86, wherein each address is used to identify a network flow. ### Claim 99 (depends on 86) The Ethernet switching means according to claim 86, further comprising packet buffer means, indicating whether a port or queue is suffering congestion. ### Claim 100 (depends on 86) A line card in an Ethernet system, comprising: at least one Ethernet switching means according to claim 86; at least one network interfacing means communicating data with the Ethernet switching means; and at least one processing means communicating data with the network interfacing means. ### Claim 101 A method for preventing head of line blocking in an Ethernet system, the method comprising: associating, in a database of an Ethernet switching means, addresses with ports or queues of Ethernet switching means in an Ethernet network; identifying a congested port or queue of the Ethernet switching means; and generating in management means of the Ethernet switching means, an Ethernet packet carrying congestion status information about the Ethernet switching means to be sent over the Ethernet network the packet to pass from the management means through switch fabric means of the Ethernet switching means to one of a plurality of ports of the Ethernet switching means, the switch fabric means communicating between the management means and address parse means of the Ethernet switching means such that communication between the management means and the address parse means passes through the switch fabric means, the address parse means communicating between the switch fabric means and the database such that communication between the switch fabric means and the database passes through the address parse means, wherein the plurality of ports includes at least one port communicating with the Ethernet network, each of said ports containing one or more queues. ### Claim 102 (depends on 101) The method according to claim 101, further comprising sending the Ethernet packet carrying congestion status information over the Ethernet network. ### Claim 103 (depends on 101) The method according to claim 101, wherein each address corresponds to a port of one of the Ethernet switching means in the Ethernet network. ### Claim 104 (depends on 101) The method according to claim 101, wherein each address corresponds to a queue of a port of one of the Ethernet switching means in the Ethernet network. ### Claim 105 (depends on 101) The method according to claim 101, wherein the Ethernet packet carrying congestion status information is in the form of a tag. ### Claim 106 (depends on 105) The method according to claim 105, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 107 (depends on 105) The method according to claim 105, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 108 (depends on 101) The method according to claim 101, wherein the Ethernet packet carrying congestion status information is an IEEE 802.3x compliant packet. ### Claim 109 (depends on 108) The method according to claim 108, wherein the Ethernet packet includes a filler containing a bitmap for each Ethernet switching means, each bit of the bitmap corresponding to a congestion status of a port or queue. ### Claim 110 (depends on 108) The method according to claim 108, wherein the Ethernet packet includes a filler containing a parametric congestion value for each port or queue. ### Claim 111 (depends on 101) The method according to claim 101, wherein each address is a media access control (MAC) address. ### Claim 112 (depends on 101) The method according to claim 101, wherein each address is a network address. ### Claim 113 (depends on 101) The method according to claim 101, wherein each address is used to identify a network flow.