// 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<<RTE.hopCnt ne #377 //can get there from here?
ifso EnqueueEIAOutput(pbi, rte<<RTE.line) //yes, send
ifnot Enqueue(pbi>>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
]