Raj JainThe Ohio State University1PNNI:PNNI:PNNI:Routing in ATM NetworksRouting in ATM NetworksRouting in ATM NetworksRaj JainProfessor of CISThe Ohio State UniversityColumbus, OH [email protected]://www.cis.ohio-state.edu/~jain/Raj JainThe Ohio State University2q Distribution of topology informationq Hierarchical groupsq Source routing ⇒ Designated Transit Listsq Crankback and Alternate routingq AddressingRef: ATM Forum 94-0471R9, "PNNI Draft Specification(Phase 1)"OverviewRaj JainThe Ohio State University3PNNIPNNIPNNIq Private Network-to-network Interfaceq Private Network Node InterfaceSwitch SwitchEndSystemEndSystemPNNIATMNetworkEndSystemEndSystemPNNIATMNetworkRaj JainThe Ohio State University4Features of PNNIFeatures of PNNIFeatures of PNNIq Point-to-point and point-to-multipoint connectionsq Can treat a cloud as a single logical linkq Multiple levels of hierarchy ⇒ Scalable for global networking.q Reroutes around failed components at connection setupq Automatic topological discovery ⇒ No manual input required.q Connection follows the same route as the setup message(associated signaling)q Uses: Cost, capacity, link constraints, propagation delayq Also uses: Cell delay, Cell delay variation, Current averageload, Current peak loadq Uses both link and node parametersq Supports transit carrier selectionq Supports anycastRaj JainThe Ohio State University5Level 1AddressingAddressingAddressingq Multiple formats.q All 20 Bytes long addresses.q Left-to-right hierarchicalq Level boundaries can be put in any bit positionq 13-byte prefix ⇒ 104 levels of hierarchy possibleLevel 2 Level 3 Level 4Raj JainThe Ohio State University6Link State RoutingLink State RoutingLink State Routingq Each node sends “Hello” packets periodicallyand on state changes.q The packet contains state of all its linksq 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 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 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 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 University10TerminologyTerminologyTerminologyq Peer group: A group of nodes at the same hierarchyq Border node: one link crosses the boundaryq Logical group node: Representation of a group as a singlepointq Logical node or Node: A physical node or a logical groupnodeq Child node: Any node at the next lower hierarchy levelq Parent node: Logical group node at the next higherhierarchy levelq Logical links: links between logical nodesRaj JainThe Ohio State University11q Peer group leader (PGL):Represents a group at the next higher level.Node with the highest "leadership priority" andhighest ATM address is elected as a leader.Continuous process ⇒ Leader may change any time.q PGL acts as a logical group node.Uses same ATM address with a different selector value.q Peer group ID: Address prefixes up to 13 bytesRaj JainThe Ohio State University12Topology State InformationTopology State InformationTopology State Informationq Metric: Added along the path, e.g., delayq Attribute: Considered individually on each element.q Performance, e.g., capacity orq Policy related, e.g., securityq State parameter: Either metric or attributeq Link state parameter. Node state parameter.q Topology = Link + Nodesq Topology state parameter: Link or node state parameterq PNNI Topology state element (PTSE):Routing information that is flooded in a peer groupq PNNI Topology state packet (PTSP): Contains one PTSERaj JainThe Ohio State University13Topology State ParametersTopology State ParametersTopology State Parametersq Metrics:q Maximum Cell Transfer Delay (MCTD)q Maximum Cell Delay Variation (MCDV)q Maximum Cell Loss Ratio (MCLR)q Administrative weightq Attributes:q Available cell rate (ACR)q Cell rate margin (CRM) = Allocated - ActualFirst order uncertainty. Optional.q Variation factor (VF) = CRM/Stdv(Actual)Second order uncertainty. Optional.q Branching Flag: Can handle point-to-multipoint trafficq Restricted Transit Flag: Supports transit traffic or notRaj JainThe Ohio State University14Database Synchronization and FloodingDatabase Synchronization and FloodingDatabase Synchronization and Floodingq Upon initialization, nodes exchange PTSE headers(My topology database is dated 11-Sep-1995:11:59)q Node with older database requests more recent infoq After synchronizing the routing database, they advertise thelink between themq The ad (PTSP) is flooded throughout the peer groupq Nodes ack each PTSP to the sending neighbors, update theirdatabase (if new) and forward the PTSP to all otherneighborsq All PTSEs have a life time and are aged out unless renewed.q Only the node that originated a PTSE can reissue it.q PTSEs are issued periodically and also event driven.Raj JainThe Ohio State University15Information Flow in the HierarchyInformation Flow in the HierarchyInformation Flow in the Hierarchyq Information = Reachability and topology aggregationq Peer group leaders summarize and circulate info in theparent groupq A raw PTSE never flows upward.q PTSEs flow horizontally through the peer group anddownward through children.q Border nodes do not exchange databases (different peergroups)Raj JainThe Ohio State University16Topology AggregationTopology AggregationTopology Aggregationq Get a simple representation of a groupq Alternatives: Symmetric star (n links) or mesh (n2/2 links)q Compromise: Star with exceptionsABFEHDCGFEHGFEHG1.251.251.251.2532221.51.51.51.5Raj JainThe Ohio State University17Address SummarizationAddress SummarizationAddress Summarizationq Summary = All nodes with prefix xxx, yyy, ...+ foreign addressesq Native addresses = All nodes with prefix xxx, yyy, ...q Example:q A.2.1 = XX1*, Y2*, W111 A.2.2 = Y1*, Z2*q A.2.3 = XX2*q A.2 = XX*, Y*, Z2*, W111. W111 is a foreign addressxx11xx12xx13y211w111y111y112y113z211z222xx21 xx22 xx23A.2.1 A.2.2A.2.3Raj JainThe Ohio State University18Address ScopeAddress ScopeAddress Scopeq Upward distribution of an address can be inhibited, ifdesired.E.g., Don't tell the competition B that W111 is reachablevia A.q Each group has a level (length of the shortest prefix).q Each address has a scope (level up to which it is