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.