System method for managing USB data transfers by sorting a plurality of endpoints in scheduling queue in descending order based partially on endpoint frequency

System and methods are provided for managing universal-serial-bus (USB) data transfers. An example system includes a non-transitory computer-readable storage medium including a first scheduling queue for sorting endpoints and a host controller. The host controller is configured to: store a plurality of endpoints for data transfers to the storage medium, an endpoint corresponding to a portion of a USB device; sort the plurality of endpoints in a first order; generate a first transmission data unit including multiple original data packets, the original data packets being allocated to the plurality of endpoints based at least in part on the first order; and transfer the first transmission data unit.

FIELD

The technology described in this patent document relates generally to data transfer and more particularly to data transfer management.

BACKGROUND

Universal Serial Bus (USB) is a standard developed to allow plug and play or hot swapping connectivity and to replace legacy serial and parallel ports between a host and peripheral devices. USB corresponds to a polled bus in which one or more attached peripheral devices (i.e., USB devices) share a bus bandwidth through a host-scheduled protocol. A USB device is allowed to be attached, configured, used, and detached while the host and other USB devices are operating.

Usually, USB data transfer occurs between a host and a USB device. When a USB device is first connected to a host, an enumeration process begins. A reset signal is sent to the USB device to determine a data rate of the USB device. Then, information associated with the USB device is read by the host and the USB device is assigned a unique address. A host controller directs raffle flow from/to the USB device. For example, the host controller executes USB operations to move data between host memory and device endpoints, where each device endpoint corresponds to a uniquely addressable portion of a USB device that is the source or sink of data in a communication flow between the host and the USB device.

Four basic types of data transfers are supported by USB specifications: control data transfer, bulk data transfer, interrupt data transfer, and isochronous data transfer. The control data transfer is often used for non-periodic, host software-initiated request/response communication (e.g., for command/status operations). The bulk data transfer is usually used for non-periodic, large-packet communication that can use any available bandwidth and can be delayed until the bandwidth is available. For example, data received by a printer in one big packet may be transferred using the bulk data transfer. In addition, the interrupt data transfer is often used for low-frequency, bounded-latency communication. For example, a mouse or a keyboard that sends very little data may use the interrupt data transfer. The isochronous data transfer, known also as streaming real time transfer, is usually used for periodic, continuous communication between a host and a USB device (e.g., communication involving time-sensitive information). For example, a streaming device (e.g., an audio speaker) may use the isochronous data transfer.

USB data transfers are scheduled by the host controller. For example, periodic data transfers, such as the isochronous data transfer and the interrupt data transfer, often have strict timing requirements, and thus need to move across the bus in a timely manner. Non-periodic data transfers, such as the bulk data transfer and the control data transfer, often do not have strict timing requirements. To ensure synchronization between the host and USB devices, the bus time is often divided into fixed-length segments. For low-speed or full-speed buses, the bus time is divided into 1 millisecond units, i.e., frames. For a high-speed bus, the bus time is divided into 125 microsecond units, i.e., microframes. A microframe includes multiple data packets, and a data packet includes 1 kbytes.

SUMMARY

In accordance with the teachings described herein, system and methods are provided for managing universal-serial-bus (USB) data transfers. An example system includes a non-transitory computer-readable storage medium including a first scheduling queue for sorting endpoints and a host controller. The host controller is configured to: store a plurality of endpoints for data transfers to the storage medium, an endpoint corresponding to a portion of a USB device; sort the plurality of endpoints in a first order; generate a first transmission data unit including multiple original data packets, the original data packets being allocated to the plurality of endpoints based at least in part on the first order; and transfer the first transmission data unit.

In one embodiment, a method is provided for managing universal-serial-bus (USB) data transfers. A plurality of endpoints are received for data transfers. An endpoint corresponds to a portion of a USB device. The plurality of endpoints are sorted in an order. A transmission data unit including multiple data packets is generated. The data packets are allocated to the plurality of endpoints based at least in part on the order. The transmission data unit is transferred.

In another embodiment, a non-transitory machine-readable storage medium includes programming instructions for managing universal-serial-bus (USB) data transfers. The programming instructions are configured to cause one or more data processors to execute certain operations. A plurality of endpoints are received for data transfers. An endpoint corresponds to a portion of a USB device. The plurality of endpoints are sorted in an order. A transmission data unit including multiple data packets is generated. The data packets are allocated to the plurality of endpoints based at least in part on the order. The transmission data unit is transferred.

DETAILED DESCRIPTION

Universal Serial Bus (USB) data transfers are usually initiated by a host that manages (e.g., schedules) periodic data transfers and non-periodic data transfers. To a large extent, the performance of a USB system depends on efficiency of data transfer management. Oftentimes, 80%-90% of the bandwidth of a USB bus is allocated to periodic data transfers. Thus, the management of periodic data transfers plays a critical role for improving the performance of the USB system.

FIG. 1depicts an example diagram showing a system for managing USB data transfers. As shown inFIG. 1, a host controller102sorts multiple endpoints (e.g., EP1, EP2, . . . , EPn) stored in a scheduling queue104in a particular order and allocates resources to the sorted endpoints according to the particular order for data transfers (e.g., periodic data transfers).

Specifically, the system100includes a number of USB devices1061,1062, . . . ,106mattached to a host108. Each of the multiple endpoints (e.g., EP1, EP2, . . . , EPn) corresponds to a uniquely addressable portion of a USB device. In some embodiments, each endpoint is associated with a frequency, and the host controller102sorts the endpoints based on the respective frequencies. For example, the host controller102may sort the endpoints in a descending order, where the endpoint with a highest frequency is stored at the top of the scheduling queue104and receives resources first for data transfer.

In certain embodiments, each endpoint is associated with an endpoint bandwidth for data transfer, and the host controller102sorts the endpoints based on the respective endpoint bandwidths. For example, the host controller102may sort the endpoints in a descending order, where the endpoint with a highest endpoint bandwidth is stored at the top of the scheduling queue104and receives resources first for data transfer. In some embodiments, the scheduling queue104is included in a memory device accessible to the host controller102.

The host controller102generates a transmission data unit (e.g., a microframe) that includes multiple data packets (e.g., 16 data packets). The data packets in the transmission data unit are allocated to the endpoints stored in the scheduling queue104(e.g., from top down). After the transmission data unit with allocated data packets is transmitted, the host controller102generates more transmission data units to perform data transfers (e.g., isochronous data transfers, interrupt data transfers, etc.) for the sorted endpoints.

FIG. 2depicts another example diagram showing a system for managing USB data transfers. As shown inFIG. 2, the host controller102manages two scheduling queues104and206for data transfers, where the scheduling queue104is used as a currently active queue and the scheduling queue206is used as a backup queue. After storing a new endpoint to the scheduling queue206, the host controller102sorts the scheduling queue206and switches from the scheduling queue104to the scheduling queue206for data transfers (e.g., periodic data transfers).

Particularly, when a new endpoint Epn+1 is received, the host controller102stores the new endpoint Epn+1 to the scheduling queue206that also includes the multiple endpoints (e.g., EP1, EP2, . . . , EPn), instead of the currently active queue104, so that the current operations of the system100are not disrupted. The host controller102sorts the endpoints (e.g., EP1, EP2, . . . , Epn, Epn+1) stored in the scheduling queue206, and switches from the scheduling queue104to the scheduling queue206so that the scheduling queue206becomes the active queue while the scheduling queue104serves as the backup queue. Subsequently, if another new endpoint is received, it will be stored to the scheduling queue104.

In some embodiments, the scheduling queue104and the scheduling queue206are included in a same memory device accessible to the host controller102, as shown inFIG. 3. For example, the scheduling queue104is processed from top down, and the scheduling queue206is processed from bottom up. In certain embodiments, the scheduling queue104and the scheduling queue206are included in different memory devices accessible to the host controller102. In some embodiments, not more than 80% of a transmission data unit is allocated for periodic data transfers, and the remaining transmission data unit is allocated for non-periodic data transfers (e.g., control data transfers, bulk data transfers, etc.). In certain embodiments, the data packets of the transmission data unit are allocated to up to three endpoints for periodic data transfers.

As an example, an available bandwidth for the system100is 16 packets per microframe. The host controller102manages data transfers for three isochronous endpoints (e.g., EP A, EP B, EP C). Particularly, the host controller102calculates a total bandwidth needed for the three endpoints, e.g., through a command processor by processing a configured endpoint command. If the total bandwidth needed is no more than the available bandwidth, the host controller102accepts the associated configuration. Otherwise, the host controller102generates an error signal.

Table 1 shows endpoint bandwidths associated with the three isochronous endpoints. As shown in Table 1, maximum endpoint-service-interval-time payloads corresponding to the three isochronous endpoints, EP A, EP B and EP C are 8 packets, 10 packets, and 12 packets, respectively. According to the respective transmission time intervals, these three endpoints have endpoint bandwidths of 8 packet per microframe, 4 packets per microframe, and 4 packets per microframe, respectively. The total bandwidth needed for this configuration is 16 packets per micro-frame, which is the same as the available bandwidth. Thus, the configuration is accepted. Data packets in a microframe (e.g., 16 data packets) may be allocated to the endpoints, EP A, EP B and EP C, according to the endpoint bandwidths.

FIG. 4depicts an example diagram showing data transfers for three endpoints. Data from the three endpoints (e.g., EP A, EP B and EP C) is transferred periodically using multiple microframes. As shown inFIG. 4, four microframes are transmitted consecutively, and the payloads of the three endpoints are divided to be transmitted among the four microframes.

Eight data packets in a first microframe402are allocated to the endpoint EP A first. An entire payload of the endpoint EP A is transmitted with the first microframe402. Then, eight data packets in the first microframe402are allocated to the endpoint EP B. No more data packets in the first microframe402are allocated to the low-priority endpoint EP C.

A second microframe404follows the first microframe402. As shown inFIG. 4, eight data packets in the second microframe404are allocated to the endpoint EP A first to transmit an entire payload of the endpoint EP A. Then, two data packets in the second microframe404are allocated to the endpoint EP B for the remaining payload that is not transmitted with the first microframe402. Six data packets remaining in the second microframe404are allocated to the endpoint EP C.

A third microframe406that follows the second microframe404is allocated similarly to the first microframe402. A fourth microframe408is used for the remaining payload (e.g., two data packets) of the endpoint EP B that is not transmitted with the third microframe406and the remaining payload (e.g., six data packets) of the endpoint EP C that is not transmitted with the second microframe404.

FIG. 5depicts another example diagram showing data transfers for three endpoints. As shown inFIG. 5, data from the three endpoints (e.g., EP A, EP B and EP C) is transferred periodically using multiple microframes. Specifically, in addition to the 16 data packets that are used for periodic data transfers, more data packets in a microframe may be reserved for periodic data transfers under certain circumstances.

As shown inFIG. 5, eight data packets in a first microframe502are allocated to the endpoint EP A first. An entire payload of the endpoint EP A is transmitted with the first microframe502. Then, eight data packets in the first microframe502are allocated to the endpoint EP B. No more data packets in the first microframe502are allocated to the low-priority endpoint EP C.

A second microframe504follows the first microframe502. As shown inFIG. 5, eight data packets in the second microframe504are allocated to the endpoint EP A first to transmit an entire payload of the endpoint EP A. Then, two data packets in the second microframe504are allocated to the endpoint EP B for the remaining payload that is not transmitted with the first microframe502. In addition to the six data packets remaining in the second microframe404, two more data packets are allocated to the endpoint EP C so that eight data packets of the payload of the endpoint EP C can be transmitted with the second microframe504.

A third microframe506that follows the second microframe504is allocated similarly to the first microframe502. A fourth microframe508is used for the remaining payload (e.g., two data packets) of the endpoint EP B that is not transmitted with the third microframe506and the remaining payload (e.g., four data packets) of the endpoint EP C that is not transmitted with the second microframe504. Dividing the payload of the endpoint EP C, 12 data packets, into an eight-packet part and a four-packet part complies with the requirements of the USB3 specification. For example, the number of data packets in a partial payload of an endpoint corresponds to a power of two (e.g., 1, 2, 4, 8, etc.).

In some embodiments, seven data packets corresponding to 15 μs are reserved as overflow bus time. For example, the available bandwidth for periodic data transfers is up to about 110 μs (or 50 data packets). The seven data packets reserved as overflow bus time may be used for periodic data transfers in addition to the available bandwidth under certain circumstances. The reserved data packets can be used for non-periodic data transfers (e.g., bulk data transfers, control data transfers) as well.

FIG. 6depicts an example diagram showing different cases for data transfer scheduling. As shown inFIG. 6, a bandwidth T1 (e.g., corresponding to 50 data packets) is set as a budget for periodic transfers in each microframe. Multiple data packets (e.g., seven data packets) are reserved as overflow bus time that can be used for periodic transfers under certain circumstances.

Specifically, in case a, data packets are allocated to multiple endpoints. The remaining data packets under the budget T1 are not enough for transmission of a payload602of an additional endpoint. However, the reserved data packets can be used together with the remaining data packets to transmit the payload602. Even though the rest of the reserved data packets may be enough for transmission of a payload604of another endpoint, such transmission is not scheduled because the budget T1 has been exceeded already.

In case b, the reserved data packets are used for transmission of a payload606of an endpoint. The rest of the reserved data packets may not be used for periodic data transfers, but may be used for non-periodic data transfers. In case c, after data packets are allocated to multiple endpoints, the remaining data packets under the budget T1 in combination with the reserved data packets are not enough for transmission of a payload of an additional endpoint. The payload of the additional endpoint may be divided into two parts, where the first part608(e.g., eight data packets) is transmitted with the current microframe and the second part610is scheduled for transmission with a next microframe.

FIG. 7depicts an example flow diagram for managing USB data transfers. At702, a plurality of endpoints are received for data transfers. An endpoint corresponds to a portion of a USB device and is associated with an endpoint bandwidth. At704, the plurality of endpoints are sorted in an order based at least in part on the endpoint bandwidths. At706, a transmission data unit including multiple data packets is generated. The data packets are allocated to the plurality of endpoints based at least in part on the order. At708, the first transmission data unit is transmitted.

This written description uses examples to disclose the invention, include the best mode, and also to enable a person skilled in the art to make and use the invention. The patentable scope of the invention may include other examples that occur to those skilled in the art. Other implementations may also be used, however, such as firmware or appropriately designed hardware configured to carry out the methods and systems described herein. For example, the systems and methods described herein may be implemented in an independent processing engine, as a co-processor, or as a hardware accelerator. In yet another example, the systems and methods described herein may be provided on many different types of computer-readable media including computer storage mechanisms (e.g., CD-ROM, diskette, RAM, flash memory, computer's hard drive, etc.) that contain instructions (e.g., software) for use in execution by one or more processors to perform the methods' operations and implement the systems described herein.