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.

RWA problem in wavelength routed WDM networks

On the introductory part of the article by Varvarigos, &
Christodoulopoulos, (2011)*, they offer a very clear and straight
forward explanation on the light-path assignment problem on a
wavelength routed WDM network where they explain that that type of
routing method is the most common in a optical transport network.

In such a network data is transmitted via optical channels that may use
multiple consecutive fibers. The data will follow a light-path. The
establishment of a light-path is based on the assignment of a route
(sequence of links) and a wavelength that is free on all the links that
comprise that path. The establishment of networks path usually must
optimize one of more performance metrics. This problem is then known as the Routing and Wavelength Assignment problem (RWA).

The generic constraints of this problem are:

1. Paths that share the same link (s) cannot be assigned to the same wavelength.
2. In case there is no wavelength converter in a light-path, this light-path data flow must be transfered using the same wavelength throughout the links it passes by.

There are two traffic models where the RWA problem takes place:

1. Off-line or Static RWA: happens during the planning phase of the WDM network, when it is configure based on the predicted traffic it will handle. The set of connection is known in advance.
2. On-line or Dynamic RWA: happens during the operational phase, as light-paths requests arrive and are established one-by-one upon arrival, restrained to the current network utilization state (the light-paths that have been already set-up)

*Varvarigos, E. A. & Christodoulopoulos, K. (2011), 'Algorithmic  Aspects of Optical Network Design'' 15th Conference on Optical Networks Design and Modeling (ONDM), 2011 Bologna Italy.

OFDM

On a WDM (Wavelength Division Multiplex) network the flows are assigned to paths which are in turn assigned to wavelengths in this case known as light-paths. However, on this model, the full wavelength capacity is assigned to one end-node pair even if the traffic between the pair does not require the wavelength transmission capacity, therefore part of the bandwidth is wasted with no traffic. (ref)

Orthogonal Frequency Division Multiplexing (OFDM)  is one of the possible methods for signal multiplexing. The multiplexing is done based on the division of a signal into several different channels each of those operating in a different frequency. The multiple channels can operate within close frequency levels without suffering interference as cross-talk. (ref)

In Optical networks the research of future application of OFDM is becoming popular because it enables flexibility and scalability on a network, by dividing a wavelength into smaller channels known as sub-wavelengths.

image extracted from Jinno, 2009

Jinno, M.; Takara, H.; Kozicki, B.; Tsukishima, Y.; Sone, Y. & Matsuoka, S. (2009), 'Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies', Communications Magazine, IEEE 47(11), 66--73.

animated presentation

video history of the internet

video about the history of the Internet in technical terms.

Introduction to basic concepts in linear programming

Linear programming is useful in network for testing a proposal regarding the optimization of the resources or minimization of time of a task operation.

The first step on a linear programming is the formulation of a problem that comprises:

Objective function = what is aimed, maximize or minimize a given function

Decision variables = constraints, the resource limitation represented by variables and equations or inequalities.

Non negative restriction = states the variables are larger or equal to zero.

Sometimes the decision variables are not very easily identified, and they must be identified before developing the objective function.

An objective function can be maximized or minimized.

There are many ways to formulate a problem.

Ideally a formulation should have as fewer variables as possible considering it must maintain the same amount of constraints.

Formulations with inequalities are usually better than formulations with equations.

An interesting video for linear programming formulation introduction.

Physical components meanings

Optical cross connects (OXCs): In a mesh topologies devices are needed at nodes to route signal from the in port to an specific out port. Types of OXCs: electronic, optical and wavelength selective.

Transceivers: Combination of a transmitter and a receiver.

Optical add-drop multiplexer(OADM): is a device used in wavelength-division multiplexing systems for multiplexing and routing different channels of light into or out of a single mode fiber (SMF).

Transponders: A wavelength converser.

3R Transponders: Do signal regeneration in Re-time, re-transmit, re-shape).

Multiplexer:

Demultiplexer:

Muxponder (multiplexed transponder): performs basic time division multiplexing of lower rate signals into a higher rate carrier.

Optical Amplifiers: amplifies an optical signal directly without the need to convert into electronic signal before.

Optical-Electrical-Optical (OEO) regenerators

Erbium Doped Fiber Amplifiers (EDFAs): most used optical amplifiers applied for the Conventional, or C-band, from approximately 1525 nm – 1565 nm, and the Long, or L-band, from approximately 1570 nm to 1610 nm.

A DWDM terminal multiplexer

An intermediate line repeater

Intermediate optical terminal, or optical add-drop multiplexer

DWDM terminal demultiplexer

Optical Supervisory Channel (OSC)

(SOA) Integrated Semiconductor Optical Amplifier Semiconductor optical amplifiers (SOAs) are amplifiers which use a semiconductor to provide the gain medium.

(SOI)  Silicon-On-Insulator.

(SOJ) Small-Outline J-lead.

(ROADM) Reconfigurable Add-Drop Multiplexing:  is a form of optical add-drop multiplexer that adds the ability to remotely switch traffic from a WDM system at the wavelength layer.

(AWG) Arrayed Waveguide Grating

(EML) Element Management Layer 

ONDM 2011 - Bologna - Day 3

15th International Conference on Optical Network Design and Modeling

The article presented by J. Ahmed mentioned that the online RWA algorithm is used for fast, real-time provisioning. Their study focus on the need of re-optimization of resource usage since network churn causes resource usage to be fragmented and may cause connection requests to be blocked. The issue is when and what to re-optimize. One option is to have the re-optimization task triggered when a given threshold number of blocked requests is reached. The current benchmark is to trigger the function after an X number of requests have entered the network. What to re-optimize can be defined by the LPs (light-paths) on most congested links, or the ones causing most congests, the current benchmark is to pick X numbers of requests from the last arrived ones.

Best paper awards:

-        Proactive Restoration of Optical Links Based on the Classification of Events
Jelena Pesic, Esther Le Rouzic, Nicolas Brochier, Laurent Dupont – Telecom

-        Power Efficiency of SARDANA and Other Long-Reach Optical Access Networks
Ana Lovric, Slavisa Aleksic, Jose Lazaro, Giorgio Tosi Beleffi, Josep Prat, Victor Polo

-      Minimizing Wavelength Conversion Cost in WDM Networks with a Constrained Blocking Probability - Han-You Jeong, Seung-Woo Seo, Yoon-Ho Choi

ONDM 2011 - Bologna - Day 2

15th International Conference on Optical Network Design and Modeling

Morning sessions had two main focus wireless optical networks (specially applied on access networks) and energy aware Optical Networks. On access networks the growth of fiber to the home has been mentioned in all presentations. In the paper by Visani et al. plastic optical fiber is presented as a cheap and easy to install solution for fiber to the home. The paper by Alresheedi et al. debated the advantages and drawbacks of Optical Wireless communications. One of the advantages is the fact that optical transceivers are more cost effective than radio frequency transceivers, one of the drawbacks is the degraded SNR partly due to the spread of signal receive.

In the energy efficiency topic, the investment of protection technology in PONs access network is analyzed in the paper by Mas et al. The paper by Ahmad et al. debates on the path computation process and the fact that it does not consider the physical topology and therefore does not take into account the energy expenditure. Their aim on finding a path is find the best trade-off between the utilization of electronic device for switching and optical resources for transmission: minimizing the total power consumption. They solved the problem with a Mixed Integer Linear Programming, heuristic and meta-heuristic techniques. The paper by Marcel Caria et al. presented a by-pass solution to avoid a congested IP routing link, by using a connection on the optical layer, where the only requirement is that the ingress router on the by-pass segment be configured to perform the task.

The big star of the afternoon sessions was PCE, and Hierarchical PCE. It is the technology of choice especially when multi-domain and multi-layer networks are the scenario for the attempt to provide end-to-end quality of services as it is mentioned in the article by Di Giglio et al. where the some studies from the STRONGEST project are presented. The GEYSERS project, presented by Giada Landi, focus on the control plane for the integration of dynamic optical network services in cloud computing scenarios. They propose a centralized NIPS (network and IT provisioning services) server in each network domains. DICONET project presented by Spadaro developed a Q-Tool that would be responsible for real time computation of the Q value. The MAINS project presented by Palacios focused on the control plane architectures for sub-wavelength path provision which results in a more flexible cost effective network. All the studies above propose extension on the control plane technologies as PCE and GMPLS. 

ONDM 2011 - Bologna - Day 1

15th International Conference on Optical Network Design and Modeling

Morning session papers presented fixed on the physical layer aspect of optical networks as the question of regenerators placement and the requirement of regenerators on a network. For cost efficiency purposes, it is important to keep the number of regenerators as small as possible.

The afternoon sessions focused on controlling and managing aspects, however a common point between all sessions was the use of linear programming application for optimization and assessment of techniques. Indeed the first presentation of the day, a paper by E.l Varvarigos and K. Christodoulopoulos, presented algorithms applied on Optical Networks and how to solve the Integer Linear programming problem, where the solution must be an Integer and not a Real number.

The paper presented by Raul Muñoz debated on the impacts of outdated Control information in GMPLS-controlled WSON for shared path protection. He reminded that the two models to deal with a failure - Protection and Restoration - juggle on a trade-off between restoration time and resource usage. Their study focused on the model where the backup connection is shared between more than one paths. The path computation relies on a Traffic Engineering database (TED), if the link state variation is highly dynamic the Ted can become out-dated. The convergence time of the TED is defined as the difference of time from when the first TE-LSA message is originated until all TED is updated.

The paper presented by J. Ahmed proposed a model for processing LSP (Label Switched Paths) requests in a dynamic bulk provision model to place the traditional one-by-one provision where requests are serviced as they arrive. The LPSs requests are collected and bundled using a time threshold to control the limit. The network architecture is also modified in order to adapt to the model, therefore there is a request queue and a path computation scheduler.

Recommendation for site-seeing: Due Torri, two tours in old central Bologna where one of them is reasonably inclined towards the other, location: by the beginig of Via Ugo Bassi.

ONDM 2011 - Bologna - Day 0

15th International Conference on Optical Network Design and Modeling

Workshop 1 - Key final outcomes of the EU BONE project

At her presentation, about Optical networks and future Internet, Dimitra Simeonidou from University of Essex, mentioned the necessity of Flexible/elastic bandwidth (BW) allocation. This flexible BW allocation can rely on technologies like the sub-lambda path allocation and Time Shared Optical Networks (TSON), and may be adjusted to the bandwidth usage float according to time of day or day of week.

Interoperability between the TSON and GMPLS control planes is possible and important.

John Mitchel from UCL UK spoke about Access Networks and focused on Hybrid Optical/Wireless Networks. Between others, he mentioned the transparent WIMAX over Multi-wavelength Gigabit PON technology and OCDMA-based PON’s that are electronic processed.

Franco Callegati from University of Bologna talked about various studies on network technologies. He mentioned the Adaptable admission control: GMPLS wavelength routed networks and adaptable guard channel to guarantee high priority class. In network design: talked about flow aware networking, traffic engineering and topology design in OPS MAN. For routing issues: Integrated BGP and PCE for traffic engineering for multi-domain networks, where Hierarchical instance of BGP (HBGP) is used and mentioned the studies on the impact of out-dated topology information.

Suggestion for dinner: Ristorante da Nello: Via Monte Grappa near via de L’Independenzia. Ask for the Lasagna Verdi a la Bolognese.

Suggestion for hotel: Hotel Palace: Via Monte Grappa 9/2: central, big rooms, old style, reasonably priced.

Dinamical lightpath establishment and QoS issues on WDM networks

Distributed routing inherently has issues of out-dated link state information that can jeopardize the proper assignment of paths that satisfy pre-determined requirements.

When a GMPLS or a PCE architecture are used on the control plane for establishing or computing paths the route computation is performed by nodes reserved for the control task and not the forwarding task characterizing a distributed routing.

The constant update of Traffic Engineering Databases (TED) or Destination Initiated Reservation (DIR) becomes crucial.

At the introduction of Ghimire's paper a brief discussion on the subject may be found.

MPLS DiffServ aware

The DiffServ architecture available on IP network provides QoS to packet flows via classifying IP packets and determining specific treatments for each packet applied by Per-Hop-Behavior on each node.

With the deployment of MPLS technology networks IP packets are no longer processed individually by nodes and therefore the DiffServ is no longer applicable.

The MPLS DiffServ aware described on RFC 3270, enables QoS by treating traffic flow classes differently regarding scheduling and drop precedence.