Layered multicast and fair bandwidth allocation and packet prioritization

• US 9,503,763 B2
• Filed: 11/13/2015
• Issued: 11/22/2016
• Est. Priority Date: 01/26/2005
• Status: Active Grant

• Current Assignee: Scale Video Coding LLC (Equitable IP Corporation)
• Original Assignee: Blitz Stream Video LLC
• Inventors: Van Zijst, Erik
• Primary Examiner(s): Wong, Xavier S.
• Application Number:
  US14/941,230
• Publication Number:
  US 20160072636A1
• Time in Patent Office: 375 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 1/18 Automatic repetition systems, e.g. Van Duuren systems
• CPC Class Codes: H04L 1/1874 Buffer management
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 12/1836 with heterogeneous network architecture
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 : by balancing the load, e.g. traffic engineering
• 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/2408 : for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 : Real-time traffic
• CPC Class Codes: H04L 47/2441 : relying on flow classification, e.g. using integrated services [IntServ]
• 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/34 : ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 61/00 : Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/103 : across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04N 19/34 : Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• CPC Class Codes: H04N 19/39 : involving multiple description coding [MDC], i.e. with separate layers being structured as independently decodable descriptions of input picture data
• CPC Class Codes: H04N 21/234327 : by decomposing into layers, e.g. base layer and one or more enhancement layers
• CPC Class Codes: H04N 21/23605 : Creation or processing of packetized elementary streams [PES]
• CPC Class Codes: H04N 21/2383 : Channel coding or modulation of digital bit-stream, e.g. QPSK modulation arrangements for detecting or preventing errors in the information received by adapting the channel coding H04L1/0009; analogue front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/2662 : Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/6125 : involving transmission via Internet transmission by internet of broadcast information H04H60/82
• CPC Class Codes: H04N 21/6405 : Multicasting data broadcast and multicast in packet switching networks H04L12/18
• CPC Class Codes: H04N 21/64322 : IP

Abstract

Embodiments include an overlay multicast network. The overlay multicast network may provide a set of features to ensure reliable and timely arrival of multicast data. The embodiments include a congestion control system that may prioritize designated layers of data within a data stream over other layers of the same data stream. Each data stream transmitted over the network may be given an equal share of the bandwidth. Addressing in routing tables maintained by routers may utilize summarized addressing based on the difference in location of the router and destination address. Summarization levels may be adjusted to minimize travel distances for packets in the network. Data from high priority data stream layers may also be retransmitted upon request from a destination machine to ensure reliable delivery of data.

Claims

1. An overlay network comprising:

a plurality of routers;

wherein each of the plurality of routers comprises;

a processor configured to execute instructions for processing inbound data packets received into an inbound interceptor pipeline and outbound data packets transmitted from an outbound interceptor pipeline;

wherein the outbound interceptor pipeline further comprises at least one of an outbound control interceptor and an outbound packet retransmission interceptor, wherein the outbound control interceptor stores outbound data packets in a first buffer until the outbound data packets are ready for transmission, and wherein the outbound packet retransmission interceptor stores the outbound data packets in a temporary outbound memory;

wherein the inbound interceptor pipeline further comprises at least one of an inbound control interceptor and an inbound packet retransmission interceptor, wherein the inbound interceptor pipeline stores inbound data packets in a second buffer until the processor is ready to process the inbound data packets, and wherein the inbound packet retransmission interceptor stores the inbound data packets in a temporary inbound memory.

2. The overlay network of claim 1, wherein a series of routers in the plurality of routers connects a source to a receiver, wherein each of the series of routers forwards data packets between the source and the receiver, wherein data packets sent towards the receiver are forward data packets, and wherein data packets sent towards the source are reverse data packets.

3. The overlay network of claim 2, wherein each of the plurality of routers forwards data packets in a multicast data stream in which each data packet includes one of a plurality of priority designations to define a plurality of virtual streams of data, at least one virtual stream having a different priority from at least one other virtual stream, wherein data packets in each of the virtual streams of packets include a designation indicating their sequence within the virtual stream, and wherein the processor executes further instructions to generate a retransmission request signal that is transmitted in a direction from which the stream containing the missing data packet originated in response to identifying a missing data packet within the sequence.

4. The overlay network of claim 3, wherein the retransmission request signal is only generated in the event that the priority designation of the stream is greater than a preselected value.

5. The overlay network of claim 3, wherein the inbound packet retransmission interceptor transmits the missing data packet in response to the retransmission request signal if the missing data packet is still stored within the temporary inbound memory of the inbound packet retransmission interceptor.

6. The overlay network of claim 3, wherein the outbound packet retransmission interceptor transmits the missing data packet in response to the retransmission request signal if the missing data packet is still stored within the temporary outbound memory of the outbound packet retransmission interceptor.

7. The overlay network of claim 3, wherein an inbound packet retransmission interceptor forwards the retransmission request in the direction from which the stream containing the missing forward data packet came if the missing data packet is not still stored within either the temporary outbound memory of the outbound packet retransmission interceptor, or the temporary inbound memory of the inbound packet retransmission interceptor.

8. The overlay network of claim 1, further comprising:

a central data store that stores only unique data packets, and wherein the temporary inbound memory and the temporary outbound memory are each linked to the central data store.

9. The overlay network of claim 1, wherein at least one instance of the inbound interceptor pipeline and at least one instance of the outbound interceptor pipeline are within one interface module.

10. The overlay network of claim 1, wherein each data packet includes one of a plurality of possible priority designations to define a plurality of separate virtual streams of data, at least one stream having a different priority than at least one other stream, and wherein the inbound control interceptor is configured to buffer the inbound data packets within a memory, each stream organized in a separate queue from among a plurality of queues with the oldest data packets toward the front of each queue, and wherein the processor executes instructions to discard a number of the data packets in response to detecting a preselected degree of increased latency in data throughput.

11. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue chosen in accordance with the priority designation.

12. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue chosen randomly.

13. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue chosen in accordance with a round robin selection algorithm.

14. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue containing the most data.

15. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue chosen from the plurality of queues containing a quantity of data nearest to a quantity of data corresponding to the preselected degree of increased latency in data throughput.

16. The overlay network of claim 10, wherein the data packets represent an encoded video signal and the priority designations are based upon video image quality criteria selected from the group consisting of screen resolution, frame-rate, and image detail, and wherein the processor executes further instructions to discard one or more data packets from one or more selected queues from among the plurality of queues, the one or more selected queues chosen in accordance with decreasing priority within the plurality of virtual streams, the priority corresponding to highest image quality being chosen first.

17. The overlay network of claim 10, wherein each stream is organized in a separate queue from among a plurality of queues so that each queue consists of packets from the same source and of the same priority.

18. The overlay network of claim 10, wherein the processor executes instructions to de-queue data packets from the plurality of queues for delivery.

19. The overlay network of claim 18, wherein the processor executes further instructions to de-queue the data packets based upon a size of a first data packet in each queue, wherein smaller data packets are delivered before larger data packets.

20. The overlay network of claim 10, wherein the processor executes further instructions to iteratively drop only one data packet at a time from any one of the plurality of queues until the memory utilization is below a predefined limit.

21. The overlay network of claim 10, wherein the processor executes further instructions to iteratively drop only one data packet at a time from any one of the plurality of queues while the preselected degree of increased latency in data throughput is detected.

22. The overlay network of claim 10, wherein the processor executes further instructions to discard one or more data packets from a selected queue from among the plurality of queues, the selected queue chosen in accordance with a weighted selection probability based upon at least one of an amount of data in the queue and a size of data packets within the queue.

23. An overlay network comprising:

a source of a multicast data stream in which each data packet includes one of a plurality of possible priority designations to define a plurality of virtual streams of data, at least one virtual stream having a different priority from at least one other virtual stream;

a receiver, wherein the receiver receives the multicast data stream; and

a plurality of intermediate nodes connecting the source to the receiver, wherein each of the plurality of intermediate nodes forwards data between the source and the receiver, and wherein each of the plurality of intermediate nodes further comprises;

a processor configured to execute instructions for processing inbound data packets received into an inbound interceptor pipeline and outbound data packets transmitted from an outbound interceptor pipeline;

wherein the outbound interceptor pipeline further comprises at least one of an outbound control interceptor and an outbound packet retransmission interceptor, wherein the outbound control interceptor stores outbound data packets in a first buffer until the outbound data packets are ready for transmission, and wherein the outbound packet retransmission interceptor stores the outbound data packets in a temporary outbound memory;

wherein the inbound interceptor pipeline further comprises at least one of an inbound control interceptor and an inbound packet retransmission interceptor, wherein the inbound interceptor pipeline stores inbound data packets in a second buffer until the processor is ready to process the inbound data packets, and wherein the inbound packet retransmission interceptor stores the inbound data packets in a temporary inbound memory.