PATENT DOCUMENT

Publication Number: US-7484013-B1
Application Number: US-31713305-A
Country: US
Kind Code: B1

Title: Automatic ID allocation for AV/C entities

Abstract:
Disclosed herein is an automatic ID allocation technique for use in AV/C device applications. The method allows ID assignment without manual user intervention. The method includes assigning an ID to an entity when called to do so upon detection of a new entity. Furthermore, old IDs are reallocated for later use upon disconnection of the associated entity.

Claims:
1. In a digital data system, a method of allocating an unallocated identifier to a target entity, the method comprising:
 determining a set of identifiers allocated to entities of a common type; 
 selecting a current identifier, wherein the current identifier is selected from a set of possible identifiers; 
 executing a main process comprising:
 determining whether the current identifier is a member of the set of allocated identifiers; 
 if the current identifier is a member of the set of allocated identifiers, selecting a new current identifier from the set of possible identifiers and repeating the main process; and 
 if the current identifier is not a member of the set of allocated identifiers, allocating the current identifier to the target entity. 
 
 
     
     
       2. The method of  claim 1 , wherein the set of possible identifiers comprises a set of integers. 
     
     
       3. The method of  claim 1 , wherein the set of possible identifiers comprises a set of non-negative integers. 
     
     
       4. The method of  claim 3 , wherein said selecting a new current identifier comprises incrementing the current identifier. 
     
     
       5. The method of  claim 1 , wherein the target entity comprises an audio/video control unit. 
     
     
       6. The method of  claim 1 , wherein the target entity comprises an audio/video control subunit. 
     
     
       7. The method of  claim 1 , wherein the target entity comprises an audio/video control plug. 
     
     
       8. The method of  claim 7 , wherein the audio/video control plug comprises an internal virtual plug implemented by an audio/video control subunit. 
     
     
       9. The method of  claim 7 , wherein the set of allocated identifiers comprises a list of identifiers, the list comprising a linked list of objects. 
     
     
       10. The method of  claim 1 , further comprising:
 receiving a deallocation request from a second entity; 
 determining an allocated identifier corresponding to the deallocation request; and 
 removing the allocated identifier from the plurality of identifiers. 
 
     
     
       11. The method of  claim 10 , wherein the target entity and the second entity comprise the same entity. 
     
     
       12. The method of  claim 10 , wherein the deallocation request comprises the allocated identifier. 
     
     
       13. The method of  claim 10 , wherein the deallocation request comprises a reference to the allocated identifier. 
     
     
       14. The method of  claim 10 , wherein the second entity comprises an audio/video control unit. 
     
     
       15. The method of  claim 10 , wherein the second entity comprises an audio/video control plug. 
     
     
       16. An apparatus adapted to allocate an unallocated identifier to a target entity, the apparatus comprising:
 a first module adapted to generate a list of identifiers allocated to entities, wherein each entity is compliant with a version of the AV/C Digital Interface Command Set General Specification; 
 a second module adapted to select a current identifier, wherein the current identifier is selected from a set of possible identifiers; 
 a third module adapted to determine whether the current identifier appears in the list of identifiers; 
 a fourth module adapted to select a new current identifier from the set of possible identifiers if the third module determines that the current identifier appears in the list of identifiers; and 
 a fifth module adapted to allocate the current identifier to the target entity if the third module determines that the current identifier does not appear in the list of identifiers. 
 
     
     
       17. The apparatus of  claim 16 , wherein the set of possible identifiers comprises a set of non-negative integers. 
     
     
       18. The apparatus of  claim 17 , wherein the fourth module is further adapted to select a new current identifier by incrementing the current identifier. 
     
     
       19. The apparatus of  claim 16 , wherein the target entity comprises an audio/video control unit. 
     
     
       20. The apparatus of  claim 16 , wherein the target entity comprises an audio/video control subunit. 
     
     
       21. The apparatus of  claim 16 , wherein the target entity comprises an audio/video control plug. 
     
     
       22. The apparatus of  claim 16 , wherein the first, second, third, fourth, and fifth modules each comprise at least one computer program instruction. 
     
     
       23. The apparatus of  claim 16 , further comprising:
 a sixth module adapted to receive a deallocation request from a requesting entity; 
 a seventh module adapted to determine an allocated identifier corresponding to the deallocation request; and 
 an eighth module adapted to remove the allocated identifier from the list of identifiers. 
 
     
     
       24. The apparatus of  claim 23 , wherein the requesting entity and the target entity comprise the same entity. 
     
     
       25. The apparatus of  claim 23 , wherein the deallocation request comprises the allocated identifier. 
     
     
       26. The apparatus of  claim 23 , wherein the deallocation request comprises a reference to the allocated identifier. 
     
     
       27. The apparatus of  claim 23 , wherein the requesting entity comprises an audio/video control unit. 
     
     
       28. The apparatus of  claim 23 , wherein the requesting entity comprises an audio/video control subunit. 
     
     
       29. The apparatus of  claim 23 , wherein the requesting entity comprises an audio/video control plug. 
     
     
       30. An apparatus adapted to allocate an unallocated identifier to a target entity, the apparatus comprising:
 a first module adapted to generate a list of identifiers allocated to entities of a common type; 
 a second module adapted to select a current identifier, wherein the current identifier is selected from a set of possible identifiers; 
 a third module adapted to determine whether the current identifier appears in the list of identifiers; 
 a fourth module adapted to select a new current identifier from the set of possible identifiers if the third module determines that the current identifier appears in the list of identifiers; and 
 a fifth module adapted to allocate the current identifier to the target entity if the third module determines that the current identifier does not appear in the list of identifiers. 
 
     
     
       31. The apparatus of  claim 30 , wherein the set of possible identifiers comprises a set of non-negative integers. 
     
     
       32. The apparatus of  claim 30 , wherein the fourth module is adapted to select a new current identifier by incrementing the current identifier. 
     
     
       33. The apparatus of  claim 30 , wherein the target entity comprises an audio/video control unit. 
     
     
       34. The apparatus of  claim 30 , wherein the target entity comprises an audio/video control subunit. 
     
     
       35. The apparatus of  claim 30 , wherein the target entity comprises an audio/video control plug. 
     
     
       36. The apparatus of  claim 30  further comprising a sixth module adapted to deallocate an allocated identifier. 
     
     
       37. The apparatus of  claim 36 , wherein the first, second, third, fourth, fifth, and sixth modules each comprise at least one computer program instruction. 
     
     
       38. In a digital data system, a method of allocating an unallocated identifier to a target entity, said target entity being one of a plurality of entities of a common type, the method comprising:
 selecting a current identifier, wherein the current identifier is selected from a set of possible identifiers for said common type of entity; 
 determining whether the current identifier is a member of a set of allocated identifiers; 
 if the current identifier is a member of the set of allocated identifiers, selecting a new current identifier from the set of possible identifiers and repeating said act of determining; and 
 if the current identifier is not a member of the set of allocated identifiers, allocating the current identifier to the target entity. 
 
     
     
       39. The method of  claim 38 , wherein the set of possible identifiers comprises a set of integers. 
     
     
       40. The method of  claim 38 , wherein said selecting a new current identifier comprises incrementing the current identifier. 
     
     
       41. The method of  claim 38 , wherein the set of allocated identifiers comprises a list of identifiers, the list comprising a linked list of objects. 
     
     
       42. The method of  claim 38 , further comprising:
 receiving a deallocation request from a second entity; 
 determining an allocated identifier corresponding to the deallocation request; and 
 removing the allocated identifier from the plurality of identifiers. 
 
     
     
       43. An apparatus adapted to allocate an unallocated identifier to a target entity, the apparatus comprising:
 a first module adapted to select a current identifier, wherein the current identifier is selected from a set of possible identifiers; 
 a second module adapted to determine whether the current identifier appears in a list of currently assigned identifiers; 
 a third module adapted to select a new current identifier from the set of possible identifiers if the second module determines that the current identifier appears in the list of currently assigned identifiers; and 
 a fourth module adapted to allocate the current identifier to the target entity if the second module determines that the current identifier does not appear in the list of currently assigned identifiers. 
 
     
     
       44. In a digital data system, apparatus for allocating an unallocated identifier to a target entity, the apparatus comprising:
 means for determining a set of identifiers allocated to entities of a common type; 
 means for selecting a current identifier, wherein the current identifier is selected from a set of possible identifiers; 
 means for executing a main process comprising:
 means for determining whether the current identifier is a member of the set of allocated identifiers; 
 means for selecting a new current identifier from the set of possible identifiers if the current identifier is a member of the set of allocated identifiers along with means for repeating the main process; and 
 means for allocating the current identifier to the target entity if the current identifier is not a member of the set of allocated identifiers.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application is a continuation of U.S. patent application Ser. No. 10/607,736, filed Jun. 26, 2003, now U.S. Pat. No. 7,003,590, which is a continuation of U.S. patent application Ser. No. 09/432,872, filed Nov. 2, 1999, now issued as U.S. Pat. No. 6,631,426. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to ID allocation techniques. More particularly, this invention relates to methods for allocating identification nomenclature to AV/C entities. 
     2. The Prior Art 
     The IEEE 1394 multimedia bus standard is to be the “convergence bus” bringing together the worlds of the PC and digital consumer electronics. It is readily becoming the digital interface of choice for consumer digital audio/video applications, providing a simple, low-cost and seamless plug-and-play interconnect for clusters of digital A/V devices, and it is being adopted for PCs and peripherals. 
     The original specification for 1394, called IEEE 1394-1995, supported data transmission speeds of 100 to 400 Mbits/second. Most consumer electronic devices available on the market have supported either 100 or 100/200 Mbits/second; meaning that plenty of headroom remains in the 1394 specification. However, as more devices are added to a system, and improvements in the quality of the A/V data (i.e., more pixels and more bits per pixel) emerge, a need for greater bandwidth and connectivity flexibility has been indicated. 
     The 1394a specification (pending approval) offers efficiency improvements, including support for very low power, arbitration acceleration, fast reset and suspend/resume features. However, current methods for allocating ID&#39;s to new devices are both manual and crude especially when considered in the context of “hot swappable” devices. 
     As indicated in the AV/C Digital Interface Command Set General Specification (hereinafter, the General Specification): an AV unit is the physical instantiation of a consumer electronic device, e.g., a camcorder or a VCR, within a Serial Bus node; an AV subunit is an instantiation of a virtual entity that can be identified uniquely within an AV unit and offers a set of coherent functions; an AV/C is an Audio/video control; and a plug is a physical or virtual end-point of connection implemented by an AV unit or subunit that may receive or transmit isochronous or other data—plugs may be Serial Bus plugs, accessible through the PCR&#39;s (PCR: is a Plug Control Register, as defined by IEC 61883, Digital Interface for Consumer Electronic Audio/Video Equipment; further, an iPCR: is an input plug PCR, as defined by IEC 61883 and an oPCR: is an output plug PCR, as defined by IEC 61883) they may be external, physical plugs on the AV unit; or they may be internal virtual plugs implemented by the AV subunits. 
     An AV/C target implementation is made up of multiple entities including AV/C subunits and plugs. Each separate entity has an associated ID number used to specify that entity when an AV/C controller sends a command acting upon that entity. 
     The implementation of the AV/C target device must ensure that the IDs used for the target entities are unique among all entities of the same type. In addition they must be between 0 and n−1 where n is the number of a particular type of entity. Thus an AV/C subunit and plug may both have an ID of 0, but two AV/C subunits may not both have an ID of 0. 
     The old methods for implementing AV/C target entities are to statically allocate the IDs for each entity. Thus, when implementing the software for the entities, the number of entities must be known in advance. Updating the implementation to support a new entity requires manual allocation of another ID. In addition, removal of an entity requires manual deallocation of its ID, and if its ID (m) is less than n−1 (e.g., 0≦m&lt;n−1), thus, residing somerwhere in the middle of the identification listings, the IDs for the entities between m+1 and n−1 must be manually decremented. 
     Modularity of software components, and independence of implementation between software components, are elements of good software design. However, the manual allocation of IDs described above prevents total independence between the implementations of the AV/C entities. In addition, the manual allocation prevents an implementation of dynamic AV/C entities as would be needed when components are hot swapped into an AV/C device. 
     BRIEF DESCRIPTION OF THE INVENTION 
     This invention provides a means of automatically and dynamically allocating IDs for AV/C entities. The IDs do not need to be determined during the implementation of the entities. The IDs are determined at run time. This has the benefit of allowing an implementation of dynamic AV/C entities. 
     This invention provides an AV/C entity allocation service which maintains a list of the currently allocated IDs. This list is initially empty. When an AV/C entity is initialized, it calls the allocation service to allocate an ID which it then uses for the initialized entity. The allocation service allocates an ID by starting with an ID of 0. The service then searches its allocated ID list to see if the current ID has already been allocated. If it finds the ID in the list, it increments its current ID and searches the list again. If it does not find the ID, it adds the current ID to the allocated list and returns the ID to the entity. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING FIGURES 
         FIG. 1  is schematic overview of the present invention. 
         FIG. 2  is a schematic drawing of entity/service interaction of the present invention. 
         FIG. 3  is a flow diagram of the method form allocating IDs of the present invention. 
         FIG. 4  is an exemplary embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT 
     Persons of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. 
     Generally speaking, units, plugs, and subunits are known as entities. According to the General Specification, each entity must have a unique ID associated with it within its class. Referring now to  FIG. 1 , an schematic diagram of an exemplary system  10  is depicted. An AV/C unit  12 , such as DV camcorder, is shown including a camera subunit  14  and two tape subunits  16  and  18  therein, as well as four external physical plugs  26 . Furthermore, the camera subunit includes four virtual plugs  20 , tape subunit  16  includes four virtual plugs  22  and tape subunit  18  includes four virtual plugs  24 . In viewing the depicted example, 20 entities are indicated. That is, the AV/C unit is an entity (which would be significant if attached to other units), each subunit is an entity, and each plug, both physical and virtual is an entity. Therefore, there are 20 entities depicted within 7 classes (1 unit class, 2 subunit classes, and 4 plug classes). 
     Since each entity must have a unique ID associated with it, the AV/C unit would have an ID 0  (not shown since no other unit are depicted in  FIG. 1 ), camera subunit  14  has ID 0  associated with it, tape subunit  16  has an ID 0  associated with it, but the second tape subunit  18  is ID 1 . Each set of plugs within each unit or subunit, likewise includes a unique ID as shown. 
     To allocate these IDs in an ordered fashion, ID allocator service  28  lies within a memory space, such as an EEPROM. Referring now to  FIG. 2 , as can be seen schematically, each entity  30 - 36  is in operative communication with the ID allocator service  28 . The ID allocator service  28  serves the function of dynamically allocating IDs to each sensed entity. That is, once an entity is detected, usually on startup, a call is made to the ID allocator service  28  to assign an ID to the new entity. Likewise, when an entity is removed and another like entity is added, a call is made to the ID allocator service  28  to assign the first available unused ID, which may be that of a previous entity. 
     To accomplish this task, and referring now to  FIG. 3 , an ID allocation system  110  is depicted. The system  110  includes as a first activity  112  starting with a current ID equal to zero. If the ID 0  is already allocated to an entity, then the system will look to the next ID as in activities  114  and  116 . This process will recur until the next available, unused, ID is located. When the next unused ID is located, the newly found entity is assigned that ID by mapping that entity to that ID in an allocation list as in activities  118  and  120 . For example, and referring again to  FIG. 1 , when the tape subunit  18  was added, the device was detected and a call was made to the ID allocator service  28 . The ID allocator service first checked to see if ID 0  was available in the tape subunit class. The service discovered that ID 0  was being used already, so it next checked ID 1 . As ID 1  was available, ID 1  was assigned to tape subunit  18 . No user intervention was required to assign the ID other than adding the entity and turning the system on. 
     In use and operation, another exemplary schematic  210  is depicted in  FIG. 4 . In this example a settop box ( 212 ) will act as a bridge between two video cameras on one side of the bridge and two televisions on the other. Included with the settop box are two USB ports  218  and  220  and two 1394 ports  236  and  246 . The televisions  238  and  248  are connected to the 1394 ports  236  and  246  respectively via an appropriate 1394 cable. In this example, the televisions are acting as hosts or servers for potential transmissions of video and audio through the STB  212 . 
     It will be understood that included within the STB  212  will be a USB AV/C subunit software module for detecting USB devices on the USB buses. Once a device is connected to one of the USB ports, the USB software will detect the entity and make a call to the ID allocator service as described above. 
     In this example, then, the camera  214  is first connected via an appropriate USB cable to port  218 . The system is turned on, and the new entity is detected by the USB software which builds an AV/C camera subunit  222  and a virtual plug  228  to put in operative communication with port  218 . Plug  228  is an input plug, whereas plugs  232  and  240  are output plugs, and hence AV/C considers them to be of different classes, and as such separate class IDs are associated therewith. The USB software, thus, makes a call to the ID allocator service  226  which initiates its recursive search for an ID as discussed with respect to  FIG. 3 . ID 0  is then assigned to AV/C camera subunit  222  and then an ID 0  is assigned to virtual plug  228 . Then, as the bridge serves but one purpose in this example, the subunit  222  must be put in operative communication with ports  236  and  246  via virtual plug  232  and  240  respectively. The ID allocator thus, assigns the next available ID, which in this case is ID 0 , to the virtual plug  240  and the next ID to virtual plug  232  or ID 1  thereby conforming this portion of the system with the General Specification&#39;s requirement of unique ID&#39;s for each entity. 
     Thereafter, a second camera  216  is added to the STB  212  at port  220 . Another call is made to the ID allocator service  226 . The ID allocator service then assigns the next available ID, which is ID 1  in this case, to the new subunit  224 . Again, three virtual plugs are needed to bridge the camera with the televisions  238  and  248  at ports  236  and  246  respectively. Thus, a first virtual input plug  230  is assigned ID 0 . Then a first virtual output plug  242  is assigned ID 0 , while a second virtual output plug  234  is assigned ID 1 . Without the allocator  226 , the second subunit could not be built without manually assigning a new ID. As one can appreciate, such is quite a cumbersome and user unfriendly task. Furthermore, if, thereafter, camera  214  were unplugged from plug  218 , the IDs associated therewith would be removed from the ID allocator list and be available for future use automatically in the present system. 
     While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.

Metadata:
Filing Date: 20051222
Publication Date: 20090127
Grant Date: 20090127
Priority Date: 19991102
Inventors: STAATS ERIK P.
Assignee: APPLE INC
CPC Classifications: [{"code": "H04N21/43632", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N21/43632", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N21/43615", "inventive": true, "first": true, "tree": "[]"}, {"code": "H04N21/43615", "inventive": true, "first": true, "tree": "[]"}, {"code": "H04N21/4108", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N21/4223", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N21/4108", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N21/4223", "inventive": true, "first": false, "tree": "[]"}]
Family ID: 28675642