Frame protocol and scheduling system

• US 20040131014A1
• Filed: 01/03/2003
• Published: 07/08/2004
• Est. Priority Date: 01/03/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yuval, Gideon A., Thompson, R. Donald III, Massarenti, Davide, Cermak, Gerald F., Corbea, Cosmin A.
• Granted Patent: US 7,792,121 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• 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 computer-readable medium having a data structure stored thereon for use in communicating transmission frames from a server device to a client device, the data structure 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, 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 computer-readable medium 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 computer-readable medium of claim 1, wherein the frame header packet is located in the first slot of the transmission frame.

4. The computer-readable medium of claim 1, wherein each framer header further includes fields for a frame number, a time stamp, a time zone offset, and a region definition.

5. The computer-readable medium 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 computer-readable medium 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 computer-readable medium 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 computer-readable medium of claim 1, 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 codename 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.

9. The computer-readable medium 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.

10. The computer-readable medium of claim 9, wherein the encrypted packets are encrypted with an encryption key and an initialization vector, wherein the initialization vector is determined by the values from at least one of the frame number field and the time stamp field.

11. The computer-readable medium of claim 1, wherein each table of contents location definition field identifies a slot location, a format type, an error correction mode, and an error correction setting for a corresponding table of contents.

12. A computer-readable medium 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.

13. A computer-readable medium 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.

14. A computer-readable medium of claim 13, wherein the initial position corresponds to a packet number that is associated with the beginning of the particular range in the transmission frame.

15. A computer-readable medium of claim 13, 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 locater, an error correction setting, and a frame reservation.

16. A computer-readable medium of claim 13, 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.

17. The computer-readable medium of claim 16, 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.

18. The computer-readable medium of claim 17, wherein the data type corresponds to one of a compact data type, a sparse data type, and a long data type.

19. The computer-readable medium of claim 13, 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.

20. The computer-readable medium of claim 13, 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.

21. The computer-readable medium of claim 13, 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.

22. The computer-readable medium 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 at least a portion of a private message for the client in at least one of the pseudo randomly assigned slots.

23. The computer-readable medium of claim 22, wherein the pseudo-randomly assigned slots are determined from at least one of a subscriber ID that is associated with the client, a current frame number, and a hash function.

24. The computer-readable medium of claim 22, 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.

25. A computer-readable medium having a data structure stored thereon for use in communicating transmission frames from a server device to a client, the data structure 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 at least a portion of a private message for the client.

26. The computer-readable medium 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 computer-readable medium of claim 25, wherein the pseudo-randomly assigned slots are determined from at least one of 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 computer-readable medium 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 computer-readable medium 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 computer-readable medium 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 computer-readable medium 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 computer-readable medium 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:

selecting packets from a list of candidates for a subsequent transmission frame;

describing the selected packets in a table of contents for the next transmission frame;

assigning the table of contents for the next transmission frame to a 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. A method for scheduling frame transmissions from a server to a client device, comprising:

receiving a request for a transmission slot, wherein the request includes a number of packets;

allocating a slot for the next transmission frame based on the requested transmission slot;

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

assigning the table of contents for the next transmission frame to a 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.

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

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

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;

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

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

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.

36. The method of claim 35, further comprising:

overriding an allocated slot assignment for a private message packet.

37. The method of claim 35, 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.

38. The method of claim 37, 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.

39. The method of claim 37, 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.

40. The method of claim 37, encrypting packets associated with the private message, wherein an encryption process uses at least one of a frame number and 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.

41. The method of claim 35, further comprising:

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.

42. The method of claim 35, 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.

43. The method of claim 35, 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.

44. The method of claim 35, 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.

45. The method of claim 35, 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.

46. The method of claim 45, 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.

47. The method of claim 45, further comprising:

updating locator fields that are associated with an assigned slot.

48. The method of claim 45, 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.

49. The method of claim 45, 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.

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

extracting a table of contents from a current transmission frame;

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

retrieving packets that are identified with slots in a subsequent transmission frame;

assembling a message from the retrieved packets; and

forwarding a completed message to an application on the client device when the message is assembled.

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

extracting a table of contents from a current transmission frame;

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

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.

52. The method for scheduling retrieval of data as in claim 51, 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.

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

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

54. The method for scheduling retrieval of data as in claim 51, wherein extracting a table of contents includes:

retrieving a frame header for the current transmission frame;

identifying a table of contents location definition from the frame header; and

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.

55. The method for scheduling retrieval of data as in claim 51, 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.

56. The method for scheduling retrieval of data as in claim 51, 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 at least one of estimated from an earlier transmission frame, and extracted from a frame header.

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

at least one of 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.

58. The method for scheduling retrieval of data as in claim 51, 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.

59. The method for scheduling retrieval of data of claim 51, 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 the at least one of the logical packet and the error corrected logical packet have valid CRCs.

60. The method for scheduling retrieval of data as in claim 51, 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.

61. The method for scheduling retrieval of data as in claim 51, 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.

62. The method for scheduling retrieval of data as in claim 51, 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.

63. The method for scheduling retrieval of data as in claim 51, 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.

64. The method for scheduling retrieval of data as in claim 63, 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.

65. The method for scheduling retrieval of data as in claim 63, 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.

66. The method for scheduling retrieval of data as in claim 63, 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.

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

retrieving a frame header from a current transmission frame;

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;

identifying a subscriber ID for the client device;

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

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.

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

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

69. The method for scheduling retrieval of data of claim 67, 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.

70. The method for scheduling retrieval of data of claim 67, 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 the at least one of the logical packet and the error corrected logical packet have valid CRCs.