Layered multicast and fair bandwidth allocation and packet prioritization

• US 8,514,718 B2
• Filed: 06/17/2009
• Issued: 08/20/2013
• 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: Zijst, Erik Van
• Primary Examiner(s): Wong, Xavier S.
• Application Number:
  US12/486,656
• Publication Number:
  US 20090252164A1
• Time in Patent Office: 1,525 Days
• Field of Search: 370/312, 370389-392, 370/395.31, 370/396, 370/400
• US Class Current: 370/238
• 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 in the 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 comprising:

storing a routing table by a network node, the routing table containing a set of summarized destination addresses based upon a location of a destination machine, wherein the destination addresses are multi-field addresses and are summarized by comparing each field of the multi-field destination address with a respective corresponding field of an address of the network node in a sequential basis, starting with a most significant field of the multi-field destination address and continuing toward the least significant field of the multi-field destination address, field-by-field, identifying a first non-matching field, and filling all subsequent fields with a wildcard;

determining a path length for the summarized destination address;

determining if the routing table contains a previously summarized destination address for the destination machine;

comparing the path length for the summarized destination address with a path length for the previously summarized destination address;

updating the routing table with the summarized destination address only if the path length for the summarized destination address is shorter than the path length for the previously summarized destination address;

propagating routing table updates to neighboring routers if the routing table is updated with the summarized destination address, and not propagating routing table updates to neighboring routers if the routing table is not updated with the summarized destination address; and

forwarding data to the destination machine using a designated hop address associated with summarized address of the destination machine.

2. The method of claim 1, wherein the location is a domain.

3. The method of claim 1, further comprising:

adjusting a level of summarization to minimize a distance data traverses to reach the destination machine.

4. The method of claim 3, wherein adjusting the level of summarization occurs at a border router adjacent a destination domain.

5. The method of claim 3, further comprising:

receiving a subscription request from an adjacent node for a multicast group; and

tracking the adjacent node that sent the subscription request in a subscription table.

6. The method of claim 5, further comprising:

forwarding subscription requests toward a source if not present in the subscription table.

7. The method of claim 1, further comprising:

sending a leave group message to an adjacent node if a connection with a source is lost.

8. The method of claim 1, further comprising:

forwarding multicast group data to each destination in an entry in a subscription table associated with a group source.