asy United States
`a2) Patent Application Publication co) Pub. No.: US 2004/0095946 Al
`(43) Pub. Date: May20, 2004
`
`Baker
`
`US 20040095946A1
`
`(54) LOGICAL STAR TOPOLOGIES FOR
`NON-STAR NETWORKS
`
`(76)
`
`Inventor: Albert D. Baker, Lincroft, NJ (US)
`
`Correspondence Address:
`MENDELSOHN AND ASSOCIATES PC
`1515 MARKET STREET
`SUITE 715
`PHILADELPHIA, PA 19102 (US)
`
`Appl. No.:
`Filed:
`
`10/298,704
`
`Nov. 18, 2002
`
`Publication Classification
`
`70/405; 370/258
`
`ae HO4L 12/28
`
`ABSTRACT
`(57)
`A logical star architecture imposed on an underlying non-
`star network, for example a Virtual Path Ring (VPR),
`enhances a mesh protocol with an automatic method for
`Virtual Path ID (VPI) generation. The VPIs are used bythe
`mesh protocol’s inherent routing function to effect automatic
`configuration at installation, automatic reconfiguration at
`node updates, and automatic reconfiguration for protection
`switching. The imposition of the logical star architecture on
`a VPR reduces node-to-node switching costs (e.g., delay, as
`well as memory and processing costs) since all nodes in a
`logical star topologyare at most two logical hops away. The
`logical star also conserves virtual path address spacerelative
`to a fully configured ring. Additionally, the imposition of the
`logical star architecture allows cxisting star functions to be
`deployed on the underlying nctwork. Finally, when the
`underlying architecture is a ring, the protection advantages
`of ring networks can be preserved.
`
`NO
`
`PH8
`
`PH4
`
`PH7
`
`N6
`
`PH6
`
`N7
`
`N5
`
`PH2
`
`N2
`
`PH3
`
`PH5
`
`PH4
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 1 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 1 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 1 of 9
`
`US 2004/0095946 Al
`
`oD
`a
`
`PH3
`
`A
`
`Ww
`O
`
`ao
`
`=
`Zz
`
`PH1
`
`PH4
`
` [ve
`
`FIG.1
`
`PH8
`
`we
`
`PH
`
`fe
`
`PH7a PH6
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 2 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 2 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 2 of 9
`
`US 2004/0095946 Al
`
`N
`
`5L
`
`e
`
`O
`z
`
`x
`
`nt
`
`as
`7
`
`Zz
`
`cD
`=z
`
`AN
`
`a
`
`ce)
`r
`0.
`
`aul
`z
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 3 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 3 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 3 of 9
`
`US 2004/0095946 Al
`
`Administerring
`
`302
`
`
`Initial Run
`or Topology
`Update
`?
`
`
`
`
`
`Analyze PTSE
`databaseto
`determine number
`of nodeson ring
`
`306
`
`308
`
`Set counter to 1
`
`Partition Virtual
`
`Path (VP) space
`
`
`Assign VPs from
`head (0) to
`node(counter)
`
`Yes
`
`Increment Counter
`
`316
`
`More nodes ?
`
`No
`
`310
`
`312
`
`314
`
`FIG. 3
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 4 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 4 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 4 of 9
`
`US 2004/0095946 Al
`
`FIG.4
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 5 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 5 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 5 of 9
`
`US 2004/0095946 Al
`
`N1
`
`N3
`
`NO
`
`vPS2
`
`N2
`
`FIG.5
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 6 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 6 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 6 of 9
`
`US 2004/0095946 Al
`
`eHdoNLHd
`
`
`
`_---Z1--
`
`
`
`/SIA
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 7 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 7 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 7 of 9
`
`US 2004/0095946 Al
`
`8Sls
`
`6‘Old
`
`9
`
`ed eed aFi
`
`eeeeeeeeeeeeeP71en|
`
`
`
`ysayyjeued
`
`OHd
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 8 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 8 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 8 of 9
`
`US 2004/0095946 Al
`
`©
`
`"© L
`
`L
`
`B
`
`2
`
`=
`
`a
`
`oO
`w
`
`w
`
`a
`
`Z
`
`a
`
`&
`
`>
`
`oD
`=z
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 9 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 9 of 19
`
`

`

`Patent Application Publication May 20,2004 Sheet 9 of 9
`
`US 2004/0095946 Al
`
`FIG.11
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 10 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 10 of 19
`
`

`

`US 2004/0095946 Al
`
`May 20, 2004
`
`LOGICAL STAR TOPOLOGIES FOR NON-STAR
`NETWORKS
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`[0001]
`[0002] The invention relates to routing signals through
`communication networks.
`
`2. Description of the Related Art
`
`[0003]
`[0004] A star network is a network of nodes having a
`topology in which one of the nodes (called “the central
`node”) is directly connected to every other node in the
`network, while each of those other nodes is directly con-
`nected only to the central node.
`[0005] Onc advantage of star networksis that traffic can be
`ransmitted between any two nodes in the nctwork with at
`most two “hops,” where a hop is defined as transmission
`between two directly connected nodes. For every hop in a
`connection, the node at the beginning of the hop performs a
`certain amount of signal processing to route the signal
`owards the node at the end of the hop. The greater the
`numberof hopsin a connection, the greater the total amount
`of such processing overhead for the connection. From the
`perspective of minimizing processing overhead and associ-
`ated communication latency, the fewer hops in a connection,
`he better. From this perspective, slar networksare allractlive
`because each connection in the network has only one hop or
`wo hops maximum.
`[0006] One of the disadvantages of star networksis that
`he central node is involved in all network traffic. In par-
`icular, for cach star nctwork connection, the central node is
`cither a terminal node(i.c., the start node or the end node for
`he connection) or an intermediate node (i.e., a pass-through
`node for a connection between two non-central nodes). As a
`result, as the number of connections in a star network
`increases, traffic bottlenecks are more and more likely to
`occur at the central node.
`
`
`
`[0007] Another disadvantage of star networks is that the
`central node correspondsto a potential single point of failure
`for the entire network. If the central node fails, then all
`communication in the network will cease.
`
`[0008] A star topology is useful for applications in which
`most orall traffic is to and/or from a single node. In such
`applications, that node is configured to be the central node
`in the star network. On the other hand, a star topology is not
`generally suitable for the backbone of a service provider
`network, because it creates both a bottleneck and a single
`point of failure.
`
`To avoid the disadvantages of star networks asso-
`[0009]
`ciated with traffic bottlenecks and single points of failure,
`networks, such as service provider networks, may be con-
`figured with non-star topologies such as a ring topology. In
`a
`ring network, every nade in the network is directly
`connected to exactly two other nodes. Ring networksare less
`susceptible to traffic bottlenecks than star networks because
`there is no single node in a ring, network that is involved in
`all possible network traffic. Ring networks also avoid the
`single point of failure problems associated with star net-
`works. In particular, if any particular node or physical link
`fails in a ring network, then, in accordance with a Lypical
`ring-based protection scheme, any traffic associated with
`
`that failed node or link maysimply be routed around the ring
`in the other direction (assuming that sufficient bandwidthis
`available).
`
`[0010] On the other hand, one of the disadvantages of ring
`octworks as compared to star nctworks is that the minimum
`distance between two nodes on diametrically opposing sidcs
`of an n-node ring network is n/2 hops. As such, as the
`oumber of nodes in a ring network increases, the average
`amount of processing overhead per network connection also
`increases.
`
`the previous discussion
`Jt should be noted that
`[0011]
`focuses on ideal topologies and ideal advantages and dis-
`advantages thereof.
`In practice, not all ring nodes are
`equivalent, nor are all of the spoke nodes of a star equiva-
`lent. For example,
`in some situations, one or more ring
`oodes in a ring or hub or spoke nodes in a star may typically
`be connected to one or more network feeders, potentiallyin
`a sparing arrangement. A feeder-connected nodeis typically
`equipped with additional redundant hardware for improved
`robustness to failure.
`
`SUMMARY OF THE INVENTION
`
`[0012] The problems in the prior art are addressed in
`accordance with the principles of the invention by overlay-
`ing a logical star topology on a non-star network, such as a
`ring network, such that signals are transmitted through the
`underlying non-star network in accordance with the overlaid
`logical star topology. In an overlaid logical star topology,
`each “logical hop” between two nodes in the logical star
`topology involves two or more nodes in the underlying
`non-star network, ic.,
`the node at
`the beginning of the
`logical hop, the node at the end of the logical hop, and zero,
`one, or more intermediate nodes. In such a logical hop, the
`processing needed to be performed by an intermediate node
`to route the signal to the next node in the logical hop is less
`than the amount of processing performed bythe node atthe
`beginning of a hop. As a result, the amount of processing
`overhead associated with a logical hap {N,, N,,} involving
`a sequence of nodes, N,, N.,...,.N,, where n is greater than
`two, is less than the amount of processing overhead asso-
`ciated with the two or more hops (i.e., {N,, No}, ..., {Nias
`N,,}) that would otherwise be involved in transmitting a
`signal from node N,
`to node N,, in the underlying non-star
`network.
`
`Onthe other hand, because the underlying physical
`[0013]
`
`network has a non-star topology, networks of the invention
`
`
`
`have fewer problemsassociated withtraffic bottlenecks and
`single points of failure than physical star networks. In the
`case where the underlying network is a protected ring, for
`example, the resulting overlaid star network benefits from
`the robustness of the underlying ring while retaining the
`routing simplicity of a star.
`
`In one embodiment, the invention is a methad for
`[0014]
`routing signals in a non-star network having a plurality of
`nades connected in a non-star
`topology. The method
`involves overlaying a logical star topology on the non-star
`network and routing the signals in the non-star network
`according to the logical star topology.
`
`In another embodiment, the invention is a non-star
`[0015]
`network having a plurality of nodes connected in a non-slar
`topology, wherein the non-star network is adapted to route
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 11 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 11 of 19
`
`

`

`US 2004/0095946 Al
`
`May 20, 2004
`
`signals in the network according to a logical star topology
`that is overlaid on the non-star network.
`
`In another embodiment, the invention is a method
`[0016]
`for automatically assigning networkresourcesto a callection
`of elements in a network. The method includes detecting the
`topology of connected elements in the network, partitioning
`resources of the network, allocating the network resources,
`and assigning the network resources to the network ele-
`ments.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0017] Othcr aspects, features, and advantages of the
`invention will become more fully apparent from the follow-
`ing detailed description,
`the appended claims, and the
`accompanying drawings in which:
`
`[0018] FIG. 1 depicts an exemplary bidirectional ring
`network overlaid with a logical star topology according to
`one embodiment of this invention.
`
`[0032] Here PH1 links NO to N1, PH2 links N1 to N2, PH3
`links N2 to N3, PH4 links N3 to N4, PH4 links N4 to N5,
`PHSlinks N5 to N6, PH6 links N6 to N7, PH7 links and PHS
`links N7 to NO. The physical links betweenthe nodes result
`in a physical ring topology. The virtual paths, however,
`represent a logical star topology overlaid on the physical
`ring, where node NO is the central node of the logical star
`[0020] FIG.3depicts a procedure for virtual path assign-
`topology. In particular, VPI links NO to NI, VP2 links NO
`ment according to one embodimentof this invention.
`to N2, VP3 links NO to N3, VP4 links NO to N4, VP5 links
`[0021]
`FIG. 4 depicts a logical star topology overlaid on
`NO to N5, VP6 links NO to N6, and VP7 links NO to N7. As
`the ring network of FIG. 2 according to one embodiment of
`used in this specification, the terms “virtual” and “logical”
`this invention.
`are used interchangeably.
`
`
`
`[0019]
`
`FIG. 2 depicts another exemplary ring network.
`
`[0022] FIG. 5 depicts the logical star topology of the
`network of FIG. 4.
`
`[0023] FIG. 6 depicts an exemplary non-slar, non-ring
`network overlaid with a logical ring topology according to
`one embodiment of this invention.
`
`[0024] FIG. 7 depicts the logical ring topology of the
`network of FIG. 6.
`
`[0025] FIG. 8 depicts another non-star, non-ring network
`overlaid with a logical ring topology according to one
`embodimentof this invention.
`
`[0026] FIG. 9 depicts the logical ring topology of the
`network of FIG.8.
`
`[0027] FIG. 10 depicts an exemplary bidirectional pro-
`tected ring network.
`[0028]
`FIG. 11 depicts a logical star topology overlaid on
`the network of FIG. 10 according to one embodimentofthe
`invention.
`
`DETAILED DESCRIPTION
`
`[0029] Reference herein to “one embodiment” or “an
`embodiment” means that a particular feature, structure, or
`characteristic described in connection with the embodiment
`can be includedinat least one embodiment of the invention.
`The appearances of the phrase “in one embodiment” in
`various places in the specification are not necessarily all
`referring to the same embodiment, nor are separate or
`alternative
`embodiments mutually exclusive of other
`embodiments,
`
`[0030] According to embodiments of the invention, a
`logical star topology is overlaid on an underlying non-star
`network, such as a ring network. Depending on the particu-
`lar implementation, the underlying ring topology may cor-
`respond to the topology of the actual physical networkorit
`
`mayitself correspond to a logical ring topology overlaid on
`a further underlying non-ring (and non-star) network. In
`theory, the invention may involve the sequential overlaying
`of one or more logical topologies on top of the ultimate,
`actual physical network.
`
`Physical Ring with Logical Star Overlay
`
`[0031] FIG. 1 illustrates a bidirectional physical commu-
`nications ring where NO through N7 represent routing and
`switching nodes, PII1 through PII8 represent bidirectional
`physical links between nodes, and VP1 through VP7 repre-
`sent bidirectional virtual paths associated with a logical star
`topology overlaid on the physical ring according to one
`embodimentof this invention.
`
`[0033] One metric associated with cost of communication
`from one node in a communication network to any other
`node in that network is the number of hops a signal must
`pass through on its way [rom a communication source lo its
`destination. In the exemplary ring network of FIG. 1, the
`minimum oumber of hops between diametrically opposed
`nodes (e.g., N2 and N6) is four, and the average number of
`hops betweenall nodes is 167 or about 2.29. Meanwhile, in
`the logical star topology of FIG. 1, the maximum oumber of
`logical hops from anynode to any other node is two, and the
`average number of logical hops between all nodes is % or
`1.75.
`
`[0034] Take, for example, communication from node N2
`to node N6 in the network of FIG. 1. Absent the invention,
`communication from N2 to N6 would involve a minimum of
`four hops, ¢.g., a first hop from N2 to N3 via physical path
`PH3, a second hop from N3 to N4 via physical path PH4, a
`third hop from N4 to N5 via physical path PHS, and a fourth
`hop from N35 to N6 via physical path PH6.
`
`[0035] With the overlaid logical star topology of the
`invention, however, the number of logical hops from N2 to
`N6is two, i-e., a first logical hop from N2 to NO via virtual
`path VP2 and a second logical hop from NO to N6 via VP6.
`In reality, the first logical hop involves communication from
`N2 to NO via intermediate node N1, while the second logical
`hop involves communication from node NO to N6 via
`intermediate node N7. Althoughthe total numberof physical
`hops in the two topologies is the same(i.e., four), the total
`amount of overhead processing for the two communications
`is different. In particular,
`the communication absent
`the
`invention involves “full-overhead” processing at nades N2,
`N3, N4, and N5, while the communication in the overlaid
`logical star topologyof the invention involves full-overhead
`processing at nodes N2 and NO (ie., the start nodes of the
`two logical hops), but only “reduced-overhead” processing
`at nodes N1 and N7(i.e., the intermediate nodes of the two
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 12 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 12 of 19
`
`

`

`US 2004/0095946 Al
`
`May 20, 2004
`
`logical hops). As a result, the total overhead processing for
`the communication of the invention is less than that for the
`communication absent the invention.
`
`[0036] As the number of nodes in the underlying ring
`networkincreases, the advantages of the logical star overlay
`become even moresignificant. In general, in an n-nodering,
`the maximum and average numbers of physical hops
`between nodesin the ring are n/2 and n?/4(n-1), respectively.
`Meanwhile, the maximum and average numbers oflogical
`hops in an n-node logical star overlay are two and 2(n-1)/n,
`respectively. Note thal, as n increases, the average number
`of hopsin the underlying ring network approachesa limit of
`o/4, while the average numberof logical hops in the overlaid
`star topology approaches a limit of two.
`
`Multi-Access Technology
`
`[0037] Fiber-optic rings were historically constructed with
`Synchronous Optical NETwork (SONET) and/or Synchro-
`nous Data Hierarchy (SDH) terminals and Add/Drop Mul-
`tiplexers (ADMs). The forward and protection paths were
`typically implemented with separate fibers or separate wave-
`lengths on the same fiber. These systems suffered from
`wasted bandwidth associated with the limitations of the
`fixed Time Division Multiplex (TDM) access methodology
`of SONET. Recently, multi-access platforms have been
`developed using Asynchronous Transfer Mode (ATM)over
`SONET to overcome some of the bandwidth utilization
`problems associated with SONET-only solutions.
`
`[0038] A common multi-access technology is known as
`AIM Virtual Path Ring (VPR). AIM VPR uses AIM cell
`
`multiplexing instead of TDM in order to gain the benefits of
`
`
`
`statistical multiplexing for transport of data traffic on a fiber
`ring. An AI'M switch can use AIM cell mappings to SONET
`frames to make use of an existing physical SONET ring
`
`
`infrastructure. ATM VPrings are ring configurations with a
`
`
`SONETphysical layer that may either carry ATM traffic
`exclusively or a combination of ATM and Synchronous
`Transfer Mode (STM)traffic. The former configurations are
`supported by pure ATM Add/Drop Multiplexers (ADMs)
`and the latter by hybrid ADMs. GR-2837-CORE,Issue 5,
`“ATM Virtual Path Ring Functionality in SONET—Generic
`Criteria” (incorporated herein by reference in its entirety)
`provides generic functional criteria for incorporating ATM
`VPRfunctionality into SONETrings. It introduces a modi-
`fied terminology for SONET, ATM, and hybrid SONET/
`ATM entities and provides a general SONET ATM ring
`evolution overview.It further introduces functional models,
`discusses potential applications and operations functionality,
`and presents a set of ATM VPlevel requirements for SONET
`ATM VP ADMs.
`
`technology is
`relevant multi-access
`[0039] Another
`Dynamic Packet Transport (DPT). DPT enables IP packets
`to be carried directly over the ring. The IP packets are carried
`in SONETframes. The entire capacity of the ring is treated
`as a single bandwidth pool for the purposes ofstatistically
`multiplexing IP packets. If a ring failure occurs,then the ring
`will wrap and a priority mechanism and a fairness algorithm
`will determine the allocation of available bandwidth among
`devices.
`
`[0040] Both of these technologies can be implemented
`incrementally on an existing SONETring network by dedi-
`cating some of the SONET TDM bandwidth to the new
`
`technology. They can also be implemented directly on a
`DWDMnetwork by using SONET framing andat the same
`time avoiding the expense of SONET multiplexers. Both of
`these technologies can also support the overlay of a logical
`star topology per the invention.
`
`ATM Adaptation
`
`[0041] As discussed earlier, for many telecommunications
`carriers today, it is common Lo use an Asynchronous Trans-
`fer Mode (ATM)adaptation layer on top of a SONETring.
`One key advantage of this approach is ellicient support for
`muluple protocols in spite of the rigid underlying SONET
`TDM infrastructure. One well-known adaptation mecha-
`oism for mapping A'M over a SONEYFring is the Virtual
`Path Ring (VPR).
`[0042]
`In sctting up a VPR,the relationship between the
`ring nodes and their virtual paths is administered atinstal-
`lation time. This is a costly and error-prone operation.
`Further, if the ring is altered, then the administration must be
`redone, with the additional complexity that the new nodes
`and path assignments do not
`interfere with previously
`administered characteristics.
`
`[0043] Additionally, node-to-node signaling is challeng-
`ing. If node-to-node paths are administered, at least one
`unique virtual path (VP) must be assigned from every node
`in the ring to every other node in the ring. In an n-node
`network, the number of VPs required is (n°-n)/2. Managing
`this number of VPs can put a burden on system management
`and administration resources. 'urther, if the protection capa-
`bility of the underlying ring is to be maintained, then the
`reverse direction paths must also be provisioned. Provision-
`ing errors mayresult in incorrect operation of the network
`and may remain hidden until a path switch occurs. If the
`node-to-node paths are not administered, then, to reach a
`nade on the opposite side of the ring in a Switched Virtual
`Circuit (SVC) environment, signaling procedures must be
`executed on each and everyintervening node. This causes an
`incremental delay per node that can cumulatively become
`unacceptably large on large rings, and which is exacerbated
`on busyrings.
`
`In the case where the underlying network is an
`[0044]
`Asynchronous Transfer Mode (ATM) Virtual Path Ring
`(VPR) routed according the Private Network-Network Inter-
`face (PNNI), a special Ring Administration task is assigned
`to the peer group leader (PGL). This Ring Administration
`task assigns virtual path IDs (VPIs) to effect a star overlay
`on the VPRat installation and to reconfigure the star overlay
`automatically at node additions, deletions, or link failures.
`Imposition or overlay of the logical star architecture on the
`VPR reduces node-to-node switching costs (c.g., delay, as
`well as memory and processing costs) since all nodes in a
`star topology are at most two logical hops away. The logical
`star also conserves virtual path address space relative to a
`fully configured VPR. Finally, since the underlying network
`is a VPR,the robustness associated with protection switch-
`ing is preserved.
`
`Virtual Path Ring
`
`[0045] A VPRrepresents one very practical example of a
`ring abstraction of an underlying network upon which this
`invention can be implemented. One embodiment of the
`invention manipulates the PNNI routing and signaling pro-
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 13 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 13 of 19
`
`

`

`US 2004/0095946 Al
`
`May 20, 2004
`
`tocols on an (ATM)Virtual Path Ring (VPR)to effect the
`creation of the logical star while maintaining compatibility
`with those protocols. Some implementation details in this
`context follow.
`
`PNNI specifies a logical hierarchyof (partial or full
`[0046]
`mesh) networks for the purpose of generalized routing.
`PNNIincludes a conceptcalled “peer group leaderelection”
`(PGLE) whereby one of the logical nodes within a peer
`group ofnodesis designated the “peer group leader” (PGT).
`The PGT. has certain responsibilities with respect to routing
`and communication of (in some cases, summarized) topol-
`ogy information to other nodes within ils peer group and Lo
`other nodes above and below it in the peer group hierarchy.
`‘These responsibilities afford the PGL certain privileges with
`respect to topology and routing control.It is these privileges
`that are exploited in this implementationof the invention to
`impose a star topology upon the VPR.
`[0047] A PGLis elected by virtueofhis relative “leader-
`ship priority” within its peer group. The leadership priority
`is a parameter configured by the system administrator or
`derived by the invention according to knowledge of the
`system topology.It is thus possible to “rig” the PGLE. Per
`this invention, a “head” node is designated that will execute
`a set of special “star overlay” procedures. Thus, one step in
`the implementation of the star overlay of this invention on
`a VPR is to rig the PGI.E such that the designated “head”
`node ofthe star overlay is the one thal gets elected PGT.. The
`PGT. (and thus the head node ofthe overlaid star network)
`is also a “border” node according to PNNI terminology,
`which equates to it being an AIM Leeder node in the context
`of ATM VPRs. Note that, io one implementation of this
`invention, the a priori knowledge of the peer group leader
`allows vendors to associate additional resources with the
`PGL(e.g., processing power, redundant hardware for pro-
`tection, and memory) to better help the PGL/head node
`accomplishits assigned tasks. In preferred implementations,
`the head node will also be the central node in the logical star
`topology, although that is not necessary.
`[0048] As per the PNNI reference specification, when a
`communications link becomes operational within a PNNI
`network, neighboring nodes exchange identification infor-
`mation over the PNNI Routing Control Channel (RCC),
`which has the well-known Virtual Path ID and Virtual
`Cireuit ID (VPI,VCT) address (0, 18). This is accomplished
`using the PNNI Hello protocol over these links whereby the
`nodes exchangetheir topologystale information using PNNIT
`‘lopology State Elements (P'I'SE) that are flooded through-
`oul the peer group. Il is by this method that the members of
`the peer group become aware of the details of group mem-
`berships and syachronize their topology databases.
`
`[0049] Referring to FIG. 2, assume NO is configured to be
`the head node and is also configured to have the highest
`leadership priority. When the system links become active,
`each adjacent node executes a “I]ello” exchange with its
`neighbor, and, executing normative PNNI procedures,
`develops PTSE and floods those around the ring.
`
`For example, NO exchanges Hellos with N1 via
`[0050]
`path PHT, N1 exchanges Hellos with N2 via path PH2, N2
`exchanges Hellos with N3 via path PH3, and N3 exchanges
`Hellos with N@ via path PH4. Via these neighbor-to-neigh-
`bor exchanges, the latest topology information is flooded
`within this peer group.
`
`[0051] Note that the head node NO has been configured to
`have the highest leadership priority. Thus, it easily wins the
`PGLE,andit is also aware of the fact thatit is both the PGL
`and the head node with respect to the logical star topology
`overlay of this invention. As such, it knows that it must
`execute a set of special “star overlay” procedures including
`“Administer Ring” as outlined in FIG.3.
`
`[0052] As illustrated by FIG. 3, when the head node
`executes the Administer Ring routine, at step 304 it checks
`to see whether this is the initial run of the routine or whether
`a topology update has occurred. A topologystate change
`could be triggered by a change in the PTSE database
`resulting from an addition or subtraction of a node from the
`ring, a node failure, a change in traffic patterns, or other
`occurrences outlined in the PNNIspecification. These would
`be detected by the head node via PNNI topology update
`messages.
`
`If this is the first time the routine has been run, then
`[0053]
`control flows to step 306. In step 306, the PISE database is
`analyzed to determine the number of nodes currently on the
`ring. In step 308, a counteris initialized to “1” correspond-
`ing to the index to thefirst node (e.g., per PISE analysis) on
`the network beyond the head node. In step 310, the VP
`address space is partitioned by the numberof nodes, option-
`ally leaving a scatter of VP addressesin reserve for topology
`changes and growth as per the mechanism detailed in U.S.
`patent application Ser. No. 09/861,947, filed May 21, 2001
`as attorney docket no. Baker 24-2 (“the ’947 application”),
`incorporated herein byreferencein its entirety. In step 312,
`for the node on the ring corresponding to the valuc of the
`counter, a VP, or sct of VPs, is assigned between the head
`node and that node. This assignment can be accomplished
`using the Interim Link Management Interface (ILMI) via the
`management (VPI,VCI) address (0, 16), where the node
`address information contained in the PTSEs formsthe basis
`for configuring the VP assignments.In step 314, the counter
`is incremented by one and, in step 316, a test is dane ta see
`whether the counter exceeds the number of nodes in the
`network (i.e., whether each of the nades has been assigned
`a set of VP addresses).
`If there is another node,
`then
`processing returns ta step 312. If all the nodes have been
`assigned VP addresses, then control returnsto the start of the
`Administer Ring routine at step 302.
`
`[0054] The result of the Administer Ring routine is the
`assignment of one or more virtual paths from the head node
`to each of the other nodesin the ring. This logical architec-
`ture equates to a star topology that
`is overlaid on the
`underlying ring network, as depicted in FIG. 4, where
`VPG1, VPG2, and VPG3 represent sets of virtual path
`addresses where each of VPG1, VPG2 and VPG3represent
`a set of one or morevirtual paths assigned between the head
`node and another node in the network. The dotted lines in
`FIG.4 representvirtual paths, while the solid lines represent
`the communication links of the underlying ring network.
`
`[0055] The following illustrates the application of the
`Administer Ring routine of FIG. 3 to the ring network of
`FIG, 2. As discussed, as the nodes are powered up, they
`would load and run the procedures associated with SONET,
`ATM,VPR, and PNNI protocols at the appropriate points in
`their initialization and configuration along with SNMP and
`TLMI procedures as is conventional
`for networks ofthis
`type. Thus, at the PNNIlevel, the Hello protocol would be
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 14 of 19
`
`UNIFIED PATENTS EXHIBIT 1008
`Page 14 of 19
`
`

`

`US 2004/0095946 Al
`
`May 20, 2004
`
`executed, PTSE would be exchanged by the nodes, and
`knowledge of the addresses and interconnection topology of
`the ring would be established throughout the ring. According
`to this invention, assuming NO is the network feeder, it
`would have been a priori configured with an initial leader-
`ship priority above that of the other nodes N1, N2, and N3
`in the ring. It would thus be elected PGL through the normal
`PNNI PGLEand then load and run the Administer Ring
`routine of this invention.
`
`Per FIG. 3, at step 304, the routine would detect
`[0056]
`that this is the initial run of the procedure and control would
`jump Lo step 306. In step 306, the PISE database is analyzed
`to determine the number of nodes currently on the ring. Io
`step 308, a counteris initialized to “1” corresponding to the
`index in an ATM address array corresponding to the first
`node on the network downstream from the head node (e.g.,
`N1). Instep 310, the VP address space is partitioned by the
`number of nodes otherthan the head node (i.e., three), which
`resulted from the analysis of step 306. In this example, we
`will assumethat 4 bits define the VP address space, resulting
`in a virtual address space of 16 unique addresses. Thus in
`step 310, the virtual address space of 16 addresses is divide
`by 3 yielding 5 addresses per virtual path “set,” with one left
`over. It is typical to reserve some of these addresses for
`future incremental expansion and modification, so in this
`example, 4 of the 16 will be set aside as reserve, leaving 12
`addresses for assignmentto the virtual paths that define the
`star topology (e.g., 4 addresses per virtual path set). In step
`312, corresponding to the valuc “1” of the counter,
`the
`logical route between node NO and node N1 onthe ring is
`assigned VPs1, 2, 3, and 4. In other words,the set of virtual
`paths between node NO and node N1is defined to be virtual
`path sct 1 (VPS1) where VPS1={VP1, VP2, VP3, VP4}),
`while VP 5 is held in reserve. The virtual paths defined by
`VPS1 are then assigned (c.g., via ILMI). In step 314, the
`counter is incremented byone and, in step 316, a test is done
`to see whether the counter exceeds the number of nodes in
`the network (i.e., whether the route from the head node to
`each of the other nades in the ring has been assigned a set
`of VP addresses). In particular, the counter is incremented to
`2 in step 314, and control returns to step 312 where the set
`of virtual paths from node NO to node N21 is defined to be
`VPS2={VP5, VP7, VP8, VP9}. These paths