PNNI: Routing in ATM NetworksSlide 2PNNIFeatures of PNNIAddressingLink State RoutingVery Large NetworksHierarchical LayersHierarchical ViewTerminologySlide 11Topology State InformationTopology State ParametersDatabase Synchronization and FloodingInformation Flow in the HierarchyTopology AggregationAddress SummarizationAddress ScopeCall Admission ControlSource RoutingDesignated Transit ListsDTL: ExampleCrankback and Alternate Path RoutingSummaryAbbreviationsSlide 26Slide 27ReferencesReferences (cont)Raj JainThe Ohio State University1PNNI: PNNI: Routing in ATM NetworksRouting in ATM NetworksRaj JainProfessor of CIS The Ohio State UniversityColumbus, OH [email protected]://www.cse.ohio-state.edu/~jain/Raj JainThe Ohio State University2Distribution of topology informationHierarchical groups Source routing  Designated Transit ListsCrankback and Alternate routingAddressingRef: ATM Forum 94-0471R9, "PNNI Draft Specification (Phase 1)" OverviewRaj JainThe Ohio State University3PNNIPNNIPrivate Network-to-network InterfacePrivate Network Node InterfaceSwitchSwitchSwitchSwitchEndSystemEndSystemEndSystemEndSystemPNNIATMNetworkATMNetworkEndSystemEndSystemEndSystemEndSystemPNNIATMNetworkATMNetworkRaj JainThe Ohio State University4Features of PNNIFeatures of PNNIPoint-to-point and point-to-multipoint connectionsCan treat a cloud as a single logical linkMultiple levels of hierarchy  Scalable for global networking.Reroutes around failed components at connection setupAutomatic topological discovery  No manual input required.Connection follows the same route as the setup message (associated signaling)Uses: Cost, capacity, link constraints, propagation delayAlso uses: Cell delay, Cell delay variation, Current average load, Current peak loadUses both link and node parametersSupports transit carrier selectionSupports anycastRaj JainThe Ohio State University5Level 1AddressingAddressingMultiple formats.All 20 Bytes long addresses.Left-to-right hierarchicalLevel boundaries can be put in any bit position13-byte prefix  104 levels of hierarchy possible Level 2 Level 3 Level 4Raj JainThe Ohio State University6Link State RoutingLink State RoutingEach node sends “Hello” packets periodically and on state changes. The packet contains state of all its linksThe packet is flooded to all nodes in the networkA.1.3A.1.1A.1.2A.2.1A.2.2Raj JainThe Ohio State University7Very Large NetworksVery Large NetworksA.1.3A.1.1A.1.2A.2.1A.2.2B.1.1B.1.2B.1.3zC.1.1C.1.2B.2.1B.2.3Raj JainThe Ohio State University8Hierarchical LayersHierarchical LayersA.1.3A.1.1A.1.2A.2.1A.2.2B.1.1B.1.2B.1.3zC.1.1C.1.2B.2.1B.2.3A.1A.2B.1B.2CABRaj JainThe Ohio State University9Hierarchical ViewHierarchical ViewA.2 B.1 B.1 CA B CA.1A.2A.1.3A.1.2B CA.1.1’s View:A.1.1Raj JainThe Ohio State University10TerminologyTerminologyPeer group: A group of nodes at the same hierarchyBorder node: one link crosses the boundaryLogical group node: Representation of a group as a single pointLogical node or Node: A physical node or a logical group nodeChild node: Any node at the next lower hierarchy levelParent node: Logical group node at the next higher hierarchy levelLogical links: links between logical nodesRaj JainThe Ohio State University11Peer group leader (PGL): Represents a group at the next higher level. Node with the highest "leadership priority" and highest ATM address is elected as a leader. Continuous process  Leader may change any time.PGL acts as a logical group node. Uses same ATM address with a different selector value.Peer group ID: Address prefixes up to 13 bytesRaj JainThe Ohio State University12Topology State InformationTopology State InformationMetric: Added along the path, e.g., delayAttribute: Considered individually on each element.Performance, e.g., capacity or Policy related, e.g., securityState parameter: Either metric or attributeLink state parameter. Node state parameter.Topology = Link + NodesTopology state parameter: Link or node state parameterPNNI Topology state element (PTSE): Routing information that is flooded in a peer groupPNNI Topology state packet (PTSP): Contains one PTSERaj JainThe Ohio State University13Topology State ParametersTopology State ParametersMetrics:Maximum Cell Transfer Delay (MCTD)Maximum Cell Delay Variation (MCDV)Maximum Cell Loss Ratio (MCLR)Administrative weight Attributes:Available cell rate (ACR)Cell rate margin (CRM) = Allocated - ActualFirst order uncertainty. Optional.Variation factor (VF) = CRM/Stdv(Actual)Second order uncertainty. Optional.Branching Flag: Can handle point-to-multipoint trafficRestricted Transit Flag: Supports transit traffic or notRaj JainThe Ohio State University14Database Synchronization and FloodingDatabase Synchronization and FloodingUpon initialization, nodes exchange PTSE headers (My topology database is dated 11-Sep-1995:11:59)Node with older database requests more recent infoAfter synchronizing the routing database, they advertise the link between themThe ad (PTSP) is flooded throughout the peer groupNodes ack each PTSP to the sending neighbors, update their database (if new) and forward the PTSP to all other neighborsAll PTSEs have a life time and are aged out unless renewed.Only the node that originated a PTSE can reissue it.PTSEs are issued periodically and also event driven.Raj JainThe Ohio State University15Information Flow in the HierarchyInformation Flow in the HierarchyInformation = Reachability and topology aggregationPeer group leaders summarize and circulate info in the parent groupA raw PTSE never flows upward.PTSEs flow horizontally through the peer group and downward through children.Border nodes do not exchange databases (different peer groups)Raj JainThe Ohio State University16Topology AggregationTopology AggregationGet a simple representation of a groupAlternatives: Symmetric star (n links) or mesh (n2/2 links)Compromise: Star with exceptionsABFEHDCGFEHGFEHG1.251.251.251.2532221.51.51.51.5Raj JainThe Ohio State University17Address SummarizationAddress SummarizationSummary = All nodes with prefix xxx, yyy, ... + foreign addressesNative addresses = All nodes with prefix xxx, yyy, ...Example: A.2.1 = XX1*, Y2*, W111 A.2.2 = Y1*, Z2*A.2.3 = XX2*A.2 = XX*, Y*, Z2*, W111. W111 is a foreign