In today's post, we briefly look at the longest common subsequence problem:
A longest common subsequence (LCS) is defined as a problem where two sequences are given X = (x1, x2, ... xm) and Y = (y1, y2, ... yn) and we wish to find a maximum length common subsequence of X and Y. A common subsequence is one that is a subsequence of both X and Y.
This is a standard textbook problem for dynamic programming. We solve this with the optimal substructure of an LCS and recursion.
We define the optimal substructure this way:
1. if xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1
2. if xm != yn, then zk != xm implies that Z is an LCS of Xm-1 and Y
3. if xm != yn, then zk != yn implies that Z is an LCS of X and Yn-1
In other words, we are defining the solution in terms of the subproblems.
This yields a recursive solution in terms of the length of the longest common subsequence c[i,j] as :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj
Condition number 2 limits which sub problems we should consider.
Also, there are overlapping sub-problems encountered something for which we could use bottom-up solving or memorization.
LCS-LENGTH(X, Y)
m = X.length
n = Y.length
initialize b[m,n] and c[m,n] as new tables
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b

and we print the LCS as
PRINT-LCS(b, X, i, j)
      if i == 0 or j == 0
        return
      if b[i,j] == up-left
         PRINT-LCS(b, X, i-1, j-1)
         print xi
      elseif b[i,j] == up
        PRINT-LCS(b, X, i-1, j)
      else PRINT-LCS(b,X, i,j-1)

#codingexercise


Double  GetNthRootProductOddRaisedPDividedQAndEvenRaisedPTimesQ (Double [] A,Double  p, Double q)


{



If ( A== null) return 0;



Return A.NthRootProductOddRaisedPDividedQAndEvenRaisedPTimesQ(p, q);



}

Today we continue to read the Riverbed optimization systems.  RiOS supports standby between primary and backup devices. Even Active/Active configuration is supported where each appliance is serving as a primary for some traffic and as a backup for some other appliance, with full data store synchronization. In addition, RiOS permits a variety of in-path, virtual in-path or out of path configurations both parallel and clustered.
Next we look at end to end security. Security and performance are often at loggerheads for WAN traffic optimizations. Either accepting sub-par performance or lowering the security bar is needed. Data has to be secured both in-motion and at rest. Here RiOS's SSL acceleration module allows customers to securely accelerate SSL encrypted traffic without scattering certifications and keys. It works along SSL offload or load balancing devices.Server IP auto discovery simplifies this set of features. RiOS also support optional encryption of inner channel traffic.
To protect data at-rest, RiOS encrypts its datastore with AES which also satisfies security or compliance regulations. Since the data in the data store constitutes of segments and proprietary references, it is difficult to put together a file from the shredded data by a hacker. The optional encryption of the data store provides an additional level of security and compliance over and on top of already secure datastore.
Since SSL connections are certificate based, RiOS devices have strong authentication securing the ends of the encryption traffic. Moreover, management functions for security are streamlined through the console and controller as we discussed in the previous posts.
The design of the WAN Optimization techniques for RiOS stems from the three issues that plague WAN traffic :

• WAN bandwidth limitations
• transport protocol inefficiencies
• and application protocol chattiness

As a summary,
RIOS provides the following optimizations
Data Streamlining:

• Memory only basic compression
• Disk-based data reduction
• QoS marking
• QoS enforcement
• Hierarchical QoS 

Transport Streamlining:

• Basic TCP optimization
• Advanced TCP optimization
• HS-TCP/MX-TCP
• 3 WAN visibility modes

Application Level optimizations

• CIFS protocol
• NFS protocol
• Local file storage
• MAPI
• HTTP
• HTTP Enhancements
• MS-SQL
• SSL traffic optimizations
• Oracle 11i
• Disaster Recovery Acceleration

Today we continue to read the Riverbed optimization systems. We started discussing the clustering options. We saw that even the series connected appliances can have a benefit. They make use of the of the feature of RiOS to pass traffic through unoptimized when the appliance is over limit. The next appliance therefore gets the chance to optimize it.
Moreover a single RiOS device can be plugged in-path on multiple network links. It can support simultaneous in-path deployment on 6 copper links or 6 fiber links, or even a mixture. In addition, the separation of server side and client side connection forwarding enables RiOS devices to co-operate across multiple redundant links when there are too many links for a single device or multiple links that are too far apart for a single device.
The deployment can also be out of path for redundancy and scale. In this mode, a pool of devices work together to handle incoming requests. When a device fails, the requests are failed over to the next device which handles the requests. This kind of deployment can be done using a Layer 4 switch, WCCP or PBR.
We now look at the notion of an interceptor. This is an optional role for Riverbed devices. It functions as a specialized connection distribution device for a bank of RiOS devices. In addition to functioning as an L4 switch, it can perform asymmetric routing. Besides it eliminates the need for WCCP or PBR which are difficult to configure. The interceptor is typically used for large Datacenter deployments where it can be deployed without requiring any static route configuration. The interceptor can  handle upto 1 million  concurrent connections. Moreover it can scale up to 12Gbps and maintain uniform performance over extended duration by monitoring the peers.
RiOS also supports warm standby between designated primary and backup devices. Using automated data store synchronization, both the data segments and the references created via Data Streamlining are copied from primary to backup appliance. On failovers, the backup functions as a hot data store and can begin serving immediately.

We were discussing Riverbed Operating System (RiOS) technical concepts. We were discussing the proxy file service which can improve performance by deferring current requests or permitting certain operations even if WAN connectivity is disrupted. PFS is an integrated local file server with support for disconnected operations and replication. It has a separate dedicated portion of disk space and does not interfere with the data streamlining activities with the remote server. This does not require any server side agent like Windows CIFS does and PFS works with any kind of host. Because its an optional feature it is not disruptive to the existing streamlining functions. Since PFS works as a local file server, it supports disconnected operations. Since it works in a dedicated mode, it can support replication to and from the remote datacenter. These are complementary to the benefits offered by the prediction and pre-population in the regular connections. In other words, the support for disconnected operations is in addition to the high performance acceleration system without the data integrity and communication issues of caching. PFS also schedules automatic updates of the  PFS shares on appliances, requiring no administrative oversight.
Next we look at high-availability clustering. This is helpful when deploying more than one RiOS devices in place of the existing RiOS device for high availability.  If the devices are place in series, then they take advantage of the fact that RiOS passes through unoptimized traffic when its performance limit is reached, handing over the opportunity to optimize the passed through traffic to the next member of the serial cluster.
#codingexercise


Double  GetNthRootProductOddRaisedPtimesQAndEvenRaisedPtimesQ (Double [] A,Double  p, Double q)


{



If ( A== null) return 0;



Return A.NthRootProductOddRaisedPtimesQAndEvenRaisedPtimesQ(p, q);



}

We were discussing Riverbed Operating System (RiOS) technical concepts. We now discuss the scalability of RiOS. The support for most network topology, no requirement to use tunnels, support for full mesh environments, no manual configuration, translates into broader scalability for large scale enterprises. Peering limits are nearly 4096 peers as compared to a few dozen with tunnel based solutions. In terms of throughput and connections, a RiOS device can support upto 40000 connections, optimizing traffic upto 10000 users. Clusters of devices can support upto one million concurrent connections and upto 4 Gigabits per second of throughput.
In terms of services, RiOS devices additionally provides customers with the capability to run software modules to run on the devices in a protected zone. By hosting the services and applications at the appliance, network level data interoperability is now available and this solution is called the Riverbed services platform. For example, The RSP helps customers by enabling branch services such as IP address management, video streaming and local print server. The RSP creates an extensible platform for multiple technology partners to deploy their services and applications without the need for dedicated servers and to deploy them at the edge. This ability to create a partition to host the RSP is done with the help of VMWare to provide a resource instance.
The RSP has additional capabilities such as the ability to add disk space without recreating RSP packages and the ability to put the RiOS appliance as a man-in-the-middle so that the interceptor based technologies can take full advantage of the RSP and the network.  In addition, RSP comes with a watchdog process that operates as a heartbeat to monitor each package and restart the Virtual Machines.
RiOS also provides an integrated local file server with support for disconnected operations and replication.Proxy File Service can improve performance by deferring current requests or permitting certain operations even if the WAN connectivity is disrupted.
#codingexercise

Double  GetNthRootProductOddRaisedPDividedQAndEvenRaisedPDividedQ (Double [] A,Double  p, Double q)

{


If ( A== null) return 0;


Return A.NthRootProductOddRaisedPDividedQAndEvenRaisedPDividedQ(p, q);


}

We were discussing Riverbed Operating System (RiOS) technical concepts. Today we look at QoS features of the product. We already discussed the network deployment and management streamlining options and found the RiOS devices to be appliances that expect no changes to the network. Now beyond the topology network considerations, let us review how QoS can be leveraged for bandwidth sensitive traffic. Traffic can be classified using the DS field (DSCP) This can be applied to both the optimized and pass-through traffic. The DS field values are passed by RiOS in completely transparent handoff  and hence existing QoS can be honored. In addition, new QoS DS fields can be defined with the WAN accelerated traffic.
The data-deduplication and data reduction  achieved with RiOS reclaims bandwidth and even undo existing QoS classifications which may no longer be necessary and can be replaced with simpler better re-classification. The RiOS devices that are deployed on the edge network can employ Hierarchical Fair Service class-of-service marking (H-FSC) and enforcement. This is used to improve both bandwidth and latency. H-FSC is a scheduling algorithm that can simultaneously support 1) hierarchical link sharing services, 2) guaranteed real-time service with provable tight delay bounds and 3) decoupled delay and bandwidth allocation. The latency-sensitivity of this approach is usually not found in many other techniques. If there are two different real-time critical applications and their bandwidth guarantees are met,  the queues could still become filled with traffic introducing jitter. In such cases, the ability to schedule application traffic based on latency and setting priority to that application traffic comes very useful with this kind of a scheduling algorithm.
Application visibility into network traffic is improved with the Riverbed "AppFlow" classification engine which utilizes a variety of technique and usually in combination. These techniques include :
port - based classification for applications
pattern-matching or application signature using patterns or magic numbers in protocol headers using regular expressions, byte or string matching.
protocol dissection - which involves detailed interpretation of the application protocol for contextual sub-classification or protocol attribute extraction
future - flow registration - where  a past occurrence of a flow is used to tag a future occurrence
behaviorial classification - where the behavioral classification relies on the detection of behavioral attributes of the network traffic using packet size, packet inter-arrival time, packet rate, data rate, and entropy calculations for a behavioral signature for an application.
decryption / decoding - where encoding, obfuscation or simple encryption may be used by applications


 

We were discussing Riverbed Operating System (RiOS) technical concepts. We were looking at the management streamlining functions. The controller and the console were used for this purpose. The central management console provides touchless feature. It provides aggregated or individual device reporting, group based configuration policies and scheduled operations. It also provides trends upto a years worth of data and drilldrowns for more granular data. This is a web interface that also facilitates over the wire software upgrades, global SSL certificate management and an easy to use QoS rules configuration interface. One of the things administrators look for when optimizing WAN traffic are those that are the heaviest users of bandwidth and they are referred to as "Top Talkers" . This is useful for both security monitoring as well as for accounting purposes.  Top Talkers together with NetFlow give a lot of WAN transparency.
While the console manages the devices, the Controller provides central management capabilities for the clients. The SMC enables easy deployment of mobile client software to remote users via MSI packages. It also integrates with Active Directory or LDAP for access control. The controller also provides license management, job scheduling and notifications to extend its administrative capabilities.
Next we look at the deployment options for RiOS. We mentioned the plug-in interface for RiOS appliances in any network topology and scalability due to its adherence to the networking fundamentals instead of specific architectures or setups such as tunnels. Consequently it requires less involvement during deployment. Even legacy devices and networks are compatible with this kind of appliances - since there are no changes expected or required from the network. Changes such as tunnel configurations, DFS changes, client drive mapping changes, plugins router configurations, route injection, or any other overhead required for competitive solutions are avoided. This implies that RiOS devices can be installed in networks as large as using satellite infrastructure or as connected as full mesh MPLS networks.

#codingexercise

Double  GetNthRootProductOddRaisedPDividedQAndEvenRaisedPPlusQ (Double [] A,Double  p, Double q)

{


If ( A== null) return 0;


Return A.NthRootProductOddRaisedPDividedQAndEvenRaisedPPlusQ(p, q);


}