Multicast to unicast conversion technique

• US 10,205,604 B2
• Filed: 06/19/2017
• Issued: 02/12/2019
• Est. Priority Date: 06/14/2012
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Aerohive Networks Incorporated (Extreme Networks, Inc.)
• Inventors: Liu, Liwu, Zeng, Jianlin
• Primary Examiner(s): Lo, Diane
• Application Number:
  US15/626,365
• Publication Number:
  US 20170302467A1
• Time in Patent Office: 603 Days
• Field of Search: None
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/629 Ensuring fair share of resources, e.g. weighted fair queuing [WFQ]
• CPC Class Codes: H04L 47/6295 using multiple queues, one for each individual QoS, connection, flow or priority
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 69/08 Protocols for interworking; Protocol conversion
• CPC Class Codes: H04W 28/0268 using specific QoS parameters for wireless networks, e.g. QoS class identifier [QCI] or guaranteed bit rate [GBR] negotiating SLA or negotiating QoS H04W28/24
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services

Abstract

A technique allows stations to utilize an equal share of resources (e.g., airtime or throughput). This prevents slow stations from consuming too many resources (e.g., using up too much air time). Fairness is ensured by selective dropping after a multicast packet is converted to unicast. This prevents slow stations from using more than their share of buffer resources. Multicast conversion aware back-pressure into the network layer can be used to prevent unnecessary dropping of packets after multicast to unicast (1:n) conversion by considering duplicated transmit buffers. This technique helps achieve airtime/resource fairness among stations.

Claims

1. A method comprising:

enqueuing a multicast packet of a multicast packet stream into a backpressure-controlled multicast queue;

converting the multicast packet into a plurality of unicast packets for transmission to stations of a plurality of stations;

enqueuing the plurality of unicast packets into a plurality of TID queues;

identifying a TID queue of the plurality of TID queues having a greatest token weight in a token bucket uniquely associated with the TID queue of a plurality of token buckets uniquely associated with and corresponding to each TID queue of the plurality of TID queues;

dequeuing one or more unicast packets from the TID queue for transmission to one or more clients;

deducting from a token weight of the token bucket uniquely associated with the TID queue an estimated amount based on an estimated packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients.

2. The method of claim 1, further comprising:

calculating an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deducting from the token weight of the token bucket associated with the TID queue an actual amount based on the actual token cost and the estimated amount deducted from the token bucket.

3. The method of claim 1, further comprising:

calculating an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deducting from the token weight of the token bucket associated with the TID queue the actual token cost;

adding the estimated amount deducted from the token bucket back into the token weight of the token bucket.

4. The method of claim 1, further comprising:

calculating an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deducting from the token weight of the token bucket associated with the TID queue the actual token cost;

adding the estimated amount deducted from the token bucket back into the token weight of the token bucket;

updating an estimated token cost to indicate the actual packet transmission cost for use in deducting from token weights uniquely associated with the plurality of TID queues in future transactions.

5. The method of claim 1, further comprising deducting from the token weight of the token bucket uniquely associated with the TID queue as part of a token restricted round-robin method for controlling dequeuing of packets from the plurality of TID queues.

6. The method of claim 1, wherein the token weight of the token bucket uniquely associated with the TID queue is defined as a number of tokens in the token bucket uniquely associated with the TID queue.

7. The method of claim 1, wherein the token weight of the token bucket uniquely associated with the TID queue is defined according to a function that weighs TID queues of the plurality of TID queues with smaller expected token costs greater than a token cost of the TID queue.

8. The method of claim 1, further comprising:

determining whether the token weight of the token bucket is greater than a token balance threshold of the token bucket;

if it is determined that the token weight of the token bucket is greater than the token balance threshold, dequeuing additional packets from the TID queue for transmission to the one or more clients.

9. The method of claim 1, further comprising:

determining whether the token weight of the token bucket is greater than a token balance threshold of the token bucket, the token balance threshold based on whether it is determined to perform a refresh cycle;

if it is determined that the token weight of the token bucket is greater than the token balance threshold, dequeuing additional packets from the TID queue for transmission to the one or more clients.

10. The method of claim 1, further comprising:

determining whether the token weight of the token bucket is greater than a token balance threshold of the token bucket;

if it is determined that the token weight of the token bucket is less than the token balance threshold, incrementing each token weight of each token bucket uniquely associated with each TID queue of the plurality of TID queues.

11. A system comprising:

a queuing engine configured to enqueue a multicast packet of a multicast packet stream into a backpressure-controlled multicast queue;

a multicast-to-unicast conversion engine configured to convert the multicast packet into a plurality of unicast packets for transmission to stations of a plurality of stations;

a TID queuing engine configured to enqueue the plurality of unicast packets into a plurality of TID queues;

a TID-to-AC scheduling engine configured to;

identify a TID queue of the plurality of TID queues having a greatest token weight in a token bucket uniquely associated with the TID queue of a plurality of token buckets uniquely associated with and corresponding to each TID queue of the plurality of TID queues;

dequeue one or more unicast packets from the TID queue for transmission to one or more clients;

a token bucket management engine configured to deduct from a token weight of the token bucket uniquely associated with the TID queue an estimated amount based on an estimated packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients.

12. The system of claim 11, wherein the token bucket management engine is further configured to:

calculate an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deduct from the token weight of the token bucket associated with the TID queue an actual amount based on the actual token cost and the estimated amount deducted from the token bucket.

13. The system of claim 11, wherein the token bucket management engine is further configured to:

calculate an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deduct from the token weight of the token bucket associated with the TID queue the actual token cost;

add the estimated amount deducted from the token bucket back into the token weight of the token bucket.

14. The system of claim 11, wherein the token bucket management engine is further configured to:

calculate an actual token cost based on an actual packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients;

deduct from the token weight of the token bucket associated with the TID queue the actual token cost;

add the estimated amount deducted from the token bucket back into the token weight of the token bucket;

update an estimated token cost to indicate the actual packet transmission cost for use in deducting from token weights uniquely associated with the plurality of TID queues in future transactions.

15. The system of claim 11, wherein the token bucket management engine is further configured to deduct from the token weight of the token bucket uniquely associated with the TID queue as part of a token restricted round-robin method for controlling dequeuing of packets from the plurality of TID queues.

16. The system of claim 11, wherein the token weight of the token bucket uniquely associated with the TID queue is defined as a number of tokens in the token bucket uniquely associated with the TID queue.

17. The system of claim 11, wherein the token weight of the token bucket uniquely associated with the TID queue is defined according to a function that weighs TID queues of the plurality of TID queues with smaller expected token costs greater than a token cost of the TID queue.

18. The system of claim 11, wherein:

the token bucket management engine is further configured to determine whether the token weight of the token bucket is greater than a token balance threshold of the token bucket;

the TID-to-AC scheduling engine is further configured to dequeue additional packets from the TID queue for transmission to the one or more clients, if it is determined that the token weight of the token bucket is greater than the token balance threshold.

19. The system of claim 11, wherein:

the token bucket management engine is further configured to determine whether the token weight of the token bucket is greater than a token balance threshold of the token bucket, the token balance threshold based on whether it is determined to perform a refresh cycle;

the TID-to-AC scheduling engine is further configured to dequeue additional packets from the TID queue for transmission to the one or more clients, if it is determined that the token weight of the token bucket is greater than the token balance threshold.

20. A system comprising:

means for enqueuing a multicast packet of a multicast packet stream into a backpressure-controlled multicast queue;

means for converting the multicast packet into a plurality of unicast packets for transmission to stations of a plurality of stations;

means for enqueuing the plurality of unicast packets into a plurality of TID queues;

means for identifying a TID queue of the plurality of TID queues having a greatest token weight in a token bucket uniquely associated with the TID queue of a plurality of token buckets uniquely associated with and corresponding to each TID queue of the plurality of TID queues;

means for dequeuing one or more unicast packets from the TID queue for transmission to one or more clients;

means for deducting from a token weight of the token bucket uniquely associated with the TID queue an estimated amount based on an estimated packet transmission cost associated with transmitting the one or more unicast packets dequeued from the TID queue to the one or more clients.