Problem Statement and Motivation - People - Publications - Deliverables - Funding
The
Internet’s simple best-effort packet-switched architecture lies at the core of
its tremendous success and impact. However, current Internet architecture
allows neither (i) users to indicate their value choices at sufficient granularity
nor (ii) providers to manage risks
involved in investment for new innovative QoS
technologies and business relationships with other providers as well as users.
To allow these flexibilities, this project investigates “contract-switching” as
a new paradigm for future Internet. Just like packet-switching
enabled flexible and efficient multiplexing of data in the Internet, a
contract-switched network will enable flexible and economically efficient
management of risks and value flows.
This
project focuses on the design of a contract-switching framework in the context
of multi-domain QoS contracts. It addresses the
challenges involved in the development of decentralized inter-domain protocol
mechanisms that can dynamically compose and price complex end-to-end contracts.
The project formulates this end-to-end contract composition as a “contract
routing” problem, resembling the QoS routing
algorithms. This research also develops an appropriate abstraction necessary
for pricing of QoS contracts, dynamically composable contracts in space and time. The project employs
financial engineering techniques to provide risk sharing mechanisms and
money-back guarantee structures for the QoS
contracts. This research brings together network architecture design and
financial engineering tools. This interdisciplinary work can inspire usage of
economic tools for security problems like spam and DDoS
attacks. The project will be especially beneficial to the Internet policy
makers.
- P. M. Kumar,
A. Gupta, M. Yuksel, and K. Kar, Path-Vector
Contracting: Profit Maximization and Risk Management, to appear in Computer Networks, Elsevier
Science.
Abstract: We consider an Internet Service Provider’s (ISP’s) problem
of providing end-to-end (e2e) services with bandwidth guarantees, using a
path-vector based approach. In this approach, an ISP uses its edge-to-edge
(g2g) single-domain contracts and vector of contracts purchased from
neighboring ISPs as the building blocks to construct, or participate in
constructing, an end-to-end “contract path”. We develop a spot-pricing
framework for the e2e bandwidth guaranteed services utilizing this path
contracting strategy, by formulating it as a stochastic optimization
problem with the objective of maximizing expected profit subject to risk
constraints. In particular, we present time-invariant path contracting
strategies that offer high expected profit at low
risks, and can be implemented in a fully distributed manner. Simulation
analysis is employed to evaluate the contracting and pricing framework
under different network and market conditions. An admission control policy
based on the path contracting strategy is developed and its performance is
analyzed using simulations.
- H. T. Karaoglu
and M. Yuksel, Path-Vector Contract Routing, to appear in Proceedings of IEEE International
Conference on Communications (ICC), Ottawa, Canada, June 2012. (slides)
Abstract: Many recently proposed clean slate Internet architectures
essentially depend on more flexible and extended representation of
Internet topology on which next generation routing protocols may operate.
Representation of neighboring relationships between Internet Service
Providers (ISPs) in finer granularity is promising to overcome many
shortcomings of the current Internet architecture. Similarly,
contract-switching paradigm promotes an ISP to define itself as a set of
edge-to- edge (g2g) links that connect ingress and egress routers of its
domain. Each link is represented by a contract which defines not only
neighboring relationships with other domains but also economic (e.g.,
price), performance (e.g., quality of service parameters) and temporal
(e.g., lifetime of the dedicated link) attributes attached to this g2g
link. In this work, we introduce Path-Vector Contract Routing (PVCR)
protocol, which allows multi-metric, multi-hop negotiation of end-to-end
inter-domain paths by leveraging path-vector style construction on top of
g2g contract definitions. Our analysis on synthetic and real-world topologies
show that Path-Vector Contract Routing has many promising properties such
as rich route diversity, end-to-end multi-domain QoS
and low control traffic. We also investigate inter-domain traffic
engineering capabilities of PVCR, which inherently considers economics of
routing in its opportunistic settings.
- P. K. Muthuswamy,
K. Kar, A. Gupta, H. T. Karaoglu,
and M. Yuksel, ISPs as Nodes or Sets of Links?, to
appear in Proceedings of IEEE International
Conference on Communications (ICC), Ottawa, Canada, June 2012. (slides)
Abstract: We consider the contract-switching paradigm for studying the
inter-domain traffic engineering problem. In the
contract-switching paradigm, each ISP in the Internet is abstracted as a
set of edge-to-edge contract links. We formulate the optimal routing
problem for the contract-switching paradigm by considering three
objectives, namely: 1) maximizing throughput, 2) minimizing delay, and 3)
minimizing bandwidth usage. We solve the optimization problems on realistic
network topologies and show that the routing solutions developed using the
contract-switching paradigm provides significant improvement in
performance compare to the BGP routing framework with respect to the three
objectives. Moreover, our simulation study also reveals that the
contract-switching paradigm performs close to the best performance that
can be achieved in the Internet in the absence of any abstractions.
- H. T. Karaoglu
and M. Yuksel, Effectiveness of Multi-Hop Negotiation on the Internet,
Proceedings of IEEE Global
Communications Conference (GLOBECOM), pages 1-6, Houston, TX, December
2011. (slides)
Abstract: Inter-domain routing has been long considered as an ongoing
negotiation on end-to-end paths between service providers. Such negotiations
were often believed to be effective in their form of bilateral
interactions between neighboring ISPs in a rather hierarchical market
structure. Traffic engineering policies, multi-homing schemes and peering
mechanisms have been often employed as only service performance
improvement methods within this localized approach. However, several
measurement studies on inter-domain routing have revealed that these
methods are not effective at capturing diversity in performance levels and
alternative paths offered by the Internet. Recently, several clean slate
Internet architecture proposals have introduced multi-hop negotiation
mechanisms in an effort to revitalize inter-domain routing on the
Internet. In this work, we quantify how effective these local policy
exceptions are in providing better quality paths. We also analyze the
increasing benefits ripened by broadening wide-area route control
capabilities of an ISP. Our analysis on traces captured from the Internet
quantitatively shows that currently adopted local policies are effective
only to a certain extent in compared to multi-hop negotiation mechanisms
for the purpose of attaining better paths in terms of multiple performance
metrics.
- H. T. Karaoglu
and M. Yuksel, Inter-domain Multi-Hop Negotiation for the Internet (poster paper), Proceedings
of IEEE International Symposium on Policies for Distributed Systems and
Networks (POLICY), pages 169-170, Pisa, Italy, June 2011. (slides)
Abstract: Inter-domain
connectivity in the Internet is currently established on policy-based
shortest-path routing. Business relationships of the Internet entities are
translated into routing decisions through policies. Although these
policies are built on simple mechanisms provided by BGP, they give rise to
very complex market structure. Extensive research efforts have been made
to understand common practices of inter-domain policies. In early stages,
hierarchical models were thought to be adequate to explain negotiation
between the entities over improving routing and expressing routing
preferences in general. Then, it has been realized that there are
significant number of local policy exceptions and random decision making
over hierarchical structure. In this work, we examine how effective these
local policy exceptions are in providing better quality paths. Our
analysis on traces captured from the Internet quantitatively shows that
currently adopted local policies could not be as effective as multi-hop
negotiations for the purpose of attaining better paths in terms of
multiple path quality metrics.
- H. T. Karaoglu,
M. Yuksel, and M. H. Gunes, On the Scalability of Path Exploration Using
Opportunistic Path-Vector Routing, Proceedings of IEEE International
Conference on Communications (ICC), pages 1-5, Kyoto, Japan, June
2011. (slides)
Abstract: It can be
argued that, BGP, de-facto inter-domain routing protocol, provides fairly
stable routes. Path stability is a desired product of that limited level
of deterministic performance of BGP. To attain this performance level, BGP
relies on keeping up-to-date (aggregated) global information by incurring
the cost of control traffic and delayed convergence. In this work, we
developed an Opportunistic Path-Vector (OPVR) protocol, which provides
nice trade-offs between path stability, routing scalability and path
quality to enable flexible inter-domain level routing services. Our
approach is to redefine routing problem as a set of smaller scale problems
that can be solved locally without requiring a global coordination but
local communication. We also provide guidelines on how to solve these
localized routing problems efficiently. Our analysis shows that our method
provides a good compromise between scalability and opportunity through
smartly randomized (non-deterministic) choices. Our experiments with OPVRs
on Internet AS-level topology show us that OPVRs can provide
non-deterministic, scalable path exploration mechanisms with reasonable
control traffic cost.
- A. Uppaluri,
P. Kumar, M. Yuksel, A. Gupta, and K. Kar, A Two-Market Inter-ISP Contracting Framework: Bandwidth
Allocation Risk Management Problem, Proceedings of IIE Industrial
Engineering Research Conference (IERC), Reno, NV, May 2011. (slides)
Abstract: An
automated way of establishing inter-ISP contracts will enable ISPs to
flexibly allocate their network resources to different contracts. However,
this flexibility comes with the additional complexity in managing the ISP
network and its risks. In this paper, we address how an ISP should assess
the risk of a particular edge-to-edge path and reflect that risk on the
contracting parameters, as well as respond to the risk by segmenting
bandwidth between edge-to-edge short-term versus long-term contracts.
- M. Yuksel, Meta-Headers: Top-Down Networking
Architecture with Application-Specific Constraints, Proceedings
of IEEE GLOBECOM Workshop on Network of the Future (FutureNet-III),
pages 309-314, Miami, FL, December 2010. (slides)
Abstract: The direction of
cross-layer wireless research has been prominently bottom-up, i.e.,
optimizing higher layer protocols based on the characteristics of the
underlying wireless communication medium. Though this approach has been
essential for efficient use of scarce wireless connectivity and bandwidth,
there is a recent trend for massive availability of wireless resources
through initiatives such as municipal WiFi and
community wireless. The key metric to optimize is becoming application
utility rather than the wireless resources. This paradigm shift calls for
top-down cross-layer designs in wireless protocols, where
application-specific requirements can be reconciled. We introduce
“meta-headers” vertically traveling across the network stack and enabling
top-down optimizations in the architecture.
- H. T. Karaoglu and M. Yuksel, Value Flows: Inter-Domain Routing over
Contract Links, Proceedings of IEEE GLOBECOM Workshop
on Network of the Future (FutureNet-III), pages
342-347, Miami, FL, December 2010. (slides)
Abstract: Due to the
Internet's commercialized ISP structure, inter-domain routing is perceived
as more of a commercial service (and market decision) instead of an
optimization problem subject to purely technical criteria. In this
perspective, routing could be defined as a service which
matches perishable resources to requested level of service demands.
This diversity in demanded services and proliferation of diverse set of
existing and emerging applications cannot be responded by a single mindset
of priorities, limited set of metrics or protocol characteristics.
Instead, we propose a contract-based routing service architecture, which
allows manageable dynamism or routing protocol characteristics. By
considering routing as a contracted service, network traffic can be
treated as “value flows” rather than bare bits. Such value-based treatment
of routing will significantly help improving inter-domain routing
economics and dynamics, where policy can be expressed as contracting
terms. In this paper, we present a Link-State Contract Routing (LSCR)
protocol for long-term services and explore how inter-domain
routing dynamics could be managed by adjusting “contract term” or routing
service lifetime.
- N. Shenoy, M. Yuksel, A. Gupta, K. Kar,
V. Perotti, and M. Karir,
RAIDER: Responsive Architecture for
Inter-Domain Economics and Routing, Proceedings of IEEE
GLOBECOM Workshop on Network of the Future (FutureNet-III),
pages 321-326, Miami, FL, December 2010. (slides)
Abstract: Multi-owner
structure shaping inter-domain operations is arguably the most important
factor determining the end-to-end performance in the current Internet.
Financial sustainability of Internet service provisioning has
significantly changed the way Internet grows and all the other business
sectors using the Internet as infrastructure. Further, scalability of BGP
routing table sizes is becoming a stressing problem. Architectural
solutions providing ways to better inter-domain economics and more
scalable inter-domain routing protocols are of crucial importance. In this
position paper, we present a new inter-domain communications architecture
to address routing scalability by leveraging the inherent structure in ISP
topologies and using a simplified addressing method. To manage risks in
costly backbone business and open the doors for realizing higher quality
end-to-end services, our architecture uses protocol-level techniques to
increase operational granularity of inter-ISP market with automated
service level agreements (SLAs).
- M. Yuksel, A.
Gupta, K. Kar, and S. Kalyanaraman,
Contract-Switching for Managing
Inter-Domain Dynamics,
chapter in Next-Generation Internet
Architectures and Protocols, Eds. B. Ramamurthy, G. N. Rouskas, K. M. Sivalingam,
Cambridge University Press, pages 136-153, December 2010.
Abstract: In this book
chapter, we report our recent work on contract-switching
and a sample intra-domain contracting scheme with bailouts and forwards.
We describe a contract-switching network architecture for flexible value
flows for the future Internet, and for allowing sophisticated financial
engineering tools to be employed in managing the risks involved in
composition of e2e QoS contracts. We concentrate
on the design of our contract-switching framework in the context of
multi-domain QoS contracts. Our architecture
allows such contracts to be dynamically composable
across space (i.e., across ISPs) and time (i.e., over longer time-scales)
in a fully decentralized manner. Once such elementary instruments are
available and a method for determining their value is created (e.g., using
secondary financial markets), ISPs can employ advanced pricing techniques
for cost recovery, and financial engineering tools to manage risks in
establishment of e2e contracts and performance guarantees for providers
and users in specific market structures, e.g., oligopoly or monopoly. In
particular, we investigate elementary QoS
contracts and service abstractions at micro (i.e., tens-of-minutes) or
macro (i.e., hours or days) time-scales. For macro-level operation at high
time-scales (i.e., several hours or
days, potentially involving contracts among ISPs and end users), we
envision a link-state like structure for computing e2e ``contract
routes.'' Similarly, to achieve micro-level operation with more
flexibility at lower time-scales (i.e., tens-of-minutes, mainly involving contracts among ISPs), we
envision a BGP-style path-vector contract routing.
- M. Yuksel, A.
Gupta, and K. Kar, Dynamic Overlay Single-Domain
Contracting for End-to-End Contract Switching, chapter in Performance
Models and Risk Management in Communication Systems, Eds. N. Gulpinar, P. Harrison, and B. Rustem,
Springer, Volume 46, pages 191-223, November 2010.
Abstract: The Internet’s
simple design resulted in huge success in basic telecommunication
services. However, in terms of providing end-to-end QoS
services, the Internet’s architecture needs major shifts since it neither
allows (i) users to indicate their value choices
at sufficient granularity nor (ii) providers to manage risks involved in
investment for new innovative QoS technologies
and business relationships with other providers as well as users. To allow
these much needed economic flexibilities, we envision contract-switching
as a new paradigm for the design of future Internet architecture. Just
like packet-switching enabled flexible and
efficient multiplexing of data, a contract-switched inter-network will
enable flexible and economically efficient management of risks and value
flows with more tussle points.
We show that economic
flexibilities can be embedded into the inter-domain designs by
concatenating single-domain contracts and this framework can be used to
compose end-to-end QoS-enabled contract paths.
Within such a framework, we also show that financial engineering
techniques (e.g. options pricing) can be used to manage risks involved in
inter-domain business relationships. We address implementation issues for
dynamic pricing over a single domain by outlining a congestion-sensitive
pricing framework Distributed Dynamic Capacity Contracting
(Distributed-DCC), which is able to provide a range of fairness (e.g. max-min,
proportional) in rate allocation by using pricing as a tool.
- M. Yuksel, K.
K. Ramakrishnan, S. Kalyanaraman,
J. D. Houle, and R. Sadhvani,
Quantifying Overprovisioning vs.
Class-of-Service: Informing the Net Neutrality Debate, Proceedings
of IEEE International Conference on Computer Communication Networks
(ICCCN), pages 1-8, Zurich, Switzerland, August 2010. (slides)
Abstract: The benefit of
Class-of-Service (CoS) is an important topic in
the “Network Neutrality” debate. Proponents of network neutrality suggest
that over-provisioning is a viable alternative to CoS.
We quantify the extra capacity requirement for an overprovisioned
classless (i.e., best-effort) network compared to a CoS
network providing the same delay or loss performance for premium traffic.
We first develop a link model that quantifies this Required Extra Capacity (REC). For realistic traffic distributions
(e.g., long-range dependent), we find the REC using ns-2 simulations of
the CoS and classless links. Our primary
contribution is in using these link models to quantify the REC for
realistic network topologies under various scenarios including “closed loop”
environments with traffic generated by TCP sources that adapt to the
available capacity. We show that REC can be significant even when the
proportion of premium traffic requiring performance assurances is small, a
situation often considered benign for the over-provisioning alternative.
- W. Liu, H. T. Karaoglu, A. Gupta, M. Yuksel, and K. Kar, Edge-to-Edge Bailout Forward Contracts
for Single-Domain Internet Services, Proceedings of IEEE
International Workshop on Quality of Service (IWQoS),
pages 259-268, Enschede, Netherlands, June 2008.
(slides)
Abstract: Despite the huge
success of the Internet in providing basic communication services, the
Internet architecture needs to be upgraded so as to provide end-to-end QoS services to its customers. Currently, a user or an
enterprise that needs end-to-end bandwidth guarantees between two
arbitrary points in the Internet for a short period of time has no way of
expressing its needs. To allow these much needed basic QoS
services we propose a single-domain edge-to-edge (g2g) dynamic capacity
contracting mechanism, where a network customer can enter into a bandwidth
contract on a g2g path at a future time, at a predetermined price. For
practical and economic viability, such forward contracts must involve a
bailout option to account for bandwidth becoming unavailable at service
delivery time, and must be priced appropriately to enable ISPs manage
risks in their contracting and investments. Our design allows ISPs to
advertise point-to-point different prices for each of their g2g paths
instead of the current point-to-anywhere prices, allowing for better
end-to-end paths, temporal flexibility and efficiency of bandwidth usage.
We compute the risk-neutral prices for these g2g bailout forward contracts
(BFCs), taking into account correlations between different contracts due
to correlated demand patterns and overlapping paths. We implement this
multiple g2g BFC framework on a realistic network model with Rocketfuel topologies, and evaluate our contract
switching mechanism in terms of key network performance metrics like
fraction of bailouts, revenue earned by the provider, and adaptability to
link failures.
- M. Yuksel, K.
K. Ramakrishnan, S. Kalyanaraman,
J. D. Houle, and R. Sadhvani,
Class-of-Service
in IP Backbones: Informing the Network Neutrality Debate,
(short paper) Proceedings of ACM
International Conference on Measurement and Modeling of Computer Systems
(SIGMETRICS), pages 465-466, Annapolis, MD, June 2008. (poster)
Abstract: The benefit of
Class-of-Service (CoS) is a heated topic in the
“Network Neutrality” debate. Proponents of network neutrality suggest that
over-provisioning is a viable alternative to CoS.
We quantify the extra capacity requirement for an over-provisioned classless
(i.e., best-effort) network compared to a CoS
network providing the same delay or loss performance for premium traffic.
We first develop a link model that quantifies this Required Extra Capacity (REC). To illustrate key parameters
involved in analytically quantifying REC, we start with simple traffic
distributions when delay or loss probability is the performance goal.
Then, for more bursty and realistic traffic
distributions (e.g., long-range dependent), we find the REC using ns-2
simulations of the CoS and classless link cases.
Our primary contribution is in using these link models to quantify the REC
for realistic network topologies (obtained from Rocketfuel)
under various scenarios including link and node failures. We show that REC
can be significant even when the proportion of premium traffic is small, a
situation often considered benign for the over-provisioning alternative.
We also show that the impact of CoS on
best-effort traffic is relatively small while still providing the desired
performance for premium traffic.
- M. Yuksel, A.
Gupta, and S. Kalyanaraman, Contract-Switching Paradigm for
Internet Value Flows and Risk Management, Proceedings of IEEE Global
Internet Symposium, Phoenix, AZ, April 2008. (slides)
Abstract: The Internet’s simple design resulted in huge success in
basic telecommunication services. However, in terms of providing
end-to-end QoS services, the Internet’s
architecture needs major shifts since it neither allows (i) users to indicate their value choices at sufficient
granularity nor (ii) providers to manage risks involved in investment for
new innovative QoS technologies and business
relationships with other providers as well as users. Currently, users can
only indicate their value choices at the access/link bandwidth level not
at the routing level. Similarly, an enterprise that needs end-to-end
capacity contracts between two arbitrary points on the Internet for a
short period of time has no way of expressing its needs. To allow these
much needed economic flexibilities, we introduce contract-switching as a new
paradigm for the design of future Internet architecture. Just like packet-switching enabled flexible and efficient
multiplexing of data, a contract-switched inter-network will enable
flexible and economically efficient management of risks and value flows
with many more tussle points.
This
project is supported by National Science Foundation award 0721600 and 0721609.
Problem Statement and Motivation - People - Publications - Deliverables - Funding
Last updated on January 9, 2012
