Low Overhead Path Computation Flooding

In (Perelló et al., 2010) a variation on the PCF is proposed, in the Low Overhead Path Computation Flooding (Lo-PCF) architecture a PCE from a given domain would only add the VSPT from one domain for each request Id. In order to accomplish this, upon receipt of a PRep message containing a VSPT the PCE checks if any other Prep from that request Id have already been processed, if so it discards the message. In case no reply message for that request Id have already been processed, the PCE updates the VSPT and forwards it in a message to all upstream domain PCEs. This scheme may lead to suboptimal resulting path compared to the PCF scheme, but it results in much lessen control messages exchanged. For this scheme to work properly request Ids must globally unique in the multi-domain network, but this scheme guarantees loop free path calculation without requiring a domain list as it is necessary in the PCF.

Perelló, J.; Hernández-Sola, G.; Agraz, F.; Spadaro, S. & Comellas, J. (2010), 'Scalable Path Computation Flooding Approach for PCE-Based Multi-domain Networks', ETRI journal 32(4).

Hybrid BRPC and H-PCE

In (Hernandez-Sola et al., 2010) a hybrid architecture between BRPC and H-PCE is proposed in order to increase the optimality of the resulting end-to-end path without increasing too much the number of control messages exchanged. “Additionally, a trade-off between shared routing information, scalability and security across domains is also obtained” (Hernandez-Sola et al., 2001). In the proposed architecture by default each child PCE executes the BRPC for path computation where the domain sequence is previously determined by a BGP protocol. In case the number of domains to be crossed (from a child source domain to the target domain) reaches a given threshold the child PCE delegates the path computation to the parent PCE. 

In the performance simulations presented in the paper the threshold value was fixed in 2 and 3 (referring to the number of domains to be crossed). The tests performed showed that the higher threshold value demand less interference of the parent PCE decreasing number of control messages, less computation burden to the parent PCE but in the other hand a subtle higher level of blocking probability.

Hernández-Sola, G.; Perelló, J.; Spadaro, S.; Moreno, A.; Agraz, F.; Comellas, J. & Junyent, G. (2010), Analysis of traffic engineering information dissemination strategies in PCE-based multi-domain optical networks, in 'Transparent Optical Networks (ICTON), 2010 12th International Conference on', pp. 1—4.

Hierarchical PCE architecture

In the Hierarchical PCE architecture child PCE's report to a parent PCE responsible to gather necessary information for an end-to-end LSP calculation not limited by a predetermined domain sequence. The parent PCE knows a topology map of the child domains and their respective child PCEs, the domains are seen as vertex and the links between border nodes at each domain (also known by the parent PCE) are the edges in such a topology. The parent PCE does not know the topology of each child domain (King & Farrel, 2009). Even though the end-to-end path resulting from this architecture reaches a higher level of optimality, it largely increases the number of control messages exchanged between PCEs and therefore problems of scalability may occur.

King, D. and Farrel, A. “The Application of the PCE Architecture to the Determination of a Sequence of Domains in MPLS &GMPLS,” IETF draft draft-king-pce-hierarchy-fwk-03.txt, Dec. 2009. http://tools.ietf.org/html/draft-king-pce-hierarchy-fwk-00

Path Computation Flooding

In a multi-domain network when a end-to-end path computation relies on a fixed, previously known domain sequence the resulting end-to-end path is considered to suboptimal in terms of resulting blocking probability (Hernández-Sola et al, 2010). To improve the optimality of the resulting path, the domain sequence should ideally be calculated on demand by one or more PCEs present in the network. However to achieve this optimality the number of overhead control messages is increased and therefore the burden of processing in the PCEs jeopardizes the scalability of the whole system, since the larger the multi-domain network the higher is the necessity of processing of control messages (Perelló et al., 2010). The control messages refer to both the constant update on link state (via OSPFs link sate advertisement) and the messages exchanged between different domains PCEs. 

Based on the BRPC, the Path Computation Flooding (PCF) is a different approach where a domain sequence is not previously stipluated. In this architecture, the destination domain PCE upon receipt of a PCReq from the source domain PCE calculates an egress VSPT and sends this as a message to all the PCE in adjacent domains and so on so forth till the PCE in the source domain receives a VSPT from all of his adjacent domain PCEs and selects the final optimum path (King & Farrel, 2009). The PCF generates too many control overhead messages and therefore presents serious scalability issues. 

Hernández-Sola, G.; Perelló, J.; Spadaro, S.; Moreno, A.; Agraz, F.; Comellas, J. & Junyent, G. (2010), Analysis of traffic engineering information dissemination strategies in PCE-based multi-domain optical networks, in 'Transparent Optical Networks (ICTON), 2010 12th International Conference on', pp. 1—4. 

King, D. and Farrel, A. “The Application of the PCE Architecture to the Determination of a Sequence of Domains in MPLS &GMPLS,” IETF draft draft-king-pce-hierarchy-fwk-03.txt, Dec. 2009. http://tools.ietf.org/html/draft-king-pce-hierarchy-fwk-00

Perelló, J.; Hernández-Sola, G.; Agraz, F.; Spadaro, S. & Comellas, J. (2010), 'Scalable Path Computation Flooding Approach for PCE-Based Multi-domain Networks', ETRI journal 32(4).

Back Recursive Path Computation

A multi-domain network presents a mayor obstacle to the effective computation of an end-to-end path that resides on the fact that a multi-domain network contains various independently managed system (autonomous system) that have confidential information on their own networks topology and state mainly due to security reasons. 

This information confidentiality prevents each single domain PCE to have full topology and Traffic Engineering information on the whole network which is necessary to compute an optimal or even feasible end-to-end path. 

In order to achieve a feasible end-to-end path computation it is possible to implement distributed or hierarchical architectures relying on the PCE. One possibility is to compute the path in a distributed way where each domain PCE computes the LSP for its own domain. In this architecture, usually, in domain sequence to be crossed is previously determined (normally via the BGP protocol). 

In a per domain path calculation, entry border nodes of each domain request its domain PCE for a LSP inside that domain, and therefore the resulting end-to-end path is a concatenation of those LSPs. In Back Recursive Path Computation (BRPC) PCEs present in each domain of the sequence collaborate to create a Virtual Shortest Path Tree. This VSPT comprises all possible end-to-end paths that cross the stipulated domain sequence. A request message is sent to the PCE in the destination domain and this one sends a VSPT to the PCE in his neighbor domain belonging to the sequence and so on so forth until the all the VSPT from all domains in the sequence reach the PCE in the source domain. Once the VSPT is informed to the source domain PCE, this selects the final path (Vasseur et al.,2009).

Vasseur, J.P. et al., “A Backward-Recursive PCE-Based Computation Procedure (BRPC) to Compute Shortest Constrained Inter-domain Traffic Engineering LSPs,” IETF RFC 5441, Apr. 2009.

Virtual Topology

"A virtual topology is a set of of all-optical connections or a group of light-paths that are established over the physical topology of a network in order to accommodate the traffic demand of network users." 1

The limitations of number of wavelengths available in each fiber link, and other network resource constraints, the virtual topology design becomes an important problem which objective is to maximize network performance by combining benefits of optical transmission and electronic processing of data.


Since traffic demand and network topology do no remain constant forever in a large transport network, reconfiguration of the physical topology is important to maintain the optimal network performance.


Network performance metrics can be: 

• number of hop between pair of nodes
• offered traffic on a light-path
• end-to-end delay from one node to another
• number of wavelength conversion required throughout a route

1 Zheng, J. & Moutfah, H.T. (2004) "Optical Networks. Concepts and Design Principles". Wiley-Interscience. NJ. pp 89-91

LSP setup delay

Label Switched Path (LSP) Dynamic Provisioning Performance Metrics in Generalized MPLS Networks RFC 5814

An LSP setup delay is an important metric to assess the quality of provisioning of a GMPLS control plane on a network. A longer LSP setup delay may incur in higher overhead for he requesting application and the impact is worsen the shorter the LSP lasting time is.

The delay itself consists of link propagation delay and nodal processing delay, and this metric may be used as testing and diagnostic of the control channel performance. The metrics unit used is either a real number of milliseconds or undefined. The setup delay metric is expressed in milliseconds.

RSVP-TE preemption policy

The different preemption priorities are defined in the RSVP-TE protocol (Awduche, 2001). A higher priority LSP may preempt a lower priority LSP that is then re-routed though a new path as if it was setup after the higher priority LSP.

The setup priority value determines the level of capability of that LSP to preempt another and a holding priority value determines the level of capability of a LSP to resit to a preemption. Both values range from 0 (highest priority) to 7 (lowest priority).


D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, and G. Swallow, “RSVP-TE: Extensions to RSVP for LSP tunnels,” RFC 3209, December 2001.

Types of connection in a ASON

From Hu, 2011

In a Automatic Switched Network 3 types of connections are possible, they vary in terms of the lasting time of the connection, and they are:

Permanent connection –usually a static connection that last for months or years. It is setup manually or by management system.

Switched connection: established on demand though routing and signaling capabilities of the control plane. Requires a user-network signaling interface. Are setup within seconds, enabling bandwidth on demand. Promotes optimization of resource utilization and traffic engineering mechanisms.

Soft permanent connection: two permanent connections are specified at the edge of the network, a switched connection is setup within the network. Soft permanent connections are triggered by management plane, but are setup within the network by the control plane. They may support TE, dynamic re-establishment of failed connections and time varying bandwidths.
Hu, W.; Sun, W.; Jin, Y.; Guo, W.; He, H. & Yi, L. (2011), 'Sub-Wavelength Switching for Future Internet'' 13th International Conference on Transparent Optical Networks (ICTON), 2011'

Issues in preemption policies

Even though preemption mechanisms may be used to reduce the total number of rejected tunnels in case of failure in a MPLS network, they can also have a negative impact on the convergence time of a network. N Chaieb et al., 2007, two approaches are proposed:

• Least preempted tunnels are prioritized for next preemption. 
• No tunnel can be preempted more than N times in a given interval of time. 

Chaieb et al., 2007c] Chaieb, I., Le Roux, J., et Cousin, B. A New Pre-emption Policy for MPLS-TE Networks. 15th IEEE International Conference on Networks (ICON) (2007c).

Preemption in MPLS network

In a MPLS network LSPs preemption is based on their set-up and holding priority values. According to (de Oliveira, 2004), this preemption strategy can lead to excessive re-routing decisions. A preemption optimization is based on three criteria:

•  Number of LPSs to be preempted 
•  Priority of the LPSs 
•  Preempted bandwidth 

In (de Oliveira, 2004), an adaptive scheme is proposed to select lower priority LSPs that can afford having their rate reduced.
Besides prioritizing access policies preemption can also be used for restoration policies in event of a network failure.
In order to establish, maintain and tear-down a LSP the Label Distribution Protocol (LDP) and the Resource Reservation Protocol (RSVP) are use (Awduche, 2002).

de Oliveira, J.; Scoglio, C.; Akyildiz, I. & Uhl, G. (2004), 'New preemption policies for DiffServ-aware traffic engineering to minimize rerouting in MPLS networks', IEEE/ACM Transactions on Networking (TON) 12(4), 733—745.

D. O. Awduche and B. Jabbari, “Internet traffic engineering using multiprotocol label switching (MPLS),” Comput. Netw., vol. 40, pp. 111–129, 2002.

Traffic Engineering Database

As defined in (Katz et al., 2003), the Traffic Engineering Database (TED) was developed from a proposal of adding more link attributes in the Opens Shortest Path First (OSPF) advertisements. The Traffic Engineering Database is in fact an extended Link Attributes Database that are built by exchange of Link State Advertising messages between routers. Some of the uses of the TED are Monitoring the extended link attributes, local constraint-based routing and global traffic engineering.

ICTON 2011 3RD DAY - Random notes

SESSION We.B3 GOC III

Power Consumption analysis of opaque and transparent optical core network  
A, Autehrieth, A.K. Tilwankar, C. Mas Machuca, J-P. Elbers

Transparent Optical Networks are increasingly more economical over 20Tbps traffic volume. Under that volume opaque network is more economical due to grooming.
The cross point is at an average demand value of 16-30 Gbps in the considered network.


Cross-layer Re-configurable optical network: Fast failure recovery in test-bed for routing algorithm
C. Ware, C.P. Lai, D. Brunina, W. Zhang, A.S. Garg, B. G. Bathula, K. Bergman

Lambda stripping: WDM payload +header wabelengths.
A failuer would trigger the switcher to an alternate port.



The impact of optical networks considering physical impairments, CAPEX and energy consumption
K. Georgakilas, A. Tzanakazi

Wavelength sharing for bkp path with common links assuming the respective primary paths are disjoint.


SESSION We.C3 WAOR III

Dynamic impairment- aware optical networking: Some experimental results of the EU DICONET project
S. Spadaro, J. Perelló, F. Agraz, M. Angelou, S. Azodolmolky, Y. Qin, R. Nejabati, D. Simeonidou, I. Tomkos

A Q-factor is estimated by a Q-tool. A PPD has info on physical impairment on the network
The established connection executed by the RSVP collects information on the physical impairments on the links on the calculated path and this info is to be used by the Q-tool.
It is and enhanced PCE      E-PCE = PCE + NPOT
Centralized light-path establishment.


Off-line algorithms for routing, modulation level and spectrum assignment in elastic optical networks
M. Klinkowski, K. Wakowiak, M. Jaworski

Elastic Optical Networks (EON)
Off-line algorithm. for routing, modulation level and spectrum assignment - RMLSA
Flexible operation: provision of just the resource requirements of a resource
Frequency slots (Jinno et al 2010)
RMLSA problem (Chistodoupoulos et. al 2011)
In a RWA algorithm a whole wavelength is assigned. In a RMSLA problem contiguous slots are assigned.


Experimental implementation of efficient multicast processes: towards carrier Ethernet networks and all-optical multicast
A. Valentí, N. Avallone, A. Pompei, F. Matera, G. Tosi Beleffi

Carrier Ethernet ad all optical multicast
MPLS-TP (transport profile)
Provider backbone bridges
E-Line, E-LAN, and E-tree services
layer 2 multicast by carrier Ethernet network
E-LAN service for multicast traffic live IPTV

Employing Ethernet spanning tree protocols in an integrated hybrid optical network
R. Veisllari, S. Bjørnstad

Hybrid optical network: employs circuit switched path and packet switched path


Optical Labeling through parametric amplification
M.L.F. Abbade, A.L.A. Costa, J.D. Marconi, V.V. Cardoso, H.L. Fragnito, E. Moschim

New optical labeling technology
Label is inserted all optically
Label and payload are emitted a part, in the same BW and different time (strategy for transmission of payload and label)

ICTON 2011 2ND DAY - Random notes

SESSION TuC3 RONEXT III

Survivable Impairment Aware Traffic-grooming and re-generator placement with shared connection-level protection
C. Gao, H.C. Cankaya, A.N. Patel, J.P. Jue, X. Wang, Q. Zhang, P. Palacharla, M. Sekiya

Protection in the connection level x in the light-path level.
Electric backplane: grooming card, line card. Client card.
Transponders (10, 40, 100 Gbps) The cost increases less than the capacity in Gbps.
Reduced signalling, control traffic reduction for hybrid approach of light-path and connection level restoration.

When grooming there is also regeneration since the signal must pass through electronic processing.


Survivable cross-layer virtual topology design using a hyper-heuristic approach
F. Corut Ergin, A Yayimli, A Sima Uyar

An heuristic over a lower level heuristic is used to select which low level heuristic is better to be used.
Ant colony to find a survivable light-path topology.


Cost dependency on protection of optical access networks for dense urban areas
C. Mas Machuca, J. Chen, L. Wosinska

FTTH - PON
Protection in access networks can be highly costly.
Protection until remote node x protection until the user.
cost by deciding previous protection or late reaction.

ICTON 2011 1ST DAY - Random notes

Plenary Speakers

Professor Biswanath Mukherjee
University of California, Davis


Title
Some "Opaque" Problems in Transparent Optical Networks


Trends: Mixed line rates: 20, 40, 100 Gbps wavelengths. (needed for hierarchical grooming)
Elastic Rate networks.
Traffic Engineering: put the traffic where the bandwidth is.
Network engineering: put the bandwidth where the traffic is.
Network planning: put the bandwidth where the traffic is fore-casted to be.


Professor Keren Bergman
Columbia University


Title
Nanophotonic Interconnection Networks for Performance-Energy Optimized Computing


Eletronic x Photonic
Eletronic: Buffer, receive, retransmit at every router
Photonic: larger BW of data. Data is streamed once per communication event.

SESSION Mo.B3

A squatting based framework to enhance network virtualization allocation in optical networks (Invited)
X. Hesselbach, N. Naumenko


Physical resource, virtual resource, logical resource.
Using virtualization helps, for instance the slow implementation of Ipv6 while Ipv4 is still in use. Virtualization helps avoiding the ossification of the Internet.
Classes relate to the amount of capacity or granularity of capacities for instance: lambdas, OBS, fibers, 100Gbps, !0Gbps etc. The demand is per type of service not per resource (BW).
With virtualization resource that is being used in one service can be used in another service.


A GRASP-based heuristic to design the GMPLS control plane network topology with resilience guarantees (Invited)
M. Ruiz, L. Velasco, G. Junyent, J. Comellas


A drawback of a minimal topology is the amount of control information per link is higher. (specially in the case of failure)

Multi layer path computation with PCE part II

From RFC5623

The calculated path is informed to the invoking LSR as a Explicit Route Object and is used for signaling by the RSVP-TE in a MPLS or GMPLS control plane. Two types of computed path may be possible: 

Otpion 1: Mono-Layer Path: 

• Case 1: the lower layer path included in the end-to-end computed path is already established or will be established on demand. This path specified by a ERO contains TE-links may be a regular TE link that is already established or a virtual TE-link that still needs to be established (RFC5212). In the case of a virtual TE link that must be established a setup attempt for a new lower-layer LSP is initiated once the signaling reaches the head-end of the lower-layer LSP. Since the path of a virtual TE-link is not necessarily know in advance a further lower-layer path computation may be needed. 
•  Case 2: the path computed by the PCE contains a loose hop that spans the lower-layer network, it selects which lower-layer to use but does not selects the path across it. A transit Label Switched Router that is the entry for the lower-layer network is responsible for expanding the loose hop in tis own network. The path expansion on the border LSR may rely on the selection of a existing lower-layer LSP or in the computation and set-up of a new one. 

Option 2: Multi-Layer Path:
The path computed by the PCE is a multi-layer path, it contains TE links from diverse layers (RFC4206). This multi-layer path can contain an already established complete path from the lower layer or if the lower layer path is not already established the signaling of the higher layer LSP triggers the establishment of the lower-layer LSP.

Takeda, T.; Oki, E.; Marzin, A.; Farrel, A. & Roux, J. (2009), 'Framework for PCE-Based Inter-Layer MPLS and GMPLS Traffic Engineering', Framework .

Multi layer path computation with PCE

In a distribute multi-layer path computation a Label Switched Router (LSR) in a higher may not have information on the topology or network state of a lower layer and hence may not be able to compute an end-to-end path.
In a centralized multi-layer path computation there are two alternatives for a successful end-to-end path computation:
1- Single PCE path computation: the PCE has topology and network state information about multiple layers in a network and can directly compute a required end-to-end path.
2- Multiple PCE path computation:
 a- with inter PCE communication: PCEs collaborate and each PCE is responsible for the path computation on its own layer.
 b- without inter PCE communication: each PCE computes PCE for its own layer after the request of its layer ingress LSR.

Takeda, T.; Oki, E.; Marzin, A.; Farrel, A. & Roux, J. (2009), 'Framework for PCE-Based Inter-Layer MPLS and GMPLS Traffic Engineering', Framework .

Algorithms for dynamic wavelength assignment

“For the dynamic problem, instead of attempting to minimize the number of wavelengths as in the static case, we assume that the number of wavelengths is fixed (this is the practical situation), and we attempt to minimize connection blocking.”

Random Wavelength Assignment (R). First, all wavelengths are analyzed for availability in the total route. Among the available wavelength on the required route, one is assigned randomly.

First-Fit (FF). All wavelengths are numbered, a lower number wavelength is analyzed for availability in the given route. Smaller computation cost than the previous model. No global knowledge is required.

Least-Used (LU)/SPREAD. The wavelength that is the least used in the network is selected. The aim is to balance the load among wavelengths. Global information and therefore this model results in additional storage, communication overhead and computation cost.

Most-Used (MU)/PACK. The wavelength that is the most used in the network is selected. Similar storage, communication overhead and computation cost as LU. Outperforms FF and LU as optimized the use of wavelengths.

Min-Product (MP). Is used in multi-fiber networks. The goal of MP is to pack wavelengths into fibers, thereby minimizing the number of fibers in the network.

Least-Loaded (LL). Is used in multi-fiber networks. Select the wavelength with the largest residual capacity in the most-loaded link along route p. Outperforms MU and FF in terms of blocking probability.

By taking the network state into consideration, maxsum(MS) and relative capacity loss (RCL) try to establish the new call on a wavelength which has the least influence on the whole network. Although RCL is better in performance the knowledge of the updated topology makes it expensive and complex to implement.

MAX-SUM (MΣ). May be used in multi or single fiber networks. It assumes all connection requests are known in advance and route for each connection is pre-selected (global information: traffic matrix and the network state and topology are required). A wavelength is selected in the most congested link

Before lightpath establishment, the route is pre-selected; After lightpath establishment, it attemps to maximize the remaining path capacity.From all the possible paths MΣ considers all possible paths (lightpaths with their preselected routes) in the network and attempts to maximize the remaining path capacities after lightpath establishment.

Relative Capacity Loss (RCL). RCL calculates the Relative Capacity Loss for each path on each available wavelength and thcn chooses the wavelength that minimizes the sum of the relative capacity loss on all the paths. Similar to MΣ. can also be viewed as an approach that chooses the wavelength j that minimizes the capacity loss on all lightpaths.

Considering that longer light-paths have a higher probability of getting blocked than shorter paths, the wavelength reservation (Rsv) and protecting threshold (Thr) schemes attempt to protect longer paths. They can not work alone and must be combined with other wavelength-assignment schemes.

Wavelength Reservation (Rsv). A wavelength on a specified link is reserved for a traffic stream between 2 nodes, usually a multi-hop stream. Another connection request for that link cannot be assigned to the reserved wavelength even if it is idle. Reduces the blocking for multi-hop traffic, while increasing the blocking for single-hop traffic.

Protecting Threshold (Thr). A wavelength is assigned to a single-hop connection only if the number of idle wavelengths on the link is at or above a given threshold. One issue when applying these heuristics to the static problem is how to order the light-paths when assigning wavelengths.

References:

Zang, H.; Jue, J. & Mukherjee, B. (2000), 'A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks', Optical Networks Magazine 1(1), 47—60.

R. A. Barry and S. Subramaniam, “The MAX-SUM wavelength assignment algorithm for WDM ring networks,” in Digest of Optical Fiber Communications Conference, Vol. 6 of 1997 Technical Digest Series (Optical Society of America, 1997), pp. 121–122.

X. Zhang and C. Qiao, “Wavelength assignment for dynamic traffic in multi-fiber WDM networks,” in Proceedings of the Seventh International Conference on Computer Communications and Networks, Vol. 1 (IEEE, 1998), pp. 479–485.

Protocol stack for IP over SDH

The IP over SDH architecture relies on th use of Point-to-Point Protocol (PPP) and High-level Data Link Control (HLDC) protocols. 

PPP provides multi-protocol encapsulation, error control and link initialization Control (RFC2615). The HDLC (RFC1662) delineates the PPP encapsulated IP packet so that inside the synchronous container it is possible to know where each IP packet starts and ends by the use of an specific byte that works as a flag. The delineation is accomplished using a technique called byte stuffing. The HDLC flag pattern is also transmitted during idle periods where no IP packet is transmitted as inter frame fill.

In the SDH architecture the frames must be scrambled before transmission to assure an adequate number transitions (byte variation) that permits synchronization between clocks.

The HDLC protocol does not permit efficient scalability for bandwidth beyond OC-48 (2.4Gbps), because every outgoing byte must be monitored so that stuffing can be done to prevent flag emulation. The bytes equally must be monitored and de-stuffing must be performed at receiver.

An alternative to the PPP/HDLC model is the use of the Simplified Data Link. (RFC2823) SDL permits high speed packet delineation for variable length datagrams with asynchronous arrival schedule. It relies on the use of a Cyclic Redundancy Check byte in the header of the datagram for payload length indication and another separate CRC in the payload of the IP datagram for its protection. In order to fill in the idle periods where IP packets are not transmitted SDL are transmitted containing a default value for payload length indicator. At receiver when the default values CRC is detected the SDL frame is discarded. In the SDL model the CRC is verified and in case an error is detected the receiver will enter a hunt state until a CRC is correctly verified.

Manchester, J.; Anderson, J.; Doshi, B. & Dravida, S. (1998), 'IP over Sonet', Communications Magazine, IEEE 36(5), 136--142

Resilient Packet Ring traffic classes

A Resilient Packet Ring is a ring-based network protocol standardized by IEEE 802.1. It is adequate to be used by service providers in MANs or WANs.

In a Resilient Packet Ring topology the access to the medium method applied is the buffer insertion ring. Every station on the ring has a buffer that is called a transit queue, frames passing by the station that are not destined to it may be temporarily stored in this buffer. A station may only start sending a frame if the transit queue is empty and there is no transit frame. If a transit frame arrives at a station while the station is already transmitting a frame the transit frame must wait in queue till the other frame is completely transmitted.

A spatial re-use occurs when a frame is removed from the ring by the receiver RPR station and the path's bandwidth that leads back to the source is available to be used by another sender.

A a resilient packet ring network work based on a three-level class priority scheme. The aim is to treat traffic with different requirements and priorities accordingly.

Class A is a low-latency low-jitter class, class B has predictable latency and jitter, and class C is treated as best effort data delivery. No frame is are discarded in case of congestion, every frame will eventually reach its destination. be a best effort transport class.

Class A traffic is subdivided into classes A0 and A1 and class B is divided into BCIR (committed information rate) and B-EIR (excess-Information rate)

Service to class A0, A1, and B-CIR traffic have their required bandwidth preallocated. For class A0 the preallocated BW is reserved and can only be used by the station that reserved it. If it is not used it is wasted. BW for A1 and B-CIR is reclaimable and if not used may be used by best effort traffic (classes B-EIR and C). 

Davik, F.; Yilmaz, M.; Gjessing, S. & Uzun, N. (2004), 'IEEE 802.17 resilient packet ring tutorial', Communications Magazine, IEEE 42(3), 112—118.

Tsang, D., 'Resilient Packet Ring', Lecture 8 Dr. Danny Tsang Department of Electrical & Electronic Engineering Hong Kong University of Science and Technology.

S. Spadaro, J. Sole-Pareta, D. Careglio, K. Wajda, A. Szymanski,“Positioning of the RPR standard in contemporary operator environments,”Network, IEEE Volume 18, Issue 2, Mar-Apr 2004 Page(s):35 –40

Data Plane and Control Plane

Extracted from : RFC 5212

"A data plane layer is a collection of network resources capable of terminating and/or switching data traffic of a particular format [RFC4397]. These resources can be used for establishing LSPs for traffic delivery. For example, VC-11 and VC4-64c represent two different layers. 

From the control plane viewpoint, an LSP region is defined as a set of one or more data plane layers that share the same type of switching technology, that is, the same switching type. For example, VC-11, VC-4, and VC-4-7v layers are part of the same TDM region. The regions that are currently defined are: PSC, L2SC, TDM, LSC, and FSC.

Hence, an LSP region is a technology domain (identified by the ISC type) for which data plane resources (i.e., data links) are represented into the control plane as an aggregate of TE information associated with a set of links (i.e., TE links). For example, VC-11 and VC4-64c capable TE links are part of the same TDM region.

Multiple layers can thus exist in a single region network. Note also that the region may produce a distinction within the control plane. Layers of the same region share the same switching technology and, therefore, use the same set of technology-specific signaling objects and technology-specific value setting of TE link attributes within the control plane, but layers from different regions may use different technology-specific objects and TE attribute values.

This means that it may not be possible to simply forward the signaling message between LSRs that host different switching technologies. This is due to changes in some of the signaling objects (for example, the traffic parameters) when crossing a region boundary even if a single control plane instance is used to manage the whole MRN (Multi Region Network)."

Shiomoto, K.; Papadimitriou, D.; Le Roux, J. & Vigoureux, M. (2008), 'D. Brungard," Requirements for GMPLS-Based Multi-Region and Multi-Layer Networks (MRN/MLN)', Technical report, RFC 5212, July 2008.

Signalling and Routing Protocols

A signaling protocol performs some crucial functions when a light-path is to be set up, it performs information exchange between nodes, distribute labels, and reserve resource along the path that is to set up. In a GMPLS network the signaling protocols used are RSVP-TE and CR-LDP that may carry within their messages any object specified by the GMPLS architecture. The signaling protocols are responsible for setting up, modifying or tearing down a G-LSP. 

An end-to-end path in a optical network have some specific requirements for the signaling function: as small set up latency (due to restoration purposes), support for bidirectional paths, rapid failure detection and notification, and fast and intelligent restoration. 

In the RSVP protocol, signaling happens between source and destination nodes, a signaling message may contain information about QoS requirements and label requests for intermediate nodes. In the CR-LDP protocol signaling occurs in a hop-by-hop basis and indicates the route and its required parameters, in each node the required resource is reserved, a label is assigned and a forwarding table is set. 

The routing protocol OSPF-TE is used by routing nodes to exchange Link State Advertisement (LSA) messages. The links state messages contain the active channels, the allocated channels, the channels that are reserved for restoration (back-up channels). Allocated channels also have holding and set-up priority parameters that are used to determine is a path set-up may preempt another already established path. The extensions to OSPF enables to inform the type of LSP that can be established in a link, the current unused bandwidth, the maximum size of G-LSP and the administrative groups supported.

Palmieri, F. (2008) “GMPLS Control Plane Services in the Next-Generation Optical Internet”, The Internet Protocol Journal, Vol.11, Number 3, September 2008.

Traffic Engineering in Optical Networks

The article by Palmieri, 2008 provides a very straightforward explanation of traffic-engineering:

Traffic-engineering functions as an assistant to routing and switching infrastructures. The use of TE aims on balancing the usage of a network and avoid congestion resultant from uneven traffic distribution.

Currently, dynamic routing is protocols rely on shortest paths to forward traffic. This practice while conserving network resource also causes some resources to be over used and others are under used. Also, traditional routing protocols do not consider specific requirements of some traffic flow as QoS and bandwidth.

A traffic-engineering application must provide control over the placement of traffic flows in a network domain promoting a better usage and a manageable network. A traffic-engineering application adequate for a Optical network present the following basic functions:

-Traffic monitoring, analysis and aggregation. Collects traffic statistics and aggregate or analyze them for later use.

-Bandwidth demand projection. Used for sub-sequent allocation, the projection estimates the bandwidth requirements for the near future based on statistics.

-Reconfiguration trigger. Set of policies that decide when a network needs to be reconfigure. The decision is based on operational areas, traffic measurements and bandwidth predictions.

-Topology design. Based on traffic measurements and predictions, it aims on optimizing a graph for specific objectives.

-Topology mitigation. Algorithms used to coordinate the migration to a new topology.

Palmieri, F. (2008) “GMPLS Control Plane Services in the Next-Generation Optical Internet”, The Internet Protocol Journal, Vol.11, Number 3, September 2008.

Interface Switching Capability

The GMPLS control manager architecture presents the Interface Switching Capability (ISC) concept (RFC4202). A switching type related to a ISC describes the ability of a node to forward data of an specific type of data plane technology and identifies a network region. The ISC types and regions are: PSC (Packet Switching Capable) , L2SC (Layer 2 Switching Capable), TDM (Time Division Multiplexing) capable, LSC (Lambda Switching Capable), and FSC (Fiber switching Capable).

An end of a data link is an interface that connects a data link to a node. In a GMPLS network each end of a data-link is associated with an ISC. An Interface Switching Capability Descriptor (ISCD) attribute advertises the ISC value of TE-link end (RFC4202). The ISCD also contains information on encoding type, bandwidth granularity and unreserved bandwidth of each of the LSP's 8 priorities types. One TE-link advertisement may contain more than one ISCDs, as some TE-links are multi switching capable and are therfore present in more than one layer. 

A single-switching-type-capable node advertises the same ISC in their ISCD as the termination capability of each of its interfaces (RFC4202). Multi-switching-type-capable LSRs (Label Switched Routers) can be “Simplex” or “Hybrid”.

A “Simplex” node would have separate interfaces for each switching capability connection. Therefore, it will advertise several TE-links each of which with one ISCD containing a single ISC value (RFC4206).

A “Hybrid” node offers the same interface for the different switching capabilities connections. Therefore it advertises only one TE-link with one ISCD containing several ISC values. In this case the node would interconnect external data-links via internal connections. 

Figure 1 shows an example of an hybrid node: it has two switching elements supporting each one a different switching capability as for instance PCS and TDMC in link 1 and link 2 respectively. The two switching elements are internally interconnected so that via communication with interface b its possible to provide adjustments for PSC traffic.

Shiomoto, et al. (2008), "Requirements for GMPLS-Based Multi-Region and Multi-Layer Networks (MRN/MLN)", Technical report, RFC 5212, June 2008.

Performance Evaluation of Resource Allocation models MPLS

In the RFC4128 (Lai, 2005) a performance evaluation presents the benefits and the trade-offs between the Russian Dolls and the Maximum allocation models. The study aimed on the comparison and the trade-off between a better efficiency under ordinary via bandwidth sharing AND a class robust/protection under overload conditions. Results showed that the Russian Dolls model allowed greater sharing of bandwidth among different classes performing better under normal conditions. On the other hand the Maximum Allocation Model does not depend on preemption and provides a more robust class isolation under overload conditions. The use of preemption gives higher-priority traffic some level of immunity to the overloading of other classes, which resulted in higher blocking/preemption for the overloaded class than in a pure blocking environment (Din, et al. 2008).

Din, N.; Hakimie, H. & Fisal, N. (2008), 'Bandwidth sharing scheme in DiffServ-aware MPLS networks ''Telecommunications and Malaysia International Conference on Communications, 2007. ICT-MICC 2007. IEEE International Conference on', IEEE, 782?787.

Lai, W. (2005), 'Bandwidth Constraints Models for Differentiated Services (Diffserv)-aware MPLS Traffic Engineering: Performance Evaluation', RFC 4128, June 2005.

Bandwidth constraints models for DS-TE MPLS networks

The implementation of DiffServ mechanisms in a MPLS network is designed by the DS-TE architecture, where Class-types and TE-classes are identified.

A Class-Type (CT) is used for link bandwidth allocation determination, constraint-based routing and admission control. One traffic trunk belongs to the same CT throughout the links it crosses. A CT comprises a given number of traffic trunks on a link that governed by the same set of bandwidth constraints.

A TE-Class is comprised by a Class-Type and a preemption priority defined for that class-type. Therefore an LSP transporting a given traffic trunk would use the associated preemption priority as a set-up priority, a holding priority or both.

One of the fundamental requirements that support the implementation of DiffServ aware MPLS in network is the possibility to enforce different bandwidth constraints for each class of traffic.

The three possible bandwidth constraints models for DS-TE are Maximum Allocation Model (MAM), Maximum Allocation with Reservation (MAR) and the Russian Dolls Model.

In the MAM model each traffic class has a given bandwidth constraint and a maximum bandwidth reservation value is associated to the link capacity. The sum of all bandwidths constraints can exceed the maximum reserved bandwidth, and therefore the higher priority traffic can preempt the lower priority traffic to get its allocated bandwidth [1].

The MAR model is similar to the MAM model in the sense that a maximum bandwidth allocation is determined to each Class-type, but in this model, each class-type may only exceed its bandwidth allocation under conditions of no congestion if the network is overloaded the that traffic class-type bandwidth allocation is fixed to its current allocation [1].

In the Russian Dolls Model the maximum bandwidth usage allowed in a link is achieved by the accumulation of successive class-type according to their priority class. A lower priority traffic may use a higher priority class' bandwidth reservation up to the sum of their bandwidth constraint values, while a higher priority traffic can preempt a lower priority traffic to use its full allocated bandwidth [1].

[1] Din, N.; Hakimie, H. & Fisal, N. (2008), 'Bandwidth sharing scheme in DiffServ-aware MPLS networks''Telecommunications and Malaysia International Conference on Communications, 2007. ICT-MICC 2007. IEEE International Conference on', IEEE, 782--787.

Heterogeneous networks: types of layers definitions

An heterogeneous network comprises multiple layers that may represent different technologies, data plane switching granularity levels, or distinct network roles.
The different technologies refer to data flow treatment and organization. For instance it could be based on Packet Switching capable nodes, Time Division Multiplexing (eg. SDH) or Lambda Switching capable (RFC3945).
In the same control plane of switching capability the data plane granularity levels may vary according to the bandwidth capability. (eg. VC4, VC12 Virtual Containers in SDH). (RFC5212).
The distinction can also refer to client and server roles in the network, where the server is the provider of the carrier network for long distance low level connection (backbone) providing service for the transmission of many data flows of smaller bandwidth granularity.

Integer Linear Programming with binary value variables

Integer Linear Programs are very useful on networking optimization problems. In some of this problems the integers variables are restricted to values {1,0}.

Some of the traditional problems in this variant are:

1. Grouping problem

2. Fixed Charge problem

Yi = 1 if location i is chosen,

Xij = quantity transported from i to j,

Fi = cost to establish factory i,

Cij = cost to transport from factory i to client j,

p = is limit of number of factorys established,

Uij = limit of quantity transported from i to j,

Ai = capacity to be transported in factory i,

Dj = demand of client j,

minimize: Z = ∑Fi.Yi + ∑Xij.Cij,

subject to: ∑Yi ≤ p,

Xij ≤ Uij,

∑Xij ≤ Ai.Yi ∀ i ∈ Z,

∑Xij ≥ Dj ∀ i ∈ Z

Xij ≥ 0 , Yi = {1,0}

3. Travel Salesman problem

4. Jobshop scheduling problem

Contains "either/or" constraints where a variable M which should approximate ∞ is added in order to make a constraint always true or always false in its inequalities.

From this video

another interesting studying aid:

Hillier, F.; Lieberman, G. & Liberman, G. (1990), Introduction to operations research, McGraw-Hill New York.

Multi layer path computation

When a end-to-end path computation crosses diverse layers it is called inter-layer path computation. The RFC 4206 defines how a higher-layer LSP that has explicit route object traversing lower-layer LSPs should be signaled. However, it might happen that a higher-layer Label Switched Router does not have topology visibility of the lower layer. A higher-layer / Lower-layer situation can be exemplified by a IP packet-based GMPLS over a GMPLS Optical network (could be a WDM Network).

This problem can be dodge by the implementation of either a single PCE model or a multiple PCE model (refer to the figure at the bottom of the post). In the single PCE model, the PCE unity has visibility in all the layers, and performs solely the end-to-end path computation. In the multiple PCE model, each PCE object has visibility restricted to its own layer, and therefore its Traffic Engineering Database is reduced. In this model PCEs from the different layers must communicate between each other and collaborate in the end-to-end path computation.

Picture extracted from Oki et al., 2008

Oki, E.; Inoue, I. & Shiomoto, K. (2008), 'Path computation element (PCE)-based traffic engineering in MPLS and GMPLS networks''Sarnoff Symposium, 2007 IEEE', IEEE, 1--5.

Integer Linear Programs

Integer Linear programming problems are problems where the variable restriction is not solely to be greater or equal to zero, but also to belong to the integer realm of numbers Z, and not to the real realm, R. Therefore the solution for IP are not contiguous points.

These problems are not as easy to solve as it may seem, as rounding off the result of a linear programing problem brings three issues:

- Rounding results is an exponential function and therefore is hard and time consuming (2ⁿ).

- The best feasible solution achieved by the rounding may not be optimal.

- There can be a case where all the optimal solutions are unfeasible.

However, if when solving an Linear programming problem, the solution is an Integer, than this solution is also optimum for the Integer Linear programming version of the same problem. Unfortunately, this may not happen often enough.

One approach is to elaborate more and more constraints so that the feasible region is being reduced to only integers corner points.

From this video

another interesting studying aid:
Hillier, F.; Lieberman, G. & Liberman, G. (1990), Introduction to operations research, McGraw-Hill New York.

layer stack IP over SDH

The optical fiber as medium for data transmission has enabled the possibility of a very elevated data rate up to 10 or 40Gbps per fiber. However the stack of protocols architecture throughout the OSI layers prevents the full use of the bandwidth in practice.

The different protocols in the stack are necessary to provide required functionalities related to the control plane, protection/restoration, packet delineation and synchronization.

Originally between the IP layer and the SDH layer there was an ATM layer that would provide most of those functions but presented two main drawbacks: 25% overhead per frame and the assembling and disassembling function requires processing resource limiting the actual bandwidth to 642Mbps.

The alternative and adopted possibility was to use IP layer directly over SDH. However with this new technology basic and required functionalities of the layer 2 were lost. The use of the PPP (point-to-point Protocol) and the HDLC (RFC 1662) were required for packet delineation and synchronization. In this architecture the packet delineation is performed by the use of flags, in order to protect the flag byte in SDH virtual container, byte stuffing is performed. The resource required to process byte stuffing limits the real bandwidth to up to 2.4 Gbps.

The current alternative is to migrate to WDM where the multiplexing is done in the wavelength sphere and not time based as it is in the SDH. To prevent the need for byte stuffing the adoption of Generic Framing Procedure (GFP), which can be easily implemented in an heterogeneous network.

Linear Programming applied on Transportation problem

Transportation Problems can be unbalanced:
     capacities≠requirements
     and the constraints functions are inequalities.

Transportation Problems can be balanced:
     capacities=requirements
     and the constraints functions are equalities.

Balanced Problems can be solved by the following algorithms

     First identify basic feasible solutions using:

• North West Rule
• Minimum Cost method
• Penalty Cost (Vogel's approximation)

    Then identify optimal solution, using:

• Stepping Stone
• MODI or UV (Modified distribution)

Minimize        ΣΣ c_ij x_ij

Subject to:     Σx_ij = Σa_i

                      Σx_ij = Σb_j

                      Σa_i=Σb_j

Where:           x_ij = amount transport from I to j

                      c_ij = cost of transport from I to j

from this class

RSVP - TE

The RSVP - TE protocol described in the RFC3209 is a extended version of the RSVP protocol to better serve LSP tunnels requirements.

A request to bind a label to a LSP tunnel is emitted by an ingress node (upstream router at the border of the MPLS network). Therefore the RSVP path message is expand with the addition of the LABEL_REQUEST object.

Labels are allocated downstream and distributed upstream via the RSVP Resv message which is, for this purpose, extended with  LABEL object.

The EXPLICIT_ROUTE object is also implemented in Path messages of the RSVP extended version. This object enables the pre definition of specific hops that must be comprised in the LSP. The explicit route can be determined manually by the network administrator, or automatically by an entity responsible for managing QoS requirements and policies where the current state of the network is taken into account.

One of the possible uses of the EXPLICIT_ROUTE object is to implement Traffic Engineering techniques. Through the selection of explicit routes the utilization of a network resources can be optimized.

The use of RSVP in establishing LSP tunnels is the possibility of the reservation of resources throughout the path. This reservation, though is not mandatory, an LSP can be assigned without the reservation of the resources, which can be used to transport best effort traffic for instance.

traffic Engineering capabilities require that a established TE tunnel may be re-routed. The circumstances in which this re-routing takes place are determined according to network policies and may be necessary when:

• A more optimal route becomes available.
• Failure of a resource along the determined path. 
• Return the TE tunnel to original route when the necessary resource becomes available again.

RSVP

The RSVP protocol is the protocol adopted in the GMPLS architecture for reserving and signaling a path in a switched based network. The RFC2205 from 19971 specifies the original regular version of this protocol before later amendments required to better serve the GMPLS architecture which culminated in the RSVP-TE, the following text refers to the above mentioned document. 

The RSVP is a reservation setup protocol. A host (receiver) uses the RSVP to request specific qualities of service for a data flow. RSVP reserves resources on each node along a selected path. It requests resources in only one direction and upstream. After a route is determined by a routing protocol the RSVP accesses the local routing database in order to obtain information on the routes, and therefore to which nodes messages will be sent.

Traffic control state and RSVP state are assumed to be dynamic, therefore RSVP establishes a soft state, it sends periodic refreshing messages tom maintain the
state along the reserved path. If refresh messages are not received the state will eventually time out and be teared down.

The Quality of Service for a data flow is implemented by mechanisms called Traffic control: packet classifier, admission control, packet scheduler.

In summary, RSVP has the following attributes:

• RSVP makes resource reservations for both unicast and many-to- many multicast applications, adapting dynamically to changing group membership as well as to changing routes. o RSVP is simplex, i.e., it makes reservations for unidirectional data flows. 
• RSVP is receiver-oriented, i.e., the receiver of a data flow initiates and maintains the resource reservation used for that flow. 
• RSVP maintains "soft" state in routers and hosts, providing graceful support for dynamic membership changes and automatic adaptation to routing changes. 
• RSVP is not a routing protocol but depends upon present and future routing protocols. 
• RSVP transports and maintains traffic control and policy control parameters that are opaque to RSVP. 
• RSVP provides several reservation models or "styles" (defined below) to fit a variety of applications. 
• RSVP provides transparent operation through routers that do not support it. 
• RSVP supports both IPv4 and IPv6.

¹ Braden, R.; Zhang, L.; Berson, S.; Herzog, S. & Jamin, S. (1997), 'RFC2205: Resource ReSerVation Protocol (RSVP)-Version 1 Functional Specification', IETF, September.