Frame protocol and scheduling system

• US 7,792,121 B2
• Filed: 01/03/2003
• Issued: 09/07/2010
• Est. Priority Date: 01/03/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Massarenti, Davide, Yuval, Gideon A., Thompson, R. Donald III, Cermak, Gerald F., Corbea, Cosmin A.
• Primary Examiner(s): Ahmed; Salman
• Application Number:
  US10/336,240
• Publication Number:
  US 20040131014A1
• Time in Patent Office: 2,804 Days
• Field of Search: 370/395.4, 370/395.41, 370/395.42, 370/395.32, 370/468, 370/470, 370/471, 370/472, 370/473, 370/474, 370/458, 370/462, 370/498
• US Class Current: 370/395.4
• CPC Class Codes: H04H 60/06 Arrangements for scheduling broadcast services or broadcast-related services
• CPC Class Codes: H04H 60/14 Arrangements for conditional access to broadcast information or to broadcast-related services
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 51/04 Real-time or near real-time messaging, e.g. instant messaging [IM]
• CPC Class Codes: H04L 51/226 Delivery according to priorities
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04W 72/23 in the downlink direction of a wireless link, i.e. towards a terminal
• CPC Class Codes: H04W 72/30 Resource management for broadcast services

Abstract

Serialized data from broadcast services is provided to a broadcast server for transmitting to one or more client devices. The serialized data may correspond to shared data, private data, or control data. Data is scheduled for transmission based on weighted priorities including quality of service metrics. The transmission frame is arranged according to a frame protocol that includes provisions for a table of contents indexing system for the shared data. Packets of shared data are formatted based on criteria that is known by the particular broadcast service and corresponding application that is resident on the client device. The client device receives the table of contents at the transport layer, and notifies applications of data that will be available in the next frame. Applications submit prioritized requests to the transport layer, requesting data in the next frame. Data is retrieved by the transport layer, and deserialized by handlers for each application.

Claims

1. A tangible computer-readable storage memory device having computer executable instructions stored thereon for formatting a data structure for use in communicating transmission frames from a server device to a client device, comprising:

a frame header packet that is located in a predetermined slot of a current transmission frame, wherein the frame header packet includes a table of contents locations definition field;

a table of content packet that is located in a flexible slot location of the current transmission frame, wherein the flexible slot location is determined by an entry in the table of contents locations definition field of the frame header packet, wherein the table of contents packet identifies shared data streams that are located in a subsequent transmission frame; and

a packet that is located in another flexible slot location of the current transmission frame, wherein the packet is associated with an entry in another table of contents packet from a previous transmission frame, wherein each table of contents packet is a forward-looking index that indexes packets in subsequent transmission frames.

2. The tangible computer-readable storage memory device of claim 1, wherein each transmission frame includes 20,480 segments that are broken into 16 segment groups of 1280 segments, wherein each segment includes 68 symbols, and wherein each frame maps into 1280 logical packets that are identified by a slot in the transmission frame.

3. The tangible computer-readable storage memory device of claim 1, wherein the frame header packet is located in the first slot of the transmission frame.

4. The tangible computer-readable storage memory device of claim 1, wherein each frame header further includes fields for a frame number, a time stamp, a time zone offset, and a broadcast region definition.

5. The tangible computer-readable storage memory device of claim 1, wherein the frame header packet further comprises a frame number field that has an associated value that is different from values associated with the corresponding frame number fields of previous and subsequent transmission frames such that replay attacks are detected by client devices.

6. The tangible computer-readable storage memory device of claim 1, wherein the frame header packet further comprises:

a time stamp field that designates the time for the beginning of the frame transmission.

7. The tangible computer-readable storage memory device of claim 1, wherein the frame header packet further comprises:

a time zone offset field that indicates a time zone for the geographic region of each frame transmission.

8. The tangible computer-readable storage memory device of claim 1, wherein the frame header packet further includes fields for a time stamp and a frame number, wherein the time stamp and the frame number are used to encrypt packets in the transmission frame such that client devices authenticate the frame header and ignore transmission frames that correspond to variation replay attacks.

9. The tangible computer-readable storage memory device of claim 8, wherein the encrypted packets are encrypted with an encryption key and an initialization vector, wherein the initialization vector is determined by the values from either the frame number field or the time stamp field.

10. The tangible computer-readable storage memory device of claim 1, wherein each table of contents locations definition field identifies a slot location, a format type, an error correction mode, and an error correction setting for a corresponding table of contents.

11. The tangible computer-readable storage memory device of claim 1, wherein each table of contents locations definition field further comprises:

indexes to tables of contents packets, wherein each index includes a slot location and a format type, wherein the slot location identifies a location for the table of contents packet within the transmission frame, and the format type identifies a particular class of client device.

12. The tangible computer-readable storage memory device of claim 1, wherein each table of contents packet further comprises:

a set of range descriptors, wherein each particular range descriptor includes fields for an initial position and a number of slots that are associated with a particular range.

13. The tangible computer-readable storage memory device of claim 12, wherein the initial position corresponds to a packet number that is associated with the beginning of the particular range in the transmission frame.

14. The tangible computer-readable storage memory device of claim 12, wherein each slot that is associated with the particular range has a corresponding slot descriptor that includes fields for a service ID, a packet count, a stream locator, an error correction setting, and a frame reservation.

15. The tangible computer-readable storage memory device of claim 12, wherein each slot that is associated with the particular range has a corresponding slot descriptor that includes a service ID field, wherein each service ID field identifies a particular broadcast service that is associated with the slot such that logical packets associated with the slot descriptor are also associated with the particular broadcast service.

16. The tangible computer-readable storage memory device of claim 15, wherein the particular broadcast service is associated with a data type, wherein each logical packet is formatted according to the data type for use by an application program that is also associated with the particular broadcast service on a client device.

17. The tangible computer-readable storage memory device of claim 16, wherein the data type corresponds to one of a compact data type, a sparse data type, and a long data type.

18. The tangible computer-readable storage memory device of claim 12, wherein each particular slot that is associated with the particular range has a corresponding slot descriptor, wherein the slot descriptor includes a packet count field that identifies a number of packets that are associated with the particular slot in the frame transmission.

19. The tangible computer-readable storage memory device of claim 12, wherein each particular slot that is associated with the particular range has a corresponding slot descriptor, wherein the slot descriptor includes a stream locator field that identifies an opaque value that is used by the application-level data handlers that are associated with a particular broadcast service.

20. The tangible computer-readable storage memory device of claim 12, wherein each slot that is associated with a range descriptor has a corresponding slot descriptor, wherein the slot descriptor includes a service ID field and a frame reservation field, wherein the service ID field identifies the broadcast service that is associated with the particular slot in the frame transmission, and wherein the frame reservation field indicates a number of frame transmissions for which the slot is assigned to the broadcast service.

21. The tangible computer-readable storage memory device of claim 1, wherein the transmission frame is divided into five partitions, a pseudo-randomly assigned slot in each of the five partitions is assigned to a client for each transmission, and wherein the transmission frame includes a portion or all of a private message for the client in one or more of the pseudo randomly assigned slots.

22. The tangible computer-readable storage memory device of claim 21, wherein the pseudo-randomly assigned slots are determined from at least one member of a group comprising a subscriber ID that is associated with the client, a current frame number, and a hash function.

23. The tangible computer-readable storage memory device of claim 21, wherein the private message spans a number of logical packets that each includes a private message header, wherein the private message header includes fields for message ID, fragments in message, and fragment index, wherein the private message is identified by the message ID field, the number of logical packets is identified by the fragments in message field, and each logical packet is identified by the fragment index.

24. A tangible computer-readable storage memory device having computer executable instructions stored thereon for formatting a data structure for use in communicating transmission frames from a server device to a client device, comprising:

a frame header packet that is located in a predetermined slot of a current transmission frame, wherein the frame header packet includes a table of contents locations definition field; and

wherein the frame header packet further comprises;

a region definition field that includes a region ID, a code name, and a list of frequencies, wherein the region ID identifies the current broadcast region, the code name provides a description of the current broadcast region, and the list of frequencies corresponds to radio frequencies that are available in the current broadcast region;

a table of content packet that is located in a flexible slot location of the current transmission frame, wherein the flexible slot location is determined by an entry in the table of contents locations definition field of the frame header packet, wherein the table of contents packet identifies shared data streams that are located in a subsequent transmission frame; and

a packet that is located in another flexible slot location of the current transmission frame, wherein the packet is associated with an entry in another table of contents packet from a previous transmission frame, wherein each table of contents packet is a forward-looking index that indexes packets in subsequent transmission frames.

25. A tangible computer-readable storage memory device having a computer executable program stored thereon for formatting a data structure for use in communicating transmission frames from a server device to a client, comprising:

logical packets that are identified with a corresponding slot in the transmission frame, wherein the logical packets are divided into partitions, wherein the client is pseudo-randomly assigned to slots, wherein each slot is pseudo-randomly assigned to the partitions, and wherein a logical packet that is associated with one of the pseudo-randomly assigned slots includes a portion or all of a private message for the client;

wherein the packets include a frame header packet that is located in a predetermined slot, wherein the frame header packet includes a table of contents locations definition field, and wherein the packets include a table of contents packet that is located in a flexible slot location, wherein the flexible slot location is determined by an entry in the table of contents locations definition field.

26. The tangible computer-readable storage memory device of claim 25, wherein each transmission frame includes 20,480 segments that are broken into 16 segment groups of 1280 segments, wherein each segment includes 68 symbols, and wherein each frame maps into the 1280 logical packets.

27. The tangible computer-readable storage memory device of claim 25, wherein the pseudo-randomly assigned slots are determined from at least one member of a group comprising a subscriber ID that is associated with the client, a current frame number that is associated with a transmission frame, and a hash function.

28. The tangible computer-readable storage memory device of claim 25, wherein the private message spans a number of logical packets that each include a private message header, wherein the private message header includes fields for message ID, fragments in message, and fragment index, wherein the private message is identified by the message ID field, the number of logical packets is identified by the fragments in message field, and each logical packet is identified by the fragment index.

29. The tangible computer-readable storage memory device of claim 25, wherein the pseudo-random slot assignments is determined by:

concatenating a subscriber ID with the current frame number to form an array, creating a hash value from the array, and limiting the hash value to a size that is associated with each partition.

30. The tangible computer-readable storage memory device of claim 29, wherein the current frame number is different for each subsequent transmission frame such that the slot locations that are assigned to each client changes for each subsequent transmission frame.

31. The tangible computer-readable storage memory device of claim 25, wherein logical packets that are associated with a private message are encrypted with an encryption string and a unique control key.

32. The tangible computer-readable storage memory device of claim 31, wherein a unique identifier that is associated with the client is determined by the unique control key.

33. A method for scheduling frame transmissions from a server to a client device, comprising:

using a processor, sending a request to a shared data service handler for needs, wherein the shared data service handler is associated with a registered broadcast service;

using the processor, receiving needs from the shared data service handler in response to the request, wherein each need requested by the shared data service handler includes a requested priority level and a requested allocation of packets for a transmission slot;

using the processor, prioritizing the needs that are received from the shared data service handler;

using the processor, allocating slots for the next transmission frame based on the prioritized needs;

using the processor, creating a table of contents for the next transmission based on the allocated slots;

requesting packets from the shared data service handler for the current transmission frame;

receiving packets from the shared data service handler for the current transmission frame, wherein the received packets are associated with a previous table of contents from a previous transmission frame;

assigning the table of contents for the next transmission to an unused slot in the current transmission frame;

assembling packets in the current transmission frame according to previous slot allocations from a previous table of contents, and the assigned slot for the table of contents for the next transmission frame; and

assembling a frame header for the current transmission frame, wherein the header frame references the location for the table of contents in the current transmission frame.

34. The method of claim 33, further comprising:

overriding an allocated slot assignment for a private message packet.

35. The method of claim 33, further comprising:

determining a pseudo-random slot assignment within a pseudo-randomly assigned partition for each private message slot, prioritizing private message slot assignments, and assigning unused slots to the private message slots on the prioritization.

36. The method of claim 35, wherein the pseudo-random slot and partition assignments are determined by a hash that employs a unique ID, the frame number, and the packet number of the private message.

37. The method of claim 35, wherein determining a pseudo-random slot assignment with a pseudo-randomly assigned partition includes:

computing a hash value for partition assignment using the unique ID and the slot index;

truncating the hash value for the partition assignment by the total number of partitions in the frame transmission to define the initial position for the unique ID;

adding the frame number to the truncated hash value so that each client cycles through all the partitions;

determining the starting and ending position of the partition;

computing a hash value for slot assignment using the unique ID, the frame number, and the slot index;

collapsing the hash value for the slot assignment so the collapsed value fits within the size of the selected partition; and

adding the start position of the partition to the collapsed hash value to determine the packet number for the requested slot.

38. The method of claim 35, encrypting packets associated with the private message, wherein an encryption process uses either a frame number or a packet number to determine an initialization vector for an encryption process, wherein the encryption process uses the initialization vector and a subscription key for encryption.

39. The method of claim 33, wherein creating a table of contents for the next transmission based on the allocated slots comprises:

determining a slot number for a broadcast service, assigning the slot number to the broadcast service, and setting the service identifier field of the table of contents entry to indicate the broadcast service.

40. The method of claim 33, wherein each need requested by each shared data service handler further includes a requested frame reservation that designates the number of transmission sequences that a slot assignment will persist.

41. The method of claim 33, further comprising:

setting frame reservation fields for each assigned slot, wherein each frame reservation filed designates a number of transmission sequences that a slot assignment will persist.

42. The method of claim 41, further comprising:

decrementing frame reservation fields for each assigned slot from each preceding frame transmission, and reclaiming each slot assignment that has a frame reservation field with a value of zero.

43. The method of claim 41, further comprising:

updating locator fields that are associated with an assigned slot.

44. The method of claim 41, further comprising:

submitting a request to each shared data service handler to update locator fields that are associated with each assigned slot, and receiving updated locator fields from the shared data service handler in response to the request.

45. The method of claim 41, further comprising:

requesting an override from a private data service handler, receiving an override request from the private data service handler, assigning a slot in the next frame transmission to a private message in response to the override request.

46. A method for scheduling frame transmissions from a server to a client device, comprising:

using a processor, sending a request to a shared data service handler for needs, wherein the shared data service handler is associated with a registered broadcast service;

using the processor, receiving needs from the shared data service handler in response to the request, wherein each need requested by the shared data service handler includes a requested priority level and a requested allocation of packets for a transmission slot;

using the processor, prioritizing the needs that are received from the shared data service handler;

using the processor, allocating slots for the next transmission frame based on the prioritized needs;

using the processor, creating a table of contents for the next transmission based on the allocated slots;

using the processor, requesting packets from the shared data service handler for the current transmission frame;

using the processor, receiving packets from the shared data service handler for the current transmission frame, wherein the received packets are associated with a previous table of contents from a previous transmission frame;

using the processor, assigning the table of contents for the next transmission to an unused slot in the current transmission frame;

using the processor, assembling packets in the current transmission frame according to previous slot allocations from a previous table of contents, and the assigned slot for the table of contents for the next transmission frame;

assembling a frame header for the current transmission frame, wherein the header frame references the location for the table of contents in the current transmission frame;

assigning a value to a frame number field, wherein the value associated with the frame number field is different for successive frames;

assigning a value to a time field, wherein the value associated with the time field is different for successive frames; and

arranging a frame header that includes the frame number field, table of contents locator field, and time field, wherein the frame header corresponds to a packet in the frame transmission that always occurs at the same logical packet number.

47. A method for scheduling retrieval of data on a client device, comprising:

using a processor, identifying a frame header that includes a table of contents locations definition field;

using the processor, locating a table of contents at a location described in the table of contents locations definition field of the frame header;

using the processor, extracting the table of contents from a current transmission frame;

using the processor, identifying an entry in the table of contents with a registered application;

using the processor, sending a request to the registered applications that is associated with the entry in the table of contents;

receiving a data request from the application, wherein the data request includes a requested priority level;

sorting the data requests based on priority level;

requesting highest priority packets from a network layer, wherein the highest priority packets are identified with slots in a subsequent transmission frame;

receiving packets from the network layer that are associated with the subsequent transmission frame;

forwarding the received packets to the handler for the registered application;

assembling a message from the received packets with the handler for the registered application; and

forwarding a completed message from the handler to the application when the message is assembled.

48. The method for scheduling retrieval of data as in claim 47, further comprising:

registering an application with a transport layer in the client device, and connecting a handler to the transport layer for the registered application.

49. The method for scheduling retrieval of data as in claim 48, further comprising:

disconnecting the handler from the transport layer in response to a terminate request from the application.

50. The method for scheduling retrieval of data as in claim 47, wherein extracting the table of contents includes:

retrieving the table of contents from the identified location in the current transmission frame, wherein the table of contents is a forward-looking index into a subsequent transmission frame.

51. The method for scheduling retrieval of data as in claim 47, further comprising:

retrieving a time stamp from a frame header in the current frame transmission, and synchronizing an internal clock in the client device based on the time stamp.

52. The method for scheduling retrieval of data as in claim 47, further comprising:

authenticating the current frame transmission based on a frame number and time stamp such that replay attacks are ignored by the client device, wherein the frame number is either estimated from an earlier transmission frame, or extracted from a frame header.

53. The method for scheduling retrieval of data as in claim 47, further including:

at least one member of a group comprising computing a frame number and retrieving the frame number from a frame header in the current frame transmission, decrypting packets with a feedback-mode packet encryption that is seeded by the frame number such that variation replay attacks are ignored by the client device.

54. The method for scheduling retrieval of data as in claim 47, further comprising:

using a frame number, a time stamp, and a packet number to generate an initial value for an decryption process that uses an encryption key, wherein the encryption key is employed by the client device to authenticate retrieved data that is associated with a broadcast service.

55. The method for scheduling retrieval of data of claim 47, further comprising:

authenticating logical packets associated with retrieved data, comprising;

decrypting the logical packet;

checking the CRC of the decrypted logical packet;

applying error correction when an invalid CRC of the decrypted logical packet is identified;

decrypting the error-corrected logical packet;

checking the CRC of the decrypted error-corrected packet;

failing authentication when the decrypted logical packet and the decrypted error corrected logical packet have invalid CRCs; and

successfully authentication when either the logical packet or the error corrected logical packet have valid CRCs.

56. The method for scheduling retrieval of data as in claim 47, wherein identifying entries in the table of contents with registered applications further comprises:

extracting a service ID from the table of contents, wherein the service ID identifies the registered application.

57. The method for scheduling retrieval of data as in claim 47, further comprising:

updating priority levels that are associated with the requested priority levels such that quality of service is maintained for each application on the client device.

58. The method for scheduling retrieval of data as in claim 47, further comprising:

receiving a packet from the network layer that is associated with another subsequent transmission frame when the table of contents fails to be retrieved and the frame reservation field from a prior table of contents indicates that the slot assignment associated with the received packet is sticky.

59. The method for scheduling retrieval of data as in claim 47, wherein messages are formatted according to a data type that is associated with a handler for an application on the client device, wherein the data type correspond to one of a compact data type, a sparse data type, and a long data type.

60. The method for scheduling retrieval of data as in claim 59, wherein the handler for a compact data type uses a stream locator from a table-of-contents slot descriptor to determine a starting location for the first compact message in the slot, and subsequent one-packet messages follow the starting location, offset by one packet at a time.

61. The method for scheduling retrieval of data as in claim 59, wherein the handler for a sparse data type uses a stream locator from a table-of-contents slot descriptor to determine a slot location for a fragment of a sparse data stream, and subsequent fragments follow the starting slot location, offset from the first fragment.

62. The method for scheduling retrieval of data as in claim 59, wherein the handler for a long data type uses a stream locator from a table-of-contents slot descriptor to determine sequence numbers for each fragment of a long data stream.

63. A method for scheduling retrieval of private data on a client device, comprising:

using a processor, retrieving a frame header from a current transmission frame;

using the processor, extracting a frame number from the frame header, wherein the frame number for a subsequent transmission frame is different from the frame number for the current transmission frame;

using the processor, identifying a subscriber ID for the client device;

using the processor, determining a private message slot assignment for the client device using the frame number and the subscriber ID;

wherein determining a private message slot assignment further comprises;

concatenating the subscriber ID, and the current frame number to form an array of bytes, creating a hash value from the array of bytes, determining slot assignments from the array of bytes, wherein the slot assignments correspond to slots in each partition of the transmission frame;

receiving a logical packet from the private message slot assignment in the transmission frame; and

authenticating the logical packet;

forwarding an authenticated logical packet to an application handler on the client device.

64. The method for scheduling retrieval of data of claim 63, wherein determining a private message slot assignment further comprises:

determining private message slot assignments from the subscriber ID and the current frame number.

65. The method for scheduling retrieval of data of claim 63, wherein authenticating the logical packet further comprises:

decrypting the logical packet;

checking the CRC of the decrypted logical packet;

applying error correction when an invalid CRC of the decrypted logical packet is identified;

decrypting the error-corrected logical packet;

checking the CRC of the decrypted error-corrected packet;

failing authentication when the decrypted logical packet and the decrypted error corrected logical packet have invalid CRCs; and

successfully authentication when either the logical packet or the error corrected logical packet have valid CRCs.