Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-08-27
2004-05-11
Caldwell, Andrew (Department: 2157)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
Reexamination Certificate
active
06735633
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the operation of a data network, and more particularly, to the allocation of bandwidth of a data network to a plurality of data streams.
BACKGROUND OF THE INVENTION
Networks need to efficiently use their bandwidth, especially when broadcasting high-bandwidth information. Broadcast information is typically characterized by a relatively small number of data sources transmitting data to a large number of destinations, such as end-users or clients. For example, the audio signal from an FM radio station may be digitized and broadcast over a public data network, like the Internet, thereby allowing a large number of end-users around the world to receive the digital broadcast.
A subset of broadcasting, known as multicasting, occurs when a broadcast is intended to be received by a selected set of clients. Unfortunately, current approaches have failed to achieve efficient multicasting over large data networks. Part of the reason for this failure is the lack of a scalable infrastructure to handle subscriptions, distribution and control of the multicast information.
Likewise, when a large number of time-critical unicast connections are multiplexed together over a network, for instance, to support voice over IP or on-demand streaming media, the network must efficiently deliver these streams and retain the best possible delivered quality even when the offered load exceeds the bandwidth of the intervening network links.
FIG. 1
shows a network portion
100
of a typical data network. The network portion
100
comprises nodes
102
,
104
and
106
coupled together by links
108
and
110
. All the links of network portion
100
can be considered bi-directional links allowing both the transmission and reception of information. An information source
112
is coupled to node
102
by link
114
. Clients
116
,
118
and
120
are coupled to node
106
by links
122
,
124
and
126
, respectively. Links
128
,
129
,
130
,
132
and
134
are coupled to other portions of the data network (not shown).
In a typical mode of operation, information source
112
forwards information to node
102
for distribution throughout the data network. The information is in the form of data packets where a series of data packets forms a data stream. For example, a data stream destined for client
118
would travel from node
102
to node
104
, then to node
106
and finally to client
118
. Each node receives the data packets of the data stream and forwards them in an output stream to the next node. In this manner, data streams may be distributed around the network from a source to a destination using a number of different data paths.
Unfortunately, transmission problems can occur because of the way a node forms its output stream. One problem concerns the issue of bandwidth allocation, since each link has only a fixed amount of bandwidth. In current networking schemes, if traffic backs up at a node, due to outbound congestion, some of the incoming packets will be dropped, and as a result, the quality of the data streams will be degraded.
One situation where a bandwidth limitation is especially critical is during the transmission of real-time data streams. Real-time data streams comprise video, audio or other types of data streams where the quality received by the client will degrade if the stream is interrupted. For example, if a real-time video stream transmitted to client
118
loses data packets due to a bandwidth limitation of link
108
, the quality of the data stream received by client
118
will be degraded. The client
118
will perceive the real-time video as having pauses, jumps or skips accompanied by glitches in the sound portion. As a result, client
118
may not want to receive such a degraded video stream.
SUMMARY OF THE INVENTION
The present invention provides a system for classifying, monitoring, controlling and otherwise managing and allocating bandwidth to data streams in a data network. The invention can be used in any network environment including, but not limited to, unicast networks, broadcast networks or other network environments where efficient use of network bandwidth is desired.
In one embodiment, a method for allocating bandwidth of a data network to a plurality of data streams is provided. The method comprises: specifying apportionment of the bandwidth to a plurality of data classes; receiving a plurality of data streams wherein each data stream has at least one attribute that associates the data stream with a data class; negotiating a transfer rate for each data stream, wherein the transfer rate is limited to the bandwidth apportioned to the data class associated with each data stream; and transmitting the data streams on the data network at the negotiated transfer rates.
In another embodiment, apparatus is provided for allocating bandwidth of a data network to a data stream wherein the data stream has stream annotations. The apparatus comprises a plug-in having logic to receive the data stream and to determine a plurality of transfer rates. The plug-in also has logic to transform the data stream into a transformed stream having a transfer rate selected from one of the plurality of transfer rates. An allocator is coupled to the plug-in and has logic to receive the data stream. The allocator has a policy tree that specifies apportionment of the bandwidth to a plurality of data classes. The allocator also has logic to associate the data stream with a data class based on the stream annotations and to negotiate with the plug-in to select the transfer rate from the plurality of transfer rates, wherein the transfer rate is limited to the bandwidth allocated by the policy tree to the data class. An output link is coupled to the plug-in and has logic to transmit the transformed stream on the data network at the transfer rate.
In another embodiment, a method of operating a data network to allocate bandwidth of the data network to a data stream is provided. The method comprises: annotating the data stream with stream annotations representative of a data class; establishing a policy tree that specifies apportionment of the bandwidth of the data network to a plurality of data classes; determining the data class of the data stream based on the stream annotations and negotiating a transfer rate for the data stream limited to the bandwidth specified by the policy tree for the data class; transforming the data stream to a transformed stream having the transfer rate; and transmitting the transformed stream on the data network at the transfer rate.
REFERENCES:
patent: 5835495 (1998-11-01), Ferriere
patent: 5956716 (1999-09-01), Kenner et al.
patent: 6003030 (1999-12-01), Kenner et al.
patent: 6028842 (2000-02-01), Chapman et al.
patent: 6046980 (2000-04-01), Packer
patent: 6052718 (2000-04-01), Gifford
patent: 6112239 (2000-08-01), Kenner et al.
patent: 6263371 (2001-07-01), Geagan, III et al.
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6449650 (2002-09-01), Westfall et al.
patent: 6463470 (2002-10-01), Mohaban et al.
patent: 6529508 (2003-03-01), Li et al.
patent: 6535486 (2003-03-01), Naudus et al.
patent: PCT/CA97/00936 (1997-12-01), None
U.S. International Searching Authority; International Search Report; Nov. 9, 2000; six (6) pages.
Deering, S. and Cheriton, D., “Multicast Routing in Datagram Internetworks and Extended LANs,”ACM Transactions on Computer Systems, vol. 8, No. 2, May 1990, pp. 85-110.
Maffeis, S., Bischofberger, W.R., and Mätzel, K. -U., “GTS: A Generic Multicast Transport Service,”UBILAB Technical Report, 94.6.1, 1994, pp. 1-7.
Bormann, C., Ott, J., Gehrcke, H.C., Kerschat, T., and Seifert, N., “Mtp-2: Towards achieving the S.E.R.O. Properties for Multicast Transport,” International Conference on Computer Communications Networks, (San Francisco, California), Sep. 1994.
Parsa, M., and Garcia-Luna-Aceves, J., “Scalable Internet Multicast Routing,” Proceedings of ICCCN 95, (Las Vegas, Nevada), Sep. 1995.
Thyagarajan, A.S., and Deering, S.E., Hierarchical Distance-Vector Multicast Routing for the MBone, Sigcomm
McCanne Steven
Parekh Abhay K.
Welch William
Albert Philip H.
Caldwell Andrew
Fast Forward Networks
Townsend and Townsend / and Crew LLP
LandOfFree
System for bandwidth allocation in a computer network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for bandwidth allocation in a computer network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for bandwidth allocation in a computer network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237368