Browse Prior Art Database

Temporal Extension of Blocking Island Contour Maps

IP.com Disclosure Number: IPCOM000013587D
Original Publication Date: 2001-Apr-13
Included in the Prior Art Database: 2003-Jun-18
Document File: 5 page(s) / 42K

Publishing Venue

IBM

Abstract

Blocking Island Contour Maps (BICM) represent the status of a communication network at a particular time point with respect to bandwidth (or other restrictive costs). Network resources are allocated for whole time intervals in practice. For this purpose, a temporal extension of the BICM data structure and the algorithms to generate, maintain and use it are presented herein. TBICM Data Structure. Adding time to the data structure requires to add a variable of type time stamp to network and abstract nodes and links, which are hence of type time stamped . Furthermore, demands and paths (and hence circuits) have a start and end time . Both times are represented as time stamps. In case that the bandwidth parameter of demands and paths change at time points within the starting and end time, such objects are decomposed into multiple elementary objects of the same type. There exist multiple instances of one and the same time-stamped object, each of which represents the object at a different point in time (and hence with a different time stamp value). It is important to understand that a new instance of an object is only created, if the object itself is modified. In particular, modifications of referred objects lead not to new instances of referring objects. Consequently, slots referring to time-stamped objects are themselves time-stamped. There exists slots holding object and sets of objects that have to be time-stamped. All time-stamped instances of an object are ordered in a time line that is represented in each object by a antecedent and subsequent slot . Therefore, an object instance is valid from its time stamp until (but not including) the time stamp of its subsequent object instance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 29% of the total text.

Page 1 of 5

Temporal Extension of Blocking Island Contour Maps

  Blocking Island Contour Maps (BICM) represent the status of a
communication network at a particular time point with respect to
bandwidth (or other restrictive costs). Network resources are
allocated for whole time intervals in practice. For this purpose, a
temporal extension of the BICM data structure and the algorithms to
generate, maintain and use it are presented herein.

TBICM Data Structure. Adding time to the data structure requires
to add a variable of type time stamp to network and abstract
nodes and links, which are hence of type time stamped.
Furthermore, demands and paths (and hence circuits) have a start
and end time. Both times are represented as time stamps. In case
that the bandwidth parameter of demands and paths change at time
points within the starting and end time, such objects are
decomposed into multiple elementary objects of the same type.

There exist multiple instances of one and the same time-stamped
object, each of which represents the object at a different point
in time (and hence with a different time stamp value). It is
important to understand that a new instance of an object is only
created, if the object itself is modified. In particular,
modifications of referred objects lead not to new instances of
referring objects. Consequently, slots referring to time-stamped
objects are themselves time-stamped. There exists slots holding
object and sets of objects that have to be time-stamped. All
time-stamped instances of an object are ordered in a time line
that is represented in each object by a antecedent and subsequent
slot
. Therefore, an object instance is valid from its time stamp
until (but not including) the time stamp of its subsequent object
instance.

Transitions from one abstract node into another one is also
recorded using the antecedent and subsequent slots. Two abstract
nodes or links might be merged (or split) in a transition to a
time stamp from its antecedent time stamps. In contrast, network
nodes and links are only modified, created and deleted, but
neither merged nor split. Consequently, such an object has at
most a single antecedent and subsequent. The former and the
latter are called time-stamped nonlinear and time-stamped linear,
respectively. A subsequent object instance is by definition a
different object, because it would otherwise be merged with its
antecedent object instance.

All references to time-stamped objects have to include a time
stamp as a parameter, which implies that all referring slots have

1

Page 2 of 5

to be modified. Avoiding these modifications is in principle
possible by creating a snapshot of the whole BICM at each time
point for which there exists a time stamped object. This approach
results in a large space complexity and, therefore, time
complexity. Hence, a concise data structure is adopted here. The
worst case space complexity of BICM is O(m) abstract nodes and
O(mlogm) abstract links, where m denotes the number of network
links. The average case is often...