Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-10-08
2004-09-21
Alam, Hosain (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S200000, C709S201000, C709S239000, C709S240000, C709S241000, C709S243000, C370S229000, C370S232000, C370S412000, C370S431000, C370S452000, C370S464000, C370S468000, C370S469000, C375S240000
Reexamination Certificate
active
06795865
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to broadcast environments such as wired and wireless networks, multi-hop networks, etc., and more particularly to adaptively changing weights for fair scheduling for data transmission within such environments.
BACKGROUND OF THE INVENTION
Broadcast environments include environments in which information is transmitted from discrete originating points over a common medium, and include environments such as networking environments, which have become increasingly common. Networking means that two or more computers or computerized devices, referred to generically as nodes, are communicatively coupled together, so that they can exchange data, typically in the form of packets of data. Networking includes wired local-area-networks (LAN's), in which nodes are connected physically over relatively short distances, wireless LAN's, in which nodes communicate wirelessly over relatively short distances, and multi-hop networks, in which nodes communicate with other nodes on the network, using intermediate nodes to forward their messages.
The amount of data that a network can handle at a given moment in time is referred to as bandwidth. For example, the commonly known Ethernet network generally comes in two different speeds: 100 megabits-per-second (mbps) and 10 megabits-per-second (mbps). This means that, per second, the network is able to accommodate either 100 megabits or 10 megabits of data.
An issue in broadcast environments, such as the ones described above, is determining which node gets to communicate at a given time. Algorithms and schemes to determine which node gets to communicate at a given time typically also concern themselves with fairness. Fairness can be defined in different ways. For example, fairness can mean that each node on the network has a predetermined percentage of the available bandwidth on the network over a given duration of time, a predetermined priority relative to the other nodes on the network, or a weight to divide the available network bandwidth relative to the other nodes. In addition, fairness can mean that a predefined Quality of Service (QOS) is guaranteed for one or more given nodes on the network. A non-restrictive example of QOS is that a given node is guaranteed to receive x amount of bandwidth within y amount of time after the node requests to transmit data over the network.
Within the prior art, fairness has generally been implemented by randomizing the time at which different nodes compete for the broadcast channel to transmit their data. The theory is that by randomizing the time, the nodes on the network will pick generally different times to transmit and consequently each will get a chance to transmit its data. While such randomization techniques improve the probability that, over a long period of time, every node gets an opportunity to use the channel, they generally result in poor performance when nodes have to transmit time-constrained data, such as voice and video.
One manner by which fairness can be achieved and which solves this problem is described in the cofiled, copending and coassigned patent application entitled “Fair Scheduling in Broadcast Environments” [U.S. patent application Ser. No. 09/415,901]. In this application, each node within a network is able to transmit a packet of data after it has counted down from a back-off interval. The back-off interval for each packet is based on at least a start tag of the packet, which is assigned to the packet when it arrives at or within the node for transmission. The tagging of packets with their start tags and using these tags to schedule transmission provides for fair scheduling, such that each node eventually has its turn to transmit information.
In fair scheduling described in the application identified in the previous paragraph, as well as in the prior art, a fixed weight is usually implicitly or explicitly assigned to each node that does not vary over time. A node's weight is usually based on its priority or bandwidth requirements. The weight for a node thus determines the amount of bandwidth that a node requires and is proportional to the amount of bandwidth it is allocated by the network. For example, where the weights for all the nodes are equal, no node has priority, and each node can be allocated the same amount of bandwidth. As another example, if all the nodes except one have a given weight, and the one node has twice the weight of any other node, then the node with the greater weight will have twice the opportunity to transmit packets of data as any other node, and thus will be able to have allocated to it twice the amount of bandwidth as compared to any other node.
Fixed weights, however, assume that the priority of the nodes and/or their bandwidth requirements are unchanging during a connection's lifetime, and can be determined a priori. This may not be the case. For example, at any given time, one or more of the nodes may be transmitting more time-sensitive data, such as voice data, such that during that transmission such nodes should be accorded higher weight. Another example is when a large quantity of data arrives at a node in a short period of time and this node would want to transmit this data quickly by picking a higher weight dynamically. Fixed-weight schemes do not provide for these situations. For these and other reasons, there is a need for the present invention.
SUMMARY OF THE INVENTION
The invention relates to adaptively changing weights for fair scheduling in broadcast environments. In one embodiment, a computer-implemented method allocates bandwidth among a plurality of flows sharing an output link. Each flow can correspond to a node within a network, for example, or an application program generating data packets within a node. The output link can correspond to the network itself, for example, or the node itself, respectively. The method includes adaptively determining a weight for each flow, based on a predetermined criterion, and allocating a portion of bandwidth to each flow proportionally to the weight for the flow.
For example, in one embodiment, the predetermined criterion takes into account an input rate of data packets for each flow. Thus, flows that are receiving more data packets for transmission over the link over a period of time are accorded higher weights. As another example, in one embodiment, the predetermined criterion takes into account the queue size for each flow. Thus, flows that have a greater backlog of data packets for transmission over the link are accorded higher weights. In either embodiment, the bandwidth accorded to each flow is proportional to the weight for the flow, and may also be based on a protocol or algorithm for fair scheduling that can utilize the weight, such as protocols and algorithms known within the prior art, and also that which is described in the copending, cofiled and coassigned application referenced in the previous section of the specification.
The invention includes computer-implemented methods, machine-readable media, computerized systems, and computers of varying scopes. Other aspects, embodiments and advantages of the invention, beyond those described here, will become apparent by reading the detailed description and with reference to the drawings.
REFERENCES:
patent: 5315586 (1994-05-01), Charvillat
patent: 5434848 (1995-07-01), Chimento, Jr. et al.
patent: 5854899 (1998-12-01), Callon et al.
patent: 6028841 (2000-02-01), Lyon et al.
patent: 6078953 (2000-06-01), Vaid et al.
patent: 6091455 (2000-07-01), Yang
patent: 6188698 (2001-02-01), Galand et al.
patent: 6198728 (2001-03-01), Hulyalkar et al.
patent: 6240463 (2001-05-01), Benmohamed et al.
patent: 6314110 (2001-11-01), Chin et al.
patent: 6341309 (2002-01-01), Vaid et al.
patent: 6408005 (2002-06-01), Fan et al.
patent: 6470016 (2002-10-01), Kalkunte et al.
patent: 0829986 (1998-03-01), None
Hui Huang et al, Hierarchical scheduling with adaptive weights for W-ATM, IEEE ATM Workshop '99 Proceedings, May 24-27, 1999, pp. 337-342.
J.L. Sobrinho, A.S. Krishnakumar,
Bahl Paramvir
Vaidya Nitin
Alam Hosain
Leydig , Voit & Mayer, Ltd.
Microsoft Corporation
Won Young N
LandOfFree
Adaptively changing weights for fair scheduling in broadcast... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptively changing weights for fair scheduling in broadcast..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptively changing weights for fair scheduling in broadcast... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207878