Layered multicast and fair bandwidth allocation and packet prioritization

• US 9,414,094 B2
• Filed: 09/14/2012
• Issued: 08/09/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 Szewai
• Application Number:
  US13/619,969
• Publication Number:
  US 20130114594A1
• Time in Patent Office: 1,425 Days
• Field of Search: 370/312, 370389-392, 370/395.31, 370/396, 370/400
• 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. A router for managing the flow of data packets in 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, said router comprising:

a processor configured to execute router software to process forward data packets, the forward data packets comprising data packets from a source within a data network to be processed and forwarded toward a receiver within the network, the processor further configured to process reverse data packets, the reverse data packets comprising data packets coming back from the direction of the receiver and to be forwarded back toward the source;

an outbound interceptor pipeline coupled to said processor for receiving said forward data packets, including,

an outbound packet retransmission interceptor for receiving said forward data packets and for temporarily storing said forward data packets in a temporary outbound packet store and then forwarding the forward data packets;

an outbound control interceptor having an input connected to the output of said outbound packet retransmission interceptor and an output connected to a connection link in the data network for sending the forward data packets on toward the receiver, said outbound control interceptor receiving and buffering the forward data packets until said connection link is ready to receive them; and

an inbound interceptor pipeline coupled to said processor for receiving said reverse data packets which includes,

an inbound packet retransmission interceptor connected to a connection link for receiving said reverse data packets and for storing said reverse data packets in a temporary inbound packet store and then forwarding the reverse data packets; and

an inbound control interceptor having an input connected to the output of said inbound packet retransmission interceptor for receiving reverse data packets, said inbound control interceptor receiving and buffering said reverse data packets until said processor is ready to process them.

2. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1 in which the forward data packets in each of the virtual streams of packets include a designation indicating their sequence within the virtual stream and wherein in response to detection by the router software of absence of a packet within the sequence said software generates a retransmission request signal and passes it back in the direction from which the stream containing the missing data packet came.

3. The router for managing the flow of data packets in a multicast data stream as set forth in claim 2 in which said retransmission request signal is only generated in the event that the priority designation of the virtual stream is greater than a selected value.

4. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which a reverse data packet contains a request for retransmission of a missing forward data packet and said outbound packet retransmission interceptor determines, by processing said request for retransmission, whether said missing forward data packet is still stored within the temporary inbound packet store of said inbound packet retransmission interceptor, and said inbound packet retransmission interceptor retransmits said missing forward data packet if said missing forward data packet is still stored within the temporary inbound packet store.

5. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which a reverse data packet contains a request for retransmission of a missing forward data packet and said inbound packet retransmission interceptor determines, by processing said request for retransmission, whether said missing forward data packet is still stored within the temporary outbound packet store of said outbound packet retransmission interceptor, and said outbound packet retransmission interceptor retransmits said missing forward data packet if said missing forward data packet is still stored within the temporary outbound packet store.

6. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which a reverse data packet contains a request for retransmission of a missing forward data packet and said outbound packet retransmission interceptor determines, by processing said request for retransmission, whether said missing forward data packet is still stored within the temporary inbound packet store of said inbound packet retransmission interceptor, and forwards said retransmission request in the direction from which the stream containing the missing forward data packet came if said missing forward data packet is not still stored within the temporary inbound packet store.

7. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which a reverse data packet contains a request for retransmission of a missing forward data packet and said inbound packet retransmission interceptor determines, by processing said request for retransmission, whether said missing forward data packet is still stored within the temporary outbound packet store of said outbound packet retransmission interceptor, and forwards said retransmission request in the direction from which the stream containing the missing forward data packet came if said missing forward data packet is not still stored within the temporary outbound packet store.

8. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which a central data store stores only unique packets and said temporary inbound packet store and said temporary outbound packet store are linked to said central data store.

9. The router for managing the flow of data packets in a multicast data stream as set forth in claim 1, in which at least one instance of said inbound interceptor pipeline and at least one instance of said outbound interceptor pipeline are within one interface module of said router.

10. A method of managing throughput within a router in a multicast data network wherein each data packet includes one of a plurality of possible priority designations to define a plurality of separate streams of data, at least one stream having a different priority than at least one other stream, said method comprising:

receiving said data streams within said router;

buffering said received data streams within a memory in said router with each stream being organized in a separate queue from among a plurality of queues with the oldest data packets toward the front of each queue;

detecting when data within said memory utilization indicates a preselected degree of increased latency in data throughput; and

designating a number of said data packets within of said memory for being dropped in response to said detection.

11. The method as set forth in claim 10 wherein said designating step includes:

choosing one of said queues in accordance with its packet'"'"'s priority designation; and

dropping one or more data packets from within that queue in response to said choice.

12. The method as set forth in claim 10 wherein said designating step includes:

choosing one of said queues randomly; and

dropping one or more data packets from within that queue in response to said choice.

13. The method as set forth in claim 10 wherein said designating step includes:

choosing one of said queues in accordance with a round robin selection algorithm; and

dropping one or more data packets from within that queue in response to said choice.

14. The method as set forth in claim 10 wherein said designating step includes:

choosing the queue containing the most data; and

dropping one or more data packets from within that queue.

15. The method as set forth in claim 10 wherein said designating step includes:

choosing the queue containing a quantity of data nearest to a quantity of data by which the data in the memory indicates the preselected degree of increased latency in data throughput; and

dropping one or more data packets from within that queue.

16. The method as set forth in claim 10 wherein said data packets represent an encoded video signal and said priority designations are based upon video image quality criteria selected from the group consisting of screen resolution, frame-rate and image detail and wherein said designating step includes:

choosing at least one of said queues in accordance with decreasing priority within the plurality of virtual streams, the priority corresponding to highest image quality being chosen first; and

dropping one or more data packets from within each of said chosen queue(s) in response to said choice.

17. The method as set forth in 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 method as set forth in claim 10 wherein the method further comprises:

dequeuing packets from said queues and delivering those packets to the data network.

19. The method as set forth in claim 18 wherein said dequeuing step includes:

detecting the size of the first packet in each queue and choosing the order of delivery of said first packets to the data network in accordance with size, with the smaller sizes being delivered to the network before the larger sizes.

20. The method as set forth in claim 10 wherein said method is performed iteratively, each iteration designating only one packet from one queue and then dropping said one packet from said one queue, and ceasing said iterations when the dropping of said one packet decreases said memory utilization level below said predefined limit.

21. The method as set forth in claim 10 wherein said designating step includes:

calculating, for each queue, a weighted selection probability based upon at least one of the amount of data in the queue and the size of data packets within the queue;

choosing the queue in accordance with said weighted selection probability; and

dropping one or more data packets from within that queue.