Source: https://patents.google.com/patent/US8843655B2/en
Timestamp: 2019-03-22 01:15:39
Document Index: 189473322

Matched Legal Cases: ['§371', 'Application No. 9910280', 'Application No. 9910280', 'Application No. 00', 'Application No. 00', 'Application No. 00']

US8843655B2 - Data transfer, synchronising applications, and low latency networks - Google Patents
Data transfer, synchronising applications, and low latency networks Download PDF
US8843655B2
US8843655B2 US13/802,400 US201313802400A US8843655B2 US 8843655 B2 US8843655 B2 US 8843655B2 US 201313802400 A US201313802400 A US 201313802400A US 8843655 B2 US8843655 B2 US 8843655B2
US13/802,400
US20130290558A1 (en
1999-05-04 Priority to GB9910280.8 priority Critical
1999-05-04 Priority to GB9910280A priority patent/GB2349717A/en
2000-05-03 Priority to PCT/GB2000/001691 priority patent/WO2000067131A2/en
2002-05-13 Priority to US98053902A priority
2005-08-05 Priority to US11/198,043 priority patent/US20060034275A1/en
2008-04-18 Priority to US12/105,412 priority patent/US8423675B2/en
2013-03-13 Priority to US13/802,400 priority patent/US8843655B2/en
2013-03-13 Application filed by AT&T Investments UK LLC filed Critical AT&T Investments UK LLC
2013-06-26 Assigned to AT&T LABORATORIES-CAMBRIDGE LTD. reassignment AT&T LABORATORIES-CAMBRIDGE LTD. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: HODGES, STEPHEN JOHN, POPE, STEVEN LESLIE, ROBERTS, DEREK EDWARD, MAPP, GLENFORD EZRA
2013-10-31 Publication of US20130290558A1 publication Critical patent/US20130290558A1/en
2014-07-29 Assigned to AT&T INVESTMENTS UK INC. reassignment AT&T INVESTMENTS UK INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: AT&T LABORATORIES-CAMBRIDGE LIMITED
2014-07-29 Assigned to AT&T INVESTMENTS UK LLC reassignment AT&T INVESTMENTS UK LLC CHANGE OF NAME (SEE DOCUMENT FOR DETAILS). Assignors: AT&T INVESTMENTS UK INC.
2014-09-23 Publication of US8843655B2 publication Critical patent/US8843655B2/en
Data transfer, synchronizing applications, and low latency networks are disclosed. An example method includes comparing a first address of a first data item of a first data burst to a second address of a last data item of a second data burst received before the first data burst; and, when the first address sequentially follows the second address, combining the first and second data bursts to form a third data burst.
This patent arises from a continuation of U.S. patent application Ser. No. 12/105,412, filed Apr. 18, 2008, now U.S. Pat. No. 8,423,675, which is a divisional of U.S. patent application Ser. No. 11/198,043, filed on Aug. 5, 2005, which is a divisional of U.S. patent application Ser. No. 09/980,539, which is a §371 of International Application No. PCT/GB00/01691, filed May 3, 2000, which claims the benefit of United Kingdom Patent Application No. 9910280.8, filed on May 4, 1999. U.S. patent application Ser. No. 12/105,412, U.S. patent application Ser. No. 11/198,043, U.S. patent application Ser. No. 09/980,539, International Application No. PCT/GB00/01691, and United Kingdom Patent Application No. 9910280.8 are hereby incorporated herein by reference in their entireties and priority to each of these cases is claimed.
After receiving a write, NIC 226 creates network packets using its packetisation engine 230. These packets are forwarded to the destination computer 221. At the destination, the memory aperture addresses of the incoming packets are remapped by the packet handler onto physical memory locations 227. The destination NIC 229 then writes the incoming data to these physical memory locations 227. This physical memory has also been mapped at connection setup time into the address space of application 223. Hence application 223 is able, using page-tables 231 and the virtual memory system, to access the data using processor read and write operations.
Other known data transfer techniques are disclosed in EP 0 600 683, EP 0 359 137, EP 0 029 800, U.S. Pat. No. 5,768,259, U.S. Pat. No. 5,550,808 and JP 600211559.
providing a new header for the untransferred data burst section comprising the new reference address; and transmitting the new header along with the untransferred data burst section.
The first aspect of the present invention addresses the synchronisation problem for memory mapped network interfaces. The present invention uses a network interface, containing snooping hardware which can be programmed to contain triggering values comprising either addresses, address ranges, or other data which are to be matched. These data are termed ‘Tripwires’. Once programmed, the interface monitors the data stream, including address data, passing through the interface for addresses and data which match the Tripwires which have been set. On a match, the snooping hardware can generate interrupts or increment event counters, or perform some other application specified action. This snooping hardware is preferably based upon Content Addressable Memory (CAM). References herein to the “data stream” refer to the stream of data words being transferred and to the address data accompanying them.
FIG. 1 shows two computers connected by a traditional network;
FIG. 2 shows two computers connected by a traditional memory-mapped network;
FIG. 3 shows a traditional SCI-like network;
FIG. 4 shows a traditional memory-mapped network between hardware entities;
FIGS. 8A-8E shows the communication protocol used in one embodiment of the invention;
At the protocol encoder, byte-enable, parity data and control information are added first to an address and then to each word to be transferred in a burst, with a control bit marking the beginning of the burst and possibly also a control bit marking the end of the burst. The control bit marking the beginning of the burst indicates that address data forming the header of the data burst comprises the first “data” word of the burst. Xon/Xoff-style management bits from block 31 are also added here. This protocol, specific to the serialiser 14 and de-serialiser 16 is also discussed elsewhere in this document.
It is also possible that data may be read out of FIFO 34 faster than it is written in. In the event of this happening, master state machine 37 uses pipeline delay 38 to anticipate the draining of FIFO 34 and to terminate the data burst on local bus 55. It then uses the CAM address latch/counter 41 to restart the burst when more data arrives in FIFO 34.
‘Tripwires’ are triggering values, such as addresses, address ranges or other data, that are programmed into the NIC to be matched. Preferably, the trigging values used as tripwires are addresses. To meet timing requirements during address match cycles (as data flows through the NIC), three CAM devices are pipelined to reduce the match cycle time from around 70 nanoseconds to less than 30 nanoseconds.
FIG. 8 shows an example of how this protocol has been implemented using the 23-bit data transfer capability of HP's GUNK chipset (serialiser 14 and de-serialiser 16). PCI to local bus bridge 12 provides a bus of 32 address/data bits, 4 parity bits and 4 byte-enable bits. It also provides an address valid signal (ADS) which signifies that a burst is beginning, and that the address is present on the address/data bus. The burst continues until a burst last signal (BLAST) is set active, signifying the end of a burst. It provides a read/write signal, and some other control signals that need not be transferred to a remote computer. FIG. 8A shows how this protocol is used to transfer an n data word burst 63. The data traffic closely mirrors that used on the PCI bus, but uses fewer signals.
FIG. 8 c, shows a read data burst 65; this is the same as a write burst 64, except data bit 16 is set to 0. On the outbound request, the data field contains the network address for the read data to be returned to. When the data for a read returns 66, it travels like a write burst, but is signified by there only being one nCAV active (signifying the network address) along with the first word. An additional bit, denoted FLAG in FIG. 8, is used to carry Xon/Xoff style information when a burst is in progress. It is not necessary therefore to break up a burst in order to send an Escape packet containing the Xon/Xoff information. The FLAG bit also serves as an additional end of packet indicator.
This method can be extended to provide support for 120 and the forthcoming Next Generation I/0 (NGIO) standard. Here, the transmit, receive and completion queues are located on the NIC rather than in the physical memory of the computer, as is currently the case for the VIA standard.
As mentioned previously, another aspect of this invention is its use in providing support for the outbound streaming of data through the NIC. This setup is described in FIG. 14. It shows a Direct Memory Access (DMA) engine 182 on the NIC 183, which has been programmed in the manner previously described by a number of user-level applications 184. These applications have requested that the NIC 183 transfer their respective data blocks 181 through the NIC 183, local bus 189, fibre-optic transceiver 190 and onto network 200. After each application has placed its data transfer request onto the DMA request queue 185, it blocks, awaiting a reschedule, initiated by device driver 187. It can be important that the system maintains fair access between a large number of such applications, especially under circumstances where an application requires a strict periodic access to the queue, such as an application generating a video stream.
In a typical example of use of the synchronising arrangement, the end-point application 306 sets a tripwire, for example to be triggered when data relating to an end-point address or range of end-point addresses in the memory 308 are present on the bus 307.
The code generator 309 supplies a code which is written into the CAM 311 and which comprises the destination memory address of the data or possibly part of this address, such as the most significant bits when a range of addresses is to be monitored. It is also possible to enter a code which represents not only the address or range of addresses but also part or all of one or more items of data which are expected in the information stream. The CAM 311 compares the address of each data burst on the bus 307, and possibly also at least some of the data of each burst, with each code stored in the CAM 311 and supplies a signal to the action generator 310 when a match is found. The action generator 310 then causes the appropriate action to be taken within the end-point application 306. This may be a single action, several actions, or one or more specific actions which are determined not only by the triggering of the tripwire but also by the data within the information stream, for example arriving at the appropriate location or locations in the memory 308.
As mentioned hereinbefore, the action generator 310 can cause any one or more of various different actions to be triggered by the tripwire. The resulting action may be determined by which tripwire has been triggered i.e. which code stored in the CAM 311 has been matched. It is also possible for the action to be at least partly determined by the data item which effectively triggered the tripwire. Any action may be targetted at the computer containing the tripwire or at a different computer. Various possible actions are described hereinafter as typical examples and may be performed singly or in any appropriate combination for the specific application and may be targeted at the computer containing the tripwire or at a different computer.
FIG. 24 illustrates the format of a data burst, a sequence of which forms the information stream on the bus 307. The data burst comprises a plurality of items which arrive one after the other in sequence on the bus. The first item is an address A(n) which is or corresponds to the end-point address, for example in the memory 308, for receiving the subsequent data items. This address is the actual address n of the first data item D.sub.1 of the burst, which immediately follows the address A(n). The subsequent data items D.sub.2, D.sub.3 . . . , D.sub.p arrive in sequence and their destination addresses are implied by their position within the burst relative to the first data item Dl and its address n. Thus, the second data item D.sub.2 has an implied address n+1, the third data item D.sub.3 has an implied address n+2 and so on. Each data item is written or supplied to the implied address as its destination address.
FIG. 27 illustrates an alternative situation in which the forwarding unit has an internal buffer 335 which contains first and second bursts 336 and 337. In this case, the implied address of the first data item D.sub.n+1 of the second burst 337 immediately follows the implied address of the last data item D.sub.n of the first burst 336. The forwarding unit checks for such situations and, when they are found, coalesces the first and second bursts into a coalesced burst 338 as shown in the lower part of FIG. 27. The forwarding unit then transmits a single contiguous burst, which saves the overhead of the excess address information (which is deleted from the second burst). Any subsequent forwarding units then treat the coalesced burst 338 as a single burst.
The format of the data burst allows such fragmentation or merging of bursts to take place. This in turn allows forwarding units to transmit data as soon as it arrives so as to reduce or minimise latency. Also, bursts of any length or number of data items can be handled which improves the flexibility of transmission of data.
storing a first data burst including a first address and first data items, the first address indicative of a first location in memory to which a first one of the first data items is directed, the first data burst not including address information for the first data items following the first one of the first data items;
identifying a second address of a last one of the first data items based on the first address;
storing a second data burst received after the first data burst, the second data burst including a third address and second data items, the third address indicative of a second location in the memory to which a first one of the second data items is directed, the second data burst not including destination information for ones of the second data items following the first one of the second data items;
determining whether the third address sequentially follows the second address; and when the third address sequentially follows the second address:
deleting the third address from the second data burst; and
combining the first and second data bursts to form a third data burst.
2. A method as defined in claim 1, further comprising transmitting the third data burst contiguously as a single burst.
3. A method as defined in claim 1, wherein the first and second data bursts are stored in an internal buffer of a forwarding unit, and the combining of the first and second data bursts is performed by the forwarding unit.
4. A method as defined in claim 3, wherein the first data burst and the second data burst are different data bursts in the internal buffer before being combined.
5. A method as defined in claim 1, further comprising, when the third address does not sequentially follow the second address, transmitting the first and second data bursts separately.
6. A method as defined in claim 1, wherein the first address is an implied address based on a reference memory location.
a memory comprising machine readable instructions;
a processor to execute the instructions to cause a machine to perform operations comprising:
storing a first data burst including a first address and first data items, the first address indicative of a first location in memory to which a first one of the first data items is directed, the first data burst not including address information for any of the first data items except the first one of the first data items;
storing a second data burst received after the first data burst, the second data burst including a third address and second data items, the third address indicative of a second location in the memory to which a first one of the second data items is directed, the second data burst not including destination information for any of the second data items except the first one of the second data items;
determining whether the third address sequentially follows the second address; and
when the third address sequentially follows the second address:
8. An apparatus as defined in claim 7, wherein the operations further comprise transmitting the third data burst contiguously as a single burst.
9. An apparatus as defined in claim 7, wherein the apparatus is a forwarding unit and the first and second data bursts are located in an internal buffer of the forwarding unit.
10. An apparatus as defined in claim 9, wherein the first data burst and the second data burst are different data bursts in the internal buffer before being combined.
11. An apparatus as defined in claim 7, wherein the operations further comprise transmitting the first and second data bursts separately when the third address does not sequentially follow the second address.
12. An apparatus as defined in claim 7, wherein the first address is an implied address based on a reference memory location.
13. A tangible machine readable storage device comprising instructions that, when executed, cause a machine to perform operations comprising:
storing a second data burst received after the first data burst, the second data burst including a third address and second data items, the third address indicative of a second location in the memory to which a first one of the second data items is directed, the second data burst not including destination information for the second data items following the first one of the second data items;
14. A storage device as defined in claim 13, wherein the operations further comprise transmitting the third data burst contiguously as a single burst.
15. A storage device as defined in claim 13, wherein the machine is a forwarding unit, the storage device comprises an internal buffer of the forwarding unit, and the combining of the first and second data bursts is performed at the forwarding unit.
16. A storage device as defined in claim 15, wherein the first data burst and the second data burst are different data bursts in the internal buffer before being combined.
17. A storage device as defined in claim 13, wherein the operations further comprise transmitting the first and second data bursts separately when the third address does not sequentially follow the second address.
18. A storage device as defined in claim 13, wherein the first address is an implied address based on a reference memory location.
US13/802,400 1999-05-04 2013-03-13 Data transfer, synchronising applications, and low latency networks Active US8843655B2 (en)
GB9910280A GB2349717A (en) 1999-05-04 1999-05-04 Low latency network
PCT/GB2000/001691 WO2000067131A2 (en) 1999-05-04 2000-05-03 Data transfer, synchronising applications, and low latency networks
US98053902A true 2002-05-13 2002-05-13
US11/198,043 US20060034275A1 (en) 2000-05-03 2005-08-05 Data transfer, synchronising applications, and low latency networks
US12/105,412 US8423675B2 (en) 1999-05-04 2008-04-18 Data transfer, synchronising applications, and low latency networks
US13/802,400 US8843655B2 (en) 1999-05-04 2013-03-13 Data transfer, synchronising applications, and low latency networks
US14/492,800 US9769274B2 (en) 1999-05-04 2014-09-22 Data transfer, synchronising applications, and low latency networks
US12/105,412 Continuation US8423675B2 (en) 1999-05-04 2008-04-18 Data transfer, synchronising applications, and low latency networks
US14/492,800 Continuation US9769274B2 (en) 1999-05-04 2014-09-22 Data transfer, synchronising applications, and low latency networks
US20130290558A1 US20130290558A1 (en) 2013-10-31
US8843655B2 true US8843655B2 (en) 2014-09-23
US11/198,043 Abandoned US20060034275A1 (en) 1999-05-04 2005-08-05 Data transfer, synchronising applications, and low latency networks
US11/198,252 Active 2025-12-06 US8073994B2 (en) 1999-05-04 2005-08-05 Data transfer, synchronising applications, and low latency networks
US11/198,260 Active 2023-07-07 US8346971B2 (en) 1999-05-04 2005-08-05 Data transfer, synchronising applications, and low latency networks
US12/105,412 Active US8423675B2 (en) 1999-05-04 2008-04-18 Data transfer, synchronising applications, and low latency networks
US13/654,876 Active US8725903B2 (en) 1999-05-04 2012-10-18 Data transfer, synchronising applications, and low latency networks
US13/802,400 Active US8843655B2 (en) 1999-05-04 2013-03-13 Data transfer, synchronising applications, and low latency networks
US14/492,800 Active 2021-01-07 US9769274B2 (en) 1999-05-04 2014-09-22 Data transfer, synchronising applications, and low latency networks
US10162775B2 (en) * 2015-12-22 2018-12-25 Futurewei Technologies, Inc. System and method for efficient cross-controller request handling in active/active storage systems
JPH06311126A (en) 1993-04-21 1994-11-04 Nec Corp Transmission frame generation circuit
GB2315638B (en) 1996-07-19 2000-09-13 Ericsson Telefon Ab L M Synchronisation checking
2005-08-05 US US11/198,043 patent/US20060034275A1/en not_active Abandoned
2005-08-05 US US11/198,252 patent/US8073994B2/en active Active
2005-08-05 US US11/198,260 patent/US8346971B2/en active Active
2008-04-18 US US12/105,412 patent/US8423675B2/en active Active
2012-10-18 US US13/654,876 patent/US8725903B2/en active Active
2013-03-13 US US13/802,400 patent/US8843655B2/en active Active
2014-09-22 US US14/492,800 patent/US9769274B2/en active Active
"Chaining of Remote Procedure Calls in Distributed Computer Environment/Remote Procedure Call." IBM Technical Disclosure Bulletin. Oct. 1, 1993. US, vol. 36, Issue 10, pp. 131-34.
Anonymous; "Low-level Interprocess Communication Facility Interface", IBC Technical Disclosure Bulletin, vol. 30, No. 10; pp. 146-148; Mar. 1, 1988; XP002151749. (cited in U.S. Appl. No. 12/105,412, to which priority is claimed).
European Patent Office, Communication pursuant to Article 64(3) EPC issued for corresponding Application No. 00 925 509.2 -2212 dated Apr. 13, 2004.
European Patent Office, Communication pursuant to Article 64(3) EPC issued for corresponding Application No. 00 925 509.2 -2212 dated Apr. 19, 2002.
European Patent Office, Communication pursuant to Article 64(3) EPC issued for corresponding Application No. 00 925 509.2 -2212 dated Nov. 11, 2009.
Hess et al.; "Implementation and Evaluation of a Prototype Reconfiguarble Router," Field Programmable Custom Computing Machines; Apr. 21, 1999; pp. 44-50. (cited in U.S. Appl. No. 12/105,412, to which priority is claimed).
International Report regarding Application No. PCT/GB/01691 dated Apr. 9, 2001. (cited in U.S. Appl. No. 12/105,412, to which priority is claimed).
Mogul, J.C., et al.; "The Packet Filter: an Efficient Mechanism for User-Level Network Code"; Operating Systems Review (SIGOPS), U.S., ACM Headquarter, New York; 1987; pp. 35-51; XP002913603. (cited in U.S. Appl. No. 12/105,412, to which priority is claimed).
NN940949. "Dynamic Random Access Memory Data Burst Control." IBM Technical Disclosure Bulletin. vol. 37, Issue 9, pp. 649-654. Sep. 1994. *
NN9511113. "Shared Burst Sequence Generator." IBM Technical Disclosure Bulletin. vol. 38, Issue 11, pp. 113-116. Nov. 1995. *
Shaw, R.H.; "A Complete Guide to OS/2 Interprocess Communications and Device Monitors"; Microsoft Systems Journal, U.S. Microsoft Co., Redmond, WA, vol. 4, No. 5; pp. 35-60; Sep. 1, 1989; XP000568106. (cited in U.S. Appl. No. 12/105,412, to which priority is claimed).
The United States Patent and Trademark Office, "Notice of Allowance and Fee(S) Due", issued for U.S. Appl. No. 11/198,260, mailed on Jul. 17, 2012, 15 pages.
The United States Patent and Trademark Office, Notice of Allowance, for U.S. Appl. No. 12/105,412, issued on Dec. 13, 2012 (17 pages).
The United States Patent and Trademark Office, Office action issued in connection with U.S. Appl. No. 11/198,260 on Jul. 5, 2011 (available as a USPTO document).
United States Patent and Trademark Office, "Non-Final Office Action," issued in connection with U.S. Appl. No. 13/654,876, Sep. 11, 2013, 35 pages.
United States Patent and Trademark Office, "Notice of Allowance," issued in connection with U.S. Appl. No. 13/654,876, Dec. 27, 2013, 8 pages.
United States Patent and Trademark Office, Office action issued in connection with U.S. Appl. No. 13/654,876 on Mar. 25, 2013.
US20150081925A1 (en) 2015-03-19
US8346971B2 (en) 2013-01-01
US8073994B2 (en) 2011-12-06
US9769274B2 (en) 2017-09-19
US20080228946A1 (en) 2008-09-18
US20130041930A1 (en) 2013-02-14
US20050289238A1 (en) 2005-12-29
US8725903B2 (en) 2014-05-13
US20060034275A1 (en) 2006-02-16
US20060029053A1 (en) 2006-02-09
US20130290558A1 (en) 2013-10-31
US8423675B2 (en) 2013-04-16
EP1142215B1 (en) 2006-04-19 A credit based flow control method
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:ROBERTS, DEREK EDWARD;MAPP, GLENFORD EZRA;POPE, STEVEN LESLIE;AND OTHERS;SIGNING DATES FROM 20020417 TO 20020507;REEL/FRAME:030691/0989
Free format text: CHANGE OF NAME;ASSIGNOR:AT&T INVESTMENTS UK INC.;REEL/FRAME:033444/0348
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:AT&T LABORATORIES-CAMBRIDGE LIMITED;REEL/FRAME:033444/0285