<PAGE>

                                                                     EXHIBIT 4.5

                    STOCKHOLDER AGREEMENT dated as of August 9, 1999 (this
               "Agreement"), between LUCENT TECHNOLOGIES INC., a Delaware
               corporation ("Lucent"), and the stockholders listed on Schedule A
               attached hereto (collectively, the "Stockholder").



          WHEREAS Lucent, Intrepid Merger Inc., a Delaware corporation and a
wholly owned subsidiary of Lucent ("Sub"), and International Network Services, a
Delaware corporation (the "Company"), propose to enter into an Agreement and
Plan of Merger dated as of the date hereof (as the same may be amended or
supplemented, the "Merger Agreement"; defined terms used but not defined herein
have the meanings set forth in the Merger Agreement), providing for, among other
things, the merger of Sub with and into the Company, upon the terms and subject
to the conditions set forth in the Merger Agreement;

          WHEREAS the Stockholder beneficially owns the number of shares of
capital stock of the Company set forth opposite the Stockholder's name on
Schedule A attached hereto (such shares of capital stock of the Company,
together with any other shares of capital stock of the Company acquired by the
Stockholder after the date hereof and during the term of this Agreement
(including through the exercise of any stock options, warrants or similar
instruments), being collectively referred to herein as the "Subject Shares");
and

          WHEREAS as a condition to its willingness to enter into the Merger
Agreement, Lucent has requested that the Stockholder enter into this Agreement.


          NOW, THEREFORE, to induce Lucent to enter into, and in consideration
of its entering into, the Merger Agreement, and in consideration of the premises
and the representations, warranties and agreements contained herein, the parties
hereto agree as follows:

          1.  Agreement to Vote Shares.  The Stockholder agrees during the term
              ------------------------
of this Agreement to vote, or cause to be voted, its Subject Shares, in person
or by proxy, (i) in favor of the Merger, the adoption and approval of the Merger
Agreement and the approval of the transactions contemplated by the Merger
Agreement at every meeting of the stockholders of the Company at which such
matters are considered and at every adjournment thereof and (ii) in such manner
as Lucent may direct with respect to all other
<PAGE>

                                                                               2


proposals submitted to the stockholders of the Company which, directly or
indirectly, in any way relate to the Merger; provided, however, that clause (ii)
                                             --------  -------
of this Section 1 shall not be construed to require any action which would
contravene paragraph 47(c) of Opinion 16 of the Accounting Principles Board and
applicable SEC rules and regulations.

          2.  Grant of Irrevocable Proxy.  The Stockholder hereby irrevocably
              --------------------------
grants to, and appoints, Pamela F. Craven and Jean F. Rankin and any other
individual who shall hereafter be designated by Lucent, and each of them, the
Stockholder's proxy and attorney-in-fact (with full power of substitution), for
and in the name, place and stead of the Stockholder, to vote, or cause to be
voted, the Stockholder's Subject Shares, or grant a consent or approval in
respect of such Subject Shares, at any meeting of stockholders of the Company or
at any adjournment thereof or in any other circumstances upon which their vote,
consent or other approval is sought, in favor of the Merger, the adoption and
approval of the Merger Agreement and the approval of the transactions
contemplated by the Merger Agreement.

          3.  No Other Grant of Proxy.  The Stockholder will not, directly or
              -----------------------
indirectly, grant any proxies or powers of attorney with respect to his Subject
Shares to any person in connection with or directly affecting the Merger other
than as set forth in Section 2.

          4.  Transfers.  Other than this Agreement, the Stockholder will not,
              ---------
nor will the Stockholder permit any entity under the Stockholder's control to,
sell, transfer, pledge, assign or otherwise dispose of (including by gift)
(collectively, "Transfer"), or consent to any Transfer of, any Subject Shares or
any interest therein or enter into any contract, option or other agreement or
arrangement (including any profit sharing or other derivative arrangement) with
respect to the Transfer of, any Subject Shares or any interest therein to any
person, unless prior to any such Transfer the transferee of such Subject Shares
enters into a stockholder agreement with Lucent on terms substantially identical
to the terms of this Agreement; provided, however, that such restriction shall
                                --------  -------
not be applicable to any of the Subject Shares that have been pledged by the
Stockholder pursuant to a margin loan account prior to the date of this
Agreement.

          5.  No Voting Trusts.  The Stockholder agrees that it will not enter
              ----------------
into any voting trust or other arrangement or agreement with respect to the
voting of the Subject Shares (and if entered into or executed, such voting trust
or other arrangement or agreement shall not be effective),
<PAGE>

                                                                               3

or agree, in any manner, to vote the Subject Shares for or against any proposal
in connection with or directly affecting the Merger submitted to the
stockholders of the Company except in furtherance of the proposals as set forth
in Section 1 hereof.

          6.  No Solicitation.  Until the Merger is consummated or the Merger
              ---------------
Agreement is terminated, the Stockholder shall not, nor shall he permit any
investment banker, attorney or other advisor or representative of the
Stockholder to, directly or indirectly through another person, solicit, initiate
or encourage, or take any other action to facilitate, any inquiries or the
making of any proposal that constitutes, or may reasonably be expected to lead
to, any Takeover Proposal.

          7.  Affiliate Agreement.  (a)  If, at the time the Merger Agreement is
              -------------------
submitted for approval to the stockholders of the Company, the Stockholder is
an "affiliate" of the Company for purposes of Rule 145 under the Securities Act
or for purposes of qualifying the Merger for pooling of interests accounting
treatment under Opinion 16 of the Accounting Principles Board and applicable SEC
rules and regulations, the Stockholder shall deliver to Lucent at least 30 days
prior to the Closing a written agreement substantially in the form attached as
Exhibit A to the Merger Agreement.

          (b)  The Stockholder shall use reasonable efforts to cause the
transactions contemplated by the Merger Agreement, including the Merger, to be
accounted for as a pooling of interests transaction under Opinion 16 of the
Accounting Principles Board and applicable SEC rules and regulations.  The
Stockholder agrees that it shall take no action that would cause such accounting
treatment not to be obtained.

          8.   Representations and Warranties of the Stockholder.  The
               -------------------------------------------------
Stockholder hereby represents and warrants to Lucent in respect of himself as
follows:

          (a)  Authority.  The Stockholder has all requisite power and authority
               ----------
to enter into this Agreement and to consummate the transactions contemplated
hereby.  This Agreement has been duly authorized, executed and delivered by the
Stockholder and constitutes a valid and binding obligation of the Stockholder
enforceable against the Stockholder in accordance with its terms.  The execution
and delivery of this Agreement do not, and the consummation of the transactions
contemplated hereby and compliance with the terms hereof will not, conflict
with, or result in any violation of, or default (with or without notice or lapse
of time or both) under any provision of, any trust agreement,
<PAGE>

                                                                               4

loan or credit agreement, note, bond, mortgage, indenture, lease or other
agreement, instrument, permit, concession, franchise, license, judgment, order,
notice, decree, statute, law, ordinance, rule or regulation applicable to the
Stockholder or to the Stockholder's property or assets. Except for informational
filings with the SEC, no consent, approval, order or authorization of, or
registration, declaration or filing with any Governmental Entity is required by
or with respect to the Stockholder in connection with the execution and delivery
of this Agreement or the consummation by the Stockholder of the transactions
contemplated hereby.

          (b)   The Subject Shares.  The Stockholder has good and marketable
                ------------------
title to the Subject Shares, free and clear of all Liens, except for the Subject
Shares that have been pledged by the Stockholder pursuant to a margin loan
account prior to the date of this Agreement.

          9.   Representations and Warranties of Lucent. Lucent hereby
               ----------------------------------------
represents and warrants to the Stockholder that Lucent has all requisite
corporate power and authority to enter into this Agreement and to consummate the
transactions contemplated hereby. The execution and delivery of this Agreement
by Lucent, and the consummation of the transactions contemplated hereby, has
been duly authorized by all necessary corporate action on the part of Lucent.
This Agreement has been duly executed and delivered by Lucent and constitutes a
valid and binding obligation of Lucent enforceable against Lucent in accordance
with its terms. The execution and delivery of this Agreement do not, and the
consummation of the transactions contemplated hereby and compliance with the
terms hereof will not, conflict with, or result in any violation of, or default
(with or without notice or lapse of time or both) under any provision of, any
trust agreement, loan or credit agreement, note, bond, mortgage, indenture,
lease or other agreement, instrument, permit, concession, franchise, license,
judgment, order, notice, decree, statute, law, ordinance, rule or regulation
applicable to Lucent or to Lucent's property or assets. Except for the
informational filings with the SEC, no consent, approval, order or authorization
of, or registration, declaration or filing with any Governmental Entity is
required by or with respect to Lucent in connection with the execution and
delivery of this Agreement or the consummation by Lucent of the transactions
contemplated hereby.

          10.  Enforcement.  The parties agree that irreparable damage would
               -----------
occur and that the parties would not have any adequate remedy at law in the
event that any of the provisions of this Agreement were not performed in
accordance with their specific terms or were otherwise
<PAGE>

                                                                               5

breached. It is accordingly agreed that the parties will be entitled to an
injunction or injunctions to prevent breaches of this Agreement and to enforce
specifically the terms and provisions of this Agreement in any Federal court
located in the State of Delaware or in Delaware state court, the foregoing being
in addition to any other remedy to which they are entitled at law or in equity.
In addition, each of the parties hereto (i) consents to submit itself to the
personal jurisdiction of any Federal court located in the State of Delaware or
any Delaware state court in the event any dispute arises out of this Agreement
or any of the transactions contemplated by this Agreement, (ii) agrees that it
will not attempt to deny or defeat such personal jurisdiction by motion or other
request for leave from any such court, and (iii) agrees that it will not bring
any action relating to this Agreement or any of the transactions contemplated by
this Agreement in any court other than a Federal court sitting in the State of
Delaware or a Delaware state court.

          11.  Term and Termination.  Subject to Section 16(f), the term of this
               --------------------
Agreement shall commence on the date hereof and shall terminate upon the earlier
of (i) the Effective Time and (ii) 10 business days after the termination of the
Merger Agreement in accordance with its terms.

          12.  Certain Events.  The Stockholder agrees that this Agreement and
               --------------
the obligations hereunder shall attach to the Stockholder's Subject Shares and
shall be binding upon any Person to which legal or beneficial ownership of such
Subject Shares shall pass, whether by operation of law or otherwise, including
the Stockholder's heirs, guardians, administrators or successors.  In the event
of any stock split, stock dividend, merger, reorganization, recapitalization
or other change in the capital structure of the Company affecting the Subject
Shares, or the acquisition of additional shares of the Company's capital stock
by the Stockholder, the number of Subject Shares listed on Schedule A beside the
name of the Stockholder shall be adjusted appropriately and this Agreement and
the obligations hereunder shall attach to any additional shares of the Company's
capital stock issued to or acquired by the Stockholder.

          13.  Stockholder Capacity.  No person executing this Agreement who is
               --------------------
or becomes during the term hereof a director or officer of the Company makes (or
shall be deemed to have made) any agreement or understanding herein in his or
her capacity as such director or officer.  Without limiting the generality of
the foregoing, the Stockholder signs solely in his capacity as the record and/or
beneficial owner, as applicable, of the Stockholder's Subject Shares
<PAGE>

                                                                               6

and nothing herein shall limit or affect any actions taken by the Stockholder
(or a designee of the Stockholder) in his capacity as an officer or director of
the Company in exercising his rights under the Merger Agreement.

          14.  Entire Agreement; No Third Party Beneficiaries; Amendment;
               ---------------------------------------------------------
Waiver.  This Agreement (including the documents and instruments referred to
------
herein) (i) constitutes the entire agreement and supersedes all prior agreements
and understandings, written or oral, among the parties with respect to the
subject matter hereof and (ii) is not intended to confer upon any Person other
than the parties hereto any rights or remedies hereunder.  This Agreement may
not be amended, supplemented or modified, and no provisions hereof may be
modified or waived, except by an instrument in writing signed by each party to
be charged. No waiver of any provisions hereof by any party shall be deemed a
waiver of any other provisions hereof by any such party, nor shall any such
waiver be deemed a continuing waiver of any provision hereof by such party.

          15.  Notices.  All notices, consents, requests, instructions,
               -------
approvals and other communications provided for herein shall be in writing and
shall be deemed to have been duly given if mailed, by first class or registered
mail, three business days after deposit in the United States Mail, or if telexed
or telecopied, sent by telegram, or delivered by hand or reputable overnight
courier, when confirmation is received, in each case as follows:

     If to the Stockholder, to the address listed on Schedule A hereto;

     If to Lucent, in accordance with Section 8.02 of the Merger Agreement;

or to such other persons or addresses as may be designated in writing by the
party to receive such notice.

          16.  Miscellaneous.  (a)  When a reference is made in this Agreement
               -------------
to Sections, such reference shall be to a Section of this Agreement unless
otherwise indicated.  The headings contained in this Agreement are for reference
purposes only and shall not affect in any way the meaning or interpretation of
this Agreement.  Wherever the words "include," "includes" or "including" are
used in this Agreement, they shall be deemed to be followed by the words
"without limitation".

          (b)  This Agreement shall be governed by, and construed in accordance
with, the laws of the State of Delaware regardless of the laws that might
otherwise govern under applicable principles of conflicts of laws.
<PAGE>

                                                                               7

          (c)  If any term or other provision of this Agreement is invalid,
illegal or incapable of being enforced by any rule of law or public policy, all
other conditions and provisions of this Agreement shall nevertheless remain in
full force and effect.  Upon such determination that any term or other provision
is invalid, illegal or incapable of being enforced, the parties hereto shall
negotiate in good faith to modify this Agreement so as to effect the original
intent of the parties as closely as possible to the fullest extent permitted by
applicable law in an acceptable manner and to the end that the transactions
contemplated hereby are fulfilled to the extent possible.

          (d)  This Agreement may be executed in one or more counterparts, all
of which shall be considered one and the same agreement, and shall become
effective when one or more of the counterparts have been signed by each of the
parties and delivered to the other parties, it being understood that each party
need not sign the same counterpart.

          (e)  This Agreement shall not be assigned by the Stockholder, on the
one hand, without the prior written consent of Lucent, or by Lucent, on the
other hand, without the prior written consent of the Stockholder, except that
Lucent may assign, in its sole discretion, any or all of its rights, interests
and obligations hereunder to any direct or indirect wholly owned subsidiary of
Lucent; provided that notwithstanding such assignment, Lucent shall remain
liable for performance of its obligations hereunder.  Subject to the preceding
sentence, this Agreement will be binding upon, inure to the benefit of and be
enforceable by the parties and their respective successors and assigns.

          (f)  The obligations of the Stockholder set forth in this Agreement
shall not be effective or binding upon the Stockholder until after such time as
the Merger Agreement is executed and delivered by Lucent, Sub and the Company.
<PAGE>

                                                                               8

          IN WITNESS WHEREOF, Lucent has caused this Agreement to be signed by
its officer thereunto duly authorized and the Stockholder has signed this
Agreement, all as of the date first written above.


                                        LUCENT TECHNOLOGIES INC.,

                                           by
                                              /s/ Patricia F. Russo
                                              ---------------------------
                                              Name:  Patricia F. Russo
                                              Title: Executive Vice
                                                     President, Strategy
                                                     and Corporate
                                                     Operations


                                        STOCKHOLDERS:


                                              /s/ Donald K. McKinney
                                              ---------------------------
                                              Donald K. McKinney


                                        THE MCKINNEY FAMILY TRUST,

                                            by
                                              /s/ Donald K. McKinney
                                              ---------------------------
                                              Donald K. McKinney, Trustee
<PAGE>

                                                                      SCHEDULE A




                                 Number of               Percentage of
                                Outstanding             Voting Power of
       Stockholder              Shares Owned              the Company
       -----------              ------------              -----------

Donald K. McKinney               1,316,999 /1/                2.28%

Donald K. McKinney,             14,473,465                   25.07%
Trustee of the McKinney
Family Trust



--------------------------
        /1/ Includes 416,999 shares subject to options which are exercisable
within 60 days of the date of this Agreement.