Method and apparatus implementing a multimedia digital network

• US 7,158,531 B2
• Filed: 09/14/2001
• Issued: 01/02/2007
• Est. Priority Date: 08/28/1997
• Status: Expired due to Fees

• Current Assignee: TiVo Solutions Inc. (Adeia Inc.)
• Original Assignee: TiVo Inc. (Adeia Inc.)
• Inventors: Barton, James M.
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): CHANG, RICHARD K
• Application Number:
  US09/953,472
• Publication Number:
  US 20020031144A1
• Time in Patent Office: 1,936 Days
• Field of Search: 370230-237, 370/468, 370503-510, 370442-443, 370/401, 370/391, 370/395.4
• US Class Current: 370/442
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

A method and apparatus for efficiently managing the allocation of available data capacity on a physically shared digital network among devices connected to that network is disclosed. Also disclosed is a method and apparatus for managing the ongoing timely movement of data on the shared network such that precise long-term data rates are achieved between attached devices with minimal additional buffering. The invention further comprises a method and apparatus which allows the use of any remaining network capacity for non time-critical data movement without the need for centralized access management.

Claims

1. A method for managing the allocation of the data capacity of a streaming media service across interconnected networks, said method comprising the steps of:

avoiding network contention across said interconnected networks using a distributed bandwidth reservation schedule;

wherein said interconnected networks contain nodes with differing connection speeds;

receiving and maintaining a copy of said reservation schedule on each node;

wherein said reservation schedule is synchronized across all nodes by a periodic network clock broadcast;

calculating bandwidth between a source node and a destination node;

reserving bandwidth for a stream in said reservation schedule on said source node based on said bandwidth calculation step; and

wherein said destination node is responsible for broadcasting continued interest allocation records after each stream packet is received indicating continued interest in receiving said stream.

2. The method of claim 1,

wherein said reservation schedule works in parallel with an on-demand packet-based service on said nodes.

3. The method of claim 1, wherein a list of allocation records on said nodes represents allocated bandwidth in said reservation schedule, and wherein each allocation record defines a window of network time.

4. The method of claim 3, further comprising the step of:

providing a queue of on-demand packets on each node; and

wherein on-demand packets are sent when a required time to send an on-demand packet exists in between allocation records.

5. The method of claim 1, wherein a portion of said reservation schedule is reserved for managing allocation records.

6. The method of claim 1, wherein a node broadcasts a bandwidth allocation request to all nodes in said interconnected networks.

7. The method of claim 6, wherein a node deletes said reserved bandwidth if said continued interest allocation records are not received within a predetermined period of time.

8. The method of claim 7, wherein if said source node deletes said reserved bandwidth then said source node ceases sending said stream to said destination node.

9. The method of claim 6, wherein a receiving node reserves bandwidth in its copy of said reservation schedule upon receipt of a valid allocation request.

10. The method of claim 6, wherein if a received allocation request matches a previous allocation request, then a receiving node discards said received allocation request.

11. The method of claim 6, wherein if a received allocation request is a tear-down request, then a receiving node deletes the matching allocation record from its copy of said reservation schedule.

12. The method of claim 6, wherein if an allocation request arrives from another node while a receiving node is creating its own allocation request, the receiving node will abandon its allocation request effort and start over after it updates its copy of said reservation schedule.

13. The method of claim 1, wherein one node in said interconnected networks is designated a clock node and sends a periodic network clock broadcast to all nodes in said interconnected networks.

14. The method of claim 13, further comprising the step of:

selecting a new clock node upon failure of said clock node.

15. An apparatus for managing the allocation of the data capacity of a streaming media service across interconnected networks, comprising:

a distributed bandwidth reservation schedule for avoiding network contention across said interconnected networks;

wherein said interconnected networks contain nodes with differing connection speeds;

reservation schedule maintenance means resident on each node for receiving and maintaining a copy of said reservation schedule;

wherein said reservation schedule is synchronized across all nodes by a periodic network clock broadcast;

bandwidth calculation means for calculating the bandwidth between a source node and a destination node;

bandwidth reservation means resident on said source node for reserving bandwidth for a stream in said reservation schedule based on said bandwidth calculation means; and

wherein said destination node is responsible for broadcasting continued interest allocation records after each stream packet is received indicating continued interest in receiving said stream.

16. The apparatus of claim 15, further comprising:

an on-demand packet-based service on said nodes; and

wherein said reservation schedule works in parallel with said on-demand packet-based service.

17. The apparatus of claim 15, further comprising:

a list of allocation records on each node;

wherein said list of allocation records represents allocated bandwidth in said reservation schedule; and

wherein each allocation record defines a window of network time.

18. The apparatus of claim 17, further comprising:

a queue of on-demand packets on each node; and

wherein on-demand packets are sent when a required time to send an on-demand packet exists in between allocation records.

19. The apparatus of claim 17, wherein a portion of said reservation schedule is reserved for managing allocation records.

20. The apparatus of claim 15, wherein a node broadcasts a bandwidth allocation request to all nodes in said interconnected networks.

21. The apparatus of claim 20, wherein a node deletes said reserved bandwidth if said continued interest allocation records are not received within a predetermined period of time.

22. The apparatus of claim 21, wherein if said source node deletes said reserved bandwidth then said source node ceases sending said stream to said destination node.

23. The apparatus of claim 20, wherein a receiving node reserves bandwidth in its copy of said reservation schedule upon receipt of a valid allocation request.

24. The apparatus of claim 20, wherein if a received allocation request matches a previous allocation request, then a receiving node discards said received allocation request.

25. The apparatus of claim 20, wherein if a received allocation request is a tear-down request, then a receiving node deletes the matching allocation record from its copy of said reservation schedule.

26. The apparatus of claim 20, wherein if an allocation request arrives from another node while the receiving node is creating its own allocation request, a receiving node will abandon its allocation request effort and start over after it updates its copy of said reservation schedule.

27. The apparatus of claim 15, wherein one node in said interconnected networks is designated a clock node and sends a periodic network clock broadcast to all nodes in said interconnected networks.

28. The apparatus of claim 27, further comprising:

means for selecting a new clock node upon failure of said clock node.