## 1. Questions to speakers

J. Crowcroft (*Computer Laboratory, University of Cambridge, UK*). *Question to R. Allsop*. Do models cope with *reduction* in demand? (For example, from a large-scale switch away from private ownership of cars.)

R. Allsop (*Centre for Transport Studies, University College London, UK*). In terms of link performance and choice of routes within networks, there are good reasons for confidence that models that have been developed over decades of rising car ownership would represent what happens under falling car ownership with little adaptation. Modelling of car ownership itself and consequent demand for movement by car and by alternative means are, however, likely to have to take account of hysteresis, in that a downward trajectory of car ownership would not be the reverse of the upward trajectory experienced so far.

A. P. Smith (*London analytics, UK*). *Question to R. Allsop*. Recent analysis of empirical data shows that a dense urban road network can manifest a network-wide speed-flow curve. Different times of day manifest different curves, with different network capacities. Does Prof. Allsop envisage a means to manipulate trip patterns, i.e. the origin–destination matrix, to optimize network capacity?

R. Allsop. Network models have the capability to investigate the dependence of levels of loading in the most heavily loaded parts of a network (under any given assumptions about route choice) upon the origin–destination matrix. Expressing network capacity in terms of the network means vehicle flow per lane-hour which is attainable without instability in network mean speed (cf. Smith 2007) and this opens the way to optimization of network capacity with respect to the demand matrix as a bi-level problem. The lower level is a user-optimized assignment, and at the upper level the objective function is network capacity as so expressed, and the control variables are the elements of the demand matrix. The latter problem is unlikely to have particularly helpful properties but may well lend itself to heuristics that find favourable solutions. Given one or more such solutions, the challenge to planners and policy-makers would then be to persuade activities so to locate as to give rise to one of the favourable origin–destination matrices.

P. Varaiya (*Department of Electrical Engineering and Computer Sciences, University of California, USA*). *Question to R. Gibbens*. NN (nearest neighbour, Gibbens & Saatci 2008) versus regression technique: which is superior for incidents?

R. Gibbens (*Computer Laboratory, University of Cambridge, UK*). Our data did not include incident information. It may well be that additional information on incidents is useful in selecting between the NN and regression technique. However, it is not clear whether such information could also be readily available in real time to inform the predictor. A more comprehensive analysis with such conditional predictors would be an interesting follow-on study.

M. Bell (*Centre for Transport Studies, Imperial College London, UK*). *Question to P. Varaiya*. Could you extend tolls to signalized junctions by enabling cars to pay to use bus lanes? Would this be desirable?

P. Varaiya. This is a complicated question. First, if a bus lane is underused, it makes sense on efficiency grounds to permit additional, tolled vehicles in that lane. Second, one can readily imagine a technology that collects appropriate data for charging the toll. However, a careful analysis is needed to show that the efficiency gain is significant compared with the cost of charging (and enforcing) tolls (see Levinson & Odlyzko 2008). If bus lanes are made accessible to toll-paying vehicles in a large enough area, and if there is significant excess capacity, the idea would be worthwhile.

J. Crowcroft. *Question to P. Varaiya*. Why not have a random toll with probability drawn from a distribution set to trade expectation of charge for expectation of delay? (The original suggestion was by David Wheeler in Cambridge to replace variable bus fares.)

P. Varaiya. At least in theory, this is a sound idea. In the US, high-occupancy vehicle (HOV) lanes are restricted to either 2+ (two or more people) or 3+ vehicles. Often, the 2+ restriction leads to overuse and the 3+ restriction to underuse. Ideally, one would want something like 2.5 passengers per vehicle, which could be achieved by an easily computed randomized charge. The only question is whether drivers would understand and accept such a charge. In many situations, a randomized charge would allow one to get around an ‘integer’ constraint, like in the HOV example above. Another application of randomization is to permit ‘free’ access to a resource (such as a congested road) to, say, half of the peak period demand, on average.

P. Key (*Microsoft Research Ltd, UK*). *Question to P. Varaiya*. ‘RB’ (ramp metering and bottleneck toll, Varaiya 2008) as a control looks attractive. Could you comment on the robustness of this scheme, given that you combine access control with charging? If the same authority is responsible for both parts of the scheme, is there not still a ‘gaming’ problem?

P. Varaiya. A road authority that determines the charge and controls access from the ramp does have an incentive to restrict access more than necessary for efficiency. This will permit raising the toll at the cost of underuse of the road. The underuse will be readily observed by drivers who, I presume, will complain. I believe some kind of public feedback like this is needed to prevent the road authority from exercising its monopoly power. Of course, one could design a combined tolling and access control scheme that is robust and achieves an efficient usage. But why would the authority adopt such a scheme?

S. Borst (*Bell Labs, Alcatel-Lucent, USA*). *Question to P. Varaiya*. If I understand correctly, you assumed that traffic demands are fixed. I was wondering if you could comment on what might happen when traffic demands are time-varying, and to what extent the various schemes that you have described might impact the traffic demands. For example, we could imagine that toll charges provide an incentive for drivers to adjust their travel times, help smooth out the load overtime and cause drivers to select different routes, or even abandon their travel plans altogether.

P. Varaiya. The mathematical analysis does assume stationary demands, because that permits derivation of ‘closed-form’ formulae. When demands are time-varying, as is always the case, one should develop an adaptive scheme for toll charges and access control. Such a scheme would take real-time measurements to update a historical demand pattern over a short term (30 min) into the future.

Over the longer term, tolls would alter the (time and money) cost profiles of different origin–destination pairs. Drivers would undoubtedly react to these changes and adjust their trips, by changing trip times or routes. Figuring out what these changes might be is also called the ‘trip assignment’ problem. At least two presentations at the workshop were devoted to this problem. While there are mathematical programming solutions to this problem, the difficulty is to estimate the origin–destination demands.

Over the very long term, a significant change in the cost profile will induce people and employers to change their location. Tolls can be an important instrument in affecting location choice.

G. Reinert (*Department of Statistics, University of Oxford, UK*). *Question to R. Mondragón*. The talk presented an exciting new network growth model for autonomous system (AS) internet networks which, at each step, not only adds new nodes and new links between new and old nodes but also new links between old nodes. While, apparently, the model impressively fits the observed AS network, with respect to the number of triangles, quadrangles, the maximum degree, the betweenness of vertices, the second nearest neighbour counts, the rich-club coefficient and the shortest path length, the main criterion used for the fit is the power law behaviour of the vertex degree distribution.

It is unusual to see a model that fits so many descriptors well. Yet we cannot expect to find a model that fits the data in every single respect; a model should fit the data well in the features that are important for the scientific question under consideration. It is not clear to me what the underlying scientific question under consideration for this study is.

In particular, the choice of power-law (or *scale-free*) behaviour of the vertex degree distribution as main criterion for the fit should be discussed in more detail. Stumpf *et al.* (2005) showed that random subnets sampled from scale-free networks are not themselves scale-free. Thus if the network was scale-free, a randomly sampled subnet would not have been scale-free. As the AS-internet network data present a subsample of the whole AS-internet network, fitting a model that displays a scale-free property in the sample might not be desirable to model the whole network. In addition, if, say, the underlying scientific question concerns, for example, communication times in the network, then a good fit to the shortest path length distribution would not only be more robust, but also possibly more relevant.

K. Briggs (*BT Research, UK*). Stumpf *et al.* (2005), in the paper referred to by Prof. Reinert, have shown that when a fraction *p* of the nodes of a scale-free graph is sampled, the observed degree distribution is not that of a scale-free graph. This was achieved by computing the exact probability generating function (PGF), and then expanding it in the powers of the parameter *p*, thus obtaining an approximate formula. In fact, an exact formula involving finite sums of polylogarithms is possible.

The setting is this: we fix a parameter , and suppose that we have an infinite graph in which the fraction of nodes with degree *k* is . We now fix a parameter *p*, 0≤*p*≤1, choose uniformly from the graph a fraction *p* of the nodes and keep the edges between these; that is, we form the induced subgraph. We delete the nodes of degree 0. I claim that the degree distribution *P*^{**} of the subgraph is given by(1.1)Here is the polylog function, *ζ* is the Riemann zeta function and *S*_{1} is the signed Stirling number of the first kind.

The proof starts with the degree PGF of the original graphFrom this Stumpf *et al.* (2005, eqn (5)) show that the PGF of the sampled graph isFrom the definition of the polylog, we immediately see that this isThe proof of my equation (1.1) is now a simple induction on *k*, using , and the recurrence for Stirling numbers of the first kind: .

Note that this formula is poor for numerical evaluation, since the Stirling numbers become large and have alternating signs. It is better to derive series expansions useful for small *p*; for example, for *k*=3, we have

The plot (figure 1) verifies that my exact formula agrees with Stumpf's approximations. It should be compared with figure 2, the case.

R. Mondragón (*Department of Electronic Engineering, Queen Mary University of London, UK*). *Reply*. The talk presented how a network model evolved as more topological properties of the AS-Internet had been taken into consideration; hence the underlying research question also changed as the model evolved. The measurements of the AS-Internet connectivity indicated that its degree distribution decayed as a power law. The Barabási–Albert model, or a modification of it, was a good starting point as it generates networks with a power-law decay of the node's degree distribution. Very quickly it was noted that models that only reproduce the node's degree distribution are not complete; they do not describe the hierarchical structure of the network. This observation triggered a search for models that reproduce what the researchers identified as important properties to be studied, e.g. the clustering coefficient, shortest path, etc. Many of these models were very successful in reproducing the properties that they were designed for, but they were unable to reproduce connectivity between the nodes with high degrees, the rich nodes. As in the Internet, the majority of nodes tend to connect to the rich nodes that play an important role in the network's structure. To quantify the connectivity of the rich nodes, we introduced the concept of rich-club coefficient, the density of connections between nodes with degrees higher than *k*. This allowed us to modify the model to reproduce the rich-club coefficient of the AS-Internet. The model presented here was not designed to reproduce such properties as shortest path or distributions of triangles in the network, but to reproduce the rich-club connectivity. This constrains the degree–degree correlation and thus the model can recreate both these properties and other properties, such as the average degree of neighbours.

Regarding the dependence of the power law of the node's degree and the measurements, the value of the power law used in the model is the one obtained from the network's measurement. Clearly, if the measurements are incomplete or skewed, this will be reflected in the value of the power-law exponent in the model. The measurements of the connectivity were not taken at random, so the results of Stumpf *et al.* (2005) do not apply directly here. The measurements were calculated by looking at routing tables or by using a tool called traceroute. Both of these measurements can produce a power-law exponent that is different from the real exponent (see Petermann & de los Rios 2004). To obtain measurements that describe the network fully is still an active research problem. However, it seems that regardless of the value of exponent of the degree distribution, the AS level has a distribution better described by a power-law decay than other models like random graphs (see comment by Dr Zhou).

S. Zhou (*University College London, UK*). The power-law degree distribution is an integral property of the Internet-AS-level topology. Superior to many previous models that mainly focus on fitting the power-law degree distribution, the PFP model accurately captures a large number of other important properties as well, e.g. the shortest path length. Moreover, the model achieves this not using a static approach based on curve-fitting, but a non-equilibrium approach based on evolution dynamics.

The Internet AS graph data used to evaluate the model are not a subset, but a full map of the global Internet collected by CAIDA, which combines traceroute data probed from tens of monitors located in different countries.

In 2004 a few researchers questioned whether such traceroute measurements could be biased, e.g. generating power-law degree distributions in ordinary random graphs that in fact have Poisson degree distributions. However, recent measurements and studies have shown that the traceroute measurements have correctly captured the global Internet structure. The more recent DIMES project collects data from thousands of observers distributed around the world, which is two orders of magnitude larger than the number of observers used in previous measurements. The Internet-AS graph obtained by DIMES exhibits a clear power-law degree distribution in agreement with previous observations. A study by Dallasta *et al.* (2006) has shown that if the observed power law was due to sampling bias and the larger real graph had a Poisson degree distribution, then the graph's average degree would be more than 100, which obviously is not realistic because it is known that the average degree on the Internet-AS graph is merely approximately 6.

R. Srikant (*Department of Electrical and Computer Engineering and Coordinated Science Lab, University of Illinois at Urbana-Champaign, USA*). *Question to R. Mondragón*. In your model, it is assumed that a new AS will attempt to connect to an existing AS with a probability proportional to node degree. However, the Internet has ASs, such as Google, which are not Internet service providers (ISPs) and therefore new ASs will not attempt to connect to such non-ISP ASs. How does this affect the degree distribution obtained from the model?

R. Mondragón. The model presented here is more descriptive than explanatory. In the model, we do not assume that a new AS is an ISP and hence the AS prefers to connect to a well-connected AS that represents another ISP. A new AS could connect to an AS like Google, not because it provides traffic delivery but because it provides other services that the users demand. All these possible ‘reasons’ for an AS connecting to another are not considered in the model. The assumption is that well-connected ASs ‘attract’ connections. If a Google-like AS becomes the best connected node, it could change the degree distribution of the network, which will be reflected in the exponent of the power-law decay of the degree distribution. The dynamics of the growth model were introduced to reproduce certain statistical characteristics of the network's connectivity. The model has been successful in reproducing many of the AS-Internet properties but we should not extrapolate and assume that the growth dynamics of the model are the growth dynamics of the Internet.

The majority of Internet topology models tend to be descriptive rather than explanatory (see Tangmunarunkit *et al.* 2002; Willinger *et al.* 2002). The few network models that try to reproduce and explain the connectivity and evolution of the Internet (at the router level) are based on technological and geographical restrictions and do not reproduce the measured properties of the Internet. At the AS level, the various factors driving Internet growth are not evident. The measurements of the Internet at both levels, router and AS, are not complete (Krioukov & Krapivsky 2006). At the AS level, we tend to model the network as an undirected graph. In reality, the connections between domains are directed as a result of different ISPs having agreements about which traffic passes through their domain. These interactions should be described by a directed graph. We still have more work to do to understand the growth mechanisms of the Internet before we can produce a model that captures these mechanisms.

K. Briggs. *Question to D. Wischik*. Could you comment on the validity of your small-*p* expansions? As , do we not enter a regime where packet-loss events are not independent, rendering your assumptions inconsistent?

D. Wischik (*Department of Computer Science, University College London, UK*). Packets are dropped when buffers become full, which might happen owing to a sudden link failure, or a denial-of-service attack or plain congestion. The first two happen all the time, all over the Internet, but plain congestion is the most common cause of drops along any given path, and it is this that I am trying to capture with *p*. The measurements I quote in my paper suggest that congestion losses are very nearly independent for packets spaced 100 ms or more apart, and that is typical. From my limited simulations so far, the small-*p* expansions give sensible estimates for this value of *p*. For a more accurate estimate, we could calculate higher order terms.

If congestion losses can be eliminated, then delays can still be caused by link failure, or denial-of-service attacks or server overload. Of these, I suspect server overload will be the most common, and indeed it may be an even larger contributor to delay than congestion. Each of the three problems will require a probability model that does not assume independence—link failures are likely to lead to correlations over several seconds, denial of service or server overload will lead to correlations over minutes or hours. I believe these will still be tractable, using techniques broadly similar to those I have described.

R. J. Atkinson (*University College London, UK*). *Question to P. Key*. The same internet node might have multiple IP addresses, but the set of equivalent IP addresses is not usually known to the transport protocols. So multi-path capabilities are difficult to use at present. The analogy with road networks is like a house with multiple street addresses (e.g. at a junction of two roads).

P. Key. You are correct, in that sender-side multipath capabilities are indeed difficult to use at the present time, for the reason you state. Multihoming and multiple addresses are under discussion in the IETF, both in the context of IPv6 and also Mobile IP, since mobility also raises issues of multiple addresses and identity. Indeed, the question of identity is very important, since traditionally IP has had a strong end-system model, and the use of multiple addresses raises problems even for single-path routing. However, receiver-driven multipath is being widely used within peer-to-peer networks, such as Skype or BitTorrent, which combine multipath routing with congestion control.

The answer to the question of how multipath routing and congestion control should be implemented depends on what the Internet node is and also involves a tradeoff between efficiency and ease of deployment. If it is an end-host, then an implementation either requires the design of a new transport protocol, which understands multiple addresses, or requires an application level solution, where the application is responsible for sending data along different paths and data integrity; the different paths may be associated with different interfaces or addresses on the end-host. A transport-layer solution is more efficient but requires an architectural change, whereas application level solutions leave the underlying transport protocols unaltered and so are much easier to deploy; but they also make it much harder to implement certain types of coordinated control. For example, it is much harder to avoid the round-trip time bias of current transport protocols.

If the node is a gateway node then the node acts as a proxy, aggregating traffic and deciding how to route. Middle boxes already provide much of this functionality; the difficult part in this scenario is enabling congestion control, since feedback needs to be received by the middle box, which has to either rely on explicit signalling or aggregate information from constituent IP flows.

M. Smith (*Department of Mathematics, University of York, UK*). *Question to M. Patriksson*. Do your results allow for flat spots in the travel cost function?

M. Patriksson (*Mathematical Sciences, Göteborg University, Sweden*). Yes, they do, in principle at least. The strict monotonicity requirements on the link costs in the statements of the results are there to guarantee the uniqueness of equilibrium link flows and demands for any possible scenario and any design solution. It is possible to restate the results based on monotonicity only, if one adds the condition that flat spots do not appear near any equilibrium solution.

D. Ralph (*Judge Business School, University of Cambridge, UK*). *Question to M. Patriksson*. Your stability analysis of the stochastic mathematical programming with equilibrium constraints (SMPEC) concerns globally optimal solutions. Is it possible to analyse the sensitivity and stability also of stationary points of the SMPEC?

M. Patriksson. That is indeed an interesting avenue for future research, in particular, if one can establish quantitative analyses. Stability analyses exist for special cases of stochastic mathematical programming with complimentarity constraints (SMPCC) (e.g. Shapiro 2006), and of course also for special convex stochastic programming problems (e.g. Römisch 2003), but for general SMPEC I am not aware of any general such results. In fact, we probably have not seen the last well-defined set of optimality conditions of SMPEC yet.

H. R. Kirby (*Napier University, UK*). *Question to M. Patriksson*. Published this year is a paper by Dr Kathryn Stewart and Prof. Mike Maher (Stewart 2007). It would be interesting to compare the approaches towards this problem from different perspectives.

M. Patriksson. It is indeed interesting and important to discuss these relations. The most important thing to recognize is that the ‘stochasticity’ involved in a stochastic user equilibrium (SUE) model is quite special, and a different one from the stochasticity that drives an SMPEC model. The two can however exist together in an SMPEC model that subsumes bi-level optimization with an SUE at the lower level.

The SUE solution is a unique equilibrium in terms of a ‘perceived’ travel cost, in which the error terms are governed by one of a few possible distributions (e.g. probit or logit). These errors are not associated with values of uncertain parameters in the travel cost formulae but are simply errors in the sum of link travel costs. There is nothing uncertain about the solution to an SUE model, and an MPEC modelled with an SUE problem at the lower level is not an SMPEC model. (In this context, the SUE model should therefore be seen in the same light as the ‘mean’ and ‘robust’ equilibrium models discussed in my paper.) On the other hand, it is possible to replace, in the SMPEC model, the deterministic user equilibrium (UE) model with an SUE model, and obtain another SMPEC model. A discussion on the reasons why this is allowed in the framework presented is included in the final section; in short, the essential property of the equilibrium model used in the SMPEC framework is that it provides unique link flows, which the UE model as well as all SUE models do.

An important distinguishing factor between the two model frameworks of MPEC and SMPEC is discussed here. Provided that an MPEC model has a solution, it produces a design, together with a corresponding lower level solution. Solving an MPEC with an SUE model at the lower level would result in just that, where the corresponding lower level solution is a known, and certain, route flow distribution. In the case of the paper by Stewart (2007), depending on the toll optimization problem being solved, there is a final, best toll design, and an ‘observable’ link flow solution associated with it. Suppose then that such a model is augmented through the introduction of uncertain elements in the travel cost and/or the demand function, as explained in my paper, such that the model is naturally phrased as an SMPEC problem. Provided that there is an optimal solution to this model, we again obtain a best toll design, if that was the upper-level variable and objective. But in the framework of the SMPEC model, this design is the best in an expected value sense, and there is no singled-out representative equilibrium flow corresponding to it. If, for example, the upper-level objective is to maximize toll revenue, then the optimal solution to the SMPEC is the toll that maximizes the expected value of the toll revenue over the traveller response scenarios represented.

Along the same lines, there are interesting differences also with respect to other possible goals with the formulation and solution of a bi-level problem. Stewart (2007) discusses an equity issue within her MPEC model, which is an analysis of the traveller responses to a change in the transportation infrastructure. Since an SMPEC model does not produce unique responses, equity measures in this type of model are also uncertain given an optimal design. But this appears to be exactly what one should expect: as responses are uncertain, so too are any equity or other measures related to the travellers' responses to tolls and the like. Analysing measures of equity is then a matter of checking how the distribution of the responses behaves relative to an equity constraint, and the toll optimization problem is naturally influenced by the ability of a given toll to provide user responses that satisfy an equity constraint (with probability one). As is discussed in the paper, previous attempts to model SMPEC problems with constraints on the responses (as ‘joint upper-level constraints’) have met with different success. It may be that in the context of equity constraints one should cope more naturally with the risk of failing to meet with the constraint by remodelling the equity constraint as an upper-level penalty function, or relax it, asking only for it to be satisfied with some probability less than one.

Personally, I like the way one reasons regarding uncertainty in the SMPEC model—one acknowledges that the response is not always the same for the same input. Moreover, uncertainty in the SMPEC formalism is connected directly to the data of the problem, and therefore can be modelled, experimented with and analysed.

N. Kennedy. *Question to J. Crowcroft*. Have you looked at historic non-telecom or pre-telecom models?

J. Crowcroft. Yes, we are considering other models—taken from sociology and anthropology—*viz*. a new project with Prof. Robin Dunbar (University of Oxford) and others on social networks, but it is only just started.

J. M. Brooke (*University of Manchester, UK*). *Question to J. Crowcroft*. A question about privacy: how could you control disclosure of privacy? An individual might give pieces of information, each of which they consider ‘safe’, in terms of disclosure; but by the spread of information in and between communities it might be possible to infer things that violate this safe boundary. In short, people are telling more about themselves than they understand.

J. Crowcroft. No, we have not done this yet—it is hard! As it is probably impossible, it might undermine our ideas for social net-based forwarding, and could even undermine the ability to do research on social nets through direct measurement.

F. Kelly (*Centre of Mathematical Sciences, University of Cambridge, UK*). *Question to A. Odlyzko*. You mention in your paper the ‘mental transaction costs’ of micropayments, and the poor prospects for such schemes as traditionally conceived. But there are many ways to skin a cat!—for example, Google collects substantial revenues from micropayments made by the advertiser.

S. Borst. *Question to R. Srikant*. I have two questions relating to time-scale issues. First of all, you seem to have assumed a strict separation of time scales where sessions are infinitely long-lived relative to packet-level dynamics. Did you have any thoughts on how to handle shorter sessions that may only consist of a moderate number of packets?

R. Srikant. Sessions with a small number of packets should be given high priority. As a result, the capacity available to long-lived flows will vary randomly due to the arrivals and departures of these higher-priority short flows. In the presence of such stochastic fluctuations in the capacity, fairness should be interpreted as long-term fairness, that is, the long-term average network capacity available to long-lived flows is fairly allocated among them.

S. Borst. Second, you mentioned that the larger the buffer sizes are, the closer the utility-optimal throughput vector is approached. However, bigger buffers may involve longer packet-level delays. Do you have any insights into that tradeoff, and possibly guidelines for what buffer sizes might be appropriate to strike the right balance?

R. Srikant. We do not have an exact expression for the delay as a function of the congestion-control parameters. However, one can derive an upper bound on the sum of the queue lengths as a function of the congestion-control parameters. Similarly, an upper bound on the difference between the optimal use and the utility realized by the congestion control algorithm can also be derived. Using these upper bounds, one can trade off between optimality and buffer sizes.

## 2. Panel discussion: transport and communication networks

R. Allsop. A deep-seated difference between transport and communication networks is that in many transport networks the traffic consists of human beings whose opportunities and capability to make choices about their use of the network persist until the end of their journeys through it, whereas in communication networks the messages or data are indifferent to the routes by which they are sent or the delays to which they are subjected. Nevertheless, the contributions to the meeting have illuminated many common features and many areas in which researchers concerned with the two kinds of network face analogous problems. Two of these seem particularly clear, one operational and the other an issue of policy.

The operational issue is the analogy between communication switches and road junctions. A switch that follows rather simple fixed operational rules has something in common with a roundabout one, at which the geometry of the junction, the give-way rule and the arriving traffic together completely determine the conditions encountered by each stream of approaching traffic. On the other hand, a more dynamically intelligent switch has more in common with a signal-controlled road junction where the signal control can respond to both long-term patterns and short-term fluctuations in approaching traffic.

The matter of policy is how to charge for use of a network, and more particularly how to gain user acceptance for the introduction of a socio-economically and operationally preferable but unfamiliar system of charging in place of an existing system, however irrational and disadvantageous, which the users have become accustomed to. In the case of road networks, this might be link-by-link charging for use in which the charges approximate to the marginal social cost of use under the prevailing conditions and are levied partly through fuel duty, partly through an electronically collected congestion-related charge and partly through a usage-related insurance premium. The total amount charged would include the valuation of local and global environmental damage and of those consequences of accident risk not covered by insurance, together with any level of general taxation that parliament has voted to levy on the expenditure on vehicle use.

P. Varaiya. First, the need to manage roadways better is becoming more urgent. Better management requires more comprehensive data. Most transportation authorities do not place a high priority on data collection and storage. Second, the tradeoffs between trips by private vehicle, public transport, teleworking, etc. are poorly understood, so it is difficult to influence people's choices by a judicious choice of incentives and charges. We urgently need to address both of these: better data collection and more reliable models of choice. Third, transportation investments are large and have a very long gestation period. At least in the USA, the investment process is inflexible, that is, once set in motion, it is very difficult to change or adapt to a changed environment. We need to create an investment design process that is much more nimble and builds in it an ability to change previous decisions.

Next to be mentioned are some comments on Levinson & Odlyzko (2008): the main point of this paper is that charging a per-use price for goods with a high fixed cost may be inefficient owing to (i) under-consumption and (ii) under-production. It causes under-consumption because the per-use price will exceed the marginal cost. Under-production is another effect because the signal that there is high (latent?) demand is not generated by a reduction in actual demand due to the (higher than optimal) per-use charge. Thus, the authors argue, it is better in such instances to charge a flat-rate fee, with the resulting zero marginal consumption cost leading to much higher usage, which, presumably, is socially desirable. The authors imply that more voice call minutes are socially better because they play a key role in human interactions, and because the increased usage visible in table 1 of Levinson & Odlyzko (2008) represents people doing what comes naturally to them. But this is unconvincing. I doubt if the authors approve of over-eating and waste evident in places that offer all you can eat for a fixed price. And I am sure they have been annoyed at the banal conversations conducted in a loud voice over a cell phone in public spaces.

The supporting argument is based on anecdotes and simple economic analysis. The relevant anecdotes, taken from bus fares and voice call price structures, show that consumption increases when a per-use charge is replaced by flat fares. This is unsurprising, first owing to the zero marginal cost and second because in the cited examples, the flat rate is chosen precisely to increase consumption, although the latter point is not made in the article. Note that a flat-rate fee creates a subscription or club model, and it is evident that the higher the subscription fee, the lower will be the number of subscribers.

Conversely, the introduction of per-use charge will lower consumption. Thus the authors conclude that the purpose of such charges is less to raise revenue than to discourage use, and infer that this is the aim of the London Congestion Charge. This seems dubious, at least in view of the officially stated purpose of the London charge.

There seems to me a significant difference between the increased consumption of voice calls and bus ridership following the introduction of a flat-rate charge. The increase in bus ridership seems more like a substitution between transport modes, whereas the increase in voice call minutes seems more like an income effect.

D. Wischik1. First, let me thank S. Borst and R. Srikant for their two stimulating talks about scheduling problems in communications networks. I would like to mention a scheduling problem that is somewhat simpler than those we have just heard about, and where the analogy to transport is more direct, but which is still complex enough to pose hard questions.

Figure 2 illustrates an input-queued switch, the piece of silicon at the core of a high-end Internet router. This one has three input ports and three output ports. Data packets arriving at the inputs may be destined for any of the outputs, thus there are nine possible traffic flows, and nine queues to hold packets. At each clock tick, the switch chooses which inputs to connect to which outputs, and it sends packets along the connections. In the left-hand diagram the switch has chosen badly, since it connects input 3 to output 2; but there are no packets waiting there to be sent, so the switch is not operating at full capacity. The key feature is that the switch fabric imposes restrictions on which of the nine flows can be served simultaneously, and the system designer has to pick a scheduling algorithm that chooses which flows get served.

Figure 3 illustrates a four-way roundabout. Here there are 12 different traffic flows, e.g. north to east or south to north. The structure of the roundabout again imposes restrictions on which flows can operate concurrently; for example, if there is a full flow of cars going south to north then no cars can enter from the west. By specifying which lanes must yield, or by adding traffic lights, the system designer picks an algorithm for choosing which flows get served.

The theoretical analysis of scheduling algorithms, in the communications literature, began with Tassiulas & Ephremides (1992). They designed a scheduling algorithm called MaxWeight, which is the ancestor of the algorithms analysed by Borst and Srikant. They also proved that it is optimal, in that if an omniscient scheduling algorithm can meet the total demand then MaxWeight can do so too.

There has been a great deal of practical work on scheduling algorithms for input-queued switches, prompted by the commercial importance of Internet routers and by the practical difficulties of implementing MaxWeight. See for example McKeown (1999). These practical algorithms seem to work well—it would be interesting to understand if there are links with scheduling problems and solutions in transport networks.

There are also several basic questions that are still unanswered, at least in the communications literature.

What scheduling algorithm minimizes average queueing delay?

Which scheduling algorithms work well when the switch is overloaded, in the sense of maximizing the departure rate?

What are good scheduling algorithms for variable-size packets?

This last question must surely have been addressed in the transport world, in which buses and bicycles share the road.

There are exciting new developments in queueing theory for input-queued switches, beginning with the work of Stolyar (2004), who characterized the distribution of queue sizes when one port is heavily loaded. When the entire system is heavily loaded, the MaxWeight scheduling algorithm pushes the vector of queue sizes to a state where it solves a certain optimization problem (Shah & Wischik submitted). A similar result in the setting of flow-level models for Internet congestion control was found by Kelly & Williams (2004). With a better understanding of this sort of optimization problem, we may be able to design scheduling algorithms, which minimize average queueing delay.

What we might call a *teleological description*, i.e. characterizing the outcome of a system as the solution to a well-chosen optimization problem, has been a tremendously useful tool in all areas of communications and transport networks. We are just beginning to understand the role of teleology in scheduling problems. For example, recent work by Bayati *et al.* (2005) reveals links between belief propagation, gradient descent and the MaxWeight scheduling algorithm.

P. Key. There are interesting similarities between transport and communication networks, reflected in certain aspects of the modelling of such networks, and in the cross-pollination of ideas between the fields, particularly from transport to communication networks. For example, both consider flow-level models, and pose certain problems as convex optimizations arising from a utility maximization framework. Indeed, differences between the social optimum and user optimum, and related consequences, such as Braess's paradox, were first enunciated by the transport community and applied later to communication networks. It is also intriguing to see similar controversy and social opposition to economic ideas such as congestion pricing appearing in both arenas.

Both networks cover similar-scale topographies and can be represented by graphs where the graph structure and properties may be similar; for example, communication networks and certain rail networks have small-world properties, meaning that the diameter is small compared with the number of nodes (such as , where *n* is the number of nodes).

But there are differences between the transport and communication networks, particularly if we consider road networks. If we make the naive mapping of packets to cars, then packets are much longer than cars: the current highest speed links in the Internet only have an order of hundreds of packets, and tens of packets on smaller links, in contrast to road networks that have orders of magnitude more (even if we scale the speeds to be comparable). Cars are (usually) driven by rational human agents, who can react to both local conditions and explicit or implicit incentives, and for whom usage functions reflect user preferences. Usage functions that relate to flows between nodes have to be constructed by aggregation. There is usually a large choice of routes between source and destination. In contrast, in a communication network, route choices are limited and packets have limited choice (the network decides). However, a flow has a natural meaning for end-systems; it is also natural to associate a usage with a flow, although packets are generated by a protocol that implies a level of indirection between the rational agent (human user) and consequences of network incentives, which are first interpreted and mediated by the protocol.

In communication networks, wired links have a capacity that is independent of the load, in contrast to road networks, whereas nodes have buffering and introduce inducing queuing delays. There is a clear distinction between physical latency (dictated by the physical properties of the medium of the links and distance) and the delay induced by queuing at the nodes. In the current Internet, the delay caused by buffering is the same order of magnitude as the physical latency, a consequence of sizing buffers in routers in proportion to the bandwidth-delay product, very similar to the road network. But it is far from clear that such large buffers are ideal or even needed for performance—having smaller buffers in the core of the network, scaling as the square root of the capacity, or even much smaller as others have proposed, would allow negligible queuing delay leaving just the physical latency. This would create a low-delay Internet, with buffering and the temporal effects of congestion moved to the edge. It is difficult to see how a similar scheme could be translated practically to a road network.

K. Briggs. Several speakers made the point that, with regard to road congestion charging, not just the monetary value but also the degree of inconvenience to the payer is significant. There is a parallel here to internet charging, which does not have to be per byte at the transport layer, as often assumed. Some anti-spam proposals, for example, envisage causing a ‘computational charge’ to the sender's computer, so that sending emails is effectively more expensive, even though no money changes hands.

R. Srikant. Many communication network problems, such as scheduling problems in high-speed switches and wireless networks, are combinatorial in nature and have to be solved in real time. Are there similar problems in road traffic theory?

P. Varaiya. *Reply*. The answer is yes and one such example is the traffic light activation problem in city streets. Imagine a long two-way street with traffic lights and cross-traffic from intersecting streets. The problem of dynamically changing the traffic light from red to green and vice-versa is a very complex combinatorial optimization problem that has to be solved in real time based on traffic conditions.

A. Odlyzko (*Department of Civil Engineering, University of Minnesota, USA*). There are many similarities between transport and communication networks, and many lessons that can be carried from one area to the other. But it is also important to keep in mind the important differences that exist. In particular, transport networks have well-known negative externalities associated with them, such as destruction of neighbourhoods, pollution, exhaustion of fossil fuels and the like. As a result, the main incentives in transport are to limit usage. Furthermore, even in the absence of limits on capacity of networks, usage would probably not grow too fast.

In contrast, in communication, capacity is generally easy to increase, at least for the demand growth rates experienced by us. (This varies, clearly, depending on whether one is considering landlines or wireless, and local versus long-haul transport.) Moreover, it can be done in ways that are mostly invisible to the population, and so they do not stimulate the same kind of opposition as road transport. Hence it can be (and has been) argued that the main incentive for communication service providers is to increase usage. That calls for policies very different from the limits on usage which transportation is usually regarded as requiring.

G. Raina (*Statistical Laboratory, University of Cambridge, UK*). The tail end of the Royal Society meeting had a general discussion on the linkages between communication and transport networks. In both these systems, one is often faced with design trade-offs, at a high level perhaps between efficiency and fairness. Let me motivate a specific example.

In the mathematical modelling of rate and congestion control, one strand of research effort has been a framework that allows a congestion control algorithm such as Jacobson's Transmission Control Protocol (TCP) to be interpreted as a distributed mechanism solving a global optimization problem. The framework is based on fluid models of packet flows, and the form of the optimization problem makes explicit the equilibrium resource allocation policy of the algorithm, which can often be restated in terms of a fairness criterion, such as proportional fairness or max–min fairness, for example, see Srikant (2004). Also see the survey paper by Kelly (2003), which discusses a few different models for rate control and analyses their fairness and efficiency properties. On the issue of ramp metering in road networks, there also appears to be interest in the balance between efficiency and fairness. One often comes across papers with interesting titles, such as Kotsialos & Papageorgiou (2001) and Zhang & Levinson (2005).

Of course, both efficiency and fairness could be context driven depending on the application area under consideration. The issue of ramp metering is a very topical one and P. Varaiya's talk centred on it. I wonder if there already exists an accepted unified tractable framework to explore these tradeoffs for ramp metering and the extent to which the above papers inform the reader on the current debates.

## Footnotes

One contribution of 16 to a Discussion Meeting Issue ‘Networks: modelling and control’.

↵Damon Wischik is supported by a Royal Society University Research Fellowship.

- © 2008 The Royal Society