Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 1 of 31
`Case 1:16-cv—02690-AT Document 121-9 Filed 08/05/16 Page 1 of 31
`
`D-4
`
`D-4
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 2 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 2 of 31
`
`
`
`
`Thanom‘rtryeudom
`
`Hierarchical routing
`for large
`I networks
`
`Performance evaluation
`and optimization
`
`Leonard Kleinrock and Farouk Kamoun
`Computer Science Department. University ofCollfornt‘o.
`tor/Inset“. CA 90024. U544.
`
`Distributed adaptlve routing has provost to be useful in
`packet switching networks. However. the storage and updsl-
`in; cast of this routing prowdrtre becomes prohibitive as the
`min-ten of nodes in the network sets large. This paper deals
`with the specification. analysts and evaluation of some hier-
`archical routing procedures which are etreetive [or large
`amend-Inward packet-switched computer networks. The
`procedures studied are an extension or present techniques
`and rely on a hierarchical clustering of the network nodes.
`In particular. optimal clustering structures are determined so
`st to mlnimhe the lenth of the routing tables required. A
`price for reduolra the table length is the increase In the aver-
`age message path length in the network. Bounds are derived
`to evaluate the maximum increase in path length for a given
`on]:
`length. From this we obtain our key remit. namely.
`that in the limit of a very large network. enormous tabla
`reduction may be achieved with essentially no increase In
`network path length.
`
`Keywords: Pscket switching. networks. computer not-
`worltr, large networks. data networks. hier—
`archical dam. routing. ares rot-sting. adap-
`tive routing. clustering. partitioning.
`
`
`
`©hlorth-l'lolland murmur; Company
`Computer Networks l (1971') 155—114
`
`I. Introduction
`
`Computer networks offer large economies through
`resource sharing. Among such resources we include
`specialized hardware. specialized software and data
`banks. These distributed computer communication
`systems made their first appearance in the form of
`packet switching wilh the ARPANET [2.5.l2.l7.
`'27}. The llrst commercial data carrier. TELENET
`[29}. is already operational. The basis ol this demand
`for computer networks is the ever increasing need
`for computer and data communication power.
`Communication among the network resources is
`accomplished by the communication subnetwork.
`This includes the hardware and software specifically
`dedicated to the transfer of data from node to node.
`Many alternative communication schemes can be
`implemented at the subnet level. Among these are:
`circuit switching I26). packet switching (a form of
`
`
`
`Leonard Kletnroch ls Professor of
`Computer Science at the University
`01' California. Los Angela. He
`received his B.E.E. at the City Col-
`ene ol New York in I95? and his
`M31211. and Ph.D.E.E. at the Massa-
`chusetts Institute of Technology in
`I959 and 1963 respectively. In I963
`he joined the faculty of the School ol'
`Engineering and Applied Science at
`the University of California. Lot
`Annalee. His research spans the fields
`or computer networks. computer systems modelin and anal-
`ysis. queueing theory and resource sharing and al ocation in
`general. At UCLA. he directs a large group in advanced tele—
`processlns systems and computer networks.
`He serves as consultant in: many domestic and foreign
`ool'pwellons and overs-intents and he is a referee for numer-
`ous scholarly pn leations and a hook reviewer for several
`publishers. He was awarded a Guggenheim Fellowship for
`Will—1972 and is an IEEE Fellow "for oontrllsulions in
`computes-communication networks.
`noticing theory. time-
`rhsrod systems.arut engineer-ins edueaaon."
`anuk ltemoun was born in Start.
`Tunhla on October 20. 1946. He
`reached the
`arlngDe eet'rom
`Boole Superkure d‘Electrl
`te' Par-la.
`France in 1910 and the M5. and
`Hal). degrees in computer science
`from the University ol' Callt'urnh.
`Los Angeles.
`in I912 and 1916.
`respectively. From l9?3 to 1976 he
`was with the University or California.
`hos Annalee. where he participated In
`the ARPA Network Project as a 90st-
`ysdnate Research Engineer and did research on design eon-
`slderarlons for large computer mmn‘umkxtlon networks. Ho
`s. on
`'ils‘updnrrgintl
`teaching at the Boole Nationale d'lngenieurs do
`This research was at:
`ted by the Advanced Research
`Projects Agency of The
`tment of Defense under Con-
`lnct DAHC lS-‘l3-C036ll.
`
`
`
`.
`
`
`
`
`
`i
`
`l
`4
`
`“a
`‘
`
`°
`'
`
`.
`l
`
`a typical design.
`. tion which satis-
`
`determinlng the
`
`controller delay
`omponent shall
`1 the response
`llllzatlon corre-
`eeoond divided
`e transactions'
`cation is then
`r the same 24.
`of terminals can
`.b corresponding
`the 90th Pep
`second (03 +
`
`ss
`
`.
`ienei'iclal when
`llcularly in the
`fictive solutions
`int can be used
`lummunlcatlon
`883ml}-
`.pwing the pro-
`: can be can.
`he of a simple
`a nomograph
`indenting of
`mightforward.
`
`[ohn my and
`l
`
`Remission .
`
`AnalysisofA
`9| Annual
`l March 1914.
`
`e a
`
`1
`
`

`

`_,
`
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 3 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 3 of 31
`
`
`
`L. Kleinmck. F. Karrmurr
`
`Hierarchical routing for
`
`field indicates the es
`1' to destination not
`cates the next node
`on its way to node
`delay path. The "hr
`number of line hop
`hop-field is to allovt
`the network.
`Each node perir
`sec in the ARPANE
`
`per sec line} sends :
`neighboring nodes;
`chronlzed among r
`date. a node updatr
`delays measured 0
`information found
`ple of an updatini
`To summarize.
`operation of the di-
`is the storage. mat
`ing of routing tab
`that
`in such schen
`must contain a nu
`ber of nodes in the
`Since the leng
`directs the traffic
`
`early (one entry pt
`we see that for larg
`of many thousanr
`to contain this Ii:
`
`costly. Also. as a
`table lengths. the r
`mation among the
`will represent a sip
`tlon lines themsel
`that some for-m
`length is called in
`schemes which 5
`McOuillan [22] p
`evaluate their pert
`
`2. Hierarchical r-or
`
`The main ids
`length is to kee
`information abor
`terms of a hop di
`sure). and lesseri
`ther away from i
`one entry per de
`
`156
`
`radio
`“6,18]
`storeand-fonvard communication)
`broadcasting [1}. satellite communication [20]. or
`any combination ofthe above,etc.
`The selection of the best switching scheme is a
`difficult problem and depends very much on the
`nature of the traffic to be handled by the network
`[3.4.24]. The burst nature of computer traffic. as
`well as the continuously decreasing cost of computer
`hardware [28]. very much favor packet switching as
`the technology to employ.
`The basic concepts for and the first implementa-
`tion of a packet switching computer network were
`developed by the United States Department of
`Defense Advanced Research Projects Agency (AREA).
`This network (the ARPANET), in operation since
`I969. has been an enormously successful demonstra-
`tion of the packet switching technique. It has result-
`ed in the development of a multitude of other net-
`works
`throughout
`the world (EPSS in England.
`CYCLADES and TRANSPAC in France, DATAPAC
`in Canada, EN in Europ, TELENET and AUTODIN
`I! in the USA,etc.)
`Present computer networks may be characterized
`as small to moderate in size (5? nodes for the AR!“-
`NET as of December 1975). Predictions indicate that.
`in fact. large networks of the order of hundreds (or
`even possibly thousands) of nodes are soon to come.
`In the course of developing the ARPANET. a
`design methodology has evolved which Is quite suit-
`able for the efficient design of small and moderate
`sized networks [6.8.18]. Unfortunately the cost of
`conducting the design is prohibitive if these same
`techniques are extrapolated to the case of large net-
`works [14]. Indeed, not only does the cost of design
`grow exponentially with the network size. but also
`the cost of a straightforward adaptive routing proce-
`dure becomes prohibitive. Other design and opera—
`tional procedures (routing techniques) must be found
`which handle the large network case. Our main objec-
`tive in this paper is to specify and evaluate routing
`policies for LARGE networks.
`
`Routirtg for packet sir-itchingr networks
`
`In a packet switching network, messages are par-
`titioned into a number of mail segments called pack-
`ets which then are transmitted through the network
`ung sloreand-forward switching. That is. a packet
`traveling from source S to destination Dis received
`and "stored" in queue at any intermediate node K
`while awaiting transmission. and is then sent “for-
`
`ward" to node P. the next node on the route froan
`to D. when channel (KI) permits.
`The selection of the next node P is made by a well-
`delirted decision rule referred to as the routing policy.
`Several classification schemes have been devised to
`characterize routing policies 116.73.21.22]. Gener-
`ally speaking. routin'g policies may be divided into two
`main clams: deterministic and adaptive.\’r'hile deter-
`ministic routing is more attractive to use at the design
`phase. adaptive pollcles are essential for the successful
`operation of real networks.
`The major goal of an adaptive routing procedure is
`to sense changes in the traffic distribution and net-
`worlr status and then to ronle messages such that the
`congested or damaged areas of the network are avoid-
`ed. It is very important for those procedures to adapt
`to line and node failures in order to maintain a good
`grade of service for the network. Such policies base
`their decisions on measured values, at given thn'es.ol
`a set of time varying quantities (number of messages
`enqueued. number of hops. etc.) which describe the
`salient features of the state of the network (tralTrc.
`topology. etc.). Such information is referred to as
`routing information. A central node could provide
`the routing information (yielding centralized control)
`and distribute it to all nodes in the network, or the
`nodes could collaborate in computing the routing
`hrfomation directly (yielding distributed control)
`[16.7.13].
`In any case. routing information must. be stored In
`tables at each node and is used to identify the output
`line for each destination.I More detailed classifica-
`
`tions of the routing policies can be found in l?,l0.
`22]. In this study. we limit our considerations to the
`most commonly used adaptive routing policies. name-
`ly, distributed routing policies. These policies base
`their decisions on routing information-contained in
`routing tables individually maintained at each node.
`The tables are updated periodically or asynchronous-
`ly or a combination of both [‘7] using routing infor-
`mation collected iniemally and provided from neigh-
`boring nodes. Such a scheme is used to operate the
`ARPANET [22].
`Typically. in a network with N nodes. each node
`("IMP" tn the ARPANBT terminology) r {i= 1.2.
`.... N) has a Routing Table (to be denoted by RT)
`which is composed of N entries. Each entry.say it.
`is subdivided into three (or more) fields. The “delay”
`
`'We do hereon-trier the casewberepackeucarrythelrm
`routing Information.
`
`
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 4 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 4 of 31
`
`
`
`
`let‘rtroek. F. Kcmmr
`
`Hierarchical routing for large network:
`
`I51
`
`the remote
`one entry per set of destinations for
`nodes. The size of this set may increase with the dis-
`tance. '
`routing in large networks the reduction of
`For
`routing information is realized through a hierarchical
`clustering of the network nodes.
`
`introduce and specify
`follows we first
`In what
`routing schemes and their underlying
`hierarchical
`clustering structures. We
`then observe that non-
`opttmally selected clustering structures may lead to
`very little table reduction. As a result.it is important
`to find optimal structures. This we do by solving an
`optimization problem whose objective is to minimise
`the table length. The optimal solution is found to
`achieve significant table reductions. The ratio (IN. of
`the new table length i. to the one obtained with no
`clustering N. constitutes. in this paper. the unique
`perfonnanoe measure by which we characterize the
`gains obtained from the hierarchical routing. In reali-
`ty. one needs to express those gains in terms of
`recovered nodal storage. line capacity.CPU proces-
`ing. and ultimately in terms of network throughput
`and delay lid]. These last we defer toa forthcoming
`paper [15].
`Unfortunately. the gains in table length are accom-
`panied with an increase of the message path length in
`the network. This results in a degradation of network
`performance {delay-throughput} due to the excess
`. internal traffic caused by longer path lengths. Again
`we defer throughput-delay considerations [14] to a
`later paper. and restrict our study here to the evalua-
`tion of the increase in network path length. After
`further specifications and characterization of the
`hierarchical schemes. bounds are derived to evaluate
`the maximum increase in path length for a given table
`reduction. The bounds demonstrate a key result.
`namely, that
`in the limit of very large networks.
`enormous table reduction may be achieved with no
`significant increase in network path length. In other
`words.
`in the limit. hierarchical routing schemes
`achieve a performance similar
`to present schemes
`with very substantial savings in storage and capacity.
`Finally. we examine the behavior of these bounds
`with respect to the relative table length i/N.
`We now proceed with the description of the hier-
`
`3 A flmlhr concept underlies the mechanism of large infor-
`mation system with pyramidal structures in which infor-
`tlon is more and more aggregated as We move up to the
`higher levels In the hierarchical organhation. Aggregation
`of information or var-tables is commonly inlmduoed when
`dealing with large systems [23.30].
`
`field indicates the estimated minimal delay from node
`i to destination node 1:. The “next-node" field indi-
`cate: the next node a message must be forwarded to
`on its way to node it. along the estimated minimal
`delay path. The "hep" field represents the minimum
`number of line hops to node it. The purpose of the
`hop-field is to allow the detection of node failures in
`the network.
`
`Each node periodically (for example every 0.64
`sec in the ARPANET. for a heavily loaded 50 kilobit
`per set: line) sends and receives update messages from
`neighboring nodes; these updates need not be syn-
`chronized among nodes. Upon reception of an up-
`date. a node updates its own routing table. using the
`delays measured on its output lines and the delay
`information found in the update message. An catam-
`ple of an updating rule is provided in Section 4.2.
`To summarise. we see that. fundamental to the
`operation of the distributed adaptive routing schemes
`is the storage. maintenance, propagation and updat-
`ing of routing tables. Also. it is important to note
`that
`in such schemes. the routing tables apparently
`must contain a number of entries equal to the num-
`ber of nodes in the network.
`
`i i F l
`
`the length of the routing table (which
`Since
`directs the traffic through each node) will grow lin-
`early (one entry per node] with the number of nodes.
`we see that for large computer networks (on the order
`of many thousands of nodes) the storage required
`to contain this list in each node will be extremely
`costly. Also. as a direct consequence of these large
`table lengths. the cost of interchanging routing infor-
`mation among the network nodes will also grow and
`will represent a significant burden on the communica-
`tion lines themsdves. All these considerations suggest
`that some form of reduction of the routing table
`length is called for. Below we present and study some
`schemes which achieve this goal. Fultz I7] and
`MoQulllan [22] proposed similar schemes but did not
`evaluate their performance as we do here.
`
`2. Hierarchical roofing schemes
`
`The main idea for reducing the routing table
`length is
`to keep, at any node, complete routing
`information about nodes which are close to it (in
`terms of a imp distance or some other nearness mea-
`sure), and lesser information about nodes located fur-
`ther away from it. This can be realized by providing
`one entry per destination for the closer nodes. and
`
`the route from S
`
`
`
`
`
`is made by a well-
`the routing policy.
`e been deviated to
`
`7.9.21.22]. Gener.
`
`be divided into two
`
`ptive. While deter-
`0 use at the design
`
`I for the successful
`
`ting procedure is
`ttibution and net-
`ges such that the
`' network are avoid»
`rocedures to adapt
`‘ o maintain a good
`Such policies base
`
`at given times. of
`
`mber of messages
`which describe the
`e network (t raffrc,
`_
`is referred to as
`ode could provide
`enrrnlized control)
`its network. or the
`pting the routing
`‘m'brrreo' control)
`
`thrust be stored in
`dentify the output
`hetailed classifica-
`le found in [7.10,
`asiderations to the
`rig policies. name-
`less policies base
`cion contained in
`fed at each node.
`:or asynchronous-
`ing routing infor-
`-_rlded from neigh-
`ad to operate the
`
`nodes. each node
`an} i (r = i. 2.
`ldencted by RT)
`eh entry. say It.
`lds.The "delay"
`
`ts tarry clack own
`
`t i
`
`i__.
`
`.l
`
`
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 5 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 5 of 31
`
`
`L. Kleinmek. F. Kornoun
`
`Hierarchical rots ring for .
`
`
`
`
`ISS
`
`srchicel routing schemes. Recall that the main objec-
`tive of such schemes is to operate with smaller table
`lengths. The reduction of routing table length is
`achieved through a hierarchical partitioning of the
`network. Basically. an m-level Hierarchical Clustering
`(ml-IC) of a set of nodes consists of grouping the
`nodes (which we shall define as (3“" level clusters) into
`I" level clusters. which in turn are grouped into 2'“1
`level clusters, etc. This operation continues in a bot-
`tom up fashion, finally grouping the m — 2"d level
`clusters into n: — I“ level clusters whose union consti-
`tutes the rut“ level cluster. The in"! level cluster is
`the highest level cluster and as such it includes all the
`nodes of the network. The nil-{C will he described
`more formally below.
`Since hierarchical routing schemes are based on an
`rrr-level hierarchical clustering. they will be denoted
`as mHR schemes. With the mill! schemes. only one
`entry in the routingtable, at any node,say i, is provided
`for each node in the same l“t level cluster as i, and for
`each l”l level cluster (a set of nodes) in the same 2"“
`level cluster as i. and in general for each I: — 1“ level
`cluster in the same 13" level clusteras r' (fr = L2. ..., in}.
`The structure of this scheme can best be understood
`
`by an example. Fig. I shows a 34evel hierarchical
`clustering imposed on a 24 node network. The cluster-
`ing leads to the tree representation shown in Fig. 2.
`where nodes are identified using the Dewey notation
`[19] . To each node we now associate a reduced routing
`table. Fig. 3 shows the layout of node 1.] .l’s routing
`table; the number of entries is now 10 (bistead of 24
`without clustering). As an example, the routing of a
`packet from node 1.1.] to node 3.2.2 may proceed as
`
`
`
`——I—-—-—--I—ul—-I—-—u
`
`l2 (we eliminated or
`of the largest cluster
`construct clustering t
`i close to N(eg.,‘2-
`and the other 3, thus
`Since the routing
`ly related to the tab
`determine those clue
`minimal table length
`2. As we stated
`information genera“
`path length. To illu:
`case where messes!
`considers cluster 3
`messages destined 1
`cluster from the all
`that the entry and
`to 3J3 and 3.1.4
`increases are resPe'
`other hand. if“ 1‘
`inate the above in
`increase the table
`example). Comet”
`tradeoff between 3
`length. Moreover.
`structure. the asst;
`to superclusten. '
`natural groupins t
`application; the la
`in ass panacea I
`Note that the
`propose need no
`structure; indeed
`significant lmP'O‘
`ed network topt
`work topology
`structure as well.
`In summary.
`
`ing two issues:
`i.’l'he detenr
`structure. is" '11
`the number of it
`the routing table
`ii.'['he perft
`schemes (in “'1‘
`son with the pro
`
`3. Minimum rout
`
`in this merit
`lion and Tantra
`
`i. m
`
`Fig. 2. A tree representation ore 34ml clustered net.
`
`follows: Node L] .l recognizes. from the address of
`the destination node 3.2.2. that it has to use entry 3,
`of the 2"“ level cluster entries, to decide upon the
`next node to whlch the packet must be forwarded.
`When the packet reaches a node, say 3.l.l. in the
`2'“I level cluster 3, then that node will in turn use
`the second entry (3.2.2) among the 1" level cluster
`entries. Finally, when the packet enters the destina-
`tion cluster. 3.2. the routing will be done using ll"I
`level cluster entry. number 2 (32.2). (Note that it
`was assumed that the mHC results in connected sub-
`earths-l
`Two remarks emerge from the above considera-
`tions.
`-
`1.1‘he length of the RT at any node is strictly a
`function of the clustering structure, i.e.. it is a func-
`tion of the number of nodes per cluster. number of
`clusters per supercluater. etc., and the number of
`levels.
`In what follows,
`in order to simplify the
`manipulation and implementation of the RT's in the
`network, we assume that eqtuu| length rubles are pro-
`vided at all nodes. Consequently, if t is that length,
`it must acconunodate the number of entries in the
`RT of any node. As a result. the clustering structure
`of Fig. I leads to f= lO.lflnthst same example,“
`merge clusters Li and 1.2, then [becomesequal to
`p
`“a” mm
`iii-m
`Li.‘
`0
`noose In
`1-“
`m“W4“u
`an
`‘-‘~
`manna
`‘1-
`II III!
`oil-amen "I
`i.
`“lam” '-
`a.
`
`a.uvnmum
`
`IIll mmm mm
`
`1" um amen menu
`
`'
`
`.
`
`' I III.’ ENTRY
`
`fig. 1. A 3-level clustered 24-node network.
`
`Fig; 3. Routing table of node LI .1.
`
`
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 6 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 6 of 31
`.
`.__
`.
`.__
`
`
`
`
`Hierarchical routing for large newts
`
` Kkiflmk. F. Kemoan
`
`'.
`'
`
`‘
`I
`
`’
`
`a
`
`
`
`.say 3.1.1, in the
`e will in turn use
`the 1“ level cluster
`enters the destina-
`l he done using 0''1
`{2.2). (Note that it
`s in connected sub-
`'3 above considera.
`
`node is strictly a
`.Le.. it is a func-
`_
`lfluflcr. number or
`d the number of
`
`to simplify the
`‘
`:of the RT’s in the
`will tables are pro-
`!irr Is that length,
`of entries in the
`[uttering structure
`lsarne example, we
`ibecomes equal to
`
`
`
`12 {we eliminated one cluster, but increased the size
`of the largest cluster by 3). Moreover, it
`is easy to
`construct clustering structures which lead to values of
`l close to N (e .g.. 2 clusters, one containing 21 nodes
`and the other 3. thus 1 = 23).
`Since the routing cost (capacity, storage} is direct-
`ly related to the table length, then it is important to
`determine those clustering structures which lead toe
`minimal table length .13., a minimal routing coat.
`in: we stated earlier. the reduction of routing
`information generally leads to an increase in network
`path length. To illustrate this factfiet us consider the
`case where messages must be sent from node 3.2.1
`considers cluster 3.] as a single node. As a result,
`messages destined to any node in 3.1 will enter that
`cluster from the some node (exchange node). Assume
`that the entry node ls 3.1.]: then messages destined
`to 3.1.3 and 3.1.4 will incur longer path lengths (the
`increases are respectively by 1 and 2 hops). 0n the
`other hand, il'we merge clusters 3.1 and 3.2,we elim-
`inate the above increase in path length but this will
`increase the table length (only by one entry in this
`example). Consequently, in general, there will be a
`tradeolT between gains in table length and loss in path
`length. Moreover, given an appropriate clustering
`structure, the assignment of nodes to clusters, clusters
`to superclusters, etc., should take advantage of the
`natural grouping of nodes which exist in a particular
`application; the latter issue, however, is not examined
`in this paper (see [14]).
`'
`Note that
`the hierarchical routing procedure we
`propose need not
`imply a hierarchical topological
`structure; indeed this routing procedure provides very
`signifith improvements when applied to a distribut-
`ed network topology. 0n the other hand. the net-
`work topology itself could include a hierarchical
`structure as well.
`
`in summary, in this paper we address the follow-
`ing two issues:
`i. The determination of an appropriate clustering
`structure. is., the sine of the clusters at all levels and
`the number of levels so as to minimize the length of
`the routing table (routing cost).
`the mill!
`it. The performance evaluation of
`schemes (in terms of path-length) and their compari-
`son with the present non-clustered policies.
`
`3. Minimum muting lnfomsation
`
`In this section, we introduce some further nota-
`tion and formally pose the problem of finding an
`
`IS?
`
`optimal clustering structure- We then proceed with
`the derivation of the optimal solution and the study
`of its characteristics.
`
`Any hierarchical classification scheme lends itself
`to a tree representation [l9]. The tree structure has
`already been introduced in Fig. 2, to represent the
`3-level hierarchical clustering of the 24 node network
`in Fig. l. and it can easily beextended lo represents
`general let-level hierarchical partitioning.
`A I!“ level cluster. Cp, is defined recursively as a
`set of k — 1'I level clusters. It corresponds to a node at
`level It in a tree representation.
`A H" level cluster is identified. similar to the
`Dewey notation. by a vector ,ot' predecessorsn'“. =
`(rm, lm_,, .... in.) which can subsequently serve as an
`address ofC'g. The index.l,,,. Indicates them — 1“ level
`cluster, say Cmdfl”), to which C‘II belong; in".
`indicates the m — 2'“l
`level cluster in Cm_.(im) to
`which Cs belongs. etc. The notation Calmlm-.. ...,
`rm) or City"), will be used when there is a need to
`identify 0..
`Notice that a leaf in the tree representation corre-
`sponds to a node (01" level cluster) in the network.
`and to any node is associated an address vector i,
`which will be used for the routing of messages. As
`an example, node (1.3.” is the 0'“ level cluster
`C°(l,3,l); It belongs to the I“ level cluster C.[l,3)
`which in turn belongs to the 2"" level cluster C30),
`and finally all 2'“1 level clusters belong to the unique
`3"“ level cluster C,.
`The degree of a ll:m level cluster, Cg. is defined as
`the number of k — 1" level clusters included in Ca. [1
`also indicates the downward degree of the corre-
`trponding node in the tree. We denote by ugh...) the
`degree of Cam”). we also define it. = aw...» i...
`as the vector of degrees of all the it“ level clusters.
`Moreover, we let n‘=(rr.,rs:,...,tl,,) be the degree
`vector. Finally,S will denote the set of nodes and N
`its size.
`
`We are now ready to derive expressions for the
`lengrlr of the routing table (RT) and the size eon-
`realm.
`
`The summation of the degrees of all the 1“ level
`clusters gives the total number of nodes In the net-
`work (ie., the total number of leaves in the tree
`structure). Hence,
`om
`“(inn—Jan) Haliw....t3)
`
`E n.(:........n).
`E
`N= 2
`la”!
`ital
`lm‘l
`Eq. (1) will generally serve as a constraint over the
`
`
`
`
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 7 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 7 of 31
`
`
`
`160
`
`choice of the optimal degree vector tr, and it will be
`referred to as the size constraint.
`
`As an example. consider a 2-level hierarchical
`clustering composed of n2 1" level clusters. Let ia
`(i, = I. 2, ....n,} denote an arbitrary 1" level cluster.
`and n.0,) be the corresponding number of nodes,
`then
`
`"2
`
`~= t)3 min).
`'1"
`
`(2}
`
`l[Co{i1)] be the length of the RT at node
`Let
`C003); length is defined as the number of entries in
`that table.'l'hen
`
`The ossrtnrption is: each node of the network. C90,),
`contains an RT with an entry for each k-l" level
`cluster in the same k'“ level cluster as Com] (there
`are "Aim.
`..,, it”) such enln'es), and this for k =
`1,2. ...,m.
`
`Recall that we assume that the RT’s are of equal
`length i . winch must accommodate the number of
`entries at any node‘s RT. Hence.
`
`linen): max {Entttm.tm-......n+.n.
`nodes
`{over all k: 1
`
`(3}
`
`in the example above.
`tilt!) 2 max {"2 + outfit}.
`‘2
`
`Finally, we have the following:
`Hobie-m statement
`
`given : N
`minimize : 1(nr, it)
`over: tn and tr
`(see eq. (1))
`subject to : size constraint
`in a positive integer variable
`in a vector of positive integer variables
`
`(see eq. (3))
`
`(4)
`
`In Section 3.2 we give the realtvalued and in Section
`3.3 the integer solution to this problem.
`
`3.2. Real-valued solution of the optimization pnobiem
`
`We first proceed to solve this problem with the
`assumption that is may be a real valued vector. We do
`
`L..Kicirttock. F. Kamoun
`
`this in order to obtain an explicit analytical expres-
`sion for the optimal solution. As a consequence of
`this assumption. a summation as in Eq. (2) becomes
`meaningful only if n2 is an integer, or if all
`the
`n,(r‘,}'s are equal,say to n]. in which case the summa-
`tion becomes nznl. in fact, the solution of the opti-
`mization problem will show that clusters at the same
`level must be of the same degree; hence. all the sum-
`mations in Eq. (I) will become meaningful a pos-
`tenor-l.
`
`Opifmeiior for a tired tn
`
`Proposition l. Given tn. the number ofieveis in the
`hierarchy and osmrning that n is a reel vohred vector,
`the soiutton of our problem is such that:
`(a) all caterers at eii levels. it = l , .... tn, tit-econ:-
`posed of the me number of lower tevei clusters,
`that ts,
`
`”k(f&+il=flh =tv't".
`
`Wm . t= l.---.m:
`[5)
`
`(b) with this optimal assignment,
`table length is
`
`the minimum
`
`t= nuv'h'
`
`.
`
`(a)
`
`Proof. The proof proceeds by induction on the num-
`ber of levels, in. Flrst,we start by showing that Prop-
`osition l
`is true for m = 2. For m = 2. the problem
`becomes:
`
`min:i=max
`mi.
`mt,“a
`
`{Hill-i) + "1} .
`
`over : n, = {ti-Mill},-2 and n; .
`"1
`
`(7)
`
`s14? n,(i2}=Nand John; positive .
`=|
`From the above. we note that
`i > nl(t,) «- n3,
`Vi, = l, ...,n,. Lotn2 beflxeid. Then. summing this
`last relation over i2, we get for a feasible vector is:
`
`n3t3N+n§.
`
`This equation provides a lower bound on the optimal
`solution for a fixed n3. Consequently. if a feasible
`solution achieves that lower bound, then it must be
`optimal.Such a solution is
`
`Hills)“ iv- .
`
`f3 = 1,2. “u”: .
`
`‘-w—‘-—..
`..—...._.
`
`Hierarchical routine {0'
`
`If we now let in, be
`to minimizing l = l'
`is achieved for H; =
`(8). proves that PrOp
`Assuming that Pr.
`levels.
`let us Show
`in levels. The tree at
`,general case, is 1h"
`subtrces- Each subl
`contains a certain n
`which we denote b3
`stralnt. Eq. (I). lS'
`conslraints:
`l'lm _l (in)
`
`natty-ru-
`
`llm-t=1
`
`‘1;
`
`the V3
`let us 117:
`an" such that E(
`becomes decornPC
`correspondins ‘0 3
`over, such subprol
`es'es: hence, for a
`
`flgtfk+|}= Mien)
`
`Vii-OI (in F1“
`
`With such an assig
`
`min : i= mall!"
`in
`
`over : pm”)
`
`I
`
`s.t. : 54(1th
`
`111: above problt
`‘t (m = 2). Then
`and (6} A I110!"
`[14].
`We now inter
`
`global optimum.
`
`Proposition 2. Ti
`when the numbe
`
`m.=lnN.
`
`
`
`

`

`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 8 of 31
`Case 1:16-cv-02690-AT Document 121-9 Filed 08/05/16 Page 8 of 31
`
`Hierarchical routing for large uremic:
`Dims-k. F. Komorm
`
`and when the degree vector is. is such that all compo-
`
`
`[i we now let n2 be a variable, the problem reduces
`analytical expres-
`nents have equal values:
`consequence of
`to minimizing l = Min2 + n, over it}. The optimum
`
`
`is achieved for n: = N"ll which. combined with Eq.
`Eq. (2} becomes
`
`[it]. proves that Proposition 1 is true for m = 2.
`r. or if all
`the
`3
`' case the summa-
`Assuming that Proposition 1 istrue for up to m - l
`
`lenls,
`let us show that
`this implies it is true for
`tion of the opti-
`
`
`or levels. The tree structure which corresponds to this
`sters at the same
`cc. all the sum-
`general case.
`is then composed of nm(m — I} level
`subtrees. Each subtree. say im (im = I, 2, ..., rim),
`
`contains a certain number of network nodes (leaves)
`which we denote by ptr'm). As a result the some con-
`straint. Eq'. (I). Is equivalent to the following set of
`constraints:
`“m-rliml
`
`
`
`
`
`-——-—__-
`
`l6!
`
`n; =rr' =e =17” ...,
`
`it = I. 2. m, .
`
`([3)
`
`The corresponding minimum table length is
`
`l. = e in N .
`
`('4)
`
`The proof follows simply from the results obtained in
`Proposition l.
`
`[healthy
`It is of Interest to consider the dual [emulation of
`our Problem (4). The new objective is to find the
`maximum number of nodes N such that there exists
`an mHC whose application results in a routing table
`of a given length. The dual propositions to l and 2
`are respectively.
`
`the real valued
`Proposition 3. For a fixed or and l.
`solution of the dual problem is such that
`
`_!
`fla-—.
`in
`
`k=l.2,...,m.
`
`mm this assignment
`M
`N= (1)
`m
`
`.
`
`Proposition 4. The real veered global optimum ofthe
`duel problem is such that
`
`"films-"Jill
`
`E...
`fM_]‘-I
`
`Z)
`{2:1
`
`"10:". ---Jr}=P(lm}.
`
`in. e l. n... .
`"in
`
`E Ml‘m)=N.
`on
`
`(9)
`
`(10)
`
`.
`
`i
`I
`
`bet us fix the variables in," and dim). i," = l. ....
`am, such um Eq. (10) a satisfied, Our problem
`becomes decomposable into rim subproblems. each
`corresponding to a given value of the