Appeal No. 2003-0843 Page 6
Application No. 09/198,728
as keepers, while the rest, i.e., those with fractional trunk
size demands, are made stragglers (specification, page 21).
Keepers are routed, as shown on graph G, according to a selected
routing algorithm (shortest path routing). Initial graphs Gs are
then formed from the links in graph G which have been used for
carrying keeper demands. Upon selection of a straggler-
connectivity option, all stragglers (figure 6B) are put on a
working list L1. One of the stragglers on the list is then chosen
and is referred to as fi. If a path exists between the source
and destination nodes of fi, fi is removed from list L1. If there
is no path Gs between the source node and destination node of fi,
straggler fi is converted to a keeper along the shortest path in
G, adding required capacity along its path. For links along the
path which are not included in the current Gs, these links are
added to Gs to form a new Gs. If L1 is empty, all stragglers are
put into a working list L2 (figure 6C). Upon picking a straggler
fj from L2, the straggler is routed along the shortest path
between its source and destination in Gs. A check is made as to
whether there is adequate connectivity along the shortest path to
accommodate fj. If adequate connectivity exists, fj is removed
from the list. If not, two augmentation options are available,
capacity-only augmentation or capacity-plus-connectivity
Page: Previous 1 2 3 4 5 6 7 8 9 10 11 Next
Last modified: November 3, 2007