Adaptive bandwidth sharing

• US 6,205,119 B1
• Filed: 09/16/1997
• Issued: 03/20/2001
• Est. Priority Date: 09/16/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Kaczynski, Tomasz
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Tsegaye, Saba
• Application Number:
  US08/931,565
• Time in Patent Office: 1,281 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/236, 370/252, 370/254, 370/412, 370/465, 370/468, 370/527
• US Class Current: 370/231
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/13 in a LAN segment, e.g. ring or bus
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method and apparatus for the efficient management of electronic communications in a ring topology network. Each Send packet and Echo packet includes a mechanism used to request to share bandwidth. In one implementation a single bit is used, while in another the mechanism includes a traffic control field providing a hierarchy of request to share bits accompanied by priority information, thereby enabling a multi-level system. When a Send packet reaches the target node the information is returned to the source node via the echo packet'"'"'s request to share bit or the traffic control field, depending upon the implementation. The source node then alters its rate of packet transmission as a function of the number of requests to share it receives and, in the second implementation, as a function of the priority of the requesting nodes in relation to the priority of the source node. In one embodiment, each node conditionally gives output packets preference over passing through packets.

Claims

1. A method of controlling the rate of packet transmissions between a plurality of nodes, including a source node, a target node and an intermediate node, the method comprising the steps of:

connecting the nodes via unidirectional links;

transmitting flow control information in a Send packet from a source node to a target node, wherein the step of transmitting includes the steps of;

sending the Send packet to the intermediate node; and

requesting, at the intermediate node, bandwidth for one of plurality of nodes,

wherein the step of requesting bandwidth includes the step of modifying, within the intermediate node, the flow control information in the Send packet;

receiving the Send packet at the target node and transferring the modified flow control information from the Send packet to an echo packet;

transmitting the echo packet from the target node to the source node; and

at the source node, adjusting the rate of packet transmission as a function of the modified flow control information contained in the echo packet and the traffic at the source node, wherein adjusting includes transmitting one or more idle symbols from the source node as a function of the modified flow control information contained in the echo packet.

2. The method of claim 1, wherein the Send packet includes a traffic control field, and wherein the step of modifying flow control information comprises the step of setting a request-to-share bit in the traffic control field.

3. The method of claim 1, wherein the Send packet includes a traffic control field, and wherein the step of modifying flow control information comprises the step of selecting a request-to-share bit to be set according to a priority held in the traffic control field.

4. The method of claim 3, wherein the step of adjusting the rate of packet transmission comprises the step of giving priority to parser traffic and Idle symbols.

5. The method of claim 3, wherein the step of adjusting the rate of packet transmission comprises the step of reducing bandwidth use as a function of a priority assigned to the node requesting bandwidth and a priority assigned to any node congesting the requesting node.

6. The method of claim 3, wherein the step of adjusting the rate of packet transmission comprises the step of giving priority to parser traffic and Idle symbols for a specified time period, but only to an amount commensurate with priorities associated with the requesting node and the source node.

7. A method of controlling the rate of packet transmissions between a plurality of nodes, including a source node, a target node and an intermediate node, the method comprising the steps of:

connecting the nodes via unidirectional links;

transmitting flow control information in a Send packet from a source node to a target node, wherein the Send packet includes a traffic control field, and wherein the step of transmitting includes the steps of;

sending the Send packet to the intermediate node; and

requesting, at the intermediate node, bandwidth for one of plurality of nodes,

wherein the step of requesting bandwidth includes the step of modifying, within the intermediate node, the flow control information in the Send packet, wherein the step of modifying flow control information comprises the step of setting a request-to-share bit in the traffic control field;

receiving the Send packet at the target node and transferring the flow control information from the Send packet to an echo packet;

transmitting the echo packet from the target node to the source node; and

at the source node, adjusting the rate of packet transmission as a function of the flow control information contained in the echo packet and the traffic at the source node.

8. A method of controlling the rate of packet transmissions between a plurality of nodes, including a source node, a target node and an intermediate node, the method comprising the steps of:

connecting the nodes via unidirectional links;

transmitting flow control information in a Send packet from a source node to a target node, wherein the Send packet includes a traffic control field, and wherein the step of transmitting includes the steps of;

sending the Send packet to the intermediate node; and

requesting, at the intermediate node, bandwidth for one of plurality of nodes,

wherein requesting bandwidth includes modifying, within the intermediate node, the flow control information in the Send packet, wherein modifying the flow control information comprises the step of selecting a request-to-share bit to be set according to a priority held in the traffic control field;

receiving the Send packet at the target node and transferring the flow control information from the Send packet to an echo packet;

transmitting the echo packet from the target node to the source node; and

at the source node, adjusting the rate of packet transmission as a function of the flow control information contained in the echo packet and the traffic at the source node.

9. The method of claim 8, wherein the step of adjusting the rate of packet transmission comprises the step of giving priority to parser traffic and Idle symbols.

10. The method of claim 8, wherein the step of adjusting the rate of packet transmission comprises the step of reducing bandwidth use as a function of a priority assigned to the node requesting bandwidth and a priority assigned to any node congesting the requesting node.

11. The method of claim 8, wherein the step of adjusting the rate of packet transmission comprises the step of giving priority to parser traffic and Idle symbols for a specified time period, but only to an amount commensurate with priorities associated with the requesting node and the source node.

12. A system for controlling electronic communications, comprising:

a network comprising a plurality of nodes, including a source node, a target node and plurality of intermediate nodes, wherein the plurality of nodes are interconnected via unidirectional links;

means for transmitting a Send packet from a source node, the Send packet comprising flow control information;

means for allowing one of the plurality of intermediate nodes to request bandwidth by modifying the flow control information in the transmitted Send packet;

means for receiving a Send packet at a target node;

means for transferring the flow control information from the received Send packet to an Echo packet;

means for transmitting the Echo packet to the source node; and

means for modifying the transmission rate according to the traffic at the source node and the modified flow control information, wherein the means for modifying transmits one or more idle symbols from the source node as a function of the modified flow control information contained in the Echo packet.

13. The system of claim 12, wherein the Send packet and the Echo packet each comprise a traffic control field, the traffic control field comprising request to share bits and priority bits.

14. The system of claim 13, wherein the size of the traffic control field in the Send packet and the Echo packet is constant regardless of the number of nodes connected to the network.

15. The system of claim 12, wherein the means of modifying comprises means for activating a request to share bit.

16. A system for controlling electronic communications, comprising:

a network comprising a plurality of nodes, including a source node, a target node and plurality of intermediate nodes, wherein the plurality of nodes are interconnected via unidirectional links;

means for transmitting a Send packet from a source node, the Send packet comprising flow control information;

means for allowing one of the plurality of intermediate nodes to request bandwidth by modifying the flow control information in the transmitted Send packet;

means for receiving a Send packet at a target node;

means for transferring the flow control information from the received Send packet to an Echo packet;

means for transmitting the Echo packet to the source node; and

means for modifying the transmission rate according to the traffic at the source node and the modified flow control information, wherein the means of modifying comprises means for activating a request to share bit.

17. The system of claim 16, wherein the Send packet and the Echo packet each comprise a traffic control field, the traffic control field comprising request to share bits and priority bits.

18. The system of claim 17, wherein the size of the traffic control field in the Send packet and the Echo packet is constant regardless of the number of nodes connected to the network.

19. A system comprising a plurality of interconnected nodes, wherein each node shares communications bandwidth with one or more of the other nodes, wherein each node comprises:

a receiver for receiving a plurality of incoming packets, including an echo packet, wherein each of the plurality of packets comprising a plurality of fields;

a modifier for writing information to one or more of the plurality of fields;

a parser for extracting information contained in one or more of the plurality of fields;

a throttling mechanism, wherein the throttling mechanism controls the amount of bandwidth being used by the node by transmitting one or more idle symbols from the node as a function of flow control information contained in the echo packet; and

an output queue for holding packets generated by the node.

20. The system of claim 19, wherein the throttling mechanism is responsive to information extracted from the plurality of fields.

21. The system of claim 20, wherein the extracted information comprises a packet priority, and wherein the throttling mechanism of each of the plurality of nodes restricts the node from transmitting packets according to the relative values of a priority assigned to a passing-through packet and a priority assigned to a packet on the node'"'"'s output queue.

22. The system of claim 19, wherein the throttling mechanism comprises a counter, wherein the counter tracks the amount of the bandwidth to share and wherein the throttling mechanism restricts the node from transmitting packets from its output queue according to the contents of the counter.

23. The system of claim 19, wherein the throttling mechanism comprises a counter, wherein the counter tracks the amount of the bandwidth to share and wherein the throttling mechanism restricts the node from transmitting packets from its output queue as a function of the counter and a passing-through packet'"'"'s relative priority to a packet on the node'"'"'s output queue.

24. A node for communicating with a network, the node comprising:

a receiver for receiving a plurality of incoming packets, including an echo packet, from the network, wherein each of the plurality of packets comprising a plurality of fields;

a modifier for writing information to one or more of the plurality of fields;

a parser for extracting information contained in one or more of the plurality of fields;

a throttling mechanism, wherein the throttling mechanism controls the amount of bandwidth being used by the node by transmitting one or more idle symbols from the node as a function of flow control information contained in the echo packet; and

an output queue for holding packets generated by the node.

25. The node of claim 24, wherein the extracted information comprises requests to share bandwidth, and wherein the throttling mechanism is responsive to the requests to share bandwidth.

26. The node of claim 24, wherein the extracted information comprises requests to share bandwidth and priority information, and wherein the throttling mechanism responds to the requests to share bandwidth as a function of the priority information.

27. A method of communicating data packets in a network of nodes comprising:

transmitting a data packet from a source node to a target node via at least one intermediate node, wherein the data packet includes flow control information;

modifying the flow control information of the data packet when the data packet passes through the intermediate node;

transmitting an echo packet from the target node to the source node, wherein the echo packet includes the modified flow control information from the data packet; and

adjusting a packet transmission rate of the source node by transmitting one or more idle symbols from the source node as a function of the modified flow control information contained in the echo packet.

28. The method of claim 27, wherein modifying the flow control information includes setting a request-to-share bit in the flow control information.

29. The method of claim 28, wherein modifying the flow control information includes selecting the request-to-share bit to be set as a function of a priority held in the flow control information.

30. The method of claim 27, wherein the modified flow control information includes an amount of requested bandwidth, and further wherein the step of adjusting the packet transmission rate includes transmitting a number of the idle symbols in proportion to the requested amount.

31. The method of claim 27, wherein the step of adjusting the packet transmission rate includes transmitting the idle symbols as a function of a priority assigned to the intermediate node and a priority assigned to any node congesting the intermediate node.

32. The method of claim 27, wherein the step of adjusting the rate of packet transmission comprises the step of giving priority to parser traffic for a time period commensurate with priorities associated with the intermediate node and the source node.

33. The method of claim 27, further comprising the step of issuing retry packets before non-retry data packets are transmitted.

34. A node for a computer network, wherein the node performs the steps of:

transmitting a data packet from a source node to a target node via at least one intermediate node, wherein the data packet includes flow control information;

modifying the flow control information of the data packet when the data packet passes through the intermediate node;

transmitting an echo packet from the target node to the source node, wherein the echo packet includes the modified flow control information from the data packet; and

adjusting a packet transmission rate of the source node by transmitting one or more idle symbols from the source node as a function of the modified flow control information contained in the echo packet.

35. A system comprising a network of interconnected nodes, wherein each node comprises:

a receiver for receiving a plurality of incoming packets from other nodes in the network, wherein the plurality of incoming packets includes an echo packet, wherein the echo packet includes flow control information;

a parser for extracting the flow control information contained in the echo packet;

a throttling mechanism for generating one or more idle symbols as a function of the extracted information, wherein the throttling mechanism adjusts a packet transmission rate of the node by transmitting one or more idle symbols from the node as a function of the flow control information contained in the echo packet; and

an output for transmitting the idle symbols and any data packet generated by the node.

36. The system of claim 35, wherein the extracted information comprises a packet priority, and wherein the output transmits the idle symbols according to a priority assigned to a passing-through packet and a priority assigned to a packet on the node'"'"'s output.

37. The system of claim 35, wherein the extracted information indicates an amount of the bandwidth to share, and further wherein the throttling mechanism generates the idle symbols in proportion to the amount.

38. The system of claim 35, wherein the throttling mechanism restricts the output from transmitting packets as a function a passing-through packet'"'"'s priority relative to a packet held in the output.

39. The system of claim 35, further comprising a modifier for writing flow control information of the received packets.

40. The system of claim 35, wherein the output issues retry data packets before non-retry data packets are transmitted.