Post-workshop Documents Available in PDF Format: (Accessible by Participants only)

Modeling and Simulation of Ultra-Large Networks: Challenges and New Research Directions

NSF-Sponsored Workshop (by Invitation-Only)

Nov. 19-20, 2001, Tucson, AZ, USA

Pre-workshop Documents Available in PDF Format:

· ULN workshop announcement

· Questions for ULN considerations

· Some responses and more questions

· Link to abstracts of overview talks

Organized by:

· The Arizona Center for Integrative Modeling and Simulation ( http://www.acims.arizona.edu )

· The Society for Modeling and Simulation International ( http://www.scs.org )

List of Participants and Observers:

Participants	Organization	Website	Presentations
Agarwal, S.	Lucent Technologies	Link
Claffy, K.	San Diego Super Computing Center, UCSD	Link
Colbourn, C.	Arizona State University	Link
Cox, P.	Lockheed Martin	Link
Floyd, S.	Lawrence Berkeley Nat'l Lab/ACIRI/UCB	Link	PDF
Fujimoto, R.	Georgia Tech	Link	PPT
Gelenbe, E.	Univ. of Central Florida	Link
Ghosh, S.	Stevens Institute of Technology	Link
Hariri , S.	University of Arizona	Link
Joslyn, C.	Los Alamos National Laboratory	Link	PDF
Kim, T.G.	Korea Advanced Inst. of Science & Tech.	Link
Martinez, R.	University of Arizona	Link
Ng, H.	Naval Research Laboratory	Link
Meyer, D.	Sprint	Link
Nicol, D.	Dartmouth College	Link
Orman, H.	Nortel	Link
Raghavendra, C.	University of Southern California	Link	PPT
Reily, G.	Georgia Tech	Link
Sanders, W.	University of Illinois, Urbana Champaign	Link	PDF
Sarjoughian, H.	Arizona State University	Link
Wainer, G.	Carleton University	Link
Wilsey, P.	University of Cincinnati	Link
Woodcock, B.	Zocal	Link
Zeigler, B.	University of Arizona	Link	PPT
Znati, T.	NSF/University of Pittsburgh	Link
Cam, H.	Arizona State University	Link
Gupta, S.	Arizona State University	Link
Krunz, M.	University of Arizona	Link
Louri, A.	University of Arizona	Link
Reisslein, M.	Arizona State University	Link
Rozenblit, J.	University of Arizona	Link
Sen, A.	Arizona State University	Link
Xue, G.	Arizona State University	Link

Abstracts of Overview Talks:

Network Dynamics and Scalable Congestion Control

S. Floyd Download PDF

Abstracts: In this talk I will address some of the current issues in network dynamics and congestion control in the Internet, and discuss some of the challenges in the evolution and growth of the Internet infrastructure. The challenges include not only those of scale, but of new functionality, new vulnerabilities, and diverse extreme environments. I will also discuss some of the difficulties in simulating and modeling the Internet. Again, the fundamental issue is not only one of scale (that is, of a vast network of many identical pieces), but of scale combined with decentralized control and pervasive heterogeneity and change.

Executing Models for Ultra Large Networks: Parallel Discrete Event Simulation and Beyond

R. Fujimoto Download PPT

Abstract: This talk will focus on characterizing the current state-of-the-art in using parallel discrete event simulation techniques to execute models of ultra large networks. I will review some current research projects and approaches in realizing tools for modeling ULNs, and speculate on the future capabilities we can reasonably expect from these efforts. I will discuss the role network simulations can play in the future, and describe research challenges in this regard.

Systems Concepts for the Simulation of Ultra-Large Networks

C. Joslyn Download PDF

Abstract: It is evident that simulation of Ultra-Large Network (ULNs) will prove a monumental challenge to both the network and simulation communities. This is primarily due to the vast complexity of these systems which combine unprecedented levels of storage, computation, and connectivity. Indeed, when modeled as formal systems, ultra-large networks, especially when coupled to social or socio-technical systems, undoubtedly represent the epitome of complex information systems. What kinds of mathematics, what classes of models, what methods of simulation, are most appropriate, indeed, give us any hope of understanding and predicting their emergent structures and behaviors? Interdisciplinary modeling fields, broadly called the Systems Sciences, attempt to bridge understanding across systems of all types by finding isomorphisms of structure, function, and organization. They invoke information scientific categories, both quantitatively and qualitatively, especially such concepts as order, organization, information, structure, and function, but especially complexity and models. In this talk, we provide a brief introduction and review of some of these concepts and current work in the hope that it will be useful in elucidating the nature of the complexity and some potential methods to facilitate our understanding of ULNs.

Issues and Challenges in Large Scale Network Modeling and Simulation

R. Raghavendra Download PPT

Abstract: With the exponential growth of the Internet and its services, our Dependence on network based systems is growing at an alarming rate. Modeling and simulation tools and techniques work well for small-scale networks. However, these existing methods and tools will not work for well large-scale networks. The issues and challenges are: building multi-scale and multi-resolution models for complex networks; accurate and trustable prediction of performance, predicting anomalies such as congestion storms or Internet meltdown; efficient and/or faster than real-time simulations; using measurements to validate modeling and simulation results; traffic models that reflect the real world traffic; and analysis to detect intrusion and attacks. These and other issues will be the topics for discussion in this workshop.

Multi-Level And Multi-Formalism Modeling Of Ultra-Large Networks

W. Sanders Download PDF

Abstract: There have been significant advances in methods for specifying and solving models that aim to predict the performance and dependability of computer systems and networks. At the same time, however, there have been dramatic increases in the complexity of the systems whose performance and dependability must be evaluated, and considerable increases in the expectations of analysts that use performance/dependability evaluation tools. This talk briefly reviews the progress that has been made in the development of performance/dependability evaluation tools, and argues that the next important step is the creation of modeling frameworks and software environments that support multi-level, multi-formalism modeling and multiple solution methods within a single integrated framework. In addition, this talk presents an review of the Möbius project, which aims to provide a modeling framework and software environment that support multiple modeling formalisms, methods for model composition and connection, and a way to integrate multiple analytical/numerical- and simulation-based model solution methods. Finally, it suggests research that must take place to make this vision a reality, and thus facilitate the performance and dependability evaluation of ultra-large networks.

Modeling and Simulation of Ultra Large Networks: Methodology Responds to Challenges

B. Zeigler Download PPT

The challenges to modeling and simulation methodology have been well elucidated by others. In this talk, I will suggest some approaches to simulation model development that complement some of those already presented. These deal with hierarchy, in both model and control schemes, and related dynamic structure capability:

· Hierarchical construction for managing the verification/validation challenges in developing models of large scale, multifaceted systems

· Hierarchical construction together with abstraction of components to control the complexity of models as they scale upward

· Models of architectures with hierarchical control schemes for management of network resources

· Dynamic structure models capable of changing their fundamental structures during run time to represent changing user patterns, modes of behavior, and system reconfiguration.

The importance of user awareness of the assumptions (abstractions) underlying the simulator (black box) has been noted. An approach to attaching such assumptions to the simulator will be suggested.

Prelude to the Workshop:

The Internet is increasing in connectivity, expected to reach 1 billion nodes in 2005, and node capability (gigahertz playstations are imminent) providing a highly interconnected and computationally powerful medium. Such a globally and ubiquitously dispersed network will provide a new frontier for new kinds of educational, commerce and entertainment activities. However, there are many issues that arise in the emergence of such a large, highly decentralized, collection of interacting parts. The increased connectivity and capability creates new complexity and dynamics that we are only on the verge of appreciating. Moreover, increased connectivity by itself does not assure improved business customer relationships, more fruitful scientific collaboration, and a safe yet adventurous environment for children. Indeed, there is ever more potential for information and processing overload and malicious security attacks that shut down the entire system. The question is then as the world scales up in inter-connectivity, how to assure that our current quality of life is actually improved, or at least maintained, and not diminished. Recent tragic events have shown how technology and scale are not necessarily good in themselves. Technology can be horribly abused and the vulnerability of systems may increase drastically with scale. Thus this workshop is more timely and urgent now than when it was first proposed. Its products are expected to be of extreme importance to the nation and the world.

Techniques that work for small networks fail markedly when the size, complexity, and interdependence of network nodes increases by one million fold. The impacts of scaling up need to be examined from several points of view such as security, openness, resource sharing, flexibility, adaptivity, and fault-tolerance. New theories, paradigms and techniques need to be developed to address these issues. Moreover, computer-based modeling and simulation (M&S) methodology is required to enable these developments since the scale is well beyond what analytical tools alone can handle. Moreover, there is limited ability to do controlled experiments on the “always on” Internet. Thus, the time has come to develop M&S-based approaches for understanding the behaviors of very large inter-connected networks with very few loci of control and many interacting and varied sources of input and services demand.

Questions for ULN consideration (First Draft)

The following questions are a first crack at the kinds of questions that might need to be answered by modeling and simulation of ultra-large networks. For M&S methodology, they are domain questions; The workshop will address the general issue of the adequacy of existing models, simulations, and methodologies for representing, simulating, and evaluating ULNs. Some questions raised for M&S methodology appear at the end. First we have domain questions:

Network Questions

1. Can IP, ATM or combinations of current protocols scale to the one billion-node Internet? Current routing algorithms incorporate hop-by-hop routing mechanism that makes QoS difficult. What are the requisite properties of new algorithms? How can they be tested before fielding?

Streamlining the Internet-fiber connection , Dixit, S.; Yinghua Ye

IEEE Spectrum, Volume: 38 Issue: 4 , April 2001 Page(s): 52 –57

IP Switching for Scalable IP Services Hassan M. ahmad, Ross Callon, Andrew G. Malis, John Moy Proceedings of the IEEE, VOL. 85, NO. 12, December 1997

An Approach to Routing Elastic Flows , Sara Oueslati, Eliane Oubagha.,

In ITC16 Volume 3b, June 1999.

A Comparative Study of Routing Algorithms for Elastic Flows in a MultiServe Network , Sara Ouslati, Eliane Oubagha. France Telecom R&D, March 2000.

2. The “last mile” is a major issue in performance and ability to bridge the digital divide. What kinds of models are needed to address this issue?

Bring home the Internet , Dutta-Roy, A.
IEEE Spectrum, Volume: 36 Issue: 3 , March 1999, Page(s): 32 –38

Managing the last mile [access network] Bernstein, L.; Yuhas, C.M.
IEEE Communications Magazine, Volume: 35 Issue: 10, Oct. 1997, Page(s): 72 –76

Paving the information superhighway's last mile Lawton, G.
Computer, Volume: 31 Issue: 4, April 1998, Page(s): 10 -12, 14

3. We seem headed toward a ubiquitous Internet characterized as a massively distributed network with powerful local servers forming the master-slave relations. Will this one-level hierarchy be capable of performance and other demands? Is more centralize/hierarchical control over the Internet required?

Master/slave computing on the Grid , Shao, G.; Berman, F.; Wolski, R.
Heterogeneous Computing Workshop, 2000. (HCW 2000) Proceedings. 9th, 2000, Page(s): 3 –16

Architectures, features, and implementation of high-speed transport protocols
La Porta, T.F.; Schwartz, M. IEEE Network , Volume: 5 Issue: 3 , May 1991, Page(s): 14 -22

4.Can/should efficient algorithms be designed/implemented that load-balance across geographical servers? Can/should header size be increased as allowed by future channel capacity increases?

A dynamic load balancing algorithm based on distributed database system
Yucai Feng; Dong Li; Hengshan Wu; Yi Zhang High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on , Volume: 2 , 2000 Page(s): 949 -952 vol.2

Issues of the state information for location and information policies in distributed load balancing algorithm Gil-Haeng Lee EUROMICRO Conference, 1999. Proceedings. 25th , Volume: 1 , 1999 ,Page(s): 67 -70 vol.1

Load balancing in a heterogeneous computing environment Gopalt, S.; Vajapeyam, U. System Sciences, 1998., Proceedings of the Thirty-First Hawaii International Conference on , Volume: 7 , 1998 , Page(s): 796 -804 vol.7

5.Can the current TCP/IP protocol suite solve the problem of pervasive networking (everything on the internet)? Do we need new architectures that specify new packet designs and the underlying infrastructure?

Building networks on the fly [cellular radio] , Pascoe, R.
IEEE Spectrum, Volume: 38 Issue: 3 , March 2001 ,Page(s): 61 –65

Architectures, features, and implementation of high speed transport protocols, La Porta, T.F.; Schwartz, M . Global Telecommunications Conference, 1991. GLOBECOM '91.'Countdown to the New Millennium., Featuring a Mini-Theme on: Personal Communications Services , 1991 Page(s): 1717 -1721 vol.3

6.What technologies might push us into next generation of networks? Optical computing and networking, wireless, …

7. Are there fundamental problems that must be solved to limit/manage information growth - an analogy is energy resources where there exists abundant amount of it, but not practical to harvest it.

Modeling and Simulation Questions Raised by Network Questions

M&S methodology per se must address questions of the form:

· Can feasible models be developed to address domain questions such as those above?

· Will there be enough scale and heterogeneity in the models to obtain realistic answers?

· Can/should complexity controlling approaches such as hierarchical construction be employed?

· Can/should families of multi-resolution models be developed -- can models address performance, reliability and security together? Are new models needed for security aspects? Can mutually consistent models be constructed?

· Is there a need for framework/strategy to view ULN from its most basic elements to its whole?

· Are there theories in other areas (e.g., chaos) that might shed light on how to structure/design ULN?

A reference that provides a general introduction to current network simulation without much depth is:

Simulating networks Kaplan, G. , IEEE Spectrum, Volume: 38 Issue: 1, Jan. 2001, Page(s): 74 -76

Responses and questions by Bill Woodcock

1. Can IP, ATM or combinations of current protocols scale to the one billion-node Internet?

It's important to think clearly as regards layer-separation, and not fall into all of the fuzzy-thinking traps that led some people into MPLS (too many layer-twos) and IP-over-fiber (too few), or the fuzzy-thinking that led people to hack OSPF into ATM switches for PVC provisioning. The problem at layer three (IP routing,
end-to-end connectivity) is fundamentally different than the problem at layer two (adjacencies, meshing, and fast-fail-over).

Both will scale, but the means by which we'll do so are as different as the problems are.

The on-the-wire protocols really aren't a problem, for the most part. It's application-layer stuff like routing decision-making algorithms and stupid content distribution and rate-limiting and a million higher-level things. You can't fix spam, or DoS, or paperwork, with TCP tweaks.

Current routing algorithms incorporate hop-by-hop routing mechanism that makes QoS difficult.

So? QoS was the fad that came between ATM and MPLS. It was tried, found irrelevant, and discarded. The hypothetical world in which it would matter would be one in which pipes were more expensive than people.

What are the requisite properties of new algorithms?

This is obviously the big issue we're all trying to nail down. The fundamental thing that's become obvious since the telco reliability crash forced the issue of dense meshing is that while, price aside, the optimum network topology is obviously a full mesh, our current routing decision-making algorithms were optimized for a _very_sparse mesh, and begin to fail badly as the network itself gets better. Therefore, we desperately need routing decision-making algorithms which work well in an ideal case, as well as the worst-case. Beyond that, propagation and dampening of propagation of policy is the next big requirement. Then authentication of delegations and so forth. I'm sure a lot of people could add to the wish-list.

How can they be tested before fielding?

Ah, _there's_ a really good question, and one I'd love to hear some people propose answers to, or at least lines of inquiry leading to answers.

2. The last mile is a major issue in performance and ability to bridge the digital divide. What kinds of models are needed to address this issue?

This is a huge problem, and entirely a regulatory, political, and business-climate one. Do researchers outside of the economic/political sphere have anything to contribute here?

This is a misperception based upon inadequate visibility into service-providers' back-end infrastructure. Multiple tiers of infrastructure actually exist behind services like Akamai and Nominum and Digital Island and UltraDNS and even Yahoo and its ilk. Not a problem, and nothing that needs to be addressed in basic research. This is just production engineering, and it's being done adequately.

Is more centralize/hierarchical control over the Internet required?

That's a political and ideological question, not a technological one. It's a topic for debate, not research.

4. Can/should efficient algorithms be designed/implemented that load-balance across geographical servers?

Topological, not geographical. And they've existed for a decade. Again, this is old hat, and production engineering. No research to be done here.

Can/should header size be increased as allowed by future channel capacity increases?

Huh? Cart leading horse? Header size is a pretty basic parameter. Changing it will break a _lot_ of things. You don't change something that basic because it's _possible_, you change it because you _have to_ for some reason. If, at some point in the future, we _have to_ change header lengths, obviously we will. No research to be done here. When we _have to_, it'll be obvious.

Of much more pressing need is universal support for jumbo frames.

5. Can the current TCP/IP protocol suite solve the problem of pervasive networking (everything on the internet)?

Sure, no reason why not.

Do we need new architectures that specify new packet designs and the underlying infrastructure?

Nope. New protocols will be defined in response to market demands. The problem isn't creating them, it's stamping them out or making them uniform. How many streaming-audio protocols do we have right now? How many do we need? How do we reduce from the former to the latter?

We don't need to overhaul IP or TCP or UDP... They're basic and functional. Everything interesting has long ago moved up the stack.

6. What technologies might push us into next generation of networks? Optical computing and networking, wireless,

Sure, fun stuff. A few things there raise real issues. Wireless has interesting issues in the intersection of regulatory requirements for on-the-air broadcast data and IP encapsulation. The whole MTU issue is starting to get out of hand, and is further aggravated by VLAN-in-VLAN and VPNs and other stuff that people are starting to push in from the edge of the network.

7. Are there fundamental problems that must be solved to limit/manage information growth an analogy is energy resources where there exists abundant amount of it, but not practical to harvest it.

Question isn't clear. You want to manage the growth of the Internet by limiting the rate at which people create new information? :-)

Workshop/Hotel Location

Hotel and Workshop Location: Sheraton Hotel, 5151 East Grant Road, Tucson, Arizona. Ph: 520-323-6262. For further information visit http://tucson.hotelguide.net/data/h100066.htm . The anonymous GroupSystems-facilitated activity will conducted at the University of Arizona, www.arizona.edu .

Reception Location

From Sheraton Hotel: Take Grant Road (heading East, take a left as you leave the hotel) to where it meets Tanque Verde, taking a left (continuing straight is Kolb). Continue on Tanque Verde (east) to Sabino Canyon Rd. (second light) and turn left (heading north); The Sahuaro Girl Scout "Hacienda" program facility is located approx. 1.5 miles ahead on the left side of road at 3101 N. Sabino Canyon road (tel# 520-319-3181). There is a left turn break in the center median right at the entrance. Balloons or ACIMS sign will mark the entrance. Follow the dirt road around until reaching the parking lot by the pool.

Financial Support:

For the invited speakers, the grant allows us to reimburse up to $400 for travel expenses, plus cover hotel accommodations (at the workshop venue). If travel expenses exceeds $400 please contact Steve Branch directly and we will make arrangements to purchase the ticket for you. Meals for the two-day event will be provided separately by the workshop.

Other Cooperating Organizations:

· University of Arizona, College of Engineering & Mines and Dept. of Electrical & Computer Engineering

· Arizona State University, College of Engineering & Applied Sciences and Dept. of Computer Science & Engineering

· Center for Advanced Telesysmatics, University of Arizona.

More Information

For more information regarding travel arrangements and accommodations, please contact

Mr. Steve Branch

Executive Director

Society of Modeling & Simulation International

P.O. Box 17900-7900

San Diego, CA 92177

sbranch@scs.org

Ph. 858-277-3888

Fax. 858-277-3930

For further technical information in regard to the workshop and ACIMS Open House (see below) activities please contact:

· Bernard Zeigler, Electrical & Computer Engr. Dept. Univ. of Arizona, zeigler@ece.arizona.edu , 520-621-2108.

· Hessam Sarjoughian, Computer Science & Engr. Dept., Arizona State Univ., sarjoughian@asu.edu , 480-965-3983

Arizona Center for Integrative Modeling and Simulation

On Nov. 18, 2001, there will be the first organizational meeting of the new Arizona Center for Integrative Modeling and Simulation. For more information, please visit www.acims.arizona.edu/EVENTS/ACIMSOpenHouse2001.html .

First Day (Monday, Nov. 19, 01) *		Location
07:00 – 7:45 am	Breakfast	Sheraton Hotel
8:00 – 12:00 am	Introduction, Three Presentations (one per focus group leader)	Sheraton Hotel
12:00 – 1:15 pm	Lunch	Sheraton Hotel
01:30 – 5:30 pm	Three Parallel Breakout Sessions	Sheraton Hotel
06:30 – 8:30 pm	Informal Discussions and Dinner	Sheraton Hotel
Second Day (Tuesday, Nov. 20, 01 )
07:00 – 7:45 am	Breakfast	Sheraton Hotel
08:15 – 11:45 am	GroupSystems-facilitated Anonymous Review of First Day’s findings	University of Arizona
12:15 – 1:30 pm	Lunch	Sheraton Hotel
01:30 – 4:30 pm	Plenary Discussion, Summary of Finding and Recommendation, and Wrap-up	Sheraton Hotel
06:00 – 8:00 pm	Dinner	Pinnacle Peak
* Evening Reception will be held on Sunday Nov. 18, 6:00 – 8:00 pm

Post-workshop Documents Available in PDF Format: (Accessible by Participants only)

Nov. 19-20, 2001, Tucson, AZ, USA

Pre-workshop Documents Available in PDF Format:

Location

List of Participants and Observers:

Participants

Organization

Website

Presentations

Systems Concepts for the Simulation of Ultra-Large Networks

Issues and Challenges in Large Scale Network Modeling and Simulation

Multi-Level And Multi-Formalism Modeling Of Ultra-Large Networks