Abstract:
Methods and apparatus are disclosed for distributing and synchronizing a global time among components of a packet switching system. A global time is kept by a master component of the switching system. In an implementation, components of the packet switching system determine an update delay from its neighbor(s) which might send it a global time update message. This update delay corresponds to certain transmission and processing delays incurred in propagating global time from one component to another. A master component periodically distributes a current global time to its neighbors, which in turn update their global time value and propagate the updated global time to their neighbors. In this manner, global time is kept synchronized among components in a packet switching system.

Description:
FIELD OF THE INVENTION 
     This invention relates to networking and switching systems; and more particularly, the invention relates to distributing and synchronizing a representation of time between components of a packet switching system. 
     BACKGROUND OF THE INVENTION 
     The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (i.e., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Packet technology typically allows a plurality of information types to be transmitted over the same transmission lines and using the same packet switching systems and devices. 
     As used herein, the term “packet” refers to generically addressable packets of all types, including, but not limited to, fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term “system” is used generically herein to describe any number of components, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof Packet switching systems can comprise many different components, with many of these components having their own independent clocks and independent counters representing a current value of time. In certain systems, it is important that the time counters of these components be synchronized; that is, each of the time counters reflect substantially the same time (within some small tolerance). Prior approaches to synchronize the clocks of the various components rely a common reset line or broadcast bus. However, such approaches are not applicable to systems which do not have a common reset line or broadcast bus. Desired are improved methods and systems for synchronizing a representation of time between components of a packet switching system. 
     SUMMARY OF THE INVENTION 
     Systems, apparatus and methods are disclosed for synchronizing a representation of a global time among components of a packet switching system. In one embodiment, the method for synchronizing a first time counter of a first component of a packet switching system with a second time counter of a second component of the packet switching system, where the first and second components are interconnected by one or more links, includes determining a message delay between the first and second components. The second component sends a time synchronization message to the first component. The time synchronization message including a time value of the second time counter. The first component receives the time synchronization message and updates its time counter based on the time value of the second time counter received in the time synchronization message and the determined message delay. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The appended claims set forth the features of the invention with particularity. The invention, together with its advantages, may be best understood from the following detailed description taken in conjunction with the accompanying drawings of which: 
     FIGS. 1A-C are block diagrams of a few of many possible embodiments and various operating environments of packet switching systems; 
     FIG. 2 is a flow diagram illustrating the operation of a packet switching system; 
     FIG. 3A is a block diagram illustrating one of many possible embodiments for determining delay between two components; 
     FIG. 3B is a block diagram of a packet format used in an embodiment for determining delay between two components; 
     FIGS. 3C-D are flow diagrams illustrating the steps performed in an embodiment for determining delay between two components; 
     FIG. 4A is a block diagram of a packet format used in an embodiment for communicating a new time counter value between two components; 
     FIGS. 4B-C are flow diagrams illustrating the steps performed in an embodiment for updating a new time counter value between two components; and 
     FIGS. 5A-B are flow diagrams illustrating the steps performed in an embodiment for determining which of the components is the current master component. 
    
    
     DETAILED DESCRIPTION 
     Methods and apparatus are disclosed for distributing and synchronizing a representation of time between components of a packet switching system. Such methods and apparatus are not limited to a single packet switching environment. Rather, the architecture and functionality of the invention as taught herein and would be understood by one skilled in the art is extensible to an unlimited number of packet switching environments and embodiments in keeping with the scope and spirit of the invention. Embodiments described herein include various elements and limitations, with no one element or limitation contemplated as being a critical element or limitation. Each of the claims individually recite an aspect of the invention in its entirety. Moreover, some embodiments described may include, inter alia, systems, integrated circuit chips, methods, and computer-readable medium containing instructions. The embodiments described hereinafter embody various aspects and configurations within the scope and spirit of the invention. Additionally, flow diagrams are used herein to illustrate embodiments, with some of the embodiments performing certain steps and operations in parallel or in other orders in keeping with the scope and spirit of the invention. 
     Turning now to the figures, FIGS. 1A-C and their discussion herein are intended to provide a description of various exemplary packet switching systems. FIGS. 1A-C illustrate different forms of packet switching systems. FIG. 1A illustrates an exemplary packet switching system. FIG. 1B illustrates an exemplary packet switching system comprising multiple planes of switching elements. FIG. 1C illustrates an exemplary folded packet switching system comprising multiple planes of switching elements. Of course, the packet switching systems may have more or less elements. 
     Turning now to FIG. 1A, illustrated is an exemplary operating environment and embodiment  120  of a packet switching system. Packet switching system  120  comprises multiple interfaces  131 - 134  interconnected over multiple links to an interconnection network  121 . Interconnection network  121  as shown comprises multiple switching elements  122 - 125  also interconnected by multiple links. The interfaces  131 - 134  may connect via bi-directional connections to other systems (not shown). 
     Turning now to FIG. 1B, illustrated is an exemplary operating environment and embodiment  140  of a packet switching system. Packet switching  140  comprises multiple interfaces  149  and  159  interconnected over multiple links to interconnection networks  141  and  151 . (It is also possible that packet switching networks  141  and  151  could be considered a single interconnection network). Interconnection network  141  comprises switching elements  142 - 147  interconnected by links. Interconnection network  151  comprises switching elements  152 - 157  interconnected by links. The interfaces  149  and  159  may connect via bi-directional connections to other systems (not shown). 
     Turning now to FIG. 1C, illustrated is an exemplary operating environment and embodiment  160  of a folded packet switching system. Packet switching  160  comprises multiple interfaces  169  and  179  interconnected over multiple links to interconnection networks  161  and  171 . (It is also possible that packet switching networks  161  and  171  could be considered a single interconnection network). Interconnection network  161  comprises switching elements  162 - 165  interconnected by links. Interconnection network  171  comprises switching elements  172 - 175  interconnected by links. The interfaces  169  and  179  may connect via bi-directional connections to other systems (not shown). 
     In implementing the packet switching systems illustrated in FIGS. 1A-1C, many design decisions are made such as how many switching elements and interconnection networks are to be used and how to break the packet switching system up into implementable components. These decisions are typically based on such considerations, inter alia, as traffic, pin count, and power requirements. Each of the components of the packet switching system is typically connected to one or more other components via one or more links. 
     Referring to FIG. 1C, packet switching system  160  may be implemented by partitioning the system into multiple components, and in a variety of different partitioning schemes. For example, interface  169  may be implemented as a first component; interface  179  may be implemented as a second component; switching elements  162  and  163  may be implemented as a third component; switching elements  164  and  165  may be implemented as a fourth component; switching elements  172  and  173  may be implemented as a fifth component; switching elements  174  and  175  may be implemented as a sixth component with the appropriate links communicating between the six components to build a functional packet switching system  160 . Each of these components has a separate time counter. In certain implementations, these time counters are synchronized to the same value for packet switching system  160  to operate correctly. Embodiments of the synchronization operation will be described in more detail hereinafter. 
     Many different embodiments for distributing and synchronizing a common time to various components of a packet switching system are possible in keeping within the scope and spirit of the invention. In one embodiment, a time counter value is sent from a master component to all components, with these components updating their respective time counters based on the received time counter value and a time delay in receiving the update message from the master component. Alternatively, the received time value could already account for the delay between the component and the master component. In another embodiment, a master component synchronizes its time counter with neighboring components. Then these neighboring components update their time counter time with their neighboring components, and so on as to propagate the global time through-out the packet switching network. 
     FIG. 2 is a high-level flow diagram of a process for synchronizing the time counters of components within a packet switching system. Referring to FIG. 2, processing begins at step  200  and proceeds to step  205  where the components of the packet switching system determine update delays between their neighboring components. Next, in step  210 , a master component initiates distribution of a global time through-out the packet switching network. The global time could be distributed from the master component, or propagated among components. Each component receives a message indicating a representation of the global time and updates its time counter based on the received indication and the determined update delay from the source of the global time (e.g., the master component or a neighboring component). The message indicating the global time could further include the update delay, or the value of global time could already take into account the determined delay. Next, in step  215 , a duration of time is waited before repeating the distribution of global time loop. Because each component has its own clocking mechanism, some time counter jitter will occur within the system. A goal of certain embodiments is to align the time counters of all components within a packet switching system within some small amount, such as a few packet times or some small time variance. In this regard, a packet switching system may want to resynchronize every so often, whether this duration be based on a predetermined period of time or a measured amount of jitter. Certain embodiments might also repeat step  205  each time through the loop to determine the current delay. Step  205  may be deleted if the delay remained constant and could be determined without measuring. 
     Turning now to FIGS. 3A-3D, illustrated are embodiments for synchronizing two neighboring components. First, FIG. 3A illustrates a block diagram representation of relevant time synchronization portions of two components  310  and  320 , which are interconnected via links  319  and  329 . Each component  310 ,  320  comprises some control logic  311 ,  321 , a global time counter  313 ,  323  for maintaining a value of the global time, an optional free running counter  312 ,  324  (in certain embodiments described herein, the global time counter  313 ,  323  could be used in place of the free running counter  312 ,  324 ), an output block  314 ,  324  and an input block  315 ,  325  for communicating with one or more components, and one or more internal communications mechanisms  316 ,  326  (shown as a bus for illustrative purposes) for communication between elements of the components  310 ,  320 . 
     As previously discussed herein, the synchronization process may be divided into two processes: determining an update delay and distributing a global time. Although not required, typically the update delay is determined prior to the distribution of a global time. FIGS. 3B-3D will be used to help illustrate an embodiment for determining the update delay with reference to the block diagram in FIG.  3 A. 
     In certain embodiments and as illustrated in FIG. 3B, a control packet  330  is created and used in determining the update delay between two components. By sending a packet back and forth between two components and recording relative times at each component for the sending and receiving operations, an update delay value can be calculated. As shown, control packet  330  includes a header  331 , a transmitter departure time field  332 , a receiver departure time field  333 , a receiver departure time field  334 , and a transmitter receive time field  335 . The use of these fields and the delay calculation will now be described using the flow diagrams illustrated in FIGS. 3C-D. 
     FIGS. 3C-D illustrate flow diagrams of a process for determining an update delay performed by the first and second components  310  and  320  (FIG. 3A) respectively, and in parallel to determine the update delay. Referring first to FIG. 3C, processing begins by the first component  310  at step  360  and proceeds to step  362  where the first component  310  creates a message delay control packet  330  (FIG. 3B) which will be sent to the second component  320  and returned to the first component  310 . Next, in step  364 , the first component  310  inserts a local departure time from its free run clock  312  (FIG. 3A) (or alternatively its global time counter  313 ) into the message delay control packet  330  and sends the message delay control packet  330  to the second component  320 . 
     Referring now to FIG. 3D, processing begins by the second component  320  at step  380  and proceeds to step  382  where the second component  320  receives the message delay control packet  330  from the first component  310  and inserts a local arrival time-stamp from its free run clock  322  (FIG. 3A) (or alternatively its global time counter  323 ) into the message delay control packet  330 . Next, in step  384 , the message delay control packet  330  is placed in an output queue of the second component  320  destined for the first component  310 . Then, in step  386 , the second component  320  inserts a local departure time from the same counter used in step  382  into the message delay control packet  330  and sends the message delay control packet  330  to the first component  310 . 
     Returning to the processing of FIG. 3C, in step  366 , the first component  310  receives the returned message delay control packet  330  from the second component  320  and inserts a local arrival time-stamp from the same counter used in step  364 . Then, in step  368 , the first component calculates the update delay. In an embodiment, the update delay is computed using simple algebra using the values of fields  332 - 335  from the packet  330  (FIG.  3 B). First, the round-trip time between the first component  310  and second component  320  is determined by subtracting the value of the first component departure time  332  from the first component receive time  335 . Next, the time that packet  330  was in the second component  320  (i.e., the second departure time  334  minus the second component receive time  333 ) is subtracted from the calculated round-trip time to produce the time the control packet  330  spent being transmitted across links  319  and  320  and processing time to time-stamp the control packet  330  twice. Assuming that the delay is equal going to and from the first component, then the update delay is one-half of the previously calculated value. If this assumption is not valid for a particular embodiment, alternative measurement and calculation mechanisms may be used to determine the update delay. Moreover, if the update delay varies with each packet transmission, then multiple message delay control packets may be sent and an appropriate delay value may be determined. As taught herein, many different embodiments are possible within the scope and spirit of the invention. 
     FIGS. 4A-C illustrate an embodiment for distributing the global time through-out a packet switching network, such as packet switching network  140  (FIG. 1B) or  160  (FIG.  1 C). Turning first to FIG. 4A, illustrated is a control packet  410  for distributing global time between two neighboring components, such as the first and second components  310  and  320  (FIG.  3 A). Control packet  410  contains several fields including a header field  411 , a field  412  containing the value of the global time at the sending component when the control packet  410  was created, a field  413  containing the value of the free running counter at the sending component when the control packet  410  was created, a field  414  at the sending component containing the value of the free running counter upon departure from the sending component, and a field  415  containing the value of the free running counter at the receiving component upon receipt. 
     The use of control packet  410  is further described hereinafter in relation to FIGS. 4B-C. FIG. 4B illustrates the operation of an embodiment of a master component, whose value of global time is used to synchronize the other components of the packet switching system. FIG. 4C illustrates the operation of an embodiment of a component which updates its global time and then proceeds to update its other neighbors with its value of the global time. FIGS. 4B-C use flow diagrams to illustrate their functionality. In some embodiments, certain steps and operations are performed in parallel or in other orders in keeping with the scope and spirit of the invention. 
     Turning first to FIG. 4B, processing begins at step  420  and proceeds to step  422  where the master component initializes an update timer which is used to determine when to repeat the processing of updating the packet switching system with its global time. In other embodiments, step  422  could be performed between steps  430  and  440 , or at various other times. Next, in step  424 , the master component determines which of the planes of the packet switching system to update. While there are more planes to update as determined in step  430 , a plane to be updated is selected in step  442 . Next, in step  444 , a control packet  410  (FIG. 4A) is created and the values of the global time and its free running counter are inserted in fields  412  and  413 . Next, in step  446 , during the operation of sending the created control packet  410  to the selected plane of the packet switching system, the current value of the free running counter of the master component is inserted into field  414  of the control packet  410 , and the control packet  410  is sent to the plane of the switching system selected in step  442 . Once all planes have been updated as determined in step  430 , step  440  is performed to delay until the update timer is expired. After the update timer is expired, processing returns to step  422  to update the packet switching network with its global time. 
     FIG. 4C illustrates the steps performed by a component receiving a control packet for updating its local version of the global time, and for possibly updating neighboring components. Processing begins at step  460  and proceeds to step  462  where the component receives the control packet  410  (FIG. 4A) and inserts the current value of its free run counter in field  415  of control packet  410  (FIG.  4 A). One embodiment uses a timer or counter to determine, as illustrated by step  463 , whether a sufficient duration has elapsed since the last update control packet is received, which may or may not me indicative of receiving update packets from multiple neighbors. If sufficient time has not elapsed, the update control packet is ignored and processing returns to step  462 . 
     Otherwise, in step  464 , the component calculates its new value of global time based on the information contained in the received control packet and the predetermined update delay. The new global time for the receiving component can be calculated using simple algebra by adding the value of the global time from field  412  to the processing delay time in the sending system (field  414  minus field  413 ) plus the processing delay time in the current system (free running counter of the current system minus field  415 ) plus the update delay. In this manner, the global time is updated based on the values of (1) the global time at the sending system, (2) the delays within the sending and receiving systems, and (3) the transmission delays. Once the value for the new global time has beencalculated, the global time counter of the component is updated in step  466 . 
     Next, steps  470 - 476  are performed to propagate the global time to any neighboring components requiring updating. While there are neighboring components to notify with the new global time value as determined in step  470  (there could be zero or more components), a component to be updated is selected in step  472 . In some embodiments, all of the neighboring components are not notified, otherwise certain components might receive multiple, and possibly numerous, updates, especially in multipath systems. In one embodiment, an enable bit or bits are used to identify whether to notify any neighboring components and/or which components to notify (or not to notify). 
     Next, in step  474 , a control packet  410  (FIG. 4A) is created with the local values of the global time and free running counter inserted into fields  412  and  413  of control packet  410 . Next, in step  476 , during the operation of sending the created control packet  410  to the selected component of the packet switching system being updated, the current value of the free running counter of the current component is inserted into field  414  of the control packet  410 , and the control packet  410  is sent to the component of the switching system selected in step  472 . One all components have been sent control packets  410  to update their respective global counters as determined in step  470 , processing returns to step  462  to await the receipt of a control packet  410  for the component to update its global time counter. 
     Initially, the packet switching system determines or identifies a component to act as the master component for distributing and synchronizing its global time with the other components. However, it is possible that during the operation of the packet switching system, the master component could fail, or possibly some other fault occurs within the packet switching system (e.g., a link or switch element failure) which prohibits global time being distributed from the master component to the other components within the packet switching system. These failure scenarios may be accommodated and/or overcome. In one embodiment, redundancy among master components is provided by having the master component cease acting as the master controller upon detection of a failure, with another component becoming the master controller upon such a failure. 
     Turning now to FIGS. 5A-B, illustrated are flow diagrams for exemplary embodiments of the master component (FIG. 5A) and of redundant components which could become the master component (FIG.  5 B). The processing of FIG. 5A begins with step  500  and proceeds to step  510  where the master controller monitors itself and the packet switching system for failures which inhibit its effectiveness as master controller for distributing global time to the other components of the packet switching system. Upon detection of such a failure, the master controller stops acting as master controller (e.g., stops sending out global time updates) as indicated by step  520 . Next, the master controller generates and sends a fault notification packet to an operations system or other alarm system in step  522 , and processing of FIG. 5A terminates with step  530 . In certain embodiments and with certain failures, the old master controller could be placed as a backup master controller after the fault is corrected. 
     Turning now to FIG. 5B, illustrated is an embodiment of backup master components to determine when to become the actual master component based on a time-out value. Processing of FIG. 5B begins at step  560  and proceeds to step  562  where the component receives an initialization control packet which indicates a time-out value for the component to use, which is extracted in step  564 . Alternatively, one of numerous other mechanisms could also be used, such as a random value or a preprogrammed value. Next, in step  566  a master time-out timer is initialized to the time-out value. Processing then loops among steps  570 - 574 , until either a global update control packet is received at which time the master time-out timer is re-initialized in step  566 , or until the master time-out timer has expired as determined in step  574  after the master time-out timer has been updated in step  572 . If the master time-out timer has expired, then, if no faults have been detected which would hinder the component from effectively acting as the master controller as determined in step  576 , the component becomes the master component as indicated by step  578 . Processing of FIG. 5B terminates with step  580 . 
     In view of the many possible embodiments to which the principles of our invention may be applied, it will be appreciated that the embodiments and aspects thereof described herein with respect to the drawings/figures are only illustrative and should not be taken as limiting the scope of the invention. To the contrary, the invention as described herein contemplates all such embodiments as may come within the scope of the following claims and equivalents thereof.