System and method for scheduling and executing data transfers over a network

• US 20020083185A1
• Filed: 08/21/2001
• Published: 06/27/2002
• Est. Priority Date: 12/22/2000
• Status: Active Grant

• Current Assignee: Comcast Cable Communications Management LLC (Comcast Corporation)
• Original Assignee: Radiance Technologies, Inc. (Comcast Corporation)
• Inventors: Agraz, David, Ruttenberg, John C., Lichtenstein, Walter D., Tobagi, Fouad A., Lemke, David, Munshi, Ashfaq A.
• Granted Patent: US 7,065,586 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for scheduling transfers of data through a network, the system comprising a transfer module at each node in the network, the transfer module being configured to schedule data transfers according to available resources at each node. In one embodiment, the transfer module includes a scheduling module, a routing module, and an execution module. The scheduling module at each node evaluates a single hop request in view of objectives, such as a deadline, and the available resources at that node, for example transmit bandwidth, receive bandwidth, and storage space, all of which may change as a function of time.

Claims

1. A system for scheduling a data transfer over a communication network, comprising:

a node configured to send data;

a node configured to receive data; and

a transfer module at each node configured to evaluate a data transfer request in view of satisfying objectives in accordance with resources at each node.

2. The system of claim 1, wherein the resources at each node include transmit bandwidth.

3. The system of claim 1, wherein the resources at each node include receive bandwidth.

4. The system of claim 1, wherein the resources at each node include storage space.

5. The system of claim 1, wherein the resources at each node vary as a function of time.

6. The system of claim 1, wherein the objectives include a deadline for the delivery of the requested data to the node configured to receive data.

7. The system of claim 1, wherein the objectives include minimizing the cost of delivery of data to the node configured to receive data.

8. The system of claim 1, wherein the transfer module evaluates the data transfer request in view of available transmit bandwidth at the node configured to send data, and available receive bandwidth at the node configured to receive the data.

9. The system of claim 1, wherein the transfer module located at the node configured to receive data transmits a message indicating available receive bandwidth to the transfer module located at the node configured to send data.

10. The system of claim 1, further comprising a node configured to send data and to receive data.

11. The system of claim 1, wherein the transfer module includes an admission control module configured to accept or deny a data transfer request from a user.

12. The system of claim 11, wherein the admission control module includes a soft rejection routine.

13. The system of claim 12, wherein the soft rejection routine suggests a different deadline for a denied data transfer request from the user.

14. The system of claim 12, wherein the soft rejection routine is configured to offer to place a denied data transfer request on a waiting list.

15. The system of claim 1, wherein the transfer module includes a scheduling module.

16. The system of claim 15, wherein the scheduling module is configured to generate a single hop request that includes the identity of the data, available resources at that node, and a deadline for delivery.

17. The system of claim 15, wherein the scheduling module is configured to evaluate a single hop request that includes the identity of requested data and a deadline for delivery, and to respond to the single hop request with a denial or an acceptance.

18. The system of claim 15, wherein the scheduling module includes a preemption module configured to preempt scheduled transfers for transfers having a higher priority.

19. The system of claim 15, wherein the scheduling module includes a feasibility test configured to determine whether a single hop request is feasible.

20. The system of claim 15, wherein the scheduling module includes an explicit scheduling routine configured to determine if an explicit schedule for a single hop data transfer can be made.

21. The system of claim 1, wherein the transfer module includes a routing module configured to identify possible sources of requested data.

22. The system of claim 1, wherein the routing modules identifies possible sources of requested data using proxy lists.

23. The system of claim 1, wherein the transfer module includes an execution module configured to execute scheduled data transfers.

24. The system of claim 23, wherein the execution module executes scheduled data transfers ahead of schedule using a dynamic request protocol.

25. The system of claim 23, wherein the execution module executes scheduled data transfers such that the scheduled data transfers are completed by their deadlines.

26. The system of claim 23, wherein the execution module uses available bandwidth at nodes in the network to execute data transfers ahead of schedule.

27. The system of claim 1, wherein the transfer module includes a slack module configured to determine an amount of reserved resources for a node.

28. The system of claim 1, wherein the transfer module includes a padding module configured to determine an amount of time to add to time required for completion of a data transfer.

29. The system of claim 1, wherein the transfer module includes a priority module configured to assign a priority to the data transfer request.

30. The system of claim 1, wherein the transfer module includes an error recovery module configured to maintain a current state of the transfer module to allow a node to be restarted.

31. The system of claim 1, wherein the data transfer request includes an earliest deadline for arrival of the data at the node configured to receive data, a latest deadline for arrival of the data at the node configured to receive data, and a minimum time available during which the data remains available to a user at the node configured to receive data.

32. The system of claim 1, wherein the transfer module at the node configured to receive data includes an admission control module configured to accept or deny a data transfer request from a user.

33. The system of claim 32, wherein the admission control module sends a scheduling request to a scheduling module, the scheduling request including an identification of the data and a deadline.

34. The system of claim 33, wherein the transfer module includes a routing module configured to identify possible source nodes for the data.

35. The system of claim 34, wherein a scheduling module at each possible source node identified by the routing module evaluates a single hop request from the scheduling module of the node configured to receive data.

36. The system of claim 35, wherein the scheduling module at one of the possible source nodes evaluates the single hop request using a feasibility test.

37. The system of claim 35, wherein the scheduling module at one of the possible source nodes evaluates the single hop request by attempting to determine an explicit schedule for the single hop request.

38. The system of claim 35, wherein the scheduling module at one of the possible source nodes places a denied single hop request on a waiting list.

39. The system of claim 35, wherein the scheduling module at one of the possible source nodes suggests an alternative deadline for a denied single hop request.

40. The system of claim 35, wherein each single hop request includes an identification of the data and a deadline.

41. The system of claim 2, wherein the transmit bandwidth includes allocated bandwidth and available bandwidth.

42. The system of claim 2, wherein the transmit bandwidth includes allocated bandwidth, available bandwidth, and reserved bandwidth.

43. The system of claim 3, wherein the receive bandwidth includes allocated bandwidth and available bandwidth.

44. The system of claim 3, wherein the receive bandwidth includes allocated bandwidth, available bandwidth, and reserved bandwidth.

45. The system of claim 15, wherein the transfer module includes an execution module configured to execute accepted data transfers under guidance of execution instructions from the scheduling module.

46. The system of claim 45, wherein an execution module at the node configured to receive data responds to dynamic conditions at that node by sending dynamic requests to the node configured to send data.

48. The method of claim 47, wherein the step of configuring a sender includes establishing transmit bandwidth resources.

49. The method of claim 47, wherein the step of configuring a receiver includes establishing receive bandwidth resources and storage space resources.

50. The method of claim 47, further comprising the step of transferring the data from the sender to an intermediary that stores a copy of the data.

51. The method of claim 50, further comprising the step of transferring the data from the intermediary to the receiver.

52. The method of claim 47, wherein the step of evaluating a request includes considering available transmit bandwidth at the sender, available receive bandwidth at the receiver, and available storage space at the receiver.

53. The method of claim 47, wherein the step of evaluating a request includes evaluating single hop requests for transfers between specific nodes in the communication network.

54. The method of claim 53, wherein evaluating a single hop request includes a feasibility test.

55. The method of claim 53, wherein each single hop request includes an identification of the data and a deadline.

56. The method of claim 47, wherein the resources at the receiver include allocated receive bandwidth and available receive bandwidth.

57. The method of claim 47, wherein the resources at the receiver vary as a function of time.

58. The method of claim 47, wherein the resources at the sender include allocated transmit bandwidth and available transmit bandwidth.

59. The method of claim 47, wherein the resources at the sender vary as a function of time.

60. The method of claim 47, further comprising the step of placing an unaccepted data transfer request on a waiting list.

61. The method of claim 47, further comprising the step of offering an alternative deadline for an unaccepted data transfer request.

62. The method of claim 47, wherein the request to transfer the data includes an earliest deadline for arrival of the data at the receiver, a latest deadline for arrival of the data at the receiver, and a minimum time available during which the data remains available to a user at the receiver.

47. A method for scheduling a data transfer over a communication network, comprising the steps of:

configuring a sender to send data;

configuring a receiver to receive the data;

evaluating a request to transfer the data from the sender to the receiver based on resources at the sender and at the receiver; and

if the request is accepted, scheduling a data transfer according to the request and the resources at the sender and at the receiver.

63. A system for scheduling a data transfer over a communication network, comprising:

means for sending data;

means for receiving data; and

means for evaluating a request to transfer the data based on resources at the means for sending data and at the means for receiving data; and

if the request is accepted, means for scheduling a data transfer according to the request and the resources.

64. A method for scheduling a data transfer over a network, comprising the steps of:

identifying a data file and a deadline window for delivery of the data file to a receiver;

sending the identity of the data file and the deadline window to an admission control module at the receiver, the admission control module being configured to prepare a scheduling request that includes the identity of the data file and a deadline within the deadline window;

sending the scheduling request to a scheduling module of the receiver;

querying a routing module at the receiver to identify a possible source node for the data file;

sending a single hop request from the scheduling module of the receiver to a scheduling module of the possible source node, the single hop request including the identity of the data file and the deadline;

evaluating the single hop request by the scheduling module at the possible source node, where the single hop request is evaluated in view of the size of the data file, the deadline, and available transmit bandwidth at the possible source node;

sending a reply to the single hop request to the scheduling module of the receiver indicating whether the single hop request is accepted or denied by the possible source node; and

if the single hop request is accepted, reserving resources at the receiver, reserving resources at the possible source node, scheduling a time to begin transferring the data file from the possible source node to the receiver, and sending a reply to the scheduling request to the admission control module.

65. The method of claim 64, wherein if the single hop request is denied, the scheduling module of the receiver sends another single hop request to another possible source node identified by the routing module.

66. The method of claim 64, wherein if the single hop request is denied, the reply to the single hop request includes a suggestion for an alternate deadline for delivery of the data file to the receiver.

68. The system of claim 67, wherein the transfer module interrogates each node in the network to determine the resources at each node.

69. The system of claim 67, wherein the transfer module is further configured to manage execution of scheduled data transfers.

70. The system of claim 67, wherein the objectives include meeting a deadline for completion of a data transfer.

71. The system of claim 67, wherein the objectives include minimizing the cost of a data transfer.

72. The system of claim 67, wherein the resources at each node include bandwidth.

73. The system of claim 67, wherein the resources at each node include storage space.

74. The system of claim 69, wherein the transfer module executes scheduled data transfers ahead of schedule using a dynamic request protocol.

75. The system of claim 69, wherein the transfer module executes scheduled data transfers such that the scheduled data transfers are completed by their deadlines.

76. The system of claim 69, wherein the transfer module uses available bandwidth at nodes in the network to execute data transfers ahead of schedule.

67. A system for scheduling and executing data transfers over a network, comprising:

a node configured to send data;

a node configured to receive data; and

a central control node including a transfer module configured to evaluate data transfer requests in view of satisfying objectives in accordance with resources at each node.