Method and apparatus implementing a multimedia digital network

• US 6,310,886 B1
• Filed: 08/18/1998
• Issued: 10/30/2001
• Est. Priority Date: 08/28/1997
• Status: Expired due to Term

• Current Assignee: TiVo Solutions Inc. (Adeia Inc.)
• Original Assignee: TiVo Inc. (Adeia Inc.)
• Inventors: Barton, James M.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): KWOH, JASPER C
• Application Number:
  US09/135,753
• Time in Patent Office: 1,169 Days
• Field of Search: 370/432, 370/463, 370/322, 370/348, 370/419, 370/420, 370/442-444, 370/449, 370/461, 370/462, 340/825.08, 340/825.14, 340/825.15, 340/825.2, 340/825.21, 340/825.22
• US Class Current: 370/462
• 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 data capacity on a physically shared network segment, said method comprising the steps of:

providing a plurality of devices on said physically shared network segment;

providing an on-demand packet-based service;

providing a streaming media service which operates in parallel with said on-demand packet-based service on said network segment; and

wherein said streaming media service utilizes a distributed reservation scheme to avoid network contention, wherein each device contains within it a copy of the entire reservation schedule and said reservation schedule is synchronized across all devices by a periodic network clock broadcast.

2. An apparatus for managing the allocation of data capacity on a physically shared network segment, comprising:

a network interface component (NIC) comprising;

a free-running time-based counter that may be read or modified by a host processor at any time; and

a first register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC is required to wait, without accessing a transmission medium, until the value in said first register matches that of said free-running time-based counter; and

wherein said NIC must transmit said packet when said value in said first register matches that of said free-running time-based counter.

3. The apparatus of claim 2, wherein said NIC marks said packet done but does not transmit said packet, and continues on to a next packet in sequence when said value in said first register matches that of said free-running counter.

4. The apparatus of claim 3, further comprising:

a second register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC transmits said packet after waiting a predetermined amount of time, as determined by said host processor-specified value, if said value in said first register matches that of said free-running counter; and

wherein said NIC ceases attempting to transmit said packet and, optionally, indicates that said packet was not sent, after waiting a predetermined amount of time, as determined by said host processor-specified value, if said value in said first register does not match that of said free-running counter.

5. The apparatus of claim 4, wherein said NIC waits until the value in said second register matches the value of said free running counter, then indicates it has finished with said packet but does not transmit said packet, and continues operation when said value in said first register matches that of said free-running counter.

6. The apparatus of claim 2, wherein said host processor, on demand, may request that a packet which is waiting for transmission be canceled.

7. A method for managing the allocation of data capacity on a physically shared network segment, said method comprising the steps of:

computing a distributed network schedule for a transmission medium indicating when various network devices are permitted to transmit on said medium; and

indicating unscheduled portions of network bandwidth which are contended for by said network devices;

wherein each node on said network maintains a representation of said distributed network schedule locally;

wherein network contention is substantially eliminated during periods where scheduled transmissions are taking place; and

wherein limited contention is allowed for unscheduled portions of said bandwidth, with the ability to stop contention in time for a next scheduled transmission.

8. The method of claim 7, further comprising the steps of:

determining the time it takes to transmit a block of X bytes between two nodes by calculating the achievable bandwidth between those nodes and the size of the block to be transmitted; and

scheduling the use of said transmission medium based on the time it takes for each transmission if an arbitrary scheduling interval is chosen, regardless of the available bandwidth between any two nodes.

9. The method of claim 7, wherein each node is responsible for setting a free-running counter in a network interface component (NIC) with a network-relative clock value which is periodically broadcast by a selected node;

wherein each node contains within it a copy of said schedule which is synchronized across all nodes by said periodic network-relative clock broadcast.

10. The method of claim 9, wherein each scheduled block of time is represented by an allocation record which contains fields describing said network-relative clock value at which said block begins, the duration of time represented by said block, and the re-scheduling period, for continuous, constant-rate streams of data.

11. The method of claim 10, further comprising the step of:

reinserting said block at an appropriate point in said schedule for sending as a next block of data when a scheduled block transmission is completed when said block represents a constant-rate stream of data.

12. The method of claim 10, wherein allocation records are set up or torn down in every node on said network with a single transmission.

13. The method of claim 10, further comprising the steps of:

performing an appropriate operation on a local copy of said schedule when a node receives an allocation message;

allocating a dead-space record which indicates to said node that it is not to transmit during that period if said node is not sending a stream of data.

14. The method of claim 10, further comprising the steps of:

combining a buffer and an allocation record into a single data structure; and

using said ring-buffer to hold said schedule.

15. A method for combining time-sensitive transmission with on-demand data transmission, such that packets involved in synchronous data transmissions are unaffected by other traffic, said method comprising the steps of:

computing a schedule for a transmission medium indicating when various network devices are permitted to transmit on said medium;

indicating unscheduled portions of network bandwidth which are contended for by said network devices;

wherein each network device on the network maintains a representation of said schedule locally;

scanning a local copy of said schedule with a network interface component (NIC) when a NIC driver on a particular node is presented with a packet to be sent; and

inserting said packet into a first unscheduled space in said schedule large enough to hold said packet.

16. The method of claim 15, wherein a streaming media packet is scheduled into said first unscheduled space if a conflict occurs between streaming media and an on-demand packet;

and

wherein a previously scheduled on-demand packet is deleted from said schedule and re-inserted in a first available slot, said on-demand packet having been replaced in said schedule by said streaming media packet.

17. The method of claim 16, further comprising the step of:

reserving on-demand transmission space.

18. The method of claim 16, further comprising the step of:

using a timeout register having a set timeout value that is equal to the time for a next on-demand packet to be sent less the time it takes to transmit said packet.

19. A method for managing the allocation of data capacity on a physically shared network segment, said method comprising the steps of:

computing a schedule for a transmission medium indicating blocks of time when various network devices are permitted to transmit on said medium, wherein each scheduled block of time is represented by an allocation record, and wherein each node contains within it a copy of said schedule which is synchronized across all nodes by a periodic network-relative clock broadcast;

reserving an implicit window for on-demand transmission immediately succeeding a periodic broadcast of said network relative clock value when a node is first connected to said network to broadcast a request for download of a current schedule;

awaiting a next clock broadcast if said node cannot successfully send a packet in said window;

responding to said download request from said broadcast node with an on-demand transmission of said current schedule; and

beginning regular operation at said node once said schedule is received.

20. The method of claim 19, wherein a first node to initialize on said network does not receive said periodic broadcast of said network relative clock;

wherein said node takes responsibility for broadcasting said network relative clock after waiting a predetermined amount of time;

wherein said node responds to other nodes as they initialize; and

wherein said nodes initializes it'"'"'s schedule to empty, such that nodes which join said network later are properly initialized.

21. The method of claim 19, wherein each node continues to follow said transmission schedule if the node which is responsible for broadcasting said network relative clock fails;

wherein each node recognizes that said network relative clock has not been received after a predetermined time;

wherein said nodes broadcast to each other a copy of a local clock register at a next available opportunity; and

wherein a first successful clock broadcast after said previous clock node failed resets a timeout value and indicates a clock node, causing succeeding clock broadcasts from other nodes to be ignored.

22. The method of claim 19, wherein a receiver node is responsible for broadcasting periodic on-demand packets indicating it'"'"'s continued interest in receiving a stream during the life of said stream;

wherein all nodes on said network use said packets to reset an internal count-down timer to a preferred value;

where each node assumes that said receiver node has failed or become inaccessible and releases an allocation record associated with said stream if said timer goes to zero; and

wherein a sender node ceases sending said streaming data, such that network capacity represented by said stream is properly recovered, even if both a sender and receiver fail.

23. The method of claim 19, wherein a node examines it'"'"'s copy of said schedule and chooses an appropriate time for a first transmission when said node desires to reserve an allocation record for transmitting streaming media;

and

wherein said node broadcasts an allocation message to all nodes during a next available on-demand window.

24. The method of claim 23, wherein each node, including a node requesting an allocation, attempts to update it'"'"'s schedule when it receives an allocation message broadcast;

wherein a new allocation request is ignored if a previously scheduled streaming media transmission conflicts with said new allocation request;

wherein a requesting node checks its copy of said schedule to see if said request is present after broadcasting;

wherein said requesting node may begin transmitting streaming media according to said schedule if said request succeeds; and

wherein said node must choose a new position in said schedule and broadcast a new request for it if said request did not succeed.

51. The method of claim 19, wherein said node broadcasts an on-demand packet identifying itself.

52. The apparatus of claim 19, wherein said node broadcasts an on-demand packet identifying itself.

25. An apparatus for managing the allocation of data capacity on a physically shared network segment, comprising:

a network interface component (NIC) comprising;

a free-running time-based counter that may be read or modified by a host processor at any time; and

a first register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC is required to wait, without accessing a transmission medium, until the value in said first register matches that of said free-running time-based counter;

wherein said NIC must transmit said packet when said value in said first register matches that of said free-running time-based counter; and

wherein commands are explicitly given to said NIC to transmit a packet or to cancel a packet.

26. An apparatus for managing the allocation of data capacity on a physically shared network segment, comprising:

a plurality of devices on said physically shared network segment;

an on-demand packet-based service;

a streaming media service which operates in parallel with said on-demand packet-based service on said network segment; and

wherein said streaming media service utilizes a distributed reservation scheme to avoid network contention, wherein each device contains within it a copy of the entire reservation schedule and said reservation schedule is synchronized across all devices by a periodic network clock broadcast.

27. A method for managing the allocation of data capacity on a physically shared network segment, comprising the step of:

providing a network interface component (NIC) comprising;

a free-running time-based counter that may be read or modified by a host processor at any time; and

providing a first register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC is required to wait, without accessing a transmission medium, until the value in said first register matches that of said free-running time-based counter; and

wherein said NIC must transmit said packet when said value in said first register matches that of said free-running time-based counter.

28. The method of claim 27, wherein said NIC marks said packet done but does not transmit said packet, and continues on to a next packet in sequence when said value in said first register matches that of said free-running counter.

29. The method of claim 28, further comprising the step of:

providing a second register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC transmits said packet after waiting a predetermined amount of time, as determined by said host processor-specified value, if said value in said first register matches that of said free-running counter; and

wherein said NIC ceases attempting to transmit said packet and, optionally, indicates that said packet was not sent, after waiting a predetermined amount of time, as determined by said host processor-specified value, if said value in said first register does not match that of said free-running counter.

30. The method of claim 29, wherein said NIC waits until the value in said second register matches the value of said free running counter, then indicates it has finished with said packet but does not transmit said packet, and continues operation when said value in said first register matches that of said free-running counter.

31. The method of claim 27, wherein said host processor, on demand, may request that a packet which is waiting for transmission be canceled.

32. An apparatus for managing the allocation of data capacity on a physically shared network segment, comprising:

a network interface component (NIC) for computing a distributed network schedule for a transmission medium indicating when various network devices are permitted to transmit on said medium; and

a mechanism that identifies unscheduled portions of network bandwidth which are contended for by said network devices;

wherein each node on said network maintains a representation of said distributed network schedule locally;

wherein network contention is substantially eliminated during periods where scheduled transmissions are taking place; and

wherein limited contention is allowed for unscheduled portions of said bandwidth, with the ability to stop contention in time for a next scheduled transmission.

33. The apparatus of claim 32, further comprising:

a timer for determining the time it takes to transmit a block of X bytes between two nodes by calculating the achievable bandwidth between those nodes and the size of the block to be transmitted; and

wherein the use of said transmission medium is scheduled based on the time it takes for each transmission if an arbitrary scheduling interval is chosen, regardless of the available bandwidth between any two nodes.

34. The apparatus of claim 33, wherein each node is responsible for setting a free-running counter in a network interface component (NIC) with a network-relative clock value which is periodically broadcast by a selected node;

wherein each node contains within it a copy of said schedule which is synchronized across all nodes by said periodic network-relative clock broadcast.

35. The apparatus of claim 34, wherein each scheduled block of time is represented by an allocation record which contains fields describing said network-relative clock value at which said block begins, the duration of time represented by said block, and the re-scheduling period, for continuous, constant-rate streams of data.

36. The apparatus of claim 34, further comprising:

a mechanism for reinserting said block at an appropriate point in said schedule for sending as a next block of data when a scheduled block transmission is completed when said block represents a constant-rate stream of data.

37. The apparatus of claim 35, wherein allocation records are set up or tom down in every node on said network with a single transmission.

38. The apparatus of claim 35, further comprising:

a mechanism for performing an appropriate operation on a local copy of said schedule when a node receives an allocation message;

a mechanism allocating a dead-space record which indicates to said node that it is not to transmit during that period if said node is not sending a stream of data.

39. The apparatus of claim 35, further comprising:

a buffer and an allocation record that are combined into a single data structure;

wherein said ring-buffer is used to hold said schedule.

40. An apparatus for combining time-sensitive transmission with on-demand data transmission, such that packets involved in synchronous data transmissions are unaffected by other traffic, comprising:

a network interface component (NIC) for computing a schedule for a transmission medium indicating when various network devices are permitted to transmit on said medium;

means for indicating unscheduled portions of network bandwidth which are contended for by said network devices;

wherein each network device on the network maintains a representation of said schedule locally;

means for scanning a local copy of said schedule with a network interface component (NIC) when a NIC driver on a particular node is presented with a packet to be sent; and

means for inserting said packet into a first unscheduled space in said schedule large enough to hold said packet.

41. The apparatus of claim 40, wherein a streaming media packet is scheduled into said first unscheduled space if a conflict occurs between streaming media and an on-demand packet;

and

wherein a previously scheduled on-demand packet is deleted from said schedule and re-inserted in a first available slot, said on-demand packet having been replaced in said schedule by said streaming media packet.

42. The apparatus of claim 41, further comprising:

means for reserving on-demand transmission space.

43. The apparatus of claim 41, further comprising:

a timeout register having a set timeout value that is equal to the time for a next on-demand packet to be sent less the time it takes to transmit said packet.

44. An apparatus for managing the allocation of data capacity on a physically shared network segment, comprising:

a network interface component (NIC) for computing a schedule for a transmission medium indicating blocks of time when various network devices are permitted to transmit on said medium, wherein each scheduled block of time is represented by an allocation record, and wherein each node contains within it a copy of said schedule which is synchronized across all nodes by a periodic network-relative clock broadcast;

an implicit window reserved for on-demand transmission immediately succeeding a periodic broadcast of said network relative clock value when a node is first connected to said network to broadcast a request for download of a current schedule;

means for awaiting a next clock broadcast if said node cannot successfully send a packet in said window;

means for responding to said download request from said broadcast node with an on-demand transmission of said current schedule; and

means for beginning regular operation at said node once said schedule is received.

45. The apparatus of claim 44, wherein a first node to initialize on said network does not receive said periodic broadcast of said network relative clock;

wherein said node takes responsibility for broadcasting said network relative clock after waiting a predetermined amount of time;

wherein said node responds to other nodes as they initialize; and

wherein said nodes initializes it'"'"'s schedule to empty, such that nodes which join said network later are properly initialized.

46. The apparatus of claim 44, wherein each node continues to follow said transmission schedule if the node which is responsible for broadcasting said network relative clock fails;

wherein each node recognizes that said network relative clock has not been received after a predetermined time;

wherein said nodes broadcast to each other a copy of a local clock register at a next available opportunity; and

wherein a first successful clock broadcast after said previous clock node failed resets a timeout value and indicates a clock node, causing succeeding clock broadcasts from other nodes to be ignored.

47. The apparatus of claim 44, wherein a receiver node is responsible for broadcasting periodic on-demand packets indicating it'"'"'s continued interest in receiving a stream during the life of said stream;

wherein all nodes on said network use said packets to reset an internal count-down timer to a preferred value;

where each node assumes that said receiver node has failed or become inaccessible and releases an allocation record associated with said stream if said timer goes to zero; and

wherein a sender node ceases sending said streaming data, such that network capacity represented by said stream is properly recovered, even if both a sender and receiver fail.

48. The apparatus of claim 44, wherein a node examines it'"'"'s copy of said schedule and chooses an appropriate time for a first transmission when said node desires to reserve an allocation record for transmitting streaming media;

and

wherein said node broadcasts an allocation message to all nodes during a next available on-demand window.

49. The apparatus of claim 48, wherein each node, including a node requesting an allocation, attempts to update it'"'"'s schedule when it receives an allocation message broadcast;

wherein a new allocation request is ignored if a previously scheduled streaming media transmission conflicts with said new allocation request;

wherein a requesting node checks its copy of said schedule to see if said request is present after broadcasting;

wherein said requesting node may begin transmitting streaming media according to said schedule if said request succeeds; and

wherein said node must choose a new position in said schedule and broadcast a new request for it if said request did not succeed.

50. A method for managing the allocation of data capacity on a physically shared network segment, comprising these steps of:

providing a network interface component (NIC) comprising;

a free-running time-based counter that may be read or modified by a host processor at any time; and

providing a first register identical in size to said counter for receiving a host processor-specified value;

wherein said NIC is required to wait, without accessing a transmission medium, until the value in said first register matches that of said free-running time-based counter;

wherein said NIC must transmit said packet when said value in said first register matches that of said free-running time-based counter; and

wherein commands are explicitly given to said NIC to transmit a packet or to cancel a packet.