next up previous
Next: Characteristics of the Predictive Up: Network Management of Predictive Previous: Predictive Standards-Based Network Management

Introduction to the Predictive Network Management System Algorithm

Terminology borrowed from previous distributed simulation algorithms has a slightly different meaning in this predictive network management system . In addition, new terminology must be introduced. Thus it is important that the terminology be precisely defined.

The predictive network management system  algorithm encapsulates Physical Processes  (PP ) simulating managed network devices within Logical Processes  (LP ). A PP  is nothing more than the executing process defined by the program code. An LP  consists of the PP  and additional data structures and instructions to maintain message order and correct operation as the system executes ahead of real time . An LP  contains a Receive Queue  (QR ), Send Queue  (QS ), and State Queue  (SQ ). The QR maintains newly arriving messages in order by their Receive Time  (TR ). The QS maintains copies of previously sent messages in order of their send times. The state of the LP  is periodically saved in the SQ. The LP  also contains its notion of time known as Local Virtual Time  (LVT ) and a Tolerance  ( tex2html_wrap_inline689  ) which is the allowable deviation between actual and predicted values of incoming messages. Also, the Current State  (CS ) of a LP  will be the current state of the LP  and its encapsulated PP .

The predictive network management system  contains a notion of the complete system time known as Global Virtual Time  (GVT ) and a sliding window known as the Lookahead  time ( tex2html_wrap_inline693  ).

Messages contain the Send Time  (TS ), Receive Time  (TR ), Anti-toggle  (A ) and the actual message itself (M). The TR is the time this message should be received by the destination LP . The TS is the time this message was sent by the originating LP . The A field is the anti-toggle and is used for creating an anti-message  to remove the effect of false messages  as described later. A message will also contain a field for the current Real Time  (RT ). This is used to differentiate a real message  from a virtual message .

A driving process  is required to predict future events and inject them into the system. For example, in a mobile system such as the Rapidly Deployable Radio Network (RDRN) [5], the Global Positioning System (GPS) is used to provide each node with its current position. The GPS receiver process may run in real-time  and inject future predicted location messages as well. In the predictive network management system, the driving process may be the number of expected users and their estimated bandwidth usage. The driving process(es)  originate virtual messages via internal prediction. The remaining PPs  react to these messages as though they are real messages . A message which is generated and time-stamped with the current time will be called a real message . Messages which contain future event information and are time-stamped with a time greater than current time are called virtual messages . If a message arrives at a LP  out of order or with invalid information, it is called a false message . A false message  will cause an LP  to rollback .

A rollback  is a mechanism by which a LP  returns to a known correct state. The rollback  occurs in three phases. In the first phase, the LP  state is restored to a time strictly earlier than the time stamp of the false message . In the second phase, anti-messages are sent to cancel the effects of any invalid messages which had been generated before the arrival of the false message . An anti-message  contains exactly the same contents as the original message with the exception of an anti-toggle bit  which is now set. When the anti-message  and original message meet, they are both annihilated . The final phase consists of executing the LP  forward in time from its rollback  state to the time the false message  arrived. No messages are canceled or sent between the time to which the LP  rolled back and the time of the false message . Because these messages are correct there is no need to cancel or re-send them. This increases performance, and it reduces the number of causing roll-backs. Note that another false message  or anti-message  may arrive before this final phase has completed without causing any problem.


next up previous
Next: Characteristics of the Predictive Up: Network Management of Predictive Previous: Predictive Standards-Based Network Management

Steve Bush
Thu Feb 27 15:34:42 CST 1997