FORM 2
THE PATENTS ACT. 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL SPECIFICATION
[See section 10 and rule 13]
1. Title:
A Novel Architecture for Guaranteed end-to-end Quality of Service (QoS) over internet
2. Applicant:
IIT Bombay, Powai, Mumbai, India - 400 076
The following specification particularly describes the invention

1. Introduction
There has been remarkable growth in the traffic on the public network in the recent past primarily because of growth in telecom industry. New services and applications such as multi-media, voice and video over IP, video-on-demand, and video-conferencing are being introduced on public network. There are many new peer-to-peer applications for video-sharing or file-transfer (viz. Joost, BitTorrent) which consume high bandwidths on the Internet. The resulting heavy bandwidth usage and bursty traffic puts tremendous pressure on the existing infrastructure and all the services that are sharing it. With increase in activity over public network, we should note that resources available in shared, public networks are finite and may lead to contention among users causing degraded performance for all.
There are various applications and services which have definite QoS requirements Enterprise services and applications such as supply chain and resource management, synchronizing critical data in real time, effective communication among geographically diverse locations of an organization, corporate telephony, video-conferencing and telecommuting have different definite QoS requirements and need end-to-end QoS guarantee for achieving best performances. Currently enterprises rely on VPN over leased line connections in spite of widespread availability of public network. This is primarily because of not having end-to-end QoS guarantees across multiple ASes Using public networks for any application is cost effective. Moreover leased line approach may not scale in the cases of the communication requirements among multiple geographically spread entities. Clearly we need to provide end-to-end QoS guarantees spanning across multiple ASes on public network to enable such premium applications and services. Also since there are finite resources available over the public network, we need to separate the premium services from other basic access or best-effort services in order to provide QoS to premium services.
Currently Intra- domain QoS can be supported using dedicated virtual connections (VCs) or dedicated MPLS tunnels with requisite resource reservation. qBGP, which is an extension to traditional Border Gateway Protocol (BGP) can be used for achieving inter-domain QoS by supporting QoS-enhanced reachability information. Another approach is to use multi-protocol BGP to setup MPLS tunnels spanning across adjoining ASes.
There are two aspects for achieving guaranteed end-to-end QoS over public network. First is to develop the framework for information exchange, signaling, co-ordination and path setup spanning across multiple ASes corresponding to the different network providers and the second part is to find an optimal inter-domain path based on specific QoS requirement. BGP based approaches do path selection in a distributed manner by applying local policies which need not match with the end-to-end QoS requirements. Firstly, there is a loss of information at each AS boundary or border node since, only a single locally optimal path is advertised further. Secondly, local policies are based on commercial considerations and do not have viable financial model that supports QoS needs of transiting traffic. Thus, the end-to-end path need not be globally optimal and best for the specific QoS requirements. In order to improve upon the information loss and path selection at border nodes, the idea of centralizing the BGP information and path selection is implemented in Routing Control Platform (RCP). However, the ASes are managed by different commercial/non-commercial entities like ISPs/educational institutes. There exist no collaboration and business models among different internet provider entities with respect to exchanging the reachability information. The RCP framework does not go beyond that to enable entire path level QoS support or provide business model for it. To achieve end-to-end QoS support for premium services you need viable framework and commercial model for collaboration among ASes. We build upon the RCP concepts to propose a new framework to achieve it.
2. Proposed Architectural Framework
The proposed framework is based on a new concept of AS Designated QoS provider Entity (ADE) for each AS. ADEs are modeled over RCPs but their role goes beyond centralizing BGP based reachability information and path selection. They are responsible for information exchange, path selection and set-up, connection aggregation, connection admission control and fault management and support of virtual connections spanning multiple ASes to enable end-to-end QoS for premium services. This architectural framework is technology independent and can work with diverse set of underlying QoS technologies like ATM, MPLS, GMPLS, etc. or any future changes in them. Figure 1 shows a typical end to end QoS Session between two users spanning over multiple domains or ASes represented by solid pink line . Each AS consists of multiple nodes connected through links as shown. The border nodes which connect outside the AS are called gateways. Each AS has a designated ADE and the connection management is performed by the respective ADEs in each AS along the path. The dotted line represents control plane information exchange for managing the QoS sessions

The proposed architectural framework in detail for providing guaranteed end-to-end QoS for inter-
provider premium Services is shown in Figure 2. The figure also shows how different network entities
interact and possible standard protocols for exchanging information between them. The architecture
constitutes user node with some signaling mechanism like SIP, various AS Designated QoS provider
Entities [ADEs], routing nodes and intermediate gateways.

A user initiates new QoS connection by signaling to its provider ADE using session initiation protocol requesting certain class of service. SIP can use SDP parameters to define QoS requirements. The provider (first) ADE is in-charge of setting up end-to-end path and also manages billing and support functions. The provider ADE refers to its network reachability database to determine the destination AS

and corresponding destination ADE and starting ADE to final ADE path. The provider ADE checks if there is suitable starting gateway to final gateway path satisfying the CoS requirement suggested via SDP parameters. It can select the most suited path when multiple paths exist. The provider ADE initiates signaling between the ADEs along the ADE to ADE path. All the ADEs in ADE to ADE path would verify that there are sufficient QoS resources for its own part after triggering the first GW in the path in their own part. We propose using the Next Steps in Signaling protocol (NSIS, RFC-4080) for the signaling between ADEs. The figure shows NSIS proxy in each ADE to enable this signaling.
First gateway in each AS will try to establish the path at gateway level by standard technology dependent QoS mechanism to satisfy the CoS requirements. The first gateway will communicate the success or failure to the respective ADE. Each ADE will then forward the request to subsequent ADEs in the path. After entire verification (typically termed as Connection Admission Control (CAC)) is complete, the last ADE will send final Acknowledgement upon which the QoS Path would be reserved for the user application at each ADE in the path. The ADEs then stitch the path segments together to form end-to-end virtual connection for forwarding the data.
Figure 3 shows proposed layered structure for this architectural framework presenting four main layers; First one is the session control plane. This is technology independent layer and only end users and ADEs participate in this plane. The second one is technology dependent control plane for ADEs that is aware of the underlying QoS mechanisms. ADEs and gateways participate in this layer. The third one is technology dependent control plane for GWs. GWs and routing nodes participate in this. The fourth one is data forwarding plane. This is the traditional data path. It can be noted that session control plane and the data forwarding plane are end to end while other layers are disjoint.

Gateways
The Gateways can be of following types: Routers having IP/MPLS support, ATM Switches, frame relays or layer 3 switches. This architecture is not limited by the underlying technology and its QoS mechanism. Specifically data link layer can be standard Ethernet, ATM or optical layer. The network domains could also be heterogeneous allowing for mix-n-match of underlying technologies and QoS models. Gateways constitute the Data Forwarding Plane. This is also termed as the virtual data layer for ADEs. The Paths are setup at Gateway level by ADEs. Functions of gateways include standard routing, forwarding and supporting underlying QoS models (like RSVP, RSVP TE, etc.)

Routing nodes
The routing nodes are the nodes along the data path within an AS. Routing nodes are gateways which do not communicate across AS boundaries. In fact gateways are the special cases of the routing nodes. They also do not communicate with ADEs. Routing nodes assist gateways in the gateway to gateway path setup within an AS. Routing nodes participate in technology dependent control signaling as well as data forwarding.
AS Designated QoS Provider Entities (ADEs)
As presented earlier this architecture presents a novel concept of AS Designated QoS Provider Entities (ADEs). The ADEs are modeled as extension of RCP concept. They are responsible for information exchange, path selection and set-up, connection aggregation, connection admission control and fault management. There are various functions that ADE implements for setting up end-to-end QoS connection. These functions are listed below and elaborated further in the discussion that follows Obtain the updated view of QoS reachability information within and across different ASes
• Provision resources among different ASes and build various possible Paths
• Select most appropriate Paths and perform Connection admission Control for a new connection.
• Connection aggregation and pre-provisioning of resources
• Fault management for selected paths including monitoring and recovery
The initial function of an ADE is to obtain the updated view of the reachability information within the given AS and with respect to the neighboring ASes. It is proposed that ADE functionality be built on top of the existing RCPs and typically RCPs will have the standard mechanism (to use BGP) to obtain the Reachability information. To extend this, this framework suggests that qBGP to be used to exchange QoS Reachability information.
End to end Paths are built by the control plane of ADEs in their respective virtual data plane (in the data layer for the Gateways) to serve the service needs of the Application Layer. We should neither have dedicated path for each flow (as in intserv) nor should we have single path for large number of flows (as in diffserv). The proposed architecture suggests that we build the paths according to the various Classes of Service (CoS) supported at the Control Plane.
We need to exchange the QoS reachability information and select optimum set of QoS NLRI (Network Layer Reachability Information) parameters to build various paths to the destination. Selecting optimum set of QoS reachability information is a difficult problem which requires controlling and optimizing the routing process. The ADEs should communicate to the border gateway protocols like qBGP for the same. Optimum set of QoS NLRIs would come from different policies at Border Routers (or Gateways) and/or ADEs.
Typically QoS NLRI set happens to be large so as to select optimum paths. This leads to scalability and bandwidth issue. QoS NLRI set may not be optimum because of the tiered structure of the internet. Provider AS may not advertise all NLRIs from its peer provider to its customers. The issue of Tiered structure of the internet can be solved by having Alliance Network Model. The issue of optimal set of QoS NLRIs would be also solved by the Alliance Model and single logically centralized ADE which provide optimal set of QoS NLRIs. Finding optimal path under multiple QoS constrains is an NP-hard problem.
The connection establishment signaling in ADEs is fully technology independent. Each ADE converts the QoS requirements into technology dependent information. It is aware of the network topology and availability of resources within the AS for which it is designated. ADE controls the border nodes or gateways within the AS through signaling protocols such as, SNMP, Telnet, or COPS (RFC-2748). Thus, ADE can initiate path set-up within the AS through a gateway based on the underlying technology. Each path segment may have different technologies and QoS models. The gateways use the underlying technology to establish the virtual path-segment. Gateways constitute the virtual data layer for ADEs and participate in path set-up using standard routing and forwarding protocols within the AS.
The ADEs also provide connection aggregation to bring scalability. An effective aggregation can be implemented by pre-provisioning tunnels and mapping new connections on to them. It also simplifies monitoring and fault management. Connection Admission Control (CAC) typically triggers connection aggregation whenever required. CAC will admit the current connection into existing aggregated path or trigger a new aggregation. CAC again will be performed on aggregated path. Aggregation logic is


executed at select ADEs where aggregation needs to be attempted. Here is the proposed algorithm for facilitating connection aggregation
Definitions
Pk: Set of paths
• Bj,k,r. :Total BW requirements between Gateway pair (GWj, GWk)
• Bj,k,a: Total available BW between GW pair (GWj, GWk)
• GWj: GW where aggregation is attempted
• j: Index of starting gateway
• k: Index of ending gateway
• r: Required
• a: Available
Algorithm
• Identify Pk{ pi, p2, ..p5k} spanning across GW pair (GWj, GWk) such that
O Bj,k,r <= Bj,k,a
o "nk" is maximized
o Repeated for each "k"
• Set up the aggregated Paths for each Pk
The path set-up and resource reservation along intermediate ASes is enabled by commercial contract initiated by the provider (starting) ADE with the respective ADE of intermediate AS. A business model to support premium services by sharing resources from multiple ASes can be supported by this framework. Once the Paths are built and selected for a user application, we need to monitor them for bandwidth overflow, continuity, node failure and link failure. If required the paths may be re-routed along optimum paths in case of any fault. This is achieved by performing CAC again at the ADEs, first in their own part and if required for all ADEs.
3. Implementation Scheme
The architectural framework consists of mainly three entities: User nodes, ADEs and Gateways. This section details the proposed implementation scheme and choice of protocols for interaction among these entities
Interaction between User Nodes and ADEs
The signaling and control layer of user node interacts with the Technology independent layer of ADEs to setup sessions between the source user node and the destination user node. SIP is an application-layer control protocol that can Establish, Modify, and Terminate multimedia sessions and invite participants to already existing sessions. SIP Supports 5 facets of Sessions: User location, availability, capabilities and Session setup, management.
Interaction between User Nodes and Gateways
The interaction between user nodes and Gateways would be typically in Data Plane and standard data layer (IP) protocols can be used for the same. User may be connected to the gateway using any technology supported by the last mile connection such as Ethernet, DSL, WiMAX, etc. Typically user connection is defined by the port on the gateway
Interaction between gateway and routing node
Since ADEs communicate (session control messages) only with gateways and not with routing nodes, gateways need to initiate path control messaging to routing nodes along the path in an AS. This path setup and control functionality is fully technology dependent. For example MPLS has its own control protocols (LDP, RSVP-TE) to setup the virtual paths (LSPs) and ATM has mechanism for setting up virtual circuits (VCs)
Interaction between ADEs and ADEs

Interaction between Technology Independent Layers of ADEs can be performed by NSIS with NSIS Proxy and/or NSIS Entity. NSIS is a hop by hop signaling protocol and provides requisite functionalities for the same. This architecture does not limit to use any other protocol for this purpose as well.
NSIS (Next Steps in Signaling) is an architectural framework for various signaling protocols and model for the network entities that take part in such signaling. NSIS constitutes NSIS Signaling Layer Protocol (NSLP) which supports specific signaling application and NSIS Transport Layer Protocol (NTLP) which supports interaction with lower-layers.
NSIS Signaling Layer can be mainly used for interaction between two ADEs while NSIS Transport Layer can be used for peer ADE discovery and other lower layer tasks. Standard NSIS protocol message semantics are listed below
• Request (to create a new reservation for a flow)
• Modify (to modify an existing reservation)
• Release (to tear down an existing reservation)
• Accept/Reject (to confirm or reject a reservation request)
• Notify (to report an event detected within the network)
• Refresh (for state management)
The implementation of information translation between technology independent and dependent control layers within an ADE can be proprietary to the ADE. The underlying technology must be able to support the QoS mechanism that technology independent layer is trying to establish.
Interaction between ADEs and Gateways
The interaction between ADEs and Gateways is mainly for following purpose:
• To obtain the updated view of Reachability information within and across different ASes
• To provision resources among different ASes and build various possible Paths
• Aggregate connections and pre-provision capacity
• To perform Connection admission Control for a new connection.
• To perform Fault Management for selected Paths
Since all these tasks are managed at ADEs but in turn performed by Gateways, we need to have a good interaction mechanism between ADE and Gateways. Here we propose three different choice of protocol mechanisms for the same: COPS, SNMP and Telnet, with each having distinct pros and cons.
Common Open Policy Service (COPS) protocol is a simple query and response protocol with a client server model which can be used to exchange policy information between a policy server (Policy Decision Point or PDP) and its clients (Policy Enforcement Points or PEPs). In the current context, the ADEs should implement PDP while Gateways should implement PEP. COPs use TCP as its transport protocol for reliable exchange of messages. The advantages of COPs includes extendibility (can support diverse client specific information without requiring modifications to the COPS protocol itself) and security (provides message level security for authentication, replay protection, and message integrity, can reuse existing protocols for security such as IPSEC or TLS). The disadvantage is that all Gateways participating in this framework are required to implement PEPs. This is especially useful when ADEs control multiple AS'es and provide managed services.
ADEs can use standard SNMP "get" and "set" operation to read and write the parameters on gateways to perform desired operations. ADEs can use standard Telnet terminal to have the same things performed. The advantage of SNMP and Telnet are that these are standard protocols already implemented on most gateways. The disadvantage is that they do not provide a clean interface and security.
4. Conclusions
We present here the generalized framework for achieving guaranteed end-to-end QoS for inter-provider premium services with the help of newly proposed AS designated QoS provider entities or ADEs. This architectural framework is fully technology independent and would work with mix of underlying QoS technologies including MPLS, ATM or GMPLS. It supports building and selecting QoS aware end-to-end paths, Connection Admission Control, connection aggregation and Fault Management. It also supports the business model to collaborate among different network service providers to offer end-to-end QoS for premium services.