H. On the Space and Traffic Problems of Interval Routing

HKU CSIS Tech Report TR-97-10On the Space and Traffic Problems of IntervalRoutingSavio S.H.Tse and Francis uDepartment of Computer ScienceThe University of Hong Kongsshtse,fcmlau@cs.hku.hkMay1997AbstractInterval routing is a space-efficient method for point-to-point networks.This paper addresses two problems with interval routing schemes(IRS’s)thatare optimal—i.e.,all the routing paths are shortest paths.Thefirst is a spaceproblem.With up to one interval label per edge,the method has been shownto be non-optimal for arbitrary graphs,where optimality is measured in termsof the longest(routing)path in a graph.In this paper,using a non-planargraph,we prove that even with a relatively large number of labels,intervalrouting still falls short of being optimal for arbitrary graphs.The bound onthe longest path we prove is,independent of any number of labelsup to,where is the diameter of the graph and the number ofnodes.The second problem with optimal IRS’s is that of traffic imbalance,which may occur among the edges of certain nodes.We illustrate this usingthe multiglobe graph.If the requirement on shortest paths can be relaxed,weshow that it is possible to derive an IRS which uses as little as four labels peredge and which balances the traffic at every node.The length of the longestpath due to this IRS matches a known lower bound for the multiglobe graphwhich is valid for as many as labels.Correspondence:u,Department of Computer Science,The University of Hong Kong,Hong Kong/Email:fcmlau@cs.hku.hk/Fax:(+852)25598447.Preliminary versions of parts of thispaper have appeared in Proc.CATS’97(Sydney,Australia)[16].11IntroductionInterval routing was first proposed by Santoro and Khatib [12],and subsequently refined by van Leeuwen and Tan [10].The idea is to label the nodes by integers (called node numbers)from a cyclicly ordered set,say,,where is the number of nodes;and the edges by intervals of the form ,where are node numbers.is the set if ,or if .is the short form for ,i.e.,the set .During routing,a message is routed along an edge whose interval label contains the destination node number,until the message reaches the destination.An example of interval routing is shown in Figure 1.The figure shows the routing path of a message that travels fromnode43a message destined for Node 0Figure 1:An example of interval routing2to node 0.The message first takes the edge to node 3because 0is contained in the interval ,and then takes the edge to node 4because is contained in ,and so on.Clearly,with interval routing,at most space is needed at a node,where is the node’s degree.In general,is smaller than ,the size of the network,and we say that the routing information stored at a node as required by interval routing is “compact”.See the survey by Tan and van Leeuwen [13]for an overview of the field of compact routing.One of the main questions in interval routing research is that given ,how to label its nodes and edges so that all the routing paths are shortest paths,where represents either a specific kind of graphs or arbitrary graphs (general networks).A successful labeling satisfying the condition constitutes an optimum interval rout-2ing scheme(IRS).For a number of specific graphs,optimum IRSs are known to exist [13].What about arbitrary graphs?Ruˇz iˇc ka answered this in the negative way by constructing a graph that has no optimum IRS[11].What then can be done if indeed no optimum IRS exists for a given network? One possibility is to relax the compactness of routing information by allowing more than one interval label to be associated with an edge.An IRS that allows up to labels per edge is called an-label IRS,or simply-IRS.Figure2shows a graph which has no optimum1-label IRS,as proved by Fraigniaud and Gavoille[3],but has optimum IRS if up to two labels per edge are allowed.One such optimum 2-IRS for the graph is shown in thefigure.3Figure2:A circular-arc graph and its optimum-IRSBecause of the existence of graphs like the one just shown,multilabel interval routing has become an interesting branch of interval routing research.The central theme is tofind a good trade-off between routing information storage(in terms of number of labels per edge)and the path lengths.In[6],Gavoille and Guˇe vremont proved that at least labels per edge are needed for shortest-path interval rout-ing in some general networks.In[4],Fraigniaud and Gavoille proved a stronger result—a total of bits are necessary for any shortest path routing in general networks.If all shortest paths are to be encoded as routing information,Kranakis, Krizanc and Urrutia proved that a total of bits would be necessary for general networks[8].It appears that for general networks,shortest-path routing is costly in3terms of space.Moreover,Flammini,Gambosi and Salomone have proved that the problem offinding minimum number of labels for shortest-path routing in general networks is NP-hard[1].In practice,it might not always be necessary to insist on shortest-path routing, as long as the paths are not too far from the optimal.Santoro and Khatib have proposed an algorithm that can label any graph to yield paths whose lengths are at most two times the graph’s diameter[12].Instead of considering all the paths,we could look at just the longest path which is commonly used as a performance indicator in many analyses.In shortest-path routing,the longest path equals the diameter of the network.In other cases,it is useful to establish a lower bound in terms of the network’s diameter on the longest path.This bound can then be used to determine the goodness of any rout-ing scheme to be applied to the network.For1-IRS,Ruˇz iˇc ka,using some planar graphs,proved a lower bound ofon the longest path in general networks[11].1Using some similar,but non-planar graphs,Tse and Lau improved this bound to,where forand for[18].For-IRS,,Tse and Lau proposed in[14]two lower bounds that are based on planar graphs on the longest path—andfor-label IRS,where is from to,and from to, ing non-planar graphs,Tse and Lau proposed in[16]two lower bounds on the longest path—and for-label IRS,where is from to,and from to,respectively.Recently,Kr´aˇloviˇc et al.improved the lower bound to for-IRS where is from to[9]. And soon after,Gavoille extended this lower bound to for to ,where is the diameter of the graph[7].These various results form a spectrum,as shown in Figure3.An extension of the spectrum to for large values of,,was derived in[15].The extended spectrum has the bound for-IRS,where is from to,.We adopt the trivial bound of for number of labels from to,Interest-ingly,only one upper bound exists,which is the upper bound for1-IRS due 1His proof has a minor problem which was corrected by Tse and Lau[17].4M)number of labelsFigure3:Spectrum of lower bounds on the longest path(not to scale).to Santoro and Khatib[12].This bound is sufficiently close to the corresponding lower bound of or.Referring to Figure3,the performance of interval routing seems to increase as more labels are allowed.But more labels means that more storage space is requiredin the routers.A good routing scheme should try strike a good balance between the various factors contributing to the success of the scheme.In this paper,we addressthis issue of tradeoff.Wefirst give,in Section3,the proof of a new lower bound onthe longest path for-IRS,where is from to(refer to Figure3).This segment of the spectrum is significant because it represents“reasonable”amountof space apart from the-label scheme.The result shows that even with as muchas labels per edge,the longest path is still some50%longer than the opti-mum.Apart from space and length of routing paths which are important factors,thereis the factor related to the balancing of traffic.An unbalanced traffic situation, where packets could become clotted,is detrimental to the overall performance ofthe routing function.Section4deals with this issue.We introduce a measure calledtraffic load ratio and apply it to a special kind of graphs.We show that if shortest-path routing is to be insisted on,the result would be unbalanced traffic(indicatedby a large traffic load ratio)in various spots of the network.However,by slightly5relaxing the requirement on the path lengths,we can derive an IRS that on the one hand can achieve balanced traffic and on the other hand uses very little space(four labels per edge)for routing information.2PropertiesThe network in question is a connected graphs,,where is the set of nodes,and the set of the edges.Every edge in is bidirectional.There are nodes in.To implement interval routing,each node is labeled with a node number,from the set.Every edge in each direction is labeled with interval labels,each of the form ,where.For that are directly connected,denote the interval labels for the edge that goes from to.For convenience,we use as a short-hand notation for.A node is said to be contained in if(1)for,or(2)or ,otherwise.We use the notation,to denote the cyclic ordering of node numbers,for.Naturally,.As in[18],the expression means that and are contained in some interval and that they are ordered after and before,but the order of and is not shown.Property1(Completeness)The set of interval labels for edges directed from a node is complete.That is,every node in must be contained in one of’s interval.Property2(No ambiguity)The interval labels for edges directed from a node are dis-joint.That is,for,is contained in exactly one of these intervals.Property3(No bouncing)For each,there exists no node,such that is contained in both and.It should be noted that these properties are necessary but not sufficient for a valid IRS.A valid IRS is one that can route a message from any node to any other node.For-IRS(),Property2seems to be unnecessary for the set of labels that are associated with the same outgoing edge.It seems,however,not practical to have multiple such labels that are overlapping,for they should be combined into6a single label,thus saving some space.In fact,an-IRS allows a stronger kind of disjointness for the multiple labels associated with an edge—that is,there could exist a gap between the labels’intervals such that they cannot be concatenated to form a single interval.This property is vital in the proof of the lower bound in Section3.3A Lower BoundThe following two facts will be used in the main proof.Fact3.1Given objects,the number of ways to partition them into two equal-size groups is.Fact3.2Among all the different ways of partitioning objects that are arranged in a circle into two equal-size groups(each of size),there is one by which all the objects in the same group will not be neighbours in the circle.We are going to construct the graph based on which we will derive our lower bound.Define which is of sizeand of diameter for,where and are as follows.ForFor7Figure4:The graph8Where,and represents the-th way,among all possible ways,of partitioning the set into two groups—in one group,and in the other group.There are“flaps”,whose roots are the nodes,and within eachflap, columns and layers.An example of the graph,,is shown in Fig-ure4.This particular graph,,has sixflaps(rooted at the nodes), and within eachflap,two columns and ten layers.The subscripts are used to denote theflap,the column,and the layer,respectively.Note that the’s are connected toflaps and the’s are connected to the remainingflaps.In every layer,we partition theflaps into two groups, each group havingflaps connected to either the’s or the’s.By Fact3.1, there are different ways of partitioning.Therefore,we need() layers in the graph,each of which represents a different way of partitioning theflaps.We can now prove the lower bound.Theorem3.1There is a graph such that for any valid-label IRS,the longest routing path will be no shorter than.Proof:Assume the contrary that there exists an IRS for such that the longest path is shorter than.By the definition of,for all,the-th,the-th,...,and the -thflaps are connected to’s and the-th,the-th,...,and the -thflaps are connected to’s.For all,it must be the case thatand;otherwise, if,then by Property1,,and the length of the path from to through the edge would be at least.Hence,for all,In each of the above,since elements are contained in interval labels,by the pigeon-hole principle,one of the intervals contains at least two elements.In fact,9by Property2,we canfind two such elements in one interval such that none of the other elements fall between them.Since all the different ways of partitioning (which are in a cycle ordered by“”)are represented by the layers,by Fact3.2,there exists one way of partitioning in which all the elements in either partition are not neighbors in the cyclic order.This contradicts the previ-ous statement concerning two elements being in the same interval and none of the other elements are in between them.Note that the proof is valid even if the edge and have fewer than labels(such as when some of the labels are not disjoint).For such cases,we can use fewerflaps to achieve the same lower bound.This shows the power of having (strong)disjoint labels(refer to Section2),which forces the graph to be of the size as has been shown.Corollary3.1There is a graph where and is any constant, such that if the longest path is less than,the number of labels per edge is at least .Proof:Clearly,when,and when.4Traffic Balancing and the Multiglobe GraphIn this section,we present the problem of traffic imbalance due to shortest-path routing,and then a solution(an IRS)to the problem.The solution trades path lengths for balanced traffic at every node.The graph we use is known as the10multiglobe graph[9].For this graph,Tse and Lau proved a lower bound on the longest path of for number of labels up to,where is the number of nodes[16].Kr´aˇloviˇc et al.proved a similar result,of,for IRS’s using labels per edge,where is the number of edges.The IRS we are propos-ing in this section uses up to four labels per edge,produces paths that are of length not longer than(thus matching the lower bound on the longest path),and balances the traffic for every node.As we can see,there are all the advantages to not insisting on shortest-path routing.The multiglobe graph,,is as shown in Figure5.It is parameterized by,the number of layers,,the number offlaps,and,the number of columns(of nodes) within aflap.The indexing of the layers,theflaps,and the columns are as shown in thefigure.We refer to the nodes that are within a layer and aflap as a chain.Figure5:The skeleton of.has diameter and size.and are as follows.Theflaps are rooted at the nodes,respectively.We will use sub-scripts for indexing the layers,theflaps,and the columns,respectively.Given11a node,say,we use to denote an edge of this node that points towards the center()of the graph,and to denote an edge that points towards the tip() of aflap.Note that when referring to a node or edge,we may omit some of its subscripts(for simplicity in notation)if the missing subscripts can be inferred from the context.And we use to denote the label or labels of,where can be a node,a set of nodes,an edge,or a set of edges.4.1The Traffic ProblemSuppose we apply shortest-path routing to the multiglobe graph.Consider the node,for any.There are betweenand paths originating from that would go through the edge,and the remaining paths would go through the edge.Hence,we have a ratio of between the the two edges in terms of expected traffic load—which is in the worst case.2That means that this node,,could become a bottleneck during operation.As we move towards the center()or the tip(),the situation improves.In particular, under shortest-path routing,the traffic load among the edges of is perfectly balanced;so is that of.We define traffic load ratio of a node to be the largest ratio ()between the traffic loads of any pair of its edges,where the traffic load of an edge is the number of paths originating from this node that would go through the edge.A ratio of means that the traffic is balanced.In the following,we give an IRS which is non-optimal in terms of the length of its paths,but which leads to balanced traffic(traffic load ratio=)at every node.The length of the paths is bounded by which meets the lower bound on the longest path for the multiglobe graph for as many as or labels. Surprisingly,our IRS uses not more than four labels per edge.Hence,our labeling is optimal for this range of number of labels,even though the paths it generates are not shortest paths.2Let be a constant,and and be.124.2A Traffic-Balanced-IRSLet and.A chain is seen as comprising two subchains:a (tail)subchain consisting of the nodes,and an(head)subchain consisting of the nodes.The lengths of these two chains differ by at most one.We partition into a set of subgraphs,and,as follows.For every layer(),consists of all the subchains in that layer and the node.For everyflap(),consists of all the subchains in thatflap and the node.Note that every subgraph,or,is a tree.We label the nodes by traversing the trees one after another:1.For,perform depth-first traversal for the subgraph rooted at.2.For,perform depth-first traversal for the subgraph rooted at.The traversal labels the nodes in sequential order:thefirst node visited is labeled ,the second,and so on.Figure6shows an example of with,,and .Figure6:An example of and its node-labels.The following are true of the labels thus produced by this labeling scheme.13For the subgraphs:.Within an subgraph:.Within a subgraph:.Within an subchain:.Within a subchain:.For simplicity,we assume that is odd.The case where is even differs in a very minor way.Lemma4.1If for any and,contains and,and contains and,then the routing path of any valid IRS from or will not exceed .Proof:The routing paths from to and are shortest paths;so are the routing paths from to and.These paths are bounded by.Then,consider the routing from to,.The routing willfirst go to some,and then take the shortest route from to the destination in.Hence,the total length will not exceed.The routing from to,is similar.Lemma4.2Given a valid IRS,for any,and,if contains,,and contains,,then the traffic load ratio of is equal to.Proof:The number of nodes that are contained in is at least,and that in is at least. Since,the traffic load ratio is,which is.We can now label the edges.The following is for any node.1.For any,and,contains(a),.14(b)if,if,orif.2.And contains(a),.(b)if,if,orif.Lemma4.3Given the above labeling of nodes and edges,and assume that contains all and for any,and contains all and for any,then for any,(1) four labels per edge is sufficient,(2)its edge-labels satisfy the completeness property,(3)its edge-labels satisfy the disjointness property,(4)the paths originating from are bounded by,(5)its paths have no cycle,and(6)it has a traffic load ratio of.Proof:(1)For,and can each be covered by one label;one label is enough to cover each of and;and one or two labels to cover.Hence,four labels suffice.Similarly for.(2)and(3)by simple inspection.(4)Since contains and,andcontains and,the argument is the same as that for Lemma4.1.(5)Any cycle will have a length of at least,which contradicts the last.(6)Di-rectly from Lemma4.2.Lemma4.3depends on the labeling of the nodes and.Consider the routing from some.The following is true because of our node labeling scheme.15Denoting each of the above intervals,except,by,we haveThere are all together’s.To balance the traffic,we divide them among the edges of:thefirst’s to thefirst()edge,the next’s to the second()edge,and so on.Similarly,consider the routing from;we havewhere,,etc.There are all together’s to be distributed among the edges of:thefirst’s to thefirst()edge, etc.The following is the labeling scheme for and.1.,contains(a),(b),and(c).2.contains(a),(b),and(c).Lemma4.4Given the above labeling scheme for and,for any or,(1)four labels per edge is sufficient,(2)its edge-labels satisfy the completeness property,(3)its edge-labels satisfy the disjointness property,(4)the paths originating from are bounded by,(5) its paths have no cycle,and(6)it has a traffic load ratio of.16Proof:Similar to that of Lemma4.3.For(1),note that two intervals will be neces-sary to cover if happens to fall inside them.By Lemma4.3and Lemma4.4,we have the following.Theorem4.1There exists a-IRS for such that the traffic load ratio of every node is and the longest path is of length.We close this section by giving the edge-labels of a few selected nodes in the example in Figure6.They were generated based on the labeling methods given above.Node Edge LabelsAs shown,the number of labels is between and.The traffic load ratio for these nodes are,,,,respectively,all very close to.These ratios, however,are not much different from those of a shortest-path IRS applied to the same graph,simply because the graph in Figure6is relatively small in size and has too few layers.For larger graphs with more layers,the difference would be much greater.175Discussion and ConclusionTheorem4.1reveals that it is not necessarily true that by increasing the number of labels,the length of the longest path is reduced.Between four labels and labels,the lower bound on the length of the longest path for the multiglobe graph, ,remains unchanged.It is interesting to note on the other hand,that increas-ing the number of labels will certainly bring about a reduction in the average path length,as demonstrated below.Theorem5.1Given an arbitrary graph and an-label IRS applied on the graph,if there is a non-optimal routing path from to,then there exists an-label IRS which can replace the path with an optimal one,while not perturbing any of the other paths.Proof:Suppose the shortest path from to is,where and .For,if does not contain,add to ,and remove from the interval(of another edge of)that contains it.Let this latter interval be.The removal might split into two disjoint intervals.As a result,one interval is added to,and might become two intervals.After all the adding and removing along the shortest path,we have an-IRS which provides an optimal routing path from to.This paper opens a new avenue for interval routing research:the derivation of interval routing schemes that can balance traffic.One could try to identify graphs or properties of graphs that are most prone to traffic imbalances under interval routing.In Section4,we defined traffic balance as an attribute of a node,which is in terms of routes that originate from the node.In real operation,other routes may pass through this node and hence add to the traffic load of this node.A more accurate measure would consider all routes,whether originating from this node or not.Consider Figure3.The lower bound results that are based on non-planar graphs appear to be a constant function.It might be worthwhile to try to replace this by a decreasing function.The segments beyond for,and beyond for are still missing a non-trivial bound.18The tightness of these existing lower bounds for-IRS()is not so clear as there are no upper bounds to match.So far,the longest-path analysis and the shortest-path analysis both focus on the worst case.Practically,longest-path analyses is not as significant as average-path analyses.The traffic burden of one longest path is not really that great if most of the other paths are close to being longest.In other words,the lower bound on average-path length is more important than the lower bound on longest-path length.The average-path analysis is expected to be more complicated;the technique of counter proof can no longer be used,and random graphs,or statistical analysis techniques will have to be used instead.References[1]M.Flammini,G.Gambosi,and S.Salomone,Interval routing schemes,Proc.12th Annual Symposium on Theoretical Aspects of Computer Science(STACS’95), 279–290,1995.[2]M.Flammini,G.Gambosi,U.Nanni,and R.Tan,Multi-Dimensional IntervalRouting Schemes,Proc.the9th International Workshop on Distributed Algorithms (WDAG’95),1995.[3]P.Fraigniaud and C.Gavoille,Interval Routing Schemes,Research ReportNo.94-04,Laboratoire de L’Informatique du Parallˇe lism,Ecole Normale Supˇe rieure de Lyon,France,1994.To appear in Algorithmica.[4]P.Fraigniaud and C.Gavoille,Universal Routing Schemes,Journal of Dis-tributed Computing,10:65–78,1997.[5]P.Fraigniaud and C.Gavoille,Local Memory Requirement of Universal Rout-ing Schemes,Research Report No.96-01,Laboratoire de L’Informatique du Parallˇe lism,Ecole Normale Supˇe rieure de Lyon,France,1996.[6]C.Gavoille and E.Guˇe vremont,Worst Case Bounds for Shortest Path IntervalRouting.Research Report No.95-02,Laboratoire de L’Informatique du Par-allˇe lism,Ecole Normale Supˇe rieure de Lyon,France,1995.19[7]C.Gavoille,On Dilation of Interval Routing,Research Report RR-1145-96,LaBRI,University of Bordeaux,France,November1996.[8]E.Kranakis,D.Krizanc,and J.Urrutia,Compact Routing and Shortest PathInformation,Proc.2nd Colloquium on Structural Information&Communication Complexity(SIROCCO’95),101–112,1995.[9]R.Kr´aˇloviˇc,P.Ruˇz iˇc ka,D.ˇStefankoviˇc,The Complexity of Shortest Path andDilation Bounded Interval Routing,Technical Report,Department of Com-puter Science,Comenius University,August1996.[10]J.van Leeuwen and R.B.Tan,Interval routing,The Computer Journal,30:298–307,1987.[11]P.Ruˇz iˇc ka,A Note on the Efficiency of an Interval Routing Algorithm,TheComputer Journal,34:475–476,1991.[12]N.Santoro and R.Khatib,Labelling and Implicit Routing in Networks,TheComputer Journal,28:5–8,1985.[13]R.B.Tan and J.van Leeuwen,Compact Routing Methods:A Survey,TechnicalReport RUU-CS-95-05,Dept.of Computer Science,Utrecht University,1995.(Also in Proc.Colloquium on Structural Information and Communication Complex-ity(SICC’94),99–109,1994.)[14]S.S.H.Tse and u,Some Lower-Bound Results on Interval Routing inPlanar Graphs,Technical Report TR-97-05,Department of Computer Science, University of Hong Kong,April1997.(Preliminary version:Lower Bounds for Multi-label Interval Routing,Proc.2nd Colloquium on Structural Information& Communication Complexity(SIROCCO’95),123–134,1995.)[15]S.S.H.Tse and u,On the Space Requirement of Interval Routing,Technical Report TR-96-11,Department of Computer Science,The University of Hong Kong,1996.[16]S.S.H.Tse and u,Two Lower Bounds for Mult-Label Interval Rout-ing,Proc.of Computing:The Australasian Theory Symposium(CATS’97),Syd-20ney,Australia,February1997,in Australian Computer Science Communication, 19(2):36–43.[17]S.S.H.Tse and u,More on the Efficiency of Interval Routing,Tech-nical Report TR-97-04,Department of Computer Science,The University of Hong Kong,March1997.[18]S.S.H.Tse and u,An Optimal Lower Bound for Interval Routing inGeneral Networks,Technical Report,Department of Computer Science,The University of Hong Kong,June1997.21。