Layered multicast and fair bandwidth allocation and packet prioritization

• US 9,438,938 B2
• Filed: 11/13/2015
• Issued: 09/06/2016
• Est. Priority Date: 01/26/2005
• Status: Active Grant

• Current Assignee: Scale Video Coding LLC (Equitable IP Corporation)
• Original Assignee: Biltz Stream Video LLC
• Inventors: Van Zijst, Erik
• Primary Examiner(s): WONG, XAVIER S
• Application Number:
  US14/941,160
• Publication Number:
  US 20160072635A1
• Time in Patent Office: 298 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. A method for generating an output stream of data, the method comprising:

receiving a stream of input data comprising a sequence of data packets representing market price information of a set of traded goods, each unique traded good in the set of traded goods associated with a unique element indicator, wherein each data packet in the sequence of data packets includes an element indicator relating the data packet with a particular traded good in the set of traded goods, and wherein each data packet of the sequence of data packets includes a sequence indicator corresponding to an order within the stream that the data packet was received;

storing each of the data packets in a circular buffer based upon the element indicator included with the data packet, wherein a received data packet having a same element indicator as a previously received data packet already present in the circular buffer is stored by replacing the previously received data packet having the same element indicator if the sequence indicator indicates that the received data packet is more recently received than the existing data packet, and wherein a received data packet having an element indicator not already present in a packet already stored in the circular buffer is stored in a new position in the circular buffer; and

sequentially extracting each packet from the circular buffer to form the output stream of data for delivery to one or more users.

2. The method of claim 1, further comprising:

providing an extraction rate for the sequentially extracting step, wherein the extraction rate is independent of a rate at which the data source is received.

3. The method of claim 1, wherein the storing step further comprises:

providing a second circular buffer comprising an identical sequence of positions in virtual alignment with the circular buffer as determined by the element indicators, and wherein replacing the existing data packet further comprises shifting the existing data packet into the second circular buffer.

4. The method of claim 1, wherein the sequentially extracting step further comprises:

traversing the circular buffer with a virtual token at a fixed speed.

5. The method of claim 1, wherein each unique traded good in the set of traded goods is a traded security, and wherein each unique element indicator is a trading symbol assigned to the traded security.

6. The method of claim 1, wherein the packets in the circular buffer are in a linked list.

7. A network node for generating an output stream of data, the network node comprising:

a memory;

a processor; and

a network interface;

wherein the network node is configured to receive, via the network interface, a stream of input data comprising a sequence of data packets representing market price information of a set of traded goods, each unique traded good in the set of traded goods associated with a unique element indicator, wherein each data packet in the sequence of data packets includes an element indicator relating the data packet with a particular traded good in the set of traded goods, and wherein each data packet of the sequence of data packets includes a sequence indicator corresponding to an order within the stream that the data packet was received;

wherein the memory is configured to store each of the data packets in a circular buffer based upon the element indicator included with the data packet, wherein a received data packet having a same element indicator as a previously received data packet already present in the circular buffer is stored by replacing the previously received data packet having the same element indicator if the sequence indicator indicates that the received data packet is more recently received than the existing data packet, and wherein a received data packet having an element indicator not already present in a packet already stored in the circular buffer is stored in a new position in the circular buffer; and

wherein the processor is executing instructions for sequentially extracting each packet from the circular buffer to form the output stream of data for delivery to one or more users.

8. The network node of claim 7, wherein the processor is executing instructions to extract each packet from the circular buffer according to an extraction rate that is selected independently of the rate at which the data source is received.

9. The network node of claim 7, wherein the memory is further configured with a second circular buffer comprising an identical sequence of positions in virtual alignment with the circular buffer as determined by the element indicators, and wherein replacing the existing data packet further comprises shifting the existing data packet into the second circular buffer.

10. The network node of claim 7, wherein the processor is further executing instructions to sequentially extract each packet by traversing the circular buffer using a virtual token at a fixed speed.

11. The network node of claim 7, wherein each unique traded good in the set of traded goods is a traded security, and wherein each unique element indicator is a trading symbol assigned to the traded security.

12. The network node of claim 7, wherein the packets in the circular buffer are in a linked list.

13. A method of generating an output data stream comprising data parsed from an incoming sequence of data elements, the method implemented in a network node comprising a network interface, memory, and a processor, wherein the processor executes instructions to cause the network node to perform the method, comprising:

receiving the incoming sequence of data elements, wherein each of the data elements comprises a first indicator identifying an item to which the data element relates, a second indicator identifying a current value of the item, and a third indicator identifying a location of the data element within the incoming sequence of data elements;

storing each of the data elements parsed from the incoming sequence of data elements into a position within a circular buffer based upon the first indicator, wherein a received data packet having a same first indicator as a previously received data packet in the circular buffer is stored by replacing the previously received data packet if the third indicator indicates that the received data packet was received later in the sequence, and wherein a received data packet having a first indicator that is not the same as a previously received data packet in the circular buffer is stored in a new position in the circular buffer;

extracting each of the data elements from the circular buffer stored in the memory in an orderly sequence to form an output stream, wherein each of the data elements comprises the current value for a related item.

14. The method of claim 13, further comprising:

providing an extraction rate for the sequentially extracting step, wherein the extraction rate is independent of a rate at which the data source is received.

15. The method of claim 13, wherein replacing the previously received data packet further comprises shifting the previously received data packet into a second circular buffer comprising an identical sequence of positions in virtual alignment with the circular buffer as determined by the first indicator.

16. The method of claim 13, wherein the extracting step further comprises:

traversing the circular buffer with a virtual token at a fixed speed.

17. The method of claim 13, wherein the item is a traded security, wherein the first indicator is a trading symbol assigned to the traded security, and wherein the second indicator is a price at which the item is being traded.

18. The method of claim 13, wherein the packets present in the circular buffer are in a linked list.