Raj JainThe Ohio State University1PNNI:PNNI:Routing 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 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 InterfaceSwitchSwitchSwitchSwitchEndSystemEndSystemEndSystemEndSystemPNNIATMNetworkRaj 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 averageload, 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 possibleLevel 2 Level 3 Level 4Raj JainThe Ohio State University6Link State RoutingLink State Routing❑ Each node sends “Hello” packets periodicallyand 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 singlepoint❑ Logical node or Node: A physical node or a logical groupnode❑ Child node: Any node at the next lower hierarchy level❑ Parent node: Logical group node at the next higherhierarchy 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" andhighest 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 thelink between them❑ The ad (PTSP) is flooded throughout the peer group❑ Nodes ack each PTSP to the sending neighbors, update theirdatabase (if new) and forward the PTSP to all otherneighbors❑ 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 theparent group❑ A raw PTSE never flows upward.❑ PTSEs flow horizontally through the peer group anddownward through children.❑ Border nodes do not exchange databases (different peergroups)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 addressxx11xx12xx13y211w111y111y112y113z211z222xx21 xx22 xx23A.2.1 A.2.2A.2.3Raj JainThe Ohio State University18Address ScopeAddress Scope❑ Upward distribution of an address can be inhibited, ifdesired.E.g., Don't tell the competition B that W111 is reachablevia A.❑ Each group has a level (length of the shortest prefix).❑ Each address has a scope (level up to which it is visible).96 8072 1049696725664Raj JainThe Ohio State University19Call Admission ControlCall Admission Control❑ Generic Call Admission Control (GCAC)❑ Run by a
View Full Document