Universal serial bus (USB) extension

[0001] This invention relates to data transmission and, more particularly, to an extended Universal Serial Bus (USB).

[0002] Devices (that is, computer peripherals such as printers, cameras, external storage, and the like) may be connected to a computer using various types of standard connections, one of which is the so-called USB (Universal Serial Bus).

[0003] The USB system/standard was designed and intended to support computer peripherals that are physically close to the computer—mostly these devices are expected to be located on the same desk as the computer itself or within the same room as the computer. The USB system is defined by a formal specification, the current version of which is USB 2.0 (dated Apr. 27, 2000), the entire contents of which are incorporated herein by reference. Under the USB 2.0 Specification, the maximum distance from a port on a computer (a so-called root port) to any supported device is thirty meters and is achieved, for example, using a series arrangement of five hubs and six five-meter cable segments.

[0004] The inventor has found that for certain applications, however, it necessary or desirable to enable USB functionality at distances greater than thirty meters. For certain applications, USB functionality is desired at distances of at least one hundred meters and preferably at distances of seven hundred and fifty meters or more (for copper and fiber link products respectively).

[0005] For example, in a KVM (“Keyboard, Video, Mouse”) system, a target or host computer may be controlled and accessed by peripheral devices (possibly connected to another computer) that are possibly located some distance away from the target computer. In such cases, it is desirable to be able to connect all kinds of peripheral devices, including USB devices, to the host computer.

[0006] Thus, in at least one aspect, the present invention provides a USB system/extension that allows for the transmission of data over greater distances than contemplated by the USB standard.

[0017] FIG. 1 depicts a typical KVM system 100 in which the USB extension of the present invention may operate. This system is described only by way of example, and should not be limiting on the invention. One skilled in the art would realize that the invention described may be used in a KVM system such as the one described here or in any other environment in which a USB device is used. As shown in FIG. 1, a host computer 102 is remotely accessed and operated by a remote computer 110. More specifically, a keyboard 104 and mouse 106 connected to the remote computer 110 are used to provide, respectively, keyboard and mouse control signals to the appropriate ports on the host computer 102. The video display output of the host computer 102 is rendered on a video display monitor 108 of the remote computer. The host and remote computers may be connected via, for example, a communication channel 111 which may pass though a known KVM switch (not shown), such as, for example, a KVM switch produced by Avocent Corporation.

[0018] For the sake of discussion, it is convenient to refer to the side of the remote computer 110 as the remote side (shown by the dashed line 112 in FIG. 1) and to the side of host computer 102 as the host side (shown by the dashed line 114 in FIG. 1).

[0019] In addition to connecting the keyboard 104, mouse 106 and monitor 108 to the host computer (via a remote computer and/or a switch), one or more remotely-located (for example, on the remote side 112) USB devices 116-1, 116-2, . . . may also be connected to the host computer 102. As shown in FIG. 1, the USB devices 116-j are preferably connected to USB hub 117 which connects to a USB remote connector 118 on the remote side 112. The USB remote connector 118 is connected (by a communication channel or link 120) to a USB host connector 122 (on the host side 114). The USB host connector 122 preferably connects to the host computer 102 via its standard USB port 124. As far as the host computer 102 is concerned, it is dealing with a standard USB device. Similarly, each USB device 116-j may be a standard USB device (for example, a computer peripheral such as a printers, camera, external storage, and the like). (The communication link 120 and the communication channel 111 are shown in the drawing as separate channels. In an actual implementation, these logical channels may share the same physical device, e.g., a fiber cable or a CAT5 wire.)

[0020] The USB remote connector 118 and USB 2.0 hub 117 may be separate components or may be integral in a single device, such as, for example, a molded cable or connector or the like.

[0021] FIG. 2 shows the logical structure of the USB host connector 122 and the USB remote connector 118 according to embodiments of the present invention. As shown in FIG. 2, the USB host connector 122 includes a USB PHY (USB Physical Layer) 126 for connection to a USB port of a host computer. The USB PHY 126 connects to upstream FPGA (Field Programmable Gate Array) 128, preferably via a USB 2.0 Transceiver Macrocell Interface (UTMI) connection. UTMI is defined, for example, in “USB 2.0 Transceiver Macrocell Interface (UTMI) Specification,” Version 1.05, published by Intel Corporation, Mar. 29, 2001, the entire contents of which are incorporated herein by reference. One skilled in the art will realize that other forms of connection interface, e.g., UTMI Plus, may be used here and are within the scope of the invention.

[0022] On the downstream side, the USB remote connector 118 includes a downstream FPGA 130 connected, preferably via a UTMI connection, to a USB PHY 132 which is connected to a USB 2.0 hub 117. Various USB devices may be connected to each of the hub's ports (as shown at “A” in the drawing). Preferably the USB 2.0 hub 117 has one to seven USB ports. Details of the upstream FPGA 128 and downstream FPGA 130 are given below.

[0023] The term “host” as used herein generally refers to the host computer system where the USB Host Controller is installed. This includes the host hardware platform (CPU, bus, etc.) and the operating system in use. The terms “upstream” and “downstream” are generally used herein consistent with the USB 2.0 standard. Thus, “downstream” refers to the direction of data flow from the host or away from the host. A downstream port is the port on a hub electrically farthest from the host that generates downstream data traffic from the hub. Downstream ports receive upstream data traffic. Conversely, “upstream” refers to the direction of data flow towards the host. An upstream port is the port on a device electrically closest to the host that generates upstream data traffic from the hub. Upstream ports receive downstream data traffic.

[0024] Communications link 120 is preferably a single cable. The communications link 120 may be integrally connected with the USB host connector 122 on one end and the USB remote connector 118 on the other end thereof or it may be constructed and adapted to be connected thereto. The cable may be of various lengths, ranging, in preferred embodiments, from 100 meters to 750 meters. Cable lengths of greater than 750 meters are possible and are contemplated by the inventor using the present invention, but may provide diminished performance for some types of USB devices. In some embodiments, appropriate transceivers (for example, transceivers 134, 136 in FIG. 2) or the like are used on either end of the communications link 120 to facilitate communication over the communications link 120. The transceivers 134 and/or 136 may be integral with the USB host connector 122 and/or USB remote connector 118, respectively, or they may be separate components. For example, the communications link 120 may comprise fiber optic cable and the transceivers 134, 136 may be optical transceivers connecting the upstream FPGA 128 to one of the cable and the downstream FPGA 130 to the other end thereof.

USB 2.0 Transactions

[0025] USB 2.0 defines various types of packets (described in greater detail below). The standard USB transaction order is: token packet; optional data packet; and optional response packet.

[0026] The USB standard defines strict response deadlines—the deadline for a USB response to a high-speed packet is approximately 1.5 microseconds. The round-trip delay though 750 meters of fiber is about 7.5 microseconds in the fiber media alone (˜5 ns per meter each way). Accordingly, in some aspects, this invention provides a mechanism/algorithm to deal with the delays inherent in the length of the communications link 120. The inventor has realized that the round-trip time delay imposed by extension requires that the initial response to any packet transmission that expects a response should be generated on the same side of the link that sent that transmission. This process is referred to herein as the spoofing algorithm.

[0027] USB data flow and packet types are strictly defined in the USB specification (for example, in the USB 2.0 Specification at Chapter 8, “Protocol Layer”). There are essentially four types of packets, namely tokens (OUT, IN, SOF and SETUP), data (DATA0, DATA1, DATA2 and MDATA), handshake (ACK, NAK, STALL, NYET) (synchronization) and special (PRE, ERR, SPLIT & PING). All token packets originate inside the host computer and flow downstream toward the device end.

[0028] All packets begin with a synchronization (SYNC) field. It is used by the input circuitry to align incoming data with the local clock. A SYNC from an initial transmitter is defined in USB 2.0 to be eight bits in length for full/low-speed and 32 bits for high-speed. Received SYNC fields may be shorter. SYNC serves only as a synchronization mechanism. The last two bits in the SYNC field are a marker that is used to identify the end of the SYNC field and, by inference, the start of the PID.

[0029] All USB 2.0 packets have distinct Start- and End-of-Packet delimiters. The Start-of-Packet (SOP) delimiter is part of the SYNC field.

[0030] A packet identifier (PID) immediately follows the SYNC field of every USB 2.0 packet. A PID consists of a four-bit packet type field followed by a four-bit check field. The PID indicates the type of packet and, by inference, the format of the packet and the type of error detection applied to the packet. The four-bit check field of the PID ensures reliable decoding of the PID so that the remainder of the packet is interpreted correctly. The PID check field is generated by performing a one's complement of the packet type field. A PID error exists if the four PID check bits are not complements of their respective packet identifier bits.

[0031] According to USB 2.0, the host and all functions must perform a complete decoding of all received PID fields. Any PID received with a failed check field or which decodes to a non-defined value is assumed to be corrupted and it, as well as the remainder of the packet, should be ignored by the packet receiver. If a function receives an otherwise valid PID for a transaction type or direction that it does not support, the function must not respond. PID types, codings, and descriptions are listed in the following table (Table 1).

[0032]

TABLE 1
	PID
PID TYPE	NAME	PID<3:0>	DESCRIPTION
Token	SOF	0101B	Start-of-Frame marker and frame
			number
Token	OUT	0001B	Address + endpoint number in
			host-to-function transaction
Token	IN	1001B	Address + endpoint number in
			function-to-host transaction
Token	SETUP	1101B	Address + endpoint number in
			host-to-function transaction for
			SETUP to a control pipe
Data	DATA0	0011B	Data packet PID even
Data	DATA1	1011B	Data packet PID odd
Data	DATA2	0111b	Data packet PID high-speed,
			high bandwidth isochronous
			transaction in a microframe
Data	MDATA	1111B	Data packet PID high-speed for
			split and high bandwidth
			isochronous transactions
HANDSHAKE	ACK	0010B	Receiver accepts error-free data
			packet
HANDSHAKE	NAK	0101B	Receiving device cannot accept
			data or transmitting device
			cannot send data
HANDSHAKE	STALL	1110B	Endpoint is halted or a control
			pipe request is not supported
HANDSHAKE	NYET	0110B	No response yet from receiver
SPECIAL	PRE	1100B	(Token) Host-issued preamble.
			Enables downstream bus traffic
			to low-speed devices.
SPECIAL	ERR	1100B	(Handshake) Split Transaction
			Error Handshake (reuses PRE
			value)
SPECIAL	SPLIT	1000B	(Token) High-speed Split
			Transaction Token
SPECIAL	PING	0100B	(Token) High-speed flow control
			probe for a bulk/control endpoint

[0033] FIGS. 3-6 show packet formats for token, data, and handshake packets. Fields within a packet are displayed in these figures in the order in which bits are shifted out onto the bus according to the USB 2.0 Specification. One of ordinary skill in the art would realize that the invention is not limited to these orderings, and that embodiments of the invention may be implemented to deal with different packet formats and bit orders.

[0034] FIG. 3 shows the field formats for a token packet. A token consists of a PID, specifying either IN, OUT, or SETUP packet type and ADDR and ENDP (endpoint) fields. The PING special token packet also has the same fields as a token packet. For OUT and SETUP transactions, the address and endpoint fields uniquely identify the endpoint that will receive the subsequent Data packet. For IN transactions, these fields uniquely identify which endpoint should transmit a Data packet. For PING transactions, these fields uniquely identify which endpoint will respond with a handshake packet. Only the host can issue token packets. An IN PID defines a Data transaction from a function to the host. OUT and SETUP PIDs define Data transactions from the host to a function. A PING PID defines a handshake transaction from the function to the host.

[0035] Token packets have a five-bit CRC (Cyclic Redundancy Check) that covers the address and endpoint fields as shown above. The CRC does not cover the PID, which has its own check field. Token and SOF packets are delimited by an EOP after three bytes of packet field data. If a packet decodes as an otherwise valid token or SOF but does not terminate with an EOP after three bytes, it must be considered invalid and ignored by the receiver.

[0036] USB 2.0 defines a special token (SPLIT) for so-called split transactions. This is a four-byte token packet compared to other normal three-byte token packets. The split transaction token packet provides additional transaction types with additional transaction specific information. The split transaction token is used to support split transactions between the host controller communicating with a hub operating at high speed with full-/low-speed devices to some of its downstream facing ports. There are two split transactions defined that use the SPLIT special token: a start-split transaction (SSPLIT) and a complete-split transaction (CSPLIT). A field in the SPLIT special token indicates the specific split transaction.

[0037] A high-speed split transaction is used only between the host controller and a hub when the hub has full-/low-speed devices attached to it. This high-speed split transaction is used to initiate a full-/low-speed transaction via the hub and some full-/low-speed device. The high-speed split transaction also allows the completion status of the full-/low-speed transaction to be retrieved from the hub. This approach allows the host controller to start a full-/low-speed transaction via a high-speed transaction and then continue with other high-speed transactions without having to wait for the full-/low-speed transaction to proceed/complete at the slower speed.

[0038] A high-speed split transaction has two parts: a start-split and a complete-split. Split transactions are only defined to be used between the host controller and a hub. No other high-speed or full-/low-speed devices ever use split transactions.

[0039] According to the USB 2.0 specification, Start-of-Frame (SOF) packets are issued by the host at a nominal rate of once every 1.00 ms±0.0005 ms for a full-speed bus and 125 μs±0.0625 μs for a high-speed bus. SOF packets consist of a PID indicating packet type followed by an 11-bit frame number field as illustrated in FIG. 4. The SOF token comprises the token-only transaction that distributes an SOF marker and accompanying frame number at precisely timed intervals corresponding to the start of each frame. All high-speed and full speed functions, including hubs, receive the SOF packet. The SOF token does not cause any receiving function to generate a return packet; therefore, SOF delivery to any given function cannot be guaranteed.

[0040] A data packet consists of a PID, a data field containing zero or more bytes of data, and a CRC of the data, as shown in FIG. 5. There are four types of data packets, identified by differing PIDs: DATA0, DATA1, DATA2 and MDATA. Two data packet PIDs (DATA0 and DATA1) are defined to support data toggle synchronization. All four data PIDs are used in data PID sequencing for high bandwidth high-speed isochronous endpoints. Three data PIDs (MDATA, DATA0, DATA1) are used in split transactions.

[0041] According to the USB specification, data must always be sent in integral numbers of bytes. The data CRC is computed over only the data field in the packet and does not include the PID, which has its own check field. The maximum data payload size allowed for low-speed devices is 8 bytes. The maximum data payload size for full-speed devices is 1023. The maximum data payload size for high-speed devices is 1024 bytes.

[0042] Handshake packets, as shown in FIG. 6, consist of only a PID. Handshake packets are used to report the status of a data transaction and can return values indicating successful reception of data, command acceptance or rejection, flow control, and halt conditions. Only transaction types that support flow control can return handshakes. Handshakes are always returned in the handshake phase of a transaction and may be returned, instead of data, in the data phase. Handshake packets are delimited by an EOP after one byte of packet field. If a packet decodes as an otherwise valid handshake but does not terminate with an EOP after one byte, it must be considered invalid and ignored by the receiver.

[0043] There are four types of handshake packets and one special handshake packet:

[0044] ACK indicates that the data packet was received without bit stuff or CRC errors over the data field and that the data PID was received correctly. ACK may be issued either when sequence bits match and the receiver can accept data or when sequence bits mismatch and the sender and receiver must resynchronize to each other. An ACK handshake is applicable only in transactions in which data has been transmitted and where a handshake is expected. ACK can be returned by the host for IN transactions and by a function for OUT, SETUP, or PING transactions.

[0045] NAK indicates that a function was unable to accept data from the host (OUT) or that a function has no data to transmit to the host (IN). NAK can only be returned by functions in the data phase of IN transactions or the handshake phase of OUT or PING transactions. The host can never issue NAK.

[0046] NAK is used for flow control purposes to indicate that a function is temporarily unable to transmit or receive data, but will eventually be able to do so without need of host intervention.

[0047] STALL is returned by a function in response to an IN token or after the data phase of an OUT or in response to a PING transaction. STALL indicates that a function is unable to transmit or receive data, or that a control pipe request is not supported. The state of a function after returning a STALL (for any endpoint except the default endpoint) is undefined. The host is not permitted to return a STALL under any condition.

[0048] The STALL handshake is used by a device in one of two distinct occasions. The first case, known as “functional stall,” is when the Halt feature associated with the endpoint is set. A special case of the functional stall is the “commanded stall.” Commanded stall occurs when the host explicitly sets the endpoint's Halt feature. Once a function's endpoint is halted, the function must continue returning STALL until the condition causing the halt has been cleared through host intervention. The second case, known as “protocol stall.” Protocol stall is unique to control pipes. Protocol stall differs from functional stall in meaning and duration. A protocol STALL is returned during the Data or Status stage of a control transfer, and the STALL condition terminates at the beginning of the next control transfer (Setup).

[0049] NYET is a high-speed only handshake that is returned in two circumstances. NYET is returned by a high-speed endpoint as part of the PING protocol described later in this chapter. NYET may also be returned by a hub in response to a split-transaction when the full-/low-speed transaction has not yet been completed or the hub is otherwise not able to handle the split-transaction.

[0050] ERR is a high-speed only handshake that is returned to allow a high-speed hub to report an error on a full-/low-speed bus. It is only returned by a high-speed hub as part of the split transaction protocol.

[0051] Transmitting and receiving functions must return handshakes based upon a specific order of precedence. The order for USB 2.0 is detailed in the following tables (Tables 2-4). Not all handshakes are allowed, depending on the transaction type and whether the handshake is being issued by a function or the host. Note that if an error occurs during the transmission of the token to the function, the function will not respond with any packets until the next token is received and successfully decoded.

[0052] Table 2 shows the possible responses a function may make in response to an IN token. If the function is unable to send data, due to a halt or a flow control condition, it issues a STALL or NAK handshake, respectively. If the function is able to issue data, it does so. If the received token is corrupted, the function returns no response.

[0053]

TABLE 2
Function Responses to IN Transactions
		Function
	Function Tx	Can
Token Received	Endpoint Halt	Transmit
Corrupted	Feature	Data	Action Taken
Yes	Don't care	Don't care	Return no response
No	Set	Don't care	Issue STALL
			handshake
No	Not set	No	Issue NAK
			handshake
No	Not set	Yes	Issue data packet

[0054] Table 3 shows the host response to an IN transaction. The host is able to return only one type of handshake: ACK. If the host receives a corrupted data packet, it discards the data and issues no response. If the host cannot accept data from a function, this condition is considered to be an error and the host returns no response. If the host is able to accept data and the data packet is received error-free, the host accepts the data and issues an ACK handshake.

[0055]

TABLE 3
Host Responses to IN Transactions
	Data Packet	Host Can Accept	Handshake Returned by
	Corrupted	Data	Host
	Yes	N/A	Discard data, return no
			response
	No	No	Discard data, return no
			response
	No	Yes	Accept data, issue ACK

[0056] Handshake responses for an OUT transaction are shown in Table 4. Assuming successful token decode, a function, upon receiving a data packet, may return any one of the three handshake types. If the data packet was corrupted, the function returns no handshake. If the data packet was received error-free and the function's receiving endpoint is halted, the function returns STALL. If the transaction is maintaining sequence bit synchronization and a mismatch is detected, then the function returns ACK and discards the data. If the function can accept the data and has received the data error-free, it returns ACK. If the function cannot accept the data packet due to flow control reasons, it returns NAK.

[0057]

TABLE 4
Function Responses to OUT Transactions in Order of Precedence
Data	Receiver		Function	Handshake
Packet	Halt	Sequence	Can Accept	Returned by
Corrupted	Feature	Bits Match	Data	Function
Yes	N/A	N/A	N/A	None
No	Set	N/A	N/A	STALL
No	Not set	No	N/A	ACK
No	Not set	Yes	Yes	ACK
No	Not set	Yes	No	NAK

[0058] SETUP defines a special type of host-to-function data transaction that permits the host to initialize an endpoint's synchronization bits to those of the host. Upon receiving a SETUP token, a function must accept the data. A function may not respond to a SETUP token with either STALL or NAK, and the receiving function must accept the data packet that follows the SETUP token. If a non-control endpoint receives a SETUP token, it must ignore the transaction and return no response.

The Upstream FPGA 128

[0059] An implementation of the upstream (or host) FPGA 128 according to embodiments of the present invention is now described with reference to the logical-block diagram of FIG. 7.

[0060] The upstream FPGA 128 receives signals (RXD) from downstream, via the transceiver (134 in FIG. 2), using a link receiver (Rx) port 140. Circuitry (a SERDES—serializer/de-serializer, not shown) between the receiver 134 and the link Rx 140 de-serializes the data it receives from downstream to form 9-bit bytes which are passed to the link Rx 140. Similarly, upstream FPGA 128 sends signals (TXD) in the downstream direction (via transceiver 134) using link transmitter (Tx) 142. Data passed downstream via the receiver 134 are first serialized by circuitry (a SERDES, not shown) between the Link Tx 142 the tranreceiver.

[0061] Actual USB signals from the host are input to the upstream FPGA 128 (from the USB PHY 126) (shown in the drawing as Udatai and ULines). The USB PHY (Physical Interface) 126 essentially performs a serialization (and de-serialization) of the actual USB serial data that comes off the USB. The USB PHY 126 performs high-speed parallel to serial conversion when it is about to transmit on the USB, and it does the high-speed serial-to-parallel conversion when it receives incoming data from the USB.

[0062] Udatai are inbound signals from the USB PHY 126. The Udatai signals are input to USB receiver 144 and the Ulines signals (2 bits) are input to USB host chirp 146. The Udata are passed from the USB receiver 144 to a token checker 148 which passes them via pass-through FIFO 150 to link transmitter 142 which sends them downstream. The pass-through FIFO 150 is used to switch from the clock domain of the FPGA (greater than 60 MHz, preferably at least 62.5 MHz) to the USB 60 MHz clock domain. Since the Udata are passed downstream, at some point a result should be obtained from the downstream end. Accordingly, the upstream FPGA 128 maintains a number of FIFOs to deal with the incoming downstream data. While one FIFO would suffice, in preferred embodiments, the system includes deep FIFOs 152 and shallow FIFOs 154. The deep FIFOs 152 are used to store responses (for example, to IN tokens) that might include data. The shallow FIFOs 154 are used to store acknowledgments (for example, ACK, NAK responses). In one present implementation, there are seven deep FIFOs, each of 577 bytes, and seven shallow FIFOs, each having 15 bytes. The deep FIFO should be able to handle at least 515 bytes in order to deal with 512 byte data from downstream (3 bytes are used for overhead). However, in order to deal with the worst case (i.e., largest possible) block—1024 bytes, in preferred embodiments, each FIFO entry should be 1027 bytes. The invention is not limited to the number or size of the FIFOs in the current implementation. One skilled in the art will realize that the numbers and sizes of the deep and shallow FIFOs depends, in part, on the amount of memory available in the FPGA.

[0063] The token check 148 evaluates the current transaction to determine what kind of transaction is being sent and whether or not that transaction has been seen before. If the transaction has not been seen before, it is added to the content addressable memory (TCAM—Token CAM 155) and sent down the link (link Tx 142, via link FIFO 150). TCAM Master 156 selects one of the FIFOs 152, 154 to receive the expected response (when it is received from downstream). TCAM Master 156 selects from deep FIFOs 152 if data are expected back or shallow FIFOs 154 if only acknowledgements are expected back (for example, an OUT token). TCAM Master 156 tracks which FIFOs have been allocated to which tokens.

[0064] When data are received on the link receiver 140, the data are input to the appropriate FIFO 152, 154 as designated by a pointer (Xselect) from the TCAM Master 156 via the pointer FIFO 158. Xselect is a bus that contains a pointer that comes out of TCAM Master 156 that indicates where to put a response when one comes back from the downstream. (Split tokens are handled in a similar manner, using SCAM (Split Token CAM) 157 and SCAM Master 159.

[0065] The injector 160 is essentially a multiplexing switch (MUX) that selects between one of the FIFOs 152, 154 and an output from the host spoof master 162. Whenever data are received from a FIFO 152, 154, that data represent an actual, real response from the other end of the link. On the other hand, data from the host spoof master 162 (Sdata), represent a spoofed response (according to the spoofing algorithm).

[0066] So, when the system spoofs, it directs the injector 160 to use the Sdata from the host spoof master 162 and to send that data (via USB Transmit 164) to the USB host (as UDatao). When the system has a real response in one of the FIFOs 152, 154, that response is picked by the injector 160 and sent to the USB host. Udatao are outbound data to the USB PHY 126.

[0067] As noted above, in some current implementations, there are seven deep FIFOs, each of 577 bytes, and seven shallow FIFOs, each having 15 bytes. In those embodiments, the injector 160 is a fifteen-way multiplexer (fourteen ways for the FIFOs 152, 154), and one for the output of the host spoof master 162. In general, if there are N deep FIFOs and M shallow FIFOs, the injector 160 will effectively be an N+M+1 multiplexer.

[0068] In order for the system to associate incoming packets (from downstream) with spoofed packets, a signature for each spoofed packet is stored in the CAM. FIG. 8 shows a layout of a CAM on the upstream FPGA according to embodiments of the present invention. The device id, endpoint and PID fields are derived from the token being spoofed.

[0069] The system maintains the status of each entry in the CAM. In preferred embodiments, the system uses two bits to maintain the status of each entry. One status bit is used to indicate whether or not a received packet is new (or already in the CAM). The other status bit is used to indicate whether or not the FIFO is ready (that is, whether or not the FIFO holds an actual response from downstream).

The Downstream FPGA 130

[0070] An implementation of the downstream (or hub) FPGA 130 according to embodiments of the present invention is now described with reference to the logical block diagram of FIG. 9.

[0071] A downstream FPGA 130 includes a link receiver 170 which connects to a link transceiver (136 in FIG. 2), which, in turn, connects to a cable (for example, to a fiber cable via an optical link) in order to receive signals from the upstream. The link receiver 170 passes incoming data to a pass-through FIFO 172 to host emulator 174. Output from the host emulator 174 is passed to FIFO 176 which passes the data to link transmitter 178. The host emulator 174 also passes data to the HUB USB Transmit 180 which sends it to the USB PHY (132 in FIG. 2) via a physical bus interface 182, which, in turn, provides the data to the hub 117 and then to the device. Host emulator 174 also receives USB device data via the physical bus interface and USB Receiver 184.

[0072] According to the USB 2.0 specification, a high speed capable device (such as, for example, a high-speed capable hub) advertises its high speed ability during the USB reset time by emitting a series of short chirp signals directed upstream. After doing so, it then listens for a response from the upstream controller. An upstream full-speed only USB controller will completely ignore these incoming chirps, but a high-speed capable one should shift into high-speed mode and respond with its own distinctive chirp sequence to notify the downstream device that it too is ready for high speed communications. This ritual exchange is called the “High-speed Detection Handshake” and is described in the USB 2.0 specification. If the handshake ritual is not completed then both ends remain in full-speed or low-speed (USB 1.1 compatible) mode.

[0073] In preferred embodiments of the present invention, the USB host chirp 146 (FIG. 7) and the USB hub chirp 183 (FIG. 9) are used to perform aspects of this handshake. The handshake differs from the usual one in that the chirp response pulse train sent as a response to the USB Hub lasts longer than usual because it does not end until it gets a signal from the host end indicating that is has some real chirps from the host PC. In other aspects, it follows the standard protocol.

Spoofing

[0074] A spoofing algorithm/mechanism according to embodiments of the present invention is now described in greater detail with respect to its operation on certain tokens. In the description that follows, the term “spoofer”, “spoof mechanism” and “spoof master” are used interchangeably to refer to the circuitry constructed and adapted to carry out aspects of the spoofing algorithm described herein. As described in greater detail below, the spoof algorithm is preferably implemented in FPGAs on the host and hub ends.

SOF Tokens

[0075] The SOF token does not elicit any response from the hub/device end. As many as two consecutive SOF packets may be missed due to bit errors and the hub will still send the SOFs to its own downstream ports at the correct time. The arrival time of all incoming SOF packets at the hub itself is important and needs to be tightly controlled, but this is unrelated to spoofing. Accordingly, as far as the spoofing logic is concerned, SOF packets can be sent downstream without any further action.

OUT Tokens

[0076] An OUT token packet indicates that the immediately following data packet will transfer data to an endpoint destination on the hub/device end. A DATA packet sent toward the device end will follow the OUT packet, and the device will normally acknowledge the data with a handshake ACK packet, unless there has been corruption of either of the packets, in which case no acknowledge packet will be returned. Thus, the valid responses to an OUT packet from the hub end of the link are: no response, STALL, ACK (acknowledge), and NAK (negative acknowledge). The spoofer at the host end has no way to know or guess which one of these four possibilities will eventually be returned, but it must fake (spoof) some kind of response to the host before the USB timeout deadline or the host will conclude a “no response” has occurred. When the host receives a NAK, it will resend the OUT and the same DATA. Accordingly, for OUT packets, the spoofing scheme performs the following (with reference also to the flow diagram in FIG. 10):

• • [0077] 1. Ship both packets (OUT and DATA) downstream (if they are “new” and have not already been sent). A token is considered to be “new” if it is not stored in the CAM. If the token is new, it is stored in the CAM and sent.
  • [0078] 2. NAK the host (this is a spoofed NAK).
  • [0079] 3. Wait for the actual response from downstream.
  • [0080] 4. When an actual response arrives from downstream, store that actual response, preferably in an indexed memory (FIFO) (for example, as described below with reference to FIG. 14).
  • [0081] 5. When the host tries to send the same OUT token again, discard (and do not send) the OUT or the associated data packet, if an actual response has been received, retrieve the actual response (that was stored in step 4) and respond to the host with the stored answer. Now clear the CAM entry so that future responses from the host will be considered new and go through. If the host tries to send the same OUT/DATA before an actual response is received (and stored), respond to the host with a (spoofed) NAK. (The upstream FPGA effectively acts as a gatekeeper, deciding which tokens will be passed downstream and which will be discarded.)

[0082] The host is thus falsely informed that the address/endpoint cannot accept the data, meanwhile that data is actually being delivered. The actual status of that delivery will be provided to the host as soon as it is known and asked for by the host again. Note that the host cannot distinguish between a spoofed response and a real response from downstream.

[0083] With reference to FIG. 7, when an OUT token is received by the USB receiver 144 of upstream FPGA 128, the token and associated data are sent downstream (via Link FIFO 150) and Link transmitter 142. The token check 148 determines that this is an OUT token and the TCAM Master 156 determines whether or not this token has been seen before (i.e., is it new or not). If needed, for a new entry, a CAM entry is allocated to this token and a space in the shallow FIFO 154 is allocated for the anticipated reply from downstream. The shallow FIFO 154 is used because the expected response to an OUT token will not include any data. At some time before the timeout period, the host spoof master 162 sends a spoofed NAK back to the host. When the actual response arrives from downstream, it is matched with the CAM entry and stored in the shallow FIFO 154. When the USB device next sends the same OUT token, the token and its associated data are discarded and the actual response to the original OUT token (now stored in the shallow FIFO 154, and addressable via data on the output select bus (FIG. 7)) is passed to the host. At that time the FIFO location in the shallow FIFO 154 can be released back to the system.

[0084] If an OUT/DATA pair eventually receives a NAK as the actual response from downstream, the host will retry the same OUT/DATA pair. Note, however, that this “OUT/DATA” pair will be considered “new” (not seen before), because there will be no corresponding entries in the CAM. In such cases, the “OUT/DATA” pair of tokens will be sent downstream by the FPGA (which will create new CAM entries for them).

[0085] On the downstream side, with reference to FIG. 9, when the downstream FPGA 130 receives an OUT token and associated DATA token, it passes them to the USB 2.0 hub which, in turn, provides them to the appropriate USB device.

[0086] An example of the operation of an embodiments of the present invention with an OUT token is shown in the data flow diagram in FIG. 11. An OUT and associated DATA token are received from the host at the upstream FPGA 128. The upstream spoofer passes both tokens downstream and issues a NAK to the host. (In the diagram, the spoofed token is shown in a bold, italicized font.) Because it received a NAK, the host issues the same OUT and DATA tokens again (denoted OUT₂ and DATA₂ in the drawing). Since the upstream FPGA 128 has not yet received a real response from downstream, it issues another NAK to the host. Once again, because it received a NAK, the host issues the same OUT and DATA tokens again (denoted OUT₃ and DATA₃ in the drawing). In the meantime, the downstream has received the OUT and DATA and returned an ACK. Now, when the host again re-issues the OUT and DATA tokens, the upstream FPGA can return the actual ACK to the host.

[0087] FIG. 11 (as are the other flow diagrams) is a simplified diagram. One skilled in the art will realize that other USB traffic (not shown in the drawings) may be active at this time. For example, SOFs or activity to other USB devices may take place between some of the tokens shown. (The “OUT/DATA” pairs are indivisible, but other, unrelated, USB activity can take place between the indivisible tokens.) For example, in FIG. 11, the host may send one or more tokens to other devices between DATA₂ and OUT₃.

IN Tokens

[0088] An IN token is similar to an OUT token, but an IN token is not followed by a DATA token, and the command is for data to be returned by the targeted address/endpoint of a device on the far end (downstream) of the link. The spoofing algorithm (with reference also to the flowchart in FIG. 12) performs the following:

• • [0089] 1. Transmit the IN token (if it is new and has not already been sent), and remember the token (for example, in the CAM).
  • [0090] 2. Spoof the host with a negative acknowledgement. This may be done, for example, by sending a NAK to the host (with a spoofed NAK) or by sending the host known bad data.
  • [0091] 3. Wait for the returned data/actual response (from downstream).
  • [0092] 4. [On hub end] ACK the returned data if its good, else give no response. (The data are considered good if the CRC check is okay.)
  • [0093] 5. Send the validated and newly ACKed (acknowledged) data packet to host end, but retain a copy in hub end memory. In some embodiments a copy is retained in case there is a need to resend, for example, because of a transmission error.
  • [0094] 6. Validate and store that returned data (that is, the actual response) in (preferably an indexed) memory on the host end.
  • [0095] 7. When that same IN token appears again [at some time in the future], fetch and respond with that stored validated data (actual response).

[0096] If the same IN token appears again before an actual response has been received, send a negative acknowledgement to the host and discard the token. The negative acknowledgement may be in the form of a NAK to the host (with a spoofed NAK). Alternatively, the host may be delayed by sending the host known bad data.

[0097] The host is falsely told that the address/endpoint cannot return the requested data, meanwhile that data are actually being fetched. The real data or the status of that fetch effort will be presented to the host as soon as it is known and asked for by the host again. In some embodiments, instead of (or as well as) sending a spoofed NAK, the upstream FPGA 128, while waiting for a real response from downstream, may send known bad data to the host (see, for example FIG. 13(b)). For example a 512 byte block of data with a bad CRC can be sent instead of a spoofed NAK. When the host decodes data with a guaranteed bad CRC, the host will throw the data away and ask again for the data. Thus, this known bad data will cause the host to delay (at least as long as it takes to receive the data and realize that the data are bad). (Note that the delay caused by the bad data is mostly caused by transmission of the data to the host.) Such a system can be used in combination with the spoofed NAKs. In some embodiments, a spoofed NAK may be sent if it is early in the microframe, and known bad data are sent if it is late in the microframe. In some embodiments, the size of the known bad data can be determined based on the size of a typical data block from the downstream device. So, for example, if a USB camera always sends a 512 byte packet of data, the spoofer will detect that and use that size packet for the bad data. In other words, the system can track the longest good data packet from a given endpoint and use that length for the size of the spoofed bad data packet.

[0098] Note that the returned data can be up 1027 bytes in length [PID, 1024, 2 byte CRC] and at least that much free storage space must be available on the host side. Note also that there are only two possible responses from the host: ACK and no response. According to the USB 2.0 specification, hosts will never issue NAK or STALL packets but are allowed to not respond, either due to detection of packet corruption or internal buffer conditions.

[0099] One skilled in the art will realize that it is within the scope of the invention to use only NAKs or only bad data or a combination thereof in order to cause the host to resend the tokens until the actual response is received from downstream. In general, the host needs to believe that it is communicating with a USB device, and the use of a spoofed NAK or bad data to delay the host are both acceptable. When multiple high-volume USB devices (for example, a camera and a USB memory) are both connected to the downstream hub, it may be preferable to use bad data rather than NAKs to delay the host.

[0100] With reference to FIG. 7, when a new IN token is received by the USB receiver 144 of upstream FPGA 128, the token is sent downstream (via Link FIFO 150) and Link transmitter 142. A CAM entry is allocated to this token and a space in the deep FIFO 152 is set aside for the anticipated reply from downstream. Unlike for the OUT token, here the deep FIFO 152 is used because the expected response to an IN token may include data. At some time before the USB timeout period (that is, before the host will timeout) the host spoof master 162 sends a spoofed response back to the host (a spoofed NAK or known bad data, as described above). When the actual response arrives from downstream, it is matched with the CAM entry and stored in the deep FIFO 152. When the USB device next sends the same IN token, the token is discarded (that is, not sent downstream) and the actual response to the original IN token (now stored in the deep FIFO 152, and addressable via output select bus (FIG. 7)) is passed to the host. At that time the FIFO location in the deep FIFO 152 can be released back to the system.

[0101] On the downstream side, with reference to FIG. 9, when the downstream FPGA 130 receives an IN token, it passes it via the 2.0 PHY (132, FIG. 2) to the USB 2.0 hub (117, FIG. 2) which in turn passes the appropriate USB device. When the device generates a reply, that reply is sent upstream. However, since the device may, itself, need a response from the host, the host emulator 174 sends the device a spoofed ACK (if the data are good), otherwise it gives no response. (The data are considered good if the CRC check is okay.) In addition, in some embodiments of the present invention, the downstream FPGA 130 may keep a copy of the validated and newly ACKed (acknowledged) data packet in hub-end memory. In some embodiments of the present invention, this data can be released up receipt of a “Got It” message from the upstream FPGA 128.

[0102] An example of the operation of the system with an IN token is shown in the data flow diagram in FIG. 13(a). The first IN token is received from the host by the upstream FPGA 128 and is sent downstream (since it has not been seen before). Room is set aside in the deep FIFO to receive the expected data from downstream. The upstream FPGA 128 sends a spoofed NAK to the host. When the next IN (denoted IN₂ in the drawing) is received from the host, it is discarded (because it is the same as one already being processed) and a spoofed NAK is again sent to the host. In the meantime the downstream device has responded to the IN token with DATA. Note that the actual data received from the USB device may be real data or it may be meta data (such as a NAK from the downstream device). As noted above, the host does not (cannot) distinguish between real NAKs and spoofed NAKs. (The reference “5” in the drawing corresponds to step 5 of the spoofing algorithm described above.) The downstream spoofer (host emulator in downstream FPGA 130) sends a spoofed ACK downstream. When the data reach the upstream FPGA 128, they are matched with the appropriate FIFO location and stored there. When the host next sends the IN token (denoted IN₃ in the drawing), the DATA from the deep FIFO is sent to the host.

[0103] Another example of the operation of the system according to embodiments of the present invention is shown in FIG. 13(b), wherein, in response to an IN token, the upstream FPGA may send known bad data to the host (instead of a NAK token). The bad data will cause the host to re-issue the IN token, as described above.

[0104] In some embodiments, for example, as shown here, the data from the USB device (if good data, that is, if it passes the CRC) is also stored on the downstream FPGA 130. In such cases, the upstream FPGA 128 will send the “Got It” meta token downstream to inform the downstream FPGA 130 that it can release the stored data.

SETUP Tokens

[0105] SETUP token packets are like OUT packets (including that they are followed by DATA packets), except they cannot be NAKed (negatively acknowledged). SETUP tokens must be acknowledged by the host spoofer if they are valid, but must be delivered without fail to their destination device/endpoint even if errors occur. Accordingly, for SETUP packets, the spoofing scheme performs the following (with reference also to the flowchart in FIG. 14):

• • [0106] 1. Transmit both packets (SETUP and associated DATA) and validate and store both.
  • [0107] 2. If both packets are good (that is, the CRC succeeds), ACK the host (with a spoofed ACK).
  • [0108] 3. Wait for the actual response from the hub end (either an ACK or a no response) meanwhile NAK any new non-SETUP packets and send nothing new downstream.
  • [0109] 4. If an ACK is received from the hub, return to normal packet processing else re-send both SETUP packets and try again.

[0110] Note that SETUP packets must be ACKed (if valid), but must be delivered without fail to their destination device/endpoint even if errors occur.

[0111] In some embodiments of the present invention, step 3 may be modified as follows: Instead of simply waiting indefinitely for a real ACK from downstream device (in response to the SETUP), the system tries to resend the SETUP one or more times (after appropriate delays). If no response is received after multiple attempts, a STALL token is sent to the host for this device. These embodiments allow the system to deal with a failure of one of multiple USB devices connected to a hub. Otherwise a SETUP token sent to a failed device would cause the system to freeze, not allowing any more tokens to any other devices. Note that for these embodiments it is necessary for the upstream FPGA to save a copy of the SETUP token until the real ACK has been received—the host will not resend the SETUP token because it has received the spoofed ACK.

[0112] FIG. 15 is an example of the operation of embodiments of the present invention with a SETUP token.

[0113] An example of USB 2.0 packet flow is shown in the block diagram in FIG. 16. On the USB side, the system operates at 60 MHz (60 Mbit/Sec.). Flow-through FIFOs are used to switch to a faster clock domain. In preferred embodiments, the second domain operates at 62.5 MHz.

Packaging

[0114] As noted above, the various components of the present invention may be packaged in a number of ways. For example, the upstream and/or downstream components may each be packaged together with an appropriate transceiver. Likewise, the cable connecting the upstream host to the downstream transceiver may be a separate component or it may be integral with the other components in some appropriate housing (for example, a molded cable or the like).

Cable Length

[0115] As noted above, the communication channel or link 120 may be of various lengths, ranging, in preferred embodiments, from 100 meters to 750 meters. Cable lengths of greater than 750 meters are possible and are contemplated by the inventor using the present invention, but may provide diminished performance for some types of USB devices.

[0116] FIG. 17 shows the format of a USB 2.0 microframe. One skilled in the art will realize that the length of the communication link 120 is related to the timing requirements of the USB microframe, since the microframe is used to synchronize the timing of the upstream end with the downstream end. Preferably the delay in the transmission is substantially constant and the hub end can rely on receiving an SOF indicator about every 125 microseconds (within a tolerance of ±0.0625 μs for a high-speed bus). The link must be of such a length that timing information on the hub end can be obtained from the successively arriving microframes. At the same time, some percentage of the microframe time will be lost to overhead, that is, to transmission time and to time used by the logic circuitry on either end.

[0117] Thus, one skilled in the art will realize that the length of the communications link 120 is a function of the delay in the link, the overhead of the processors and the acceptable loss due to overhead. For example, with an optical cable having a delay of 5 ns/meter (one way, 10 ns/meter round trip), a 750 meter cable would give a 7.5 microsecond round-trip delay. Even with 1.5 microseconds for processing overhead, the total overhead is less than 10% of the microframe.

[0118] If the communications link 120 is extended to a length the does not allow overlapping microframes (that is, does not allow synchronization using the microframes, then an asynchronous scheme must be used with a local time generator on the hub end.

[0119] Embodiments of the invention may use singlemode or multimode fiber cable for the communications link 120. Regular quality multimode fiber cable allows lengths of about 550 meters. Premium quality multimode fiber cable allows lengths of 750 meters or greater. If copper cables, e.g., CAT5 cables, are used, cable lengths of about 100-120 meters should be achieved.

[0120] A system according to embodiments of the present invention was built connecting a USB camera and mouse to a USB hub. The USB hub was connected to a USB 2.0 PHY which connected to the downstream FPGA. The downstream FPGA was connected via a pair of optical transceivers, using a 750 meter optical cable, to the upstream host FPGA which connected to a USB 2.0 PHY and then to a USB port on a host computer.

[0121] In some embodiments, it may be necessary to deliver packets in a deterministic or at least bounded manner. For instance, SOF packets should be delivered within ±62 ns of the ideal arrival time with respect to last one received (125 microseconds earlier). In such embodiments, a packet scheduling scheme may be used, with SOF getting highest priority.

[0122] For packet types other than SOF it may be desirable to know the worst-case additional latency due to packet contention with non-USB traffic. Accordingly, in some embodiments, time may be added on to the no-response time limit that the spoofing logic will need to count up to before it gives up on the other side.

[0123] In some embodiments may be desirable to actually measure link round trip delay prior to first use for the purpose of setting that timeout value as low as possible to maximize performance.

[0124] The present invention was described in some aspects with reference to a KVM system. One skilled in the art will immediately realize that the present invention is not limited to operating in such a system.

[0125] The present invention was described in some aspects with reference to the USB 2.0 standard. One skilled in the art would immediately realize that the invention will work with other USB standards and is not limited to the USB 2.0 standard.

[0126] While the invention has been described in connection with what is presently considered to be the most practical and preferred embodiment, it is to be understood that the invention is not to be limited to the disclosed embodiment, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.