Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-03-09
2001-07-03
Harrell, Robert B. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
Reexamination Certificate
active
06256674
ABSTRACT:
FIELD OF THE INVENTION
This application relates to communications methods and apparatus in a distributed switching architecture, and in particular to buffer sharing methods and apparatus in a distributed switching architecture.
BACKGROUND OF THE INVENTION
A Flow Controlled Virtual Connection (FCVC) protocol for use in a distributed switching architecture is presently known in the art, and is briefly discussed below with reference to FIG.
1
. This protocol involves communication of status (buffer allocation and current state) on a per virtual connection, such as a virtual channel connection or virtual path connection, basis between upstream and downstream network elements to provide a “no cell loss” guarantee. A cell is the unit of data to be transmitted. Each cell requires a buffer to store it.
One example of this protocol involves a credit-based flow control system, where a number of connections exist within the same link with the necessary buffers established and flow control monitored on a per-connection basis. Buffer usage over a known time interval, the link round-trip time, is determined in order to calculate the per-connection bandwidth. A trade-off is established between maximum bandwidth and buffer allocation per connection. Such per-connection feedback and subsequent flow control at the transmitter avoids data loss from an inability of the downstream element to store data cells sent from the upstream element. The flow control protocol isolates each connection, ensuring lossless cell transmission for that connection. However, since buffers reserved for a first connection cannot be made available for (that is, shared with) a second connection without risking cell loss in the first connection, the cost of the potentially enormous number of cell buffers required for long-haul, high-bandwidth links, each supporting a large number of connections, quickly becomes of great significance.
Connection-level flow control results in a trade-off between update frequency and the realized bandwidth for the connection. High update frequency has the effect of minimizing situations in which a large number of receiver cell buffers are available, though the transmitter incorrectly believes the buffers to be unavailable. Thus it reduces the number of buffers that must be set aside for a connection. However, a high update frequency to control a traffic flow will require a high utilization of bandwidth (in the reverse direction) to supply the necessary flow control buffer update information where a large number of connections exist in the same link. Realizing that transmission systems are typically symmetrical with traffic flowing in both directions, and flow control buffer update information likewise flowing in both directions, it is readily apparent that a high its update frequency is wasteful of the bandwidth of the link. On the other hand, using a lower update frequency to lower the high cost of this bandwidth loss in the link, in turn requires that more buffers be set aside for each connection. This trade-off can thus be restated as being between more efficient receiver cell buffer usage and a higher cell transmission rate. In practice, given a large number of connections in a given link, it turns out that any compromise results in both too high a cost for buffers and too much bandwidth wasted in the link.
Therefore, presently known cell transfer flow control protocols fail to provide for a minimized receiver cell buffer pool and a high link data transfer efficiency, while simultaneously maintaining the “no cell loss” guarantee on a per-connection basis when a plurality of connections exist in the same link.
SUMMARY OF THE INVENTION
The presently claimed invention provides buffer state flow control at the link level, otherwise known as link flow control, in addition to the flow control on a per-connection basis.
In such a system, link flow control may have a high update frequency, whereas connection flow control information may have a low update frequency. The end result is a low effective update frequency since link level flow control exists only once per link basis whereas the link typically has many connections within it, each needing their own flow control. This minimizes the wasting of link bandwidth to transmit flow control update information. However, since the whole link now has a flow control mechanism ensuring lossless transmission for it and thus for all of the connections within it, buffers may be allocated from a pool of buffers and thus connections may share in access to available buffers. Sharing buffers means that fewer buffers are needed since the projected buffers required for a link in the defined known time interval may be shown to be less than the projected buffers that would be required if independently calculated and summed for all of the connections within the link for the same time interval. Furthermore, the high update frequency that may be used on the link level flow control without undue wasting of link bandwidth, allows further minimization of the buffers that must be assigned to a link. Minimizing the number of cell buffers at the receiver significantly decreases net receiver cost.
The link can be defined either as a physical link or as a logical grouping comprised of logical connections.
The resultant system has eliminated both defects of the presently known art. It eliminates the excessive wasting of link bandwidth that results from reliance on a per-connection flow control mechanism alone, while taking advantage of both a high update frequency at the link level and buffer sharing to minimize the buffer requirements of the receiver. Yet this flow control mechanism still ensures the same lossless transmission of cells as would the prior art.
As an additional advantage of this invention, a judicious use of the counters associated with the link level and connection level flow control mechanisms, allows easy incorporation of a dynamic buffer allocation mechanism to control the number of buffers allocated to each connection, further reducing the buffer requirements.
REFERENCES:
patent: 3804991 (1974-04-01), Hammond et al.
patent: 3974343 (1976-08-01), Cheney et al.
patent: 4069399 (1978-01-01), Barrett et al.
patent: 4084228 (1978-04-01), Dufond et al.
patent: 4240143 (1980-12-01), Bessemer et al.
patent: 4603382 (1986-07-01), Cole et al.
patent: 4715030 (1987-12-01), Koch et al.
patent: 4727537 (1988-02-01), Nichols
patent: 4737953 (1988-04-01), Koch et al.
patent: 4748658 (1988-05-01), Gopal et al.
patent: 4797881 (1989-01-01), Ben-Artzi
patent: 4821034 (1989-04-01), Anderson et al.
patent: 4837761 (1989-06-01), Isono et al.
patent: 4849968 (1989-07-01), Turner
patent: 4870641 (1989-09-01), Pattavina
patent: 4872157 (1989-10-01), Hemmady et al.
patent: 4872159 (1989-10-01), Hemmady et al.
patent: 4872160 (1989-10-01), Hemmady et al.
patent: 4872197 (1989-10-01), Pemmaraju
patent: 4878216 (1989-10-01), Yunoki
patent: 4893302 (1990-01-01), Hemmady et al.
patent: 4893307 (1990-01-01), McKay et al.
patent: 4894824 (1990-01-01), Hemmady et al.
patent: 4897833 (1990-01-01), Kent et al.
patent: 4897841 (1990-01-01), Gang, Jr.
patent: 4899333 (1990-02-01), Roediger
patent: 4920531 (1990-04-01), Isono et al.
patent: 4922503 (1990-05-01), Leone
patent: 4933938 (1990-06-01), Sheehy
patent: 4942574 (1990-07-01), Zelle
patent: 4947390 (1990-08-01), Sheehy
patent: 4953157 (1990-08-01), Franklin et al.
patent: 4956839 (1990-09-01), Torii et al.
patent: 4958341 (1990-09-01), Hemmady et al.
patent: 4979100 (1990-12-01), Makris et al.
patent: 4993018 (1991-02-01), Hajikano et al.
patent: 5014192 (1991-05-01), Mansfield et al.
patent: 5021949 (1991-06-01), Morten et al.
patent: 5029164 (1991-07-01), Goldstein et al.
patent: 5060228 (1991-10-01), Tsutsui et al.
patent: 5067123 (1991-11-01), Hyodo et al.
patent: 5070498 (1991-12-01), Kakuma et al.
patent: 5083269 (1992-01-01), Syobatake et al.
patent: 5084867 (1992-01-01), Tachibana et al.
patent: 5084871 (1992-01-01), Carn et al.
patent: 5090011 (1992-02-01), Fukuta et al.
patent: 5090024 (1992-02-01), Vander Mey et al.
pat
Caldara Stephen A.
Hauser Stephen A.
Hunt Douglas H.
Manning Thomas A.
Strouble Raymond L.
Fujitsu Network Communications, Inc.
Harrell Robert B.
Weingarten, Schurgin, Cagnebin & Hayes LLP
LandOfFree
Method and apparatus for providing buffer state flow control... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for providing buffer state flow control..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing buffer state flow control... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2547539