Collaborative state machine framework for use in a communication network

An apparatus for use in a communication network comprises a state machine capable of transitioning between a plurality of states. The plurality of states comprises at least two concurrent states. The state machine operates in the at least two concurrent states concurrently. Each of the concurrent states may be associated with a task. At least a portion of the task associated with one of the concurrent states may be performed concurrently with at least a portion of the task associated with another of the concurrent states when the state machine operates in the concurrent states.

TECHNICAL FIELD

This disclosure relates generally to communication networks and more specifically to a collaborative state machine framework for use in a communication network.

BACKGROUND OF THE INVENTION

Communication networks often use finite state machines (FSM) to control the establishment of communication sessions and other network operations. For example, a code division multiple access (CDMA) wireless network often uses a finite state machine to control the setup of telephone calls in the network. The state machine typically includes a null or initial state, a network setup state, a link setup state, and a traffic state. The null state typically represents a state where no action is occurring to satisfy a request for service. The network setup state and the link setup state typically represent tasks needed to establish a connection and provide service in the network. The traffic state typically represents a state where voice traffic is carried over the network.

A problem with conventional communication networks is that the finite state machines often operate sequentially. In other words, a state machine cannot progress (or transition) from one state to the next state until all actions associated with the previous state have been completed. This often increases the time needed to satisfy a request for service. This delay may be particularly problematic when the requested service has stringent time requirements.

Therefore, there is a need in the art for improved telecommunications equipment that implements state machines that are capable of operating in a non-sequential manner. In particular, there is a need in the art for telecommunication devices that use state machines that can transition from a first state to a second state without waiting for all actions associated with a previous state to complete.

SUMMARY OF THE INVENTION

The present invention provides a collaborative state machine framework for use in telecommunication devices that enables state machines to transition from a first state to a second state without waiting for all actions associated with a previous state to complete.

According to an exemplary embodiment of the present invention, an apparatus for use in a communication network includes a state machine that transitions between a plurality of states. The plurality of states includes at least two concurrent states, and the state machine is capable of operating concurrently in the at least two concurrent states.

According to the exemplary embodiment of the present invention, each of the concurrent states is associated with a task. At least a portion of the task associated with one of the concurrent states is performed concurrently with at least a portion of the task associated with another of the concurrent states when the state machine operates in the concurrent states.

According to another embodiment of the present invention, a communication network includes a plurality of components and at least one state machine. Each of the components is capable of communicating with at least one other of the components and at least one of the components is capable of communicating with one or more communication devices. The at least one state machine transitions between a plurality of states. At least one of the states is associated with at least one task that provides a service to at least one of the communication devices. The plurality of states includes at least two concurrent states and the at least one state machine operates concurrently in the at least two concurrent states.

According to yet another embodiment of the present invention, a method for use in a communication network comprises the step of transitioning from an initial state to a plurality of additional states in response to a request for service. At least two of the additional states include at least two concurrent states. The step of transitioning to the additional states includes the step of operating in the at least two concurrent states concurrently. The method also includes the step of transitioning to a final state associated with providing the requested service.

One or more technical features may be present according to various embodiments of this disclosure. Particular embodiments of this disclosure may exhibit none, some, or all of the following features depending on the implementation. For example, in some embodiments, an improved collaborative state machine framework for use in a communication network is provided. In particular embodiments, a state machine is capable of launching or transitioning to two or more states concurrently. Tasks associated with the concurrent states may then be performed concurrently. This may allow, for example, multiple network resources to concurrently perform actions needed to satisfy a request for service. Because these actions are performed concurrently or at least partially overlap, the time required to satisfy the request for service may be reduced.

DETAILED DESCRIPTION

FIGS. 1 through 5, discussed below, and the various embodiments used to describe the principles of this disclosure are by way of illustration only and should not be construed in any way to limit the scope of the invention. Those skilled in the art will understand that the principles of this disclosure may be implemented in any suitable communication network or device.

FIG. 1illustrates exemplary communication network100, which uses a collaborative state machine framework according to the principles of the present invention. In the exemplary embodiment, communication network100represents a wireless network. Communication network100shown inFIG. 1is for illustration only. Other communication networks, including wireline networks, may be used without departing from the scope of the present invention.

Communication network100comprises a plurality of cell sites102-104. Each of cell sites102-104comprises one of a plurality of base stations (BS)106-108. Each one of base stations106-108communicates with one or more wireless communication devices (WCD)110-113. In one embodiment of the present invention, base stations106-108may communicate with wireless communication devices110-113over code division multiple access (CDMA) channels according to the IS-2000-C standard (i.e., Release C of CDMA2000).

Each of wireless communication devices110-113may represent a mobile wireless device, such as a cell phone, a Personal Communications System (PCS) handset, a personal digital assistant (PDA) handset, a portable computer, a telemetry device, or the like. Each of wireless communication devices110-113may represent any other suitable device operable to communicate with one or more base stations106-108via wireless links, including stationary and mobile wireless devices.

The dotted lines inFIG. 1show the approximate boundaries of cell sites102-104in which base stations106-108are located. Cell sites102-104are shown as being approximately circular for the purposes of illustration and explanation only. It will be understood that cell sites102-104may have many other shapes (including irregular shapes), depending on the cell configuration and natural and man-made obstructions. In some embodiments, each of cell sites102-104includes a plurality of sectors, and directional antennas coupled to base stations106-108may provide service for each sector. The embodiment shown inFIG. 1illustrates base stations106-108in the centers of cell sites102-104. In other embodiments, the directional antennas may be positioned in corners of the sectors or in any other suitable location or locations. Communication network100is not limited to any particular cell site configuration.

According to an exemplary embodiment of the present invention, each of base stations106-108may comprise a base station controller and at least one base transceiver subsystem. The base station controllers are operable to manage wireless communication resources, including the base transceiver subsystems, for specified cells102-104within communication network100. For example, the base transceiver subsystems may include radio frequency (RF) transceivers, antennas, and other electrical equipment located in each of cell sites102-104. This equipment may include air conditioning units, heating units, electrical supplies, telephone line interfaces, and RF transmitters and RF receivers. For the purposes of simplicity and clarity in explaining the operation of communication network100, the base transceiver subsystem in each of cells102-104and the base station controller associated with each base transceiver subsystem are collectively represented by base stations106-108, respectively.

Base stations106-108are capable of transferring voice and data signals between each other and to and from a public switched telephone network (PSTN) or other network via communication line120and mobile switching center (MSC)130. Base stations106-108also may transfer data signals, such as packet data, back and forth from the Internet or other network via communication line120and packet data server node (PDSN)140. Packet control function (PCF) unit150is capable of controlling the flow of data packets between base stations106-108and PDSN140. PCF unit150may be implemented as part of PDSN140, as part of base stations106-108, as a stand-alone device that communicates with PDSN140, or in any other suitable manner. Communication line120provides connections for voice and data circuits between MSC130and base stations106-108.

Communication line120may represent any suitable connection, including a T1 line, a T3 line, a fiber optic link, or any other type of data connection. The connections on communication line120may transmit analog voice signals or digital voice signals in pulse code modulated (PCM) format, Internet Protocol (IP) format, asynchronous transfer mode (ATM) format, or any other suitable format. In some embodiments, communication line120also provides an Internet Protocol (IP) connection or other connection that transfers data packets between base stations106-108of communication network100. For example, communication line120may include a local area network (LAN) that provides direct IP connections between base stations106-108without using PDSN140.

In an exemplary embodiment of the present invention, MSC130may comprise a switching device that provides services and coordination between the subscribers in communication network100and external networks, such as the PSTN or the Internet. In an exemplary embodiment, communication line120may include several different data links, where each data link couples one of base stations106-108to MSC130.

In the embodiment shown inFIG. 1, wireless communication device110and wireless communication device111are located in cell site102and are capable of communicating with base station106. Wireless communication device112is located in cell site103and is capable of communicating with base station107, and wireless communication device113is located in cell site104and is capable of communicating with base station108.

According to an advantageous embodiment of the present invention, one or more of base stations106-108and MSC130may comprise, or otherwise have access to, one or more state machines160-163. As described in more detail below, at least one of state machines160-163implements a collaborative state machine framework capable of launching or transitioning to two or more states concurrently in according with the principles of the present invention. Each of the states may be associated with different tasks needed to provide a service in communication network100. By allowing one or more of state machines160-163to operate in two or more states simultaneously, multiple network resources (e.g., base station108, MSC130) may concurrently perform the tasks needed to satisfy the request for service. Advantageously, performing these tasks concurrently reduces the time required to satisfy the request for service.

Each of state machines160-163may represent any hardware, software, firmware, or combination thereof supporting the execution of multiple tasks in two or more concurrent states. For example, each of state machines160-163may comprise one or more software routines executed by one or more processors. For the purposes of this disclosure, the terms “concurrent” and “simultaneous” and their derivatives refer to a total overlap of two or more elements as well as a partial overlap of two or more elements.

Because one or more of state machines160-163implements a collaborative state machine framework, state machines160-163provide faster response times than conventional finite state machines. For example, conventional finite state machines often operate sequentially and cannot transition from one state to the next state until the completion of all actions associated with the prior state. A collaborative state machine framework according to the principles of the present invention allows tasks for multiple states to be performed at the same time, reducing the time needed to complete the tasks. This may be useful, for example, in applications requiring high throughput and fast response times. These applications may include Voice over Internet Protocol (VoIP), “Push-to-Talk” or rapid connection establishment, instant messaging, location-based services, multimedia streaming, and other applications.

The exemplary embodiment of communication network100inFIG. 1should not be construed to limit the scope of the present invention. Those skilled in the art will readily understand that various changes may be made to communication network100without departing from the principles of the present invention. For example, communication network100may include any number of cell cites, base stations, and wireless communication devices. Additional state machines may be used in other devise in communication network100. These may include state machines used by wireless communication devices110-113, state machines used by MSC130, state machine used by PDSN140, and state machines used by PCF150. In sum, many types of communication devices may use a collaborative state machine framework according to the principles of the present invention, including switches and routers, among others.

FIG. 2illustrates exemplary base station106in greater detail according to one embodiment of the present invention. Base station106is shown of the purposes of illustration only. It will be understood that the components illustrated and described with respect to base station106are also implemented in exemplary base stations107and108.

In the exemplary embodiment of the present invention, base station106comprises base station controller210and at least one base transceiver subsystem220. Although illustrated with one base transceiver subsystem220, it will be understood that base station106may include any suitable number of base transceiver subsystems without departing from the scope of the present invention.

Base station controller210manages the resources in cell site102, including base transceiver subsystem220. As described in more detail below, base station controller210may include or otherwise have access to state machine161. In the illustrated embodiment, base transceiver subsystem220comprises base transceiver subsystem (BTS) controller225, channel controller235(which comprises at least one channel element240), transceiver interface (IF)245, radio-frequency (RF) transceiver unit250, and antenna array255. BTS controller225may comprise processing circuitry and memory capable of executing an operating program that controls the overall operation of base transceiver subsystem220and communicates with base station controller210.

Under normal conditions, BTS controller225directs the operation of channel controller235, which may include a number of channel elements such as channel element240. Each channel element is capable of performing bidirectional communications in a forward channel and a reverse channel. A “forward channel” refers to outbound signals from base station106to a wireless communication device, and a “reverse channel” refers to inbound signals from a wireless communication device to base station106.

Transceiver IF245transfer the bidirectional channel signals between channel controller235and RF transceiver unit250. Antenna array255transmits forward channel signals received from RF transceiver unit250to wireless communication devices110-111in the coverage area of base station106. Antenna array255also sends to RF transceiver unit250reverse channel signals received from wireless communication devices110-111in the coverage area of base station106. In an exemplary embodiment, antenna array255comprises a multi-sector antenna, such as a three-sector antenna, in which each antenna sector is responsible for transmitting and receiving in a coverage area corresponding to an arc of approximately 120°. Additionally, RF transceiver unit250may include an antenna selection unit to select among different antennas in antenna array255during both transmit and receive operations.

As described in more detail below, state machine161implements a collaborative state machine framework. The collaborative state machine framework is capable of launching or transitioning to two or more states concurrently. In other words, the collaborative state machine framework allows state machine161to operate in multiple states concurrently. This allows multiple tasks associated with the states to be performed or executed concurrently. For example, state machine161in base station controller210may transition to and operate in two states. One state may involve MSC130assigning a circuit identity code (CIC) to a requested telephone call, and another state may involve base station controller210assigning resources to the requested call. Because tasks for these concurrent states may be executed at the same time or at least partially overlap, the overall time needed to complete the tasks is reduced. As a result, the request for service may be completed more quickly.

Although illustrated in base station controller210, it will be understood that state machine161may be implemented elsewhere. For example, state machine161may be implemented within base transceiver subsystem220or elsewhere within base station106without departing from the principles of the present invention.

In an exemplary embodiment, state machine161may comprise logic encoded in media. The logic includes functional instructions for carrying out program tasks, among other things. The media may comprise computer disks or other computer-readable media, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), digital signal processors (DSPs), other suitable specific or general purpose processors, transmission media, or other suitable media in which logic may be encoded and utilized.

FIG. 3illustrates collaborative state machine framework300in communication network100according to an exemplary embodiment of the present invention. Collaborative state machine framework300may be implemented by one or more of state machines160-163in communication network100. The exemplary embodiment of collaborative state machine framework300illustrated inFIG. 3is by way of example only and should not be construed to limit the scope of the present invention. Other collaborative state machine frameworks may be used without departing from the scope of the present invention. Collaborative state machine framework300may be used in any other communication network.

In an exemplary embodiment of the present invention, a state machine may represent a set of program code or other logic that contains a set of input events, a set of output events, and a set of states. The state machine may also comprise a function that maps input events and states to output events, a function that maps input events and states to other states (referred to as state transitions), and a description of the initial state. In addition, the transitions between states (represented as paths between the states inFIG. 3) typically involve the transfer of one or more messages or other data.

In the illustrated example, collaborative state machine framework300comprises null state302. Null state302represents the initial state of state machines160-163. In particular, null state302represents a state where no action is occurring to establish a voice connection or provide another service in communication network100.

When a request for service is received, state machines160-163transition from null state302to correlation state304. Correlation state304knows which tasks may be performed concurrently and correlation state304is capable of launching two or more concurrent states306-308. When this occurs, state machines160-163transition to the two or more concurrent states306-308.

Concurrent states306-308represent any suitable states, and each of concurrent states306-308may involve any suitable task or tasks. When each of concurrent states306-308is completed, correlation state304receives the results of those tasks. Correlation state304gathers and correlates the data generated during concurrent states306-308. Correlation state304then transitions to final state310.

Final state310represents the final or completed state of collaborative state machine framework300. In final state310, the requested service may be provided to one or more of wireless communication devices110-113. State machines160-163support various attributes that implement collaborative state machine framework300. These attributes may include concurrency, hierarchy, and collaboration.

Concurrency refers to the ability of one or more components in communication network100to execute multiple tasks associated with collaborative state machine framework300, where the execution at least partially overlaps. Concurrency in collaborative state machine framework300involves identifying various ones of states302-310that may be grouped together and decoupled from other states302-310. The decoupled states may then be implemented as separate tasks that are performed concurrently. As an example, states302,304,310may be grouped into one group and represent a single task. State306could be grouped by itself and represent another task. State308could be grouped by itself and represent a third task. In this example, at least portions of these tasks may be performed at the same time. This helps to increase the speed at which all of the tasks are completed, which reduces the time needed to satisfy a request for service (the time needed to reach and complete final state310).

Hierarchy in collaborative state machine framework300refers to the classification of entities into successive levels (or tiers), where each level is subordinate to the level above. Hierarchy may be used to identify superior and subordinate relationships and to organize repetitive patterns in a standard, consistent approach. As described above, in collaborative state machine framework300, multiple tasks may be executed or performed concurrently. One task may need to be informed of errors occurring in other tasks. Because of this, collaborative state machine framework300supports a hierarchy within each state or task. One example of the hierarchy is shown inFIG. 4, which is described below.

Collaboration in collaborative state machine framework300refers to communicating information, such as important events or errors, across various states302-310. As an example, multiple tasks executed concurrently often need to share information on state transitions, data updates, exceptions, and events. Various mechanisms may be used to support collaboration in collaborative state machine framework300, such as semaphores, shared memory, global data, and interrupts.

Correlation state304in collaborative state machine framework300represents a facilitator of collaboration within framework300. Correlation state304contains knowledge of the concurrent tasks associated with concurrent states306-308and logic used to determine when a transition may be made to the next state (final state310). Correlation state304also correlates the responses and data results from those concurrent states306-308. Correlation of responses may be necessary, for example, when the transition to final state310depends on a particular combination of results from concurrent states306-308. As a particular example, correlation of data may be necessary when some parameters are required in order for a transition to occur and dependencies are separated across concurrent tasks.

The embodiment of collaborative state machine framework300illustrated and described inFIG. 3is by way of example only, and should not be construed so as to limit the scope of the present invention. Those skilled in the art will readily understand that various changes may be made to the embodiment inFIG. 3. For example, whileFIG. 3illustrates two concurrent states306and308, collaborative state machine framework300may support any suitable number of concurrent states. Collaborative state machine framework300also may comprise multiple correlation states304, each of which is capable of launching two or more concurrent states. Furthermore, each of states302-310inFIG. 3may represent any combination of messages and sub-states. Collaborative state machine framework300may support additional states.

FIG. 4illustrates additional details of collaborative state machine framework300used by communication network100according to an exemplary embodiment of the present invention. In particular, state machines160-163implement collaborative state machine framework300in communication network100. The additional details of collaborative state machine framework300shown inFIG. 4are by way of example only. Other collaborative state machine frameworks may be used without departing from the scope of this disclosure.

As described above, state machines160-163that support collaborative state machine framework300may implement a hierarchy. In collaborative state machine framework300, multiple tasks may be executed concurrently, and one task may need to be informed of errors occurring in other tasks. To support this, collaborative state machine framework300implements a hierarchy within at least some of the states or tasks.

As shown inFIG. 4, at least some of states304-310include normal sub-state machine402and exception sub-state machine404. In this example, normal sub-state machine402supports various sub-states406-412. Sub-states406-412represent sub-tasks needed to perform the task associated with one of states304-310. These sub-tasks may represent, for example, portions of a higher-level state (such as state306) that has a superior-subordinate relationship or that is repetitive in nature.

In this example, exception sub-state machine404supports various exception sub-states414-416. Exception sub-states414-416represent sub-tasks associated with exception or error handling. For example, exception sub-states414-416in one of states304-310may notify other states304-310of an error. Exception sub-states414-416may also perform clean-up operations once errors have occurred. In this way, exception (or error) handling may be performed within each one of states304-310and other ones of states304-310may be notified of the exceptions (or errors) and may act accordingly.

Dividing states in collaborative state machine framework300into normal sub-state machine402and exception sub-state machine404may help to simplify the logic needed to implement collaborative state machine framework300. Moreover, this division may provide a straightforward mechanism for handling exceptions or errors.

AlthoughFIG. 4illustrates one example of additional details of collaborative state machine framework300used by communication network100ofFIG. 1, various changes may be made toFIG. 4. For example, each of states304-310may include any number of sub-tasks in normal sub-state machine402and any number of sub-tasks in exception sub-state machine404.

FIG. 5depicts flow diagram500, which illustrates a method for providing service in communication network100ofFIG. 1according to the principles of the present invention. For ease of explanation, flow diagram500is described with respect to state machine161operating in base station106. The method may be used by any other device and in any other communication network without departing from the scope of the present invention.

Initially, a request for service is received (process step502). This may comprise, for example, base station106receiving a request from wireless communication device110. The request may represent a message indicating that a telephone voice connection is desired between wireless communication device110and a destination.

Next, state machine161transitions from null state302(process step504). This may include, for example, state machine161transitioning from null state302to correlation state304. Correlation state304then launches two or more concurrent states306-308(process step506). This may include, for example, state machine161performing two or more transitions and operating in two or more concurrent states306-308at the same time.

Tasks associated with concurrent states306-308are then performed (process step508). This may include, for example, MSC130assigning a CIC to the requested telephone call as part of one concurrent state306. This may also include base station controller210assigning resources to the requested call as part of other concurrent state308.

Next, correlation state304correlates the results from concurrent states306-308(process step510). This may include, for example, correlation state304determining whether the tasks associated with concurrent states306-308were successfully completed. If not, correlation state304may take any suitable action, such as returning to null state302.

If the tasks were successful, correlation state304places the results in any suitable format and transitions to the next state (process step512). This may include, for example, state machine161transitioning from correlation state304to final state310. After completion of any tasks associated with final state310, communication network100provides the requested service (process step514). This may include, for example, communication network100establishing a voice connection through network100.

AlthoughFIG. 5illustrates one method of providing service in communication network100, various changes may be made toFIG. 5. For example, state machine161may transition from null state302to one or more intermediate states before transitioning to correlation state304. State machine161may transition to any number of correlation states304during the method. Furthermore, state machine161may transition from correlation state304to one or more intermediate states before transitioning to final state310. Each correlation state304may launch any suitable number of concurrent states306-308.