`

`~ IEEE COMMUNICATIONS SOCIETY t!..,
`
`.
`The field of interest of the IEEE Communications Society consists of all telecommunica tions inc luding telephone , telegraphy, facs imile, a nd point-to-point television , by elec trom
`propagation including radio ; wire ; ae rial , underground , coaxial, and subma rine cables; waveguides, communication satellites, and lasers ; in marine, aeronautical , space and fi xed stations ag?ehc
`repeater~, r~dio rel ayi ng , signal s_torage, a nd regeneration; telecommunication error detection and correction; multiplexing and carrier techniques; communica tion switching syste;;1~es;
`ata
`communications; and communication theory.
`In addition to the a bove, this TRANSACTIONS contains papers pertaining to analog and digita l signal processing a nd modul atio n. a udio and video e ncoding techniques, the theory and de .
`transmitters , receiv<:rs, and repeaters for communications vi~ optical a nd s? nic_ media , the design and_ analysis ?f computer communication sys tems , a ~d ~he development of co mmunf~!~ of
`software . Contnbut1ons of theory enhancing the und e rsta nding of communication syste ms a nd techniques are included , as are d1 scuss1ons of the soc ia l 1mphcat1ons of th e developm
`ion
`communication technology. All m embers of the IEEE are eligible for membership in the Society upon payment of the annual Society membership fee of $ 12 .00. Members may recei ent ~f
`TRANSACTIONS or the IEEE JoURNAL ON SELECTED AREAS IN COMMUNICATIONS upon pay me nt of an additi o nal $8. 00 ($20.00 total). or both publica tion s upon pay ment of an additional ~~~his
`.0()
`($28 .00 tota l) . For information on joining, write to the IEEE a t the addre ss below .
`IEEE COMMUNICATIONS SOCIETY
`TRANSACTIONS Editorial Board 1987
`
`P . E. GREEN, JR ., Director of Publications
`IBM Res . Cen ., Rm . H3D8
`Yorktown Heights, NY 10598
`
`J . R . LESH , Editor-in-Chief
`Jet Propul sio n Lab., 200-122
`4800 Oak Grove Dr.
`Pasaden a, CA 91109
`
`J. L. LOC ICERO, Publirntions Editor
`Dep. Elec . Eng., Illinoi s lnsl. Technol.
`C hi cago, IL 60616
`
`E. R. BYRNE , Communication Software
`Bellcore , Rm. 4D-376
`Piscataway , NJ 08854
`
`D. C. Cou, CATV
`Dep. Syst. Comput. E ng., Carleton U niv .
`Ottawa, Ont. , Canada KI S 5B6
`
`D . D. FALCONER, Dig ital Comm1111ications
`Dep. Syst. Compul. Eng., Carleton Univ.
`Ottawa, Ont. , Canada KIS 5B6
`
`N. FARVARDIN, Quantiza tion , Speech /
`Image Coding
`Dep. Elec. Eng.
`Univ . of Maryland
`College Park , MD 20742
`
`M. J. FERGUSON , Co111puler Network
`Performan ce
`INRS Telecommun .
`3 Place du Commerce, lie des Soeurs
`Verdun , P.Q ., Canada H3E IH6
`
`I. G ARRETT, Fiber Optic Com111unications
`British Telecom Re s. Lab.
`Rl7 .2, Martlesham Heath
`Ipswich , IP5 7RE, England
`
`I. GoPAL, Network Pro tocols
`IBM T. J . Watson Res. Cen .
`Yorktown Heights, NY 10598
`
`R . IL TIS, Spread Sp ectm111
`Dep. E lec . Comput. Eng ., Univ. California
`Santa Barbara, CA 93106
`
`J . JAFFE, Rowing and Switching
`IBM T.J. Watso n Re s.
`P.O. Box 218
`Yorktown, NY I0598
`
`M . KAV EHRAD , Mo bile Com111unications
`ATT Bell L a b ., Rm. HOH L - 159
`Crawfords Co rner Rd .
`Holmde l, NJ 07733
`
`Editors
`P. MERMELSTEIN , Sp eech Processing
`Bell Northern Re s.
`3 Place du Commerce , lie des Soeurs
`Verdun , P.Q., Ca nada H 3E IH6
`
`K. K OMMERLE , Local Area Ne tworks
`IBM Zurich Re s. Lab.
`Saumerstrasse 4
`8803 Ru sc hlikon , Switzlerland
`
`S. LAM, Network Protocols
`Dep . Comput. Sci., Univ . Texas
`Austin, TX 78712
`
`R. LANGSETH , Transmission S ystems
`AT&T Bell Lab ., Rm . 3M-526
`Holmde l, NJ 07733
`
`A . LEON-GARCIA, Voice/Data Networks
`Dep . Elec. E ng ., Univ. Toronto
`Toronto , Ont. , Canada M5S I A4
`
`A. LEVESQUE , Coding TheOI)' and
`A pplications
`GTE Go ve rnment Syst.
`2 Executive Park
`Natick, MA 01760
`
`J . MARK, Wide Area Networks
`Comput. Commun. Network Group
`Univ. Waterloo
`Waterloo, Ont., Ca nad a N2L 30 I
`
`P . MCLANE, Modulation TheOI)' and
`Nonlinear Channels
`Dep . Elec . E ng., Queen's Univ .
`Kings ton , Ont., Ca nada K 7L 3N6
`
`A. NETRAVALI. Ima ge Processing
`AT&T Bell Lab. , Rm . 3 D-406
`Murray Hill. NJ 07974
`
`W. H . NINK E, /111a ge Communication
`System s
`AT&T Bell Lab ., Rm. 4C-5 16
`Holmdel, NJ 07733
`
`P. PAPANTO NI-KA ZAKOS, Random Access
`Svs tems
`Dep . E le c. E ng. Co mput. Sci., Box U 157
`Univ. Co nn ec ti cut
`Storrs, CT 06268
`
`S. PASUPATHY , Data Communications and
`Modulation
`De p . Elec. Eng., Univ. Toronto
`Toronto, Ont. , Ca nada M5S IA4
`
`I. RUBIN , Queueing/Buffer Ma nage m ent
`Dep . Elec . E ng.
`UCLA, 673 1 Boelter Hall
`Los Angeles, CA 90024
`
`E. G. SABLE, Communication S witchiny,
`AT&T Bell Lab ., Rm. 2B-63 1
`Holmdel. NJ 07733
`
`Associate Editors
`J . G. KAPP EL
`D. VLACK
`
`A. SEGALL , Computer Com1111111ications
`TheOI)'
`Dep. E lec. E ng. , Tech nion-I.LT.
`Haifa 32000, Israel
`
`W . STARK, Spread Spectn1111
`Dep. E lec . Co mpul. E ng., Un iv. Michigan
`A nn Arbor, Ml 48 109
`
`C. A. SUNSH INE, Protocol Va lida ti0115
`System Development Corp.
`2500 Colorado Ave.
`Santa Monica. CA 90406
`
`H. TAKAG I, Queuei11g a11d Ne twork
`Pe1forma11 ce
`IBM Japan Tokyo Re s. Lab., No. 36 Kowa
`Bldg .
`5-19. Sanban-c ho .
`C hi yoda-k u , Tokyo 102, Ja pan
`
`D . TAYLOR , Sig11al Desig11, Modulmio11,
`a11d Detectio11
`Dep. E lec . Comput. Eng. , McMaster Univ.
`Hamilton , O nt. , Canada L8S 4L7
`
`D. TOWSLEY. Co111111u11ica tio11 Networks
`Dep. Co mput. Inform . Sci.
`Univ. Massac hu sett s
`A mh erst , MA 01003
`
`J. UHRAN, A 11alog Com111u11icatio11s
`Dep. E lec. Eng., Univ . Not re Dame
`South Bend , IN 46556
`
`S. G . WILSON, Coding Theo1y and
`Applicatio11s
`Dep. Elec . E ng. & Commun. Syst. Lab.
`U niv . Virginia
`C harlottesville, VA 2290 I
`
`W. W . Wu . Satellit e Co1111111111icatio11s and
`Codi11 g
`INTELSAT
`3400 Inte rna ti onal Dr. , N.W .
`Washingto n, DC 20008
`
`M. J . JOINDOT, Radio Co111n11111ications
`CNET/LAB/MER
`Route de Tregastel, BP 40
`22301 Lannion , France
`
`U . M ENGA LI , Synchronization Systems and
`Techniques
`JET , Univ. Pisa, Via Diotisalvi 2
`56IOO Pisa, Italy
`
`K. S. SHANMUGAN, Computer-Aided
`Design of Co111111u11ica tions System s
`Dep. E lec. E ng ., U ni v. Kansas
`Lawrence, KS 66045
`
`Consultant
`T. 0SATAKE, Far Eastem Contributions
`47-5 Noga ta-6-c home
`Nakano-k u, Tokyo , 165, Japa n
`
`(Information for Authors, ComSoc Board of Govemors, Depart111ents , and Committees appear 011 Cover III .)
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`
`HENRY L. BACHMAN , President
`RUSSELL C. DREW, President Elect
`MERRILL W . BUCKLEY , JR., Executive Vice President
`RAMIRO GARCIA SOSA, Secre/al)'
`EDWARD J. DOYLE , Treasurer
`
`RONALD G. HOELZEMAN, Vice President , Educatio11al Activities
`CA RL ETON A. BAYLESS, Vice President , Professional Activities
`C HARL ES H . HOU SE, Vice Preside/// , Publication Activities
`ROB ERTS. D UGGAN, JR ., Vice President , R egional Activities
`EMERSON W . PUGH , Vice President, Technical Activities
`ERICE. SUMN ER, Director, Division III-Co111munirntions Tech11ology Division
`
`THOMAS w. BARTLETT, Controller
`DONALD CHRISTIANSEN, Editor, IEEE Spectrum
`IRVING ENGELSON , Staff Director , Technical Activities
`LEO FANNING , Staff Director, Professional Activities
`
`Headquarters Staff
`ERIC HERZ , Executive Director and Ge nernl Ma11ag er
`ELWOOD K . GANN ETT , Deputy Genernl Manager
`SAVA SHERR , Staff Direc tor, S tandards
`DAVID L. STAIGER, Staff Direcior, Publishing Services
`C HARLES F. STEWA RT , JR., S taff Director, Administrative Services
`DONALD L. SUPPERS , S ta.D· Director, Field Services
`T HOMAS C. WHITE, S taff Director, Public J,,for111ation
`Publications Department
`Publication Managers: ANN H. BuRGMEYER, GAILS . FERENC , CAROLY NE TAMNEY
`Associate Editor: H ENRY B. FRIEDMAN
`IEEE TRANSACTIONS ON COMMUNICATIONS is published monthly by The Institute of E lec trica l a nd E lectro ni cs E ngine~rs . Inc. Responsibilit y fo r the co nt e nts rests upon the author and "~:~;~
`the IEEE, the Society Council , or its members . Headquarters: 345 East 47th Street , New York, NY 1001 7-2394 U.S .A . IEEE Service Center (for orders, subscriptions, address c r-?910,
`Region/Section/Student Services) : 445 Hoes Lane, P .O . Box 1331, Piscataway, NJ 08855-1331. Telephones: Headqu arters 2 12-705 + exte nsion: Info rmat io n-7900, G eneral Man~~ce 202-
`/Section/
`Controller-7748, Educational Services-7860 , Publishing Services-7560, Standards-7960, Technical Services-7890. IEEE Service Center 201-98 1-0060. Professio na l Services: _wa_s hington
`785-0017 . NY Telecopier: 212-752-4929 . NY Telex : 236-41 I (international messages only) . IEEE Service Center (for o rders , subsc ription s. ad dress c ha nges, Ed uc ation al Act1v1t1es , Regio~W suite
`Student Se:"ices): 445 Hoes L ane , P .O . Box 1331 , Pisca taway, NJ 08855-1331. NJ Telephone: 201-981 -0060. IEEE Washington Office (for U.S. professional ac ti vities): 1111 19th Stree~ er,coPY·
`608, Washington , DC 20036. Washington Telephone : 202-785-0017. Price/Publication Information: Indi vidual copies: IEEE me mbers $ 10.00 (fi rst copy o nl y), no nm embers $ZO. _ . p of u.S.
`Available in microfiche and microfilm . Copyright and Reprint Permission: Abstracting is permitted with credit to the source . Libraries are perm itted to photocop y be yond the hmi~opyrighl
`Copyright law for private use of patrons; I) those post-1977 articles tha t carry a code at the bottom of the first page , provided th e per-copy fee indicated in th e code is paid through _the I fee. for
`Clearance Center, 29 Congress St. , Salem , MA 01970 ; 2) pre-1978 articles without fee. Instructors are permitted to photocop y isolated art icles for no nco mm ercial classroom u_se wi th~:87 by 1be
`to IEEE
`other copying, reprint , or republication permission , write to Copyrights and Permissions Department . Publi shing Services at IEEE Headq uarters. All rights reserved. Copyright ©
`Ins titute of Electrical and Electronics Engineers , Inc. Printed in U.S.A. Second-class postage paid at New York, NY a nd at ad dition al mailing office s . Postmaster: Se nd address changes
`TRANSACTIONS ON COMMUNICATIONS, IEEE, 445 Hoes Lane , P .O . Box 133 1, Pi sca taway, NJ 08855-1331.
`
`

`

`PAPERS TO BE PUBLISHED IN THE NEXT ISSUE
`June 1987
`
`Papers
`
`A Petri Net Cont:ol Unit For High-~peed Modular Signal Processo~ ........................... ... . S. Bro.fferio
`Spectral Correlat~on of Modulated S~gnals: Part I-An.al.og Modulat1.on .. .... . .. . .... . . .......... W. A . Gardner
`Spectral Correlation of Modulated Signals: Part II-D1g1tal Modulat10n ..... .. . . . ........................ .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . W. A. Gardner, W. A. Brown, and C .-K. Ch~;
`Time Slot Assignment in SS/TDMA Systems with Intersatellite Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`...... . .. . ........................... . . .. .. . . . .. . ... . . A. A. Bertossi , G. Boniiovanni, and M . Bonuc·c·e.lii
`Message Delays with Prioritized HOLP and Round-Robin Packer Servicing .......... . ............. J. N . Daigle
`Proof that Timing Requirements of the FDDI Token Ring Protocol are Satisfied ........ . ........... M. Johnson
`Maximum-Likelihood Symbol Synchronization for the Direct-Detection Optical On-Off-Keying Channel .. ... .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . : C. N . Georghiad~~
`Optimum Joint Slot and Symbol Synchronization for the Optical PPM Channel ...... . ........ C. N . Georghiades
`15/30 Mbits/s Universal Digital TV Codec Using a Median Adaptive Predictive Coding Method ....... ... .. .. .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H. Murakami, S. Matsumoto, Y. Hatori, and H . Ya mamo~~
`Adaptive Median Filtering for Impulse Noise Elimination in Real-Time TV Signals . ..... .. . .. .. ........ . . .. .
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . S. S. Perlman. S. Eisenlwndler. P. W. Lyons. and M. J. Sh umf/~
`A Prototype Switching System Employing a Matching-Based Language ......... N. Kml'ashima and Y. Hirakmva
`Performance Evaluation of Multireject , Selective Reject, and Other Protocol Enhancements ........ . P. T. Brady
`
`1
`
`Correspondence
`
`A Code-Division Multiple-Access Local Area Network . ......................... . .... J. R. Lee and C. K. Un
`Conditional Run-Length and Variable-Length Coding of Digital Pictures ................. : .. .... .... H. Gharal'i
`An Efficient Nearest Neighbor Search Method ........... . .. . ... . ... . ..... M. R. Soleyrnani and S. D. Mo rgera
`Corrections to "A New Rapid Acquisition Technique for Direct Sequence Spread-Spectrum Communications ....
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . S. Davidol'ici, L. B. Milstein, and D. L. Schilling
`Efficiency of Digital Synchronous Communication Systems .... S. Glisic·, G. Lukatela, G. Petrovic, and D. Drajic
`Derivation of Gardner's Timing-Error Detector from the Maximum-Likelihood Principle . ... . . . . ... . . . M . Oerder
`Accurate Calculation of TWT Intermodulation in the Many Carrier Case .. ... . ....... .. ..... . ...... .. A. Guida
`
`V>Z
`CJ\
`t'\I n
`~ rt
`lo-
`0
`·l: u
`:> ll.J
`H'
`
`

`

`IEEE TRANSACTIONS ON COMMUNICATIONS , VOL. COM-35, NO . 5, 1\1-AY 1987
`
`503
`
`Routing in the Manhattan Street Network
`
`NICHOLAS F. MAXEMCHUK, SENIOR MEMBER, IEEE
`
`Abstract-The Manhattan Street Network is a regular, two-connected
`network, designed for packet communications in a local or metropolitan
`area. It operates as a slotted system, similar to conventional loop
`networks. Unlike loop networks, routing decisions must be made at every
`node in this network. In this paper, several distributed routing rules are
`investigated that take advantage of the regular structure of the network.
`In an operational network, irregularities occur in the structure because
`of the addressing mechanisms, adding single nodes, and failures. A
`fn1ctional addressing scheme is described that makes it possible to add
`new rows or columns to the network without changing the addresses of
`existing nodes. A technique is described for adding one node at a time to
`the network, while changing only two existing links. FiQally, two
`procedures are described that ?llow the network to adapt to node or link
`failures. The effect that irregularities have on routing mechanisms
`designed for a regular structure is investigated.
`
`I. INTRODUCTION
`
`THE Manhattan Street Network (MSN) [1], Fig. 1, is a
`
`two-connected, regular network with unidirectional links.
`The links are arranged in a structure that resembles the streets
`and avenues in Manhattan. The MSN topology is being
`applied to a local or metropolitan area packet communication
`system .
`The nodes in the MSN are described in Section II. The
`structure of the nodes and the access strategy are similar to
`those in a slotted loop system. The principle difference
`between the MSN and a loop network is that there are two
`links arriving at and leaving each node instead of a single link,
`and a routing decision must be made for each packet
`transmitted at each node. An experimental network is being
`constructed with a 50 Mbit/s transmission rate on each link
`and 128 bit fixed sized packets. More than 750 000 routing
`decisions per second may have to be made at each node in this
`network. In this type of network, the routing rule must be
`simple .
`In this paper, distributed routing rules for the MSN are
`investigated. Simple routing rules that use the regular structure
`of the network are compared to shortest path algorithms and
`random routing strategies. Jn the MSN, shown in Fig. 1, the
`number of rows and columns completely defines the network,
`and if these numbers are known, the shortest path between any
`pair of nodes can be determined. In addition, because of the
`cyclic structure of the MSN, routing is only dependent upon
`the relative location of the current node with respect to the
`destination, as defined in Section III-B, and the same routing
`rule can be used at every node. In Section IV-A, a distributed
`rule is described that finds the shortest path. In Sections IV-B
`and IV -C, two simplifications of the shortest path rule are
`described. The simplified rules do not always find the shortest
`path , and the effect that these rules have on the average path
`length is investigated in Section IV-E.
`In Section III-A, a fractional addressing scheme is de(cid:173)
`scribed. This addressing scheme has two advantages over the
`integer addressing scheme in Fig. 1.
`
`Paper approved by the Editor for Wide Area Networks of the IEEE
`Communications Society . Manuscript received November 25 , 1985; revised
`December 11, 1986.
`The author is with AT&T Bell Laboratories, Murray Hill , NJ 07974.
`IEEE Log Number 8613925.
`
`Fig. 1. 36-node MSN .
`
`1) New rows or columns are added to the network without
`changing the addresses of existing nodes.
`2) The distributed routing rules are independent of the
`number of rows or columns in the network.
`A disadvantage of fractional addressing is that the distrib(cid:173)
`uted routing rules must operate without knowing the position
`of all of the rows and columns in the network and cannot
`always find the shortest path to the destination. The effect that
`this addressing scheme has on the average distance between
`nodes in investigated in Section IV-E .
`The MSN is a regular structure with an even number of
`rows and columns and is not defined for an arbitrary number
`of nodes. A realistic network, in which nodes are added and
`other nodes or links fail, may be approximated by the MSN ,
`but it is unlikely that it will exactly correspond to the regular
`structure. The routing rule that is selected for the MSN must
`operate in networks with irregularities. The effect
`that
`irregularities have on the routing rules depends upon the
`techniques used to add nodes and remove failed components.
`In Section V-A , a technique is described for adding one node
`at a time to the network. When this technique is used, only two
`links must be changed when a new node is added to the
`network. As nodes are added , a row or column may not have a
`full complement of nodes. The routing rules operate without
`knowing which rows or columns are incomplete. In Sections
`V-B and V-C , procedures are described that allow the network
`to adapt to node or link failures. The adaptations guarantee
`that the nodes ~ontinue to operate without losing packets at any
`of the surviving nodes. The routing rules operate without
`knowing which nodes or links have failed .
`
`II. SYSTEM DESCRIPTION
`The MSN , Fig. 1, is a member of a class of multiply(cid:173)
`connected , regular, mesh-configured networks. There is an
`
`0090-6778/87/0500-0503$01. 00 © 1987 IEEE
`
`

`

`504
`
`IEEE TRANSACTIONS ON COMMUNICATIONS , VOL. COM-35 , NO . 5, MAY 1987
`
`2
`
`I t--+--•Out I
`
`t--+--•Out 2
`
`Source
`Fig. 2. The structure of a node in a two-connected network with fixed size
`·
`packets .
`
`even number of rows and columns with two links arriving at
`and two links leaving each node. Logically , the links form a
`grid on the surface of a torus, with links in adjacent rows or
`columns traveling in opposite directions.
`In [2] , it has been demonstrated that, because of the
`increased connectivity , mesh networks can achieve higher
`throughputs and support more sources than conventional loop
`[3]-[5] and bus [6], [7] networks. This occurs because of the
`following.
`1) On the average , a smaller fraction of the links in the
`network are used to interconnect a source and destination.
`2) Sources that communicate frequently can be clustered
`into communities of interest that do not interfere with one
`another.
`In a network with several paths arriving at a node , messages
`froin more than one incoming link may be destined for the
`same outgoing link. Data from several links can be concen(cid:173)
`trated onto one link by storing the data, forwarding them when
`the link is available , and establishing protocols to recover
`messages that are lost because of buffer overflows. In [2], a
`slotted system is described that does not require buffering on
`the output links and does not lose packets because of buffer
`overflows. The structure of a node in this network is shown in
`Fig. 2.
`The packets in the slotted system are a fixed size. A node
`periodically transmits a packet from an input line, a packet
`from the source, or an empty packet on each output line . At
`each node, the packets from the input lines are delayed so that
`they arrive at the switch at the time that the node transmits a
`packet. The node switches each of the incoming packets not
`destined for the node to one of the output links. If the buffer
`for an output link is full, and two incoming packets are
`destined for this link, one of the packets is forced to take the
`other output link. This strategy guarantees that packets are
`never lost because of buffer overflow, even if the output buffer
`size at the nodes is reduced to zero; however, the larger the
`buffers at a node, the less likely it is that a packet must be
`misdirected. Packets from the source are only transmitted
`when there is an empty slot on an output link. The node
`controls the source so that packets do not arrive faster than
`they are transmitted, and the rate available to the source
`decreases when the network is busy. Packets that are misdi(cid:173)
`rected take a longer path to their destination and prevent more
`new packets from entering the network. Therefore , there is a
`tradeoff between buffer size and the throughput of the
`network.
`In the MSN , each time a packet is misdirected, the length of
`the path to the destination is increased by at most four links. In
`addition, there are many nodes for which either outgoing link
`provides the same path length to the destination, and when a
`
`packet may take either link, the probability any packet Will
`have to be misdirected decreases. A recently published
`analysis and simulation of the MSN [8] indicates that the MSN
`operates reasonably efficiently without buffers on the outgoing
`links , and the experimental system that is being implemented
`does not have buffers .
`
`III. ADDRESSING NODES IN THE NETWORK
`Each node in the network has a unique address that is called
`the node ' s absolute address. To simplify the routing rule, the
`absolute address of a node reflects the regular structure of the
`MSN. Because of the cyclic nature of the MSN , routing only
`depends on the relative position of the current node and the
`destination, called the current nodes relative address , and not
`on the absolute address of any node. Relative addresses allow
`the same routing rule to be used at each node.
`
`A. Absolute Addresses
`In Fig. 1, the rows in the MSN are sequentially numbered
`from O to m - 1 , the columns are numbered from O to n -
`I
`and the absolute address of a node is its row and column. Th;
`odd-numbered rows have links in one direction and the even(cid:173)
`numbered rows have links in the opposite direction. New rows
`or columns are added in pairs to preserve the alternating
`directions , and the address of an existing row or column
`changes when new elements are added in the middle of the
`network. To reduce the effect of changing addresses on the
`communications routines at the source , there must be a
`transformation between a logical address by which the source
`refers to the destination and a physical address that is the
`destination node's current row and column . The transforma(cid:173)
`tion need only be performed at the source node of a packet;
`however, a transformation table must be maintained at every
`node in the network, and a protocol must be developed to
`update the table as physical addresses change.
`An alternative to changing the address of a node when new
`rows and columns are added is to plan for expansion by not
`using all of the addresses initially. For instance , in the initial
`implementation of the network, the rows may be numbered 0,
`11, 22, · · · so that ten new rows can be added between each of
`the initial rows. By leaving an even number of integers
`between assigned rows or columns, the alternating direction
`can be retained as new rows are added. The spacing between
`rows can be decreased when nodes in the same community of
`interest are in adjacent rows, and it can be increased where
`new communities of interest may be inserted. This approach
`requires careful planning because the network growth must be
`predicted when the initial network is designed. The planning
`can be reduced by using fractional addresses rather than
`integer addresses. Fractional addresses allow an arbitrary
`number of pairs of rows to be added at any position in the
`network.
`The fractional addressing scheme that has been selected is
`shown in Fig. 3. The first two rows or columns are labelel 0
`and 1 . Rows are added in pairs and are labeled as two
`fractions, 1/3 of the way between two other rows. For
`instance, two rows added between O and 1 are labeled 1/3 and
`2/3 and two rows added between 2/3 and 1 are labeled 7 /9 and
`8/9. New rows that are added between 1 and Oare considered
`to be between 1 and 2 so that they have different addresses
`from the rows between O and 1. For instance, two rows added
`between 1 and O are labeled 4/3 and 5/3 and two rows between
`5/3 and O are labeled 16/9 and 17 /9. Fractional addressin:
`does not constrain the total number of rows that can be adde
`to the network or the number of rows that can be added to a
`community of interest in a particular area of the network. In
`addition, the fractional addressing scheme selected guarantees
`that all rows with an even numerator have links in one
`direction and all rows with an odd numerator have links in the
`opposite direction, as in the integer addressed system.
`
`

`

`MAXEMCHUK: ROUTING IN THE MANHA TT AN STREET NETWORK
`
`505
`
`1/3
`
`2/3
`
`4/3
`
`5/3
`
`1/9 2/9
`
`4/9 5/9
`
`7/9 8/9
`
`10/9 11/9
`
`13/9 14/9
`
`16/9 17/9
`
`Fig. 3.
`
`Fractional addressing in the MSN.
`
`Quadrant 3 or 4
`_l _l.
`0
`3
`3
`
`Quadrant 1 or 2
`l.
`l
`l
`9
`3
`3
`
`l.
`9
`
`a) Actual assignment of rows to quadrants
`
`Quadrant 3 or 4
`2
`1
`3
`3
`
`Quadrant 1 or 2
`l.
`l
`l
`I
`9
`9
`3
`3
`
`Qzr - - - - - - - - - - - - - - - - - - - - - - - - - - - - -:- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -Q I
`
`b) Expected assignment of rows to quadrants
`
`I
`
`Fig. 5 . Assignment of rows to quadrants in a network with eight rows.
`
`network. A node is in Q1 when r > 0 and c > 0, Q2 when r >
`0 and c ~ 0, Q3 when r ~ 0 and c ~ 0, and Q4 when r > 0
`and c ~ 0. The quadrant of the current node indicates the
`direction in which to proceed to get to the destination . Because
`the network has unidirectional links, this routing strategy must
`be modified when the current node is at the boundary of the
`quadrants, as discussed in Section IV. Fixing the orientation of
`the links at the destination allows the same routing decisions to
`apply at the boundaries.
`An advantage of fractional addressing over integer address(cid:173)
`ing is that the relative addresses are independent of the number
`of rows or columns in the network. In an integer-addressed
`network, the arithmetic unit that calculates the relative address
`must be changed whenever the number of rows or columns
`changes. This arithmetic unit does not change in the fraction(cid:173)
`ally addressed network.
`A disadvantage of fractional addressing is that the destina(cid:173)
`tion is sometimes displaced from the center of the network
`when relative addresses are calculated. For instance, in Fig.
`5(a), a possible assignment of rows to quadrants is shown for a
`network with eight rows and only two of a possible 12 rows in
`the 119th addressing level. Five rows are assigned to quadrants
`1 or 2 and only three to quadrants 3 or 4, and as a result,
`packets routed from nodes with a relative address (1, X) may
`take a longer path to the destination. In Fig. 5(b), the
`assignment of rows to quadrants that places the destination in
`the center is shown.
`It is evident from this example that new rows should be
`added uniformly, when possible, in order to calculate the
`quadrant correctly. However, the quadrant is most likely to be
`calculated incorrectly for the nodes that are furthest apart. In
`large networks, with many small communities of interest,
`expanding the network with nonuniform addresses that keep
`nodes in their communities of interest is preferable to forcing
`nodes to join distant parts of the network. If most packets
`remain within the community of interest and are not directed to
`the nodes that are furthest away, the distance between nodes
`that communicate frequently is kept small and the effect of
`nonuniform addresses is less than in a network with uniform
`traffic requirements.
`
`IV. DISTRIBUTED ROUTING RULES
`In Sections IV-A, B, and C, three distributed routing rules
`are described that use the regular structure of the MSN to
`select a path to the destination. Rule 1 determines all shortest
`paths to the destination for integer addressed MSN 's. Rules 2
`and 3 reduce the number of calculations that are performed at
`each node, but occasionally take longer paths. Rules 1 and 2
`are dependent upon the addresses of the adjacent nodes to
`which a node is connnected; rule 3 is not.
`In complete, integer-addressed networks, the address of
`adjacent nodes is known. In fractionally addressed networks or
`in networks with partially full rows or columns, as described
`in Section V-A, the address of adjacent nodes is not known. If
`rule 1 or 2 is used, a technique must be used to determine the
`node to which each node is connected. In the experimental
`network, the nodes to which a node is connected is stored
`locally and changed manually when the network connectivity
`
`Q3L - - - - - - -
`
`- -
`
`- - - - - - -
`
`- - - - - - - - - -
`
`I
`I
`- - _,_ - - - -
`
`- - - - -
`
`- - - -
`
`- - -
`
`- - - - - - - -
`
`- - - - -Q4
`
`Fig. 4. Relative addresses in a 36-node MSN.
`
`B. R elative Addresses
`Because of the cyclic structure of the MSN, any node can be
`considered to be in the center of the network. The relative
`address (r, c) of a node with absolute address (r1r, c1r) with
`respect to the destination node with absolute address (r10 , c10 )
`is defined so that the destination node is approximately at the
`center of the network, has relative address (0, 0), and has both
`row and column links directed toward decreasing numbered
`nodes , as in Fig. 4.
`The relative address in an m x n integer-addressed network
`
`is
`
`r=; -[ (; -DcCrrr,0 ) ) mod m]
`c=i-[ G-D,(crcto)) mod n]
`
`(1)
`
`and in a fractionally addressed network is
`
`r= 1- {(l -Dc(r1,-r10 )) mod 2}
`
`(2)
`
`C= l -{(l-Dr(c1,-c10 )) mod 2}
`Where D e and D, are dependent upon the direction of the links
`at the destination node. In a network with the links in the even
`and odd rows and columns directed toward increasing or
`decreasing rows and columns, as in Fig. 1, De = + 1 when c10
`(the numerator of c10 in a fractionally addressed network) is
`even, D e = - 1 when c10 is odd, Dr = + 1 when r10 is even,
`and D r = - 1 when r10 is odd.
`. The definition of the relative coordinates in (1) and (2)
`limits the relative address of the current node to - (m/2) < r
`:s; m/2, and - (n/2) < c ~ n/2 for an integer-addressed
`network and - 1 < r, c ~ 1 for a fractionally addressed
`
`

`

`506
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-35, NO . 5, MAY 1987
`
`Q .= -2 - - - - - - - - -~ - - , - - - - - - - - - - . . . . - - -Q , Q,...2------------.--,------------
`-{r,
`-------- - --------------,----
`
`1
`
`Qi-
`
`-
`
`Cz
`
`-Q , -
`
`Qi-
`
`-
`
`C2
`
`-Q,
`
`r2 -
`
`r2 -
`
`-
`
`r4
`
`-
`loe.,t
`L.:..:::_ --- -r--------i---------- ----
`
`r4
`
`Q3-
`
`-
`
`Q3 -
`
`-Q4-
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`
`.-L:
`
`C3
`
`Fig. 6. Preferred paths in Rule 1.
`
`Fig. 7. Preferi:ed paths in Rule 2.
`
`changes. When the procedure described in Section V-A is used
`to add nodes, the connectivity for only two nodes changes
`when a new node is added to the network. Therefore, a manual
`rather than an automatic procedure is reasonable . When nodes
`or links fail and are bypassed automatically, as in Sections V-B
`and C, the connectivity information at a node is not changed ,
`and it is incorrect.
`These three rules are referred to as deterministic routing
`rules. In addition , two random routing rules are desc