A.Channel Allocation Issues 
        1.Broadcast networks, which includes all LAN's and MAN's as well as satellite and cell phone networks, in some way 
          must be found to allocate the shared channel (be it a wire or the airwaves) among users. [By contrast, point-to-point 
          networks don't have this problem; so it doesn't appear in WAN's.] 
        2.There are two basic ways of allocating channels: 
             a.Static: When there is a small, fixed number of users, one carves up the channel into "pieces" and gives each 
               user a piece of the channel. 
               The basic techniques are: 
                    FDM (frequency division multiplexing): We already discussed this in connection with analog trunks in 
                    the phone system. One simply divides the frequency bandwidth into well-separated domains. 
                    TDM (time division multiplexing): We discussed this in connection with digital trunks in the phone 
                    system. One assigns consecutive time slots, e.g. bytes (SONET) or bits (T1), to specific users. 
                    CDMA (code division multiple access): Users share the same time slots and frequency spectrum, but 
                    use specific codes in the time slot for 1's and 0's that can be distinguished from one another (they are 
                    orthogonal in some sense) . This approach is widely used in wireless communications (cellular phones 
                    or sattelite). It can have superior noise properties, and we will say more about it shortly. 
             b.Dynamic: All users are allowed to use the same channel to both transmit and receive. If two users transmit at 
               once, their frames are garbled and must be decarded. This event is a collision, and all stations can detect 
               collisions (in LAN's by monitoring the channel continually). The protocol must either avoid collisions by 
               passing a token or deal with them in some way. 

               Note: Ethernet has users retransmit after a random time when there is a collision. 

        3.CDMA (Code Division Multiple Access) 
             a.Each time slot is divided into m short intervals, referred to as chips. Each station is assigned an m-bit chip 
               sequence. A 1 is transmitted by sending the chip sequence. A 0 is transmitted by sending the complement. 
               [Typically, m=64 or 128.] 

               The complement turns every 1 into a 0 and every 0 into a 1 in the sequence. 

               Example: Suppose m=8, and A is assigned 00011011. Then, 1=00011011 and 0=11100100. The bandwidth of 
               each station is mB where B is the bandwidth required to send a single chip/bit; so, more bandwidth is 
               required. 

             b.Following Tanenbaum, we represent the chip sequences using +1 and -1 <-> 0, so that the chip sequence for 
               station A becomes -1 -1 -1 +1 +1 -1 +1 +1. 
             c.All chip sequences are pairwise orthogonal. 
 
 
 

             e.In the example shown here where 4 stations can transmit and six transmissions are recorded, we see that the 
               S[j] correspond to the sum of the different transmissions. The contribution of C to the sum can be determined 
               by dotting the S[j] with C. Thus, by knowing the chip sequence, the receiver can extract the signal of a 
               particular channel. 
 
 

               Fig. 4-16 (a)Binary chip sequences for four stations. (b) Bipolar chip sequences. (c) Six examples of 
               transmissions. (d) Recovery of station C's signal. 

             f.The principle advantages of this approach are: (1)By spreading the signal in time and frequency, it is less 
               succeptible to burst noise disturbances in either. (2)Since one must know the chip sequence to decode, 
               security is enhanced. 
   B.Multiple Access (Dynamic) Protocols 
        1.Pure ALOHA 
             a.Transmitters send frames whenever they want, and they monitor the channel to look for collisions. In LAN's, 
               they now immediately; in sattelites, there is a delay. If there is a collision, then the two senders must 
               retransmit after a random delay. If we assume a fixed frame size (because it maximizes throughput and 
               simplifies the analysis), then the vulnerable window is 2t, where t is the frame size. 
 
 
 

             b.It is reasonable to assume that the user community puts out frames at a rate of S (average rate) per frame 
               time. In this case 0 < S < 1. [If S > 1, then the channel is overloaded.] If transmissions are random, then the 
               frame arrivals are Poisson distributed. 

               Formula: 
 

               The maximum occurs at G = 0.5 with S = (1/2)e ~ 0.184 

               Maximum Utilization ~ 18% (not great!) 

        2.Slotted ALOHA: A simple improvement that helps a lot is to demand that the users send frames in slots. In that 
          case, the vulnerable window decreases from 2G to G, so that S = Ge^(-6) which has a maximum of 0.368 at G = 1.0, 
          implying that the best utilization is up to 37% (At this point, 37% of the slots are also empty and 26% have collisions). 
        3.Carrier Sense Multiple Access (CSMA) Protocols: In LAN's, where it is possible to sense almost immediately if a 
          channel is being used, it makes sense to use this knowledge (carrier sense) to avoid collisions. 
             a.1-persistant CSMA: In this case, the protocol waits until the channel is free and then tries to transmit. If there 
               is a collision (which can happen if two stations want to start transmitting at the same time), then they wait a 
               random time and start over. 
             b.Non-persistant CSMA: Rather than sensing the channel continually, the protocol tries again after a random 
               time interval. This approach leads to longer delays but fewer collisions. 
             c.p-persistant CSMA: When a slot is free, a frame is transmitted with probability p. With probability of 1-p, the 
               stations defer to the next slot and so on until the channel is busy or it transmits. When the channel is busy, it 
               acts just like it would with a collision: it waits a random amount of time and starts again. 
 
 

               Fig. 4-4 Comparison of the channel utilization versus load for various random access protocols. 

        4.CSMA/CD (CSMA with collision detection): After a collision has occured, it does not make much sense to keep 
          transmitting a frame since it is garbled anyway--particularly in a LAN where collision detection is nearly immediate. 
          Instead in LAN protocols like ethernet, the system will abort transmission after detecting a collision and try again 
          after a random period, assuming another channel has not started. Contention periods last 2t, the distance for a signal 
          to propagate back and forth on the LAN. Special encoding can be used to unambiguously recognize collisions. [Two 
          zeros at 0 volts would not be recognized, but two ones at 5 volts would produce 10 volts.] 
 
 
 

        5.Collision-free Protocols 
             a.For some networks, any collisions can be a big problem, e.g., optical fiber networks with long propagation 
               distances (large t) and short frames. Protocols with a designed contention period in which users reserve the 
               next transmission period are one possible solution. 
             b.Bit-map protocol: In this approach, a bit slot is reserved for every member of the network during the 
               contention period. A user that wants to transmit puts a 1 in the slot. The frames are then transmitted in 
               numerical order. 
 
 
 

             c.Binary count-down: To avoid one bit per station, one can identify each station by its binary address so that 2^n 
               stations implies the use of n bits. 

               The stations all broadcast their high-order bits. If there is a 1 in the slot, all stations with a 0 in the slot drop 
               out, and one proceeds to the next highest-order slot. At the end, only one station remains. 

               After transmission, the numbers are permuted among stations from 0 - up to the successful transmitter for the 
               algorithm to remain fair. 
 
 
 

        6.Limited-contention Protocols 
             a.With light loads, CMSA protocols are more efficient than collision-free protocols since they avoid reservation 
               delays. At heavy loads, the opposite is true. 

               One can deal with this situation by dividing the stations into groups and reserving a slot for each group. Each 
               situation must only contend within the group for its slot. 

               The goal is to dynamically alter the number of stations in each group so at low loads there is a small number 
               of groups with many members (ultimately one group with all stations). At high load, there is a large number of 
               groups with a small number of members (ultimately one station per group). 
             b.Adaptive Tree Wall Protocols: After a successful transmission: (1)All stations can compete for the first slot 
               (0'th slot in Tanenbaum). If transmission occurs, fine. If not, (2) all stations under 2 can compete for slot 1. If 
               a collision occurs, (3) it is now node 3's turn and so on. (4) There are numerous ways to improve this basic 
               algorithm. 

               An obvious one: If q stations are expected to contend for each slot, then starting at 1 doesn't make sense. It is 
               better to start at the level L where there are q nodes; i.e., q = 2^L -> L = log[2] q 
 
 
 

   C.IEEE 802 LAN's and MAN's 
        1.The 802.x standards define LAN and MAN standards. These standards have also been adopted by ANSI, NIST, 
          and ISO and so are broadly accepted. They are divided as follows: 
             a.802.1: Introduces all standards and defines interface primitives. 
             b.802.2: Defines the LLC (Logical Link Control) like HDLC which runs the upper half of the data link layer. 
             c.802.3: CSMA/CD (ethernet) {LAN's} 
             d.802.4: Token bus {LAN's} 
             e.802.5: Toke ring {LAN's} 
             f.802.6: DQDB {MAN's} 

          Note: Strictly speaking, ethernet is an implementation of CMSA/CD. 

        2.Why three standards for LAN's? Briefly: Three different companies pushed three different standards to satisfy 
          different needs. 

          Xerox <-> Ethernet (w/DEC and Intel) 

          General Motors <-> Token bus 

          IBM <-> Token ring 

        3.802.3: CSMA/CD (Ethernet) 
             a.Cabling: There are four common kinds of cabling that differ in terms of length and expense. [UMBC uses a 
               lot of thin-net/10 Base 2.] 
 
 
 

             b.Topoplogy: Different topologies are possible (tree, linear, backbone) and if the system goes beyond the 
               allowed length repeaters must be installed. 
 
 
 

             c.Ethernet avoids having a high voltage for a 1 and a low voltage for a 0 because there is no way to tell an idle 
               user from a user transmitting a zero and leads to synchronization problems as well. For this reason, it uses 
               Manchester coding. 
 
 
 

                    In Manchester coding, a 1 is represented by a high-low and a 0 is represented by a low-high. 
                    In a variant referred to as Differential Manchester coding, a transition at the bit interval boundary 
                    indicates a zero and no transition inidicates a 1. 
                    The high signal is specified at +0.85 volts and the low signal is specified at -0.84 volts. 

                    Note: Signals are at 10 Mbits/sec. These are all physical layer issues. 

             d.MAC sublayer protocol: The frame components are: 
 
 
 

                    Preamble: 7 bytes of 10101010 used to synchronize clocks. 
                    Frame delimiter: 10101011 
                    Destination address: In addition to individual users (0...), the addresses can be multi-cast (1...) or 
                    broadcast (111...1). 
                    Length: Size of the data field (from 0 to 1500 bytes). 
                    Pad: Fills out frame to a minimum size of 64 bytes when the data field is less than 46 bytes. 
             e.Why a minimum length? Packets must be at least 2t in size where t is the end-to-end transmission time so that 
               a collision occurs and is detected before the transmission ends. In a 10 Mbps LAN, the maximum length is 
               2500 m with 4 repeaters (and their delay). 
             f.Binary exponential back-off: After a successful transmission, contention slots 2t in width are set aside. After 
               one collision, stations wait a time 0 or 1 before trying again. If there is another collision, they wait a time 0, 1, 
               2, or 3 before trying again. In general, after i collisions, a random number between 0 and 2^(i-1) is chosen. 
               This algorithm implies that if the number of colliding stations is small, then delay is low but if there are many, 
               then the number of spots among which the random choice is made expands rapidly. 
             g.As more stations are added, traffic will eventually saturate the LAN. Rather than replace all the cards in the 
               computer, one can replace the backbone with a switch. The switch has a high-speed backplane. The 
               backplane has cards which connect to the hosts. There are two levels of contention: 
                    The hosts contend for the card. 
                    The cards contend for the backplane. 
                    If a host wants to transmit to another host or the same card, there is no contention on the backplane. 
                    When hosts on the same card collide, one might be buffered. 

               This approach enhances performance over a single connection shared by all. 

        4.802.4: Token Bus 
 
 
 

             a.CSMA/DC (ethernet) can lead to unbounded transport times for frames and has no way to prioritize frames. 
               Rings solve this problem because the time scale is bounded, but the topology is not suited to assembly lines. 
               This problem is solved by using a physical bus. 

               Note that physical and logical topology do not have to be the same! 

             b.When the ring is initialized, the highest-numbered node has the "token" first. When it finishes transmitting, it 
               passes the "token" to a neighbor, by sending a special control frame. The neighbor can now transmit. Since 
               only one host can transmit at any time, collisions are avoided. 
             c.The physical layer uses 75-ohm broadband coaxial cable (just like in cable tv). A variety of analog modulation 
               formats can be used--see Tanenbaum for details. 
             d.This protocol has four different priorities. When a host gets the token, its highest priority frames go first until 
               they are done or the highest priority times out. Then the next highest priority goes, etc., until the station as a 
               whole times out. 
             e.MAC sublayer components: 
 
 
 

                    The preamble: In this case, is as short as one byte. 
                    Start and End Delimiters: Contain symbols different from 1 and 0. No length byte is needed because of 
                    the two delimiters. 
                    Frame Control: Distinguishes data from control frames; contains priority information for data frames; 
                    contains an indicator allowing hosts to acknowledge receipt of data. 
             f.Managing new hosts coming into or out of the network and managing the network when the token is lost or its 
               holder goes down so that it has to be regenerated or when a successor station goes down or a duplicate 
               appears is a complicated business. See Tanenbaum for details. 
             g.Note: While there is no contention for control of bandwidth, there is contention to enter the ring and contention 
               to control the token when it begins its rounds. 
        5.802.5: Token Ring 
             a.Ring networks which are physically rings have some nice features: 
                    They are a concatenation of point-to-point links. 
                    They are largely digital since there is no collision detection which requires analog components. 
                    Token rings are fair, guaranteeing everyone access. 
             b.The physical bit length is a major issue. A 1 Mbps, 1000 meter ring can only contain five bits on it at once. 
 
 
 

             c.Every host has an interface to the ring with a one bit buffer to read in and act on the bit. This buffer 
               introduces a one bit delay. 
             d.When the ring is idle, a token continually circulates. When a host wishes to transmit, it "removes" the token by 
               inverting one bit of the three byte token to turn it into the "start frame" delimiter. 

               Note: A token ring must have sufficient delay to fit the whole token. If interfaces power down at night, then 
               the one bit delay is lost and the ring can become too short. In that case, an artificial delay must be inserted. 

             e.Acknowledgments can be inserted by the recipient after the checksum. 
             f.Data is removed by the sender after one pass through the system. 
             g.Physically, the token ring uses twisted wire pair and differential Manchester Coding at +- 3.0 - 4.5 volts. 
               High-high and low-low are used for control. 
             h.To avoid destroying the ring when one cable goes out, the hosts are normally connected through a wire center 
               which can switch out bad connections. 
 
 
 

              i.MAC Sub-layer Protocol: 
 
 
 

                    Start and End Delimiters: This contains invalid Manchester patterns (high-high and low-low) to 
                    distinguish them from data. 
                    Access Control: This contains bits that are used for reservation and priority to get access to the token. 
                    Higher priority frames are allowed to "reserve" the token using a mechanism described by Tanenbaum. 
                    Frame Control: Distinguishes data from various control frames. 
                    Frame Status: Used by the recipient to say whether the frame got where it was supposed to or not (it 
                    starts out as 0-0). 

                    A=0, C=0: destination not available 

                    A=1, C=0: destination available, but frame rejected 

                    A=1, C=1: destination available and frame accepted 

                    Where A & C refer to bits. Since these are not protected by the checksum, they are repeated. 

              j.802.5 uses a monitor to clean up orphan frames (frames that are left when a host crashes), taking care of lost 
               tokens, and fixing ring breaks. 

               Any host can become the monitor. If a host notices that there is no monitor, it can send out a CLAIM 
               TOKEN control frame. If it goes all the way around, that host becomes a monitor. 

               A sick monitor sending out ACTIVE MONITOR PRESENT signals is a potential source of trouble. 

               Note: Token bus has no monitors which complicates life, but is presumably more reliable. [Tanenbaum sounds 
               sceptical.] 

        6.802.6: DQDB (Distributed Queue Dual Bus) 
             a.This is a MAN, not a LAN and is meant to connect metropolitan areas. It operates from dual buses that 
               snake through a city in parallel. Each bus has a head end that sends out a string of 53 byte cells which push 
               by all the hosts and drop off the end. Since each bus is uni-directional, when one host wishes to transmit to 
               another, it must know where the host is and transmit on the appropriate bus. (If B wants to send to A, it sends 
               on bus B. If B wants to send to D, it sends on bus A). 
 
 
 

             b.Each cell holds 2 protocol bits: BUSY (which indicates that a cell is occupied) and REQUEST (which is set 
               when a station wants to transmit. 
             c.The protocol is "polite" (Tanenbaum's language). Each station maintains two counters: RC = Request Counter 
               and CD = Count Delay, which are used to set up a FIFO (first-in, first-out). This idea is different from the 
               LAN's in which stations transmit whenever they can. 
             d.The procedure is as follows: 
                    Initially RC = 0 for all hosts. 
                    A station (d) sends a request on the reverse bus from which it intends to transmit. All stations 
                    downstream set their RC. 
                    Suppose another station (B) wishes to transmit. It copies RC into CD and sets RC = 0. All 
                    downstream RC's are incremented. 
                    When the head end generates a cell, the cell CD = 0 transmits (D) and all others decrement CD. In 
                    our example, B's CD -> 0 so that B transmits in the next round. 
             e.Typical distances are 160km and typical speeds are 44Mbps (T1 line). 
   D.Bridges 
        1.Organizations typically run several LAN's and wish to interconnect them. 
             a.To connect LAN's that have different formats (802.3 and 802.5). 
             b.To connect across distances where a single LAN cannot run. 
             c.To reduce overload on the LAN (the separate LAN's do not share the transmission medium and do not 
               contend with each other). 
             d.To increase reliability (a defective host cripples only its own LAN) and security (a host on one LAN cannot 
               automatically listen in on all the conversations in another LAN). 
        2.Connecting between different 802.x frames is quite difficult. 
             a.The maximum lengths are different and an acceptable length on one cannot be accepted on another. 

               Note: Bridges cannot solve this problem which must be resolved at the network layer. 

             b.Timely receipt of acknowledgments is a problem. 
             c.What to do about priority is a problem (802.3 doesn't have it; 802.4 and 802.5 do, but they are handled in very 
               different ways). 
             d.Compatible frame formats require considerable processing. 
 
 
 

               Note: Tanenbaum discusses all these issues in great detail. 

        3.Transparent Bridge/Spanning Tree Bridge 
             a.This bridge requires no changes in the LAN's themselves; "plug it in and walk away," according to 
               Tanenbaum. 
             b.The bridges operate promiscuously, accepting every frame from every LAN to which it is attached. If a 
               frame from A destined for B arrives at B1, it is discarded; if it is for G, it must be forwarded. To know where 
               to forward the frame, it looks up the destination on a "hash" table to see which line the packet should be 
               forwarded on. 
             c.At first, when bridges are turned on, the hash tables are empty. Frames are delivered by flooding; they are 
               sent out on all LAN's except in the incoming one. Example: If D sends a frame to C, it is snt out to LAN2 and 
               LAN4. 
             d.Bridges build their hash table by backward learning. When B2 gets a frame from C, then it knows that C is 
               reachable from LAN2 and from then on only sends frames for C there. To deal with topology changes, 
               entries that are more than a few minutes old are periodically purged. 
             e.If two bridges form a "loop", then it is possible for flooding to create an infinite loop. 
             f.To avoid this problem, the bridges create a spanning tree, in which some physical connections (bridges) are 
               ignored so that there is a single path from any LAN to any other LAN. To build the tree: 
                    All bridges broadcast their serial numbers; the low number wins and is the root of the tree. 
                    A tree of shortest paths from the root to every other bridge is created. 
 
 
 

        4.Tanenbaum discusses another bridge approach called source routing which is not transparent. 
   E.High-Speed LAN's 
        1.A need has developed for higher speed, longer-distance LAN's at about 100 Mbps. A number of approaches, most 
          fiber-based, have developed. 
        2.FDDI (Fiber Distributed Data Interface) 
 
 
 

             a.It is based on multi-mode fiber using light-emitting diodes, rather thatn single mode fiber with laser diodes 
               (cheaper and safer but limits distances to 200km). There are two counter-rotating rings for robustness against 
               line breaks. 
             b.To reduce the signaling bandwidth, 4 out of 5 encoding is used instead of Manchester Coding. 16 of 32 bit 
               combinations are used for data coding, 8 are used for delimiters, control and signaling, and 8 are unused. A 
               long preamble and carefully controlled clocks are used to maintain synchronization. 
             c.The frame format and protocol is close to 802.5. Differences are that: 
                    The token is put n the ring once transmission is finished so that several frames can be on the ring at 
                    once. 
                    Priority is handled like 802.4 (which is fairer than 802.5's approach). 
                    There is an asynchronous mode which allows circuit-switched PCM or ISDN frames to be 
                    transmitted. 
        3.Fast Ethernet (802.3u) 
             a.FDDI has proved too expensive for the mass market, although it is often used in backbones. Fast ethernet is 
               an upgrade of ethernet to 100 Mbps. 
             b.Different wiring solutions are allowed to make it possible to use category 3 UTP twisted pair. In this case, the 
               basic signaling speed is 25Mhz, only 25% fster than the 20Mhz required for standard ethernet. BUT: four 
               twisted pairs are used--three in the transmission direction. Also, ternary signaling is used, thus allowing 27 
               symbols to be sent per clock period which is sufficient for 4 bits (16 symbols), allowing 100Mhz to be sent. 
               Fiber and category 5 wiring use simpler physical coding. 
             c.Hubs must be used; they can be shared or switched. 
        4.HIPPI - High Performance Parallel Interface 
             a.This is a high-performance interface to connect super-computers. The initial specification was for 800 Mbps 
               because video requires frames of 1024x1024 pixels with 24 bits per pixel and 30 frames/sec = 750Mbps. 
             b.It has been upgraded to 1600Mbps as an option. 
             c.A HIPPI contains 50 twisted pairs and every 40ns, a word with 32 bits of data and 18 bits of control is sent 
               across the interface. Transfer is simplex; so, two-way communication requires two cables. Distances are 25 
               meters. 
             d.Frames consist of 256 words and error checking is done a horizontal parity bit per word and a vertical parity 
               word at the end of the frame. Checksums were considered too slow and expensive.