(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0095946A1
`(43) Pub. Date:
`May 20, 2004
`Baker
`
`US 20040095946A1
`
`(54)
`
`(76)
`
`(21)
`(22)
`
`LOGICAL STAR TOPOLOGIES FOR
`NON-STAR NETWORKS
`
`Inventor: Albert D. Baker, Lincroft, NJ (US)
`Correspondence Address:
`MENDELSOHN AND ASSOCATES PC
`1515 MARKET STREET
`SUTE 715
`PHILADELPHIA, PA 19102 (US)
`Appl. No.:
`10/298,704
`
`Filed:
`
`Nov. 18, 2002
`
`Publication Classification
`
`(51)
`(52)
`
`Es. Oyo E'.
`
`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 by the
`mesh protocols 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 topology are at most two logical hops away. The
`logical Star also conserves virtual path address Space relative
`to a fully configured ring. Additionally, the imposition of the
`logical Star architecture allows existing Star functions to be
`deployed on the underlying network. Finally, when the
`underlying architecture is a ring, the protection advantages
`of ring networks can be preserved.
`
`NO
`
`PH8
`
`PH1
`
`N7
`
`PH7
`
`N6
`
`PH6
`
`N5
`
`N1
`
`PH2
`
`N2
`
`PH3
`
`N3
`
`PH5
`
`PH4
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 1 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 1 of 9
`
`US 2004/0095946A1
`
`N
`
`I
`
`-
`
`o
`
`g
`
`2
`
`2
`
`2
`
`f
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 2 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 2 of 9
`
`US 2004/0095946A1
`
`9
`
`S
`
`s
`
`S2
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 3 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 3 of 9
`
`US 2004/0095946A1
`
`3O2
`
`Administer ring
`
`
`
`
`
`Initial Run
`or Topology
`Update
`?
`
`
`
`
`
`
`
`
`
`Analyze PTSE
`database to
`determine number
`of nodes on ring
`
`Set COunter to 1
`
`Partition Virtual
`Path (VP) space
`
`Assign VPs from
`head (0) to
`node(counter)
`
`Increment COunter
`
`NO
`
`3O8
`
`310
`
`312
`
`314
`
`Yes
`
`316
`
`More nodes 2
`
`FIG. 3
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 4 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 4 of 9
`
`US 2004/0095946A1
`
`
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 5 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 5 of 9
`
`US 2004/0095946A1
`
`9.
`
`S
`
`g
`
`2
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 6 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 6 of 9
`
`US 2004/0095946A1
`
`
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 7 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 7 of 9
`
`US 2004/0095946A1
`
`€T|ZHd|
`||
`| | ||
`| ||
`
`Ie?ued { L— —9N9.Hd| |?seW
`
`
`L–––––––––-----------------------#77- - - - - - -–1
`
`
`
`---
`
`0Hd
`
`———— || TI -------º?-----
`
`| |
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 8 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 8 of 9
`
`US 2004/0095946A1
`
`2
`
`o
`
`h
`
`5
`
`9
`
`Sp
`
`83
`
`S
`
`2
`
`S
`
`O
`
`CD
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 9 of 19
`
`

`

`Patent Application Publication May 20, 2004 Sheet 9 of 9
`
`US 2004/0095946A1
`
`
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 10 of 19
`
`

`

`US 2004/0095946 A1
`
`May 20, 2004
`
`LOGICAL STAR TOPOLOGIES FOR NON-STAR
`NETWORKS
`
`BACKGROUND OF THE INVENTION
`0001) 1. Field of the Invention
`0002 The invention relates to routing signals through
`communication networks.
`0003 2. Description of the Related Art
`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 One advantage of star networks is that traffic can be
`transmitted between any two nodes in the network 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
`towards the node at the end of the hop. The greater the
`number of hops in 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,
`the better. From this perspective, Star networks are attractive
`because each connection in the network has only one hop or
`two hops maximum.
`0006. One of the disadvantages of star networks is that
`the central node is involved in all network traffic. In par
`ticular, for each Star network connection, the central node is
`either a terminal node (i.e., the start node or the end node for
`the 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 corresponds to 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 or all 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.
`0009. To avoid the disadvantages of star networks asso
`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 node in the network is directly
`connected to exactly two other nodes. Ring networks are 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 typical
`ring-based protection Scheme, any traffic associated with
`
`that failed node or link may simply be routed around the ring
`in the other direction (assuming that Sufficient bandwidth is
`available).
`0010. On the other hand, one of the disadvantages of ring
`networks as compared to Star networks is that the minimum
`distance between two nodes on diametrically opposing sides
`of an n-node ring network is n/2 hops. AS Such, as the
`number of nodes in a ring network increases, the average
`amount of processing overhead per network connection also
`increases.
`0011. It should be noted that the previous discussion
`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
`nodes in a ring or hub or spoke nodes in a Star may typically
`be connected to one or more network feeders, potentially in
`a sparing arrangement. A feeder-connected node is 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, i.e., 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 by the node at the
`beginning of a hop. As a result, the amount of processing
`overhead associated with a logical hop {N1, 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., {N1, N2}, ..., {N-1,
`N}) that would otherwise be involved in transmitting a
`Signal from node N to node N in the underlying non-Star
`network.
`0013. On the other hand, because the underlying physical
`network has a non-Star topology, networks of the invention
`have fewer problems associated with traffic 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.
`0014.
`In one embodiment, the invention is a method for
`routing Signals in a non-Star network having a plurality of
`nodes 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.
`0015. In another embodiment, the invention is a non-star
`network having a plurality of nodes connected in a non-Star
`topology, wherein the non-Star network is adapted to route
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 11 of 19
`
`

`

`US 2004/0095946 A1
`
`May 20, 2004
`
`Signals in the network according to a logical Star topology
`that is overlaid on the non-Star network.
`0016. In another embodiment, the invention is a method
`for automatically assigning network resources to a collection
`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
`0.017. Other 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:
`0.018
`FIG. 1 depicts an exemplary bidirectional ring
`network overlaid with a logical Star topology according to
`one embodiment of this invention.
`FIG. 2 depicts another exemplary ring network.
`0019)
`0020 FIG. 3 depicts a procedure for virtual path assign
`ment according to one embodiment of this invention.
`0021
`FIG. 4 depicts a logical star topology overlaid on
`the ring network of FIG. 2 according to one embodiment of
`this invention.
`0022 FIG. 5 depicts the logical star topology of the
`network of FIG. 4.
`0023 FIG. 6 depicts an exemplary non-star, 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.
`0.025
`FIG. 8 depicts another non-star, non-ring network
`overlaid with a logical ring topology according to one
`embodiment of this invention.
`0.026
`FIG. 9 depicts the logical ring topology of the
`network of FIG. 8.
`0.027
`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 embodiment of the
`invention.
`
`66
`
`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 included in at 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.
`0.030. 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 network or it
`
`may itself 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
`FIG. 1 illustrates a bidirectional physical commu
`0031
`nications ring where N0 through N7 represent routing and
`Switching nodes, PH1 through PH8 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
`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,
`PH5 links N5 to N6, PH6 links N6 to N7, PH7 links and PH8
`links N7 to N0. The physical links between the nodes result
`in a physical ring topology. The virtual paths, however,
`represent a logical Star topology overlaid on the physical
`ring, where node N0 is the central node of the logical star
`topology. In particular, VP1 links N0 to N1, VP2 links N0
`to N2, VP3 links NO to N3, VP4 links NO to N4, VP5 links
`N0 to N5, VP6 links NO to N6, and VP7 links NO to N7. As
`used in this specification, the terms “virtual” and “logical”
`are used interchangeably.
`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 from a communication Source to its
`destination. In the exemplary ring network of FIG. 1, the
`minimum number of hops between diametrically opposed
`nodes (e.g., N2 and N6) is four, and the average number of
`hops between all nodes is 1% or about 2.29. Meanwhile, in
`the logical star topology of FIG. 1, the maximum number of
`logical hops from any node to any other node is two, and the
`average number of logical hops between all nodes is 7/4 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, e.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 PH5, and a fourth
`hop from N5 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
`N6 is two, i.e., a first logical hop from N2 to NO via virtual
`path VP2 and a second logical hop from N0 to N6 via VP6.
`In reality, the first logical hop involves communication from
`N2 to N0 via intermediate node N1, while the second logical
`hop involves communication from node N0 to N6 via
`intermediate node N7. Although the total number of 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 nodes N2,
`N3, N4, and N5, while the communication in the overlaid
`logical Star topology of the invention involves full-overhead
`processing at nodes N2 and N0 (i.e., 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
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 12 of 19
`
`

`

`US 2004/0095946 A1
`
`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
`network increases, the advantages of the logical Star overlay
`become even more Significant. In general, in an n-node ring,
`the maximum and average numbers of physical hops
`between nodes in the ring are n/2 and n/4(n-1), respectively.
`Meanwhile, the maximum and average numbers of logical
`hops in an n-node logical Star overlay are two and 20n-1)/n,
`respectively. Note that, as n increases, the average number
`of hops in the underlying ring network approaches a limit of
`n/4, while the average number of 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.
`0.038 A common multi-access technology is known as
`ATM Virtual Path Ring (VPR). ATM VPR uses ATM cell
`multiplexing instead of TDM in order to gain the benefits of
`Statistical multiplexing for transport of data traffic on a fiber
`ring. An ATM Switch can use ATM cell mappings to SONET
`frames to make use of an existing physical SONET ring
`infrastructure. ATMVP rings are ring configurations with a
`SONET physical 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
`VPR functionality into SONET rings. 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 ATMVP level requirements for SONET
`ATM VPADMS.
`0039. Another relevant multi-access technology is
`Dynamic Packet Transport (DPT). DPT enables IP packets
`to be carried directly over the ring. The IP packets are carried
`in SONET frames. The entire capacity of the ring is treated
`as a Single bandwidth pool for the purposes of Statistically
`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 SONET ring network by dedi
`cating some of the SONET TDM bandwidth to the new
`
`technology. They can also be implemented directly on a
`DWDM network by using SONET framing and at 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 to use an ASynchronous Trans
`fer Mode (ATM) adaptation layer on top of a SONET ring.
`One key advantage of this approach is efficient Support for
`multiple protocols in spite of the rigid underlying SONET
`TDM infrastructure. One well-known adaptation mecha
`nism for mapping ATM over a SONET ring is the Virtual
`Path Ring (VPR).
`0042. In setting up a VPR, the relationship between the
`ring nodes and their virtual paths is administered at instal
`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. Further, 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 may result 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
`node on the opposite side of the ring in a Switched Virtual
`Circuit (SVC) environment, signaling procedures must be
`executed on each and every intervening node. This causes an
`incremental delay per node that can cumulatively become
`unacceptably large on large rings, and which is exacerbated
`on busy rings.
`0044) In the case where the underlying network is an
`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 VPR at 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 (e.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 AVPR represents 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
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 13 of 19
`
`

`

`US 2004/0095946 A1
`
`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.
`0046 PNNI specifies a logical hierarchy of (partial or full
`mesh) networks for the purpose of generalized routing.
`PNNI includes a concept called “peer group leader election”
`(PGLE) whereby one of the logical nodes within a peer
`group of nodes is designated the "peer group leader” (PGL).
`The PGL has certain responsibilities with respect to routing
`and communication of (in Some cases, Summarized) topol
`ogy information to other nodes within its peer group and to
`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 implementation of the invention to
`impose a Star topology upon the VPR.
`0047 A PGL is elected by virtue of his 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 PGLE such that the designated “head”
`node of the star overlay is the one that gets elected PGL. The
`PGL (and thus the head node of the overlaid star network)
`is also a “border node according to PNNI terminology,
`which equates to it being an ATM feeder node in the context
`of ATM VPRs. Note that, in 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
`accomplish its assigned tasks. In preferred implementations,
`the head node will also be the central node in the logical Star
`topology, although that is not necessary.
`0.048. 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
`Circuit ID (VPI.VCI) address (0, 18). This is accomplished
`using the PNNI Hello protocol over these links whereby the
`nodes exchange their topology State information using PNNI
`Topology State Elements (PTSE) that are flooded through
`out the peer group. It is by this method that the members of
`the peer group become aware of the details of group mem
`bershipS and Synchronize 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 “Hello” exchange with its
`neighbor, and, executing normative PNNI procedures,
`develops PTSE and floods those around the ring.
`0050 For example, N0 exchanges Hellos with N1 via
`path PHI, N1 exchanges Hellos with N2 via path PH2, N2
`exchanges Hellos with N3 via path PH3, and N3 exchanges
`Hellos with NO 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 N0 has been configured to
`have the highest leadership priority. Thus, it easily wins the
`PGLE, and it is also aware of the fact that it 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.
`0.052 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 topology State 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 PNNI specification. These would
`be detected by the head node via PNNI topology update
`meSSageS.
`0053 If this is the first time the routine has been run, then
`control flows to step 306. In step 306, the PTSE database is
`analyzed to determine the number of nodes currently on the
`ring. In step 308, a counter is initialized to “1” correspond
`ing to the index to the first node (e.g., per PTSE analysis) on
`the network beyond the head node. In step 310, the VP
`address Space is partitioned by the number of nodes, option
`ally leaving a Scatter of VP addresses in 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 by reference in its entirety. In Step 312,
`for the node on the ring corresponding to the value of the
`counter, a VP or set 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 forms the basis
`for configuring the VP assignments. In Step 314, the counter
`is incremented by one and, in Step 316, a test is done to See
`whether the counter exceeds the number of nodes in the
`network (i.e., whether each of the nodes has been assigned
`a set of VP addresses). If there is another node, then
`processing returns to Step 312. If all the nodes have been
`assigned VP addresses, then control returns to 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 nodes in 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 VPG3 represent
`a set of one or more virtual paths assigned between the head
`node and another node in the network. The dotted lines in
`FIG. 4 represent virtual 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
`ILMI procedures as is conventional for networks of this
`type. Thus, at the PNNI level, the Hello protocol would be
`
`Ex.1005
`CISCO SYSTEMS, INC. / Page 14 of 19
`
`

`

`US 2004/0095946 A1
`
`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 N0 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 PGLE and then load and run the Administer Ring
`routine of this invention.
`0056 Per FIG. 3, at step 304, the routine would detect
`that this is the initial run of the procedure and control would
`jump to step 306. In step 306, the PTSE database is analyzed
`to determine the number of nodes currently on the ring. In
`step 308, a counter is 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). In step 310, the VP address space is partitioned by the
`number of nodes other than the head node (i.e., three), which
`resulted from the analysis of step 306. In this example, we
`will assume that 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 assignment to the virtual paths that define the
`Star topology (e.g., 4 addresses per virtual path Set). In Step
`312, corresponding to the value “1” of the counter, the
`logical route between node N0 and node N1 on the ring is
`assigned VPS 1, 2, 3, and 4. In other words, the set of virtual
`paths between node N0 and node N1 is defined to be virtual
`path set 1 (VPS1) where VPS1={VP1,VP2, VP3, VP4}),
`while VP 5 is held in reserve. The virtual paths defined by
`VPS1 are then assigned (e.g., via ILMI). In step 314, the
`counter is incremented by one 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 nodes 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 N0 to node N21 is defined to be
`VPS2={VP5, VP7, VP8, VP9). These paths are then
`assigned (again via ILMI or equivalent administration pro
`tocol),