System for placing packets on network for transmission from sending endnode to receiving endnode at times which are determined by window size and metering interval

• US 6,105,064 A
• Filed: 05/30/1997
• Issued: 08/15/2000
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: Micro Focus Software, Inc. (Open Text Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Davis, Howard, Echols, Grant, Hundley, B. Gregory, Richey, Jonathan, Dege, Michael, Neath, Greg
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US08/866,542
• Time in Patent Office: 1,173 Days
• Field of Search: 709/200, 709/201, 709/209, 709/217, 709/218, 709/219, 709/220, 709/221, 709/223, 709/224, 709/225, 709/232, 709/233, 709/234, 709/235, 709/246, 370/229, 370/231, 370/232, 370/236, 370/320, 370/400, 370/466
• US Class Current: 709/224
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking

Abstract

A method for controlling communications between endnodes in a packet-switched computer network includes dynamic window sizing and dynamic packet metering. Dynamic window sizing regularly probes the network to determine whether higher throughput is available at an increased window size, and avoids unnecessary decreases in window size after a packet is dropped or all available data has been transmitted. Dynamic packet metering regularly adjusts the rate at which packets are transmitted in response to changes in the measured propagation rate of packets through the network. To avoid unnecessary ack packets, acks are bundled together and piggybacked on returning data packets when appropriate. The invention provides control even if the address of an endnode changes. The invention also supports multiplexing several logical connections over a single transport session and combining data from several connections in a single packet, as well as construction of packets in a network-layer-independent format.

Claims

1. A method of controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the packets including a plurality of data packets which are capable of carrying data over the network, the method comprising the computer-implemented steps of:

selecting a window size which limits the amount of outstanding data, outstanding data being data that has been sent in a data packet from the sending endnode but has not yet been acknowledged by the receiving endnode;

selecting a metering interval which limits the rate at which data packets are placed on the network; and

placing packets on the network for transmission from the sending endnode to the receiving endnode at times which are determined in response to the window size and the metering interval.

2. The method of claim 1, wherein the step of selecting a window size comprises the steps of:

measuring packet throughput from the sending endnode to the receiving endnode at a plurality of different window sizes; and

selecting the smallest window size at which the measured packet throughput is greatest.

3. The method of claim 2, wherein the step of selecting the window size comprises determining an excessive window size at which throughput no longer increases.

4. The method of claim 1, wherein the step of selecting a metering interval comprises the steps of:

measuring interpacket gaps between packets arriving at an endnode; and

determining the metering interval of the sending endnode based on the measured interpacket gaps.

5. The method of claim 4, wherein the step of determining the metering interval comprises determining an average interpacket gap time for packets received at the receiving endnode.

6. The method of claim 5, further comprising the computer-implemented step of sending a packet from the receiving endnode to the sending endnode containing a new average interpacket gap time in response to a change in the average interpacket gap time.

7. The method of claim 1, further comprising the computer-implemented step of multiplexing a plurality of logical connections over a single transport session.

8. The method of claim 1, wherein the step of placing packets on the network for transmission comprises the step of using packets that have a network-layer-independent internal format to generate packets that have a format which is tailored to a predetermined network layer.

9. The method of claim 8, wherein the generated packets have a format that is tailored to a network layer selected from the group consisting of IP, IPX, and ATM network layers.

10. The method of claim 1, further comprising the computer-implemented step of filling a single data packet with data from a plurality of connections.

11. The method of claim 1, further comprising the computer-implemented step of sending an acknowledgment from the receiving endnode to the sending endnode in response to receipt of a data packet by the receiving endnode and also in response to an occurrence of an acknowledgment update event.

12. The method of claim 11, wherein the acknowledgment update event is selected from the group of events consisting of:

the passage of at least an acknowledgment update time interval amount of time since the most recent sending of an acknowledgment by the receiving endnode, and

the receipt of at least an acknowledgment update packet count number of packets at the receiving endnode since the most recent sending of an acknowledgment by the receiving endnode.

13. The method of claim 12, further comprising the computer-implemented step of sending a packet containing the acknowledgment update packet count from the sending endnode to the receiving endnode in response to receiving notice of a change in the window size of the sending endnode.

14. The method of claim 1, further comprising the computer-implemented step of sending a plurality of acknowledgments in one packet from the receiving endnode to the sending endnode to acknowledge receipt by the receiving endnode of a corresponding plurality of data packets.

15. The method of claim 1, further comprising the computer-implemented step of sending an acknowledgment in a second data packet from the receiving endnode to the sending endnode in response to receipt of a first data packet by the receiving endnode.

16. The method of claim 1, further comprising the computer-implemented step of receiving at the sending endnode an address change packet which specifies a new address for the receiving endnode, the step of placing packets on the network further comprising placing a data packet on the network for transmission to the new address.

17. The method of claim 16, further comprising the step of validating the address change packet prior to placing a data packet on the network for transmission to the new address.

35. The storage medium of claim 1, wherein the method steps comprise the steps of claim 34.

38. A computer storage medium having a configuration that represents data and instructions which will cause at least a portion of a computer system to perform method steps for controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the packets including a plurality of data packets which are capable of carrying data over the network, the method steps comprising the steps of claim 1.

39. The storage medium of claim 38, wherein the method steps comprise the steps of claim 2.

40. The storage medium of claim 38, wherein the method steps comprise the steps of claim 4.

41. The storage medium of claim 38, wherein the method steps comprise the steps of claim 6.

42. The storage medium of claim 38, wherein the method steps comprise the steps of claim 12.

18. A method of controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the packets including a plurality of data packets which are capable of carrying data over the network, the method comprising the computer-implemented steps of:

dynamically selecting a preferred window size which limits the amount of outstanding data by measuring packet throughput from the sending endnode to the receiving endnode and determining the preferred window size based on the measured packet throughput, outstanding data being data that has been sent in a data packet from the sending endnode but has not yet been acknowledged by the receiving endnode; and

placing packets on the network for transmission from the sending endnode to the receiving endnode such that the window size is an upper bound on the number of unacknowledged packets.

19. The method of claim 18, wherein the step of placing packets on the network for transmission comprises the step of using packets that have a network-layer-independent internal format to generate packets that have a format which is tailored to a predetermined network layer.

20. The method of claim 18, further comprising the computer-implemented step of sending an acknowledgment from the receiving endnode to the sending endnode in response to receipt of a data packet by the receiving endnode and also in response to an occurrence of an acknowledgment update event.

21. The method of claim 18, further comprising the computer-implemented step of sending an acknowledgment in a second data packet from the receiving endnode to the sending endnode in response to receipt of a first data packet by the receiving endnode.

22. The method of claim 18, further comprising the computer-implemented step of receiving at the sending endnode an address change packet which specifies a new address for the receiving endnode, the step of placing packets on the network further comprising placing a data packet on the network for transmission to the new address.

23. The method of claim 18, wherein the step of dynamically selecting a preferred window size further comprises the computer-implemented steps of:

successively increasing a current window size and then measuring the packet throughput associated with the current window size until a maximum associated throughput is identified; and

then

selecting as the preferred window size the smallest window size with which the maximum packet throughput is associated.

24. The method of claim 23, further comprising the computer-implemented step of selecting a metering interval which limits the rate at which data packets are placed on the network during the placing step.

25. The method of claim 24, wherein the step of selecting a metering interval comprises the steps of:

measuring interpacket gaps between packets arriving at an endnode;

determining the metering interval of the sending endnode based on the measured interpacket gaps.

26. The method of claim 18, wherein the step of dynamically selecting a preferred window size further comprises the computer-implemented steps of:

designating an initial window size as a current window size;

installing the current window size as an upper bound on the number of unacknowledged packets;

measuring packet throughput from the sending endnode to the receiving endnode after the installing step;

determining whether the measured throughput associated with the current window size is no greater than a measured throughput associated with a previous window size; and

choosing a subsequent action based on the outcome of the determining step, wherein the subsequent action comprises selecting a previous window size as the preferred window size if the measured throughput associated with the current window size is no greater than the measured throughput associated with that previous window size, and the subsequent action otherwise comprises replacing the current window size with a designated larger window size and then repeating the installing, measuring, determining, and choosing steps.

43. A computer storage medium having a configuration that represents data and instructions which will cause at least a portion of a computer system to perform method steps for controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the packets including a plurality of data packets which are capable of carrying data over the network, the method steps comprising the steps of claim 18.

44. The storage medium of claim 43, wherein the method steps comprise the steps of claim 19.

45. The storage medium of claim 43, wherein the method steps comprise the steps of claim 20.

46. The storage medium of claim 43, wherein the method steps comprise the steps of claim 26.

27. A method of controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the method comprising the computer-implemented steps of:

associating a plurality of logical connections with a single transport session;

placing a packet on the network as part of the single transport session for transmission from the sending endnode to the receiving endnode; and

selecting a metering interval which limits the rate at which packets are placed on the network and wherein the placing step places packets on the network for transmission from the sending endnode to the receiving endnode at times which are determined in response to metering interval.

28. The method of claim 27, wherein the packet carries information for a plurality of connections.

29. The method of claim 28, wherein the packet is a data packet carrying data for a plurality of connections.

30. The method of claim 28, wherein the packet is a control packet carrying control information for a plurality of connections.

31. The method of claim 28, wherein the packet carries both data and control information, and provides carrying capability for a plurality of connections.

32. The method of claim 27, wherein at least one of the packets carries information for a plurality of connections.

33. The method of claim 27, wherein the step of placing the data packet on the network for transmission comprises the step of using a data packet that has a network-layer-independent internal format to generate a packet that has a format which is tailored to a predetermined network layer.

34. The method of claim 27, further comprising the computer-implemented step of sending an acknowledgment from the receiving endnode to the sending endnode in response to receipt of the data packet by the receiving endnode and also in response to an occurrence of an acknowledgment update event.

36. The method of claim 27, further comprising the computer-implemented step of sending an acknowledgment in a second data packet from the receiving endnode to the sending endnode in response to receipt of a first data packet by the receiving endnode.

37. The method of claim 27, further comprising the computer-implemented step of receiving at the sending endnode an address change packet which specifies a new address for the receiving endnode, the step of placing packets on the network further comprising placing a data packet on the network for transmission to the new address.

47. A computer storage medium having a configuration that represents data and instructions which will cause at least a portion of a computer system to perform method steps for controlling the transmission of packets over a computer network between a sending endnode and a receiving endnode on the network, the method steps comprising the steps of claim 27.

48. The storage medium of claim 47, wherein the method steps comprise the steps of claim 28.

49. A system for transmitting data packets, comprising:

a computer network including a sending endnode and a receiving endnode;

means for selecting a window size which limits the amount of outstanding data, outstanding data being data that has been sent in a data packet from the sending endnode but has not yet been acknowledged by the receiving endnode;

means for selecting a metering interval which limits the rate at which data packets are placed for transmission; and

means for placing packets for transmission from the sending endnode to the receiving endnode at times which are determined in response to the window size and the metering interval.

50. The system of claim 49, wherein the means for selecting a window size comprises:

means for measuring packet throughput from the sending endnode to the receiving endnode at a plurality of different window sizes; and

means for selecting the smallest window size at which the measured packet throughput is greatest.

51. The system of claim 49, wherein the means for selecting a metering interval comprises:

means for measuring interpacket gaps between packets arriving at an endnode; and

means for determining the metering interval of the sending endnode based on the measured interpacket gaps.

52. A system for transmitting data packets, comprising:

a computer network including a sending endnode and a receiving endnode;

means for dynamically selecting a preferred window size which limits the amount of outstanding data by measuring packet throughput from the sending endnode to the receiving endnode and determining the preferred window size based on the measured packet throughput, outstanding data being data that has been sent in a data packet from the sending endnode but has not yet been acknowledged by the receiving endnode; and

means for placing packets for transmission from the sending endnode to the receiving endnode such that the window size is an upper bound on the number of unacknowledged packets.

53. A system for transmitting data packets, comprising:

a computer network including a sending endnode and a receiving endnode;

means for associating a plurality of logical connections with a single transport session;

means for placing a packet for transmission from the sending endnode to the receiving endnode over at least one of the connections during the session; and

means for selecting a metering interval which limits the rate at which packets are placed on the network, and wherein the placing means places packets on the network for transmission from the sending endnode to the receiving endnode at times which are determined in response to metering interval.