Method and system for measuring load and capacity on a variable capacity channel

• US 20040003107A1
• Filed: 06/28/2002
• Published: 01/01/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stratford, Neil, Black, Richard, Barham, Paul
• Granted Patent: US 7,296,083 B2
• Time in Patent Office: Days
• US Class Current: 709/235
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A method and system are presented for determining the loading and capacity on a variable capacity channel by measuring the times at which packets are enqueued for transmission, and have their transmission completed, or by measuring these times in addition to the arrival times of the packets. The times may be measured using a device driver or other operating system component. The measurement may be performed in a centralized or distributed fashion for multi-access or point to point channels.

Claims

1. In a computer network, a method comprising:

determining loading and capacity of a channel, including measuring the interval time between when a measured packet is queued for transmission and when the measured packet is actually transmitted; and

comparing data corresponding to the interval time with a nominal time for network packet transmission.

2. The method of claim 1 wherein the data corresponding to the interval time comprises a value determined by applying a statistical technique to the interval time of the measured packet and interval times of a plurality of other packets.

3. The method of claim 2 wherein a media access control protocol controls network communication, and wherein the comparison indicates the mean behavior of the media access control protocol.

4. The method of claim 1 wherein measuring the interval time comprises receiving data from the device driver.

5. The method of claim 1 wherein measuring the interval time comprises detecting at an additional operating system component at least one request from a device driver related to a system resource.

6. The method of claim 5 wherein detecting at least one request related to a system resource comprises detecting a request related to memory.

7. The method of claim 5 wherein detecting at least one request related to a system resource comprises detecting a request related to a handle.

8. The method of claim 5 wherein detecting at least one request related to a system resource comprises detecting a request related to a reference count.

9. The method of claim 5 wherein detecting at least one request related to a system resource comprises detecting a request related to a thread.

10. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

11. In a computer network, a method comprising:

obtaining a record set of at least one record, each record including a time of a transmit request of a packet and an arrival time of the packet, and

determining the load and capacity of a channel by inferring a queuing time, media access delays, and data-link retransmission from the record set.

12. The method of claim 11 wherein one computer in the network obtains the records from at least one other computer in the network.

13. The method of claim 11 wherein the records are each based on common time data available to each computer in the network.

14. The method of claim 13 where each packet is a broadcast packet such that the packet arrives at recipient computers at substantially the same time.

15. The method of claim 13, further comprising, establishing the common time data via a sequence of packets, each of which carries a sequence number and a local time of a source of the packet.

16. The method of claim 15 further comprising, at a computer that receives the packet, recording a local time when the packet arrived, and using a calculable nominal transmit time and a generalized regression method to determine an offset and drift between the local time and a time at the source of the packet.

17. The method of claim 11 wherein a plurality of record sets are obtained, each record set divided into distinct periods corresponding to a mean loading and capacity of the network during the corresponding period.

18. The method of claim 17 wherein the distinct periods are delineated by the sending of a broadcast packet on the network.

19. The method of claim 18 where each broadcast packet further includes load and capacity data for distributing the load and capacity data to recipient computers.

20. A computer-readable medium having computer-executable instructions for performing the method of claim 11.

21. In a computer network, a method comprising:

determining the loading and capacity of a channel, including;

1) measuring a first interval between when a packet is queued for transmission, and when the packet has completed transmission;

2) measuring a second interval between a packet having completed transmission and a subsequent packet being queued for transmission; and

3) computing a load value from a fraction of the second time over a total time, and a capacity value from the first time and a size of the transmitted packet.

22. The method of claim 21 where data corresponding to at least one of the time intervals is provided by a device driver.

23. The method of claim 21 where data corresponding to at least one of the time intervals is provided by an operating system based on requests for system resources received from a device driver.

24. The method of claim 21 where a plurality of packets are queued, and further comprising, measuring a third time interval corresponding to a time between occurrences of queuing packets, the load determined from a fraction of the time in which no packets are queued, and the capacity determined from at least one of either from the time to transmit a most recent packet or an interval and total amount of transmission since the last idle period of the channel.

25. A computer-readable medium having computer-executable instructions for performing the method of claim 21.

26. In a computer network, a method comprising:

measuring the interval time between when a measured packet is queued for transmission and when the measured packet is actually transmitted;

comparing data corresponding to the interval time with a nominal time for network packet transmission; and

determining loading and capacity of a channel based on the data comparison.

27. The method of claim 26 wherein measuring the interval time includes receiving data corresponding to the measuring time from a device driver that queues the packet for transmission.

28. The method of claim 27 receiving data corresponding to the measuring time comprises receiving a start time and a completion time.

29. The method of claim 26 wherein measuring the interval time includes detecting an operation of a device driver that queues the packet for transmission.

30. The method of claim 29 wherein detecting an operation of a device driver that queues the packet for transmission comprises receiving at least one request from the device driver that is related to memory usage.

31. The method of claim 30 wherein the device driver operation includes requesting allocation and deallocation of memory.

32. The method of claim 29 wherein detecting an operation of a device driver that queues the packet for transmission comprises receiving at least one request from the device driver that is related to a handle.

33. The method of claim 29 wherein detecting an operation of a device driver that queues the packet for transmission comprises receiving at least one request from the device driver that is related to a reference count.

34. The method of claim 33 wherein the device driver operation includes requesting an incrementing and decrementing of the reference count.

35. The method of claim 29 wherein detecting an operation of a device driver that queues the packet for transmission comprises receiving at least one request from the device driver that is related to a thread.

36. The method of claim 35 wherein the device driver operation corresponds to obtaining and releasing control of the thread.