Layered multicast and fair bandwidth allocation and packet prioritization

• US 20060268871A1
• Filed: 01/26/2006
• Published: 11/30/2006
• Est. Priority Date: 01/26/2005
• Status: Active Grant

• Current Assignee: Scale Video Coding LLC (Equitable IP Corporation)
• Original Assignee: INTERNET BROADCASTING CORPORATION
• Inventors: Van Zijst, Erik
• Granted Patent: US 7,733,868 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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:

receiving data from a source in a single stream;

forwarding the data to multiple concurrent receivers over a packet switched network;

detecting inadequate bandwidth to transmit the stream to a destination; and

selecting a layer of high priority packets in the stream to forward to the destination.

2. The method of claim 1, wherein the data is live.

3. The method of claim 2, further comprising:

guaranteeing timely deliver of the data to the multiple concurrent receivers.

4. The method of claim 3, wherein the packet-switched network includes nodes with insufficient bandwidth.

5. The method of claim 1, further comprising:

encoding the data in virtual layers by including a layer identifier in each packet, the layer identifier indicating the importance of the packet.

6. The method of claim 5, further comprising:

labeling each packet in each virtual layer with an incrementing sequence number.

7. The method of claim 6, further comprising:

tracking a most recently used sequence number for each virtual layer.

8. The method of claim 1, further comprising:

inspecting a sequence vector in a packet to detect packet loss in a virtual layer.

9. The method of claim 1, further comprising:

dividing available bandwidth among a plurality of data streams,

wherein a network router prioritizes forwarding of high priority virtual layers.

10. The method of claim 1, further comprising:

initiating a countdown timer for each missing packet; and

sending a retransmission request to the source for each missing packet.

11. The method of claim 1, further comprising:

delivering packets in an original order; and

maintaining a buffer to temporarily queue packets to wait for a less recent missing packet to be retransmitted.

12. The method of claim 1, further comprising:

marking a virtual layer as irrecoverable if a countdown timer has run out for a packet in the virtual layer.

13. The method of claim 1, further comprising:

receiving a request from a destination for a packet from the layer; and

retransmitting the packet to the destination.

14. The method of claim 13, further comprising:

forwarding the request toward the source if the copy of requested data is not found locally.

15. The method of claim 1, further comprising:

selecting a layer of lower priority packets in the stream to forward if sufficient bandwidth is available to the destination.

16. The method of claim 1, further comprising:

discarding duplicate retransmission requests upon receipt.

17. The method of claim 1, further comprising:

monitoring the bandwidth availability to each destination;

adjusting a number of layers of packets from the stream to be transmitted to the destination based on the bandwidth.

18. A method comprising:

sending data through a network using a unique dotted string address to identify a destination; and

assigning the unique dotted string address to each router in a network,

wherein the dotted string address is related to a location in the network, and

wherein the dotted string address indicates hierarchy.

19. The method of claim 18, further comprising:

executing a distance-vector routing protocol on each router to periodically exchange routing information by sending a cost of a shortest path to reach any known destination to each neighbor router; and

using the routing information received from each neighbors to optimize local routing information.

20. The method of claim 19, wherein the routing information includes a destination address, cost and an address of a pre-final node.

21. The method of claim 20, wherein the routing information includes a distance vector.

22. The method of claim 20, wherein pre-final node information allows the backtracking of an entire path to any destination, and

wherein a router uses backtracking information to avoid routing loops by not advertising paths to neighbor routers that are a part of a shortest path.

23. The method of claim 18, further comprising:

comparing each address field in the unique dotted string address of the destination with a unique dotted string address of a local router to determine a first dissimilar field; and

replacing all consecutive fields of the unique dotted string address of the destination with a wildcard indicator.

24. The method of claim 18, further comprising:

summarizing addresses prior to providing distance vectors to a routing algorithm.

25. The method of claim 18, further comprising:

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

26. A method comprising:

receiving data, the data categorized into a set of logical layers;

buffering the data to await one of transmission or processing;

detecting a threshold buffer utilization is met; and

selecting data to be dropped from the buffer based on the priority of its logical layer.

27. The method of claim 26, wherein buffering the data further comprises:

storing data in a queue based on a source address of the data; and

organizing data in the queue based on relative priority of the data.

28. The method of claim 26, wherein selecting data to be dropped further comprises:

selecting a queue to drop data from based on a weighting factor for the queue.

29. The method of claim 26, further comprising:

flagging a logical layer as reliable based on consistent reception of packets from the layer.

30. The method of claim 29, further comprising:

flagging a logical layer as unreliable based on packet loss from the layer.

31. A method comprising:

storing a routing table, the routing table containing a set of summarized destination addresses based on a location of a destination machine; and

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

32. The method of claim 31, wherein the location is a domain.

33. The method of claim 31, further comprising:

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

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

35. The method of claim 33, 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.

36. The method of claim 35, further comprising:

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

37. The method of claim 31, further comprising:

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

38. The method of claim 31, further comprising:

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

39. A system comprising:

a primary communication network;

a first router in communication with the primary communication network; and

a second router in communication with the primary network, the second router configured to communicate with the first router via a reliable link over the primary network, the first and second router to form an overlay network over the primary network, the second router to manage bandwidth by equal allotment to each data stream transmitted via the overlay network.

40. The system of claim 39, wherein the overlay network transmits data categorized into logical layers within a data stream.

41. The system of claim 39, further comprising:

a first application in communication with the first router, the first application to generate a layered data stream and forward the data stream to the first router.

42. The system of claim 41, further comprising:

a second application in communication with the second router, the second application to receive the layered data stream from the second router and reassemble the layered data stream.

43. The system of claim 42, wherein the first router and second router implement an extended Bellman-Ford routing algorithm.

44. The system of claim 39, wherein the second router requests retransmission of missing packets from high priority logical layers.

45. The system of claim 39, wherein the reliable link is a TCP connection.

46. The system of claim 39, wherein the second router processes an hierarchical dotted string address system.

47. The system of claim 39, wherein the second router summarizes address of neighbor nodes in the overlay network.

48. The system of claim 39, wherein the second router maintains a subscription table for multicast data.