1. A database updates system comprising:
a processor configured via executing computer executable components stored in a computer readable memory, the computer executable components comprising:
a receiver component that receives a database update transaction;
a process component that reads stale data from a cache, wherein the stale data satisfies one or more relaxed freshness constraints associated with the transaction at read time, and the process component processes the transaction, the one or more freshness constraints automatically generated for each update transaction, wherein each data item or group of data has metadata associated therewith identifying when the data item or group of data was last modified and until when it is valid to facilitate definition and enforcement of relaxed freshness constraints;
a verification component which verifies that the one or more relaxed freshness constraints associated with the transaction are satisfied during processing and at commit time, wherein at least one of the relaxed freshness constraints requires that an aggregate computed over a read set of the transaction be within a specified percentage of a recent value, wherein the verification component enforces a time-drift bound relaxed freshness constraint via a determination of whether the last modified time of the most recently modified data item read by the transaction is less than the minimum time a data item read by the transaction is valid until plus a specified time period; and an update component for updating the database with data from the cache, wherein the relaxed freshness constraints are defined through snapshot consistency.
2. The system of claim 1, at least one of the relaxed freshness constraints is time bound and limits the amount of time between the time a version becomes invalid and the time it is read.
3. The system of claim 1, at least one of the relaxed freshness constraints is value bound and specifies a percentage a read data value can vary from the value of a valid version.
4. The system of claim 1, at least one of the relaxed freshness constraints requires that when more than one data item is read, the data items be read from the same snapshot and the data items be read within a specified time of each other.
5. The system of claim 1, the verification component enforces a time bound relaxed freshness constraint via a determination of whether a time stamp associated with the execution of the transaction is less than or equal to the valid until time associated with a data item read by the transaction plus some specified period of time.
6. The system of claim 1, the database update transaction comprising one or more partially ordered operations, wherein an operation comprises a relaxed freshness constraint specifying when to read a version of a data item from the cache based at least on how up-to-date the version is.
7. The system of claim 1, the one or more freshness constraints automatically generated for each update transaction based at least on a context of the transaction.
8. A database update system for relaxed currency constraints ensuring the result is relaxed currency serializable comprising:
a processor configured via executing computer executable components stored in a computer readable memory, the computer executable components comprising:
a receiver component that receives a database update transaction comprising relaxed freshness constraints that specify when to read a version of a data item from a cache based at least on how up-to-date the version is;
a process component that reads out-of-date data associated with the database update transaction from the cache, and verifies that the out-of-date data satisfies one or more relaxed freshness constraints associated with the transaction at read time, the one or more freshness constraints automatically generated for each update transaction based at least on a context of the transaction;
a verification component which verifies satisfaction of the one or more freshness constraints at commit time;
an update component that updates the database with the data item from the cache,
wherein the relaxed freshness constraints are defined through snapshot consistency;
a first relaxed freshness constraint that is value bound and specifies a percentage a read data value can vary from the value of a valid version;
a second relaxed freshness constraint requiring that when more than one data item is read, the data items be read from the same snapshot and the data items be read within a specified time of each other;
a third relaxed freshness constraint requiring that an aggregate computed over a read set of the transaction be within a specified percentage of a recent value;
wherein each data item or group of data has metadata associated therewith identifying when the data item or group was last modified and when it is valid until to facilitate definition and enforcement of the relaxed freshness constraints; and
the verification component enforces a time-drift bound relaxed freshness constraint via a determination of whether a last modified time of a most recently modified data item read by the transaction is less than a minimum time a data item read by the transaction is valid until plus a specified time period.
9. A method of transactional database interaction comprising:
reading stale cached data;
verifying that the read data satisfies one or more relaxed currency constraints associated with a transaction, wherein the one or more relaxed currency constraints specify when to read a version of a data item from a cache based at least on how up-to-date the version is;
updating a database with the data from the cache, wherein the stale cached data is justified by the one or more relaxed currency constraints; and
verifying the one or more relaxed currency constraints are satisfied at commit time, wherein the one or more currency constraints are automatically generated for each transaction based at least on a context of the transaction, and a relaxed currency constraint is satisfied when an aggregate computed over a set of data items read is within a specified percentage of a recent value,
wherein the relaxed currency constraints are defined through snapshot consistency at a particular point in time; and associating a last modified timestamp and a valid-till timestamp with each copy of data, wherein verifying satisfaction of one or more relaxed constraints comprises determining whether a timestamp associated with the transaction is less than or equal to the valid-till timestamp associated with the data being read plus a specified period of time.
10. The method of claim 9, a relaxed currency constraint is satisfied when data is read within a programmable time.
11. The method of claim 9, a relaxed currency constraint is satisfied when the value of data read is within a percentage of a value of a valid version.
12. The method of claim 9, a relaxed currency constraint is satisfied when more than one data item is read and the data items are read from the same snapshot.
13. The method of claim 9, a relaxed currency constraint is satisfied when the data items read are within a specified time of each other.
14. The method of claim 9, verifying satisfaction of one or more relaxed constraints comprises:
determining whether a set of data items to be read by the transaction is associated with the same snapshot; and
identifying the largest last-modified timestamp associated with a data item in the set;
identifying the smallest valid-till timestamp associated with a data item in the set; and
determining whether the largest last-modified timestamp is less than the smallest valid-till timestamp plus a specified period of time.
15. The method of claim 9, further comprising assigning the transaction a timestamp that is that is consistent with the relaxed constraints.
16. The method of claim 9, wherein each data item or group of data has metadata associated therewith identifying when a data item or group of data was last modified and until when it is valid to facilitate definition and enforcement of the relaxed currency constraints;
verifying that the read data satisfies one or more relaxed currency constraints associated with a transaction comprises enforcing a time-drift bound relaxed currency constraint via a determination of whether the last modified time of the most recently modified data item read by the transaction is less than the minimum time a data item read by the transaction is valid until plus a specified time period.
17. The method of claim 9, the one or more relaxed currency constraints comprising:
a first relaxed currency constraint that is satisfied when the value of data read is within a percentage of a value of a valid version;
a second relaxed currency constraint that is satisfied when more than one data item is read within a specified time of each other, and the data items are read from the same snapshot; and
a third relaxed currency constraint that is satisfied when an aggregate computed over a set of data items read is within a specified percentage of a recent value;
wherein each data item or group of data has metadata associated therewith identifying when a data item or group of data was last modified and until when it is valid to facilitate definition and enforcement of the relaxed currency constraints; and
enforcing a time-drift bound relaxed currency constraint by determining whether a last modified time of a most recently modified data item read by the transaction is less than a minimum time a data item read by the transaction is valid until plus a specified time period.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method, comprising:
receiving packets from a network at a network control device;
determining an end-to-end delay (T) of the received packets at the network control device;
determining an end-to-end transmission delay (X) of the received packets;
determining an end-to-end deterministic delay (D) of the received packets;
identifying fast packets of the received packets at the network control device;
determining an estimated path utilization based on the fast packets;
identifying back-to-back fast packet pairs of the fast packets; and
determining available bandwidth based on the estimated path utilization at the network control device.
2. The method of claim 1, wherein the end-to-end delay (T) of a given packet of the received packets is a difference between a time that the given packet exits the network and a timestamp indicating when the given packet entered the network.
3. The method of claim 2, where determining the end-to-end deterministic delay (D) comprises determining a time difference between a fast packet end-to-end delay (T) and the end-to-end transmission delay (X).
4. The method of claim 1, where identifying fast packets comprises identifying a packet of the received packets having a predetermined length as a fast packet of the predetermined length by determining the fast packet has a minimum end-to-end delay (T) value over all received packets whose length is the predetermined length.
5. The method of claim 1, where determining the estimated path utilization comprises determining a complement of a ratio of a number of fast packets received during a current time interval to a total number of packets received during the current time interval.
6. The method of claim 1, where determining available bandwidth comprises determining a product of the narrow link bandwidth and the estimated path utilization.
7. The method of claim 1, further comprising:
calculating packet dispersion to determine a narrow link bandwidth at the network control device; and
wherein determining the available bandwidth based on the estimated path utilization comprises determining the available bandwidth based on the estimated path utilization and the packet dispersion.
8. The method of claim 7, where identifying the back-to-back fast packet pairs comprises identifying a given packet pair of the fast packets where a difference in ingress timestamps of packets of the given packet pair is less than a predetermined threshold (\u03b4) and lengths of the packets of the given packet pair are equal.
9. The method of claim 8, where calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the fast packets (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.
10. The method of claim 9, where calculating packet dispersion to determine the narrow link bandwidth comprises determining a ratio LC, where L is the packet length of each packet of the given packet pair and C is a link capacity.
11. The method of claim 10, where determining the available bandwidth comprises determining a product of the narrow link bandwidth and the estimated path utilization.
12. The method of claim 7, where calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the packet pairs (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.
13. The method of claim 7, where determining the available bandwidth comprises determining a product of the narrow link bandwidth and the estimated path utilization.
14. An apparatus, comprising:
a traffic sensor configured to receive a plurality of packets from a network; and
a bandwidth estimator configured to perform operations comprising:
identifying a plurality of fast packets from the plurality of packets,
determining an estimated path utilization based on the plurality of fast packets,
identifying back-to-back fast packet pairs of the plurality of fast packets, and
determining available bandwidth based on the estimated path utilization.
15. The apparatus of claim 14, where the operations further comprise:
determining an end-to-end delay of at least one packet of the plurality of packets;
determining an end-to-end transmission delay of at least one packet of the plurality of packets;
determining an end-to-end deterministic delay of at least one packet of the plurality of packets; and
determining a narrow link bandwidth for at least one link of the network.
16. The apparatus of claim 14, where the at least one link comprises a work-conserving link.
17. A tangible program storage device, readable by a machine, embodying instructions that, in response to execution by the machine, cause the machine to perform operations comprising:
determining an end-to-end delay (T) of received packets;
determining an end-to-end transmission delay (X) of the received packets;
determining an end-to-end deterministic delay (D) of the received packets;
identifying fast packets of the received packets;
determining an estimated path utilization based on the fast packets;
identifying back-to-back fast packet pairs of the fast packets; and
determining available bandwidth based on the estimated path utilization.
18. The tangible program storage device of claim 17, wherein the end-to-end delay (T) for a given packet of the received packets is a difference between a time the given packet exits a network and a timestamp indicating when the given packet entered the network.
19. The tangible program storage device of claim 18, where determining the end-to-end deterministic delay (D) comprises determining a time difference between a fast packet end-to-end delay (T) and the end-to-end transmission delay (X).
20. The tangible program storage device of claim 17, where identifying fast packets comprises identifying a packet of the received packets having a predetermined length as a fast packet of the predetermined length by determining the fast packet has a minimum end-to-end delay (T) value over all received packets whose length is the predetermined length.
21. The tangible program storage device of claim 17, where determining the estimated path utilization comprises determining a complement of a ratio of a number of fast packets received during a current time interval to a total number of packets received during the current time interval.
22. The tangible program storage device of claim 17, wherein the operations further comprise:
calculating packet dispersion to determine a narrow link bandwidth; and
wherein determining the available bandwidth based on the estimated path utilization comprises determining the available bandwidth based on the estimated path utilization and the packet dispersion.
23. The tangible program storage device of claim 22, where calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the packet pairs (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.
24. A method, comprising:
receiving packets from a network at a network control device;
determining an end-to-end delay (T) of the received packets at the network control device;
determining an end-to-end transmission delay (X) of the received packets;
determining an end-to-end deterministic delay (D) of the received packets;
identifying fast packets of the received packets at the network control device;
determining an estimated path utilization based on the fast packets; and
identifying back-to-back fast packet pairs of the fast packets at the network control device.
25. The method of claim 24, wherein the end-to-end delay (T) for a given packet of the received packets is a difference between a time the given packet exits a network and a timestamp indicating when the given packet entered the network.
26. The method of claim 25, where said determining the end-to-end deterministic delay (D) comprises determining a time difference between a fast packet end-to-end delay (T) and the end-to-end transmission delay (X).
27. The method of claim 24, where identifying fast packets comprises identifying a packet of the received packets having a predetermined length as a fast packet of the predetermined length by determining the fast packet has a minimum end-to-end delay (T) value over all received packets whose length is the predetermined length.
28. The method of claim 24, where determining the estimated path utilization comprises determining a complement of a ratio of a number of fast packets received during a current time interval to a total number of packets received during the current time interval.
29. The method of claim 24, further comprising:
calculating packet dispersion to determine a narrow link bandwidth at the network control device.
30. The method of claim 29, where identifying back-to-back fast packet pairs comprises identifying a given packet pair of the fast packets where a difference in ingress timestamps of packets of the given packet pair is less than a predetermined threshold (\u03b4) and lengths of the packets of the given packet pair are equal.
31. The method of claim 30, where calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the received packets (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.
32. The method of claim 29, where calculating packet dispersion to determine the narrow link bandwidth comprises determining a ratio LC, where L is the packet length of each packet of the given packet pair and C is a link capacity.
33. The method of claim 29, where said calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the received packets (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.
34. A tangible program storage device, readable by a machine, embodying instructions that, in response to execution by the machine, cause the machine to perform operations comprising:
determining an end-to-end delay (T) of received packets;
determining an end-to-end transmission delay (X) of the received packets;
determining an end-to-end deterministic delay (D) of the received packets;
identifying fast packets of the received packets;
determining an estimated path utilization based on the fast packets; and
identifying back-to-back fast packet pairs of the fast packets.
35. The tangible program storage device of claim 34, wherein the end-to-end delay (T) for a given packet of the received packets is a difference between a time the given packet exits a network and a timestamp indicating when the given packet entered the network.
36. The tangible program storage device of claim 35, where determining the end-to-end deterministic delay (D) comprises determining a time difference between a fast packet end-to-end delay (T) and the end-to-end transmission delay (X).
37. The tangible program storage device of claim 34, where identifying fast packets comprises identifying a packet of the received packets having a predetermined length as a fast packet of the predetermined length by determining the fast packet has a minimum end-to-end delay (T) value over all received packets whose length is the predetermined length.
38. The tangible program storage device of claim 34, where determining the estimated path utilization comprises determining a complement of a ratio of a number of fast packets received during a current time interval to a total number of packets received during the current time interval.
39. The tangible program storage device of claim 34, wherein the operations further comprise:
calculating packet dispersion to determine a narrow link bandwidth.
40. The tangible program storage device of claim 39, where said calculating packet dispersion comprises measuring a difference (\u0394) in end-to-end delay measurements of a given packet pair of the packet pairs (\u0394=T1\u2212T2), where T1 is an end-to-end delay of a lead packet of the given packet pair and T2 is an end-to-end delay of a second packet of the given packet pair.