// PupAlEIAb.bcpl - Pup level 0 driver for EIA interface // Copyright Xerox Corporation 1979 // Last modified January 30, 1979 1:29 PM by Boggs get "Pup0.decl" get "PupAlEIA.decl" external [ // outgoing procedures EncapsulateEIAPup; SendEIAPacket; SendEIAStats EIAInputDone; EIAOutputDone EIAProcess; EIAPupFilter; EIARoutingFilter // incoming procedures Enqueue; Dequeue; Dismiss; Min; MultEq; DoubleIncrement SetTimer; TimerHasExpired; MoveBlock StartEIAT; StopEIAT; StartEIAR; StopEIAR // incoming statics pbiFreeQ; lenPup; eiaNDB; eiaLT ] //---------------------------------------------------------------------------- let EncapsulateEIAPup(pbi, pdh) be //---------------------------------------------------------------------------- // Performs EIA dependent encapsulation // pbi points at a PBI // pdh is physical destination host for Pup [ pbi>>EIAPBI.dest = pdh pbi>>EIAPBI.type = typePup pbi>>EIAPBI.broadcast = pdh eq 0 pbi>>EIAPBI.allLines = false pbi>>PBI.packetLength = (pbi>>PBI.pup.length+3) & #177776 ] //---------------------------------------------------------------------------- and SendEIAPacket(pbi) be //---------------------------------------------------------------------------- // Routes packet to host given in EIAPBI.dest via some line. // Sends broadcast packets out all lines that are up. // Packets to self are routed through a looped-back line, if any. [ test pbi>>EIAPBI.allLines % pbi>>EIAPBI.broadcast ifso EIAOutputDispose(pbi, 0) //send first on line 0 ifnot [ let rte = eiaNDB>>EIANDB.rt^(pbi>>EIAPBI.dest) test pbi>>EIAPBI.dest le maxHost & //host in range? rte<>PBI.queue, pbi) //no, discard ] ] //---------------------------------------------------------------------------- and SendEIAStats(pbi, ndb) = valof //---------------------------------------------------------------------------- [ pbi>>PBI.pup.length = pupOvBytes + lenSLAStats let stats = lv pbi>>PBI.pup.words stats>>SLAStats.statsType = netTypeSLA stats>>SLAStats.statsVersion = slaStatsVersion stats>>SLAStats.maxHost = maxHost MoveBlock(lv stats>>SLAStats.rt^1, lv ndb>>EIANDB.rt^1, maxHost) stats>>SLAStats.maxLine = maxLine for line = 0 to maxLine do MoveBlock(lv stats>>SLAStats.lineStats^line, lv ndb>>EIANDB.lcb^line.stats, lenSLAStats) resultis true ] //---------------------------------------------------------------------------- and EnqueueEIAOutput(pbi, line) be //---------------------------------------------------------------------------- // Enqueues pbi on output queue for line, then starts output if required. [ let lcb = lv eiaNDB>>EIANDB.lcb^line // Decide whether high- or low-priority packet. // Non-Pups (ie, just routing tables at present) are always high-priority. // Pups are high-priority iff Pup length le maxHiPriBytes and there are not // any already-queued low-priority Pups with same source and destination. // The latter check is made so as to avoid scrambling packets belonging // to a single conversation. let high = valof [ if pbi>>EIAPBI.type ne typePup resultis true //non-Pup if pbi>>PBI.pup.length gr maxHiPriBytes resultis false //large Pup let curr = lcb>>LCB.lowOQ.head while curr ne 0 do [ // Search for low-priority Pup with same source and destination. if MultEq(lv curr>>PBI.pup.dPort, lv pbi>>PBI.pup.dPort, 2*lenPort) then resultis false //found one, make new pbi low-priority also curr = curr!0 ] resultis true ] Enqueue((high? lv lcb>>LCB.highOQ, lv lcb>>LCB.lowOQ), pbi) // Start output if necessary StartEIAOutput(lcb) ] //---------------------------------------------------------------------------- and StartEIAOutput(lcb) be //---------------------------------------------------------------------------- // Starts output if line is idle and there is a packet waiting to go out. [ if lcb>>LCB.oPBI eq 0 then [ // Output not already active, try to dequeue a pbi. // Check the high-priority queue first, then the low. lcb>>LCB.oPBI = Dequeue(lv lcb>>LCB.highOQ) if lcb>>LCB.oPBI eq 0 then lcb>>LCB.oPBI = Dequeue(lv lcb>>LCB.lowOQ) if lcb>>LCB.oPBI ne 0 then [ // Now idle, start transmitter StartEIAT(lcb) // Compute timeout on the basis of worst-case transmission time // at 2160 baud (2400 baud minus 10% for multiplexor overhead and slop). // Timeout = (2*packetLength+frameOverheadBytes) / 270 seconds // = 10 * (2*packetLength+frameOverheadBytes) / 27 timer ticks (10 ms). // We use 2*packetLength in case every byte is a DLE that is doubled. // 270 bytes/second corresponds to 2160 baud. SetTimer(lv lcb>>LCB.tTimer, (10*(2 * lcb>>LCB.oPBI>>PBI.packetLength + frameOverheadBytes))/27) ] ] ] //---------------------------------------------------------------------------- and EIAOutputDone(lcb) be //---------------------------------------------------------------------------- // Called from interrupt level after a packet has been sent. [ DoubleIncrement(lv lcb>>LCB.transmitPackets) DoubleIncrement(lv lcb>>LCB.transmitBytes, lcb>>LCB.oPBI>>PBI.packetLength) EIAOutputDispose(lcb>>LCB.oPBI, lcb>>LCB.line+1) lcb>>LCB.oPBI = 0 StartEIAOutput(lcb) ] //---------------------------------------------------------------------------- and EIAOutputDispose(pbi, firstLine) be //---------------------------------------------------------------------------- // Called to dispose of a pbi possibly being sent to multiple lines. // If pbi is going to all lines, send it to firstLine (if in range). // If pbi is a broadcast Pup, send it to the first line ge // firstLine that is up. [ if pbi>>EIAPBI.allLines % pbi>>EIAPBI.broadcast then for line = firstLine to maxLine do if eiaLT>>EIALT.eiaLTE^line.exists & (pbi>>EIAPBI.allLines % (lv eiaNDB>>EIANDB.lcb^line)>>LCB.state ne slaLineDown) then [ EnqueueEIAOutput(pbi, line) return ] Enqueue(pbi>>PBI.queue, pbi) //no more lines to output to ] //---------------------------------------------------------------------------- and EIAInputDone(lcb) be //---------------------------------------------------------------------------- //called from interrupt level after a packet has arrived. [ let pbi = lcb>>LCB.iPBI pbi>>PBI.ndb = eiaNDB pbi>>EIAPBI.line = lcb>>LCB.line DoubleIncrement(lv lcb>>LCB.receivePackets) DoubleIncrement(lv lcb>>LCB.receiveBytes, pbi>>PBI.packetLength) let pf = eiaNDB>>EIANDB.pfQ.head while pf ne 0 do [ if (pf>>PF.predicate)(pbi) then [ lcb>>LCB.iPBI = 0 Enqueue(pf>>PF.queue, pbi) break ] pf = pf>>PF.link ] ] //---------------------------------------------------------------------------- and EIAPupFilter(pbi) = //---------------------------------------------------------------------------- pbi>>EIAPBI.type eq typePup & pbi>>PBI.packetLength eq ((pbi>>PBI.pup.length+3) & #177776) //---------------------------------------------------------------------------- and EIARoutingFilter(pbi) = pbi>>EIAPBI.type eq typeRoute //---------------------------------------------------------------------------- //---------------------------------------------------------------------------- and EIAProcess() be //---------------------------------------------------------------------------- // This background process maintains an internal routing table, // times out hung transmitter lines, and restarts reception on lines that // ran out of PBIs. // The routing algorithm is similar to that used in the Arpanet, // but with a modification that permits keeping less local state. // The state we maintain is simply a line number and a hop count // for every destination host. When a routing table is received // from a neighbor over a line l, we simply purge all entries in // our own routing table that route out over line l, then replace // entries in our routing table with corresponding ones in the // incoming table iff the incoming entry's hop count +1 is le ours. // The test is "le" rather than "ls" so that in the long run we will // spread the load among all equally-good routes. // Purged entries have a hop count of "infinity" = #377. // When a line or neighbor goes down (no routing table received // for some timeout), we purge all entries routing out through // that line. If there is an alternate path to some purged // destination, we will discover that eventually, when some other // neighbor tells us about it, whereas in the Arpanet algorithm // the alternate path is usually known immediately since the // number of hops to a given destination through each line // is kept, and hence a new routing can be computed immediately. // Our algorithm, however, requires only (number of hosts) entries // in the routing table, whereas the Arpanet algorithm requires // an array of size (number of hosts)*(number of lines). // A special case we handle is that of a looped-back line // (detected when we receive our own routing table over that line). // In this case, we set up our own entry in the routing table // to route out over that line (with 1 hop), since this is useful // for the purpose of testing the line. However, when we send // our routing table to a neighbor, we zero our own entry's hop // count in the copy we give him so that the normal routing table // update process works correctly. [ let rtTimer = nil; SetTimer(lv rtTimer, 0) [ Dismiss(10) // 100 ms if eiaNDB>>EIANDB.rIQ.head ne 0 then [ //received a routing table let pbi = Dequeue(lv eiaNDB>>EIANDB.rIQ) let line = pbi>>EIAPBI.line let lcb = lv eiaNDB>>EIANDB.lcb^line SetTimer(lv lcb>>LCB.rTimer, routingTimeout) PurgeLineFromRT(line) //purge all entries routing to line test pbi>>RTPBI.srcHost eq eiaNDB>>NDB.localHost ifso [ //received my routing table, line is looped back lcb>>LCB.state = slaLineLoopedBack let rte = lv eiaNDB>>EIANDB.rt^(eiaNDB>>NDB.localHost) rte>>RTE.line = line //route to myself via this line rte>>RTE.hopCnt = 1 ] ifnot [ //received a neighbor's routing table lcb>>LCB.state = slaLineUp for i = 1 to Min(maxHost, pbi>>RTPBI.numEntries) do [ let rte = lv eiaNDB>>EIANDB.rt^i let newHop = pbi>>RTPBI.rt^i.hopCnt+1 if newHop le rte>>RTE.hopCnt then [ rte>>RTE.hopCnt = newHop le maxHops? newHop, #377 rte>>RTE.line = line ] ] ] Enqueue(pbiFreeQ, pbi) ] // EIAProcess (cont'd) for line = 0 to maxLine do if eiaLT>>EIALT.eiaLTE^line.exists then [ //flush routing entries for dead lines let lcb = lv eiaNDB>>EIANDB.lcb^line if TimerHasExpired(lv lcb>>LCB.rTimer) then [ lcb>>LCB.state = slaLineDown PurgeLineFromRT(line) ] if TimerHasExpired(lv lcb>>LCB.tTimer) & lcb>>LCB.oPBI ne 0 then while lcb>>LCB.oPBI ne 0 do // Transmitter is hung. [ // Stop it and dispose of all pbis queued for this line. // Note that EIAOutputDone will cause the hardware to be // started for each pbi discarded, but since the line is // dead that doesn't really matter. StopEIAT(lcb) EIAOutputDone(lcb) ] // Restart reception for a line that ran out of input PBIs. if lcb>>LCB.iPBI eq 0 then [ lcb>>LCB.iPBI = Dequeue(pbiFreeQ) if lcb>>LCB.iPBI ne 0 then StartEIAR(lcb) ] ] if TimerHasExpired(lv rtTimer) then [ //time to broadcast our level 0 routing table let pbi = Dequeue(pbiFreeQ); if pbi ne 0 then [ SetTimer(lv rtTimer, routingProbeInterval) pbi>>PBI.queue = pbiFreeQ pbi>>EIAPBI.allLines = true pbi>>EIAPBI.type = typeRoute MoveBlock(lv pbi>>RTPBI.rt, lv eiaNDB>>EIANDB.rt, maxHost*lenRTE) pbi>>RTPBI.rt^(eiaNDB>>NDB.localHost) = 0 pbi>>RTPBI.srcHost = eiaNDB>>NDB.localHost pbi>>RTPBI.numEntries = maxHost pbi>>PBI.packetLength = lenRTPacket*2 SendEIAPacket(pbi) ] ] ] repeat ] //---------------------------------------------------------------------------- and PurgeLineFromRT(line) be //---------------------------------------------------------------------------- [ for j = 1 to maxHost do if eiaNDB>>EIANDB.rt^j.line eq line then eiaNDB>>EIANDB.rt^j.hopCnt = -1 ]